Extending Test-Time Augmentation with Metamorphic Relations for Combinatorial Problems

Siwei Wei, Xudong Zhang, Zhiyang Zhou, Yan Cai
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:52658-52679, 2024.

Abstract

The application of machine learning methods to solve combinatorial problems has garnered considerable research interest. In this paper, we propose MAgg (Metamorphic Aggregation), a method to augment machine learning models for combinatorial problems at inference time using metamorphic relations. MAgg models metamorphic relations using directed graphs, which are then fed to a Graph Neural Network (GNN) model to improve the aggregation of predictions across transformed input instances. By incorporating metamorphic relations, MAgg essentially extends standard Test-Time Augmentation (TTA), eliminating the necessity of label-preserving transformations and expanding its applicability to a broader range of supervised learning tasks for combinatorial problems. We evaluate the proposed MAgg method on three mainstream machine learning tasks for combinatorial problems, namely Boolean Satisfiability Prediction (SAT), Decision Traveling Salesman Problem Satisfiability Prediction (Decision TSP), and Graph Edit Distance Estimation (GED). The evaluation result shows significant improvements over base models in all three tasks, corroborating the effectiveness and versatility of the proposed method.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-wei24i, title = {Extending Test-Time Augmentation with Metamorphic Relations for Combinatorial Problems}, author = {Wei, Siwei and Zhang, Xudong and Zhou, Zhiyang and Cai, Yan}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {52658--52679}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/wei24i/wei24i.pdf}, url = {https://proceedings.mlr.press/v235/wei24i.html}, abstract = {The application of machine learning methods to solve combinatorial problems has garnered considerable research interest. In this paper, we propose MAgg (Metamorphic Aggregation), a method to augment machine learning models for combinatorial problems at inference time using metamorphic relations. MAgg models metamorphic relations using directed graphs, which are then fed to a Graph Neural Network (GNN) model to improve the aggregation of predictions across transformed input instances. By incorporating metamorphic relations, MAgg essentially extends standard Test-Time Augmentation (TTA), eliminating the necessity of label-preserving transformations and expanding its applicability to a broader range of supervised learning tasks for combinatorial problems. We evaluate the proposed MAgg method on three mainstream machine learning tasks for combinatorial problems, namely Boolean Satisfiability Prediction (SAT), Decision Traveling Salesman Problem Satisfiability Prediction (Decision TSP), and Graph Edit Distance Estimation (GED). The evaluation result shows significant improvements over base models in all three tasks, corroborating the effectiveness and versatility of the proposed method.} }
Endnote
%0 Conference Paper %T Extending Test-Time Augmentation with Metamorphic Relations for Combinatorial Problems %A Siwei Wei %A Xudong Zhang %A Zhiyang Zhou %A Yan Cai %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-wei24i %I PMLR %P 52658--52679 %U https://proceedings.mlr.press/v235/wei24i.html %V 235 %X The application of machine learning methods to solve combinatorial problems has garnered considerable research interest. In this paper, we propose MAgg (Metamorphic Aggregation), a method to augment machine learning models for combinatorial problems at inference time using metamorphic relations. MAgg models metamorphic relations using directed graphs, which are then fed to a Graph Neural Network (GNN) model to improve the aggregation of predictions across transformed input instances. By incorporating metamorphic relations, MAgg essentially extends standard Test-Time Augmentation (TTA), eliminating the necessity of label-preserving transformations and expanding its applicability to a broader range of supervised learning tasks for combinatorial problems. We evaluate the proposed MAgg method on three mainstream machine learning tasks for combinatorial problems, namely Boolean Satisfiability Prediction (SAT), Decision Traveling Salesman Problem Satisfiability Prediction (Decision TSP), and Graph Edit Distance Estimation (GED). The evaluation result shows significant improvements over base models in all three tasks, corroborating the effectiveness and versatility of the proposed method.
APA
Wei, S., Zhang, X., Zhou, Z. & Cai, Y.. (2024). Extending Test-Time Augmentation with Metamorphic Relations for Combinatorial Problems. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:52658-52679 Available from https://proceedings.mlr.press/v235/wei24i.html.

Related Material