Ising on the Graph: Task-Specific Graph Subsampling via the Ising Model

Maria Bånkestad, Jennifer R. Andersson, Sebastian Mair, Jens Sjölund
Proceedings of the Third Learning on Graphs Conference, PMLR 269:6:1-6:29, 2025.

Abstract

Reducing a graph while preserving its overall properties is an important problem with many applications. Typically, reduction approaches either remove edges (sparsification) or merge nodes (coarsening) in an unsupervised way with no specific downstream task in mind. In this paper, we present an approach for subsampling graph structures using an Ising model defined on either the nodes or edges and learning the external magnetic field of the Ising model using a graph neural network. Our approach is task-specific as it can learn how to reduce a graph for a specific downstream task in an end-to-end fashion without requiring a differentiable loss function for the task. We showcase the versatility of our approach on four distinct applications: image segmentation, explainability for graph classification, 3D shape sparsification, and sparse approximate matrix inverse determination.

Cite this Paper

BibTeX
@InProceedings{pmlr-v269-bankestad25a, title = {Ising on the Graph: Task-Specific Graph Subsampling via the Ising Model}, author = {B{\aa}nkestad, Maria and Andersson, Jennifer R. and Mair, Sebastian and Sj{\"o}lund, Jens}, booktitle = {Proceedings of the Third Learning on Graphs Conference}, pages = {6:1--6:29}, year = {2025}, editor = {Wolf, Guy and Krishnaswamy, Smita}, volume = {269}, series = {Proceedings of Machine Learning Research}, month = {26--29 Nov}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v269/main/assets/bankestad25a/bankestad25a.pdf}, url = {https://proceedings.mlr.press/v269/bankestad25a.html}, abstract = {Reducing a graph while preserving its overall properties is an important problem with many applications. Typically, reduction approaches either remove edges (sparsification) or merge nodes (coarsening) in an unsupervised way with no specific downstream task in mind. In this paper, we present an approach for subsampling graph structures using an Ising model defined on either the nodes or edges and learning the external magnetic field of the Ising model using a graph neural network. Our approach is task-specific as it can learn how to reduce a graph for a specific downstream task in an end-to-end fashion without requiring a differentiable loss function for the task. We showcase the versatility of our approach on four distinct applications: image segmentation, explainability for graph classification, 3D shape sparsification, and sparse approximate matrix inverse determination.} }
Endnote
%0 Conference Paper %T Ising on the Graph: Task-Specific Graph Subsampling via the Ising Model %A Maria Bånkestad %A Jennifer R. Andersson %A Sebastian Mair %A Jens Sjölund %B Proceedings of the Third Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2025 %E Guy Wolf %E Smita Krishnaswamy %F pmlr-v269-bankestad25a %I PMLR %P 6:1--6:29 %U https://proceedings.mlr.press/v269/bankestad25a.html %V 269 %X Reducing a graph while preserving its overall properties is an important problem with many applications. Typically, reduction approaches either remove edges (sparsification) or merge nodes (coarsening) in an unsupervised way with no specific downstream task in mind. In this paper, we present an approach for subsampling graph structures using an Ising model defined on either the nodes or edges and learning the external magnetic field of the Ising model using a graph neural network. Our approach is task-specific as it can learn how to reduce a graph for a specific downstream task in an end-to-end fashion without requiring a differentiable loss function for the task. We showcase the versatility of our approach on four distinct applications: image segmentation, explainability for graph classification, 3D shape sparsification, and sparse approximate matrix inverse determination.
APA
Bånkestad, M., Andersson, J.R., Mair, S. & Sjölund, J.. (2025). Ising on the Graph: Task-Specific Graph Subsampling via the Ising Model. Proceedings of the Third Learning on Graphs Conference, in Proceedings of Machine Learning Research 269:6:1-6:29 Available from https://proceedings.mlr.press/v269/bankestad25a.html.

Related Material