Research map / Graph learning / Graph algorithms and clustering
Extending Test-Time Augmentation with Metamorphic Relations for Combinatorial Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MAgg, which extends test-time augmentation to combinatorial-problem ML models by building ego metamorphic graphs from metamorphic relations and aggregating base-model predictions with a small GNN.
Problem
Standard test-time augmentation requires label-preserving transformations, which are hard to find for combinatorial problems, and its fixed averaging ignores semantic relations between instances.
Approach
Use non-label-preserving metamorphic transformations to create transformed instances, represent their binary metamorphic relations as a directed ego graph, and aggregate base-model predictions on that graph with a trainable MPNN instead of a fixed average.
Key results
- SAT: MAgg(10,10) raises NeuroSAT accuracy on SR(40) from 0.8444 to 0.9757 (up to ~0.13 gain).
- Decision TSP: MAgg(10) improves TSP-GNN accuracy on TSP(0.01) from 0.6562 to 0.6812 and on TSP(0.02) from 0.8101 to 0.8321.
- GED: MAgg(50) reduces GREED RMSE on LINUX from 0.4151 to 0.2409 (42% relative), but gives no gain on AIDS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| augment NeuroSAT with first-level metamorphic transformations | NeuroSAT · SR(40) | accuracy: 0.8444 -> 0.9548 | Helped |
| add second-level metamorphic transformations (ablation) | MAgg(10) with NeuroSAT · SR(40) | accuracy: 0.9548 -> 0.9757 | Helped |
| augment NeuroSAT with first-level metamorphic transformations | NeuroSAT · SR(80) | accuracy: 0.7268 -> 0.7936 | Helped |
| add second-level metamorphic transformations (ablation) | MAgg(10) with NeuroSAT · SR(80) | accuracy: 0.7936 -> 0.8533 | Helped |
| augment NeuroSAT with first-level metamorphic transformations | NeuroSAT · SR(120) | accuracy: 0.6270 -> 0.6412 | Helped |
| add second-level metamorphic transformations (ablation) | MAgg(10) with NeuroSAT · SR(120) | accuracy: 0.6412 -> 0.6643 | Helped |
| augment TSP-GNN with metamorphic transformations | TSP-GNN · TSP(0.01) | accuracy: 0.6562 -> 0.6812 | Helped |
| augment TSP-GNN with metamorphic transformations | TSP-GNN · TSP(0.02) | accuracy: 0.8101 -> 0.8321 | Helped |
| augment GREED with metamorphic transformations | GREED · AIDS | RMSE: 0.7957 -> 0.7994 | Hurt |
| augment GREED with metamorphic transformations | GREED · LINUX | RMSE: 0.4151 -> 0.2409 | Helped |
| augment GREED with metamorphic transformations | GREED · IMDB | RMSE: 6.7341 -> 6.3107 | Helped |
Surprising findings
- The linear MAgg(10) aggregator alone yields large SAT accuracy gains, attributed to making satisfiable and unsatisfiable cases linearly separable on transformed-instance predictions.
- MAgg gives no improvement on the AIDS GED dataset, which the authors attribute to node labels making random edits more likely to change GED.
Limitations
- Only binary metamorphic relations and single-input transformations are considered.
- No gains on the AIDS GED dataset with node labels.
- Evaluated on only three tasks with small-scale base models.
Experimental setup
Datasets: SR(n) SAT instances TSP(dev) Decision TSP instances AIDS IMDB LINUX
Benchmarks: SR(40) SR(80) SR(120) TSP(0.01) TSP(0.02) AIDS LINUX IMDB
Metrics: accuracy RMSE
Baselines: NeuroSAT TSP-GNN GREED standard TTA
Builds on: test-time augmentation metamorphic testing message passing neural network
Closest papers by meaning
- What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization (ICLR 2022 · similarity 0.86)
- Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation (AAAI 2020 · similarity 0.86)
- ConRep4CO: Contrastive Representation Learning of Combinatorial Optimization Instances across Types (ICLR 2026 · similarity 0.86)
- Machine Learning meets Algebraic Combinatorics: A Suite of Datasets Capturing Research-level Conjecturing Ability in Pure Mathematics (ICML 2025 · similarity 0.85)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.85)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.