Community 구조를 활용한 Disassortative 및 Heterophilic 그래프 핸들링에 대한 고민들
이 글에서는 우리 연구실(Network Science Lab @ CUK)의 Van Thuy Hoang 박사과정과 함께 진행하여 IEEE TSNE에 게재한 Community-aware Graph Transformer(CGT) 연구
Unified Graph Transformer 연구를 통해 우리는 원본 그래프의 구조적 특징을 보존하면서도 인접하지 않으나 높은 Structural Similarity를 갖는 노드들 사이에 Message를 전파할 방법을 제시했다. 이 방법은 다양한 Downstream Task에서 SOTA 성능을 보였을 뿐만 아니라, Node Clustering과 Graph Classification에 대한 SOTA 성능 및 3d-WL에 준하는 Isomorphism Testing 성능을 통해 구조적 특징 보존 능력을 입증했다. 하지만, k-step Transition Probability와 k-hop Proximity를 바탕으로 구조적 유사도가 높은 노드 사이에 Message 전파를 강화하는 이 방식은 Dissortative하고 Heterophilic한 실세계 그래프들에서 흔하게 발생하는 고질적인 문제인 Degree Bias 문제를 해결하는 것에는 그리 효과가 없었다.
Degree Bias의 주된 발생 원인은 Degree에 따라 노드가 수신하는 Message의 양적 그리고 질적 격차가 발생하는 것인데, 이에 따라 Degree가 낮은 노드와 높은 노드 모두에서 노드 Representation의 품질 저하와 Task 성능 저하 문제가 발생하는 것을 확인할 수 있었다. 실세계 그래프 데이터의 상당 부분을 차지하는 Scale-free 그래프들의 노드 Degree 분포가 멱함수 분포를 따른다는 점은 Downstream Task에서의 평균적인 성능 저하를 더욱 심화시켰다. 이와 같은 문제의 근본적인 원인은 Node Homophily에 대한 가정을 바탕으로 인접 노드로부터 전달되는 Message를 취합하여 목표 노드의 Representation을 업데이트하는 Message Passing Mechanism의 특성에 있다. 인접한 노드는 비슷한 특징을 가질 것이라는 이 가정은 Degree가 높은 노드는 지나치게 많은 Message로 인해 Over-Representation되도록 하며 Degree가 낮은 노드는 지나치게 적은 Message로 인해 Under-Representation되게 만든다. 이 문제는 Scale-free 그래프의 구조적 특징으로 인해 실세계 그래프들에서 더욱 심각해지는데, 소수의 Degree가 높은 노드(허브)를 중심으로 대다수의 Degree가 낮은 노드(단말)들이 Community를 이루며 모여 있고 Community 사이의 연결은 Degree가 높은 노드들이 직접 연결되거나 소수의 매개자 역할을 하는 노드를 통하기 때문이다. 이러한 구조로 인해, Degree가 높은 노드들, 즉 Community의 허브 노드들은 많은 양의 Message들을 받더라도 대부분의 Message가 구조적으로 이질적인 동일 Community의 말단 노드로부터 오거나 구조적으로는 동질적이더라도 Proximity가 낮은 다른 Community의 허브 노드로부터 오기 때문에 수신되는 Message들의 막대한 양에 비하여 대부분의 Message가 Noisy할 수밖에 없다. 마찬가지로 Degree가 낮은 노드 중 대다수를 차지하는 Community의 단말 노드들도 소수의 Message가 거의 모두 구조적으로 이질적인 동일 Community의 허브 노드로부터 온다는 문제가 있다.
여기서 우리의 가장 큰 아이디어는 Community 구조로부터 오는 문제를 Community 구조를 활용해서 해결하는 것이었다. 커뮤니티는 소속된 노드 간에는 높은 Proximity를 외부 노드에 대해서는 낮은 Proximity를 갖는, 즉 Node Homophily에 대한 가정을 따르면 내부적으로는 동질적인 특성을 외부에 대해서는 배타적인 특성을 갖는 노드들의 집단이다. 이에 따라, 동일 커뮤니티에 속한 노드들은 일정 수준 이상의 High-order Proximity를 가지고 있으며 Informative Message의 Source로 고려할 첫 번째 대상이라고 볼 수 있다. 하지만, 앞서 논의한 바와 같이 하나의 Community에도 허브 노드와 단말 노드가 존재하며, 구조적으로 이질적인 이들이 비슷한 특징을 가질 것으로 기대하기는 어렵다. 이에 따라, High-order Proximity와 Structural Similarity를 함께 갖춘 노드라야 서로의 Representation을 업데이트하는데 유의미한 정보를 전달할 수 있을 것으로 보고, 우리는 동일한 Community에 속하면서도 구조적으로 동질적인 노드 사이에 Message가 전파되도록 하면 노드 Representation의 질을 개선하고 Degree Bias 문제를 해결하면서도 Message 전파의 경로를 수정함으로써 발생하는 구조적 특징 정보 손실을 최소화할 수 있을 것이라 보았다.
위의 원칙을 바탕으로 한 그래프 구조의 Augmentation을 위하여 우리는 Edge Perturbation 기반의 Structure Learning을 채용했다. 일반적으로 노드 특징의 연관성을 바탕으로 하는 Edge Perturbation에 Community에 대한 Membership과 High-order Proximity, Role-based Similarity를 추가로 고려할 수 있도록 하였으며, 이 특징들은 Transformer Layer의 Attention Score에서도 같은 방식으로 고려되었다. 추가로, 제안하는 방법이 노드의 고차 인접성과 구조적 동질성을 모두 고려한다고 하더라도, Structure Learning을 통한 그래프 구조의 변화는 그래프 구조적 특징 정보의 소실을 동반할 수밖에 없다. 이를 보완하기 위해, 우리는 Structure Learning에 대한 Regularization으로 UGT 모델에서도 활용했던 Transition Probability의 보존 임무를 함께 채용했다. 이를 통해, 모델은 Task 수행에 최적화된 방향으로 커뮤니티 구조 및 각 노드가 커뮤니티 내에서 갖는 역할을 고려하여 간선을 추가하거나 삭제하면서 Informative Message를 최대화하고 Noisy Message를 최소화하지만, 이러한 구조의 변경을 고차 인접성 정보인 Transition Probability를 재건할 수 있는 선에서 수행하도록 학습된다.
이 모델의 평가를 위해, 우리는 노드 Degree에 따른 모델의 성능 변화를 확인하였고, 제안하는 모델이 기존 방법들 대비 Degree 편향을 가장 유의미하게 완화할 수 있는 방법 중 하나라는 것을 확인하였다. 이와 동시에 제안한 모델인 CGT는 전체적인 노드 분류 성능과 군집화 성능에서도 최고 수준을 보였으며, 특히 군집화 성능은 제안한 모델이 구조 정보의 소실을 최소화했음을 방증하기도 한다. 추가로, 우리는 실험 결과를 분석하면서 모델의 전반적인 성능과 Degree 편향 완화 사이에 Trade-off 관계가 있음을 발견하였는데, 이러한 면에서도 제안한 모델은 가장 약한 수준의 Trade-off를 보였다. 결론적으로, 우리는 실세계 그래프 데이터들의 대다수를 차지하는 Scale-free 그래프에서 Message Passing을 적용할 경우 Degree 편향이 발생하는 주된 이유가 Community 구조에서 온다고 봤고, 이에 따라 Community Membership과 노드들의 Community 내 역할을 고려할 수 있는 Learnable Structure Augmentation 방법과 Graph Transformer 구조를 제시하여 해당 문제를 유의미하게 개선할 수 있었다.
앞선 Unified Graph Transformer(UGT)에 대한 연구가 예상 밖의 뛰어난 성과를 거두고 나서, 우리는 우리의 연구를 좀 더 꼼꼼하게 그리고 단단하게 다지는 과정에 충분한 노력을 기울이지 않았던 것 같다. Community-aware Graph Transformer(CGT)에 대한 실험과 검증을 하던 시점에서 CGT는 우리의 앞선 모델인 UGT와 비교해서도 대부분의 Node-level 그리고 Graph-level Task들에서 우수한 SOTA 수준의 성능을 보였다. 하지만, 우리는 제안된 모델의 가장 주요한 설계 목표인 Degree Bias에 대한 뚜렷하고 객관적인 검증 및 평가 방법을 제시해야 했으나 그렇지 못했다. 2023년 겨울, 이 연구를 막 마무리한 시점에서 Degree 범위에 따른 모델 성능 편차를 확인하는 것은 우리가 채용할 수 있는 최선의 방법 중 하나라고 생각했으나 곧 다른 연구에서 DEO(Degree Equal Opportunity)와 DSP(Degree Statistical Parity) 등과 같은 좀 더 체계적인 평가 방법이 제시되었다. 이러한 검증과 평가 면에서의 엄밀함의 부족이 처음 투고했던 IJCAI 2024에서 좋은 결과를 얻지 못한 원인이었다고 생각된다. 그 후, 우리는 대부분의 실험을 다시 설계하고 실험의 폭 또한 대폭 확장하여 CIKM 2024에 투고하였으나, 처음 논문을 투고할 때는 꽤 신선한 접근이었던 Structure Learning을 바탕으로 한 그래프 증강은 이 시점에 와서는 참신성이 부족했고, 무엇보다 우리가 Data Mining 분야 컨퍼런스가 요구하는 Writing Style에 익숙하지 않았다. 이 시기마저 놓치고 나니 다른 컨퍼런스들에서는 2023년 겨울에 이미 arXiv와 Github에 공개된 우리 논문과 비슷한 접근과 방법을 채용한 논문들이 눈에 띄기 시작했고, AAAI 2025에서마저도 좋은 결과를 얻을 수 없었기는 마찬가지였다. 다행스럽게도 우리가 진행했던 폭넓은 실험에 대해서 Discussion의 폭과 깊이를 크게 보완한 끝에 유의미한 Insight들을 잘 정리하여 네트워크 과학 분야의 권위 있는 학술지 중 하나인 IEEE Transactions on Network Science and Engineering(TNSE)에 연구를 발표하게 되어 좋은 결과로 마무리할 수 있었다. 돌이켜 보면 이 일련의 과정은 PI로써 미숙한 부분이 많았던 나의 연구 기획 역량의 부족이었던 것으로 생각된다. Van Thuy Hoang 박사과정이 수행한 깊이 있는 연구가 곧바로 좋은 결과로 이어지지 못하고 여러 번 고배를 마시게 된 것에는 아직도 미안함이 크게 남는다. 부가적으로, 추후 여러 논문심사 과정을 거치며 현재 모델의 이름은 DegFairGT로 수정되었다.