摘要
图表征学习的目的是将图中的节点嵌入低维的表征并有效地保留图的结构信息。
导读
许多复杂的系统具有图的形式，如社交网络、生物网络和信息网络。为了有效地处理图数据，第一个关键的挑战是找到有效的图数据表征方法，也就是如何简洁地表征图，以便在时间和空间上有效地进行高级的分析任务，如模式识别、分析和预测。
对于大型图来说，比如那些有数十亿个节点的图，传统的图表征在图的处理和分析上面临一些挑战：
- 高计算复杂性：比如算两点之间的最短距离，一共数十亿个节点。
- 低可并行性：图中节点之间的耦合是由边集显式反应的，将不同的节点分布在不同的分片或服务器上，往往会导致服务器之间的通信成本过高并降低加速率。
- 机器学习方法的不适用性：大多数机器学习算法可能并不适用，因为这些方法通常假设数据样本可以用向量空间中的独立向量来表示，数据中的样本（即节点）在某种程度上因为边而相互依赖，尽管可以用邻接矩阵的行向量来表示一个节点，但是节点多的时候维度就很高，会增加后续图处理和分析的难度。
新的图表征学习，比如针对节点学习密集和连续的低维向量特征，可以减少噪声或冗余信息，并保留内在的结构信息。节点之间的边信息等可由向量空间中节点之间的距离捕获，节点的结构特征就被编码到了该节点的表征向量中。
图表征学习有两个目标。首先，原始图结构可以从学习到的表征向量中重建，具体原理是，如果两个节点间有一条边或关系，那么这两个节点在表征空间中的距离应该相对较小。其次，学习到的表征空间可以有效地支持图推理，如预测未见的链接、识别重要的节点以及推断节点标签等。图重建为目标的图表征对图推理来说是不够的，得到表征后还需要根据这些表征来处理下游任务，比如节点分类、节点聚类、图的可视化和链接预测。
传统图嵌入方法
传统图嵌入方法最初是作为降维技术进行研究的。传统图嵌入方法的目标函数主要针对图的重建。传统图嵌入方法可以看做现代图嵌入方法的特例，而现代图嵌入的最新研究进展则更加关注网络推理。
现代图嵌入方法
为了更好地支持图推理，现代图嵌入学习考虑了图中更丰富的信息。根据图表征学习中所保留信息的类型，现代图嵌入方法可以分为三类：保留图结构和属性的图表征学习、带有侧面信息的图表征学习、保留高级信息的图表征学习。常用的模型包括矩阵分解、随机行走、深度神经网络及其变体等。
保留图结构和属性的图表征学习
图的结构和属性是在很大程度上影响图推理的两个关键因素。图表征学习的一个基本要求就是适当地保留图的结构并捕捉图的属性。图结构包括一阶结构和高阶结构（如二阶结构和群落结构）。不同类型的图有不同的属性，比如有向图具有非对称传递性。
保留图结构的图表征学习
图的结构可以分为不同的类别，而且不同类别拥有不同粒度的图表征。
DeepWalk采用了随机行走来捕捉领域结构，然后对于随机行走产生的每个行走序列，按照Skip-Gram模型，最大化行走序列中邻居节点出现的概率。node2vec定义了一个灵活的节点图邻域概念，并设计了一种二阶随机行走策略来对邻域节点进行抽样，从而在广度优先抽样（BFS）和深度优先抽样（DFS）之间平稳插值。
保留图属性的图表征学习
现有的保留属性的图表征学习方法大多数侧重于保留所有类型图的传递性以及有符号图的结构平稳性。
图常常存在传递性，保留这样的属性并不难，这是因为在度量空间中，不同数据之间的距离天然满足三角形不等式。
但有时现实世界中很多关系并不具有传递性，比如A和B是好友，B和C是好友，不代表A和C是好友。但也有解决方法，首先学习多个节点的嵌入表征，然后根据多个相似性而不是一个相似性来比较节点接近度，如果两个节点有很大的语义相似性，那么它们至少有一种嵌入表征的相似性很大，否则所有表征的相似性都很小。
在网络嵌入空间中保持图属性中，关键的挑战是如何解决原始网络空间和嵌入矢量空间在属性层面的差异和不均匀性。大多数结构和属性保护方法都考虑了节点的高阶接近度，这表明了在图嵌入中优先服务高阶接近度结构的重要性，区别在于获得高阶接近度结构的策略。
带有侧面信息的图表征学习
除图结构外，侧面信息是图表征学习的另一个重要信息源。侧面信息可以分为节点内容以及节点和边的类型，它们的区别在于整合网络结构和侧面信息的方式。
带有节点内容的图表征学习
节点有丰富的信息，比如节点标签、属性甚至语义描述。在图表征学习中把它们与网络拓扑结构结合起来，引起了人们的研究兴趣。半监督的图嵌入算法MMDW，基于DeepWalk衍生的矩阵分解，采用支持向量机（SVM）并结合标签信息来找到最佳分类边界。TADW在学习节点的低维表征时会考虑与节点相关的丰富信息（比如文本）。不同的方法都认为节点内容提供了额外的接近度信息来约束节点的表征。
异质图表征学习
异质图由不同类型的节点和边组成。Jacob提出了一种用于分类节点的异质社交图表征学习算法，该算法将在一个共同的向量空间中学习所有类型节点的表征，并在这个空间中进行推理。Chang提出一种针对异质图（节点可以是图像、文本等类型）的深度图表征学习算法，图像和文本的非线性嵌入算法可以分别由CNN模型和全连接层学习到。
总结
侧面信息引入了附加的接近度度量，这样可以更全面地学习节点之间的关系。
保留高级信息的图表征学习
与侧面信息不同，高级信息是指特定任务中的监督或伪监督信息。保留高级信息的网络嵌入通常包括两部分：一部分是保留网络结构，以便学习节点表征；另一部分是建立节点表征和目标任务之间的联系。
图神经网络
利用深度学习方法来分析图数据仍非常具有挑战性，具体表现在：
- 图的不规则结构，一些基本的数学运算很难推广到图上
- 图的异质性和多样性，解决具体问题时需要利用不同的模型结构
- 大规模图，节点数太多，必须设计可扩展的模型
- 纳入跨学科知识
Graph RNN通过在节点级或图级进行状态建模来捕捉图的循环和顺序模式。GCN则在不规则的图结构上定义卷积和读取操作，以捕捉常见的局部和全局结构模式。GAE假设低秩图结构并采用无监督的方法进行节点表征学习。图强化学习定义了基于图的动作和奖励，以便在遵循约束条件的同时获得图任务的反馈。图对抗方法采用对抗训练技术来提高图模型的泛化能力，并通过对抗攻击来测试其鲁棒性。