Scalable Topology-Preserving Graph Coarsening with Graph Collapse

• URL: http://arxiv.org/abs/2601.22943v1
• Date: Fri, 30 Jan 2026 13:02:26 GMT
• Title: Scalable Topology-Preserving Graph Coarsening with Graph Collapse
• Authors: Xiang Wu, Rong-Hua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang,
• Abstract summary: We show that preserving topological features helps maintain the predictive performance of graph neural networks (GNNs) trained on the coarsened graph but suffers from exponential time complexity.<n>We propose Scalable Topology-Preserving Graph Coarsening (STPGC) by introducing the concepts of graph strong collapse and graph edge collapse extended from algebraic topology.<n>STPGC comprises three new algorithms, GStrongCollapse, GEdgeCollapse, and NeighborhoodConing based on these two concepts, which eliminate spatial edges while rigorously preserving topological features.
• Score: 40.30540248213416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph coarsening reduces the size of a graph while preserving certain properties. Most existing methods preserve either spectral or spatial characteristics. Recent research has shown that preserving topological features helps maintain the predictive performance of graph neural networks (GNNs) trained on the coarsened graph but suffers from exponential time complexity. To address these problems, we propose Scalable Topology-Preserving Graph Coarsening (STPGC) by introducing the concepts of graph strong collapse and graph edge collapse extended from algebraic topology. STPGC comprises three new algorithms, GStrongCollapse, GEdgeCollapse, and NeighborhoodConing based on these two concepts, which eliminate dominated nodes and edges while rigorously preserving topological features. We further prove that STPGC preserves the GNN receptive field and develop approximate algorithms to accelerate GNN training. Experiments on node classification with GNNs demonstrate the efficiency and effectiveness of STPGC.

Related papers

• Line Graph Vietoris-Rips Persistence Diagram for Topological Graph Representation Learning [3.6881508872690825]
  We introduce a novel edge filtration-based persistence diagram, named Topological Edge Diagram (TED)<n>TED is mathematically proven to preserve node embedding information as well as contain additional topological information.<n>We propose a neural network based algorithm, named Line Graph Vietoris-Rips (LGVR) Persistence Diagram, that extracts edge information by transforming a graph into its line graph.
  arXiv  Detail & Related papers  (2024-12-23T10:46:44Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. We propose Graph Sparse Training ( GST), which dynamically manipulates sparsity at the data level. GST produces a sparse graph with maximum topological integrity and no performance degradation.
  arXiv  Detail & Related papers  (2024-02-02T09:10:35Z)
• Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
  Graph Neural Networks (GNNs) have emerged as a notorious alternative to address learning problems dealing with non-Euclidean datasets. This work proposes a robust implementation of GNNs that explicitly accounts for the presence of perturbations in the observed topology.
  arXiv  Detail & Related papers  (2023-12-11T17:43:57Z)
• DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
  We propose DEGREE to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. We also design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods.
  arXiv  Detail & Related papers  (2023-05-22T10:29:52Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Topological Relational Learning on Graphs [2.4692806302088868]
  Graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. We propose a novel topological relational inference (TRI) which allows for integrating higher-order graph information to GNNs. We show that the new TRI-GNN outperforms all 14 state-of-the-art baselines on 6 out 7 graphs and exhibit higher robustness to perturbations.
  arXiv  Detail & Related papers  (2021-10-29T04:03:27Z)
• Geom-GCN: Geometric Graph Convolutional Networks [15.783571061254847]
  We propose a novel geometric aggregation scheme for graph neural networks to overcome the two weaknesses. The proposed aggregation scheme is permutation-invariant and consists of three modules, node embedding, structural neighborhood, and bi-level aggregation. We also present an implementation of the scheme in graph convolutional networks, termed Geom-GCN, to perform transductive learning on graphs.
  arXiv  Detail & Related papers  (2020-02-13T00:03:09Z)
• Gated Graph Recurrent Neural Networks [176.3960927323358]
  We introduce Graph Recurrent Neural Networks (GRNNs) as a general learning framework for graph processes. To address the problem of vanishing gradients, we put forward GRNNs with three different gating mechanisms: time, node and edge gates. The numerical results also show that GRNNs outperform GNNs and RNNs, highlighting the importance of taking both the temporal and graph structures of a graph process into account.
  arXiv  Detail & Related papers  (2020-02-03T22:35:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.