Source-linked AI summary
Graph Summarization Methods and Applications: A Survey
Yike Liu, Tara Safavi, Abhilash Dighe, Danai Koutra
TL;DR
Graph summarization addresses the need to condense massive, complex, and noisy graph data for analysis as human pattern-recognition capacity has not kept pace with data growth. This survey organizes graph summarization methods by input graph type and core technique, reviews applications, and identifies open problems. It reports efficiency gains in query handling and summarizes a field that remains relatively new and underexplored.
Problem
Growing, complex, noisy, and dynamic graph data require summaries that support efficient analysis while preserving application-relevant information.
Method
The survey develops a taxonomy by input graph type and core summarization technique, explains algorithmic ideas, reviews applications, and connects methods with related fields.
Results
Graph summarization improves query handling across settings, including up to 10× query speedup, up to 92% compression with up to 70% runtime reduction, and up to 12500× faster summary construction than GraSS.
Takeaways & Limitations
The survey provides a structured view of graph summarization methods, applications, and open problems for researchers and practitioners.
Takeaways & Limitations
The field remains relatively new and underexplored, with no existing work covering temporal graphs with side information and unresolved needs for lossless compression with general-purpose queries.
Abstract
from arXiv · showhide
While advances in computing resources have made processing enormous amounts of data possible, human ability to identify patterns in such data has not scaled accordingly. Efficient computational methods for condensing and simplifying data are thus becoming vital for extracting actionable insights. In particular, while data summarization techniques have been studied extensively, only recently has summarizing interconnected data, or graphs, become popular. This survey is a structured, comprehensive overview of the state-of-the-art methods for summarizing graph data. We first broach the motivation behind, and the challenges of, graph summarization. We then categorize summarization approaches by the type of graphs taken as input and further organize each category by core methodology. Finally, we discuss applications of summarization on real-world graphs and conclude by describing some open problems in the field.
1. INTRODUCTION
Graph summarization condenses massive, complex, and often noisy graph data to support efficient analysis, visualization, and pattern discovery. This survey organizes methods by graph input type and core methodology, reviews applications, and identifies open research problems.
- Motivation: Graph summarization reduces data volume and storage while enabling smaller graphs to be loaded, queried, analyzed, and visualized more efficiently.Summaries can reduce I/O and communication volume and help avoid the “hairball” visualization problem.
- Motivation: Summarization filters noise and can reveal patterns hidden by erroneous, missing, or unobserved links and labels.Real graph data may be large-scale and noisy, increasing processing workload and obscuring important information.
- Applications: Graph summaries support applications including clustering, classification, community detection, outlier detection, pattern set mining, and infection-source identification.The survey also connects summarization with interactive analysis and visualization of datasets too large to load into memory.
- Challenges: A graph summary is application-dependent: it may preserve structural patterns, focus on entities, preserve query answers, or maintain graph-property distributions.Evaluation criteria vary by application, including query accuracy, community preservation, reconstruction error, compression, and visualization support.
- Challenges: Graph summarization must reduce input size while itself scaling to large graphs, handling complex heterogeneous data, and incorporating noisy or missing information.The many interactions among entities make graph operations difficult to partition and parallelize, while side information can require detailed algorithmic design.
- Challenges: Because real networks change over time, summaries should evolve efficiently, yet dynamic graph summarization remains a difficult and multifaceted problem.Existing approaches may treat dynamic graphs as sequences of static snapshots or as streams.
- Survey scope: The survey categorizes methods by input type and methodology, covering static, labeled, and dynamic graphs alongside applications, related fields, and open problems.It also distinguishes homogeneous and heterogeneous inputs, with heterogeneous methods generally more complex but more expressive.
2. STATIC GRAPH SUMMARIZATION: PLAIN NETWORKS
Static plain-graph summarization seeks compact representations of graphs without side information, organized by core methodology. The survey covers grouping, compression, and application-oriented approaches that produce supergraphs, sparsified graphs, or structure-based summaries.
- Static plain-graph summarization describes a graph without side information using a summary graph, structures, or compressed data structure.
- Grouping-based methods: Grouping-based methods partition nodes or edges to create compact summaries, while clustering outputs can also be converted into supernode-and-superedge graphs.
- Node-grouping methods: Clustering groups densely connected nodes, whereas tailored summarization groups nodes with similar external connections that can be replaced by a supernode.
- Node-grouping methods: Sketching, sampling, and approximate partitioning can produce supergraphs with guarantees by minimizing the lp-reconstruction error for a fixed number of supernodes.
- Application-oriented methods: CoSum jointly condenses vertices and links in k-partite heterogeneous graphs to improve entity resolution, while Graph Dedensification compresses redundant high-degree neighborhoods with compressor nodes.
- Compression-based methods: MDL-based summaries aggregate nodes into supernodes and store corrections, while VOG encodes large graphs with overlapping structures such as cliques, stars, chains, and bipartite cores.
- Influence-based methods: Influence-based summaries can represent communities as nodes and influence relationships as directed edges, using MDL and BIC to select the number of communities.
3. STATIC GRAPH SUMMARIZATION: LABELED NETWORKS
Labeled-graph summarization combines structural connections with node or edge attributes, using grouping, compression, and related structure-discovery methods. Approaches seek compact summaries that preserve salient labeled structure, support queries, or exploit repeated patterns.
- Scope and challenge: Labeled-graph summarization must combine structural connections with attributes, but most existing work focuses on node attributes alone.Joint summarization of graphs with text, images, or streaming data remains underexplored.
- Grouping-based methods: Grouping-based methods aggregate structurally close nodes with similar attributes into supernodes connected by superedges.SNAP creates attribute-homogeneous groups and iteratively splits them until relationship compatibility is satisfied; k-SNAP controls summary resolution.
- Compression-based methods: S-Node provides lossless, two-level Web-graph compression that combines space efficiency with complex queries and local graph navigation.It groups pages using domain locality and page similarity, then applies reference encoding to lower-level directed graphs.
- Grouping-based methods: CANAL supports interactive labeled-graph summarization by categorizing numerical attributes and ranking summaries using diversity, coverage, and conciseness.Its criteria incorporate domain knowledge about node labels and graph structure.
- Knowledge-graph methods: Knowledge-graph d-summaries group similar entities within d hops, supporting efficient summarization and querying while maintaining up to 99% accuracy for subgraph queries.The framework uses supergraphs and evaluates entity similarity and summary coverage.
- Compression and similarity-based methods: MDL-based methods group nodes or replace frequent labeled subgraphs with virtual nodes, while LSH-based methods efficiently aggregate nodes with similar neighborhoods and labels.SUBDUE uses greedy beam search to replace frequent subgraphs that minimize MDL cost; LSH uses minhash functions on node neighborhoods.
4. DYNAMIC GRAPH SUMMARIZATION: PLAIN NETWORKS
Dynamic graph summarization addresses evolving networks through snapshot, aggregate, grouping, sketching, compression, and influence-based approaches. Its central difficulty is preserving meaningful temporal behavior despite sensitive and often arbitrary time granularity.
- Challenges: Dynamic graph summarization remains less developed than static summarization because irregular evolution complicates tracking, online interestingness, and visualization.Methods are sensitive to time granularity, which may range from minutes to years and is often chosen arbitrarily.
- Problem definition: Dynamic graph summarization represents evolving networks as temporal summary graphs, overlapping temporal structures, or sparsified graph sequences.The input may be streaming edges or a sequence of adjacency matrices, while outputs reduce nodes or edges.
- Snapshot and aggregate methods: Snapshot-based summarization applies static methods separately to each timestep, but small granularity increases data volume while large granularity can miss dynamics.Effectiveness depends heavily on user-specified aggregation operations and the chosen time unit.
- Snapshot and aggregate methods: Approximation graphs aggregate interactions over time using recency- and frequency-weighted kernel smoothing, optionally pruning edges below a threshold.The approach has been used for telecommunications fraud detection, anomaly detection, behavior prediction, and attribute classification.
- Grouping-based methods: NETCONDENSE recursively merges nodes and timesteps while minimizing changes to the maximum eigenvalue, preserving diffusive properties relevant to marketing and influence dynamics.It flattens the dynamic network into a static problem and uses transformations to achieve sub-quadratic running time and linear space complexity.
- Compression-based methods: TIMECRUNCH uses MDL to identify temporal behaviors of local structures, including flickering, periodic, and one-shot patterns over cliques, stars, chains, and bipartite cores.Its temporal vocabulary extends static graph structures with temporal behavior categories.
- Influence-based methods: OSNet summarizes diffusion cascades from time-ordered interactions by constructing spreading trees and ranking subgraphs using node out-degree, propagation radius, entropy, and a threshold.It targets dynamic behavior that static per-timestamp summaries are not suited to capture.
5. GRAPH SUMMARIZATION IN REAL-WORLD APPLICATIONS
Graph summarization supports efficient querying, pattern discovery, influence extraction, and visualization across diverse real-world graphs. Applications show that summaries can preserve or expose salient structures while reducing the cost of graph analysis.
- 5.1. Summarization for query handling and efficiency: Graph summarization improves query efficiency across pattern-matching, social-network, Web, and knowledge-graph workloads.Reported gains include up to 10× speedup, 92% compression with 70% runtime reduction, 12500× faster construction, 75–90% shorter navigation time, and up to 40× speedup for different applications.
- 5.2. Summarization for visualization: Summaries enable visualization and interactive exploration of graphs that are too large or dense to load and display in raw form.The survey frames visualization as a real-world application alongside algorithmic summarization and query handling.
- 5.2. Summarization for pattern discovery: VOG extracts salient structures from Wikipedia collaboration data, identifying 8 stars and 2 bipartite subgraphs among the 10 most informative structures.The star centers correspond to administrators or highly active contributors, while bipartite cores represent edit wars.
- 5.3. Summarization for influence extraction: Egocentric abstraction improved users’ accuracy, efficiency, and confidence when identifying influential crime-committing gangs in a simulated heterogeneous crime graph.Different abstraction views captured different parts of key criminal evidence, including relationships involving a hired middleman.
- 5.3. Summarization for influence extraction: COARSENET found that many Flixster movies spread through a small number of groups with a multi-modal distribution, while other analyses found no clear general influence structure.The influence findings indicate that propagation can occur at multiple scales, whereas influence and link probabilities need not correlate strongly.
6. CONCLUSION
The survey organizes graph summarization methods into a taxonomy by input-graph type and core technique, reviews applications, and identifies open problems. It concludes that the field is promising but still underexplored, especially for richer graph data and standardized evaluation.
- Conclusion: The survey presents a state-of-the-art taxonomy organized by input-graph type and core summarization technique, with algorithm details, relationships, applications, and open problems.Its scope is methodological and includes examples of real-life applications for each algorithm category.
- Open Research Problems: Graph summarization remains relatively new and underexplored, particularly for temporal graphs with side information, multi-layer graphs, and multiview graphs.Future methods must also incorporate richer data such as time series associated with network nodes.
- Open Research Problems: Evaluation remains application-specific, motivating common metrics for supergraph sparsity, information loss, and ease of visualization.The survey also highlights the need to standardize, generalize, or extend algorithmic and evaluation techniques.
- Open Research Problems: Existing query-oriented methods often provide approximate results or support only specific exact queries, leaving general-purpose lossless compression unresolved.The survey identifies this as an area requiring further work.
- Open Research Problems: Learning graph summaries from automatically derived deep node representations is identified as a promising research direction.This direction builds on prior methods using latent representations or manually selected structural features.