Dipartimento di Scienze Ambientali, Informatica e Statistica, Università Cà Foscari di Venezia, via Torino 155, Venezia-Mestre 30172, Italy.
IEEE Trans Pattern Anal Mach Intell. 2013 Jun;35(6):1312-27. doi: 10.1109/TPAMI.2012.226.
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 predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we offer a radically different view of 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 our purpose well. To this end, we formulate the hypergraph clustering problem in terms of a noncooperative multiplayer "clustering game," and show that a natural notion of a cluster turns out to be equivalent to a classical (evolutionary) game-theoretic equilibrium concept. We prove 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 high-order replicator dynamics to perform this optimization, based on the Baum-Eagon inequality. Experiments over synthetic as well as real-world data are presented which show the superiority of our approach over the state of the art.
超图聚类是指使用高阶（而非成对）相似度从一组对象中提取最大一致性组的过程。传统的方法基于将输入数据划分为预定数量的类别的思想，从而将聚类作为分区过程的副产品获得。在本文中，我们提供了对该问题的完全不同的看法。与经典方法相反，我们尝试对聚类的概念进行有意义的形式化，并且表明博弈论提供了一个有吸引力且尚未开发的视角，非常适合我们的目的。为此，我们根据非合作的多人“聚类游戏”来表述超图聚类问题，并表明聚类的自然概念等同于经典（进化）博弈论均衡概念。我们证明，寻找我们的聚类游戏均衡的问题等同于在标准单形上局部优化多项式函数，并且我们提供了一种基于 Baum-Eagon 不等式的离散时间高阶复制器动力学来执行此优化。我们提出了在合成数据和真实世界数据上的实验，结果表明我们的方法优于最先进的方法。
