# flow-based clustering and spectral clustering: a comparison

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 20 Jun 2022.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Local Graph Clustering with Network Lasso](https://mlsanity.com/paper/2004.12199/) (2020)
- [Semi-supervised Learning in Network-Structured Data via Total Variation Minimization](https://mlsanity.com/paper/1901.09838/) (2019)
- [Localized Linear Regression in Networked Data](https://mlsanity.com/paper/1903.11178/) (2019)
- [On the Duality between Network Flows and Network Lasso](https://mlsanity.com/paper/1910.01805/) (2019)
- [Complex Networks, Communities and Clustering: A survey](https://mlsanity.com/paper/1503.06277/) (2015)
- [Social significance of community structure: Statistical view](https://mlsanity.com/paper/1503.08039/) (2015)
- [The Network Nullspace Property for Compressed Sensing of Big Data over Networks](https://mlsanity.com/paper/1705.04379/) (2017)
- [Clustering in Partially Labeled Stochastic Block Models via Total Variation Minimization](https://mlsanity.com/paper/1911.00958/) (2019)

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

- [Plug In and Learn: Federated Intelligence over a Smart Grid of Models](https://mlsanity.com/paper/2302.04363/) (2023)

## Abstract (arXiv)

We propose and study a novel graph clustering method for data with an intrinsic network structure. Similar to spectral clustering, we exploit an intrinsic network structure of data to construct Euclidean feature vectors. These feature vectors can then be fed into basic clustering methods such as k-means or Gaussian mixture model (GMM) based soft clustering. What sets our approach apart from spectral clustering is that we do not use the eigenvectors of a graph Laplacian to construct the feature vectors. Instead, we use the solutions of total variation minimization problems to construct feature vectors that reflect connectivity between data points. Our motivation is that the solutions of total variation minimization are piece-wise constant around a given set of seed nodes. These seed nodes can be obtained from domain knowledge or by simple heuristics that are based on the network structure of data. Our results indicate that our clustering methods can cope with certain graph structures that are challenging for spectral clustering methods.