How Expressive are Graph Neural Networks? - GCN, GraphSAGE and "GIN"

연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.

유튜브 강의 링크는 다음과 같다.

https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn

Stanford CS224W: Machine Learning with Graphs

 

 

목차

 

 

 

 

 

Theory of GNNs

 

GNN Framework

 

Graph Neural Network는 위 그림과 같이 Graph를 입력으로 받아 node, subgraph, graph 등의 embedding을 출력해준다.

 

Inofrmation Aggregation and Message Passing

 

주요 아이디어는 local network neighbor들의 정보(message)를 합쳐(aggregation) 방법을 통해 전달받는 것이고, 노드의 정보는 각각 neural network를 거쳐 얻는다.

앞서 message 계산 방법, aggregation 방법에 따라 GNN은 다음과 같이 분류됨을 알아보았다. (링크)

• GCN
• GAT
• GraphSAGE

 

이번에는 GNN의 여러 모델 중, 어떤 모델이 expressive power가 높은지, 가장 expressive한 GNN model을 어떻게 설계할 것인지를 알아보자.

Expressive power란, 서로 다른 graph 구조를 얼마나 잘 구분할 수 있는가를 말한다.

 

 

 

GNN Models

 

GCN, GraphSAGE, GAT, Design Space 등 많은 GNN 모델들은 위의 'Information Aggregation and Message Passing' 그림에서 어떤 Neural network를 사용할 것인가에 따라 달라진다. 좀 더 자세히 살펴보자.

 

GCN (mean-pool)

GCN (mean-pool)

 

GraphSAGE (max-pool)

GraphSAGE (max-pool)

 

 

 

 

Node Colors, Local Neighborhood Structures

 

Node(subgraph, graph)를 구분하기 위한 방법은 아래와 같은 것들이 있다.

• Node Colors
• Local Neighborhood Structures

각각을 자세히 알아보자.

 

Node Colors

Node color란, 서로 같은 feature를 갖는 node를 같은 색으로 표현하는 것이다.

그러면 node가 모두 같은 color이면(feature가 모두 같으면) 두 node는 같은 노드일까?

당연히 아니다! Feature(color)가 같더라도 local neighborhood structure에 따라 달라질 수 있다.

 

Local Neighborhood Structures

다음 그래프의 모든 노드는 featrue가 같다.

Example

하지만, Node1과 node5(다른 노드들도 마찬가지로)는 서로 명확히 다른 node이다.

이는 서로 local neighborhood structure가 다르기 때문이다. Local neighborhood structure는 말 그대로, 각 노드가 갖고 있는 (지역적인) 이웃 노드들의 구조이다. Local neighborhood structure에 사용될 수 있는 개념도 여러가지가 있다.

먼저, node 1과 node 5는 서로 node degree가 각각 2, 3으로 다르므로 쉽게 다른 노드임을 구분할 수 있다.

그리고, node 1과 node 4는 node degree가 같지만, 이웃 노드(1st hop)의 node degree가 다르므로 다른 노드임을 구분할 수 있다.

하지만 node 1과 node 2의 경우, 두 노드는 서로 symmetric(isomorphic)하다. 즉, 서로 같은 neighborhood structure를 갖는다. 두 노드의 degree, 이웃 노드(1st hop)의 degree 등 모두 같다.

 

 

 

Computational Graph

 

GNN의 node embedding이 node의 local neighborhood structure를 언제 잘 구분하고, 언제 구분을 못하는지를 알기 위해서는 GNN이 local neighborhood structure를 어떻게 capture하는지를 이해해야 한다.

GNN이 local neighborhood structure를 포착하는 가장 주요한 개념은 computational graph이다.

 

각 layer에서는 GNN을 활용하여 이웃 노드의 node emebdding을 합친다.(aggregation)

Computational graph는 이렇게 GNN이 node embedding을 생성할 때 이웃 노드로부터 정의되어 사용된다.

예를 들어, 위 예시 그래프에서 node 1과 2의 computational graph는 아래와 같다. (2-layer GNN만 고려)

 

Computational graphs in 2-layer GNN (1)

 

하지만, GNN은 node의 id를 고려하지 않고 feature vector의 aggregation만 진행하기 때문에, 실제로 node 1과 node 2의 embedding은 아래 사진과 같이 구분이 불가능할 것이다.

 

Computational graphs in 2-layer GNN (2)

 

 

 

 

How Expressive is a GNN?

 

위 내용에 이어 GNN이 얼마나 expressive한지, 즉 서로 다른 노드를 얼마나 잘 구분하는지 알아보려면 어떤 기준이 필요한지 알아보자.

 

일반적으로, 이웃 노드의 구조가 다르면 다른 computational graph를 갖는다. 그리고, computational graph는 각 노드에 대한 rooted subtree 구조이다.

 

Computational graph for each nodes

 

따라서, 가장 expressive한 GNN은 서로 다른 rooted subtree(=local neighborhood structure)를 다른 node embedding으로 맵핑하는 GNN일 것이다. (그 node embedding은 color로 표현된다.) 다른 표현으로 가장 expressive한 GNN은 subtree를 node embedding에 일대일(injective하게맵핑하는) 함수일 것이다.

 

Injective mapping from subtree into embedding space

 

그러므로 GNN의 expressiveness(powerfulness)를 알기 위한 핵심은 Subtree가 leaf node에서부터 root node까지 recursive하게 characterize될 수 있는지 알아보는 것이다. 한글로 표현하기가 애매해서 영어를 쓰다보니 더 헷갈리는데, 다음 그림을 보자.

 

Key observation

 

Subtree 구조에 따라 input feature가 leaf가 될 것이고, node의 embedding이 root일 것이다. 처음 node 1과 node 4가 같은지 비교했을 때에는 해당 node의 degree, 1-hop 이웃 노드들의 degree, 2-hop 이웃 노드들의 degree ... 와 같은 순서로 비교했었지만, 이미 subtree 구조가 주어졌다면 leaf부터 비교하는 것이 빠르다.

즉, 이제는 node1과 node4의 최종-hop (위의 경우에는 depth가 3인 subtree이므로 1-hop) neighborhood의 node degree부터 비교하면 된다. Node 1은 (2 neighbors, 3 neighbors), node 4는 (1 neighbor, 3 neighbors)이므로 서로 다른 노드임이 명확해진 것이다.

이렇게 leaf부터 비교해도 되는 이유는 모든 GNN aggregation 과정에서 이웃 노드인지에 대한 정보가 계속 유지되기 때문이다.

따라서 가장 expressive한 GNN은 모든 step에서의 neighbor aggregation 과정이 일대일 대응이어야 한다.

 

한마디로, GNN의 모든 neighbor aggregation 과정이 일대일 대응이라면, 그 모델은 서로 다른 subtree 구조를 완전히 구분할 수 있다.

 

 

 

 

 

 

Most Powerful GNN

 

위에서 정리한 내용에 따라, GNN 모델의 expressive power는 그 모델이 어떤 neighbor aggregation function을 사용하는가(injective aggregation function을 사용하는가)에 달려있다.

그렇다면 neighbor aggregation function 중에서 일대일 함수가 어떤 것이 있을지 알아보자.

 

 

 

GCN(mean-pooling) and GraphSAGE(max-pooling)

 

우선, Neighbor aggregation은 multi-set에 대한 function이다. 여기서 multi-set이란, 반복되는 요소를 포함하는 집합을 말한다. 예를 들어, 어떤 graph \(\mathcal{G}\)에서 각 노드의 feature는 \(\{ a, a, b, c, d\}\)로 다섯 개일 수 있다. 위에서 계속 예시로 들었던 그래프가 이러한 형태일 것이다.

GNN 모델 중에서 대표적인 두 모델인 GCN과 GraphSAGE의 aggregation function을 다시 한 번 살펴보자.

• GCN (mean-pool)
  • 이웃 node feature들에 대해 element-wise mean pooling 사용
  • /(\text{Mean}(\{x_u\}_{u \in N(v)})\)
• GraphSAGE (max-pool)
  • 이웃 node feature들에 대해 element-wise max pooling 사용
  • \(\text{Max}( \{ x_u\}_{u \in N(v)}) \)

 

하지만, mean pooling과 max pooling은 일대일 함수가 아니다.

먼저, mean pooling은 같은 color 비율인 서로 다른 두 multi-set의 결과가 같다. (즉, 구분할 수 없다.)

예를 들어, color(node feature)가 각각 \( \{y, b\}\)(yellow, blue)와 \( \{y, y, b, b\} \)인 두 multi-set을 살펴보자.

yellow를 \([1 \; 0]^\top \), blue를 \([0 \; 1]^\top\)로 one-hot encoding하여 mean pooling을 적용하면 \( \left([1 \; 0]^\top + [0 \; 1]^\top \right)/2 = \left( [1 \; 0]^\top + [1 \; 0]^\top + [0 \; 1]^\top + [0 \; 1]^\top \right)/4 = [0.5 \; 0.5]^\top \)로 같은 결과가 나올 것이다.

 

그리고, max pooling은 color의 종류의 수(서로 다른 color의 수)가 같지만 각 color의 수가 다른 multi-set을 구분할 수 없다.

간단한 예시로 \(\{y, b\}\), \(\{y, y, b\}\), \(\{y, y, b, b\}\)는 세 개가 모두 서로 다른 multi-set이지만, max pooling을 한 결과는 \(\{y, b\}\)로 같을 것임을 쉽게 알아차릴 수 있다.

 

따라서 GCN과 GraphSAGE는 서로 다른 node임에도 같은 node로 분류할 가능성이 있고, most expressive GNN이 아니다.

 

 

 

GIN(Graph Isomorphism Network)

 

그렇다면 message-passing GNN 중에서 가장 powerful한(expressive한) GNN 모델은 무엇일까? 즉, multi-set에 대해 injective한 neighbor aggregation function을 갖는 GNN 모델은 무엇일까?

바로, neighbor aggregation function으로 summation을 사용하는 모델이다. 이 모델을 GIN(Graph Isomorphism Network)이라 한다. (GIN 논문에 대한 상세한 리뷰는 링크를 참조하자.)

Sum pooling은 비율이 같지만 다른 multi-set, 서로 다른 color 수가 같지만 다른 multi-set을 모두 구분할 수 있다. 모든 element를 one-hot vector로 바꾸어 더해버린다면 서로 다른 multi-set에 대해서는 값이 다를 수밖에 없다는 것이 증명되었다. 즉, one-hot encoding의 합은 multi-set 입력에 대해 모든 정보를 보존한다.

GIN의 injective multi-set function인 neighbor aggregation function은 다음과 같이 표현한다.

\( \phi \left( \sum\limits_{x \in S} f(x) \right) \)

• \(\phi\) : Non-linear function for aggregated neighbor information
• \(\sum\limits_{x \in S} \) : Summation over multi-set
• \(f\) : Non-linear function for input features

위 식을 모델링하기 위해서는 multi-layer perceptron (MLP)를 사용한다.

딥러닝을 배워본 사람이라면 universal approximation theorem을 들어본 적이 있을 것이다. Universal approximation theorem이란, 충분히 큰 차원의 한 층의 hidden layer와 적절한 non-linear function만 있으면 어떤 연속 함수도 근사할 수 있다는 이론이다.

 

따라서 식에 이를 적용하면, neighbor aggregation function은 다음과 같이 나타낼 수 있다.

\( \text{MLP}_\phi \left( \sum\limits_{x \in S} \text{MLP}_f(x) \right) \)

실험에 따르면 MLP의 hidden dimensionality는 100~500정도가 적당하다고 한다.

 

따라서, message-passing GNN 중에서 가장 expressive한 GNN 모델은 GIN이다!

GIN의 neighbor aggregation function을 살펴보았으니, 모델의 전체적인 동작 원리를 알아보자.

 

 

 

Full-Model of GIN

 

이전에 링크에서 WL graph kernel을 다루었다. 이는 graph-level feature를 얻는 전통적인 방법이었다. GIN은 WL graph kernel의 neural network 버전의 개념이다.

WL graph kernel의 color refinement algorithm을 잠깐 떠올려보자면, 각 노드 \(v\)에 initial color \(c^{(0)} (v)\)를 할당하고, hash table을 사용하여 node color를 반복적으로 개선했다. 이를 K번 반복하면 \(c^{(K)} (v)\)가 해당 그래프의 K-hop neighborhood 구조를 표현한다는 개념이었다. 

GIN은 node color를 개선하는 (injective) 함수로 neural network를 사용한다. 특히, 이러한 injective function은 (root node colors(features), neighboring node colors) tuple \( (c^{(k)} (v), \{ c^{(k)} (u) \}_{u \in N(v)} )\)에 대해 적용한다. 이를 수식으로 표현하면 다음과 같다.

\( \text{MLP}_\phi \left( \left( 1 + \epsilon \right) \cdot \text{MLP}_f \left( c^{(k)} (v) \right) + \sum\limits_{u \in N(v)} \text{MLP}_f \left( c^{(k)} (u) \right) \right) \)

• \(\epsilon\) : Root node의 color를 얼마나 더 중요하게 볼지를 결정하는 learnable parameter

 

여기서, input feature \(c^{(0)} (v)\)는 one-hot vector로 표현되며, \(f\)는 injective function인 summation으로 대체함에 따라 \(\phi\)만 일대일 대응이라면 수식 전체의 injectivity가 결정된다.

 

\( \text{GINConv} \left( c^{(k)} (v), \{ c^{(k)} (u) \}_{u \in N(v)} \right) = \)
\( \text{MLP}_\phi \left( \left( 1 + \epsilon \right) \cdot c^{(k)} (v) + \sum\limits_{u \in N(v)} c^{(k)} (u) \right) \)

여기서 \(\text{MLP}_\phi\)는 next layer의 input feature인 one-hot vector를 출력한다.

 

따라서 GIN 모델의 node embedding update는 다음 식으로 이루어진다.

\( c^{(k+1)} (v) = \text{GINConv} \left( \left\{ c^{(k)} (v), \left\{ c^{(k)} (u) \right\}_{u \in N(v)} \right\} \right) \)

여기서 \(\text{GINConv}\) 함수는 서로 다른 input은 서로 다른 embedding으로 맵핑하는, 미분 가능한 color HASH function이다.

WL graph kernel에서와 마찬가지로 위 과정이 K번 반복되면 \(c^{(K)} (v)\)는 K-hop neighborhood 구조를 표현한다.

 

GIN과 WL graph kernel을 다음과 같이 비교해볼 수 있다.

WL Graph Kernel vs Graph Isomorphism Network

 

GIN으로 구분이 가능한 두 그래프는 WL kernel로도 가능하고, 역도 성립한다.

GIN을 사용했을 때의 장점은 node embedding이 저차원이므로 노드 간의 더 미세한 구별이 가능해지고, 학습한 update function의 parameter를 다양한 downstream task들에 적용할 수 있다는 점이다.