Mining EL Bases with Adaptable Role Depth

Ricardo Guimarães, Ana Ozaki, Cosimo Persia, Baris SertkayaAAAI 2021 · DOI

Introduction

In Knowledge Representation, extracting logical rules from existing data—such as knowledge graphs or databases—is a fundamental task for building and maintaining ontologies. This process typically leverages Description Logics (DL) for formal rule expression and Formal Concept Analysis (FCA) to identify underlying dependencies. However, mining rules in the lightweight logic $\mathcal{EL}^\perp$ faces a significant hurdle when data contains cyclic relationships.

The Challenge of Cycles

When a dataset includes cycles—for instance, a city being part of a region that in turn contains the city—the number of possible concept expressions can become infinite. Traditional approaches to this problem often fall into two camps:

  1. Greatest Fix-Point Semantics ($\mathcal{EL}^\perp_{gfp}$): While mathematically robust, these produce rules that are difficult for humans to interpret and computationally expensive for machines to process.
  2. Fixed Role Depth: By capping the length of relationship chains, the search space remains finite. However, this arbitrary limit risks missing critical rules that exist beyond the chosen depth.
Figure 1: Illustrative cyclic relationships in a knowledge graph context, showing dependencies between cities, regions, and governing parties.

Proposed Solution: Adaptable Role Depth

The authors introduce a strategy that avoids the pitfalls of fixed limits by making the role depth adaptable. Instead of a global constant, the depth is determined by the local topology of the data graph.

The MVF Metric

The core of this approach is a new graph-theoretic measure called Maximum Vertices From (MVF). For any given point in a data graph, the MVF is the maximum number of distinct vertices a walk can visit starting from that point. This metric provides a tighter, more structural bound than simple reachability, specifically addressing how cycles "unravel" into tree structures during rule mining.

Figure 3: The process of unravelling a cyclic relationship (i) into tree structures of increasing role depth (ii and iii).

Efficient Computation

To ensure the method is practical for large-scale data, the authors developed a linear-time algorithm ($O(|V| + |E|)$) to compute MVF. The algorithm identifies Strongly Connected Components (SCCs) and then calculates the longest path in the resulting Directed Acyclic Graph (DAG).

Key Insights and Results

The primary breakthrough is the realization that the depth required to describe a concept should not be a global constraint. By treating simple tree structures and complex cyclic webs differently, the algorithm captures the essence of cyclic data within standard, human-readable $\mathcal{EL}^\perp$.

The authors prove that their strategy produces a "base" (a set of rules) that is:

  • Sound: Every mined rule is true within the provided data.
  • Complete: Every rule true in the data is logically entailed by the base.

While the role depth can theoretically grow exponentially in the worst case, the MVF-based approach ensures that the depth used is the minimal necessary to capture the specific structure of the input graph.

Future Directions

While the current framework provides a sound and complete base, the authors note that the resulting set of rules is not necessarily minimal and may contain redundancies. Future work will focus on compressing these bases and integrating "support" and "confidence" metrics to handle the noise and incompleteness inherent in real-world knowledge graphs like DBpedia. Implementation on large-scale benchmarks is also planned to further validate practical performance.

Summary updated

BibTeX
@inproceedings{guimaraes2021mining,
  author = {Ricardo Guimarães and Ana Ozaki and Cosimo Persia and Baris Sertkaya},
  title = {{Mining EL Bases with Adaptable Role Depth}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i7.16790},
}

Loading related content...

Figure