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.