一种具有结构意识的进化框架，用于在复杂图上进行学习

《Neurocomputing》：An evolutionary framework with structural awareness for learning on complex graphs

　　摘要：图神经网络通常通过梯度下降进行训练，其中图作为固定输入而非优化过程中的积极参与者。我们提出了EFSA，这是一种具有结构意识的进化框架，它将图的谱属性——即标准化的拉普拉斯矩阵、低频特征向量以及衍生的拓扑描述符——注入进化优化器的三个主要组成部分中。适应度函数通过狄利克雷能量惩罚来增强任务损失，以奖励结构上平滑的表示；拓扑感知的选择机制通过中心性描述符对节点进行加权，从而保留结构多样性的候选者；谱突变仅在最低频率的特征模式下扰动节点-潜在块，使得该块由谱系数而非自由条目参数化。从理论上讲，我们证明了基于结构的适应度的利普希茨连续性，量化了谱突变与各向同性突变所注入的狄利克雷能量，并在明确的局部漂移条件下，确立了迄今最好个体的期望最优性差距的上限，其中收敛是在变异算子可到达的范围内达到一个受限最优解。一种平衡尺度的启发式方法将正则化强度与谱间隙联系起来，从而消除了一个超参数。在涵盖引文网络、合作者网络和共同购买网络的七个节点分类基准测试中，EFSA与基于梯度的方法、图转换器和架构搜索基线相比具有竞争力，包括那些接收相同的谱节点-潜在块并通过梯度下降进行训练的容量匹配基线，在连接较弱的图（谱间隙较小）上获得了最大的收益，这一探索性趋势与理论一致。我们还报告了在边重连和消融实验下的鲁棒性，以隔离每个结构组件的贡献。该框架本身是以任务不可知的方式制定的，但这里报告的实证证据仅限于传输节点分类，我们的主张也相应地受到了限制。

引言：图结构化数据广泛应用于多种场景，包括引文分析、生物交互建模、交通优化和知识图谱推理[1]。在这些场景中，实体通过违反传统机器学习独立性假设的关系模式相互关联[2]。这类数据的非欧几里得特性——不规则的连接性、异构的节点度和层次化的社区结构——对学习和推理提出了根本性的挑战[3]。图神经网络（GNN）及其变体推动了该领域的许多最新进展[4]、[5]、[6]。通过消息传递和邻域聚合来传播信息，GNN提取了具有辨别能力的节点和图级表示[7]、[8]，并在节点分类、链接预测和图分类方面取得了最先进的结果。尽管取得了这些成功，大多数GNN仍然依赖于固定的架构设计和基于梯度的优化方法，这些方法在适应现实世界图的结构多样性方面存在困难，并且容易陷入局部最优解[9]、[10]；消息传递设计在异质图上也表现不佳，这促使人们开发出重塑信息在边上流动方式的架构[11]。进化计算提供了一种互补的无梯度范式，它在非凸和多模态场景中有效[12]、[13]。基于种群的算法通过选择、变异和替换维护多样化的候选解决方案，无需梯度信息即可实现鲁棒的探索[14]、[15]，并已成功应用于神经架构搜索、超参数优化和表示学习[16]、[17]、[18]。然而，传统的进化方法隐式地处理结构信息，依赖于不利用图拓扑的问题不可知适应度评估[19]、[20]。将结构意识整合到进化学习中在很大程度上仍然是未被探索的。现有的进化优化和图学习 hybrids 专注于架构或超参数搜索，并将图结构视为固定的输入而非搜索的主动驱动因素[21]。这种分离限制了它们利用拓扑的能力，可能在异构或噪声图中产生次优解[22]。我们所追求的机会是这两种范式在某种精确意义上是互补的。图神经网络在其前向计算中编码了拓扑，但继承了梯度下降在非凸、对称诱导景观上的脆弱性；进化搜索对此景观具有鲁棒性，但其标准形式对拓扑是盲目的。单独使用这两种方法都无法充分利用问题的结构：GNN 使用了图但没有使用鲁棒的优化器，而进化算法使用了鲁棒的优化器但没有使用图。如果有一种方法能够让图谱本身塑造进化动态——哪些候选者被优先考虑、后代如何被扰动、哪些解决方案能够存活——那么它将结合两者的优势。然而，要实现这一点，需要回答拓扑应该如何进入每个操作符，以及这样做在理论上是否可以得到合理化。我们确定了三个具体的差距：
- G1——适应度中没有结构反馈。进化图学习的适应度函数仅依赖于任务性能，忽略了结构一致性，并且缺乏任何关于拓扑应该如何塑造进化动态的理论解释[23]、[24]。
- G2——有限的拓扑适应性和薄弱的理论。结构感知方法依赖于固定的表示和预定义的聚合，随着深度的增加而出现过度平滑的问题[25]、[26]。更根本的是，它们的优化属性——收敛行为和它们优化的目标几何形状——在很大程度上没有得到表征，因此很少有理论可以预测结构感知优化何时会有帮助。
- G3——没有统一的原则性框架。现有的 hybrids 都是特定于应用的或与特定架构相关，没有一种通用的、任务不可知的框架可以使用结构信号来指导进化搜索，并在理论上有保证[27]。

表1总结了现有范式如何解决或未能解决这些差距，并相应地定位了EFSA。

为了填补这些差距，我们提出了EFSA，这是一个将图的结构属性直接嵌入优化过程的进化框架。一个基于谱图论的结构感知适应度函数将预测目标与结构一致性项结合起来，使搜索受到拓扑的指导，而不是将其视为被动输入。自适应的变异操作符利用局部图属性产生结构连贯的后代，而拓扑感知的选择机制保持对图的结构区域的覆盖。我们进一步证明，由此产生的适应度景观是利普希茨连续的，并且在明确的局部漂移条件（A4）下，该框架会在变异算子可到达的范围内收敛到一个受限最优解，其收敛速率取决于利普希茨常数、搜索空间直径、漂移参数和子空间维数。为了与以往的工作区分开来：例如GraphNAS [21]（一种强化学习、策略梯度控制器）和SANE [27]（一种可微分架构搜索）将搜索放在外部循环中，针对架构或超参数，而内部学习器仍然是梯度训练的，图仅作为固定输入；最近的表示和拓扑优化进化方法也分别保持结构和搜索[29]、[30]。另一类工作通过结构正则化器注入拓扑信息——向梯度训练的目标添加狄利克雷能量或平滑惩罚——但优化器本身对拓扑是盲目的。EFSA 不属于这两个类别：一组光谱量（拉普拉斯矩阵、其最低特征模式和节点级结构描述符）同时驱动适应度、变异操作符和无梯度种群搜索的选择规则。据我们所知，这是第一个图拓扑同时塑造所有三个进化操作符的框架，并配有一个收敛保证。本文的主要贡献如下：
- 一个统一的、结构感知的进化框架（解决了G1和G3）。EFSA 通过基于谱的适应度函数将结构反馈直接嵌入进化动态中，而不是将结构视为辅助输入。该框架的制定不依赖于特定的下游任务；我们在传输节点分类上对其进行了实证验证，并且不声称在该设置之外的实验支持。
- 理论保证（解决了G2）。我们证明了基于结构的适应度是利普希茨连续的，其常数由图的谱属性限定（定理1），并在局部漂移条件（A4）下，确立了在可达集合上的收敛速率（定理2），为具有结构感知的进化优化提供了首个此类分析。
- 全面的实证验证。在涵盖引文网络、共同购买网络和合作者网络的七个基准测试中，EFSA 在匹配的计算预算下始终优于代表性基线，包括容量匹配的对照组，其中最强的梯度基线接收相同的谱节点-潜在块，并通过带有Holm校正的配对t检验确立了显著性。消融实验确认了每个组件的必要性，测量到的改进与谱间隙之间的关系与理论预测的方向一致。

本文的其余部分组织如下：第2节回顾相关工作。第3节介绍初步知识和问题表述。第4节介绍EFSA及其理论分析。第5节报告实验结果。第6节讨论优势和局限性，第7节总结。

相关工作：我们回顾了三种工作——用于复杂优化的进化计算、图表示学习以及混合进化-图方法——并将EFSA与每种方法进行对比，强调现有方法在第1节中 identified 的差距上的不足。

初步知识：本节介绍了符号、图谱背景和进化设置，然后正式陈述问题。表2总结了符号。

提出的方法：本节介绍了EFSA。我们首先提供概述，然后详细描述每个组件及其理论依据，并以完整算法作为结论。

实验：我们的实验围绕七个研究问题展开，这些问题共同测试第4节中的理论主张是否能够转化为实践，每个设计选择是否合理，以及该方法是否实际可行。在整个过程中，我们优先考虑公平比较——匹配的架构和计算预算——以及统计严谨性。

结构感知何时有帮助？实证结果和理论共同指出了EFSA最有价值的情况。在稀疏、连接较弱的图（如引文网络）中，结构感知带来了最大的收益（百分比点），因为这些图的谱间隙较小，低频谱模式携带了与任务相关的强结构。在密度较大的图（共同购买、合作者网络）中，改进较小（百分点），表明当图连接性较好时，结构利用的效果减弱。

结论：我们提出了EFSA，这是一个将图的结构属性直接嵌入优化过程的进化框架，而不是将拓扑视为静态输入。它的三个组件——基于谱的结构感知适应度、谱变异操作符和拓扑感知的选择方案——共同引导基于种群的搜索，利用图拓扑。在理论方面，我们证明了适应度景观是利普希茨连续的，其常数有谱限制（CRediT）。

作者贡献声明：王俊：写作——审阅与编辑、撰写——初稿、可视化、验证、监督、软件、资源、项目管理和方法论、调查、资金获取、形式分析、数据整理、概念化。罗哲：写作——审阅与编辑、撰写——初稿、可视化、验证、监督、软件、资源、项目管理和方法论、调查、资金获取、形式分析、数据整理、概念化。

利益冲突声明：作者声明他们没有已知的竞争性财务利益或个人关系可能影响本文报告的工作。

致谢：本研究由湖南省教育部门（24B0648）的科学研究项目资助。本研究由湖南省教育部门（25C0699）的科学研究项目资助。本研究由湖南省“十四五”关键学科和应用导向学科（Xiangjiaotong [2022] 351）资助。本研究由教育部供需匹配就业教育项目（2025052109016）资助。

王俊，湖南省衡阳市，硕士学历，讲师，主要研究兴趣包括人工智能和通信网络。罗哲，湖南省衡阳市衡阳师范学院计算机科学与技术学院，硕士学历，主要研究兴趣包括人工智能和通信网络。