2021/08/16 by Gunnar Carlsson, Carlsson, Gunnar, Facundo Mémoli +3
Computer Science · Physics and Astronomy · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.2108.07247
openalex publication_date 2021/08/16 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We provide a complete taxonomic characterization of robust hierarchical\nclustering methods for directed networks following an axiomatic approach. We\nbegin by introducing three practical properties associated with the notion of\nrobustness in hierarchical clustering: linear scale preservation, stability,\nand excisiveness. Linear scale preservation enforces imperviousness to change\nin units of measure whereas stability ensures that a bounded perturbation in\nthe input network entails a bounded perturbation in the clustering output.\nExcisiveness refers to the local consistency of the clustering outcome.\nAlgorithmically, excisiveness implies that we can reduce computational\ncomplexity by only clustering a subset of our data while theoretically\nguaranteeing that the same hierarchical outcome would be observed when\nclustering the whole dataset. In parallel to these three properties, we\nintroduce the concept of representability, a generative model for describing\nclustering methods through the specification of their action on a collection of\nnetworks. Our main result is to leverage this generative model to give a\nprecise characterization of all robust -- i.e., excisive, linear scale\npreserving, and stable -- hierarchical clustering methods for directed\nnetworks. We also address the implementation of our methods and describe an\napplication to real data.\n