CoRe-GNN: 축약된 그래프에서의 다수준 메시지 패싱
CoRe-GNN: Multilevel Message passing on Coarsened graphs
한국어 초록
대규모 그래프에서 그래프 신경망(GNN)을 학습(training)시키는 것은 여러 층(layer)에 걸쳐 모든 노드(node) 표현을 저장해야 하는 메모리 비용으로 인해 어려움을 겪습니다. 본 논문에서는 기존의 여러 확장 가능한 접근법들이 GNN 전파 행렬의 구조화된 변형으로 표현될 수 있음을 보이고, 각 방식의 한계를 드러내는 통합된 관점을 제시합니다. 구체적으로, 그래프 축약(graph coarsening)은 전파 행렬을 스펙트럼 보장을 가능하게 하는 저계수 근사(low-rank approximation)로 대체하지만 클러스터링된 노드들에 획일적인 표현을 할당하며, Cluster-GCN은 효율적인 배칭을 가능하게 하지만 장거리 정보를 차단하는 클러스터 내 연결로 전파 행렬을 제한합니다. 이는 그래프를 노드 그룹으로 분해하는 *동일한* 방식에서 나타나는 상호보완적인 한계점들입니다. 두 접근법의 장점을 모두 취하기 위해, 본 연구에서는 각 층에서 두 전파를 병렬로 수행하는 **CoRe-GNN**을 제안합니다. 즉, 장거리 구조를 포착하는 축약된 클러스터 간 항과 노드별 식별력을 보존하는 국소적 클러스터 내 항을 함께 사용합니다. 본 논문은 CoRe-GNN이 그래프 축약과 유사한 근사 보장을 이어받음을 증명하고, 수백만 개의 노드를 가진 그래프로 확장 가능한 자연스러운 클러스터 기반 *배칭 기법(batching scheme)*을 도입합니다. 동질적(homophilic), 이질적(heterophilic), 대규모 및 장거리 그래프를 아우르는 노드 분류(classification) 벤치마크에서 CoRe-GNN은 그래프 축약 및 Cluster-GCN 베이스라인 모두를 능가합니다. 특히 CoRe-GNN은 배칭을 통해 메모리 효율성을 유지하면서도 *장거리(long-range)* 태스크에서 경쟁력 있는 정확도를 달성합니다.
원문 초록
Training Graph Neural Networks on large graphs is challenged by the memory cost of storing all node representations across layers. We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix, providing a unified perspective that exposes their respective limitations. In particular, graph coarsening replaces it by a low-rank approximation that enables spectral guarantees but assigns uniform representations to clustered nodes, while Cluster-GCN restricts the propagation matrix to intra-cluster connections that allow efficient batching but sever long-range information. These are complementary failures of the \emph{same} decomposition of the graph into groups of nodes. To obtain the best of both worlds, we propose \textbf{CoRe-GNN}, which performs both propagations in parallel at each layer: a coarsened inter-cluster term capturing long-range structure, and a local intra-cluster term preserving per-node discriminability. We prove that CoRe-GNN inherits analogous approximation guarantees to those of graph coarsening, and introduce a natural cluster-based \emph{batching scheme} that scales to graphs with millions of nodes. On node classification benchmarks spanning homophilic, heterophilic, large-scale, and long-range graphs, CoRe-GNN outperforms both graph coarsening and Cluster-GCN baselines. Notably, CoRe-GNN reaches competitive accuracy on \emph{long-range} tasks, while remaining memory-efficient through batching.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2608.02128v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
공통 태그로 연결된 공개 논문이 아직 없습니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.