{'fraction_non_alphanumeric': 0.03135288835677941, 'fraction_numerical': 0.011747979646812332, 'mean_word_length': 4.881326096523398, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DropMessage: Unifying Random Dropping for Graph Neural Networks

Graph Neural Networks (GNNs) are powerful tools for graph representation learning. Despite their rapid development, GNNs also face some challenges, such as over-fitting, over-smoothing, and non-robustness. Previous works indicate that these problems can be alleviated by random dropping methods, which integrate augmented data into models by randomly masking parts of the input. However, some open problems of random dropping on GNNs remain to be solved. First, it is challenging to find a universal method that are suitable for all cases considering the divergence of different datasets and models. Second, augmented data introduced to GNNs causes the incomplete coverage of parameters and unstable training process. Third, there is no theoretical analysis on the effectiveness of random dropping methods on GNNs. In this paper, we propose a novel random dropping method called DropMessage, which performs dropping operations directly on the propagated messages during the message-passing process. More importantly, we find that DropMessage provides a unified framework for most existing random dropping methods, based on which we give theoretical analysis of their effectiveness. Furthermore, we elaborate the superiority of DropMessage: it stabilizes the training process by reducing sample variance; it keeps information diversity from the perspective of information theory, enabling it become a theoretical upper bound of other methods. To evaluate our proposed method, we conduct experiments that aims for multiple tasks on five public datasets and two industrial datasets with various backbone models. The experimental results show that DropMessage has the advantages of both effectiveness and generalization, and can significantly alleviate the problems mentioned above.


Introduction
Graphs, ubiquitous in the real world, are used to present complex relationships among various objects in numerous domains such as social media (social networks), finance (trading networks), and biology (biological networks). As powerful tools for representation learning on graphs, graph neural networks (GNNs) have attracted considerable attention recently (Defferrard, Bresson, and Vandergheynst 2016;Kipf and Welling 2017;Velickovic et al. 2018;Ding, Tang, and Zhang 2018). In particular, GNNs adopt a message-passing schema (Gilmer et al. 2017), in which each node aggregates information from its neighbors in each convolutional layer, and have been widely applied in various downstream tasks such as node classification (Kipf and Welling 2017), link prediction (Kipf and Welling 2016), vertex clustering (Ramaswamy, Gedik, and Liu 2005), and recommendation systems (Ying et al. 2018).
Yet, despite their rapid development, training GNNs on large-scale graphs is facing several challenges such as overfitting, over-smoothing, and non-robustness. Indeed, compared to other data forms, gathering labels for graph data is expensive and inherently biased, which limits the generalization ability of GNNs due to over-fitting. Besides, representations of different nodes in a GNN tend to become indistinguishable as a result of aggregating information from neighbors recursively. This phenomenon of over-smoothing prevents GNNs from effectively modeling the higher-order dependencies from multi-hop neighbors (Li, Han, and Wu 2018;Xu et al. 2018;Chen et al. 2020;Zhao and Akoglu 2020;Oono andSuzuki 2020, 2019). Recursively aggregating schema makes GNNs vulnerable to the quality of input graphs (Zhu et al. 2019;Zügner, Akbarnejad, and Günnemann 2018). In other words, noisy graphs or adversarial attacks can easily influence a GNN's performance.
The aforementioned problems can be helped by random dropping methods (Hinton et al. 2012;Rong et al. 2019;Feng et al. 2020), which integrate augmented data into models by randomly masking parts of the input. These methods (Maaten et al. 2013;Matsuoka 1992;Bishop 1995;Cohen, Rosenfeld, and Kolter 2019) focus on randomly dropping or sampling existing information, and can also be considered as a data augmentation technique. Benefiting from the advantages of being unbiased, adaptive, and free of parameters, random dropping methods have greatly contributed to improving the performance of most GNNs.
However, some open questions related to random dropping methods on GNNs still exist. First, a general and critical issue of existing random dropping methods is that augmented data introduced to GNNs make parameters difficult to converge and the training process unstable. Moreover, it is challenging to find an optimal dropping method suitable to all graphs and models, because different graphs and models are equipped  Figure 1: Illustrations of DropMessage and other existing random dropping methods. Considering the messages propagated by the center node (i.e., Node 1), DropMessage allows to propagate distinct messages to different neighbor nodes, and its induced message matrix can be arbitrary. The induced message matrices of other methods obey some explicit constraints and can be regarded as special forms of DropMessage.
with their own properties and the model performance can be influenced greatly by employing various dropping strategies. Furthermore, the answer to how to choose a proper dropping rate when applying these methods is still unclear, and so far no theoretical guarantee has been provided to explain why random dropping methods can improve the performance of a GNN.
In this paper, we propose a novel random dropping method called DropMessage, which can be applied to all messagepassing GNNs. As Figure 1 suggests, existing random dropping methods perform dropping on either the node feature matrix (Hinton et al. 2012;Feng et al. 2020) or the adjacency matrix (Rong et al. 2019), while our DropMessage performs dropping operations on the propagated messages, which allows the same node to propagate different messages to its different neighbors. Besides, we unify existing dropping methods into our framework and demonstrate theoretically that conducting random dropping methods on GNNs is equivalent to introducing additional regularization terms to their loss functions, which makes the models more robust. Furthermore, we also elaborate the superiority of our DropMessage whose sample variance is much smaller and training process is more stable. From the perspective of information theory, DropMessage keeps the property of information diversity, and is theoretically regarded as an upper bound of other random dropping methods. To sum up, the contributions of this paper are as follows: • We propose a novel random dropping method, called DropMessage, for all message-passing GNNs. Existing random dropping methods on GNNs can be unified into our framework via performing masking in accordance with the certain rule on the message matrix. In other words, these methods can be regarded as one special form of DropMessage. • We theoretically demonstrate the effectiveness of the random dropping methods, filling the gap in this field. • We conduct sufficient experiments for different down-stream tasks, and the experimental results show that DropMessage can better alleviate over-fitting, oversmoothing, and non-robustness compared to other existing random dropping methods.

Related Work
To sort out the key logic of our work, we first review some related work about random dropping methods with a particular focus on GNNs.
In general, random dropping can be regarded as a form of feature-noising schema that alleviates over-fitting by artificially corrupting the training data. As a representative work, Dropout is first introduced by Hinton et al. (Hinton et al. 2012) and has been proved to be effective in many scenarios (Abu-Mostafa 1990; Burges and Schölkopf 1996;Simard et al. 1998;Rifai et al. 2011;Maaten et al. 2013). Besides, Bishop (Bishop 1995) demonstrates the equivalence of corrupted features and L 2 -type regularization. Wager et al. (Wager, Wang, and Liang 2013) show that the dropout regularizer is first-order equivalent to an L 2 regularizer that being applied after scaling the features by an estimate of the inverse diagonal Fisher information matrix.
With the rapid development of GNNs, random dropping has also been generalized to the graph field, thus leading to three most common methods: Dropout (Hinton et al. 2012), DropEdge (Rong et al. 2019) and DropNode (Feng et al. 2020). Dropout performs random dropping operation on the node feature matrix, while DropEdge and DropNode, as the name implies, respectively act on the adjacency matrix (edges) and nodes. These random dropping methods can also be regarded as special forms of data augmentation (Shorten and Khoshgoftaar 2019;Frid-Adar et al. 2018;Buslaev et al. 2020;Ding et al. 2022b;Velickovic et al. 2019b), with the advantage of not requiring parameter estimation (Papp et al. 2021;Luo et al. 2021;Chen, Ma, and Xiao 2018;Zeng et al. 2020) and easy to apply. All the methods mentioned above can be used to alleviate over-fitting and over-smoothing on GNNs. However, they can achieve effective performance only on some specific datasets and GNNs. The question of how to find an optimal dropping method that suitable for most cases still remains to be explored. Moreover, there is no theoretical explanation about the effectiveness of random dropping methods on GNNs, which adds some ambiguity to the function of these methods.

Notations and Preliminaries
Notations. Let G = (V, E) represent the graph, where V = {v 1 , . . . , v n } denotes the set of n nodes, and E ⊆ V × V is the set of edges between nodes. The node features can be denoted as a matrix X = {x 1 , . . . , x n } ∈ R n×c , where x i is the feature vector of the node v i , and c is the dimensionality of node features. The edges describe the relations between nodes and can be represented as an adjacent matrix A = {a 1 , . . . , a n } ∈ R n×n , where a i denotes the i-th row of the adjacency matrix, and A (i, j) denotes the relation between nodes v i and v j . Also, the node degrees are given by d = {d 1 , . . . , d n }, where d i computes the sum of edge weights connected to node v i . Meanwhile, the degree of the whole graph is calculated by d(G) = n i d i . When we apply message-passing GNNs on G, the message matrix can be represented as M = {m 1 , . . . , m k } ∈ R k×c , where m i is a message propagated between nodes, k is the total number of messages propagated on the graph, and c is the dimension number of the messages. Message-passing GNNs. Most of the existing GNN models adopt the message-passing framework, where each node sends messages to its neighbors and simultaneously receives messages from its neighbors. In the process of the propagation, node representations are updated based on node feature information and messages from neighbors, which can be formulated as i denotes the hidden representation of node v i in the l-th layer, and N (i) is a set of nodes adjacent to node v i ; e j,i represents the edge from node j to node i; φ (l) and γ (l) are differentiable functions; and AGG represents the aggregation operation. From the perspective of the messagepassing schema, we can gather all the propagated messages into a message matrix M ∈ R k×c . Specifically, each row of the message matrix M corresponds to a message propagated on a directed edge, which can be expressed as below: where φ denotes the mapping that generates the messages, c is the dimension number of the messages, and the row number k of the message matrix M is equal to the directed edge number in the graph.

Our Approach
In this section, we introduce our proposed DropMessage, which can be applied to all message-passing GNNs. We first describe the details of our approach, and further prove that the most common existing random dropping methods, i.e., Dropout, DropEdge and DropNode, can be unified into our framework. Based on that, we give a theoretical explanation of the effectiveness of these methods. After that, we theoretically analyze the superiority of DropMessage in terms of stabilizing the training process and keeping information diversity. Finally, we derive a theoretical upper bound to guide the selection of dropping rate δ.

DropMessage
Algorithm description. Different from existing random dropping methods, DropMessage performs directly on the message matrix M instead of the feature matrix or the adjacency matrix. More specifically, DropMessage conducts dropping on the message matrix with the dropping rate δ, which means that δ|M| elements of the message matrix will be masked in expectation. Formally, this operation can be regarded as a sampling process. For each element M i,j in the message matrix, we generate an independent mask i,j to determine whether it will be preserved or not, according to a Bernoulli distribution i,j ∼ Bernoulli(1 − δ). Then, we obtain the perturbed message matrix M by multiplying each element with its mask. Finally, we scale M with the factor of 1 1−δ to guarantee that the perturbed message matrix is equal to the original message matrix in expectation. Thus, the whole process can be expressed as . The applied GNN model then propagates information via the perturbed message matrix M instead of the original message matrix. It should be moted that DropMessage only affects on the training process. Practical implementation. In practice, we do NOT need to generate the complete message matrix explicitly, because each row in the message matrix represents a distinct directed edge in the graph, and our proposed DropMessage can be applied to every directed edge independently. This property allows DropMessage to be easily parallelized, e.g., edge-wise, node-wise, or batch-wise, and to be applied to the messagepassing backbone model without increasing time or space complexity. Unifying random dropping methods. As we have mentioned above, DropMessage differs from existing methods by directly performing on messages instead of graphs. However, in intuition, the dropping of features, edges, nodes or messages will all eventually act on the message matrix. It inspires us to explore the theoretical connection between different dropping methods. As a start, we demonstrate that Dropout, DropEdge, DropNode, and DropMessage can all be formulated as Bernoulli sampling processes in Table 1. More importantly, we find that existing random dropping methods are actually special cases of DropMessage, and thus can be expressed in a uniform framework. Lemma 1. Dropout, DropEdge, DropNode, and DropMessage perform random masking on the message matrices in accordance with certain rules.
We provide the equivalent operation on the message matrix

Method
Formula of each method below.
Dropout. Dropping the elements DropMessage. This method directly performs random masking on the message matrix M. According to above descriptions, we find DropMessage conduct finest-grained masking on the message matrix, which makes it the most flexible dropping method, and other methods can be regarded as a special form of DropMessage.
Theoretical explanation of effectiveness. Previous studies have explored and explained why random dropping works in the filed of computer vision (Wager, Wang, and Liang 2013;Wan et al. 2013). However, to the best of our knowledge, the effectiveness of random dropping on GNNs has not been studied yet. To fill this gap, based on the unified framework of existing methods, we next provide a theoretical analysis.
Theorem 1. Unbiased random dropping on GNNs methods introduce an additional regularization term into the objective functions, which makes the models more robust.
Proof. For analytical simplicity, we assume that the downstream task is a binary classification and we apply a single layer GCN (Kipf and Welling 2017) as the backbone model, which can be formulated as H = BMW, where M denotes the message matrix, W denotes the transformation matrix, B ∈ R n×k indicates which messages should be aggregated by each node and B is its normalized form. Also, we adopt sigmoid as non-linear function and present the result as Z = sigmoid(H). When we use cross-entropy as loss function, the objective function can be expressed as follows: When performing random dropping on graphs, we use the perturbed message matrix M instead of the original message matrix M. Thus, the objective function in expectation can be expressed as follows: More details of the derivation can be found in Appendix. As shown in Equation 3, random dropping methods on graphs introduce an extra regularization to the objective function. For binary classification tasks, this regularization enforces the classification probability approach to 0 or 1, thus a clearer judgment can be obtained. By reducing the variance ofh i , random dropping methods motivate the model to extract more essential high-level representations. Therefore, the robustness of the models is enhanced. It is noted that Equation 3 can be well generalized to multi-classification tasks by extending dimension of the model output. Formally, when dealing with the multi-classification task, the final objective function can be expressed as where c i is the label of node v i , and the superscript indicates which dimension of the vector is selected.

Advantages of DropMessage
We give two additional analysis to demonstrate the advantages of DropMessage on two aspects: stabilizing the training process and keeping diverse information. Reducing sample variance. All random dropping methods are challenged by the problem of unstable training process. As existing works suggest, it is caused by the random noises introduced into each training epoch. These noises then add the difficulty of parameter coverage and the unstability of training process. Generally, sample variance can be used to measure the degree of stability. According to Table 1, the input of each training epoch can be regarded as a random sample of the whole graph, and the sample variance is calculated by the average difference of every two independent samples. Compared with other random dropping methods, DropMessage effectively alleviates the aforementioned problem by reducing the sample variance. Theorem 2. DropMessage presents the smallest sample variance among existing random dropping methods on messagepassing GNNs with the same dropping rate δ.
We leave the proof in Appendix. Intuitively, DropMessage independently determines whether an element in the message matrix is masked or not, which is exactly the smallest Bernoulli trail for random dropping on the message matrix. By reducing the sample variance, DropMessage diminishes the difference of message matrices among distinct training epochs, which stabilizes the training process and expedites the convergence. The reason why DropMessage has the minimum sample variance is that it is the finest-grained random dropping method for GNN models. When applying DropMessage, each element M i,j will be independently judged that whether it should be masked. Keeping diverse information. In the following, we compare different random dropping methods with their degree of losing information diversity, from the perspective of information theory. Definition 1. The information diversity consists of feature diversity and topology diversity. We define feature diversity indicates the slice of the row numbers corresponding to the edges sourced from v i ; topology diversity is defined as TD M ∈ R k×c represents the message matrix, · 0 calculates the zero norm of the input vector, and card(·) counts the number of elements in the set.
In other words, feature diversity is defined as the total number of preserved feature dimensions from distinct source nodes; topology diversity is defined as the total number of directed edges propagating at least one dimension message. With the above definition, we claim that a method possesses the ability of keeping information diversity only under the condition where neither the feature diversity nor the topology diversity decreases after random dropping. Lemma 2. None of Dropout, DropEdge, and DropNode is able to keep information diversity.
According to Definition 1, when we drop an element of the feature matrix X, all corresponding elements in the message matrix are masked and the feature diversity is decreased by 1. When we drop an edge in adjacency matrix, the corresponding two rows for undirected graphs in the message matrix are masked and the topology diversity is decreased by 2. Similarly, when we drop a node, i.e., a row in the feature matrix, elements in the corresponding rows of the message matrix are all masked. Both the feature diversity and the topology diversity are therefore decreased. Thus, for all of these methods, their feature and topology information cannot be completely recovered by propagated messages, leading to the loss of information diversity. Theorem 3. DropMessage can keep information diversity in expectation when δ i ≤ 1 − min( 1 di , 1 c ), where δ i is the dropping rate for node v i , d i is the out-degree of v i , and c is the feature dimension.
Proof. DropMessage conducts random dropping directly on message matrix M. To keep the diversity of the topology information, we expect that at least one element of each row in message matrix M can be preserved in expectation: To keep the diversity of the feature information, we expect that for every element in the feature matrix X, at least one of its corresponding elements in the message matrix M is preserved in expectation: Therefore, to keep the information diversity, the dropping rate δ i should satisfy both Equation 4 and Equation 5 as From the perspective of information theory, a random dropping method with the capability of keeping information diversity can preserve more information and theoretically perform better than those without such capability. Thus, it can explain why our method performs better than those existing dropping methods. Actually, we may only set one dropping rate δ for the whole graph rather than for each node in practice. Consequently, both DropMessage and other methods may lose some information. However, DropMessage still preserves more information than other methods with the same dropping rate even under this circumstance. It is demonstrated that DropMessage remains its advantage in real-world scenarios.

Experimental Setup
We empirically validate the effectiveness and adaptability of our proposed DropMessage in this section. In particular, we explore the following questions: 1) Does DropMessage outperform other random dropping methods on GNNs? 2) Could DropMessage further improve the robustness and training efficiency of GNNs? 3) Does information diversity (described in Definition 1) matter in GNNs? Datasets. We employ 7 graph datasets in our experiments, including 5 public datasets Cora, CiteSeer, PubMed, ogbnarxiv, Flickr and 2 industrial datasets FinV, Telecom.
• Cora, CiteSeer, PubMed, ogbn-arxiv: These 4 different citation networks are widely used as graph benchmarks (Sen et al. 2008;Hu et al. 2020). We conduct node classification tasks on each dataset to determine the research area of papers/researchers. We also consider link prediction on the first three graphs to predict whether one paper cites another. • Flickr: It is provided by Flickr, the largest photo-sharing website (Zeng et al. 2020). One node in the graph represents one image uploaded to Flickr. If two images share some common properties (e.g., same geographic location, same gallery, or comments by the same user), an edge between the nodes of these two images will appear. We conduct the node classification task that aims to categorize these images into 7 classes determined by their tags. • FinV, Telecom: These are two real-world mobile communication networks provided by FinVolution Group (Yang et al. 2019) and China Telecom (Yang et al. 2021), respectively. In the two datasets, nodes represent users, and edges indicate the situation where two users have communicated with each other at a certain frequency. The task is to identify whether a user is a default borrower or a telecom fraudster.
Baseline methods. We compare our proposed DropMessage with other existing random dropping methods, including Backbone models. In this paper, we mainly consider three mainstream GNNs as our backbone models: GCN (Kipf and Welling 2017), GAT (Velickovic et al. 2018), and APPNP (Klicpera, Bojchevski, and Günnemann 2019). We take the official practice of these methods while make some minor modifications. All these backbone models have random dropping modules for different steps in their model implementation. For instance, GAT models perform random dropping after self-attention calculation, while APPNP models perform random dropping at the beginning of each iteration. For a fair comparison, we unify the implementation of random dropping modules in the same step for different backbone models. We fix Dropout, DropEdge, and DropNode on the initial input and fix DropMessage at the start point of the message propagation process. Table 2 summarizes the overall results. For the node classification task, the performance is measured by accuracy on four public datasets (Cora, CiteSeer, PubMed, ogbn-arxiv). As for Flickr and two imbalanced industrial datasets, we employ F1 scores. When it comes to the link prediction task, we calculate the AUC values for comparisons. Considering the space limitation, the std values of the experimental results are presented in the Appendix.

Comparison Results
Effect of random dropping methods. It is observed that random dropping methods consistently outperform GNNs without random dropping in both node classification and link prediction. Besides, we see that the effects of random dropping methods vary over different datasets, backbone models, and downstream tasks. For example, random dropping methods on APPAP obtain an average accuracy improvement of 1.4% on CiteSeer, while 0.1% on PubMed. Meanwhile, random dropping methods achieve 2.1% accuracy improvement for GCN on Cora, while only 0.8% for GAT.
Comparison of different dropping methods. Our proposed DropMessage works well in all settings, exhibiting its strong adaptability to various scenarios. Overall, we have 21 settings under the node classification task, each of which is a combination of different backbone models and datasets (e.g., GCN-Cora). It is showed that DropMessage achieves the optimal results in 15 settings, and gets sub-optimal results in the rest. As to 9 setttings under the link prediction task, DropMessage achieves the optimal results in 5 settings, and sub-optimal results in the rest. Moreover, the stable performance of DropMessage over all datasets compared to other methods is clearly presented. Taking DropEdge as the counterexample, it appears strong performance on industrial datasets but demonstrates a clear drop on public ones. A reasonable explanation is that the message matrix patterns reserved by distinct mask methods vary from each other as presented in Table 1. With the favor of its finest-grained dropping strategy, DropMessage obtains smaller inductive bias. Thus, compared with other methods, DropMessage is more applicable in most scenarios.

Additional Results
Robustness analysis. We study the robustness of dropping methods through measuring their ability of handling perturbed graphs. To guarantee that the initial data is comparatively clean, we conduct experiments on three citation networks: Cora, CiteSeer, and PubMed. We randomly add a certain ratio of edges into these datasets and perform the node classification. We find that all the random dropping methods have positive effects when the perturbation rate increases from 0% to 30%. The average improvement in the case of 30% perturbation reached 37% compared to that without perturbation, which indicates that the random dropping Over-smoothing analysis. Over-smoothing is a common issue on GNNs (Li, Han, and Wu 2018), which implies that the node representations become indistinguishable as the network depth increases. In this part, we evaluate the effects that various random dropping methods exert on this issue, and measure the degree of over-smoothing by MADGap . It should be noted that here a smaller value indicates the more indistinguishable node representations and vice versa. Experiments are conducted on Cora with GCNs serving as backbone models. Figure 2a and Figure 2b show Training process analysis. We conduct experiments to analyze the loss during the training process when employing different random dropping methods. Figure 2c shows the change of loss in GCN training processes when employing different random dropping methods on Cora. Furthermore, the similar training loss curves can be drawn under other experimental settings. The experimental results suggest that DropMessage presents the smallest sample variance among all methods, thus achieving the fastest convergence and the most stable performance. This is consistent with the theoretical results in Section 4.2.
Information diversity analysis. We conduct experiments to evaluate the importance of information diversity for messagepassing GNN models. We set Cora as our experimental dataset, which contains 2708 nodes and 5429 edges. The average node degree of Cora is close to 4. According to Equation 6, the upper bound of dropping rate is calculated from the node degree and the feature dimension. The feature dimension number of Cora is 1433, which is much larger than the number of node degree. Therefore, the upper bound is only determined by the degree of the node. In (backbone)nodewise settings, we set the dropping rate to be equal to its upper bound δ i = 1 − 1 di for each node. In (backbone)average settings, we set the dropping rate δ i = 0.75 + i , where i ∼ U nif orm(−0.15, 0.15). Both of these settings employ DropMessage. The average random dropping rate of all nodes is almost identical under these two settings, but only the former one can keep the information diversity in expectation. Table 3 presents the results. The (backbone)-nodewise settings outperform (backbone)-average settings regardless of which backbone model is selected.

Conclusion
In this paper, we propose DropMessage, a general random dropping method for message-passing GNN models. We first unify all random dropping methods to our framework via performing dropping on the message matrix and analyzing their effects. Then we illustrate the superiority of DropMessage theoretically in stabilizing the training process and keeping information diversity. Due to its fine-grained dropping operations on the message matrix, DropMessage shows greater applicability in most cases. By conducting experiments for multiple tasks on five public datasets and two industrial datasets, we demonstrate the effectiveness and generalization of our proposed method.

Derivation Details
Detailed proof of Theorem 1. Theorem 1 Unbiased random dropping methods introduce an extra regularization term into the objective functions, which make the models more robust.
We give more derivation details of Theorem 1. When we use cross-entropy as the loss function, the objective function can be expressed as follows: According to above equation, the initial objective function is L CE = j,yj =1 log(1 + e −hj ) + k,y k =0 log(1 + e h k ). When we perturb the message matrix, the objective function can be regarded as a process of adding a bias to the original function, expressed as follows: . We can approximate it with the second-order Taylor expansion of f (.) and g(.) around h i . Thus, the objective function in expectation can be expressed as bellow: Proof of Theorem 2. Theorem 2 DropMessage presents the smallest sample variance among all existing random dropping methods on messagepassing GNNs with the same dropping rate δ.
Proof. As stated in Lemma 1, all random dropping methods on graphs can be converted to masking operations on the message matrix M. We can measure the difference of message matrices in different epochs by the way of comparing the sample variance of random dropping methods, which can be measured via the norm variance of the message matrix |M| F . Without loss of generality, we assume the original message matrix M is 1 n×n , i.e., every element is 1. Thus, we can calculate its sample variance via the 1-norm of the message matrix. We consider that the message-passing GNNs do not possess the node-sampler or the edge-sampler, which means every directed edge corresponds to a row vector in the message matrix M. For analytical simplicity, we assume that the graph is undirected and the degree of each node is d. In this case, k = 2|E| = nd rows of the message matrix counts in total. All random dropping methods can be considered as multiple independent Bernoulli samplings. The whole process conforms to a binomial distribution, and so we can calculate the variance of |M|. Dropout. Perform nc times of Bernoulli sampling. Dropping an element in the feature matrix leads to masking d elements in the message matrix. Its variance can be calculated by V ar do (|M|) = (1 − δ)δncd 2 .
DropEdge. Perform nd 2 times of Bernoulli sampling. Dropping an element in the adjacency matrix leads to masking 2c elements in the message matrix. Its variance can be calculated by V ar de (|M|) = 2(1 − δ)δnc 2 d. DropNode. Perform n times of Bernoulli sampling. Dropping an element in the node set leads to masking cd elements in the message matrix. Its variance can be calculated by V ar dn (|M|) = (1 − δ)δnc 2 d 2 .
DropMessage. Perform ncd times of Bernoulli sampling. Dropping an element in the message matrix leads to masking 1 elements in the message matrix. Its variance can be calculated by V ar dm (|M|) = (1 − δ)δncd.
Therefore, the variances of the random dropping methods are sorted as follows: Our DropMessage has the smallest sample variance among all existing random dropping methods.

Experiment Details
Hardware spcification and environment. We run our experiments on the machine with Intel Xeon Gold CPUs (6240@2.6Ghz), ten NVIDIA GeForce 2080ti GPUs (11GB). The code is written in Python 3.8, Pytorch 1.8, and Pytorch-Geometric 1.7.
Dataset statistics. Table 4 shows the statistics of datasets. Implementation details. We conduct 20 independent experiments for each setting and obtain the average results. On the five public datasets, we continue to employ the same hyper-parameter settings as previous works have proposed. And on the two real-world datasets, we obtain the best parameters through careful tuning. As for public datasets Cora, CiteSeer, PubMed, and Flickr, we apply two-layer models. However, when it comes to the public dataset ogbn-arxiv and two industrial datasets, Telecom and FinV, we employ three-layer models with two batch normalization layers between the network layers. These experimental settings are identical for node classification tasks and link prediction tasks. The number of hidden units on GCNs is 16 for Cora, CiteSeer, PubMed, and is 64 for others. For GATs, we apply eight-head models with 8 hidden units for Cora, CiteSeer, PubMed, and use single-head models with 128 hidden units for the other datasets. As for APPNPs, we use the teleport probability α = 0.1 and K = 10 power iteration steps. The number of hidden units on APPNPs is always 64 for all datasets. In all cases, we use Adam optimizers with learning rate of 0.005 and L 2 regularization of 5 × 10 −4 , and train each model 200 epochs. We adjust the dropping rate from 0.05 to 0.95 in steps of 0.05 and select the optimal one for each setting. Table 5 and 6 present the optimal selections of dropping rates δ. Additional data for comparison results. For the node classification task, the performance is measured by accuracy on four public datasets (Cora, CiteSeer, PubMed, ogbn-arxiv). As for Flickr and two imbalanced industrial datasets, we employ F1 scores. When it comes to the link prediction task, we calculate the AUC values for comparisons. Table 7 present the std values of comparison results. Results of robustness analysis. We conduct experiments for robustness analysis on three citation networks: Cora, CiteSeer, and PubMed. Specifically, we randomly add a certain ratio of edges (0%, 10%, 20%, 30%) into these datasets and perform the node classification. Table 8 summarizes the classification accuracy of robustness analysis.

Related Works About Data Augmentations
In this section, we introduce some previous works about data augmentation techniques that are related to the random dropping methods discussed in our paper. GNN's effectiveness tends to be weakened due to the noise and low-resource problems in real-world graph data (Dai, Aggarwal, and Wang 2021) (Ding et al. 2022a)(Sun, Lin, and Zhu 2020). Data augmentation has attracted a lot of research interest as it is an effective tool to improve model performance in noisy settings ). However, apart from i.i.d. data, graph data, which is defined on non-Euclidean space with multi-modality, is hard to be handled by conventional data augmentation methods (Ding et al. 2022c). To address this problem, an increasing number of graph data augmentation methods have been proposed, which include feature-wise (

Additional Experiments
Results on SOTA models. We also compare the performance of different random dropping methods and our proposed DropMessage on two SOTA backbone models: DAGNN (Liu, Gao, and Ji 2020) and GCNII (Ming Chen, Zengfeng Huang, and Li 2020). We employ these two models to perform node classification tasks on five datasets. Table 9 presents the experimental results. The results indicate that DropMessage consistently outperforms other random dropping methods. Comparison to Random Augmentation Methods. Random dropping methods are similar to random augmentation techniques used in graph contrastive learning. We compare the performance of our proposed DropMessage with some widely-used augmentation techniques (Ding et al. 2022b), and their brief descriptions are listed as below.
Node Dropping: it randomly discards a certain portion of vertices along with their connections. Edge Perturbation: it perturbs the connectivities in graph through randomly adding or dropping a certain ratio of edges. Subgraph: it samples a subgraph using random walk. Table 10 summaries the experimental results on five datasets (Cora, CiteSeer, PubMed, ogbn-arxiv and Flickr) for node classification tasks. The results indicate that our proposed DropMessage consistently outperforms the random data augmentation methods. Graph Property Prediction. We perform the graph property prediction task on ogbg-molhiv and ogbg-molpcba (Hu et al. 2020). They are two molecular property prediction datasets adopted from the MoleculeNet (Wu et al. 2017). Table 11 shows the results of ROC-AUC scores with GCN as the backbone model. Graph Rewiring. We conduct experiments on graph rewiring to evaluate the robustness of random dropping methods. Specifically, we first remove a certain ratio of edges, and then randomly add an equal number of edges. We perform the experiments on three citation datasets with GCN as the backbone model. Table 12 presents the results.   where X denotes all possible values of x. Now, we measure the degree of over-smoothing of the model by calculating the Shannon entropy of the propagated messages. Intuitively, the larger the Shannon entropy, the more diverse the propagated messages are, and the less likely the aggregated representations will converge.
We assume there are k types of d-dimension messages propagated in the GNN model. For the i-th type of the propagated messages, they are delivered for t i times by n i nodes. Then, we can calculate the Shannon entropy for the initial messages: Then, we consider the Shannon entropy after random dropping with dropping rate δ. For DropEdge and DropNode, they generate blank messages at the ratio δ. So the Shannon entropy can be expressed as: From above derivations, we prove the effectiveness of random dropping methods in alleviating over-smoothing issue, and our proposed DropMessage achieves the best effect.