We aim to deepen the theoretical understanding of Graph Neural Networks
(GNNs) on large graphs, with a focus on their expressive power. Existing
analyses relate this notion to the graph isomorphism problem, which is mostly
relevant for graphs of small sizes, or studied graph classification or
regression tasks, while prediction tasks on nodes are far more relevant on
large graphs. Recently, several works showed that, on very general random
graphs models, GNNs converge to certains functions as the number of nodes
grows. In this paper, we provide a more complete and intuitive description of
the function space generated by equivariant GNNs for node-tasks, through
general notions of convergence that encompass several previous examples. We
emphasize the role of input node features, and study the impact of node
Positional Encodings (PEs), a recent line of work that has been shown to yield
state-of-the-art results in practice. Through the study of several examples of
PEs on large random graphs, we extend previously known universality results to
significantly more general models. Our theoretical results hint at some
normalization tricks, which is shown numerically to have a positive impact on
GNN generalization on synthetic and real data. Our proofs contain new
concentration inequalities of independent interest.

本文旨在加深对大型图上图神经网络（GNNs）的理论理解，特别是着重于它们的表达能力。通过对等变 GNNs 生成的函数空间进行更完整和直观的描述，我们强调了输入节点特征的作用，并研究了节点位置编码（PEs）的影响，这是最近一项在实践中表现出卓越成果的研究。通过对大型随机图的 PEs 的研究，我们将先前已知的普适性结果扩展到了更为普遍的模型，同时提出了一些规范化技巧，这在合成和实际数据上得到了正面的验证。

图神经网络能在随机图上计算哪些函数？位置编码的作用

What functions can Graph Neural Networks compute on random graphs? The  role of Positional Encoding

While machine learning approaches to image restoration offer great promise,
current methods risk training models fixated on performing well only for image
corruption of a particular level of difficulty---such as a certain level of
noise or blur. First, we examine the weakness of conventional "fixated" models
and demonstrate that training general models to handle arbitrary levels of
corruption is indeed non-trivial. Then, we propose an on-demand learning
algorithm for training image restoration models with deep convolutional neural
networks. The main idea is to exploit a feedback mechanism to self-generate
training instances where they are needed most, thereby learning models that can
generalize across difficulty levels. On four restoration tasks---image
inpainting, pixel interpolation, image deblurring, and image denoising---and
three diverse datasets, our approach consistently outperforms both the status
quo training procedure and curriculum learning alternatives.

本文提出一种基于反馈机制的面向难度级别泛化的深度卷积神经网络图像修复模型自动生成的算法，旨在避免 “固定” 模型对于固定难度级别的训练。实验表明，在四个图像修复任务上，本算法均优于传统训练和课程学习替代方案。