# Graph Dilated Network with Rejection Mechanism
## 5 Graph Dilated Network with Rejection Mechanism
### Rejection Mechanism  
#### 5.1.1 Method  
To address the over-smoothing problem, we propose a simple but effective Rejection Mechanism (RM). As discussed in Section 4, the over-smoothing problem is caused by averaging too much information from distant neighbors. Therefore, we introduce a learnable hop penalty parameter \(c^{(k)}\in R\) (optimized by the backpropagation) at each layer to adaptively control the messages flowing from one layer to the next layer (i.e., from one hop to the next hop). In this way, the model can reject the messages from distant nodes to address the over-smoothing problem.  
Different from GAT, which dynamically selects messages from 1-hop neighbors, the rejection mechanism is a layer-wise or hop-wise operation. Specifically, the rejection mechanism focuses on the combination function (i.e., Equation (2)) introduced in the message propagation. At the \(k\)-th layer, the hop penalty parameter \(c^{(k)}\) is applied into the integrated message representation from neighbors, and then the combination function can be rewritten as  
\[c^{(k)^{\prime}} =\textit{sigmoid}\left(c^{(k)}\right)\] \[h_{v}^{(k)} =\sigma\left(W^{(k)}\left(h_{v}^{(k-1)}\oplus c^{(k)^{\prime}} \odot m_{v}^{(k)}\right)\right) \tag{5}\]  
where \(W^{(k)}\) is a weight matrix, \(c^{(k)^{\prime}}\in[0,1]\) is the rescaled penalty parameter, and \(\odot\) refers that each element of the vector \(m^{(k)}\) multiplies the rescaled hop penalty parameter \(c^{(k)^{\prime}}\). Intuitively, the value of \(c^{(k)^{\prime}}\) can be regarded as a gate to influence the message propagation from neighbors to the center node. \(\oplus\) is an element-wise addition operation.  
To fully understand the proposed rejection mechanism, we provide an example (shown in Figure 3) to illustrate how it works to address the over-smoothing problem. For simplicity, a chain graph containing four nodes is taken as an example, and only considers the predecessor nodes as 1-hop neighbors. Considering a three-layer graph neural network, which adopts the mean aggregation function and the proposed combination function with RM, the propagation in the \(k\)-th layer for this chain graph can be expressed as (ignoring the weight matrix and nonlinear function in Equation (5))  
\[m_{i}^{(k)} =h_{i-1}^{(k-1)} \tag{6}\] \[h_{i}^{(k)} =h_{i}^{(k-1)}\oplus c^{(k)}m_{i}^{(k)}\] \[=h_{i}^{(k-1)}\oplus c^{(k)}h_{i-1}^{(k-1)} \tag{7}\]  
Figure 2: The architecture of Graph Dilated networks with Rejection mechanism (GraphDRej).  
where \(i,k\in\{1,2,3\}\), the symbol \(\odot\) in Equation (5) is ignored for expressing convenience, and \(c^{(k)}\) refers to the rescaled parameter \(c^{(k)^{\prime}}\).  
Then, the node 3's representation obtained from the last layer, can be represented as  
\[h_{3}^{(3)}= h_{3}^{(0)}\oplus(c^{(1)}+c^{(2)}+c^{(3)})h_{2}^{(0)}\] \[\oplus(c^{(1)}c^{(2)}+c^{(1)}c^{(3)}+c^{(2)}c^{(3)})h_{1}^{(0)}\] \[\oplus c^{(1)}c^{(2)}c^{(3)}h_{0}^{(0)}. \tag{8}\]  
It reveals that the influence from the distant node 0 to the representation of node 3 is punished by \(\prod_{k=1}^{3}c^{(k)}\). Due to \(c^{(k)}\in[0,1]\), multiple multiplications will lead to a small value, which adaptively controls the message flowing from distant nodes (e.g., node 0) to the representation node (e.g., node 3).  
Therefore, the benefits of the proposed rejection mechanism can be summarized as follows. (1) When stacking layers to build a deep GNN, the information from distant nodes will be more likely to be punished or even rejected. It is a simple but effective way to address the over-smoothing problem. (2) The information from distant nodes can also affect the node representation, which helps to capture the global structure. (3) The combination of the hop penalty parameters leads to adaptively aggregate information from different hops, which contributes to building a more powerful deep graph model.