I've work with GNNs. I have not explicitly looked into this, but in general, the dynamics of GNNs are really interesting and there are many different lenses in which one can study the behavior of GNNs and find interesting takeaways.

- Explicit Message Passing: https://arxiv.org/abs/2202.11097

- Algorithmic Reasoning: https://arxiv.org/abs/2203.15544

- Diffusion: https://proceedings.mlr.press/v139/chamberlain21a.html

- Spectral: https://arxiv.org/abs/2010.02863

- Sparsity: https://arxiv.org/abs/2211.15335

- Training Tricks: https://arxiv.org/abs/2108.10521

- Interaction Networks / Physical Models: https://arxiv.org/pdf/1612.00222.pdf

- Expressive Power: https://arxiv.org/abs/2308.08235

- "Over-Squashing": https://arxiv.org/abs/2111.14522

Yes, and no. I just completed a PhD on GNNs, and in the last 4 years I have not used a single GNN without residual connection. It is quite well known that res connections allow to alleviate a lot of issues such as oversmoothing, and I expect that it would be the case here as well.

This is a personal impressionistic opinion, so please take it as such and don’t expect citations or details. It has been empirically clear since the inception of GNN that the message passing structure and forced equivariance would make it hard to optimize GNNs for many practical applications. In a sense if you could solve graph isomorphism with these architectures, you would find a counter example for an NP-complete problem, so few people expected magic, but it was still disheartening to see the old school hashed bags of subgraphs outperform fancy GNNs on practical problems and to see that pretraining didn’t help the GNNs as much, or to see that the internal structures of these models are not quickly building up sensible hierarchies on their own. So then people started the hacking and exploring and by now the practical models are better than the early hacks but the theoretical optimization for how to deal with graphs in subdomains of extreme interest (say drug discovery, biology, or materials design) has not yet finished. By comparison autoregressive language models are super mature and generally applicable, as are transformers. These mixups in the early GNN led people to spend a lot of effort reformulating problems to match established architectures better or complement the GNN parts with hacks.

In my use case I care not one bit about the overall graph structure, but only about the inter-node interactions/relationships. But often times you will get graphs where you have 1% type A interactions, 12% type B interactions and 87% type C interactions and that makes training quite challenging. But I am not sure if you can stay that that is over-fitting the graph structure rather than simply learning the most common interactions in the dataset.

I haven't worked on GNNs specifically, but I’ve done academic research on other architectures, and I used MirrorThink.ai to perform a comprehensive literature review. Hope it gives some useful context.

---

The paper “Graph Neural Networks Tend to Overfit the Graph Structure” provides a significant contribution to the field of Graph Neural Networks (GNNs) by highlighting the issue of overfitting to the graph structure. This overfitting phenomenon can lead to reduced performance, especially when the graph structure is non-informative or irrelevant to the task at hand. To address this issue, the authors propose a graph-editing method called R-COV, which aims to reduce the coefficient of variation (COV) of a given graph, making it more similar to regular graphs.

This research aligns with other studies in the field that have also addressed the issue of overfitting in GNNs. For instance, the paper “Overfitting Mechanism and Avoidance in Deep Neural Networks” discusses the problem of overfitting in deep neural networks and proposes a consensus-based classification algorithm to address this issue. This algorithm identifies consistently classified samples and rejects samples that are classified randomly, which can help avoid overfitting even with a small number of training samples.

Another relevant study is “Neighborhood Random Walk Graph Sampling for Regularized Bayesian Graph Convolutional Neural Networks,” which proposes a Bayesian Graph Convolutional Neural Network (BGCN) that accounts for uncertainty in the graph structure and reduces overfitting. The BGCN model utilizes a neighborhood random walk-based graph sampling method to sample nodes from the observed graph, improving sampling efficiency and diversifying connections between nodes.

The paper “Training Graph Neural Networks by Graphon Estimation” also proposes a method for training GNNs that mitigates the issues of overfitting and over-smoothing. This method involves resampling the adjacency matrix of the graph from a graphon estimate obtained from the underlying network data. By resampling the adjacency matrix, the method provides data augmentation and introduces randomness to the GNN training process, which helps alleviate overfitting and over-smoothing.

Finally, the paper “Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs” proposes the Eigen-GNN module to enhance GNNs’ ability to preserve graph structures by integrating the eigenspace of graph structures with GNNs. This approach significantly improves the preservation of graph structures and consistently outperforms existing GNNs in structure-driven tasks.