Locally Consistent Bayesian Network Scores for Multi-Relational Data

Oliver Schulte, Sajjad Gholami

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."

Example of a multi-relational schema involving User, Rating, and Movie tables.

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:

  1. Rescaling Statistics: Sufficient statistics of the simpler graph $G$ are rescaled to match the local sample size of the more complex graph $G^+$.
  2. 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.

A relational Bayesian Network structure representing dependencies between ratings and user attributes.

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

Abstract

An important task for relational learning is Bayesian network (BN) structure learning. A fundamental component of structure learning is a model selection score that measures how well a model fits a dataset. We describe a new method that upgrades for multi-relational databases, a log-linear BN score designed for single-table i.i.d. data. Chickering and Meek showed that for i.i.d. data, standard BN scores are locally consistent, meaning that their maxima converge to an optimal model, that represents the data generating distribution {\em and} contains no redundant edges. Our main theorem establishes that if a model selection score is locally consistent for i.i.d. data, then our upgraded gain function is locally consistent for relational data as well. To our knowledge this is the first consistency result for relational structure learning. A novel aspect of our approach is employing a {\em gain function} that compares two models: a current vs. an alternative BN structure. In contrast, previous approaches employed a score that is a function of a single model only. Empirical evaluation on six benchmark relational databases shows that our gain function is also practically useful: On realistic size data sets, it selects informative BN structures with a better data fit than those selected by baseline single-model scores.
BibTeX
@inproceedings{schulte2017locally,
  author = {Oliver Schulte and Sajjad Gholami},
  title = {{Locally Consistent Bayesian Network Scores for Multi-Relational Data}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/375},
}
Figure