F²LP-AP: 적응형 커널을 활용한 빠르고 유연한 레이블 전파 기법

그래프 머신러닝(Graph Machine Learning)의 핵심 과제 중 하나인 준지도 노드 분류(Semi-supervised node classification)는 그래프 구조를 활용하여 레이블이 부족한 데이터에서도 노드를 분류하는 중요한 작업입니다. 하지만 현재 최첨단 그래프 신경망(GNNs)들은 높은 계산 오버헤드와 강한 동종성(homophily) 가정을 필요로 한다는 근본적인 한계에 직면해 있습니다.

전통적인 GNN 아키텍처는 반복적인 훈련과 다층 메시지 전달(multi-layer message passing) 과정을 거치기 때문에 계산 비용이 매우 높습니다. 반면, 레이블 전파(Label Propagation)와 같은 기존의 학습 없는(training-free) 방법들은 그래프가 가진 이질적 구조(heterophilous graph structure)에 적응하는 유연성이 부족하다는 단점이 있었습니다.

본 논문에서 제안하는 **F²LP-AP (Fast and Flexible Label Propagation with Adaptive Propagation Kernel)**는 이러한 문제점들을 해결하기 위해 설계된, 계산 효율적인 학습 없는 프레임워크입니다. F²LP-AP의 핵심은 그래프의 국소적(local) 토폴로지 변화에 적응할 수 있다는 점에 있습니다.

주요 작동 원리:

1. 강건한 클래스 프로토타입 구축: F²LP-AP는 기하 평균점(geometric median)을 활용하여 각 클래스의 견고한 대표값, 즉 클래스 프로토타입을 구축합니다. 이는 노드 분류의 기준점을 명확히 합니다.
2. 적응형 전파 매개변수 조정: 가장 중요한 특징은 로컬 클러스터링 계수(Local Clustering Coefficient, LCC)를 기반으로 레이블 전파 매개변수를 동적으로 조절한다는 것입니다. 이 적응 메커니즘 덕분에 F²LP-AP는 단순히 유사한 노드가 모여있는 동종성 그래프뿐만 아니라, 구조적 관계가 복잡하고 다양한 특성을 가진 이질적(heterophilous) 그래프에서도 높은 성능을 유지할 수 있습니다.

성과:
다양한 벤치마크 데이터셋에 걸친 광범위한 실험 결과는 F²LP-AP가 학습된 GNN들과 비교하여 경쟁적이거나 그 이상의 정확도를 달성함을 보여줍니다. 동시에, 계산 효율성 측면에서는 기존의 베이스라인들을 크게 능가하는 성능을 입증했습니다. 이는 고성능과 높은 실용성을 모두 갖춘 혁신적인 접근 방식임을 의미합니다.