Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

기술 요약: 확장 가능한 위상 보존 그래프 코어닝 (STPGC)

문제 정의
그래프 코어닝(Graph coarsening)은 효율적인 분석을 위해, 특히 그래프 신경망(GNN)을 위한 특정 속성을 보존하면서 그래프의 크기를 줄이는 것을 목표로 한다. 기존 방법들은 주로 스펙트럼 특성(라플라시안의 고유값/고유벡터)이나 공간적 특성(국소적 연결성, 영향력 확산)을 보존하는 데 집중한다. 최근 연구에 따르면 위상적 특징(연결성, 링, 고차 보이드)을 보존하는 것이 GNN 성능 유지에 매우 중요하다는 점이 밝혀졌으나, 현재의 위상 보존 접근 방식들은 심각한 확장성 문제를 겪고 있다. 구체적으로, 최첨단 방법론인 그래프 기본 붕괴(Graph Elementary Collapse, GEC)는 축소 가능한 구조를 식별하기 위해 클리크 열거(clique enumeration)에 의존하며, 이는 $O(3^{n/3})$의 지수적 최악 시간 복잡도를 초라한다. 이는 대규모 그래프에 대해 GEC를 비실용적으로 만든다. 더욱이, GEC가 사용하는 그래프 분할 방식은 전역적 위상 특징을 저해하며, 이는 재구성 과정에서 복구될 수 없다.

방법론
저자들은 대수적 위상수학의 개념인 **강한 붕괴(strong collapse)**와 **에지 붕계(edge collapse)**를 그래프 영역으로 확장한 확장 가능한 위상 보존 그래프 코어닝(STPGC) 프레임워크를 제안한다. GEC와 달리, STPGC는 비용이 많이 드는 클리크 열거를 피하기 위해 이웃 포함 관계(neighborhood inclusion)를 통해 축소 가능한 구조를 식별한다.

이 프레임워크는 세 가지 핵심 알고리즘으로 구성된다:

1. GStrongCollapse: "지배되는 노드(dominated nodes)"를 반복적으로 식별한다. 노드 $u$의 폐쇄 이웃(closed neighborhood)이 $v$의 폐쇄 이웃의 부분집합($N[u] \subseteq N[v]$)일 때, 노드 $u$는 $v$에 의해 지배된다고 한다. 이 알고리즘은 지배되는 노드와 그 에지들을 제거하고, 이를 슈퍼노드로 병합한다.
2. GEdgeCollapse: "지배되는 에지(dominated edges)"를 반복적으로 식별한다. 에지 $(x, y)$가 노드 $v$ ($v \notin \{x, y\}$)에 의해 지배된다는 것은, 에지의 폐쇄 이웃이 $v$의 폐쇄 이웃의 부분집합($N[x, y] \subseteq N[v]$)임을 의미한다. 이러한 에지들을 제거하면 구조적 교착 상태(structural deadlocks)가 깨지며, 새로운 지배되는 노드들이 드러난다.
3. NeighborhoodConing: 초기 단계에서 지배되는 노드나 에지가 존재하지 않는 시나리오를 처리하기 위해, 이 알고리즘은 타겟 노드 $u$의 이웃들 사이에 "지배되는 에지"를 삽입하여 새로운 지배되는 노드를 생성한다. "코닝(coning)"이라고 명명된 이 과정은 호모토피 동치(homotopy equivalence)를 유지하면서 추가적인 축소를 가능하게 한다.

이론적 보증
본 논문은 이러한 연산들의 조합이 원래 그래프와 코어닝된 그래프 사이의 호모토피 동치를 보존함을 증명한다. 이는 연결 성분, 링, 보이드 및 베티 수(Betti numbers)와 같은 위상 불변량이 유지됨을 보장한다. 또한, 저자들은 이러한 연산들이 **GNN 수용 영역(receptive field)**을 보존함을 입증한다. 구체적으로:

• GStrongCollapse와 NeighborhoodConing은 임의의 노드 쌍 사이의 최단 경로 거리를 증가시키지 않는다.
• GEdgeCollapse는 최단 경로 거리를 최대 1만큼 증가시킨다.
  이러한 최단 경로 거리의 보존은 GNN의 정보 집계 범위가 크게 유지되도록 보장한다.

정확한 위상 보존이 임의의 코어닝 비율을 달성하지 못할 수 있다는 한계(그래프를 최소 코어로 축소하는 것이 NP-난해인 문제이기 때문)를 해결하기 위해, 저자들은 ApproximateCoarsening을 도입한다. 이 2단계 전략은 먼저 정확한 코어닝을 수행한 후, 이웃 포함 조건에서 최대 $r$개의 노드가 결여될 수 있도록 허용하는 **$r$-완화 강한 붕괴($r$-relaxed strong collapse)**를 적용하여 유연한 축소 비율을 가능하게 한다.

주요 기여

1. 새로운 개념 및 알고리즘: 대수적 위상수학에서 확장된 그래프 강한 붕계 및 그래프 에지 붕계 개념을 도입하였으며, 지수적 복잡도 없이 지배되는 구조를 제거하는 세 가지 확장 가능한 알고리즘(GStrongCollapse, GEdgeCollapse, NeighborhoodConing)을 구현하였다.
2. GNN 학습에의 적용: STPGC가 GNN 수용 영역을 보존한다는 증명과 함께, 위상적 충실도와 확장성 사이의 균형을 맞추기 위한 근사 코어닝 전략을 제시하였다.
3. 최첨단 성능: STPGC가 노드 분류 작업에서 기존 베이스라인 모델들을 능가함을 보여주는 실증적 근거를 제시하였다.

실험 결과
실험은 노드 분류를 위한 5개의 레이블된 벤치마크(Cora, Citeseer, DBLP, ogbn-arXiv, ogbn-products)와 확장성 평가를 위한 4개의 대규모 레이블 없는 데이터셋을 대상으로 수행되었다.

• 정확도: STPGC는 스펙트럼 및 공간적 방법을 포함한 9개의 베이스라인을 일관되게 능가했다. 5개 데이터셋에 대해 GEC 대비 평균 1.73%의 정확도 향상을 달성했다. 결과는 위상 보존 방법(STPTG, GEC)이 비위상 보존 베이스라인보다 일반적으로 더 우수한 성능을 보임을 강조한다.
• 효율성: STPGC는 모든 베이스라인에 비해 우수한 실행 시간 및 메모리 효율성을 보여주었다. 특히, GEC 대비 최대 37배의 실행 시간 단축을 달계했다. DBLP 데이터셋의 코어닝 비율 0.1에서 STPGC는 GEC보다 15배 이상 빨랐다.
• 위상 보존: 베티 수 분석 결과, STPGC는 정확한 코어닝 단계가 종료될 때까지 위상적 특징의 수를 엄격하게 유지하는 반면, 그래프 분할이나 전역적 보존 결여로 인해 다른 방법들(GEC 포함)은 프로세스 초기 단계에서 위상적 특징을 상실함을 보여주었다.
• 확장성: 대규모 데이터셋(LiveJournal, Youtube, cit-Patent, Flixster)에서 STPGC는 실행 시간 측면에서 거의 선형적인 확장성을 보였으며, 메모리 증가가 단조적임을 입증하여 대규모 그래프에 대한 적용 가능성을 검증했다.

의의 및 주장
본 논문은 STPGC가 계산 복잡도로 인해 제한되었던, 위상적 특징을 엄격하게 보존하면서도 확장 가능한 그래프 코어닝 솔루션을 제공한다고 주장한다. 호모토피 동치를 보장하고 GNN 수용 영역을 보존함으로써, STPGC는 원래 데이터에 대한 성능 저하 없이 훨씬 작은 그래프에서 GNN을 학습할 수 있게 한다. 저자들은 STPGC를 다운스트림 GNN 아키텍처와 독립적인 "플러그 앤 플레이(plug-and-play)" 전처리 모듈로 포지셔닝한다.

이 연구는 대규모 그래프의 GNN 학습에 필요한 계산 자원과 에너지 소비를 줄임으로써 "그린 AI(Green AI)"에 기여한다. 저자들은 휴리스틱한 특징 평균화 및 슈퍼노드를 위한 다수결 레이블 집계 방식이 특정 작업에서는 최적이 아닐 수 있다는 한계를 인정하며, 향후 약물 발견을 위한 생물학적 데이터 압축과 같은 더 넓은 영역에 이 방법을 적용하는 것을 향후 과제로 제시한다.