이번에는 over-squashing 현상을 해결할 수 있는 graph rewiring의 알고리즘적 접근법에 대해서 알아볼 것이다. 이전에는 이론적인 접근법들을 살펴보았는데, 이번에는 알고리즘적으로 어떻게 접근해서 over-squashing 현상을 완화할 수 있는지 알아보자. ICML 2023에 나온 방법에 대해서 알아볼 것이며, 이는 graph rewiring을 단순히 수행하기보다는 dynamic graph rewiring을 수행하는 것이 더 효과적이라 이야기했다. 이 방법은 over-squashing 문제를 해결하는 방법으로 edge를 아무 곳이나 추가해도 된다고 한다. 만약 정보가 잘 흐르지 않는 vertex 쌍이 있다고 하면 여기에 edge를 추가할 수 있을 것이다. 하지만 over-squashing과 over-smoothing 사이에는 고유한 trade-off가 존재한다. Graph에 edge를 추가하게 되면 graph가 전체적으로 더 평균화가 되어 over-smoothing 현상에 더 민감해질 것이다. Graph의 크기가 커짐에 따라 학습 시간도 증가할 것이다. 그리고 rewiring task를 하게 되면 input graph를 수정하게 되는데, 이에 따라 기존의 정보들을 잃을 수도 있다.
Graph rewiring algorithm이 graph가 주어졌을 때 over-squashing 현상을 해결하기 위해서 어떻게 graph를 수정해야하는지와 관련이 있다. 그러나 이 dynamic graph rewiring을 제안한 저자들은 graph rewiring을 단순히 수행하기보다는 GNN의 서로 다른 layer 사이에 edge를 추가하자는 것이었다. 그래서 layer마다 graph 사이에 connection을 추가할 수 있다. 0번째 layer에서 1번째 layer에 edge를 추가하기도 하고, 0번째 layer에서 2번째 layer로 edge를 추가하기도 한다. 이는 어떻게 보면 residucal connection과 비슷한 방법이지만, 이 방법은 동일한 vertex 사이가 아닌 다른 vertex와 connection을 추가하는 방법이다.
그래서 정보를 aggregation할 때 이전 layer뿐만 아니라 만큼 떨어진 이웃들에 대해서 layer에도 수행하게 된다. 만약 3개의 layer 이전부터 정보를 모은다고 하면 결국 3-hop 떨어진 이웃들로부터 정보를 모으는 것과 같아지게 된다. 여기서 factor를 infinity로 하면 원래의 rewiring 기술과 같아지게 된다. 결국 이러한 방법은 기존의 rewiring 방법의 generalization 버전인 것이다.
이들이 제안한 방식의 장점은 graph가 더 효율적인 framework를 만들기 위해서 각 layer에 점진적으로 채워진다는 것이다. 그리고 더 가까운 node는 일찍부터 상호작용하기 때문에 input graph로부터 inductive bias를 보존할 수 있다. 이는 단순히 멀리 떨어진 vertex 사이에 임의의 edge를 추가하는 것과는 다르다. 이전에는 사람들이 멀리 떨어진 vertex 쌍을 선택해서 이들 사이를 연결하려는 시도를 하였지만, 이번에 살펴보는 이 방법은 -hop neighbor connection을 기반으로 이루어지기에 기존의 정보를 더욱 잘 보존하게 된다. 이러한 방식은 결국 over-smoothing 현상 또한 완화하는데 이점을 가지게 된다. 비록 멀리 떨어진 vertex를 연결한다고 하더라도 서로 다른 layer를 통해서 연결하기 때문에 smoothing 현상이 발생할 가능성이 낮아지게 된다.
이 방법은 또한 long-range dependency를 가지는 새로운 graph benchmark를 소개하여 유명해지기도 했다. 이 dataset은 GNN이 long-range dependency를 인지할 수 있는 능력을 가지는데 확인할 수 있는 좋은 benchmark이다. 이는 peptide나 protein을 나타내는 molecule들로 구성되어 있다. PASCALVOC는 image의 super-pixel을 기반으로 하는데, 이는 image의 graph representation과 같다. PCQM은 또다른 molecule dataset이다.
이러한 실험들을 통해서 long-range dependency와 관련해서는 graph transformer가 기존의 GNN보다 좋은 성능을 보여주었다. 아무래도 graph transformer가 long-range dependency를 잘 파악할 수 있는 구조를 지니고 있다. 하지만 저자들은 graph transformer가 없어도 long-range dependency를 잘 파악할 수 있으며 graph rewiring을 제안하는 방식대로 하는게 transformer보다 더 좋다고 주장했다. 왜냐하면 이들이 제안한 방식은 parameter의 수가 적어서 over-squashing 문제를 크게 겪지 않기 때문이다.
이 논문에서 위의 그림은 다소 흥미로운 부분이 있다. 기존의 GCN이나 rewiring 방식의 DRew-GCN의 경우 lyer의 수를 증가시킴에 따라 over-squashing 현상을 겪는 것을 보여주고 있다. Layer를 쌓기 시작하면 expressive power가 강력해져 성능이 오르는 것을 확인할 수 있지만, 점점 많이 쌓기 시작하면 over-squashing 현상 때문에 성능이 오르지 않는 것을 볼 수 있다. 하지만, 이들이 제안하는 방식을 사용한 GCN의 경우 layer를 쌓을수록 성능이 계속해서 오르는 것을 확인할 수 있다. 이러한 실험적 결과로부터 이들은 over-squashing 문제를 극복했다고 이야기했다.