Graph Summarization via Node Grouping: A Spectral Algorithm

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


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.
Original languageEnglish
Title of host publicationProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining
PublisherAssociation for Computing Machinery
Publication dateFeb 2023
ISBN (Electronic)978-1-4503-9407-9
Publication statusPublished - Feb 2023
MoE publication typeA4 Article in conference proceedings
EventACM International Conference On Web Search And Data Mining - , Singapore
Duration: 27 Feb 20233 Mar 2023
Conference number: 16

Fields of Science

  • 113 Computer and information sciences

Cite this