Finding Modes by Probabilistic Hypergraphs Shifting
This work addresses the challenge of improving graph mode detection for applications like clustering and graph matching, offering a novel approach that is not incremental.
The paper tackles the problem of finding robust graph modes by introducing a hypergraph shift paradigm that uses probabilistic voting and high-order edges, resulting in graph modes that better capture object semantics and significantly outperform existing techniques in clustering and graph matching.
In this paper, we develop a novel paradigm, namely hypergraph shift, to find robust graph modes by probabilistic voting strategy, which are semantically sound besides the self-cohesiveness requirement in forming graph modes. Unlike the existing techniques to seek graph modes by shifting vertices based on pair-wise edges (i.e, an edge with $2$ ends), our paradigm is based on shifting high-order edges (hyperedges) to deliver graph modes. Specifically, we convert the problem of seeking graph modes as the problem of seeking maximizers of a novel objective function with the aim to generate good graph modes based on sifting edges in hypergraphs. As a result, the generated graph modes based on dense subhypergraphs may more accurately capture the object semantics besides the self-cohesiveness requirement. We also formally prove that our technique is always convergent. Extensive empirical studies on synthetic and real world data sets are conducted on clustering and graph matching. They demonstrate that our techniques significantly outperform the existing techniques.