# Blind Extraction of Equitable Partitions from Graph Signals

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 10 Mar 2022.

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [Blind Community Detection from Low-rank Excitations of a Graph Filter](https://mlsanity.com/paper/1809.01485/) (2018)
- [Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis](https://mlsanity.com/paper/2109.13573/) (2021)
- [Graph partitions and cluster synchronization in networks of oscillators](https://mlsanity.com/paper/1608.04283/) (2016)
- [Blind identification of stochastic block models from dynamical observations](https://mlsanity.com/paper/1905.09107/) (2019)
- [Exact Blind Community Detection from Signals on Multiple Graphs](https://mlsanity.com/paper/2001.10944/) (2020)
- [Blind Inference of Centrality Rankings from Graph Signals](https://mlsanity.com/paper/1910.10846/) (2019)
- [Estimating Centrality Blindly from Low-pass Filtered Graph Signals](https://mlsanity.com/paper/1910.13137/) (2019)

## Abstract (arXiv)

Finding equitable partitions is closely related to the extraction of graph symmetries and of interest in a variety of applications context such as node role detection, cluster synchronization, consensus dynamics, and network control problems. In this work we study a blind identification problem in which we aim to recover an equitable partition of a network without the knowledge of the network's edges but based solely on the observations of the outputs of an unknown graph filter. Specifically, we consider two settings. First, we consider a scenario in which we can control the input to the graph filter and present a method to extract the partition inspired by the well known Weisfeiler-Lehman (color refinement) algorithm. Second, we generalize this idea to a setting where only observe the outputs to random, low-rank excitations of the graph filter, and present a simple spectral algorithm to extract the relevant equitable partitions. Finally, we establish theoretical bounds on the error that this spectral detection scheme incurs and perform numerical experiments that illustrate our theoretical results and compare both algorithms.