使用卷积神经网络估计随机图的稳定数
文章提出一种基于深度学习和启发式算法的图卷积网络方法,用于解决某些NP困难问题,并在四个NP困难问题和五个数据集上进行了评估,结果表明该方法在某些NP困难问题上已经达到了高度优化的最新启发式算法的水平,并具有较强的泛化性和扩展性。
Oct, 2018
本文介绍了如何使用简单的 GNN 架构来解决图着色的基本组合问题,并且展示了该模型在独立于训练数据的图数据上的泛化能力以及优于其他基线模型的表现。同时,我们还展示了如何将节点嵌入在多维空间中进行聚类,从而获得构造性解决方案。我们的结果有助于缩小人们对 GNN 算法学习的差距,并提供了符号推理与深度学习系统集成的可靠方法。
Mar, 2019
本文研究了图卷积神经网络在半监督学习环境下的算法稳定性及其一阶推论;通过分析单层GCNN模型的稳定性,导出其一般化保证,提出稳定性关于其卷积核最大绝对特征值的依赖规律,并说明产生保证所需的卷积核最大特征值与图大小无关,为设计保证的算法稳定性的新型及更好的卷积核提供新思路。最后在多个真实世界的图数据集上评估了实验结果,实验结果支持理论结果。
May, 2019
该论文从理论角度研究了如何利用图神经网络解决组合问题的近似算法,并提出了一种新的GNN类别,揭示了GNN的相对近似比,并证明了在节点特征中添加染色可以提高学习算法的近似比。
May, 2019
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建TSP图表示,并通过高度并行化的Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从50个节点降低到0.01%,100个节点从 2.26%降至1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
本文提出了一种基于图卷积神经网络的分支定界变量选择新模型,通过模仿学习和强分支专家规则训练,成功解决了组合优化问题。实验结果表明,该方法不仅在分支机制上优于现有的机器学习方法,而且在大问题上也优于现有的专家设计分支规则。
Jun, 2019
本研究通过对随机图模型的分析,研究了图卷积网络(GCN)的性质,包括 GCN 达到其连续对应的收敛性以及 GCN 对随机图小变形的稳定性,这有助于解释卷积表示在欧几里得域中成功的原因。
Jun, 2020
在图像分类中,卷积神经网络通过卷积和池化实现了重大进展;然而,对于图中的池化方法存在着一些问题,如图的断开或过连接、低减少率和删除大部分图等。本文基于最大独立集的概念提出了三种池化方法,并通过实验结果确认最大独立集约束对图池化的相关性。
Jul, 2023