기술 요약: 완전 유도형 그래프 신경망을 위한 구조적 상호작용 그래프 상의 뉴럴 메시지 패싱

1. 문제 정의

그래프 파운데이션 모델(Graph Foundation Models, GFMs)의 개발은 **입력 이질성(input heterogeneity)**이라는 핵심적인 장애물에 직면해 있습니다. 자연어와 달리, 공유된 토큰 어휘집을 통해 모델이 모든 텍스트를 인코딩할 수 있는 것과 달리, 그래프는 차원, 좌표 의미론(coordinate semantics), 레이블 집합이 서로 다른 고유한 노드 특징 공간을 가지고 도착합니다. 결과적으로, 한 그래프에서 학습된 모델은 일반적으로 다른 그래프를 "읽을" 수 없습니다.

기존의 접근 방식들은 이러한 과제의 일부를 해결하지만 이를 통합하는 데는 실패합니다:

• 노드 분류 GFM: GraphAny와 같은 방법은 임의의 특징 및 레이블 공간을 처리하지만, 링크 예측이나 관계 추론을 위한 메커니즘이 부족한 노드 분류만을 위해 설계되었습니다.
• 지식 그래프 파운데이션 모델(KGFMs): ULTRA와 같은 모델은 이산적인 관계 유형에 대한 "관계 그래프"를 구축함으로써 지식 그래프에서 제로샷 전이를 달もの합니다. 그러나 이 접근 방식은 근본적으로 이산적입니다. 즉, 유한한 관계 어휘집을 가정하며 연속적인 노드 또는 에지 특징을 위한 메커니즘이 결여되어 있습니다.

핵-과제는 세 가지 축(보지 못한 그래프 구조, 보지 못한 특징 공간(임의의 차원 및 의미론), 보지 못한 레이블 공간)에 대해 동시에 일반화할 수 있는 완전 유도형(fully-inductive) 그래프 모델을 설계하는 것입니다.

2. 방법론: Sigil 프레임워크

저자들은 임의의 속성 그래프를 통일된 고정 차원 표현 공간으로 매핑하는 Sigil(Structural Interaction Graphs for Inductive Learning) 프레임-워크를 제안합니다. 핵심 혁신은 **구조적 상호작용 그래프(Structural Interaction Graph, SIG)**입니다.

2.1 구조적 상호작용 그래프(SIG) 구축

노드 특징 $X \in \mathbb{R}^{n \times d}$를 가진 입력 그래프 $G=(V, E)$가 주어졌을 때, Sigil은 그래프를 노드 도메인에서 특징 차원 도메인으로 "리프트(lift)"합니다.

1. 다중 차수 전파(Multi-Order Propagation): 특징은 비매개변수적 전파를 사용하여 증가하는 이웃 차수 $k$ ($0$에서$K$까지)에 따라 전파됩니다:$X^{(k)} = A^k X$.
2. 상호작용 연산자(Interaction Operators): 각 차수 $k$에 대해, 인접한 노드의 특징에 상호작용 연산자 $g$(예: 뺄셈 또는 요소별 곱셈)를 적용하여 에지 특징을 생성합니다.
3. 역할 집계(Role Aggregation): 이러한 에지 특징은 역할(방향 그래프의 경우 head/tail)에 따라 노드로 다시 집계되어 요약 행렬 $\bar{X}^{(k)}_h$ 및 $\bar{X}^{(k)}_t$를 생성합니다. 이 행렬들은 특징 값이 국소적 이웃 전체에 걸쳐 어떻게 실체화되는지를 특징짓습니다.
4. 그람 행렬(Gram Matrix) 구축: 특징 차원 간의 정렬은 요약 벡터들의 내적(inner product)인 그람 행렬 $\bar{A}^{(k)} = (\bar{X}^{(k)})^\top \bar{X}^{(k)}$를 계산함으로써 포착됩니다.
5. SIG: 결과 행렬 $\bar{A}^{(k)}$는 구조적 상호작용 그래프 $G_{struct}$를 형성합니다. 이 그래프에서:
   • 노드는 입력 특징 차원 $[d]$입니다.
   • 에지는 가중치가 있고 유형이 지정되어 있으며, 서로 다른 연결 차수에서 특징 쌍이 어떻게 정렬되는지를 인코딩합니다.
   • 방향 그래프의 경우, 구성 과정에서 4개의 슬라이스(head-head, tail-tail, head-tail, tail-head)가 생성되어 방향성 상호작용을 포착합니다.

2.2 관계형 메시지 패싱을 통한 표현 학습

SIG가 구축되면, **관계형 메시지 패싱 네트워크(RMPNN)**가 그 위에서 작동합니다:

• 임베딩(Embedding): RMPNN은 각 특징 차원 $f \in [d]$를 고정된 크기의 은닉 공간 $d_h$로 임베딩합니다.
• 변환(Transformation): 학습된 특징 임베딩 $\Theta^{(T)} \in \mathbb{R}^{d \times d_h}$는 임의의 그래프의 원래 노드 특징을 통일된 표현으로 변환하는 데 사용됩니다: $H = X \Theta^{(T)}$.
• 유도적 특성(Inductive Property): RMPNN 파라미터는 오직 고정된 은닉 너비 $d_h$에 대해서만 작동하고 입력 차원 $d$에는 영향을 미치지 않으므로, 단일하게 학습된 Sigil 모델은 임의의 특징 차원을 가진 그래프를 처리할 수 있습니다.

2.3 다운스트림 태스크

• 링크 예측(Link Prediction): 통일된 노드 표현은 표현력이 풍부한 링크 예측 GNN(예: NBFNet)에 입력되어 제로샷 추론을 수행합니다.
• 노드 분류(Node Classification): 통일된 표현은 레이블을 예측하기 위해 다운스트림 디코더(예: 경량 MLP 또는 폐쇄형 해석적 솔루션)의 입력으로 사용됩니다.

3. 주요 기여 및 이론적 특성

3.1 KGFM의 엄격한 일반화

본 논문은 Sigil이 기존의 지식 그래프 파운데이션 모델(예: ULTRA)의 **엄격한 일반화(strict generalization)**임을 증명합니다.

• 정리 1: 입력 특징이 이산적 관계의 원-핫 인디케이터(one-hot indicators)인 경우, SIG 구성은 KGFM에서 사용되는 관계 그래프를 정확히 복구합니다.
• 확장: KGFM과 달리, Sigil은 연속적인 특징을 수용합니다. 그람 행렬은 정수 형태의 공생 빈도(co-occurrence counts)가 아닌 연속적인 특징 정렬 행렬이 됩니다. 또한, Sigil의 다중 차수 전파는 KGFM(단일 홉 모티프에 국한됨)이 놓치는 특징 간의 고차 상호작용을 인코딩합니다.

3.2 대칭성 및 등변성(Symmetry and Equivariance)

Sigil은 완전 유도형 일반화에 필요한 대칭성을 충족합니다:

• 노드 치환 등변성(Node Permutation Equivariance): 출력 노드 표현은 입력 노드의 치환에 대해 등변합니다.
• 특징 치환 불변성(Feature Permutation Invariance): 통일된 표현은 입력 특징 차원의 순서나 정체성에 대해 불변합니다. 이를 통해 모델은 한 번도 본 적 없는 특징 공간을 가진 그래프를 읽을 수 있습니다.
• 레이블 치환 등변성(Label Permutation Equivariance): 등변 디코더와 결합될 때, 모델은 레이블 치환을 존중합니다.

4. 실험 결과

저자들은 단일 모델을 Cora 데이터셋(링크 예측 및 노드 분류용) 또는 여러 지식 그래프의 혼합(KG 추론용)으로 사전 학습하여 세 가지 체제에서 Sigil을 평가합니다.

4.1 링크 예측 (연속 특징)

11개의 벤치마크(속성 그래프 7개, 비속성 그래프 4개)에서 평가되었습니다.

• 속성 그래프: Sigil-lp는 모든 데이터셋에서 가장 강력한 완전 유도형 방법이며, UniLP 및 TFMLinker를 능가합니다. 특히 CiteSeer 및 AmazonPhotos와 같은 데이터셋에서 UniLP를 크게 앞지르며, SIG를 통해 특징 공간을 활용하는 것이 특징을 버리는 것보다 우월함을 입증했습니다.
• 비속성 그래프: Sigil-lp는 경쟁력을 유지하며, 완전 유도형 방법 중 2위를 차지하였고 높은 안정성을 보여주었습니다.
• 효율성: Sigil-lp는 추론을 몇 분 안에 완료하는 반면, UniLP와 같은 인컨텍스트(in-context) 베이스라인은 24시간 이상의 시간을 초과합니다.

- 지식 그래프 추론

ULTRA 벤치마크(보지 못한 엔티티 및 관계가 있는 유도 설정)에서 평가되었습니다.

• 재현: Sigil(0) (차수 0 SIG)은 기존 KGFM의 성능을 작은 차이 내에서 재현합니다 (예: 사전 학습 그래프에서 MRR을 정확히 일치시킴).
• 표현력: 고차 SIG(Sigil(1), Sigil(2))는 데이터셋에 따라 가변적인 성능을 보였으며, 이는 고차 상호작용이 표현력을 더해주기는 하지만 모든 태스크에서 균일하게 성능을 향상시키지는 않는다는 것을 시사합니다.

4.3 노드 분류

다양한 특징 차원과 클래스 수를 가진 26개 벤치마크에서 평가되었습니다.

• 성능: Sigil-nc는 경쟁력이 있으며, 26개 중 10개 데이터셋에서 최고 또는 2위의 성능을 기록했습니다. 특정 태스크에 최적화된 RGVT 및 TAG와 같은 전문 모델에는 뒤처지지만, GraphAny 및 TS-MEAN보다는 뛰어납니다.
• 분석: 저자들은 이러한 성능 격차를 "통합의 비용(cost of unification)" 때문이라고 설명합니다. 즉, 임의의 특징 공간을 고정된 차원 $d_h$로 압축하면 원래의 좌표를 디코더가 접근할 수 없게 되어 더 많은 감독(supervision)이 필요하게 됩니다. 그러나 결과는 SIG 상에서 학습하는 것이 노드 분류를 위한 그래프 파운데이션 모델로서 유효한 접근법임을 확인시켜 줍니다.

5. 의의 및 주장

본 논문은 Sigil이 다음과 같이 이전에 분리되어 있던 여러 그래프 파운데이션 모델 설계 체제를 통합한다고 주장합니다:

1. 통합: 노드 분류 GFM(임의의 특징 처리)과 KGFM(관계 추론 처리) 사이의 간극을 메워, 두 가지 모두를 위한 단일 메커니즘을 제공합니다.
2. 전이 가능성: 단일 모델이 완전히 다른 특징 공간과 구조를 가진 그래프에 대해 강력한 제로샷 성능을 제공할 수 있음을 입증했습니다.
3. 일반화: 관계 그래프를 구조적 상호작용 그래프의 이산적 사례로 공식화함으로써, 본 연구는 관계 추론을 연속적인 입력 공간으로 확장하기 위한 이론적 토대를 제공합니다.

저자들은 전이 가능성, 관계 추론, 그리고 에지 수준의 태스크가 별도의 설계가 아닌 단일 메커니즘(SIG 구축 및 메시지 패싱)으로부터 발생할 수 있다고 결론짓습니다. 향후 연구로는 SIG 상에서의 학습을 위한 아키텍처 개선 및 그 표현력에 대한 연구가 제안되었습니다.