2015 LearningwithSimilarityFunctions

• (Johansson & Dubhashi, 2015) ⇒ Fredrik D. Johansson, and Devdatt Dubhashi. (2015). “Learning with Similarity Functions on Graphs Using Matchings of Geometric Embeddings.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783341

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Learning+with+Similarity+Functions+on+Graphs+Using+Matchings+of+Geometric+Embeddings
• http://dl.acm.org/citation.cfm?id=2783258.2783341&preflayout=flat#citedby

Quotes

Author Keywords

• Classification; geometric; geometric embeddings; graphs; matchings; network problems; similarity functions

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 LearningwithSimilarityFunctions	Fredrik D. Johansson Devdatt Dubhashi			Learning with Similarity Functions on Graphs Using Matchings of Geometric Embeddings				10.1145/2783258.2783341		2015