On Mining Closed Sets in Multi-Relational Data

Gemma C. Garriga, Roni Khardon, Luc De RaedtIJCAI 2007 · OpenReview

Abstract

We investigate the problem of mining closed sets in multi-relational databases. Previous work introduced different semantics and associated algorithms for mining closed sets in multirelational databases. However, insight into the implications of semantic choices and the relationships among them was still lacking. Our investigation shows that the semantic choices are important because they imply different properties, which in turn affect the range of algorithms that can mine for such sets. Of particular interest is the question whether the seminal LCM algorithm by Uno et al. can be upgraded towards multi-relational problems. LCM is attractive since its run time is linear in the number of closed sets and it does not need to store outputs in order to avoid duplicates. We provide a positive answer to this question for some of the semantic choices, and report on experiments that evaluate the scalability and applicability of the upgraded algorithm on benchmark problems.

Introduction

In modern data mining, identifying frequent itemsets is a fundamental task. However, as data moves from simple flat files to complex multi-relational databases—such as molecular structures or social networks—the number of frequent patterns can explode exponentially. To address this, researchers utilize closed sets. A set is considered "closed" if none of its supersets share the same frequency in the database, allowing for a significant reduction in the number of patterns while preserving all essential information.

Despite their utility, defining closed sets in relational logic is non-trivial. Different semantic rules for pattern matching impact the efficiency and feasibility of mining algorithms. This paper explores these semantic choices and investigates whether the state-of-the-art Linear time Closed pattern Miner (LCM) algorithm can be effectively upgraded for multi-relational environments.

Methodology

The authors propose two primary algorithmic adaptations of LCM:

  1. RelLCM1 (Learning from Multiple Interpretations): Tailored for datasets where each entry is an independent relational structure (e.g., a collection of molecules). It employs the Least General Generalization (lgg) to define closures. Due to the nature of these closures, RelLCM1 requires a memory-intensive lookup table to avoid duplicate outputs.
  2. RelLCM2 (Single Interpretation): Designed for large, interconnected datasets (e.g., citation graphs), RelLCM2 introduces a mathematical framework involving "Core Prefixes" and "Prefix Preserving Closure Extensions." This allows the algorithm to traverse the search space as a tree, ensuring each closed pattern has a unique parent and eliminating the need for memory-heavy duplicate tracking.

The study also compares standard θ-subsumption logic matching against Object Identity (OI) subsumption, where distinct variables must correspond to distinct real-world objects.

Experimental Results

The algorithms were evaluated on the NCTRER (Estrogen Receptor Binding) and Cora (computer science citation network) datasets.

Efficiency and Compression

RelLCM2 demonstrated high scalability, processing thousands of patterns efficiently. A key metric is the Compression Factor (CF%), which represents the percentage of frequent patterns that are redundant and thus excluded from the closed set output. In the NCTRER dataset, compression factors reached as high as 87.6%.

Table 1: Performance of RelLCM2 and RelLCM2-OI on the NCTRER dataset across varying minimum frequencies.

Impact of Semantics

The choice of semantics significantly affects performance. As shown in the experimental data, using Object Identity (OI) semantics substantially reduces the number of frequent and closed sets compared to standard θ-subsumption. This leads to faster runtimes while maintaining meaningful relational insights.

Table 2: Scalability of RelLCM2 and RelLCM2-OI on the NCTRER dataset as the number of variables (Vars) increases.

Discussion and Conclusion

The investigation reveals that semantic choices in relational logic are not merely theoretical; they dictate the fundamental complexity and scalability of mining algorithms. While RelLCM2 offers a memory-efficient solution for single-interpretation data, challenges remain. Relational search spaces can be infinite, necessitating constraints like "range-restriction" and "depth bounds" on the number of atoms in a pattern. Future work will focus on integrating more complex syntactic constraints while preserving the efficient "unique parent" property of the LCM framework.

Summary updated

Abstract

We investigate the problem of mining closed sets in multi-relational databases. Previous work introduced different semantics and associated algorithms for mining closed sets in multirelational databases. However, insight into the implications of semantic choices and the relationships among them was still lacking. Our investigation shows that the semantic choices are important because they imply different properties, which in turn affect the range of algorithms that can mine for such sets. Of particular interest is the question whether the seminal LCM algorithm by Uno et al. can be upgraded towards multi-relational problems. LCM is attractive since its run time is linear in the number of closed sets and it does not need to store outputs in order to avoid duplicates. We provide a positive answer to this question for some of the semantic choices, and report on experiments that evaluate the scalability and applicability of the upgraded algorithm on benchmark problems.
BibTeX
@inproceedings{garriga2007mining,
  author = {Gemma C. Garriga and Roni Khardon and Luc De Raedt},
  title = {{On Mining Closed Sets in Multi-Relational Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=SJWKB4zOWH},
}
Figure