GNN의 한계? GIN의 한계?

GNN의 한계

Graph representation을 위한 방법은 크게 2가지가 존재한다. Graph kernels 그리고 Graph neural networks. 전자의 경우, 그래프의 분해를 기반으로, 그래프에 대한 임베딩 값을 생성한다. 예를 들면 해당 그래프 내의 triangles의 수를 세리는 방법 등이 존재한다. 이러한 연구의 주된 목적은 그래프 간의 isomorphism을 잘 보존하는 임베딩을 찾아내기 위함이다. 즉, 두 그래프가 iso 하다는 것과 각각의 임베딩 값이 같다는 것은 동치-로 만드는 것이 그래프 커널의 목표인 것. 다만 이러한 문제를 푸는 것은 p-problem보다 어려운 것으로 알려져 있음. 물론 Anonymous walk embedding과 같은 임베딩 방법론들은 존재합니다. (그럼 이건 WL TEST 보다 진보된 것인가?) 다시다시 정리하자면, 그래프 커널은 그래프 iso 구분 문제를 해결하기 위해 고안된 것이며, 이러한 커널을 통해 얻어진 임베딩이 구분할 수 있는 그래프가 많다는 것은 임베딩 능력이 좋다는 것이다.

그러나 GNN이 등장하면서, 이러한 원칙(구분을 잘한다(=iso problem) = 임베딩이 좋다)이 변화함. 구분을 잘하니 마니 하는 문제를 푸는 것 대신에, 우리는 다른 문제를 풀어 볼 수 있을 것이다. 가령 shortest path를 찾거나, cycle을 감지하는 것 등의 문제말이다. 이러한 문제들은 꽤나 유망한데, 가령 우리가 네비게이션 시스템을 설계할 때, 주어진 상황 아래에서 직접적으로 shortest path를 잘 찾아낼 수 있다면 - 기존의 알고리즘을 사용하지 않고, 신경망을 통해 학습할 수 있다면 - , 생각할 것도 없지 않은가? 물론 신경망이 갖는 단점 중 하나인 - bad local optimum 문제 - 를 어떻게 잘 해결해 나갈 것인가. 그 외의 약간의 GNN의 한계 점들을 풀어야 하긴 한다. 이는 나중에 설명토록 하겠다.

Conditions on GNN to be powerful / GNN이 강력해질 수 있는 조건

너도 읽었지만 “How powerful are GNN”은 정말 GNN의 이론적 설명에 대산 연구를 촉발시킨 트리거였다. 특히 GNN은 WL 알고리즘과 자주 비교되는데, 한번 깊이 살펴보자

WL Algorithm?

이건 어떤 ppt의 55p 부터를 참조하시면 2해가 빠릅니다.

주목해야할 점은, WL 알고리즘이 injective function을 사용한다는 것. 이건 다른 인풋은 다른 아웃풋을 얻도록 보장하는데, 특히나 WL에서는 이전 이터레이션에서는 볼 수 없었던 인풋을 다음 이터레이션에서 생성하게 됩니다. 이는 애초에 도메인이 categorical(=countable)한 집합이었기에 가능합니다.

이 알고리즘의 메인 목표는 두 그래프 간의 iso를 판정하는 것인데, k번의 반복 후에도 두 그래프가 같은 컬러링을 같은 경우, 그것들은 iso할 가능성이 있다- 정도로 판단하게 된다. 절대 iso 하다! 가 아니다. iso할 가능성이 있는데? 정도이다. 반대로 두 그래프가 다른 컬러링을 같게되면 iso 하지 않다-라고 말할 수 있다.

이건 70년대에 고안되었는데, 1-WL의 경우(wl paper 읽어봐) regular graphs들을 구분할 수 없다(최종 색상은 모두 동일해진다, 그전까지는 컬러링이 다르겠지만…) 그럼에도 불구하고, 이것은 iso test에 대한 굉장히 파워풀한 이론이며, 정리 자체에서 언급되는 n은 사실상 inf의 의미이므로, 이론적으로는 굉장히 강력한 알고리즘이다.

Back to GNN

만약 네가 GNN과 WL의 알고리즘을 주의깊게 살펴봤다면, 노드의 특성을 업데이트 해나가는 과정이 상당히 유사함을 깨달았을 것이다. 특히, GNN의 경우 message-passing mechanism을 활용하여 특성을 업데이트한다. (Message passing은 별개 아니라 정보를 계속 다음단계로 recursive하게 넘기는 정도의 의미 with aggregation function) 서로 다르다고 말하는 GNN들간의 차이는 단순히 어떤 aggregation and readout function을 사용하는가에 있다. 다만 그러한 aggregation function은 injectice여아만 WL과 같은 힘을 갖게되는데, 이에 대한 내용이 Theorem 3이다. -

GNN의 agg 함수는 WL test가 non-iso라고 판정한 2개의 그래프를 서로 다른 값으로 임베딩한다. 다만 2가지 조건을 만족해야하는데 첫째는, agg and update 함수가 inj 할 것, 둘째는 readout 함수가 inj 할 것. - 즉, GNN의 parameterized functions이 inj 할 때, GNN의 강력함을 보장한다는 것인데, WL 알고리즘에서도 당연히 update function이 inj 해야했다는 측면을 고려하면, 뭐 당연한 말이다. 쨋든, 우리는 GNN이 오래되고, 신뢰성있는 알고리즘인 WL만큼이나, iso test에 대해서 휼륭하게 작동한다는 점을 배웠다.

About the limitations of GNN

GNN의 가장 기본적인 한계는 Theorem 3에 대한 한계일 것. 그러니까 반드시 injective한 egg and update 함수가 필요하다. 만야 agg fn으로 mean fn을 채택해보자. 이 경우 different graphs들을 same embedding으로 만들어버리는 상황을 쉽게 생각할 수 있는데, 이건 mean fn이 non-inj이기 때문이다. 그러나 만약, 네가 sum and transform embedding function을 specific manner로 가져오게 되면, 멋진 inj fn을 얻을 수 있는데, 이게 Lemma 5이다.

정말 중요한 점은 sum을 진행하기전 반드시 f를 사용한다는 점이다. 그래야만 inj 가 성립한다. 실제로 정리에서도 이런 f에 대해 구체적으로 언급하고 있으며, 이에 필요한 2가지 조건 - X가 countable 하고, 모든 multiset들은 bounded되어 있다 - 는 저자의 생각에는 별로 strong한 조건은 아니다. 쨋든, 우리는 유한한 특성과 이웃들을 가진 유한한 그래프들에 GNN을 적용하고자하며, 우리는 f(x)를 씌운 후에 sum을 진행하면, 이것은 inj fn이라는 것을 알고 있다.

다만 이러한 Theorem 3에는 구체적인 agg fn에 대한 언급(자신과 자신의 이웃들을 통합해야한다는 의미에서)이 없는데, 이를 위해 Corollary 6이 나오셨다… 정리 3의 파이에 해당하는 놈을 잡아주신 것?

여기서 h 함수는 f(x)를 summation하지만, inj가 성립되도록 만들었다는 것에 주의한다. 쨋든, 우리가 단순히 강력한 임베딩 펑션을 찾는 것이 목표였다면, 우리는 이미 그것을 달성한셈이다. 멋진 inj fn들의 조합을 찾아냈으니. 그러나 우리는 그런걸 찾으려 했던 것이아니라, supervised learning의 방식을 통해서, node classification과 같은 downstream task를 풀어낼 수 있기를 원한거다. 그리고 그 함수 h는 learnable parameter들을 포함하지 않는다. - 즉, 지금으로써는 학습을 시킬 수가 없어. 그래서 MLP를 사용할건데, 핵심이되는 phi 와 f fn을 MLP로 대체해보자고. UAT Thm이 있으니, 조건만 맞다면 MLP는 phi 와 f fn을 잘 대체해줄거야. 아래와 같이 말이야.

주의! 다만, MLP 그 자체, 그리고 내부의 메커니즘은 inj을 보증하지는 않습니다. 그냥 더 나은 성능으로 업데이트 되는 과정에서 inj이 되기를 하늘에 바랄 뿐이지. 다만, 인풋이 원핫인코딩되어 있을 경우에는, 1-st layer에 한정해서 MLP 내부의 sum은 inj가 맞습니다. 그러나 그 이후는? 보증못한다 그죠.

쨋든, 그래서,... MLP가 injective function으로써 작동할 때에서야, GIN은 WL만큼 강력하다.

But in fact, 훈련과정 중에 MLP 가 inj할 것이라는 보장은 없다. So, GIN은 한계가 명확하다.

 

출처 자료: 링크