de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

The skew spectrum of graphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons75313

Borgwardt,  K
Max Planck Institute for Biological Cybernetics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Kondor, R., & Borgwardt, K. (2008). The skew spectrum of graphs. In Twenty-Fifth International Conference on Machine Learning (ICML 2008) (pp. 496-503). New York, NY, USA: ACM Press.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-C847-3
Abstract
The central issue in representing graph-structured data instances in learning algorithms is designing features which are invariant to permuting the numbering of the vertices. We present a new system of invariant graph features which we call the skew spectrum of graphs. The skew spectrum is based on mapping the adjacency matrix of any (weigted, directed, unlabeled) graph to a function on the symmetric group and computing bispectral invariants. The reduced form of the skew spectrum is computable in O(n3) time, and experiments show that on several benchmark datasets it can outperform state of the art graph kernels.