{"id":"fcfec131-85f5-47d6-adbf-5741a45b9d52","arxiv_id":"2505.05785","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Learnable random-walk path sampling with a kernel-density mutual information loss improves node classification under distribution shifts, outperforming prior graph OOD methods on seven benchmarks.","lead":"This paper proposes a graph AI method that learns which paths to walk through a network so predictions stay stable when the data distribution shifts over time or across domains. It reports accuracy gains over existing out-of-distribution methods on citation, social, and web datasets, with a claimed average improvement of 3.87%.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (2) defines transition probabilities as raw cosine similarities, which are unnormalized and can be negative; the random-walk sampler and the OOD guarantees built on it are not well-defined as stated.","rationale":"The paper's central claim is that learnable random walk sequences, not invariant topology or spectrum, should instantiate invariant knowledge for graph OOD generalization, and that LRW-OOD realizes this by sampling paths from a learnable transition matrix and training with a KDE-based MI loss. For this claim to be coherent, Eq. (2) must define a genuine probability distribution over each node's neighbors. It does not: cosine similarity is not normalized over the neighbor set and can be negative, so the random walk sampler is undefined as stated. The reader's weakest assumption identifies exactly this issue, and I agree it is the most load-bearing concern. The theoretical guarantees in Theorems 3.1–3.2 are stated about an encoder optimized under this undefined sampler, so the proofs cannot currently establish sufficiency or invariance. I do not treat this as evidence of dishonesty; it is an underspecification that could be resolved by reporting the exact normalization and releasing code. The experimental results are extensive and consistently favor LRW-OOD, so rejection is not warranted; the appropriate disposition remains conditional acceptance pending this specification. Hence I recommend no change to the reader's conditional verdict.","tokens_in":16391,"tokens_out":5666,"duration_ms":58674,"concrete_test":"Inspect or reproduce the implementation of Eq. (2) and verify that the transition weights used for sampling satisfy w_{ij} ≥ 0 and Σ_{j∈N(i)} w_{ij} = 1 for all nodes in a batch. Then rerun Cora, WebKB, and ogb-ArXiv with the explicit normalized transition kernel P_{ij} = softmax_j(τ cos(z_i, z_j)) over neighbors, using the same hyperparameters as Table 1. If the reproduced accuracies differ by more than the reported standard deviations, the unstated normalization is material to the claimed 3.87% improvement; if the released code uses a different normalization, the paper's central description should be amended accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Eq. (2), the paper sets Pr_{v_j∈N(v_i)}(v_i→v_j) = cos(z_i, z_j), where z = GNN(A, X). As written, the right-hand side is a scalar in [-1,1] that does not sum to 1 over the neighbor set N(v_i) and can take negative values; it is therefore not a valid transition probability kernel. No softmax, degree-based normalization, temperature, clipping, or other device is specified in §3.2 or Appendix A. This is load-bearing because every downstream component — sampling k paths {p_i^r}, constructing path embeddings h_i^r via Eq. (3), and the KDE-based MI losses in Eqs. (4)–(5) — is defined conditionally on these transition probabilities. If the sampler cannot sample from a probability distribution, then the path encoder and the losses operate on objects whose generative process is unspecified. The theorems in §3.3 and Appendix A inherit the problem: an encoder trained on walks from an undefined sampling distribution cannot be shown to satisfy sufficiency or invariance. A related secondary issue is that Eq. (4) evaluates a pointwise density-ratio term rather than the summed KDE mutual-information estimator used in Lemma A.1, so the proof of Theorem 3.1 also needs an explicit estimator and consistency argument. The empirical comparisons may still stand if the implementation silently uses a softmax normalization, but that normalization is part of the method and must be reported or released.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper argues that existing graph OOD methods that treat invariant topology or spectrum as carriers of invariant knowledge are fragile, and proposes that learnable random walk sequences instantiate invariant knowledge. It introduces LRW-OOD with a GNN-based LRW sampler that builds a cosine-similarity transition matrix, samples k random walk paths per node, encodes them with an MLP, and trains with a KDE-based MI loss combining sufficiency maximization and risk-extrapolation variance minimization. The manuscript states Theorem 3.1 (optimizing the loss yields sufficiency and invariance), Theorem 3.2 (the optimized encoder solves the worst-case OOD objective), and Theorem 3.3 (complexity bounds), and reports experiments on seven datasets with nine baselines, claiming an average 3.87% improvement.","tokens_in":16712,"tokens_out":5551,"duration_ms":52513,"significance":"The perspective that invariant knowledge can be carried by learnable walk distributions rather than fixed topology or spectrum is interesting and potentially useful for OOD node classification. The experimental evaluation is broad: 10-run means with standard deviations, seven datasets spanning synthetic, cross-domain, and temporal shifts, nine baselines, ablations, and hyperparameter sensitivity, and the results are consistently in favor of the proposed model. The complexity analysis is also a nice practical addition. However, the theoretical guarantees claimed in Theorems 3.1 and 3.2 are not established by the current derivations, and the transition-probability definition is incomplete, so the significance of the paper currently rests on the empirical results.","major_comments":[{"comment":"The transition rule in Eq. (2) does not define a valid probability distribution: cos(z_i,z_j) lies in [-1,1], need not sum to one over N(v_i), and can be negative. Because the LRW sampler, the path embeddings in Eq. (3), and the KDE-based MI losses in Eqs. (4)-(5) all depend on sampling from this transition matrix, the method and the proofs in Section 3.3 are undefined as stated. Please specify the normalization (e.g., softmax, temperature, degree-based renormalization) and how negative similarities are handled; this choice is part of the method, not an implementation detail.","section":"Section 3.2, Eq. (2)"},{"comment":"Eq. (4) defines LMI_Suff as a pointwise kernel-density ratio, but a mutual information estimate is a sum or integral over sample points of the log-ratio weighted by the joint density; the expression shown is not an MI estimate. Lemma A.1 claims convergence of 'the kernel density estimation as defined in equations 4', but no consistent estimator is actually specified. Please replace Eq. (4) with a proper KDE-based MI estimator, such as an average over the observed samples, and provide the bandwidth conditions under which Lemma A.1 holds.","section":"Section 3.2, Eq. (4) and Appendix A, Lemma A.1"},{"comment":"The proof of Theorem 3.1 uses the claim 'I(y,e) ≤ I(y,e|h)' at the start of the invariance argument. The identity I(Y;E) = I(Y;E|H) + I(Y;H) - I(Y;H|E) shows this inequality is not generally true, and Eq. (12) writes I(y,e|h) as KL(Pr(y|h,e)||Pr(y|h)), which omits the expectation over h and the correct conditional distribution of e. Consequently Theorem 3.1 is not proven as stated.","section":"Appendix A.1, proof of Theorem 3.1"},{"comment":"Theorem 3.1 largely restates the construction: the loss in Eq. (5) is deliberately composed of an MI-sufficiency term and a risk-extrapolation variance term, so 'if the loss is optimized then the encoder satisfies sufficiency and invariance' is close to a tautology unless the proof establishes that the optima of these terms truly correspond to the conditions y=f*(G_e)+σ and Pr(y|e)=Pr(y). As it stands, the theorem adds little beyond the definition and the questionable derivations above.","section":"Section 3.3, Theorem 3.1"},{"comment":"The proof of Theorem 3.2 assumes that sufficiency implies the loss of f* is minimized for any graph G'_e and any comparator f, and that invariance implies 'the loss of f* is minimized under any graph with arbitrary environment'; neither implication follows from the stated conditions. The jump from sufficiency and invariance to the worst-case objective in Eq. (1) requires additional assumptions about the class of environments and the loss, which are not given.","section":"Appendix A.2, proof of Theorem 3.2"}],"minor_comments":[{"comment":"The caption contains the typo 'corss-domain' and should read 'cross-domain'; also, the very large standard deviations for DGNN and MARIO on WebKB suggest that the comparison could benefit from a more careful presentation.","section":"Table 1 caption"},{"comment":"There is a typo 'chain low of mutual information' that should be 'chain rule of mutual information', and 'Jenson Inequality' should be 'Jensen's inequality'.","section":"Appendix A.1"},{"comment":"The lemma states that the KDE estimator 'converges in probability' but Eq. (6) asserts almost-sure convergence; additionally, the proof cites Glivenko-Cantelli for the empirical CDF, which is not directly a pointwise KDE density convergence result. Please clarify the mode of convergence and the required assumptions on the bandwidth.","section":"Appendix A, Lemma A.1 and Eq. (6)"},{"comment":"The text says 'each experiment is repeated 10 times, and the average performance is reported,' but the tables report mean ± std; please clarify how the standard deviation is computed and how random seeds are handled.","section":"Section 4.1"},{"comment":"The abstract claims an average improvement of 3.87% over state-of-the-art baselines, while Section 4.2 reports about 3.1% (GCN) and 1.0% (GAT) on Table 1; please state where the 3.87% figure is computed.","section":"Abstract and Section 4.2"},{"comment":"No code is released, and the unstated normalization in Eq. (2) makes the method hard to reproduce; please release the implementation or provide all implementation details.","section":"Reproducibility"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's theoretical section is the weak point; the empirical study is solid. If the authors reframe the main contribution as an empirically validated method and fix the transition-normalization issue, the paper may be publishable. Given the current emphasis on Theorems 3.1 and 3.2, I do not think the claims hold as stated. Additionally, the paper leans heavily on Wu et al. [29] for the two OOD conditions yet does not clearly delimit the new theoretical contribution beyond that prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: this paper argues that learnable random walk sequences, not topology or spectrum, are the right carrier of invariant knowledge for graph out-of-distribution generalization. That is a genuinely new perspective, and the authors back it with an actual method (LRW-OOD) plus consistent empirical gains across seven datasets with 10-run means and standard deviations. The empirical claim seems believable.\n\nWhat it does well: the idea of parameterizing the transition matrix instead of fixing the degree-normalized adjacency matrix is natural and underexplored in the graph OOD literature. The KDE-based MI sufficiency loss, while rough around the edges, is a reasonable alternative to histogram-based estimators because it is differentiable. The ablations and sensitivity analyses are honest about which components matter; the ablation shows the LRW encoder itself is what carries the performance, which supports the paper's central claim.\n\nNow the soft spots, in proportion. The load-bearing problem is Eq. (2). It defines the transition probability from v_i to v_j as cos(z_i, z_j). Cosine similarity is not normalized over the neighbor set and can be negative. As written, this is not a valid probability distribution, and the random walk sampler is undefined. The entire method and all downstream theory assume this sampler. If the implementation uses a softmax or some other normalization, that is part of the method and must be stated. This is not a minor omission; it is the core mechanism.\n\nThe theory is also much weaker than it looks. Theorem 3.1 claims the optimized encoder satisfies sufficiency and invariance, but the proof basically assumes the loss does what it is designed to do and then argues by contradiction with an optimal parameter h*. That is circular. The sufficiency condition from Wu et al. is restated, and the loss in Eq. (5) is explicitly built from MI sufficiency maximization and risk extrapolation minimization; showing that the optimized encoder satisfies those conditions is close to restating the construction. The KDE pointwise expression in Eq. (4) is not the summed MI estimator used in Lemma A.1, so the consistency argument does not directly apply.\n\nA few smaller things: no code is released, and several baselines OOM on the larger datasets, which makes the 3.87% average improvement less clean than it sounds. On the cross-domain GAT results the gain over the sub-optimal baseline is about 1%, not 3.87%.\n\nWho is this for? Researchers working on graph OOD who want a new angle on invariant knowledge representation. The empirical method is worth seeing; the theory needs to be rewritten, not just patched.\n\nMy recommendation: this deserves a serious referee, not a desk reject. The novelty is real and the experiments are extensive. But the authors should be asked to specify the transition normalization, fix the MI estimator, soften the theoretical claims to what is actually proven, and release code. Conditional accept after major revision is the right call.","headline":"Sound empirical idea and a genuinely new invariant carrier for graph OOD, but Eq. (2) underspecifies the sampler and the theory is mostly restatement; worth a serious referee after fixes.","tokens_in":17253,"tokens_out":1370,"would_cite":false,"duration_ms":15301,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that learnable random walk sequences, rather than invariant topology or spectrum, are the right carrier of invariant knowledge for graph OOD generalization, and that LRW-OOD realizes this with a learnable transition…","keywords":["graph out-of-distribution generalization","learnable random walk","mutual information","kernel density estimation","graph neural network","invariant representation","node classification","distribution shift"],"falsifier":"Compute the row sums of the transition matrix $[\\cos(z_i,z_j)]$ over each node's neighbors on Cora (or any benchmark graph) with the trained encoder; if any row does not sum to one, the random walk sampler in Eq. (2) has no valid probability distribution and the reported results must rely on an unstated normalization or a different mechanism.","tokens_in":16204,"feed_emoji":"🔀","tokens_out":11178,"duration_ms":112923,"temperature":0.7,"pith_summary":"The paper argues that when graphs shift between training and test time, the invariant signal is best carried by learnable random-walk sequences rather than by invariant graph topology or spectrum. LRW-OOD samples paths with transition probabilities set by the cosine similarity between learned node embeddings, encodes each path with an MLP, and trains with a kernel-density-estimation mutual-information loss that enforces sufficiency (the label is predictable from the path embedding) and invariance (the label distribution is stable across environments). The authors prove that an encoder optimized this way satisfies both conditions and is the solution to the worst-case graph OOD objective. This matters because GNNs degrade under distribution shifts, and on seven benchmarks the paper reports an average accuracy gain of 3.87% over nine graph OOD baselines using either GCN or GAT backbones.","feed_headline":"Beat graph OOD baselines by 3.87% with learned random walks","feed_subtitle":"The paper replaces invariant topology or spectrum with random-walk paths shaped by a mutual-information loss.","key_machinery":"The load-bearing object is the learnable random walk: a sampler whose transition probability from node $v_i$ to neighbor $v_j$ is $\\cos(z_i,z_j)$, where $z$ is produced by a GNN backbone, so topology and node features enter the path distribution together. Each sampled path $p^r_i$ is encoded by an MLP into an LRW embedding $h^r_i$, and a KDE-based mutual-information loss (sufficiency maximization plus variance-minimizing risk extrapolation) shapes those embeddings. This replaces the fixed degree-normalized adjacency matrix used as the transition matrix in prior random-walk GNNs and is the mechanism through which the paper's theoretical guarantees and empirical gains are supposed to flow.","core_discovery":"On its own terms, the paper establishes that invariant knowledge in graph OOD generalization can be instantiated as the probability of a random walk moving to a semantically similar neighbor, and that sampling $k$ such paths per node and encoding them produces representations that carry the label information while discarding environment-specific correlations. The contribution is LRW-OOD: a learnable random walk encoder whose transition matrix is parameterized by a GNN (initialized from cosine similarities), a path encoder that maps each sampled path to an embedding, and a KDE-based mutual-information loss combining MI sufficiency maximization with risk extrapolation minimization. Theorem 3.1 states that minimizing this loss yields an encoder satisfying the sufficiency and invariance conditions, and Theorem 3.2 states that such an encoder solves the worst-case formulation in Eq. (1). The experiments across synthetic, cross-domain, and temporal shift datasets support the paper's claim that the approach outperforms the compared baselines.","pith_inferences":["Editorial inference: as written, Eq. (2) uses raw cosine similarities as transition probabilities; because these values can be negative and need not sum to one over a node's neighbors, a softmax or other normalization is almost certainly required for the sampler to be well-defined, and comparing the stated version with an explicitly normalized version would clarify the actual mechanism.","Editorial inference: random-walk paths of bounded length are a restricted class of subgraphs, so the paper's perspective connects naturally to subgraph- and motif-based invariant learning; future work could ask which path lengths and shapes carry the invariant signal for a given shift.","Editorial inference: the KDE bandwidth and covariance choices in Eq. (4) are likely to affect finite-sample behavior, so a controlled comparison against histogram-based or neural mutual-information estimators on small graphs with known true mutual information would test whether the loss itself, rather than the overall architecture, drives the gains.","Editorial inference: path embeddings trained to be invariant could double as an OOD detection signal, since paths that remain predictive of the label across environments are invariant while environment-specific paths stand out as spurious; the paper does not explore this use."],"forward_implications":["If the central claim is correct, graph OOD generalization no longer requires an invariant topology or an invariant spectrum; any graph with shared semantic structure can be handled by learning transition probabilities.","The KDE-based mutual-information loss gives a differentiable way to push toward the sufficiency condition, replacing the KL-divergence approximations used by earlier graph OOD methods.","The two-stage design means the LRW encoder can be trained once and then combined with standard GCN or GAT classifiers, so the claimed gains transfer across backbone architectures.","The complexity bound of $O(nd^2(l_1+l_2)+nksd)$ time and $O(nd(l_1+l_2))$ space suggests the approach remains practical for larger graphs, including the temporal ogb-ArXiv benchmark.","Across the evaluated synthetic, cross-domain, and temporal datasets, the paper reports an average improvement of 3.87% over nine graph OOD baselines."],"supporting_citations":[{"why":"It supplies the worst-case OOD objective and the sufficiency/invariance conditions that LRW-OOD's theory extends.","marker":"[29]"},{"why":"It is the invariant-topology baseline (CIT) whose core assumption, that topology stays invariant, LRW-OOD argues is not guaranteed.","marker":"[31]"},{"why":"It is the invariant-spectrum baseline (SpCo) that treats low-frequency components as invariant, the view LRW-OOD replaces.","marker":"[14]"},{"why":"It is the causal-intervention baseline (CaNet) used in comparisons and one source of the OOD formulation lineage.","marker":"[28]"},{"why":"It is the graph-contrastive baseline (MARIO) used for comparison and placed in the same OOD formulation lineage.","marker":"[40]"},{"why":"It is the generative-risk-minimization baseline (GRM) using KL-divergence loss, the approximation the KDE-MI loss replaces.","marker":"[27]"},{"why":"It represents the earlier random-walk convention of fixing the transition matrix as the degree-normalized adjacency matrix, which LRW-OOD makes learnable.","marker":"[32]"},{"why":"It is the path-aware random-walk method with fixed transition probabilities that LRW-OOD contrasts with its learnable sampler.","marker":"[22]"},{"why":"It supplies the kernel-density-estimation approach for mutual information used in the sufficiency loss.","marker":"[15]"},{"why":"It provides kernel-based mutual-information estimation used to motivate the differentiable MI objective.","marker":"[12]"}],"fun_headline_variants":["Learnable random walks improve graph OOD by 3.87%","Graph OOD gains 3.87% via learned random walks","Rethinking graph OOD with learnable path sampling","Random walk paths beat invariant topology for graph OOD","LRW-OOD: KDE loss steers random walks for distribution shifts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the raw cosine similarities $\\cos(z_i,z_j)$ between learned node embeddings can serve as random-walk transition probabilities, but the paper never specifies how these values are normalized or made nonnegative, so the sampler in Eq. (2) is not a well-defined probability distribution as written.","fun_headline_variants_meta":{"raw":{"variants":["Learnable random walks improve graph OOD by 3.87%","Graph OOD gains 3.87% via learned random walks","Rethinking graph OOD with learnable path sampling","Random walk paths beat invariant topology for graph OOD","LRW-OOD: KDE loss steers random walks for distribution shifts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000459,"raw_usage":{"total_tokens":2305,"prompt_tokens":955,"completion_tokens":1350,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":571,"completion_tokens_details":{"reasoning_tokens":1262}},"tokens_in":571,"tokens_out":1350,"duration_ms":11347,"temperature":1.0,"reasoning_tokens":1262,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:55:55.509375+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the row sums of the transition matrix $[\\cos(z_i,z_j)]$ over each node's neighbors on Cora (or any benchmark graph) with the trained encoder; if any row does not sum to one, the random walk sampler in Eq. (2) has no valid probability distribution and the reported results must rely on an unstated normalization or a different mechanism.","supporting_citations":[{"cited_title":"Learning invariant representations of graph neural networks via cluster generalization","cited_arxiv_id":null,"evidence_quote":"It is the invariant-topology baseline (CIT) whose core assumption, that topology stays invariant, LRW-OOD argues is not guaranteed."},{"cited_title":"Graph out-of-distribution generalization via causal intervention","cited_arxiv_id":null,"evidence_quote":"It is the causal-intervention baseline (CaNet) used in comparisons and one source of the OOD formulation lineage."},{"cited_title":"Mario: Model agnostic recipe for improving ood generalization of graph contrastive learning","cited_arxiv_id":null,"evidence_quote":"It is the graph-contrastive baseline (MARIO) used for comparison and placed in the same OOD formulation lineage."},{"cited_title":"PathMLP: Smooth Path Towards High-order Homophily","cited_arxiv_id":"2306.13532","evidence_quote":"It represents the earlier random-walk convention of fixing the transition matrix as the degree-normalized adjacency matrix, which LRW-OOD makes learnable."},{"cited_title":"Estimation of mutual information using kernel density estimators","cited_arxiv_id":null,"evidence_quote":"It supplies the kernel-density-estimation approach for mutual information used in the sufficiency loss."}],"review_version":1}