Ising on the Graph: Task-specific Graph Subsampling via the Ising Model
Maria Bånkestad Jennifer Andersson Sebastian Mair Jens Sjölund
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 three distinct
applications: image segmentation, 3D shape sparsification, and sparse
approximate matrix inverse determination.