详解图嵌入Graph Embedding之相关文献综述

详解图嵌入系列传送门：https://mhy12345.xyz/graph-embedding-tutorials/

文献综述

Relational learning via latent social dimensions

在这篇文章之前，图的多标签分类是传统算法的天下。在此之前，甚至人们探讨的都是如何给社交网络划分集群等传统问题。当时人们的思想还是类似于page-rank一样的影响力模型，一个节点的邻居是什么标签，那么这个点也应该是什么标签。

这篇文章提出了先为图中每个节点识别出一个K维向量，然后将图的分类问题转换为向量的分类问题。而这个向量本身，是图的Modularity矩阵的前K大的特征向量。Modularity细节一言难尽，可以参考实际的论文。不过感性上来看，第K个特征向量中1的项暗示了这个节点可以被分到第K类。

这篇文章算是将矩阵、线性代数那一波东西引入图嵌入中比较成功的一个例子。也是图分类从统计学、线性代数等传统方法向深度学习的图嵌入的中间产物。

DeepWalk: Online Learning of Social Representations

这篇文章首先说：“从图中一个指定点出发随机游走较短距离遍历过的点，从频数分布来说与普通英文文章中的词频相似，都符合幂律分布(power-law distribution)。”

接下来，节点的Embedding就变成了将从他开始若干路径视为“句子”，使用NLP中的词嵌入算法生成的Embedding。文章还介绍了一个称之为Hierarchical Softmax的分层求解Softmax的方法。可以使模型更加高效。

Structural Deep Network Embedding

文章首先介绍了一阶相似度(first-order proximity)和二阶相似度(second-order proximity)，其中，一阶相似度要求两个节点的编码能够有效的表征其间是否存在连边，而二阶相似度要求两个节点的编码能够有效表征他们的共同邻居的存在。实际上，一个合理的Embedding方式，应该能够同时满足一阶/二阶相似度的关联性。因此我们将一阶/二阶相似度引入到Loss函数中，作为优化的一项参数即可。

SocialGCN: An Efficient Graph Convolutional Netowork based Model for Social Recommendation

文章指出之前的很多文章没有考虑到社交网络中的信息扩散效益，通过K轮迭代的方式，使得图中中每个节点内部的信息（即节点的Embedding）有机会扩展到距离为K的节点中。

GraphGAN: Graph representation learning with generative adversarial nets.

文章指出了图表示学习诸多算法的一种分类方式——基于生成性&判别性分类。并进一步设计了基于图的生成模型算法。具体来说，生成器G尝试拟合节点 $v_c$ 的真实邻居的概率分布 $p_{true}(v|v_c)$ 。并从这个分布中采样一部分邻居用以迷惑判别器D。同时判别器D需要判断出某一个节点真的是邻居还是生成器G假装生成的。

比较特别的是，这篇文章由于存在采样，因此使用的是强化学习Policy Gradient中的“随机梯度下降算法(Stochastic gradient descent)”方法进行学习。

参考文献

[3] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

详解图嵌入Graph Embedding之算法概述

详解图嵌入系列传送门：https://mhy12345.xyz/graph-embedding-tutorials/

算法概述

将深度学习放在图上

深度学习在近十年有着井喷式的突破，随着研究者们在该领域投入大量的人力物力，大量新颖有效的结构被创造了出来，比如能够完成手写数字识别的卷积神经网络CNN，能够提取语句情感色彩的LSTM结构，能够生成图片的对抗神经网络GAN……

CIFAR-10 Samples — CIFAR-10 数据集的分类是机器学习中一个公开的基准测试问题，其任务是对一组32x32RGB的图像进行分类

现有的神经网络大多都是建立在图像和序列上的，还有少量建立在树形结构上。如何将神经网络迁移到图上，成为了很多学者研究的问题，为什么会尝试把神经网络迁移到图上呢？在笔者看来有两个原因——

第一个原因是图结构本身就是所有数据组织结构的大杂烩。我们平常处理的“链式结构”，“树形结构”，“二维网格图”都可以被“图”这样一个概念囊括。如果我们能够提出一个建立在图上面的，足够高效智能的算法，其意义在机器学习问题中不亚于大统一理论在物理中的意义。

图本身就是大量数据结构的抽象化结果，比如计算机视觉中，卷积神经网络处理的二维图像，从某种意义上也是图的一种，研究者们尝试将CNN的模型迁移到图上，就成为了现在的图卷积神经网络GCN。[1]

第二个原因是图上的分类问题，在我们生活中也大有应用。比如基于关注列表的商品推荐、社交网络中的朋友推荐、以及社交网络中的兴趣推荐等等。这些问题的核心都是将用户的关注列表抽象为图结构，并从中提取出有用的信息。

既有实现深度学习大统一的“仰望星空”，又有解决实际问题的“脚踏实地”，基于图的深度学习算法，在近年来逐渐火了起来。

图嵌入识别节点空间结构

相比于传统的深度学习问题，基于图的神经网络不仅需要处理节点自带的若干属性，还需要处理节点在图上的空间结构。

我们将通过社交网络中一类重要的数据集类别“博客”为例，讲解图嵌入的意义。博主通常会为自己的博客添加一些标签作为博客本身的介绍。这些标签同时还可以优化博客的检索与搜索。但是，并不是所有博主都会上传自己博客的标签，甚至有些博主会由于某些因素上传一些不那么准确的标签。这就要求我们的模型能从博客的关注图结构以及部分博客标签中，补全其他节点的标签。[4]

与博客网络相似的还有基于社交网络的广告推荐。不过不同的是，对于广告推荐而言，有效样本占总体数据的比重非常非常的小（毕竟只有很小一拨人会点击广告并被我们的模型捕获）。这也要求模型花更多精力投入到识别图结构本身的特征而非节点上蕴含的信息。后者对标签特征的提取与图本身无关，可以套用传统的深度学习模型，而后者对图特征的提取就需要特殊的算法解决了。而计算节点在图中的空间特征的算法就是图嵌入(Graph Embedding)或网络嵌入(Network Embedding)。

图嵌入的目标是将图中的节点表示为一个低维向量，该向量保留了节点在网络中的拓扑结构以及节点内部信息。通过这个表示向量，其他的经典深度学习算法才得以被应用到图中，最终实现分类、聚类、推荐等问题。[3]

数据集与模型评价

综述文章[3]中有一张很大的表，记录了基于图深度学习文章常用的数据集。包括类别、规模以及引用。本系列的另一篇文章会详细描述我在学习过程中了解过的数据集。

在表中，数据集被分为了引用网络(Citation Network)，社交网络(Social Network)，化学/生物的图结构(Chemical/Biological Graphs)，去结构化的图(Unstructured Graphs)和其他(Others)。每一种类型都对应了不同的问题，比如社交网络数据集着重于测试模型能否捕获临近节点的信息，以及识别出节点的空间特征，而去结构的图则着重测试模型是否可以成功泛化一些本可以有更强结构信息的图。

在图嵌入这个问题中，节点所处的空间特征很重要，因此相关的论文喜欢用社交网络数据集进行测试。一个最简洁的社交网络数据集有如下组成部分——

节点表：记录了这个图结构所有节点
边表：记录了图中的所有有向边
标签表：记录图中所有节点所述的分类

对于图上的分类算法的测试，我们一般将标签表中一部分点的数据隐藏，让模型试图通过没有隐藏的节点标签推导出这部分隐藏数据，并计算准确率。[4] 由于这是一个多标签分类问题，学术界通常使用Micro-F1和Macro-F1两个指标来衡量模型效果。

当然，对于图嵌入算法来说，模型输出的并不是分类本身，而是一个表征了节点信息的向量。在这样的情境下，我们一般以这个向量为输入，跑一个简单的分类算法。例如文章[5]就使用了一个“一对多的逻辑回归(one-vs-rest logistic regression)”来分类这些节点的embedding。

算法发展

从历史的角度来看图嵌入算法的发展历程，最初这类算法使用传统概率模型，通过类似于page-rank的思路计算出每个节点属于每一类的概率。接下来，在传统领域，有些学者引入了图的拉普拉斯矩阵与模块度矩阵来优化分类效果。这类做法归根结底是使用更为复杂精巧的数学模型解决问题。

当然，随着深度学习的发展，有很多学者使用了诸多深度学习的方法，比如之前所说的图嵌入与图卷积神经网络。这类方法尝试重现深度学习在其他领域的突破性成功。至今为止，start-of-art的模型当然是基于深度学习的。我们可以从paperwithcode网站的排行榜上面看到当前最新的图嵌入算法。

这些基于深度学习的图算法有很多不同的思路，比如是以DeepWalk[5]、SocialGCN[7]为代表算法的通过随机游走、多重迭代等遍历策略来生成的图嵌入算法。另一种是以SDNE[6]为代表，通过设计损失函数引导梯度下降，来保证嵌入向量能够表示某种特定的图结构信息。详细的介绍可以看本系列另一篇文章详解图嵌入Graph Embedding之相关文献综述

引用

[1] Niepert, M., Ahmed, M., & Kutzkov, K. (2016, June). Learning convolutional neural networks for graphs. In International conference on machine learning (pp. 2014-2023).

[2] Wang, H., Wang, J., Wang, J., Zhao, M., Zhang, W., Zhang, F., … & Guo, M. (2018, April). Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence.

[3] Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2019). A comprehensive survey on graph neural networks. arXiv preprint arXiv:1901.00596.

[4] Tang, L., & Liu, H. (2009, June). Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817-826). ACM.

[5] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ACM.

[6] Wang, D., Cui, P., & Zhu, W. (2016, August). Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1225-1234). ACM.

[7] Wu, L., Sun, P., Hong, R., Fu, Y., Wang, X., & Wang, M. (2018). SocialGCN: An Efficient Graph Convolutional Network based Model for Social Recommendation. arXiv preprint arXiv:1811.02815.

图谱分解的拉普拉斯矩阵中特征值与特征向量的含义

图的谱分解是人们研究图的一个重要方向，对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[1]时，发现其中图的谱分解涉及到图的拉普拉斯矩阵的特征值与特征向量非常难以理解，因此我花了一段时间研究了网上的资料，最终写下了这篇文章。

拉普拉斯矩阵的含义

说到拉普拉斯矩阵，不得不先提一下与之相关的另一个我们比较熟悉的数学概念：拉普拉斯算子。

$\Delta f = \nabla^2 f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}$

在图像处理中，拉普拉斯算子可以用于边缘检测，比如下面这张图，就是对x坐标使用了拉普拉斯算子的结果——

See the source image — 拉普拉斯算子刻画了“某一个像素点变为其相邻的元素点产生的期望影响大小”：在颜色剧烈变化的图像边缘拉普拉斯算子计算出来的值较大，而均匀色块计算出来的值则为零，表示一个像素变为相邻元素的期望影响为零

当然，上面的图片也可以看做以 $\left( \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right)$ 作为卷积核的图卷积操作，这样的卷积适用于抓取横向的边缘信息。当然我们也可以设计卷积核同时抓取横向和纵向的信息 $\left( \begin{matrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{matrix} \right)$ 。这个卷积核就是上面列到的拉普拉斯算子的离散版本了。

从直观上来说，使用上述的拉普拉斯算子进行卷积操作计算了图像的边界信息。实际上，我们也可以理解为某一个像素点变为其相邻的元素点产生的期望影响大小。从某种意义上来说，拉普拉斯算子非常成功刻画了一个像素的邻域信息。

对于图像来说，拉普拉斯矩阵就是将卷积的操作修改为矩阵，如一个 $3\times 3$ 的图像，有

$L = \left( \begin{matrix} 2 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \\ -1 & 3 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & \\ 0 & -1 & 2 & 0 & 0 & -1 & 0 & 0 & 0 & \\ -1 & 0 & 0 & 3 & -1 & 0 & -1 & 0 & 0 & \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & \\ 0 & 0 & -1 & 0 & -1 & 3 & 0 & 0 & -1 & \\ 0 & 0 & 0 & -1 & 0 & 0 & 2 & -1 & 0 & \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 3 & -1 & \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 2 \end{matrix} \right)$

上述矩阵的第一行表示：图像拉普拉斯矩阵第一项值 $Lx_{(0)} = 2x_{(0)}-x_{(1)}-x_{(3)}= 2x_{(0,0)}-x_{(0,1)}-x_{(1,0)}$ ，恰好就是左上角进行一次拉普拉斯卷积的结果。同时我们还可以通过观察矩阵发现，矩阵的对角线一个类似于“度数”的正整数值，而其他地方则类似于一个负的“邻接矩阵”。

而图的拉普拉斯算子，也可以理解为将一个节点权值变成其相邻节点权值的期望影响，对应的矩阵是 $L = D-W$ ，其中 $D$ 是图的度数矩阵， $W$ 是图的边权矩阵。有没有发现，不管是图，还是图像，拉普拉斯矩阵都是对角线为正数，其他地方为负数。

当然，图的拉普拉斯矩阵有若干不同的变种，分别为：

非标准化的拉普拉斯矩阵： $L = D-W$
标准化的拉普拉斯矩阵： $L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}$
标准化的拉普拉斯矩阵： $L_{rw} = D^{-1}L = I - D^{-1}W$

拉普拉斯矩阵特征

我们令 $L = D-W$ ，则 $L$ 满足如下特征：

对于任意 $f \in \mathbb{R}^n$ ，有 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2$
L是对称的半正定矩阵
矩阵L的最小特征值为1，其对应的特征向量为 $1$
L的特征值是非负实数 $0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \dots \lambda_n$
L的特征值中0的个数等同于原图的连通块数量。

对于上述特性的证明如下——

特性1：

(1) $\begin{align*} f' W f &= f' D f - f' W f \\&= \sum_{i=1}^n d_i f^2_i - \sum_{i=1}^n f_i f_j w_{ij} \\&= \frac{1}{2} \left( \sum_{i=1}^n d_i f^2_i - 2 \sum_{i,j=1}^n f_i f_j w_{ij} + \sum_{i=1}^n d_i f^2_i \right) \\&= \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2\end{align*}$

特性2：

由于度数矩阵 $D$ 和权值矩阵 $W$ 都是对称的，所以 $L=D-W$ 也是对称矩阵。同时，由于特性1，我们发现 $f'Wf \geq 0$ 对于所有 $f \in \mathbb{R}$ 成立，所以矩阵是半正定的。

特性3：

将 $1$ 带入即可验证

特性4：

可以通过特性2保证特征值非负实数，通过特性3保证存在0特征值。

特性5：

倘若希望 $f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2 = 0$ ，那么我们需要保证在 $w_{i,j} \neq 0$ 时， $f_i = f_j$ ，因此， $f_i = 1$ 一定是一个可能的解，但是，当图存在多个连通块时，相等关系只需要在块内满足即可，因此，可能有等同于连通块个数个正交基满足特征值为0.

上述内容可以在参考文献[2]中查看详细信息。

基于拉普拉斯矩阵的图的谱分解

在文献[1]中，定义了 $||\nabla x||_W^2 = \sum_i \sum_j W_{ij} [x(i)-x(j)]^2$ ，其实这只是上一小节里面 $f' L f$ 的另一种表现形式而已。

不过一个比较混乱的地方在于文章[1]借用 $||\nabla x||_W^2$ 生成了一系列基 $f_0, f_1, \dots, f_m$ ，满足——

(2) $\begin{align*}f_0 = \arg min _{x \in \mathbb{R}^m, ||x||=1} ||\nabla x||_W^2 = (1/\sqrt{m}) 1_m \\f_i = \arg min _{x \in \mathbb{R}^m, ||x||=1, x \perp \{v_0, v_1, \dots, v_{i-1}\}} ||\nabla x||_W^2 \end{align*}$

实际上，这些 $f_i$ 恰好是 $L$ 的特征值从小到大对应的特征向量！

证明可以这样想，若 $f$ 为 $L$ 的 $\lambda$ 特征值对应的特征向量，且 $\|x\| = 1$ ，那么 $f' W f = \lambda f' f = \lambda$ 。现在假设 $f_0, f_1, \dots, f_{i-1}$ 是L的前i-1个特征向量，我们希望证明下一个能够最小化 $||\nabla x||_W^2$ 的向量 $f_t$ 恰好是 $f_i$ 。如果存在 $f' W f < \lambda_i$ ，那么 $f$ 一定与 $f_0, f_1, \dots, f_{i-1}$ 中的某一个向量不正交。如果保证了 $f_t$ 与 $f_0, f_1, \dots, f_{i-1}$ 正交，那么任意一个非 $f_t$ 的向量，一定包含了一个特征值大于等于 $\lambda_i$ 的基，则最终一定没有 $f_i$ 优。因此，我们发现将 $L$ 的特征向量作为解是最优的。

谱分解的作用

我们可以使用傅里叶对于卷积的优化来类比图的谱分解对于图卷积的意义。原来图上面做卷积是将一个邻域内的点与一个“卷积核”做卷积，这个“卷积核”的权值个数会相对比较多一些，而谱分解就是考虑到了“时域的卷积等于频域的点积”。将图的权值矩阵映射为“不同频率的分量强度为多少”，而对这个“强度”做点积完全等效于原来的卷积。这样一方面减少运算量，另一方面还减少了（如神经网络的）待训练权值个数。

引用

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[2] Von Luxburg, Ulrike. “A tutorial on spectral clustering.” Statistics and computing 17.4 (2007): 395-416.

[3] 图卷积神经网络(GCN)详解:包括了数学基础(傅里叶，拉普拉斯)

SelectorGAN汉字风格迁移模型（Chinese Charactor Style Transfer)

这个项目是在 CVPR论文 Separating Style and Content for Generalized Style Transfer的基础上改进而来的，是我和LJSthu在学校人工神经网络课程上面的课程作业。我们提出的模型叫做SelectorGAN，从模型效果上面来看，大幅度超越了上文中提出的state of art算法EMD，但模型本身并没有对应的paper，因此，如果希望研究汉字迁移问题，并且引用本文的模型，可以直接引用本博客。

我们的模型尝试处理这样一个问题：给定风格A的16个字体图片，以及字B的不同风格16个图片，尝试合成同时拥有字体A与风格B的图片。如下图所示，一个是ground truth，一个是模型输出，你能猜出谁是谁吗？

首先，我们找到了原文模型EMD的代码，并使用自己的数据集进行复现，得到下图的效果，其中右图是ground true，左图是模型生成结果。可以发现，在我们自己的数据集（规模和原文差不多）上面，模型完全没有paper里面配图的讲的那么好。

与之对比的，是我们提出的SelectorGAN输出如下图所示，其中，左边是ground truth ，右边是模型的输出结果。最明显的区别是我们的模型不容易生成全黑或者全白的无意义图片，几乎所有文字都是清晰可辨的。

在介绍我们的模型之前，我们先分析了当前state of art模型的缺陷。EMD模型的图例如下图所示，将16张候选图片，输入到CNN的16个channel中。这里，由于16张图片是无序不可分的，而CNN的不同Channel是有序可分的，这里就会导致交换输入图片的顺序会产生不同的结果。这其实是一个不正确的做法，倘若我们将16*1的CNN作用于16张图片修改16个为1*1的CNN分别作用于16张图片，可以将模型的参数个数降低16倍，有效降低过拟合的出现。用时，原文的欧几里得距离损失函数，也是的模型在对于生成图片没有信心时，直接输出全部空白，或者全部黑色，而正常图片也存在模糊边界的问题。这一系列问题到这了EMD模型实际跑的并没有文章中说的那么厉害。

我们的模型SelectorGAN为了解决上述的问题，引入了若干个特殊的机制。首先，为了解决生成图像模糊的问题，我们不在使用回归模型训练，而是使用生成模型进行创造。具体来说，我们使用了GAN。

我们使用的GAN实际上是魔改版的 CycleGAN and pix2pix，使用了GAN后，我们发现生成模型可以很好的理解诸如字体宽度，字体边界曲率等信息，并加以模仿。

接下来，我们发现，将原文中16个风格和16个字体结合生成的效果，与1个风格1个字体结合生成效果无区别。上图就是用1对1的方式生成的16张候选图片。

1对1的生成还会出现另一个比较麻烦的东西，就是生成器容易通过增删笔画的方式欺骗判别器。

通常，当原字体与目标字体长款比差距较大时，Generator认为增添笔画可以糊弄Discriminator，而且实际上它成功了。

对于上述的问题，我们发现，我们现在有整整16张候选图片。我们希望能够设计出一个评分模型Selector实现字体的选择。这个Selector应该怎么设计呢？

一个直观的想法是直接使用Discriminator的输出当做Selector，因为Discriminator觉得“真的”的图片往往真的很像答案。但是这样做并不好，因为Discriminator输入的是一堆“真的或者假的”图片，但是实际上，即使是假的图片，不考虑原来输入的话，在风格上都是无懈可击的。这时Discriminator并不能很好的判断出输出的好坏。

基于上面的考虑，我们额外设计了一个Selector模型，作为一个评分模型，通过预测Discriminator的评分进行训练，与Discriminator不同的是，Selector同时使用原始输入图片与Generator的生成图片作为输入，且可以理解为Discriminator的滑动平均。降低了Discriminator的抖动。（当然，实验证明，将Selector评分和Discriminator评分加权平均能够获得更好的效果）

上面两个图片介绍了我们的SelectorGAN的基本原理。同时，我们也在模型上进行了若干试验，比如对于style vector进行插值，可以得到两种风格间的渐变矩阵。

以上就是对于我们模型的简要介绍，有兴趣也可以阅读我们的展示ppt与课程论文。

SelectorGAN

汉字风格迁移-2.0

月份：2019年8月