  When searching for characteristic subpatterns in potentially noisy graph
data, it appears self-evident that having multiple observations would be better
than having just one. However, it turns out that the inconsistencies introduced
when different graph instances have different edge sets pose a serious
challenge. In this work we address this challenge for the problem of finding
maximum weighted cliques.
  We introduce the concept of most persistent soft-clique. This is subset of
vertices, that 1) is almost fully or at least densely connected, 2) occurs in
all or almost all graph instances, and 3) has the maximum weight. We present a
measure of clique-ness, that essentially counts the number of edge missing to
make a subset of vertices into a clique. With this measure, we show that the
problem of finding the most persistent soft-clique problem can be cast either
as: a) a max-min two person game optimization problem, or b) a min-min soft
margin optimization problem. Both formulations lead to the same solution when
using a partial Lagrangian method to solve the optimization problems. By
experiments on synthetic data and on real social network data, we show that the
proposed method is able to reliably find soft cliques in graph data, even if
that is distorted by random noise or unreliable observations.
