ML Anthology

The Skew Spectrum of Graphs

Risi Kondor, Karsten M. Borgwardt
ICML 2008 pp. 496-503
doi:10.1145/1390156.1390219 /icml/2008/kondor2008icml-skew/

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 to a function on the symmetric group and computing bispectral invariants. The reduced form of the skew spectrum is computable in O(n 3 ) time, and experiments show that on several benchmark datasets it can outperform state of the art graph kernels.

PDF ICML Semantic Scholar

Cite

Text

Kondor and Borgwardt. "The Skew Spectrum of Graphs." International Conference on Machine Learning, 2008. doi:10.1145/1390156.1390219

Markdown

[Kondor and Borgwardt. "The Skew Spectrum of Graphs." International Conference on Machine Learning, 2008.](https://mlanthology.org/icml/2008/kondor2008icml-skew/) doi:10.1145/1390156.1390219

BibTeX

@inproceedings{kondor2008icml-skew,
  title     = {{The Skew Spectrum of Graphs}},
  author    = {Kondor, Risi and Borgwardt, Karsten M.},
  booktitle = {International Conference on Machine Learning},
  year      = {2008},
  pages     = {496-503},
  doi       = {10.1145/1390156.1390219},
  url       = {https://mlanthology.org/icml/2008/kondor2008icml-skew/}
}