Meaningful

Meaningful

Greeting :)

[논문리뷰]Identity-Aware Graph Neural Network

Date:     Updated:

카테고리:

1. Problem Set

1) Limitation of Existing GNN Architecture

  • Fail to capture the position(location) of the node within the broader context of the graph structure
    • 즉, Graph에서 노드들의 위치를 구분하지 못한다. 다시 말해 노드들의 위치 정보가 부족하다.

2) Limitation of One-hot Encoding

  • Models trained with one-hot encodings cannot generalize to unseen graphs, and arbitrarily deep GNNs still cannot distinguish structurally isomorphic nodes
    • One-hot encoding으로 모델을 학습시키면 Unseen Grpah에 대해서 일반화하지 못한다. 즉, Graph의 Isomorphic(Symmetric) node를 구별하지 못한다.

3) GNNs also Can’t perfectly perform in Structure-Aware

기존의 GNN 기반 모델들은 Structure-aware 이다. 하지만, 그렇다고해서 Structure-aware task에 해당하는 모든 문제를 정확하게 해결하지 못한다.

  • Three levels of failure cases
    1. Node Level
    2. Edge Level
    3. Graph Level

1. Node Level

1

먼저 Node Level에서 GNN의 문제점을 살펴보면, 서로 다른 Input graph이 GNN을 통과했음에도 같은 모양의 Embdedding 결과를 보여준다. 즉, GNN의 Computational Graph에서 \(v_1\)과 \(v_2\)를 중심으로 하는 Tree(computational graph)는 Isomorphic하기 때문에 GNN에서는 두 노드를 같은 노드로 인식하게 된다. 임베딩 결과가 구조적으로 동일하기 때문에 \(v_1\)과 \(v_2\)를 다른 Class로 분류하지 못한다.(위의 Task는 Node Classification)

참고로 Computational graph는 다음과 같은 과정으로 만들어진다.

1

2. Edge Level

1

Edge Level에서 GNN의 문제점을 바라보면 위의 task는 Link prediction인데, 위의 Input을 보면, \(v_0\)에서 \(v_1\)또는 \(v_2\)로 Edge를 연결할 지를 정하기 위해 GNN을 이용하면 두 노드 모두 기준점 \(v_0\)에서 1-hop씩 direct하게 연결되기에 결국 임베딩 결과가 같은, Computational graph가 동일하게 나온다. 결론적으로 Link Prediction task를 해결하지 못한다.

3. Graph Level

1

Graph-Level 수준에서 풀고자 하는 task는 Graph classification으로 Node level에서와 마찬가지로 서로 다른 Input임에도 임베딩 결과가 같아 서로 다른 Class로 구분하지 못한다.

  • GNN
  • GCN
  • GAN
  • GIN
  • GraphSAGE

  • P-GNN

  • Expressive neural networks beyond 1-WL test
  • Graph Neural Networks with inductive coloring
  • GNNs with anisotropic message passing

3. Method

1) Idea: Inductive Node Coloring

1

Identity-aware GNN의 Key idea는 바로 “Coloring“이다. 특정 노드에 색깔을 입히는 것이다. 여기서 특정 노드에 색깔을 입힌다는 것은 다시 말하면 특정 노드를 구별할 수 있게 Attribute를 추가한다는 것이다.

이렇게 하면 위의 그림에서처럼 \(v_1\)에 대한 임베딩을 할 때 \(v_1\)을 계속해서 추적할 수 있다. 이 때 “Coloring”을 Inductive라고 한다. 이 Inductive는 node 순서나 Identity에 대해서 변하지 않는다.

Coloring으로 인해서 Subtree를 비교하면, 비교할 수 있는 기준점이 생겨 같은 Computational graph임에도(= 같은 Structure) Class 구분이 가능하다.

1

Coloring으로 Node Classification & Graph Classification Task 해결

1

Coloring으로 Link Prediction Task 해결

Link Prediction을 잠시 살펴보면, Link Prediction에서는 노드쌍을 분류하는 것이 목표이고 \(v_0\)를 coloring한 후 GNN 아키텍쳐를 통해 임베딩한다. 이 때, \(v_0\)에 대한 일종의 Constraint가 생긴 것이므로 \(v_1\)과 \(v_2\)에 대해 서로 다른 임베딩 결과가 나오게 된다.

Coloring을 이용하면 자연스럽게 노드들은 두 가지로 카테로리화된다.

  • Coloring Node
  • Non-coloring Node

2) Method of Coloring 1

1

Coloring을 하는데 핵심은 바로 Heterogenous Message Passing이다. 기존의 GNN은 Message computation과 aggregation을 하나의 Neural network를 통해서 진행한다. 즉 같은 방법을 모든 노드에 똑같이 적용하기에 Isomorphic에 취약하다. 위의 왼쪽 그림을 보면 하나의 Neural network를 이용해 모든 노드에 Message passing을 진행하는 것을 볼 수 있다.

반면 오른쪽 그림을 보면, 서로 다른 Neural network가 서로 다른 노드들에 대하여 Message Passing을 진행한다. 이렇게 되면 Neural network에 따라 노드들이 카테고리화된다. 이것이 Coloring이다.

Heterogenous라는 것은 결국 다른 타입의 메세지 패싱이 다른 노드들에 적용되는 것이다.

3) Method of Coloring 2

Inductive identity coloring

주어진 노드\(v \in \cal G\)를 K-layer ID-GNN을 통해 임베딩하려면 먼저 K-hop ego network \(\cal G_v^{(K)}\)를 먼저 추출하고, ego network의 중심 노드를 coloring한다.
ego network로 인해 임베딩 과정에서 두 가지 타입으로 Categorized 된다.

  • Categorized
    • Nodes with coloring
    • Nodes without coloring

이 coloring technicque를 Inductive라 한다. 그 이유는, 비록 배열되어 있더라고 ego network의 중심 노드에 따라 이웃 노드들이 변할 수 있기 때문이다.

Heterogenous message passing

총 K 번의 라운드(Iteration) Message Passing은 추출된 모든 ego network에 적용된다. \(h_v^{(K)}\)는 K라운드 적용된 뒤에 노드 \(v\)의 Embedding Representation(노드 임베딩의 결과)이다. 그 식은 다음과 같다.

1

ID-GNN의 Message Passing은 오른쪽 식이다. 이 식의 기본꼴은 왼쪽 식인 기존의 GNN과 동일하다. 여기서 다른 것은 Indicator function \(\mathbb{1}[s=v]\) 이다. 앞서 말했듯, Coloring으로 인해 ID-GNN에서는 노드들이 두 가지로 Categorization되어있다.

  • Indicator function \(s = v\)
    • s = v = 1
      • nodes with identity coloring
    • s = v = 0
      • nodes without identity coloring

따라서, <span style = color:red>Message passing이 Coloring된 노드들과 Coloring되지 않은 노드들이 따로 되는 것</span>이다.
(그림에서처럼 Message Passing에 다른 Neural Network를 이용)

4) GNN vs ID-GNN

1

Cycle & Length
먼저 Cycle과 Length에 대해 간단히 설명하자면, 왼쪽의 3개의 노드로 구성된 그래프의 경우 \(v_1\)에서 다시 \(v_1\)으로 되돌아 오려면, 총 3개의 edge를 이동해야한다. 즉 노드를 이동할때 이를 배열로 나타내면 \(v_1\) ➜ \(v_2\) ➜ \(v_3\) ➜ \(v_1\)으로 3-hop을 이동한 것과 같다. 이 경우 3-hop이 1 cycle이 되는 것이다.(왼쪽은 4-hop이 1 cycle.)

Length는 이동한 node의 수이다.

1

GNN과 ID-GNN의 차이점을 시각화하면 위와 같다. GNN의 경우 같은 Neural Network를 이용하여 Message Passing을 하고 Node Embedding을 하였다. 그래서 서로 다른 Input에 대해서 같은 모양의(Structure) Graph가 나오고 그 결과가 Isomorphic하기에 Class 분류가 불가능하다.

반면, ID-GNN은 ID-GNN을 보면 서로 다른 Input에 대해 같은 모양의(Structure) Graph가 나오지만 Identity attribute가 추가된 노드들로 인해 Class 분류가 가능하다. ID-GNN에서 \(v_1\)에 대한 임베딩 결과로 나온 computational graph를 보면 1 cycle에 3-hop이고, length가 3인 computational graph에서 마지막으로 coloring된 노드로의 경로(Path)가 2개이므로 Cycle이 2인 것이다. 반면, \(v_2\)의 경우 1 cycle에 4-hop인데, computational graph가 최대 3-hop까지만 나와 있으므로 Cycle 없다.

5) ID-GNN Fast

1

논문에서는 ID-GNN의 간소화 버전도 함께 제시한다. 앞서 말한 original ID-GNN을 간소화하려면 간단하다. Input으로 추가적인 Attribute(Information)을 더 넣어주면 된다. 추가적인 정보는 Computational graph(Tree)의 Level별로 Coloring된 노드의 갯수를 카운팅하여 벡터화한 것이다.

이를 Augmented node feature이라고 합니다. 이러한 Identity information을 하면 굳이 Heterogenous message passing을 필요로 하지 않는다.

6) Computation & Pseudo Code

1

코드를 보면 Ego라고 쓰여진 부분이 있다. 특정 노드를 중심으로 뻗어나가는 graph를 Ego graph이다. 이는 즉, Coloring된 노드를 중심으로 뻗어나가는 그래프를 만든다는 것이다. Input graph에 특정 노드를 Coloring해서 넘겨주는 것이 ID-GNN의 핵심이다.

따라서 매 스텝마다 Ego Graph를 만들어주고 K 번을 반복하면서 Message computation과 aggregation을 해준다. 그 수식은 오른쪽과 같습니다. 여기서 주의할 것은 기존의 GNN은 MSG와 message embedding값에 영향을 주는 요소가 Input node \(u\)나 \(v\)입니다. 하지만, ID-GNN에서는 s = v = 1이면 coloring된 노드를 의미하고 0이면 색칠이 되지 않은 노드들을 의미해 스텝이 나뉘게 된다.

전반적인 구조는 GNN과 비슷하지만 EGO graph를 잡아 coloring해 주는 것과 embedding step에 차이점이 있다.

ID-GNN은 하나의 아키텍쳐가 아닌 하나의 방법론으로 모든 GNN 기반의 아키텍쳐에 적용가능하다.

4. Experiment & Result

1) Data Structure

1

실험에서 사용된 데이터 셋은 총 8개로, 위의 4개는 오직 graph property prediction task를 푸는데 사용되었고, 8개 모드 real-world prediction task를 푸는데 사용되었다.

두 task가 해결하려는 문제는 모든 level에서의 task로 같지만, 세부적인 것은 조금씩 다르다.

2) Result of Graph Property Task

1

먼저 Graph Property Prediction Task의 결과이다. Node Classification의 경우 Original ID-GNN과 ID-GNN-Fast가 기존의 GNN모델보다 성능이 우수합니다. 또한 GraphSAGE의 경우 ID-GNN-Fast를 아키텍쳐에서 두드러진 성능 향상을 보였다.

다음으로는 Edge Level Task이다. Edge Level Task에서 놀라운 점은 original ID-GNN 모델이 압도적인 성능 향상을 보여 주었고, 그 결과는 거의 정확하게 예측해내는 것을 볼 수 있다.

마지막으로 Graph Classification인데, 여기서는 ID-GNN-Fast 아키텍쳐가 가장 눈에 띄는 성능향상을 보여주었고, 세 개의 테스크중 가장 높은 성능향상 수치를 보여주었다.

3) Result of Real-World Task

1

노드 클래시피케이션의 경우 1에서 1.6%라는 작지만, 그래도 유의미한 성능향상을 보여주었다. 다만, GIN 과 GraphSage에서 Cora dataset을 사용한 경우 기존의 GNN 모델이 더 성능이 좋 은 것을 볼 수 있는데, 이는 논문에서는 풍부한 노드 피쳐의 수가 결론적으로는 이 task에서 graph structure의 중요성을 희석시키고 결국은 Identity 정보를 추가한 것이 무의미해지게 된것 이라 추측한다.

링크 프레딕션의 경우 original ID-GNN이 가장 좋은 성능을 보여주었다. 하지만, random graph에 대해서 낮은 성능향상을 보여주었는데 논문에서는 이런 Synthetic graph 즉, 입베딩되는 그래프의 랜덤성으로 인해 Positive edge와 negative edge 의 경계를 모호하게 만들어 버린다 추측한다. 즉, 부호가 있는 Signed-Node들을 Identity Information이 오히려 그 의미를 퇴색시킨다고 추측한다.

마지막으로 Graph Classification인데, 역시 Original ID-GNN에서 가장 두드러지는 성능향상을 보여주었다. ENZYMES 데이터셋의 경우 ID-GNN-Fast 기반의 GNN에서 아주 높은 성능향상을 보였다.

5. Contribution

  • Propose ID-GNNs as a general solution in existing GNNs, with rich theoretical and experimental result(Extracting Ego Graph using coloring)
    • 기존의 GNN이 가지고 있던 한계를 타파하고 엄청난 성능향상을 보여주었다는데 의의가 있다.
  • Present Synthetic and real-world tasks to reveal failure modes of existing GNNs and demonstrate the superior performance of ID-GNNs over both existing GNNs and other powerful networks.
    • Graph Property Prediction Task뿐만 아니라 실제 세계의 그래프 문제에도 적용해 성능 향상을 보여주었다는 것이다. 이를 통해 기존의 GNN보다 성능적으로 더 우수하다는 것을 입증했고, General form으로서 ID-GNN을 써야하는 이유를 보여주었다. 즉, 모든 GNN기반의 아키텍쳐에 적용가능하다.

Reference

Paper: Identity-aware Graph Neural Network
Stanford GNN Lecture book
Stanford GNN Lecture

GR 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)