Data Clustering with a Relational Push-Pull Model

Relational data clustering is the task of grouping data objects together when both features and relations between objects are present. I present a new generative model for relational data in which relations between objects can have either a binding or separating effect. For example, with a group of students separated into gender clusters, a "dating" relation would appear most frequently between the clusters, but a "roommate" relation would appear more often within clusters. In visualizing these relations, one can imagine that the "dating" relation effectively pushes clusters apart, while the "roommate" relation pulls clusters into tighter formations. I use simulated annealing to search for optimal values of the unknown model parameters, where the objective function is a Bayesian score derived from the generative model. Specifically, I show that an assumption that relations should most frequently appear within clusters can lead to poor performance, using experiments with artificial data and two real-world data sets: a Hollywood actor database and an ecological food web. The experiments show that push-type relations do exist, and therefore the tendency of relations to pull clusters together cannot be assumed in general.