An expressive dissimilarity measure for relational clustering using
  neighbourhood trees
  Clustering is an underspecified task: there are no universal criteria for
what makes a good clustering. This is especially true for relational data,
where similarity can be based on the features of individuals, the relationships
between them, or a mix of both. Existing methods for relational clustering have
strong and often implicit biases in this respect. In this paper, we introduce a
novel similarity measure for relational data. It is the first measure to
incorporate a wide variety of types of similarity, including similarity of
attributes, similarity of relational context, and proximity in a hypergraph. We
experimentally evaluate how using this similarity affects the quality of
clustering on very different types of datasets. The experiments demonstrate
that (a) using this similarity in standard clustering methods consistently
gives good results, whereas other measures work well only on datasets that
match their bias; and (b) on most datasets, the novel similarity outperforms
even the best among the existing ones.
