acceptodds
Under review as a conference paper at ICLR 2027

Towards Invariance to Node Identifiers in Graph Neural Networks

Abstract

Message-Passing Graph Neural Networks (GNNs) are known to have limited expressive power, due to their message passing structure. One mechanism for circumventing this limitation is to add unique node identifiers (IDs), which break the symmetries that underlie the expressivity limitation. In this work, we highlight a key limitation of the ID framework, and propose an approach for addressing it. We begin by observing that the final output of the GNN should clearly not depend on the specific IDs used. We then show that in practice the network does in fact depend on the IDs, which is undesirable. Invariance to node IDs may be enforced in several ways, and we discuss their theoretical properties. We then propose a novel regularization method that effectively enforces ID invariance to the network. Extensive evaluations on both real-world and synthetic tasks demonstrate that our approach significantly improves ID invariance and, in turn, often boosts generalization performance.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, ID Invariance, Expressivity

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_D1u4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents a novel method in addressing a critical issue in the expressiveness of GNN (Graph Neural Networks). They introduce the fundamental limits of MPNN (message passing neural networks) in its expressiveness and found out the issue with an existing method in bridging the expressiveness gap (RNI, random node initialization). They then fixed this gap with ICON (ID-Invariance through Contrast), and provided empirical and theoretical analyses on how and why practical models fail to learn invariance with the added expressiveness property and how ICON learns these behaviors.

Critical strengths
  1. substantial improvements over the baseline RNI results in many axes
  2. good theoretical analyses
  3. clean writing
Critical weaknesses
  1. mixed improvements compared with baseline GNNs (GraphConv, GIN, GAT, TransformerConv, and GraphGPS without RNI and ICON): I am not observing significant improvements to the baseline methods. The performance of the models in table 2 are mostly just matching regular baseline GNNs without the author's methods, and that actually adding the expressive baseline method (RNI) for becoming more expressive hurts most of the time. This entails a question that, if the expressive baseline is significantly worse than the baseline GNNs and the authors just try to fix the expressive baseline to match the baseline GNNs, what's the right interpretation on the benefits that this paper introduces? Why do we need this method if it is a "fix" to a bug in the expressive baseline?
  2. Convergence and Generalization claims: I am not seeing the matched comparison with baseline GNNs.
Questions for authors
  1. Can you explain why ICON helps very little with downstream graph task performance (compared with GNN baseline)? I am seeing Table 2 showing mixed improvements on various tasks compared with baseline GNN methods(GraphConv, GIN, GAT, TransformerConv, and GraphGPS). It would also be nice if the authors can report the compute and flop required for training the methods so that we can be certain on the validity on the comparison.
  2. Regarding the claim on faster convergence: could you also compare with GNN baseline?
  3. It'd be nice if the authors could justify why it is so critical to be more expressive with a GNN method, when its performance only matches that of the baseline GNN methods. The added benefits are on generalization and convergence speed, but it is not cleanly compared with baseline GNNs.
Reviewer_ALYbOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes ICON, an ID-invariance regularization method that addresses overfitting and degraded generalization caused by GNNs over-relying on specific random node ID values when enhancing expressive power. Experimental results show that ICON consistently outperforms random node initialization (RNI) across various GNN architectures.

Critical strengths

(1) This paper proposes a simple yet effective method for enhancing GNN expressivity with minimal architectural modifications. (2) This paper provides theoretical analysis of the relationship between ID invariance and GNN expressivity. (3) This paper demonstrates the effectiveness of the proposed method through experiments on multiple datasets and GNN architectures.

Critical weaknesses

(1) Although the paper addresses an interesting problem, the proposed method essentially relies on a conventional consistency regularization term to reduce the model's dependence on specific random node ID values, resulting in limited methodological novelty. (2) While ICON achieves promising improvements over the original random node initialization (RNI) method, comparisons with other node ID-based methods are missing. Moreover, most evaluated GNN architectures are relatively outdated, leaving its effectiveness compared with recent GNN architectures and node ID-based methods unclear. (3) The paper lacks further ablation studies to evaluate the effects of applying regularization at different layers or multiple layers. Additionally, ICON appears to show limited improvements over the original GNNs on some smaller graphs or datasets, which warrants further investigation.

Questions for authors

(1) The authors are encouraged to compare ICON with more recent node ID-based methods and GNN architectures to further validate its effectiveness. (2) Additional ablation studies are recommended to better demonstrate the effectiveness of applying regularization specifically at the final layer. (3) The authors should provide a more thorough discussion of ICON's performance across different graph and dataset sizes, particularly on small graphs and datasets.

Reviewer_s1HgOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

While GNNs naturally provide permutation invariance over nodes, the authors aim to enhance their expressive power by introducing node IDs as additional node features. However, random node ID features may break permutation invariance. Therefore, the authors propose introducing regularization terms during training to preserve this invariance while incorporating node ID features.

Critical strengths

The experimental benchmarking includes multiple baselines and provides comprehensive results demonstrating improvements on small-scale datasets.

The overall flow of the paper is natural and easy to follow. The intermediate results effectively motivate the proposed idea and demonstrate the authors' clear reasoning behind its development.

Critical weaknesses

One concern is that, although the proposed regularization term encourages node ID invariance, it is unclear whether the final node features are strictly constrained to guarantee this property. How do the authors ensure that all permutations of node IDs produce the same results? Does the training process consider all possible node ID permutations when computing the regularization term?

Additionally, for more expressive GNN architectures that can distinguish graphs beyond 1-WL, how can the proposed regularization term guarantee node ID invariance on input graphs distinguishable by 3-WL? For example, if you apply this term to GIN, which is proven to have 1-WL test expressiveness, can adding this regularization term distinguish a 3-WL test graph?

Questions for authors

For Definition 4.1, would the authors mind clarifying the definition of the symbol SS? Does SS represent the set of all graphs? Additionally, for the matrix �2��2�, could the authors clarify the definition of rr?

I also have a question regarding the expressive power of the proposed method. With the introduction of the new node features, can the expressive power of GNNs be improved beyond the 1-WL or even 3-WL test? If so, could the authors provide further theoretical justification?

Besides real-world graph datasets, have the authors evaluated the proposed method on synthetic datasets specifically designed for WL tests? Additionally, have the authors compared their method with other GNN architectures whose expressive power has been theoretically established beyond 1-WL and up to 3-WL? What are the advantages and disadvantages of the proposed method compared to these approaches?

Comments on the paper

1 comment

Thank you for your comment. My concern is that the experimental comparisons primarily rely on RNI (2021) as the node ID-based baseline, while most of the evaluated GNN architectures date back to 2022 or earlier. Both the related work discussed in the manuscript and more recent studies suggest relevant alternatives for comparison, such as A Systematic Approach to Universal Random Features in Graph Neural Networks (TMLR 2023), On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024), and Expressive Graph Neural Networks via Equivariant Use of Noise (ICML 2026).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.