跳到正文
arXiv cs.AI· Zhe Dong, Fang Qin·· 10 小时前AI 评分29

用可验证的答案改变对照评估神经图算法中的不变性训练

Evaluating invariance training with certified answer-changing controls in neural graph algorithms

AI 导读

研究用最小生成树上的可验证答案改变对照检验不变性训练评估:复现的图 Transformer(GDT)在 64 顶点图上经桥接附加子图后,对可证明固定标签的改动率达 53.3-65.9%。

正文 · 原文

View PDF HTML (experimental)

Abstract:Invariance training aims to make neural algorithmic reasoners robust to answer-preserving input changes and is judged by accuracy and by how rarely such edits change predictions. We ask whether this evaluation detects lost sensitivity to answer-changing edits on minimum spanning trees of synthetic graphs, where both directions can be certified. Attaching a subgraph through one bridge provably preserves every original label. Attaching it through two edges, oracle-selected to change a label, and lowering one weight inside the graph serve as answer-changing controls; a response is a changed prediction on an edge whose label changes. A reproduced graph transformer (GDT) within its published accuracy range changes a provably fixed label on 53.3-65.9% of the 64-vertex graphs it solves exactly after a 64-vertex bridge attachment; removing the connecting edge changes little. With 16-vertex graphs and attachments, three invariance objectives lower GDT violations from 2.91% to 0.52-2.02% of pairs at essentially unchanged accuracy. Training also lowers the response to two-edge attachments from 97.6% to 66.0-79.0%, while the response to in-base weight edits stays near 99.5%. At 64 vertices accuracy also falls, but on 16-vertex bases only the attachment control reveals the loss. A message-passing network loses some attachment response at small penalty weights but gains little invariance. Running the conventionally trained GDT on each biconnected block separately removes all observed violations and keeps accuracy and both responses, so the task does not force the trade-off. Sensitivity checks for trained invariance should include certified answer-changing edits that attach material as the training edits do.
Comments: 25 pages, 3 figures, 16 tables
Subjects: Artificial Intelligence (cs.AI)
ACM classes: I.2.6; G.2.2
Cite as: arXiv:2611.23907 [cs.AI]
  (or arXiv:2611.23907v1 [cs.AI] for this version)
  https://doi.org/10.48550/arXiv.2611.23907

arXiv-issued DOI via DataCite (pending registration)

Submission history

From: Zhe Dong [view email]
[v1] Wed, 18 Nov 2026 05:59:36 UTC (81 KB)

来源:arXiv cs.AI · arxiv.org