Timezone: »
Poster
The Lovasz $\theta$ function, SVMs and finding large dense subgraphs
Vinay Jethava · Anders Martinsson · Chiranjib Bhattacharyya · Devdatt Dubhashi
Mon Dec 03 07:00 PM  12:00 AM (PST) @ Harrahâ€™s Special Events Center 2nd Floor
The Lovasz $\theta$ function of a graph, is a fundamental tool in combinatorial optimization and approximation algorithms. Computing $\theta$ involves solving a SDP and is extremely expensive even for moderately sized graphs. In this paper we establish that the Lovasz $\theta$ function is equivalent to a kernel learning problem related to one class SVM. This interesting connection opens up many opportunities bridging graph theoretic algorithms and machine learning. We show that there exist graphs, which we call $SVM\theta$ graphs, on which the Lovasz $\theta$ function can be approximated well by a oneclass SVM. This leads to a novel use of SVM techniques to solve algorithmic problems in large graphs e.g. identifying a planted clique of size $\Theta({\sqrt{n}})$ in a random graph $G(n,\frac{1}{2})$. A classic approach for this problem involves computing the $\theta$ 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\theta$ graph, and as a consequence a SVM based approach easily identifies the clique in large graphs and is competitive with the stateoftheart. Further, we introduce the notion of a ''common orthogonal labeling'' which extends the notion of a ''orthogonal labelling of a single graph (used in defining the $\theta$ function) to multiple graphs. The problem of finding the optimal common orthogonal labelling is cast as a Multiple Kernel Learning problem and is used to identify a large common dense region in multiple graphs. The proposed algorithm achieves an order of magnitude scalability compared to the state of the art.
Author Information
Vinay Jethava (DocuSign)
Anders Martinsson (Chalmers University)
Chiranjib Bhattacharyya (Indian Institute of Science)
Devdatt Dubhashi (Chalmers University, Sweden)
More from the Same Authors

2015 Poster: Weighted Theta Functions and Embeddings with Applications to MaxCut, Clustering and Summarization »
Fredrik D Johansson · Ankani Chattoraj · Chiranjib Bhattacharyya · Devdatt Dubhashi 
2015 Poster: Spectral Norm Regularization of Orthonormal Representations for Graph Transduction »
Rakesh Shivanna · Bibaswan K Chatterjee · Raman Sankaran · Chiranjib Bhattacharyya · Francis Bach 
2014 Poster: Learning on graphs using Orthonormal Representation is Statistically Consistent »
Rakesh Shivanna · Chiranjib Bhattacharyya 
2014 Poster: A provable SVDbased algorithm for learning topics in dominant admixture corpus »
Trapit Bansal · Chiranjib Bhattacharyya · Ravindran Kannan 
2010 Poster: Efficient algorithms for learning kernels from multiple similarity matrices with general convex loss functions »
Achintya Kundu · Vikram Mukunda Rao Tankasali · Chiranjib Bhattacharyya · Aharon BenTal 
2009 Poster: On the Algorithmics and Applications of a Mixednorm based Kernel Learning Formulation »
Saketha Nath Jagarlapudi · dinesh govindaraj · Raman S · Chiranjib Bhattacharyya · Aharon BenTal · K. R. Ramakrishnan 
2007 Poster: Kernels on Attributed Pointsets with Applications »
Mehul Parsana · Sourangshu Bhattacharya · Chiranjib Bhattacharyya · K. R. Ramakrishnan 
2007 Poster: A Randomized Algorithm for Large Scale Support Vector Learning »
Krishnan S Kumar · Chiranjib Bhattacharyya · Ramesh Hariharan