Generic Mining of Condensed Pattern Representations under Constraints

Sergey Paramonov, Tao Chen, Tias GunsYSIP 2017 · OpenReview

Introduction

Pattern mining is a fundamental task in data science used to identify regularities within complex datasets. However, a persistent challenge in this field is the "pattern explosion" problem, where algorithms generate an overwhelming number of results, many of which are redundant. To address this, researchers typically apply two types of constraints: local constraints (e.g., minimum sequence length or maximum graph cost) and condensed representation constraints (e.g., mining only "closed" or "maximal" patterns to eliminate sub-patterns with identical frequency).

Historically, tools for these tasks have been siloed, optimized for a single data type like itemsets or a specific constraint. Generic search-based methods exist but often fail to scale to large, complex structures like graphs. This paper introduces hyppro, a generic, pattern-type agnostic framework designed to efficiently mine condensed representations under local constraints across itemsets, sequences, and graphs.

The hyppro Framework

The authors propose a three-step "inductive database" pipeline that leverages the strengths of existing specialized miners while adding a flexible filtering layer.

The three-step hyppro pipeline: initial mining, local constraint filtering, and dominance checking.
  1. Step 1: Frequent Pattern Mining: Instead of building a new miner from scratch, hyppro uses highly optimized, specialized algorithms (such as Eclat for itemsets or gSpan for graphs) as "black boxes." This allows the framework to benefit from decades of performance tuning.
  2. Step 2: Local Constraint Filtering: The system performs a fast linear scan to discard any individual patterns that do not meet user-defined criteria, such as size or cost.
  3. Step 3: Dominance Checks: This final stage identifies and removes redundant patterns. For example, if a user wants "closed" patterns, hyppro must check if a pattern is a sub-pattern of another with the same frequency. This is the most computationally intensive step, particularly for graphs where subgraph isomorphism is NP-complete.

Optimizing the Bottleneck

To make Step 3 feasible at scale, the authors implemented several critical optimizations designed to prune the search space and avoid expensive computations.

Detailed view of Step 3 optimizations, including sliding window checks (3a) and property-based filtering (3b).
  • Neighborhood Checks (Sliding Window): Mining algorithms often output similar patterns in close proximity. By performing a linear scan of patterns within a fixed window ($2\delta$), hyppro can quickly catch many redundancies.
  • Property-based Filtering: Before performing expensive isomorphism tests, the system checks "easy" properties like the number of nodes, label arity, or frequency. If these don't match, the more complex check can be skipped entirely.
  • Transitivity: If pattern A is shown to dominate pattern B, and B dominates C, the system can immediately discard C without further comparison.

Results and Key Insights

The framework was evaluated across a wide array of benchmarks, including chemical compounds (AIDS, Chemical 340), web logs (Unix users), and standard itemset datasets (Mushrooms, German-credit).

Key findings include:

  • Performance: hyppro significantly outperforms generic search-based systems like Answer Set Programming (ASP) and Dominance Programming (DP).
  • Efficiency: The multi-stage filtering in Step 3 is the primary driver of speed, keeping total runtime within a manageable constant factor (10-20x) of the initial specialized mining time.
  • Constraint Ordering: The authors demonstrate that applying local constraints before dominance checks is essential. This prevents valid patterns from being incorrectly "dominated" by larger patterns that would have been filtered out anyway.

While the framework's performance is currently tied to the speed of the underlying Step 1 miner and can be memory-intensive at very low frequency thresholds, its modular design makes it a powerful tool for extensible, high-performance pattern discovery.

Summary updated

BibTeX
@inproceedings{paramonov2017generic,
  author = {Sergey Paramonov and Tao Chen and Tias Guns},
  title = {{Generic Mining of Condensed Pattern Representations under Constraints}},
  booktitle = {YSIP},
  year = {2017},
  url = {https://openreview.net/forum?id=0dReNXILLJ},
}
Figure