Hyper-Clique Graph Matching and Applications

This paper proposes a method for hyper-clique graph (HCG) generation, which can be considered an extension of classical graphs and hyper-graphs in which the node is replaced with the clique (a set of neighboring nodes in a specific feature space) and the hyper-edge linking multiple nodes is replaced with the hyper-edge linkingmultiple cliques. In addition, we propose the HCG matching method by preserving global and local structures. Specifically, we embed the clique relations of arbitrary orders in a high-order similarity tensor in a recursive manner. Then, we formulate the objective function of HCG matching with respect to two latent variables: the latent clique structure information in the original graph and the similarity measure of clique sets from pairwise HCGs. Since the objective function is not jointly convex with respect to both latent variables, we decompose it into two consecutive measurements for optimization: 1) a clique-to-clique similarity measurement by preserving local unary and pairwise correspondences and 2) a graph-to-graph similarity measurement by preserving global clique-toclique correspondence. We suitably adopt the affinity-preserving reweighted random walks to optimize the objective function. We extensively evaluate the HCG matching performance on multiple applications: 1) we evaluate the robustness of HCG with respect to the deformation noise, the number of outliers, and the edge density on synthetic data and explore the effects of both the clique order and hyper-edge order on performance; 2) we explore HCG matching for feature point matching on multiple image data sets (CMU house sequence, Caltech+MSRC, and Car+Motor); and 3) we explore HCG matching for multi-view object retrieval, which is a much more challenging task since multi-view objects contain significant variations of illumination, viewpoint, and so on, using popular data sets (MV-RED and NTU). A comparison against the state-of-the-art methods demonstrates the superior performance of the proposed method.