acceptodds
Under review as a conference paper at ICLR 2027

Instance Indistinguishability and the Limits of Graph Learning: A Local-Global Perspective

Abstract

Graph-level prediction infers global properties from local neighborhoods, but it may fail when classes differ globally while local observations remain indistinguishable. We ask when interactions among local observations reveal a global difference and whether graph learners can exploit it. Planted Model RB makes this question controllable by varying problem size and constraint density. Although satisfiability distinguishes planted from random instances above the classical threshold, every individual constraint has the same distribution in both models. To characterize this transition, we derive the low-degree likelihood-ratio projection, showing that the first informative component comes from constraint pairs sharing variables and giving its exact finite-sample strength. We prove further that, when this pairwise signal vanishes, all polynomial statistics up to logarithmic degree are asymptotically uninformative, yielding a local-global separation that widens with problem size. Experiments corroborate this size dependence and reveal a growing gap between the shared-variable signal available in the complete instance and the signal extracted by the evaluated GNNs. This gap narrows substantially when the graph representation preserves shared-variable relations, but not under generic structural augmentation or increased architectural expressivity. Our theoretical and empirical findings therefore indicate that learning a global distinction from local observations depends on both sufficient overlap among those observations and a representation that preserves the structure through which the distinguishing signal emerges.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Neural Networks, Instance Indistinguishability, Planted Constraint Satisfaction Problems, Low-Degree Analysis

Reviews

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

The paper studies discrimination between mixed planted Model RB and null Model RB to investigate global distinguishability, low-degree statistical visibility, and empirical graph learnability. It identifies the complete-instance likelihood ratio with the normalized solution count, derives an exact low-degree likelihood-ratio norm, and shows that the one-constraint marginals are identical. The first nonzero component arises from pairs of constraints with overlapping scopes. Its strength, Λ2\Lambda_2, equals the maximum squared null-standardized mean separation over degree-at-most-two statistics on the complete observation, with the observed scopes available as side information.

Under the stated domain-growth and constraint-count conditions, Λ2→0\Lambda_2\to0 implies ∣L≤D∣22→1|L^{\le D}|_2^2\to1 for polynomial degrees D=O(log⁡n)D=O(\log n). Together with the satisfiability threshold, this establishes a separation between global distinguishability and low-degree mean separation. Experiments with binary constraints compare a shared-variable pair score, GIN, other graph learners, and representation and architecture interventions across instance sizes and densities. The reported results favor relation-aligned features over the evaluated generic features and architecture changes. These theoretical results concern complete-instance polynomial statistics, not a direct lower bound for a particular GNN.

Critical strengths
  1. Exact finite-instance signal characterization and a logarithmic-degree extension. The identity ∣L≤2∣22−1=Λ2|L^{\le2}|_2^2-1=\Lambda_2, its variational interpretation, and the constructive quadratic optimizer give the diagnostic signal a precise mathematical meaning. The extension to logarithmic polynomial degree shows that the vanishing-signal result is not confined to one hand-crafted detector.

  2. A controlled experimental framework with theoretically justified negative controls. Size and density sweeps, label shuffling, and independent local planting address identifiable aspects of the generation and evaluation procedures. In particular, Lemma B.4 proves that independent local planting recovers the null law exactly, giving that negative control a clear interpretation. This does not validate every other comparison, but it is a useful component of the experimental design.

Critical weaknesses
  1. The encoding comparison does not establish the claimed separation of input information and signal extraction.

The scope-only factor graph should have population AUC 1/21/2. Appendix D.5 describes this input as a variable–constraint incidence graph with two node-type indicators and no relation tables. Definitions 2.2–2.3 give the two classes the same scope distribution. For a fixed parameter cell, this input therefore has the form Ginc=h(S)G_{\mathrm{inc}}=h(S), with $ P_0^S=P_1^S\quad\Longrightarrow\quad P_0^{G_{\mathrm{inc}}}=P_1^{G_{\mathrm{inc}}}. $ Conditional on a scoring function trained and selected independently of the test observations, its scores on fresh null and planted instances consequently have the same distribution. For independent test draws, $ \operatorname{AUC}(f) =\Pr(f(G_1)>f(G_0)) +\tfrac12\Pr(f(G_1)=f(G_0)) =\tfrac12. $ This is an absence-of-input-information result, not a limitation of GIN capacity. Yet Table E.7 reports above-chance factor-graph AUCs, and Section 4.3 and Appendix E.6 interpret these results as a benefit of exposing variable–constraint organization. For example, the (α,p)=(0.6,0.5), n=40(\alpha,p)=(0.6,0.5),\ n=40 row reports 68.72% for the factor graph and 54.51% for the anonymous graph, averaged over the selected hard densities and model seeds. Finite-sample fluctuations and post hoc selection can affect these reported averages; they do not establish population-level discriminative information in a scope-only input. The actual implementation may contain an omitted input, or the interpretation may need revision. This needs clarification before the encoding ladder can support the claimed mechanism.

A targeted check is to generate a null and a planted test instance from each common scope realization, using the same node and constraint ordering for the paired inputs. If the input truly depends only on those scopes, then under a fixed deterministic evaluation protocol the two classes have identical multisets of input tensors and scores, giving empirical AUC exactly 1/21/2.

The aligned-feature input is also insufficiently specified. Appendix D.5 describes aligned and generic features as functions of GG alone, but Eqs. (D.3)–(D.4) use a partition Π\Pi of value nodes into variable blocks, exclude within-block edges, and count edges separately by neighboring block. As written, their construction uses Faligned=ψ(G,Π)F_{\mathrm{aligned}}=\psi(G,\Pi). Appendix D.2 says that unique recovery of this partition has not been established; it does not prove that recovery is impossible. The missing point is whether preprocessing reads the generator-provided partition or computes an equivalent feature map from the anonymous adjacency alone. The absence of a uniqueness proof does not itself prove that these features cannot be computed from the graph; the feature-computation procedure needs to resolve the issue. If the meanings of node indices are used, this metadata should be stated explicitly.

Moreover, the features include the per-variable quadratic contraction TkT_k. Their gains can therefore reflect both access to variable grouping and targeted statistical precomputation, rather than message passing alone. This is a legitimate intervention, but not an isolated test of the GNN's ability to recover the same statistic from the same input. A grouping-only comparison and a pooling/readout model receiving the identical normalized features without message passing would help separate these effects. Graph-wise normalization means that simply summing the provided features should not be assumed to reproduce the raw pair score.

These issues matter because Figure 7 and Appendix E.6 use the encoding ladder to identify the source of the recovery, rather than merely to report predictive performance.

  1. The scale and data controls do not separate limited training data from representational limitations.

Appendix D.7 uses 2000 instances per class for $n\in ${15,25}, 1500 for n=40n=40, and 1000 for n=60n=60. With the 60% training split, this gives 1200, 900, and 600 training instances per class. Thus, problem size increases while the training sample size decreases. The observed crossover describes this protocol, but its entire drift cannot be attributed to instance size or representation alone without a cross-size comparison using a fixed training sample count.

The four-cell data-scale control in Table E.6 is informative but does not resolve this confounding across the main size sweep. For the two hard cells, Table E.6 reports improvements of 6.19 and 12.17 AUC percentage points when training data increase from 500 to 4000 examples per class. These results support the statement that the tested increase does not close the gap. They do not establish the stronger conclusion in Appendix E.4 that additional data fail where the model cannot express the discriminative function, or that the hard cells do not have too few examples. The later discussion correctly acknowledges that fitting training labels does not establish the best-generalizing GIN solution; the interpretation should remain consistent with that qualification.

Finally, the three model seeds use the same data split, and the hard-cell groups are selected using the reference GIN's own outcomes. These choices are disclosed and are not intrinsically invalid. They make the error bars and grouped comparisons descriptive, however, rather than a clean separation of model randomness, instance-sampling uncertainty, and selection effects. Paired cell-level differences and independent-instance verification would be more informative than pooled means for determining which intervention consistently recovers the gap.

Questions for authors
  1. Does the factor graph in Table E.7 contain only scope incidence and node-type indicators, or does its implementation use any relation-dependent input? Please give its exact construction. Under the scope-only definition, how do you reconcile the population zero-information property with the interpretation of the reported gains? Does the paired-scope test described above produce identical inputs and scores?

  2. Can the aligned features be recomputed, up to the corresponding node permutation, after arbitrary node relabeling using only the anonymous adjacency and base degree features, without the original variable partition? If so, please explain the construction. Otherwise, please identify the metadata supplied during preprocessing. Is there a comparison that separates access to the partition from precomputation of TkT_k, and separates those features from the contribution of message passing?

  3. Appendix D.4 distinguishes the exact optimizer S2⋆S_2^\star in Eq. (C.36) from TpairT_{\mathrm{pair}} in Eq. (D.2), while Figure 4 and Figure E.6 use an optimal-degree-two label. Which statistic was implemented for those curves? Figure 5 and Table E.6 already identify a deduplicated relation-level score; please reconcile the remaining labels and specify the corresponding information level. Can the calibration interpretation be checked against the actual implemented statistic rather than treating the exact-optimizer SNR as an AUC ceiling?

  4. Is there a cross-size comparison using a fixed number of training instances per class, evaluated on independent test-instance realizations? If not, will the authors limit the scale and data conclusions to the observed protocol rather than use them to exclude a finite-sample explanation or establish an expressivity limitation?

7 comments

Thank you for your careful and constructive review. We appreciate your recognition of the exact signal characterization, the logarithmic-degree result and the theoretically justified negative control, as well as the concrete tests you propose. We address the input definitions, statistical calibration and training and evaluation controls below.

Preview

  • Weakness #1 & Question #1: Factor construction and paired-scope check.
  • Weakness #1 & Question #2: Partition metadata, grouping and readout controls.
  • Question #3: Implemented score and Gaussian calibration.
  • Weakness #2 & Question #4: Fixed sample counts, scaling and independent-instance evaluation.
  • Conclusion.

Response to Weakness #1 & Question #1

Weakness #1 & Question #1: Specify the factor graph construction and explain the reported AUC in light of the zero-information property of a scope-only input. Does fixing the scopes and node order give identical paired tensors and scores?

A: We appreciate the paired scope test you proposed, which gives a direct check of whether the planted and null inputs are identical. When the encoding is a function of the scopes alone, the shared scope law gives population AUC 1/21/2 for a fixed score evaluated on fresh instances. Pairing the scopes also gives identical input tensors and scores for each pair under deterministic evaluation.

The factor implementation in the available code uses nqnq value nodes and mm constraint nodes. For each forbidden tuple (x,y)(x,y) of constraint aa on variables (i,j)(i,j), it adds bidirectional edges between cac_a and each of (i,x)(i,x) and (j,y)(j,y). It retains repeated edges and adds clique edges within each variable block. The node features are normalized degree and a constraint node indicator. The edges and their multiplicities encode counts of forbidden tuple endpoints for each constraint. These counts preserve marginal information that can vary with the relations and carry the shared variable signal studied in the paper.

We implemented the test with the same scopes and node ordering in each pair. All 64 pairs in each cell had identical tensors under the scope encoding. A fixed degree squared score gave identical scores in those pairs and AUC 0.500 in both cells. The relation graph tensors differed in all 64 pairs in each cell, showing directly where the forbidden tuple information enters the input.

Pairs with common scopesScope graph tensor mismatchesAUC of the fixed scope probeRelation graph tensor mismatches
n=40,r=1.73n=40,r=1.736400.50064
n=60,r=2.16n=60,r=2.166400.50064

The archived run summaries reproduce the 68.72% AUC reported for the factor variant in Table E.7. The available loader and the paired test establish the behavior of the construction described here. The archived summaries do not contain the original tensors or a source snapshot for those runs. The explicit construction and the paired check identify which input is subject to the scope invariance result.


Response to Weakness #1 & Question #2(a)

Weakness #1 & Question #2(a): Can preprocessing recover the aligned features after arbitrary node relabeling from anonymous adjacency and degree features alone? If the implementation uses the original indexing or partition, specify the metadata it receives.

A: Thank you for asking which information is used to construct the aligned features. The preprocessing uses the original value node indexing and obtains the variable block by integer division of each index by qq. Thus the supplied information is the adjacency GG together with the partition Π\Pi, and the feature map is Faligned=ψ(G,Π)F_{\rm aligned}=\psi(G,\Pi). The implementation requires this partition to reproduce the features after an arbitrary relabeling.

We checked the effect of transporting the partition with the graph. For the null instance in each of the 64 pairs at n=40n=40 and in each of the 64 pairs at n=60n=60, we applied a permutation to the nodes, transported the partition, recomputed the features, and compared them in the original order. The maximum absolute difference was zero. This follows from the construction, since the permutation preserves the corresponding between block edge counts.

The grouping control in the next response evaluates the contribution of this supplied partition before adding the aligned feature vector.

Response to Weakness #1 & Question #2(b)

Weakness #1 & Question #2(b): Separate the effects of supplying the partition, precomputing the aligned features and applying message passing. Compare against a readout using the same normalized features.

A: Thank you for proposing these comparisons. We evaluated a grouping-aware learner with normalized degree, the same learner with the full aligned feature vector (S,S2,T)(S,S^2,T), and a grouped readout with per-node nonlinear transformations that receives exactly the same aligned node features and uses the same hierarchical pooling. The GIN and the readout use 38,469 and 38,466 parameters, respectively. All arms share the underlying instances and split identities. The grouping intervention changes the pooling interface, and the feature comparison holds that interface fixed.

Input and learnern=40,r=1.73n=40,r=1.73n=40,r=2.60n=40,r=2.60n=60,r=2.16n=60,r=2.16
Anonymous GIN52.58 ± 2.9157.47 ± 2.8551.31 ± 1.95
Grouping-aware GIN53.28 ± 2.7184.79 ± 11.8850.94 ± 1.89
Grouping-aware GIN with aligned features99.97 ± 0.0299.98 ± 0.0299.89 ± 0.12
Grouped readout with identical aligned features87.22 ± 1.4196.17 ± 0.8882.57 ± 2.21
GIN with aligned features, standard pooling99.86 ± 0.0999.98 ± 0.0299.54 ± 0.27

Each entry is test AUC (%) over three independently generated datasets. We average three model initializations within each dataset and report the mean and sample SD across datasets. All arms within a cell share the same underlying instances and train, validation, and test identities.

The paired differences below are in AUC points, with SD across dataset-level differences.

Gain from grouping over anonymous GINAligned features added to grouping-aware GINMessage passing with identical aligned features
n=40,r=1.73n=40,r=1.730.70 ± 0.3646.69 ± 2.7212.74 ± 1.41
n=40,r=2.60n=40,r=2.6027.32 ± 12.0215.19 ± 11.893.81 ± 0.88
n=60,r=2.16n=60,r=2.16-0.37 ± 0.6448.95 ± 1.9117.32 ± 2.12

At n=40,r=1.73n=40,r=1.73 and n=60,r=2.16n=60,r=2.16, grouping alone stays close to the anonymous reference and supplying aligned features produces the largest gain. At n=40,r=2.60n=40,r=2.60, grouping also yields a large improvement. The identical-feature readout demonstrates that aligned features are useful through nonlinear feature aggregation, even though feature-wise centering makes their simple sums approximately zero. The grouped aligned GIN improves further in each cell, with a gain from 3.81 to 17.32 points over that readout. The contrasts quantify the full aligned feature intervention and the additional contribution of the evaluated graph learner.


Response to Question #3(a)

Question #3(a): Which statistic is used in Figure 4 and Figure E.6? Reconcile the labels with the exact optimizer in Eq. C.36 and the implemented pair score in Eq. D.2, and specify what information each comparison uses.

A: Thank you for asking how the evaluated detector relates to the exact optimizer. The relation score markers in Figure 4 and the reference bars in Figure E.6 use the shared-variable marginal pair score TpairT_{\rm pair} from Eq. D.2. Eq. C.36 gives the exact finite-instance optimizer S2⋆S_2^\star, which additionally accounts for repeated scopes.

For binary constraints sharing exactly one variable, the marginal inner product is the corresponding exact quadratic contribution up to scale. For repeated scopes, the exact optimizer includes a centered contraction over the full relation table. This is the additional contribution described in Appendix D.4.

The comparisons below distinguish shared-variable pair score on the complete relation observation, deduplicated scope-level pair score, partition available, exact quadratic optimizer including repeated scopes, and GIN on the anonymous graph. In particular, tuple deduplication does not remove the partition supplied to the L2L_2 score.

Additional local CPU diagnostic. We used 200 independent calibration instances per class to estimate moments and 400 independent test instances per class to measure AUC in each cell, with the score direction fixed. The marginal score is a fixed positive rescaling of the implemented TpairT_{\rm pair}, so its AUC is unchanged. We use the generator's rounded values of qq and mm and the resulting peffp_{\rm eff}. AUCs are in percent, and the gain is the difference between the exact and marginal AUCs in percentage points.

Mean repeated-scope pairs, testTpairT_{\rm pair} AUCExact S2⋆S_2^\star AUCDeduplicated AUCExact score gain
n=40,r=1.73n=40,r=1.7341.3492.8094.0592.821.25
n=40,r=2.60n=40,r=2.6094.3898.2398.8298.640.59
n=60,r=2.16n=60,r=2.1679.3192.9893.7693.690.78

On the same test instances, the exact score gains 0.59 to 1.25 AUC points over the marginal score. This comparison quantifies the contribution of the full table term at the tested densities.

Response to Question #3(b)

Question #3(b): Can the Gaussian calibration be tested using the actual implemented score and its class moments? What is the status of the exact optimizer's SNR-based reference?

A: Thank you for suggesting a calibration check for the implemented score. We measured its class means and variances on a separate calibration set and used them to predict AUC on fresh test instances.

For an approximately Gaussian score with means μ0,μ1\mu_0,\mu_1 and variances v0,v1v_0,v_1, the relevant prediction is Φ((μ1−μ0)/v0+v1)\Phi((\mu_1-\mu_0)/\sqrt{v_0+v_1}). This differs from Φ(Λ2/2)\Phi(\sqrt{\Lambda_2/2}), which uses the exact optimizer's null variance and an additional equal-variance approximation. The latter is a theoretical reference coordinate, not a certified ceiling for arbitrary graph classifiers.

The submitted residual analysis compares measured shared-variable AUC with the displayed reference, reporting gridwise mean absolute errors of 1.35 to 2.70 AUC points. We supplemented that comparison with a direct moment calibration of the implemented marginal score.

Additional local CPU diagnostic. We used 200 independent calibration instances per class to estimate moments and 400 independent test instances per class to measure AUC in each cell, with the score direction fixed. The marginal score is a fixed positive rescaling of the implemented TpairT_{\rm pair}, so its AUC is unchanged. We use the generator's rounded values of qq and mm and the resulting peffp_{\rm eff}. The table gives AUCs in percent. The Gaussian column uses the moments of each score, and Δ\Delta is test AUC minus that prediction in percentage points.

nnrrScorev1/v0v_1/v_0Test AUC95% CIGaussianΛ2\Lambda_2 ref.Δ\Delta
401.73Marginal1.20992.80[90.98, 94.39]93.8794.62-1.07
401.73Exact1.10894.05[92.52, 95.41]94.8394.62-0.78
402.60Marginal1.53498.23[97.55, 98.90]98.2499.23-0.01
402.60Exact1.39498.82[98.23, 99.29]98.6599.23+0.17
602.16Marginal1.40892.98[91.04, 94.64]92.8893.14+0.10
602.16Exact1.43093.76[92.23, 95.17]94.2593.14-0.49

For the implemented marginal score, the absolute differences between the moment prediction and measured AUC are 1.07, 0.01 and 0.10 points. The intervals use 500 stratified bootstrap resamples of the test set with the calibration moments held fixed.


Response to Weakness #2 & Question #4

Weakness #2 & Question #4: Does the crossover move across sizes when training instances per class are held fixed and performance is evaluated on independent test-instance realizations?

A: Thank you for asking for this control. We ran a cross-size comparison at n∈{15,25,40,60}n\in\{15,25,40,60\} with 600 training instances per class at every size. For each size and density, we generated three independent dataset realizations. Each realization has separately generated training, validation and test sets, with 200 validation and 400 test instances per class. Thus each realization has its own held-out test instances. We trained three GIN model seeds on each realization and averaged their test AUCs within that realization.

We linearly interpolated the 0.70 AUC crossing on each realization's mean curve. The table reports the mean and sample standard deviation across the three dataset realizations. For comparison at a common density, it also gives test AUC at 3rcr3r_{\rm cr}.

nnCrossing r0.70/rcrr_{0.70}/r_{\rm cr}AUC at 3rcr3r_{\rm cr} (%)
151.48 ± 0.0395.61 ± 0.46
252.48 ± 0.1381.54 ± 1.23
403.63 ± 0.2456.01 ± 4.06
60Not reached51.79 ± 1.45

The crossing moves to higher density from n=15n=15 to n=25n=25 to n=40n=40 in all three realizations. At n=60n=60, all three curves stay below 0.70 at every evaluated density through 3rcr3r_{\rm cr}, the largest density evaluated at that size. The rightward shift therefore persists with identical training counts and independently generated test sets. Table E.6 complements this comparison by varying the training count at a fixed size and density. The fixed-count result establishes the size trend at 600 training instances per class. The dependence of that trend on larger training sets remains an empirical question.

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

This paper studies the relationship between global distinguishability, low-degree statistical evidence, and empirical graph learnability using planted Model RB. Although individual constraints have identical distributions under the null and planted models, interactions between constraints sharing variables provide a distinguishing signal. The paper derives the exact low-degree likelihood-ratio norm and optimal quadratic signal-to-noise ratio, and proves logarithmic-degree invisibility when the pairwise signal vanishes under the stated assumptions. Experiments compare a shared-variable detector with GNNs and examine how graph representations and architectural interventions affect the observed performance gap.

Critical strengths
  1. The theoretical characterization is substantive and interpretable. The exact finite-sample analysis in Theorems 3.2 and 3.4 identifies both the strength and the structural source of the first informative component. Theorem 3.8 extends the analysis beyond quadratic statistics, establishing a meaningful separation between global distinguishability and low-degree mean separation.
  2. The problem setting provides useful experimental control. The null and planted models share individual constraint marginals, scope distributions, and basic instance parameters. This makes the setting well suited to studying how information emerges through interactions between constraints, while allowing problem size and constraint density to be varied systematically.
  3. The paper includes a substantial diagnostic effort. The size and density sweeps, alternative backbones, negative controls, data-scale experiments, and representation and architecture comparisons provide several complementary views of the phenomenon. The presentation also distinguishes polynomial degree from GNN depth and WL order, and explicitly acknowledges important limits of the empirical conclusions.
Critical weaknesses
  1. The source of the empirical extraction gap is not sufficiently resolved. The shared-variable detector uses the variable/scope partition, whereas the anonymous GNN does not explicitly receive this information. As acknowledged in Appendix D.2 and Figure E.3, the deduplication controls retain this partition and therefore do not isolate the effects of the complete instance-to-graph conversion. The aligned-feature intervention also requires variable blocks and precomputes the relevant quadratic contraction before feature normalization (Eqs. D.3-D.4). However, Appendix D.5 describes these features as functions of the graph alone without explaining how the required partition is obtained from the anonymous input. Consequently, the experiments leave access to relational metadata and the difficulty of learning the relevant computation entangled. A comparison with matched partition information, separating the provision of that information from the provision of the analytically derived features, would make the explanation of GNN behavior substantially more convincing.
  2. The factor-graph gains need to be reconciled with the stated input definition. Appendix D.5 describes the factor-graph input as variable-constraint incidence with node-type indicators and no relation tables. Under the model in Section 2.2, the scope distribution is identical in both classes. Such an input therefore has identical class-conditional distributions and carries no population-level classification signal. Nevertheless, Figure 7 and Table E.7 report an intermediate improvement from this representation, including a mean AUC of 68.72% for the hard cells at n = 40 in the α = 0.6, p = 0.5 grid. Finite-sample fluctuations are possible, but the stated construction does not explain the reported pattern or its interpretation as a benefit of exposing constraint organization. The authors should specify any relation-dependent features or connections used in the actual implementation and reconcile them with the input definition before drawing conclusions from this comparison.
Questions for authors
  1. Does the extraction gap mainly arise from missing variable-partition information or from difficulty learning the shared-variable computation?
  2. How does the factor-graph model achieve the reported gains when its stated input has the same distribution in both classes?
3 comments

Thank you for the detailed and technically precise assessment. We appreciate your recognition of the exact finite-instance results, the logarithmic-degree extension and the substantial diagnostic effort. Your two questions identify the key empirical attribution, which we address by specifying the inputs and separating the controls.

Preview

  • Weakness #1 & Question #1: Partition access, precomputation and message passing.
  • Weakness #2 & Question #2: Relation-dependent factor construction and scope-only control.
  • Conclusion.

Response to Weakness #1 & Question #1

Weakness #1 & Question #1: Does the extraction gap arise from access to the variable partition, precomputation of the shared-variable statistic, or the learner? Please separate these effects with matched comparisons.

A: Thank you for distinguishing access to the variable partition from computation of the quadratic feature. We supplemented the representation ladder with matched comparisons on identical instances, with 600 training, 200 validation and 400 test instances per class. The grouping-aware GIN receives Π\Pi through hierarchical pooling. We then keep the same learner and add (S,S2,T)(S,S^2,T) computed from (G,Π)(G,\Pi). A third model receives those identical aligned features and uses the same hierarchical pooling with per-node transformations in place of message passing.

Input and learnern=40,r=1.73n=40,r=1.73n=40,r=2.60n=40,r=2.60n=60,r=2.16n=60,r=2.16
Anonymous GIN52.58 ± 2.9157.47 ± 2.8551.31 ± 1.95
Grouping-aware GIN53.28 ± 2.7184.79 ± 11.8850.94 ± 1.89
Grouping-aware GIN with aligned features99.97 ± 0.0299.98 ± 0.0299.89 ± 0.12
Grouped readout with identical aligned features87.22 ± 1.4196.17 ± 0.8882.57 ± 2.21
GIN with aligned features, standard pooling99.86 ± 0.0999.98 ± 0.0299.54 ± 0.27

Each entry is test AUC (%) over three independently generated datasets. We average three model initializations within each dataset and report the mean and sample SD across datasets. All arms within a cell share the same underlying instances and train, validation, and test identities.

In the two cells with near-chance anonymous AUC, n=40,r=1.73n=40,r=1.73 and n=60,r=2.16n=60,r=2.16, the grouping-aware intervention changes AUC by 0.70 and −0.37 points. Adding the aligned features under the same grouped architecture contributes 46.69 and 48.95 points. At n=40,r=2.60n=40,r=2.60, grouping alone contributes 27.32 points, and the aligned features add another 15.19. The strength of the grouping intervention therefore depends on the cell, while aligned features improve the grouped learner in all three. The identical-feature readout reaches 82.57 to 96.17%, showing that the precomputed features expose substantial usable evidence, and the grouped aligned GIN adds 3.81 to 17.32 points with message passing. The aligned GIN and the readout use 38,469 and 38,466 parameters, respectively. Their matched comparison measures the contribution of the evaluated message passing layers at almost identical parameter counts.

Response to Weakness #2 & Question #2

Weakness #2 & Question #2: What information does the factor graph use, and how can the reported 68.72% AUC be reconciled with identical scope distributions in the two classes?

A: Thank you for asking what information the factor input contains. A graph computed solely from the scopes has the same distribution in both classes. The factor construction available in our code also uses the forbidden tuples, which gives a concrete source of relation information.

The factor implementation in the available code uses nqnq value nodes and mm constraint nodes. For each forbidden tuple (x,y)(x,y) of constraint aa on variables (i,j)(i,j), it adds bidirectional edges between cac_a and each of (i,x)(i,x) and (j,y)(j,y). It retains repeated edges and adds clique edges within each variable block. The node features are normalized degree and a constraint node indicator. The edges and their multiplicities encode counts of forbidden tuple endpoints for each constraint. These counts preserve marginal information that can vary with the relations and carry the shared variable signal studied in the paper.

We tested these two constructions using 64 planted and null pairs in each of two cells. Within each pair we fixed the scopes and node ordering. The scope tensors were identical throughout, and a fixed degree squared score gave identical paired scores and AUC 0.500. The relation graph tensors differed in every pair.

Pairs with common scopesScope graph tensor mismatchesAUC of the fixed scope probeRelation graph tensor mismatches
n=40,r=1.73n=40,r=1.736400.50064
n=60,r=2.16n=60,r=2.166400.50064

The archived run summaries reproduce the 68.72% AUC reported for the factor variant in Table E.7. The available loader and the paired test establish the behavior of the construction described here. The archived summaries do not contain the original tensors or a source snapshot for those runs.


Changes in the revision (shown in blue):

  • Section 4.3 and Appendices D.5 and I.4. We specify the variable partition used in aligned preprocessing. The matched comparisons vary grouping, aligned precomputation, and message passing on the same instances. They include a readout with identical aligned features, the same pooling, and nearly the same parameter count.
  • Figure 7, Table E.7, and Appendix I.3. We identify the archived factor variant explicitly, document the relation-dependent incidences in the available implementation, and report the paired scope check. Appendix I.3 explains what can be verified about the historical 68.72% AUC from the archived results.

Conclusion

Thank you for proposing the matched comparisons. The new results quantify the contribution of aligned features when the grouping interface is held fixed and the additional gain from message passing at nearly identical parameter counts. The paired scope test also identifies how the input construction determines which evidence is available to the learner.

AuthorsOpenReview ↗

Friendly Reminder

Dear Reviewer 8HcV,

This is a friendly reminder that we greatly value your input on our rebuttal. Your comments have been extremely helpful in improving our paper.

The matched comparisons you suggested help distinguish the effects of variable grouping, aligned features, and message passing on the same instances. We also report the paired scope test, which gives identical inputs and scores when the encoding uses only the scopes, and describe the relation-dependent inputs in the available factor implementation.

As the discussion period closes on Nov. 18 (AoE), we would welcome any feedback on whether our response addresses your concerns. If it has clarified the points you raised, we would appreciate your taking the new evidence into account when updating your assessment. If any questions remain, we would be glad to address them.

Thank you for your time.

Best regards,
Authors of Submission #9120

Reviewer_2Ss3OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the limitations of Graph Neural Networks (GNNs) in distinguishing graphs that appear similar locally but differ globally. Using planted Model RB, the authors investigate when differences between null and planted satisfiable instances can be detected mathematically and whether GNNs can learn them. They also compare different GNN architectures and graph representations empirically. They show that global differences can be detectable even when low-degree statistics cannot distinguish the instances. Their experiments suggest that the evaluated GNNs struggle to extract available information, while representations preserving relevant structural relations improve performance.

Critical strengths
  • The paper addresses an interesting and important question regarding the limitations of GNNs in learning local-global information.
  • The theoretical results appear mathematically sound and provide a rigorous analysis.
  • The experiments are extensive, covering different problem sizes, GNN architectures, and graph representations, and provide useful comparisons with the theoretical findings.
Critical weaknesses
  • Presentation and Clarity: Sections 2 and 3 are difficult to follow, as definitions, propositions and theorems are introduced with little to none motivation or interpretation of their importance. The paper often moves directly from one mathematical statement to another without explaining why it is needed. Furthermore, the paper assumes familiarity with Model RB, planted CSPs, and low-degree analysis, making it difficult to follow for readers without this specific background.
  • The paper explains that the theoretical results do not directly apply to GNNs, and that the connection is mainly explored through experiments. Could the authors elaborate on whether these theoretical results could also help establish limitations of GNNs, rather than only low-degree statistics?
Questions for authors

See limitations.

4 comments

Thank you for your thoughtful review. We appreciate your recognition of the important local-global question, the rigor of the theoretical analysis and the extensive experiments. Below we explain the mathematical development and its connection to the learning study.


Response to Weakness #1

Weakness #1: Explain the motivation and significance of the definitions and results in Sections 2 and 3 for readers unfamiliar with Model RB, planted CSPs and low-degree analysis.

A: Thank you for your careful reading and for recognizing both the rigorous analysis and the extensive experiments. The starting question is how two generators can agree on each individual constraint while producing different satisfiability outcomes. The results in Sections 2 and 3 follow this question from a single constraint to shared variables and then to higher-order statistics.

  • What differs globally? A planted instance contains one hidden assignment accepted by all constraints. Above the classical threshold, a null instance is unsatisfiable with probability tending to one. This supplies the global distinction.
  • Why does one local observation not reveal it? After the hidden assignment is marginalized, each individual relation has exactly the same distribution in the two models. A single constraint cannot identify the generator, even though the constraints collectively differ.
  • Where does evidence first appear? Constraints sharing a variable interact through the same hidden value. Their centered marginal profiles can show distinguishing agreement. Theorem 3.4 gives the exact strength Λ2\Lambda_2 of this first informative quadratic component. Increasing density creates more opportunities for agreement. Growing the domain weakens each contribution.
  • What does higher-degree analysis add? Theorem 3.8 shows that when this pairwise quantity vanishes, increasing polynomial degree through O(log⁡n)O(\log n) still gives vanishing standardized mean separation under the stated assumptions. This separates the global distinction from a substantial class of low-order statistics.
  • What do the experiments ask? Once the evidence is characterized independently of a neural model, we compare its visibility with learned performance and vary representation, aggregation, communication and training data. These experiments show how the evaluated pipelines use the available signal. The polynomial degree in the theory refers to relation indicators.

The revision uses this sequence to introduce Sections 2 and 3.


Response to Weakness #2

Weakness #2: Under what conditions can the low-degree results help establish limitations for graph learners?

A: Thank you for asking how the theory can be applied to graph learners. It gives a precise conditional guarantee for any graph score whose dependence on the underlying relation indicators has bounded polynomial degree.

Let fθ(G)f_\theta(G) be the trained score, with θ\theta fixed before observing a fresh test instance. Write hθ(X)=fθ(ϕ(X))h_\theta(X)=f_\theta(\phi(X)) for that score as a function of the complete observation. If the score is in the degree DD class H≤D\mathcal H_{\le D} with observed scopes as side information and 0<Var⁡0(hθ)<∞0<\operatorname{Var}_0(h_\theta)<\infty, its null-standardized mean separation is at most ∥L≤D∥22−1\sqrt{\|L_{\le D}\|_2^2-1}. Theorem 3.8 then gives vanishing mean separation for D=O(log⁡n)D=O(\log n) when Λ2→0\Lambda_2\to0 under its assumptions.

This gives a route for studying a specific graph learner. For an encoder whose coordinates are degree kk polynomials of the relation indicators and a score that is a degree ℓ\ell polynomial of those coordinates, the composed score has degree at most kℓk\ell. The bound applies when the product lies in the theorem's degree range. For nonlinear GNNs and graph encoders, one would need a separate argument establishing this degree condition or an approximation with controlled class means and null variance.

Our architecture comparisons show where relation scores detect evidence that several graph learners struggle to exploit.


Changes in the revision (in blue):

  • Sections 2 and 3. We introduce the complete constraint observation and the graph encoding before the formal analysis. We explain why one constraint has the same marginal law in both classes, why overlaps reveal shared-variable evidence, and what the logarithmic-degree result says when this evidence vanishes.
  • Section 3 and Appendix I.6. We state the condition under which the low-degree mean-separation guarantee applies to a graph score and give a sufficient degree bound for a polynomial encoder followed by a polynomial readout.

Conclusion

We appreciate your guidance on making the theory more accessible. The overlap calculation gives a concrete route from the motivating distinction to the experiments. The bounded-degree condition specifies when the theoretical conclusion carries over to a score computed by a graph learner.

AuthorsOpenReview ↗

Friendly Reminder

Dear Reviewer 2Ss3,

This is a friendly reminder that we greatly value your input on our rebuttal. Your comments have been extremely helpful in improving our paper.

Your comments helped us explain how identical single-constraint marginals can coexist with a global satisfiability distinction and why shared variables provide the first detectable signal. We also state the condition under which the low-degree mean-separation result applies to a score computed by a graph learner.

As the discussion period closes on Nov. 18 (AoE), we would welcome any feedback on whether our response addresses your concerns. If it has clarified the points you raised, we would appreciate your taking the new evidence into account when updating your assessment. If any questions remain, we would be glad to address them.

Thank you for your time.

Best regards,
Authors of Submission #9120

I thank the authors for the detailed response and I appreciate the additional explanations and the effort to address my concerns. While I still believe that the presentation could be improved and that the theoretical connection to GNNs remains limited, I think the authors have addressed the points I raised. I have therefore decided to update my recommendation to weak accept.

Thank you very much for taking the time to review our work so carefully and for considering the additional explanations and experiments. Your constructive feedback helped us improve the paper, and we sincerely appreciate your recognition that our response addressed your concerns and your decision to raise the score. We are grateful for your support and have incorporated your suggestions, the new experimental results, and the accompanying analysis into the revised manuscript.

Reviewer_GDhhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigated planted Model RB and provide a useful empirical comparison between available statistical evidence and the performance. Specifically, it studies how to distinguish planted and null instances of the Model RB constraint-satisfaction problem. In planted instances, a hidden assignment satisfies all constraints, but only with each constraint has the same distribution in both classes. In their experiments, the authors compare a pair statistic based on the theory with GIN.The pair statistic roughly follows the predicted signal scale (while GIN needs denser instances as problem size grows).

Critical strengths
  • It provides a finite-instance characterization of the pairwise signal and the extension to claimed extension to logarithmic polynomial degree
  • The work separates global distinguishability, low-degree visibility, and empirical learnability is conceptually valuable
  • The finite expression serves as an informative comparator for a learned model
Critical weaknesses
  • Figures 4–5 compare methods that use different inputs. The pair statistic appears to use relation-level information that the anonymous graph does not retain. The graph removes constraint identities, scope labels, and repeated edges. Thus, the observed gap may arise from either the input representation or the learning method.
  • Proposition 2.5 shows that deterministic encoding cannot increase chi-squared divergence. However, it does not prove that this graph loses information or explain the observed AUC gap. Moreover, removing repeated edges does not necessarily change satisfiability, even if it changes the likelihood ratio or the pair statistic.
  • It is not clear how the relation-aligned features are defined and what are their computational cost.
  • Figure 4 labels Φ(Λ2/2)\Phi(\sqrt{\Lambda_2/2}) as a "ceiling," but Section 4.2 presents it as a Gaussian approximation. The theorem proves optimal mean separation after scaling by the null variance, not an AUC upper bound. For Gaussian scores, AUC(T)=Φ(μ1−μ0σ02+σ12)\mathrm{AUC}(T)=\Phi\left(\frac{\mu_1-\mu_0}{\sqrt{\sigma_0^2+\sigma_1^2}}\right). For T=L≤2−1T=L_{\leq 2}-1, the theory gives E0[T]=0\mathbb{E}_0[T]=0, Var0(T)=Λ2\mathrm{Var}_0(T)=\Lambda_2, and E1[T]=Λ2\mathbb{E}_1[T]=\Lambda_2, but it doesnt not determine Var1(T)\mathrm{Var}_1(T), so the proposed curve also assumes approximately equal variances across classes.
  • The reported crossover densities in Section 4.1 didnt follow from Table 1
  • Although the introduction identifies a relevant local-global question and includes illustrative examples, the transition from 1-WL indistinguishability to planted Model RB and low-degree likelihood-ratio analysis is abrupt. The paper introduces substantial notation and several formal results before adequately explaining why constraint overlaps contain distinguishing evidence, what the signal parameter measures, and how these statements relate to the graph-learning experiments. So the paper is difficult to follow without already knowing both planted-CSP theory and the low-degree method.
  • The main experimental presentation relies too heavily on GIN to support conclusions about graph learners more broadly. The paper said that GCN, GraphSAGE, and GAT are in appendix but their results should be summarized in the main text, especially in the difficult regimes used to motivate the claimed extraction gap. It would also be important to clarify whether the alternative-backbone experiments support only the size-dependent crossover in RQ1 or the extraction-gap and representation conclusions in RQ2 and RQ3 too
  • Model RB and its satisfiability threshold were established by Xu and Li. Earlier work also studied planted satisfiable instances. The paper should focus its novelty claims on the exact detection results and their connection to graph learning. The optimality of the projected likelihood ratio is a standard low-degree result. The main contributions appear to be its exact form for Model RB, the pairwise formula, and the extension to logarithmic degree. The authors should explain how these results differ from earlier work on solution counts and second moments.
  • While the synthetic setting is suitable for the paper's goals, and real-world data are not necessary
Questions for authors

See above

8 comments

Thank you for your careful and constructive evaluation. We appreciate your recognition of the finite-instance characterization, the distinction between global distinguishability, low-degree visibility and empirical learnability, and the usefulness of the diagnostic comparator. We address each point below.

Preview:

  • Weakness #1: Relation-level evidence and the graph observation interface.
  • Weakness #2: Information contraction under graph encoding.
  • Weakness #3: Aligned feature construction and computational cost.
  • Weakness #4: The exact quadratic result and the Gaussian AUC reference.
  • Weakness #5: Sampled densities, interpolated crossings, and the fixed-count check.
  • Weakness #6: From the 1-WL example to shared-variable evidence in Model RB.
  • Weakness #7: Cross-backbone evidence for RQ1, RQ2 and RQ3.
  • Weakness #8: The local-global formulation and the new exact results.
  • Synthetic setting: Why controlled Model RB instances suit the question.
  • Conclusion.

Response to Weakness #1

Weakness #1: Figures 4 and 5 compare a score that uses relation information with a learner on an anonymous graph. How much of the gap reflects the input representation and how much reflects the learner?

A: Thank you for highlighting the observation interface. The relation-level pair score measures the evidence predicted by the complete-observation theory, while anonymous GIN measures how much the evaluated learner extracts from the encoded graph. Table E.4 also measures the effect of relation grouping and tuple deduplication on the score while retaining the variable partition. Across the four grids, the mean absolute AUC change from L0L_0 to L2L_2 is 0.59 to 2.04 points.

We added a matched-instance experiment at (α,p)=(0.6,0.5)(\alpha,p)=(0.6,0.5) to test how the input interface contributes to the observed gap. The grouping-aware GIN keeps its message-passing architecture and hierarchical pooling when we add the aligned feature vector. A grouped readout uses the same aligned node features and pooling to assess the benefit of message passing.

Input and learnern=40,r=1.73n=40,r=1.73n=40,r=2.60n=40,r=2.60n=60,r=2.16n=60,r=2.16
Anonymous GIN52.58 ± 2.9157.47 ± 2.8551.31 ± 1.95
Grouping-aware GIN53.28 ± 2.7184.79 ± 11.8850.94 ± 1.89
Grouping-aware GIN with aligned features99.97 ± 0.0299.98 ± 0.0299.89 ± 0.12
Grouped readout with identical aligned features87.22 ± 1.4196.17 ± 0.8882.57 ± 2.21
GIN with aligned features, standard pooling99.86 ± 0.0999.98 ± 0.0299.54 ± 0.27

Each entry is test AUC (%) over three independently generated datasets. We average three model initializations within each dataset and report the mean and sample SD across datasets. All arms within a cell share the same underlying instances and train, validation, and test identities.

Grouping access alone moves AUC from 52.58 to 53.28 at n=40,r=1.73n=40,r=1.73 and from 51.31 to 50.94 at n=60,r=2.16n=60,r=2.16. Adding aligned features to the grouping-aware GIN raises these means to 99.97 and 99.89. Grouping is itself helpful at n=40,r=2.60n=40,r=2.60, where it raises AUC from 57.47 to 84.79 and the aligned features raise it further to 99.98. The results identify where the grouping interface helps and where making the shared-variable contraction accessible adds substantially more.


Response to Weakness #2

Weakness #2: Proposition 2.5 establishes contraction of divergence under encoding. Does it establish strict information loss for this graph, explain the measured AUC gap, or imply that removing repeated edges changes satisfiability?

A: Thank you for making this distinction precise. Proposition 2.5 gives the exact relation between the instance-level likelihood ratio and the likelihood ratio after observing GG, namely LG(G)=E0[LX(X)∣G]L_G(G)=\mathbb E_0[L_X(X)\mid G].

For square-integrable LXL_X, the conditional-expectation decomposition gives χ2(P1∥P0)−χ2(P1G∥P0G)=E0[Var⁡0(LX∣G)]\chi^2(P_1\Vert P_0)-\chi^2(P_1^G\Vert P_0^G)=\mathbb E_0[\operatorname{Var}_0(L_X\mid G)].

Equality holds exactly when LXL_X is measurable from GG up to null sets. The identity identifies the information available after encoding. Our matched comparisons then measure how the evaluated learners use the supplied observations.

Preserving satisfiability and preserving a detection statistic are different requirements. Removing duplicate forbidden edges can preserve the satisfying-assignment set while changing counts and quadratic statistics that use constraint provenance. A graph-measurable statistic can still retain evidence that is absent from a particular score.

The empirical ladder tests robustness of the implemented score to grouping and tuple deduplication with the partition retained. The exact finite-instance and logarithmic-degree results use the complete observation specified in the theory. Proposition 2.5 gives the complementary likelihood-ratio identity for encoded observations.

Response to Weakness #3

Weakness #3: How are the relation-aligned features defined, and what does their computation cost?

A: Thank you for requesting the explicit construction and cost. The aligned features expose the shared-variable contraction identified by the theory. Let Π\Pi partition the nqnq value nodes into variable blocks, and let ck,b,xc_{k,b,x} count edges from (k,x)(k,x) into block bb, excluding within-block clique edges. The centered count is Mk,b,x=ck,b,x−q−1∑x′ck,b,x′M_{k,b,x}=c_{k,b,x}-q^{-1}\sum_{x'}c_{k,b,x'}. We compute Sk,x=∑bMk,b,xS_{k,x}=\sum_bM_{k,b,x} and Qk=∑b,xMk,b,x2Q_k=\sum_{b,x}M_{k,b,x}^2. The quadratic feature is Tk=12(∑xSk,x2−Qk)T_k=\tfrac12(\sum_xS_{k,x}^2-Q_k).

Absent block pairs contribute zero. Each value node receives (Sk,x,Sk,x2,Tk)(S_{k,x},S_{k,x}^2,T_k), standardized per feature within each graph and concatenated with normalized degree, giving four input coordinates.

Information used. The current preprocessing obtains Π\Pi from the value-node indexing convention, so its accurate specification is ψ(G,Π)\psi(G,\Pi). It reads neither the hidden assignment, label, solution count nor a satisfiability oracle. Partition access is nevertheless an additional interface assumption relative to the anonymous baseline. We precompute TkT_k to measure the benefit of making the shared variable signal accessible to the learner.

Cost. The current dense implementation allocates an n×n×qn\times n\times q count tensor. Counting and reductions take O(∣E∣+n2q)O(|E|+n^2q) time and O(n2q)O(n^2q) dense count storage, plus O(∣E∣)O(|E|) temporary edge-index buffers. Total auxiliary memory is O(∣E∣+n2q)O(|E|+n^2q). This polynomial-time preprocessing is distinct from GNN training. Equal feature dimension with the generic control does not imply equal preprocessing cost.

For example, at n=60n=60 and q=12q=12, one dense float32 count tensor has 43,200 entries (168.75 KiB). The bound above also accounts for the temporary edge-index buffers.

Our server configuration uses an Intel Xeon Gold 6240 CPU at 2.60 GHz, 256 GB of RAM and a Tesla V100 PCIe GPU with 32 GB of memory, running Ubuntu 20.04 LTS. The costs above characterize the feature construction and its memory requirements.


Response to Weakness #4

Weakness #4: Figure 4 calls the Gaussian AUC approximation a ceiling. How does that curve relate to the exact theorem on standardized mean separation, and what assumption does it make about the planted variance?

A: Thank you for asking about the relation between the theorem and the plotted reference. Theorem 3.4 gives the exact optimal null-standardized mean separation. The AUC curve illustrates what that signal scale predicts under a Gaussian approximation. For the exact score T=S2∗=L≤2−1T=S_2^*=L_{\le2}-1, the moments are E0T=0\mathbb E_0T=0, Var⁡0(T)=Λ2\operatorname{Var}_0(T)=\Lambda_2 and E1T=Λ2\mathbb E_1T=\Lambda_2.

Under a Gaussian approximation, the AUC is Φ(Λ2/Λ2+Var⁡1(T))\Phi(\Lambda_2/\sqrt{\Lambda_2+\operatorname{Var}_1(T)}).

The simpler Φ(Λ2/2)\Phi(\sqrt{\Lambda_2/2}) additionally assumes approximately equal class variances. We refer to this curve as the Gaussian reference.

The implementation distinction is also important. The reported shared-variable score computes centered marginal contractions. It agrees, up to scale, with the one-variable-overlap contribution. The exact finite-instance optimizer additionally handles repeated scopes through a full-table contraction. Thus the reference organizes strength predicted by the exact theory, whereas the empirical calibration concerns the implemented score. The reported gridwise mean calibration errors of 1.35 to 2.70 AUC points are empirical observations, not an upper-bound guarantee.

Additional local CPU diagnostic. We used 200 independent calibration instances per class to estimate moments and 400 independent test instances per class to measure AUC in each cell, with the score direction fixed. The marginal score is a fixed positive rescaling of the implemented TpairT_{\rm pair}, so its AUC is unchanged. We use the generator's rounded values of qq and mm and the resulting peffp_{\rm eff}. The table reports AUCs in percent and gives the null and planted moments in separate columns.

nnrrScoreTest AUCμ0\mu_0v0v_0μ1\mu_1v1v_1GaussianΛ2\Lambda_2 ref.
401.73Marginal92.80-0.1894.8354.8565.84593.8794.62
401.73Exact94.05-0.1445.3475.3235.92294.8394.62
402.60Marginal98.230.0199.96210.60315.28698.2499.23
402.60Exact98.820.05811.43711.63615.93798.6599.23
602.16Marginal92.980.0193.5594.3145.01392.8893.14
602.16Exact93.76-0.0153.6904.7045.27594.2593.14

The unequal-variance prediction agrees closely with the measured AUCs in these three cells, while the exact optimizer improves over the marginal score by approximately 0.59 to 1.25 points. These measurements assess the Gaussian approximation at the reported parameter cells.

Response to Weakness #5

Weakness #5: How do the crossover densities in Section 4.1 follow from the results in Table 1?

A: Thank you for checking how the crossover relates to Table 1. Table 1 gives test AUC and accuracy at a common set of sampled densities, indexed by r/rcrr/r_{\rm cr}. Section 4.1 summarizes the density at which the GIN AUC curve first reaches 0.70. This is an interpolated statistic of the density sweep, computed between adjacent measurements that bracket 0.70. Table E.1 extends this analysis to different metrics and target levels.

The four values in Section 4.1, 1.15, 1.89, 2.68 and 4.21, are the absolute densities r0.70r_{0.70} in Table E.1. At (α,p)=(0.6,0.5)(\alpha,p)=(0.6,0.5), the corresponding coordinates on the Table 1 axis are obtained by dividing by rcr=0.6/log⁡2≈0.8656r_{\rm cr}=0.6/\log 2\approx0.8656. We provide the crossings in both units below, alongside the estimates obtained from Table 1 alone. The normalized column for the full sweep gives the multipliers of rcrr_{\rm cr} for Section 4.1.

nnFull-sweep r0.70r_{0.70}Full-sweep r0.70/rcrr_{0.70}/r_{\rm cr}r0.70/rcrr_{0.70}/r_{\rm cr} using only Table 1
151.151.331.33
251.892.192.26
402.683.103.10
604.214.874.87

For example, at n=25n=25, Table 1 reports 65.71% AUC at 2rcr2r_{\rm cr} and 82.38% at 3rcr3r_{\rm cr}. Linear interpolation between these two points gives 2.26rcr2.26r_{\rm cr}. The full sweep also measured 74.68% at 2.5rcr2.5r_{\rm cr}, so interpolating between 2rcr2r_{\rm cr} and that nearer point gives 2.19rcr2.19r_{\rm cr}, as reported in Appendix E.8. With either grid, the density needed to reach 0.70 AUC increases across all four sizes.

We further tested this pattern with 600 training instances per class at every size, on three independently generated datasets per cell. The mean normalized crossings at n=15,25,40n=15,25,40 are 1.48, 2.48 and 3.63. Every evaluated point at n=60n=60 through 3rcr3r_{\rm cr} stays below 0.70. The fixed-count sweep provides an independent check of the shift, with its own sampling and training protocol.


Response to Weakness #6

Weakness #6: Explain how the 1-WL example motivates planted Model RB, why shared variables carry evidence, what the low-degree signal measures, and how it connects to the experiments.

A: Thank you for pointing out where the motivation would benefit from a more gradual transition. The 1-WL example asks whether local observations can hide a difference in a global property. Model RB lets us pose that question statistically. The planted instance has a satisfying assignment by construction. Above the classical threshold, the null instance is unsatisfiable with probability tending to one. Once we marginalize the planted assignment, an individual constraint has exactly the same distribution in both ensembles.

Evidence first becomes visible when constraints share a variable. In the planted ensemble, both constraints accept the same hidden value of that variable. This introduces dependence between their centered marginal profiles. Theorem 3.4 quantifies the resulting quadratic signal as Λ2=(m2)B\Lambda_2=\binom m2B, where BB is the mean squared contribution of one constraint pair. Theorem 3.8 then tells us what happens when that signal vanishes. Under its assumptions, the mean separation vanishes even when the allowed degree grows logarithmically.

This calculation motivates the graph experiments. The relation score measures the signal available in the constraint tables, and the representation and learner controls show how much of it the tested graph pipelines can use.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.