Header logo is ei

The skew spectrum of graphs


Conference Paper


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.

Author(s): Kondor, R. and Borgwardt, K.
Pages: 496-503
Year: 2008
Month: July
Day: 0
Editors: Cohen, W.W. , A. McCallum, S.T. Roweis
Publisher: ACM Press

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1145/1390156.1390219
Event Name: Twenty-Fifth International Conference on Machine Learning (ICML 2008)
Event Place: Helsinki, Finland

Address: New York, NY, USA
Digital: 0
ISBN: 978-1-605-58205-4

Links: Web


  title = {The skew spectrum of graphs},
  author = {Kondor, R. and Borgwardt, K.},
  pages = {496-503},
  editors = {Cohen, W.W. , A. McCallum, S.T. Roweis},
  publisher = {ACM Press},
  address = {New York, NY, USA},
  month = jul,
  year = {2008},
  month_numeric = {7}