NEURAL EXECUTION OF GRAPH ALGORITHMS
Petar Velickovic, etc.
2 Problem Setup
2.1 Graph Algorithms
node level input $$x_i$$, node level output $$y_i$$
2.2 Learning to Execute Graph Algorithms
encoder network: $$z_i^t = f_A(x_i^t, h_i^{t-1})$$
processor network: $$H^t=P(Z^t, E^t)$$
decoder network: $$y_i^t = g_A(z_i^t, h_i^t)$$
processor network还会再去判断是否能将一个算法终止，由termination network $$T_A$$ 来定义。$$\tau^t = \sigma(T_A(H^t, \bar H_t)), \bar H_t = \frac{1}{|V|} \sum_i h_i^t$$
$$\tau>0.5$$ 就是不终止，反之就终止。
在我们的视线中，这几个模型$$f_A,g_A,T_A$$ 都是linear projection。而主要的expressivenss都在processor network $$P$$ 上。这里我们比较了GAT和MPNN。