Graphs are everywhere in science and engineering, and they are often too large to work with directly. The usual response is to reduce them, either by removing edges or by merging nodes. But classical reduction methods do this in the dark: they try to preserve the graph in general, with no idea of what the smaller graph will actually be used for. The result is often a graph that looks reasonable but throws away exactly the structure the downstream task needed.
We turn the problem around and let the task decide. The idea is to place an Ising model on the nodes or edges of the graph, where each element is kept or dropped according to a spin, and to learn the external magnetic field of that Ising model with a graph neural network (Bånkestad et al., 2025). Because the whole thing is trained end-to-end against the downstream objective, the model learns to keep precisely the structure that objective depends on. A useful consequence of working through the Ising model is that the task loss does not even have to be differentiable.
The same recipe transfers across very different problems. We demonstrate it on image segmentation, explainability for graph classification, 3D shape sparsification, and computing sparse approximate matrix inverses.
Task-specific subsampling of a 3D shape graph via the learned Ising model.
Reducing a graph while preserving its overall structure is an important problem with many applications. Typically, the 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. The utilized loss function of the task does not even have to be differentiable. We showcase the versatility of our approach on distinct applications, including image segmentation, explainability for graph classification, 3D shape sparsification, and sparse approximate matrix inverse determination.
@inproceedings{bankestad2025ising,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},series={Proceedings of Machine Learning Research},volume={269},publisher={PMLR},year={2025},}
