비동질 그래프에서도 잘 작동하는 비지도 노드 표현학습, FUEL
1. 들어가며
그래프에서 노드 임베딩(node embedding)은 말 그대로 각 노드를 벡터로 표현한 것이다. 이렇게 얻은 임베딩은 이후 노드 분류(node classification), 노드 군집화(clustering), 링크 예측 등 다양한 downstream task의 입력으로 사용된다. 특히 최근에는 라벨이 충분하지 않은 현실적인 상황을 고려해, 비지도(unsupervised) 노드 표현학습이 꾸준히 중요해지고 있다. 라벨 없이도 좋은 임베딩을 만들 수 있다면, 비용도 줄고 라벨 희소 상황에서도 더 강하게 작동할 수 있기 때문이다.
그런데 그래프 representation learning에서 거의 습관처럼 등장하는 것이 있다. 바로 graph convolution이다. GCN류 방법들은 이웃 노드의 정보를 aggregate해서 현재 노드 표현을 업데이트한다. 직관적으로도 꽤 자연스럽다. 연결된 노드끼리는 어느 정도 비슷할 것이라는 가정, 즉 homophily가 성립한다면 이웃 정보를 섞는 것이 도움이 된다. 예를 들어 같은 관심사를 가진 사람끼리 연결된 소셜 네트워크라면, 친구들의 정보를 반영하는 것이 내 표현을 더 잘 만드는 데 도움이 될 수 있다.
하지만 문제는 모든 그래프가 그렇게 생기지 않았다는 점이다. 실제 그래프에는 non-homophilic graph, 즉 서로 다른 속성을 가진 노드끼리도 자주 연결되는 그래프가 많다. 이 경우 graph convolution을 과하게 쓰면, 원래 달라야 할 노드들의 표현까지 서로 비슷해지는 문제가 생긴다. 이 논문은 바로 그 지점을 파고든다.
핵심 문제의식은 간단하다.
비지도 노드 표현학습에서, graph convolution을 얼마나 써야 하는가?
supervised setting에서는 downstream label supervision이 있으니, 모델이 알아서 “어느 정도 섞는 게 좋은지”를 배울 수 있다. 하지만 unsupervised setting에서는 그런 기준이 없다. 그래서 이 논문은 homophily를 당연한 전제로 두지 않고, 비지도 환경에서 graph convolution의 사용 정도를 적절히 조절하는 방법을 제안한다. 그 방법이 바로 FUEL (Feature-centric Unsupervised node rEpresentation Learning) 이다.
2. 왜 기존 비지도 GNN 방식이 비동질 그래프에서 약해지는가
논문을 이해하려면 먼저 graph convolution의 성격을 짚고 가야 한다.
graph convolution은 대체로 이런 식으로 작동한다.
- 내 feature만 쓰지 않고,
- 1-hop 이웃의 feature를 섞고,
- 필요하면 2-hop, 3-hop 이웃의 feature까지 더 섞는다.
이 과정은 본질적으로 연결된 노드들의 표현을 서로 닮게 만든다. 그래서 homophilic graph에서는 잘 맞는다. 비슷한 노드가 연결되어 있으니, 이웃을 섞을수록 같은 클래스 노드끼리 더 뭉치게 된다.
그런데 non-homophilic graph에서는 상황이 달라진다. 서로 feature도 다르고 class도 다른 노드가 자주 연결되어 있다면, graph convolution은 오히려 서로 다른 클래스 노드들을 섞어버린다. 그러면 embedding space에서 intra-class similarity는 떨어지고, inter-class separability도 무너질 수 있다. 논문 초반에서 말하는 “graph convolution을 과하게 쓰면 unduly similar embeddings가 생긴다”는 표현이 바로 이 뜻이다.
이 문제는 supervised learning에서는 어느 정도 연구되어 왔다. 예를 들어 특정 계수 αk를 학습해서 A, A^2 같은 여러 수준의 graph convolution을 얼마나 섞을지 조절하는 방법들이 있다. 하지만 unsupervised에서는 어떤 기준으로 그 계수를 학습할지가 애매하다. label이 없으니 “지금 잘 섞고 있는지”를 직접 평가하기 어렵기 때문이다. 이 논문은 바로 이 공백을 메운다.
3. 이 논문의 핵심 아이디어: “class separability”를 직접 못 보면, feature 기반 cluster separability를 보자
FUEL의 핵심은 surprisingly simple하다.
라벨이 없어서 class separability를 직접 볼 수 없다면, node feature가 암시하는 잠재적 군집(latent class) 을 대신 보자는 것이다.
논문은 다음과 같은 직관에 기반한다.
- 같은 class의 노드들은 보통 비슷한 feature를 가진다.
- 다른 class의 노드들은 feature도 대체로 다르다.
- 따라서 node feature 공간에는 자연스럽게 어느 정도 cluster 구조가 존재한다.
- 그러면 이 cluster를 “가짜 class(proxy class)”처럼 활용할 수 있다.
즉, 진짜 라벨은 모르지만 feature 기반으로 얻은 군집이 어느 정도 class를 반영한다고 보고,
“같은 군집은 더 조밀하게, 다른 군집은 더 멀게” 만드는 방향으로 graph convolution의 정도를 조절하자는 것이다.
이 논문은 이 proxy 개념을 latent-class separability라고 부른다. 그리고 이것이 실제 class separability의 좋은 proxy라는 점을 empirical, theoretical 양쪽에서 보여준다.
4. 제안 proxy: latent-class separability란 무엇인가
논문 3장은 FUEL 전체보다도 오히려 더 중요한 역할을 한다. 왜냐하면 이 논문의 모든 설계가 “latent-class separability가 class separability의 proxy가 된다”는 주장 위에 서 있기 때문이다.
4.1 직관
진짜 class label은 없지만, feature가 비슷한 노드끼리 같은 latent class를 형성한다고 보자.
그렇다면 좋은 embedding은
- 같은 latent class 안에서는 응집(cohesive)되어 있고
- 다른 latent class와는 잘 분리(separable)되어 있어야 한다.
이게 바로 latent-class separability의 뜻이다.
4.2 empirical evidence
논문은 여러 graph convolution coefficient를 랜덤하게 바꿔가며 서로 다른 embedding을 만든 뒤,
각 embedding에 대해
- 실제 label을 이용한 class separability
- feature-based cluster를 이용한 latent-class separability
를 동시에 측정한다.
그 결과 Figure 1에서 보이듯, Cora, Citeseer 같은 homophilic graph뿐 아니라 Actor, Cornell 같은 non-homophilic graph에서도 둘 사이의 Spearman correlation이 0.82 이상으로 매우 높게 나온다. 즉, latent-class separability가 높을수록 실제 class separability도 높다는 것이다.
이 실험은 이 논문의 출발점을 꽤 설득력 있게 뒷받침한다.
5. 이론적 분석: latent-class separability가 왜 proxy가 되는가
논문은 empirical correlation만 보여주고 끝나지 않는다. 간단한 이론 세팅 아래에서 latent-class separability와 class separability의 ordering이 같아진다는 정리를 제시한다.
핵심 세팅은 다음과 같다.
- 두 클래스 C0,C1가 있고
- 각 클래스의 node feature는 서로 다른 Gaussian 분포에서 나온다.
- 각 노드는 같은 클래스 이웃 n0, 다른 클래스 이웃 n1 를 가진다.
- graph convolution 사용 정도를 w∈[0,1]로 표현한다.
이때 graph convolution 후 embedding을
처럼 둔다. 즉,
- w=0 이면 자기 feature만 쓰고
- w 가 커질수록 이웃 정보를 더 많이 섞는다.
그리고 class separability는 베이즈 분류기의 error를 바탕으로 정의하고, latent-class separability는 일종의 클래스 간 평균 거리 대비 클래스 내 분산 비율로 정의한다. 논문에 적힌 형태는 다음과 비슷하다.
즉,
분자 = 클래스 평균 간 거리,
분모 = 클래스 내부 분산이다.
논문 Theorem 1은 특정 조건 하에서
가 성립한다고 보인다. 즉, 두 graph convolution 정도 w,w′ 중 어느 쪽이 더 class separability가 좋은지의 순서는 latent-class separability로도 정확히 판단할 수 있다는 것이다.
이 정리는 이 논문의 가장 중요한 이론적 뒷받침이다.
정확한 절댓값을 맞춘다기보다, “어느 정도의 convolution이 더 좋은가”를 고르는 ranking signal로 latent-class separability가 충분하다는 뜻이다.
6. FUEL 전체 구조 개요
Figure 2를 보면 FUEL의 전체 구조가 나온다. FUEL은 두 단계로 이루어진다.
- Step 1: Specialized clustering scheme
- Step 2: Embedding refinement
즉,
- 먼저 graph convolution의 적절한 정도를 학습하고,
- 그 결과 얻은 intermediate embedding을 다시 refinement해서 latent-class separability를 더 끌어올린다.
여기서 중요한 점은, FUEL이 처음부터 복잡한 end-to-end GNN을 학습하는 것이 아니라는 것이다.
오히려 간단한 adaptive graph convolution으로 적절한 mixing 정도를 먼저 찾고,
그다음 별도의 refinement network로 embedding 품질을 다듬는 구조다.
7. Step 1: graph convolution 사용 정도를 배우는 specialized clustering scheme
7.1 adaptive graph convolution model
FUEL은 먼저 다음과 같은 형태의 intermediate embedding을 만든다.
여기서
- X: 원래 node feature
- A(tilda)X: 1-hop 이웃 정보를 한 번 섞은 feature
- A(2tilda): 2-hop 이웃 정보까지 반영한 feature
- α0,α1,α2∈[0,1] ,
이다.
이 식의 의미는 매우 직관적이다.
- α0가 크면 자기 feature를 많이 믿는 것
- α1,α2가 크면 이웃 정보를 많이 섞는 것
즉, FUEL은 결국 원본 feature vs 1-hop smoothing vs 2-hop smoothing를 얼마나 섞을지를 자동으로 정하는 모델이다.
이 계수는 직접 학습하지 않고,
c0,c1,c2∈Rc_0,c_1,c_2 \in \mathbb{R} 를 학습한 뒤 softmax로 바꿔서 얻는다.
이렇게 하면 계수들이 자연스럽게 0과 1 사이에 있고 합이 1이 된다.
8. Step 1의 학습 목표: clustering loss
문제는 이 α 들을 무슨 기준으로 학습하느냐이다. FUEL은 clustering 기반 손실을 만든다.
8.1 cluster assignment
각 cluster c 에 learnable centroid tc 를 두고, node vi 가 cluster c 에 속할 score를
처럼 정의한다. 즉, xi∗ 와 centroid tc의 유사도가 클수록 그 cluster에 속할 확률이 커진다.
8.2 세 가지 loss
FUEL의 clustering loss는 세 부분으로 구성된다.
(1) L1L_1: 각 노드가 한 cluster에 뚜렷이 속하게 만들기
이건 node별 assignment entropy를 줄이는 항이다.
즉, 한 노드가 여러 cluster에 애매하게 걸치지 말고, 하나의 cluster에 뚜렷하게 속하게 만든다.
(2) L2L_2: 모든 노드가 한 cluster로 몰리는 collapse 방지
이 항은 전체 cluster 사용량이 균등하도록 유도한다.
즉, 모든 노드가 한 cluster로 몰리는 trivial solution을 막는다.
(3) L3L_3: cluster 간 거리는 멀고, cluster 내 거리는 가깝게
여기서 V+ 는 같은 cluster에 할당된 node pair, V− 는 다른 cluster pair다.
즉, intra-cluster distance는 줄이고, inter-cluster distance는 늘리도록 유도한다.
8.3 최종 clustering loss
최종적으로는
를 최소화한다.
이렇게 해서 α0,α1,α2 와 cluster centroid를 함께 학습한다.
이 과정을 마치면 최종 intermediate embedding은
가 된다. 여기서 α∗ 는 학습된 최적 계수들이다.
9. Step 2: refinement로 latent-class separability 더 끌어올리기
논문은 Step 1의 adaptive graph convolution만으로는 표현력이 제한될 수 있다고 본다.
그래서 intermediate embedding H 를 고정한 뒤, 추가 refinement를 수행한다.
최종 embedding은
로 정의된다. 여기서 fθ는 feed-forward neural network이고, +H는 skip connection이다.
skip connection을 넣은 이유는 직관적이다.
Step 1에서 이미 얻은 유용한 구조를 보존하면서, refinement는 필요한 부분만 조정하게 하기 위해서다.
refinement loss
refinement에서는 HH 공간에서 각 node의 nearest neighbors를 찾는다.
같은 latent class일 가능성이 높은 이웃 pair는 가깝게, 나머지는 멀게 만든다.
손실은
이다. 여기서
- V+: H 공간에서의 nearest-neighbor pair
- V'−: 그 외 negative pair
- d(x,y)=∥x−y∥의 l2 norm
- τ: temperature
이다.
이 loss는 positive pair 거리는 줄이고, negative pair 거리는 늘리게 만든다.
즉, Step 1에서 얻은 latent class 구조를 더 또렷하게 sharpen하는 역할이다.
10. 실험 설정 한눈에 보기
논문은 꽤 넓은 범위의 실험을 수행한다.
- 14개 real-world benchmark graph
- 15개 baseline
- 7개 도메인
- homophily 0.11 수준의 매우 비동질 그래프부터 0.85 수준의 매우 동질 그래프까지 포함
baseline도 다양하다.
- Contrastive: DGI, GraphCL, MVGRL, BGRL
- Generative: GAE, GraphMAE, MaskGAE
- Non-homophilic-oriented SSL: HGRL, DSSL, GREET, NeCo, PolyGCL, HeterGCL, HLCL
즉, 단순히 몇 개 baseline만 이긴 것이 아니라, 기존 비지도 graph SSL 계열 전반과 비교한 셈이다.
11. RQ1: node classification에서 정말 잘 되는가?
Table 1을 보면 FUEL은 16개 방법 중 가장 좋은 average rank 2.4를 기록한다. 특히 중요한 점은,
가장 비동질적인 그래프(Texas) 에서도,
가장 동질적인 그래프(Photo) 에서도
최고 성능을 낸다는 점이다.
예를 들면:
- Texas (homophily 0.057): FUEL 84.6
- Photo (homophily 0.849): FUEL 94.2
즉, FUEL은 “비동질 그래프 특화”라고만 보기 어렵고, homophily 수준이 달라져도 적응적으로 잘 작동하는 general method에 가깝다.
이게 중요한 이유는, 어떤 방법은 homophilic graph에서는 잘 되지만 heterophilic graph에서 무너지고, 반대로 어떤 방법은 heterophilic graph만 겨냥해 homophilic graph에서 손해를 보기도 하기 때문이다. 그런데 FUEL은 둘 다 잡는다.
12. RQ2: clustering에서도 잘 되는가?
node classification뿐 아니라 clustering 결과도 강하다.
Table 2에서 FUEL은 clustering에서도 가장 좋은 average rank 2.4를 기록한다. 마찬가지로 least homophilic graph와 most homophilic graph 모두에서 좋은 성능을 낸다.
이 결과는 꽤 의미 있다.
왜냐하면 classification은 downstream classifier가 어느 정도 보정할 수 있지만, clustering은 embedding quality 자체가 더 직접적으로 드러나는 task이기 때문이다. clustering에서도 잘 된다는 것은 FUEL이 embedding space 자체를 잘 조직화한다는 뜻이다.
13. RQ3: FUEL은 정말 설계 의도대로 동작하는가?
논문은 단순 성능표만 보여주지 않고, 방법이 실제로 의도대로 작동했는지도 분석한다.
13.1 homophily에 따라 learned convolution degree가 달라지는가?
Figure 3(a)를 보면,
- Cora, Citeseer 같은 homophilic graph에서는
A~X,A~2X의 weight가 크다. - Actor, Cornell 같은 non-homophilic graph에서는
거의 대부분 weight가 X 에 몰리고, graph-convolution 항의 비중은 거의 0에 가깝다.
즉, FUEL은 정말로 graph 특성에 따라 “얼마나 이웃을 섞을지”를 적응적으로 정한다.
13.2 refinement가 separability를 높이는가?
Figure 3(b)는 Step 1 직후 intermediate embedding과 Step 2 후 final embedding의 latent-class separability를 비교한다. 모든 그래프에서 refinement 후 separability가 커진다.
즉, Step 2는 단순 덧붙이기가 아니라 실제로 embedding quality를 개선한다.
14. RQ4: 각 구성요소가 정말 필요한가?
ablation도 꽤 깔끔하다. 논문은 다음 변형들을 비교한다.
- w/o Step 1
- w/o Step 2
- w/o SK (skip connection 제거)
- w/o Exp (loss의 exponential 제거)
결과적으로 node classification과 clustering에서 FUEL이 이 변형들보다 10/14 데이터셋에서 더 좋다고 보고한다.
즉,
- Step 1의 adaptive convolution selection
- Step 2의 refinement
- skip connection
- exponential-form loss
가 모두 성능에 기여한다는 뜻이다.
15. 이 논문의 장점
개인적으로 이 논문의 장점은 다음 네 가지로 보인다.
15.1 문제 정의가 정확하다
비지도 setting에서 homophily assumption이 항상 맞지 않는데, 기존 연구는 이걸 충분히 다루지 못했다. 이 논문은 바로 그 공백을 정확히 찌른다.
15.2 proxy 설계가 설득력 있다
“라벨이 없으면 feature-based cluster separability를 보자”는 아이디어가 직관적이고, empirical + theoretical evidence까지 갖췄다.
15.3 모델이 의외로 단순하다
adaptive combination of X,A~X,A~2XX, \tilde{A}X, \tilde{A}^2X + feed-forward refinement라는 구조는 복잡한 거대 GNN보다 훨씬 해석 가능하다.
15.4 동질/비동질 둘 다 잘 잡는다
많은 heterophily methods는 homophilic graph에서 손해를 보는데, FUEL은 그렇지 않다. 이건 실용적으로 꽤 큰 장점이다.
16. 생각해볼 한계
물론 한계도 있다.
16.1 feature 정보가 약하면 proxy도 약해질 수 있다
이 방법은 기본적으로 “feature가 class 정보를 어느 정도 담고 있다”는 가정에 기대고 있다. 만약 feature가 매우 noisy하거나 class와 거의 무관하다면 latent-class separability 자체가 불안정할 수 있다.
16.2 cluster 수를 class 수와 맞췄다
실험에서는 cluster 개수를 실제 class 개수와 동일하게 뒀다. 논문은 이에 민감하지 않다고 추가 실험을 언급하지만, 현실에서는 class 수를 모르는 경우가 많기 때문에 완전한 free lunch는 아니다.
16.3 현재는 비교적 단순한 graph convolution family
A~,A~2\tilde{A}, \tilde{A}^2 수준의 mixing을 사용한다. 물론 이것만으로도 충분히 강했지만, 더 복잡한 spectral filter나 heterophily-aware operator와 결합하면 추가 확장 가능성이 있어 보인다.
17. 개인적인 해석
이 논문을 읽고 든 가장 큰 생각은,
결국 비지도 graph learning에서도 중요한 것은 무작정 이웃을 섞는 것이 아니라 얼마나 섞어야 하는지 판단하는 것이라는 점이다.
예전에는 GNN이든 graph SSL이든, 그래프가 주어지면 일단 이웃 정보를 aggregate하는 것이 거의 기본 전제처럼 느껴졌다. 그런데 이 논문은 그 전제를 한 발 물러서서 다시 묻는다.
- 이 그래프는 정말 이웃을 믿어도 되는가?
- 믿더라도 1-hop까지만 볼까, 2-hop도 볼까?
- 아니면 feature 자체를 더 믿는 편이 나을까?
그리고 그 답을 label supervision 없이도 feature-based clustering으로 찾아보겠다는 발상이 꽤 인상적이었다.
특히 Figure 3(a)에서 homophilic graph에서는 convolution weight가 커지고, non-homophilic graph에서는 거의 0으로 줄어드는 결과는, FUEL이 단순히 성능만 좋은 것이 아니라 진짜로 그래프 특성에 반응하고 있다는 점을 보여준다.
18. 마무리
정리하면, 이 논문은 비지도 노드 표현학습에서 homophily assumption을 당연하게 두지 말자는 메시지를 담고 있다.
핵심을 다시 정리하면 다음과 같다.
- graph convolution은 유용하지만, 비동질 그래프에서는 과하면 오히려 해가 될 수 있다.
- supervised setting에서는 label로 그 정도를 조절할 수 있지만, unsupervised setting에서는 그게 어렵다.
- FUEL은 feature 기반 clustering을 통해 latent-class separability를 proxy로 삼고,
- 이를 최대화하는 방향으로 graph convolution 사용 정도를 적응적으로 학습한다.
- 이후 refinement step으로 latent-class separability를 더 높인다.
- 그 결과 node classification과 clustering 모두에서, homophily 수준이 매우 다양한 그래프 전반에 걸쳐 strong performance를 달성한다.
개인적으로는 이 논문이 비지도 graph representation learning에서
“graph를 얼마나 쓸 것인가”
라는 질문을 훨씬 정교하게 만든 논문이라고 느꼈다.
앞으로는 단순히 새로운 contrastive objective나 generative objective를 제안하는 것뿐 아니라, 그래프 topology 자체를 어느 정도 신뢰할지부터 adaptively 결정하는 방향이 더 중요해질 수도 있겠다는 생각이 들었다.