🤖 machine learning

Scalable Topology-Preserving Graph Coarsening: Concepts and Algorithms

This paper proposes Scalable Topology-Preserving Graph Coarsening (STPGC), a framework utilizing graph strong and edge collapse concepts to efficiently reduce graph size while rigorously preserving topological features and GNN receptive fields, thereby overcoming the exponential time complexity of existing topology-preserving methods.

Original authors: Xiang Wu, Rong-Hua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xiang Wu, Rong-Hua Li, Xunkai Li, Kangfei Zhao, Hongchao Qin, Guoren Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, intricate map of a city with millions of streets and intersections. You want to study traffic patterns, but the map is so huge that your computer can't handle it. You need a smaller, simplified version of the map that still tells you the same story: where the loops are, where the dead ends are, and how neighborhoods connect.

This is the problem of Graph Coarsening. It's like taking a high-resolution photo and shrinking it down. The challenge is: if you shrink it too much or the wrong way, you might lose the "shape" of the city. You might accidentally turn a roundabout into a straight line or merge two distinct neighborhoods into one confusing blob.

The paper introduces a new method called STPGC (Scalable Topology-Preserving Graph Coarsening) to solve this. Here is how it works, using simple analogies:

The Problem with Old Methods

Previous methods tried to shrink the map by either:

Looking at the "vibe" (Spectral methods): They tried to keep the mathematical "sound" of the city the same, but often ignored the actual street layout.
Looking at the "shape" (Topology methods): One existing method tried to keep the exact shape (like rings and loops) by checking every possible combination of streets. But this was like trying to count every grain of sand on a beach to find a specific shell—it took so long (exponential time) that it was impossible for big cities.

The New Solution: STPGC

The authors created a smarter, faster way to shrink the map while keeping its essential "shape" (topology). They borrowed ideas from a branch of math called algebraic topology and turned them into three simple rules for shrinking the graph:

1. The "Shadow" Rule (Graph Strong Collapse)

Imagine a small side street that is completely overshadowed by a bigger main street. If every house on the side street is also accessible from the main street, the side street is redundant.

The Analogy: If you have a small room (Node A) and a big room (Node B), and every door leading out of the small room also leads out of the big room, the small room is "dominated." You can delete the small room and its doors without changing the overall layout of the building.
STPGC does this: It finds these "shadow" nodes and removes them, merging them into their bigger neighbors.

2. The "Redundant Bridge" Rule (Graph Edge Collapse)

Sometimes, a whole street (edge) is unnecessary because a nearby building (node) already connects to everything that street connects to.

The Analogy: Imagine a bridge connecting two islands. If there is a giant lighthouse on one island that already has a path to every destination the bridge connects to, the bridge is "dominated." You can remove the bridge, and the islands are still just as connected.
STPGC does this: It finds these redundant bridges and cuts them, simplifying the map without breaking the loops or connections.

3. The "Magic Connector" Rule (Neighborhood Coning)

Sometimes, the map is tricky. There are no obvious "shadow" nodes or "redundant" bridges to remove. The map looks stuck.

The Analogy: Imagine a small cul-de-sac with no exits. You can't remove it yet. But, if you magically built a new road connecting the cul-de-sac to a nearby main street, suddenly that cul-de-sac becomes a "shadow" node that can be removed.
STPGC does this: It temporarily adds a few "magic" connections (edges) to create new opportunities for removal. Once the new connections make a node redundant, it removes the node. This allows the system to keep shrinking the map even when it seems impossible.

Why This Matters for AI (GNNs)

Graph Neural Networks (GNNs) are AI models that learn by looking at a node's neighbors (like a person learning by talking to their friends).

The Receptive Field: If you shrink the map, you don't want to change how far a node can "see" its friends.
The Guarantee: The paper proves that STPGC keeps the "distance" between friends the same. Even though the map is smaller, the AI still sees the same world. It doesn't lose the "rings" (loops) or the "voids" (empty spaces) that are crucial for understanding the data.

The Results

Speed: The old "shape-preserving" method was so slow it couldn't handle big data. STPGC is 37 times faster on some datasets.
Accuracy: When they tested it on classifying nodes (like sorting people into groups), STPGC performed better than all other methods, including the old slow one.
Scalability: It works on massive graphs (like social networks with millions of users) without crashing the computer's memory.

In Summary

STPGC is like a master editor for a massive story. Instead of randomly cutting pages (which ruins the plot), it uses smart rules to remove only the redundant sentences and paragraphs. It ensures the story's structure (the plot twists, the character relationships, the loops) remains exactly the same, but the book becomes much thinner and easier to read. This allows AI to learn from huge datasets much faster without losing the important details.

Technical Summary: Scalable Topology-Preserving Graph Coarsening (STPGC)

Problem Statement
Graph coarsening aims to reduce graph size while preserving specific properties to facilitate efficient analysis, particularly for Graph Neural Networks (GNNs). Existing methods primarily focus on preserving spectral properties (eigenvalues/eigenvectors of the Laplacian) or spatial characteristics (local connectivity, influence diffusion). While recent research indicates that preserving topological features (connectivity, rings, higher-order voids) is crucial for maintaining GNN performance, current topology-preserving approaches suffer from severe scalability issues. Specifically, the state-of-the-art method, Graph Elementary Collapse (GEC), relies on clique enumeration to identify reducible structures, resulting in an exponential worst-case time complexity of $O(3^{n/3})$ . This makes GEC impractical for large-scale graphs. Furthermore, GEC's workaround of partitioning graphs disrupts global topological features, which cannot be recovered during reconstruction.

Methodology
The authors propose Scalable Topology-Preserving Graph Coarsening (STPGC), a framework that extends concepts from algebraic topology—specifically strong collapse and edge collapse—to the graph domain. Unlike GEC, STPGC avoids costly clique enumeration by identifying reducible structures through neighborhood inclusion.

The framework consists of three core algorithms:

GStrongCollapse: Iteratively identifies "dominated nodes." A node $u$ is dominated by $v$ if its closed neighborhood is a subset of $v$ 's closed neighborhood ( $N[u] \subseteq N[v]$ ). The algorithm removes dominated nodes and their edges, merging them into supernodes.
GEdgeCollapse: Iteratively identifies "dominated edges." An edge $(x, y)$ is dominated by a node $v$ (where $v \notin \{x, y\}$ ) if the closed neighborhood of the edge is a subset of $v$ 's closed neighborhood ( $N[x, y] \subseteq N[v]$ ). Removing these edges breaks structural deadlocks, exposing new dominated nodes.
NeighborhoodConing: To handle scenarios where no dominated nodes or edges exist initially, this algorithm inserts "dominated edges" between neighbors of a target node $u$ to create a new dominated node. This process, formalized as "coning," allows for further reduction while maintaining homotopy equivalence.

Theoretical Guarantees
The paper proves that the combination of these operations preserves homotopy equivalence between the original graph and the coarsened graph. This ensures that topological invariants, such as connected components, rings, voids, and Betti numbers, are retained. Furthermore, the authors demonstrate that these operations preserve the GNN receptive field. Specifically:

GStrongCollapse and NeighborhoodConing do not increase the shortest path distance between any pair of nodes.
GEdgeCollapse increases the shortest path distance by at most 1.
This preservation of shortest path distances ensures that the information aggregation scope for GNNs remains largely intact.

To address the limitation that exact topological preservation may not achieve arbitrary coarsening ratios (due to the NP-hard nature of reducing a graph to its minimal core), the authors introduce ApproximateCoarsening. This two-stage strategy first performs exact coarsening, then applies $r$ -relaxed strong collapse, which allows up to $r$ nodes in the neighborhood inclusion condition to be absent, enabling flexible reduction ratios.

Key Contributions

Novel Concepts and Algorithms: The introduction of graph strong collapse and graph edge collapse extended from algebraic topology, implemented via three scalable algorithms (GStrongCollapse, GEdgeCollapse, NeighborhoodConing) that eliminate dominated structures without exponential complexity.
Application to GNN Training: A proof that STPGC preserves the GNN receptive field, coupled with an approximate coarsening strategy to balance topological fidelity with scalability for training acceleration.
State-of-the-Art Performance: Empirical evidence showing STPGC outperforms existing baselines in node classification tasks while offering significant runtime improvements.

Experimental Results
Experiments were conducted on five labeled benchmarks (Cora, Citeseer, DBLP, ogbn-arXiv, ogbn-products) for node classification and four large unlabeled datasets for scalability evaluation.

Accuracy: STPGC consistently outperformed nine baselines, including spectral and spatial methods. It achieved an average accuracy improvement of 1.73% over GEC across five datasets. The results highlight that topology-preserving methods (STPGC and GEC) generally outperform non-topology-preserving baselines.
Efficiency: STPGC demonstrated superior runtime and memory efficiency compared to all baselines. Notably, it achieved up to a 37x runtime speedup over GEC. On the DBLP dataset at a coarsening ratio of 0.1, STPGC was over 15x faster than GEC.
Topological Preservation: Analysis of Betti numbers showed that STPGC strictly maintains the number of topological features until the exact coarsening phase terminates, whereas other methods (including GEC) lose topological features early in the process due to graph partitioning or lack of global preservation.
Scalability: On large-scale datasets (LiveJournal, Youtube, cit-Patent, Flixster), STPGC exhibited near-linear scalability in runtime and monotonic memory growth, validating its applicability to massive graphs.

Significance and Claims
The paper claims that STPGC provides a theoretically grounded, scalable solution for graph coarsening that rigorously preserves topological features, a capability previously limited by computational complexity. By ensuring homotopy equivalence and preserving the GNN receptive field, STPGC enables the training of GNNs on significantly smaller graphs without sacrificing performance on the original data. The authors position STPGC as a "plug-and-play" preprocessing module that is independent of downstream GNN architectures.

The work contributes to "Green AI" by reducing the computational resources and energy consumption required for training GNNs on large-scale graphs. The authors acknowledge limitations, such as the use of heuristic feature averaging and majority-vote label aggregation for supernodes, which may be suboptimal for certain tasks, and suggest future work in applying these methods to broader domains like biological data compression for drug discovery.