- 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, , 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, implies for polynomial degrees . 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
-
Exact finite-instance signal characterization and a logarithmic-degree extension. The identity , 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.
-
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
- The encoding comparison does not establish the claimed separation of input information and signal extraction.
The scope-only factor graph should have population AUC . 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 , 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 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 .
The aligned-feature input is also insufficiently specified. Appendix D.5 describes aligned and generic features as functions of alone, but Eqs. (D.3)–(D.4) use a partition of value nodes into variable blocks, exclude within-block edges, and count edges separately by neighboring block. As written, their construction uses . 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 . 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.
- 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 , and 1000 for . 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
-
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?
-
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 , and separates those features from the contribution of message passing?
-
Appendix D.4 distinguishes the exact optimizer in Eq. (C.36) from 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?
-
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
Rebuttal
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 , 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 learner | |||
|---|---|---|---|
| Anonymous GIN | 52.58 ± 2.91 | 57.47 ± 2.85 | 51.31 ± 1.95 |
| Grouping-aware GIN | 53.28 ± 2.71 | 84.79 ± 11.88 | 50.94 ± 1.89 |
| Grouping-aware GIN with aligned features | 99.97 ± 0.02 | 99.98 ± 0.02 | 99.89 ± 0.12 |
| Grouped readout with identical aligned features | 87.22 ± 1.41 | 96.17 ± 0.88 | 82.57 ± 2.21 |
| GIN with aligned features, standard pooling | 99.86 ± 0.09 | 99.98 ± 0.02 | 99.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 GIN | Aligned features added to grouping-aware GIN | Message passing with identical aligned features | |
|---|---|---|---|
| 0.70 ± 0.36 | 46.69 ± 2.72 | 12.74 ± 1.41 | |
| 27.32 ± 12.02 | 15.19 ± 11.89 | 3.81 ± 0.88 | |
| -0.37 ± 0.64 | 48.95 ± 1.91 | 17.32 ± 2.12 |
At and , grouping alone stays close to the anonymous reference and supplying aligned features produces the largest gain. At , 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 from Eq. D.2. Eq. C.36 gives the exact finite-instance optimizer , 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 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 , so its AUC is unchanged. We use the generator's rounded values of and and the resulting . AUCs are in percent, and the gain is the difference between the exact and marginal AUCs in percentage points.
| Mean repeated-scope pairs, test | AUC | Exact AUC | Deduplicated AUC | Exact score gain | |
|---|---|---|---|---|---|
| 41.34 | 92.80 | 94.05 | 92.82 | 1.25 | |
| 94.38 | 98.23 | 98.82 | 98.64 | 0.59 | |
| 79.31 | 92.98 | 93.76 | 93.69 | 0.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.
Rebuttal
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 and variances , the relevant prediction is . This differs from , 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 , so its AUC is unchanged. We use the generator's rounded values of and and the resulting . The table gives AUCs in percent. The Gaussian column uses the moments of each score, and is test AUC minus that prediction in percentage points.
| Score | Test AUC | 95% CI | Gaussian | ref. | ||||
|---|---|---|---|---|---|---|---|---|
| 40 | 1.73 | Marginal | 1.209 | 92.80 | [90.98, 94.39] | 93.87 | 94.62 | -1.07 |
| 40 | 1.73 | Exact | 1.108 | 94.05 | [92.52, 95.41] | 94.83 | 94.62 | -0.78 |
| 40 | 2.60 | Marginal | 1.534 | 98.23 | [97.55, 98.90] | 98.24 | 99.23 | -0.01 |
| 40 | 2.60 | Exact | 1.394 | 98.82 | [98.23, 99.29] | 98.65 | 99.23 | +0.17 |
| 60 | 2.16 | Marginal | 1.408 | 92.98 | [91.04, 94.64] | 92.88 | 93.14 | +0.10 |
| 60 | 2.16 | Exact | 1.430 | 93.76 | [92.23, 95.17] | 94.25 | 93.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 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 .
| Crossing | AUC at (%) | |
|---|---|---|
| 15 | 1.48 ± 0.03 | 95.61 ± 0.46 |
| 25 | 2.48 ± 0.13 | 81.54 ± 1.23 |
| 40 | 3.63 ± 0.24 | 56.01 ± 4.06 |
| 60 | Not reached | 51.79 ± 1.45 |
The crossing moves to higher density from to to in all three realizations. At , all three curves stay below 0.70 at every evaluated density through , 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.
Rebuttal
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
Response to Weakness #1 & Question #1
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/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 nq value nodes and m constraint nodes. For each forbidden tuple (x,y) of constraint a on variables (i,j), it adds bidirectional edges between ca and each of (i,x) and (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.
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)
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 q. Thus the supplied information is the adjacency G together with the partition Π, and the feature map is Faligned=ψ(G,Π). 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=40 and in each of the 64 pairs at n=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.