[论文笔记]GMNN图马尔可夫网络原理

GMNN Note

参考：

Paper: GMNN: Graph Markov Neural Networks (arxiv.org)

Paper

Motivation

• 问题定义：弱监督下的关系数据中的对象分类。形式化地来说，给定一个图G，图上有结点V表示一系列对象，在对象间存在有一系列边E，且所有结点的属性集合为。当前已知部分结点L的标签，，目的是推测出剩余结点U的标签值，。

• 该问题当前主要可以从两个方向进行研究：

  1. 统计关系学习（SRL, Statistical Relational Learning）
     以统计模型来对关系数据进行建模，代表性的方法有条件马尔可夫网络（relational Markov networks）和马尔可夫逻辑网（Markov logic networks）。这些方法通常使用条件随机场来对对象之间的依赖关系进行建模，也正是因为这种建模的有效性，这些方法能够在弱监督的对象分类上取得不错的效果。

采用CRF 序列化标注算法（sequence labeling algorithm）

• 以如下方式计算标签的联合概率分布： %3D%5Cfrac%7B1%7D%7BZ(xV)%7D%5Cprod%7B(i%2Cj)%5Cin%20E%7D%5Cpsi%7Bi%2Cj%7D(y_i%2Cy_j%2Cx_V)%20%5Ctag%7B1%7D%0A#card=math&code=p%28y_V%7Cx_V%29%3D%5Cfrac%7B1%7D%7BZ%28x_V%29%7D%5Cprod%7B%28i%2Cj%29%5Cin%20E%7D%5Cpsi_%7Bi%2Cj%7D%28y_i%2Cy_j%2Cx_V%29%20%5Ctag%7B1%7D%0A)

• #card=math&code=%28i%2Cj%29)是图G上的边，#card=math&code=%5Cpsi_%7Bi%2Cj%7D%28y_i%2Cy_j%2Cx_V%29)是边的潜在得分，通常潜在的分数是通过一些手工功能函数（如逻辑公式）的线性组合来计算的。

• 这种情况下，预测未知标签任务被看做是推断问题，我们还要去计算位置标签的后验分布#card=math&code=p%28y_U%7Cy_L%2Cx_V%29)，然而由于标签的复杂结构关系，后验十分难求。

1. 图神经网络（GNN, Graph Neural Network）
   通过非线性的神经结构，能够以端到端的方式学习到有效的对象表示（representation），从而解决对象分类的问题。例如图卷积网络（graph convolutional networks）可以有效地将周围结点的信息学习到结点的表示当中。这类方法由于能够有效地从关系数据中学习到对象的表示，目前已经达到了SOTA的表现。

• 与 SRL 相比，GNN 忽略掉标签的依赖关系，只关注于节点的特征表示。由于 GNN 将标签之间视为独立，那么此情况下标签的联合分布表示为： %3D%5Cprod%7Bn%5Cin%20V%7Dp(y_n%7Cx_V)%0A#card=math&code=p%28y_V%7Cx_V%29%3D%5Cprod%7Bn%5Cin%20V%7Dp%28y_n%7Cx_V%29%0A)

• 因此，GNN独立地独立推断每个对象的标签分布#card=math&code=p%28y_n%7Cx_V%29)。 %2Cp(y_n%7Cx_V)%3DCat(y_n%7Csoftmax(Wh_n))%5Ctag%7B2%7D%0A#card=math&code=h%3Dg%28x_V%2CE%29%2Cp%28y_n%7Cx_V%29%3DCat%28y_n%7Csoftmax%28Wh_n%29%29%5Ctag%7B2%7D%0A)

其中h是|V|×d维的特征向量，W是权重，每一轮节点特征h都会通过自己的邻居进行更新。经过多层网络的学习，特征最后经过一个softmax分类器来预测最终的标签。整个工作可以看做一个端到端的训练。代表性的方法有GCN、GAT等。

#card=math&code=p%28y_V%7Cx_V%2CE%29)

• 存在的问题

  • 在传统的统计关系学习方法中，存在着以下缺陷：

    1. 由于这些方法通常采用CRF进行建模，因此需要手动地构造一些特征函数来作为势函数的组成部分，而这些特征函数往往是启发式的，从而导致了模型的能力有限；
    2. 由于对象之间关系结构的复杂性，导致难以推理（inference）出未知标签的结点U的后验分布（posterior distribution）。
  • 在图神经网络的方法中，由于各个结点的标签是根据相关的表示分别预测的，因此忽略了各个结点的标签之间的依赖性

Method

• 提出基于半监督目标分类的图马尔可夫神经网络（GMNN, Graph Markov Neural Network），结合了SRL与GNN的优点，既能够学习到有效的结点表示，也能够对结点标签之间的依赖进行建模。
  

• GMNN利用CRF通过对象属性（节点特征）来建模标签之间的联合分布：#card=math&code=p%28y_V%7Cx_V%29)。然后采用伪似然变分EM（Pseudolikelihood Variational EM）框架对条件随机场进行优化。在E-step中，使用GNN来学习节点特征，以便进行标签预测。在M-step中，利用另一个GNN对目标标签的局部依赖性进行建模。

Pseudo-likelihood Variational EM

• GMNN使用SRL方法CRF，即 %3D%5Cfrac%7B1%7D%7BZ(xV)%7D%5Cprod%7B(i%2Cj)%5Cin%20E%7D%5Cpsi%7Bi%2Cj%7D(y_i%2Cy_j%2Cx_V)%5Ctag%7B1%7D%0A#card=math&code=p%7B%5Cphi%7D%28yV%7Cx_V%29%3D%5Cfrac%7B1%7D%7BZ%28x_V%29%7D%5Cprod%7B%28i%2Cj%29%5Cin%20E%7D%5Cpsi_%7Bi%2Cj%7D%28y_i%2Cy_j%2Cx_V%29%5Ctag%7B1%7D%0A)

来建立基于节点特征的节点标签联合分布模型#card=math&code=p_%7B%5Cphi%7D%28y_V%7Cx_V%29)，其中是模型参数。

• 链式马尔科夫随机向量场CRF公式：

%3D%5Cfrac%7B%5Cexp(w%C2%B7%5Cphi(x%2Cy))%7D%7BZ(x)%7D%5C%5C%0AZ(x)%3D%5Csum_y%5Cexp(w%C2%B7%5Cphi(x%2Cy))%0A#card=math&code=P%28y%7Cx%29%3D%5Cfrac%7B%5Cexp%28w%C2%B7%5Cphi%28x%2Cy%29%29%7D%7BZ%28x%29%7D%5C%5C%0AZ%28x%29%3D%5Csum_y%5Cexp%28w%C2%B7%5Cphi%28x%2Cy%29%29%0A)

• 在普遍的随机向量场

CRF 则使用一个指数模型来表示整个标签序列的联合概率，这个概率条件依赖于给定的完整观察序列。也就是说CRF是一个以观测序列为全局条件的随机场。存在函数#card=math&code=f%28y_1%2C…%2Cy_n%3BX%29)，使得

%3D%5Cfrac%7B%5Cexp(f(y1%2Cy_2%2C…%2Cy_n%3BX))%7D%7BZ(X)%7D%5C%5C%0A%20Z(X)%3D%5Csum%7By1%2Cy_2%2C…%2Cy_n%5Cin%20S%5En%7De%5E%7Bf(y_1%2C…%2Cy_n%3BX)%7D%0A#card=math&code=%20P%28y_1%2Cy_2%2C…%2Cy_n%7CX%29%3D%5Cfrac%7B%5Cexp%28f%28y_1%2Cy_2%2C…%2Cy_n%3BX%29%29%7D%7BZ%28X%29%7D%5C%5C%0A%20Z%28X%29%3D%5Csum%7By_1%2Cy_2%2C…%2Cy_n%5Cin%20S%5En%7De%5E%7Bf%28y_1%2C…%2Cy_n%3BX%29%7D%0A)

CRF 的计算困难之处在于上式的分母项包含了所有可能路径的求和，搜索空间非常庞大.因此做出一些简化，假设输出之间的关联仅发生在相邻位置，并且关联是指数加性的：

%3D%5Csum%7Bk%3D1%7D%5E%7Bn%7Df(y_k%3BX)%2B%5Csum%7Bk%3D2%7D%5E%7Bn%7Dg(y%7Bk-1%7D%2Cy%7Bk%7D)%0A#card=math&code=%20f%28y1%2C…%2Cy_n%3BX%29%3D%5Csum%7Bk%3D1%7D%5E%7Bn%7Df%28yk%3BX%29%2B%5Csum%7Bk%3D2%7D%5E%7Bn%7Dg%28y%7Bk-1%7D%2Cy%7Bk%7D%29%0A)

• 这里，)#card=math&code=%5Cexp%28f%28y1%2C…%2Cy_n%3BX%29%29)取了边的潜在得分：#card=math&code=%5Cpsi%7Bi%2Cj%7D%28y_i%2Cyj%2Cx_V%29) 不知道为什么这么取

• 我们通过最大化观测对象标签的对数似然函数，即#card=math&code=%5Clog%20p%7B%5Cphi%7D%28y_L%7Cx_V%29)来优化模型参数，从而求已知标签的最大似然：#card=math&code=p%7B%5Cphi%7D%28y_L%7Cx_V%29)。

• 但由于存在大量的未知标签，直接最大化对数似然很困难，因此我们通过变分推断的方法，用变分分布#card=math&code=q%5Ctheta%28y_U%7Cx_V%29)来最大化对数似然的证据下界（ELBO）： %5Cgeq%5C%5C%20%0A%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D(y_U%7Cx_V)%7D%5B%5Clog%20p%7B%5Cphi%7D(yL%2Cy_U%7Cx_V)-%5Clog%20q%7B%5Ctheta%7D(yU%7Cx_V)%5D%20%5Ctag%7B3%7D%0A#card=math&code=%5Clog%20p%7B%5Cphi%7D%28yL%7Cx_V%29%5Cgeq%5C%5C%20%0A%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%28y_U%7Cx_V%29%7D%5B%5Clog%20p%7B%5Cphi%7D%28yL%2Cy_U%7Cx_V%29-%5Clog%20q%7B%5Ctheta%7D%28y_U%7Cx_V%29%5D%20%5Ctag%7B3%7D%0A)

变分推断

假定用代表我们输入的观测值，代表模型中的隐藏变量，问题即为推断输入数据的后验条件概率分布#card=math&code=p%28Z%7CX%29)。

1. 我们提出关于隐藏变量的近似概率分布，希望从中找到一个与真实的后验分布的KL Divergence（KL散度）最小的分布#card=math&code=q%5E%2A%28X%29)。因此变分推断将推断问题转化为了求极值的优化问题。

2. 由于 )%3D%5Cint%20Q(Z)%5Cln(%7BP(X%2CZ)%7D)dZ-%5Cint%20Q(Z)%5Cln(Q(Z))dZ%2B%5Cint%20Q(Z)%5Cln(%5Cfrac%7BQ(Z)%7D%7BP(Z%7CX)%7D)dZ%0A#card=math&code=%5Cln%28P%28X%29%29%3D%5Cint%20Q%28Z%29%5Cln%28%7BP%28X%2CZ%29%7D%29dZ-%5Cint%20Q%28Z%29%5Cln%28Q%28Z%29%29dZ%2B%5Cint%20Q%28Z%29%5Cln%28%5Cfrac%7BQ%28Z%29%7D%7BP%28Z%7CX%29%7D%29dZ%0A)

等式的右端，ELBO是一个泛函，是Q的函数，由于KL距离是非负的，所以ELBO的上界就是lnP(X) 。
我们的目标是最小化KL距离，但其中P(Z|X) 是难以得知的，但式中KL距离和ELBO是此消彼长的关系，这等价于最大化ELBO。所以我们改变优化目标为evidence lower bound（简称ELBO）： %7D)-%5Cmathbb%7BE%7D(%5Cln(Q(Z))%0A#card=math&code=%5Carg%5Cmax_Q%3D%5Cmathbb%7BE%7D%28%5Cln%28%7BP%28X%2CZ%29%7D%29-%5Cmathbb%7BE%7D%28%5Cln%28Q%28Z%29%29%0A)

• 接下来，根据变分EM算法(Neal & Hinton, 1998)，可以通过变分E步和M步交替来优化该下界ELBO。

• 在变分E-step（又称推理程序）中，目标是固定并更新变分分布#card=math&code=q%5Ctheta%28y_U%7Cx_V%29)以近似真实的后验分布#card=math&code=p%5Cphi%28y_U%7Cy_L%2Cx_V%29)，即计算最佳的变分参数。

• 在M-step（也就是学习过程）中，我们固定并更新以最大化以下似然函数:（即利用E步求出的#card=math&code=q%5Ctheta%28y_U%7Cx_V%29)更新模型参数） %3D%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D(y_U%7Cx_V)%7D%5B%5Clog%7Bp%5Cphi%7D(yL%2Cy_U%7Cx_V)%5D%5Ctag%7B4%7D%0A#card=math&code=%5Cmathscr%7Bl%7D%28%5Cphi%29%3D%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%28y_U%7Cx_V%29%7D%5B%5Clog%7Bp%5Cphi%7D%28y_L%2Cy_U%7Cx_V%29%5D%5Ctag%7B4%7D%0A)

M-Step

在 M-step，这等价于优化（4）式。然而，直接优化（4）式是很困难的，因为这是对整个条件随机场进行优化，需要计算的配分函数（partition function），即（1）式中的分母 #card=math&code=Z%28xV%29)。基于#card=math&code=p%5Cphi%28y_V%7Cx_V%29)的独立性，我们可以将（4）式转化为优化（5）式：？

%20%26%20%5Ctriangleq%20%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft(%5Cmathbf%7By%7D%7BU%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%7D%5Cleft%5B%5Csum%7Bn%20%5Cin%20V%7D%20%5Clog%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7BV%20%5Cbackslash%20n%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Cright%5D%20%5C%5C%0A%20%20%26%3D%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft(%5Cmathbf%7By%7D%7BU%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%7D%5Cleft%5B%5Csum%7Bn%20%5Cin%20V%7D%20%5Clog%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D(%5Cmathrm%7Bn%7D)%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Cright%5D%0A%20%20%5Cend%7Baligned%7D%5Ctag%7B5%7D%0A#card=math&code=%20%20%5Cbegin%7Baligned%7D%0A%20%20%5Cell%7BP%20L%7D%28%5Cphi%29%20%26%20%5Ctriangleq%20%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7BU%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%7D%5Cleft%5B%5Csum%7Bn%20%5Cin%20V%7D%20%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7BV%20%5Cbackslash%20n%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%5Cright%5D%20%5C%5C%0A%20%20%26%3D%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7BU%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%7D%5Cleft%5B%5Csum%7Bn%20%5Cin%20V%7D%20%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28%5Cmathrm%7Bn%7D%29%7D%2C%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Cright%5D%0A%20%20%5Cend%7Baligned%7D%5Ctag%7B5%7D%0A)

其中 NB（n）是节点 n 的邻居。（5）式被称为伪似然函数（pseudo-likelihood function）。在似然函数（4）式中，某节点的标签与图上的其他所有节点有关；在伪似然函数（5）式中，某节点的标签只与其邻域节点有关；此时，通过最大化伪似然函数求取节点标签，就只需要聚合邻域的信息。
（5）式的意义是，聚合邻域的标签信息和特征信息，通过最大化伪似然函数求取节点标签。因为 GNN 是一个聚合邻域信息并进行消息传递的过程，所以 可以通过一个 GNN 实现。

%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%3D%5Coperatorname%7BCat%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Coperatorname%7Bsoftmax%7D%5Cleft(W%7B%5Cphi%7D%20%5Cmathbf%7Bh%7D%7B%5Cphi%2C%20n%7D%5Cright)%5Cright)%0A#card=math&code=%20%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%3D%5Coperatorname%7BCat%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Coperatorname%7Bsoftmax%7D%5Cleft%28W%7B%5Cphi%7D%20%5Cmathbf%7Bh%7D_%7B%5Cphi%2C%20n%7D%5Cright%29%5Cright%29%0A)

E-Step

然后讨论E-step中的。由于具体的后验分布是难以计算的，因此引入了平均场近似（mean-field approximation）。由于其独立性，故由平均场理论有：

%3D%5Cprod%7Bn%20%5Cin%20U%7D%20q%7B%5Ctheta%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Ctag%7B6%7D%0A#card=math&code=q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7BU%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%3D%5Cprod%7Bn%20%5Cin%20U%7D%20q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Ctag%7B6%7D%0A)

受摊还推断（amortized inference）的启发，同样使用一个GNN来参数化结点标签的后验分布，该GNN能够学习到有利于标签预测的结点的表示。

%3D%5Coperatorname%7BCat%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Coperatorname%7Bsoftmax%7D%5Cleft(W%7B%5Cphi%7D%20%5Cmathbf%7Bh%7D%7B%5Cphi%2C%20n%7D%5Cright)%5Cright)%5Ctag%7B7%7D%0A#card=math&code=q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%3D%5Coperatorname%7BCat%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Coperatorname%7Bsoftmax%7D%5Cleft%28W%7B%5Cphi%7D%20%5Cmathbf%7Bh%7D_%7B%5Cphi%2C%20n%7D%5Cright%29%5Cright%29%5Ctag%7B7%7D%0A)

最大化似然函数：证明

%3D%20%5C%5C%0A%26%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft(%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D(n)%20%5Ccap%20U%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%7D%5Cleft%5B%5Clog%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D(n)%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Cright%5D%2B%5Cmathrm%7Bconst.%7D%0A%5Cend%7Baligned%7D%5Ctag%7B8%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%26%5Clog%20q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%3D%20%5C%5C%0A%26%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28n%29%20%5Ccap%20U%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%7D%5Cleft%5B%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Cright%5D%2B%5Cmathrm%7Bconst.%7D%0A%5Cend%7Baligned%7D%5Ctag%7B8%7D%0A)

（8）式证明见附录，参考文献 [4] 中也给出了一个类似的式子的证明过程。在（8）式中，用采样代替求期望：

%20%5Ccap%20U%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%7D%5Cleft%5B%5Clog%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D(n)%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Cright%5D%20%5C%5C%0A%26%5Csimeq%20%5Clog%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D(n)%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%0A%5Cend%7Baligned%7D%5Ctag%7B9%7D%0A#card=math&code=%5Cbegin%7Baligned%7D%0A%26%5Cmathbb%7BE%7D%7Bq%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28n%29%20%5Ccap%20U%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%7D%5Cleft%5B%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7By%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%5Cright%5D%20%5C%5C%0A%26%5Csimeq%20%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%0A%5Cend%7Baligned%7D%5Ctag%7B9%7D%0A)

在上述公式中，%7D%3D%5C%7B%5Chat%20yk%5C%7D%7Bk%5Cin%20NB(n)%7D#card=math&code=%5Chat%20y%7BNB%28n%29%7D%3D%5C%7B%5Chat%20y_k%5C%7D%7Bk%5Cin%20NB%28n%29%7D)定义如下：对于对象n的每个未标记邻域k，我们给出了#card=math&code=%5Chat%20yk%5Csim%20q%5Ctheta%28y_k%7Cx_V%29)，而对于对象n每一个被标记的邻域K，被设为真实的标签。

在实践中，我们发现使用%5Ccap%20U%7D%7CxV)#card=math&code=q%5Ctheta%28y%7BNB%28n%29%5Ccap%20U%7D%7Cx_V%29)中的一个样本可以得到多个样本的可比结果，因此，在实验中为了效率，只有一个样本被使用，基于方程（8）和（9），最优#card=math&code=q%5Ctheta%28y_n%7Cx_V%29)满足：

%20%5Capprox%20p%7B%5Cphi%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D(n)%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Ctag%7B10%7D%0A#card=math&code=q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%20%5Capprox%20p%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Ctag%7B10%7D%0A)

（10）式中，是一个进行特征传播的 GNN，学习一个从特征到标签的映射，是一个进行标签传播的 GNN，学习一个从已标注节点标签到未标注节点标签的映射。即我们使用%7D%2CxV)#card=math&code=p%5Cphi%20%28yn%7C%5Chat%20y%7BNB%28n%29%7D%2CxV%29)，并最小化：%7D%2CxV)%7C%7Cq%5Ctheta(yn%7C%7Cx_V))#card=math&code=KL%28p%5Cphi%20%28yn%7C%5Chat%20y%7BNB%28n%29%7D%2CxV%29%7C%7Cq%5Ctheta%28y_n%7C%7Cx_V%29%29)

我们进一步使用并行更新策略来加速训练，即联合

为对 GMNN 进行训练，我们首先预训练：用全体节点的特征作为输入，将已标注节点标签作为监督信息，为全体节点学习“伪标签”。优化目标：

%5Ctag%7B12%7D%0A#card=math&code=O%7B%5Ctheta%2C%20L%7D%3D%5Csum%7Bn%20%5Cin%20L%7D%20%5Clog%20q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Ctag%7B12%7D%0A)

接着，将生成的“伪标签”输入，训练目标是使得其生成的标签与“伪标签”尽量接近，这就是（5）式的意义。根据（8）（9）式可将（5）式简化为：

%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Ctag%7B15%7D%0A#card=math&code=O%7B%5Cphi%7D%3D%5Csum%7Bn%20%5Cin%20V%7D%20%5Clog%20p%7B%5Cphi%7D%5Cleft%28%5Chat%7B%5Cmathbf%7By%7D%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D%28%5Cmathrm%7Bn%7D%29%7D%2C%20%5Cmathbf%7Bx%7D_%7BV%7D%5Cright%29%5Ctag%7B15%7D%0A)

最后，将节点特征再次输入，训练目标是使得其生成的标签与生成的标签尽量接近，并将此时输出的标签作为预测结果。训练目标：

%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%7D%5Cleft%5B%5Clog%20q%7B%5Ctheta%7D%5Cleft(%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright)%5Cright%5D%5Ctag%7B11%7D%0A#card=math&code=O%7B%5Ctheta%2C%20U%7D%3D%5Csum%7Bn%20%5Cin%20U%7D%20%5Cmathbb%7BE%7D%7Bp%7B%5Cphi%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Chat%7B%5Cmathbf%7By%7D%7D%7B%5Cmathrm%7BNB%7D%28n%29%7D%2C%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%7D%5Cleft%5B%5Clog%20q%7B%5Ctheta%7D%5Cleft%28%5Cmathbf%7By%7D%7Bn%7D%20%5Cmid%20%5Cmathbf%7Bx%7D%7BV%7D%5Cright%29%5Cright%5D%5Ctag%7B11%7D%0A)

所以：