6 ms·

Anyone working with GNNs have an experience with this? Has this affected your work?

by dpflan 3y ago

cmavvv 3y ago
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.
dauertewigkeit 3y ago
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.
- lmeyerov 3y ago
  the paper is on my queue, but yeah, these kind of class imbalance & class dependency problems are why things like RGCNs and negative sampling are so popular. It's almost the typical case in cyber, fraud, supply chain, social, etc. As others posted here, ideas like metapaths, transformer equivalence, etc are common building blocks in the GNN world because of these kinds of things. Important areas so def curious.
stefanpie 3y ago
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 https://arxiv.org/abs/2202.11097 - Algorithmic Reasoning: https://arxiv.org/abs/2203.15544 https://arxiv.org/abs/2203.15544 - Diffusion: https://proceedings.mlr.press/v139/chamberlain21a.html https://proceedings.mlr.press/v139/chamberlain21a.html - Spectral: https://arxiv.org/abs/2010.02863 https://arxiv.org/abs/2010.02863 - Sparsity: https://arxiv.org/abs/2211.15335 https://arxiv.org/abs/2211.15335 - Training Tricks: https://arxiv.org/abs/2108.10521 https://arxiv.org/abs/2108.10521 - Interaction Networks / Physical Models: https://arxiv.org/pdf/1612.00222.pdf https://arxiv.org/pdf/1612.00222.pdf - Expressive Power: https://arxiv.org/abs/2308.08235 https://arxiv.org/abs/2308.08235 - "Over-Squashing": https://arxiv.org/abs/2111.14522 https://arxiv.org/abs/2111.14522
pama 3y ago
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.
- mrfox321 3y ago
  When you say hashed bags of sub graphs, are you generalizing bag of words, here?
  - brilee 3y ago
    see https://www.rdkit.org/docs/GettingStartedInPython.html#morgan-fingerprints-circular-fingerprints https://www.rdkit.org/docs/GettingStartedInPython.html#morga...
    - pama 3y ago
      Yes that is the example for small molecules. One can generalize to other graphs as well.
- donottell 3y ago
  [dead]
oersted 3y ago
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.

Anyone working with GNNs have an experience with this? Has this affected your work?

by dpflan 3y ago

Anyone working with GNNs have an experience with this? Has this affected your work?

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.

dauertewigkeit 3y ago

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.

lmeyerov 3y ago
the paper is on my queue, but yeah, these kind of class imbalance & class dependency problems are why things like RGCNs and negative sampling are so popular. It's almost the typical case in cyber, fraud, supply chain, social, etc. As others posted here, ideas like metapaths, transformer equivalence, etc are common building blocks in the GNN world because of these kinds of things. Important areas so def curious.

stefanpie 3y ago

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 https://arxiv.org/abs/2202.11097 - Algorithmic Reasoning: https://arxiv.org/abs/2203.15544 https://arxiv.org/abs/2203.15544 - Diffusion: https://proceedings.mlr.press/v139/chamberlain21a.html https://proceedings.mlr.press/v139/chamberlain21a.html - Spectral: https://arxiv.org/abs/2010.02863 https://arxiv.org/abs/2010.02863 - Sparsity: https://arxiv.org/abs/2211.15335 https://arxiv.org/abs/2211.15335 - Training Tricks: https://arxiv.org/abs/2108.10521 https://arxiv.org/abs/2108.10521 - Interaction Networks / Physical Models: https://arxiv.org/pdf/1612.00222.pdf https://arxiv.org/pdf/1612.00222.pdf - Expressive Power: https://arxiv.org/abs/2308.08235 https://arxiv.org/abs/2308.08235 - "Over-Squashing": https://arxiv.org/abs/2111.14522 https://arxiv.org/abs/2111.14522

pama 3y ago

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.

mrfox321 3y ago
When you say hashed bags of sub graphs, are you generalizing bag of words, here?
- brilee 3y ago
  see https://www.rdkit.org/docs/GettingStartedInPython.html#morgan-fingerprints-circular-fingerprints https://www.rdkit.org/docs/GettingStartedInPython.html#morga...
  - pama 3y ago
    Yes that is the example for small molecules. One can generalize to other graphs as well.
donottell 3y ago
[dead]

oersted 3y ago

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.