PaperlayerView exact revision on arXiv

Source-linked AI summary

Local Evidence and Geometric Readout Repair in Trained GNNs

Nadi Tomeh, Hugo Attali

arXiv:2609.27092v1cs.LGcs.AI

TL;DR

Node-classification errors can come from poor mixture weights or from a fixed-message set that cannot support the true class. The paper tests evidence reachability with an exact-mass linear program and compares two learned post-hoc repairs; across 64 dataset–backbone cases, mean accuracy rises from 62.6% frozen to 63.8% with reweighting and 65.3% with set translation.

  • Problem

    End-to-end accuracy conflates errors caused by unhelpful mixture weights with cases where no admissible mixture of fixed messages supports the true class.

    Source: §1 · p. 1

  • Method

    An exact-mass linear program diagnoses class reachability, while two label-free adapters compare reweighting within the reachable set with free centered logit translation.

    Source: §1 · p. 2

  • Results

    Across 64 dataset–backbone cases, mean accuracy rises from 62.6% frozen to 63.8% with reweighting and 65.3% with set translation.

    Source: §4.2 · p. 9

  • Takeaways & Limitations

    Translation captures most of the improvement, while the message set supplies a smaller additional benefit; label-free reweighting captures little of the oracle opportunity.

    Source: §5 · p. 9

    True-class reachability uses the test label and is an oracle diagnostic rather than a deployable prediction rule.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

Many node-classification GNNs apply a linear classifier to a nonnegative mixture of local messages. An error can reflect either poor mixture weights or a reachable logit set poorly positioned for the classifier. We separate these causes with an exact-mass linear program and two learned post-hoc repairs. Every reweighted prediction has an equivalent centered logit translation, but only translations in a message-induced displacement set are realizable by reweighting. Across eight datasets, eight GNN backbones, and ten splits, mean accuracy rises from 62.6% for the frozen models to 63.8% with reweighting and 65.3% with set-conditioned translation. A parameter-matched node-only translator reaches 64.6%, showing that translation explains most of the gain while the message set supplies a smaller additional benefit. Although oracle reweighting can correct many errors, label-free reweighting captures little of this potential: local evidence is often present but hard to select, and relaxing the evidence constraint is more effective than learning within it.

1 Introduction

A node-classification error can reflect either unhelpful mixture weights or a fixed-message set that cannot support the true class, while end-to-end accuracy conflates these causes. The paper uses an exact-mass oracle and two frozen-model adapters to distinguish evidence availability from evidence selection.

1 Introduction

  • End-to-end accuracy conflates errors from unhelpful mixture weights with errors where no admissible mixture supports the true class.The distinction matters when helpful and conflicting messages coexist in heterophilous or noisy graphs.Source: §1 · p. 1
  • An exact-mass linear program tests whether fixed messages can support a proposed class, with positive worst-rival margin certifying fixed-message support.The label is used only for the oracle analysis.Source: §1 · p. 2
  • Two label-free adapters compare reweighting within the reachable set against a free centered logit translation, with controls separating set conditioning from generic readout capacity.A refitted head and parameter-matched node-only translator help isolate these effects.Source: §1 · p. 2

2 Fixed-Message Reachability

With the GNN frozen, nonnegative coefficients redistribute fixed mass among local message logits, defining the set of reachable logits. An exact-mass linear program tests whether that set can give a proposed class a positive worst-rival margin, and its basic optima can be compact but remain oracle diagnostics.

2.1 Reachable logits and class margins

  • The reachable logit set consists of the frozen fixed contribution plus groupwise message contributions under nonnegative coefficients that preserve each group's frozen mass.For one group, the set is a scaled convex hull; with multiple groups, it combines a point from each group's hull.Source: §2.1 · pp. 2–3
  • Reweighting redistributes mass within the reachable set but cannot change its shape, branch scale, or transfer mass across groups.The fixed contribution includes classifier bias and any non-adjustable root, residual, or branch-bias contribution.Source: §2.1 · pp. 2–3

2.2 Exact-mass oracle and compact solutions

  • The linear program maximizes a proposed class's worst-rival margin over exact-mass weightings; a positive value means that class beats every rival.For the true class, positive margin certifies coefficient-only correction, while the test label is used only in this oracle analysis.Source: §2.2 · p. 3, §2.1 · p. 3
  • A basic optimum needs at most C + B_v − 2 active terms overall and C − 1 per group, but it may be nonunique and is not a prediction rule.A nonpositive true-class margin means correction requires changing the messages or another part of the model.Source: §2.2 · p. 3

3 Learning Constrained and Free Readout Corrections

The frozen GNN is paired with constrained reweighting and free centered translation adapters that use the same local information. Their comparison tests the cost of requiring a correction to remain realizable from the frozen messages.

3 Learning Constrained and Free Readout Corrections

  • The frozen GNN stays unchanged while two post-hoc adapters use the same local information, isolating the constraint that reweighting remain within reachable message combinations.One adapter reweights within L_v; the other predicts a free centered logit translation.Source: §3 · p. 4, §3.2 · p. 5

3.1 Shared local encoding

  • Both adapters encode the same final-stage set, including adjustable messages and exposed fixed context, with permutation-invariant encoders for variable set sizes.Fixed terms provide context but are not reweighted.Source: §3.1 · p. 4

3.2 Readout repair variants

  • Centered translation rigidly shifts L_v, while reweighting stays within it; a translation is reweighting-equivalent exactly when it lies in D_v.The reweighting adapter tilts frozen coefficients while preserving groupwise mass, and zero-weight terms remain unavailable.Source: §3.2 · p. 5

3.3 Training the adapters

  • Training labels supervise cross-entropy, but test-time repair uses only S_v and the target class is not an input; adapters start as exact no-ops.Only adapter parameters are updated; the graph, backbone, messages, support, and classifier remain fixed.Source: §3.3 · p. 6

3.4 Relation to existing methods

  • Unlike graph-wide propagation methods, these repairs stay local to the final message set; unlike calibration, they target error correction.Earlier GNN layers remain unchanged, unlike edge-conditioned or feature-wise message modulation.Source: §3.4 · p. 6

4 Experiments

Across 64 dataset–backbone cases, learned repairs improve on frozen models, while exact-mass oracle diagnostics show that many frozen errors are correctable within the fixed messages. Capacity and information controls compare translators using the message set with a parameter-matched node-only translator.

4 Experiments

  • The evaluation covers eight datasets and eight backbones over ten transductive node-classification splits, with frozen graphs, messages, coefficients, and classifiers during diagnostics and repairs.Macro averages weight the 64 dataset–backbone cases equally.Source: §4 · p. 6

4.1 Oracle reachability of frozen errors

  • 84.4% macro true-class reach and 59.2% error reach show many errors are correctable by exact-mass reweighting, while about two fifths are not.Error reach ranges from 39.9% for GraphSAGE to 88.3% for SGC, and from 29.5% on Citeseer to 73.1% on Chameleon; positive solutions use 1.99 active terms on average. These are label-aware oracle diagnostics, not predictions.Source: §4.1 · p. 7

4.2 Accuracy and controls for the learned repairs

  • 65.3% test accuracy for set-conditioned translation versus 62.6% frozen and 63.8% reweighting; translation improves on Frozen in 53 cases.The reported comparison is across the 64 dataset–backbone cases; Table 2 reports mean test accuracy over ten splits.Source: Table 2 · p. 8, §4.2 · p. 9
  • The capacity controls compare a refit head and a node-only translator with set translation; the node translator is parameter-matched within 1% in every case.The comparison tests the value of message-set input at matched output space and capacity.Source: §4.2 · p. 8, Table 3 · p. 8

5 Conclusion

The conclusion finds that many frozen errors have compact true-class combinations, but learned reweighting captures little of this oracle opportunity. Free translation performs better, with node-only translation accounting for most of the benefit and the full message set adding a smaller gain.

5 Conclusion

  • The exact-mass oracle finds compact true-class combinations for many errors, but learned reweighting captures little of this opportunity.Free translation performs better because it can express corrections outside the fixed-message polytope.Source: §5 · p. 9
  • Node-only translation captures most of the benefit, while the full message set provides a smaller additional gain at matched capacity.Local evidence also helps select the direction of a free correction, beyond defining the reweighting diagnostic.Source: §5 · p. 9
  • Future work may learn stable near-optimal sets rather than one LP solution and test larger structured relaxations.Source: §5 · p. 9

A Proof of Proposition 1

The proof connects positive worst-rival margin to strict feasibility for the proposed class, then bounds the number of active coefficients in an optimal basic solution.

A Proof of Proposition 1

  • A positive γ_v(c) holds exactly when a feasible logit has every class-c margin positive, equivalent to intersection with the interior of K_c.Source: A Proof of Proposition 1 · p. 12
  • An optimal basic solution has at most C + B_v − 2 active terms overall and at most C − 1 in any group.Source: A Proof of Proposition 1 · p. 12
  • The support bound follows by counting active nonnegativity, exact-mass, and rival-margin constraints against the LP’s K_v + 1 variables.Source: A Proof of Proposition 1 · p. 12

B.1 Datasets, preprocessing, and splits

The experiments cover eight node-classification datasets with standardized preprocessing and ten-split evaluation. Three datasets use ten newly generated class-stratified splits because this data interface provides only one standard mask.

B.1 Datasets, preprocessing, and splits

  • Eight datasets use floating-point features without further normalization, symmetrized graphs with duplicate directed entries coalesced, and one self-loop per node.All node features and the resulting graph are available during transductive training and evaluation.Source: §B.1 · p. 12
  • Table 4 reports dataset statistics after preprocessing, with E counting directed entries and split percentages listed as train/validation/test.“Provided” denotes the ten masks distributed with a dataset.Source: §B.1 · p. 12
  • Citeseer, Cora, and PubMed use ten class-stratified 60/20/20 splits with seeds 100–109; the other five datasets use provided split columns 0–9.Every reported entry averages ten splits, addressing known split sensitivity in GNN evaluation.Source: §B.1 · p. 13

B.2 Backbone architectures and training

The study evaluates eight GNN backbones with architecture-specific message-passing designs and exposes their final-stage terms while preserving each group’s frozen coefficient mass. Repair adapters use shared-width MLP components and are trained with separate groupwise normalization for reweighting.

B.2 Backbone architectures and training

  • GCN, GAT, GraphSAGE, GATv2, GraphConv, SGC, MixHop, and H2GCN are evaluated with hidden width 128 and architecture-specific layer, propagation, and attention designs.The first five use two message-passing layers; SGC uses two propagation steps, MixHop uses powers {0, 1, 2}, and H2GCN-style layers concatenate root, one-hop, and two-hop channels.Source: §B.2 · p. 13

B.3 Final-stage term exposure

  • Final-stage term exposure combines multiple paths to the same source into one higher-order coefficient, while each group retains its own frozen coefficient mass.GraphSAGE and GraphConv root terms are fixed context for the translation adapter and remain in βv rather than being reweighted.Source: §B.3 · p. 13, Table 5 · p. 14

B.4 Repair adapters and optimization

  • Repair adapters use two-layer width-128 MLPs, zero-initialized output layers, and groupwise normalization that preserves exact reweighting masses throughout training.Reweighting uses a 4 tanh-bounded score, while translation centers a 4 tanh-bounded output; the adapters are not parameter-matched and use different learning rates and epoch limits.Source: §B.4 · pp. 14–15

B.5 LP implementation and numerical checks

The LP diagnostics solve each validation and test node’s optimization over its complete exposed term set without neighborhood caps. Reachability and active support are determined using explicit numerical thresholds.

B.5 LP implementation and numerical checks

  • Every validation and test node is solved over its complete exposed term set without a node or neighborhood cap, using Gurobi dual simplex with one thread and disabled presolve.The solver returns a basic optimum from which support is measured.Source: §B.5 · p. 15
  • The fixed term is reconstructed from checkpoint logits so the original frozen logits are retained exactly, including non-adjustable contributions and accumulation remainders.This enforces zv(αv) = z0v exactly.Source: §B.5 · p. 15
  • Reachability requires γv(yv) > 10^-7, and a coefficient is active above 10^-7; TC reach, Err. reach, and Support use these events to summarize test nodes.No solver failure or violation of Proposition 1’s support bound was observed.Source: §B.5 · p. 15

C Full Capacity-Control Results

The capacity controls keep the graph and backbone frozen while changing only the prediction rule, with training labels used for fitting and validation accuracy for checkpoint selection. They compare a refitted linear head and a parameter-matched node-only translator against set translation.

C Full Capacity-Control Results

  • The controls keep the graph and GNN frozen, fit only the final prediction rule on training-node labels, and use validation accuracy for checkpoint selection.Test labels only score the selected checkpoint.Source: C Full Capacity-Control Results · p. 15
  • A refitted linear head trains a new affine map on standardized frozen node embeddings without updating any GNN representation, graph coefficient, or message.It is intentionally a small linear model rather than a capacity-matched translator.Source: C Full Capacity-Control Results · p. 15
  • The node-only translator predicts a centered bounded residual from the frozen recipient representation and original logits, without message features or set summaries.Its parameter count is matched independently to set translation in each dataset–backbone case, with at most 0.083% relative mismatch across 64 cases.Source: C Full Capacity-Control Results · p. 16
  • Node translation and set translation retain the frozen prediction as epoch zero, and the controls receive a training budget at least as generous as set translation.The refitted head is selected among its trained affine checkpoints.Source: C Full Capacity-Control Results · p. 16
  • Table 6 presents full capacity-control results as mean test accuracy over ten splits, with backbones in rows and datasets in columns.The supplied passage identifies the table’s scope and layout but does not provide its cell values.Source: C Full Capacity-Control Results · p. 16

Related papers

Loading 2609.27092v1…