Streaming and Batch Algorithms for Truss Decomposition

Venkata Rohit Jakkula, George KarypisGc 2019 · DOI

TL;DR

This paper introduces efficient algorithms for updating truss decompositions in dynamic graphs. They present a novel incremental algorithm that significantly speeds up updates by intelligently exploring only relevant parts of the graph, and a batch algorithm that further optimizes performance when multiple edges are added simultaneously.

What Problem Does This Paper Address?

Graphs are powerful tools for representing relationships, and "truss decomposition" is a technique used to identify cohesive subgraphs within these networks. These subgraphs reveal important community structures, like tightly-knit groups in social networks. However, real-world graphs are rarely static; they evolve over time as new relationships (edges) are added or removed. Recomputing the entire truss decomposition from scratch after every small change is computationally prohibitive. This paper addresses the challenge of efficiently updating truss decompositions in dynamic graphs, focusing on scenarios where edges are added incrementally or in batches.

Methods

The paper builds upon existing work on truss decomposition and incremental updates. Their core contributions are:

  • Theoretical Foundation for Incremental Updates: They develop a theory that precisely identifies which edges' truss numbers could potentially change after an edge insertion. This theory provides an upper bound on the subset of edges that need to be examined, drastically reducing the search space compared to previous methods.
  • Efficient Incremental Algorithm (JK-Inc): Based on the theory, they design an incremental algorithm that leverages optimizations to explore fewer edges. This algorithm is designed to be more efficient than prior incremental approaches.
  • Batch Algorithm (JK-Batch): They extend the incremental theory to handle updates involving a set of edges (a batch). This batch algorithm aims to avoid redundant computations that would occur if each edge in the batch were processed individually.
  • Optimized Incremental Algorithm (JK-Inc Improved): A further optimization is introduced by pre-computing "truss-degrees" to further refine the set of edges to explore.

Datasets

The authors evaluated their algorithms on two real-world datasets:

  • sx-stackoverflow-a2q (stackoverflow): A large, sparse temporal graph.
  • email-Eu-core-temporal (email): A denser temporal graph.

These datasets were sourced from SNAP and represent graphs where edges have timestamps, allowing for the simulation of streaming data.

Key Insights and Ideas

  • Localized Changes: The core insight is that adding an edge typically only affects the truss decomposition in a localized region of the graph, near the newly added edge. This principle is the foundation for efficient incremental updates.
  • Recursive Structure of Change: The theoretical work reveals a recursive structure in how truss numbers change, allowing for a more targeted exploration of affected edges.
  • Parallelism Potential: The independence of certain algorithmic components for different truss values (k) suggests opportunities for parallelization, though this was not explicitly implemented in the current work.
  • Batch Processing Advantage: Processing multiple edge updates together in a batch can be significantly more efficient than handling them one by one, especially when edges in the batch contribute to the same truss structures.

Key Results

  • Incremental Speedup: The JK-Inc algorithm achieved an average speedup of over 250,000x for edge insertions on a sparse graph compared to recomputing the truss decomposition from scratch.
  • Batch vs. Incremental: The JK-Batch algorithm consistently outperformed the incremental JK-Inc algorithm for batch updates, showing speedups of up to 17.5x on the dense dataset and up to 6x on the sparse dataset.
  • Scalability: Both incremental algorithms scale well for sparse graphs, which are common in real-world scenarios. Performance on dense graphs was less impressive due to the potential for localized changes to affect a larger portion of the graph.

Limitations and Future Work

  • Dense Graph Performance: The incremental algorithms' performance degrades on dense graphs, as a single edge insertion can potentially affect a larger portion of the graph.
  • Overhead in JK-Inc: In some cases, the overhead of updating memoized truss-degrees in the JK-Inc algorithm could negate its benefits, especially when the set of affected edges is not significantly smaller than what HCQTY explores.
  • Predicting When to Revert: The authors acknowledge that in situations where incremental algorithms become slow, reverting to a non-incremental approach might be beneficial. However, predicting when this switch is optimal requires further analysis.
  • Optimal Batch Size: The paper suggests exploring how to determine optimal batch sizes for different scenarios, as very large batches might also lead to performance degradation compared to non-incremental methods.
  • Parallel Implementation: The theoretical insights suggest opportunities for parallelism, which could be explored in future work.

Summary updated

BibTeX
@inproceedings{jakkula2019streaming,
  author = {Venkata Rohit Jakkula and George Karypis},
  title = {{Streaming and Batch Algorithms for Truss Decomposition}},
  booktitle = {Gc},
  year = {2019},
  doi = {10.1109/gc46384.2019.00016},
}
Figure