CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Global graph kernels using geometric embeddings

Fredrik Johansson (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Vinay Jethava (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Devdatt Dubhashi (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; C. Bhattacharyya
Proceedings of the 31st International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014 p. 694–702. (2014)
[Konferensbidrag, refereegranskat]

Applications of machine learning methods increasingly deal with graph structured data through kernels. Most existing graph kernels compare graphs in terms of features defined on small subgraphs such as walks, paths or graphlets, adopting an inherently local perspective. However, several interesting properties such as girth or chromatic number are global properties of the graph, and are not captured in local substructures. This paper presents two graph kernels defined on unlabeled graphs which capture global properties of graphs using the celebrated Lovasz number and its associated orthonormal representation. We make progress towards theoretical results aiding kernel choice, proving a result about the separation margin of our kernel for classes of graphs. We give empirical results on classification of synthesized graphs with important global properties as well as established benchmark graph datasets, showing that the accuracy of our kernels is better than or competitive to existing graph kernels.



Denna post skapades 2015-01-14. Senast ändrad 2015-01-14.
CPL Pubid: 210678

 

Läs direkt!

Lokal fulltext (fritt tillgänglig)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)

Ämnesområden

Data- och informationsvetenskap

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Learning with Geometric Embeddings of Graphs