Clustering via matrix powering

ABSTRACT

Given a set of n points with a matrix of pairwise similarity measures, one would like to partition the points into clusters so that similar points are together and different ones apart. We present an algorithm requiring only matrix powering that performs well in practice and bears an elegant interpretation in terms of random walks on a graph. Under a certain mixture model involving planting a partition via randomized rounding of tailored matrix entries, the algorithm can be proven effective for only a single squaring. It is shown that the clustering performance of the algorithm degrades with larger values of the exponent, thus revealing that a single squaring is optimal.

REFERENCES

• 1: Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
• 2: Sanjeev Arora , Prabhakar Raghavan , Satish Rao, Approximation schemes for Euclidean k-medians and related problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.106-113, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276718]
• 3: Y. Azar, A. Fiat, A. Karlin, and F. McSherry. Data mining through spectral analysis. In IEEE Symposium on Foundations of Computer Science, 2001.
• 4: Avrim Blum , Joel Spencer, Coloring random and semi-random k-colorable graphs, Journal of Algorithms, v.19 n.2, p.204-234, Sept. 1995 [doi>10.1006/jagm.1995.1034]
• 5: R. Boppana. Eigenvalues and graph bisection: An average-case analysis. In IEEE Symposium on Foundations of Computer Science, pages 280--285, 1985.
• 6: Moses Charikar , Sudipto Guha, Improved Combinatorial Algorithms for the Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.378, October 17-18, 1999
• 7: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 8: A. Condon and R. Karp. Algorithms for graph partitioning on the planted partition model. In Random Structure and Algorithms, 1999.
• 9: D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions, 1990.
• 10: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 11: Z. Drezner, Facility Location: A survey of Applications and Methods. Springer-Verlag, 1995.
• 12: P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
• 13: M. Dyer and A. M. Frieze. A simple heuristic for the p-center problem. Operations Research Letters, 3:285--288, 1985.
• 14: D. S. Hochbaum and D. B. Shmoys. A best possible approximation algorithm for the k-center problem. Math. Oper. Res., 10:180--184, 1985.
• 15: Kamal Jain , Vijay V. Vazirani, Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.2, October 17-18, 1999
• 16: M. Jambu and M. O. Lebeaux. Cluster Analysis and Data Analysis. North-Holland, New York, 1983.
• 17: M. Jerrum and G. Sorkin. Simulated annealing for graph bisection. In IEEE Symposium on Foundations of Computer Science, 1993.
• 18: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 19: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
• 20: L. Lovasz. Random walks on graphs: a survey. In Combinatorics, pages 1--46, 1993.
• 21: F. McSherry, Spectral Partitioning of Random Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.529, October 14-17, 2001
• 22: R. Ostrovsky , Y. Rabani, Polynomial time approximation schemes for geometric k-clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.349, November 12-14, 2000
• 23: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 24: M. Szummer and T. Jaakkola. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems, volume 14, 2001.
• 25: Satu Virtanen, Clustering the Chilean Web, Proceedings of the First Conference on Latin American Web Congress, p.229, November 10-12, 2003