《Adaptive Propagation Graph Convolutional Network》（TNNLS 2020）

为每个节点赋予一个停止单元，该单元输出一个值控制Propagation是否应该继续进行下一跳。聚合时停止单元的输出值就是聚合每跳的权重。可以理解成为每个节点找到自己的感受野。

首先节点的特征先经过一个MLP变成embedding，这就是Propagation的起点，然后开始递归的Propagation：
z i 0 = z i z i 1 = propagate ⁡ ( { z j 0 ∣ j ∈ N i } ) z i 2 = propagate ⁡ ( { z j 1 ∣ j ∈ N i } ) . . . . . .

​zi0​=zi​zi1​=propagate({zj0​∣j∈Ni​})zi2​=propagate({zj1​∣j∈Ni​})......​
传播的步数应该由每个节点自身决定的，因此给每个节点附加一个线性二分类器作为传播过程的“停止单元”。经过k次迭代传播后的输出：
$$h_i^k=\sigma \left(\mathbf{Q}{\mathbf{z}}_i^k+q\right)$$
其中 $Q,q$ 是训练参数， $h_i^k$ 是该节点当前迭代应该停止的概率（0～1）。为了确保传播步数合理，有两个技巧：规定一个最大步数 $T$；用halting values的加和来定义Propagation的边界：
$$K_i=\min \left\{k^{\prime }:\sum _{k=1}^{k^{\prime }}{h}_i^k>=1-ϵ\right\}$$
其中 $ϵ$ 是通常设置为一个很小的值0.01，保证传播一次之后也可以终止。对于节点 i 的第 k 轮迭代，当$k=K_i$ 时Propagation停止。

节点 i 每一次迭代的停止概率为：
p i k = { R i = 1 − ∑ k = 1 K i − 1 h i k ,  if  k = K i  or  k = T ∑ k = 1 K i h i k ,  otherwise.  p_{i}^{k}=

pik​={Ri​=1−∑k=1Ki​−1​hik​,∑k=1Ki​​hik​,​ if k=Ki​ or k=T otherwise. ​
很自然的可以用它来作为节点聚合每层embedding的权重：
$${\hat{\mathbf{z}}}_i=\frac{1}{K_i}\sum _{k=1}^{K_i}{p}_i^k{\mathbf{z}}_i^k+\left(1-p_i^k\right){\mathbf{z}}_i^{k-1}$$
还定义了节点 i 的 propagation cost：
$${\mathcal{S}}_i=K_i+R_i$$
最终loss有监督信号和惩罚正则化项构成：
$$\hat{\mathcal{L}}=\mathcal{L}+\alpha \sum _{i\in \mathcal{V}}{\mathcal{S}}_i$$
这个惩罚项控制了信息在图上传播的“难以程度”。每5个step优化一次惩罚项。

AP-GCN学出的停止步数分布。看起来符合直觉：稀疏的图感受野一般更大，稠密的图一般只聚合1～2阶邻居。