PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Neural Networks Use Graphs When They Shouldn't

Maya Bechler-Speicher, Ido Amos, Ran Gilad-Bachrach, Amir Globerson

arXiv:2309.04332v2cs.LGcs.AI

TL;DR

The paper asks whether GNNs can disregard graph structure when it is better to ignore it, and examines their implicit bias under gradient descent. It finds that GNNs can overfit graph structure even with infinite data, while regular graphs are more robust and offer an extrapolation guarantee; making real-world graphs more regular can improve performance.

  • Problem

    It is unclear whether GNNs ignore graph structure when it is uninformative or less useful than node features.

    Source: §1 · p. 1

  • Method

    The authors analyze GNNs’ implicit bias under gradient descent, compare graph distributions, and test graph regularization on real-world data.

    Source: §1 · p. 2

  • Results

    GNNs tend to overfit graph structure and are not guaranteed to learn a graph-ignoring solution even with infinite data, while regular graphs are more robust and guarantee extrapolation under gradient descent.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    Graph selection matters, and making input graphs more regular can mitigate overfitting and improve performance.

    Source: §1 · p. 2, §7 · p. 9

    The analysis focuses on over-parameterized GNNs, and enabling models to use useful graph information while ignoring unhelpful structure without prior knowledge remains difficult.

    Source: §1 · p. 1, §6 · p. 8

Abstract

from arXiv · show

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.

1. Introduction

The introduction asks whether GNNs can ignore graph structure when it is uninformative or less useful than node features. It reports that they tend to overfit that structure, while regular graphs offer greater robustness and can improve real-world performance when made more regular.

1. Introduction

  • When graph structure is uninformative, or a GNN cannot exploit it effectively, better test accuracy may come from ignoring it.The introduction gives molecular mass and user income predicted from zipcode as examples where node features can dominate.Source: §1 · p. 1
  • The authors focus on implicit bias because over-parameterized models can fit training data, while gradient descent may favor some solutions over others.They ask whether this bias favors using or disregarding graph structure.Source: §1 · pp. 1–2
  • GNNs tend not to ignore the graph, and their test performance can depend strongly on its structure, with some structures yielding low accuracy.The introduction frames this as graph-structure overfitting.Source: §1 · p. 2
  • With gradient descent, GNNs are not guaranteed to learn a graph-ignoring solution even with infinite data, whereas within regular graphs they are guaranteed to extrapolate, subject to a stated sufficient condition.The analysis concerns a graph-less ground truth and includes a sufficient condition for extrapolation on regular graphs.Source: §1 · p. 2
  • Regular graphs are more resilient to graph overfitting, and making real-world input graphs more regular can improve performance, including when the graph need not be ignored.The introduction also reports that transforming input graphs to be more regular can mitigate overfitting.Source: §1 · p. 2

2. GNNs Overfit the Graph-Structure

The section shows that GNNs can use graph structure even when ignoring it is preferable, and that overfitting varies with the supplied graph distribution. Regular graphs perform best in the distribution comparison.

2. GNNs Overfit the Graph-Structure

  • Graph overfitting means using graph structure when preferable to ignore it; zeroing topological weights is the stated way to make a GNN graph-less.Some GNN architectures cannot ignore structure because their root and topological weights are tied.Source: §2 · p. 2, §2.1 · p. 2

2.1. Preliminaries

  • A graph example is represented by adjacency matrix A and node-feature matrix X, while a graph-less function depends on X alone.The section focuses on message-passing neural networks for graph-labeling tasks.Source: §2.1 · p. 2

2.2. Evidence for Graph Overfitting

  • Across all three tasks, GNN∅ achieves higher accuracy than the same-architecture GNN, indicating graph use despite a better graph-ignoring solution.The comparison changes only whether the graph structure is provided; the graph-ignoring solution is realizable by the graph-input model.Source: Table 1 · p. 3, §2.2 · p. 3

2.3. How Graph-Structure Affects Overfitting

  • Performance differs across graph distributions despite shared node features, and regular-graph training performs best across all training-set sizes.The distributions vary only in graph structure.Source: Figure 1 · p. 4, §2.3 · p. 4
  • For non-empty graphs, topological-weight norm exceeds root-weight norm; empty graphs have ratio 0 because those weights are untrained.Thus, regular graphs' stronger performance does not correspond to lower topological-weight norm.Source: Figure 1 · p. 4, §2.3 · p. 4

3. Theoretical Analysis

The analysis shows that gradient-descent-trained GNNs can use graph structure even when the teacher is graph-less, so they may fail to extrapolate across graph distributions. For regular-graph training, it establishes conditions that guarantee extrapolation and relate success on modified graphs to closeness to regularity.

3. Theoretical Analysis

  • The theoretical results use a one-layer GNN with sum-pooling, no readout, output dimension 1, and no bias term.The learning analysis considers linearly separable labeled graphs and uses the gradient-descent max-margin characterization.Source: §3 · p. 4, §3.1 · p. 4

3.1. Implicit bias of Gradient Descent for GNNs

  • For r-regular training examples, gradient descent aligns the root and topological weights, with w2 = r w1.The analysis characterizes the learned solution through a max-margin problem; on regular graphs, the classifier acts on summed node features with an r-dependent regularizer.Source: §3.1 · pp. 4–5

3.2. Extrapolation with graph-less teachers

  • With a graph-less teacher, a linear GNN trained by gradient descent can have test error of at least 1/4 under a graph-distribution shift, even with infinite training data.The train and test graph distributions can differ while node features come from the same fixed distribution.Source: §3.2 · p. 5
  • Training on r-regular graphs guarantees zero test error on other regular graph distributions when training data are infinite and labeled by a graph-less teacher.The training and test regularity degrees may differ.Source: §3.2 · p. 5

3.2.1. CHARACTERIZING EXTRAPOLATION ACCURACY

  • For modified test graphs, the sufficient condition in Theorem 3.4 guarantees that the learned GNN matches the graph-less teacher; smaller degree deviations indicate greater closeness to regularity.The condition held for all correctly classified test examples examined, and the authors identify closeness to regularity as an important determinant of extrapolation accuracy.Source: §3.2.1 · p. 6

4. Are Regular Graphs Better when Graphs are Useful?

The evaluation finds that reducing graph degree variation improves generalization across datasets and models, even when empty graphs outperform the original graphs on PROTEINS and IMDB-M. It also tests whether progressively reducing variation helps on PROTEINS and describes a way to regularize graphs while retaining their original information.

4. Are Regular Graphs Better when Graphs are Useful?

  • The graph transformation adds edges between low-degree nodes to reduce COV while preserving original information by marking original and added edges with features 1 and 0.5.COV is the ratio of the standard deviation to the mean of node degrees; regular graphs have COV 0.Source: §4 · pp. 6–7

4.1. Datasets

  • The evaluation covers 11 graph datasets and compares original graphs, graphs with COV set to 80% or 50% of its original average, and empty graphs equivalent to DeepSets.The datasets vary in graph size, density, node-feature count, and number of classes.Source: §4.1 · p. 7
  • Reducing COV improves generalization across datasets and models; on PROTEINS and IMDB-M, empty graphs outperform original graphs, yet COV reduction improves performance relative to empty graphs.This suggests structural information may be informative even when the GNN does not exploit it effectively.Source: Table 3 · p. 7, §4.1 · p. 8
  • On PROTEINS, performance improves monotonically as COV is reduced; full graphs are computationally costly, so the reduction level can be limited according to available computation.Added edges are distinguished from original edges, allowing the network to ignore them.Source: §4.1 · p. 8, Figure 3 · p. 8

5. Practical Implications

Users often choose graph layouts without knowing whether they are informative or whether a GNN can exploit them. Because graph-structure choices can affect performance, the authors identify topology’s role in GNN training as an avenue for further study.

5. Practical Implications

  • Because users often cannot tell whether a graph layout is informative or exploitable in advance, graph choice is pivotal to performance and motivates studying how topology affects GNNs.The authors connect this concern to settings where graph structures are selected from domain knowledge or explored among alternatives.Source: §5 · p. 8

6. Future Work

The authors recommend comparing against empty-graph learning and suggest regularizing topological weights when graphs are known to contribute little. They identify selective use of useful graph information without prior knowledge, and analysis of nonlinear GNNs, as future challenges.

6. Future Work

  • When graph contribution is expected to be small, the authors recommend trying empty graphs and suggest regularizing topological weights.Empty-graph learning corresponds to DeepSets.Source: §6 · p. 8
  • A central open challenge is improving a GNN’s ability to exploit useful graph information and ignore it otherwise without prior knowledge.The authors also propose studying whether existing GNN mitigation methods help with graph overfitting.Source: §6 · p. 8
  • Future analysis could examine implicit bias in nonlinear GNNs, including Graph Attention and Transformers.Source: §6 · p. 8

7. Conclusion

The paper concludes that GNNs tend to overfit graph structure, even when it should be ignored, and that regular graphs are more robust. It emphasizes graph selection and the ability to ignore structure when needed.

7. Conclusion

  • GNNs tend to overfit graph structure, and even with infinite data gradient-descent learning is not guaranteed to ignore it when the ground truth does.The paper reports regular-graph robustness, a theoretical explanation, and extrapolation results for that setting.Source: §7 · p. 8
  • Graph selection matters because structure can hurt GNN performance, making the ability to ignore it important.Source: §7 · pp. 8–9

A. Proofs and Extensions

  • The analysis assumes training and test labels come from a graph-less teacher that classifies instances using features, not graph structure.Source: A. Proofs and Extensions · p. 11

A.1. Proof of Lemma 3.1

The proof uses regularity to relate root and topological weights, then extends the alignment result to readouts and multiple layers.

A.1. Proof of Lemma 3.1

  • With readout, the proof establishes alignment between W1 and W2, and between W3W1 and W3W2.The readout is applied after sum-pooling.Source: §A.1 · pp. 11–12
  • For the one-layer GNN without readout, the root and topological weights are aligned in every layer.The proof begins with this simplest case before extending to readout and multiple layers.Source: §A.1 · pp. 11, 13

L Layers - Overview

  • For L layers, the proof sketches the max-margin and stationarity argument used to establish root–topological weight alignment.The max-margin problem changes through P(W), and the overview identifies alignment in layer k as the goal.Source: L Layers - Overview · p. 13

A.2. Proof of Theorem 3.2

The proof shows that training on regular graphs need not extrapolate to star graphs, even when the labels come from a graph-less function. It attributes the failure to the star’s central node dominating the prediction.

A.2. Proof of Theorem 3.2

  • Training on r-regular graphs leads the learned predictor to average over nodes, whereas a star’s center node typically determines its label.The proof assumes one-dimensional Gaussian node features and a graph-less teacher defined by a sum over features.Source: §A.2 · p. 14
  • As the star’s size grows, the prediction is determined by its central node, producing a nonzero error against the graph-less target.The proof analyzes the correlation of the star-based prediction with the target and concludes the error exceeds 0.25.Source: §A.2 · p. 14
  • A model trained on r-regular graphs fails to extrapolate to star graphs, with error greater than 0.25.The proof considers a graph-less teacher and takes graph size to infinity; it notes finite-graph results hold with high probability by concentration.Source: §A.2 · pp. 14–15

A.3. Proof of Theorem 3.3

The appendix proves perfect extrapolation between regular-graph distributions under a shared feature distribution, and presents supporting analyses of perturbations, learned weights, other models, and a node task.

A.3. Proof of Theorem 3.3

  • Training on r-regular graphs yields perfect extrapolation to r′-regular graphs when the feature distribution is shared.The proof establishes agreement with the graph-less teacher on the training distribution and correctness on test instances.Source: §A.3 · p. 15

A.4. Proof of Theorem 3.4

  • The perturbation proof identifies a degree-deviation component that can be dropped when it is small relative to the regular component and does not change the sign.The setup modifies an example’s graph and defines degree deviations relative to r′.Source: §A.4 · pp. 15–16

B.1. Empirical Validation of Lemma 3.1

  • During training on regular graphs, the ratio of topological to root weights converges to the regularity degree across the reported one- and two-layer models with readout.Figure 4 plots the ratio for different regularity degrees; V is graph size and r is regularity degree.Source: §B.1 · p. 16, Figure 4 · p. 16

B.2. Evidences For Graph Overfitting With Additional Models (Section 2.2)

  • GIN, GAT, Graph Transformer, and GraphConv show trends similar to those reported for the main-paper model in the graph-overfitting evaluation.The appendix reports the additional model evaluations on the Sum task.Source: §B.2 · p. 16

B.3. Evidence For Graph Overfitting With Node Task (Section 2.2)

  • In the graph-classification teacher–student task, different input graphs affect generalization although the teacher does not use the graph.The training graph has over 4,000 nodes, while validation and test graphs have over 500 nodes; node features are 128-dimensional Gaussian samples.Source: §B.3 · p. 16

B.4. Additional Results on How Graph Structure Affects Overfitting (Section 2.3)

The appendix adds broader learning-curve results across graph distributions and parameters, along with separate root and topological weight norms.

B.4. Additional Results on How Graph Structure Affects Overfitting (Section 2.3)

  • Figure 10 presents learning curves for all tested graph distributions and multiple parameters, extending the selected curves shown in the main paper.Figure 11 separately presents root and topological weight norms for curves shown in the main paper.Source: §B.4 · p. 16
  • Figure 5 evaluates GIN on the Sum task, where the graph should be ignored.The figure caption identifies the task context but does not state an outcome.Source: Figure 5 · p. 17
  • Figure 6 evaluates GAT on the Sum task, where the graph should be ignored.The supplied figure passage identifies the model and task but does not state an outcome.Source: Figure 6 · p. 17

C.1. Additional Implementation Details For Section 2.2

The appendix details synthetic-task setups, the real-world datasets, and model and training configurations used in the evaluations. It also reports that regular graphs perform best among the tested graph distributions.

C.1. Additional Implementation Details For Section 2.2

  • For the Sum task, the graphless teacher uses a readout sampled once from N(0, 1), with 20-node graphs and 128-dimensional i.i.d. Gaussian node features.The student is a one-layer GNN for Sum and three-layer GNNs for PROTEINS and ENZYMES.Source: §C.1 · p. 17
  • The Sum-task learning curves use sample sizes from 20 to 4,000; the approximately 16,000-parameter GNN can fit the training data perfectly.The listed sample sizes are 20, 40, 60, 100, 200, 300, 400, 500, 1,000, 2,000, and 4,000.Source: §C.1 · p. 17

C.2. Experimental setup in Section 3.2.1

  • The Section 3.2.1 experiment trains a one-layer linear GNN with readout on 20-node 5-regular graphs and evaluates it on 100-example test sets varying in graph distribution.All test sets share the same node features.Source: §C.2 · p. 18

C.3. Additional Dataset Information

  • The real-world dataset descriptions cover movie-genre, chemical-compound, scientific-collaboration, and Reddit community prediction tasks.The chemical-compound datasets include enzyme prediction and tumor-growth suppression or inhibition labels.Source: §C.3 · pp. 18–19
  • The appendix identifies mol-hiv and mol-pcba as molecular-property datasets, summarizes dataset statistics in Table 4, and adds node-degree features when datasets lack node features.The table caption identifies its scope as the real-world datasets used in the evaluation.Source: §C.3 · p. 19, Table 4 · p. 19

C.4. Hyper-Parameters

  • The evaluated GNNs use ReLU, 3 or 5 layers, 64 hidden channels, Adam, 1,000 epochs, and early stopping; learning rate, dropout, and preserved COV are varied.Figure 11 tracks topological and root weight norms; on empty graphs, topological weights are untrained and their ratio is zero from initialization. Listed learning rates are 1e-3 and 1e-4, dropout rates are 0 and 0.5, and preserved COV values are 80% and 50%.Source: §C.4 · pp. 19–20, Figure 11 · p. 20
  • Regular graphs show the best performance among the tested graph distributions when the same GNN is trained on graphs with identical node features and graphless-teacher labels.Figure 10 compares learning curves across graph structures.Source: Figure 10 · p. 20

C.5. Models

  • For reduced-COV evaluations, added edges receive edge features that distinguish them from original edges, and neighbor aggregation processes this information nonlinearly.Source: §C.5 · p. 20
Loading 2309.04332v2…