Graph reduction by local variation

Andreas Loukas

Abstract: Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation that restricted approximation carries strong spectral and cut guarantees, and that it implies approximation results for unsupervised learning problems relying on spectral embeddings. The paper then focuses on coarsening—the most common type of graph reduction. Sufficient conditions are derived for a small graph to approximate a larger one in the sense of restricted similarity. These findings give rise to nearly-linear algorithms that, compared to both standard and advanced graph reduction methods, find coarse graphs of improved quality, often by a large margin, without sacrificing speed.

Introduction

As datasets grow in complexity, graphs representing social networks, physical simulations, and biological systems become too large for efficient processing. Researchers typically simplify these structures using two strategies: sparsification (removing edges) and coarsening (merging vertices). While graph sparsification has a mature theoretical foundation—specifically spectral sparsifiers that preserve eigenvalues—graph coarsening has historically relied on intuition-based heuristics.

This research bridges the gap between heuristic practice and theoretical rigor by introducing a framework for graph coarsening based on "restricted spectral approximation." By focusing on preserving the principal eigenspace, the proposed "local variation" algorithms simplify massive graphs in nearly-linear time while maintaining global structure significantly better than existing methods.

Methodology

The core of this approach is restricted spectral approximation. Rather than attempting to preserve the entire graph spectrum—an impossible task when reducing the vertex count—the method targets the principal eigenspace that captures global community structure.

Key components of the framework include:

  • Laplacian Consistent Coarsening: Ensures the reduced graph remains a valid combinatorial Laplacian with non-negative edge weights.
  • Local Variation Algorithms: Greedy algorithms that minimize a "variation cost," measuring how much a graph signal fluctuates within contraction sets (groups of merged vertices).
  • Decoupling: A mathematical insight that breaks down global error bounds into local, independent costs, allowing for fast, local merging decisions without sacrificing global approximation goals.

This coarsening process is illustrated in the toy example below, where sets of vertices in the original graph $G$ are contracted into single vertices in the coarse graph $G_c$:

The original graph $G$ with contraction sets highlighted in grey.

Experimental Setup and Results

The algorithms were evaluated on several representative graphs, including the Yeast protein-protein network, the Airfoil finite-element mesh, the Minnesota road network, and the Bunny point cloud mesh. Synthetic 10-regular graphs were also used to test computational scaling.

Key Results

  • Superior Quality: The local variation methods outperformed standard techniques like heavy-edge matching and advanced methods like Kron reduction in nearly every instance.
  • Massive Error Reduction: For a 70% reduction in graph size, the new methods achieved an average of 2.6x smaller eigenvalue error than the next best method. When excluding Kron reduction, the improvement reached 3.9x.
  • Efficiency: The algorithms scale nearly-linearly with the number of edges, making them practical for large-scale applications.
  • Preserved Partitioning: The framework ensures that if the original graph contains a "good cut" (distinct communities), the coarsened graph will reliably preserve that structure.

Discussion and Insights

The research suggests that coarsening acts as a form of low-pass filtering, smoothing out local high-frequency details while preserving low-frequency global trends. A critical insight is that every level of a multi-level reduction scheme should strive to approximate the original graph directly, rather than the previous level, to prevent error accumulation. By targeting the principal eigenspace, the method ensures that unsupervised learning tasks like spectral clustering and graph partitioning remain accurate even on significantly reduced graphs.

Limitations and Future Work

Despite its strengths, finding the absolute optimal set of vertices to merge remains an NP-hard problem; the proposed algorithm is a high-quality greedy approximation. Future work may focus on pre-determining the exact reduction possible for a specific target error $\epsilon$ and further refining the relationship between spectral approximation and graph conductance to provide even tighter cut guarantees.

Summary updated

Abstract

Can one reduce the size of a graph without significantly altering its basic properties? The graph reduction problem is hereby approached from the perspective of restricted spectral approximation, a modification of the spectral similarity measure used for graph sparsification. This choice is motivated by the observation that restricted approximation carries strong spectral and cut guarantees, and that it implies approximation results for unsupervised learning problems relying on spectral embeddings. The paper then focuses on coarsening---the most common type of graph reduction. Sufficient conditions are derived for a small graph to approximate a larger one in the sense of restricted similarity. These findings give rise to nearly-linear algorithms that, compared to both standard and advanced graph reduction methods, find coarse graphs of improved quality, often by a large margin, without sacrificing speed.
BibTeX
@article{loukas2019graph,
  author = {Andreas Loukas},
  title = {{Graph reduction by local variation}},
  journal = {J. Mach. Learn. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=Ds_UrT0SCZj},
}
Figure