mlsanityData to 14 Oct 2026

On the Utilization of Unique Node Identifiers in Graph Neural Networks

arXiv 2411.02271 ↗First posted 4 Nov 2024cs.LG cs.AI stat.MLcited by 2

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks have inherent representational limitations due to their message-passing structure. Recent work has suggested that these limitations can be overcome by using unique node identifiers (UIDs). Here we argue that despite the advantages of UIDs, one of their disadvantages is that they lose the desirable property of permutation-equivariance. We thus propose to focus on UID models that are permutation-equivariant, and present theoretical arguments for their advantages. Motivated by this, we propose a method to regularize UID models towards permutation equivariance, via a contrastive loss. We empirically demonstrate that our approach improves generalization and extrapolation abilities while providing faster training convergence. On the recent BREC expressiveness benchmark, our proposed method achieves state-of-the-art performance compared to other random-based approaches.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 28 of its 34 references that are in the map. First posted on arXiv 4 Nov 2024.

Builds on

28 of 34 references.

References · 28

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2019Simplifying Graph Convolutional Networkscited by 1,477
  3. 2015Spatial Transformer Networkscited by 1,429
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  7. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  8. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  9. 2021Identity-aware Graph Neural Networkscited by 198
  10. 2020Random Features Strengthen Graph Neural Networkscited by 186
  11. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  12. 2021Equivariant Subgraph Aggregation Networkscited by 154
16 more
  1. 2019Relational Pooling for Graph Representationscited by 150
  2. 2021Nested Graph Neural Networkscited by 137
  3. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  4. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  5. 2016TI-POOLING: transformation-invariant pooling for feature learning in Convolutional Neural Networkscited by 67
  6. 2022Ordered Subgraph Aggregation Networkscited by 57
  7. 2020Learning Invariances in Neural Networkscited by 52
  8. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  9. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  10. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  11. 2023Graph Positional and Structural Encodercited by 33
  12. 2023Graph Positional Encoding via Random Feature Propagationcited by 31
  13. 2024The Interpretable and Effective Graph Neural Additive Networkscited by 20
  14. 2023Graph Invariant Learning with Subgraph Co-mixup for Out-Of-Distribution Generalizationcited by 18
  15. 2024Learning Invariant Representations of Graph Neural Networks via Cluster Generalizationcited by 10
  16. 2024GRANOLA: Adaptive Normalization for Graph Neural Networkscited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2026Universality and Approximation Rates of Graph Neural Networks with Random Featurescited by 3
  2. 2025Feature Augmentation of GNNs for ILPs: Local Uniqueness Sufficescited by 0