  Deep learning models have achieved huge success in numerous fields, such as
computer vision and natural language processing. However, unlike such fields,
it is hard to apply traditional deep learning models on the graph data due to
the 'node-orderless' property. Normally, adjacency matrices will cast an
artificial and random node-order on the graphs, which renders the performance
of deep models on graph classification tasks extremely erratic, and the
representations learned by such models lack clear interpretability. To
eliminate the unnecessary node-order constraint, we propose a novel model named
Isomorphic Neural Network (IsoNN), which learns the graph representation by
extracting its isomorphic features via the graph matching between input graph
and templates. IsoNN has two main components: graph isomorphic feature
extraction component and classification component. The graph isomorphic feature
extraction component utilizes a set of subgraph templates as the kernel
variables to learn the possible subgraph patterns existing in the input graph
and then computes the isomorphic features. A set of permutation matrices is
used in the component to break the node-order brought by the matrix
representation. Three fully-connected layers are used as the classification
component in IsoNN. Extensive experiments are conducted on benchmark datasets,
the experimental results can demonstrate the effectiveness of ISONN, especially
compared with both classic and state-of-the-art graph classification methods.
