Axioms for clustering simple unweighted graphs: No impossibility result

In 2002, Kleinberg proposed three axioms for distance-based clustering, and proved that it was impossible for a clustering method to satisfy all three. While there has been much subsequent work examining and modifying these axioms for distance-based clustering, little work has been done to explore axioms relevant to the graph partitioning problem when the graph is unweighted and given without a distance matrix. Here, we propose and explore axioms for graph partitioning for this case, including modifications of Kleinberg’s axioms and three others: two axioms relevant to the “Resolution Limit” and one addressing well-connectedness. We prove that clustering under the Constant Potts Model satisfies all the axioms, while Modularity clustering and iterative k-core both fail many axioms we pose. These theoretical properties of the clustering methods are relevant both for theoretical investigation as well as to practitioners considering which methods to use for their domain science studies.Author summary: In 2002, Kleinberg proposed three axioms for distance-based clustering and proved that it was not possible for any clustering method to simultaneously satisfy all three axioms. Here, we examine these axioms in the context where the input network is given without any pairwise distance matrix and is instead a simple unweighted graph. For this case we propose corresponding axioms, and we include three additional axioms, two related to the resolution limit and the other related to well-connectedness. We establish that some methods, such as optimizing under the Constant Potts Model, satisfy all the axioms we pose, but that others (notably clustering under the Modularity optimization problem) fail to satisfy some of these axioms. This study sheds light on limitations of existing clustering methods.