acceptodds
Withdrawn from ICLR 2027

Learning After Structural Poisoning: Label Coverage and Label Transfer

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Structural poisoning can erase target information without destroying realizability; labels can recover this information, yet training may fail to transfer it. On a sparse-tree family, we derive an exact coverage-based minimax law and a depth-dependent capacity law. A separate connected, bounded-degree construction preserves the realizing teacher under legal edge additions and has 20% cross-block neighbor-message mass at receivers. On this family, we prove a nonvanishing expected excess-risk lower bound over the information reference for finite-width, one-hop nonlinear graph neural networks with shared representations and trainable biases. The bound holds for GD and Adam at every fixed training horizon under the specified independent initialization and equally weighted hit-role logistic loss. A permutation symmetry obstructs label transfer even when cross-role logit-gradient inner products remain strictly positive. In a linear specialization, a positive-definite gradient preconditioner attains the information reference in one step without changing the function class, loss, or initial predictor. In a matched nonlinear study on the connected family, coupled Adam updates reduce overall test error by 10.90 percentage points across 96 independent problems, with all observed labels fitted. These results establish a separation between label coverage and label transfer, and show how optimizer design can improve transfer within a fixed model class.

Primary area:
learning theory
Keywords:
Graph neural networks, structural poisoning, transductive learning, minimax risk, sample complexity, training dynamics, label transfer

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_EAo7OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper focuses on structural poisoning, where edge additions or deletions to the given graph change the prediction. It claims to derive an exact excess risk lower bound for one layer GNN under gradient descent and Adam, and connect it to label transfer.

Critical strengths

None

Critical weaknesses

The paper has substantial clarity and presentation issues that make it difficult to understand the contributions. Despite spending considerable time reading it, I struggled to comprehend the results. A few examples are mentioned below.

The abstract combines standard terms such as structural poisoning and minimax risk with expressions such as sparse-tree family, 'legal' edge additions, neighbor message mass, receivers, equally weighted 'hit-role' logistic loss, 'cross role' logit gradient. These terms require context that is not provided. So, I found it difficult to understand what problem is being solved in the first place.

The introduction does not resolve these difficulties. For instance, right at the beginning, line 37 mentions 'block' - it is not clear what is referenced as a block in a graph or why its nodes share a label. The problem of interest is also not introduced. Lines 38 to 42 are just not understandable: the mathematical quantities B,d,m,N,RL⋆,ϵB, d, m, N, \mathfrak{R}_L^\star, \epsilon are all undefined. What are capacity, coverage and packing limits here? I find the whole of the introduction to be filled with jargon, and, more importantly, there are no references cited to establish the motivating gap or explain how it is relevant in the graph learning research.

Notations are also overloaded in some cases. For example, b=min⁡B,db=\min\\{B,d\\} in line 218, and bb is the number of receivers in line 257.

Technical sections are also difficult to parse. Theorem 6.1 uses equally weighted hit role logistic loss without providing its definition, even though this weighting is important to the argument.

The presentation currently prevents a clear assessment of the contributions and significance. For these reasons, I recommend rejection.

Questions for authors

Please see Weaknesses.

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

This paper decomposes the problem “whether learning remains feasible after structural poisoning” into two separable subproblems: label coverage (how much information remains, for which an exact solution exists) and label transfer (whether the covered labels can be effectively utilized during training, for which a lower bound exists). It further proves a quantifiable gap between these two quantities.

Critical strengths

The conceptual decomposition is clear. Coverage and transfer are distinct notions: the former admits an exact solution while the latter has a lower bound, rendering this framework inherently interpretable. The construction is valid. It satisfies connectivity, bounded degrees, teacher preservation, budget constraints, and label-agnostic attacks. No artificial difficulty is introduced by breaking implementability.

Critical weaknesses

The phenomenon that “training fails to transfer labels” is specific to first-order parameterizations where the self-matrix and neighbor matrix are not shared; it is not a universal behavior of learning under structural poisoning. The authors themselves note that repeated aggregation exposes unused rows of the self-matrix to the loss of observed receivers. Consequently, the abstract statement “training may fail to transfer” is overly broad. Moreover, the selling point that “optimizer design can improve transfer” is substantially weakened, given that switching to a standard architecture resolves the issue.

The node count ranges from 128 to 1536. The block structure, feature encoding, and teacher rules are manually constructed, and the feature dimension grows with the number of hidden bits (the authors have acknowledged this as a limitation). No natural graphs are evaluated. For a paper titled around “structural poisoning”, readers would expect to see whether this phenomenon emerges on Cora and ogbn-arxiv. In the sparse tree family experiments, SAGE with bias exhibits “perfect fitting yet erroneous predictions on covered nodes”, which serves as the most realistic evidence; however, it is still observed on synthetic graphs.

Questions for authors

The 2 weeknesses should be answered.

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

This paper studies learning after structural graph poisoning, distinguishing label coverage from the effective use of observed labels by GNN training. It constructs graph families where edge additions erase structural information about targets while preserving realizability. On a sparse-tree family, it derives an exact coverage-based minimax risk and depth-dependent capacity results. On a separate connected family, it establishes a risk gap for specified one-hop nonlinear GNN training procedures and presents an optimizer intervention that attains the information benchmark in a linear specialization. Experiments on constructed graph families evaluate nonlinear optimizer interventions, architectural conditions for label transfer, and supporting controls.

Critical strengths

The paper demonstrates the possibility of label-transfer failures. Within the constructed graph families and specified training conditions, the paper provides theoretical and empirical evidence that GNN training can fail to use observed label information that is sufficient to determine correct predictions, even when the model can represent the targets. This provides a concrete example of the gap between information availability and its effective use during training.

Critical weaknesses

W1. The research motivation and problem framing are insufficiently clear.

  1. The introduction moves quickly to bridge completion, block constructions, and exact risk formulas before clearly establishing the gap in existing analyses. This makes it difficult to understand why label coverage and label transfer are the central questions to investigate.

  2. The coverage analysis concerns unrestricted learners on a disconnected tree-block family, whereas the training analysis considers specified one-hop GNNs on a separate connected construction. Although this distinction is acknowledged, their conceptual relationship is insufficiently explained, making it difficult to assess how the results jointly answer the central research question.

  3. The connection between transfer failures and structural poisoning needs stronger justification. Section 7 reports transfer errors on clean graphs as well, while component copying eliminates covered-block errors on the original homogeneous-block family. The paper should clarify which difficulties are introduced by poisoning and what broader insight the training analysis provides beyond demonstrating architecture or optimization limitations in these constructions.

W2. The paper’s fragmented organization makes its central argument and supporting evidence difficult to assess.

  1. Although the introduction lists the contributions, the main text does not establish a sufficiently clear hierarchy between the central results and supporting extensions. In particular, Section 8 introduces deterministic, noisy-label, and relational analyses after the training results and experiments, without adequately explaining how these additional threads advance the main argument.

  2. Section 7 presents optimizer interventions, architectural comparisons, feature controls, and readout and stability audits in a dense sequence. These studies address different questions under different conditions, but their organization does not make the claim–evidence relationships easy to follow. This complicates assessment of what each experiment establishes.

  3. Related experimental protocols and supporting analyses are distributed across multiple appendices, while the main text frequently switches between constructions, models, and evaluation conditions. This creates a substantial cross-referencing burden. A consolidated overview of the settings, assumptions, and corresponding results would help readers determine which findings are directly comparable and which support separate claims.

Questions for authors

Relevance to structural poisoning. The paper explains that poisoning creates an information requirement, but also reports transfer errors on clean graphs. What additional insight about structural poisoning does the transfer analysis provide beyond demonstrating training limitations that also occur without an attack?

Connection between the theoretical settings. How do the exact coverage analysis on the disconnected tree-block family and the training analysis on the separate connected family jointly establish the paper’s central contribution? Which conclusions connect the two settings, and which should be interpreted as separate existence results?

Scope of the experimental evidence. Which studies in Section 7 directly support the central claims, and which address auxiliary architectural or stability questions? Given the differences in graph constructions, model classes, and training conditions, could you clarify which findings can be interpreted together and what conclusions they collectively support beyond the existence of transfer failures?

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

Related papers

Discussion (0)

Sign in to comment.