TL;DR
This paper introduces a novel framework for sampling frequent subgraph patterns, addressing the scalability and information overload issues in traditional graph mining. By employing a Metropolis-Hastings algorithm to perform a random walk on the partial order of frequent subgraphs, the authors demonstrate an efficient and generic method to obtain representative subgraphs without enumerating the entire output space.
What Problem Does This Paper Address?
Graph pattern mining, particularly finding frequent subgraphs, is crucial in various domains like cheminformatics and bioinformatics. However, traditional algorithms struggle with scalability when dealing with large and dense graph databases. This leads to two major problems: (1) scalability issues, where algorithms take prohibitively long to run, and (2) information overload, where the sheer number of frequent subgraphs makes it difficult to extract meaningful insights. Existing approaches to mitigate this include sampling the input data or using pruning criteria to reduce the candidate subgraph space. This paper tackles the problem by proposing to sample the output space of frequent subgraphs, aiming to find a small, representative subset of patterns directly.
Methods
The core contribution is a generic sampling framework based on the Metropolis-Hastings (MH) algorithm. This framework performs a random walk on the partial order graph (POG) of frequent subgraphs. The POG represents all frequent subgraphs and their relationships (subgraph containment).
Key aspects of the method:
- Metropolis-Hastings Algorithm: Used to simulate a Markov chain whose stationary distribution matches a desired target distribution (e.g., uniform or support-proportional).
- Random Walk on POG: The states of the Markov chain are the frequent subgraph patterns. The algorithm explores the POG by moving between neighboring patterns (super- or sub-patterns).
- Generic Framework: The MH algorithm is adaptable to different "interestingness" criteria (e.g., support, discriminatory score) by simply changing the target distribution.
- Output Space Sampling: Unlike input sampling, this method directly samples from the set of frequent patterns, addressing the information overload problem.
- Specific Sampling Strategies:
- Uniform Sampling: Aims to sample each frequent subgraph with equal probability. This is achieved by ensuring the transition probability matrix is doubly stochastic.
- Support-Proportional Sampling: Samples subgraphs with a probability proportional to their support. This requires a carefully chosen proposal distribution that biases the walk towards higher-support patterns.
- Discriminatory Subgraph Sampling: Samples subgraphs based on their discriminatory power (e.g., using a "delta score" for classification tasks). The proposal distribution is designed to favor patterns with higher discriminatory scores.
Datasets
The paper evaluates its methods on several datasets:
- DTP (CM) AIDS antiviral screening dataset: Used for uniform sampling experiments. It contains 1084 graphs with an average size of 45 edges and 43 vertices.
- Chess dataset (UCI Machine Learning Repository): Used for uniform sampling of itemsets (as a comparison/validation). It has 3196 transactions with an average of 10.25 items.
- Mutagenicity I dataset: Used for discriminatory subgraph sampling. It contains 4337 chemical graphs with two classes.
- Protein Interaction (PI) graphs: Large graph dataset used to demonstrate scalability.
- Cell-Graphs: Large graph dataset used to demonstrate scalability and discriminatory sampling.
Key Insights and Ideas
- Output Space Sampling as a Solution: The paper convincingly argues that sampling the output space is a viable and efficient alternative to enumerating all frequent subgraphs, especially for large datasets.
- Genericity of MH: The Metropolis-Hastings framework provides a flexible and generic approach that can be adapted to various subgraph interestingness measures without redesigning the core algorithm.
- POG as a State Space: The partial order graph of frequent subgraphs is a natural and effective state space for the random walk.
- Bias-Correction in Sampling: The MH algorithm's acceptance probability mechanism is crucial for correcting biases introduced by proposal distributions, allowing for accurate sampling of target distributions.
- Trade-offs in Sampling Strategies: Different sampling objectives (uniform, support-proportional, discriminatory) require different proposal distributions and lead to varying experimental outcomes, highlighting the importance of tailoring the approach to the task.
Key Results
- Uniform Sampling: Achieved good uniformity on the DTP dataset, with visit counts reasonably close to the ideal uniform distribution, though some skewness was observed due to the POG's structure. The Chess dataset showed even better uniformity.
- Support-Proportional Sampling: Demonstrated a linear correlation between sampled pattern visit counts and their support values, indicating successful bias towards higher-support patterns.
- Discriminatory Subgraph Sampling: Showed that the algorithm can efficiently find patterns with high discriminatory scores, spending more sampling time on patterns with higher delta scores compared to their overall frequency.
- Scalability: The sampling approach significantly outperforms traditional mining algorithms on large graph datasets (Protein Interaction and Cell-Graphs), where complete enumeration is infeasible. For example, on Cell-Graphs, the sampler found patterns with delta scores of 9 or more in 2 hours, while a traditional algorithm found only 3 such patterns in the same period.
Limitations and Future Work
- Database in Memory: A significant limitation is that the current implementation requires the entire graph database to be in memory for efficient neighbor computation. This makes the random walk inefficient if the database is too large for RAM.
- Proposal Distribution Choice: The performance and quality of sampling are highly dependent on the choice of the proposal distribution. Finding an appropriate proposal distribution can be challenging and may require empirical tuning or dynamic adaptation.
- Mixing Rate: The POG graph can have a poor mixing rate, meaning the Markov chain might take many steps to converge to the stationary distribution.
- Future Work:
- Improving Mixing Rate: Incorporating random edges on the POG (similar to ORIGAMI) to embed a random graph structure and improve mixing.
- Integrating with Classification: For discriminatory sampling, integrating the sampled patterns into a graph classification framework to evaluate their effectiveness directly.
- Handling Large Databases: Developing methods to handle graph databases that do not fit into memory.
Summary updated