While Graph Neural Networks (GNNs) are powerful models for learning representations on graphs, most state-of-the-art models do not have significant accuracy gain beyond two to three layers. Deep GNNs fundamentally need to address: 1). expressivity challenge due to oversmoothing, and 2). computation challenge due to neighborhood explosion. We propose a simple "deep GNN, shallow sampler" design principle to improve both the GNN accuracy and efficiency -- to generate representation of a target node, we use a deep GNN to pass messages only within a shallow, localized subgraph. A properly sampled subgraph may exclude irrelevant or even noisy nodes, and still preserve the critical neighbor features and graph structures. The deep GNN then smooths the informative local signals to enhance feature learning, rather than oversmoothing the global graph signals into just "white noise". We theoretically justify why the combination of deep GNNs with shallow samplers yields the best learning performance. We then propose various sampling algorithms and neural architecture extensions to achieve good empirical results. Experiments on five large graphs show that our models achieve significantly higher accuracy and efficiency, compared with state-of-the-art.

本研究提出了一种“深GNN，浅采样器”设计规则，通过利用深层次的GNN在一个浅层、局部的子图内传递信息，避免了在全局范围内过度平滑和邻域爆炸的问题，从而提高了GNN的准确性和效率。通过采用各种子图采样算法和神经架构扩展，研究人员在最大的公共图形数据集上取得了最先进的准确性，同时大幅减少了硬件成本。

深度图神经网络与浅层子图采样器