# Graph Dilated Network with Rejection Mechanism
## 1 Introduction  
Graph structure data is ubiquitous in the real world, such as social networks [1; 2; 3; 4; 5], citation networks [6; 7; 8], wireless sensor networks [9], and graph-based molecules [10; 11]. Recently, graph neural networks (GNNs) have aroused a surge of research interest. The goal of GNNs is to learn representation vectors of nodes in a graph, and then the learned vectors can be used in many graph-based applications, such as link prediction and node classification [12; 13; 14; 15; 16]. The general idea of GNNs is \"message propagation\", i.e., each node iteratively passes, transforms, and aggregates messages (i.e., features) from its neighbors. Then, after \(k\) iterations, each node can capture the information of its neighbor nodes within \(k\)-hops.  
There are many works in developing graph neural networks. GCN [17] simplifies the localized spectral filters used in [18] by weighted propagating information. GraphSAGE [6] proposes several types of aggregation strategies to propagate messages from neighbors effectively. GAT [10] adopts a self-attention [19] to dynamically propagate messages.  
However, the majority of these models suffer from the \"over-smoothing\" problem [20; 21]. Specifically, message propagation is proved to be a type of Laplacian smoothing. Stacking too many layers (i.e., repeatedly applying Laplacian smoothing many times) may lead to the representations of nodes indistinguishable and hurt the performance of GNNs [20]. Furthermore, a random walk view to message propagation shows GNNs converge to a random walk distribution [21], leading to similar conclusions with the \"over-smoothing\" problem.  
As a matter of fact, many GNNs are shallow neural networks with only two or three layers. Thus, limited neighborhood information is captured. Moreover, adding additional layers cannot always improve the performance of GNNs, and may even have an opposite effect on GNNs [17; 20]. The above discussions reflect the inability of the current GNN models in exploring the global graph structure. Therefore, although a sufficient size of neighborhoods may help models to capture the high-level graphpatterns [12; 20; 21], most of GNNs fall into the over-smoothing problem and can only capture limited local structure of nodes.  
In this paper, we focus on dealing with the limitations of current GNNs, i.e., the need and the bottleneck both introduced by the global information. In detail, we propose a rejection mechanism, which softly rejects information from distant nodes, and allows our model to be free from the over-smoothing problem. To further capture the global graph structure, a graph dilated convolution kernel is proposed, and enlarges the size of the neighborhood at each layer.  
The main contributions of this paper are summarized as follows.  
* We propose a novel graph neural network model, i.e., Graph Dilated networks with Rejection mechanism (GraphDRej), to learn expressive node representations.
* We design a rejection mechanism, which is a simple but effective strategy to address the over-smoothing problem.
* We present multiple graph dilated convolution kernels to explore a sufficient size of neighborhoods in message propagation.
* Extensive experimental results show that the proposed model achieves state-of-the-art results. Also, the effectiveness of both the rejection mechanism and the graph dilated convolution kernel used in GraphDRej is demonstrated.  
The remainder of this paper is organized as follows. Section 2 reviews the related work. Section 3 presents the preliminaries. Section 4 analyzes the limitation of existing GNNs. Section 5 proposes GraphDRej model, i.e., Graph Dilated Network with Rejection Mechanism. Section 6 reports the experiments. Section 7 concludes the paper.