Spectral Embeddings Leak Graph Topology: Theory, Benchmark, and Adaptive Reconstruction

1. 문제 정의 (Problem Definition)

• 현실적 제약: 연동 그래프 학습 (FGL) 및 분산 시스템에서는 각 클라이언트가 전체 그래프가 아닌 국소적인 부분 그래프 (Local Subgraph) 만을 보유합니다. 또한, 프라이버시 보호를 위해 원본 인접 행렬 대신 **스펙트럴 임베딩 (고유벡터)**이나 노이즈가 추가된 요약 데이터만 공유됩니다.
• 수동 유출 위협 (Passive Leakage Threat): 공격자가 그래프 구조를 직접 조작하는 것이 아니라, 합법적으로 공유된 스펙트럴 임베딩 (고유벡터) 을 관찰만 하더라도 원래 그래프의 위상 구조를 복원할 수 있습니다. 이는 기존에 알려진 그래디언트 기반 공격과 달리, 공유된 데이터 자체의 고유한 속성에서 발생하는 근본적인 취약점입니다.
• 핵심 과제:
  1. 분할되고 노이즈가 섞인 스펙트럴 조각 (Fragments) 으로부터 그래프를 얼마나 정확하게 복원할 수 있는지 측정할 수 있는 벤치마크 부재.
  2. 불완전한 조각들을 어떻게 효과적으로 조립하여 전체 그래프를 복구할 수 있는지에 대한 알고리즘 부재.

2. 주요 기여 (Key Contributions)

A. LoGraB (Local Graph Benchmark)

• 목적: 분할, 스펙트럴 단축 (Truncation), 노이즈가 결합된 환경을 체계적으로 평가하기 위한 벤치마크입니다.
• 데이터 생성 전략:
  1. 노드 중심 d-hop 패치: 각 노드 주변의 d-거리 내 노드들을 패치로 생성.
  2. 클러스터 기반 분할: 그래프를 클러스터로 나누고 경계에서 1-hop 이웃을 포함하여 중첩을 만듦.
  3. 무작위 중첩 패치: 임의의 시드 노드에서 생성된 불규칙한 패치들.
• 제어 가능한 파라미터:
  • $d$: 이웃 반경 (Locality)
  • $k$: 유지된 고유벡터 수 (Spectral Quality)
  • $\sigma$: 가우시안 노이즈 수준
  • $p$: 커버리지 비율 (생성된 패치가 전체 노드를 얼마나 덮는지)
• 평가 태스크:
  1. 그래프 재구성 (Graph Reconstruction): 국소 조각들로부터 전체 그래프 복원.
  2. 국소 노드 분류 (Localized Node Classification): 분할된 뷰 내에서 노드 레이블 예측.
  3. 분할 간 링크 예측 (Inter-fragment Link Prediction): 서로 다른 조각에 속한 노드 간의 연결성 예측.
• 새로운 지표: Island Cohesion (섬 결속도) - 단순히 에지 정확도뿐만 아니라 복원된 그래프가 내부적으로 구조적으로 일관된 '섬 (Island)'을 형성하는지 측정하는 지표.

B. AFR (Adaptive Fidelity-driven Reconstruction)

• 개요: 노이즈가 섞이고 품질이 불균일한 스펙트럴 조각들을 적응적으로 조립하여 그래프를 복구하는 알고리즘입니다.
• 핵심 메커니즘:
  1. 신뢰도 점수 (Fidelity Score): 각 패치의 품질을 정량화합니다.
     • Gap-to-truncation Ratio: 스펙트럴 갭과 단축 오차의 비율 (안정성).
     • 구조적 엔트로피 (Structural Entropy): 노드 차수의 다양성 (Procrustes 정렬의 조건부 상태 판단).
  2. 3 단계 파이프라인:
     • Stage 1 (국소 재구성): 히트 커널 (Heat Kernel) 을 이용해 스펙트럴 임베딩에서 국소 인접 행렬을 복원하고 신뢰도 점수를 산출.
     • Stage 2 (적응형 섬 조립): 신뢰도가 높은 '핵심 패치 (Core Patches)'를 우선순위로 선정. RANSAC-Procrustes를 사용하여 아웃라이어가 있는 경우에도 견고하게 정렬 (Alignment) 하고, 신뢰도에 따라 조립 기준 (Overlap 크기 등) 을 동적으로 조정.
     • Stage 3 (전역 정제): Bundle Adjustment를 통해 누적된 정렬 오차를 보정하고, Cross-voting 메커니즘을 통해 서로 다른 섬 (Island) 간의 잠재적 연결을 추론.

C. 이론적 분석 (Theoretical Analysis)

• 스펙트럴 유출 명제 (Spectral Leakage Proposition): 스펙트럴 갭 (Spectral Gap) 이 존재하고 충분한 수의 고유벡터 ($k \ge k^*$) 가 공유될 경우, 다항 시간 (Polynomial-time) 내에 베이지안 추론을 통해 그래프를 복구할 수 있음을 정보 이론적으로 증명 (Heuristic 기반).
• 국소 복구 보장: AFR 알고리즘에 대해 열 커널 분리 갭 (Heat-kernel separation gap), Davis-Kahan 섭동 안정성, 그리고 정렬 오차의 한계를 엄밀하게 증명했습니다.

3. 실험 결과 (Results)

• 데이터셋: Cora, CiteSeer, PubMed, ogbn-arXiv, BlogCatalog 등 9 개의 다양한 데이터셋 (인용 네트워크, 소셜 그래프, 생물학적 구조, 분자 접촉 등).
• 그래프 재구성 (Task 1):
  • AFR 은 9 개 데이터셋 중 7 개에서 가장 높은 F1 점수를 기록했습니다.
  • 기존 방법 (Eigen-sync, GAE, VGAE 등) 보다 노이즈와 분할 조건에서 훨씬 강력한 성능을 보였습니다.
  • 특히 대규모 그래프 (ogbn-arXiv) 에서 AFR 은 Eigen-sync 보다 10 포인트 이상 높은 성능을 보였습니다.
  • 예외: CiteSeer (VGAE 가 약간 우세) 와 PubMed (GCN-LE 가 우세) 는 그래프 구조가 매우 불연속적이거나 노드 특징과 엣지 존재가 강하게 상관관계가 있는 특수한 경우로, AFR 의 기하학적 접근이 약점을 보인 사례입니다.
• 프라이버시 방어 (Differential Privacy) 하의 성능:
  • $(\epsilon, \delta)$-가우시안 프라이버시 보호를 적용했을 때, AFR 은 $\epsilon=2$에서도 방어되지 않은 상태의 F1 점수 75% 를 유지했습니다.
  • 이는 다른 공격 방법들 (GAE, Eigen-sync 등) 이 더 급격히 성능이 저하되는 것과 대비됩니다. AFR 의 신뢰도 기반 설계가 노이즈가 섞인 패치를 적절히 배제하기 때문입니다.
• GNN 성능 분석 (Task 2 & 3):
  • 국소 분류: 이웃 반경 ($d$) 과 커버리지 ($p$) 가 성능에 가장 큰 영향을 미쳤으며, 스펙트럴 품질 ($k$) 보다는 정보의 '범위'가 중요함을 보였습니다.
  • 링크 예측: 분할 전략에 따라 최적 모델이 달랐으며, 분할된 경계를 넘어선 추론은 여전히 어려운 과제임을 확인했습니다.

4. 의의 및 결론 (Significance)

1. 현실적 벤치마크의 부재 해소: 기존 GNN 연구가 이상화된 중앙 집중식 데이터를 가정했던 한계를 지적하고, 분산 및 프라이버시 환경에서의 모델 강건성을 평가할 수 있는 LoGraB를 제시했습니다.
2. 프라이버시 위협의 명확화: 스펙트럴 임베딩이 단순한 표현이 아니라 수동적인 유출 채널이 될 수 있음을 이론과 실험으로 입증했습니다. 이는 연동 학습 및 분산 시스템에서 구조 정보 공유의 위험성을 경고합니다.
3. 강건한 복구 알고리즘: 불완전한 데이터에서도 작동하는 AFR 알고리즘을 제안하여, 공격자가 어떻게 그래프를 복구할 수 있는지 보여줌과 동시에, 방어 메커니즘 (DP 등) 의 효과를 정량적으로 평가할 수 있는 기준을 마련했습니다.
4. 향후 연구 방향: AFR 의 성능을 기반으로 한 그래프 레벨의 프라이버시 방어 전략 (예: 구조적 노이즈 추가, 임베딩 변환 등) 개발의 필요성을 제기했습니다.

요약하자면, 이 논문은 **"스펙트럴 임베딩을 통한 그래프 위상 유출은 이론적으로 가능하고 실제로도 발생 가능하다"**는 사실을 증명하며, 이를 측정하기 위한 LoGraB와 이를 복구하는 AFR을 통해 그래프 학습의 프라이버시와 보안에 대한 새로운 연구 패러다임을 제시합니다.