Data Clustering with a Relational Push-Pull Model

Abstract

We present a new generative model for relational data in which relations between objects can have ei- ther a binding or a separating effect. For example, in 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 rela- tions, one can imagine that the "dating" relation effec- tively pushes clusters apart, while the "roommate" re- lation pulls clusters into tighter formations. A unique aspect of the model is that an edge's existence is depen- dent on both the clusters to which the two connected objects belong and the features of the connected objects. We use simulated annealing to search for optimal val- ues of the unknown model parameters, where the ob- jective function is a Bayesian score derived from the generative model. Results describing the performance of the model are shown with artificial data as well as a subset of the Internet Movie Database. The results show that discovering a relation's tendency to either push or pull is critical to discovering a consistent clus- tering.