【论文阅读笔记】图表示学习DONE & AdONE

Title：Outlier Resistant Unsupervised Deep Architectures for Attributed Network Embedding

Source：WSDM 2020

注：本笔记中混用了离群点和异常点两个概念

Summary

• 这里的outlier离群点类似anomaly，但是想阐述的意义有一点点不太一样，感觉在本文的范围内可以粗略的理解为node anomaly ≈ outlier
• 本文工作的重点在于表示学习，而非下游工作
• 异常点的存在会使得node embedding 的表达能力变差，对于很多下游工作有不利影响，本文提出的两个方法旨在解决这个问题

动机&本文贡献

1. 异常点会对embedding的计算带来不利影响，主要指出了node2vec对有异常点的时候会使不同社区的节点有相似的embedding，主要原因是异常点会导致出现跨社区的游走，破坏了同质性
2. 提出DONE，（首个）无监督的深度架构，用于异常值感知的属性网络嵌入 Deep Outlier aware attributed Network Embedding
3. 提出AdONE，利用对抗学习的想法来做异常感知的网络embedding Adversarial ONE

问题定义

(a) Structural Outlier: The node is structurally connected to nodes from different communities, i.e., its structural neighborhood is inconsistent. (b) Attribute Outlier: The attributes of the node are similar to that of nodes from different communities, i.e., its attribute neighborhood is inconsistent. (c) Combined Outlier: Node belongs to a community structurally but it belongs to a different community in terms of attribute similarity.

( a )结构离群点：节点在结构上与来自不同社区的节点相连，即其结构邻域是不一致的。( b )属性离群点：节点的属性与来自不同社区的节点的属性相似，即其属性邻域不一致。( c )组合离群点：节点在结构上属于一个社区，但在属性相似度上属于不同的社区。

方法前言&概览

网络预处理

• 因为现实中的网络大多是高度稀疏的，存在节点之间的连接缺失的情况。邻接矩阵的行只能捕捉到观测到的链接。受page rank的启发，作者使用重新启动的随机游走来获得更丰富的上下文，从而在拟提出的解决方案中保留更高阶的邻近性

  • 重启随机游走。备注：D是度矩阵，对角阵；​(P^{t}_i)_j 是节点i开始经过t个步骤之后到达节点j的概率，由此可以组成​P^t矩阵。对于​P^0_i来说，初始状态​(P^0_i)_i = 1

最终得到新的X

• 目前已有符号这里的A是邻接矩阵，D是度矩阵，P概率转移矩阵，X：输入的结构矩阵

架构图

本文第一个方法：DONE【上标s表示structural，上标a表示attribute】

• 两个并行的AE，分别处理结构和节点属性，前者接受的输入是::X::，后者接受的输入是::C::

• 每个节点都会有两个向量，分别代表结构向量和属性向量

• loss函数：重构损失部分会受到异常值的影响，所以作者将邻近损失proximity loss修改为【用的是X】：

  \mathcal{L}_{str}^{Prox}=\frac1N\sum_{i=1}^Nlog(\frac1{o_i^s})||\mathbf{x}_i-\hat{\mathbf{x}}_i||_2^2

  ​o_i^s是异常得分

• 同质性：loss的下一部分由同质性得到，有边连接的两个节点应该有相似的行为【用的是结构embedding】：

  \mathcal{L}_{str}^{Hom}=\frac1N\sum_{i=1}^{N}log(\frac1{o_{i}^{s}})\frac1{|\mathcal{N}(i)|}\sum_{j\in\mathcal{N}(i)}||\mathbf{h}_{i}^{s}-\mathbf{h}_{j}^{s}||_{2}^{2}

• 上面的是structure，对于属性也就是attribute AE，loss类似的，有如下两部分【用的分别是属性C和属性embedding】：

  \mathcal{L}_{attr}^{Prox}=\frac1N\sum_{i=1}^Nlog(\frac1{o_i^a})||\mathbf{c}_i-\mathbf{\hat{c}}_i||_2^2
  \mathcal{L}_{attr}^{Hom}=\frac{1}{N}\sum_{i=1}^{N}log(\frac{1}{o_{i}^{a}})\frac{1}{|\mathcal{N}(i)|}\sum_{j\in\mathcal{N}(i)}||\mathbf{h}_{i}^{a}-\mathbf{h}_{j}^{a}||_{2}^{2}

• 最后一个结合了结构和属性的loss【用的是结构emb和属性emb】：

  \mathcal{L}^{Com}=\frac1N\sum_{i=1}^Nlog(\frac1{o_i^{com}})||\mathbf{h}_i^s-\mathbf{h}_i^a||_2^2

• 总的loss，目标则是最小化它

  \begin{aligned} &\min_{\Theta,O}\mathcal{L}_{DONE} \\ &=\alpha_{1}\mathcal{L}_{str}^{Prox}+\alpha_{2}\mathcal{L}_{str}^{Hom}+\alpha_{3}\mathcal{L}_{attr}^{Prox}+\alpha_{4}\mathcal{L}_{attr}^{Hom}+\alpha_{5}\mathcal{L}^{Com} \end{aligned}

• 作者提到，​\mathcal{L}_{DONE}是凸的，可以采用“alternating minimization technique，交替极小化”进行参数更新，下面介绍更新方法

更新方法

首先推导​o_i^s, \forall i的更新算法，为了让​\sum_{i=1}^No_i^s=1，通过拉格朗日乘子法对优化目标进行改造，于是​\min_{\Theta,O}\mathcal{L}_{DONE}相应的拉格朗日函数为：

Note：只剩​\alpha_1, \alpha_2是因为只有这两部分涉及了​o_i^s，然后展开就得到了上式。

现在对​\mathbb{L}求偏导：

求导的细节：

1. 对于第一个损失项
   先不考虑带N的地方：

   \frac{\partial}{\partial o^s_i} \left( \log\left(\frac{1}{o^s_i}\right) \|x_i - \hat{x}_i\|^2 \right) = -\frac{\|x_i - \hat{x}_i\|^2}{o^s_i}

   Note：因为是对​o^s_i求导，所以其他​j, j\ne i的情况都是常数，求导=0，所以最后只会剩这一项
   考虑上N，所以最终他的偏导如下：

   -\alpha_1 \frac{\|x_i - \hat{x}_i\|^2}{N \cdot o^s_i}

2. 对于第二个损失项：
   同样先不考虑N

   \frac{\partial}{\partial o^s_i} \left( \log\left(\frac{1}{o^s_i}\right) \frac{1}{|\mathcal{N}(i)|} \sum_{j \in \mathcal{N}(i)} \|h^s_i - h^s_j\|^2 \right) = -\frac{\frac{1}{|\mathcal{N}(i)|} \sum_{j \in \mathcal{N}(i)} \|h^s_i - h^s_j\|^2}{o^s_i}

   带上N：

   -\alpha_2 \frac{\frac{1}{|N(i)|} \sum_{j \in N(i)} \|h^s_i - h^s_j\|^2}{N \cdot o^s_i}

3. 对于拉格朗日乘子项求导等于：

   \frac{\partial}{\partial o^s_i} \left( \lambda \sum_{i=1}^{N} o^s_i \right) = \lambda

4. 综合起来：

   \frac{\partial \mathbb{L}}{\partial o^s_i} = -\alpha_1 \frac{\|x_i - \hat{x}_i\|^2}{N \cdot o^s_i} - \alpha_2 \frac{\frac{1}{|N(i)|} \sum_{j \in N(i)} \|h^s_i - h^s_j\|^2}{N \cdot o^s_i} + \lambda = 0

令偏导等于0，移项等步骤可以得到：

然后，利用​\sum_{i=1}^{N} o^s_i = 1的条件，可以得到下面的式子

把​\lambda代入到之前的式子，可以将​o^s_i改写成：

类似的可以计算得到属性和联合异常score的更新方法如下：

其他

在完成训练过程后，节点的嵌入是通过​h_i=h_i^s||h_i^a得到的，这就完成了outlier resistant 的嵌入

补充：交替极小化算法

C 老师：

交替极小化算法（Alternating Minimization Algorithm）是一种优化算法，常用于解决非凸优化问题。该算法的基本思想是将一个复杂的优化问题分解成多个较简单的子问题，通过交替优化这些子问题来逐步逼近全局最优解。这种方法特别适合用于处理涉及多变量的复杂函数。

交替极小化算法的步骤：

1. 初始化：选择初始解 ​(x_0, y_0)。

2. 交替优化：

   • 固定 ​y，最小化 ​x：找到使目标函数 ​f(x, y) 最小的 ​x。
   • 固定 ​x，最小化 ​y：找到使目标函数 ​f(x, y) 最小的 ​y。

3. 迭代：重复步骤2，直到收敛到某个停止准则（例如，函数值的变化小于某个阈值或达到最大迭代次数）。

应用领域：

1. 机器学习：在矩阵分解（如非负矩阵分解）、词嵌入等领域，交替极小化被广泛应用。
2. 计算机视觉：图像恢复、特征匹配等问题常用此算法。
3. 信号处理：在一些盲源分离问题中，交替极小化也是常用方法。

优点和缺点：

优点：

• 可以处理高维度、复杂结构的问题。
• 每次迭代步骤通常比较简单，计算量较小。

缺点：

• 可能收敛到局部最优解，尤其在非凸优化问题中。
• 收敛速度可能较慢，特别是对于高度非线性的问题。

示例：

假设我们要最小化函数 ​f(x, y) = (x - y)^2 + (x + y - 2)^2。

1. 初始化：设定初始值 ​x_0 = 0, y_0 = 0。

2. 交替优化：

   • 固定 ​y = 0，最小化 ​f(x, 0) 得到 ​x_1 = 1。
   • 固定 ​x = 1，最小化 ​f(1, y) 得到 ​y_1 = 1。

经过若干次迭代后，我们可以找到使 ​f(x, y) 最小的 ​x 和 ​y。

交替极小化算法通过这种逐步优化的方法，能够有效地解决许多复杂的优化问题。

‍

本文第二个方法：AdONE

动机：

• DONE的局限：在DONE中用了L2范数来正则化embedding，但是直接用L2太严格了，因为L2正则化使节点的str和attr embedding的欧式距离太近了（因为L2正则化就是加上了一个欧式距离的约束，使得它们离得更近），即使结构和属性之间存在不一致时，这导致难以灵活地对齐嵌入

基本思路：

• 区别于DONE直接使用L2正则化做的对齐，AdONE引入了一个判别器进行结构和属性embedding的对齐，判别器用来判断一个embedding来自结构还是属性encoder，而这两个encoder需要欺骗过判别器
• 如此一来，当判别和欺骗的过程结束之后，节点​i的​h^s和​h^a能够在决策边界（不是很理解）上对齐，而欧氏空间上却不一定很近

方法

引入判别器discriminator，maximize以下loss：

其中​D就表示判别器。为了实现鉴别的效果所以max它，那么就要求​D(\mathbf{h}_i^s)趋近于1而​D(\mathbf{h}_i^a)趋近于0，也就是结构embedding鉴别为1，属性为0，相应的，encoder就需要最小化这个，使得二者被鉴别出来的结果趋近于一致，达到欺骗的目的

补充：log(x) + log(1-y)的可视化如下：

可见，该函数的最大值其实就是让前半个D（暂记作x吧）趋近于1而后半个D（暂记作y）趋近于0，那么最大值: 当​x\rightarrow1和​y\rightarrow 0时， L的最大值为0。

Encoder为了实现欺骗的效果，就需要minimize相同的函数，但是同时对异常值加权来减少它们的影响，所以就改成下式（以联合异常combined outlier为例）：

其他类型的异常，只用改​o_i^{com}就行了，最终的loss为：

与DONE类似的，最终rep的获得方式是​h_i=h_i^s||h_i^a。

实验

不再复述实验这一小节，主要还是看方法，因为方法提供了能够抵抗outlier的表示学习方式，所以理论上可以接任意的下游任务

对比方法

实验细节

上面的方法主要都是为了获得embedding h，所以很多基于表示学习的下游工作都可以基于这个来进行，不仅限于异常检测，本文还做了社区检测、节点分类等其他实验

‍