Graph Neural Networks Use Graphs When They Shouldn't
Predictions over graphs play a crucial role in various domains, including
social networks and medicine. Graph Neural Networks (GNNs) have emerged as the
dominant approach for learning on graph data. Although a graph-structure is
provided as input to the GNN, in some cases the best solution can be obtained
by ignoring it. While GNNs have the ability to ignore the graph- structure in
such cases, it is not clear that they will. In this work, we show that GNNs
actually tend to overfit the given graph-structure. Namely, they use it even
when a better solution can be obtained by ignoring it. We analyze the implicit
bias of gradient-descent learning of GNNs and prove that when the ground truth
function does not use the graphs, GNNs are not guaranteed to learn a solution
that ignores the graph, even with infinite data. We examine this phenomenon
with respect to different graph distributions and find that regular graphs are
more robust to this over-fitting. We also prove that within the family of
regular graphs, GNNs are guaranteed to extrapolate when learning with gradient
descent. Finally, based on our empirical and theoretical findings, we
demonstrate on real-data how regular graphs can be leveraged to reduce graph
overfitting and enhance performance.
Maya Bechler-Speicher, Ido Amos, Ran Gilad-Bachrach, Amir Globerson
# Graph Neural Networks Use Graphs When They Shouldn't

###### Abstract

Predictions over graphs play a crucial role in various domains, including social networks, molecular biology, medicine, and more. Graph Neural Networks (GNNs) have emerged as the dominant approach for learning on graph data. Instances of graph labeling problems consist of the graph-structure (i.e., the adjacency matrix), along with node-specific feature vectors. In some cases, this graph-structure is non-informative for the predictive task. For instance, molecular properties such as molar mass depend solely on the constituent atoms (node features), and not on the molecular structure. While GNNs have the ability to ignore the graph-structure in such cases, it is not clear that they will. In this work, we show that GNNs actually tend to overfit the graph-structure in the sense that they use it even when a better solution can be obtained by ignoring it. We examine this phenomenon with respect to different graph distributions and find that regular graphs are more robust to this overfitting. We then provide a theoretical explanation for this phenomenon, via analyzing the implicit bias of gradient-descent-based learning of GNNs in this setting. Finally, based on our empirical and theoretical findings, we propose a graph-editing method to mitigate the tendency of GNNs to overfit graph-structures that should be ignored. We show that this method indeed improves the accuracy of GNNs across multiple benchmarks.

## 1 Introduction

Graph labeling problems arise in many domains, from social networks to molecular biology. In these settings, the goal is to label a graph or its nodes given information about the graph. The information for each graph instance is typically provided in the form of the graph-structure (i.e., its adjacency matrix) as well as the features of its nodes.

Graph Neural Networks (GNNs) [16, 13, 14] have emerged as the leading approach for such tasks. The fundamental idea behind GNNs is to use neural-networks that combine the node features with the graph-structure, in order to obtain useful graph representations. This combination is done in an iterative manner, which can capture complex properties of the graph and its node features.

Although the graph-structures are provided as input to the GNN, in some cases the best solution can be obtained by ignoring them. This may be due to these graph-structures being non-informative for the predictive task at hand. For instance, some molecular properties such as the molar mass (i.e., weight) depend solely on the constituent atoms (node features), and not on the molecular structure. Also, in cases where the provided graph-structure contains valuable information for the task, the GNN might struggle to effectively exploit this information. In such cases, it is anticipated that better accuracy can be achieved by ignoring the graph-structure.

Motivated by this observation, we ask a core question in GNNs learning: will GNNs work well in cases where the graph-structure should be ignored or will they overfit the graph, resulting in reduced accuracy? Answering this question has several far-reaching practical implications. To illustrate, if GNNs lack the ability to discern when to disregard the graph, then providing a graph can actually hurt the performance of GNNs, and thus one must carefully re-think which graphs to provide a GNN. On the other hand, if GNNs easily reject the structure when it fails to exploit it, then practitioners should add it even if their domain knowledge and expertise suggest that there is only a small chance that it is informative.

We consider the common setting of over-parameterized GNNs. Namely, when the number of parameters the GNN uses is larger than the size of the training data. This is a very common case in deep-learning [15, 16, 17, 18], where the learned model can fit any training data. Previous studies showed that despite over-parameterization, models learned using gradient descent often generalize well. Hence, it was suggested that the learning algorithm uses an implicit bias (e.g., low parameter norm) to avoid spurious models that happen to fit the training data.

Our focus is thus on the implicit bias of GNN learning and specifically, whether GNNs are biased towards using or not using the graph-structure. If the implicit bias is towards "simple models" that do not use the graph-structure when possible, then one would expect GNNs to be oblivious to the graph-structure when it is not informative. Our first empirical finding is that this is actually not the case. Namely, GNNs tend to _not_ ignore the graph, and their performance is highly dependent on the provided graph structure. Specifically, there are graph structures that result in models with low accuracy.

Next, we ask which properties of the learned graph distribution affect the GNN's ability to ignore the graph. We
empirically show that graphs that are regular result in more resilient GNNs. We then provide a theoretical analysis that explains why GNNs are more robust when applied to non-informative regular graphs

Finally, based on our empirical and theoretical findings, we propose a method to mitigate the tendency of GNNs to overfit non-informative graph-structures. Our approach is to add synthetic edges to the input graphs, such that they resemble regular graphs. This turns out to improve accuracy on both synthetic and real problems.

**The main contributions of this work are** (1) We show that overparameterized GNNs tend to overfit graph-structures, when they should be ignored. (2) We evaluate the graph-structure overfitting phenomenon with respect to different graph distributions and find that the best performance is obtained for regular graphs. (3) We theoretically analyze the implicit bias of GNNs trained on regular graphs and show they converge to unique solutions that are more robust to graph-structure overfitting. (4) We establish an extrapolation result and assessment for GNNs trained on regular graphs, by incorporating insights from the implicit bias analysis. (5) Based on our empirical and theoretical findings, we propose a method to mitigate the tendency of GNNs to overfit the graph-structure, and show that it performs well in practice.

To the best of our knowledge, this is the first work to examine the implicit bias of learning GNNs. Indeed, understanding this bias is key to designing GNN learning methods that generalize well.

## 2 GNNs Overfit the Graph-Structure

In this section, we present an empirical evaluation showing that GNNs tend to overfit graph-structures that should be ignored, thus hurting their generalization accuracy.

### Preliminaries

A graph example is a tuple \(G=(A,X)\). \(A\) is an adjacency matrix representing the graph-structure. Each node \(i\) is assigned with a feature vector \(\mathbf{x}_{i}\in\mathbb{R}^{d}\), and all the feature vectors are stacked to a feature matrix \(X\in\mathbb{R}^{n\times d}\), where \(n\) is the number of nodes in \(G\). The set of neighbors of node \(i\) is denoted by \(N(i)\). We denote the number of samples in a dataset by \(m\). We focus on the common class of Message-Passing Neural Networks (Morris et al., 2021). In these networks, at each layer, each node updates its representation as follows:

\[h_{i}^{(k)}=\sigma\left(W_{1}^{(k)}h_{i}^{(k-1)}+W_{2}^{(k)}\sum_{j\in N(i)}h_ {j}^{(k-1)}+b^{(k)}\right) \tag{1}\]

where \(W_{1}^{(k)},W_{2}^{(k)}\in\mathbb{R}^{d_{k}\times d_{k-1}}\). The initial representation of node \(i\) is its feature vector \(h_{i}^{(0)}=\mathbf{x}_{i}\). The final node representations \(\{h_{i}^{(L)}\}_{i=1}^{n}\) obtained in the last layer, can then be used for downstream tasks such as node or graph labeling. We focus on graph labeling tasks, where a graph representation vector is obtained by summing all the node representations. This is then followed by a linear transformation matrix \(W_{3}\) that provides the final classification/regression output for regression or classification (referred to as a _readout_). For the sake of presentation, we drop the superscript in cases of one-layer GNNs. We refer to \(W_{1}^{(k)}\) as the _root-weights_ of layer \(k\) and to \(W_{2}^{(k)}\) as the _topological-weights_ of layer \(k\). A Natural way for GNNs to ignore the graph-structure is by zeroing the topological-weights \(W_{2}^{(k)}=\vec{0}\).

### Evidence for Graph Overfitting

Our goal is to examine what happens when GNNs learn over graphs that should be ignored. To that end, we conducted experiments on three datasets.

Node SumThis is a synthetic task where the label is independent of the graph-structure and relies only on the node features. Therefore the graph-structures should be ignored. In the Node Sum task, the label is generated using a one-layer linear "teacher" model. This teacher simply sums the node features, and applies a linear readout to produce a scalar. The label is then the sign of the result. The teacher readout is sampled once from \(\mathcal{N}(0,1)\) and used for all the graphs. All graphs have \(n=20\) nodes, and each node is assigned with a feature vector in \(\mathbb{R}^{128}\) sampled i.i.d from \(\mathcal{N}(0,1)\). The non-informative graph structures are drawn from the GNP graph distribution (Erdos and Renyi, 1959), where the edges are sampled i.i.d with probability \(p\) (we used \(p=0.5\)). As the teacher model only uses the node features to compute the label, the given graph-structures are non-informative for this task.

PROTEINS and ENZYMES(Morris et al., 2020) These are two tasks based on real-world molecular data, where the goal is to classify a molecule into one of two or six classes, respectively. We chose these datasets because Errica et al. (2022) reported on a thorough GNNs comparison, that the best accuracy on these datasets is achieved when the graph-structures are omitted, i.e., on empty graphs. In Errica et al. (2022), the model trained on empty graphs is not an instance of the other compared models. Therefore, one cannot immediately conclude that the other GNNs overfitted the graph-structures. For example, the superiority of the model trained on empty graphs may be due to its architecture rather than the graph information. Nevertheless, if a fixed architecture is used, better performances that are achieved when learning over empty graphs, do indicate that it was better for the GNN to ignore the graph, but it didn't. This is because with a fixed architecture, the solution learned by the

\begin{table}
\begin{tabular}{l|c|c|c} \hline \hline  & Node Sum & PROTEINS & ENZYMES \\ \hline \(GNN\) & 94.5 \(\pm\) 0.9 & 67.4 \(\pm\) 1.9 & 55.2 \(\pm\) 3.1 \\ \(GNN_{\emptyset}\) & 97.5 \(\pm\) 0.7 & 74.1 \(\pm\) 2.5 & 64.1 \(\pm\) 5.7 \\ \hline \hline \end{tabular}
\end{table}
Table 1: The accuracy of the same GNN architecture, trained on the given datasets (GNN) and on the same data where the graph-structure is omitted (\(GNN_{\emptyset}\)), i.e., on empty graphs. Because the solution of \(GNN_{\emptyset}\) is realizable by \(GNN\), and the only difference between the runs is the given graph-structures, this suggests that the decreased performance of \(GNN\) is due to graph-structure overfitting.
GNN trained on empty graphs, is always realizable by the GNN trained on any non-empty graphs. In our experiments, we use a fixed architecture.

GNN ModelFor the Node Sum task, following the teacher model, we used a 1-layer "student" GNN, using the update rule in Equation 1, with readout and ReLU activations. For the PROTEINS and ENZYMES tasks, we used 3-layers.

Protocol and ResultsOn each of the three datasets, we trained the same GNN twice: once on the given graph-structures in the data (\(GNN\)), and once when the graph-structure is replaced with an empty graph and only the node features are given for training (\(GNN_{\emptyset}\)). The hyperparameters are tuned on a separate validation test. We report test errors averaged over 10 runs with random seeds on a separate holdout test set. More information can be found in the appendix. This difference between these setups shows the effect of providing the graph-structure.

Table 1 shows the results of the experiments. In the three tasks, \(GNN_{\emptyset}\) achieves higher accuracy than \(GNN\). This suggests that \(GNN\) made use of the graph in a way that led to lower test accuracy. Therefore, we conclude that \(GNN\) overfitted the graph-structure.

### How Graph Structure Affects Overfitting

The previous section showed that in the Node Sum task, where the graph-structures are non-informative and should be ignored, the GNN overfits them instead. Here we further study how this phenomenon is affected by the specific graph-structure used. Thus, we repeat the setup of the Node Sum task but with different graph distributions.

DataWe used the Node Sum task described in Section 2.2. We created 4 different datasets from this baseline, by sampling graph-structures from different graph distributions. The set of node feature vectors remains the same across all the datasets, thus the datasets differ only in their graph-structures. The graph distributions we used are: \(r\)-regular graphs (Regular) where all the nodes have the same degree \(r\), star-graph (Star) where the only connections are between one specific node and all other nodes, the Erdos-Renyi graph distribution (GNP) [1], where the edges are sampled i.i.d with probability \(p\), and the preferential attachment model (BA) [1], where the graph is built by incrementally adding new nodes and connecting them to existing nodes with probability proportional to the degrees of the existing nodes.

ProtocolThe GNN model was as in the Node Sum task in the previous section. On each dataset, we varied the training set size and evaluated test errors on 10 runs with random seeds. We note that the GNN has a total of \(\sim\)16,000 parameters, and thus it is overparameterized and can fit the training data with perfect accuracy. More information can be found in the appendix.

ResultsFor the sake of presentation, we present the results on one instance from each distribution: Regular with \(r=10\), GNP with \(p=0.6\) and BA with \(m=3\). Additional results with more parameters are given in the appendix, and show similar trends. Recall that the datasets differ only by the edges and share the same set of nodes and features. Therefore, had the GNN ignored the graph-structures, we would expect to see similar performance for all datasets. As shown in Figure 1(a), the performance largely differs between different graph distributions, which indicates the GNN overfits the graphs rather than ignores them.

To further understand what the GNN learns in these cases, we evaluate the ratio between the norms of the topological and root weights. Results are shown in Figure 1(b). It can be seen that for all the graphs except the empty graphs, the ratio

Figure 1: (a) The learning curves of the same GNN model trained on graphs that have the same node features and only differ in their graph-structure, that is samples from different distributions. The label is computed from the node features without the use of any graph-structure. If GNNs were to ignore the non-informative graph-structure they were given, similar performance should have been observed for all graph distributions. Among the different distributions, regular graphs exhibit the best performance. (b) The norm ratio between the topological and the root weights along the same runs. Except for the empty graphs, the ratio is always greater than 1, which indicates that more norm is given to the topological weights. On the empty graphs, the topological weights are not trained and the ratio is 0 due to initialization.
is larger than 1, indicating that there is more norm on the topological weights than on the root weights. Specifically, the graph-structure is not ignored. In the case of empty graphs, the topological weights are not trained, and the ratio is 0 due to initialization. We also present the norms of the root and topological weights separately in the appendix.

Figure 1 suggests that some graph distributions are more robust to graph-structure overfitting. The GNN trained on regular graphs performs best across all training set sizes.

The good performance on regular graphs would seem to suggest that it learns to use low topological weights. However as Figure 1(b) shows actually the opposite is true. This may seem counter-intuitive, but in the next section we show how this comes about.

## 3 Analyzing Regular Distributions

In the previous section, we saw that although GNNs tend to overfit the graph-structure when it should be ignored, regular graphs create more resilient GNNs. In this section, we theoretically examine the solutions learned by linear GNNs trained on regular graphs. We begin by analyzing their implicit bias. We then prove they are guaranteed to extrapolate to any other regular graph distribution. For the sake of clarity, we state all theorems for a one-layer GNN with sum-pooling, no readout, and output dimension 1. For simplicity, we also assume no bias term in our analysis. All the proofs and extensions can be found in the appendix.

### Implicit bias of GNNs

To examine the solutions learned by GNNs trained on regular graphs, we utilize Theorem 4 from Gunasekar et al. (2018). This theorem states that homogeneous neural networks trained with GD on linearly separable data converge to the max-margin solution. Translated to our formulation of GNNs trained on \(r\)-regular graphs, we get that GD converges to the max-margin solution of the following quadratic problem:

\[\min_{\mathbf{w}_{1},\mathbf{w}_{2}} \|\mathbf{w}_{1}\|_{2}^{2}+\|\mathbf{w}_{2}\|_{2}^{2} \tag{2}\] \[s.t. y^{(l)}\big{[}\{(\mathbf{w}_{1}+r\mathbf{w}_{2})\,\cdot\,\Sigma_{i }^{n}\,\mathbf{x}_{i}^{(l)}\}\geq 1\] \[\forall(G^{(l)},\mathbf{y}^{(l)})\in S\]

This can be viewed as a max-margin problem in \(\mathbb{R}^{d}\) where the input vector is \(\sum_{i}^{n}\,\mathbf{x}_{i}^{(l)}\). Specifically, although two weight vectors \(\mathbf{w}_{1}\) and \(\mathbf{w}_{2}\) are learned, in the case of \(r\)-regular graphs the GNN only utilizes their weighted sum \(\mathbf{\tilde{w}}=\mathbf{w}_{1}+r\mathbf{w}_{2}\). In the appendix, we present the same view for GNNs trained on general graphs (i.e., not necessarily regular).

The next theorem shows that when a GNN is trained using gradient descent on regular graphs, the learned root and topological weights are aligned.

**Theorem 3.1** (Weight Alignment).: _Let \(S\) be a set of linearly separable graph examples drawn i.i.d from an \(r\)-regular graph distribution with binary labels. A GNN trained with GD that fits \(S\) perfectly converges to a solution such that \(\mathbf{w}_{2}=r\mathbf{w}_{1}\). Specifically, the root weights \(\mathbf{w}_{1}\) and topological weights \(\mathbf{w}_{2}\) are aligned._

To prove Theorem 3.1 we analyze the KKT conditions for first order stationary points of Equation 2.

### Extrapolation

We now use Theorem 3.1 to show that when learning on regular graphs from teachers that do not use the graph-structure, the GNN will extrapolate well to any other regular graph, including the empty graph. This result is in agreement with our empirical results from the previous section where learning with regular graphs indeed succeeds for teachers that do not use the graph-structure.

**Theorem 3.2** (Extrapolation).: _Let \(S\) be a set of linearly separable graph examples drawn from an \(r\)-regular distribution, with binary labels. Assume that the ground truth function \(f^{*}\) is realizable by a GNN with \(\mathbf{w}_{2}^{*}=0\). Then a GNN that fits \(S\) perfectly, will extrapolate to any \(r^{\prime}\)-regular distribution._

To prove Theorem 3.2, we substitute the topological weights in Equation 2 with the aligned weights guaranteed from Theorem 3.1. We get that the weights vector used by the GNN is \(\mathbf{w}_{1}+r^{2}\mathbf{w}_{1}\), which does not change its direction when the value of \(r\) is changed.

While Theorem 3.2 guarantees extrapolation within the family of regular distributions, we empirically observe that GNNs trained on regular graphs exhibit good extrapolation to other non-regular graph distributions as well, as shown in Table 2. The GNN trained on 5-regular graphs, generalize perfectly for GNP distribution shifts. It generalizes well to BA distribution shifts, and there is a decrease in performance when tested on star-graphs. These extrapolation performances are non-trivial, as it was previously shown in Yehudai et al. (2020) that when there is a certain discrepancy between the train and test distributions, GNNs may fail to extrapolate.

We next suggest an explanation for these results. The following lemma shows that applying a GNN trained on regular graphs to any given graph is equivalent to applying it to an \(r^{\prime}\)-regular graph plus applying it to another \(\Delta\)-graph that depends on \(r^{\prime}\), for some \(0\leq r^{\prime}\leq n-1\).

**Lemma 3.3**.: _Let \(f\) be a GNN that perfectly fits a training set of \(r\)-regular graphs. Then applying \(f\) to a graph \(G\) can be

\begin{table}
\begin{tabular}{l|c} \hline Test distribution & Accuracy \\ \hline Regular (r=10) & 100.0 \(\pm\) 0.0 \\ Regular (r=15) & 100.0 \(\pm\) 0.0 \\ \hline GNP (p=0.2) & 100.0 \(\pm\) 0.0 \\ GNP (p=0.5) & 100.0 \(\pm\) 0.0 \\ GNP (p=0.8) & 100.0 \(\pm\) 0.0 \\ \hline BA (m=3) & 98.0 \(\pm\) 1.7 \\ BA (m=15) & 94.2 \(\pm\) 0.9 \\ \hline Star Graph & 73.9 \(\pm\) 1.1 \\ \hline \end{tabular}
\end{table}
Table 2: Accuracy of a GNN trained on 5-regular graphs and tested on different distribution shifts. The GNN extrapolates perfectly to regular graph distributions, as guaranteed by Theorem 3.2. It also extrapolates well to other distributions, where the lowest performance is when tested on star graphs.
written as_

\[f(G)=\underbrace{W_{1}\sum_{i=1}^{n}\mathbf{x}_{i}+rW_{1}\sum_{i=1}^{n}r^{\prime }\mathbf{x}_{i}}_{Regular\ Component}+\underbrace{rW_{1}\sum_{i=1}^{n}\Delta_{r^{ \prime}}(i)\mathbf{x}_{i}}_{\Delta\ Component}\]

_Such that \(\Delta_{r^{\prime}}(i)=deg_{G}(i)-r^{\prime}\), for any \(0\leq r^{\prime}\leq n-1\)_

From Lemma 3.3 it follows that if there is \(0\leq r^{\prime}\leq n-1\) such that the \(\Delta\)-component is small with respect to the regular component, then a good extrapolation follows from Theorem 3.2. In the appendix we empirically show, that indeed when the extrapolation is good, there is such \(r^{\prime}\). This suggests that applying the GNN to graphs that are "closer" to regular graphs, exhibits better extrapolation. Due to space limitations, this is fully formulated and explained in the appendix. Inspired by these observations, in the next section we present a method to mitigate the tendency of GNNs to overfit the graph-structure when it should be ignored.

## 4 A Method for Reducing Graph Overfitting

In the previous sections, we observed that GNNs tend to overfit the graph-structure even if it should be ignored. One simple practical approach to mitigate this issue is to always try learning a model with an empty graph. This would be equivalent to using a DeepSet model [22]. However, there are cases where the given graph-structure still carries some degree of pertinent information, but the GNN fails to exploit it. In such cases, entirely discarding the graph-structure may result in improved performance, but this performance could potentially be improved if the GNN would manage to exploit the given graph information. Consequently, we suggest a graph-editing method that improves the ability of GNN to exploit the given graph-structures in cases they to carry useful information while reducing overfitting to irrelevant structural information. We show that our method consistently improves performance over the originally given graphs in both synthetic and real-world data.

The R-COV Graph Editing MethodThe previous sections showed that regular graphs exhibit robustness to the tendency of GNNs to overfit graph-structures which should be ignored. Therefore, it may be beneficial to edit a given graph to be regular. We suggest a method that preserves the original graph-structures while improving the ability of the GNN to exploit them in the case they are useful for the task and disregard them when they aren't. Unfortunately, it is not clear how to turn a given graph into a regular graph without removing edges. On the other hand, it is possible to make the graphs regular by completing them into full graphs. However, this approach may be computationally expensive or even infeasible when learning on large graphs.

Our method, Reduced COV (R-COV) makes the given graphs "more similar" to regular graphs, by reducing their coefficient of variation (COV), i.e., the ratio between the standard-deviation and mean of the node degrees. The COV of regular graphs is 0. Different techniques can be used to reduce the COV of a given graph. In our experiments, we reduce the COV up to a certain threshold by adding edges sampled randomly between nodes of low degree. We iteratively add to each graph a sampled batch of non-existing edges that have at least one end-point in the 10 lowest-degree nodes, until the threshold is exceeded. For efficiency, we used batches of size 3 for small graphs (up to 100 nodes) and batches of size 50 for large graphs (more than 100 nodes). Of course, we do not want to remove the information about the original graph. Thus, we add features to edges that specify if they were part of the original graph or were added by R-COV.

Implementation DetailsThe GNN's update rule was revised to incorporate edge-features, as follows. Let \(e_{ij}\) denote the edge-features on edge \(ij\). Then the GNN update is given by:

\[h_{i}^{(k)}=\sigma\left(W_{1}^{(k)}h_{i}^{(k-1)}+W_{2}^{(k)}\sum_{j\in N(i)} \left(h_{j}^{(k-1)}+\phi(e_{ij})\right)\right) \tag{3}\]

Here \(\phi\) is an MLP with ReLU activations. We used edge feature values 1 and 0.5 for the original and added edges by R-COV, respectively. For the R-COV method, we treated the threshold as a hyper-parameter, and we tested the values \(\{0.15,0.1,0.05\}\). We did not use lower values in order to avoid graphs that are too dense.

### Experiments on Synthetic Data

We evaluated R-COV1 on four synthetic tasks: One task where any graph-structure is non-informative (Node Sum), two tasks where the graph-structure is informative and the label relies fully on the graph-structure (Edges, Motifs), and a task where the label can be computed using either the graph-structure or the node features (Mixed Information), i.e., the graph-structure is informative but also can be ignored. In all these datasets, each node has a constant 1 feature and 16 random features drawn i.i.d from \(\mathcal{N}(0,1)\).

Footnote 1: Code can be found in github.com/mayabechlerspeicher/Graph_Neural_Networks_Overfit_Graphs

Node SumThis is the same task described in Section 2.2. The label is only dependent on the node features. We used graphs over 20 nodes drawn randomly from a GNP(\(p=0.5\)) distribution.

EdgesIn this task, the goal is to determine if the number of edges is above a certain threshold. We use the same graphs from the Node Sum task. The label of the graph is 1 if it has at least 190 edges (the average amount of edges in the dataset) and 0 otherwise. In this task, the label relies fully on the graph-structure. Therefore, the graph-structures are informative in the sense that they hold valuable information for the predictive task.

MotifsWe used the synthetic motif dataset from Luo et al. (2020). In this dataset, each graph is a random Barabasi-Albert graph over 20 vertices. Half of the graphs are connected to a 5-node house structured graph, and the rest are connected with a 5-node cycle graph. The task is a binary classification of the graph according to the type of structure connected to it. In this task, the graph-structure is informative and the label relies fully on the graph-structure.
Mixed InformationHere the task is again to determine if the number of edges is above a certain threshold, as in Edges. This data is designed to allow the GNN to compute the label either from the node features or the graph-structure. We used the same dataset from Edges, with additional node features that indicate for each node to which nodes in the graph it is connected (using a fixed node ordering). Therefore, the number of edges in the graph can be realized from the node features, and so does the graph label. We then created another dataset that shares the same extended node features, but the graph-structures are replaced with non-informative graphs that should be ignored. We then wish to see the performance of R-COV when applied to the dataset with non-informative graphs, with respect to the dataset with the informative graphs. More details about the node features and the non-informative graph generation can be found in the appendix.

ProtocolWe evaluate the model in Equation 3 on empty graphs (Empty Graphs), on the original graphs in the dataset (Original Graphs), and on the original graphs with R-COV (Original Graph + R-COV). For each task, we sample the training, validation, and test data from the same distribution. For the Node Sum and Edges, we used a one-layer student GNN with readout, 64 hidden channels, and Relu activations, following the teacher GNN. For the Motifs dataset, two GNN layers were used (because one layer did not fit the training data well). In the Mixed Information task, following our findings in Section 2.2, we expect the GNN to overfit the non-informative graphs. Therefore, we wish to see to what extent R-COV applied to the non-informative graphs is able to improve the performance, with respect to the case where the informative structures, on which the label is computed, are given as the graphs. To allow a more refined analysis, we evaluated this task on varying training set sizes. All models were tuned on a validation set and tested 10 times with random seeds using the best configuration found on the validation set. More details about the training and the hyper-parameters can be found in the appendix.

ResultsThe results of Node Sum, Edge and Motif are presented in Table 3. Across all tasks, R-COV significantly improves over the original graphs. The results of the Node Sum task are particularly interesting. The label is only dependent on the node features, yet with R-COV the GNN manages to significantly improve performance over empty graphs. This suggests that the GNN exploits the graph structure although it is not informative. One way in which this can happen is that the graph is used for more efficiently pooling information across the node, or implementing other non-linearities that are invariant to node permutation. Notice that for the Edge and Motif task, the task is not realizable when the graphs are empty, which explains the low performance in this case.

Figure 2 shows the learning curves of each dataset in the Mixed Information task. The GNNs trained on the informative graph-structures and the empty graph-structures, perform similarly. As expected, due to GNNs overfitting the graph-structures, when non-informative graph-structures are given, the performance decrease, and does not recover even with \(10k\) samples. When R-COV is applied to the non-informative graph-structures, the performance significantly improves when at least 100 training examples are used. When \(3k\) examples are given, R-COV matches the performance to the case where the informative graphs are given.

### Experiments on Real-World Data

Next, we further evaluate R-COV on the real-world datasets used in Errica et al. (2022). All these datasets are publicly available and are frequently used in the GNNs literature.

**PROTEINS, ENZYMES, NCI & DD**(Shervashidze et al., 2011) are datasets of chemical compounds. In each dataset, the goal is to classify the compounds according to some property of interest.

**IMDB-B, IMDB-M, COLLAB, REDDIT-B, REDDIT-5k**(Yanardag and Vishwanathan, 2015) are social network datasets. Following Errica et al. (2022), we added a feature of the node degrees for all the social network datasets. More information on the datasets can be found in the appendix.

EvaluationWe used the protocol and implementation of Errica et al. (2022) who performed a thorough comparison of different GNNs, including GNNs trained on empty graphs. We evaluated the same model in Equation 3 twice: once on the original graphs in the datasets, and once with R-COV applied to the original graphs. The final reported result is the average of 30 runs (10-folds and 3 random seeds). We

\begin{table}
\begin{tabular}{c|c|c|c} \hline \hline  & Nodes Sum & Edges & Motifs \\ \hline Empty Graphs & 97.5 \(\pm\) 0.7 & 50.7 \(\pm\) 1.1 & 50.1 \(\pm\) 0.9 \\ Original Graphs & 94.5 \(\pm\) 0.9 & 89.9 \(\pm\) 0.7 & 85.0 \(\pm\) 0.6 \\ \hline Original Graphs & \multirow{2}{*}{98.9 \(\pm\) 0.9} & \multirow{2}{*}{100.0 \(\pm\) 0.0} & \multirow{2}{*}{95.0 \(\pm\) 0.9} \\ \cline{1-1} \cline{5-5}
also included the accuracy of the best model from Errica et al. (2022) among the 5 models they compared. Additionally, we included the accuracy reported on empty graphs from Errica et al. (2022). When the information is available, we also included the best accuracy reported in Alon and Yahav (2021), where the best models from Errica et al. (2022) were trained on the given graphs, with the last layer applied a full graph (FA), to allow long-distance information flow. Additional training details including the hyper-parameters grid are provided in the appendix.

ResultsAcross all datasets, R-COV significantly improves over the original graphs. Particularly intriguing outcomes are obtained in the PROTEINS and IMDB-M datasets. Within these two datasets, superior performance is attained when learning over empty graphs in comparison to the provided graphs. Nonetheless, R-COV improves performance also with respect to the empty graphs. This observation suggests that the structural information inherent in the data is indeed informative, yet not fully optimal, as evidenced by the GNN's limited capacity to exploit it.

## 5 Discussion and Practical Implications

In practice, the graph layout is typically determined based on a prior understanding of the task at hand, and it is common to asses multiple layouts. In some cases, a natural graph-structure inherently exists within the data, such as in social networks, where the network connections naturally define the graph layout. Nevertheless, it is usually not clear in advance if these graph layouts are informative for the task. Given that certain layouts could provide valuable information for the task while others might not, and this distinction isn't always clear beforehand, this aspect drove our research. Indeed we found that the definition of the graph-structure, typically determined by users, emerges as a pivotal factor in performance outcomes due to the tendency of GNNs to overfit the provided graphs. This revelation opens up a fascinating avenue for further research into the significance of topological information during the training of GNNs. Understanding how GNNs respond to different structural layouts and why certain graph-structures are more effective than others could potentially revolutionize the way we design and train these models.

## 6 Conclusion

In this study, we showed that although GNNs possess the capability to disregard the provided graph-structures when needed, they don't. Instead, GNNs tend to overfit the graph-structures, which results in reduced performance. We found that among different graph distributions, regular graphs are more robust to this overfitting. We analyzed the implicit bias of gradient-descent learning of GNNs, as well as their extrapolation abilities, in this setting. Our study shows that in some cases, the graph structure hurts the performance of GNNs, and therefore graph selection is of great importance, as well as having a model that knows when to ignore the graph. Motivated by our empirical and theoretical findings, we suggested R-COV, a graph-editing method that reduces the graph-structure overfitting. We demonstrated on synthetic and real datasets, that R-COV consistently enhances performance. Taken together, our results demonstrate the dramatic effect of the input graph-structure on the performance of GNNs. In future work it will be interesting to obtain a more detailed analysis of the inductive bias of GNNs, for example in cases where both graph structure and node features are informative.

## 7 Acknowledgements

This work was supported by a grant from the Tel Aviv University Center for AI and Data Science (TAD) and by the Israeli Science Foundation research grant 1186/18.

\begin{table}
\begin{tabular}{l|c|c|c|c} \hline  & IMDB-B & IMDB-M & COLLAB & REDDIT-B & REDDIT-5K \\ \hline Empty Graphs† & 60.7 ± 2.5 & 49.1 ± 3.5 & 70.2 ± 1.5 & 82.2 ± 3.0 & 52.2 ± 1.5 \\ Original Graphs† & 71.2 ± 3.9 & 48.5 ± 3.3 & **75.6 ± 2.3** & 89.9 ± 1.9 & **56.1 ± 1.7** \\ \hline Original Graphs� & 68.2 ± 2.1 & 47.7 ± 0.9 & 73.5 ± 1.9 & 83.9 ± 1.5 & 50.0 ± 2.1 \\ Original Graphs� + R-COV & **74.1 ± 3.3** & **50.1 ± 3.5** & 74.7 ± 1.9 & **90.2 ± 2.1** & 52.5 ± 2.0 \\ \hline \end{tabular}
\end{table}
Table 4: Accuracy on real-world tasks. On a fixed architecture using Equation 3, R-COV significantly improves performance across all datasets. § - Equation 3, † - Previously reported in Errica et al. (2022), ‡ - Previously reported in Alon and Yahav (2021).