arXiv:2408.12334v2 提交类型: 替换-交叉 摘要：图神经网络（GNNs）在处理图结构数据方面表现出色，但在链接预测任务中的表现通常不如古典方法，主要原因是常用的消息传递原则的局限性。值得关注的是，它们区分非同构图的能力受限于1维韦施费勒-勒曼测试。我们的研究提出了一种新方法，通过将诱导子图嵌入图拉普拉斯矩阵的特征基中来增强GNNs的表达能力。我们引入了一种具有线性约束的可学习拉朗兹算法（LLwLC），提出了两种新颖的子图提取策略：编码删除顶点的子图和应用内尔曼特征值约束。对于前者，我们展示了区分2-WL无法区分的图的能力，同时保持高效的时间复杂性。后者侧重于链接表示，能够区分$k$-规则图和节点自同构，这是链接预测任务中的关键方面。我们的方法导致了一个极其轻量级的架构，减少了对大规模训练数据集的需求。实验结果表明，我们的方法在基准数据集上的困难的链接预测任务中提高了性能，证明了其实用价值并支持了我们的理论发现。值得注意的是，LLwLC仅需PubMed和OGBL-Vessel数据集的5%和10%数据即可实现与当前最佳方法相比的速度提升20倍和10倍。