# T-Stochastic Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 58 references that are in the map.
- First posted on arXiv 4 Sep 2023.

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

- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Construction of the Literature Graph in Semantic Scholar](https://mlsanity.com/paper/1805.02262/) (2018)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Vintage Factor Analysis with Varimax Performs Statistical Inference](https://mlsanity.com/paper/2004.05387/) (2020)
- [Hierarchical community detection by recursive partitioning](https://mlsanity.com/paper/1810.01509/) (2018)
- [Estimating Graph Dimension with Cross-validated Eigenvalues](https://mlsanity.com/paper/2108.03336/) (2021)
- [Consistency of Spectral Clustering on Hierarchical Stochastic Block Models](https://mlsanity.com/paper/2004.14531/) (2020)
- [Spectral Top-Down Recovery of Latent Tree Models](https://mlsanity.com/paper/2102.13276/) (2021)

## Built on by (most cited first, 1 of 1)

- [Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding](https://mlsanity.com/paper/2603.11965/) (2026)

## Abstract (arXiv)

Previous statistical approaches to hierarchical clustering for social network analysis all construct an "ultrametric" hierarchy. While the assumption of ultrametricity has been discussed and studied in the phylogenetics literature, it has not yet been acknowledged in the social network literature. We show that "non-ultrametric structure" in the network introduces significant instabilities in the existing top-down recovery algorithms. To address this issue, we introduce an instability diagnostic plot and use it to examine a collection of empirical networks. These networks appear to violate the "ultrametric" assumption. We propose a deceptively simple and yet general class of probabilistic models called mathbbT-Stochastic Graphs which impose no topological restrictions on the latent hierarchy. To illustrate this model, we propose six alternative forms of hierarchical network models and then show that all six are equivalent to the mathbbT-Stochastic Graph model. These alternative models motivate a novel approach to hierarchical clustering that combines spectral techniques with the well-known Neighbor-Joining algorithm from phylogenetic reconstruction. We prove this spectral approach is statistically consistent.