Vector Space Embedding of Undirected Graphs with Fixed-cardinality Vertex Sequences for Classification

Simple weighted undirected graphs with a fixed number of vertices and fixed vertex orderings can be used to represent data and patterns in a wide variety of scientific and engineering domains. Classification of such graphs by existing graph matching methods perform rather poorly because they do not exploit their specificity. As an alternative, methods relying on vector-space embedding hold promising potential. We propose two such techniques that can be deployed as a front-end for any pattern recognition classifiers: one has low computational cost but generates high-dimensional spaces, while the other is more computationally demanding but can yield relatively low-dimensional vector space representations. We show experimental results on an fMRI brain state decoding task and discuss the shortfalls of graph edit distance for the type of graph under consideration.