# Sublinear-Time Clustering Oracle for Signed Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 28 Jun 2022.

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

- [SPONGE: A generalized eigenproblem for clustering signed networks](https://mlsanity.com/paper/1904.08575/) (2019)
- [Discovering Polarized Communities in Signed Networks](https://mlsanity.com/paper/1910.02438/) (2019)
- [Clustering Signed Networks with the Geometric Mean of Laplacians](https://mlsanity.com/paper/1701.00757/) (2017)
- [Spectral Clustering of Signed Graphs via Matrix Power Means](https://mlsanity.com/paper/1905.06230/) (2019)
- [Finding large balanced subgraphs in signed networks](https://mlsanity.com/paper/2002.00775/) (2020)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Regularized spectral methods for clustering signed networks](https://mlsanity.com/paper/2011.01737/) (2020)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs](https://mlsanity.com/paper/1904.09710/) (2019)
- [Spectral Clustering Oracles in Sublinear Time](https://mlsanity.com/paper/2101.05549/) (2021)
- [Prediction and Clustering in Signed Networks: A Local to Global Perspective](https://mlsanity.com/paper/1302.5145/) (2013)
- [A Correlation Clustering Approach to Link Classification in Signed Networks -- Full Version --](https://mlsanity.com/paper/1301.4769/) (2013)
- [Cheeger constants, structural balance, and spectral clustering analysis for signed graphs](https://mlsanity.com/paper/1411.3530/) (2014)
- [Searching for polarization in signed graphs: a local spectral approach](https://mlsanity.com/paper/2001.09410/) (2020)

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

- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)

## Abstract (arXiv)

Social networks are often modeled using signed graphs, where vertices correspond to users and edges have a sign that indicates whether an interaction between users was positive or negative. The arising signed graphs typically contain a clear community structure in the sense that the graph can be partitioned into a small number of polarized communities, each defining a sparse cut and indivisible into smaller polarized sub-communities. We provide a local clustering oracle for signed graphs with such a clear community structure, that can answer membership queries, i.e., "Given a vertex v, which community does v belong to?", in sublinear time by reading only a small portion of the graph. Formally, when the graph has bounded maximum degree and the number of communities is at most O(log n), then with tildeO(√noperatornamepoly(1/varepsilon)) preprocessing time, our oracle can answer each membership query in tildeO(√noperatornamepoly(1/varepsilon)) time, and it correctly classifies a (1-varepsilon)-fraction of vertices w.r.t. a set of hidden planted ground-truth communities. Our oracle is desirable in applications where the clustering information is needed for only a small number of vertices. Previously, such local clustering oracles were only known for unsigned graphs; our generalization to signed graphs requires a number of new ideas and gives a novel spectral analysis of the behavior of random walks with signs. We evaluate our algorithm for constructing such an oracle and answering membership queries on both synthetic and real-world datasets, validating its performance in practice.