Strateges for Better GNN Architectures
사람들이 여러 GNN을 만들기 위해서 어떠한 것들을 고려하는지 알아보고자 한다. 이를 설명하기 위해서 위와 같은 레퍼런스로부터 미로라는 metaphor를 이용해서 알아볼 것이다. 이미 존재하는 GNN들을 나누는데 있어 최적의 metaphor가 바로 미로인 셈이다. 여기에는 어떻게 GNN을 적용하는지는 내용이 없으며, 이는 오로지 어떠한 방향으로 GNN 구조에 디자인해야하는지를 설명하고 있다. 총 7가지의 카테고리가 있으며, 대부분 이미 이전에 다 이야기한 내용들이다.
Walk and Look Around
첫번째로는 message-passing과 관련된 전략으로 walk and look around에 대해서 알아보고자 한다. 우리가 미로를 통과하고자 할 때 가장 먼저 하는 일은 일반적으로는 임의로 걸어보는 것이고, 이러한 과정을 message-passing 전략으로 볼 수 있다. 흔히 고전적인 GNN들에서 주로 사용되는 방식이다. 하지만 walk and look around 전략은 흔히 잘 알려진 over-smoothing과 over-squashing 문제로 연결된다.
Over-Smoothing Problem
Over-smoothing 문제는 이전에 이야기했던 homophily와 관련이 있다. GNN이 있을 때 여러번의 message-passing layer를 통과한 후에 output node의 representation이 이웃간에 서로 비슷하게 보이는 현상을 이야기한다. 어떠한 node든 간에 위와 같이 computational graph에서 message-passing이 끝난 후에는 모두 비슷한 성질을 지니게 될 것이다. 근처에 있는 node라고 한다면 2-hop, 3-hop neighbor node 정보를 모은 후에는 거의 동일하게 만들어지게 된다. 아무래도 각 node가 1-hop distance라는 동일한 거리로 떨어져 정의되어 있기 때문이다. 결국 모든 node가 평균화되기 때문에 서로가 비슷한 representation을 만들게 되는 것이고, 이를 우리는 over-smoothing이라고 한다.
Over-Squashing Problem
다음으로 over-squashing 문제는 LSTM에서 흔히 발생할 수 있는 문제이다. 만약 여러 time step으로부터 정보를 모아야한다면 실제로 굉장히 많은 정보들이 모이게 될 것이다. 그리고 이는 hidden layer에 전부 담지 못하게 될 것이다. 이러한 현상이 GNN에서도 발생하는 것이다. 너무 많은 정보들을 GNN으로 모으려고 한다면 각 GNN step마다 기하급수적으로 정보량이 폭발하게 될 것이다. Layer의 수가 많아지면 많아질수록 이웃 node간 degree에 따라서 많은 정보들을 서로 가지게 될 것이다. 따라서 각 vertex가 우리가 필요한 만큼 이상의 정보를 모으게 되는 것을 over-squashing이라고 한다.
이렇게 살펴본 2가지 문제가 지금까지도 사람들이 GNN에서 풀고자 하는 대표적인 문제들이다. 그렇다면 이러한 문제들을 어떻게 해결할 수 있을까?
Color Your Way
첫번째 방법으로는 color your way로, 임의로 random walk나 position에 색을 칠하는 과정이다. 만약 걷는 길을 따라 색을 칠하게 된다면 message-passing update를 위한 기록이 남게 될 것이고, 이에 따라 미로에서 길을 잃지 않게 될 것이다. Message-passing update를 할 때마다 각 vertex에 색을 칠하게 되면 결국에는 GNN에 expressive power를 얻게되는 것과 같아지게 된다.
이와 비슷한 또 다른 예시로는 cycle counting augmentation이 있다. 전체 graph에 대해서 sub-graph를 기록하게 되면 expressive power를 얻게 되는 것이다.
Squeeze Through Narrow Path
이번에는 over-squashing 문제와 관련이 있는 상황을 생각해보고자 한다. 때로는 미로에 우리가 빈번히 지나야만 하는 bottleneck이 존재할 수도 있다. Over-squashing 문제와 관련해서 정보에 bottleneck이 존재한다면 이 문제를 처리하기 위해서 추가적으로 capacity를 늘려주면 될 것이다. GNN 구조로부터 information bottleneck을 확인하기 위한 시도들을 할 것이고, 여기에 hidden dimension을 추가해주게 된다면 over-squashing 문제를 해결할 수 있을 것이다.
여기 expander graph라는 개념이 있다. 만약 많은 정보들이 전체 graph에 대해서 제대로 전파 되지 않는다면, 우리는 여기에 auxilary edge들을 추가함으로써 message-passing을 원활하게 만들 수 있다. 위에서 직선들로 연결된 graph가 expander graph이고, 이는 GNN의 message-passing 구조의 최적화된 결과를 나타낸다. 우리는 이러한 auxilary structure를 추가함으로써 message-passing을 augmentation할 수 있게 된다.
Listen to the Echo
다음으로는 spectral 방법들을 이용한 listen to the echo가 있다. 이는 전체 adjacency matrix로부터 얻어진 eigenvector들을 이용한 spectral한 접근법으로 graph를 파악하고자 하는 것이다.
Use a Map
Use a map은 각 vertex에 positional encoding을 해주는 것이다. 각 vertex에 색을 칠하거나 feature를 더하는 식으로 모든 vertex에 unique한 식별자를 할당해주는 식으로 할 수 있다. Labeling scheme으로 인하여 local position이나 global position을 쉽게 파악하고자 하는 것이고, 이는 흔히 transformer에서 주로 사용되는 방법 중 하나이다.
Destroy Some Walls
Destroy some walls는 auxilary edge를 추가해서 멀리 떨어진 vertex를 가깝게 만들고자 하는 것이다. 우리는 이를 graph rewiring이라고 부를 수 있다.
여러 고전적인 message-passing neural network에는 그들만의 message-passing structure가 있는데, 여기에 GNN의 computational graph를 수정함으로써 더 나은 propagation 결과를 얻고자 하는 것이다.
Fly Above
마지막으로 graph transformer에서 사용되는 개념으로 fly above가 있다. Graph transformer를 이용해서 모든 vertex를 연결해서 graph를 파악하고자 하는 것이다.
