Mining Graph Patterns Efficiently via Randomized Summaries

Chen Chen, Cindy Xide Lin, Matt Fredrikson, Mihai Christodorescu, Xifeng Yan, Jiawei Han

TL;DR

This paper introduces SUMMARIZE-MINE, a novel framework for efficiently mining frequent patterns in massive graphs. It tackles the computational bottleneck of subgraph isomorphism by creating randomized "summaries" of large graphs, mining these smaller summaries, and then verifying the results. This approach significantly speeds up pattern discovery, especially for applications like malware analysis, while providing probabilistic guarantees against missing true patterns.

What Problem Does This Paper Address?

Graph pattern mining is crucial for understanding complex data in fields like bioinformatics, social networks, and cybersecurity. However, existing algorithms often struggle with the sheer size of modern graphs. The core challenge lies in the subgraph isomorphism problem, which is computationally expensive. For any given pattern, finding all its occurrences (embeddings) in a large graph can involve checking an astronomical number of potential subgraphs, leading to prohibitive runtime. This bottleneck hinders practical applications, such as identifying malicious program behaviors through system call graphs, where graphs can be enormous.

Methods

The paper proposes the SUMMARIZE-MINE framework, which tackles the problem by reducing the data space within each graph transaction, rather than reducing the number of transactions or compressing between them.

Here's how it works:

  1. Summarization: Each large graph $G_i$ is transformed into a smaller "summarized" graph $S_i$. This is achieved by grouping vertices with identical labels and collapsing each group into a single node in $S_i$. This process dramatically reduces the graph size and, consequently, the number of potential subgraph embeddings.
  2. Randomization: To mitigate the pattern loss that can occur during summarization, the grouping of vertices is done randomly. This process is repeated for multiple independent rounds. The intuition is that true frequent patterns are unlikely to be missed in all rounds.
  3. Mining Summaries: A standard frequent subgraph mining algorithm (like gSpan) is applied to the collection of summarized graphs $D' = \{S_1, S_2, ..., S_n\}$. A slightly lowered support threshold ($min\_sup'$) is used to account for potential minor pattern loss.
  4. Verification: Patterns found in the summarized database ($FP(D')$) are then verified against the original, larger database ($D$). Patterns that do not meet the original minimum support threshold ($min\_sup$) are discarded as false positives.
  5. Iteration and Combination: Steps 1-3 are repeated for $t$ iterations. The final set of frequent patterns is the union of verified patterns from all iterations. The number of iterations $t$ is determined to provide a probabilistic guarantee ($\epsilon$) on the likelihood of missing any true frequent pattern.

A key optimization is Summary-Guided Isomorphism Checking, where embeddings found in the summarized graph $S_i$ are used to guide the search for embeddings in the original graph $G_i$, significantly speeding up verification.

Datasets

The paper evaluates SUMMARIZE-MINE on:

  • Real Malware Trace Data: This dataset consists of program dependence graphs generated from malware analysis. These graphs are noted to be very large, with an average of 1,300 nodes per graph.
  • Synthetic Datasets: These datasets are generated using a custom generator that allows control over parameters like the number of graphs, average graph size, number of seed patterns, and number of distinct vertex/edge labels. This allows for systematic evaluation of performance and parameter tuning.

Key Insights and Ideas

  • Data Space Reduction within Transactions: The core innovation is compressing information inside each graph, rather than just selecting subsets of graphs or compressing between them. This directly addresses the bottleneck of subgraph isomorphism.
  • Randomization for Probabilistic Guarantees: Instead of aiming for lossless compression (which is difficult), the authors embrace randomized summarization. By repeating the process, they can provide strong probabilistic guarantees against missing true patterns.
  • Summarization as a Preprocessing Step: The work highlights the potential of summarization as a general preprocessing technique for large graph analysis, enabling efficient mining of patterns that would otherwise be computationally intractable.
  • Trade-off Between Compression and Accuracy: The paper meticulously analyzes the trade-offs between the degree of summarization (compression ratio $\alpha$) and the mining performance, demonstrating that an optimal balance exists.

Key Results

  • Significant Speedup: SUMMARIZE-MINE demonstrates substantial efficiency gains compared to a standard algorithm like gSpan, especially as the size of the input graphs increases. For instance, gSpan could not finish within 3 hours on larger graphs where SUMMARIZE-MINE remained stable.
  • Effective Malware Pattern Discovery: The method successfully identified interesting malware fingerprints that were not revealed by previous approaches.
  • Probabilistic Guarantees: The theoretical analysis provides bounds on the false negative rate, and experimental results (Figure 8) show that the empirical event frequencies are well within the predicted theoretical bounds, indicating the safety of the approach.
  • Optimal Parameter Tuning: Experiments (Figure 12) show how to find an optimal balance for the summarized support threshold ($min\_sup'$) to achieve the best running time while maintaining a low false negative rate.
  • Scalability: The algorithm exhibits linear scalability with respect to the number of transactions (graphs) in the dataset (Figure 14).

Limitations and Future Work

  • False Positives: While the paper provides a verification mechanism to discard false positives, the initial mining on summarized graphs can still generate them, requiring the verification step.
  • Parameter Sensitivity: The performance and accuracy are influenced by parameters like the summarization ratio ($\alpha$) and the lowered support threshold ($min\_sup'$). Finding optimal values is crucial, as explored in the experiments.
  • Future Work: The authors suggest exploring alternative verification strategies (e.g., bottom-up vs. top-down) and investigating the necessity of maintaining verified ID-lists for all patterns, as some optimizations might be achievable without them. They also note that the core idea of randomized summarization could be extended to other data structures like sequences and trees.

Summary updated

BibTeX
@article{chen2009mining,
  author = {Chen Chen and Cindy Xide Lin and Matt Fredrikson and Mihai Christodorescu and Xifeng Yan and Jiawei Han},
  title = {{Mining Graph Patterns Efficiently via Randomized Summaries}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687627.1687711},
}
Figure