Shifting multi-hypergraphs via collaborative probabilistic voting

摘要

Graphs are widely utilized to characterize the complex relationship among big data. Graph mode seeking is of great importance to many applications in data mining and machine learning era, and it attracts a number of approaches. Typically, existing methods, e.g., graph shift, focus on shifting vertices based on pairwise edges (i.e., an edge connecting two vertices) to find the cohesively dense subgraph. However, they overlooked the semantics of these subgraphs, resulting into undesirable results to the users in specific applications, e.g., saliency detection. In this paper, we propose a novel paradigm aimed at shifting high-order edges (i.e., hyperedges) to deliver graph modes, via a novel probabilistic voting strategy. As a result, the generated graph modes based on dense subhypergraphs may more accurately capture the semantics of objects besides the self-cohesiveness requirement. It is widely known that data objects are always described by multiple features or multi-views, e.g., an image has a color feature and shape feature, where the information provided by all views are complementary to each other. Based on such fact, we propose another novel technique of shifting multiple hypergraphs, each of which corresponds to one view, by conducting a novel collaborative probabilistic voting strategy, named SMHCPV, so as to further improve the performance over hypergraph shift method. Extensive experiments are conducted on both synthetic and real-world datasets to validate the superiority of our proposed technique for both hypergraph shift and SMHCPV.