1、【 arXiv:2111.10810】Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
Author ：Haizhou Du, Zong Yan, Qiao Xiang, Qinqing Zhan
导读：图中的Steiner树问题(STP)的目标是在连接一组给定顶点的图中寻找一棵权值最小的树。它是一个经典的NP-hard组合优化问题，在实际中有很多应用(如VLSI芯片设计、交通网络规划和无线传感器网络)。针对STP问题，已有许多精确算法和近似算法，但分别存在计算复杂度高、最坏情况解保证能力弱等问题。并开发了启发式算法。但是，它们每一个都需要应用领域的知识来设计，并且只适用于特定的场景。基于最近报道的相同NP-hard组合问题的实例可能保持相同或相似的组合结构，但主要是数据不同的观察，我们研究了将机器学习技术应用于求解STP的可行性和益处。为此，我们设计了一种基于新型图形神经网络和深度强化学习的Vulcan模型。Vulcan的核心是一种新颖、紧凑的图形嵌入，它将高维图形结构数据(即路径改变的信息)转换为低维矢量表示。给定一个STP实例，Vulcan使用这种嵌入对其路径相关信息进行编码，并将编码后的图形发送到基于双深度Q网络(DDQN)的深度强化学习组件以找到解决方案。除了STP之外，Vulcan还可以通过将其简化为STP来找到广泛的NP难题(例如SAT、MVC和X3C)的解决方案。我们实现了一个Vulcan的原型，并通过使用真实世界和合成数据集的大量实验证明了它的有效性和高效性。
链接：https://arxiv.org/abs/2111.10810

2、【SIGIR 2021】Should Graph Convolution Trust Neighbors? A Simple Causal Inference Method
作者：Fuli Feng, Weiran Huang, Xiangnan He, Xin Xin, Qifan Wang, Tat-Seng Chua The Chinese University of Hong Kong
链接：https://arxiv.org/abs/2010.11797v2
文章导读：使用因果图分析了GCN的工作机制，估计了节点局部结构对预测的因果效应。通过阻塞图结构来干预预测，然后，将原始预测与干预预测进行比较，以评估局部结构对预测的因果影响。

3、Do Transformers Really Perform Bad for Graph Representation?
作者：C Ying，T Cai，S Luo，S Zheng，TY Liu, Dalian University of Technology
文章导读：本文通过提出 Graphormer 模型对此问题给予肯定回答。Graphormer 模型建立在标准的 Transformer 模型之上，并且在广泛的图表示学习任务上取得了非常优异的结果，如其在 KDD Cup 2021 – 大规模图学习挑战赛中夺冠，并在多个流行的图学习公开排行榜上位列第一。Graphormer 模型兼具强大的表达能力和高效地捕捉图结构信息的能力，可以证明主流的 GNN 及其变种均为Graphormer 模型的特例。Graphormer 模型的提出证明了 Transformer 文章导读：模型将有潜力成为图学习任务上即 GNN 后又一主要模型结构。
论文链接：https://arxiv.org/abs/2106.05234