An ellipsoidal bounding scheme for the quasi-clique number of a graph

Abstract

A $\gamma$-quasi-clique in a simple undirected graph refers to a subset of vertices that induces a subgraph with edge density at least $\gamma \in [0,1]$. When $\gamma =1$, this definition corresponds to a classical clique. When $\gamma <1$, it relaxes the requirement of all possible edges by the clique definition. Quasi-clique detection has been used in graph-based data mining to find dense clusters, especially in large-scale error-prone data sets in which the clique model can be overly restrictive. The maximum $\gamma$-quasi-clique problem, seeking a $\gamma$-quasi-clique of maximum cardinality in the given graph, can be formulated as an optimization problem with a linear objective function and a single quadratic constraint in binary variables. This article investigates the Lagrangian dual of this formulation, and develops an upper-bounding technique using the geometry of ellipsoids to bound the Lagrangian dual. The tightness of the upper-bound is compared to those obtained from multiple mixed-integer programming formulations of the problem via experiments on benchmark instances.