图机器学习
图学习的主要任务
图学习中包含三种主要的任务：
链接预测（Link prediction）
节点标记预测（Node labeling）
图嵌入（Graph Embedding）
链接预测（Link prediction）
在链接预测中，给定图G，我们的目标是预测新边。例如，当图未被完全观察时，或者当新客户加入平台（例如，新的LinkedIn用户）时，预测未来关系或缺失边是很有用的。
知乎回答：如何理解链接预测（link prediction）
新LinkedIn用户的链接预测只是给出它可能认识的人的建议。
在链路预测中，我们只是尝试在节点对之间建立相似性度量，并链接最相似的节点。现在的问题是识别和计算正确的相似性分数！
相似度分数
我们可以根据它们的邻居为这两个节点建立几个相似度分数。
公共邻居：S ( i , j ) = ∣ N ( i ) ∩ N ( j ) ∣ ，即公共邻居的数量。在此示例中，分数将为2，因为它们仅共享2个公共邻居。
Jaccard系数：S ( i , j ) = ∣ N ( i ) ∩ N ( j ) ∣ ∣ N ( i ) ∪ N ( j ) ∣
,标准化的共同邻居版本。
Adamic-Adar指数：S ( i , j ) = ∑ k ∈ N ( i ) ∩ N ( j ) 1 log ∣ N ( k ) ∣
。 对于节点i和j的每个公共邻居（common neighbor），我们将1除以该节点的邻居总数。这个概念是，当预测两个节点之间的连接时，与少量节点之间共享的元素相比，具有非常大的邻域的公共元素不太重要。
优先依附(Preferential attachment)： S ( i , j ) = ∣ N ( i ) ∣ ∗ ∣ N ( j ) ∣
性能指标(Performance metrics)
我们如何进行链接预测的评估？我们必须隐藏节点对的子集，并根据上面定义的规则预测它们的链接。这相当于监督学习中的train/test的划分。
然后，我们评估密集图的正确预测的比例，或者使用稀疏图的标准曲线下的面积(AUC)。
节点标记预测（Node labeling）
给定一个未标记某些节点的图，我们希望对这些节点的标签进行预测。这在某种意义上是一种半监督的学习问题。
处理这些问题的一种常见方法是假设图上有一定的平滑度。平滑度假设指出通过数据上的高密度区域的路径连接的点可能具有相似的标签。这是标签传播算法背后的主要假设。
标签传播算法（Label Propagation Algorithm,LPA）是一种快速算法，仅使用网络结构作为指导来发现图中的社区，而无需任何预定义的目标函数或关于社区的先验信息。
单个标签在密集连接的节点组中迅速占据主导地位，但是在穿过稀疏连接区域时会遇到问题。
半监督标签传播算法是如何工作？
首先，我们有一些数据：x 1 , . . . , x l , x l + 1 , . . . , x n ∈ R p ,，以及前l ll个点的标签：y 1 , . . . , y l ∈ 1... C我们定义初始标签矩阵Y ∈ R n × C ，如果x i 具有标签y i = j 则Y i j = 1，否则为0。
该算法将生成预测矩阵F ∈ R n × C，我们将在下面详述。然后，我们通过查找最可能的标签来预测节点的标签：
Y i ^ = a r g m a x j F i , j
预测矩阵F 是什么？
预测矩阵是矩阵F ⋆，其最小化平滑度和准确度。因此，我们的结果在平滑性和准确性之间进行权衡。
问题的描述非常复杂，所以不会详细介绍。但是，解决方案是：
F ⋆ = ( ( 1 − α ) I + L s y m ) − 1 Y
其中：
参数α = 1 \ 1 + μ
Y是给定的标签
L s y m是图的归一化拉普拉斯矩阵（Laplacian matrix）
图神经网络
什么是图神经网络
在过去的几年中，神经网络的兴起与应用成功推动了模式识别和数据挖掘的研究。许多曾经严重依赖于手工提取特征的机器学习任务（如目标检测、机器翻译和语音识别），如今都已被各种端到端的深度学习范式（例如卷积神经网络（CNN）、长短期记忆（LSTM）和自动编码器）彻底改变了。
尽管传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。例如，在电子商务中，一个基于图（Graph）的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐，但图的复杂性使得现有的深度学习算法在处理时面临着巨大的挑战。这是因为图是不规则的，每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积）在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。
近年来，人们对深度学习方法在图上的扩展越来越感兴趣。在多方因素的成功推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——“图神经网络（Graph Neural Networks，GNN）”应运而生
需要注意的是，图神经网络的研究与图嵌入（对图嵌入不了解的读者可以参考这篇文章《图嵌入综述》）或网络嵌入密切相关，图嵌入或网络嵌入是数据挖掘和机器学习界日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息，将图中顶点表示为低维向量，以便使用简单的机器学习算法（例如，支持向量机分类）进行处理。许多图嵌入算法通常是无监督的算法，它们可以大致可以划分为三个类别，即矩阵分解、随机游走和深度学习方法。同时图嵌入的深度学习方法也属于图神经网络，包括基于图自动编码器的算法（如DNGR和SDNE）和无监督训练的图卷积神经网络（如GraphSage）。
图神经网络划分为五大类别，分别是：图卷积网络（Graph Convolution Networks，GCN）、 图注意力网络（Graph Attention Networks）、图自编码器（ Graph Autoencoders）、图生成网络（ Graph Generative Networks） 和图时空网络（Graph Spatial-temporal Networks）。
图卷积网络（Graph Convolution Networks，GCNs）
图卷积网络将卷积运算从传统数据（例如图像）推广到图数据。其核心思想是学习一个函数映射f ( . ) ，通过该映射图中的节点v i可以聚合它自己的特征x i 与它的邻居特征x j
(j ∈ N ( v i )）来生成节点 v i 的新表示。图卷积网络是许多复杂图神经网络模型的基础，包括基于自动编码器的模型、生成模型和时空网络等。下图直观地展示了图神经网络学习节点表示的步骤。
GCN方法又可以分为两大类，基于谱（spectral-based）和基于空间（spatial-based）。基于谱的方法从图信号处理的角度引入滤波器来定义图卷积，其中图卷积操作被解释为从图信号中去除噪声。基于空间的方法将图卷积表示为从邻域聚合特征信息，当图卷积网络的算法在节点层次运行时，图池化模块可以与图卷积层交错，将图粗化为高级子结构。如下图所示，这种架构设计可用于提取图的各级表示和执行图分类任务。
基于谱的GCNs方法
在基于谱的图神经网络中，图被假定为无向图，无向图的一种鲁棒数学表示是正则化图拉普拉斯矩阵，即
其中，A为图的邻接矩阵，D为对角矩阵且
正则化图拉普拉斯矩阵具有实对称半正定的性质。利用这个性质，正则化拉普拉斯矩阵可以分解为
其中,
U是由L的特征向量构成的矩阵， Λ是对角矩阵，对角线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基。
在图信号处理过程中，一个图的信号
x ∈ R N
是一个由图的各个节点组成的特征向量， x i
代表第i个节点。
对图X的傅里叶变换由此被定义为
F ( x ) = U T x
傅里叶反变换则为
F ( x ^ ) = U x ^
其中 x ^ 为傅里叶变换后的结果。
为了更好地理解图的傅里叶变换，从它的定义我们可以看出，它确实将输入的图信号投影到正交空间，而这个正交空间的基（base）则是由正则化图拉普拉斯的特征向量构成。
转换后得到的信号 x ^的元素是新空间中图信号的坐标，因此原来的输入信号可以表示为
这正是傅里叶反变换的结果。
现在我们可以来定义对输入信号X的图卷积操作了
其中， g ∈ R N 是我们定义的滤波器； ⊙ 表示Hadamard product。
假如我们定义这样一个滤波器
那么我们的图卷积操作可以简化表示为
基于谱的图卷积网络都遵循这样的模式，它们之间关键的不同点在于选择的滤波器不同。
现有的基于谱的图卷积网络模型有以下这些：Spectral CNN、Chebyshev Spectral CNN (ChebNet)、Adaptive Graph Convolution Network (AGCN)
基于谱的图卷积神经网络方法的一个常见缺点是，它们需要将整个图加载到内存中以执行图卷积，这在处理大型图时是不高效的。
基于空间的GCNs方法
基于空间的图卷积神经网络的思想主要源自于传统卷积神经网络对图像的卷积运算，不同的是基于空间的图卷积神经网络是基于节点的空间关系来定义图卷积的。
为了将图像与图关联起来，可以将图像视为图的特殊形式，每个像素代表一个节点，如下图a所示，每个像素直接连接到其附近的像素。通过一个3×3的窗口，每个节点的邻域是其周围的8个像素。这八个像素的位置表示一个节点的邻居的顺序。然后，通过对每个通道上的中心节点及其相邻节点的像素值进行加权平均，对该3×3窗口应用一个滤波器。由于相邻节点的特定顺序，可以在不同的位置共享可训练权重。同样，对于一般的图，基于空间的图卷积将中心节点表示和相邻节点表示进行聚合，以获得该节点的新表示，如图b所示。
一种共同的实践是将多个图卷积层叠加在一起。根据卷积层叠的不同方法，基于空间的GCN可以进一步分为两类：recurrent-based和composition-based的空间GCN。recurrent-based的方法使用相同的图卷积层来更新隐藏表示，composition-based的方法使用不同的图卷积层来更新隐藏表示。下图说明了这种差异。
作为最早的图卷积网络，基于谱的模型在许多与图相关的分析任务中取得了令人印象深刻的结果。这些模型在图信号处理方面有一定的理论基础。通过设计新的图信号滤波器，我们可以从理论上设计新的图卷积网络。然而，基于谱的模型有着一些难以克服的缺点，下面我们将从效率、通用性和灵活性三个方面来阐述。
在效率方面，基于谱的模型的计算成本随着图的大小而急剧增加，因为它们要么需要执行特征向量计算，要么同时处理整个图，这使得它们很难适用于大型图。基于空间的模型有潜力处理大型图，因为它们通过聚集相邻节点直接在图域中执行卷积。计算可以在一批节点中执行，而不是在整个图中执行。当相邻节点数量增加时，可以引入采样技术来提高效率。
在一般性方面，基于谱的模型假定一个固定的图，使得它们很难在图中添加新的节点。另一方面，基于空间的模型在每个节点本地执行图卷积，可以轻松地在不同的位置和结构之间共享权重。
在灵活性方面，基于谱的模型仅限于在无向图上工作，有向图上的拉普拉斯矩阵没有明确的定义，因此将基于谱的模型应用于有向图的唯一方法是将有向图转换为无向图。基于空间的模型更灵活地处理多源输入，这些输入可以合并到聚合函数中。因此，近年来空间模型越来越受到关注。
图注意力网络（Graph Attention Networks）
注意力机制如今已经被广泛地应用到了基于序列的任务中，它的优点是能够放大数据中最重要的部分的影响。这个特性已经被证明对许多任务有用，例如机器翻译和自然语言理解。如今融入注意力机制的模型数量正在持续增加，图神经网络也受益于此，它在聚合过程中使用注意力，整合多个模型的输出，并生成面向重要目标的随机行走。
图自动编码器（Graph Autoencoders）
图自动编码器是一类图嵌入方法，其目的是利用神经网络结构将图的顶点表示为低维向量。典型的解决方案是利用多层感知机作为编码器来获取节点嵌入，其中解码器重建节点的邻域统计信息，如positive pointwise mutual information （PPMI）或一阶和二阶近似值。最近，研究人员已经探索了将GCN作为编码器的用途，将GCN与GAN结合起来，或将LSTM与GAN结合起来设计图自动编码器。
图生成网络（Graph Generative Networks）
图生成网络的目标是在给定一组观察到的图的情况下生成新的图。图生成网络的许多方法都是特定于领域的。例如，在分子图生成中，一些工作模拟了称为SMILES的分子图的字符串表示。在自然语言处理中，生成语义图或知识图通常以给定的句子为条件。最近，人们提出了几种通用的方法。一些工作将生成过程作为节点和边的交替形成因素，而另一些则采用生成对抗训练。这类方法要么使用GCN作为构建基块，要么使用不同的架构。
图时空网络Graph Spatial-Temporal Networks
图时空网络同时捕捉时空图的时空相关性。时空图具有全局图结构，每个节点的输入随时间变化。例如，在交通网络中，每个传感器作为一个节点连续记录某条道路的交通速度，其中交通网络的边由传感器对之间的距离决定。图形时空网络的目标可以是预测未来的节点值或标签，或者预测时空图标签。最近的研究仅仅探讨了GCNs的使用，GCNs与RNN或CNN的结合，以及根据图结构定制的循环体系结构。
