Canonical Forms for Frequent Graph Mining

Christian BorgeltGfKl 2006 · DOI

TL;DR

This paper introduces a generalized framework for canonical graph representations, crucial for efficient frequent subgraph mining. By systematically constructing spanning trees, it unifies and extends existing methods like gSpan and MoSS/MoFa, leading to significant performance improvements by pruning redundant search paths.

What Problem Does This Paper Address?

Finding common subgraphs in large datasets (frequent subgraph mining) is a fundamental task with applications in areas like bioinformatics and web mining. A major challenge is avoiding redundant computations. When growing subgraphs to find frequent ones, the same subgraph can be discovered through many different sequences of additions. This leads to exploring the same structures multiple times, drastically slowing down the mining process. Existing algorithms try to address this by using canonical forms – unique representations for each subgraph – to ensure each structure is considered only once. However, the specific canonical forms used can impact efficiency.

Methods

The paper proposes a family of canonical forms for graphs, generalizing the approach used in the gSpan algorithm. The core idea is to represent a graph as a "code word" derived from systematically constructed spanning trees.

  • Spanning Tree Construction: The authors show that canonical forms can be based on either Depth-First Search (DFS) or Breadth-First Search (BFS) spanning trees. While gSpan uses DFS, they demonstrate that MoSS/MoFa implicitly uses a BFS-based canonical form.
  • Code Word Generation: A code word is generated by encoding the edges of the graph based on the node numbering derived from the spanning tree. This encoding includes node and edge attributes.
  • Canonical Form Test: A key contribution is a method to check if a generated code word is the lexicographically smallest among all possible representations of the same subgraph. This test is crucial for pruning the search space.
  • Restricted Extensions: The canonical forms are not just for testing but also for actively restricting the search. By analyzing the code word, the algorithm can immediately prune extensions that are guaranteed to lead to non-canonical (and thus redundant) representations. This is achieved by defining specific rules for which nodes can be extended and with which edges, based on the structure of the spanning tree and the code word.

Datasets

The paper evaluates its approach using two datasets:

  • Index Chemicus (IC93) subset: A dataset of chemical compounds.
  • Steroids dataset: A dataset consisting of 17 steroids.

The authors do not introduce new benchmarks but use these established datasets to compare their canonical form-based pruning against other strategies.

Key Insights and Ideas

  • Unifying Framework: The paper provides a generalized framework that elegantly unifies different canonical form approaches (DFS-based like gSpan, and BFS-based like MoSS/MoFa) under a single conceptual umbrella.
  • BFS Canonical Form Justification: The heuristic "maximum source extension" strategy in MoSS/MoFa is formally justified as being implicitly based on a BFS-derived canonical form. This provides a theoretical grounding for a previously ad-hoc optimization.
  • Restricted Extensions as Pruning: The insight that canonical forms can directly restrict search extensions, rather than just being used for post-hoc checking, is a significant optimization. This proactive pruning dramatically reduces the search space.
  • Efficiency Gains: The experimental results demonstrate substantial speedups, highlighting the practical importance of these canonical forms for efficient graph mining.

Key Results

The experimental results show significant improvements in performance:

  • Speedups: The canonical form-based pruning strategies (both DFS and BFS) achieved speedups ranging from about 2.5x to over 30x compared to approaches without pruning or with explicit duplicate removal.
  • IC93 Data: The BFS canonical form performed slightly better (10-15% less time) due to generating fewer fragments and embeddings.
  • Steroids Data: The DFS canonical form performed marginally better at very low support values, primarily by generating fewer fragments, though this was sometimes offset by more embeddings.

Limitations and Future Work

  • Limitations: The paper acknowledges that while canonical forms significantly reduce redundancy, they cannot eliminate it entirely, especially in cases of graph symmetry where multiple automorphisms exist. The pseudocode for checking canonical form assumes node and edge attributes can be coded as integers, which might require preprocessing for other data types.
  • Future Work: The authors suggest that other systematic ways of constructing spanning trees could also form the basis of canonical forms, implying a broader family of possibilities beyond DFS and BFS. They also mention that strategies like those in the Gaston algorithm, which prioritize spanning tree edges before closing cycles, might offer further advantages and could be incorporated into this framework.

Summary updated

BibTeX
@inproceedings{borgelt2006canonical,
  author = {Christian Borgelt},
  title = {{Canonical Forms for Frequent Graph Mining}},
  booktitle = {GfKl},
  year = {2006},
  doi = {10.1007/978-3-540-70981-7\_38},
}

Loading related content...

Figure