기술 요약: 고차 클래스 레이블 연결성을 활용한 그래프 신경망(Graph Neural Network)

문제 정의

그래프 신경별 네트워크(GNN)에서의 노드 분류는 노드들이 유사한 클래스 레이블을 가질 때 서로 연결되는 동종성(homophily) 그래프에서는 높은 정확도를 달 정도로 성과를 거두었습니다. 그러나 노드들이 서로 다른 클래스 레이블을 가질 가능성이 높은 이종성(heterophily) 그래프에서는 성능이 크게 저하됩니다.

저자들은 현재의 GNN(GCN, GAT 및 H2GCN, LINKX와 같은 고급 이종성 모델 포함)이 가진 구체적인 한계를 지적합니다. 이러한 모델들은 노드 분류 문제를 임베딩 공간에서 클래스 레이블 공간으로의 단순한 매핑으로 변환합니다. 결과적으로, 이 모델들은 방향성 에지(directed edges)를 통해 여러 홉(multi-hop)에 걸쳐 나타나는 클래스 레이블 간의 구조적 관계, 즉 **고차 클래스 레이블 연결성(higher-order class label connectivity)**을 포착하지 못합니다. 일부 방법들은 1차 연결성을 포착하기 위해 클래스 호환성 행렬을 활용하지만, 실제 방향성 그래프(예: "Student" 노드가 "Department" 노드에 연결되고, "Department" 노드는 다시 "Staff" 노드에 연결되는 Texas 데이터셋)에서 빈번하게 관찰되는 복잡한 다중 홉 레이블 상호작용은 고려하지 못합니다.

방법론

제안된 접근 방식은 새로운 분류기인 **레이블 컨텍스트 분류기(Label Context Classifier, LCC)**를 도입하고, 이를 기존 GNN과 통합하는 프레임워크를 제시합니다.

1. 레이블 컨텍스트 분류기 (LCC)

LCC는 word2vec의 Skip-gram 모델에서 영감을 받아, 그래프 워크(graph walk)를 따라 발생하는 클래스 레이블의 시퀀스를 컨텍스트로 취급함으로써 고차 클래스 레이블 연결성을 포착하도록 설계되었습니다. 과정은 세 가지 주요 단계로 구성됩니다:

• 레이블 워크 추출(Label Walk Extraction): 타겟 노드로부터 네 가지 유형의 레이블 워크를 추출합니다. 레이블 워크는 노드가 레이블로 대체된 클래스 레이블의 시퀀스입니다. 만약 노드가 훈련 세트에 없다면, null 레이블을 사용합니다.
  • 순방향 워크(Forward Walk): 에지의 방향을 따라 깊이 우선 탐색을 수행합니다 (Target $\to$ Child $\to$ Grandchild).
  • 역방향 워크(Backward Walk): 에지의 역방향을 따라 깊이 우선 탐사를 수행합니다 (Target $\to$ Parent $\to$ Grandparent).
  • 형제 워크(Sibling Walk): 부모 노드로 역방향 이동한 후, 그 부모의 다른 자식 노드로 순방향 이동합니다 (Target $\to$ Parent $\to$ Sibling). 이는 공통 부모를 공유하는 노드 간의 연결성을 포착합니다.
  • 가디언 워크(Guardian Walk): 자식 노드로 순방향 이동한 후, 그 자식의 다른 부모 노드로 역방향 이동합니다 (Target $\to$ Child $\to$ Co-parent). 이는 공통 자식을 공유하는 노드 간의 연결성을 포착합니다.
• 레이블 컨텍스트 임베딩 생성(Label Context Embedding Generation): 추출된 워크를 사용하여 모델은 "레이블 컨텍스트"를 나타내는 임베딩을 학습합니다. 간단한 2층 다층 퍼셉트론(MLP)을 사용하여, 입력된 타겟 노드의 레이블로부터 컨텍스트 레이블(워크 내의 후속 레이블들)을 예측하도록 학습합니다. 은닉층은 **레이블 컨텍스트 임베딩($Z$)**을 생성합니다.
• 분류기 학습(Classifier Training): 최종 LCC 분류기는 원래의 노드 특징(features)과 네 가지 워크 유형에서 유도된 레이블 컨텍스트 임베딩을 결합(concatenation)하여 학습되는 MLP입니다.

2. GNN과의 통합

기존 GNN(특징 및 국소적 구조 정보를 포착)과 LCC(고차 레이블 연결성을 포착)의 강점을 모두 활용하기 위해, 저자들은 적응형 통합 기법을 제안합니다:

• 독립적 학습(Independent Training): GNN과 LCC는 각각 훈련 세트에서 독립적으로 학습됩니다.
• 적응형 가중치 부여(Adaptive Weighting): 각 모델의 중요도는 **검증 손실(validation loss)**을 사용하여 결정됩니다. 가중치($w_{LCC}$ 및 $w_{GNN}$)는 온도 파라미터($T$)에 의해 조정된 검증 손실의 역수로 계산됩니다.
• 앙상블 예측(Ensemble Prediction): 최종 예측은 GNN과 LCC 출력의 가중 평균입니다. 이 통합 과정에는 추가적인 모델 학습이 필요하지 않으며, 오직 검증 성능에 기반한 가중치 계산만을 요구합니다.

주요 기여

1. LCC 제안: 네 가지 방향 인식 레이블 워크(Forward, Backward, Sibling, Guardian)를 통해 고차 클래스 레이블 연결성을 추정하는 새로운 분류기를 제안했습니다.
2. 적응형 통합 프레임워크: 추가적인 학습 비용 없이 검증 손실을 기반으로 중요도 가중치를 적응적으로 학습하여, LCC를 기존의 모든 GNN과 통합할 수 있는 방법을 제공합니다.
3. 실증적 검증: 이종성 방향성 그래프에서 LCC를 GNN과 통합했을 때 SOTA(State-of-the-Art) 방법들보다 우수한 성능을 보임을 실험적 결과로 입증했습니다.

실험 결과

저자들은 Cornell, Texas, Wisconsin, Chameleon, Squirrel, Roman-Empire, Amazon-Ratings의 7개 이종성 방향성 그래프 데이터셋에 대해 실험을 수행했습니다.

• 성능 향상: 통합된 모델(예: H2GCN+LCC, LINKX+LCC, GloGNN+LCC)은 단독 GNN, MLP, 또는 LCC 단독 모델보다 모든 데이터셋에서 가장 높은 노드 분류 정확도를 달성했습니다.
• 상보성(Complementarity): 결과는 LCC와 GNN이 서로 다른 그래프 속성을 포착함을 보여줍니다. 대부분의 경우, 통합 모델은 개별 구성 요소보다 정확도를 향상시켰습니다.
• 레이블 워크의 효과성: LCC는 바닐라 MLP(노드 특징만을 사용하는 모델)보다 성능이 현저히 뛰어났으며, 이는 레이블 컨텍스트 임베딩이 클래스 레이블 연결성을 효과적으로 포착함을 확인시켜 줍니다. 특히 Chameleon, Squirrel, Roman-Empire, Amazon-Ratings과 같은 데이터셋에서는 정확도 향상이 10%를 초과했습니다.
• 워크 유형의 중요성: 특정 워크 유형의 중요성은 데이터셋마다 달랐습니다. 예를 들어, 가디언 워크는 Chameleon, Squirrel, Amazon-Ratings에서 가장 결정적이었던 반면, 형제 워크는 Roman-Empire에서 가장 효과적이었습니다.
• 워크 길이(Walk Length): (순방향/역방향 워크의) 워크 길이를 늘리거나 2-hop 워크(형제/가디언)를 활용하는 것이 일반적으로 성능을 향상시켰으며, 이는 고차 연결성을 포착하는 것의 필요성을 강조합니다.

의의 및 주장

본 논문은 이종성 환경에서 현재 GNN의 주요 약점이 방향성 그래프에서 클래스 레이블이 여러 홉을 통해 어떻게 연결되는지를 모델링하지 못한다는 점이라고 주장합니다. 레이블 워크를 통해 이러한 고차 관계를 명시적으로 모델링함으로써, LCC는 특징 기반 GNN에 보완적인 신호를 제공합니다.

저자들은 이 접근 방식이 기존 GNN에 복잡한 구조적 변경을 요구하지 않으며, 오히려 성능을 높이기 위해 어떤 GNN과도 적응적으로 결합할 수 있는 모듈형 분류기를 제공한다는 점을 강조합니다. 결과는 노드 특징이나 즉각적인 이웃뿐만 아니라, 클래스 레이블 사이의 구조적 정보를 활용하는 것이 이종성 방향성 그래프에서 정확한 분류를 위해 매우 중요하다는 것을 시사합니다. 본 연구는 JSPS KAKENHI 및 JST ASPIRE 그랜트의 지원을 받았습니다.