기술 요약: 고정 집계 특징(Fixed Aggregation Features)은 GNN과 대등할 수 있다

문제 정의

그래프 신경망(GNN)은 그래프 구조 데이터로부터 학습하기 위한 표준이 되었으며, 특히 노드 분류 작업에서 그러하다. 이러한 모델들은 일반적으로 여러 층의 학습 가능한 이웃 집계(예: 학습된 선형 결합, 어텐션 메커니즘)를 통해 노드 표현을 업데이트하는 메시 전달 패러다임에 의존한다. 효과적이기는 하지만, 이 방식은 높은 모델 복잡도, 해석력의 어려움, 그리고 상당한 계산 비용을 초래한다.

최근의 증거에 따르면, 클래식 GNN(GCN, GAT, GraphSAGE)은 엄격한 하이퍼파라미터 튜닝이 동반될 경우 최첨단 그래프 트랜스포머(Graph Transformer) 및 이질성 인식(heterophily-aware) 모델들과 경쟁할 만한 수준을 유지한다. 이는 근본적인 질문을 제기한다: 학습 가능한 집계 함수를 사용하는 높은 복로(complexity)가 진정으로 필요한가? 구체적으로, 집계 자체를 학습하는 것이 다운스트림 분류 작업에 비해 얼마나 중요한가?

방법론: 고정 집계 특징 (Fixed Aggregation Features, FAFs)

저자들은 그래프 학습 작업을 표준적인 정형 데이터(tabular) 문제로 변환하는 학습 불필요(training-free) 접근 방식인 **고정 집계 특징(FAFs)**을 소개한다. 핵심 아이디어는 고정된, 학습되지 않는 집계 연산자를 사용하여 표현 학습(representation learning)과 최적화(optimization)를 분리하는 것이다.

FAF 파이프라인

1. 고정 집계: 주어진 노드 $v$에 대해, 정해진 리듀서(reducers) $\mathcal{R}$ 집합(예: mean, sum, max, min, std)을 사용하여 $k$-홉 이웃으로부터 특징을 재귀적으로 계산한다.
   • $h^{(0,r)}_v = x_v$ (원래의 특징)
   • $h^{(k,r)}_v = r(\{h^{(k-1,r)}_u : u \in \mathcal{N}(v)\})$
2. 특징 결합(Feature Concatenation): 모든 홉($k \in \{1, \dots, K\}$)과 모든 리듀서($r \in \mathcal{R}$)로부터 얻은 특징들을 원래의 노드 특징과 결합하여 고차원의 정형 벡터 $z_v$를 형성한다.
   • $z_v = x_v \oplus \bigoplus_{r \in \mathcal{R}} \bigoplus_{k=1}^K h^{(k,r)}_v$
3. 다운스트림 분류: 이 고정된 특징 $z_v$에 대해 표준적이고 잘 튜닝된 다층 퍼셉트론(MLP)을 학습시킨다. 집계 단계에는 그래디언트가 역전파되지 않는다; 즉, 집계는 전처리 단계이다.

이론적 토대

본 논문은 FAF를 **콜모고로프-아놀드 표현 정리(Kolmogorov–Arnold representation theorem)**와 연결한다. 이 정리는 임의의 다변수 연속 함수가 일변수 함수들의 합성으로 표현될 수 있음을 명시한다.

• 이론적 가능성: 저자들은 삼진 전개(ternary expansions)와 칸토어 집합(Cantor set)에 기반한 특정 고정 불변(fixed) 인젝티브(injective) 집계 함수 $\Phi$를 구축하며, 이는 이론적으로 이웃 멀티셋(multisets)의 손실 없는 인코딩을 가능하게 함을 보여준다. 이는 이론적으로 집계 과정에서 정보를 학습할 필요가 없음을 의미한다.
• 실제적 현실: $\Phi$는 이론적으로는 손실이 없으나, 수치적으로 취약하며 표준 분류기에 부적합한 "거친(rough)" 임베딩을 생성한다. 반면, 단순하고 비인젝티브(non-injective)한 리듀서(예: mean, sum)는 경험적으로 최적화에 더 용이하다. 저자들은 대부분의 벤치마크에서 관련 신호가 낮은 홉(1–2 홉)의 이웃에 집중되어 있으며, 단순한 집계가 충분한 정보를 보존한다고 주장한다.

주요 기여

1. 이론적 통찰: 본 논문은 콜모고로프-아놀드 표현에서 유도된 고정된 인젝티브 함수를 통해 손실 없는 이웃 집계가 이론적으로 가능하다는 것을 입증한다. 그러나 이는 *표현력(expressivity)*과 학습 가능성(learnability) 사이의 중대한 간극을 강조한다. 즉, 단순한 비인젝티브 리듀서들이 더 나은 실질적 성능을 보이는 이유는 이들이 다운스트림 분류기가 더 효과적으로 최적화할 수 있는 매끄러운 임베딩을 생성하기 때문이다.
2. 방법론적 제안: 그래프 데이터를 고정된 다중 홉 집계를 쌓아 올려 정형 데이터 형식으로 변환하는 FAF를 도입한다. 이는 구조적 편향 없이 그래프 구조, 특징, 그리고 작업 간의 상호작는 관계를 연구할 수 있는 해석 가능한 프레임워크를 제공한다.
3. 경험적 증거: 14개의 표준 노드 분류 벤치마크에 대한 광범위한 실험을 통해, 잘 튜닝된 MLP와 결합된 FAF가 14개 작업 중 12개에서 최첨단 GNN 및 그래프 트랜스포머와 대등하거나 이를 능가함을 보여준다.
   • 성능: FAF는 인용 네트워크(Cora, Citeseer, PubMed), 공동 저자 그래프, Amazon 제품 그래프에서 클래식 GNN(GCN, GAT, SAGE) 및 복잡한 아키텍처와 대등하거나 더 높은 성능을 보인다.
   • 예외 사항: FAF는 Roman Empire와 Minesweeper 데이터셋에서는 성능이 저하된다. 저자들은 이를 해당 데이터셋이 장거리 의존성이나 특정 선형 잔차 연결(linear residual connections)을 요구하기 때문으로 보며, 이는 일반적인 FAF(2–4 홉 사용)가 포착하지 못하는 부분이며, 파라미터화된 잔차를 가진 깊은 GNN이 유리하다는 기존 연구 결과와 일치한다.
4. 벤치마킹에 대한 시사점: 결과는 현재의 표준 벤치마크에서 학습 가능한 집계의 필요성에 의문을 제기한다. 저자들은 많은 데이터셋이 강력한 정형 예측기에 의해 해결될 수 있으며, 이는 현재의 벤치마크가 복잡한 집계 역학을 학습하는 능력을 적절히 테스트하지 못하고 있음을 시사한다고 주장한다.

결과 및 분석

• 절제 연구(Ablation Studies):
  • 분류기 복잡도: 잘 튜닝된 MLP는 FAF 특징에 적용되었을 때 단일 선형 레이어보다 유의미하게 우수한 성능을 보인다. 이는 비선형성과 용량(capacity)이 다중 홉 정보를 활용하는 데 매우 중요하다는 것을 나타낸다.
  • 홉 결합(Hop Concatenation): 모든 홉의 특징을 결합하는 것이 마지막 홉만 사용하는 것보다 성능이 좋았다. 이는 반복적인 집계 과정에서 정보가 손실됨을 확인시켜 주며, 초기 홉(0–2)이 가장 예측력이 높은 신호를 포함하고 있음을 입증한다.
  • 리듀서 선택: 여러 리듀서(예: mean, sum, max, min)를 결합하는 것이 일반적으로 유익하지만, 단일 리듀서(종종 mean)만으로도 충분하며 때로는 복잡한 조합보다 더 나은 성능을 보인다. 이는 고차원 공간에서의 과적합 감소 때문인 것으로 보인다.
• 해석 가능성: 문제를 정형 데이터로 취급함으로써, 저자들은 SHAP 값을 활용하여 특징 중요도를 분석했다. 예를 들어, Minesweeper 데이터셋에서 특정 특징의 hop-1 mean이 주요 신호임을 식별하여 모델이 성공하거나 실패하는 지점을 명확히 밝혔다.
• 효율성: 집계를 미리 계산하고 MLP를 학습하는 것은 일반적으로 깊은 GNN을 학습하는 것보다 확장성이 높고 효율적이지만, 홉과 리듀서의 수에 따라 입력 차원이 증가한다.

의의 및 주장

본 논문은 그래프 학습 분야가 단순한 고정 통계만으로도 충분한 작업에 대해 지나치게 복잡하고 학습 가능한 집계 메커니즘에 의존하고 있다고 주장한다. 저자들의 주장은 다음과 같다:

1. 강력한 베이스라인: FAF는 향후 그래프 학습 연구에서 필수적인 강력한 베이스라인 역할을 해야 한다. 만약 새로운 GNN이 잘 튜닝된 FAF를 능가하지 못한다면, 그 추가된 복잡성은 정당화될 수 없다.
2. 벤치마크의 재평가: 현재의 표준 벤치마크(예: Cora, Citeseer)는 학습 가능한 집계가 실제로 필요하지 않을 수 있다. 예측 신호가 흔히 저차(low-order) 이웃에 집중되어 있기 때문이다. 저자들은 장거리 의존성과 복잡한 홉 간 역학을 진정으로 테스트할 수 있는 "더 풍부한 벤치마크"를 요구한다.
3. 최적화 vs 표현력: FAF의 성공은 **최적화 가능성(optimizability)**과 **학습 가능성(trainability)**이 이론적 표현력만큼이나 중요하다는 것을 시사한다. 복잡한 GNN은 표현력이 부족해서가 아니라, 최적화의 어려움(예: 기울기 소실, 오버 스무딩)으로 인해 유용한 집계를 학습하는 데 어려움을 겪을 수 있다.
4. 정형 데이터 관점: 그래프 문제를 정형 데이터 문제로 변환하면 연구자들이 정형 데이터 학습의 성숙한 도구들(특징 선택, 해석력, 클래스 불균형 처리 등)을 활용할 수 있으며, 최적화의 부산물로부터 그래프 구조의 기여도를 분리해낼 수 있다.

결론적으로, 저자들은 관점의 전환을 촉구한다. 추가적인 파라미터나 더 높은 표현력이 자동으로 더 관련성 있는 신호를 추출한다고 가정하기보다는, 더 단순하고 해석 가능한 모델을 우선시하고, 복잡한 집계 함수 학습을 진정으로 필요로 하는 벤치마크를 설계해야 한다는 것이다.