Graph Pattern-based Association Rules Evaluated Under No-repeated-anything Semantics in the Graph Transactional Setting
This work addresses the need for more effective association rule mining in graph data, such as RDF graphs, by extending beyond existing formalisms, though it appears incremental as it builds on prior graph and relational rule frameworks.
The paper tackles the problem of evaluating graph pattern-based association rules (GPARs) for directed labeled multigraphs, introducing a framework that supports generative and evaluative tasks under no-repeated-anything semantics, and derives probabilistic metrics like confidence and lift while analyzing their properties compared to classical itemset-based methods.
We introduce graph pattern-based association rules (GPARs) for directed labeled multigraphs such as RDF graphs. GPARs support both generative tasks, where a graph is extended, and evaluative tasks, where the plausibility of a graph is assessed. The framework goes beyond related formalisms such as graph functional dependencies, graph entity dependencies, relational association rules, graph association rules, multi-relation and path association rules, and Horn rules. Given a collection of graphs, we evaluate graph patterns under no-repeated-anything semantics, which allows the topology of a graph to be taken into account more effectively. We define a probability space and derive confidence, lift, leverage, and conviction in a probabilistic setting. We further analyze how these metrics relate to their classical itemset-based counterparts and identify conditions under which their characteristic properties are preserved.