Clustering via Matrix Powering

Summary: Proposes a clustering algorithm that uses only matrix powering (viewed as random walks) to partition points from pairwise similarity matrices. Under a planted-mixture model, a single squaring suffices for provable recovery and larger exponents provably degrade performance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1316
Venue: PODS
Year: 2004
Pagerank: 6.3754336e-05
Overall Rank: 4,187 | 70.88%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Hanson Zhou
2. David Woodruff

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,257	Approximation Algorithms for Co-Clustering	2008	PODS	4.3690661e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
428	Latent Semantic Indexing: A Probabilistic Analysis	1998	PODS	0.00023512226

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,323	CRD: Fast Co-clustering on Large Datasets Utilizing Sampling-Based Matrix Decomposition	2008	SIGMOD	7.2224696e-05
3,636	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB	6.8976555e-05
3,141	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB	7.4829448e-05
8,168	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB	4.5701004e-05
6,019	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB	5.2415551e-05
8,535	Biclustering and Boolean Matrix Factorization in Data Streams	2020	VLDB	4.4937074e-05
313	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB	0.00028097557
4,090	Finding Near Neighbors Through Cluster Pruning	2007	PODS	6.4577834e-05
4,817	Clustering by Pattern Similarity in Large Data Sets	2002	SIGMOD	5.8987807e-05
9,257	Approximation Algorithms for Co-Clustering	2008	PODS	4.3690661e-05