9. Theory of Graph Neural Networks

GNN Tobigs·2021년 9월 6일
4

작성자 : 장아연

Aggregate Neighbors

• local network neighborhood를 바탕으로 node embedding 생성
• node는 neural network 이용해 neighbor로부터 aggregate information

GNN Model

• 서로 다른 GNN model은 서로 다른 neural network를 사용
GCN (mean - pool)

GraphSAGE (max - pool)

Local Neighborhood structure

Note : Node Color
use color to represent node feature
-> same color = same feature representation

Can GNN distinguish different graph structure?

• quantify local network neighborhood around each node

easy to distinguish

nodesingle hop neighborhood
node 1degree of 2
node 5degree of 3

case 1 : hard to distinguish

nodesingle hop neighborhoodsecond hop neighborhood
node 1degree of 2degrees of 2 (node 2) and 3 (node 5)
node 4degree of 2degrees of 1 (node 3) and 3 (node 5)

case 2 : can not to distinguish

• symmetric within graph
nodesingle hop neighborhoodsecond hop neighborhood
node 1degree of 2degrees of 2 (node 2) and 3 (node 5)
node 2degree of 2degrees of 2 (node 1) and 3 (node 5)

go steep deeper to 2nd hop neighbor, still have same degree

Computational Graph

• GNN aggregate neighbor node embedding
• define neighborhood
-> use computation graph
-> then GNN generate node embedding

• Node 1's commputational graph (2-layer GNN)
level 0 : (node 1, node 5) , (node 1, node 2, node 4)
level 1 :
node 5 aggregate information from (node 1, node 2, node 4)
node 2 aggregate information from (node 1, node 5)
level 2 :
node 1 aggregate information from node 2 and node 5

• GNN은 message passing information without node ID, only use node feature

• computation graph of two node are same
-> embedded exactly into same point in embedding space

• GNN generate same embedding for node 1 and node 2
why ?
1. computational graph are same
2. node feature are same

• Computational graph are identical to rooted subtree structure for each node
• Rooted subtree structure
: recursively unfolding neighboring node from rooted nodes

• GNN은 rooted subtree structure 포착해 이에 따른 node embedding 매핑

How expressive is a GNN?

Injective function

• $f$ : $X$ -> $Y$ : 서로 다른 X에 대해 서로 다른 Y 매핑
• $f$가 input $X$에 대한 모든 결과값을 가짐

GNN map subtree to node embedding injectively

Most Expressive GNN : use injective neighbor aggregation

• same depth subtree : recursively characterized from leaf to root node
• Injective neighbor aggregation :
서로 다른 neighbor -> 서로 다른 embedding
( GNN aggregation에서 neighborhood information을 완전히 얻는 경우, 생성된 node embedding은 서로 다른 rooted subtree 구별 가능 )

Neighbor Aggregation

• GNN 표현력은 사용하는 neighbor aggregation function에 따라 좌우됨

Neighbor Aggregation : a function over multi-set

neighbor aggregation
: node and aggregated from two neighbor for two children
Multi-set function
: set of children (two yellow) and need to aggregate information from that set

Aggregation function for GNN model

GCN (mean-pool)

• element wise mean -> linear function -> Relu activation
• same color proportion의 multi-set 구별 불가능
• failure case example
represent node color by one-hot encoding

GraphSAGE(max-pool)

• element wise max pooling
• same distinct color set의 multi-set 구별 불가능
• failure case example

not injective : fail to distinguish some basic multi-set
not maximally powerfull GNN
need to design neural network that can model injective multiset function

Injective Multi-Set Function

• $f$ produce one-hot encoding of color
• summation of one-hot encoding retain all information about input multi-set

Universal Approximation Theorem

• use MLP(Multi-layer perceptron) to model $\Phi$ & $f$
• large hidden dimensionality 1-hidden layer MLP and non linearity
-> continous function을 arbitrary accuracy로 근사 가능
(hidden dimensionality는 100~500 정도가 적절)

The Complete Graph Isomorphism Network Model

• take multi-set with element $x$ -> apply multi-layer perceptron -> sum up -> apply another perceptron
• multi-layer perceptron은 임의의 함수에 근사하고 이로서 $f$$Phi$에도 근사됨
• GIN의 neighbor aggregation function은 injective함
GNN에서 가장 표현력이 좋음 & 실패 사례 없음

Full model of GIN with relation to WL Graph Kernel
color refinement algorithm in WL kernel

• initial color : $C^{(0)}(v)$ to each node
• interatively refine node color

to create color at k+1 for given node
-> take color of node $u$ that are its neighbor from previous iteration
-> then, take node $v$ from previous iteration
-> after, hash two colors
• after $K$ color refinement, $c^{(K)}(v)$$K$-hop neighborhood의 구조를 요약함

Example

• stable coloring에 도달할 때까지 process가 이어짐
• 두 그래프가 같은 color set을 가진 경우, isomorphic하다고 함

GIN use Neural Network to model injective Hash Function

• $(1 + \epsilon)$
• $MLP_{f}(c^{(k)}(v))$
: our own message transformed by $k$
• $\sum\limits_{u\in\mathbb{N(v)}} MLP_f(c^{(k)}(u))$
: take message from children and transform them using MLP, then sum up
• $MLP_{\Phi}($ $(1 + \epsilon)$ * $MLP_{f}(c^{(k)}(v))$ + $\sum\limits_{u\in\mathbb{N(v)}} MLP_f(c^{(k)}(u))$ $)$
: add two together and pass through another function $\Phi$

input feature가 one-hot vector로 표현 가능한 경우, direct summation은 injective하기 때문에 $\Phi$가 injective하도록 보장하면 됨

GIN's node embedding update

• initial vector : $C^{(0)}(v)$ to each node
• interatively update node vector
• after $K$ step of GIN iteration, $c^{(K)}(v)$$K$-hop neighborhood의 구조를 요약함

GIN and WL Kernel

GIN ~ differentiable neural network version of WL graph kernel

• low dimensional of node embedding -> can capture fine-grained similarity of different node
• parameter of update function can be learned for the downstream task

GIN과 WL graph kernel의 연관성으로 인해 표현력은 동일
GIN은 실제 모든 graph를 구별 가능

Power of Pooling

Failure case of mean and max pooling
(a) : type of neighborhood structure with all same feature
(b) : number of distinct color are same
(c) : proportion of distinct color is same

Ranking by discriminative power

투빅스 1415기 GNN 스터디입니다.

3개의 댓글

2021년 9월 16일

14기 김상현

• GNN은 rooted subtree의 구조를 포착해 이에 따른 node embedding 수행
• Node feature가 같은 경우 computational graph가 같은 경우 injective node embedding 불가
• 표현력이 풍부한 GNN은 injective neighbor aggregation을 사용. 기존의 GCN, GraphSAGE는 not injective neighbor aggregation -> 표현력이 부족
• Injective aggregation을 위해 MLP을 이용 -> GIN(graph isomorphism network
• GIN은 WL graph kernel과 동일한 표현력을 갖으면서 미분 가능한 신경망
- GIN: GINConv를 사용해 node embeddings(low-dim vectors)
- WL graph kernel: Hash function 사용해 node colors(one-hot)

GNN의 표현력과 GIN에 대해 이해할 수 있었습니다.
유익한 강의 감사합니다 :)

답글 달기
2021년 9월 17일

[15기 이성범]

• GNN은 주변 노드를 바탕으로 노드의 임베딩을 생성한다. 여기서 주변 노드의 정보를 합칠 때 neural network를 사용한다.
• 서로 다른 GNN 모델은 서로 다른 NN을 사용한다.
• GNN은 노드의 주변 노드를 map subtree로 나타내 이를 이용하여 Node를 임베딩 한다.
• 따라서 서로 다른 주변 노드를 가지고 있으면 서로 다른 임베딩을 가지게 된다.
• GNN의 표현력은 사용하는 neighbor aggregation function에 따라 좌우된다.
• Graph Isomorphism Network의 neighbor aggregation function은 injective하여 GNN에서 가장 표현력이 좋으머 실패 사례가 없다.
• GIN은 Color refinement라고 불리는 알고리즘을 활용하는 WL 커널을 사용하는 방식이다.
답글 달기
2021년 9월 24일

15기 김재희

• GNN의 aggregation function은 이웃 노드에 대한 subtree 구조를 입력으로 하여 임베딩 벡터를 아웃풋으로 내보내는 함수
• message passing의 관점에서 표현력이 좋은 gnn이 되기 위해서는 aggregation function이 단사함수여야 함.
• 기존에 배웟던 mean, max pooling 등은 단사함수가 아니기 때문에 좋은 aggregation function이 아님
• MLP가 충분히 큰 hidden node를 가지면 어떤 연속함수든 근사가 가능하다는 성질을 이용하여 MLP로 aggregation function을 구성하면 단사함수가 됨.
• 이를 이용한 것이 GIN으로 수식적으로 WL kernel의 근사함수.
• 그러므로 GIN의 표현력의 상한은 wl kernel이 됨
답글 달기