用可认证的答案改变型对照评估神经图算法的不变性训练
Evaluating invariance training with certified answer-changing controls in neural graph algorithms
AI 导读
arXiv 论文提出用可认证的答案改变型对照来评估神经算法推理器的不变性训练。在合成图最小生成树上,复现的 graph transformer(GDT)在 64 顶点桥接附加后,对可证明不变的标签在 53.3-65.9% 的精确求解图上改变了预测;三个不变性目标将违例从 2.91% 降到 0.52-2.02%,但两边缘加的响应从 97.6% 仍留在 66.0-79.0%。
正文 · 原文
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