[CS224w] Graph Augmentation

반응형

 

Introduction

지금까지  input graph와 computational graph가 같다는 가정이 필요했다.

그러나 여러 이유로 인해 이러한 가정을 유지할 수 없다.

 

Feature level

feature가 부족 → feature augmentation

 

Structure level

too sparse → message passing이 비효율적 → add virtual node/edge

too dense → message passing이 too costly → sample neighbors when doing message passing

too large → GPU로도 부족한 계산량 → sample subgraphs to compute embeddings

 

Feature Augmentation

Case 1. Input graph does not have node features

Case 1 - (a) Constant node feature

Assign constant values to nodes

 

Expressive power

모든 노드가 동일하지만(구별 불가능하지만) GNN은 여전히 그래프 구조를 학습할 수 있다.

 

Inductive learning (generalize to unseen nodes)

새로운 노드를 매우 쉽게 일반화 할 수 있다. 단순히 새로운 노드에 상수를 부여하면 된다.

 

Computational cost

1차원 벡터를 이용하기때문에 매우 낮다. 

 

Use cases

모든 그래프에 적용 가능하다. 

inductive setting에 사용된다.

Case 1 - (b) One-Hot node feature

Assign unique IDs to nodes

Expressive power

각 노드는 ID를 갖고 있기 때문에 (노드 벡터의) 표현력은 매우 높다.

node-specific information을 저장할 수 있다.

 

Inductive learning (generalize to unseen nodes)

새로운 노드에 일반화가 불가능하다.

GNN은 unseen ID를 임베딩 할 수 없다.

 

Computational cost

매우 고차원 벡터를 이용하기에, large graph에는 적용할 수 없다.

 

Use cases

비교적 작은 그래프에 적용한다.

transductive setting에 사용된다. (no new nodes)

 

Case 2. Certain structures are hard to learn by GNN

그래프 구조에 따라서 GNN으로 학습이 불가능하거나 매우 어려울 수 있다.

예를 들어, 그래프에 사이클이 존재하는 경우를 생각해보자.

$v_1$ resides in a cycle with length 3 and 4

노드 $v_1$은 GNN으로 사이클의 길이를 학습할 수 있을까? 그렇지 않다.

 

게다가, 또다른 문제가 있다. $v_1$은 그래프 내에서 구별이 안된다.

모든 노드의 degree는 2이기 때문에 $v_1$을 특정할 수 없는 문제가 있다.

Cycle count feature

augmented node feature에 cycle length를 추가하여 표현할 수 있다.

이때, cycle length는 0부터 시작한다.

Cycle count as augmented node features (start from 0)

Other augmented features

cycle count 말고도 다른 여러가지 feature를 추가할 수 있다.

전통적인 ML-graph에서 논의된 feature가 사용될 수 있다.

• Clustering coefficient
• PageRank
• Centrality
• etc.

 

Add Virtual Nodes/Edges

sparse graph의 문제를 해결하기 위한 방법이다.

Add virtual edges

일반적으로 2-hop neighbor를 연결하여 virtual edge를 생성한다.

인접행렬 $A$를 input graph로 사용하는 대신에, $A + A^2$을 사용한다.

 

Bipartite graph

 

(추천시스템에서 자주 사용되는) Bipartite graph(이분그래프)에서 사용된다.

author-paper 구조에서, 2-hop virtual edge를 통해 author-author collaboration graph를 생성할 수 있다.

Add virtual nodes

virtual node는 그래프 내의 모든 노드들과 연결되는 가상의 노드를 말한다.

virtual node

예를 들어, 어떤 sparse graph에서 두 노드의 최단거리가 10이라고 하자. 이 경우 messaging이 거의 되지 않는다.

그러나 virtual node를 도입하면, 모든 노드들의 최단거리는 2가 된다. 

virtual node를 도입하여 message passing의 성능을 매우 향상시킬 수 있다.

 

Node Neighborhood Sampling

그래프가 too dense한 경우를 살펴보자.

모든 노드들이 message passing을 하기 때문에 계산량이 매우 증가한다.

All nodes are used for message passing

 

이를 해결하기 위해 일부 이웃 노드들을 (랜덤하게) 샘플링하여 message passing을 하는 방법을 말한다.

 

예를 들어, 첫 번째 message passing은 $B, D$ 노드만 $A$로 message passing한다고 하자.

그리고 다음에는 $C, D$만 $A$로 message passing을 하는 것을 생각해볼 수 있다.

이렇게 해도 임베딩은 모든 노드를 사용한 것과 유사할 것이라고 기대할 수 있다. (그리고 실제로 그렇다)

 

Benefit: computational cost를 매우 줄일 수 있다.

Neighborhood sampleing example