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
this https URL

本文提出一种基于边 - 顶点转换和对偶图同构性质的双重消息传递神经网络 (DMPNNs) 模型，用于在异步方式下加强子结构表示学习，适用于子图同构计数和匹配以及无监督节点分类任务。大量实验在合成和真实异构图中展示了 DMPNNs 结合节点和边表示学习的鲁棒性能，代码可在给出的网址中获取。

使用双重信息传递的图卷积网络进行子图同构计数和匹配

Graph Convolutional Networks with Dual Message Passing for Subgraph  Isomorphism Counting and Matching

We propose a new method for embedding graphs while preserving directed edge
information. Learning such continuous-space vector representations (or
embeddings) of nodes in a graph is an important first step for using network
information (from social networks, user-item graphs, knowledge bases, etc.) in
many machine learning tasks.
Unlike previous work, we (1) explicitly model an edge as a function of node
embeddings, and we (2) propose a novel objective, the "graph likelihood", which
contrasts information from sampled random walks with non-existent edges.
Individually, both of these contributions improve the learned representations,
especially when there are memory constraints on the total size of the
embeddings. When combined, our contributions enable us to significantly improve
the state-of-the-art by learning more concise representations that better
preserve the graph structure.
We evaluate our method on a variety of link-prediction task including social
networks, collaboration networks, and protein interactions, showing that our
proposed method learn representations with error reductions of up to 76% and
55%, on directed and undirected graphs. In addition, we show that the
representations learned by our method are quite space efficient, producing
embeddings which have higher structure-preserving accuracy but are 10 times
smaller.

本文提出了一种新的无向图嵌入方法，通过建模节点的连边函数，并结合从随机游走中抽样的信息，对图的联通结构进行表达，从而提高了学到的嵌入空间的表现和空间效率。该方法在社交网络、蛋白质相互作用等数据集上均取得了较好的表现。