GraphProp: Training the Graph Foundation Models using Graph Properties

이 논문은 그래프 불변량을 예측하여 구조적 일반화 능력을 갖춘 그래프 기초 모델을 학습한 후, 이를 위치 인코딩으로 활용하여 도메인 간 일반화 성능을 극대화하는 'GraphProp'을 제안하고, 특히 노드 속성이 없는 그래프에서 기존 방법보다 우수한 성능을 입증합니다.

핵심

1. 문제: 왜 기존 AI 는 헷갈려 할까요?

지금까지의 AI 모델들은 각기 다른 세계 (도메인) 에서 온 데이터를 섞어 공부할 때 어려움을 겪었습니다.

• 상황: 한쪽에는 분자 (약물) 데이터가 있고, 다른 쪽에는 소셜 네트워크 (친구 관계) 데이터가 있다고 상상해 보세요.
• 기존 방식의 한계:
  • 분자 데이터: 원자들이 어떤 화학 성질을 가졌는지 (노드 특징) 를 중요하게 여깁니다.
  • 소셜 데이터: 사람들이 어떤 취미나 성격을 가졌는지 (노드 특징) 를 중요하게 여깁니다.
  • 문제점: AI 가 "화학 성질"과 "사람의 성격"을 섞어서 공부하려니, 두 세계가 너무 달라서 공통된 규칙을 찾기 힘들었습니다. 마치 "사과와 오렌지를 섞어서 만든 새로운 과일"을 찾으려다 보니, 둘 다 제대로 못 이해하게 된 거죠.

2. 해결책: GraphProp 의 핵심 아이디어

저자들은 **"노드 (원자/사람) 의 특징보다는, 그들을 연결하는 '구조'가 더 공통된 언어를 가진다"**는 것을 발견했습니다.

• 비유: 분자든, 친구 관계든, **모양 (구조)**은 비슷합니다.
  • 예: "이 모양은 3 개의 점이 서로 연결되어 있다"라는 사실은 분자든, 친구 관계든 똑같이 적용됩니다.
  • 하지만 "이 점은 탄소 원자다" 또는 "이 점은 김철수다"라는 정보는 도메인마다 완전히 다릅니다.

그래서 GraphProp 은 구조 (모양) 를 먼저 배우고, 그다음에 세부 정보 (노드 특징) 를 배웁니다.

3. GraphProp 의 두 단계 학습 과정

이 방법은 두 단계로 나뉩니다. 마치 건축가가 건물을 짓는 과정과 같습니다.

1 단계: 구조 기초 공학 (Structural GFM) - "모양만 보고猜는 훈련"

• 목표: AI 에게 그래프의 **수학적 성질 (그래프 속성)**을 맞추는 훈련을 시킵니다.
• 방법:
  • AI 에게 "이 그래프의 지름은 얼마야?", "이 그래프는 몇 개의 조각으로 나뉠 수 있어?", "이 그래프의 색칠하기는 몇 가지 색이 필요해?" 같은 수학적 퀴즈를 냅니다.
  • 이 퀴즈들은 노드가 무엇인지 (화학 원자인지, 사람인지) 상관없이 오직 **모양 (구조)**만으로 정답을 맞출 수 있습니다.
  • 효과: AI 는 이제 어떤 도메인 (분자, 소셜 등) 에 속하든, 그래프의 모양을 통찰력 있게 이해하는 능력을 갖게 됩니다. 이는 마치 모든 건물의 구조를 이해하는 건축가가 된 것과 같습니다.

2 단계: 종합 건축 (Comprehensive GFM) - "세부 정보 입히기"

• 목표: 1 단계에서 배운 '구조 이해력'을 바탕으로, 실제 데이터의 세부 정보 (노드 특징) 를 학습합니다.
• 방법:
  • 이제 AI 는 "아, 이 모양은 구조적으로 이런 특징이 있구나"라고 알고 있습니다.
  • 여기에 "그리고 이 노드는 탄소 원자야", "저 노드는 김철수야"라는 세부 정보를 덧붙여서 최종적인 판단 (분자 분류, 커뮤니티 분류 등) 을 내립니다.
  • 효과: 구조를 이미 잘 이해하고 있기 때문에, 노드 정보가 없는 그래프 (예: 친구 관계만 있고 이름이 없는 데이터) 에서도 아주 잘 작동합니다.

4. 왜 이것이 혁신적인가요? (장점)

1. 데이터가 없어도 공부할 수 있어요:

   • 기존에는 레이블 (정답) 이 있는 데이터가 엄청 많이 필요했습니다.
   • 하지만 GraphProp 은 레이블이 없는 데이터나 인위적으로 만든 가짜 데이터로도 1 단계 훈련을 할 수 있습니다. (수학적 퀴즈를 맞추는 데는 정답 레이블만 있으면 되니까요.)
   • 비유: 요리사가 레시피 (정답) 가 없는 재료만 보고도 "이 재료는 어떻게 조리해야 맛있는지"를 수학적으로 추론해 내는 것과 같습니다.

2. 노드 정보가 없는 데이터도 다룰 수 있어요:

   • 많은 AI 는 "사람 이름"이나 "화학 성분" 같은 정보가 없으면 망칩니다.
   • 하지만 GraphProp 은 **모양 (구조)**만으로도 충분히 잘 작동합니다.

3. 새로운 분야로 쉽게 적응:

   • 분자 데이터를 배운 AI 가 갑자기 소셜 네트워크 데이터를 만나도, "아, 모양이 비슷하네"라고 바로 적응할 수 있습니다.

5. 요약

GraphProp은 AI 에게 "무엇인가 (노드 특징)"를 외우게 하는 대신, **"어떻게 연결되어 있는지 (구조)"**를 깊이 있게 이해하도록 가르칩니다.

• 기존: "이건 사과고, 저건 오렌지야." (도메인마다 다름)
• GraphProp: "이건 둥글고, 저건 네모나. 모양을 먼저 보고 분류하자." (공통된 규칙)

이렇게 하면 AI 는 훨씬 더 똑똑해지고, 데이터가 부족하거나 정보가 없는 상황에서도 뛰어난 성능을 발휘할 수 있게 됩니다. 마치 모든 언어의 문법 (구조) 을 먼저 배운 후, 각 언어의 단어 (노드 특징) 를 익히는 것과 같습니다.

기술 요약

1. 문제 정의 (Problem)

그래프 기반 모델 (Graph Foundation Models, GFMs) 은 다양한 도메인 (예: 분자, 소셜 네트워크) 에서 그래프 분류와 같은 그래프 레벨 작업에 대한 강력한 일반화 능력을 목표로 합니다. 그러나 기존 GFMs 는 다음과 같은 한계를 가지고 있습니다.

• 도메인 간 불일치: 노드 특성 (Node Features) 과 그래프 라벨은 도메인마다 매우 다르게 분포합니다 (예: 분자의 화학적 속성 vs 소셜 네트워크의 사용자 속성). 이로 인해 단일 모델이 도메인 간에 통일된 표현을 학습하기 어렵습니다.
• 구조적 일반화 부족: 기존 방법들은 주로 텍스트 기반의 노드 특성을 통합하는 데 초점을 맞추거나, LLM 을 이용한 추론에 의존합니다. 그러나 이는 그래프의 추상적인 구조적 정보를 도메인 간에 일관되게 전달하는 데 실패하며, 특히 노드 특성이 없는 그래프 (Node-featureless graphs) 에서는 성능이 급격히 저하됩니다.
• 데이터 부족: 대규모 GFMs 훈련을 위한 레이블이 지정된 데이터는 부족하지만, 레이블이 없는 데이터나 합성 데이터는 풍부합니다.

2. 방법론 (Methodology)

저자들은 그래프의 **구조 (Structure)**가 노드 특성보다 도메인 간에 더 일관된 정보 (불변성) 를 담고 있다는 통찰에서 출발하여 GraphProp을 제안했습니다. 이 방법은 두 단계로 구성됩니다.

단계 1: 그래프 불변성 (Graph Invariants) 을 활용한 구조적 GFM 훈련

• 핵심 아이디어: 그래프의 추상적 구조에만 의존하는 '그래프 불변성 (Graph Invariants)'을 예측하여 모델을 훈련시킵니다. 불변성은 그래프의 라벨링이나 표현 방식에 관계없이 구조 자체에 의해 결정되는 속성 (예: Fiedler 값, Lovász 수, 분수 채색수 등) 입니다.
• 훈련 과정:
  1. 입력: 노드 특성 없이 순서도 행렬 (Adjacency Matrix, $A$) 만을 입력으로 사용합니다.
  2. 위치 인코딩: $A$를 역변환 가능한 (Reversible) 위치 인코딩 행렬 $B$로 변환합니다 (스펙트럴 임베딩은 역변환이 불가능하여 사용 불가).
  3. 모델: 그래프 트랜스포머 (Graph Transformer) 를 사용하여 구조적 표현 $Z$를 생성하고, 회귀기 (Regressor) 를 통해 $K$개의 그래프 속성 벡터 $\hat{p}$를 예측합니다.
  4. 손실 함수: 예측된 속성과 실제 계산된 속성 간의 오차를 최소화하도록 파라미터를 최적화합니다.
• 데이터 증강: 이 단계에서는 레이블이 없는 그래프나 합성 그래프 (Synthetic Graphs) 도 훈련에 활용할 수 있어 데이터 부족 문제를 해결합니다.

단계 2: 문맥 학습 (In-context Learning) 을 통한 종합적 GFM 훈련

• 목표: 훈련된 구조적 GFM 의 표현을 활용하여 도메인 특유의 노드 특성과 라벨을 통합합니다.
• 과정:
  1. 단계 1 에서 학습된 구조적 GFM 을 사용하여 각 그래프의 구조적 표현 $Z$를 계산합니다.
  2. 이 구조적 표현 $Z$를 **위치 인코딩 (Positional Encoding)**으로 사용하여, 기존에 학습된 도메인 특유의 노드 특성 (TAG, Text-Attributed Graphs) 과 결합합니다.
  3. 결합된 특징 행렬을 통해 최종 그래프 분류 작업을 수행하는 종합적 GFM 을 훈련합니다.

3. 주요 기여 (Key Contributions)

1. GraphProp 프레임워크 제안: 그래프 속성 예측을 통해 구조적 GFM 을 먼저 훈련하고, 이를 기반으로 문맥 학습을 통해 종합적 GFM 을 구축하는 새로운 훈련 패러다임을 제시했습니다.
2. 이중 일반화 달성: 기존 GFMs 가 노드 특성 일반화에 치중했던 것과 달리, GraphProp 은 구조적 일반화와 노드 특성 일반화를 동시에 달성한 최초의 그래프 레벨 작업용 GFM 입니다.
3. 이론적 증명: 제안된 방법이 그래프 구별 능력 (Graph-discrimination ability) 을 가짐을 수학적으로 증명했습니다. 즉, 유사한 그래프는 유사한 속성을 예측하고, 다른 그래프는 다른 속성을 예측함을 보였습니다.
4. 그래프 이론과 GFM 의 융합: 그래프 이론의 다양한 속성 (Fiedler 값, Lovász 수 등) 을 지도 학습의 레이블로 활용하여, 레이블이 없는 데이터와 합성 데이터를 효과적으로 활용할 수 있게 했습니다.

4. 실험 결과 (Results)

저자들은 분자 데이터 (노드 특성 있음) 와 소셜/그래프 데이터 (노드 특성 없음) 를 포함한 다양한 도메인에서 실험을 수행했습니다.

• 지도 학습 (Supervised Learning):
  • 노드 특성이 있는 데이터 (G1): OFA(One For All) 등 기존 최첨단 모델보다 약간 더 나은 성능을 보였습니다.
  • 노드 특성이 없는 데이터 (G2): GraphProp 은 OFA, BRIDGE, EdgePrompt+ 등 모든 경쟁 모델보다 압도적으로 우수한 성능을 기록했습니다. 특히 COLLAB, IMDB-B, DD 데이터셋에서 큰 향상을 보였습니다. 이는 구조적 일반화 능력이 노드 특성이 없는 환경에서 결정적인 역할을 함을 의미합니다.
• Few-shot 학습 (Few-shot Learning):
  • 소량의 데이터 (k-shot) 로 새로운 도메인이나 클래스에 적응하는 능력에서도 GraphProp 이 다른 모델들을 일관되게 능가했습니다.
• 결론: GraphProp 은 특히 노드 특성이 부재하거나 도메인 간 차이가 큰 상황에서 가장 강력한 일반화 능력을 입증했습니다.

5. 의의 및 의의 (Significance)

• 구조 중심의 패러다임 전환: 그래프 모델 훈련에 있어 노드 특성보다 그래프 구조의 불변성이 도메인 간 전이 학습에 더 핵심적인 요소임을 입증했습니다.
• 데이터 효율성: 레이블이 없는 그래프나 합성 그래프를 훈련에 활용할 수 있게 함으로써, 대규모 GFMs 훈련에 필요한 데이터 부족 문제를 해결하는 길을 열었습니다.
• 범용성: 화학, 소셜 네트워크 등 다양한 도메인의 그래프 데이터를 통합적으로 처리할 수 있는 범용 그래프 모델 개발의 새로운 기준을 제시했습니다.

요약하자면, GraphProp은 그래프의 본질적인 구조적 속성을 예측하는 것을 통해 도메인 간 일관된 표현을 학습하고, 이를 기반으로 노드 특성을 통합하여 그래프 레벨 작업에서 최고의 일반화 성능을 달성하는 혁신적인 방법론입니다.