图神经网络论文

白行健（右）此前获COO金牌第一名

高中生开始研究图神经网络

白行健的论文为《基于自适应性图卷积神经网络的暴力用户检测》，目前已经成功入围总决赛。

文章提出了⼀种新的⾃适应图卷积神经⽹络模型（Adaptive Graph Convolutional Neural Networks，简称AdaGCN），在传统的GCN模型的基础上进⾏了改进和创新。为了解决参数增加带来的模型难以训练和过拟合情况，文章引入了标签平滑假设，对边权的训练施加了额外的监督，从⽽实现了和GCN模型的⾃然结合。

白行健的数据集包含了10万余名Twitter⽤户和200余万条社交关系，其中⼤约5千名⽤户被标记是否为暴⼒⽤户。实验结果表明，AdaGCN的AUC得分为，F1得分为，得分⾼于所有对⽐⽅法，包括传统的GCN模型， 图注意⼒⽹络 (GAT)，标签传播算法（LPA），⽀持向量机（SVM）等等。此外， AdaGCN模型的结果具有最低的标准差，这表明AdaGCN模型具有很强的稳定性。 在线社交平台可以利⽤本⽂提出的⽅法来更好地评估、检测暴⼒⽤户，防⽌暴⼒⽤户伤害他⼈ 并传播仇恨⾔论。 同时，⾃适应图卷积神经⽹络模型也可以⽤来评估不同类型的暴⼒⾔论造成的社会影响。

开挂的学霸少年

此次入围丘成桐奖之前，白行健从2018年开始多次参加相关竞赛获得好成绩：

白行健（右）

在生活方面，白行健也有很多其他尝试，他目前就读北京师范⼤学附属实验中学国际部⾼三，对数学和计算机科学非常感兴趣，担任学校计算机社社长和⼈⽂社社长。

图 | 微博

而今年的丘成桐中学科学奖中，白行健选择用图神经网络为切入点，对网络暴力用户进行检测。很大一部分原因也是身边有好友经历过网络暴力：

“2018年2⽉10⽇，⼀个名叫Ted Senior的22岁男孩在林地上吊⾃杀，原因是⼀些⼈在社交媒体上恶意地分享和评判他与⼀名⼥孩的聊天内容。在我身 边，我的同学好友在学校论坛发表观点，但是遭受匿名的辱骂和攻击，这种羞辱让他感到⾮常痛苦。我深深地被这些可恨的⾏为和可怕的后果所触动。计算机科学带来了信息时代，社交⽹络改变了我们的⽣活，我们期望技术会让世界更美好。但没有什么是尽善尽美的。⽹络暴⼒是信息技术⽆意中带来的⼀个问题，我渴望找到⼀种⽅法来发现和控制它们。”

而目前对于网络暴力， 目前已经有不少基于深度学习的网络欺凌模型。比如Instagram去年推出 「增强版的评论过滤器」 ，通过对照片、文字的检测分析，对其中的恶意行为采取过滤等措施。、

Facebook和Twitter也推出了类似的举措来限制其平台上的欺凌行为。Twitter在去年十月制定了一个时间表，以便从其平台中删除裸露和仇恨图像等内容。去年Facebook添加了一些工具，允许用户一次隐藏或删除多条评论，并允许用户代表朋友或家人报告欺凌或骚扰。

科技的发展真实的改变着我们的生活，我们享受其便利、承受其弊端。而像白行健这样的年轻人将越来越早的进入改变世界的行列，用技术影响着我们。

看来未来不仅仅是「同辈压力」了，「后辈压力」也追着我们跑来了。毕竟当你还在拼命打排位的时候，高中生已经论文已经发起来了......

在这篇文章中，我们将仔细研究一个名为GCN的著名图神经网络。首先，我们先直观的了解一下它的工作原理，然后再深入了解它背后的数学原理。

字幕组双语原文： 【GCN】图卷积网络(GCN)入门详解 英语原文： Graph Convolutional Networks (GCN) 翻译： 听风1996 、 大表哥

许多问题的本质上都是图。在我们的世界里，我们看到很多数据都是图，比如分子、社交网络、论文引用网络。

图的例子。(图片来自[1])

在图中，我们有节点特征（代表节点的数据）和图的结构（表示节点如何连接）。

对于节点来说，我们可以很容易地得到每个节点的数据。但是当涉及到图的结构时，要从中提取有用的信息就不是一件容易的事情了。例如，如果2个节点彼此距离很近，我们是否应该将它们与其他对节点区别对待呢？高低度节点又该如何处理呢？其实，对于每一项具体的工作，仅仅是特征工程，即把图结构转换为我们的特征，就会消耗大量的时间和精力。

图上的特征工程。(图片来自[1])

如果能以某种方式同时得到图的节点特征和结构信息作为输入，让机器自己去判断哪些信息是有用的，那就更好了。

这也是为什么我们需要图表示学习的原因。

我们希望图能够自己学习 "特征工程"。(图片来自[1])

论文 ：基于图神经网络的半监督分类 （2017）[3]

GCN是一种卷积神经网络，它可以直接在图上工作，并利用图的结构信息。

它解决的是对图（如引文网络）中的节点（如文档）进行分类的问题，其中仅有一小部分节点有标签（半监督学习）。

在Graphs上进行半监督学习的例子。有些节点没有标签（未知节点）。

就像"卷积"这个名字所指代的那样，这个想法来自于图像，之后引进到图（Graphs）中。然而，当图像有固定的结构时，图（Graphs）就复杂得多。

从图像到图形的卷积思想。 (图片来自[1])

GCN的基本思路：对于每个节点，我们从它的所有邻居节点处获取其特征信息，当然也包括它自身的特征。假设我们使用average()函数。我们将对所有的节点进行同样的操作。最后，我们将这些计算得到的平均值输入到神经网络中。

在下图中，我们有一个引文网络的简单实例。其中每个节点代表一篇研究论文，同时边代表的是引文。我们在这里有一个预处理步骤。在这里我们不使用原始论文作为特征，而是将论文转换成向量（通过使用NLP嵌入，例如tf-idf）。NLP嵌入，例如TF-IDF)。

让我们考虑下绿色节点。首先，我们得到它的所有邻居的特征值，包括自身节点，接着取平均值。最后通过神经网络返回一个结果向量并将此作为最终结果。

GCN的主要思想。我们以绿色节点为例。首先，我们取其所有邻居节点的平均值，包括自身节点。然后，将平均值通过神经网络。请注意，在GCN中，我们仅仅使用一个全连接层。在这个例子中，我们得到2维向量作为输出（全连接层的2个节点）。

在实际操作中，我们可以使用比average函数更复杂的聚合函数。我们还可以将更多的层叠加在一起，以获得更深的GCN。其中每一层的输出会被视为下一层的输入。

2层GCN的例子：第一层的输出是第二层的输入。同样，注意GCN中的神经网络仅仅是一个全连接层（图片来自[2]）。

让我们认真从数学角度看看它到底是如何起作用的。

首先，我们需要一些注解

我们考虑图G，如下图所示。

从图G中，我们有一个邻接矩阵A和一个度矩阵D。同时我们也有特征矩阵X。

那么我们怎样才能从邻居节点处得到每一个节点的特征值呢？解决方法就在于A和X的相乘。

看看邻接矩阵的第一行，我们看到节点A与节点E之间有连接，得到的矩阵第一行就是与A相连接的E节点的特征向量（如下图）。同理，得到的矩阵的第二行是D和E的特征向量之和，通过这个方法，我们可以得到所有邻居节点的向量之和。

计算 "和向量矩阵 "AX的第一行。

在问题（1）中，我们可以通过在A中增加一个单位矩阵I来解决，得到一个新的邻接矩阵Ã。

取lambda=1（使得节点本身的特征和邻居一样重要），我们就有Ã=A+I，注意，我们可以把lambda当做一个可训练的参数，但现在只要把lambda赋值为1就可以了，即使在论文中，lambda也只是简单的赋值为1。

通过给每个节点增加一个自循环，我们得到新的邻接矩阵

对于问题(2): 对于矩阵缩放，我们通常将矩阵乘以对角线矩阵。在当前的情况下，我们要取聚合特征的平均值，或者从数学角度上说，要根据节点度数对聚合向量矩阵ÃX进行缩放。直觉告诉我们这里用来缩放的对角矩阵是和度矩阵D̃有关的东西（为什么是D̃，而不是D？因为我们考虑的是新邻接矩阵Ã 的度矩阵D̃，而不再是A了）。

现在的问题变成了我们要如何对和向量进行缩放/归一化？换句话说：

我们如何将邻居的信息传递给特定节点？我们从我们的老朋友average开始。在这种情况下，D̃的逆矩阵（即，D̃^{-1}）就会用起作用。基本上，D̃的逆矩阵中的每个元素都是对角矩阵D中相应项的倒数。

例如，节点A的度数为2，所以我们将节点A的聚合向量乘以1/2，而节点E的度数为5，我们应该将E的聚合向量乘以1/5，以此类推。

因此，通过D̃取反和X的乘法，我们可以取所有邻居节点的特征向量（包括自身节点）的平均值。

到目前为止一切都很好。但是你可能会问加权平均()怎么样？直觉上，如果我们对高低度的节点区别对待，应该会更好。

但我们只是按行缩放，但忽略了对应的列（虚线框）。

为列增加一个新的缩放器。

新的缩放方法给我们提供了 "加权 "的平均值。我们在这里做的是给低度的节点加更多的权重，以减少高度节点的影响。这个加权平均的想法是，我们假设低度节点会对邻居节点产生更大的影响，而高度节点则会产生较低的影响，因为它们的影响力分散在太多的邻居节点上。

在节点B处聚合邻接节点特征时，我们为节点B本身分配最大的权重（度数为3），为节点E分配最小的权重（度数为5）。

因为我们归一化了两次，所以将"-1 "改为"-1/2"

例如，我们有一个多分类问题，有10个类，F 被设置为10。在第2层有了10个维度的向量后，我们将这些向量通过一个softmax函数进行预测。

Loss函数的计算方法很简单，就是通过对所有有标签的例子的交叉熵误差来计算，其中Y_{l}是有标签的节点的集合。

层数是指节点特征能够传输的最远距离。例如，在1层的GCN中，每个节点只能从其邻居那里获得信息。每个节点收集信息的过程是独立进行的，对所有节点来说都是在同一时间进行的。

当在第一层的基础上再叠加一层时，我们重复收集信息的过程，但这一次，邻居节点已经有了自己的邻居的信息（来自上一步）。这使得层数成为每个节点可以走的最大跳步。所以，这取决于我们认为一个节点应该从网络中获取多远的信息，我们可以为#layers设置一个合适的数字。但同样，在图中，通常我们不希望走得太远。设置为6-7跳，我们就几乎可以得到整个图，但是这就使得聚合的意义不大。

例： 收集目标节点 i 的两层信息的过程

在论文中，作者还分别对浅层和深层的GCN进行了一些实验。在下图中，我们可以看到，使用2层或3层的模型可以得到最好的结果。此外，对于深层的GCN（超过7层），反而往往得到不好的性能（虚线蓝色）。一种解决方案是借助隐藏层之间的残余连接（紫色线）。

不同层数#的性能。图片来自论文[3]

论文作者的说明

该框架目前仅限于无向图（加权或不加权）。但是，可以通过将原始有向图表示为一个无向的两端图，并增加代表原始图中边的节点，来处理有向边和边特征。

对于GCN，我们似乎可以同时利用节点特征和图的结构。然而，如果图中的边有不同的类型呢？我们是否应该对每种关系进行不同的处理？在这种情况下如何聚合邻居节点？最近有哪些先进的方法？

在图专题的下一篇文章中，我们将研究一些更复杂的方法。

如何处理边的不同关系（兄弟、朋友、......）？

[1] Excellent slides on Graph Representation Learning by Jure Leskovec (Stanford):

[2] Video Graph Convolutional Networks (GCNs) made simple:

[3] Paper Semi-supervised Classification with Graph Convolutional Networks (2017):

[4] GCN source code:

[5] Demo with StellarGraph library:

雷锋字幕组是一个由AI爱好者组成的翻译团队，汇聚五五多位志愿者的力量，分享最新的海外AI资讯，交流关于人工智能技术领域的行业转变与技术创新的见解。

团队成员有大数据专家，算法工程师，图像处理工程师，产品经理，产品运营，IT咨询人，在校师生；志愿者们来自IBM，AVL，Adobe，阿里，百度等知名企业，北大，清华，港大，中科院，南卡罗莱纳大学，早稻田大学等海内外高校研究所。

如果，你也是位热爱分享的AI爱好者。欢迎与雷锋字幕组一起，学习新知，分享成长。

大数据的核心是数据智能。数据智能的本质是在大量样本中发现、评估若干概念之间的关联性，归纳形成数学表达，再利用数学表达进行推理运算，从而完成对未知样本的判断决策。这就需要发现海量数据背后的规律，解决数据表征问题。数据智能先后经历了专家系统、传统机器学习和神经网络三个阶段，输入的知识从具体到抽象，从规则到特征再到模式，越来越宏观，智能化处理效率越来越高，对底层的感知和模型的可解释性越来越弱化。随着专家系统逐渐淡出，传统机器学习和神经网络成为数据智能的两大常见技术。实践证明，随着数据集样本的增多，传统机器学习的性能不及神经网络（见图一）。这主要归结于前者的表达能力不如后者。Goodfellow在2013年ICML（国际机器学习大会）上发表了论文《MaxoutNetworks》（最大输出网络）。在这篇论文中证明了MaxoutNetworks能够无限逼近任意连续函数。也即是说，神经网络能够拟合任意连续函数，与传统机器学习相比，神经网络具有突出的表达能力优势。         （上图）：横轴代表数据量，纵轴代表算法精度             我们看到几个趋势：行业数据量指数级增长、以GPU为代表的专业芯片算力增长、新型算法层出不穷、学术界的前沿研究、投资界的资金投入、工商业的多种场景，这些因素都促进了神经网络快速发展。神经网络的发展形态有两种方向：一是以DNN深度全连接和CNN卷积神经网络为代表的纵向发展，即层数增多的纵向迭代，典型应用是CV计算机视觉；二是以RNN循环神经网络为代表的横向发展，即神经元之间的横向迭代，典型应用是以NLP自然语言理解为代表的序列处理。神经网络技术同时呈现两种发展形态，并在多个领域有广泛应用，就说明这个技术已经进入成熟期了。下一步往哪个方向发展？很有可能是：将纵向发展和横向发展进行结合，渗透到更多的应用领域。这看似顺水推舟的事情。事实证明，这个判断是正确的，图神经网络就是二者的结合。         纵观技术圈的发展历史，可以总结出这样的事实：一个理论技术能否在更多的领域推广，关键取决于它能否真实地刻画现实世界的实体特征和关系。如果它刻画得越真实，那么它的应用场景就越多。比如马尔科夫链这个理论，就真实地刻画了现实世界中的时序对象的特征和依赖关系，因此它广泛应用在语音理解、机器翻译、国民经济、事件预测等领域；再如概率图理论，用图来表示事件概率的依存关系，也是真实刻画了现实世界中的实体关系，因此它也广泛应用在反欺诈、图像理解、事件预测等领域。从方法论看，要刻画现实世界的实体，就必须在模型中置入代表这个实体的节点，并且设计出实体之间的依赖关系转化。但无论是马尔科夫链还是概率图等方法，都弱化了嵌入表示，从而丢失了一些隐语义信息，是有缺憾的。 图神经网络（GraphNeural Networks，GNN）的问世，使事情出现了转机。在图神经网络中，存在两种网络。一种是拓扑结构网络，通常描述众多实体及其关系；另一种是特征变换神经网络，通常用于节点、边、图或子图的特征转化。前者完成信息横向传播，实现图信号的拓扑关系传递，理论依据是图论；后者完成信息纵向传播，实现原始特征向嵌入表示的转化，理论依据是深度学习。图神经网络是图论与深度学习的完美结合，它既考虑了实体关系，又考虑了实体特征。与传统图方法和传统深度学习相比，图神经网络具有明显的优势：建模来源数据更充分，更能反映现实世界中实体之间的真实关系，它既能从图结构代表的非欧式空间数据中学习到语义表示，又能让学习到的语义表示最大限度地符合图结构的实体关系。         现实世界中80%以上的数据更适合用图结构来刻画，比如交通数据、社交数据、分子结构数据、行业经济数据等。图神经网络能适应这样的数据，在分布式学习架构下，图神经网络能处理的数据规模非常庞大，非常适合处理数亿节点的产业数据。因此图神经网络的应用场景更为广泛。近三年来，各种国际顶会关于图神经网络的论文频频发布，众多互联网科技公司（如阿里、百度、字节跳动）花重金在这一领域布局，并取得重大进展，广泛应用于关联搜索、实时推荐、风险防控、异常检测、行为预测、模式识别等。这些现象无疑说明了图神经网络是未来技术发展的重要领域方向。         综上所述，在行业数据、算法理论、算力支持、市场需求、资本涌入等背景下，图神经网络的迅速崛起是大数据时代发展的必然。