Meaningful

Meaningful

Greeting :)

[논문리뷰]Position-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를 구별하지 못한다.

1

  • GNN
  • GCN
  • GAN
  • GIN
  • GraphSAGE

3. Method

1) Node Embedding

  • Vector Representation of nodes in graph

즉, 그래프에 있는 노드 정보들을 벡터로 표현하는 것을 노드 임베딩(Node Embedding)이라고 한다. 노드 임베딩을 하는 방법으로는 크게 세 가지 방법이 있다.

  • Node Embedding
    • Graph Neural Networks(GNNs)
    • Matrix-factorization
    • Random-walk-based(DeepWalk, node2vec,…)

1

위의 그림은 node2vec 아키텍쳐의 노드 임베딩을 시각화 한 것이다. node2vec 아키텍쳐는 자연어 처리(NLP)에서 많이 사용되는 모델이다. 간단히 설명하면 어떤 그래프가 주어졌을 때, Random-walk를 통해 graph smapling을 하고 만들어지 노드 페어(Node pair, 노드 쌍)를 Word2Vec 알고리즘을 적용해 임베딩 공간(Embedding space)를 표현합니다. 하지만 이런 Random-walk base method의 경우 Transductive Setting을 가지고 있고 이런경우 노드의 정보를 제대로 사용하지 못합니다. GNN의 경우 애초에 Node feature 정보가 들어갈 수 있는데, Random-walk의 경우 Node property를 넣지 못한는 단점이 있습니다.

2) Structure-aware & Position-aware

  • Structure-aware
    • 어떤 노드 \(v_i\)가 주어졌을 때, k-hop까지 \(N_1~N_q\)까지 표현을 하는 어떤 함수 \(g\)
    • 이 g를 이용한 것이 Structure-aware Embedding이다.
    • GNN의 경우 Structure-aware이다.

image

  • Position-aware
    • 논문에서 Random-walk 아키텍쳐의 임베딩 방법을 Position-ware Embedding이라고 한다.
    • 여기서 \(g\)함수는 어떤 노드 \(v_i, v_j\)의 최단거리(Shortest Path, \(d_{sp}\))와 같아지게 하는 함수
    • 이러한 임베딩 방법을 Position-aware Embedding이라고 한다.

image

일반적으로 두 Structure-aware Embedding은 Position-Aware Embedding가 아니다.

Proposition
There exists a mapping function \(g\) that maps structure-aware embedding to position-aware embeddings, if and only if no pair of nodes have isomorphic local \(q\)-hop neighborhood graphs

논문에서 제안하는 것은 ‘만약에 어떤 노드 페어든, Isomorphic한 특성을 따르지 않는다면 이 Structure-aware embedding을 Position-aware embedding으로 mappong할 수 있는 함수 \(g\)가 있다.’ 이다.

3) Limitation of Existing GNN

image

  • Can’t capture position(location) of node within a graph
  • GNN can’t classify \(v_1\) and \(v_2\) because of isomorphic network neighborhoods

Graph Neural Network(GNN)은 Structure-aware embedding 방식을 채택하고, 이는 어떤 그래프가 주어졌을때 노드들의 정확한 위치를 Detect하지 못한다. 그래서 Vertex \(v_1\)과 \(v_2\)를 Isomorphic Characteristic 떄문에 구분하지 못한다.

이를 타래의 그림처럼 rooted 된 subtree형태로 바꿔 표현하면 되면 사실상 \(v_1\)의 subtree와 \(v_2\)의 subtree가 같은 구조이므로 \(v_1\)과 \(v_2\) 노드를 같은 노드로 판별하게 된다.

이러한 특성이 문제가 되는 이유는 분자 구조 예측이나 Social-Network 문제를 풀 때 문제가 된다. 두 문제의 경우 모두 Node들의 위치가 중요하다.

4) Position-aware의 핵심

image

이러한 한계점으로 논문에서는 Position-aware Embedding을 제안한다. 전체적인 process는 위의 그림과 같다.

여기서 Focus해야 할 것은 두 가지이다. 첫번째로 Anchor-set Selection이다. Anchor-set은 간단히 말하면 노드의 위치 정보를 계산하기 위해 기준점이 되는 노드 셋을 Sampling하는 것이다.

그리고 두 번째는 역시 Position-aware Node Embedding이다. 주어진 노드의 거리를 계산해서 정보를 반영하는 임베딩이다.

결국 전체적인 프로세스는, 먼저 Anchor-set을 통해 Sampling을하고 이를 통해 노드 임베딩을 진행시켜줍니다. 이렇게하면 노드들의 Positional information을 알 수 있습니다. 임베딩 이후 Message Computaion과정을 통해 계산을 하고 이를 Message Aggregation을 통해 취합해 줍니다.

  • Anchor-set Selcetion
  • Position-aware Node Embedding

5) Anchor-Set Selection

Rely on Bourgain Theorem when selecting achor-sets in P-GNNs

  • Existance of a low distortion embedding

  • \(O(log^2n)\) Anchor-set

  • Anchor-set size: Exponentially distributed

  • Size of Anchor-set
    • Small set: Enough provide positional information, but hit ratio is small
    • Large set: High sample efficiency, but little information on position

논문에서는 볼겐 정리(Bourgain’s Theorem)에 근거하야 Anchor-set Selection을 제안하였다. 이 정리에 의하면 \(O(log^2n)\)만큼의 Sampling set을 추출하면 왜곡(Distortion)이 가장 적어지며, 그렇기에 Embedding을 했을때 가장 유의미하다.

이렇게 추출된 anchor-set들의 Size는 다양하다. 다양하게 추출해야하는 이뉴는 Small set과 Large set들이 각각 장단점을 가지고 있고, 다양한 크기의 set을 추출해서 서로의 장단점을 보완해주기 위함이다.

Small set으로 sampling하면 좀 더 Specific한 subgraph를 표현하기에 그 만큼 Position을 표현하기에 유용하지만, 자칫 기준점으로부터 거리가 너무 멀어질 수 있다.

Large set의 경우는 노드간의 계산을 할 수있으나 노드의 Position을 설명하는 파워는 줄어든다. 따라서, Position과 Set의 크기는 Trade-off 관계에 있다.

image

따라서, 논문에서는 Anchor-set의 개수를 \(log^2n\)개만큼, 다양한 크기를 추출해 사용하였다.

  • P-GNNs \(k\, = \, clog^2n\) Random anchor-set
    • k개의 anchor-set을 selection하고 여기서 c와 n은 Hyperparameter이다.
    • Denoted as \(S_{i,j}\subset V, i = 1, \cdots, logn, j = 1, \cdots, clogn\)
  • Sample each node in \(V\) independently with probability \(\frac{1}{2^i}\)

6) Message Conputation & Aggregation Function

Sampling이 끝났으면 임베딩을 하기위해 계산을 하는 과정이 필요하다. 이를 Message Computation이라고 한다. Message conputaion function \(F\) 를 이용해 이 과정이 진행된다.

(1)Message Computation

image

Message Computation Function의 경우 크게 두 가지 정보를 필요하다. 먼저 q-hop까지의 최단거리이다. 최단거리를 정석적으로 계산을 하면 모든 노드들에 대해 최단거리르 계산해야 한다. 하지만, 그렇게 할 경우 Computation Complexity가 기하급수적으로 증가하고 알고리즘 성능 평가에 치명적이다.

따라서 논문에서는 한가지 대안을 제시하는데 이것이 바로 q-hop까지의 최단거리만을 계산하고, 그거보다 멀리있는 노드들의 거리는 무한대로 처리해버리는 것이다. 실제로 이렇게 알고리즘을 실행하여도 모든 최단거리를 계산하는 것과 크게 차이가 나지 않는다. 계산된 q-hop까지의 거리를 \(d_{sp}\)(Shortest path distance)라고 한다. 이 최단거리를 Score로 나타내주기 위해 변형을 해주고 그 식이 바로 \(s(v,u)\)이다. 이때, v와 u는 각각 다른 노드를 의미한다.

최단거리가 Score값으로 변환되었으면 이제 이를 이용하여 Message computation function을 정의해야 하는데, 그때 그 과정에서 Feature Information을 같이 계산하게 된다. 즉, F는 두 노드의 Shortest path 정보인 Score와 노드 하나하나의 feature 정보를 곱해 계산된 식을 의미한다. feature 정보는 \(h_v\)와 \(h_u\)로 표시하고, 이 두개를 Concatenation한 후 Score값과 곱해준 것이 F이다. \(F(v,u,h_v,h_u) = s(v,u)CONCAT(h_v,h_u)\)이다.

(2)Message Aggregation

image

다음으로는, 이렇게 계산된 결과를 Aggregation한다. 논문에서는 이 정보(Message computation 결과)들을 취합할때 Mean(평균)을 이용한다. 즉, 벡터들의 평균값을 가지고와서 Aggregation을 한다. 이 때 취합을 하는 함수를 \(AGG\)라 한다.

  • \(AGG_M\) = Mean vector로 aggregation
  • \(AGG_S\) = Vector Sum을 통해 aggregation

7) Pseudo Code of P-GNNs

image

Multiple P-GNN layer를 Pseudo Code로 구성한 것이다. 총 k개의 random anchor-set을 추출해서 사용하였다. 위의 첫번째 빨간 네모 상자안의 부분이 Message computation과 aggregation 이 일어나느 부분이다. 여기서 중요한 것은 k 개의 랜덤한 anchor-set을 매 iteration마다 새롭게 추출해야한다. 이렇게 추출된 acnhor-set과 주어진 노드로 두 과정을 진행한다.

그리고 나서 그 아래 박스를 보면 \(Z_v\)가 있다. 이거는 Message computation과 aggregation이후의 임베딩 결과값을 Weight와 곱한 후 Nonlinearity를 먹 것이다. 이렇게 하면 임베딩된 Feature Vector가 나오게 된다. 여기서 주의할 점은, \(Z_v\)의 각각의 비트는 특정 위치를 의미한다.

그 아래 \(h_v\)에 관한 부분이 있다. 이거는 한 번 스텝을 돌때마다 Anchor-set을 새롭게 추출한다고 했는데, 그러면 당연히 노드의 포지션은 스텝마다 변하게 되므로 거리고, 포지션도 달라지므로 이 것이 바로 다음 레이어로 넘어가면 안되기 때문에 다시 한 번 더 Anchor-set에 대해 Aggregation을 취해주는 부분이다.(F를 계산할때의 \(h_v\)와는 다르 것!!!)

4. Experiment & Result

1) Data Set

image

논문에서 P-GNNs 를 이용해 푼 문제는 크게 1) Link prediction task와 2) Pairwise node classification task 이다.

각 Task를 해결하기 위해 Task당 3개의 데이터 셋으로 실험을 진행하였다.

2) Learning Method

논문에서 실험을 하기 위해 두가지 Learning Method를 사용했다.

1. Transductive Learning

  • 고정된 노드 순서를 가진 그래프를 통해 Model Training과 Test ➜ 즉 순서가 중요 !!
  • Unique한 One-hot identifiers 이용하여 node attribute를 확대

Transductive Learning은 고정된 노드 순서를 가진 그래프를 통해 Model train과 test를 진행하는 방법이다. 즉, 순서가 중요하다. GCN을 예로 들면 Node feature를 계산하고 aggregation한 후 다음 레이어로 넘어갈 때 이 노드 순서가 문제가 되는 경우가 있다. 이러한 문제를 방지하기 위해서 aggregation step을 거쳐서 진행한다.

이처럼 노드 순서를 구별하기 위해 One-hot Identifier를 이용해서 노드 attribute가 없는 노드들에 적용해 사용한다.

2. Inductive Learning

  • Pairwise node classification ➜ 노드 pair가 주어졌을때 이 class에 속하니? 안속하니? ➜ Unseen graph에게 우치 정보를 전달 가낭
  • 노드와 상관없는 attribute를 이용해서 train과 test진행

Inductive Learning은 Pairwise node classification 문제를 해결하는데 사용되었다. Generalization이 필요하기 때문에 노드 순서를 신경쓰지 않는 방향으로 진행한다. 그래서 노드 순서와는 전혀 상관 없는 attribute를 사용해서 진행하였다.

참고
Transductive learning이라는 것은 결국 Test set과 Train set을 구분하지 않고 모델을 학습시킨디 그 학습시킨 데이터의 다른 파라미터를 이용해 테스트를 진행하는 것이다.
Inductive learning은 우리가 일반적으로 아는 Supervised Learning로 function parameter가 주어진 labeled data로 학습한다.

3) Result

image

Table 1에서 위의 4개 행이 기존에 존재하던 GNN모델에 대한 결과이다. GCN, GraphSAGE, Graph Attention 그리고 Graph Isomorphic 네트워크에이다. 이번에 Column(열)을 보면 Grid-T와 Communities-T가 있는데 T는 Transductive learning 셋팅을 의미한다. 즉, One-hot identifier를 줬을때와 안줬을때를 비교한다.

여기서 흥미로운 점은 Transductive Setting을 줬을때 일반적인 GNN도 성능이 좋은 것을 볼 수 있는데, 이는 One-hot encoding 정보를 노드 Attribute에 줬을때 일반적인 GNN도 어느정도 구별을 할 수 있다는 것을 말합니다. 그래서 P-GNN의 성능을 어느정도 다라간다고 할 수 있다. 하지만, 단점으로는 노드 attribute가 one-hot으로 들어가게 되면 노드의 개수만큼 feature vector가 들어가므로 dimension이 엄청 커지게 되고 행렬 곱의 계산이 매우 복잡해져 Computation complexity가 증가한다.

P-GNN의 경우 Position Information을 자체적으로 계산하므로 feature가 있든 없든 성능에 영향을 미치지 않는다고 한다. 따라서, 만약에 노드에 feature가 어느정도 정보력이 있으면 Position Information을 넣었다 해도 성능 향상이 두드러지지 않는다고 설명한다.

마지막으로 P-GNN-F와 E에서 F는 q-hop의 threshold를 주어 최단 거리를 계산한 것이고, E는 모든 노드의 최단 거리를 계산하여 진행한 것이다. 네트워크가 너무 커지면 실험에서처럼 2-hop 의 Threshold를 주어도 성능이 괜찮음을 볼 수있다.

5. Contribution

  • Node Positional Information을 GNN에 성공적으로 접목시켰다.

  • GNN의 Isomorphic한 그래프에 대해서도 성공적으로 Node classification을 할 수 있게 되었다.

Reference

Youtube 발표
CS224W: Machine Learning with Graphs | 2021 | Lecture 16.2 - Position-Aware Graph Neural Networks
Paper: Postion-Aware Graph Neural Network

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

댓글 남기기

최근 글 10 개 :)