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

**Harvard**

Johansson, F. och Dubhashi, D. (2015) *Learning with similarity functions on graphs using matchings of geometric embeddings*.

** BibTeX **

@conference{

Johansson2015,

author={Johansson, Fredrik and Dubhashi, Devdatt},

title={Learning with similarity functions on graphs using matchings of geometric embeddings},

booktitle={Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},

pages={467-476},

abstract={We develop and apply the Balcan-Blum-Srebro (BBS) theory of classification via similarity functions (which are not necessarily kernels) to the problem of graph classification. First we place the BBS theory into the unifying framework of optimal transport theory. This also opens the way to exploit coupling methods for establishing properties required of a good similarity function as per their definition. Next, we use the approach to the problem of graph classification via geometric embeddings such as the Laplacian, pseudo-inverse Laplacian and the Lovász orthogonal labellings. We consider the similarity function given by optimal and near-optimal matchings with respect to Euclidean distance of the corresponding embeddings of the graphs in high dimensions. We use optimal couplings to rigorously establish that this yields a "good" similarity measure in the BBS sense for two well known families of graphs. Further, we show that the similarity yields better classification accuracy in practice, on these families, than matchings of other well-known graph embeddings. Finally we perform an extensive empirical evaluation on benchmark data sets where we show that classifying graphs using matchings of geometric embeddings outperforms the previous state-of-the-art methods.},

year={2015},

keywords={Classification , Geometric embeddings , Graphs , Matchings , Similarity functions},

}

** RefWorks **

RT Conference Proceedings

SR Electronic

ID 236308

A1 Johansson, Fredrik

A1 Dubhashi, Devdatt

T1 Learning with similarity functions on graphs using matchings of geometric embeddings

YR 2015

T2 Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

SP 467

OP 476

AB We develop and apply the Balcan-Blum-Srebro (BBS) theory of classification via similarity functions (which are not necessarily kernels) to the problem of graph classification. First we place the BBS theory into the unifying framework of optimal transport theory. This also opens the way to exploit coupling methods for establishing properties required of a good similarity function as per their definition. Next, we use the approach to the problem of graph classification via geometric embeddings such as the Laplacian, pseudo-inverse Laplacian and the Lovász orthogonal labellings. We consider the similarity function given by optimal and near-optimal matchings with respect to Euclidean distance of the corresponding embeddings of the graphs in high dimensions. We use optimal couplings to rigorously establish that this yields a "good" similarity measure in the BBS sense for two well known families of graphs. Further, we show that the similarity yields better classification accuracy in practice, on these families, than matchings of other well-known graph embeddings. Finally we perform an extensive empirical evaluation on benchmark data sets where we show that classifying graphs using matchings of geometric embeddings outperforms the previous state-of-the-art methods.

LA eng

DO 10.1145/2783258.2783341

LK http://dx.doi.org/10.1145/2783258.2783341

OL 30