acceptodds
Withdrawn from ICLR 2027

Going Deeper, Staying Distinct: Graph Learning through Minimal Substitution

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Deep graph models need to gather information from distant nodes while preserving the differences between node representations. In conventional message passing, this wider reach is obtained by repeatedly mixing neighboring features, which can gradually erase the distinctions needed for downstream tasks. We introduce Deep Minimal Substitution Graph Learning (DMSGL), which views deep propagation as dynamic succession within a complex network, assuming this succession follows a widely used yet structurally minimalist model of Minimal Substitution. Inspired by Minimal Substitution, we design a Message-substitution mechanism that treats the layer-wise evolution of node features as dynamic succession. Each layer incorporates nonlocal features while retaining the graph structure learned through local propagation. This broadens the information available to a node without tying long-range access entirely to repeated local smoothing. We analyze how representations vary under DMSGL and establish conditions for retaining discriminative information through deep propagation. Extensive experiments demonstrate that DMSGL maintains stable performance. Furthermore, as the model depth increases, the quality of the learned representations improves without succumbing to the over-smoothing problem typically associated with traditional message-passing mechanisms. Together, these results show that DMSGL supports going deeper while keeping node representations distinct.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Minimal substitution, Representation learning for graph, Deep model

Reviews

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

DMSGL models deep feature propagation as network succession. A substitution rule weights information from sampled nonlocal nodes. A learned coefficient combines this information with local propagation. Residual updates retain earlier representations. The paper provides a finite-depth analysis and evaluates node classification on six benchmarks.

Critical strengths

1.DMSGL achieves the highest reported mean accuracy at 64 layers across all six benchmarks. Repeated runs support the result. The depth curves show that it can maintain performance in deep settings. This provides useful evidence that its approach to nonlocal propagation is effective. 2.The ablations support combining local propagation with global information. The appendix establishes a conditional variation bound for realized hub sequences. This connects the architecture to a checkable spectral condition rather than relying only on predictive results.

Critical weaknesses

1.The certificate measures distance from the normalized-Laplacian nullspace. On irregular graphs, identical node representations can still have positive Laplacian energy. The lower bound can also be zero. Therefore, the theorem does not directly establish the advertised retention of useful node distinctions. Its practical relevance needs evidence that the bound remains informative in trained models. 2.The source of the performance gain remains insufficiently isolated. The substitution rule needs comparison with sampled global attention while other components are held fixed. The deep Photo curve also appears inconsistent with the main reported result. These issues affect interpretation of the mechanism. Including the relevant GCNII baseline would strengthen the comparison.

Questions for authors

1.How often is the certificate positive in trained models? What connects this spectral condition to node distinctions that support classification? 2.What explains the Photo discrepancy? Does the substitution rule remain beneficial when the rest of the architecture is held fixed?

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

The article introduces a model (called DMSGL) that combines local and global message passing to prevent over-smoothing. The main idea is to randomly select global hub nodes which propagate information to all nodes. Such hubs are reselected at every layer. This global information is then combined with a standard local GCN propagation step. In an experimental section, the authors show that their model achieves the best performance among the tested methods when setting the depth to 64. They furthermore show that their model remains stable with increasing numbers of layers.

Critical strengths

The method is conceptually cheap and is stable even with a large number of layers. This approach could potentially also be used to other (local) GNNs to reduce the sensitivity to the choice of the number of layers, although this is not explicitly considered in the paper.

Critical weaknesses
  1. The idea of using global nodes for message passing is not new. Here, the authors simply introduce a variation of this idea where global nodes are selected randomly from the set of all nodes and the information propagation is separate from the local message passing. This idea is similarly found in GraphGPS which is neither discussed nor compared against. On a similar note, I believe Exphormer is equally related.

  2. The experimental evaluation is mainly based on a table that compares methods strictly at 64 layers. While DMSGL, being optimised for this scenario, outperforms the other tested methods, I'd argue that setting the number of layers to such an extreme value is quite unfair to the competitors. It's a well-known observation that shallow models generally do better on most datasets. So, a comparison at each method's optimal depth would be a fairer comparison, I believe.

Questions for authors
  1. Have the authors tested how DMSGL compares when the depth for all methods is tuned as a hyperparameter?
  2. Did the authors compare to other methods that use global message passing such as GraphGPS or Exphormer?
Reviewer_Hfa2OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a deep graph learning architecture that combines local graph propagation with feature-dependent interactions through randomly sampled hub nodes. The global interaction weights are governed by feature similarity, receiver-node degree, and propagation depth, framed around a “minimal substitution” perspective. The model additionally incorporates local–global fusion, residual updates, and a spectral regularization term. Experiments evaluate node classification performance across six benchmarks, including ogbn-arxiv.

Critical strengths
  • The problem is relevant and clearly presented. Maintaining representation expressiveness and preventing degradation in deep GNNs remains an important topic, and combining local propagation with sparse nonlocal interactions is a sensible practical direction.
  • Due to sparse hub sampling, the computational overhead is significantly reduced.
  • Competitive raw performance, compared to the baselines listed in the paper.
Critical weaknesses
  • The 'minimal substitution' framing is unsubstantiated by the mathematical formulation. The paper’s primary conceptual claim rests on adapting the “minimal substitution” principle, yet there is no rigorous correspondence between this concept and the implemented update rule. Operationally, the model computes a similarity-gated sum over sampled hubs, fuses it with local message passing, and applies an additive residual update. It is completely unclear what is being substituted, which mathematical term enforces substitution rather than standard additive aggregation, or what structural constraints this principle imposes on the architecture.

  • The paper fails to isolate the empirical gains of the proposed mechanism from the confounding effects of the backbone. The current ablation study does not convincingly demonstrate that the proposed degree and depth modulated hub mechanism is the true driver of the reported improvements. In particular, the paper’s own branch ablations reveal that the local-only backbone accounts for nearly all of the performance gains. For example, on Photo and Computer, removing the entire global branch yields 95.74% and 89.62%, respectively (compared to 96.50% and 90.22% for the full model), which already outperforms the strongest external baselines in the main table. This indicates that the heavy lifting is done by the underlying residual backbone, local–global fusion structure, or training/regularization recipe—not the proposed global substitution rule. Second, the ablations fail to decompose the three factors of the proposed gate.

  • The paper does not sufficiently position it in the literature on gnn oversmoothing and important baselines are missing, such as GCNII, graph transformer and so on. Furthermore, the paper lacks direct, same-backbone comparisons against established graph rewiring methods, virtual/global node architectures, or simple random-shortcut baselines. Comparing the full proposed system only against external architectures with different backbones and regularizers leaves open the obvious alternative explanation that any sparse nonlocal shortcut added to the authors' backbone would perform similarly.

  • The benchmark datasets do not cover the full spectrum of homophiliy. Heterophilic graphs are missing.

  • The theoretical analysis does not support a mechanism-specific claim, the The finite-depth lower bound presented in the paper relies on generic properties of residual recursions and matrix norms. It does not meaningfully exploit the specific functional form of beta_i,l or cosine similarity.

Questions for authors
  • Because hubs are sampled at each layer, a 64-layer model is exposed to many more sampled global nodes over a forward pass than a 2-layer model. Consequently, performance gains at greater depth may simply reflect increased global node coverage rather than successful long-range propagation. A controlled interaction budget (e.g., shallow models with more hubs vs. deep models with fewer hubs) is needed.

  • There are unexplained inconsistencies between the main tables and Appendix D (e.g., the 64-layer Computer result for the proposed model and the 64-layer Cora result for GCN), what is your evaluation consistency and hyperparameter tuning parity across baselines?

  • Other questions have been involved in the "weakness".

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

Related papers

Discussion (0)

Sign in to comment.