Publication

Possibility results for graph clustering: A novel consistency axiom

Journal Article (2022)

Journal

Pattern Recognition

Pages

108687

Volume

128

Doc link

https://doi.org/10.1016/j.patcog.2022.108687

File

Download the digital copy of the doc pdf document

Authors

Abstract

Kleinberg introduced three natural clustering properties, or axioms, and showed they cannot be simultaneously satisfied by any clustering algorithm. We present a new clustering property, Monotonic Consistency, which avoids the well-known problematic behaviour of Kleinberg’s Consistency axiom, and the impossibility result. Namely, we describe a clustering algorithm, Morse Clustering, inspired by Morse Theory in Differential Topology, which satisfies Kleinberg’s original axioms with Consistency replaced by Monotonic Consistency. Morse clustering uncovers the underlying flow structure on a set or graph and returns a partition into trees representing basins of attraction of critical vertices. We also generalise Kleinberg’s axiomatic approach to sparse graphs, showing an impossibility result for Consistency, and a possibility result for Monotonic Consistency and Morse clustering.

Categories

pattern recognition.

Author keywords

Data clustering, Graph clustering, Axiomatic clustering, Morse theory, Morse flow

Scientific reference

F. Strazzeri and Rubén J. Sánchez-García. Possibility results for graph clustering: A novel consistency axiom. Pattern Recognition, 128: 108687, 2022.