详解图嵌入Graph Embedding之社交网络应用

社交网络推荐是图嵌入(Graph Embedding)的经典应用场景。这篇文章会介绍图嵌入具体到社交网络问题中，派生出的解决算法。

研究问题

协同过滤

协同过滤(Collaborative Filtering)算法在给定用户(user)对于物品(item)的评分矩阵 $R$ 后，将用户和物品都投影到同样的低维空间中，而用户对于物品的期望评分应该可以用双方在低维空间投影向量的相似度刻画。[1]

社交网络推荐

社交网络推荐(Social Recommendation)着重研究的是在社交网络中特有的性质——节点蕴含的信息可以通过社交网络的邻居进行扩散。在社交网络的邻居倾向于拥有相同的偏好。[1]

社交网络的特点

数据稀疏

社交网络的一大特点是稀疏性[1]，不仅一个节点的邻居非常稀疏，而且通常来说用户的反馈也是稀疏的。社交网络推荐系统的典型应用就是通过少数用户的标签推测出其他用户的标签，这种场景下可见的标签必然是及其稀疏的。

属性多元性

相比于其它问题中，图的节点信息较少。在社交网络图结构中，一个节点（用户）拥有非常多的属性，如年龄、性别、地域、经历等等。[1] 同时，两个节点的联系也存在不同的属性，他们可能是亲属、同事、同学，或者仅仅是兴趣相同的线上朋友。这意味着图中的连边并不一定意味着相同的兴趣爱好（相同的标签）[2]。

小世界现象

小世界现象(Small World Phenomenon)说的是在一个比较大的人口集合中，选取任意两个人作为起点终点，计算从起点到终点的“认识链”（即链上的人依次互相认识），这个链长平均为5.7。该现象暗示社交网络图的直径非常小，而且信息扩散是指数级别的，而一般来说社交网络中的“局部”指的是从起点开始1到2跳形成的邻域。[2]

节点度数分布

节点度数的规模无关现象(Scale-free property)说的是在社交网络图里面，节点的度数基本上是与社交网络规模无关的（具体来说应该是O(loglogn)）的关系。[3]

引用

[1] 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.Chicago

[2] Travers, J., & Milgram, S. (1977). An experimental study of the small world problem. In Social Networks (pp. 179-197). Academic Press.

[3] Chakrabarti, D., & Faloutsos, C. (2006). Graph mining: Laws, generators, and algorithms. ACM computing surveys (CSUR), 38(1), 2.

详解图嵌入Graph Embedding之经典数据集

Yelp数据集

Yelp数据集是由美国最大的点评网站Yelp公开维护的数据集，网站开放了能够做预测的几乎所有数据。包括——

[bussiness]餐馆详情：名称、地址、坐标、评分、类别、营业时间、有没有WIFI……
[checkin]餐馆的登记时间戳
[photo]餐馆上传的室内/室外照片
[review]用户对餐厅的评价
[tip]大概是用户对餐厅的建议
[user]用户信息，历史好评/差评数量，及其好友列表

Yelp还定期举办比赛，看哪个团队的预测结果最准确。写这篇文章的时候，比赛已经进行到了第13轮。一个需要注意的是在数据集下载界面中的“Please sign by entering your initials”是让你输入姓名中姓和名的大写首字母。[1]

.<br> ├── business.json<br> ├── checkin.json<br> ├── Dataset_Challenge_Dataset_Agreement.pdf<br> ├── photo.json<br> ├── review.json<br> ├── tip.json<br> ├── user.json<br> ├── Yelp_Dataset_Challenge_Round_13.pdf<br> └── yelp_photos.tar.gz

1	.<br> ├── business.json<br> ├── checkin.json<br> ├── Dataset_Challenge_Dataset_Agreement.pdf<br> ├── photo.json<br> ├── review.json<br> ├── tip.json<br> ├── user.json<br> ├── Yelp_Dataset_Challenge_Round_13.pdf<br> └── yelp_photos.tar.gz

Wikipedia数据集

Wikipedia数据集从英文维基百科的存档中截取了1,000,000个字节的数据，并将单词的出现建立成一张图。而单词的词性标注(part-of-speech tags)被看做这个节点的标记。不过由于我不太懂NLP方面的东西，也没有找到具体建图的流程，只在[2]里面看到了一个粗略的介绍，如果有读者知道的话，欢迎留言。一个经过处理后的图数据集可以在这里找到。

BlogCatalog数据集

BlogCatalog3数据集是从著名博客目录网站BlogCatalog抓取的博客数据集，其中节点代表了每一个用户（博客），而节点的标签则是用户在网站中所属的用户组别，在一定程度上，标签反映了用户本身感兴趣的种类。[3] 数据集包括——

[edges] 所有边所连接的端点的表
[group-edges] 所有标签对应的节点编号
[nodes] 所有的节点编号
[groups] 所有的标签编号

.<br> ├── BlogCatalog-dataset<br> │&nbsp;&nbsp; ├── data<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── edges.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── group-edges.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; ├── groups.csv<br> │&nbsp;&nbsp; │&nbsp;&nbsp; └── nodes.csv<br> │&nbsp;&nbsp; └── readme.txt<br> └── BlogCatalog-dataset.zip

1	.<br> ├── BlogCatalog-dataset<br> │   ├── data<br> │   │   ├── edges.csv<br> │   │   ├── group-edges.csv<br> │   │   ├── groups.csv<br> │   │   └── nodes.csv<br> │   └── readme.txt<br> └── BlogCatalog-dataset.zip

引用

[1] 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.

[2] 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.

[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/

文献综述

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)”方法进行学习。

参考文献

详解图嵌入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

ubuntu安装ss-server

相比于普通的ssserver， ss-server命令支持更多的加密方式，也更加安全。安装它，需要首先在终端执行下列命令

apt update
apt install shadowsocks-libev

接着在用户目录新建配置文件config.json——

{
	"server":"0.0.0.0",
	"server_port":8388,
	"local_address": "127.0.0.1",
	"local_port":1880,
	"password":"<password>",
	"timeout":300,
	"method":"aes-256-gcm",
	"fast_open": false
}

表示ss-server将监听0.0.0.0的8388端口，链接密码为<password>，加密方式为aes-256-gcm（现在已知比较安全的一种加密方式）。最后使用

ss-server -c config.json

运行服务端，即可实现ss-server的shadowsocks翻墙。

对于客户端，需要下载支持aes-256-gcm的客户端，如github的shadowsocksX-NG

Segmented LRU替换算法

在LRU(Least Recently Used)算法中，我们将缓存行按照最近使用时间进行排序。每次替换其中最长时间没有访问过的缓存行。

在实际的cache替换场景中，有一个很重要的现象，即如果一个缓存行被短时间访问了超过两次，那么他极有可能在近期再次被访问。LRU算法并没有基于该现象进行优化，而常常由于某一个常用缓存行在短时间内恰好没有使用而被替换出去。

Segmented LRU算法就是用来解决上述问题的，他通过在缓存行上面新加一个位，将缓存分为两个段(segment)，分别称作试用段(probationary segment)和保护段(protected segment)。保护段里面存放了那些近期被多次访问，极有可能再次被访问的缓存行。而试用段则存放最近被导入缓存，但是并没有被多次访问的段。

上图非常清楚的解释了两个段的关系——

任何段的访问都会导致该行被移到保护段的顶端
保护段中最近未被使用的行会被退回到试用段的顶端，在替换他之前，为它提供额外的机会

当然，如果我们仔细对比了LRU和SLRU的代码，可以发现区别并不像之前我们说的这么多。如果我们将保护段和试用段连到一起，你就会发现，SLRU和LRU唯一的区别就是当一个不在缓存中的行进入缓存时，LRU算法将它放在了第0号位置，即Most Recently Used的位置，而SLRU算法将它放在了不那么高的一个位置，即保护段和试用段连接处的位置。这样SLRU算法就不会担心某一些特定代码段（比如短时间塞入了大量无用缓存行）会完全破坏缓存的有效性了。

参考文献：R. Karedla et al, “Caching Strategies to Improve Disk System Performance”, Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.

使用mac对含FDisk_partition_scheme的U盘重新分区

我有一个4G的U盘，由于用来装机后，U盘被分成了两个区。使用mac系统自带的Disk Utility只能够对于两个分区分别格式化，却不能够进行“分区”以及“删除分区”操作。

使用百度上建议的diskutil mergePartitions命令报如下错误——

Merging partitions encountered error "MediaKit reports partition (map) too small; if you recently grew your whole-disk, you should run whole-disk repair (-5341)".

使用终端命令diskutil list，可以看出U盘有如下结构——

/dev/disk5 (external, physical):
#:                       TYPE NAME                    SIZE       IDENTIFIER
0:     FDisk_partition_scheme                        *4.0 GB     disk5
1:                  Apple_HFS                         2.9 GB     disk5s1
2:                  Apple_HFS                         314.6 MB   disk5s2

第0项指示了U盘总空间大小，我猜测是类似于分区表的根目录，指示了整个树形结构的大小总和，而表中1号2号项则加起来大约4G，是我们需要合并的两个分区。

我的其他U盘的第0项的TYPE是“GUID_partition_scheme”。猜测可能我们的MAC系统不支持“FDisk_partition_scheme”的磁盘分区操作。而接下来，我们这试图将磁盘抹掉，重置为“GUID_partition_scheme”。

diskutil list
diskutil unmountDisk force disk5
sudo dd if=/dev/zero of=/dev/disk5 bs=1024 count=1024
diskutil list

此时，输出为

/dev/disk5 (external, physical):
#:                       TYPE NAME                    SIZE       IDENTIFIER
0:                                                   *4.0 GB     disk5

接着，我们使用diskutil重新对这个空白磁盘格式化

diskutil partitionDisk disk5 GPT JHFS+ "My External HD" 0g

现在，我们的磁盘就和普通u盘一样了，有3.7G的可用空间。

/dev/disk5 (external, physical):

   #:                       TYPE NAME                    SIZE       IDENTIFIER

   0:      GUID_partition_scheme                        *4.0 GB     disk5

   1:                        EFI EFI                     209.7 MB   disk5s1

   2:                  Apple_HFS My External HD          3.7 GB     disk5s2

参考链接：https://superuser.com/questions/233531/how-can-i-resolve-the-error-mediakit-reports-partition-map-too-small

浅析trapframe与context的原理与区别

TRAPFRAME与CONTEXT的区别

在ucore操作系统中，trapframe和context是很容易混淆的两个结构，他们都会出现在线程的调度中。实际上，结构体trapframe用于切换优先级、页表目录等，而context则是用于轻量级的上下文切换。从技术上来看，两者的区别在于context仅仅能够切换普通寄存器，而trapframe可以切换包括普通寄存器、段寄存器以及少量的控制寄存器。

*在看后续内容之前，你需要提前了解汇编语言、栈、C函数调用的实现。

TRAPFRAME结构体

trapframe定义如下——

struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

struct trapframe {

struct pushregs tf_regs;

uint16_t tf_gs;

uint16_t tf_padding0;

uint16_t tf_fs;

uint16_t tf_padding1;

uint16_t tf_es;

uint16_t tf_padding2;

uint16_t tf_ds;

uint16_t tf_padding3;

uint32_t tf_trapno;

/* below here defined by x86 hardware */

uint32_t tf_err;

uintptr_t tf_eip;

uint16_t tf_cs;

uint16_t tf_padding4;

uint32_t tf_eflags;

/* below here only when crossing rings, such as from user to kernel */

uintptr_t tf_esp;

uint16_t tf_ss;

uint16_t tf_padding5;

} __attribute__((packed));

这个结构体中，依次储存了——

目标寄存器
gs, fs, es, ds 段寄存器
trap_no, err 用于储存中断信息
eip, cs, eflags 用于储存陷阱(trap)返回后的目的地址
esp, ss 在权限发生变化时，用于指示新的栈的位置

有两个地方使用了trapframe，一个是中断调用，另一个是进程切换。两者对于trapframe的使用有相似之处，但也并不完全相同。

中断调用中使用TRAPFRAME

trapframe在中断中，在前期负责中断信息的储存，后期负责中断的恢复。同时，trapframe结构体是位于栈中的，其生成和使用都是通过栈的push、pop命令实现的，这将在后面详细解释。

中断发生时，下面代码，将一系列信息压到栈中。这些信息在后续的，trap(struct trapframe *tf)函数中，被对齐到了tf结构体中。

.globl __alltraps                                                                                                                  
__alltraps:                                                                                                                        
    # push registers to build a trap frame                                                                                         
    # therefore make the stack look like a struct trapframe                                                                        
    pushl %ds                                                                                                                      
    pushl %es                                                                                                                      
    pushl %fs                                                                                                                      
    pushl %gs                                                                                                                      
    pushal                                                                                                                         
                                                                                                                                   
    # load GD_KDATA into %ds and %es to set up data segments for kernel
    movl $GD_KDATA, %eax
    movw %ax, %ds
    movw %ax, %es

    # push %esp to pass a pointer to the trapframe as an argument to trap()
    pushl %esp

    # call trap(tf), where tf=%esp
    call trap

.globl __alltraps

__alltraps:

# push registers to build a trap frame

# therefore make the stack look like a struct trapframe

pushl %ds

pushl %es

pushl %fs

pushl %gs

pushal

# load GD_KDATA into %ds and %es to set up data segments for kernel

movl $GD_KDATA, %eax

movw %ax, %ds

movw %ax, %es

# push %esp to pass a pointer to the trapframe as an argument to trap()

pushl %esp

# call trap(tf), where tf=%esp

call trap

中断处理完成后，需要恢复原来的运行状态，此时，按顺序将之前push的所有信息pop出来即可。

    # call trap(tf), where tf=%esp
    call trap

    # pop the pushed stack pointer
    popl %esp

    # return falls through to trapret...
.globl __trapret
__trapret:
    # restore registers from stack
    popal

    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds

    # get rid of the trap number and error code
    addl $0x8, %esp
    iret

# call trap(tf), where tf=%esp

call trap

# pop the pushed stack pointer

popl %esp

# return falls through to trapret...

.globl __trapret

__trapret:

# restore registers from stack

popal

# restore %ds, %es, %fs and %gs

popl %gs

popl %fs

popl %es

popl %ds

# get rid of the trap number and error code

addl $0x8, %esp

iret

当然，倘若读者认为trapframe仅仅像这样中规中矩的实现信息的保存，那就太小看他了。我们发现，在调用call trap之后，有一句popl %esp，而后续恢复的信息完全是基于该%esp进行定位的，那么在中断处理内存中，如果我们强行修改%esp成为我们希望接下来运行的代码段的trap描述，那么经过__trapret代码恢复trapframe后，你就可以让程序跳转到任何你希望的地方。

比如下面代码就实现了内核态到用户态的切换。

    if (tf->tf_cs == KERNEL_CS) {                                                                                              
        cprintf("T_SWITH_TOU\n");                                                                                              
        userframe =  *tf;                                                                                                      
        userframe.tf_cs = USER_CS;                                                                                             
        userframe.tf_ds = USER_DS;                                                                                             
        userframe.tf_es = USER_DS;                                                                                             
        userframe.tf_ss = USER_DS;                                                                                             
        //userframe.tf_fs = USER_DS;                                                                                           
        userframe.tf_eflags |= FL_IOPL_MASK;                                                                                   
        userframe.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8;                                                        
        *((uint32_t *)tf - 1) = (uint32_t)&userframe;                                                                     
    }

if (tf->tf_cs == KERNEL_CS) {

cprintf("T_SWITH_TOU\n");

userframe = *tf;

userframe.tf_cs = USER_CS;

userframe.tf_ds = USER_DS;

userframe.tf_es = USER_DS;

userframe.tf_ss = USER_DS;

//userframe.tf_fs = USER_DS;

userframe.tf_eflags |= FL_IOPL_MASK;

userframe.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8;

*((uint32_t *)tf - 1) = (uint32_t)&userframe;

}

其中*((uint32_t *)tf - 1)这个位置的值就是之后popl %esp恢复的%esp的值。

进程切换中CONTEXT的作用

context的结构体定义如下，可以看到，其中储存了所有的用户寄存器的值。

// Saved registers for kernel context switches.                                                                                    
// Don't need to save all the %fs etc. segment registers,                                                                          
// because they are constant across kernel contexts.                                                                               
// Save all the regular registers so we don't need to care                                                                         
// which are caller save, but not the return register %eax.                                                                        
// (Not saving %eax just simplifies the switching code.)                                                                           
// The layout of context must match code in switch.S.                                                                              
struct context {                                                                                                                   
    uint32_t eip;                                                                                                                  
    uint32_t esp;                                                                                                                  
    uint32_t ebx;                                                                                                                  
    uint32_t ecx;                                                                                                                  
    uint32_t edx;                                                                                                                  
    uint32_t esi;                                                                                                                  
    uint32_t edi;                                                                                                                  
    uint32_t ebp;                                                                                                                  
};

// Saved registers for kernel context switches.

// Don't need to save all the %fs etc. segment registers,

// because they are constant across kernel contexts.

// Save all the regular registers so we don't need to care

// which are caller save, but not the return register %eax.

// (Not saving %eax just simplifies the switching code.)

// The layout of context must match code in switch.S.

struct context {

uint32_t eip;

uint32_t esp;

uint32_t ebx;

uint32_t ecx;

uint32_t edx;

uint32_t esi;

uint32_t edi;

uint32_t ebp;

};

context结构体干的事情也很简单，可以用switch_to函数囊括，即保存一系列寄存器，并恢复一系列寄存器。在C++中，switch_to是拥有两个context结构体为参数的函数switch_to(&(prev->context), &(next->context)); ，其实现如下——

switch_to:                      # switch_to(from, to)

    # save from's registers
    movl 4(%esp), %eax          # eax points to from
    popl 0(%eax)                # save eip !popl
    movl %esp, 4(%eax)          # save esp::context of from
    movl %ebx, 8(%eax)          # save ebx::context of from
    movl %ecx, 12(%eax)         # save ecx::context of from
    movl %edx, 16(%eax)         # save edx::context of from
    movl %esi, 20(%eax)         # save esi::context of from
    movl %edi, 24(%eax)         # save edi::context of from
    movl %ebp, 28(%eax)         # save ebp::context of from

    # restore to's registers
    movl 4(%esp), %eax          # not 8(%esp): popped return address already
                                # eax now points to to
    movl 28(%eax), %ebp         # restore ebp::context of to
    movl 24(%eax), %edi         # restore edi::context of to
    movl 20(%eax), %esi         # restore esi::context of to
    movl 16(%eax), %edx         # restore edx::context of to
    movl 12(%eax), %ecx         # restore ecx::context of to
    movl 8(%eax), %ebx          # restore ebx::context of to
    movl 4(%eax), %esp          # restore esp::context of to

    pushl 0(%eax)               # push eip

    ret

switch_to: # switch_to(from, to)

# save from's registers

movl 4(%esp), %eax # eax points to from

popl 0(%eax) # save eip !popl

movl %esp, 4(%eax) # save esp::context of from

movl %ebx, 8(%eax) # save ebx::context of from

movl %ecx, 12(%eax) # save ecx::context of from

movl %edx, 16(%eax) # save edx::context of from

movl %esi, 20(%eax) # save esi::context of from

movl %edi, 24(%eax) # save edi::context of from

movl %ebp, 28(%eax) # save ebp::context of from

# restore to's registers

movl 4(%esp), %eax # not 8(%esp): popped return address already

# eax now points to to

movl 28(%eax), %ebp # restore ebp::context of to

movl 24(%eax), %edi # restore edi::context of to

movl 20(%eax), %esi # restore esi::context of to

movl 16(%eax), %edx # restore edx::context of to

movl 12(%eax), %ecx # restore ecx::context of to

movl 8(%eax), %ebx # restore ebx::context of to

movl 4(%eax), %esp # restore esp::context of to

pushl 0(%eax) # push eip

ret

进程切换中TRAPFRAME的作用

那是不是进程的切换就可以直接用switch_to函数呢？答案是否定的，因为switch_to仅仅保存、恢复了普通寄存器，无法实现优先级跳转、段寄存器修改等等。这时，就要借助trapframe了。

由于switch_to函数跳转后，将调到context.eip位置。而这个跳转我们没法完全实现进程切换，所以我们可以将其设置为一个触发二级跳转的函数，forkret。

proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);

1 2	proc->context.eip = (uintptr_t)forkret; proc->context.esp = (uintptr_t)(proc->tf);

其中，forkret定义如下（current是当前进程，也就是进程切换的目标进程），forkret不同于switch_to，它尝试使用trapframe作为进程切换的手段，而相比于context，trapframe的功能就强大多了。

static void
forkret(void) {
    forkrets(current->tf);
}

static void

forkret(void) {

forkrets(current->tf);

}

而forkrets定义如下——

.globl __trapret
__trapret:
    # restore registers from stack
    popal

    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds

    # get rid of the trap number and error code
    addl $0x8, %esp
    iret

.globl forkrets
forkrets:
    # set stack to this new process's trapframe
    movl 4(%esp), %esp
    jmp __trapret

.globl __trapret

__trapret:

# restore registers from stack

popal

# restore %ds, %es, %fs and %gs

popl %gs

popl %fs

popl %es

popl %ds

# get rid of the trap number and error code

addl $0x8, %esp

iret

.globl forkrets

forkrets:

# set stack to this new process's trapframe

movl 4(%esp), %esp

jmp __trapret

现在，又回到了中断恢复的那一段代码，而其中的逻辑也完全相同。最终，进程跳转目标进程的入口，而该入口的地址，被存放在proc->tf中。下面是kernel_thread的trapframe初始化代码，也能佐证最终调用函数入口fn被储存在了eip中。

// kernel_thread - create a kernel thread using "fn" function                                                                      
 // NOTE: the contents of temp trapframe tf will be copied to                                                                       
 //       proc->tf in do_fork-->copy_thread function                                                                                
 int                                                                                                                                
 kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {                                                                
     struct trapframe tf;                                                                                                           
     memset(&amp;tf, 0, sizeof(struct trapframe));                                                                                      
     tf.tf_cs = KERNEL_CS;                                                                                                          
     tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;                                                                                    
     tf.tf_regs.reg_ebx = (uint32_t)fn;                                                                                             
     tf.tf_regs.reg_edx = (uint32_t)arg;                                                                                            
     tf.tf_eip = (uint32_t)kernel_thread_entry;                                                                                     
     return do_fork(clone_flags | CLONE_VM, 0, &amp;tf);                                                                                
 }

// kernel_thread - create a kernel thread using "fn" function

// NOTE: the contents of temp trapframe tf will be copied to

// proc->tf in do_fork-->copy_thread function

int

kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {

struct trapframe tf;

memset(&tf, 0, sizeof(struct trapframe));

tf.tf_cs = KERNEL_CS;

tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;

tf.tf_regs.reg_ebx = (uint32_t)fn;

tf.tf_regs.reg_edx = (uint32_t)arg;

tf.tf_eip = (uint32_t)kernel_thread_entry;

return do_fork(clone_flags | CLONE_VM, 0, &tf);

}