Learning Bayes Nets for Relational Data with Link Uncertainty

Abstract. We present an algorithm for learning correlations among link types and node attributes in relational data that represent complex net-works. The link correlations are represented in a Bayes net structure. This provides a succinct graphical way to display relational statisti-cal patterns and support powerful probabilistic inferences. The current state of the art algorithm for learning relational Bayes nets captures only correlations among entity attributes given the existence of links among entities. The models described in this paper capture a wider class of cor-relations that involve uncertainty about the link structure. Our base line method learns a Bayes net from join tables directly. This is a statisti-cally powerful procedure that finds many correlations, but does not scale well to larger datasets. We compare join table search with a hierarchical search strategy.