The Lovász ϑ function, SVMs and finding large dense subgraphs

Abstract

The Lovász ϑ function of a graph, a fundamental tool in combinatorial optimiza-tion and approximation algorithms, is computed by solving a SDP. In this paper we establish that the Lovász ϑ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportuni-ties bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call SVM − ϑ graphs, on which the Lovász ϑ function can be approximated well by a one-class SVM. This leads to novel use of SVM techniques for solving algorithmic problems in large graphs e.g. identifying a planted clique of size Θ(√ n) in a random graph G(n, 1 2). A classic approach for this problem involves computing the ϑ function, however it is not scalable due to SDP computation. We show that the random graph with a planted clique is an example of SVM − ϑ graph. As a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the state-of-the-art. We introduce the notion of common orthogonal labelling and show that it can be computed by solving a Multiple Kernel learning problem. It is further shown that such a labelling is extremely useful in identifying a large common dense subgraph in multiple graphs, which is known to be a computationally difficult problem. The proposed algorithm achieves an order of magnitude scalability compared to state of the art methods.