Message Passing and Node Classification

연구를 하면서 머신러닝에 사용되는 Graph에 관해 알아둘 필요가 있어, 관련 기초 내용을 알차게 다루는 Stanford CS224W 강의를 수강하고, 내용을 정리하려 한다.

유튜브 강의 링크는 다음과 같다.

https://www.youtube.com/playlist?list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn

Stanford CS224W: Machine Learning with Graphs

This course covers important research on the structure and analysis of such large social and information networks and on models and algorithms that abstract ...

www.youtube.com

Introduction

Message Passing은 Graph Neural Network (GNN)을 이해하기 위해 꼭 알아두어야 할 개념이다.

이번 글에서 다루는 주요 문제는 node classification으로, network(그래프)에 일부 노드만 label이 주어졌을 때, 다른 노드에 할당할 label을 예측하는 것이다.

이는 앞서 다뤘던 node embedding에 classifier를 추가하여 해결한다.

주어진 node의 label로 unlabeled node의 label을 예측하므로, 정확히 말하자면 semi-supervised node classifiation이다.

Correlation

Network의 노드들 간에는 correlation이 존재한다. 즉, 비슷한 node들은 서로 연결되어있다.

이를 통해 node를 labeling하는 방법을 collective classification이라 한다.

Collective classification의 classical tecunique은 다음과 같다. (이 방법들은 graph를 활용한 deep learning, 즉 GNN의 기초가 된다.)

Relational Classification
Iterative Classification
Belief Propagation

직접 다루지는 않았으나, page rank algorithm에서는 score를 update하지만, collective classification에서는 belief라는 개념을 update한다. Belief란, node의 label이 무엇인지 예측하는 개념으로, 아래에서 자세히 다룰 것이다.

여기서는 correlation에 대해 자세히 알아보자.

Correlation은 가까운 node는 같은 class에 속할 것이라는 개념으로부터 출발한다.

Main types of dependencies that lead to correlation

Network에 존재하는 correlation의 주요 요인은 크게 두 가지로 나눌 수 있다. (정확한 비유는 아니지만 이해를 위해 비유해보았다.)

Homophily (동종 선호) → 유유상종
- 특징이 비슷한 사람은 서로 연결될 것이다.
Influence → 맹모삼천지교 (조금 뜻이 다르긴 하지만, social이 individual에게 영향을 준다는 개념으로 비유해보았다.)
- 사회적 connection이 개개인의 특징에 영향을 준다.

Homophily 개념(즉, 비슷한 node는 서로 연결된다는 개념)으로 node classifcation을 수행하는 방법을 알아보자.

따라서 연결된 node, 즉 이웃 노드들의 label에 따라 unlabeled node의 label을 예측해볼 수 있다.

Node \(v\)의 classification label은 다음과 같은 요인에 영향을 받는다.

\(v\)의 feature
\(v\)의 이웃 노드들의 label
\(v\)의 이웃 노드들의 feature

Semi-supervised Node Classification

요약하자면, semi-supervised node classification task를 정리해보면 다음과 같다.

Graph와 labeled node 일부가 주어졌을 때
Unlabeld node의 class를 찾아야 한다.
이때, network에 homophily가 있다고 가정한다.

예를 들어,

\(n\)개의 node에 대한 \(n \times n\) 크기의 인접행렬 \(\mathbf{A}\)가 있다.

이때 \(Y = \{0, 1\}^n\)은 label을 나타내는 vector이다. 즉, \(Y_v = 1\)이면 node \(v\)의 class가 1, \(Y_v = 0\)이면 class가 0임을 뜻한다.

목표는 unlabeled node들의 class가 1인지, 0인지 예측하는 것이다.

Collective Classification

Collective classification은 correlation을 사용하여 서로 연결된 노드를 동시에 classification한다. Probabilistic framework이며, 다음과 같이 first-order Markov assumption을 만족한다.

\( P(Y_v) = P(Y_v \vert N_v) \)

여기서 Markov assumption은 node \(v\)의 label \(Y_v\)는 이웃 노드 \(N_v\)의 라벨을 통해 정해진다는 것을 나타낸다. (first-order이므로 1-degree neighborhood에 대한 가정이다.)

Collective classification은 아래와 같은 3단계의 과정을 거친다.

Local Classifier : Unlabeled node의 initial label을 할당한다.
- node attributes(features)에 따라 초기 label을 결정한다.
- Standard classification task로, network information을 사용하지 않는다.
Relationanl Classifier : Node 간의 correlation을 파악한다.
- Classifier를 학습하여 특정 노드를 이웃 노드의 label들을 기반으로 labelilng한다.
- Network information(이웃 노드의 정보 + 이웃 노드에 전달된 correlation → network 전반적인 정보)을 사용한다.
Collective Inference : Correlation을 network를 통해 전파(propagate)한다.
- 각 노드에 대해 relational classifier를 적용한다.
- 이웃 노드의 라벨과의 불일치성(inconsistency)이 최소화될 떄까지(수렴할 때까지) 반복하며, network structure가 마지막 prediction에 영향을 준다.

예를 들어, 다음과 같은 그래프가 주어져있다.

빨간색, 초록색은 각각 class 1, class 0인 label을 뜻한다.

각 노드 \(v\)는 feature vector \(f_v\)를 갖고 있을 때, 회색인 unlabeled node \(v\)의 label \(Y_v\)를 예측해야 한다.

이는 semi-supervised node classification task이고, homophily 개념을 기반으로 세 가지 technique을 사용한다. 이 세 가지 technique은 collective classification의 주요 모델이며, 이 글의 핵심이므로, 다시 한 번 정리한다.

Relational Classification
Iterative Classification
Belief Propagation

Relational Classification

Relational classifier는 확률론적 모델이며, node \(v\)의 class probability \(Y_v\)를 \(v\)의 이웃 노드의 class probabilities의 weighted average로 구한다.

그 과정은 다음과 같다.

Labeled node \(v\)에 대해서는 label \(Y_v\)를 ground-truth label \(Y_v^*\)로 초기화한다.
Unlabeled node에 대해서는 \(Y_v = 0.5\)로 초기화한다.
랜덤 순서로 모든 노드 각각에 대해 수렴할 떄까지(혹은 주어진 max ieteration이 될 때까지) label을 update한다.

각 노드 \(v\)에 대해 label \(c\)가 있는 경우, update 수식은 다음과 같이 나타낼 수 있다.

\( P(Y_v = c) = \cfrac{1}{\sum_{(v, u) \in E} \mathbf{A}_{v, u}} \sum\limits_{(v, u) \in E} \mathbf{A}_{v, u} P(Y_u = c) \)

여기서 \(P(Y_v = c)\)는 node \(v\)가 label \(c\)를 가질 확률, \(\mathbf{A}_{v, u}\)는 \(v\)와 \(u\) 사이의 edge의 weight(edge에 weight 정보가 있는 경우)를 나타낸다.

\(\left(\sum\limits_{(v, u) \in E} \mathbf{A}_{v, u} P(Y_u = c)\right)\) 부분은 neighbor node의 class 정보를 합하여 나타내는 term이고,

\(\left(\cfrac{1}{\sum_{(v, u) \in E} \mathbf{A}_{v, u}} \right) \) 부분은 합에 대해 normalize를 해주는 term이다. (\(v\)의 degree로 나눠줌)

Example

예를 들어 살펴보자.

1. Initialize : labeled node는 주어진 label로, unlabeled node는 0.5로(class 1에 포함될 확률이 0.5이므로) labeling한다.

여기서 \(P_{Y_k}\)는 \(P(Y_k = 1)\), 즉 class가 1일 확률을 나타낸다.

2. 1st iteration : 랜덤으로 node 3을 골랐다고 가정하자.

\(N_3 = \{ 1, 2, 4\}\)이므로, \(P(Y_3) = (0 + 0 + 0.5)/3 = 0.17\)로 계산할 수 있다.

같은 방법으로 node 4 → node 5 → node 8 → node 9 순서로 계산했다고 가정하면, 다음과 같은 결과를 얻는다. (node 4를 계산할 때 \(P(Y_3) = 0.17\)로, 계산한 값을 사용한다.

3. repeat iteration : 모든 노드가 수렴할 때까지 같은 과정을 반복한다.

iteration 2 이후에는 다음과 같은 결과를 얻는다.

\(P(Y_9)\)는 1로, 이전과 같은 값이 나왔다. 따라서 node 9는 수렴했다고 판단한다.

이 과정을 모든 노드가 수렴할 때까지, 혹은 max iteration 값에 도달할 때까지 반복한다.

Result : 최종 결과는 다음과 같다.

Relational Classification Example (result)

총 4번의 iteration을 거친 후 위와 같은 결과가 나왔으며, node 4, 5, 8, 9는 class 1 \((\because P_{Y_v} > 0.5)\), node 3은 class 0 \((\because P_{Y_v} < 0.5)\)임을 알 수 있다.

Challenges

하지만 이 방법은 다음과 같은 한계점이 있다.

Convergence가 보장되어있지 않다.
- 그래프가 큰 경우에 취약하다.
Node feature(attribute) information을 사용하지 않는다.

이를 해결하기 위해 iterative classification을 사용한다.

Iterative Classification

Iterative classification에서는 node \(v\)를 분류할 때, 이웃 노드 set \(N_v\)의 label \(z_v\) 뿐만 아니라 노드 \(v\)의 attributes \(f_v\)도 사용한다.

Node \(v\)의 feature vector \(f_v\), \(Y_v\)로 라벨링된 nodes \(v\)를 입력받고, unlabeled node들의 label을 예측한다.

이떄, 총 두 가지 classifier를 학습시킨다.

\(\phi_1 (f_v)\) : node feature vector \(f_v\)를 사용하여 node label을 예측한다.
\(\phi_2 (f_v, z_v)\) : node feature vector \(f_v\)와 summary(\(v\)의 이웃 노드의 labels) \(z_v\)로 node label을 예측한다.

이때 Summary \(\mathbf{z}_v\)는 이웃 노드의 라벨 정보를 요약한 vector로, \(N_v\)의 각각의 label의 개수(비율)에 대한 histogram, \(N_v\)에서 가장 자주 등장하는 label, \(N_v\)에서 서로 다른 label의 개수 등이 될 수 있다.

Iterative classifier가 동작하는 과정은 크게 두 가지 phase로 나뉜다.

Phase 1 : node attributes만 사용하여 분류한다.
1. Training set (classifier 기준으로 training set은 labeled node일 것이다.)을 사용하여 classifer \(\phi_1(f_v)\), \(\phi_2(f_v, z_v)\)를 학습한다. (linear classifier, neural networks 등 활용)
Phase 2 : 수렴할 때까지 반복한다.
1. Test set (classifier 기준으로 test set은 unlabeled node일 것이다.)에 대해, 먼저 \(\phi_1\) classifier로 label \(Y_v\)를 설정하고, \(z_v\)를 계산한 후에 \(\phi_2\)를 활용하여 label을 예측한다.
2. 모든 노드 각각에 대해 반복한다.
  1. 모든 노드 \(u \in N_v\)에 대해 \(Y_u\)로 \(z_v\)를 update
  2. \(z_v\), 즉 \(\phi_2\)로 \(Y_v\)를 update
3. 수렴할 때까지, 혹은 max iteration에 도달할 때까지 반복한다.

단, 이 경우에도 convergence는 보장되지 않는다는 점을 주의하자.

Example

Wep page classification으로 예를 들어보자.

주어진 graph의 node는 web page이고, edge(directed)s는 web page간의 hyperlink이다.

Node feature는 webpage description으로, 예시에서는 간단히 2개의 binary feature로 나타낸다.

이때 webpage의 주제를 예측하는 task를 생각해보자.

Baseline

먼저, iterative classification 과정에서 node feature와 summary vector를 이해하기 위해 간단한 baseline을 살펴보자.

이 baseline은 binary node attribute를 기반으로 page를 구분하는 classifier를 학습시킨다.

\(f_v\)는 node attribute이다.

그런데, 가운데 node를 틀리게 예측했다. 이를 update하는 과정을 알아보자.

위 그림과 같이, 각 노드는 그 노드의 이웃 노드에 대한 summary vector \(\mathbf{z}_v\)를 가지며, 다음과 같이 정의한다.

\(I\) : Incoming neighbor label information vector
\(O\) : Outgoing neighbor label information vector

값을 할당할 때에는 0번 index의 경우 label이 0인 incoming(outgoing) page가 하나 이상 있으면 1, 1번 index의 경우 label이 1인 incoming(outgoing) page가 하나 이상 있으면 1을 할당한다.

따라서 \(\mathbf{z}_v\)는 \(I, O\)를 통틀어 4차원 벡터임을 알 수 있다.

Iterative Classifier

이제 본격적으로 iterative classification 과정을 살펴보자.

1. Train two classifiers : Node attribute vector \(f_v\)만 사용하여 \(\phi_1\)을 (green), \(f_v\)와 \(z_v\)를 모두 사용하여 \(\phi_2\)를 (red) 학습한다.

위 노드들은 training set으로, label이 주어진 node이다.

2. Apply classifier to test set : Test set에 대해 training set으로 학습한 node feature vector classifier \(\phi_1\)만 사용하여 classification을 진행한다. (즉, \(Y_v\)를 결정한다.)

위 그림에서는 가운데 node의 \(Y_v\)를 설정한다. \(\phi_1\)만 사용했을 때에는 틀리게 설정했음을 알 수 있다.

3. Iteration

3.1. 모든 노드에 대해 Relational feature \(\mathbf{z}_v\)를 update한다.

3.2 두 번째 classifier \(\phi_2\), 즉 \(z_v\)와 \(f_v\)를 모두 사용하여 \(Y_v\)를 다시 update한다.

이제 제대로 label을 예측했음을 알 수 있다. 수렴할 떄까지 3번 과정을 반복한다. 반복 후에는 아래와 같이 \(z_v\)가 바뀐다.

가운데 node의 \(Y_v\)는 바뀌지 않고 수렴하였으므로, iteration을 종료한다.

이에 따라 최종적으로 가운데 노드의 label은 1로 결정된다.

Belief Propagation (Message Passing)

Belief propagation이란, graph에서 조건부 확률을 사용하여 특정 node가 어느 class에 속하는지에 대한 정보인 belief를 전달하는 과정이다. Dynamic programming을 사용한다.

이때 사용하는 아이디어가 바로 message passing이다.

Message Passing

간단한 예시를 통해 message passing에 대해 알아보자.

다음과 같은 path graph에 대해, node의 개수를 세는 task를 진행하려 한다. 이때, 각 노드는 이웃 노드에만 message를 전달할 수 있다. (그리고 graph에 cycle이 없다고 가정한다.)

각 노드는 정해진 순서에 따라 이웃 노드로부터 message를 전달받아 이를 update하고 다음 노드로 전달한다.

같은 예시를 tree로 확장시켜보자. Order는 leaves → root 방향이다.

위 과정을 반복하다보면 root node(1번 노드)에서는 최종적으로 7을 얻을 것이다. (1 + 5 + 1)

Loopy Belief Propagation Algorithm

다음 그래프를 보자.

\(i\)가 \(j\)에게 보내는 message는 negihbor인 \(k, u, v\) 노드에게 전달받은 belief일 것이다.

즉, node \(i\)는 nodes \(k, u, v\)의 class 정보를 받고, belief를 update한 후 node \(j\)가 class \(Y_j\)에 속할 확률을 전달할 것이다.

먼저, 관련 notation을 알아보자.

Label-label potential matrix \(\boldsymbol{\psi}\) : 어떤 node와 그 이웃 노드(하나)와의 dependency(correlation)를 나타낸다.
- \(\boldsymbol{\psi} (Y_i, Y_j) \)는 node \(i\)가 class \(Y_i\)에 속할 확률이 주어졌을 때, node \(j\)가 \(Y_j\)에 속할 확률에 비례한다.
Prior belief \(\phi\) : \(\phi(Y_i)\)는 node \(i\)가 \(Y_i\)에 속할 확률에 비례한다.
message \(m_{i \rightarrow j} (Y_j) \) : \(j\)가 \(Y_j\)에 속할 것이라고 추정하는 \(i\)의 message
\( \mathcal{L} \) : 모든 classes(labels)의 set

1. 모든 message를 1로 초기화한 후, 각 노드에 대해 다음을 반복한다.

\( m_{i \rightarrow j} (Y_j) = \sum_{Y_i \in \mathcal{L}} \boldsymbol{\psi} (Y_i, Y_j) \phi_i(Y_i) \prod_{k \in N_{i} \backslash j} m_{k \rightarrow i} (Y_i), \quad \forall Y_j \in \mathcal{L} \)

식의 의미를 알아보자.

\( \left( \sum_{Y_i \in \mathcal{L}} \boldsymbol{\psi} (Y_i, Y_j) \phi_i(Y_i) \right) \) 부분은 label-label potential과 prior의 곱을 모든 states(labels)에 대해 더한다는 의미이다.

\( \left( \prod_{k \in N_{i} \backslash j} m_{k \rightarrow i} (Y_i) \right) \)부분은 \(i\)가 받은 모든 메시지(따라서 \(j\)는 제외된다.)를 곱하는 것을 의미한다.

2. 각 node에 대한 belief를 계산한다.

Message 값이 수렴한 후에, belief \(b_i (Y_i)\)는 class \(Y_i\)에 속할 node \(i\)의 belief이며, 다음과 같이 계산한다.

\( b_i(Y_i) = \phi_i(Y_i) \prod_{k \in N_i} m_{k \rightarrow i} (Y_i), \quad \forall Y_i \in \mathcal{L} \)

\(k\)는 \(i\)의 이웃 노드 중 하나이다. 모든 이웃 노드의 message를 곱한 값에, \(i\)의 prior와 곱하여 belief를 구한다.

하지만, Loopy belief propagation은 cyclic graph에서는 사용할 수 없다.

이는 cyclic graph에서는 서로 다른 subgraph에서의 message가 독립적이지 않기 때문이다.

알고리즘을 진행하면 위와 같이 loop를 돌게 되고, 6번 과정에서 O표시한 두 값들은 독립적이지 않다. (5번 결과가 1번 결과의 영향을 받았기 때문이다.) 따라서 결과의 신빙성이 사라진다.

하지만 실제로는 cyclic의 영향이 약하다. Cycle이 매우 길거나, cycle 도중에 weak correlation을 갖는 경우가 많기 때문이다.

Properties of Belief Propagation

Belief propagation에서는 potential function을 parameterize하여, 이를 학습할 수 있다.

장점은 구현이 쉽고, 병렬화 처리가 가능하다는 점이다. 또한, potential의 형태를 바꾸어 어떤 graph model에도 적용이 가능하다. (예를 들면, potential을 더 높은 차원으로 \(\boldsymbol{\psi}(Y_i, Y_j, Y_k, Y_v \dots )\)와 같이 설정하여 일반화할 수 있다.)

하지만, (특히 closed loop를 많이 포함할 경우) 여전히 convergence가 보장되지 않는다는 한계가 존재한다.

저작자표시 비영리 변경금지

Message Passing and Node Classification