The skew spectrum of graphs

Kondor, R; Borgwardt, K; Cohen,; W.W.,; McCallum, A.; Roweis, S.T.

doi:10.1145/1390156.1390219

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

The skew spectrum of graphs

MPS-Authors

There are no MPG-Authors in the publication available

External Resource

https://dl.acm.org/citation.cfm?doid=1390156.1390219
(出版社版)

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Kondor, R., & Borgwardt, K. (2008). The skew spectrum of graphs. In W., Cohen, A., McCallum, & S., Roweis (Eds.), ICML '08: Proceedings of the 25th international conference on Machine (pp. 496-503). New York, NY, USA: ACM Press.

引用: https://hdl.handle.net/11858/00-001M-0000-0013-C847-3

要旨

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.