关于图神经网络在区分可分解图和例外图方面的有效性

《The ANZIAM Journal》：ON THE EFFICACY OF GRAPH NEURAL NETWORKS IN DISTINGUISHING DECOMPOSABLE AND EXCEPTIONAL GRAPHS

　　

摘要

若图 $G$ 的每条边 $(u,v) \in E(G)$ 的两个端点 $u$ 和 $v$ 具有不同的度数，则称该图为局部不规则图。局部不规则边着色问题是一个图分解问题，其目标是对图的边进行着色，使得每种颜色所诱导的子图都是局部不规则的。若图 $G$ 可以被边着色使得每种颜色诱导的子图都是局部不规则的，则称 $G$ 是可分解的；否则称 $G$ 是例外的。图神经网络（GNNs）是一类专为处理图结构数据而设计的深度学习模型，通常用于涉及丰富节点特征的任务。在本研究中，我们针对可分解图和例外图的分类问题，使用最小特征输入对几种流行的图神经网络架构进行了探索和基准测试。我们比较了具有不同输入表示的模型，并详细分析了它们的学习行为以及所得到的图嵌入。我们的结果表明，在许多图相关问题中，许多消息传递图神经网络在缺乏节点特征时性能会下降。然而，目前关于造成这一现象原因的研究工作很少。我们的结果表明，这一情况并非普遍成立，现代图神经网络能够在一定程度上学习到有意义的结构表示，从而有效地区分这些图。此外，我们观察到模型对分布外图具有一定程度的泛化能力，这表明图神经网络作为理论图问题中模式发现工具既有潜力也存在当前的局限性。

---

---