Cyclosa: Redundancy-Free Graph Pattern Mining via Set Dataflow

Chuangyi Gui, Xiaofei Liao, Long Zheng, Hai JinUSENIX ATC 2023 · OpenReview

TL;DR

This paper introduces Cyclosa, a novel framework for graph pattern mining that significantly speeds up the process by eliminating redundant computations. It achieves this by representing graph patterns as a "set dataflow" and employing a smart execution engine and data management substrate to reuse intermediate results, outperforming existing methods by up to 16.28x.

What Problem Does This Paper Address?

Graph pattern mining, the task of finding specific substructures within large graphs, is crucial for analyzing networks in fields like social media, finance, and bioinformatics. While existing "pattern-centric" approaches have improved efficiency by transforming patterns into a series of set operations, they still suffer from significant redundancy. These redundancies, both "explicit" (repeated computations within a single pattern analysis) and "implicit" (repeated computations across different pattern instances or even different patterns), can consume over 80% of the runtime. Existing systems can only address a fraction of these redundancies, leading to hours or days of computation for complex tasks. Cyclosa aims to tackle this pervasive problem by eliminating both explicit and implicit redundancies.

Methods

Cyclosa introduces a three-pronged approach:

  • Set Dataflow Representation: Instead of just looking at the overall structure of a pattern, Cyclosa breaks down the set operations into a directed graph called a "set dataflow." This representation exposes fine-grained computation similarities at the operand level, allowing for the identification and elimination of both explicit and implicit redundancies.
  • Dataflow Execution Engine: This engine decouples data access from computation, enabling efficient sharing of intermediate results. It processes the set dataflow, requesting and reusing computed results whenever possible, rather than recomputing them.
  • Memory-Friendly Data Management Substrate: To handle the potentially large number of intermediate results, Cyclosa employs a smart caching strategy. It prioritizes storing results with higher "reuse probability" (based on factors like vertex degree and dataflow depth) in a multi-level buffer, ensuring efficient memory usage and fast retrieval.

Datasets

The paper evaluates Cyclosa on several real-world graph datasets from the Stanford SNAP collection, commonly used in graph mining research. These include:

  • WikiVote (WV)
  • MiCo (MI)
  • WikiTalk (WT)
  • Patents (PA)
  • LiveJournal (LJ)
  • Orkut (OR)
  • Friendster (FR)

These datasets represent typical graphs from various domains and are used to test different types of graph pattern mining applications, including single pattern queries (like motif counting and clique finding) and multi-pattern queries (like pseudo-clique counting).

Key Insights and Ideas

  • Beyond Structural Equality: The core insight is that focusing solely on structural equality of set formulas is insufficient. Cyclosa's "set dataflow" reveals deeper, operand-level similarities that are key to uncovering and eliminating implicit redundancies.
  • Dynamic Similarity is Crucial: The paper highlights that a small subset of high-degree vertices are involved in a disproportionately large number of computations. This "dynamic similarity" is a critical factor that Cyclosa leverages for efficient caching and reuse.
  • Dataflow as a Blueprint for Reuse: The set dataflow acts as a blueprint, not just for computation, but for identifying opportunities to reuse results. This is a fundamental shift from previous approaches.
  • Smart Caching is Essential: Simply storing all intermediate results is infeasible. Cyclosa's intelligent caching, guided by reuse probability and vertex degrees, is vital for managing memory and achieving performance gains.

Key Results

Cyclosa demonstrates significant performance improvements over state-of-the-art systems:

  • Single Pattern Mining: Cyclosa achieves speedups of up to 16.28x compared to GraphPi and up to 5.52x compared to SumPA on various single pattern mining tasks.
  • Clique Finding: Cyclosa outperforms GraphPi by up to 7.13x and SumPA by up to 5.26x for clique counting.
  • Multi-Pattern Mining: For motif counting, Cyclosa shows average speedups of 1.64x for 4-MC and 2.95x for 5-MC, with higher speedups observed for larger patterns.
  • Pseudo Cliques: Cyclosa is superior to GraphPi and SumPA by 4.01x ~ 7.52x and 1.48x ~ 2.63x, respectively, for pseudo-clique mining.
  • Scalability: Cyclosa scales well with an increasing number of threads and demonstrates efficiency on large graphs with billions of edges.
  • Memory Consumption: Despite maintaining some intermediate results, Cyclosa's memory footprint is comparable to or even smaller than GraphPi, thanks to its efficient sharing and caching strategies.

Limitations and Future Work

  • Unlabeled Patterns: The current implementation of Cyclosa focuses on mining unlabeled patterns. While it can be extended to handle labeled patterns by adding label information as constraints, the dynamic computation similarity might change with high-degree vertices having different labels.
  • Memory Contention: While Cyclosa generally performs well, memory access contention can become a factor when hyperthreading is heavily utilized, impacting performance improvements.
  • Future Work: The authors suggest that their data management substrate could be integrated into existing systems to reduce redundancies. Further exploration into handling labeled patterns and optimizing for memory contention are implied future directions.

Summary updated

BibTeX
@inproceedings{gui2023cyclosa,
  author = {Chuangyi Gui and Xiaofei Liao and Long Zheng and Hai Jin},
  title = {{Cyclosa: Redundancy-Free Graph Pattern Mining via Set Dataflow}},
  booktitle = {USENIX ATC},
  year = {2023},
  url = {https://openreview.net/forum?id=2aT9xGwr8h},
}
Figure