acceptodds
Under review as a conference paper at ICLR 2027

To Learn is to Wander: Learning Across Graphs and Tasks with Random Walks

Abstract

Graph foundation models aim to transfer across graphs, feature spaces, relational schemas, and prediction tasks, yet existing approaches typically generalize only within particular graph modalities or tasks. We propose Wander, a graph foundation model designed to operate across these settings within *a single pretrained checkpoint*. Following the prior-predictive perspective, we formulate graph learning as completion of a partially observed graph. We realize this task-general view through a common interface based on random walks, allowing the same model to operate across homogeneous and multi-relational graphs with varying features, labels, and relational schemas. Wander can increase its structural context at inference time without changing its learned parameters and, under suitable assumptions, universally approximates the corresponding Bayes-optimal predictor on bounded connected graphs. Empirically, a single pretrained checkpoint achieves state-of-the-art or highly competitive results across node classification, homogeneous link prediction, and knowledge-graph link prediction. Moreover, joint pretraining across graph modalities and tasks preserves performance in specialized settings while enabling positive transfer and the composition of separately learned capabilities at inference time.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph foundation models, prior-data fitted networks, random walks, in-context learning, inference-time adaption, link prediction, node classification, knowledge graph reasoning

Reviews

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

The paper proposes a new approach to graph foundation models that is based on sampling random walks from a graph and applying to them a neural network that is based on prior-data fitted networks (PFNs) paradigm and is pretrained on synthetically-generated data. The proposed model (WANDER) can be applied to node classification, link prediction, and typed link prediction (in knowledge graphs) in the in-context learning regime, and is the first model that can perform all these tasks with a single checkpoint. The paper proves some theoretical properties of the proposed approach and provides extensive empirical evaluation.

Critical strengths

The general approach proposed in the paper is interesting and might be potentially useful.

Critical weaknesses

The paper is very difficult to follow, which is exacerbated by a lot of important information being hidden in the appendix. Most notably, Section 5 barely describes how the model actually works - while some basic information flow is described, it is not described what is an intra-node processor, how an in-context learning update is performed, what random walk algorithm is used, what is a recording protocol and a consensus protocol. Providing this information would have been much more useful than spending space on Figure 1 which does not add anything to the text. Another issue are the mathematical results on which the paper spends a lot of space. Almost all of them are conceptually quite straightforward, but following the provided derivations is very difficult due to convoluted notation that tries to unify node classification and link prediction. Overall, I believe the paper needs to be substantially rewritten to properly describe the method being proposed in the main text.

Another weakness is the experimental section. The experiments cover a vast range of datasets, however, most of the node classification and link prediction datasets used are not reliable and have been criticized many times [1, 2, 3]. The paper even cites some of these works, but still uses flawed datasets. For link prediction, it would have been much better to use datasets from OGB [4], and for node property prediction, it would have been much better to use datasets from GraphLand [3] (the paper uses 2 datasets from GraphLand instead of the full benchmark, and one of them is strongly downsampled, which raises the question about the scalability of the method, while on the second one WANDER is very strongly outperformed by a simple GCN, which is also a suspicious signal that is never investigated in the paper).

Finally, Appendix D2 reveals that the pretraining pipeline is very complex and involves multiple stages with different parts of the model being trained. This likely indicates that the model is unstable to train, but the training pipeline is not ablated.

Overall, I believe the paper needs much better presentation, experiments on more reliable datasets, and proper architetcure and training ablations.

[1] A critical look at the evaluation of GNNs under heterophily: Are we really making progress? (ICLR 2023)

[2] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks (ICML 2025)

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

[4] Open Graph Benchmark: Datasets for Machine Learning on Graphs (NeurIPS 2020)

Questions for authors

Can the model scale to large graphs?

Why were link prediction and node classification experiments conducted on outdated datasets?

Can the training pipeline be simplified to train the entire model in one stage?

There are also some issues with references in the paper. Examples: TS-Net was published at NeurIPS 2025, not NeurIPS 2026. GraphPFN was published at ICML 2026 and the bibliography reference is correct, but Table 1 claims the year 2025 for this model.

5 comments
AuthorsOpenReview ↗

Response to reviewers concerns and questions (Part 1/2)

We thank the reviewer for their detailed feedback. Their suggestions have helped us improve the presentation and extend the experimental evaluation. Below, we address each concern and describe the corresponding revisions and additional results.

Weakness 1: …Section 5 barely describes how the model actually works…

We thank the reviewer for this feedback. We have expanded the method description in Section 5, which now explicitly describes both the role and the implementation of each component.

We have also simplified Section 4 by removing the former Theorem 1 and its associated risk notation. Instead, we decided to simply explain the posterior-mixture interpretation directly to reduce notation and complexity. The section now makes the connection to our experimental questions more explicit: learning across tasks and diverse graph families, and combining capabilities acquired during pretraining.

Weakness 2 & Question 2: Why were link prediction and node classification experiments conducted on outdated datasets?

Our original dataset selection was motivated by direct comparability with existing graph foundation models, including GraphAny, TS-Net, and NodePFN, which evaluate on overlapping benchmarks. The datasets proposed by the reviewer also presented practical challenges for baseline evaluation. GraphPFN encountered memory limitations, while NodePFN supports at most 20 classes and cannot be applied to all datasets. These constraints motivated our initial use of a downsampled version of Pokec Regions.

To address the reviewer's concern, we have substantially extended our evaluation across all three prediction tasks. Across these additional benchmarks, Wander outperforms all evaluated baselines on both node-classification datasets, two of three homogeneous link-prediction datasets, and on OGB-BioKG, demonstrating its competitiveness on larger and more recent benchmarks.

Node classification: We additionally evaluated the full Pokec Regions and Web Topics datasets from GraphLand, with results incorporated into Table 5.

DatasetGCNTabPFNv3GraphAnyWander
Pokec Regions45.54.56.248.1
Web Topics30.739.036.942.1

NodePFN and GraphPFN could not be run on these datasets as they exceed their maximum number of supported classes. Using the official ECOC implementation of GraphPFN exceeded the memory limit of the used 80GB H100 GPU.

Homogeneous link prediction: We additionally evaluated OGB-Collab, OGB-PPA, and OGB-Citation2 using sampled Recall@20 (%) with 1,000 randomly sampled negatives. Results have been added to Appendix D.4 (Table 18). AnyGraph could not be evaluated on Citation2 due to a runtime error in its official implementation, while NBFNet exceeded the memory capacity of an 80GB H100 GPU.

ModelCollabPPACitation2
BUDDY64.1592.6097.37
NBFNet44.8589.18—
AnyGraph63.8072.41—
WANDER66.4193.4194.97

Knowledge graph completion: We additionally evaluated OGB-BioKG, obtaining the following results:

ModelMRRHits@1Hits@3Hits@10
Wander0.75830.66590.82270.9311
Flock0.72500.62790.78990.9083
Trix0.70280.60490.75660.9031
Ultra0.65990.57180.69730.8484

Regarding HM Categories, we agree that the substantial performance gap to GCN merits attention. As analyzed in Appendix D.6, this dataset is unusually dense, potentially limiting the structural coverage of a fixed random-walk budget. Increasing the base walk count from 256 to 2,048 improves WANDER's accuracy from 48.7% to 52.1%. Although this does not close the gap to GCN, it suggests that insufficient walk coverage contributes to the performance difference and that walk budgets may need to account for graph density as well as graph size.

AuthorsOpenReview ↗

Response to reviewers concerns and questions (Part 2/2)

Question 1: Can the model scale to large graphs?

Yes. Our additional experiments demonstrate that Wander can be evaluated on graphs with millions of nodes, including Web Topics (2.9 million nodes) and OGB-Citation2 (2.9 million nodes).

For link prediction, Wander processes queries independently, while for node classification it processes test nodes in batches and reuses cached context representations. Larger evaluation sets therefore naturally require more computation because they contain more prediction queries. The random-walk interface provides control over the structural computation allocated to each query or batch: for a fixed architecture, this computation scales linearly with the number and length of sampled walks, rather than the total number of graph edges.

Whether a fixed sampling budget maintains predictive accuracy on larger graphs is a separate empirical question. As discussed in Appendix D.10, walk budgets and test-time ensembling provide a tradeoff between computation and predictive performance. Our additional large-graph experiments illustrate this tradeoff:

GraphNodesEdgesWalk budget × lengthBatch sizeInference samplesSeconds/batch*AccuracySampled Recall@20
PPA576,28960,652,546256 × 64426.5—91.2
PPA576,28960,652,546512 × 64427.3—93.4
Web Topics2,890,33124,754,822256 × 1282,04848239.9—
Web Topics2,890,33124,754,822256 × 12825647942.1—

*measured on single H100 GPU

On PPA, halving the walk budget reduces runtime from 7.3 to 6.5 seconds at a cost of 2.2 percentage points in sampled Recall@20. On Web Topics, increasing batch size eightfold improves throughput by 7.7×, with a preliminary accuracy decrease of 3.2 percentage points. These results illustrate Wander’s computation–accuracy tradeoff on large graphs.

Separately, random-walk sampling also has precedents in large-scale production recommendation systems: Pinterest’s Pixie [1] reports deployed query-time random-walk recommendations over a graph with 3 billion nodes and 17 billion edges, while Twitter’s GraphJet [2] reports serving real-time recommendations using random-walk algorithms. These systems provide evidence that random-walk graph access can be practical at industrial scale.

[1] Eksombatchai et al: Pixie: A system for recommending 3+ billion items to 200+ million users in real-time. WWW 2018.

[2] Sharma et al.: GraphJet: Real-time content recommendations at Twitter. VLDB 2016.

Question 3: Can the training pipeline be simplified to train the entire model in one stage?

Yes, the entire model can be trained in one stage from scratch. The motivation for initially hiding structure is that the model might otherwise learn to predict labels from neighboring labels without learning to relate node features to labeled examples through the ICL layer. This shortcut can work well on the pretraining graphs but transfer poorly to graphs with different relationships between structure and labels. Hiding structure forces the model to learn from features and in-context supervision first.

Following reviewers advice, we added a preliminary ablation in Appendix D.15 comparing three runs:

  • Tabular from scratch: our first pretraining stage, which hides graph structure.
  • Graph from tabular: our third stage, which introduces structure after 200 epochs of structure-free pretraining.
  • Graph from scratch: the same third-stage setup trained from scratch, skipping structure-free pretraining.

On Roman Empire, after the same 48,000 node-classification training steps, Tabular from scratch achieves 56.59% accuracy, compared with 42.44% for Graph from scratch. Thus, hiding structure leads to better transfer for the same number of training steps, consistent with encouraging more effective use of features and in-context supervision. Graph from tabular maintains strong performance after structure is introduced (59.58%), suggesting that it retains these capabilities.

On Cora, where neighboring labels are strongly predictive and the ICL layer may be less essential, Graph from scratch approaches the performance of Graph from tabular.

These early results motivate our curriculum but do not establish that it is necessary. We are running a full comparison with single-stage training and will report the results once available.

I appreciate the authors' responses. However, I believe the evaluation setting being used is still very flawed, especially in the node classification experiments, thus I maintain my score.

The authors refer to "direct comparability with existing graph foundation models, including GraphAny, TS-Net, and NodePFN" as explanation for their evaluation setting used. However, I would like to note that comparing to these models is actually a problem in itself - as the GraphPFN paper shows, TS-Net and NodePFN models obtain very weak results on realistic datasets and are outperformed by simple GNNs. As for GraphAny - it achieves even weaker results because it is simply a weighted ensemble of linear regression models. Note that the GraphAny paper does not actually claim GraphAny to be a GFM (an earlier version of the paper did claim that, but the paper was only excepted after this claim was removed). A recent study [1] shows that that GraphPFN, TAG, and G2T are currently the strongest GFMs for node property prediction, and they are what new models should be compared to (especially as the proposed model is also based on PFNs). And using flawed and actively criticized datasets for compatibility with prior studies is also not a good reason. For example, GraphPFN and [1] reevaluated multiple models including TAG and TS-Net on more reliable datasets for their studies.

Finally, I appreciate the experiments that show that the model scales to million-node graphs, however, results on the web-topics dataset once again demonstrate that on realistic feature-rich datasets WANDER is outperformed by simple GNNs (see the GraphLand paper for GNN results on this dataset).

[1] A Fair Evaluation of Graph Foundation Models for Node Property Prediction

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

WANDER: a graph foundation model that uses random walks to generalize across different graph structures and prediction tasks using a single pretrained model. The authors uses graph learning as a graph completion problem, where missing node labels or edges are predicted from partially observed graphs. WANDER combines node features, labels, and structural information through intra-node attention, in-context attention, and random-walk-based structural updates. The model supports three tasks: node classification, homogeneous link prediction, and knowledge-graph link prediction. Experimental results demonstrate strong or competitive performance across all three tasks. Additionally, joint pretraining enables positive transfer, particularly for homogeneous link prediction, while adjusting the length, number, or sampling strategy of random walks at inference time allows the model to incorporate broader structural information without retraining.

Critical strengths
  1. WANDER combines intra-node attention, in-context attention, and random-walk-based structural updates to incorporate node features, labels, and relational information. The model also allows the number, length, and sampling strategy of random walks to be adjusted without retraining, enabling it to capture broader structural information and improve performance on tasks requiring long-range information propagation.

  2. The authors evaluate WANDER on a diverse collection of graph benchmarks and report competitive or state-of-the-art results across all three tasks. Achieving this performance with a single pretrained checkpoint demonstrates the potential of a generalist graph model.

Critical weaknesses
  1. WANDER is pretrained on FB15k-237, WN18RR, and CoDEx Medium, while some evaluation datasets share underlying graph sources. The paper does not provide an explicit pretraining–test overlap analysis, raising concerns about the zero-shot generalization claims.

  2. In the joint versus single-task experiments, the jointly trained model receives additional updates from other tasks. Thus, the improvements may partly result from increased training rather than positive transfer alone.

Questions for authors
  1. Did the authors check for any overlap between the pretraining and test data in the knowledge-graph experiments?

  2. Can the authors compare joint and single-task training using the same total training budget?

  3. Are the reported improvements consistent across different random seeds?

4 comments
AuthorsOpenReview ↗

Response to reviewers questions

We thank the reviewer for their constructive feedback. We are pleased that they recognize Wander’s flexible structural processing and the potential of a single pretrained model across all three tasks. We address their questions below.

Question 1: Did the authors check for any overlap between the pretraining and test data in the knowledge-graph experiments?

We follow the established pretraining and evaluation protocol used by Ultra, Trix, and Flock, ensuring direct comparability with these methods. Nevertheless, we acknowledge the reviewer’s concern: some evaluation datasets originate from the same underlying knowledge graphs as our pretraining data, and their original inductive splits do not guarantee disjointness in entities, relations, or triples.

Our analysis identified 11 evaluation datasets sharing an underlying source with the pretraining datasets. To assess whether our conclusions depend on this potential overlap, we additionally report the average performance of all models on the remaining datasets, excluding these 11 datasets:

Inductive (e, r)Inductive (e)TransductiveAll 43
MRRH@10MRRH@10MRRH@10MRRH@10
Ultra0.3410.5010.3470.4790.3120.4580.3330.483
Trix0.3670.5310.3720.5060.3390.5000.3590.516
Flock0.3660.5450.3640.5120.3400.5090.3580.526
Wander0.3770.5490.3690.5170.3530.5160.3680.532

These results confirm that Wander’s competitive performance is not driven by datasets sharing underlying sources with pretraining, strengthening our evidence for zero-shot generalization to independently sourced knowledge graphs.

Question 2: Can the authors compare joint and single-task training using the same total training budget?

We thank the reviewer for raising this important question. We would first like to clarify that our single-task ablation is specifically designed to investigate positive transfer across tasks, addressing the following question:

“Does training the same architecture on additional tasks improve performance on the task of interest?”

To isolate this effect, we need to keep the number of target-task training updates identical between the single-task and jointly trained models, while introducing training updates from additional tasks for the jointly trained models. This design directly tests whether learning from other tasks benefits the task of interest.

The reviewer's suggested compute-matched comparison addresses a complementary question:

“Does joint training improve performance more than allocating the same additional training budget exclusively to the target task?”

This distinction is important. Our original experiments provide evidence of positive transfer across tasks, demonstrating that incorporating additional training tasks can improve target-task performance without requiring additional target-task data. This is particularly relevant for broad pretraining scenarios where task-specific training data may be limited.

Nevertheless, we agree that the compute-matched comparison provides valuable additional insight. We have therefore conducted a new experiment on homogeneous link prediction in which the single-task model receives the same total number of training steps as the jointly trained model.

ModelMean R@20 (%)
Joint training (three independent pretraining seeds)42.56 ± 1.22
LP-only, matched task-specific updates40.37
LP-only, matched total training steps41.32

The results show that additional single-task training recovers part of the performance gap (from 40.37% to 41.32%), but the resulting model still achieves lower performance than joint training (42.56%). This suggests that the benefits of joint training are not solely attributable to a larger number of training steps, although additional compute explains part of the improvement.

Overall, we believe these results strengthen our original finding: training on additional tasks benefits the target task when target-task training is held fixed, while the new experiment provides encouraging evidence that this advantage may persist even when total training steps are matched.

Question 3: Are the reported improvements consistent across different random seeds?

Yes. We evaluated Wander with three independent pretraining seeds, including the originally reported checkpoint. The table below reports the mean performance across datasets for each task, summarized as mean ± sample standard deviation across seeds.

TaskOriginal checkpointThree seeds
Knowledge-graph LP (MRR)0.39900.3978 ± 0.0023
Node classification (accuracy, %)67.4967.26 ± 0.68
Homogeneous LP (R@20, %)43.3942.56 ± 1.31

Thank you for the response and the additional experiments. They help address my concerns. Do you have any further results for LP-only training with the same total training steps as joint training? I saw the latest run, but that one matches task-specific updates.

I understand there is limited time, so if these results are not ready, that is fine. I’ll consider the evidence already provided and read the other reviewers’ comments and your responses before making my final decision.

Thank you for the follow-up and for your understanding. We are glad the additional experiments helped address your concerns, and we hope they give you greater confidence in the paper as you make your final decision.

Yes, the latest LP-only run matches task-specific updates. For the comparison with matched total training steps, the previously reported LP-only run is the only result we have available right now.

Dear Reviewer, thank you again for your thoughtful feedback. It helped us improve the paper. Is there any remaining concern we could clarify before the discussion ends? We would also appreciate hearing whether our clarifications and the additional results give you enough confidence in the paper to consider a higher score.

We appreciate the time and care you have put into reviewing our work.

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

The paper introduces WANDER, a graph foundation model that uses a single pretrained checkpoint for node classification, homogeneous link prediction, and knowledge-graph link prediction. It formulates these tasks as predicting missing components of a partially observed graph and combines feature, label, and structure tokens through intra-node attention, in-context attention, and random-walk-based structural updates. The paper establishes permutation equivariance in distribution and, under suitable capacity and sampling assumptions, universal approximation of the Bayes-optimal graph predictor. Evaluation spans 26 node-classification graphs, 10 homogeneous link-prediction datasets, and 54 knowledge graphs, showing competitive or leading aggregate performance. Additional experiments examine joint-task transfer, compositional generalization, inference-time adaptation, architectural and prior ablations, and computational trade-offs.

Critical strengths
  1. Broad validation of a single pretrained model. WANDER uses one checkpoint across node classification, homogeneous link prediction, and knowledge-graph link prediction, with competitive or leading aggregate results on 26, 10, and 54 graphs, respectively. This breadth provides substantive evidence that a shared architecture can accommodate different feature spaces, relation schemas, and prediction tasks without sacrificing specialized performance.

  2. A unified interface with useful inference-time flexibility. The random-walk interface allows structural context to be adjusted without retraining. The long-range experiments and compute–performance analysis demonstrate practical benefits of this flexibility, while architectural and pretraining-prior ablations help substantiate the design. This makes the contribution valuable beyond simply supporting multiple tasks.

Critical weaknesses
  1. The experiments do not sufficiently isolate the benefits of unification and the random-walk interface. The joint-versus-single-task comparison matches task-specific updates but gives the joint model additional updates from other tasks, leaving its advantage under a matched total training budget unresolved. Likewise, component-removal ablations establish the importance of structural processing but do not compare random walks against message passing or adjacency-based attention under the same prior and training budget. These gaps limit the central explanation of why the proposed unified design is effective.

  2. The universality guarantee remains substantially disconnected from the implemented model. The proof relies on an injective multiset aggregation assumption that preserves proposal multiplicities, whereas the implemented softmax-normalized weighted average generally cannot preserve such counts. The paper acknowledges that the theorem concerns a more general framework, but this limits its explanatory value for the evaluated architecture. Consequently, the theoretical result provides weaker support for the practical model’s claimed expressive advantages than the presentation may suggest.

Questions for authors
  1. Joint-training attribution. The single-task variants receive the same number of task-specific updates as the joint model, but fewer total updates. Does joint training still improve performance when total training steps or compute are matched? Are the reported gains stable across independent pretraining runs? This would determine how strongly the results support positive transfer.

  2. Necessity of the random-walk interface. Removing structural updates establishes that structure is useful, but does not isolate the advantage of random walks. Under the same pretraining prior and comparable training budget, how does WANDER compare with a variant using message passing or adjacency-masked attention? This comparison would materially clarify the architectural contribution beyond combining existing components.

  3. Applicability of the universality theorem. Lemma 7 relies on preserving proposal multiplicities to construct identifiers, whereas softmax-normalized weighted averaging is invariant to duplicating the entire proposal multiset. Does the implemented consensus module satisfy A4 through an additional mechanism? If not, which theoretical expressive guarantees apply to the evaluated architecture?

  4. Conditions for posterior equivariance. The proof derives posterior equivariance from a prior over isomorphism classes. However, an observation mechanism that masks labels with class-dependent probabilities can break this symmetry. Is permutation compatibility of the observation mechanism an additional assumption? Please specify the condition under which the proposition holds.

7 comments
AuthorsOpenReview ↗

Response to reviewers questions (Part 1/3)

We thank the reviewer for their detailed and thoughtful feedback. We are pleased that they appreciate the breadth of our evaluation and the practical benefits of the unified random-walk interface. Below, we address each question and describe the additional experiments and theoretical clarifications.

Question 1: Joint-training attribution. The single-task variants receive the same number of task-specific updates as the joint model, but fewer total updates. Does joint training still improve performance when total training steps or compute are matched? Are the reported gains stable across independent pretraining runs? This would determine how strongly the results support positive transfer.

We thank the reviewer for raising this important question. We would first like to clarify that our single-task ablation is specifically designed to investigate positive transfer across tasks, addressing the following question:

“Does training the same architecture on additional tasks improve performance on the task of interest?”

To isolate this effect, we need to keep the number of target-task training updates identical between the single-task and jointly trained models, while introducing training updates from additional tasks for the jointly trained models. This design directly tests whether learning from other tasks benefits the task of interest.

The reviewer's suggested compute-matched comparison addresses a complementary question:

“Does joint training improve performance more than allocating the same additional training budget exclusively to the target task?”

This distinction is important. Our original experiments provide evidence of positive transfer across tasks, demonstrating that incorporating additional training tasks can improve target-task performance without requiring additional target-task data. This is particularly relevant for broad pretraining scenarios where task-specific training data may be limited.

Nevertheless, we agree that the compute-matched comparison provides valuable additional insight. We have therefore conducted a new experiment on homogeneous link prediction in which the single-task model receives the same total number of training steps as the jointly trained model.

ModelMean R@20 (%)
Joint training (three independent pretraining seeds)42.56 ± 1.22
LP-only, matched task-specific updates40.37
LP-only, matched total training steps41.32

The results show that additional single-task training recovers part of the performance gap (from 40.37% to 41.32%), but the resulting model still achieves lower performance than joint training (42.56%). This suggests that the benefits of joint training are not solely attributable to a larger number of training steps, although additional compute explains part of the improvement.

Overall, we believe these results strengthen our original finding: training on additional tasks benefits the target task when target-task training is held fixed, while the new experiment provides encouraging evidence that this advantage may persist even when total training steps are matched.

AuthorsOpenReview ↗

Response to reviewers questions (Part 2/3)

Question 2: Necessity of the random-walk interface. Removing structural updates establishes that structure is useful, but does not isolate the advantage of random walks. Under the same pretraining prior and comparable training budget, how does WANDER compare with a variant using message passing or adjacency-masked attention? This comparison would materially clarify the architectural contribution beyond combining existing components.

One of Wander’s central contributions is a unified structural interface supporting different graph schemas, including multiple relation types, across all three prediction settings. Our paper demonstrates how random walks can provide such a general interface within a single architecture. We do not claim that random walks are the only way to construct such an interface. However, simply replacing our random-walk interface with standard message passing or adjacency-masked attention would not yield an architecture supporting all three prediction settings. Developing a comparably general interface using these alternatives would require additional architectural design (encoding specific feature, label, and relation symmetries) rather than a direct component substitution. Consequently, the proposed comparison cannot be realized as a controlled ablation of Wander’s random-walk interface.

Beyond this generality, our random-walk interface offers two further advantages:

  • Test-time flexibility: Unlike conventional message-passing architectures with a fixed number of layers, Wander does not impose a fixed neighborhood radius. Its random-walk interface allows the model to explore graph structure at different distances and expand its structural context at inference time without retraining or modifying the architecture. This is particularly useful when transferring to graphs with different sizes and structural characteristics.
  • Structural expressivity: Random walks can capture structural patterns beyond the expressive power of standard 1-WL message passing. Appendix D.11 provides a targeted demonstration using a featureless, 3-regular graph whose nodes are classified according to their participation in triangles, four-cycles, five-cycles, or the remaining backbone. Standard 1-WL message passing cannot distinguish these nodes from structure alone. On this benchmark, Wander achieves 97.5% accuracy, compared with 63.3% for GCN and 67.4% for GraphPFN (which uses adjacency-masked attention), against a majority-class baseline of 64.0%.

Together, these considerations highlight three key advantages of our random-walk interface: generality across graph schemas and prediction settings, test-time flexibility, and structural expressivity.

AuthorsOpenReview ↗

Response to reviewers questions (Part 3/3)

Question 3: Applicability of the universality theorem. Lemma 7 relies on preserving proposal multiplicities to construct identifiers, whereas softmax-normalized weighted averaging is invariant to duplicating the entire proposal multiset. Does the implemented consensus module satisfy A4 through an additional mechanism? If not, which theoretical expressive guarantees apply to the evaluated architecture?

We thank the reviewer for identifying this mismatch. The implemented consensus has no additional mechanism for retaining absolute proposal multiplicities and therefore does not satisfy A4 as originally stated. However, absolute multiplicities are not necessary for the universality argument, and we have revised the assumption and proof accordingly (see p. 21-23).

Specifically, A4 now requires preserving the normalized empirical distribution of proposals (instead of the multiset). The revised Lemmas 5–6 (the identifier construction was previously Lemma 7) show that the fraction of node occurrences corresponding to walk starts, and the analogous fraction for first relation traversals, provide distinct identifiers with probability tending to one as the number of sampled walks increases. These frequencies are invariant to uniformly replicating the proposal multiset. The graph-reconstruction argument in Lemma 9 requires only the support of the proposal distribution, so it likewise does not require absolute multiplicities.

This weaker requirement is compatible with softmax consensus given sufficiently expressive proposal encoders. For any fixed finite sampling budget and walk length, the number of proposals is bounded. On a compact proposal domain, a sufficiently rich finite moment encoding uniquely determines such empirical distributions through averaging; equal confidence scores realize this averaging within softmax consensus. Overall, Theorem 2 remains a universality result with softmax normalization under the stated sampling and module-capacity assumptions. We appreciate the reviewer feedback pointing to this issue, which led us to further strengthen this result.

Question 4: Conditions for posterior equivariance. The proof derives posterior equivariance from a prior over isomorphism classes. However, an observation mechanism that masks labels with class-dependent probabilities can break this symmetry. Is permutation compatibility of the observation mechanism an additional assumption? Please specify the condition under which the proposition holds.

We thank the reviewer for pointing this out. Yes, permutation compatibility of the observation mechanism is an additional assumption that was missing from the original statement. Specifically, jointly relabeling a complete graph and its partial observation must leave the observation likelihood unchanged. Together with the invariant prior, this ensures posterior equivariance by Bayes’ rule. Masking probabilities tied to specific class identities can violate this condition.

We have now explicitly introduced this assumption in Section 3, added it to Proposition 1, and updated the proof in Appendix C.1 to explain why both prior weights and observation likelihoods are preserved under relabeling.

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

This paper proposes WANDER, a graph foundation model that uses random walks as a shared structural interface. A single pretrained checkpoint supports node classification, homogeneous link prediction, and knowledge-graph link prediction. Its random-walk configuration can be adjusted at inference time without updating the learned parameters. Experiments show competitive results across three graph tasks, benefits from joint pretraining, and evidence for compositional generalization. Additional ablation and efficiency analyses are provided in the appendices.

Critical strengths
  1. The unified framework demonstrates broad applicability across graph-learning tasks. A single pretrained checkpoint remains competitive across three prediction settings, supporting the practical value of the unified formulation.
  2. The compositional-generalization experiments further show that the model can jointly exploit node features and relation types whose processing capabilities were learned in separate training settings.
  3. The structural context is adjustable at inference time. The random-walk interface allows the model to change the structural information it collects by varying walk counts, walk lengths, and sampling strategies, without retraining.
Critical weaknesses
  1. The individual contributions of components in the stochastic structural update are not disentangled. Table 27 (Appendix D.14) shows removing this module degrades performance, but this ablation removes graph structure and cannot separate gains from confidence-weighted consensus and the bidirectional GRU processor.retraining variants under fixed random-walk sampling would clarify these design merits.
  2. Inference configurations (walk count, walk length, independent forward passes and aggregation) are scattered across Appendices D.2–D.5 and differ by task. A compact summary in the main experiment section or table captions would improve reproducibility.
Questions for authors
  1. With fixed random-walk sampling and retrained variants, how does replacing the confidence-weighted consensus or bidirectional GRU processor with simpler alternatives impact performance on the three tasks?
  2. Can you add a summary of walk count, walk length, inference samples and logit aggregation per task to the main text or table captions?
  3. Do the performance trends with varying walk counts and numbers of inference samples in Figure 5 also hold for knowledge-graph link prediction?
2 comments
AuthorsOpenReview ↗

Response to the reviewers questions

We thank the reviewer for their constructive feedback. We are pleased that they recognize Wander's broad applicability, compositional generalization, and inference-time flexibility. We address each question below.

Question 1: With fixed random-walk sampling and retrained variants, how does replacing the confidence-weighted consensus or bidirectional GRU processor with simpler alternatives impact performance on the three tasks?

Wander adopts the confidence-weighted consensus and bidirectional GRU processor from Flock [1], whose ablations found that replacing them with unweighted mean aggregation or a transformer processor, respectively, reduced overall knowledge-graph link-prediction performance (Table 5, [1]). These findings and ablations from the literature motivate our architectural choices. To address the reviewers' concern concretely, and to establish the benefits of these choices across all three tasks considered in our work, we are conducting additional ablations, retraining variants with each component replaced while keeping the random-walk sampling configuration fixed. We will incorporate the results into the paper once these experiments are complete.

[1] Kim et al.: Flock: A knowledge graph foundation model via learning on random walks. ICML 2026.

Question 2: Can you add a summary of walk count, walk length, inference samples and logit aggregation per task to the main text or table captions?

We thank the reviewer for this suggestion. We have added a “Walk sampling and inference” paragraph to the main experimental section, and Table 2 summarizes walk counts and lengths for node classification and homogeneous link prediction.

Question 3: Do the performance trends with varying walk counts and numbers of inference samples in Figure 5 also hold for knowledge-graph link prediction?

Yes, we observe a similar compute–performance tradeoff for knowledge-graph link prediction, although performance is more sensitive to reductions in walk count. This likely reflects the smaller default walk budgets used in these evaluations, which may make further reductions more consequential.

We evaluate the subset of knowledge graphs whose default configurations use at least four inference samples and a base walk count of at least four (see Table 14). For each dataset, we independently reduce the walk count, walk length, or number of inference samples to one-half and one-quarter of its default value, keeping all other settings fixed. The table below reports MRR and wall-clock speedup relative to the default configuration.

Reducing the number of inference samples offers the most favorable tradeoff: using one-quarter of the default samples yields a 3.47x speedup, with MRR decreasing only from 0.401 to 0.396.

SettingMRRSpeedup
Default0.4011.00×
Walk count half0.3901.13×
Walk count quarter0.3691.21×
Inference samples half0.3991.88×
Inference samples quarter0.3963.47×
Walk length half0.3931.33×
Walk length quarter0.3811.59×

Dear Reviewer, thank you again for your thoughtful feedback. Your suggestions helped us improve the paper. As the discussion period is about to end, we would be grateful to hear whether the inference summary in the main text and knowledge-graph experiments address your questions. The component ablations are still in progress. Is there anything else we could clarify that would help you feel confident recommending acceptance?

We appreciate the time you’ve put into reviewing our paper!

Comments on the paper

2 comments
AuthorsOpenReview ↗

New manuscript and summary of our responses to reviewers concerns

We thank all reviewers for their time and constructive feedback! We have uploaded a revised manuscript, with changes highlighted in blue. We summarize our responses to reviewer concerns:

  • Presentation (Reviewer mdGU): We expanded Section 5 to explain the implementation of each architectural component in greater detail. We also simplified Section 4 by replacing the former Theorem 1 and its associated notation with a direct explanation of the posterior-mixture interpretation.
  • Inference details (Reviewer rTj9): We added a paragraph on Walk Sampling and Inference to the experimental section, clarifying walk budgets, starting positions, and inference configurations.
  • Expanded evaluation (Reviewer mdGU): We substantially extended our experiments across all three prediction tasks, adding node-classification results on the full Pokec Regions and Web Topics datasets from GraphLand, link-prediction results on OGB-Collab, OGB-PPA, and OGB-Citation2, and knowledge-graph completion results on OGB-BioKG. Wander outperforms all evaluated baselines on both new node classification datasets, two of three link prediction datasets, and on OGB-BioKG.
  • Posterior equivariance (Reviewer cNKU): We clarified the conditions for posterior equivariance by explicitly requiring permutation compatibility of the observation mechanism, and updated Proposition 1 and its proof accordingly.
  • Expressivity of softmax-normalized consensus (Reviewer cNKU): We revised our universality proof to establish that the expressivity guarantees also apply to softmax-normalized consensus.
  • Pretraining analyses (Reviewers cNKU and jvLr): We added a compute-matched single-task comparison and evaluated joint-training variability across independent pretraining runs. We also introduced a preliminary ablation examining the effect of initially hiding graph structure on learning and transfer, providing further motivation for our staged pretraining curriculum (Appendix D.15).
  • Knowledge graph evaluation protocol (Reviewer jvLr): We analyzed potential source overlap between pretraining and evaluation datasets and additionally examined performance on datasets originating from different knowledge graph sources.

We provide detailed responses to each review below, including additional experimental results, theoretical clarifications, and discussions of our architectural design choices. We are also conducting further architectural ablations in response to the reviewers' suggestions.

We thank the reviewers again for their valuable feedback, which has helped us strengthen the paper's presentation, empirical evaluation, and theoretical foundations.

We thank all reviewers again for their time and thoughtful feedback. As the discussion period is drawing to a close, we would greatly appreciate any further thoughts on our responses and revisions. In particular, it would be helpful to know whether these have addressed your concerns or whether any questions remain that we could still clarify. Thank you again for engaging with our work!

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.