  Graph neural networks (GNNs) and message passing neural networks (MPNNs) have
been proven to be expressive for subgraph structures in many applications. Some
applications in heterogeneous graphs require explicit edge modeling, such as
subgraph isomorphism counting and matching. However, existing message passing
mechanisms are not designed well in theory. In this paper, we start from a
particular edge-to-vertex transform and exploit the isomorphism property in the
edge-to-vertex dual graphs. We prove that searching isomorphisms on the
original graph is equivalent to searching on its dual graph. Based on this
observation, we propose dual message passing neural networks (DMPNNs) to
enhance the substructure representation learning in an asynchronous way for
subgraph isomorphism counting and matching as well as unsupervised node
classification. Extensive experiments demonstrate the robust performance of
DMPNNs by combining both node and edge representation learning in synthetic and
real heterogeneous graphs. Code is available at
https://github.com/HKUST-KnowComp/DualMessagePassing.
