Lovasz theta function, SVMs and Finding Dense Subgraphs

Vinay Jethava; Anders Martinsson; Chiranjib Bhattacharyya; Devdatt Dubhashi

In this paper we establish that the LovÃ¡sz $\vartheta$ function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-$\vartheta$ graphs, on which LovÃ¡sz $\vartheta$ function can be approximated well by a Support vector machine (SVM). We show that ErdÃ¶s-RÃ©nyi random $G(n,p)$ graphs are SVM-$\vartheta$ graphs for $ \frac{\log^4 n}{n} \le p < 1 $. Even if we embed a large clique of size $\Theta\left(\sqrt{\frac{np}{1-p}}\right)$ in a $G(n,p)$ graph the resultant graph still remains a LovÃ¡sz $\vartheta$ graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the $\vartheta$ function is the notion of orthogonal labellings. We introduce common orthogonal labellings which extends the idea of orthogonal labellings to multiple graphs. This allows us to propose a Multiple Kernel learning (MKL) based solution which is capable of identifying a large common dense subgraph in multiple graphs. Both in the planted clique case and common subgraph detection problem the proposed solutions beat the state of the art by an order of magnitude.

Lovasz theta function, SVMs and Finding Dense Subgraphs

Abstract