acceptodds
Under review as a conference paper at ICLR 2027

What Explains Quadratic Feature Gains in Semi-Supervised Classification?

Abstract

Adding quadratic interactions can improve classification with sparse annotations. Does that gain require additional feature directions, or merely a different regularizer? We study this question for spectral graph features using exact controls, a classification theorem, and paired experiments. Projected products are exactly a low-dimensional linear component with an anisotropic penalty. More surprisingly, we construct connected graphs on which full and projected models make identical decisions, although fitting the complementary block separately achieves perfect classification. No positive quadratic reweighting of the fixed linear-feature space recovers that result; the error separation persists as the labeled fraction tends to zero. On three image graphs, a 52-budget study establishes a reference gain. A separate matched decomposition with a common free intercept shows that jointly fitting a separate complementary coefficient block helps on two graphs, while recoupling offsets part of that benefit. A theory-prescribed scalar control leaves further gains in some annotation regimes, while stronger model selection remains competitive. Finally, signed class-margin bounds identify decisions invariant along the entire coupling path. Their numerical coverage rises from 33.02% for a norm bound to 93.17% with signs and 98.20% after refinement. The resulting lesson is operational: separate reweighting, complementary directions, and their coupling before interpreting an enrichment gain or a near-zero ablation gap.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
semi-supervised learning, graph-based classification, spectral graph features, quadratic feature enrichment, anisotropic regularization, feature coupling, feature attribution, prediction stability

Reviews

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

This paper investigates why quadratic features improve graph-based semi-supervised classification by separating reweighting within the original feature space, complementary feature directions, and coupling between the two components. It establishes an exact linear-feature interpretation of projected products and constructs connected graphs where Full and Parallel make identical predictions, although Decoupled achieves perfect classification. Experiments on three image graphs examine these effects under matched controls and stronger model selection. The paper also develops signed margin bounds for assessing prediction stability along the entire coupling path.

Critical strengths
  1. The classification counterexample is the strongest contribution. It demonstrates that identical predictions can conceal useful complementary features, with a nonvanishing error separation as the labeled fraction decreases.

  2. The matched controls are carefully designed. In particular, the common free intercept addresses the constant-direction confound, and the experiments distinguish controlled interventions from independently selected procedures.

  3. The whole-path analysis provides information that endpoint comparisons miss, supported by concrete examples of predictions changing and subsequently returning to their initial class.

Critical weaknesses
  1. The main theorem establishes an existence result on a specially constructed graph. It does not characterize when harmful coupling should arise on ordinary data, leaving the connection between the construction and the benchmark observations incomplete.

  2. Empirical generality remains limited. All three graphs participated in development, and the stronger selection experiments mainly use three trajectories. The small and mixed gains after selection, together with the sign reversal in the expanded MNIST experiment in Appendix C.7, weaken confidence in practical robustness.

  3. Numerical validation of the adaptive diagnostic is incomplete. Appendix B.7 assesses cutoff sensitivity for direct signed bounds, but the refinement-only cases lack retained final interval bounds. The relationship between sensitivity flags and prediction errors is also not established.

Questions for authors
  1. Which properties of the observed feature geometry or regularization settings explain why the complementary-block benefit persists on CIFAR-10 but reverses on Fashion-MNIST under shared selection?

  2. How were the reference geometry and penalties chosen, and how consistently does the cancellation pattern appear across the existing factorial geometry study?

  3. Can the authors report accepted interval-bound margins or tolerance sensitivity for the refinement-only diagnoses contributing to the 98.20% coverage?

2 comments

Thank you for identifying the missing refinement bounds and the questions about geometry and replication. We have recovered the minimum accepted bounds for all 11,122 diagnoses obtained only after subdivision, crossed geometry with penalty choices on the support driving the original reversal, extended shared selection to ten trajectories, and linked the diagnoses to prediction errors.

Geometry and reference settings (§3, p. 3; C.10, pp. 28–29). We examined the Fashion-MNIST and CIFAR-10 supports at 40 labels per class, seed 20270104, because their previously observed complementary effects differed. On this Fashion-MNIST support, changing from G64 to G128 reverses Decoupled−Parallel under both penalty choices: from +0.065 to −0.246 percentage point at reference penalties, and from +0.243 to −1.967 with the Base-selected tuple. Base selected G128 with both feature penalties equal to 0.003, τ=1\tau=1 and σ=0.001\sigma=0.001. It chose G128 on 20/30 Fashion-MNIST supports, including this one.

G128 changes rank and diffusion time together: it doubles the rank and halves the time. The selected tuple also changes more than one penalty. The crossed comparison localizes the observed reversal to the geometry change and shows its amplification under the selected tuple; it does not isolate rank, diffusion time or one penalty, nor provide a general predictive rule. All four corresponding CIFAR-10 effects remain positive (+0.485 to +0.861). The complementary share of squared quadratic feature norm increases on both graphs, so that share alone does not explain their different signs.

G64 and the reference penalties were development settings, and all three image graphs participated in development. Their original selection criterion is absent from the retained records. We therefore treat them as development choices rather than independently validated optima and examine sensitivity to their variation. Across nine fixed-penalty geometries, ten trajectories and three budgets, addition and recoupling have opposite mean effects in 8/9 MNIST settings and 9/9 settings on each of Fashion-MNIST and CIFAR-10. Five geometries per graph retain part of the gain after recoupling.

Replication and the link to the theorem (C.7, C.10–C.12). Across ten shared-selection trajectories on CIFAR-10, adding the complement improves mean accuracy and sharing coefficients reduces that gain; nine retain a net gain over Parallel. Fashion-MNIST's mean complementary gain is near zero, with an interval spanning zero. Independent selection still has three complete trajectories per graph. The ten-seed MNIST extension at five labels per class gives a mean Full–Base difference of −0.123 percentage point, with an exploratory bootstrap interval [−1.078, +0.536]. It does not establish a consistently positive enrichment gain. Matched Cora and C. elegans experiments establish occurrence outside image graphs under two edge constructions, without establishing prevalence across networks.

The connection to the theorem now reaches individual decisions. Among 221,184 query/configuration evaluations, Decoupled corrects a common Parallel/Full error in 741 cases; the reverse pattern occurs 369 times. In 325 of the 741 cases, the complementary and cross terms are each necessary for the respective margin signs at fixed fitted coefficients. C.11 separates these contributions from changes caused by refitting. A general criterion predicting harmful coupling remains open.

Refinement bounds and prediction errors (C.11, pp. 29–30). For each of the 11,122 refinement-only diagnoses, we recovered the minimum bound over all accepted intervals and rival classes. The smallest bound is 3.25×10−93.25\times10^{-9} and the median 4.93×10−34.93\times10^{-3}. With the partitions fixed, cutoffs of 10−610^{-6} and 10−410^{-4} retain 11,101 and 10,584 of these diagnoses. After including the direct diagnoses that survive each cutoff, the respective overall coverages are 98.19% and 97.94% of all 221,184 evaluations. These are floating-point bounds, without a directed-rounding guarantee.

On the same population, initial error is 19.36% among numerically stable predictions and 57.95% among witnessed changes, with this ordering in all 54 configurations. Within the stable group, the direct and refinement-only error rates are 16.96% and 63.79%. Refinement identifies further invariant decisions, including persistent errors; invariance does not ensure correctness.

The common correction and verification note and supplement register describe the numerical corrections. Table 3 mean contrasts change by less than 0.032 percentage points, and Full−Base is unchanged. The original cause could not be established from retained records.

Please let us know which concern, if any, remains unresolved.

Thank you for the additional analyses. My remaining reservation is about scope. The results show that coupling can mask useful complementary features, but they do not yet tell us when to expect this on a new graph. I agree that a general predictive criterion is beyond what the present evidence establishes.

Reviewer_q8tfOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies if improvements from quadratic feature enrichment in graph-based semi-supervised classification come from genuinely new feature information or just changes in the regularization. Authors compare linear, quadratic, projected, and decoupled feature models. They show that the projected quadratic features are equivalent to changing the regularization of linear features. Importantly, they make cases where the full quadratic model and its projected versions make similar predictions, even though they achieve perfect classification by separately using the complementary features.

They perform experiments on MNIST, fashion-MNIST, and CIFAR-10 datasets which show that complementary features can improve accuracy, but combining them with the existing features can partially cancel these gains. The improvements are not very consistent after hyperparameter tuning. Paper also gives bounds to identify predictions that remain stable as feature coupling changes. Overall, it explains why small difference between model variants may not necessarily mean the additional features being useless.

Critical strengths

1.⁠ ⁠Theorem 1 builds connected weighted graphs where at every vertex, full and parallel agree, still decoupled one is able to achieve perfect classification. The additional impossibility result of positive-semidefinite reweightings of the fixed linear-feature space makes it stronger than the regular counterexample to feature redundancy.

2.⁠ ⁠Proposition 1, along with the common-intercept comparisons differentiates changes in anisotropic regularization from the contribution of complementary directions.

3.⁠ ⁠The comparisons in experiments show that adding an independently parameterized complementary block can improve accuracy, and restoring the coefficient coupling can partially reverse this improvement.

4.⁠ ⁠The signed coupling-path analysis catches changes that endpoint agreement misses to identify. It significant improvement on a norm-based certificate shows the value of retraining signed contributions while analyzing prediction stability

Critical weaknesses

1.⁠ ⁠The current fixed-recipe experiments show consistent improvements from quadratic enrichment, but the independently selected full achieves very small gains (+0.13, −0.18, and +0.32 pp across the three datasets). Minimal gains are concerning. Authors must be able to explain why it happens.

2.⁠ ⁠In experiments, the complementary-block benefit and recoupling loss vary across datasets and selection protocols, making it sensitive to model selection.

3.⁠ ⁠Theorem 3 certifies prediction invariance along the coupling path. But the invariance may not imply/translate to correctness. To claim that, authors must relate certified stability to the actual classification errors to practical usability of the proposed diagnostic.

Questions for authors

1.⁠ ⁠As stated above, independently selected full provides smaller and sometimes negative gains over the base. You should analyze and report, in which settings they believe quadriatic enrichment offers a reliable (and consistent) practical gains. Claims maybe narrowed down accordingly.

2.⁠ ⁠Can you quantify if the signed feature-transmission mechanism underlying theorem 1 is there in the image-graph experiments of the experimentation section or not. Results should not rely on the aggregate accuracy cancellation.

3.⁠ ⁠Can you evaluate the signed stability certificates against prediction correctness on the same query population to check if stable and coupling-sensitive predictions exhibit different error characteristics.

4.⁠ It would be great if you can experimentally establish if the shared setting complementary-block gains and recoupling losses persist over additional annotation trajectories or not, especially on Fashion-MNIST.

2 comments

Thank you for these questions. We have extended shared Base selection to ten complete annotation trajectories, tested the signed mechanism on individual decisions, and joined stability diagnoses to their classification errors. We also explain why independent model selection reduces the gains and state which positive results remain supported.

1. Practical gains after selection (§5.2, C.5 and C.7). The smaller gains arise because selecting geometry and penalties improves Base more than Full. On the same annotations, CIFAR-10 Base gains 4.56 percentage points and Full 2.88, reducing their gap from 2.00 to 0.32. On Fashion-MNIST, the larger improvement of Base reverses their ordering.

At 160 labels per class on CIFAR-10, independently selected Full gains 0.97 point over Base, with positive differences on all three trajectories. At 40 labels per class it falls below Base in every graph mean. The ten-seed MNIST extension at five labels per class gives −0.123 point, with an exploratory interval [−1.078, +0.536]. These results support gains conditional on the graph, budget and selection procedure.

Laplacian-regularized least squares (LapRLS) instead penalizes the whole predicted function. With its expanded grid, quadratic features improve on linear features by 0.47–1.18 points across graphs, averaging the three budgets; the difference is positive on each graph's three complete trajectories. The lowest grid penalty remains selected in 27/54 decisions. This identifies another setting where enrichment helps, within the tested geometry and grid (§5.2; B.3). The paper's contribution concerns the interpretation of feature ablation, without establishing a generally superior selected classifier.

2. Signed mechanism in individual decisions (§6, p. 9; C.11, pp. 30–31). We examined 221,184 query/configuration evaluations. In 741 cases, Parallel and Full chose the same wrong class and Decoupled was correct; the reverse pattern occurred 369 times. In 325 of the 741 cases, removing the complementary contribution erased Decoupled's positive true-versus-rival margin, and removing the cross contribution erased Full's negative margin, each at its own fixed fitted coefficients. C.11 separates these sign tests from the terms due to refitting.

This connects the signed mechanism to individual decisions, beyond aggregate accuracy cancellation. It does not establish on the benchmarks the theorem's impossibility result for every positive-semidefinite reweighting within the original affine feature space.

3. Stability and correctness (§6, p. 10; C.11, pp. 29–30). On that same population, initial error was 19.36% among numerically stable predictions and 57.95% among witnessed changes; this ordering held in all 54 configurations. Within the stable group, error was 16.96% under the direct signed bound and 63.79% among predictions numerically certified only after subdivision. Refinement therefore identifies additional invariant predictions, including persistent errors. Invariance along the coupling path does not establish correctness.

4. Additional annotation trajectories (C.10, pp. 28–29). Shared Base selection now covers ten complete trajectories at 5, 40 and 160 labels per class. On CIFAR-10, the two effects retain opposite mean signs:

Contrast at the shared Base-selected settingMean effect (percentage points)Marginal 95% interval
Decoupled − Parallel+0.486[+0.274, +0.655]
Full − Decoupled−0.213[−0.291, −0.140]

These paired bootstrap intervals resample whole annotation trajectories on the fixed graph. Nine trajectories retain a net gain over Parallel. On Fashion-MNIST, the complementary gain is positive on seven trajectories but averages −0.010 point [−0.214, +0.192]; recoupling averages −0.104 [−0.185, −0.012]. Thus the extension supports the opposing effects on CIFAR-10, while it does not establish a consistently positive complementary benefit on Fashion-MNIST.

This extension concerns the controlled comparison at a shared Base-selected setting. Independently selected procedures still have three complete trajectories per graph; the ten-seed MNIST result above extends only the five-labels-per-class cell.

Please also see the common correction and verification note, which documents the numerical changes to the submitted results and their verification.

Please let us know whether any of these analyses leaves a specific concern unresolved.

Dear Authors,

Thank you for your detailed response. It broadly addresses all my concerns. My initial rating of 3 is sufficient for the contribution the paper makes. Therefore, I would maintain my positive stance.

Reviewer_61rfOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper investigates whether improvements from quadratic spectral features are due to capturing additional feature directions or altering the effect of regularization. It analyzes a feature predictor augmented with a graph-regularized adjustment, employing projected products to serve as a directed linear-feature baseline. By refitting models under matched conditions, the study isolates the contributions of extra features from the impact of coupling among coefficients.

The main theorem demonstrates the existence of connected graphs in which Full and Parallel yield identical predictions, while Decoupled achieves perfect classification and all possible admissible linear-feature reweightings result in errors. Additional results provide both a scalar comparison formula and bounds on the margin along the entire path. Experiments on three image-similarity graphs investigate how the gains from additional features are offset by losses due to recoupling.

Critical strengths
  • The problem is interesting: the paper asks whether quadratic-feature gains arise from new directions or changed regularization.
  • The experiments evaluate Base, Parallel, Decoupled, and Full models while keeping the graph, penalty, and intercept conditions consistent. This design isolates the effects of reweighting, adding complementary features, and recoupling, highlighting that coupling can diminish the benefits of additional features.
Critical weaknesses
  • The writing needs improvement. The current exposition is quite difficult to follow. The abstract is too dense. The central research problem, as well as experimental pipeline, were not explained clearly enough.
  • All real data experiments use graphs constructed from image dataset, which might be limited.
  • The empirical sensitivity results are not linked to actual prediction outcomes, which restricts how effectively the diagnostic's practical usefulness can be assessed.
Questions for authors
  1. Improve the paper writing and explain the experimental pipeline.

The abstract presents several arguments before clearly introducing the central problem of this paper. Likewise, the introduction makes itself challenging to follow. I suggest that authors should polish writing before any publication. At least, the paper should first explain the central research problem clearly, then provide a concise overview of the experiments, e.g., algorithm to construct similarity graphs. The authors should consider present some algorithm blocks to present the methodology in the main text. Then it would be easier to follow. Also, when I was reading line 44, I had no idea what do 'Full' and 'Parallel' refer to. The paper should define the Parallel and Full approaches first, then make comparisons among those terminologies to illustrate the concepts.

2. Broaden validation beyond image-similarity graphs

All real-data experiments are based on nearest-neighbor graphs generated from fixed VAE/AET features of MNIST, Fashion-MNIST, and CIFAR-10. While these settings provide well-controlled scenarios, the results observed may be specific to the particular image representations and graph construction choices. Although the authors note this limitation, the empirical support for more general conclusions is limited. To strengthen the work, the authors should consider include node classification results on one real-world network data, such as a citation or biological network, then evaluate the sensitivity to graph construction methods, ensuring that attribution controls remain consistent. The existence theorem shows that masking is possible, but expanded experiments are necessary to determine how prevalent this effect is in real-world settings.

3. Connect sensitivity diagnoses to the observed error changes (lines 449--462).

The query level sensitivity panel does not include true labels or the final selected predictions, making it impossible to match its diagnoses directly with the separate counts of repairs and damages. Please link these results so that it is clear which changes are beneficial, harmful, accuracy neutral, or reflect stable errors. While the change-and-return cases illustrate sensitivities that endpoint agreement misses, connecting these findings to prediction correctness would more convincingly demonstrate the practical value of the diagnostic.

4 comments

Thank you for identifying three ways to strengthen the paper. We have reorganized the exposition and experimental pipeline, added two non-image networks with controlled changes to their edges, and linked sensitivity diagnoses to prediction errors on the same query evaluations. We address each concern below.

1. Explain the question and experimental pipeline (§1; §3, p. 3; B.1, p. 19). The revised abstract opens with the question: if a classifier makes the same predictions after features are removed, what can we infer about those features? The introduction defines the four models before comparing them and explains how sharing coefficients can hide useful features:

  • Base: uses coordinates derived from the graph.
  • Parallel: adds the parts of their pairwise products expressible using those coordinates and a constant.
  • Decoupled: adds the remaining product components with their own coefficients, fitted jointly.
  • Full: uses the original products, sharing coefficients between their two components.

All retain a graph-regularized correction. The numbered protocol now opens §3, before the notation and equations: construct the graph and features, fit the models, then evaluate on unannotated nodes. The matched attribution comparisons use the same graph, annotations, feature settings, penalties and free intercept. Appendix B.1 specifies the nearest-neighbor construction and Gaussian edge weights. The conclusion explains how to test the remaining product components before discarding them.

2. Test non-image networks and different edge constructions (§5.2, p. 8; C.12, p. 31). We added Cora's citation network (2,485 papers) and the C. elegans connectome (279 neurons). Both experiments use recorded links alone. We compare the recorded edges with an expansion connecting nodes at distance at most two, preserving total edge weight and recomputing the features. Each comparison uses the same annotations and penalties over ten annotation trajectories at 5, 10 and 20 labels per class.

The mean effect of sharing coefficients reverses when the edges change. The table gives accuracy differences in percentage points. Add is Decoupled minus Parallel; Share is Full minus Decoupled.

NetworkEdgesAddShare
CoraRecorded+0.18−0.35
CoraUp to two hops−0.48+0.10
C. elegansRecorded+0.38+0.37
C. elegansUp to two hops+0.67−0.70

Both networks contain decisions where Decoupled corrects a shared Parallel/Full error; C.12 reports these and the reverse cases. These observations establish occurrence beyond image graphs. The ranges across trajectories include both signs for every addition and sharing contrast. Nodes enter repeated evaluations, neuronal role labels partly reflect connectivity, and prevalence across networks remains open.

3. Relate prediction changes to errors (§6, pp. 9–10; C.11, pp. 29–31). We now join each sensitivity diagnosis and its prediction outcomes to the true class on the same 221,184 query/configuration evaluations. This replaces the earlier comparison with separate error counts from a different population.

Of 3,952 endpoint changes, 1,088 repaired errors, 1,669 lost correct predictions and 1,195 moved between wrong classes. Among 217,200 numerically stable evaluations, 42,054 predictions were incorrect. These counts distinguish useful, harmful and accuracy-neutral changes from persistent errors.

In the 31 change-and-return cases, predictions at the first recorded interior witness corrected 15 initially wrong predictions, made six initially correct predictions wrong, and switched between wrong classes in ten cases. All returned to their initial prediction, so endpoint agreement concealed each interior change. One evaluation remains unresolved. The diagnostic therefore describes what happened along the coupling path; invariance alone does not establish correctness.

Please also see the common correction and verification note, which documents the numerical changes to the submitted results and their verification.

Please let us know whether any of these concerns remains unresolved, or whether a specific validity concern needs further clarification.

Dear Reviewer 61rf,

As the discussion period is nearing its end, we would welcome your feedback on our November 11 response. Could you let us know whether the revised exposition, the added non-image experiments, and the analysis linking sensitivity to prediction errors address the concerns raised in your review? If any specific concern about the validity of the results remains, we would appreciate the opportunity to clarify it.

Thank you for your time.

I would like to thank the authors for detailed extensive responses, and substantially rewriting of the abstract and the introduction. The revised abstract and introduction are clearer than the submitted version. The new experiments on citation and neuronal graphs address my concerns that in the submitted version, the proposed method built on spectral graph features were only evaluated on graphs constructed from image data.

However, the revision changes the focus of the paper. The submitted version asked whether the gain from adding quadratic interactions requires additional feature directions or only a different regularizer, where the interpretation of ablations was treated as a secondary point. The revised version drops the question about enrichment gains from its framing and conclusion, and instead asks what can be inferred when predictions are unchanged after features are removed. Also, as the revised abstract notes, the gains after model selection on the image graphs remain small and mixed. The theoretical constructions are largely the same, but the framing, the main message and a central part of the evaluation are new. Changes at such a scale need a full review, which can't be provided at the discussion period.

Therefore, I would like to keep my score. I still encourage the authors to continue polishing the writing before any publication. In particular, every terminology should be introduced clearly before its first use. In the abstract, the central research problem and main conclusions should be stated in a clear and precise manner.

AuthorsOpenReview ↗

Closing clarification on the original contribution and revised framing

Thank you for the discussion and the suggestions that helped improve the paper. To assist the final assessment, we would like to clarify how the revised framing relates to the original contribution.

We agree that the revised abstract places greater emphasis on interpreting ablations, and that the additional empirical analyses are substantive. Our intention was to make the connection between enrichment gains and ablation interpretation clearer.

In the original submission, the introduction already stated:

“Our central finding is that a near-zero ablation gap can hide useful complementary features.” (p. 1, line 043)

This finding was formalized in Theorem 1 (§4.4) and discussed alongside the interpretation of enrichment gains in the original conclusion (§7). The revised introduction also retains the question of whether pairwise products supply useful new directions or change the penalties on existing directions (p. 1, lines 031–035).

The small and mixed gains after independent model selection were already reported in the submitted §5.2 (p. 7, lines 365–371). We agree that these constrain claims of practical superiority. The submitted introduction likewise distinguished the attribution question from assuming that quadratic features or decoupling always improve performance (p. 1, lines 051–053).

The added non-image experiments and the analyses linking sensitivity to prediction errors extend the validation of the existing models and diagnostic in response to the reviews. We appreciate that these additions require scrutiny.

The contribution we ask to be assessed is the classification result, the matched controls separating reweighting from complementary directions and coefficient coupling, and the signed coupling-path diagnostic, with the stated limitations of the empirical evidence. We hope these references help clarify the continuity between the submitted contribution and the revised presentation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.