### Skapa referens, olika format (klipp och klistra)

**Harvard**

Jethava, V., Martinsson, A., Bhattacharyya, C. och Dubhashi, D. (2012) *The Lovász v function, SVMs and finding large dense subgraphs*.

** BibTeX **

@conference{

Jethava2012,

author={Jethava, Vinay and Martinsson, Anders and Bhattacharyya, C. and Dubhashi, Devdatt},

title={The Lovász v function, SVMs and finding large dense subgraphs},

booktitle={26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012, Lake Tahoe, United States, 3-6 December 2012},

isbn={978-16-27-48003-1},

pages={1160-1168},

abstract={The Lovász v function of a graph, a fundamental tool in combinatorial optimization and approximation algorithms, is computed by solving a SDP. In this paper we establish that the Lovász v 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 - v graphs, on which the Lovász v 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 v 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 - v 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.},

year={2012},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 177394

A1 Jethava, Vinay

A1 Martinsson, Anders

A1 Bhattacharyya, C.

A1 Dubhashi, Devdatt

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

YR 2012

T2 26th Annual Conference on Neural Information Processing Systems 2012, NIPS 2012, Lake Tahoe, United States, 3-6 December 2012

SN 978-16-27-48003-1

SP 1160

OP 1168

AB The Lovász v function of a graph, a fundamental tool in combinatorial optimization and approximation algorithms, is computed by solving a SDP. In this paper we establish that the Lovász v 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 - v graphs, on which the Lovász v 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 v 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 - v 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.

LA eng

LK http://books.nips.cc/papers/files/nips25/NIPS2012_0563.pdf

OL 30