acceptodds
Under review as a conference paper at ICLR 2027

When Irrelevant Graph Growth Changes Old-Node Predictions: Graph Extension Consistency for Spectral Positional Encodings

Abstract

Graph positional and structural encodings are often recomputed when an input graph grows. We ask whether this recomputation can change a frozen predictor's output on persistent nodes, even when their features, original edges, and local computational neighborhoods remain unchanged. We formalize this requirement as graph extension consistency. For global spectral encodings that retain the smallest strictly positive Laplacian modes, we identify spectral budget competition: added regions can displace modes representing the original graph. Under the stated graph and spectral-gap assumptions, we derive exact old-node spectral-projector discrepancies under disjoint extension and a strictly positive limit as a connecting bridge weakens to zero. We further introduce a paired extension audit that isolates the predictive consequences of encoding recomputation while holding learned parameters, inference state, raw features, and protected non-encoding computations fixed. Across WebKB and Airports datasets, we observe encoding-dependent probability drift and, in some configurations, prediction flips. Matched controls that preserve the original structural inputs reduce this drift to zero or the numerical-control scale, while targeted interventions distinguish spectral-input sensitivity from other encoder-domain effects. These results establish graph extension consistency as a distinct theoretical and empirical criterion for evaluating graph-dependent structural encodings.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph representation learning, Spectral positional encodings, Graph extension consistency

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_LLLyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper addresses the problem of structural encoding recomputation changing predictions on existing nodes after graph extension and formalizes Graph Extension Consistency (GEC). Theoretically, it proves spectral subspace discrepancies under disjoint and weak-bridge extensions for spectral encodings that select a fixed number of low-frequency Laplacian modes with strictly positive eigenvalues. Experimentally, it investigates the effects of encoding recomputation on predictions and demonstrates changes in predicted probabilities across multiple datasets and encoding methods.

Critical strengths
  • The theoretical result that consistency can fail under weak-bridge extensions even when it holds under disjoint extensions is interesting.
Critical weaknesses
  • Insufficient motivation and significance of the problem setting.

    • Although graph extension consistency is an interesting problem, the paper does not sufficiently explain when and why this property matters in practical graph learning. In particular, it is unclear how naturally the assumptions of the proposed setting arise in practice. Moreover, since changes in predictions do not necessarily imply degraded performance, it is difficult to assess the practical significance of the problem.
  • Major issues with organization and clarity.

    • The relationships among the problem setting, theoretical contributions, and experimental validation are not clearly organized, making the paper's central claims difficult to understand even after careful reading. Many definitions and assumptions are introduced without sufficient background or intuitive explanations. The poor readability makes it difficult to properly assess the significance of the theoretical results.
Questions for authors
  • Could the authors provide concrete examples of practical scenarios where the proposed setting is important? In particular, the reviewer would like to understand situations where structural encodings must be recomputed after adding irrelevant graph regions, even though the task-relevant information for existing nodes remains unchanged.
Reviewer_bdpLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes "graph extension consistency" (GEC), which argues that recomputing structural encodings after a graph grows should not change a frozen model's predictions on unchanged old nodes. It identifies "spectral budget competition" in encodings that keep the kk lowest positive Laplacian modes, and introduces an "Extension Counterfactual Audit" (ECA) that recomputes encodings for a frozen model.

Critical strengths

S1: The paper raises an interesting question that, as far as I'm aware, has not been studied directly: whether growth elsewhere in the graph can change predictions on nodes whose own inputs are untouched.

S2: I like that the paper does not stop at the failure case and also identifies encodings that provably avoid it, such as heat-kernel and random-walk features.

Critical weaknesses

W1: My main concern is that I don't see a convincing example where this drift actually causes a problem. The paper shows that predictions can change, but accuracy sometimes improves after extension and sometimes gets worse. I'm therefore not convinced that this is an important issue in realistic settings where GNNs are deployed.

W2: The experiments rely on small, older datasets such as Airports and WebKB, whose relevance has been questioned [1], even though larger and more realistic benchmarks are now available [2, 3, 4].

W3: I'm also concerned about how the extensions are constructed. Joining two unrelated graphs seems quite different from how a graph would grow in practice.

W4: No anonymized code is provided, which is problematic since several components, including the R-PEARL reference and the WIRE audit wrapper, are local reimplementations.

W5: The paper introduces many new acronyms and writes in heavily qualified prose that repeats similar caveats across sections, which makes the core argument harder to follow than its content requires.

References:

[1] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks, ICML 2025.

[2] GraphBench: Next-generation graph learning benchmarking.

[3] GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data, NeurIPS 2025.

[4] OgBench: A Framework for Evaluating Graph Neural Networks on Omics Data.

Questions for authors

Q1: Can the authors show a realistic setting, where encoding drift measurably harms old-node accuracy?

Q2: Can you report the main frozen-prediction comparison on more dataset pairs and with other backbones, such as a graph Transformer?

Q3: How large is the drift on larger and more recent benchmarks, for example a temporal split where new nodes arrive over time, using a standard global spectral encoding? Perhaps over temporal benchmarks?

Q4: Can you release an anonymized code repository, including the local R-PEARL implementation and the WIRE audit wrapper?

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

The paper focuses on a relatively well-known property of GNNs: adding new nodes can alter the predictions for existing nodes through message passing. It then seeks to explain this behavior using theorems involving spectral gaps. However, given the numerous assumptions these theorems require, it is unclear to me whether they offer meaningful insights for practical applications. Finally, the paper presents experimental results examining the resulting prediction flips.

Critical strengths

The paper tries to formalize a known issue via some spectral analysis.

Suggests an auditing mechanism to understand the impact of graph changes.

Critical weaknesses

The practical value of the theoretical results is unclear to me, particularly whether the resulting recommendations apply to real-world graphs.

The evaluation is also limited to two datasets and a narrow set of GCN models. More extensive experiments across additional datasets and diverse GNN architectures are needed to establish the scope and significance of the contribution.

Finally, it is unclear whether prediction consistency is always desirable in practice. Newly added nodes may provide relevant information that justifies changing the predictions for existing nodes, potentially improving overall accuracy.

Questions for authors

Could you please provide analysis on whether the assumptions given for theorems are meaningful for existing graphs?

Do changing/flipping the labels reduce performance when new nodes are added ? How overall performance changes?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.