Abstract
Learning Bayesian Network (BN) structures from multi-relational databases is challenging because traditional scoring metrics fail to account for varying local sample sizes. This paper introduces a novel "normalized gain function" and provides the first theoretical proof of local consistency for relational structure learning, ensuring convergence to optimal models as data scales.
Introduction
In traditional machine learning, data is typically assumed to be independent and identically distributed (i.i.d.), represented in a single flat table. However, real-world enterprise data is predominantly multi-relational, stored across multiple tables with complex inter-relationships. Learning the structure of a Bayesian Network from such data is difficult because standard model selection scores, such as AIC or BIC, break down when the "local sample size"—the number of ways a relationship can be instantiated—changes with the addition of new edges.
The Challenge of Relational Structure Learning
Relational data, such as the schema involving users, movies, and ratings shown below, presents a "scaling trap."
In this setting, adding a parent to a node can increase the number of possible "groundings" by orders of magnitude. A single-model score cannot account for this shifting baseline, often leading to models that are either overly sparse (missing key correlations) or overly dense (adding redundant complexity).
The Normalized Gain Function
To address this, the authors propose upgrading standard i.i.d. BN scores using a Normalized Gain Function, $\Delta S(G, G^+, D)$. Rather than calculating an absolute score for a single model, this function measures the improvement when transitioning from a graph $G$ to an alternative graph $G^+$.
The methodology involves:
- Rescaling Statistics: Sufficient statistics of the simpler graph $G$ are rescaled to match the local sample size of the more complex graph $G^+$.
- Normalization: The gain is divided by the local sample size, effectively measuring the "gain per instance."
The authors mathematically prove that if an i.i.d. score is locally consistent, its upgraded relational version remains locally consistent. This theoretical milestone guarantees that the algorithm will find the "true" data-generating distribution given sufficient data.
Empirical Evaluation
The method was evaluated on six benchmark relational databases, including IMDb, Movielens, and Financial datasets.
On the IMDb dataset, which contains over 1.3 million tuples, standard "Count Scores" produced an overly conservative model with only 69 parameters. In contrast, the Normalized Gain Function identified a model with 14,450 parameters that provided a significantly better fit. Furthermore, by using magnification factors to simulate larger datasets, the authors demonstrated that the Kullback-Leibler Divergence (KLD) for their method approaches zero, empirically confirming their consistency proof.
Conclusion and Future Work
The normalized gain approach provides a robust framework for learning Bayesian Networks from complex, multi-relational data. While currently focused on simple functors, future work will extend this to complex terms like aggregate functions (e.g., average ratings) and explore its application to other statistical-relational models such as Markov Logic Networks (MLNs).
Summary updated