一种基于混合图神经网络的最大团问题的解决方法

一种基于混合图神经网络的最大团问题的解决方法

最大团问题（MCP）是在一般图中找到最大基数的完整子图。它是一个NP-hard问题，难以在有限的时间内解决。MCP是研究最多的组合优化问题之一。MCP在许多领域都有广泛的实际应用，例如在生物信息学邻域、金融网络领域，通信网络等多个领域出现了越来越多的团问题的实际应用。

本发明涉及深度学习领域，具体涉及到使用混合图神经网络解决最大团问题（MCP）。

背景技术

1. MCP是在一般图中找到最大基数的完整子图。它是一个NP-hard问题，难以在有限的时间内解决。MCP是研究最多的组合优化问题之一。MCP在许多领域都有广泛的实际应用，例如在生物信息学邻域、金融网络领域，通信网络等多个领域出现了越来越多的团问题的实际应用。
2. 鉴于MCP的重要性和实际意义，人们已经投入了大量的精力来开发各种解决MCP的方法。一方面，主要基于一般的分支定界框架设计了有效的精确方法；这些方法在理论上具有保证解的最优性的优点。然而，由于MCP固有的计算复杂性，求精确解的方法在一般情况下可能需要令人难以置信的计算时间，并且通常只适用于有限规模的问题。另一方面，为了处理无法在合理时间内获得最优解的问题，人们设计了各种启发式和元启发式算法，目的是在可接受的时间内为大型问题提供尽可能好的最优解。但是这些算法仍然具有求解时间过长的缺陷。
3. 图神经网络的出现重新激发了人们对快速解决组合优化问题的兴趣。图神经网络是一种基于图的神经网络模型，能够对节点和边进行端到端的学习，具有良好的可扩展性和泛化能力。图神经网络的快速发展为解决上述的问题提供一个有效的方案。图神经网络（GNN）采用嵌入传播算法来迭代地聚合节点的邻居嵌入信息，从而使得每个节点能够获取邻居的信息。由于处理结构化数据和探索结构化信息方面的优势，基于图神经网络的方法已成为获取图的特征表示最先进的新方法。然而，现有的图神经网络方法由于经过多层图神经网络后，提取到的信息不再精确，可能会产生过平滑的问题，导致求解图上的最大团的精确度较低。为此，我们设计了一种方法，使提取到的节点信息更加精确，并通过精确的节点信息求解图的MCP。

技术实现思路

1. 本发明所要解决的技术问题在于：如何有效地解决传统图神经网络算法优化问题，提高算法求解MCP的性能，提供了一种基于混合图神经网络的最大团问题的解决方法，首先在训练集上我们通过最小化无监督的损失函数对混合图神经网络进行训练；输入图数据，通过训练好的神经网络将表示的一组节点级数据转换成概率向量,该概率向量表示每个节点属于最大团的概率；最后是解码器，通过贪心算法将概率向量映射为输入图上的最大团，得到MCP的近似最优解。
2. 本发明是通过以下技术方案解决上述技术问题的，本发明包括以下步骤：
3. S1：给定图G＝(V,E)，其中V表示图的顶点集，E表示边集；不同的图根据顶点数|V|构建，并且用N*N的邻接矩阵表示，将数据集分割为训练接，测试集，验证集，三者的比例为6:2:2；
4. S2：在训练集的图上使用无监督损失函数来训练神经网络，该损失函数有两项，一项鼓励网络寻找高度连接的节点，另一项作为节点形成集团约束的代理；对输入的图G构建节点级多尺度丰富表示，图神经网络和扩散散射网络同时对图G进行处理，其中图神经网络获得的是低维度的信息，扩散散射网络获得的是高维度的信息；对经过图神经网络和扩散散射网络提取出的节点表示信息进行串联操作，获得了更精确的节点表示；
5. S3：对经过网络层提取的信息经过一个全连接层，将矩阵转换为向量P，然后对向量P进行归一化处理，得到了关于节点是最大团一部分可能性的概率向量；
6. S4：使用贪心算法从概率向量中选取最大团。

更进一步地

在所述步骤S1中，图G为无向图，邻接矩阵A中的元素均∈{0,1}，其中0表示图中对应两个顶点之间没有边相连，1表示有边相连。在训练集上训练算法，在验证集上对我们的超参数进行调整，最后在测试集上测试最终的算法。

所述步骤S2包括以下步骤：

S21:损失函数选择为

其中Wu,v只能等于0或1，如果Wu,v＝1则节点u,v相连，反之则为0；P为概率向量，若Pv≈1则节点v是最大团的一个节点，反之则Pv≈0；α是超参数，用来平衡前后两项，α的具体值我们在验证集中调整。

S22：图G在扩散散射神经网络和图神经网络中进行训练。其中在扩散散射神经网络中设置一个可学习的参数λ＝{λ0,…,λj}用于在扩散散射神经网络的每一层进行参数共享，接下来使用一个可学习的矩阵对加权后的每一层节点的特征表示进行线性投影，其中HHID是隐藏层的维度。节点特征矩阵通过扩散散射网络，得到了新的节点特征FL(G,X)，其中F0(G,X)＝X。将节点特征矩阵与可学习的矩阵W相乘，即得到了节点的尺度间加权表示：

其中，J表示阶数，||是指串联运算，S(L)表示第L层的节点经过散射网络后的加权后特征，表示散射路径，τ＝{(ψi；0≤i≤j)}表示一步路径，FT表示散射路径T对应节点的散射特征，C(T)表示节点T的孩子节点。

S23:图G经过图神经网络得到一组关于节点的特征表示：

其中，A表示图的邻接矩阵，W(L)是一个可学习的权重矩阵，H(L)是第L层的节点特征矩阵。

S24:然后将这两个节点特征进行串联操作，使得节点信息得到了增强：

其中σ为非线性激活函数，||表示串联操作。经过多层前向传播，可以得到融合高维和低维的多维度信号的节点级嵌入特征。

在所述步骤S3中，包括以下步骤

S31：将精确的节点表征信息通过一个全连接层，让节点信息矩阵转换为向量P。

S32：然后我们使用min-max normalization，也称为离差标准化,是对原始数据的线性变换,使向量P里的值映射到[0-1]之间，向量P就转换成了一个代表节点在最大团中的一部分的概率。

在所述步骤S4中

我们通过贪心算法以概率从大到小的顺序扫描输出的每个节点，并在满足最大团约束时才将该节点添加到集合中来有效地解码团；贪心算法的输入是经过之前的步骤得到的概率向量，以及有N个节点的图G和样本长度N，N为图G的顶点个数；创建函数对节点进行降序排列，将第一个节点作为最大团的一部分，即：选择下一个节点，若该节点与之前的节点构成一个最大团，则将该节点加入到最大团中，判断下一个节点是否是最大团的一部分，直到跳出循环；最后，通过贪心算法，得到一个长度在1和N之间的一个最大团；为了量化说明本发明的有效性，将算法在三个真实世界数据集IMDB、COLLAB、TWITTER上与其他经典算法进行比较，求解最大团的效果将采用平均测试近似分数(三次运行的平均值±标准差)和在真实世界数据集中求解最大团所需的平均时间(括号中的数字)，以秒/图(S/G)为单位进行测量；实验结果如表1所示。

表一、各算法近似分数对比

其中SCATTERINGCLIQUE为混合几何散射网络算法，GCN为图卷积神经网络算法，ERD″OS为无监督约束的图神经网络算法，GUROBI为整数规划求解器，HEURISTIC为启发式算法。通过表一，我们可以得出对于简单的数据集，如IMDB数据集，大多数算法都可以达到类似的性能；对于较为复杂的数据集TWITTER，我们的方法要优于大部分其他的神经网络算法，近似分数只比GUROBI算法低，但是我们的速度快于GUROBI算法。所以本发明的效果最好。

本发明相比于现有技术具有以下优点：

(1)本发明通过混合扩散散射网络与图神经网络，可以解决现有的基于传统的神经网络方法忽略高阶信息从而无法充分利用邻居节点信息求解最大团的问题。
(2)本发明采用无监督的损失函数，所学习的分布在可控概率下包含一个低成本的解，而且该解服从MCP的约束。
(3)本发明在散射网络中进行权重共享，以更好的捕捉节点之间的复杂关系，从而更好的利用邻居信息进行求解最大团。