Abstract
We developed a flexible parallel algorithm for graph summarization based on vertex-centric programming and parameterized message passing. The base algorithm supports infinitely many structural graph summary models defined in a formal language. An extension of the parallel base algorithm allows incremental graph summarization. In this paper, we prove that the incremental algorithm is correct and show that updates are performed in time $\mathcal{O}(\Delta \cdot d^k)$, where $\Delta$ is the number of additions, deletions, and modifications to the input graph, $d$ the maximum degree, and $k$ is the maximum distance in the subgraphs considered. Although the iterative algorithm supports values of $k>1$, it requires nested data structures for the message passing that are memory-inefficient. Thus, we extended the base summarization algorithm by a hash-based messaging mechanism to support a scalable iterative computation of graph summarizations based on $k$-bisimulation for arbitrary $k$. We empirically evaluate the performance of our algorithms using benchmark and real-world datasets. The incremental algorithm almost always outperforms the batch computation, even when 50% of the graph database changes. The incremental computation requires a three-layered hash index with a low memory overhead of only 8%. Finally, the iterative parallel $k$-bisimulation algorithm computes summaries on graphs with over 10M edges within seconds and 1B edges in under an hour.
Introduction
In the era of the Semantic Web and massive social networks, graphs are not just enormous—they are constantly changing. Structural graph summarization is a vital technique used to create "condensed" versions of these graphs, which are essential for query optimization, data exploration, and cardinality estimation. However, most existing summarization algorithms suffer from two major flaws: they are often batch-only, requiring full recomputation for minor changes, and they face memory bottlenecks when using advanced models like $k$-bisimulation.
This paper addresses these challenges by introducing a flexible, parallel, and incremental framework designed for evolving graphs. By leveraging a vertex-centric programming model and novel indexing strategies, the proposed system bridges the gap between high-fidelity structural analysis and the practical constraints of massive, dynamic datasets.
Methodology and Formal Framework
The solution is built on a vertex-centric programming model (similar to Google’s Pregel), enabling high levels of parallelism. The framework utilizes a formal model for Labeled Property Graphs (GDB) and their summaries (SG), as detailed in the following notation:
The approach consists of three main components:
- The Base Parallel Algorithm: A flexible framework using parameterized message passing to support various summary models defined in the formal language FLUID.
- Incremental Updates via
VertexUpdateHashIndex: Instead of re-summarizing the entire graph, a three-layered hash index tracks relationships between original vertices, summary counterparts, and payloads. This allows the algorithm to identify and update only affected portions of the summary when the graph evolves. - Hash-based Messaging: To scale $k$-bisimulation, the authors replaced full structural descriptions with unique, fixed-size hashes. This "parallel hash-based" variant allows scaling to large values of $k$ without memory exhaustion.
The incremental process is visualized below, showing how changes in the source data at time $t+1$ are propagated to the summary.
Evaluation and Results
The algorithms were evaluated using synthetic benchmarks (LUBM, BSBM) and real-world web crawls (DyLDO). Key findings include:
- The 50% Rule: The incremental algorithm almost always outperformed batch recomputation, even when up to 50% of the graph changed.
- Efficiency and Scalability: The
VertexUpdateHashIndexadded only ~8% memory overhead while providing 5x to 44x speedups on real-world data. The hash-based algorithm processed the 1-billion-edge BSBM1B dataset ($k=10$) in under 55 minutes. - Real-world Complexity: Experiments showed that real-world graphs, with their heterogeneous schema structures, are significantly harder to summarize than synthetic ones, yet the incremental approach remained competitive even on single-core runs.
Conclusion
This work demonstrates that deep neighborhood analysis on a billion-edge scale is feasible through parallel hashing and incremental updates. Future work includes combining incremental and hash-based methods—a non-trivial task due to hash sensitivity—and exploring Multi-GPU acceleration to move toward real-time processing of evolving massive graphs.
Summary updated