  Graphs are commonly used to represent objects, such as images and text, for
pattern classification. In a dynamic world, an object may continuously evolve
over time, and so does the graph extracted from the underlying object. These
changes in graph structure with respect to the temporal order present a new
representation of the graph, in which an object corresponds to a set of
time-variant graphs. In this paper, we formulate a novel time-variant graph
classification task and propose a new graph feature, called a graph-shapelet
pattern, for learning and classifying time-variant graphs. Graph-shapelet
patterns are compact and discriminative graph transformation subsequences. A
graph-shapelet pattern can be regarded as a graphical extension of a shapelet
-- a class of discriminative features designed for vector-based temporal data
classification. To discover graph-shapelet patterns, we propose to convert a
time-variant graph sequence into time-series data and use the discovered
shapelets to find graph transformation subsequences as graph-shapelet patterns.
By converting each graph-shapelet pattern into a unique tokenized graph
transformation sequence, we can measure the similarity between two
graph-shapelet patterns and therefore classify time-variant graphs. Experiments
on both synthetic and real-world data demonstrate the superior performance of
the proposed algorithms.
