기술적 요약: 그래프 언어 모델이 암기 이상으로 나아갈 때

1. 문제 제기

본 연구가 다루는 핵심 질문은, 직렬화된 그래프 표현으로 훈련된 자기회귀 디코더인 그래프 언어 모델 (GLM) 이 그래프의 구조적 규칙성을 근본적으로 학습하는지, 아니면 단순히 훈련 데이터를 암기하여 경험적 분포에 근접한 그래프를 생성하는지에 대한 것이다.

현재의 집계 정밀도 지표 (예: 차수/클러스터링/궤도 최대 평균 불일치, GIN 기반 MMD/FID) 는 이러한 모호성을 해결하기에 부족하다. 부록 3에서 공식화되었듯, 어떤 단일 유계 서브그래프 통계량에 대한 일치성은 두 가지 regimes(구조적 패턴을 학습하는 모델과 훈련 그래프를 그대로 재현하는 모델) 모두와 수학적으로 일관된다. 보정된 기준이 없다면, 높은 정밀도 점수는 '구조적 학습'과 'verbatim(말 그대로) 회상'을 구별할 수 없다.

2. 방법론

저자들은 암기와 구조적 정렬을 분리하기 위해 설계된 보정 진단 프로토콜을 제안한다. 이 프레임워크는 두 가지 축으로 작동한다: 암기 축(verbatim 회상 vs. 신규 생성) 과 정렬 축(훈련 서브그래프 통계량에 대한 분포적 정밀도).

핵심 구성 요소

1. 그래프 수준 부트스트랩 기준선:
   이 프로토콜은 훈련 코퍼스에서 직접 재샘플링하여 구성된 비학습 참조 분포 $\hat{P}^{boot}_G$를 도입한다. 이 기준선은 오직 암기를 통해 달성 가능한 분포적 정렬을 나타낸다. 모델이 이 부트스트랩 분포에서 서브그래프 통계량이 유의미하게 벗어날 때만, 모델이 암기를 넘어섰다고 간주된다.

2. 빈도 서브그래프 마이닝 (gSpan):
   집계 그래프 통계량에 의존하는 대신, 평가는 서브그래프 패턴에 초점을 맞춘다. 최소 지원도 임계값 ($\sigma = 0.1$) 을 사용하여 gSpan 알고리즘을 employing 하여 훈련 ($D_{tr}$) 과 생성 ($D_{gen}$) 데이터베이스에서 빈번한 연결된 서브그래프를 열거한다.

3. 빈도 계층화 분석:
   정렬이 성공하거나 실패하는 지점을 드러내기 위해 서브그래프 패턴의 지원도 분포를 세 개의 층으로 분할한다:

   • 헤드 (Head): 상위 10%(고빈도 모티프).
   • 토르소 (Torso): 중간 80%(중간 빈도 패턴).
   • 테일 (Tail): 하위 10%(지원도 임계값 근처의 희귀 패턴).
     지표 (스피어만 순위 상관관계, 제이슨 - 섀넌 발산, 누락 질량) 는 각 층에 대해 독립적으로 계산된다.

4. 직렬화 강건성:
   특정 토큰화의 산물이 아닌지 확인하기 위해 두 가지 다른 직렬화 방법을 통해 분석을 수행한다:

   • 정규 DFS 코드: 동형 그래프에 대한 고유한 표현.
   • DGMG 동작 시퀀스: ADD_NODE, ADD_EDGE 등의 순차적 결정 과정을 인코딩.

실험 설정

• 모델: 직렬화된 그래프에서 처음부터 훈련된 LLaMA 스타일 인과 언어 모델 (디코더 전용).
• 데이터셋: 다섯 가지 TU 벤치마크 (MUTAG, PTC_MR, ENZYMES, PROTEINS, NCI1) 와 대규모 PCQM4Mv2 분자 코퍼스 (약 375 만 개 그래프).
• 기준선: DiGress(확산), GraphRNN, DGMG-official 을 포함한 구조적 기준선과 비교.

3. 주요 결과

A. 소규모 영역 (TU 벤치마크)

소규모 데이터셋에서 GLM 은 암기 지배적 영역에서 작동한다.

• 회상을 통한 높은 정밀도: 모델은 높은 스피어만 상관관계 ($\rho \approx 0.95\text{--}0.99$) 와 낮은 제이슨 - 섀넌 발산을 달성한다. 그러나 부트스트랩 보정은 이러한 지표가 훈련 세트의 단순 재샘플링에서 기대되는 범위 내에 있거나 그 이하임을 드러낸다.
• verbatim 회상: 전체 그래프 정확 일치율 (정밀도) 이 극도로 높다 (예: MUTAG 에서 82.8%, NCI1 에서 100%).
• 결론: 이 영역에서 집계 정밀도는 구조적 학습의 증거가 아니라 암기의 통계적 결과이다.

B. 대규모 영역 (PCQM4Mv2)

규모가 커지면 (375 만 개 그래프), 위상 전이가 발생한다.

• 분리: 전체 그래프 암기는 급격히 감소하지만 (정밀도 $\approx 31.7\%$), 서브그래프 수준의 스피어만 상관관계는 여전히 천장에 근접한다 ($\rho \approx 0.976$).
• 신규성 전용 정렬: '신규 전용' 부분집합 (암기된 그래프 제외) 으로 제한할 때, 스피어만 상관관계는 전체 생성 상관관계와 0.026 이내로 추적된다. 이는 모델이 암기되지 않은 그래프에서도 구조적 규칙성을 유지함을 확인시켜 준다.
• 결론: 대규모 GLM 은 구조적 규칙성을 성공적으로 내면화하여 암시적 신경 그래프 마이닝 역할을 수행한다.

C. 지속되는 희귀 패턴 결핍

모든 규모와 직렬화에서 근본적인 한계가 관찰된다:

• 헤드/토르소 성공: 빈번하고 중간 빈도의 패턴은 높은 정밀도로 재현된다 ($\rho \ge 0.91$).
• 테일 실패: 희귀 패턴 (테일 층) 은 일관되게 잘 커버되지 않는다. 테일의 누락 질량은 헤드/토르소에 비해 한 자릿수 더 높다 (예: TU 데이터셋에서 13.5%–22.0% 대 헤드의 <1%). 테일의 순위 상관관계는 현저히 낮다 (TU 에서 $\rho \in [0.26, 0.56]$, PCQM4Mv2 에서 $\approx 0.41$).
• 강건성: 이 결핍은 모델 용량 (1050 만에서 4 억 5100 만 파라미터로 확장) 과 직렬화 형식에 관계없이 지속되며, 희귀 서브구조에 대한 현재 자기회귀 생성의 구조적 격차를 나타낸다.

D. 기준선 비교

• DiGress (확산): 거의 제로 암기를 달성하지만 빈번한 서브그래프 분포를 복원하지 못한다 (PCQM4Mv2 에서 $\rho \approx 0.25$), 저암기/저정렬 영역을 차지한다.
• GraphRNN/DGMG-official: 레이블 인식 없는 기준선은 레이블이 있는 서브그래프 지원을 전혀 복원하지 못하여 대부분의 데이터셋에서 서브그래프 통계량을 정의할 수 없게 만든다.

4. 기여

1. 보정 진단 프로토콜: 빈번한 서브그래프 마이닝과 그래프 수준 부트스트랩 기준선을 결합한 프레임워크의 도입. 이는 정렬이 암기를 통해 달성 가능한 것을 초과하는지 명시적으로 테스트함으로써 집계 지표의 한계를 극복한다.
2. 규모 의존적 구조적 학습의 증거: GLM 이 소규모 데이터셋에서는 암기 지배적 영역에서 대규모에서는 분리된 영역으로 전환하며, 신규 그래프에 대해 서브그래프 통계량을 유지함을 입증.
3. 희귀 패턴 결핍의 식별: 모델 용량이 증가하더라도 여전히 병목이 되는 희귀 (테일) 패턴 분포 학습의 체계적 실패 노출.

5. 중요성과 주장

본 논문은 GLM 이 암기를 넘어설 수 있는지에 대해 조건부 답변을 제시한다: 예, 하지만 충분한 규모에서 그리고 주로 빈번한 서브구조에 대해서만.

• 방법론적 전환: 이 연구는 암기 참조 없이는 집계 정밀도 지표가 무의미하다고 주장한다. 높은 상관관계 점수를 올바르게 해석하기 위해 제안된 부트스트랩 보정이 필요하다.
• 암시적 마이닝: 결과는 훈련 코퍼스가 경험적 분포로의 완전한 붕괴를 방지할 만큼 충분히 크다면, 그래프 직렬화의 자기회귀 모델링이 명시적 패턴 열거 없이도 LLM 이 구조적 규칙성을 암시적으로 내면화하게 함 (즉, '신경 그래프 마이닝' 역할) 을 시사한다.
• 한계: 저자들은 겸손하게도 분포의 '헤드'는 잘 복원되지만 '테일'은 여전히 중요한 격차라고 지적한다. 모델은 지배적인 지원 구조를 포착하지만 희귀 서브구조로 일반화하지 못하는 부분적 마이너로 행동한다.

본 논문은 대규모 설정에서 관찰된 높은 정렬이 특정 직렬화 (DFS 및 DGMG 를 통해 확인됨) 의 산물이 아니라, 순수한 암기와 비-LLM 생성 기준선과 구별되는 대규모 그래프 언어 모델의 강건한 속성임을 결론짓는다.