mlsanityData to 7 Oct 2026

Graph Classification with GNNs: Optimisation, Representation and Inductive Bias

arXiv 2408.09266 ↗First posted 17 Aug 2024cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Theoretical studies on the representation power of GNNs have been centered around understanding the equivalence of GNNs, using WL-Tests for detecting graph isomorphism. In this paper, we argue that such equivalence ignores the accompanying optimization issues and does not provide a holistic view of the GNN learning process. We illustrate these gaps between representation and optimization with examples and experiments. We also explore the existence of an implicit inductive bias (e.g. fully connected networks prefer to learn low frequency functions in their input space) in GNNs, in the context of graph classification tasks. We further prove theoretically that the message-passing layers in the graph, have a tendency to search for either discriminative subgraphs, or a collection of discriminative nodes dispersed across the graph, depending on the different global pooling layers used. We empirically verify this bias through experiments over real-world and synthetic datasets. Finally, we show how our work can help in incorporating domain knowledge via attention based architectures, and can evince their capability to discriminate coherent subgraphs.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 26 of its 31 references that are in the map. First posted on arXiv 17 Aug 2024.

Builds on

26 of 31 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2021How Attentive are Graph Attention Networks?cited by 818
  7. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 762
  8. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 503
  11. 2019Graph U-Netscited by 489
  12. 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
14 more
  1. 2019Self-Attention Graph Poolingcited by 421
  2. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  3. 2016Benefits of depth in neural networkscited by 248
  4. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  5. 2020Can Graph Neural Networks Count Substructures?cited by 235
  6. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  7. 2019ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representationscited by 156
  8. 2020Interpreting Graph Neural Networks for NLP With Differentiable Edge Maskingcited by 152
  9. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  10. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  11. 2022GraphFramEx: Towards Systematic Evaluation of Explainability Methods for Graph Neural Networkscited by 57
  12. 2020Explicit regularization and implicit bias in deep network classifiers trained with the square losscited by 37
  13. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  14. 2017Quantifying Translation-Invariance in Convolutional Neural Networkscited by 30

Built on by

Not cited yet.