[CS224w] Theory of GNNs (1) - Local Neighborhood Structures, Computational Graph

 

Local Neighborhood Structures

Example Graph

같은 색의 노드는 같은 feature를 갖는다고 하자. 위의 경우 5개의 노드가 동일한 feature를 가진 경우이다.

1번 노드와 4번 노드는 degree가 2로 동일하지만, neighborhood structure는 다르다.

1번 노드의 이웃노드들은 degree=2지만, 4번 노드의 이웃노드들은 degree가 1 또는 3으로 다르기 때문이다.

 

1번 노드와 2번 노드는 neighborhood structure가 동일하다.

모두 이웃 노드의 degree가 2와 3으로 동일하다.

 

Can GNN node embeddings distinguish differenct node's local neighborhood structures?

Computational Graph

각 layer마다 GNN은 이웃 노드 임베딩을 합친다. (aggregate)

computational graph (계산 그래프?)를 통해 GNN은 노드 임베딩을 생성한다.

Node 1's Computational Graph (2-layer GNN)

GNN이 효과적이려면 각 노드 임베딩이 고유한 표현을 가져야 한다.

그러나 위 예시 그래프 구조에서 1번 노드와 2번 노드는 computational graph가 동일하다. (id는 feature가 아니기 때문)

따라서 GNN은 1번 노드와 2번 노드의 임베딩이 동일할 것이다.

GNN won't be able to distinguish nodes 1 and 2

이를 통해 알 수 있는 것은, (일반적으로) 다른 local neighborhood 라면 다른 computational graph를 갖는다는 점이다.

그리고 computational graph는 rooted subtree structure와 동일한 구조이다.

가장 표현력이 높은 (most expressive) GNN은 다른 rooted subtree마다 다른 node embedding을 injective 매핑(단사 함수)하는 것이다.

 

Computational Graph and Node Embeddings

반응형

(leaf에서 root 방향으로) 같은 depth의 subtree는 recursively characterized하게 유지된다.

Subtrees of the same depth can be recursively characterized from the leaf nodes to the root nodes.

 

Summary

node embedding을 만들 때 GNN은 computational graph를 이용한다.

computational graph는 rooted subtree와 구조가 동일하다.

모든 step에서 GNN은 완전히 subtree 구조를 구별할 수 있다.