一种基于分阶段多目标优化和结构感知图神经网络的图布局生成方法及系统

本发明涉及图数据处理、图可视化、图神经网络和机器学习优化，提供了一种基于分阶段多目标优化和结构感知图神经网络的图布局生成方法及系统。

背景技术：

1、图布局是图数据处理与图可视化领域中的核心技术问题，其目标是将图结构数据中的节点和边映射至二维坐标空间，使所生成的布局能够清晰、合理地表达节点之间的拓扑关系。随着社交网络、交通网络、通信网络及生物网络等图结构数据规模的持续增长，对图布局方法在布局质量、优化效率及可扩展性方面提出了更高要求。

2、目前，已有的图布局生成方法主要包括以下几类：

3、第一类为基于力导向的图布局方法，如fruchterman-reingold算法、forceatlas2算法等。该类方法将节点间的连接关系建模为引力与斥力，通过迭代更新节点位置使系统达到力学平衡状态，从而实现图结构的自动布局。此类方法被广泛应用于gephi等图可视化系统中。

4、第二类为基于分层或约束的图布局方法，如graphviz中的dot/sugiyama分层布局算法。该类方法通过节点分层、边交叉最小化以及坐标分配等步骤生成结构化图布局，适用于有向图、流程图及依赖关系图等特定场景。

5、第三类为基于多目标优化的布局生成方法。该类方法采用nsga-ii、moea/d等多目标进化优化算法，同时优化节点重叠、边交叉数量、边长度、布局紧凑度、节点间距等多个图布局指标，并从pareto最优解集中选取最终布局方案。

6、此外，在基于学习的图布局生成方法中，如multicriteria scalable graphdrawing via stochastic gradient descent（(sgd)²，发表于ieee transactions onvisualization and computer graphics, 2022）等多指标图布局优化方法，能够对多个可微布局质量指标进行优化，并在布局质量、运行时间及可扩展性方面进行了实验验证。

7、然而，上述现有技术在多目标图布局优化方面仍存在明显不足：

8、一方面，传统力导向方法、多维尺度分析（mds）方法以及分层布局方法通常依赖人工设计的布局规则、迭代优化过程以及较为敏感的参数设置，且往往围绕特定布局原则进行设计，难以在统一框架下同时兼顾全局结构保持、节点遮挡减少、边长合理性以及局部角度可读性等多个相互冲突的布局质量优化目标。

9、另一方面，对于现有学习式图布局方法，多数采用加权联合损失的方式将多个布局质量目标合并为单一标量损失进行同步优化。该方式对各损失项的权重设置较为敏感；当不同优化目标在数值尺度、收敛速度或梯度方向上存在差异时，容易产生目标间的相互干扰、训练不稳定以及优化结果偏向部分目标的问题。此外，在单次训练过程中同时计算并反向传播多个目标函数，会显著增加计算量和显存占用，尤其在大规模图数据场景下，可能导致训练效率下降、计算资源消耗过高以及多目标权衡能力受限等技术瓶颈。

10、因此，亟需一种能够在统一框架下协调多个布局质量优化目标、降低多目标训练过程中的目标间干扰及资源消耗，同时提高图结构信息利用能力的图布局生成方法。

技术实现思路

1、本发明的目的在于解决现有图布局生成方法在多目标优化过程中采用多目标加权联合损失及图结构信息利用不足引起的目标间梯度相互干扰、训练不稳定、计算与显存开销较高以及布局质量难以有效权衡的技术问题。

2、为了实现上述目的本发明采用以下技术手段：

3、办发明提供了一种基于分阶段多目标优化和结构感知图神经网络的图布局生成方法，包括以下步骤：

4、步骤1、对输入图数据进行图结构解析及结构特征构建，得到邻接矩阵、节点特征以及包含节点间结构距离信息的边结构特征；

5、步骤2、对步骤1中得到的边结构特征进行神经网络映射和归一化处理，得到用于调制节点间消息传播强度的边权重；

6、步骤3、对步骤1中得到的节点特征以及步骤2中得到的边权重进行结构感知消息聚合和多层图神经网络特征变换，得到各节点对应的布局结构表示；

7、步骤4、对步骤3中得到的布局结构表示进行二维坐标映射，得到各节点对应的二维坐标以及当前预测图布局；

8、步骤5、对步骤4中得到的当前预测图布局分别进行多个布局质量指标计算，得到多个独立的布局质量优化目标；

9、步骤6、对步骤5中得到的多个布局质量优化目标按照预设阶段分配关系进行周期执行序列构建，得到各训练步骤对应的激活目标序列；

10、步骤7、根据步骤6中得到的激活目标序列选取当前训练步骤对应的单一布局质量优化目标，对所述单一布局质量优化目标执行损失计算和梯度反向传播，并根据所得梯度更新图布局生成模型参数；按照所述激活目标序列循环执行模型训练，得到训练完成的图布局生成模型。

11、上述方案中，步骤1包括：

12、步骤1.1、读取待处理图数据，解析图数据中的节点集合和边集合，根据节点连接关系建立邻接矩阵，得到图结构数据；

13、步骤1.2、对步骤1.1中得到的节点数据进行节点属性编码或节点特征初始化处理，得到节点特征矩阵；

14、步骤1.3、基于步骤1.1中得到的图结构数据，通过最短路径计算算法计算节点与节点之间的结构距离，得到节点对的结构距离信息；

15、步骤1.4、对步骤1.3得到的结构距离进行特征编码，构建对应边的结构特征向量：

16、

17、其中，为节点与节点之间的最短路径距离，为用于避免数值不稳定的预设正数。本发明基于不同结构边对节点信息传播贡献程度存在差异的思考，为此采用“神经网络映射和归一化处理，得到用于调制节点间消息传播强度的边权重”，解决现有图神经网络难以区分不同结构边重要程度、易受低相关性边干扰的技术问题。

18、上述方案中，步骤2包括：

19、步骤2.1、将步骤1.4中得到的边结构特征输入边权重网络，通过多层感知机对所述边结构特征进行非线性映射处理；

20、步骤2.2、对步骤2.1得到的映射结果通过sigmoid激活函数进行数值映射，得到各边对应的结构调制权重：

21、

22、其中，为节点与节点之间边的结构调制权重，为sigmoid激活函数，为多层感知机，为步骤1.4中得到的边结构特征向量；

23、步骤2.3、对步骤2.2得到的结构调制权重执行softmax归一化计算，得到节点向节点传播信息时对应的归一化边权重：

24、

25、其中，为节点向节点传播信息时的归一化边权重，为控制softmax权重分布集中程度的参数，为节点的邻居节点集合，为节点与节点之间边的结构调制权重。

26、本发明基于不同结构关系对节点特征更新贡献存在差异且深层消息传播易产生过度平滑的思考，为此采用“结构感知消息聚合和多层图神经网络特征变换”，解决现有图神经网络难以差异化利用结构信息并保持深层节点表示有效性的技术问题。

27、上述方案中，步骤3包括：

28、步骤3.1、根据步骤2.3中得到的归一化边权重，对目标节点的邻居节点隐藏特征执行加权消息聚合，得到结构感知的邻域聚合信息：

29、

30、其中，为邻居节点的隐藏特征，为步骤2.3中得到的归一化边权重，为目标节点的邻居节点集合；

31、步骤3.2、将步骤3.1中得到的邻域聚合信息与目标节点自身的隐藏特征进行融合，并通过全连接层执行特征变换，得到更新后的节点隐藏表示；

32、步骤3.2.1、获取当前布局变换层中的目标节点隐藏特征和邻域聚合信息。设当前布局变换层为第 l 层，读取目标节点 v 在当前层对应的隐藏特征 ，并读取步骤3.1根据结构感知边权重得到的节点 (v) 的邻域聚合信息：

33、

34、其中，n(v)表示节点 v 的邻居节点集合，表示非线性处理，为用于提高数值稳定性的预设正数；所述邻域聚合过程由步骤2得到的归一化边权重控制，使不同邻居节点按照其结构相关程度参与目标节点的特征更新。

35、步骤3.2.2、将目标节点自身隐藏特征与邻域聚合信息进行融合。将步骤3.2.1得到的目标节点自身隐藏特征  与邻域聚合信息  进行特征融合，得到融合特征：

36、

37、通过保留节点自身特征并加入结构感知邻域信息，使更新后的节点表示既包含当前节点已有的结构表示，又包含依据边结构相关程度选择性传播得到的邻域结构信息。

38、步骤3.2.3、对融合特征进行全连接特征变换。将步骤3.2.2得到的融合特征输入全连接层，执行特征空间变换，得到当前布局变换层产生的中间节点隐藏表示 ，即：

39、

40、其中，表示全连接特征变换函数。

41、通过上述处理，将目标节点自身信息与依据结构边权筛选后的邻域信息映射至统一的隐藏特征空间，为后续多层布局结构特征提取提供节点表示。

42、步骤3.3、对步骤3.2得到的节点隐藏表示执行归一化、非线性激活以及残差连接处理，得到当前布局变换层的输出；

43、步骤3.3.1、对节点隐藏表示执行归一化处理。对步骤3.2.3得到的中间节点隐藏表示执行归一化处理：

44、

45、其中，表示归一化操作，用于对不同节点或不同特征维度上的数值分布进行调整，降低连续多层特征变换过程中数值尺度变化对模型训练稳定性的影响。

46、步骤3.3.2、对归一化后的节点隐藏表示执行非线性激活。将步骤3.3.1得到的节点表示输入非线性激活函数，得到：

47、

48、利用非线性激活提高多层布局变换网络对复杂图结构关系的特征表达能力。

49、步骤3.3.3、在相邻布局变换块之间设置残差连接。为降低多个布局变换块连续执行图消息传播时产生的节点表示过度平滑以及深层网络梯度衰减，将当前布局变换块输入端的节点隐藏表示通过残差路径传递至当前布局变换块的输出端，使低层节点结构信息能够与当前布局变换块提取的结构特征共同形成输出节点表示。在一种输入特征维度与输出特征维度相同的实施方式中，残差处理可表示为：

50、

51、得到第 l 个布局变换块对应的输出节点表示 。

52、通过设置残差连接，使前层节点结构特征能够直接传递到较深的布局变换层，降低连续多层图消息传播造成的节点特征过度平滑以及梯度衰减，并使较低层提取的局部结构信息与较高层形成的较大范围结构信息共同参与后续图布局表示构建。

53、步骤3.4、将步骤3.3得到的节点表示输入下一布局变换层，重复执行消息聚合及特征变换处理，经过预设数量的布局变换层后，得到各节点对应的最终布局结构表示。

54、步骤3.4.1、将当前布局变换块输出作为下一布局变换块的节点输入。将步骤3.3得到的节点表示 作为第 l+1 个布局变换层的节点隐藏特征输入。

55、同时，在下一布局变换层中继续利用步骤2得到的结构感知边权，对各邻居节点的信息贡献进行调制。

56、步骤3.4.2、在下一布局变换层中重复执行结构感知消息聚合。对于第 l+1个布局变换层，根据目标节点 v 对应各邻居节点的归一化边权重重新执行步骤3.1中的结构感知消息聚合：

57、

58、其中，为根据节点间结构距离特征经边权重网络及softmax归一化得到的消息聚合权重，为relu激活函数，为数值稳定参数。通过逐层执行上述结构感知聚合，使节点能够逐步获取更大范围内的图拓扑结构信息，同时降低低相关结构连接在深层消息传播过程中的干扰。

59、步骤3.4.3、重复执行节点特征融合和全连接特征变换。将步骤3.4.2得到的结构感知邻域聚合信息  与目标节点自身的隐藏表示  进行融合，得到：

60、

61、并将融合后的节点特征输入当前布局变换块中的全连接层进行特征空间映射，得到：

62、=

63、其中，表示第 l+1 个布局变换块中layoutgnn层对应的可学习全连接特征变换函数。在一种实施方式中，所述全连接特征变换可表示为：

64、

65、其中，为当前布局变换块对应的可训练权重矩阵，为可训练偏置向量。通过上述全连接特征变换，将节点自身特征与结构感知邻域信息形成的融合特征映射至当前隐藏特征空间。

66、步骤3.4.4、输出最终布局结构表示。当完成预设数量 k 个布局变换块的处理后，将最后一个布局变换块得到的节点隐藏表示：

67、

68、确定为各节点对应的最终布局结构表示，并将所述最终布局结构表示输入步骤4中的二维坐标预测模块，以生成各节点对应的二维布局坐标。在一种具体实施方式中，所述布局变换网络包括11个依次连接的布局变换块；该数量属于具体实施参数，可根据待处理图数据规模、节点数量以及计算设备资源进行调整，不构成对布局变换层数量的限定。

69、本发明基于图布局生成需要将多层结构特征进一步映射为低维空间位置，以获得各节点对应布局坐标的思考，为此采用“预测当前图布局”，解决现有图神经网络获得节点结构表示后难以直接形成可用于图可视化的二维节点位置的问题。

70、上述方案中，步骤4包括：

71、步骤4.1、将母步骤3中得到的节点布局结构表示输入坐标预测网络；

72、步骤4.2、利用全连接层将节点布局结构表示映射至二维坐标空间，得到节点 (i)对应的二维坐标；

73、步骤4.3、将步骤4.2中得到的全部节点的二维坐标进行组合，得到当前预测图布局。

74、上述方案中，步骤5中，所述多个布局质量优化目标包括全局图结构保持目标、节点遮挡目标、边长度一致性目标以及局部角度可读性目标；

75、所述全局图结构保持目标的计算方式为：

76、

77、其中，和分别为节点和节点的二维坐标，为节点与节点之间的图最短路径距离；

78、所述节点遮挡目标的计算方式为：

79、

80、其中，为控制衰减程度的预设参数，为节点与节点之间的欧氏距离，为节点集合；

81、所述边长度一致性目标的计算方式为：

82、

83、其中，为边在当前二维布局中的欧氏长度，为所有边长度的均值，为边的总数，为边集合；

84、所述局部角度可读性目标的计算方式为：

85、

86、其中，为节点处第个相邻边夹角，为节点的度数，为节点集合。

87、本发明基于多目标优化任务需要按预设比例分阶段执行的思考，为此采用“按照预设阶段分配关系进行周期执行序列构建，得到各训练步骤对应的激活目标序列”，解决多目标同时优化导致的梯度干扰、训练控制困难及计算开销较大的技术问题。

88、上述方案中，步骤6包括：

89、步骤6.1、读取各布局质量优化目标对应的预设阶段数量，形成阶段数量向量，其中为第个布局质量优化目标的预设阶段数量，为布局质量优化目标的总数；

90、步骤6.2、对步骤6.1得到的阶段数量执行最大公约数计算，得到，并根据最大公约数对各目标的阶段数量进行压缩，得到第个目标在一个执行周期中的阶段数量, 周期长度；

91、步骤6.3、根据步骤6.2得到的各目标阶段数量，构建周期性目标执行序列；

92、步骤6.4、根据当前训练步骤编号、执行序列长度以及预设起始偏移量，通过取模计算从所述周期性目标执行序列中获取当前激活目标：

93、

94、其中，为当前训练步骤对应的激活布局质量优化目标，为周期性目标执行序列，为当前训练步骤编号，为预设起始偏移量，为一个执行周期包含的阶段总数。

95、本发明基于多目标同时参与训练易产生梯度干扰并增加计算开销的思考，为此采用“按照所述激活目标序列循环执行模型训练，得到训练完成的图布局生成模型”，解决多目标联合训练中梯度冲突、训练不稳定及资源消耗较大的技术问题。

96、上述方案中，步骤7包括：

97、步骤7.1、根据步骤6.4确定的当前激活目标，调用与所述激活目标对应的损失计算程序；

98、步骤7.2、通过图神经网络对当前批次图数据执行前向传播得到二维预测布局，并仅计算当前激活目标对应的损失值，当前训练步骤中的非激活布局质量优化目标不执行损失计算和反向传播；

99、步骤7.3、利用深度学习计算框架的自动微分程序，根据当前激活目标建立对应计算图并计算模型参数梯度；

100、步骤7.3.1、确定当前训练步骤参与梯度计算的目标。获取步骤7.2得到的当前激活布局质量优化目标对应的损失值，其中，t表示当前训练步骤，表示由周期性激活目标序列确定的当前目标索引。将所述确定为当前训练步骤唯一参与梯度反向传播的损失值；对于目标集合中其余非激活布局质量优化目标，其中，在当前训练步骤中不与进行加权组合，并且不参与当前模型参数梯度的计算。

101、由此，当前训练步骤不构造多个布局质量目标组成的联合损失，而仅保留当前激活目标与二维预测布局及图布局生成模型参数之间的计算依赖关系。

102、步骤7.3.2、基于当前激活目标执行自动微分及梯度反向传播。以步骤7.3.1确定的当前激活目标损失值 作为反向传播起点，利用支持自动微分的深度学习计算框架，沿当前二维预测布局的前向计算路径执行梯度反向传播，计算所述当前激活目标相对于图布局生成模型参数的梯度：

103、

104、其中，表示第 t 个训练步骤得到的模型参数梯度，表示图布局生成模型参数，表示图布局生成模型针对输入图g输出的二维预测布局。

105、当前训练步骤中的非激活布局质量优化目标不执行对应的梯度反向传播，因此不产生所述非激活目标相对于模型参数的梯度。

106、步骤7.3.3、输出当前单目标梯度作为模型参数更新依据。将步骤7.3.2得到的模型参数梯度 作为当前训练步骤的参数更新依据，并传递至后续模型参数更新步骤。所述梯度仅反映当前激活布局质量优化目标对模型参数的优化方向，而非多个布局质量优化目标梯度的加权求和结果。完成当前训练步骤后，在下一训练步骤中按照步骤6得到的周期性激活目标序列重新确定新的激活目标，并针对新的激活目标重复执行上述单目标损失计算及梯度反向传播过程，从而使不同布局质量优化目标按照预设阶段分配关系依次参与模型参数优化。

107、步骤7.4、根据步骤7.3得到的模型参数梯度，通过优化器更新图布局生成模型参数, 其中，表示第 t 个训练步骤更新前的模型参数，表示完成当前训练步骤更新后的模型参数，表示学习率；

108、步骤7.5、在完成当前训练步骤后更新训练步骤编号，并按照步骤6生成的周期性目标执行序列确定下一训练步骤的激活目标，使多个布局质量优化目标在不同训练步骤中依次参与模型参数更新；

109、步骤7.6、重复执行步骤2至步骤7，直至达到预设训练终止条件，得到训练完成的图布局生成模型；将待布局图数据输入所述训练完成的图布局生成模型，经过结构感知消息聚合和二维坐标预测后，输出目标图的二维布局结果。

110、本发明还提供了一种基于分阶段多目标优化和结构感知图神经网络的图布局生成系统，包括：

111、图数据输入及预处理模块，用于获取待处理图数据并将所述图数据转换为邻接矩阵、节点特征矩阵及节点连接关系；

112、边结构特征构建模块，用于根据节点之间的图结构关系生成包含节点间结构距离信息的边结构特征；

113、边权重计算模块，用于通过边权重网络对所述边结构特征进行非线性映射，得到对应边的结构调制权重；

114、图布局特征变换模块，用于利用图神经网络并基于所述结构调制权重对节点特征进行多层结构感知消息传递和特征变换，得到各节点对应的布局结构表示；

115、二维坐标预测模块，用于将所述布局结构表示映射至二维坐标空间，得到各节点对应的二维坐标；

116、多目标评价模块，用于根据预测得到的节点二维坐标分别计算多个独立的布局质量优化目标；

117、分阶段多目标优化模块，用于根据预设阶段分配关系构建周期性目标执行序列，并在每一训练步骤中仅激活一个布局质量优化目标执行损失计算、梯度反向传播及模型参数更新。

118、本发明还提供了一种电子设备，包括处理器和存储器，所述存储器中存储有计算机程序，所述处理器执行所述计算机程序时实现所述的基于分阶段多目标优化和结构感知图神经网络的图布局生成方法。

119、本发明还提供了一种计算机可读存储介质，所述计算机可读存储介质中存储有计算机程序，所述计算机程序被处理器执行时实现所述的基于分阶段多目标优化和结构感知图神经网络的图布局生成方法。

120、因为本发明采用上述技术手段，因此具备以下有益效果：

121、1.本发明通过步骤6构建周期性目标执行序列，并通过步骤7在每一训练步骤中仅激活一个布局质量目标进行损失计算、梯度反向传播及模型参数更新，避免现有联合训练方式在同一训练步骤中同时计算全部目标。实验结果表明，在相同 gvlm 模型架构下，本发明采用的 pmo 方法平均训练时间为 2.98 min/epoch、峰值显存占用为 3.64 gb、计算量为 5.56×1012 flops/epoch；相比 joint training 的 8.26 min/epoch、14.69 gb 和19.21×1012 flops/epoch，分别仅为其约 36.1%、24.8% 和 28.9%，即训练时间约降低63.9%、峰值显存约降低 75.2%、flops 约降低 71.1%，从而解决多目标同步计算导致训练资源消耗较高的技术问题。

122、2.本发明通过步骤5将 stress、node occlusion、edge length variance 和angular resolution 保持为相互独立的优化目标，并通过步骤6和步骤7将其沿训练时间维度分阶段执行，从而避免多个目标在同一步骤中形成联合梯度。实验结果显示，在相同gvlm 架构下，pmo 在 stress、occ、edgevar 和 angle 指标上的结果分别为 2136.86、1431.89、168.537 和 596.50，在显著降低训练资源消耗的同时，与 joint training、dwa和 gradnorm 等多目标训练方法保持总体可竞争的布局质量，说明本发明能够改善多目标训练中的质量—效率权衡。

123、3. 本发明通过步骤1构建节点间结构距离特征，并通过步骤2学习边调制权重，再母步骤3中利用所述边权重执行结构感知消息聚合，使不同结构连接按照其相关程度参与节点表示更新。消融实验中，在均采用 pmo 的情况下，引入边权重网络后，stress 从2152.49 降至 2136.02，occ 从 1445.63 降至 1430.02，angle 从 609.884 降至598.400，表明该结构感知边权机制能够改善全局结构保持、节点空间分离及局部角度可读性等布局质量指标。

124、4. 本发明采用单目标阶段化执行方式，使新增布局质量目标主要扩展目标集合及阶段调度序列，而不要求在每一次参数更新中同时计算全部目标。实验中，当优化目标数量由 1个增加至5个时，平均训练时间仍维持在约 2.66～2.85 min/epoch 的范围内，未随目标数量增加呈明显单调增长，说明该方法在增加布局优化目标时具有较低的单步运行时间敏感性，适合扩展至更复杂的多目标图布局任务。

125、5. 本发明通过将基于边结构权重的差异化消息聚合机制与基于周期执行序列的分阶段单目标训练机制进行组合，使前者提高图神经网络对有效结构连接的利用能力，后者降低多目标同步反向传播产生的梯度干扰及资源开销，两者共同作用，使模型既能够获得具有结构感知能力的节点布局表示，又能够以较低训练成本完成多个布局质量目标的持续优化。消融实验中，完整的 gvlm-pmo 在四种对比变体中取得了最优的 stress（2136.02）、occ（1430.02）和 angle（598.400） 三项指标，同时 pmo 相比 joint training显著降低训练时间、显存占用和 flops，由此形成单独采用边权机制或单独采用传统联合优化方式所不能同时获得的结构表达能力与训练资源效率兼顾的技术效果。