近期必读的12篇KDD 2019【图神经网络（GNN）】相关论文

2019 年 8 月 6 日 专知

【导读】最近，数据挖掘领域国际最高级别会议KDD 2019 于 2019 年 8 月 4 日- 8 日在美国阿拉斯加州安克雷奇市举行。今年的 KDD 包括两个track：Research Track和 Applied Data Science track。据了解，Research Track 共收到约 1200 篇投稿，其中约 110 篇接收为oral 论文，60 篇接收为poster 论文，接收率仅为 14%。专知小编发现关于图神经网络的相关论文在今年的KDD上非常多，所以今天小编专门整理最新12篇图神经网络（GNN）相关论文——聚类-GCN、条件随机场-GCN、Degree-GNN、GCN-MF、GCN-Pooling、GRN、异构GNN、强化学习-GNN、对抗攻击-GCN。

1. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

作者：Wei-Lin Chiang; Xuanqing Liu; Si Si; Yang Li; Samy Bengio; Cho-Jui Hsieh;

摘要：图卷积网络(GCN)已成功地应用于许多基于图的应用中; 然而，训练一个大规模的GCN仍然是具有挑战性的。现有的基于SGD的算法要么计算成本高，且随着GCN层数的增加呈指数级增长，要么需要很大的空间来保存整个图以及在内存中嵌入每个节点。本文利用图的聚类结构，提出了一种新的适合于基于SGD的训练的GCN算法Cluster-GCN。Cluster-GCN的工作原理如下: 在每一步中，它对与图聚类算法标识的密集子图相关联的节点块进行采样，并限制在该子图中进行邻域搜索。这种简单而有效的策略能够显著提高内存和计算效率，同时能够达到与以前算法相当的测试精度。为了测试算法的可扩展性，我们创建了一个新的Amazon2M数据集，包含200万个节点和6100万条边，比之前最大的公共可用数据集(Reddit)大5倍以上。对于在此数据集上训练3层GCN, Cluster-GCN比之前最先进的VR-GCN(1523秒vs. 1961秒)更快，并且使用更少的内存(2.2GB vs. 11.2GB)。此外，对于该数据集的4层GCN的训练，我们的算法可以在36分钟左右完成，而现有的GCN训练算法都因为内存不足而无法训练。此外，Cluster-GCN允许我们在不需要太多时间和内存开销的情况下训练更深层的GCN，从而提高了预测精度——使用5层Cluster-GCN，我们在PPI数据集上实现了最先进的测试结果，F1 score为99.36，而之前最好的结果是98.71。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/cluster-gcn-an-efficient-algorithm-for-training-deep-and-large-graph-convol

2. Conditional Random Field Enhanced Graph Convolutional Neural Networks

作者：Hongchang Gao; Jian Pei; Heng Huang;

摘要：图卷积神经网络近年来受到越来越多的关注。与标准卷积神经网络不同，图卷积神经网络对图数据进行卷积运算。与一般数据相比，图数据具有不同节点间的相似性信息。因此，在图卷积神经网络的隐层中保存这种相似性信息是非常重要的。然而，现有的工作没有做到这一点。另一方面，为了保持相似关系，对隐藏层的增强是一个挑战。为了解决这一问题，我们提出了一种新的CRF层用于图卷积神经网络，以使得相似节点具有相似的隐藏特征。这样，可以显式地保存相似性信息。此外，我们提出的CRF层易于计算和优化。因此，它可以很容易地插入到现有的图卷积神经网络中，提高其性能。最后，大量的实验结果验证了我们提出的CRF层的有效性。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/conditional-random-field-enhanced-graph-convolutional-neural-networks

3. DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification

作者：Jun Wu; Jingrui He; Jiejun Xu;

摘要：图数据广泛存在于许多具有高影响力的应用中。受网格结构数据深度学习成功的启发，研究者提出了一种学习强大的节点级或图级表示的图神经网络模型。然而，现有的图神经网络大多存在以下局限性：(1)对图卷积的seed-oriented、degree-aware、order-free等特性的分析比较有限; (2) 在区分结构感知节点邻域时，没有将节点的degree-specific图结构显式表示为图卷积; (3)图级pooling机制的理论解释尚不明确。为了解决这些问题，我们提出了一种基于Weisfeiler- Lehman图同构测试的通用degree-specific图神经网络DEMO-Net。为了显式地捕获与节点属性集成的图的拓扑结构，我们认为图卷积应该具有三个属性：seed-oriented, degree-aware 和order-free。为此，我们提出了多任务图卷积，其中每个任务表示具有specific degree value的节点的节点表示学习，从而保持了degree-specific的图结构。特别地，我们设计了两种多任务学习方法：degree-specific权重法和图卷积的哈希函数法。此外，我们还提出了一种新的图级pooling/readout方案，用于学习图形表示，可证明位于degree-specific的Hilbert kernel空间中。在多个节点和图分类基准数据集上的实验结果表明，我们提出的DEMO-Net相对于最先进的图神经网络模型的有效性和高效性。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/demo-net-degree-specific-graph-neural-networks-for-node-and-graph-classific

4. GCN-MF: Disease-Gene Association Identification By Graph Convolutional Networks and Matrix Factorization

作者：Peng Han; Peng Yang; Peilin Zhao; Shuo Shang; Yong Liu; Jiayu Zhou; Xin Gao; Panos Kalnis;

摘要：发现疾病基因关联是一项基础性和关键性的生物医学任务，它有助于生物学家和医生发现症候的致病机制。基于网络的半监督学习(NSSL)是这些研究中常用的一种方法，它利用各种临床生物标志物来测量基因和疾病表型之间的相似性，来解决这个类平衡的大规模数据问题。然而，大多数现有的NSSL方法都是基于线性模型的，存在两个主要限制:1)它们隐式地考虑每个候选对象的局部结构表示; 2)他们无法捕捉疾病和基因之间的非线性联系。本文将图卷积网络(GCN)和矩阵因子分解相结合，提出了一种新的疾病基因关联任务框架GCN-MF。在GCN的帮助下，我们可以捕获非线性相互作用，并利用测量到的相似性。此外，我们定义了一个边际控制损失函数，以减少稀疏性的影响。实验结果表明，所提出的深度学习算法在大多数指标上都优于其他最先进的方法。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/cluster-gcn-an-efficient-algorithm-for-training-deep-and-large-graph-convol

5. Estimating Node Importance in Knowledge Graphs Using Graph Neural Networks

作者：Namyong Park; Andrey Kan; Xin Luna Dong; Tong Zhao; Christos Faloutsos;

摘要：如何估计知识图谱(KG)中节点的重要性? KG是一个多关系图，它被证明对于许多任务(包括问题回答和语义搜索)都很有价值。在本文中，我们提出了GENI，一种解决KG中节点重要性估计问题的方法，该方法支持商品推荐和资源分配等多种下游应用。虽然已经有了一些方法来解决一般图的这个问题，但是它们没有充分利用KG中可用的信息，或者缺乏建模实体与其重要性之间复杂关系所需的灵活性。为了解决这些限制，我们探索了有监督的机器学习算法。特别是，基于图神经网络（GNN）的最新进展，我们开发了GENI，这是一种基于GNN的方法，旨在应对预测KG中节点重要性所涉及的独特挑战。我们的方法通过predicate-aware注意力机制和灵活的中心性调整来执行重要性分数的聚合，而不是聚合节点嵌入。在我们对GENI和现有方法的评估中，GENI在预测具有不同特征的真实KG中节点重要性方面比现有方法高出5-17%。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/estimating-node-importance-in-knowledge-graphs-using-graph-neural-networks

6. Graph Convolutional Networks with EigenPooling

作者：Yao Ma; Suhang Wang; Charu Aggarwal; Jiliang Tang;

摘要：图神经网络将深度神经网络模型推广到图结构数据中，近年来受到越来越多的关注。它们通常通过转换、传播和聚合节点特征来学习节点表示，并被证明可以提高许多与图相关的任务的性能，如节点分类和链接预测。将图神经网络应用于图分类任务，需要从节点表示生成图表示的方法。一种常见的方法是全局组合节点表示。然而，丰富的结构信息被忽略了。因此，在图表示学习过程中，需要一个层次的pooling过程来保持图的结构。最近有一些关于层次学习图表示的工作类似于传统卷积神经网络（CNN）中的pooling步骤。然而，在汇聚过程中，局部结构信息在很大程度上仍然被忽略。本文介绍了一种基于图的傅里叶变换的pooling操作EigenPooling，它可以利用pooling过程中的节点特征和局部结构。然后基于pooling算子设计pooling层，并与传统的GCN卷积层进一步结合，形成一个用于图分类的图神经网络框架EigenGCN。从局部和全局的角度对EigenGCN进行了理论分析。图分类任务在6个常用benchmark上的实验结果表明了该框架的有效性。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/graph-convolutional-networks-with-eigenpooling

7. Graph Recurrent Networks with Attributed Random Walks

作者：Xiao Huang; Qingquan Song; Yuening Li; Xia Hu;

摘要：随机游走被广泛应用于从网络嵌入到标签传播的各种网络分析任务中。它可以捕获并将几何结构转换为结构化序列，同时解决了稀疏性和维数的灾难性问题。虽然对纯网络上的随机游走进行了深入的研究，但在实际系统中，节点往往不是纯顶点，而是具有不同的特征，并由与之相关的丰富数据集来描述。这些节点属性包含丰富的信息，这些信息通常是网络的补充，并为基于随机游走的分析带来了机会。然而，目前还不清楚如何为attributed网络开发随机游走来实现有效的联合信息提取。节点属性使得节点之间的交互更加复杂，拓扑结构也更加异构。

为了弥补这一不足，我们研究了在attributed网络上进行联合随机游动，并利用它们来提高深度节点表示学习。提出的框架GraphRNA由两个主要组件组成，即，一种协作游走机制—AttriWalk，以及一种为随机游走量身定制的深度嵌入体系结构，称为图递归网络(graph recurrent networks ，GRN)。AttriWalk将节点属性看作是一个二分网络，并利用它来促进节点间的离散化，减少节点间向高中心汇聚的趋势。AttriWalk使我们能够将突出的深度网络嵌入模型-图卷积网络推向一个更有效的架构——GRN。GRN赋予节点表示以与原始attributed网络中的节点交互相同的方式进行交互。在真实数据集上的实验结果表明，与目前最先进的嵌入算法相比，GraphRNA算法很有效。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/graph-recurrent-networks-with-attributed-random-walks

8. HetGNN: Heterogeneous Graph Neural Network

作者：Chuxu Zhang; Dongjin Song; Chao Huang; Ananthram Swami; Nitesh V. Chawla;

摘要：异构图表示学习的目的是为每个节点寻求一个有意义的向量表示，以便于后续应用，如链接预测、个性化推荐、节点分类等。然而，该任务具有挑战性，不仅因为需要合并异构由多种类型的节点和边组成的结构（图）信息，但也需要考虑与每个节点相关联的异构属性或内容（例如，文本或图像）。尽管在同构(或异构)图嵌入、属性图嵌入以及图神经网络等方面都做了大量的工作，但很少有图神经网络能够有效地联合考虑图的异构结构(图)信息以及各节点的异构内容信息。为此，我们提出了一种异构图神经网络模型HetGNN。具体来说，我们首先引入一个具有重启策略的随机游走，为每个节点抽取一个固定大小的强相关异构邻居，并根据节点类型对它们进行分组。接下来，我们设计了一个包含两个模块的神经网络结构来聚合这些采样的相邻节点的特征信息。第一个模块对异构内容的“深度”特性交互进行编码，并为每个节点生成内容嵌入。第二个模块聚合不同邻近组(类型)的内容(属性)嵌入，并通过考虑不同组的影响来进一步组合它们，以获得最终的节点嵌入。最后，我们利用图context loss和一个mini-batch梯度下降过程以端到端方式训练模型。在多个数据集上的大量实验表明，HetGNN在各种图挖掘任务（比如链路预测、推荐、节点分类聚类、归纳节点分类聚类）中都能超越最先进的baseline。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/hetgnn-heterogeneous-graph-neural-network

9. Learning Dynamic Context Graphs for Predicting Social Events

作者：Songgaojun Deng; Huzefa Rangwala; Yue Ning;

摘要：以建模上下文信息为目标的事件预测是自动分析生成和资源分配等应用程序的一项重要任务。为感兴趣的事件捕获上下文信息可以帮助分析人员理解与该事件相关的因素。然而，由于以下几个因素，在事件预测中获取上下文信息是具有挑战性的: (i)上下文结构和形成的不确定性，(ii)高维特征，以及(iii)特征随时间的适应性。最近，图表示学习在交通预测、社会影响预测和可视化问题回答系统等应用中取得了成功。在本文中，我们研究了社会事件建模中的图表示，以识别事件上下文的动态属性作为social indicators。

受图神经网络的启发，我们提出了一种新的图卷积网络来预测未来的事件(例如，国内动乱运动)。我们从历史/以前的事件文档中提取和学习图表示。该模型利用隐藏的单词图特征预测未来事件的发生，并将动态图序列识别为事件上下文。在多个真实数据集上的实验结果表明，该方法与各种先进的社会事件预测方法相比具有较强的竞争力。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/learning-dynamic-context-graphs-for-predicting-social-events

10. Automating Feature Subspace Exploration via Multi-Agent Reinforcement Learning

作者：Kunpeng Liu; Yanjie Fu; Pengfei Wang; Le Wu; Rui Bo; Xiaolin Li;

摘要：特征选择是机器学习的预处理步骤，它试图为后续的预测任务选择最相关的特征。有效的特征选择可以降低维数，提高预测精度，提高结果的可理解性。从子集空间中寻找最优特征子集是一个非常具有挑战性的问题，因为子集空间可能非常大。在已有研究的基础上，增强学习为搜索策略的全局化提供了新的视角。针对特征选择问题，提出了一种多智能体增强学习框架。具体来说，我们首先用一个增强学习框架来重新制定特征选择，将每个特征视为一个智能体。然后，通过三种方法得到环境状态，即为了使算法更好地理解学习过程，本文采用了统计描述、自动编码器和图卷积网络(GCN)。我们展示了如何以一种基于图的方式学习状态表示，这种方法不仅可以处理边的变化，还可以处理节点逐步变化的情况。此外，我们还研究了如何通过更合理的奖励方案来改善不同特征之间的协调。该方法具有全局搜索特征子集的能力，并且由于增强学习的性质，可以很容易地适应实时情况(实时特征选择)。此外，我们还提出了一种有效的加速多智能体强化学习收敛的策略。最后，大量的实验结果表明，该方法比传统方法有显著的改进。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/automating-feature-subspace-exploration-via-multi-agent-reinforcement-learn

11. Robust Graph Convolutional Networks Against Adversarial Attacks

作者：Dingyuan Zhu; Ziwei Zhang; Peng Cui; Wenwu Zhu;

摘要：图卷积网络(GCNs)是一种新兴的基于图的神经网络模型，在节点分类任务中取得了最先进的性能。然而，近年来的研究表明，GCN容易受到恶意攻击，即在图结构和节点属性上的小扰动，这给GCN网络在实际应用中带来了很大的挑战。如何提高GCN的鲁棒性仍然是一个关键的开放性问题。

为了解决这一问题，我们提出了Robust GCN (RGCN)，这是一种新的模型，它“加强”了GCN的对抗攻击能力。具体来说，我们的方法不是将节点表示为向量，而是采用高斯分布作为每个卷积层中节点的隐藏表示。这样，当图受到攻击时，我们的模型可以自动吸收高斯分布方差变化的不利影响。此外，为了弥补对抗性攻击在GCN中的传播，我们提出了一种基于方差的注意力机制，即在执行卷积时根据节点邻域的方差分配不同的权值。大量的实验结果表明，我们提出的方法可以有效地提高GCN的鲁棒性。在三个基准图上，与最先进的GCN方法相比，我们的RGCN在各种对抗攻击策略下的节点分类精度有了显著提高。

网址：

https://www.kdd.org/kdd2019/accepted-papers/view/robust-graph-convolutional-networks-against-adversarial-attacks

12. Stability and Generalization of Graph Convolutional Neural Networks

作者：Saurabh Verma; Zhi-Li Zhang;

摘要：图卷积神经网络(GCNNs)是受卷积神经网络在一维和二维数据上的启发而发展起来的一种用于各种图数据学习任务的神经网络，在实际数据集上表现出了良好的性能。尽管GCNN模型取得了一定的成功，但是对于GCNN模型的泛化性质等理论探索却十分缺乏。本文通过分析单层GCNN模型的稳定性，推导出其在半监督图学习环境下的泛化保证，为深入理解GCNN模型迈出了第一步。特别地，我们证明了GCNN模型的算法稳定性依赖于其图卷积滤波器的最大绝对特征值。此外，为了确保提供强泛化保证所需的均匀稳定性，最大绝对特征值必须与图的大小无关。我们的结果为设计新的和改进的具有算法稳定性的图卷积滤波器提供了新的见解。我们对各种真实世界图数据集的泛华差距和稳定性进行了评价，实证结果确实支持了我们的理论发现。据我们所知，我们是第一个在半监督设置下研究图学习的稳定性边界，并推导出GCNN模型的泛化边界。