nips nips2009 nips2009-9 nips2009-9-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Samuel R. Bulò, Marcello Pelillo
Abstract: Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a user-defined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we provide a radically different perspective to the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. Specifically, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player “clustering game”, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. From the computational viewpoint, we show that the problem of finding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques.
[1] S. Agarwal, K. Branson, and S. Belongie. Higher order learning with graphs. In Int. Conf. on Mach. Learning, volume 148, pages 17–24, 2006.
[2] S. Agarwal, J. Lim, L. Zelnik-Manor, P. Perona, D. Kriegman, and S. Belongie. Beyond pairwise clustering. In IEEE Conf. Computer Vision and Patt. Recogn., volume 2, pages 838– 845, 2005.
[3] L. E. Baum and J. A. Eagon. An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bull. Amer. Math. Soc., 73:360–363, 1967. 8
[4] L. E. Baum, T. Petrie, G. Soules, and N. Weiss. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Ann. Math. Statistics, 41:164– 171, 1970.
[5] P. Belhumeur and D. Kriegman. What is the set of images of an object under all possible lighting conditions. Int. J. Comput. Vision, 28(3):245–260, 1998.
[6] M. Bolla. Spectral, euclidean representations and clusterings of hypergraphs. Discr. Math., 117:19–39, 1993.
[7] M. Broom., C. Cannings, and G. T. Vickers. Multi-player matrix games. Bull. Math. Biology, 59(5):931–952, 1997.
[8] A. S. Georghiades., P. N. Belhumeur, and D. J. Kriegman. From few to many: illumination cone models for face recognition under variable lighting and pose. IEEE Trans. Pattern Anal. Machine Intell., 23(6):643–660, 2001.
[9] D. Gibson, J. M. Kleinberg, and P. Raghavan. VLDB, chapter Clustering categoral data: An approach based on dynamical systems., pages 311–322. Morgan Kaufmann Publishers Inc., 1998.
[10] T. Hu and K. Moerder. Multiterminal flows in hypergraphs. In T. Hu and E. S. Kuh, editors, VLSI circuit layout: theory and design, pages 87–93. 1985.
[11] G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. VLSI Design, 11(3):285– 300, 2000.
[12] K. C. Lee, J. Ho, and D. Kriegman. Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans. Pattern Anal. Machine Intell., 27(5):684–698, 2005.
[13] D. G. Luenberger. Linear and nonlinear programming. Addison Wesley, 1984.
[14] M. Pavan and M. Pelillo. Dominant sets and pairwise clustering. IEEE Trans. Pattern Anal. Machine Intell., 29(1):167–172, 2007.
[15] M. Pelillo. The dynamics of nonlinear relaxation labeling processes. J. Math. Imag. and Vision, 7(4):309–323, 1997.
[16] J. Rodr`guez. On the Laplacian spectrum and walk-regular hypergraphs. Linear and Multilinı ear Algebra, 51:285–297, 2003.
[17] S. Rota Bul` . A game-theoretic framework for similarity-based data clustering. PhD thesis, o University of Venice, 2009.
[18] A. Shashua, R. Zass, and T. Hazan. Multi-way clustering using super-symmetric non-negative tensor factorization. In Europ. Conf. on Comp. Vision, volume 3954, pages 595–608, 2006.
[19] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Machine Intell., 22:888–905, 2000.
[20] A. Torsello, S. Rota Bul` , and M. Pelillo. Grouping with asymmetric affinities: a gameo theoretic perspective. In IEEE Conf. Computer Vision and Patt. Recogn., pages 292–299, 2006.
[21] A. Torsello, S. Rota Bul` , and M. Pelillo. Beyond partitions: allowing overlapping groups in o pairwise clustering. In Int. Conf. Patt. Recogn., 2008.
[22] J. W. Weibull. Evolutionary game theory. Cambridge University Press, 1995.
[23] D. Zhou, J. Huang, and B. Sch¨ lkopf. Learning with hypergraphs: clustering, classification, o embedding. In Adv. in Neur. Inf. Processing Systems, volume 19, pages 1601–1608, 2006.
[24] J. Y. Zien, M. D. F. Schlag, and P. K. Chan. Multilevel spectral hypergraph partitioning with arbitrary vertex sizes. IEEE Trans. on Comp.-Aided Design of Integr. Circ. and Systems, 18:1389–1399, 1999. 9