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.
Introduction
Large-scale graphs are ubiquitous, appearing in contexts ranging from social networks to protein-interaction maps. However, as these graphs scale to millions of nodes, standard analytical tasks like querying and visualization become computationally prohibitive. Graph summarization offers a solution by grouping nodes into "supernodes" to create a smaller, representative "supergraph." The primary objective is to minimize the loss of adjacency information, ensuring that the original graph can be reconstructed with minimal error.
Existing summarization methods often face a trade-off between speed and accuracy. High-quality methods like S2L are often too memory-intensive for massive graphs, while faster heuristic methods like SSumM may "over-sparsify" the graph, losing critical topological features such as triangle counts.
Methodology: The SpecSumm Algorithm
The core contribution of this work is the reformulation of the $l_2$-reconstruction error minimization problem into an equivalent integer trace maximization problem. This shift in perspective allows the use of spectral graph theory to find high-quality groupings efficiently.
SpecSumm operates in two distinct phases:
- Spectral Initialization: The algorithm computes the top $k$ eigenvectors of the adjacency matrix. These eigenvectors capture the most significant structural information in a low-dimensional space. By running $k$-means clustering on these eigenvectors, SpecSumm generates an initial assignment of nodes to supernodes.
- Greedy Reassignment: Because the spectral phase solves a "relaxed" version of the problem, the resulting clusters may not be perfectly optimal for the discrete integer constraints. SpecSumm includes an optional refinement phase that randomly samples nodes and greedily reassigns them if the move improves the overall objective function.
A key insight is the ability to decouple the number of eigenvectors used ($d$) from the number of supernodes ($k$). Using fewer eigenvectors for a larger summary can accelerate the process by up to 17x while maintaining high quality.
Experimental Evaluation
The authors evaluated SpecSumm across 11 diverse real-world datasets, ranging from small citation networks (Cora) to massive communication graphs like Wikitalk, which contains 2.3 million nodes.
The results demonstrate that SpecSumm consistently outperforms existing methods in both quality and efficiency. On small-to-medium graphs, SpecSumm achieved up to 22.5% higher quality than S2L and 76.1% higher quality than SSumM. In terms of speed, SpecSumm was 200x faster than S2L on the email-Enron dataset. Most notably, SpecSumm successfully summarized the 2.3-million-node Wikitalk graph in under three hours, a task where competing high-quality algorithms failed due to timeouts or memory crashes.
Conclusion
SpecSumm provides a mathematically grounded and highly scalable approach to graph summarization. By leveraging the spectral properties of the adjacency matrix, it bridges the gap between fast heuristics and computationally expensive optimization methods. Future work includes extending this framework to directed and weighted graphs, as well as optimizing the greedy reassignment phase for better parallelization.
Summary updated