Keywords (2)

Academic
Publications
A Game-Theoretic Approach to Hypergraph Clustering

A Game-Theoretic Approach to Hypergraph Clustering,Samuel Rota Bul,Marcello Pelillo

A Game-Theoretic Approach to Hypergraph Clustering   (Citations: 2)
BibTex | RIS | RefWorks Download
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 obt aining the clusters as a by-product of the partitioning process. In this paper, we p rovide a radically dif- ferent perspective to the problem. In contrast to the classi cal 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 clust ering problem can be naturally cast into a non-cooperative multi-player "clu stering game", whereby the notion of a cluster is equivalent to a classical game-the oretic equilibrium con- cept. From the computational viewpoint, we show that the problem of finding the equilibria of our clustering game is equivalent to locally o ptimizing 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 clusteri ng techniques.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...This will require replacing the pairwise interactions with higher-order interactions in defining payoffs, along the lines proposed in Rota Bulò and Pelillo (2009) for unsupervised learning...

    Aykut Erdemet al. Graph Transduction as a Noncooperative Game

    • ...Our work is also related to graph-based ranking and hypergraph learning [2, 3, 8, 13, 38, 48, 49]...
    • ...Recently, there has been a lot of interest in learning with hypergraph [3, 8, 13, 38, 48]...
    • ...Bulò et al. introduce a hypergraph clustering algorithm to extract maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities [8]...
    • ...There are many existing algorithms for learning on hypergraph [3, 8, 13, 38, 48]...

    Shulong Tanet al. Using Rich Social Media Information for Music Recommendation via Hyper...

Sort by: