Time and Memory Efficient Parallel Algorithm for Structural Graph Summaries and two Extensions to Incremental Summarization and $k$-Bisimulation for Long $k$-Chaining

Till Blume, Jannik Rau, David Richerby, Ansgar Scherp

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. We observe in our experiments that the incremental algorithm is faster even in cases when $50\%$ of the graph database changes from one version to the next. The incremental computation requires a three-layered hash index, which has a low memory overhead of only $8\%$ ($\pm 1\%$). Finally, the incremental summarization algorithm outperforms the batch algorithm even with fewer cores. The iterative parallel $k$-bisimulation algorithm computes summaries on graphs with over $10$M edges within seconds. We show that the algorithm processes graphs of $100+\,$M edges within a few minutes while having a moderate memory consumption of $<150$ GB. For the largest BSBM1B dataset with 1 billion edges, it computes $k=10$ bisimulation in under an hour.

Introduction

Graphs are fundamental to modern data representation, from social networks to the Semantic Web. However, their massive scale often makes direct querying or visualization impossible. Graph summarization addresses this by creating a condensed version that preserves essential structural features. Traditional summarization faces two major hurdles: the "Evolving Graph" problem, where static batch algorithms must recompute everything for minor changes, and the "Memory Explosion" problem, where complex structural summaries like $k$-bisimulation require prohibitively large nested data structures.

Methods and Framework

The proposed solution utilizes a vertex-centric programming model, where each vertex independently processes and passes messages. This framework introduces three key innovations:

Formal Language Integration (FLUID)

The algorithm is model-agnostic, using the FLUID formal language to define summaries. This allows it to compute a wide variety of structural summary models by simply adjusting parameters.

Formal symbols and definitions used in the GDB and SG models.

Incremental Summarization

To handle evolving data, the authors developed an incremental update mechanism. Instead of full recomputation, a three-layered VertexUpdateHashIndex tracks relationships between original vertices and their summary counterparts. When the graph changes, only the affected local neighborhoods are updated.

Illustration of incremental graph summarization over time steps t and t+1, showing how changes in the data graph propagate to the summary.

Hash-Based Messaging for $k$-Bisimulation

For long-range structural summaries ($k$-bisimulation), the algorithm replaces complex structural descriptions with unique, iteration-specific hashes. This reduces memory consumption and transforms structural comparison into simple numerical matching, enabling scalability to billion-edge graphs.

Experimental Evaluation

The framework was tested on synthetic (LUBM, BSBM) and real-world (DyLDO) datasets.

  • Scalability: On the BSBM1B dataset (1 billion edges), the algorithm computed a $k=10$ bisimulation in under an hour.
  • Incremental Efficiency: The incremental algorithm outperformed batch recomputation even when 50% of the graph changed. It also maintained high efficiency with fewer CPU cores than the batch version.
  • Memory Overhead: The incremental index adds a minimal memory overhead of only 8% (±1%).
  • Real-World Complexity: Summaries of real-world Semantic Web data (DyLDO) were found to be 10–100 times larger than synthetic counterparts due to higher structural heterogeneity.

Conclusion

This work demonstrates a scalable, parallel approach to maintaining structural graph summaries on evolving, billion-edge datasets. By combining formal flexibility with incremental updates and hash-based messaging, the framework overcomes traditional memory and time constraints. Future work will focus on unifying the incremental and hash-messaging extensions and exploring Multi-GPU acceleration.

Summary updated

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}(Δ\cdot d^k)$, where $Δ$ 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&gt;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. We observe in our experiments that the incremental algorithm is faster even in cases when $50\%$ of the graph database changes from one version to the next. The incremental computation requires a three-layered hash index, which has a low memory overhead of only $8\%$ ($\pm 1\%$). Finally, the incremental summarization algorithm outperforms the batch algorithm even with fewer cores. The iterative parallel $k$-bisimulation algorithm computes summaries on graphs with over $10$M edges within seconds. We show that the algorithm processes graphs of $100+\,$M edges within a few minutes while having a moderate memory consumption of $&lt;150$ GB. For the largest BSBM1B dataset with 1 billion edges, it computes $k=10$ bisimulation in under an hour.
BibTeX
@misc{blume2021time,
  author = {Till Blume and Jannik Rau and David Richerby and Ansgar Scherp},
  title = {{Time and Memory Efficient Parallel Algorithm for Structural Graph Summaries and two Extensions to Incremental Summarization and $k$-Bisimulation for Long $k$-Chaining}},
  year = {2021},
  eprint = {2111.12493},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.12493},
}
Figure