  In this paper, we study a new graph learning problem: learning to count
subgraph isomorphisms. Different from other traditional graph learning problems
such as node classification and link prediction, subgraph isomorphism counting
is NP-complete and requires more global inference to oversee the whole graph.
To make it scalable for large-scale graphs and patterns, we propose a learning
framework which augments different representation learning architectures and
iteratively attends pattern and target data graphs to memorize subgraph
isomorphisms for the global counting. We develop both small graphs (<= 1,024
subgraph isomorphisms in each) and large graphs (<= 4,096 subgraph isomorphisms
in each) sets to evaluate different models. A mutagenic compound dataset,
MUTAG, is also used to evaluate neural models and demonstrate the success of
transfer learning. While the learning based approach is inexact, we are able to
generalize to count large patterns and data graphs in linear time compared to
the exponential time of the original NP-complete problem. Experimental results
show that learning based subgraph isomorphism counting can speed up the
traditional algorithm, VF2, 10-1,000 times with acceptable errors. Domain
adaptation based on fine-tuning also shows the usefulness of our approach in
real-world applications.
