{"id":"5aefe9d1-ec30-4915-b802-2a3a3e2fd030","arxiv_id":"2501.12595","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"UIL aligns class-level graphons across environments plus representation-level invariance, improving OOD graph classification accuracy, but the convergence-to-minimal-stable-features proof is not valid as written.","lead":"Graph classifiers often fail when test data shifts, and invariant learning tries to fix that by finding stable graph substructures. This paper proposes UIL, which adds a graphon-based structural invariance term on top of semantic invariance to better isolate the label-causal parts of a graph.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 2 is unproven: the appendix proof treats the data-generation Bernoulli parameter p as if it were a trainable variable, so the central convergence claim rests on circular reasoning rather than a derivation.","rationale":"I read the paper as making two moves: (i) a modeling claim that class-conditional stable structures can be summarized by graphons that are invariant across environments, and (ii) a theoretical claim that minimizing structural graphon distance plus semantic invariance drives the extracted subgraph to the minimal stable set. The modeling claim (Assumption 1) is explicit and testable, and the empirical results in Table 2 are consistent across benchmarks, so this is not a trivial submission. My concern is with (ii). The appendix proof is the only support for Proposition 2, and it is internally incoherent: it assigns a Gaussian distribution to graphon estimates and then says minimizing the L2 distance between environment estimates forces the Bernoulli parameter p of the environmental features to zero. The loss in Eq. (4) is computed from the extracted masks; p is a property of the unobserved data-generation process. A rigorous argument would need to show that the minimizer of Eq. (8) over masks excludes environmental edges under identifiable conditions, and that gradient descent reaches that minimizer. Neither is shown. The paper also asserts without proof that the training-set minimal stable set equals the causal ground-truth subgraph (Definition 3 vs. Section 2.1). That equivalence is exactly what invariant learning needs to establish. The synthetic validation in Section 5.2 uses the same Bernoulli-p toy model as the theory, so it does not break the circularity. The empirical method may still work as a heuristic, and code is promised, but the central theoretical claim is unsupported. The reader's verdict of REJECT with high correctness risk is appropriate; this stress-test does not change it.","tokens_in":22524,"tokens_out":5520,"duration_ms":61518,"concrete_test":"Write down the exact optimization problem (8) with masks as the only trainable variables and p fixed by the generative model. Then construct a generative process in which W_se is identical across training environments (e.g., environmental edges appear with probability p = 0.5 in every environment) and W_st is a fixed motif graphon; show that L_str = 0 even when the stable mask includes all environmental edges, and that L_suf + L_sem can also be minimized, so the loss cannot distinguish G_st from G_st ∪ G_se. Run UIL on this process and measure the ROC-AUC of the masks against the true G_st; if precision does not approach 1 while L_str = 0, Proposition 2's convergence claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Proposition 2: with the objective in Eq. (8), the estimated stable feature G_hat_st approaches the minimal stable feature G_st indefinitely. The proof in Appendix A.2 does not establish this. It defines the estimated stable graphon as W_hat_st = W_st + W_se ⊙ (1 − W_st), models W_hat_st(i,j) ∼ N(W_st(i,j) + p(1−W_st(i,j)), εp), and then states that minimizing ||W_hat^e_st − W_hat^{e'}_st||_F 'propels the value of p towards zero.' But p is the parameter of the Bernoulli distribution of the stable-environmental features in the data-generating process; it is not a parameter of f = ω ∘ h ∘ Φ and it does not appear in Eq. (8). The trainable quantities are the masks M^x and M^a. Minimizing the Frobenius norm of a zero-mean random matrix cannot drive its variance parameter to zero unless that parameter is an optimization variable. The proof therefore asserts the desired conclusion: unless the masks already exclude the environmental edges, the loss does not know about p. The paper also equates Definition 3's MinStable(Y), defined by conditional expectation under the training distribution, with the causal ground-truth subgraph, without a causal identifiability argument. Because the synthetic validation in Section 5.2 is generated from exactly the same toy model (Bernoulli-p stable-environmental edges plus SYN-b stable motifs), it does not provide independent evidence that structural invariance recovers causal subgraphs in general. The empirical improvements in Table 2 may be genuine, but the theoretical guarantee that is the paper's stated contribution is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes UIL, a graph-classification method that enforces invariance in both graph space and representation space. A feature separator produces stable and environmental subgraph masks; class-wise stable graphons are estimated from the masked stable features, and the method minimizes Frobenius distances between these graphons across inferred environments (structural invariance), together with sufficiency, regularization, and semantic-invariance losses. The central theoretical claim (Proposition 2) is that, under the full objective in Eq. (8), the estimated stable features converge to the minimal stable feature set G_st. Experiments on SYN, Motif, CMNIST, Molhiv, and Molbbbp report accuracy and AUC gains over ERM and several invariant-learning baselines, with additional analyses of stable-feature precision and cut distances.","tokens_in":22835,"tokens_out":8691,"duration_ms":86789,"significance":"If Proposition 2 were rigorously established, the paper would make a valuable contribution by showing that graphon-level structural invariance complements semantic invariance and helps isolate causal subgraphs for OOD generalization. The framework is clearly described, the code is released, and the experimental comparison is broad, including synthetic and real benchmarks. However, the central convergence proof is invalid as written, and the synthetic experiment used to validate it is generated from the same toy model as the theory. The empirical accuracy improvements in Table 2 are consistent with the method's usefulness, but they do not by themselves establish the paper's mechanistic claim that structural invariance recovers the minimal stable features. The contribution is therefore not yet supported at the level required for publication.","major_comments":[{"comment":"The proof of Proposition 2 is not valid. It defines the estimated stable graphon as W_hat_st = W_st + W_se ⊙ (1 - W_st), models W_hat_st(i,j) as a Gaussian N(W_st(i,j) + p(1 - W_st(i,j)), eps p), and then asserts that minimizing the Frobenius distance between W_hat^e_st and W_hat^{e'}_st in Eq. (4) propels the value of p towards zero. However, p is the parameter of the Bernoulli distribution of stable-environmental features in the data-generating process; it is not a parameter of f = omega ∘ h ∘ Phi and it does not appear in the objective in Eq. (8). The trainable quantities are the masks M^x and M^a. Minimizing the Frobenius norm of a zero-mean random matrix cannot drive its variance parameter to zero unless that parameter is an optimization variable. The proof therefore assumes the desired conclusion: unless the masks already exclude the environmental edges, the loss does not know about p. Since Proposition 2 is the paper's central convergence claim, this gap is load-bearing.","section":"Appendix A.2 (proof of Proposition 2)"},{"comment":"The paper equates MinStable(Y), defined in Definition 3 as a minimal subset of features satisfying E_Ptr(Y|G') = E_Ptr(Y|G), with the causal ground-truth G_st. This equivalence is asserted rather than derived. Under the training distribution, stable-environmental features can be predictive of Y, so the minimal sufficient subgraph need not coincide with the causal subgraph; an identifiability argument based on interventions or an explicit causal model is required. Without such an argument, the target of the structural invariance loss is ambiguous, and Proposition 2 cannot be read as a statement about recovering the true causal structure.","section":"Definition 3 and Section 4"},{"comment":"The synthetic validation in Section 5.2 is generated from exactly the toy model used in the theoretical discussion: SYN-b motifs augmented with Bernoulli(p) stable-environmental subgraphs, with p = 0.001 at training and p = 0.003 at test. Because this is the same data-generating process assumed in the proof of Proposition 2, the experiment cannot provide independent evidence that structural invariance recovers causal subgraphs in general graph distributions. It demonstrates behavior under the paper's own assumptions, not the general convergence claim stated in Section 4.","section":"Section 5.2"},{"comment":"The convergence claim also rests on Assumption 1, which postulates that the minimal stable features and the estimated stable features are generated by graphons, and on the implicit assumption that the same graphon is shared across environments. These are substantive modeling assumptions about the data-generating process rather than consequences of the optimization. The paper provides no evidence, beyond the synthetic construction, that real-world stable structures such as molecular functional groups satisfy this graphon-invariance condition. Consequently, the scope of Proposition 2 is narrower than the general statement in the abstract and introduction.","section":"Assumption 1 and Definition 5"}],"minor_comments":[{"comment":"There is a typo 'grouth-truth' in the phrase 'the stable features identified by the semantic invariance might surpass the scope of the grouth-truth stable features'; it should read 'ground-truth'.","section":"Section 2.2"},{"comment":"The display of Eq. (7) contains malformed bracket notation in the submitted version; please clean up the formatting so the expectation and summation are unambiguous.","section":"Eq. (7)"},{"comment":"The citation to CAL in 'causal features [41? ]' appears as a broken or unresolved reference; please correct it.","section":"Section 2.1"},{"comment":"Figure 6(a) reports results on SYN-0.1 and SYN-0.9, but Table 4 only lists SYN-b base; please define these datasets and explain how they relate to the SYN-b construction.","section":"Table 4 and Figure 6(a)"},{"comment":"The visualization of captured stable features would be easier to interpret if the ground-truth stable features were marked in every panel, not only in some, and if the caption stated which dataset and environment are shown.","section":"Figure 5"}],"recommendation":"reject","confidential_remarks":"To the editor: the central theoretical claim is not just missing a step; the Appendix A.2 proof conflates a fixed data-generation parameter p with an optimization variable, and the Section 5.2 experiment is built from the same toy model. I do not see how a routine revision can repair Proposition 2 without either a substantially new theoretical analysis or a reframing of the paper as an empirical study with a much softer convergence claim. The empirical results are promising and the code is released, so if the authors can supply a rigorous proof or reposition the contribution, a resubmission may be viable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this one. First, the empirical recipe is genuinely useful: UIL consistently beats strong baselines across GOOD and OGB graph OOD benchmarks, and the design—adding a cross-environment graphon-distance penalty on extracted stable subgraphs to the usual semantic invariance—is a clean, plausible inductive bias. Second, the theoretical guarantee is not proven. The appendix proof of Proposition 2 treats the data-generation Bernoulli parameter p as if minimizing the structural loss drives it to zero, but p is not an optimization variable and does not appear in Eq. (8). The trainable quantities are the masks; the loss cannot know about p unless the masks already exclude the environmental edges. That is circular.\n\nWhat's genuinely new: prior invariant graph learning for graphs has mostly enforced invariance in representation space. The idea of enforcing structural invariance by aligning graphons of estimated stable features across environments is not in the cited prior work (DIR, CAL, GREA, CIGA). The empirical section is thorough: 10 seeds, multiple benchmarks, ablations, sensitivity analyses, and a direct graphon-distance check showing that UIL's learned stable features have smaller cross-environment distances than baselines. That is real work, and the gains in Table 2 are consistent enough to take seriously.\n\nThe soft spots are the theory and the validation of the theory. The circular proof is load-bearing: the paper's stated contribution is identifying minimal stable features, and Proposition 2 is the only formal support for the claim that structural invariance recovers the causal subgraph. The synthetic experiment in Section 5.2 is generated from exactly the same toy model as the theory, so it cannot independently validate the theory. The paper also equates the training-distribution minimal stable set with the causal ground-truth subgraph without a causal identifiability argument, and Assumption 1 is a strong modeling assumption about graphon-generating stable features. These are not minor quibbles; they undermine the central claim. The method may still work as a heuristic—I'm not convinced the empirical gains are fake—but the paper as written overclaims.\n\nWho is this for? Anyone working on GNN OOD generalization or invariant graph learning. The empirical recipe is worth trying, and the failure mode is instructive for the community. It deserves a serious referee, but the referee should expect major revision: either supply a correct proof, or reframe Proposition 2 as a conjecture/empirical motivation and lean on the experimental evidence.","headline":"Solid empirical recipe for graph OOD with the graphon-distance regularizer, but the proof of the central convergence claim is circular; worth a careful referee, not acceptance as is.","tokens_in":23419,"tokens_out":1853,"would_cite":true,"duration_ms":21620,"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 enforcing structural invariance in graph space—matching class-level graphons across environments—alongside semantic invariance lets GNNs recover minimal stable features and generalize out of distribution.","keywords":["invariant learning","graph classification","out-of-distribution generalization","graph neural networks","graphon","structural invariance","semantic invariance","minimal stable features"],"falsifier":"Construct a synthetic graph classification task where the causal stable subgraph for each label is drawn from a different graphon in each training environment (labels still fully determined by the subgraph), while environmental subgraphs are identical across environments; if UIL's extracted stable subgraphs still match ground truth better than semantic-only baselines, the assumption survives, but if it collapses to ERM-level accuracy and precision, the graphon-invariance premise is refuted.","tokens_in":22256,"feed_emoji":"🔗","tokens_out":5277,"duration_ms":54114,"temperature":0.7,"pith_summary":"This paper argues that invariant graph learning has been enforcing invariance in the wrong place: representation-space (semantic) losses alone can mistake 'stable-environmental' subgraphs—features that happen to be stable within the training environments but have no causal link to the label—for true stable features. To fix this, the authors propose Unified Invariant Learning (UIL), which adds a structural invariance principle in graph space: for each label, the stable subgraphs extracted from different environments should be generated by the same graphon, so UIL estimates a stable graphon per class and environment and penalizes their distance. Combined with the usual semantic invariance loss, this joint objective is claimed to drive the extracted stable features toward the minimal stable (causal) features, and the paper gives a theoretical statement (Proposition 2) plus experiments showing better OOD accuracy than existing methods.","feed_headline":"Graphon matching lifts graph OOD accuracy to 70.9 percent","feed_subtitle":"Adding structural invariance—same class pattern across environments—finds true causal subgraphs that semantic-only methods miss.","key_machinery":"The load-bearing object is the stable graphon: a symmetric measurable function describing, for a class of graphs sharing a label, the probability that an edge of the extracted stable subgraph exists between two nodes. UIL estimates graphons as step-function matrices, aligns graphs by node degrees under the stable edge mask, and enforces structural invariance by minimizing the Frobenius-norm distance between stable graphons across inferred environments; a weak regularity lemma justifies approximation in cut norm. The semantic branch trains the classifier on the extracted stable subgraph, regularizes mask sparsity with a learnable stable ratio, and adds a loss that combines each stable representation with environmental representations so predictions are invariant to environment; environments are inferred from K-means clusters of environmental representations.","core_discovery":"The paper's central claim is that invariant graph learning fails when constrained to representation space alone, because features that are stable only within training environments—'stable-environmental features'—can satisfy semantic invariance without being causal. UIL adds a structural invariance principle: for each label, the estimated stable subgraphs across environments should be generated by the same graphon, so the framework estimates a stable graphon per class and environment and penalizes their cut distance (implemented as Frobenius distance between step-function matrices). Under Assumption 1 that minimal stable and estimated stable features are graphon-generated and the graphons are environment-invariant, Proposition 2 states that optimizing the combined objective (sufficiency, structural, and semantic losses) drives the estimated stable features toward minimal stable features indefinitely. Empirically, UIL reports 70.90 average accuracy versus 66.11 for ERM across Motif, CMNIST, Molhiv, and Molbbbp, and higher AUC for recovering ground-truth stable subgraphs than semantic-only baselines.","pith_inferences":["A testable extension: apply the structural-invariance loss to node classification or link prediction where stable features are graphon-like; if the same convergence holds, UIL's principle generalizes beyond graph-level tasks.","The framework depends on training environments being inferred reliably; when K-means clusters do not align with true environments, the graphon-matching penalty could push together graphons from different causal regimes. One could replace K-means with a differentiable environment estimator and test whether gains persist.","The claim suggests a simpler criterion for dataset design: distribution shifts that alter the generative pattern of stable features are out of reach, so benchmarks for invariant graph learning should be constructed with environment-invariant causal graphons, otherwise no invariant method can succeed.","Because the structural loss is computed in graph space, the learned stable graphon itself may serve as an interpretability tool: a class-level summary of the causal structure a GNN relies on."],"forward_implications":["If UIL is right, adding a graphon-matching loss to any subgraph-selection GNN can recover causal subgraphs that semantic-invariance-only methods miss.","OOD graph classification on synthetic and molecular benchmarks should improve substantially over ERM and over invariant baselines, with the reported gap (70.90 vs 66.11 average) being repeatable.","The stable ratio can be learned rather than fixed, because structural invariance supplies the signal that prevents the mask from absorbing stable-environmental features.","Graphon distance across environments becomes a diagnostic: smaller cross-environment cut distance of extracted stable subgraphs indicates better recovery of minimal stable features.","The unified objective gives a template for combining graph-space and representation-space invariance, applicable beyond classification to any graph task with stable substructures."],"supporting_citations":[{"why":"Supplies the invariant risk minimization principle that UIL extends from Euclidean data to graph classification.","marker":"[2]"},{"why":"Provides the weak regularity lemma, cut norm, and cut distance used to define and justify structural invariance over graphons.","marker":"[28]"},{"why":"Provides the GOOD graph out-of-distribution benchmark and baseline result tables used for comparison.","marker":"[12]"},{"why":"Supplies the OGB molecular datasets (Molhiv, Molbbbp) used in the real-world experiments.","marker":"[15]"},{"why":"Defines invariant rationales and minimal stable features, the baseline DIR that UIL builds on and must beat.","marker":"[53]"},{"why":"Introduces causal attention and the CAL baseline, a semantic-invariance-only approach that UIL contrasts with.","marker":"[41]"},{"why":"Introduces GREA, an environment-based augmentation baseline that UIL compares against.","marker":"[26]"},{"why":"Provides DisC, a disentangled causal substructure baseline for graph OOD generalization.","marker":"[8]"},{"why":"Provides the Gromov-Wasserstein barycenter method used to estimate graphons and compute cut distances in practice.","marker":"[54]"}],"fun_headline_variants":["Graphon matching unifies structural and semantic invariance for OOD","Structural invariance via graphons improves graph OOD to 70.9%","Same graphon per class across environments finds true causal subgraphs","UIL: matching graphons per class improves OOD generalization to 70.9"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument leans on the assumption that, for every set of graphs sharing a label, both the true causal subgraphs and the extracted ones can be generated by graphons, and that these graphons do not change across environments; if stable causal structure is not graphon-like or environment-specific structural variation exists, the structural loss cannot tell stable features from stable-environmental ones.","fun_headline_variants_meta":{"raw":{"variants":["Graphon matching unifies structural and semantic invariance for OOD","Structural invariance via graphons improves graph OOD to 70.9%","Same graphon per class across environments finds true causal subgraphs","UIL: matching graphons per class improves OOD generalization to 70.9"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001215,"raw_usage":{"total_tokens":5037,"prompt_tokens":1021,"completion_tokens":4016,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":3937}},"tokens_in":637,"tokens_out":4016,"duration_ms":27962,"temperature":1.0,"reasoning_tokens":3937,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:00:25.492371+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a synthetic graph classification task where the causal stable subgraph for each label is drawn from a different graphon in each training environment (labels still fully determined by the subgraph), while environmental subgraphs are identical across environments; if UIL's extracted stable subgraphs still match ground truth better than semantic-only baselines, the assumption survives, but if it collapses to ERM-level accuracy and precision, the graphon-invariance premise is refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the weak regularity lemma, cut norm, and cut distance used to define and justify structural invariance over graphons."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the GOOD graph out-of-distribution benchmark and baseline result tables used for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the OGB molecular datasets (Molhiv, Molbbbp) used in the real-world experiments."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines invariant rationales and minimal stable features, the baseline DIR that UIL builds on and must beat."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces GREA, an environment-based augmentation baseline that UIL compares against."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides DisC, a disentangled causal substructure baseline for graph OOD generalization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Gromov-Wasserstein barycenter method used to estimate graphons and compute cut distances in practice."}],"review_version":1}