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: 1315
Venue: PODS
Year: 2004
Pagerank: 5.9728946e-05
Overall Rank: 6,110 | 58.09%
DOI: 10.1145/1055558.1055579

Incoming Non-self Citations Over Time

Authors

1. Hanson Zhou (Massachusetts Institute of Technology)
2. David Woodruff (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{zhou_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Clustering via Matrix Powering}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055579},
        doi = {10.1145/1055558.1055579},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Zhou, Hanson and Woodruff, David},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,402	Approximation Algorithms for Co-Clustering	2008	PODS	5.2755515e-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
1,119	Latent Semantic Indexing: A Probabilistic Analysis	1998	PODS	0.00012097985

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,934	CRD: Fast Co-clustering on Large Datasets Utilizing Sampling-Based Matrix Decomposition	2008	SIGMOD
2	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
3	2,567	ClusterJoin: A Similarity Joins Framework using Map-Reduce	2014	VLDB
4	8,778	Evaluating Clustering in Subspace Projections of High Dimensional Data	2009	VLDB
5	6,974	Uncertain Centroid based Partitional Clustering of Uncertain Data	2012	VLDB
6	364	Graph Clustering Based on Structural/Attribute Similarities	2009	VLDB
7	8,739	Biclustering and Boolean Matrix Factorization in Data Streams	2020	VLDB
8	4,657	Finding Near Neighbors Through Cluster Pruning	2007	PODS
9	4,812	Clustering by Pattern Similarity in Large Data Sets	2002	SIGMOD
10	9,402	Approximation Algorithms for Co-Clustering	2008	PODS