【GCN】《Adaptive Propagation Graph Convolutional Network》（TNNLS 2020）

《Adaptive Propagation Graph Convolutional Network》（TNNLS 2020）

Assign a stop unit to each node , The unit outputs a value to control Propagation Whether we should continue with the next jump . The output value of the stop unit during aggregation is the weight of each hop of aggregation . It can be understood that each node finds its own feeling field .

First, the characteristics of the node pass through a MLP become embedding, This is it. Propagation The starting point of the , Then start recursive Propagation：
$$\begin{array}{rl}& {\mathbf{z}}_i^0={\mathbf{z}}_i\\ & {\mathbf{z}}_i^1=\mathrm{propagate}\left(\left\{{\mathbf{z}}_j^0\mid j\in {\mathcal{N}}_i\right\}\right)\\ & {\mathbf{z}}_i^2=\mathrm{propagate}\left(\left\{{\mathbf{z}}_j^1\mid j\in {\mathcal{N}}_i\right\}\right)\\ & ......\end{array}$$
The number of propagation steps should be determined by each node itself , Therefore, a linear two classifier is attached to each node as the basis of the propagation process “ Stop unit ”. after k Output after second iteration propagation ：
$$h_i^k=\sigma \left(\mathbf{Q}{\mathbf{z}}_i^k+q\right)$$
among $Q,q$ It's a training parameter , $h_i^k$ Is the probability that the current iteration of this node should stop （0～1）. To ensure a reasonable number of propagation steps , There are two techniques ： Specify a maximum number of steps $T$; use halting values To define Propagation The boundary of the ：
$$K_i=\min \left\{k^{\prime }:\sum _{k=1}^{k^{\prime }}{h}_i^k>=1-ϵ\right\}$$
among $ϵ$ Is usually set to a small value 0.01, Ensure that it can be terminated after one transmission . For the node i Of the k iteration , When $k=K_i$ when Propagation stop it .

node i The stopping probability of each iteration is ：
$$p_i^k=\{\begin{array}{ll}{R}_i=1-{\sum }_{k=1}^{K_i-1}{h}_i^k,& \text{ if }k=K_i\text{ or }k=T\\ {\sum }_{k=1}^{K_i}{h}_i^k,& \text{ otherwise. }\end{array}$$
Naturally, it can be used as a node to aggregate each layer embedding The weight of ：
$${\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}$$
Nodes are also defined i Of propagation cost：
$${\mathcal{S}}_i=K_i+R_i$$
Final loss There are supervision signals and penalty regularization terms ：
$$\hat{\mathcal{L}}=\mathcal{L}+\alpha \sum _{i\in \mathcal{V}}{\mathcal{S}}_i$$
This penalty item controls the spread of information on the graph “ Difficulty degree ”. Every time 5 individual step Optimize the penalty item once .

AP-GCN The learned stop step distribution . It seems intuitive ： Sparse map receptive field is generally larger , Dense graphs generally only aggregate 1～2 Step neighbors .