「论文阅读(简)」Learning Robust Representations with Graph Denoising Policy Network

任务与存在问题

任务：图表征学习，目的是学习低维表示，以捕获在原始图上节点直接的依赖性。

存在问题：现有的表征学习方法是基于图神经网络，他们的变体依赖于邻居信息的聚合，这使得他们对图中的噪声非常敏感。

主要工作和创新点

1. 提出了一个新颖的模型GDPNet，用于实现结合了强化学习的鲁棒性图表征学习。GDPNet由两部分组成，分别称为signal neighbor selection和representation learning。GDPNet有效地从噪声图数据中学习了节点的表征
2. 将signal neighbor selection作为一个强化学习问题，使模型能够对待特定任务的奖励信号的弱监督下执行图去噪。
3. GDPNet能够生成不可见节点的表征 in an inductive fashion，其利用了图结构和节点特特征信息的联系。
4. 证明了GDPNet在数学上等价于求解子模最大化问题，从而保证了模型可以得到有界的最优解。

提出的方法

Graph Denoising Policy Network(GDPNet)

根据signal neighbor选择环境的定义，本文引入了GDPNet模型，其中包括两个阶段：信号邻居选择（signal neighbor selection）和表示学习（representation learning）。

给定一个目标节点$v$，GDPNet首先使用他的邻居集合$\mathcal{N}(v)$作为输入，并输入一个signal neighborhood子集$\hat{\mathcal{N}}(v)$。然后通过从signal neighborhood子集$\hat{\mathcal{N}}(v)$中聚合信息来学习这个节点的表示$h_v$。

1. 确定neighborhood顺序：

   本文使用链式法则去分解signal neighbor selection分解为一个顺序的决策过程。然而这需要一个顺序去执行决定。在这里涉及了一种高级策略去学习一个顺序$[u_1,...,u_{|\mathcal{N}(v)|}]$并用于策略函数$\pi_{\theta}$做出action。

   本文为每一个邻居定义了一个regret score $\mathcal{l}$去帮助确定顺序。邻居的regret score越高就越可能被选中。在每一次的step中，本文计算每一个邻居的regret score然后采样邻居中的一个作为第t个邻居。这个regret score被描述为：

   $$l_{k}=W_{1} \cdot \operatorname{ReLU}\left(W_{2} \cdot s_{t}\right), s_{t}=\left[h_{v}^{t}, h_{u_{k}}\right]$$

   其中$u_k$是neighborhood集合$\mathcal{N}(v)$在随机顺序下的第k个邻居，$W_1,W_2$是参数矩阵。为了减小$\hat{\mathcal{N}}(v)$的大小来提高计算效率，本文引入了一个ending neighbor $u_e$到$\mathcal{N}(v)$中，用于实现提前停止的目的。当采样到$u_e$时，节点$v$的neighborhood selection过程就会停止。本文使用Softmax函数去normalize regret scores。然后从通过Softmax生成的分布中采样一个邻居作为第t个邻居。

   $$u_{t} \sim \operatorname{SOFTMAX}\left(\left[l_{1}, l_{2}, \ldots, l_{e}, \ldots, l_{\left|\mathcal{N}(v)_{e}^{c}\right|} \mid\right)\right.$$

   其中$u_{t} \in \mathcal{N}(v)_{t}^{c}$是用于signal neighbor selection的第k个邻居，$\mathcal{N}(v)_{t}^{c}=\left(\mathcal{N}(v) \backslash \hat{\mathcal{N}}(v)_{t}\right)$。$l_e$表示ending neighbor $u_e$的regret score。在选择一个邻居$u_t$后，采用策略函数$\pi_{\theta}$去决定是否选择$u_t$作为一个signal neighbor。然后$u_t$将从$\mathcal{N}(v)_{t}^{c}$中移除。

2. signal neighbor selection

   给定第t个邻居$u_t$，GDPNet在第t步采取一个动作$a_t=\{0,1\}$决定是否选择$u_t$。在这里signal neighbor的所有数量将被自动地确定。策略函数$\pi_{\theta}(a_t|s_t)$被学习在第t步($t=1,...,|\hat{\mathcal{N}}(v)|$)，去映射状态$s_t$到对应的动作，同时对应的reward $r_t$将被提供。本文的目标是去最大化在这些steps过程中所有采取的actions的总reward。

   $$\begin{aligned} \pi_{\theta}\left(a_{t} \mid s_{t}\right) &=\sigma\left(W_{1} \cdot \operatorname{ReLU}\left(W_{2} \cdot s_{t}\right)\right) \\ a_{t} & \sim \pi_{\theta} \in\{0,1\} \end{aligned}$$

   其中$W_1,W_2$是与公式1共享的权重矩阵，action $a_t$是从通过$\pi_{\theta}(a_t|s_t)$生成的伯努利分布中采样的结果。

   signal neighbor selection的目标是选择neighbor中的一个组合，最大化reward $R_{\pi}(\hat{\mathcal{N}}(v))=\mathbb{E}_{\hat{\mathcal{N}}(v)}[\sum_{t=1}^{|\hat{N}(v)|}r_t]$，其中$\hat{\mathcal{N}}(v)$是生成的signal neighborhood集合，$r_t$是特定任务的reward，用于检验动作$a_t$。$R_{\pi}$是累积reward函数。

   reward计算方式如下

   $$r_t = \frac {f_c(AGG(x_v,{x_{u_t}}))}{\sum_{\hat{u}\in\hat{\mathcal{N}}(v)_t}f_c(AGG(x_v,\{x_{\hat{u}}\}))}$$

   其中$AGG(\cdot)$聚合目标节点特征$x_v$和邻居节点特征$\{x_{u_t}\}$去更新目标节点的表示，当考虑$u_t$作为邻居时，$f_c$会从节点分类任务中返回一个micro-averaged F1 score

   这个地方有点笨比

3. Representation Learning：

   在每一个step中，GDPNet计算目标节点v和第t个邻居$u_t$的embedding，如下：

   $$\begin{aligned} h_{v}^{t} & \leftarrow \operatorname{AGG}\left(x_{v},\left\{x_{\bar{u}}, \forall \tilde{u} \in \hat{\mathcal{N}}(v)_{t}\right\}\right) \\ h_{u_{t}} & \leftarrow \operatorname{AGG}\left(x_{u_{t}},\{\varnothing\}\right) \end{aligned}$$

   其中$\operatorname{AGG}\left(x,\left\{y_{i}, \forall i \in \mathcal{I}\right\}\right)=\sigma\left(W \cdot \operatorname{MEAN}\left(\{x\} \cup\left\{y_{i}, \forall i \in\right.\right.\right.\mathcal{I}\})$。$x_v$和$x_{u_t}$分别是$v$节点和$u_t$的特征。本文通过邻居节点$u_t$的特征$x_{u_t}$计算他自己的embedding，因为目的是估计$u_t$的独立分布。GDPNet可以简单地拓展去聚合多阶邻居信息，使用一种增强的候选neigborhood集合，用于signal neighbor selection。对于第t步的状态$s_t=[h_v^t,h_{u_t}]$是中间点解嵌入$h_v^t$和$h_{u_t}$的拼接。最终可以得到表示$h_v$，以及状态$s_t=[h_v^t,h_{u_t}]$

4. 迭代优化：

   本文考虑迭代优化的方法去优化GDPNet，其迭代地优化了signal neighobor selection阶段和representation learning阶段去学习策略函数$\pi_{\theta}$和表示$h_v$。当用于representation learning阶段时，他聚合从$\pi_{\theta}$选择的signal neighobors中的信息去学习目标节点$v$的embedding $h_v$。然而，策略函数$\pi_{\theta}$通过使用$h_v$计算的状态和相应的rewards进行训练。在本文中，$\pi_{\theta}$使用PPO进行优化，最常用的策略梯度方法如下：

   $$\max \mathbb{E}_{s \sim \rho_{\theta_{o l d}}, a \sim q}\left[\frac{\pi_{\theta}(a \mid s)}{q(a \mid s)} Q_{\theta_{o l d}}(s, a)\right]\\ \text{s.t. }\mathbb{E}_{s \sim \rho_{\theta} \text { old }}\left[D_{K L}\left(\pi_{\theta_{o l d}}(\cdot \mid s) \| \pi_{\theta}(\cdot \mid s)\right)\right] \leq \delta$$

   其中使用KL散度惩罚用于控制每次迭代是策略的更改，以使用阈值$\delta$执行trust region中的更新。$q(a|s)$和$Q_{old}=\sum_{i=t}^{T} \gamma r_{i}$分别是策略和Q-value。这些都是在训练期间当前step保存的。$\rho_{\theta_{o l d}}$是一个discounted state分布，定义如下：

   $$\rho_{\theta_{o l d}}\left(s_{t}\right)=\sum_{t=0}^{T} \gamma^{t-1} p\left(s_{t}=s \mid \pi_{\theta_{o l d}}\right)$$