# Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach

arXiv: https://arxiv.org/abs/2108.07247 · HTML: https://mlsanity.com/paper/2108.07247/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 59 references that are in the map.
- First posted on arXiv 16 Aug 2021.

## Builds on (most cited first, 9 of 9)

- [Signal Processing on Directed Graphs](https://mlsanity.com/paper/2008.00586/) (2020)
- [Robust Hierarchical Clustering](https://mlsanity.com/paper/1401.0247/) (2014)
- [Axioms for graph clustering quality functions](https://mlsanity.com/paper/1308.3383/) (2013)
- [Axiomatic Construction of Hierarchical Clustering in Asymmetric Networks](https://mlsanity.com/paper/1301.7724/) (2013)
- [Hierarchical Clustering of Asymmetric Networks](https://mlsanity.com/paper/1607.06294/) (2016)
- [Hierarchical Quasi-Clustering Methods for Asymmetric Networks](https://mlsanity.com/paper/1404.4655/) (2014)
- [Admissible Hierarchical Clustering Methods and Algorithms for Asymmetric Networks](https://mlsanity.com/paper/1607.06335/) (2016)
- [Convergence of Hierarchical Clustering and Persistent Homology Methods on Directed Networks](https://mlsanity.com/paper/1711.04211/) (2017)
- [Motivic clustering schemes for directed graphs](https://mlsanity.com/paper/2001.00278/) (2020)

## Abstract (arXiv)

We provide a complete taxonomic characterization of robust hierarchical clustering methods for directed networks following an axiomatic approach. We begin by introducing three practical properties associated with the notion of robustness in hierarchical clustering: linear scale preservation, stability, and excisiveness. Linear scale preservation enforces imperviousness to change in units of measure whereas stability ensures that a bounded perturbation in the input network entails a bounded perturbation in the clustering output. Excisiveness refers to the local consistency of the clustering outcome. Algorithmically, excisiveness implies that we can reduce computational complexity by only clustering a subset of our data while theoretically guaranteeing that the same hierarchical outcome would be observed when clustering the whole dataset. In parallel to these three properties, we introduce the concept of representability, a generative model for describing clustering methods through the specification of their action on a collection of networks. Our main result is to leverage this generative model to give a precise characterization of all robust -- i.e., excisive, linear scale preserving, and stable -- hierarchical clustering methods for directed networks. We also address the implementation of our methods and describe an application to real data.