文献汇报六

发表于

Classifying and Counting with Recurrent Contexts

简介

  分类和量化（计数）是两个不同但又紧密相关的数据挖掘任务。它们可以相互获益。我们可以通过分类和计数每一个样本来量化样本。相反，我们也可以使用量化结果来调整分类的决策阈值，来改善具有不同类分别的应用中的分类准确度。

  这篇论文中，作者假设：（1）数据可以被（近似）描述为一系列反复出现的概念（context） （2）尽管一些潜在的因素会造成概念漂移，但可观测变量的更小的集合和这些潜在因素是相关的。（3）在训练期间可用的变量，作者并不假设其在之后也可用。作者研究的是：在具有验证延迟的非稳态环境，如何准确地识别数据样本正确的上下文，同时估计正类的比例。

  原文地址

  作者动机。作者的实验室为飞虫设计了一个传感器，其使用红外线捕捉飞虫的翅膀动作和机器学习根据飞虫信号分类它的物种和性别。这个传感器可以增强现有的捕蚊设别，这样的设备对于蚊虫控制和监控是很有价值的工作。分类是控制的首要任务，量化是监控的首要任务。由这些捕蚊设备收集的数据会呈现出漂移。有许多因素会影响昆虫的飞行行为，如温度、适度、气压、食物等。但一个严重的问题是：类分布是未知的并且是高度变化的。它取决于两个首要的因素：感兴趣物种的当地可用性（数量）和昆虫的昼夜节律。

  在实验室作者可以控制各种变量使用虫箱（带有传感器的容器）来收集训练数据，这些数据可以确定所有经常性行为模式（context）的合理部分。每一个虫箱维持某一单一物种的昆虫。但是训练数据提供的是关于类分别$P(Y)$的有限的信息。在实验里，类分别取决于每一个虫箱里昆虫的数量和其昼夜节律；但在野外，类分别取决于昆虫当地分布和其昼夜节律。另外，实验人员可以评估许多会影响昆虫行为的因素，但他们想要移除一些非必要的因素。

提出的方法

  作者提出了两种方法，它们可以识别一个样本所属的上下文，同时估计正样本类比率。作者提出的方法适合处理二分类和量化任务。

  作者假设一个样本在某时间点仅属于一个上下文。尽管其算法接受一个样本作为输入，这可块可以视为是在数据流上的一个滑窗。

  背景知识。HDy 是一种依赖于分类器为正面和负面事件输出的分数之间的统计差异的方法。其建立两个正则直方图，$H_+$和$H_-$，是由分类器分别在只包含正样本和负样本的验证集获得的分数的直方图。当出现未标注的测试数据集时，该算法使用同样的分类器在其上建立$H_?$。然后，使用如下的公式计算正样本比率：

HDY

HD 是 Hellinger Distance，它可以量化两个分布之间的相似性，其中每一个直方图有 B 个区间，由一个 B 维向量表示。HD公式如下：

HD

两个直方图之间的差值可以代表另一种分布。

SMR-HDy

  这个算法是解决该问题的一个简单方法，是第二个算法的基准。

  考虑有上下文的集合$C = \{1,2,…,|C|\}$。对每一个上下文$i \in C$，都有可用的事件训练集$T_i \in T$和事件验证集$V_i \in V$。在这些集合中的每一个事件都关联一个类标签$y \in \{+,-\}$。令$V_i^y \subseteq V_i$是$V_i$的子集，其包含$V_i$中所有标签是$y$的样本。

  从训练集$T_i$，作者推理得到分类模型$M_i$（ps：对每一个上下文单独训练一个分类器）。该算法接着计算在验证集$V_i$上由$M_i$获得的分数的正则直方图$H_i^y,y\in \{+,-\}$。

  最后，给定事件$U$的无标注测试集，计算在测试集$U$上由分类器$M_i$获得的分数的正则直方图$H_i^U$。接着我们考虑对$U$最可能的上下文：

context

  换句话说，$\hat{c}_s$是最小化分类器$M_{\hat{c}_s}$在验证集$V_{\hat{c}_s}$和测试集$U$获得分数的分布之间的散度的上下文。SMR-HDy背后的基本原理是验证集的直方图代表了分数的预期行为。比如，$H_1^+$代表的是对于使用$M_1$在context 1的正事件上取得分数所期望的行为。最后，HDy算法提供一个插值参数（在该论文中，即是正类比率的估计），该参数可以最小化测试直方图和两个训练直方图插值之间的散度。另外，该算法的一个副产品是，我们得到一种比较不同的上下文的测量方法。

  值得注意的是，作者指出，在SMR-HDy算法中，我们期望的分数的行为，分数是由每个模型在仅属于它（模型）对应的上下文的事件上产生的。这是一种简单的方法，实际上作者认为这样会丢弃有用信息：分数的预期行为，当分数是由分类器$M_i$在验证集$V_j$上取得的且$i \ne j$。

XO-HDy

  作者提出的第二个方法是Crossed Opinions HDy（XO-HDy），该算法考虑了当来自一个事件的分数是由对应不同上下文的分类器所获得是，该分数如何预期行为。

  考虑$H_{i,j}^y$是由分类器$M_i$在验证集$V_j^y$上所获得分数的正则直方图。另外$\alpha_{i,j}$如下所示：

alpha_ij

  对$U$而言，最可能的上下文如下所示：

XO

Figure 3提供了在该算法中数据分数在 Hellinger Distance 内的计算的视觉阐述。

Figure 3

该算法提供的$a_{\hat{c}_x}$，即是正类比率的估计。

分类调整

  作者指出，一旦获得了推断上下文$\hat{c}$和正类比率的估计$\hat{a}$，我们就可以使用一个新的阈值重调分类器，并重新分类$U$中的事件。作者期望$\hat{a}$%的样本属于正类。因此，可以将分类阈值设为获得分数的$(1-\hat{a})$%。

三条限制

  1. 只适用于二分类问题。
  2. 上下文纯洁性假设，也就是，相邻实例属于同一个上下文。
  3. 假设我们已知所有上下文。

A Tutorial on Network Embeddings

介绍

  原文地址

  NE（network embedding）的中心思想是找到一种映射函数，可以将网络中的每一个节点转换为一个低维潜在表示。这些表示可以作为特征，用于在图上的一般任务，如分裂，聚类，链路预测和可视化。

Alt text

  目标：

  1. 适应性。

    • 真正的网络在不断演化。不应要求重复学习过程。

  2. 可扩展。

    • 真正的网络通常很巨大，因此网络嵌入算法应该在短时间内处理大规模的网络。

  3. 社区感知。

    • 潜在表示之间的距离应该用以表示对应的节点之间的相似性度量。

  4. 低维。

    • 当标注数据稀缺时，低维模型泛化的更好，并能加速收敛和推理。

  5. 连续性。

    • 要求在连续空间内，潜在表示能建模部分社区成员关系。除了提供社区成员关系的细微视角外，连续的表示在社区间具有平滑的决策边界，令分类更鲁棒。

    此文包含：

    • 网络嵌入的概述
    • 无监督网络嵌入方法在无特征同质网络上的应用
    • 在特征网络和部分标注网络上的嵌入方法
    • 讨论异质网络嵌入算法

网络嵌入的简短历史

传统意义的网络嵌入

  传统意义上，图嵌入被视为降维。

  1. PCA
  2. 多维缩放（MDS）
    • 将 M 的每一行投影到 k 维向量，同时在 k 维空间中保留 不同对象在原始特征矩阵 M 中的距离。
  3. Isomap
    • Isomap是 MDS 的扩展，通过将每个节点与特定距离内的节点连接构造邻域图，在邻域图上使用 MDS ，以保持非线性流形的整体结构
  4. 局部线性嵌入（LLE）
    • 仅压榨数据点的局部邻域，不试图估计遥远数据点之间的距离。LLE 假设输入数据本质上是从某种潜在流行上采样得到的，一个数据点可以被重建为它邻居们的线性组合。

  方法1，2只能够捕捉线性结构信息，不能发现输入数据之间的非线性。通常来说，以上方法能在小网络上有很好的表现。然而，这些方法的时间复杂度至少是二次，无法在大规模网络上运行。

深度学习时代

  DeepWalk是被提出的第一个使用深度学习方法的网络嵌入方法。DeepWalk将节点当作单词，生成短的随机行走作为句子，弥合了网络嵌入和词嵌入之间的差距。然后，神经语言模型如 Skip-gram 可以应用在这些随机行走上获得网络嵌入。

DeepWalk范式的三个步骤：

  1. 选择一个和输入图关联的矩阵。
  2. 图采样，节点序列从选中的矩阵中采样得到。这一步是可选的。
  3. 从生成的序列（或是第一步选的矩阵）中学习节点嵌入。

DeepWalk范式是高度灵活的，其可从两方面被扩展：

  1. 被建模的图的复杂性可以被扩展。
  2. DeepWalk的两个关键成分的方法，即用于从潜在矩阵中采样序列和从采样的序列学习节点嵌入，都可被扩展。

DeepWalk

无监督网络嵌入

无向图嵌入

  DeepWalk 提出一种学习网络嵌入的两阶段算法。第一阶段是决定每一个节点得到上下文节点。通过在网络中生成截断的随机行走，上下文节点 v 可被定义为每一个随机行走序列中一个大小为 k 窗口内的节点。一旦上下文节点确定好了，第二步同 Skip-gram 模型一样：最大化预测上下文节点的似然概率来学习嵌入。

Algorithm 1

  许多后续的在图嵌入的工作都追随 DeepWalk 中提出的两阶段框架，在每个阶段各有不同。下表总结了一些网络嵌入方法，按照它们对上下文节点的定义和用于学习嵌入的方法分类。

Table 1

  • LINE

    • 为了更好的保存网络的结构信息，提出了一阶相似度和二阶相似度的概念，并在目标函数中结合了两者

    • 使用宽度优先策略来产生上下文节点，只有距离给定节点最多两跳的节点才被视为相邻节点

    • 使用 Skip-gram with Negative Sampling

  • Node2vc

    • 引入有偏向的随机游走，联合了 BFS 和 DFS 探索近邻
  • Walklets
    • 从$A^1,A^2,…,A^k$学习多尺度网络嵌入，由于计算$A^i$的时间复杂度至少是网络中节点数量的平方，Walklets 通过在短随机游走间跳过节点来近似$A^i$。
    • 从$A$的不同幂次来学习，在不同粒度捕捉网络的结构信息。
  • GraRep
    • 通过将图形邻接矩阵提升到不同的幂来利用不同尺度的节点共现信息，将奇异值分解（SVD）应用于邻接矩阵的幂以获得节点的低维表示
  • GraphAttention
    • 不是预先确定超参数来控制上下文节点分布，而是自动学习对图转换矩阵的幂集数的关注
    • 通过设置隐藏层，这些层里的节点能够注意其邻近节点的特征，我们能够（隐含地）为邻近的不同节点指定不同的权重，不需要进行成本高昂的矩阵运算（例如反演），也无需事先知道图的结构
  • SDNE
    • 通过深度自动编码器保持 2 跳邻居之间的接近度。它通过最小化它们的表示之间的欧几里德距离来进一步保持相邻节点之间的接近度。
    • 具有多层非线性函数，从而能够捕获到高度非线性的网络结构。然后使用一阶和二阶邻近关系来保持网络结构。二阶邻近关系被无监督学习用来捕获全局的网络结构，一阶邻近关系使用监督学习来保留网络的局部结构。
  • DNGR
    • 使用随机冲浪来捕捉图结构信息。
    • 将这些结构信息转换为一个 PPMI 矩阵，使用 层叠降噪自动编码器来嵌入节点。

有向图嵌入

  前一节介绍的在无向图上操作的方法可以通过使用有向随机行走作为训练数据，自然地泛化到有向图上。

  • HOPE
    • 是专门为有向图设计的图嵌入方法。
    • 是保存非对称传递图嵌入的通用框架，整合了一些流行的近似测量如 Katz index
    • 使用泛化的SVD来优化

边嵌入

  如链路预测这样的任务要求对图的边准确建模。一种为边$e = (u,v)$构建表示的无监督方式是在$\phi(u)$和$\phi(v)$上运用二元算子：

binary operator

在node2vec中，考虑了一些二元算子，如平均数，Hardmard product，L1距离和L2距离。然而，这些对称二元算子总是对边$(u,v)$和$(v,u)$赋予相同的值，忽略了边的方向。

figure 5

  为了缓和这个问题，Abu-El-Haija等人一种通过低秩对称投影的边表示学习方法。他们的方法由三部分组成。如Figure 5所示。

签名图嵌入

  签名图中每一条边都有一个权重$w \in \{1,-1\}$，具有权重1的边代表节点之间的积极连结，反之则为负面连结。

  • SiNE
    • 基于结构平衡理论，一个节点同敌人相比，于朋友更接近。SiNE通过最大化朋友的嵌入相似性和敌人的嵌入相似性之间的间距来保持这个性质。
    • 负连结很系数时，引入一个虚拟节点来保持这种性质。
  • SNE
    • 通过连个一个节点的上下文节点的表示来预测该节点的表示。

子图嵌入

  另一个研究分支是关于图的大规模成分的嵌入，如图的子结构或整个图。Yanardag 和 Vishwanathan提出深度图核，是一种建模图中子结构相似性的通用框架。两个图$\mathcal{G}$和$\mathcal{G}’$之间的核如下：

graph kernel

但这些表示不能揭示两个不同但相似子结构之间的相似性。也就是，即使两个图仅仅有一条边或是一个顶点不同，它们被视为完全是不同的。这种核定义导致了对角优势问题：一个图只能与它自己相似，而不能和其他图相似。为了克服这个问题，Yanardag 和 Vishwanathan提出了另一种核定义：

alternative graph kernel

为了构建$\mathcal{M}$，他们的算法首先生成图子结构的共现矩阵。然后使用Skip-gram模型在共现矩阵上训练过的子结构的潜在表示，使用其来计算$\mathcal{M}$。

使用元策略来改进网络嵌入

  至今用于网络嵌入的神经方法，都具有一些相同的弱点。首先，它们都是局部方法——受限于节点周围的结构。这种聚焦于局部结构的方法忽略了远距离的全局关系。其次，它们都依靠非收敛的优化目标，这往往使用随机梯度下降，而其会导致困在局部最小值。换句话说，这些方法学习的嵌入配置，可能会丢弃输入图的重要结构特征。

  HARP递归的合并原始图中的点和边，成功得到一系列具有相似结构的更小的图。这些合并图，每一个都有不同的粒度，提供我们原始图全局结构的视角。从最简单的形式开始，每一个图学习一系列初始表示，可以作为嵌入下一个更细节的图的良好初始。重复这个过程，直到我们得到原始图中每一个节点的嵌入。

Figure 6

属性网络嵌入

  在真实世界中，节点或边通常会关联额外的特征，称其为属性。例如在诸如 Twitter 的社交网络站点中，用户（节点）发布的文本内容是可用的。因此期望网络嵌入方法还从节点属性和边属性中的丰富内容中学习。这一部分仅讨论节点属性的工作。对不同类型的属性，有不同的策略。特别的，研究对两类属性感兴趣：高层次特征，比如文本和图片；和节点标签。

  挑战：高维稀疏特征，及如何将其整合到现有的网络嵌入方法。

  方法：

  • TADW

    • 研究节点与文本特征相关联情况

    • 第一次证明 DeepWalk 将转移概率矩阵 分解为两个低维矩阵，受此启发将文本特征矩阵合并到矩阵分解过程中。

  联合建模网络结构和节点特征（除了强制节点之间具有嵌入相似性，还应使具有相似特征向量的节点具有嵌入相似性）

  • CENE
    • 将文本内容视为特殊类型的节点，并利用节点-节点链接和节点内容链接进行节点嵌入。
    • 优化目标是共同最小化两种类型链路的损失。

  对于节点标签，整合标签信息的典型方法是联合优化产生节点嵌入和预测节点标签的损失。

  • GENE

异构网络嵌入

  异构网络具有多种类型的节点或边。大多数嵌入方法通过联合的最小化在每种模式上的损失来学习节点嵌入。这些方法或者在相同的隐空间直接学习所有节点的嵌入，或为每一种模式构造一种嵌入，然后将其映射到同一个隐空间。

网络嵌入的应用

  1. 知识表示。
    • 知识表示的问题是关于使用包含主语、谓语和对象的短句子编码关于世界的事实。
  2. 推荐系统。
    • 用户之间的交互，用户的查询和事项形成了一个异构网络，其编码了用户潜在的偏好。
  3. 自然语言处理。
    • 目前最先进的网络嵌入方法大多受自然语言处理领域的启发。反之，网络嵌入方法也可导致更好的建模人类语言。
  4. 社交网络分析。

Graph Neural Networks: A Review of Methods and Applications

Introduction

  原文地址

  图是一种建模一组节点和它们之间关系的数据结构。近来，使用机器学习分析图的研究受到了越来越多的关注，因为图具有强大的表达能力，比如，图可以被应用在大量种类的系统中，包括社会科学（社交网络），自然科学（物理系统，蛋白质交互网络），知识图和其他研究领域。作为一种独特的非欧几里得的数据结构，对于机器学习来说，图分析集中在节点分类，链路预测和聚类。图神经网络（GNNs）是基于深度学习的方法，其在图域上操作。因为其令人信服的表现和高可解释性，GNN已经成为了广泛应用的图分析方法。
  Motivations：

  • GNNs的第一个动机根植于CNNs。

    • CNNs的关键是：局部连结，参数共享和使用多层网络
    • 图是最典型的局部连结结构
    • 和传统的频谱图理论相比，参数共享可以减少计算代价
    • 多层网络结构是处理层次模式的关键，其可以捕获不同尺寸的特征

  • 第二个动机来源于图嵌入（graph embedding）

    • 基于CNNs和 图嵌入，GNNs被提出来聚合来自于图结构的信息。因此，GNNs可以建包含元素和它们之间关系的输入或是输出。
    • 此外，GNNs还可以使用 RNN kernel 同时建模图的扩散过程

  为什么GNNs值得研究：

  1. 像CNN和RNN这样的标准神经网络无法正确处理图形输入，因为它们按特定顺序堆叠节点的特征。而GNNs在每个节点上分别传播，忽略节点的输入顺序。
  2. 图中的边表示两个节点之间的依赖信息。 在标准神经网络中，依赖信息仅被视为节点的特征。 但是，GNN可以通过图结构进行传播，而不是将其用作特征的一部分。
  3. 推理是高级人工智能的一个非常重要的研究课题，人脑中的推理过程几乎都是基于从日常经验中提取的图形。

  此文包含：

  • GNN的原始模型和其变体，和一些通用框架
  • GNNs的应用：结构化场景，非结构化场景和其他场景
  • 未来研究的四个开放问题

Model

Graph Neural Network

  这部分介绍原始的图卷积网络，及其在表示能力和训练效率方面的限制。

  在一个图中，每一个节点自然地由它的特征和相关节点所定义。GNN的目标是学习到状态嵌入（state embedding）$h_v \in \mathbb{R}^s$ ，其包含每个节点的邻居的信息。状态嵌入$h_v$是节点 $v$ 的 $s$ 维向量，可被用来产生输出 $o_v$，比如节点标签。令 $f$ 是参数函数，称为局部转变函数，其在所有节点之中共享，并根据输入的邻居更新节点状态。令 $g$ 为局部输出函数，其描述了输出是如何产生的。然后，$h_v$ 和 $o_v$ 定义如下：

equal 1 2

  令 $H,O,X$ 和 $X_N$ 是分别通过堆叠所有状态，所有输出，所有特征和所有节点特征构造的向量。于是我们得到一种紧凑形式：

equal 3 4

  根据巴拿马不动点理论，GNN使用下面的经典迭代方案来计算状态：

equal 5

  当我有拥有了GNN框架之后，接下来的问题就是如何学习 $f$ 和 $g$ 的参数。对于监督学习，具有目标信息 $t_v$，损失可被写作如下形式：

equal 6

其中 $p$ 是有监督节点的数目。学习算法基于梯度下降策略，由如下步骤组成。

  • 状态 $h_v^t$ 由 Eq.1 迭代的更新，直到时间 T。它们到达 Eq.3 的不动点解决方案：$H(T) \approx H$
  • 根据 loss 计算权重 $W$ 的梯度
  • 根据上一步计算出来的梯度更新权重$W$

  Limitations：

  1. 对于不动点，迭代地更新节点的隐藏状态不高效。如果松弛不动点假设，可以设计多层网络的GNN来获得节点及其邻居更稳定的表示
  2. GNN在迭代中使用相同的参数，然而大多数流行的神经网络在不同层使用不同的参数，作为一个层次特征提取器。此外，节点隐藏状态的更新是顺序过程，不能从RNN kernel受益。
  3. 在边上的信息特征不能被原始GNN 高效建模。
  4. 如果我们聚焦于节点表示而不是图表示的话，使用不动点假设是不合适的，因为在不动点假设中，表示的分布会更在值上更平滑，具有少量信息来区分节点。

Variants of Graph Neural Networks

  这一部分作者介绍了几种GNN的变体。该部分的第一部分聚焦于在不同图类型上操作的变体，这些变体扩展了原始模型的表示能力；第二部分列出了在传播步骤上的修改（卷积，门机制，注意力机制和跳跃连结）的变体；第三部分描述了使用先进训练方法的变体。

  图类型：

Graphy Types

  传播步骤：

Propagation steps

  训练方法

training methods

Table 2

通用框架

  一些通用框架被提出来旨在将不同的方法整合到单一框架中。message passing neural network（MPNN），统一了各种GNN和GCN 方案；non-local neural network（NLNN），统一了一些自注意风格的方法；graph network（GN）统一了 MPNN，NLNN和其他变体。

   Message Passing Neural Networks

  MPNN框架抽象了几种最流行的图结构数据模型之间的共性，例如图卷积中频谱方法和非光谱方法，门控图神经网络，交互网络，分子图卷积，深张量神经网络等等。

  该模型包含了两个阶段：信息传递阶段和读出阶段。消息传递阶段（传播步骤）运行 $T$ 个时间步，根据消息函数 $M_t$ 和顶点更新函数 $U_t$ 所定义。使用消息 $m_v^t$ ，隐藏状态 $h_v^t$ 的更新函数如下：

equal 34

读出阶段使用读出函数 $R$ 计算整个图的特征向量：

equal 35

消息传递函数，顶点更新函数和读出函数可以具有不同的设置，因此 MPNN 可以泛化到一些不同的模型。

  Non-local Neural Networks

  非局部运算是计算机视觉中经典非局部均值运算的推广。非局部运算将某一位置的响应计算为所有位置特征的加权和。这组位置可以在空间、时间或时空中。 因此，NLNN 可以被视为不同“自注意”方式的统一。

  遵循非局部平均运算，通用非局部运算定义如下：

equal 37

$i$ 是输出位置的索引，$j$ 是所有可能位置的索引。$f(h_i,h_j)$可以看作是表示两点之间关系的一个标量。$g(h_j)$ 表示输入 $h_j$ 的转换。$\frac{1}{C(h)}$用来为归一化系数。

  Graph Networks

  图定义：在 GN 中，一个图被定义为一个三元组 $G = (u,H,E)$。$u$ 是全局属性，$H = \{h_i\}_{i=1:N^v}$ 是顶点集，其中 $h_i$ 是顶点的属性。$E=\{(e_k,r_k,s_k)\}_{k=1:N^e}$ 是边集合，$e_k$ 是边属性，$r_k$ 和 $s_k$ 分别是接受点和发送点的索引。

  GN block：

GN block

  计算步骤：

Computation steps

  注意这里次序并不是严格要求的。

Applications

  作者将应用分为三个场景：（1）结构化场景，其中数据具有显示的关系结构，如物理系统，分子结构和知识图谱（2）非结构化场景，其中关系结构并不是显示的，如图片，文本等。（3）其他应用场景如生成模型和和组合优化问题。

结构化场景

  1. 物理。对现实世界的物理系统进行建模是理解人类智能的最基本方面之一。通过将对象表示为节点，将关系表示为边，我们可以以简化但有效的方式执行关于对象，关系和物理的基于GNN的推理。
  2. 化学和生物学
    • 分子手印
    • 蛋白质界面预测
  3. 知识图谱

非结构化场景

  1. 图片
    • 图片分类
    • 视觉推理
    • 语义分割
  2. 文本
    • 文本分类
    • 序列标注
    • 神经机器翻译
    • 关系抽取
    • 事件抽取

其他场景

  1. 生成模型
    • 建模社交交互
    • 发现新的化学结构
    • 构建知识图谱
  2. 组合优化问题
    • TSP
    • 二次分配问题，如衡量两个图的相似性

Open problems

  1. 浅结构
    • 堆叠多层GCN 网络层会导致过平滑问题（over-smooth），也就是所有顶点会收敛到相同值
  2. 动态图
    • 如何处理具有动态结构的图
    • 当点或边出现或消失时，GNN不能适应性改变
  3. 非结构场景
    • 没有从原始数据中生成图的最佳方法
  4. 可扩展性
    • 在大数据环境下，GNN的许多核心步骤都具有很大的计算开销。

A Comprehensive Survey on Graph Neural Networks

Introduction

  在这篇综述中，作者对图神经网络做了全面的概述。作者提出了一种新的分类，将图神经网络分为五类，分别是：图卷积网络，图注意力网络，图自动编码器，图生成网络和图时空网络（graph spatial-temporal networks）。作者对这些分类之内或之外的方法做了彻底的评论，比较和总结。然后，作者介绍了图神经网络广泛的应用，总结了关于图神经网络的数据集，开源代码和基准。最后，作者关于图神经网络的未来方向给出了建议。

  原文地址

Categorization and Frameworks

  图卷积网络在捕捉图结构依赖上扮演了一个中心角色。下面，简要介绍每一种分类。

fig 3

Table 1

Taxonomy of GNNs

  图卷积网络将传统数据上的卷积操作推广到图数据上。其关键是学得一个函数 $f$ 生成 节点 $v_i$ 的表示，通过聚合节点自己的特征和邻居的特征。

  图注意力网络同GCNs一样寻找一个整合函数来融合邻居节点，随机行走和候选模型来学得一个新的表示。关键的不同是，图注意力网络使用注意力机制，其对重要的节点，随机行走和模型赋予更大的权值。注意力参数和神经网络参数是在一个端到端框架中一起学得的。

  图自动编码器是一种无监督学习框架，其旨在学习低维节点向量，先通过一个编码器，然后使用解码器来重构图数据。图自动编码器不管是对有无属性的网络来说，都是学习图嵌入的流行方式。

  图生成网络旨在从数据中生成似是而非的结构。给定图经验分布生成图具有根本的挑战性，主要是因为图是复杂的数据结构。为了解决这个问题，研究者们将生成过程分解为交替生成点和边，并引入生成对抗训练。

  图时空网络旨在从时空图中学习看不见的模式，其在许多应用中越来越重要，如交通预测和人类活动预测。图时空网络的关键思想是同时考虑空间依赖和时间依赖。

Frameworks

  图神经网络，尤其是图卷积网络，试图在图数据上复制 CNN 的成功，通过以频谱理论或空间位置来定义图卷积。使用图结构和节点内容信息作为输入，GCN 的输出使用一下的机制之一聚焦于不同的图分析任务：

  • Node-level 输出是关于节点回归和分类任务。因为图卷积模块直接给出节点的隐表达，一个多层感知机或是一个softmax 层用来作为 GCN 的最有一层。
  • Edge-level 输出关于边分类和链路预测。为了预测边的标签或是连接强度，一个额外的函数使用来自于图卷积模块的两个节点的隐表示作为输出。
  • Graph-level 输出关于图分类任务。为了获得图级的紧凑表示，池化模块被用来将图粗粒化为子图或是求和/平均所有节点的表示。

  端到端训练框架。图卷积网络可以在端到端框架之内使用监督或半监督或无监督的方式训练，这取决于学习的任务和手中可用的标签信息。

  • Semi-supervised learning for node-level classification 给定一个图，其中仅部分节点有标签，图卷积网络可以学到一个鲁棒的模型，其可以有效识别未标注节点的类标签。为此，可以通过堆叠一些图卷积层，后跟 softmax 层来构建多类分类的端到端框架。
  • Supervised learning for graph-level classification 给定一个图数据集，图级的分类旨在为整个图预测类标签。对这个任务的端到端学习可以联合图卷积层和池化过程。特别的，通过使用图卷积层，我们可以在单个图上为每个节点获得固定数目的表示。然后，我们可以获得整个图的表示，通过池化操作。最后，使用线性层和 softmax 层，我们就可以构建一个用于图分类的端到端框架。
  • Unsupervised learning for graph embedding 当图中无可用的类标签信息时，我们可以纯无监督的方式学习图嵌入，在端到端框架中。这些算法在利用边级信息有两种方式。一种简单的方式是采用自动编码器框架。另一种方式是使用负采样方法，其中采样节点对的一部分作为负样本，而现有的具有连结的节点对作为正样本。然后，在卷积层后使用 logistic 回归层，用于端到端学习。

Graph Convolutional Networks

  GCNs 方法可以分为两类，基于频谱的方法和基于空间的方法。基于频谱的方法通过引入来自图信号处理的过滤器来定义图卷积，其中卷积操作被阐释为移除图信号的噪声。基于空间的方法将图卷积定义为整合来自邻居的特征信息。

fig 1

Spectral-based GNNs

  背景。在基于频谱的方法中，图被认为是无向的。无向图的一个鲁棒的数学表示是范数图拉普拉斯矩阵：$L = I_n - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$，其中D是节点度的对角矩阵，$D_{ii} = \sum_j{A_{ij}}$。范数图拉普拉斯矩阵具有真对称半正定性质。具有这个性质，其可以被分解为$L = U\Lambda U^T$，其中$U$是按照特征值排列的特征向量矩阵，$\Lambda$是特征值的对角矩阵，$\Lambda_{ii} = \lambda_i$ 。范数拉普拉斯矩阵的特征向量来自于一个正交空间，也就是$UU^T = I$ 。在图信号处理中，$x \in R^N$ 是图中一个节点的特征向量。对 $x$ 来说，图傅立叶变化被定义为 $\mathcal{G}(x) = U^Tx$，逆图傅立叶变化是$\mathcal{G}^{-1} = U\hat{x}$。为了理解图傅立叶变换，从它的定义我们看到它确实将输入图信号投影到正交空间，其中基由由范数图拉普拉斯算子的特征向量形成。变换信号$\hat{x}$的元素是新空间中图信号的坐标，这样输入信号就被表示为 $x = \sum_i{\hat{x}_iU_i}$，这恰恰就是逆傅里叶变换。现在，对于输入信号$x$，具有一个过滤器$g \in R^N$的图卷积定义如下：

equal 1

如果我们将过滤器记为$g_\theta = diag(U^Tg)$ ，图卷积可以简化为：

equal 2

（ps：Eq.1 等于 Eq.2）

基于频谱的图卷积网络都遵循这个定义。关键的不同在于对过滤器$g_\theta$的选择。

  基于频谱的 GCNs的方法：

  Spectral CNN:

假设过滤器 $g_\theta = \Theta_{i,j}^k$是一组可学习的参数，并认为图信号是多维的，其将图卷积层定义为：

equal 3

   Chebyshev Spectral CNN（ChebNet）：

将过滤器定义为特征值的对角矩阵的切比雪夫多项式，也就是

chebyshev

切比雪夫多项式由$T_k(x) = 2xT_{k-1}(x)-T_{k-2}{x}$，$T_0(x) = 1,T_1(x) = x$所递归的定义。

作为结果，图信号 $x$ 的带有过滤器$g_\theta$ 卷积被定义如下：

eq4

  First order of ChebNet （1stChebNet：

是对 ChebNet的一阶近似。假设 K = 1 和 $\lambda_{max} = 2$，Eq.4. 被简化为：

eq5

  为了抑制参数数目和避免过拟合，1stChebNet 进一步假设$\theta = \theta_0 = -\theta$，得到下面的土卷积的定义：

eq6

  为了处理多维的图输入信号，1stChebNet提出来Eq.6.修改版本：

eq7

  由1stChebNet提出的该图卷积是位于空间中的，它弥合了基于频谱方法和基于空间方法之间的裂隙。输出的每一行代表每个节点的潜在表示，该潜在表示是通过对来自节点本身及其相邻节点的聚合信息进行线性变换而获得的，其权重由$\widetilde{A}$的行指定。

  Adaptive Graph Convolution Network（AGCN):

为了利用图拉普拉斯矩阵上不明确的隐式的结构关系，该方法使用一个残差图增强了图，该残差图是计算节点对之间的距离而构建的。

  总结：

  1. 依赖对范数图拉普拉斯矩阵的特征分解
  2. 任何对图的排列变化会导致特征基的变化
  3. 学习的过滤器是域独立的，不能用于具有其他结构的图上
  4. 特征分解时间复杂度是$O(N^3)$，空间复杂度是$O(N^2)$
  5. 需要将整个图加载进内存中来执行卷积操作

Spatial-based GNNs

  基于空间的GCNs可以被分类两类：基于循环的方法和基于组合的方法。基于循环的方法使用同一个图卷积层来更新节点的隐表示，而基于组合的方法使用不同的图卷积层来更新隐表示。Fig. 7展示了这中不同。

fig 7

  Recurrent-based Spatial GCNs：

  Graph Neural Networks(GNNs)作为图神经网络早期工作之一，GNNs循环的更新节点隐表示直到收敛。GNNs的空间图卷积定义如下：

eq8

为了保证收敛，循环函数$f(\cdot)$必须是收缩映射，其收缩两个点在映射之后的距离。

  Gated Graph Neural Networks（GGNNs使用GRU作为循环函数，减少了循环的次数。

eq9

不同于GNNs，GGNNs使用时间后向传播来学习参数。优势是不在需要约束参数确保收敛。缺点是，时间和空间效率受影响。

  Stochastic Steady-state Embedding（SSE）是为了改善学习效率而提出来的，其以异步的方式来随机更新节点隐表示。如Algorithm 1所示，SSE通过采样批数据循环的估计节点隐表示和更新参数。为了确保收敛到稳定状态，SSE的循环函数被定义为历史状态和新状态的权重的和：

eq10

尽管求和邻居信息隐示的考虑到了节点度，但这种求和的规模是否会影响算法的稳定性依然是一个问题。

Algorithm 1

  Composition Based Spatial GCNs ：

  Message Passing Neural Networks（MPNNs）包含两个阶段，消息传递阶段和读出阶段。消息传递阶段实际上运行 T-step 的基于空间的图卷积。图空间卷积由消息函数$M_t(\cdot)$和更新函数$U_t(\cdot)$定义：

eq11

读出阶段实际上是一个池化操作，其基于每个节点的隐表示得到整个图的表示：

eq12

  GraphSage一引入聚合函数来定义图卷积。聚合函数可以集成节点邻居的信息，它必须对节点次序的排列具有不变性，如求和，均值和最大值。图卷积操作定义如下：

eq13

GraphSage 提出一种批训练算法。首先，它取样一个节点固定数目的局部的 k-hop 邻居。然后，它通过聚合邻居节点的特征信息得到中央节点最后的状态。最后，它使用中央节点最后的状态来做预测和后向传播错误。这个过程如Fig 8所示。

fig 8

  Miscellaneous Variants of Spatial GCNs：

  Diffusion Convolution Neural Networks(DCNN)提出了一种图形卷积网络，它封装了图扩散过程。一个隐藏的节点表示通过使用转移概率矩阵的指数系列独立卷积输出而获得。DCNN的扩散卷积运算定义如下：

eq14

  PATCHY-SAN使用CNN来解决图分类问题。它将图结构的数据转换为网格结构数据。

  Large-scale Graph Convolution Networks（LGCN）提出一种基于节点特征信息的排序算法。

  Mixture Model Network(MoNet)将标准CNN与非欧几里得域上的卷积结构统一起来。MoNet引入伪坐标和权重函数，以使节点邻居的权重由节点与其邻居之间的相对位置（伪坐标）确定。

Graph Pooling Modules

  图池化模块可以减少方差和计算复杂度，通过对原始特征数据下采样。

  图池化有如下几种方法：

  1. 均值/最大值/求和池化
  2. ChebNet：对图粗粒化
  3. DGCNN：对节点根据它们在图中的结构角色排序。
  4. DIFFPOOL:可以生成图的层次表示

Comparison Between Spectral and Spatial Models

  1. 效率上。基于频谱的方法的计算代价随图大小急剧增大，因为需要同时计算特征向量和处理整个图，令平行处理和应对大规模的图很难。
  2. 泛化性。
  3. 灵活性。基于频谱的方法只适用于无向图，因为对有向图的拉普拉斯矩阵还没有清晰的定义。

Beyond Graph Convolutional Networks

Graph Attention Neworks

  注意力机制的优点是它们能够集中于一个物体上最重要的部分。图神经网络在聚合，整合多个模型的输出和产生面向重要性的随机行走时使用注意力机制，并从中受益。

  Methods of Graph Attention NetWorks ：

  Graph Attention Newtork(GAT)在聚合邻居特征信息时使用注意力机制。

eq20&21

  Gated Attention Network（GAAN）提出multi-head注意力机制来更新节点的隐状态，并引入自注意机制来为每个 head 计算权重：

eq22

  Graph Attention Model(GAM)提出循环神经网络模型来解决图分类问题，其通过访问重要节点序列来处理图的信息部分。模型定义如下：

eq23

  Attention Walks通过随机行走学习节点嵌入。不像deepwalk使用固定的优先级，Attention Walk使用不同的注意力权重来分解共线矩阵：

eq25

Graph Auto-encoders

  图自动编码器是学习图嵌入的方法。

  Graph Auto-encoder(GAE）第一次将GCN整合进自动编码器框架。

  Adversarially Regularized Graph Autoencoder（ARGA）引入对抗学习。

  Network Representations with Adversarially Regularized Autoencoders(NetRA) 使用sequence-to-sequence 架构重构随机行走的节点序列。

  Deep Neural Networks for GraphRepresentations(DNGR)使用堆叠去噪自动编码器来重构PPMI矩阵。

  Structural Deep Network Embedding(SDNE)使用堆叠自动编码器保留节点的一阶近似和二阶近似。一阶近似被定义为节点节点和它邻居隐表示之间的距离。

Graph Generative Networks

  图生成网络的目标是给定一组观察到的图，然后生成图。许多图生成网络是特定于领域的。

  方法：

  1. Molecular Generative Adversarial Networks (MolGAN)

    使用GAN 和RL 来生成具有所期望性质的图

  2. Deep Generative Models of Graphs (DGMG)

    • 交替重复增加节点和边的步骤，直至评价标准被激活。

  3. GraphRNN

    • 通过两级的循环神经网络
    • graph-level 的RNN 每一时间将一个新节点加入一个节点序列，edge-level RNN 为新节点和之前的节点产生边

  4. NetGAN

    • 联合 LSTM 和 Wasserstein GAN，基于随机行走的方法来生成图。

Graph Spatial-Temporal Networks

  图形时空网络同时捕捉时空图的空间依赖和时间依赖。

  方法：

  1. Diffusion Convolutional Recurrent Neural Network
    (DCRNN)
    • 引入扩散卷积来捕捉空间依赖，具有GRU的sequence-to-sequence 架构来捕捉时间依赖。
  2. CNN-GCN
    • 交替使用GCN和1D-CNN来学习时空图数据
  3. Spatial Temporal GCN (ST-GCN)
    • 将时间流扩展为图的边，以便可以使用统一的GCN模型同时提取空间和时间信息。
  4. Structural-RNN
    • 旨在在每个时间步预测节点标签
    • 由两种 RNNs 组成，nodeRNN 和edgeRNN。每个节点的时间信息通过nodeRNN和edgeRNN传递
    • 为不同的节点和边假设不同的nodeRNN和edgeRNN

Applications

Datasets

Table 5

Benchmarks & Open-source Implementations

Table 6
Table 7

Practical Applicatons

  1. 计算机视觉
    • 场景图生成
    • 点云分类和分割
    • 动作识别
    • 人-物交互
    • few-shot image classification
    • 语义分割
    • 视觉推理和问答
  2. 推荐系统
    • 链路预测（预测用户和事项之间缺失的连结）
  3. 交通预测
    • 流量预测
    • 出租车需求预测
  4. 化学
    • 分子手印
    • 预测分子性质
    • 蛋白质界面推理
    • 合成化合物
  5. 其他
    • 程序确认
    • 程序推理
    • 社交影响预测
    • 对抗性攻击避免
    • 脑网络
    • 事件检测
    • 组合优化

Future Direction

  1. 变得更深。
    • 这是由于图卷积的影响，因为它本质上推动了相邻节点的表示彼此更接近，因此理论上，无限次卷积时，所有节点的表示将收敛到单个点。
    • 这引发了一个问题，对于学习图结构的数据，变得更深是否是一个更好的策略。
  2. 感受野。
    • 一些节点具有很多邻居，一些则仅有很少的邻居。
  3. 可扩展性。
    • 一个节点的最后状态设计大量它的邻居的隐藏状态，这令后向传播很复杂。
  4. 动态和异质图。