Source-linked AI summary
SSumM: Sparse Summarization of Massive Graphs
Kyuhan Lee, Hyeonsoo Jo, Jihoon Ko, Sungsu Lim, Kijung Shin
TL;DR
Massive graphs are difficult to analyze because existing summarization methods scale poorly and may produce dense outputs that do not reduce storage in bits. SSumM constrains summary size in bits and jointly merges nodes with sparsifying edges using a minimum-description-length cost, achieving more concise and accurate summaries while scaling to larger graphs. Experiments on 10 real-world graphs report up to 11.2× smaller summaries, up to 4.2× lower reconstruction error, and processing of graphs 26× larger than competitors.
Problem
Existing graph-summarization methods have limited scalability and often reduce node count without reducing, or even increasing, graph size in bits.
Source: §1 · pp. 1–2Method
SSumM constrains summary size in bits and balances node merging with edge sparsification using a minimum-description-length cost and a reduced candidate search space.
Source: §1 · p. 2, §3.1 · p. 4, §3.2 · p. 5Results
Across 10 real-world graphs, SSumM yields up to 11.2× smaller summaries with similar reconstruction error, up to 4.2× smaller reconstruction error at similar size, and processes 26× larger graphs.
Source: §4.2 · p. 8, §4.4 · p. 8, §6 · p. 9Takeaways & Limitations
SSumM provides a concise, accurate, and scalable alternative to state-of-the-art graph-summarization methods for large graphs.
Source: §1 · p. 2, §6 · p. 9Existing comparison methods cannot be applied to billion-scale graphs and were previously used only on graphs of about 3 million nodes and 34 million edges.
Source: §1 · pp. 1–2
Abstract
from arXiv · showhide
Given a graph G and the desired size k in bits, how can we summarize G within k bits, while minimizing the information loss? Large-scale graphs have become omnipresent, posing considerable computational challenges. Analyzing such large graphs can be fast and easy if they are compressed sufficiently to fit in main memory or even cache. Graph summarization, which yields a coarse-grained summary graph with merged nodes, stands out with several advantages among graph compression techniques. Thus, a number of algorithms have been developed for obtaining a concise summary graph with little information loss or equivalently small reconstruction error. However, the existing methods focus solely on reducing the number of nodes, and they often yield dense summary graphs, failing to achieve better compression rates. Moreover, due to their limited scalability, they can be applied only to moderate-size graphs. In this work, we propose SSumM, a scalable and effective graph-summarization algorithm that yields a sparse summary graph. SSumM not only merges nodes together but also sparsifies the summary graph, and the two strategies are carefully balanced based on the minimum description length principle. Compared with state-of-the-art competitors, SSumM is (a) Concise: yields up to 11.2X smaller summary graphs with similar reconstruction error, (b) Accurate: achieves up to 4.2X smaller reconstruction error with similarly concise outputs, and (c) Scalable: summarizes 26X larger graphs while exhibiting linear scalability. We validate these advantages through extensive experiments on 10 real-world graphs.
1 INTRODUCTION
SSumM addresses the scalability and compression limits of graph summarization by constraining output size in bits and jointly merging nodes with sparsifying edges. Across extensive experiments, it produces concise, accurate summaries and scales to substantially larger graphs than prior methods.
1 INTRODUCTION
- Graph summarization preserves essential graph structure while shrinking graphs, and its graph outputs remain usable with existing analysis and visualization tools.The summary graph supports applications such as adjacency queries, PageRank, and triangle-density analysis.Source: §1 · p. 1
- Existing graph-summarization methods have limited scalability and focus on reducing node count, often producing dense summaries whose bit size can exceed the original graph.Prior methods were applied to graphs of about 3 million nodes and 34 million edges, and their summaries can be larger in bits than the input.Source: §1 · pp. 1–2
- SSumM balances compactness and accuracy by combining node merging with edge sparsification while rapidly searching promising node pairs.This jointly optimizes the summary graph's bit size and reconstruction quality rather than optimizing node count alone.Source: §1 · p. 2
- SSumM introduces a graph-summarization formulation that constrains output size in bits rather than the number of supernodes, helping outputs fit target storage.The formulation targets a summary graph from which the original graph can be reconstructed with minimal information loss.Source: §1 · pp. 1–2
- SSumM handles up to 26× larger graphs with linear scalability and yields up to 11.2× smaller summary graphs with similar reconstruction errors.These advantages are validated against state-of-the-art competitors through experiments on 10 real-world graphs.Source: §1 · p. 2, Figure 2 · p. 2
2 PRELIMINARIES & PROBLEM DEFINITION
This section defines graph summarization as constructing a weighted summary graph within a bit budget so the original graph can be reconstructed with low error.
2.1 Notations and Concepts
- Graph summarization partitions input nodes into exhaustive, disjoint supernodes and represents connections between them with weighted superedges.Each superedge weight counts subedges between its incident supernodes.Source: §2.1 · p. 2
- The reconstructed graph connects every pair of subnodes whose supernodes share a summary superedge, assigning weights based on the density of possible subedges.The reconstruction need not equal the original graph.Source: §2.1 · pp. 2–3
2.2 Problem Definition
- Problem 1 minimizes reconstruction error while constraining the summary graph's size in bits to at most k.The formulation targets storage budgets directly rather than only limiting the number of supernodes.Source: §2.2 · p. 3
- Reconstruction error is measured from the difference between the original adjacency matrix A and the reconstructed weighted adjacency matrix Â.The section uses the ℓ_p reconstruction error.Source: §2.2 · p. 3
- The summary size counts superedge encodings and node-to-supernode membership, with superedge weights encoded up to the maximum weight.The stated size is |P|(2 log2 |S| + log2 ω_max) + |V| log2 |S|.Source: §2.2 · p. 3
3 PROPOSED METHOD
SSumM summarizes graphs by jointly controlling description size and reconstruction error, combining supernode merging with selective edge sparsification under an MDL-based cost. Its randomized greedy search reduces the candidate space to achieve linear scalability while producing a summary within the bit budget.
3.1 Cost Function in SSumM
- SSumM jointly merges supernodes and selectively creates superedges, allowing sparsification to complement node merging.For a fixed set of supernodes, a superedge is created only when it reduces the description cost.Source: §3 · p. 3, §3.1 · p. 4
- SSumM balances summary size and reconstruction error by minimizing a shared description-length cost measured in bits.The cost combines model cost, which measures summary-graph size, and data cost, which represents reconstruction error.Source: §3.1 · p. 4
3.2 Search Method in SSumM
- SSumM uses a randomized greedy search that repeatedly merges promising supernode pairs and sparsifies the summary until the bit budget or iteration limit is reached.The algorithm initializes with singleton supernodes, then alternates merging and sparsification phases.Source: §3.2 · p. 5
- Grouping supernodes within two hops reduces the search space because such merges tend to reduce cost more than merges between nodes three or more hops apart.This candidate-generation strategy supports rapid selection of promising pairs.Source: §3.2 · p. 5
3.3 Complexity Analysis
- SSumM has time complexity O(T·|E|), establishing linear scalability in the input graph size for T iterations.The merging and sparsification phase takes O(|E|) time under the paper’s complexity assumptions.Source: §3.3 · p. 6
4 EXPERIMENTS
Experiments compare SSumM with competing summarizers on real-world graphs for compactness, accuracy, speed, and scalability. SSumM consistently achieves compact, accurate outputs while scaling linearly and processing substantially larger graphs.
4.2 Q1. Compactness and Accuracy
- SSumM yielded up to 11.2× smaller summaries with similar or smaller ℓ1 reconstruction error, and up to 4.2× smaller error at similar or smaller sizes.These results held consistently across the considered datasets, with consistent conclusions under ℓ2 reconstruction error.Source: §4.2 · p. 8
- SSumM always respected the target size in bits, whereas competitors often produced summaries larger than the original graph.The competing methods focused on reducing node counts rather than summary-graph bit size.Source: §4.2 · p. 8
- On Ego-Facebook, SSumM produced a more concise summary than alternatives with similar ℓ1 reconstruction error of (5.9 ± 0.3) × 10^-3.The visual comparison emphasizes fewer edges at comparable reconstruction quality.Source: §4.2 · p. 8
4.3 Q2. Speed
- SSumM was up to 406.6× faster than competitors while producing better-quality summaries, and only SSumM scaled to the largest datasets.SAA-Gs could be faster but produced much lower-quality outputs; other competitors were slower, lower-quality, or exceeded 12 hours.Source: §4.3 · p. 8, Figure 5 · p. 8
4.4 Q3. Scalability (Fig. 6)
- SSumM scaled linearly with input-graph size and successfully processed datasets 26× larger than its best competitors, including graphs with about 0.8 billion edges.The scalability experiment varied sampled graph sizes from the Skitter and LiveJournal datasets.Source: §4.4 · p. 8, Figure 6 · p. 8
5 RELATED WORK
Prior graph-summarization methods primarily merge nodes under a fixed supernode budget, but their scalability and bit-level compactness remain limited. SSumM instead optimizes summary size in bits by combining node merging with edge sparsification.
5 RELATED WORK
- Existing methods target a fixed number of supernodes and often have limited scalability, with S2L reaching O(|V|^2) time when the supernode budget is O(|V|).S2L also requires substantial memory for high-dimensional clustering, while SAA-Gs has lower time complexity but remains memory-limited.Source: §5 · pp. 8–9
- Unlike prior methods that focus solely on reducing supernodes, SSumM minimizes summary-graph size in bits through both node merging and superedge sparsification.This design targets the practical requirement that summaries fit specified storage capacities.Source: §5 · p. 9
- Other graph-summarization variants produce unweighted summaries with edge corrections, differing from SSumM’s sparse weighted-summary formulation.The cited variants include methods aimed at compression and related objectives.Source: §5 · pp. 8–9
6 CONCLUSION
The paper formulates graph summarization with a bit-level target and proposes SSumM, which balances concise, accurate summaries through node merging and edge sparsification. Across 10 real-world graphs, it reports strong compactness, speed, and scalability advantages over competitors.
6 CONCLUSION
- SSumM combines node merging and edge sparsification while reducing candidate-search space to achieve concise, accurate, and scalable summaries.The algorithm is designed to balance compactness and reconstruction accuracy under a bit-level size constraint.Source: §6 · p. 9
- SSumM yields up to 11.2× more concise summaries with similar reconstruction error and produces better-quality outputs up to 406.6× faster than competitors.The conclusion reports these advantages from experiments on 10 real-world graphs.Source: §6 · p. 9
- SSumM summarizes graphs with about 0.8 billion edges while scaling linearly with input-graph size.The conclusion attributes the scalability claim to the theoretical and experimental results.Source: §6 · p. 9
A.1 Compactness and Accuracy (Fig. 7)
Using ℓ2 reconstruction error, SSumM consistently produced more concise and accurate summaries than its competitors. Increasing iterations reduced error until convergence, with 20 iterations sufficient in all tested settings.
A.1 Compactness and Accuracy (Fig. 7)
- SSumM consistently produced more concise and accurate summaries than competitors under ℓ2 reconstruction error.This matches the compactness and accuracy pattern observed with ℓ1 reconstruction error.Source: §A.1 · p. 10
- Twenty iterations were sufficient for convergence in all tested settings, although smaller target summaries required more iterations.The iteration study varied target sizes from 30% to 80% on Amazon-0601; reconstruction error decreased and eventually converged.Source: §A.2 · p. 10
B APPENDIX: PROOFS
The appendix proves Lemmas 3.1 and 3.2 using supporting lemmas about merging supernodes and cost inequalities. The arguments analyze cases involving supernode distances, optimal partitions, and coding costs.
B APPENDIX: PROOFS
- Lemmas B.1 and B.2 provide the supporting results used to prove Lemmas 3.1 and 3.2.The appendix explicitly states that these proofs are based on Lemmas B.1 and B.2.Source: B APPENDIX: PROOFS · pp. 10–11
- Merging two supernodes replaces A and B with A′ := A ∪ B in the partition S′ := S ∪ {A′} \ {A, B}.This merge operation is the setup for both supporting lemmas.Source: B APPENDIX: PROOFS · pp. 10–11
- The proof of Lemma B.1 handles four cases determined by whether pairs involving A or A′ and another supernode C belong to the optimal partition.The cases compare membership in P★(S) and P★(S′), using optimality and Shannon’s source coding theorem where applicable.Source: B APPENDIX: PROOFS · p. 10
- Cost bounds use Shannon’s source coding theorem and the edge-count relation |E_AA| + |E_BB| ≤ |E_A′A′|.These ingredients establish the displayed inequalities for the merged representation.Source: B APPENDIX: PROOFS · p. 11
- The appendix derives later inequalities from the optimality of P★(S) together with previously established bounds.This reasoning is used for Eqs. (27) and (28).Source: B APPENDIX: PROOFS · p. 11
B.1 Proof of Lemma 3.1
The proof of Lemma 3.1 analyzes merging two supernodes within two hops and establishes the corresponding cost inequality. It also shows the inequality is tight using a two-hop example.
B.1 Proof of Lemma 3.1
- For two supernodes A and B within 2 hops, merging them into A′ := A ∪ B and forming S′ establishes Eq. (18).The proof derives Eq. (18) from Eqs. (22) and (28).Source: §B.1 · p. 11
- The bound in Eq. (18) is tight because there exists a pair of supernodes within 2 hops attaining it.The proof identifies Figure 9 as such an example.Source: §B.1 · p. 11
B.2 Proof of Lemma 3.2
The proof of Lemma 3.2 considers merging supernodes at least three hops apart and derives the resulting equalities and inequality. Nonincident cross terms vanish in this distance regime.
B.2 Proof of Lemma 3.2
- When A and B are at least 3 hops apart, merging them into A′ := A ∪ B makes B_C(S) = 0 for every C outside {A, B}.This zero relation is one of the equalities used in the proof.Source: §B.2 · p. 11
- The zero cross-term relation, together with Eqs. (22) and (36), yields the next cost relation for the merged partition.The proof then uses Eqs. (27), (36), and (38) to continue the derivation.Source: §B.2 · p. 11
- Eqs. (39) and (17) imply Eq. (19), completing the proof of Lemma 3.2.The appendix states this final implication directly.Source: §B.2 · p. 11