CS224W - (8) Label Propagation on Graphs
Introduction
그래프가 주어져있습니다. 그 그래프는 일부 노드에만 레이블이 있습니다. 그러면 다른 나머지 노드에는 어떻게 레이블을 부여할 수 있을까요? 가령 주어진 네트워크로 온라인 사기 탐지를 한다고 할 때, 일부 노드는 사기꾼이고 일부 노드는 일반인이면 나머지 다른 노드들은 어떻게 구분할 수 있을까요? 지금까지 다룬 내용 중에서는 노드 임베딩을 활용할 수 있습니다. 주어진 노드를 활용해 준지도학습(semi-supervised learning) 을 하는 것이죠.
하지만 이번 포스트에서는 노드 임베딩이 아닌 다른 방법인 레이블 전파(label propagation) 에 대해서 알아보도록 하겠습니다. 레이블 전파의 개념은 네트워크에는 상관 관계가 있다는 것입니다. 연결된 노드는 같은 레이블을 공유하는 경향이 있다는 것이죠. 이처럼 네트워크에서 노드의 행동이 상관관계가 있다는 이유에 대한 두 가지 설명이 있습니다.
Homophily and Influence
호모필리(Homophily)
유유상종 효과라고도 불리는 호모필리는 어떠한 개인이 자신과 비슷한 다른 사람들과 어울리고 유대감을 형성하는 경향을 일컫습니다. 이런 경향은 연령, 성별, 조직 내 역할 등 다양한 속성을 기반으로 한 여러 네트워크 연구에서 관찰된 바 있습니다. 예를 들어 같은 연구 분야에 집중하는 연구자들이 서로 인맥을 쌓을 가능성이 더 높습니다.
Easley and Kleinberg, 2010
또 가장 쉬운 예로는 온라인 소셜 네트워크 서비스가 있습니다. 노드는 사람이 되고 엣지는 일종의 친구 여부가 되는거죠. 노드 색깔은 그들의 관심사에 해당합니다. 위 네트워크를 보시면 동일한 관심사를 갖는 사용자끼리 뭉쳐있는 것을 확인할 수 있습니다.
영향력(Influence)
사회적 관계가 개인의 특성에 영향을 미칠 수 있다는 내용입니다. 예를 들어 친구 중 한 명에게 저와 같은 장르의 음악을 좋아할 때까지 본인의 취향에 맞는 음악을 계속 추천하는 경우가 있습니다.
네트워크에서 노드 상관관계를 활용하기
레이블 전파(Label Propagation)
레이블 전파는 네트워크 전체에 노드의 레이블 정보를 전파한다는 아이디어에서 비롯됐습니다. 노드 $v$의 클래스 확률 $Y_v$ 는 이웃 클래스 확률의 가중 평균이 되는거죠. 우선 식별되어 있는 노드는 모두 실제 레이블 값으로 초기화합니다. 레이블이 지정되어 있지 않은 노드는 모두 0.5로 초기화합니다. 그리고 최대 반복 횟수에 도달하거나 어느 정도 확률값이 수렴할 때까지 모든 노드를 무작위 순서로 업데이트합니다. 레이블이 지정되지 않은 노드는 다음 수식으로 업데이트됩니다.
\[p^{(t+1)}(Y_v = c) = \frac{1}{\sum_{(v, u) \in E} A_{v, u}} \sum_{(v, u) \in E} A_{v, u} P^{(t)}(Y_u = c)\]만약 엣지가 가중치에 대한 정보를 갖고 있다면 $A_{v, u}$는 엣지 가중치로 대체할 수 있습니다. 이 계산을 수렴할 때까지 계속 진행하면 됩니다.
레이블 전파의 수렴은 노드의 레이블 확률값의 변화가 매우 적어졌을 때로 정의합니다. 따라서 모든 노드 $v$에 대하여 수렴 기준은 다음과 같습니다.
몇 번의 반복을 하고 나면 다음과 같이 수렴하는 모습을 볼 수 있습니다.
이 방식은 문서 분류, 스팸이나 사기 탐지 등에 많이 활용됩니다.
레이블 전파는 단순하지만 수렴이 매우 느릴 수 있고 또한 수렴이 보장되어 있지 않습니다. 게다가 노드 어트리뷰트를 하나도 사용하지 않습니다. 노드의 어트리뷰트나 피처 정보를 쓰기 위해선 어떻게 해야 할까요?
Correct & Smooth
OGB Leaderboard snapshot at Jun 26, 2023
Correct & Smooth (C&S)는 가장 최신의 노드 분류 기법입니다. 레이블 전파 기법은 위에서 다루었듯이 추가적인 정보나 추가적인 피처를 사용하지 않습니다. GNN의 경우 추가적인 정보를 많이 활용하지만 느린데다 레이블들이 서로 상관관계가 있다고 가정하지 않습니다.
GNN은 모델의 가중치를 학습할 때 레이블을 활용합니다. 모델이 주어졌을 때 서로 다른 노드에 대한 예측값은 독립적이고 상관관계가 없습니다. 대신 레이블 전파 방식은 예측에 레이블을 직접 활용하죠.
Node features are overwhelmingly predictive!
만약 노드 피처가 위 그림처럼 매우 강력한 수준으로 예측력을 갖고 있다면 각 노드에 대해 상관관계 없는 예측을 만들어도 문제가 없습니다. 하지만 아래와 같이 예측력이 낮다면 큰 문제가 생깁니다. 이 경우엔 오히려 피처를 무시하는 레이블 전파 방법이 더 나은 성능을 보이죠.
Catastrophic case
이런 문제를 모두 해결할 수 있는 방법이 바로 Correct & Smooth 입니다. 우선 일부만 레이블이 지정되어 있는 그래프와 피처를 준비합니다. 그리고 다음의 단계를 거쳐서 알고리즘을 수행합니다.
우선 베이스 예측자(Base predictor)를 학습합니다. 레이블된 노드는 학습/검증 데이터로 사용됩니다. 베이스 예측자는 단순한 모델을 사용합니다. 선형 모델이나 피처에 대한 MLP나 GNN을 사용합니다.
그리고 베이스 예측자를 통해 모든 노드에 대해 소프트 레이블(soft label)을 예측합니다. 이런 소프트 레이블은 생각보다 꽤 정확하게 나옵니다.
Intuition of Correct & Smooth
이제 마지막으로 그래프 구조를 사용하여 예측값을 후처리해서 모든 노드의 최종 예측값을 얻습니다. 이 후처리는 Correct step과 Smooth step으로 나뉩니다. 우선 소프트 레이블의 오류가 어느 정도 편향되어 있을 것이기 때문에 그 오류 편향을 수집하는 것이 최우선 목표입니다. 이게 correct step이 됩니다. 그리고 소프트 레이블은 그래프 전체에 대해서 스무스한 예측값을 생성하지 못했을 것이기 때문에 그 값을 스무딩해야 합니다. 이 과정이 smooth step입니다.
Correct Step
Correct step의 핵심 아이디어는 베이스 예측의 오류가 그래프 엣지에 따라서 양의 상관관계가 있을 것으로 예상하는 것입니다. 다시 말해서 노드 $u$에서 오류가 발생하면 $u$의 이웃 노드에서 유사한 오류가 발생할 가능성이 높아지는거죠. 그래서 우린 그래프에 이러한 불확실성을 분산시켜야 합니다.
우선 노드의 학습 에러를 계산합니다. 여기서 학습 에러는 이미 존재하는 레이블에 대해서만 소프트 레이블을 빼준 값입니다. 레이블되어 있지 않은 노드는 모두 0으로 처리합니다.
이제 이 학습 오류 $E^{(0)}$을 엣지에 걸쳐서 확산시킵니다. $A$를 인접 행렬이라고 할 때 $\tilde{A}$를 확산 행렬이라고 정의합니다.
\[\tilde{A} \equiv D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\]여기서 $D$는 각 노드의 degree matrix가 됩니다. 이 확산 행렬을 사용해 다음과 같이 학습 오류를 업데이트 합니다.
\[E^{(t+1)} \leftarrow (1 - \alpha) \cdot E^{(t)} + \alpha \cdot \tilde{A}E^{(t)}\]확산 행렬의 모든 eigenvalue $\lambda$는 $[-1, 1]$에 있습니다.
\[\begin{aligned}\tilde{A}D^{1/2}1 &= D^{-1/2} A D^{-1/2} D^{1/2} 1 \\ &= D^{-1/2} A 1 \\ &= D^{-1/2} D1, \quad \text{ $A1 = D1$, since they both leads to node degree vector} \\ &= 1 D^{1/2} 1 \end{aligned}\]따라서 $\tilde{A}^K$ 에도 이 성질이 적용됩니다. $\tilde{A}^K$의 eigenvalue 역시 $[-1, 1]$에 속하고, 가장 큰 eigenvalue는 항상 1입니다.
만약 $i$와 $j$가 연결되어 있다면 $\tilde{A}_{ij} = \frac{1}{\sqrt{d_i}\sqrt{d_j}}$ 가 됩니다. 그래서 만약 $i$와 $j$가 서로만 연결되어 있는 경우에는 $\tilde{A}_{ij}$ 값이 커지지만, $i$와 $j$가 다른 수많은 노드와 연결되어 있는 경우에는 $\tilde{A}_{ij}$ 값이 작아집니다.
이렇게 오류를 확산시키고 나면 위 그림과 같은 결과를 얻을 수 있습니다. 마지막으로 확산된 학습 에러를 예측한 소프트 레이블에 더하면 됩니다. 결과는 다음과 같습니다.
Smooth Step
이제 소프트 레이블을 엣지를 거쳐 스무딩을 진행합니다. 여기서 이웃 노드들은 같은 레이블을 공유한다는 가정을 기저에 두고 있습니다. 이때 학습되는 노드는 소프트 레이블 대신 실제 레이블(하드 레이블)을 사용합니다.
Correct step과 비슷하게 Smooth step도 그래프 구조를 통해 확산 레이블인 $Z^{(0)}$을 확산시킵니다. 수식으론 다음과 같이 나타낼 수 있습니다.
\[Z^{(t+1)} \leftarrow (1 - \alpha) \cdot Z^{(t)} + \alpha \tilde{A} Z^{(t)}.\]이렇게 몇 번의 스무딩을 거치면 다음과 같은 결과를 얻을 수 있습니다. 이때 결과는 확률값이 아니기 때문에 레이블에 대해 나온 값을 모두 더했을 때 1이 아닐 수 있습니다.
Result of smooth step
Correct & Smooth는 베이스 모델로부터 엄청난 성능 향상을 줍니다. Correct & Smooth는 Smooth step만 수행했을 때보다도 훨씬 좋은 성능을 내구요.
Masked Label Prediction
지금까지의 방법과 다르게 노드 레이블 정보를 명시적으로 포함하는 방식도 있습니다. BERT처럼 마스킹(masking)을 사용하는 방법인데요. Masked label prediction이라고 불리는 이 방법은 레이블을 추가적인 피처로 활용합니다. 기존 노드 피처 매트릭스 $X$와 노드 레이블 매트릭스 $Y$를 붙여서 사용하죠.
부분적으로 존재하는 레이블 $\hat{Y}$를 사용해서 지정되지 않은 레이블을 예측하는 것은 같은데요. 학습할 때는 $\hat{Y}$의 일부를 임의로 마스킹하여 $\tilde{Y}$로 변환하고, $[X, \tilde{Y}]$를 사용하여 마스킹된 노드 레이블을 예측합니다. 그리고 추론 시에는 모든 $\hat{Y}$를 사용하여 미지정된 레이블을 예측합니다. 일종의 링크 예측과 유사한데 준지도학습 태스크 형태인거죠.