The skew spectrum of graphs --- a new class of graph invariants
Risi Kondor, Gatsby Unit, University College London
One of the central issues in representing graph structured data
instances in machine learning and other computational fields is
designing features that are invariant to permuting the labeling of the
vertices. We present a new, powerful system of relabeling invariant
graph features called the skew spectrum of graphs.
Most of the graph invariants in practical use today are based on
either counting local features (subgraphs, shortest paths, etc) or
manipulating the eigenvalues of the graph Laplacian. In contrast, the
skew spectrum is an algebraic approach based on the action of
permutations on the adjacency matrix regarded as a function on a
specific homogeneous space of the symmetric group.
For computational efficiency, we introduce a variant called the
reduced skew spectrum which is computable in n^3 time. Despite the
fact that the reduced skew spectrum has only a constant number of
scalar components (to be exact, 49), it seems to be surprisingly good
at discriminating between graphs. Complete enumeration of simple
graphs of small size shows that non-isomorphic graphs having identical
skew spectra is very rare. Experiments on standard molecule
classification tasks show that the skew spectrum is as good or better
than state of the art graph kernels for representing graphs up to
about n=200.
This is joint work with Karsten Borgwardt.