Probabilistic classification and clustering in relational data

Supervised and unsupervised learning methods have tradi-tionally focused on data consisting of independent instances of a single type. However, many real-world domains are best described by relational models in which instances of multiple types are related to each other in complex ways. For exam-ple, in a scientific paper domain, papers are related to each other via citation, and are also related to their authors. In this case, the label of one entity (e.g., the topic of the paper) is of-ten correlated with the labels of related entities. We propose a general class of models for classification and clustering in re-lational domains that capture probabilistic dependencies be-tween related instances. We show how to learn such models efficiently from data. We present empirical results on two real world data sets. Our experiments in a transductive clas-sification setting indicate that accuracy can be significantly improved by modeling relational dependencies. Our algo-rithm automatically induces a very natural behavior, where our knowledge about one instance helps us classify related ones, which in turn help us classify others. In an unsuper-vised setting, our models produced coherent clusters with a very natural interpretation, even for instance types that do not have any attributes.