transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

Lovasz theta function, SVMs and Finding Dense Subgraphs

Författare och institution:
Vinay Jethava (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers), Chalmers); Anders Martinsson (Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers/GU); C. Bhattacharyya (-); Devdatt Dubhashi (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers), Chalmers)
Publicerad i:
Journal of machine learning research, 14 s. 3495-3536
ISSN:
1532-4435
Publikationstyp:
Artikel, refereegranskad vetenskaplig
Publiceringsår:
2013
Språk:
engelska
Fulltextlänk:
Sammanfattning (abstract):
In this paper we establish that the Lovasz theta function on a graph can be restated as a kernel learning problem. We introduce the notion of SVM-theta graphs, on which Lovasz theta function can be approximated well by a Support vector machine (SVM). We show that Erdos-Renyi random G(n, p) graphs are SVM-theta graphs for log(4)n/n <= p < 1. Even if we embed a large clique of size Theta(root np/1-p) in a G(n, p) graph the resultant graph still remains a SVM-theta graph. This immediately suggests an SVM based algorithm for recovering a large planted clique in random graphs. Associated with the theta 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.
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Data- och informationsvetenskap
Nyckelord:
orthogonal labellings of graphs, planted cliques, random graphs, common dense subgraph
Postens nummer:
199483
Posten skapad:
2014-06-23 11:23
Posten ändrad:
2016-08-22 15:19

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007