Multi-Class Imbalanced Graph Convolutional Network Learning

简介

论文传送门

该工作要解决的问题是图表示学习中的多类不平衡问题，也就是大多数节点属于大类，然后少数节点属于其他小类。当面对不平衡类分布时，现有的网络表示学习倾向于偏向于来自于大类的节点，而使得来自于小类的节点未经过充分训练。存在于一个类或更多类中的类别不平衡学习问题会导致其他类被过度代表，进而导致表示学习方法的性能下降。这是由于下面两个原因造成的：

1. 拓扑交互：除了每个节点关联的特征信息外，不同的节点具有与其他节点的拓扑连接，意味着节点的类别赋予不仅被其自身的特征信息决定，还被与其连接的节点决定。
2. 不清楚的边界：图数据往往具有多种高度有偏的节点类别，使得很难去平衡表示学习和准确的类别边界识别。因为，特定类别的学习可能会被邻近的类结构所影响，比如，大类可能会主导节点之间的特征传播。

因此，在这篇论文中，作者提出了双正则的图卷积网络来处理多类不平衡图，其中两种不同的正则方法被用来解决类别不平衡表示学习。为了确保所有类被同等地表示，作者提出以类别为条件的对抗训练过程来处理带标签节点的分离。同时，为了保证训练平衡,作者强迫无标签节点服从于和有标签节点隐分布相似的分布,这是通过最小化两种分布之间的KL散度得到的。

方法

首先，作者使用两层的图卷积网络在类被不平衡标签上训练来获得节点表示。该图卷积网络表示如下：

$$O=\tilde{\mathbf{A}} \operatorname{Re} L U\left(\tilde{\mathbf{A}} \mathbf{X} \mathbf{W}_{0}\right) \mathbf{W}_{1}$$

该图卷积网络得到表示传入一个softmax分类器来执行多类节点分类训练，如下所示：

$$Z=\operatorname{softmax}(O)=\frac{\exp (O)}{\sum_{i} \exp \left(O_{i}\right)}$$ $$\mathcal{L}_{g c n}=-\sum_{v_{i} \in \mathbf{V}_{l}} \sum_{j=1}^{d} Y_{i j} \ln Z_{i j}$$

为了令来自不同类的节点的表示更具有区分性，作者整合进去条件对抗雪莲过程来帮助分离不同类的标签节点的表示。该对抗训练的学习目标如下：

$$\begin{array}{c} \min _{G} \max _{D} \mathcal{L}(D, G)=\mathbb{E}_{x \sim p_{\text {data}}(x)} \log D(x \mid y) \\ +\mathbb{E}_{z \sim p_{z}(z)} \log (1-D(G(z \mid y))) \end{array}$$

另外，为了减少卷积过程中来自于大类的负传播影响，作者训练所有的无标签数据来拟合一个数据分布，该分布相似于得到很好训练的标签节点在学到的表示空间的分布。（ps：假设理解起来不容易，但实验结果来看，该步骤提升比较大），该过程促进了大类和小类之间的平衡训练。

作者假设有标签空间和无标签空间的表示服从两个d维的多元高斯分布$x_{l} \sim \mathcal{N}\left(\mu_{l}, \Sigma_{l}\right)$，$x_{u} \sim \mathcal{N}\left(\mu_{u}, \Sigma_{u}\right)$，它们的概率密度函数如下：

$$p\left(x_{l} ; \mu_{l}, \Sigma_{l}\right)=\frac{\exp \left(-\frac{1}{2}\left(x_{l}-\mu_{l}\right)^{T} \Sigma_{l}^{-1}\left(x_{l}-\mu_{l}\right)\right)}{(2 \pi)^{d / 2}\left|\Sigma_{l}\right|^{1 / 2}}$$ $$p\left(x_{u} ; \mu_{u}, \Sigma_{u}\right)=\frac{\exp \left(-\frac{1}{2}\left(x_{u}-\mu_{u}\right)^{T} \Sigma_{u}^{-1}\left(x_{u}-\mu_{u}\right)\right)}{(2 \pi)^{d / 2}\left|\Sigma_{u}\right|^{1 / 2}}$$

对于类标签之间没有关联的场景，上面的概率密度函数可以被分别被表示为d个独立高斯分布的乘积，如下：

$$p\left(x_{l} ; \mu_{l}, \Sigma_{l}\right)=\prod_{k=1}^{d} \frac{1}{\sqrt{2 \pi} \sigma_{l, k}} \exp \left(-\frac{\left(x_{l, k}-\mu_{l, k}\right)^{2}}{2 \sigma_{l, k}^{2}}\right)$$ $$p\left(x_{u} ; \mu_{u}, \Sigma_{u}\right)=\prod_{k=1}^{d} \frac{1}{\sqrt{2 \pi} \sigma_{u, k}} \exp \left(-\frac{\left(x_{u, k}-\mu_{u, k}\right)^{2}}{2 \sigma_{u, k}^{2}}\right)$$

其中参数可以从有标签样本和无标签样本中近似得到，如下：

$$\mu_{l}=\frac{1}{\left|\mathbf{V}_{l}\right|} \sum_{v_{i} \in \mathbf{V}_{l}} \mathbf{h}_{v_{i}}, \mu_{u}=\frac{1}{\left|\mathbf{V}_{u}\right|} \sum_{v_{j} \in \mathbf{V}_{u}} \mathbf{h}_{v_{j}}$$ $$\Sigma_{l}=\frac{1}{\left|\mathbf{V}_{l}\right|} \sum_{v_{i} \in \mathbf{V}_{l}}\left(\mathbf{h}_{v_{i}}-\mu_{l}\right)^{2}, \Sigma_{u}=\frac{1}{\left|\mathbf{V}_{u}\right|} \sum_{v_{j} \in \mathbf{V}_{u}}\left(\mathbf{h}_{v_{j}}-\mu_{u}\right)^{2}$$

然后基于KL散度最小化$\mathcal{N}\left(\mu_{l}, \Sigma_{l}\right)$和$\mathcal{N}\left(\mu_{u}, \Sigma_{u}\right)$之间的距离：

$$\begin{array}{r} \mathcal{L}_{\text {dist}}=\frac{1}{2}\left(\log \frac{\left|\Sigma_{u}\right|}{\left|\Sigma_{l}\right|}-d+\operatorname{tr}\left(\Sigma_{u}^{-1} \Sigma_{l}\right)+\right. \\ \left.\left(\mu_{u}-\mu_{l}\right)^{T} \Sigma_{u}^{-1}\left(\mu_{u}-\mu_{l}\right)\right) \end{array}$$

最后，为了避免由分布对齐对卷积学习带来强约束，使用下面的式子平衡二者：

$$\mathcal{L}=(1-\alpha) \mathcal{L}_{g c n}+\alpha \mathcal{L}_{\text {dist}}$$

优化

结论

真实世界中的图结构数据往往呈现高度有偏的类别分布。当从类被不平衡的图中学习时，最关键的挑战是节点具有很强的拓扑依赖，造成现有的网络表示学习方法在小类上表现不好。在该论文中，作者提出一种双正则的图卷积网络，其中包含了条件对抗训练来加强来自不同类的节点表示分离，和一个分布对齐训练来强迫大类和小类之间的平衡学习。