Graph Summarization via Node Grouping: A Spectral Algorithm

Arpit Merchant, Michael Mathioudakis, Yanhao Wang

Large-scale graphs are everywhere, from social networks to protein-interaction maps. However, as these graphs grow into the millions of nodes, querying and visualizing them becomes computationally prohibitive. Graph summarization—grouping nodes into "supernodes" to create a smaller, representative "supergraph"—is a standard solution, but existing methods often force a choice between speed and accuracy.

In their paper, "Graph Summarization via Node Grouping: A Spectral Algorithm," Arpit Merchant and colleagues introduce SpecSumm, a novel algorithm that leverages the mathematical "DNA" of a graph to produce high-quality summaries at massive scales.

TL;DR

SpecSumm reformulates graph summarization as a trace maximization problem, allowing it to use the spectral properties (eigenvectors) of a graph's adjacency matrix to group nodes efficiently. The result is an algorithm that is up to 200x faster than previous state-of-the-art methods while producing summaries with significantly lower reconstruction error.

What Problem Does This Paper Address?

The goal of graph summarization is to create a $k$-summary: a smaller graph with $k$ supernodes that minimizes the loss of adjacency information. If you try to "reconstruct" the original graph from the summary, you want the result to be as close to the original as possible (measured by $l_2$-error).

The challenge is twofold:

  1. Scalability: High-quality methods like S2L use $k$-means on the full adjacency matrix, which is memory-intensive and slow for large graphs.
  2. Quality: Faster methods like SSumM often "over-sparsify" the graph, destroying important topological features like triangle counts.

SpecSumm aims to bridge this gap by providing a mathematically grounded approach that scales to millions of nodes without sacrificing structural integrity.

Methods

The authors' key contribution is a change in perspective. They prove that minimizing the $l_2$-reconstruction error is mathematically equivalent to an integer trace maximization problem.

To solve this, SpecSumm operates in two main phases:

  1. Spectral Initialization: Instead of working with the massive original adjacency matrix, the algorithm computes the top $k$ eigenvectors. These eigenvectors capture the most significant structural information of the graph in a low-dimensional space. The algorithm then runs $k$-means clustering on these eigenvectors to provide an initial grouping of nodes into supernodes.
  2. Greedy Reassignment: Since the spectral phase uses a "relaxed" (fractional) version of the problem, the resulting clusters might not be perfectly optimal for the discrete (integer) reality. SpecSumm includes an optional second phase that randomly samples nodes and greedily moves them to different supernodes if the move improves the overall objective function.

The authors also introduce Ocsa, an orthonormality-constrained steepest ascent algorithm, to demonstrate that the eigenvector solution represents at least a local maximum for the summarization objective.

Datasets

The researchers evaluated SpecSumm on 11 diverse real-world datasets:

  • Small/Medium: SBM (synthetic), Cora (citation), PPI (protein-protein), ca-GrQc (collaboration), LastFM-Asia (social), BlogCatalog (social), Facebook (web), and email-Enron (communication).
  • Large-Scale: Amazon (product co-purchasing, ~334k nodes), Youtube (social, ~1.1M nodes), and Wikitalk (communication, ~2.3M nodes).

Key Insights and Ideas

  • The Spectral Connection: The most striking insight is that the "best" way to group nodes to preserve the graph's structure is deeply tied to the largest-magnitude eigenvectors of the adjacency matrix. This provides a rigorous theoretical foundation for using spectral clustering in summarization.
  • Decoupling $d$ and $k$: The authors found they could decouple the number of eigenvectors used ($d$) from the number of supernodes ($k$). Using a smaller number of eigenvectors for a larger summary can speed up the process by up to 17x while maintaining comparable quality.
  • Preserving Topology: Unlike compression-based methods that focus on bit-reduction, SpecSumm's objective naturally preserves higher-order structures. For example, it is significantly more accurate at estimating the number of triangles in the original graph compared to SSumM.

Key Results

  • Higher Quality: SpecSumm produced summaries with up to 22.5% higher quality than S2L and 76.1% higher quality than SSumM on small-to-medium graphs.
  • Massive Speedups: On the email-Enron dataset, SpecSumm was 200x faster than S2L.
  • Scalability: SpecSumm successfully summarized the Wikitalk graph (2.3 million nodes and 5 million edges) into 5,000 supernodes in less than 3 hours—a task that caused competing high-quality algorithms to crash or time out.

Limitations and Future Work

While SpecSumm is highly effective, the authors note a few areas for improvement:

  • Reassignment Bottleneck: The greedy reassignment phase (SpecSumm-R) provides the highest quality but is significantly slower than the spectral phase because it is difficult to parallelize.
  • Theoretical Conjecture: The authors conjecture that eigenvectors represent the global optimum for the relaxed problem. While they provide strong empirical evidence and prove they are a local optimum, a formal proof for the global case remains an open challenge.
  • Graph Types: The current work focuses on unweighted, undirected graphs. Extending this spectral framework to directed or weighted graphs is a logical next step.

Summary updated

Abstract

Graph summarization via node grouping is a popular method to build concise graph representations by grouping nodes from the original graph into supernodes and encoding edges into superedges such that the loss of adjacency information is minimized. Such summaries have immense applications in large-scale graph analytics due to their small size and high query processing efficiency. In this paper, we reformulate the loss minimization problem for summarization into an equivalent integer maximization problem. By initially allowing relaxed (fractional) solutions for integer maximization, we analytically expose the underlying connections to the spectral properties of the adjacency matrix. Consequently, we design an algorithm called SpecSumm that consists of two phases. In the first phase, motivated by spectral graph theory, we apply k-means clustering on the k largest (in magnitude) eigenvectors of the adjacency matrix to assign nodes to supernodes. In the second phase, we propose a greedy heuristic that updates the initial assignment to further improve summary quality. Finally, via extensive experiments on 11 datasets, we show that SpecSumm efficiently produces high-quality summaries compared to state-of-the-art summarization algorithms and scales to graphs with millions of nodes.
BibTeX
@inproceedings{merchant2023graph,
  author = {Arpit Merchant and Michael Mathioudakis and Yanhao Wang},
  title = {{Graph Summarization via Node Grouping: A Spectral Algorithm}},
  booktitle = {WSDM},
  year = {2023},
  doi = {10.1145/3539597.3570441},
}

Loading related content...

Figure