  The graph retrieval problem is to search in a large corpus of graphs for ones
that are most similar to a query graph. A common consideration for scoring
similarity is the maximum common subgraph (MCS) between the query and corpus
graphs, usually counting the number of common edges (i.e., MCES). In some
applications, it is also desirable that the common subgraph be connected, i.e.,
the maximum common connected subgraph (MCCS). Finding exact MCES and MCCS is
intractable, but may be unnecessary if ranking corpus graphs by relevance is
the goal. We design fast and trainable neural functions that approximate MCES
and MCCS well. Late interaction methods compute dense representations for the
query and corpus graph separately, and compare these representations using
simple similarity functions at the last stage, leading to highly scalable
systems. Early interaction methods combine information from both graphs right
from the input stages, are usually considerably more accurate, but slower. We
propose both late and early interaction neural MCES and MCCS formulations. They
are both based on a continuous relaxation of a node alignment matrix between
query and corpus nodes. For MCCS, we propose a novel differentiable network for
estimating the size of the largest connected common subgraph. Extensive
experiments with seven data sets show that our proposals are superior among
late interaction models in terms of both accuracy and speed. Our early
interaction models provide accuracy competitive with the state of the art, at
substantially greater speeds.
