A game-theoretic approach to partial clique enumeration

摘要

In many computer vision and pattern recognition applications using graph-based representations, it is of great interest to be able to extract the k largest cliques in a graph. However, most methods are geared either towards extracting a single clique of maximum size, or enumerating all cliques, without following any particular order. In this paper, we present a novel approach for partial clique enumeration, which is the problem of extracting the k largest cliques of a graph. Our approach is based on a continuous formulation of the clique problem developed in the 1960s by Motzkin and Straus, and is able to avoid extracting the same clique multiple times. This is done by casting the problem into a game-theoretic framework, where stable strategies are in correspondence with maximal cliques, and by iteratively rendering the extracted solutions unstable. The approach has been tested on the maximum clique problem and compared against several state-of-the-art algorithms both on random as well as D1MACS benchmark graphs. Further, we applied our enumerative heuristic to the matching of shapes using the shock-graph representation. The results confirm the effectiveness of the approach.