[그래프 기계학습] Dynamic Graph Rewiring

Some Limitations of Static Graph-Rewiring

이번에는 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를 수정하게 되는데, 이에 따라 기존의 정보들을 잃을 수도 있다.

Dynamic Edge-Addition and Delay

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을 추가하는 방법이다.

$\nu$-DREW in Equations

그래서 정보를 aggregation할 때 이전 layer뿐만 아니라 $k$만큼 떨어진 이웃들에 대해서 $\tau_\nu(k)$ layer에도 수행하게 된다. 만약 3개의 layer 이전부터 정보를 모은다고 하면 결국 3-hop 떨어진 이웃들로부터 정보를 모으는 것과 같아지게 된다. 여기서 $\nu$ factor를 infinity로 하면 원래의 rewiring 기술과 같아지게 된다. 결국 이러한 방법은 기존의 rewiring 방법의 generalization 버전인 것이다.

Advantages of $\nu$-DREW

이들이 제안한 방식의 장점은 graph가 더 효율적인 framework를 만들기 위해서 각 layer에 점진적으로 채워진다는 것이다. 그리고 더 가까운 node는 일찍부터 상호작용하기 때문에 input graph로부터 inductive bias를 보존할 수 있다. 이는 단순히 멀리 떨어진 vertex 사이에 임의의 edge를 추가하는 것과는 다르다. 이전에는 사람들이 멀리 떨어진 vertex 쌍을 선택해서 이들 사이를 연결하려는 시도를 하였지만, 이번에 살펴보는 이 방법은 $k$-hop neighbor connection을 기반으로 이루어지기에 기존의 정보를 더욱 잘 보존하게 된다. 이러한 방식은 결국 over-smoothing 현상 또한 완화하는데 이점을 가지게 된다. 비록 멀리 떨어진 vertex를 연결한다고 하더라도 서로 다른 layer를 통해서 연결하기 때문에 smoothing 현상이 발생할 가능성이 낮아지게 된다.

Long-Range Graph Benchmarks

이 방법은 또한 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 문제를 극복했다고 이야기했다.