Possibility results for graph clustering: A novel consistency axiom
This work addresses theoretical limitations in graph clustering for researchers in machine learning and data analysis, offering a novel axiomatic framework.
The paper tackles the impossibility of satisfying Kleinberg's clustering axioms by introducing a new axiom, Monotonic Consistency, and proposes Morse Clustering, which satisfies the original axioms with this replacement, and extends the analysis to sparse graphs.
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.