半监督-Learning Discrete Structures for Graph Neural Networks

标签：图神经网络

动机

• 图神经网络主要优点是能够在数据点之间结合稀疏和离散的依赖关系, 但是, 图神经网络也只能在这样的图结构进行使用, 而在真实的世界中的图通常是带有噪声和不完整的, 或者根本不可用的

贡献

• 提出近似求解一个学习图的边上的离散概率分布的双层规划和学习图卷积网络的图结构和参数

思想

定义

符号定义

一个无向图 \(\mathcal{G} = \{\mathcal{V}, \mathcal{E}, A\}\), 顶点集合 \(|\mathcal{V}| = N\), 边集合 \(\mathcal{E} = M\), \(A \in \mathcal{H}_N\) 是一个邻接矩阵, 特征矩阵 \(X \in \mathcal{X}_N \subset \mathbb{R} ^{N \times n}\) ,

相关工作

图神经网络

一个标签集合 \(\mathcal{Y}\) 和一个标签映射函数 \(y: V \rightarrow \mathcal{Y}\), 给一个训练节点集 \(V_{Train}\) 去学习一个函数:

\[f_w:~~\mathcal{X} \times \mathcal{H}_{N} \rightarrow \mathcal{Y}^N ~~~~~~~~~(1) \]

通过最小化一些正则化的经验损失:

\[L(w, A) = \sum_{v \in V_{Train}}\ell(f_w(X,A)_v, y_v) + \Omega(w)~~~~~~~~~(2) \]

\(w \in \mathbb{R}^d\) 是 \(f_w\) 的参数, 对于节点 \(v\) \(f_w(X,A)\) 是 \(f_w\) 的输出, \(\ell : ~\mathcal{Y} \times \mathcal{Y} = \mathbb{R}^+\) 是一个点损失函数, \(\Omega\) 是一个正则化, 两层 GCN , 它的计算概率:

\[f_w(X,A) = Softmax(\hat{A}ReLu(\hat{A} ~ X ~ W_1)W_2)~~~~~~~~~(3) \]

\(w = (W_1 ~~~W_2)\) 是 GCN 的参数.

双层规划问题

双层规划是优化问题，其中目标函数中出现的一组变量被约束为另一个优化问题的最优解, 形式上给定两个目标函数 \(F\) 和 \(L\), \(F\) 为外目标函数和 \(L\) 内目标函数，以及两组变量 \(\theta \in \mathbb{R}^m ~~~~ w \in \mathbb{R}^d\)，\(\theta\) 外目标函数变量和 \(w\) 内目标函数变量，给出了一个双层规划形式:

\[min_{\theta, w_{\theta}}F(w_{\theta}, \theta) ~~~ s.t. ~~~ w_{\theta} \in \arg \min_{w} L (w, \theta)~~~~~~~~~(4) \]

针对上式, 我们最终目的是求解 \(F(w_{\theta}, \theta)\) 的最小值, 但它其中一个参数 \(w_{\theta}\) 是关于另外一个问题 \(L(w, \theta)\) 解的函数， 解决上式问题具有挑战性, 因为内部问题的解集通常在封闭形式中不可用. 标准的方法包括用迭代优化动力学 \(\Phi\) 的重复应用代替最小化 \(L\), 例如(随机)梯度下降. 设 \(w_{\theta, T}\) 为动力 \(\Phi\) 经过 \(T\) 次迭代后的内变量, \(w_{\theta, T} = \Phi(w_{\theta, T- 1}, \theta) = \Phi(\Phi(w_{\theta, T- 1}, \theta), \theta)\), 如果 \(\theta\) 和 \(w\) 为真实值并且带动量目标函数是平滑的, 可以进行计算函数 \(F(w_{\theta, T}, \theta)\) 关于 (\(w.r.t\)) \(\theta\) 的梯度:

\[\partial_wF(w_{\theta, T}, \theta)\nabla_{\theta}w_{\theta,T} + \partial_{\theta}F(w_{\theta, T}, \theta)~~~~~~~~~(5) \]

可用反向微积分进行有效的计算

框架

首先是输入数据节点, 利用图生成器生成图, 然后进行图采样, 优化内目标函数, 即计算梯度和更新 GCN 参数, 优化外目标函数, 计算超参数和更新图生成器 \(\theta\).

算法

Jointly Learning the Structure and Parameters

假设关于真实邻接矩阵 \(A\) 的信息缺失或不完整, 最终是寻找一个最小化泛化误差的模型, 假设存在第二个具有已知目标的实例子集 \(V_{val}\), 估计推广误差, 提出寻找 \(A\in \mathcal{H}_N\), 最小化以下参数

\[F(w_A, A) = \sum_{v \in V_{val}}\ell(f_{w,A}(X,A)_V，y_v)~~~~~~~~~(6) \]

假设 \(w_A\) 是 \(L\) 唯一最小值, 我们将等式 \((2)、(6)\) 构成一个混合整数双层规划问题的内部目标函数和外部目标函数, 其中外部目标旨在找到最优离散图结构, 内部目标是给定图的 GCN 的最优参数. 由此产生双层规划问题即使对小图也很难精确解决, 此外, 它既包含连续变量也包含离散值变量, 这使得无法应用公式 \((5)\), 所以本文维护了图结构的生成模型, 并根据离散图上的分布的 (连续) 参数重构双层规划问题; 也就是用伯努利 \(Bernoulli\) 随机变量对每条边建模, 设 \(\bar{H} =Conv(\mathcal{H}_N)\) 是 \(N\) 个节点所有邻接矩阵集的凸包, 通过将所有可能的边建模为一组具有参数矩阵 \(\theta \in \mathcal{H}_N\) 的相互独立的伯努利随机变量，我们可以将图采样为 \(\mathcal{H} \ni A \sim Ber(\theta)\). \((2)\) 和 \((6)\) 然后可以被替换，通过使用图结构上的期望。由此产生的双层问题可以写成:

\[min_{\theta \in \bar{H}_N} \mathbb{E}_{A \sim Ber(\theta)}[F(w_{\theta}, A)] ~~~~(7)~~~s.t.~~~ w_{\theta} = \arg \min \mathbb{E}_{A \sim Ber{(\theta)}}[L(w, A)] ~~~~~~(8) \]

通过采用期望, 内部和外部目标都成为伯努利参数的连续 (并且可能平滑)函数. 方程给出的双层规划问题. \((7)-(8)\) 仍然很难有效解决. 这是因为内部问题的解在封闭形式下对于 GCNs 是不可用的(目标是非凸的); 而且期望值很难精确计算. 因此, 有效的算法只能找到近似的随机解，即 \(\theta_{i，j} \in (0，1)\) 在描述一种解决方程给出的优化问题的方法之前. \((7)-(8)\) 大约在超梯度下降的情况下，我们首先转向获得最终 GCN 模型的问题, 该模型可用于预测. 对于具有 \(N\) 个节点和参数 \(\theta\) 的图上的给定分布 \(P_{\theta}\), GCN 的期望输出是:

\[f_{w}^{exp}(X) = \mathbb{E}_A[f_w(X,A)] = \sum_{A \in \mathcal{H}_N}P_{\theta}(A)f_w(X,A) ~~~~~(9) \]

不幸的是，即使对于小图，计算这个期望也是难以处理的；然而，我们可以计算出输出的经验估计:

\[\hat{f}_{w}(X) = \frac{1}{S}\sum_{i = 1}^{S} f_w(X,A) ~~~~~~~~~~~~(10) \]

其中 $S > 0 $ 是我们希望抽取的样本数量. 注意, \(f\) 是 \(f ^{exp}_w\) 的无偏估计量. 因此, 为了使用具有双层公式的 GCN \(f_w\)进行预测, 我们从分布 \(P_θ\) 中取样 \(S\) 图, 并将预测计算为 \(f_w\) 值的经验平均值

Structure Learning via Hypergradient Descent

双层规划形式自然适合于为特定的下游任务学习图形生成模型和GNN参数的问题. 这里, 外部变量θ是图生成模型的参数, 内部变量w是GCN的参数. 我们现在讨论一个实用的算法来处理方程定义的双层问题. (7)和(8). 关于内点问题, 我们注意到期望

\[ \mathbb{E}_{A \sim Ber(\theta)}[L(w,A)] = \sum_{A \in \mathcal{H}_N}P_{\theta}(A)f_w(X,A) ~~~~~~~~~(11) \]

由 \(2^{N^2}\) 项之和组成, 即使对于相对较小的图也是难以处理的. 然而, 我们可以选择易处理的近似学习动态 \(\Phi\), 例如随机梯度下降( SGD ):

\[w_{\theta, t + 1} = \Phi(w_{\theta, t}, A_t) = w_{\theta,t} - \gamma_t \nabla L(w_{\theta, t}, A_t) \]

其中 \(\gamma\) 是学习速率, 在每次迭代时画出At∞Ber(θ). 在适当的假设下, 对于 \(t → ∞\), SGD 收敛到一个依赖于边的概率分布的权向量 \(w_θ\)。设 \(w_{θ, T}\) 为\(\mathbb{E}[L]\) 的近似极小值(其中 \(T\) 可能取决于 \(θ\) ). 我们现在需要计算超辐射\(?_{\theta} \mathbb{E}_{A～Ber(θ)}[F]\) . 的估计量我们有:

\[\nabla_{\theta} \mathbb{E}[F(w_{\theta, T}, A)] = \mathbb{E}[\nabla(w_{\theta,T}, A)] = \mathbb{E}[\partial_wF(w_{\theta, T}, A) \nabla_{\theta} w_{\theta, T} + \partial_A F(w_{\theta,T}, A)\nabla_{\theta}A] \]

伪码

实验

半监督节点分类任务

总结

提出了 LDS ，一个同时学习图结构和 GNN 参数的框架。虽然我们在实验中使用了特定的 GCN 变体(Kipf & Welling，2017)，但该方法更普遍地适用于其他神经网络。LDS 的优势在于它以合理的计算成本在典型的半监督分类数据集上获得了高精度。此外，由于图生成模型 LDS 学习，边缘参数具有概率解释。这种方法有其局限性。虽然效率相对较高，但它目前无法扩展到大型数据集:这将需要一个能够处理小批量节点的实现。当所有数据点(节点)在训练期间都可用时，我们仅在转导设置中评估 LDS 。在训练之后添加额外的节点(归纳设置)目前需要从头开始重新训练整个模型。当对图进行采样时，我们当前不强制图是连通的