Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort to graph neural networks (GNNs) to learn a low-dimensional representation for both the query and input graphs, in order to predict the number of subgraph isomorphisms on the input graph. However, typical GNNs employ a node-centric message passing scheme that receives and aggregates messages on nodes, which is inadequate in complex structure matching for isomorphism counting. Moreover, on an input graph, the space of possible query graphs is enormous, and different parts of the input graph will be triggered to match different queries. Thus, expecting a fixed representation of the input graph to match diversely structured query graphs is unrealistic. In this paper, we propose a novel GNN called Count-GNN for subgraph isomorphism counting, to deal with the above challenges. At the edge level, given that an edge is an atomic unit of encoding graph structures, we propose an edge-centric message passing scheme, where messages on edges are propagated and aggregated based on the edge adjacency to preserve fine-grained structural information. At the graph level, we modulate the input graph representation conditioned on the query, so that the input graph can be adapted to each query individually to improve their matching. Finally, we conduct extensive experiments on a number of benchmark datasets to demonstrate the superior performance of Count-GNN.
翻译:由于许多基于图形的任务都利用了反复出现的子图模式,所以地貌统计是一个重要问题。典型的方法通常归结为后跟踪框架,需要浏览巨大的搜索空间,计算成本过高。最近的一些研究采用图形神经网络(GNNS)来为查询和输入图形学习低维的表达方式,以便预测输入图中的子图数。然而,典型的GNNS采用一个节点接收和汇总信息传递方案,在复杂结构中,无法匹配偏向式计数。此外,在输入图上,可能的查询图表空间巨大,而输入图的不同部分将被用于匹配不同的查询。因此,期望输入图的固定表达方式与结构多样的查询图表相匹配是不现实的。在本文中,我们提议一个新型 GNNNC 调用计数的点数 GNNNN,以应对上述挑战。在边缘一级,鉴于一个复杂的结构匹配结构结构结构结构,我们提议在精确的图表结构平面结构图结构图结构上,我们提出一个更精细的原子单位,我们用直径直的图表结构图表,我们最后要显示一个边端平面的图表。</s>