在社交网络中找到有影响力的用户是一个基本问题，具有许多可能的应用程序。将社交网络视为图形，可以通过位于网络中给定数量的跳数内的邻居的数量来测量一组用户的影响，其中每个跳标标记了影响扩散的步骤。在本文中，我们将IM的问题减少到预算受限的D-Hop主导集合问题（KDDSP）。我们提出了一个统一的机器学习（ML）框架，FastCover，通过以无人监督的方式学习高效的贪婪策略来解决KDDSP。作为框架的一个关键组成部分，我们设计了一种新颖的图形神经网络（GNN）架构，图反转关注网络（GRAT），其捕获邻居之间的扩散过程。与用于组合优化问题的大多数启发式算法和并发ML框架不同，FastCover确定从GNN的一个正向传播的节点的分数确定整个种子集，并且在图形大小中具有时间复杂性准线性。综合图和现实世界社交网络的实验表明，FastCover通过并发算法呈现的更好或相当的质量来找到解决方案，同时实现超过1000x的加速。

Influence Maximization (IM) is a classical combinatorial optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. It aims at selecting a small number of users such that maximizing the influence spread across the online social network. Because of its potential commercial and academic value, there are a lot of researchers focusing on studying the IM problem from different perspectives. The main challenge comes from the NP-hardness of the IM problem and \#P-hardness of estimating the influence spread, thus traditional algorithms for overcoming them can be categorized into two classes: heuristic algorithms and approximation algorithms. However, there is no theoretical guarantee for heuristic algorithms, and the theoretical design is close to the limit. Therefore, it is almost impossible to further optimize and improve their performance. With the rapid development of artificial intelligence, the technology based on Machine Learning (ML) has achieved remarkable achievements in many fields. In view of this, in recent years, a number of new methods have emerged to solve combinatorial optimization problems by using ML-based techniques. These methods have the advantages of fast solving speed and strong generalization ability to unknown graphs, which provide a brand-new direction for solving combinatorial optimization problems. Therefore, we abandon the traditional algorithms based on iterative search and review the recent development of ML-based methods, especially Deep Reinforcement Learning, to solve the IM problem and other variants in social networks. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research. Finally, the challenges that need to be solved urgently in future IM research are pointed out.

Steiner树问题（STP）在图中旨在在连接给定的顶点集的图表中找到一个最小权重的树。它是一种经典的NP - 硬组合优化问题，具有许多现实世界应用（例如，VLSI芯片设计，运输网络规划和无线传感器网络）。为STP开发了许多精确和近似算法，但它们分别遭受高计算复杂性和弱案例解决方案保证。还开发了启发式算法。但是，它们中的每一个都需要应用域知识来设计，并且仅适用于特定方案。最近报道的观察结果，同一NP-COLLECLIAL问题的情况可能保持相同或相似的组合结构，但主要在其数据中不同，我们调查将机器学习技术应用于STP的可行性和益处。为此，我们基于新型图形神经网络和深增强学习设计了一种新型模型瓦坎。 Vulcan的核心是一种新颖的紧凑型图形嵌入，将高瞻度图形结构数据（即路径改变信息）转换为低维矢量表示。鉴于STP实例，Vulcan使用此嵌入来对其路径相关的信息进行编码，并基于双层Q网络（DDQN）将编码的图形发送到深度加强学习组件，以找到解决方案。除了STP之外，Vulcan还可以通过将解决方案（例如，SAT，MVC和X3C）来减少到STP来找到解决方案。我们使用现实世界和合成数据集进行广泛的实验，展示了vulcan的原型，并展示了它的功效和效率。

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

随着组合优化的机器学习领域，通过这种新的视角，传统问题重新敷设和重新进行了折叠。大多数文献中的绝大多数侧重于小的图形问题，而几个真实问题致力于大图。在这里，我们专注于两个这样的问题：影响估计，＃p-coll counting问题，以及影响最大化，np-colly问题。我们开发Glie，一个图形神经网络（GNN），其固有地参数化影响估计的上限并在小模拟图上培训。实验表明，Glie为真正的图表提供了精确的影响，该估计比列车集大10倍。更重要的是，它可以用于对大大更大图的影响最大化，因为预测排名不受精度降低的影响。我们使用Glie制定一个Cely Optimization，而不是模拟的影响估计，超越了影响最大化的基准，尽管具有计算开销。为了平衡时间复杂性和影响质量，我们提出了两种不同的方法。第一个是Q-Network，学会使用Glie的预测顺序选择种子。第二种基于Glie的表示在构建种子集的同时，基于Glie的表示来定义一个可怕的子模块功能。后者提供了时间效率和影响的最佳组合，表现优于SOTA基准。

图表神经网络（GNNS）在行业中，由于各种预测任务的表现令人印象深刻，在行业中获得了显着的采用。然而，单独的性能是不够的。任何广泛部署的机器学习算法都必须强大到对抗性攻击。在这项工作中，我们调查了GNN的这个方面，识别漏洞，并将它们链接到图形属性，可能导致更安全和强大的GNN的开发。具体而言，我们制定任务和模型不可知逃避攻击问题，其中对手修改了测试图以影响任何未知下游任务的性能。提出的算法，盛大（$ GR $ APH $ A $ TTACK通过$ N $ eighbors $ D $ Istorration）显示节点邻域的失真在急剧损害预测性能方面是有效的。虽然邻里失真是一个NP难题，但是宏伟设计了通过具有深入$ Q $ -Learning的图形同构网络的新组合的启发式。关于实际数据集的广泛实验表明，平均而言，盛大的速度高达50美元，而不是最先进的技术，同时速度超过100美元。

图表表示学习是一种快速增长的领域，其中一个主要目标是在低维空间中产生有意义的图形表示。已经成功地应用了学习的嵌入式来执行各种预测任务，例如链路预测，节点分类，群集和可视化。图表社区的集体努力提供了数百种方法，但在所有评估指标下没有单一方法擅长，例如预测准确性，运行时间，可扩展性等。该调查旨在通过考虑算法来评估嵌入方法的所有主要类别的图表变体，参数选择，可伸缩性，硬件和软件平台，下游ML任务和多样化数据集。我们使用包含手动特征工程，矩阵分解，浅神经网络和深图卷积网络的分类法组织了图形嵌入技术。我们使用广泛使用的基准图表评估了节点分类，链路预测，群集和可视化任务的这些类别算法。我们在Pytorch几何和DGL库上设计了我们的实验，并在不同的多核CPU和GPU平台上运行实验。我们严格地审查了各种性能指标下嵌入方法的性能，并总结了结果。因此，本文可以作为比较指南，以帮助用户选择最适合其任务的方法。

我们提出了一个通用图形神经网络体系结构，可以作为任何约束满意度问题（CSP）作为末端2端搜索启发式训练。我们的体系结构可以通过政策梯度下降进行无监督的培训，以纯粹的数据驱动方式为任何CSP生成问题的特定启发式方法。该方法基于CSP的新型图表，既是通用又紧凑的，并且使我们能够使用一个GNN处理所有可能的CSP实例，而不管有限的Arity，关系或域大小。与以前的基于RL的方法不同，我们在全局搜索动作空间上运行，并允许我们的GNN在随机搜索的每个步骤中修改任何数量的变量。这使我们的方法能够正确利用GNN的固有并行性。我们进行了彻底的经验评估，从随机数据（包括图形着色，Maxcut，3-SAT和Max-K-Sat）中学习启发式和重要的CSP。我们的方法表现优于先验的神经组合优化的方法。它可以在测试实例上与常规搜索启发式竞争，甚至可以改善几个数量级，结构上比训练中看到的数量级更为复杂。

组合优化是运营研究和计算机科学领域的一个公认领域。直到最近，它的方法一直集中在孤立地解决问题实例，而忽略了它们通常源于实践中的相关数据分布。但是，近年来，人们对使用机器学习，尤其是图形神经网络（GNN）的兴趣激增，作为组合任务的关键构件，直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入，因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾，旨在优化和机器学习研究人员。

由于其在线社交网络上的广泛应用，影响力最大化（IM）在过去几十年中引起了广泛关注。当前的IM研究缺乏对种子如何产生影响效应的人类理解的解释，从而降低了现有解决方案的可信度，尽管它们适用。由于IM的复杂性，目前的大多数研究都集中在估计一阶扩散能力上，并且经常考虑从不同种子分散的流量之间的相互作用。这项研究使用SOBOL指数，这是基于方差的灵敏度分析的基石，可以分解对单个种子及其相互作用的影响效果。 SOBOL指数是针对IM上下文量身定制的，通过将种子选择作为二进制变量进行建模。这种说明方法普遍适用于所有网络类型，IM技术和扩散模型。基于解释方法，提出了一个称为Sobolim的一般框架，以通过过度选择节点，然后是消除策略来提高IM研究的性能。关于合成和现实世界图的实验表明，对影响效应的解释可以可靠地识别各种网络和IM方法之间种子之间的关键高阶相互作用。在经验上，Sobolim在有效性和效率上具有优势。

图形上的组合优化问题（COP）是优化的基本挑战。强化学习（RL）最近成为解决这些问题的新框架，并证明了令人鼓舞的结果。但是，大多数RL解决方案都采用贪婪的方式来逐步构建解决方案，因此不可避免地对动作序列构成不必要的依赖性，并且需要许多特定于问题的设计。我们提出了一个通用的RL框架，该框架不仅表现出最先进的经验表现，而且还推广到各种各样的警察。具体而言，我们将状态定义为解决问题实例的解决方案，并将操作作为对该解决方案的扰动。我们利用图形神经网络（GNN）为给定的问题实例提取潜在表示，然后应用深Q学习以获得通过翻转或交换顶点标签逐渐完善解决方案的策略。实验是在最大$ k $ cut和旅行推销员问题上进行的，并且针对一系列基于学习的启发式基线实现了绩效改善。

We propose a geometric scattering-based graph neural network (GNN) for approximating solutions of the NP-hard maximum clique (MC) problem. We construct a loss function with two terms, one which encourages the network to find highly connected nodes and the other which acts as a surrogate for the constraint that the nodes form a clique. We then use this loss to train an efficient GNN architecture that outputs a vector representing the probability for each node to be part of the MC and apply a rule-based decoder to make our final prediction. The incorporation of the scattering transform alleviates the so-called oversmoothing problem that is often encountered in GNNs and would degrade the performance of our proposed setup. Our empirical results demonstrate that our method outperforms representative GNN baselines in terms of solution accuracy and inference speed as well as conventional solvers like Gurobi with limited time budgets. Furthermore, our scattering model is very parameter efficient with only $\sim$ 0.1\% of the number of parameters compared to previous GNN baseline models.

本文介绍了一种增强的元启发式（ML-ACO），将机器学习（ML）和蚁群优化（ACO）结合起来解决组合优化问题。为了说明我们ML-ACO算法的底层机制，我们首先描述测试问题，定向问题。在这个问题中，目的是找到一个路线，该路线在时间预算中在图中访问顶点的子集，以最大化收集的分数。在我们ML-ACO算法的第一阶段，使用一组小问题实例训练ML模型，其中已知最佳解决方案。具体地，分类模型用于将边缘分类为最佳路由的一部分，或不使用特定于问题的特征和统计测量。然后，训练模型用于预测测试问题实例图表中的边缘所属的概率属于相应的最优路由。在第二阶段，我们将预测的概率纳入我们算法的ACO组件，即，使用概率值作为启发式权重或者热启动信息素矩阵。这里，在构建可行的路线时偏向有利于这些预测的高质量边缘的概率值。我们已经测试了多种分类模型，包括图形神经网络，逻辑回归和支持向量机，实验结果表明，我们的解决方案预测方法一直促进ACO的性能。此外，我们经验证明我们在小型合成实例上培训的ML模型概括为大型合成和现实世界的情况。我们将ML与META-HEURISTIC集成的方法是通用的，可以应用于各种优化问题。

数据处理的最新进展刺激了对非常大尺度的学习图的需求。众所周知，图形神经网络（GNN）是解决图形学习任务的一种新兴和有力的方法，很难扩大规模。大多数可扩展模型应用基于节点的技术来简化GNN的昂贵图形消息传播过程。但是，我们发现当应用于百万甚至数十亿尺度的图表时，这种加速度不足。在这项工作中，我们提出了Scara，这是一种可扩展的GNN，具有针对图形计算的特征优化。 Scara有效地计算出从节点功能中嵌入的图形，并进一步选择和重用功能计算结果以减少开销。理论分析表明，我们的模型在传播过程以及GNN培训和推理中具有确保精度，实现了子线性时间的复杂性。我们在各种数据集上进行了广泛的实验，以评估圣aca的功效和效率。与基线的性能比较表明，与快速收敛和可比精度相比，与当前的最新方法相比，圣aca最高可达到100倍的图形传播加速度。最值得注意的是，在100秒内处理最大的十亿个GNN数据集纸100m（1.11亿节点，1.6B边缘）上的预先计算是有效的。

在影响最大化（IM）的现实世界应用中，网络结构通常是未知的。因此，我们可以通过仅探索基础网络的一部分来确定最有影响力的种子节点，但对于节点查询的预算很小。由于收集节点元数据比通过查询节点调查节点之间的关系更具成本效益，我们提出了IM-Meta，这是一种端到端的解决方案，这是通过从查询和节点中检索信息的网络中IM的端到端解决方案元数据。但是，由于元数据的嘈杂性质和连通性推断的不确定性，使用这种元数据来帮助IM过程并非没有风险。为了应对这些挑战，我们制定了一个新的IM问题，旨在找到种子节点和查询节点。在IM-META中，我们开发了一种有效的方法，该方法可以迭代执行三个步骤：1）我们通过暹罗神经网络模型学习了收集的元数据和边缘之间的关系，2）我们选择了许多推断的自信边缘来构建增强的图形， 3）我们通过使用我们的拓扑感知的排名策略来最大程度地提高推断影响扩展，以确定查询的下一个节点。通过查询仅5％的节点，IM-META达到了上限性能的93％。

我们考虑了最大化的影响（IM）问题：'如果我们能说服社交网络中的一部分个人采用新产品或创新，目的是触发大量的进一步收养级联我们应该定位吗？正式地，这是在社交网络中选择$ K $种子节点的任务，以使网络中预期的影响节点（在某些影响下传播模型）最大化。在文献中已经广泛研究了这个问题，并提出了几种解决方案方法。但是，大多数基于模拟的方法涉及耗时的蒙特卡洛模拟，以计算种子节点在整个网络中的影响。这限制了这些方法在大型社交网络上的适用性。在本文中，我们有兴趣以时间效率的方式解决影响最大化的问题。我们提出了一种社区意识的分歧和纠纷策略，涉及（i）学习社交网络的固有社区结构，（ii）通过解决每个社区的影响最大化问题，以及（iii）选择最终的影响力来生成候选解决方案。使用新颖的渐进预算计划来自候选解决方案的个人。我们提供有关现实世界社交网络的实验，表明所提出的算法在经验运行时和启发式算法方面优于基于仿真的算法。我们还研究了社区结构对算法性能的影响。我们的实验表明，具有较高模块化的社区结构导致所提出的算法在运行时和影响方面表现更好。

深度强化学习（DRL）赋予了各种人工智能领域，包括模式识别，机器人技术，推荐系统和游戏。同样，图神经网络（GNN）也证明了它们在图形结构数据的监督学习方面的出色表现。最近，GNN与DRL用于图形结构环境的融合引起了很多关注。本文对这些混合动力作品进行了全面评论。这些作品可以分为两类：（1）算法增强，其中DRL和GNN相互补充以获得更好的实用性； （2）特定于应用程序的增强，其中DRL和GNN相互支持。这种融合有效地解决了工程和生命科学方面的各种复杂问题。基于审查，我们进一步分析了融合这两个领域的适用性和好处，尤其是在提高通用性和降低计算复杂性方面。最后，集成DRL和GNN的关键挑战以及潜在的未来研究方向被突出显示，这将引起更广泛的机器学习社区的关注。

在线社交平台，例如Twitter，Facebook，LinkedIn和微信在过去十年中的发展非常快，并且是人们互相交流和共享信息的最有效平台之一。由于“口口相传”的效果，信息通常可以在这些社交媒体平台上迅速传播。因此，重要的是研究推动信息扩散的机制并量化信息传播的后果。许多努力都集中在这个问题上，以帮助我们更好地理解并在病毒营销和广告中实现更高的性能。另一方面，在过去的几年中，神经网络的发展蓬勃发展，导致大量的图表学习（GRL）模型。与传统模型相比，GRL方法通常被证明更有效。在本文中，我们对现有作品进行了全面的审查，该综述使用GRL方法用于普及预测问题，并根据其主要使用的模型和技术将相关文献分为两个大类：基于嵌入的方法和深度学习方法。深度学习方法进一步分为六个小类：卷积神经网络，图形卷积网络，图形注意力网络，图形神经网络，复发性神经网络和增强学习。我们比较这些不同模型的性能，并讨论它们的优势和局限性。最后，我们概述了受欢迎程度预测问题的挑战和未来机会。

Graph神经网络（GNN）最近已成为使用图的机器学习的主要范式。对GNNS的研究主要集中于消息传递神经网络（MPNNS）的家族。与同构的Weisfeiler-Leman（WL）测试类似，这些模型遵循迭代的邻域聚合过程以更新顶点表示，并通过汇总顶点表示来更新顶点图表。尽管非常成功，但在过去的几年中，对MPNN进行了深入的研究。因此，需要新颖的体系结构，这将使该领域的研究能够脱离MPNN。在本文中，我们提出了一个新的图形神经网络模型，即所谓的$ \ pi $ -gnn，该模型学习了每个图的“软”排列（即双随机）矩阵，从而将所有图形投影到一个共同的矢量空间中。学到的矩阵在输入图的顶点上强加了“软”顺序，并基于此顺序，将邻接矩阵映射到向量中。这些向量可以被送入完全连接或卷积的层，以应对监督的学习任务。在大图的情况下，为了使模型在运行时间和记忆方面更有效，我们进一步放松了双随机矩阵，以使其排列随机矩阵。我们从经验上评估了图形分类和图形回归数据集的模型，并表明它与最新模型达到了性能竞争。

Graph mining tasks arise from many different application domains, ranging from social networks, transportation to E-commerce, etc., which have been receiving great attention from the theoretical and algorithmic design communities in recent years, and there has been some pioneering work employing the research-rich Reinforcement Learning (RL) techniques to address graph data mining tasks. However, these graph mining methods and RL models are dispersed in different research areas, which makes it hard to compare them. In this survey, we provide a comprehensive overview of RL and graph mining methods and generalize these methods to Graph Reinforcement Learning (GRL) as a unified formulation. We further discuss the applications of GRL methods across various domains and summarize the method descriptions, open-source codes, and benchmark datasets of GRL methods. Furthermore, we propose important directions and challenges to be solved in the future. As far as we know, this is the latest work on a comprehensive survey of GRL, this work provides a global view and a learning resource for scholars. In addition, we create an online open-source for both interested scholars who want to enter this rapidly developing domain and experts who would like to compare GRL methods.