论文标题
MGNN：受距离几何问题启发的图形神经网络
MGNN: Graph Neural Networks Inspired by Distance Geometry Problem
论文作者
论文摘要
图形神经网络（GNN）已成为机器学习领域的重要研究主题。现有的GNN模型通常分为两种类型：基于多项式图滤波器和空间GNN设计的光谱GNN，它们利用消息通话方案作为模型的基础。对于光谱GNN的表达力和普遍性，一种自然的方法是改善基础函数的设计，以获得更好的近似能力。至于空间GNN，诸如图形同构网络（GIN）之类的模型基于图同构测试分析其表现力。最近，已经尝试在空间GNN与曲率和细胞或骨绳索等几何概念以及振荡器等物理现象之间建立联系。但是，尽管最近取得了进展，但从几何和物理学的角度来看，仍然缺乏关于空间GNN的普遍性的全面分析。在本文中，我们提出了Metricgnn（MGNN），这是一种由GNN分类阶段分类阶段的一致性启发的空间GNN模型。我们证明，如果GNN模型可以生成与任何给定的嵌入矩阵一致的嵌入矩阵，则它是通用的。该属性与距离几何问题（DGP）密切相关。由于DGP是NP-硬化组合优化问题，因此我们提出优化源自春季网络和多维缩放（MDS）问题的能量函数。这种方法还允许我们的模型处理同粒细胞和异质图。最后，我们建议采用迭代方法优化我们的能量功能。我们通过对合成和现实世界数据集进行的实验广泛评估了模型的有效性。我们的代码可在以下网址提供：https：//github.com/guanyucui/mgnn。
Graph Neural Networks (GNNs) have emerged as a prominent research topic in the field of machine learning. Existing GNN models are commonly categorized into two types: spectral GNNs, which are designed based on polynomial graph filters, and spatial GNNs, which utilize a message-passing scheme as the foundation of the model. For the expressive power and universality of spectral GNNs, a natural approach is to improve the design of basis functions for better approximation ability. As for spatial GNNs, models like Graph Isomorphism Networks (GIN) analyze their expressive power based on Graph Isomorphism Tests. Recently, there have been attempts to establish connections between spatial GNNs and geometric concepts like curvature and cellular sheaves, as well as physical phenomena like oscillators. However, despite the recent progress, there is still a lack of comprehensive analysis regarding the universality of spatial GNNs from the perspectives of geometry and physics. In this paper, we propose MetricGNN (MGNN), a spatial GNN model inspired by the congruent-insensitivity property of classifiers in the classification phase of GNNs. We demonstrate that a GNN model is universal in the spatial domain if it can generate embedding matrices that are congruent to any given embedding matrix. This property is closely related to the Distance Geometry Problem (DGP). Since DGP is an NP-Hard combinatorial optimization problem, we propose optimizing an energy function derived from spring networks and the Multi-Dimensional Scaling (MDS) problem. This approach also allows our model to handle both homophilic and heterophilic graphs. Finally, we propose employing the iteration method to optimize our energy function. We extensively evaluate the effectiveness of our model through experiments conducted on both synthetic and real-world datasets. Our code is available at: https://github.com/GuanyuCui/MGNN.
