Ising on the Graph: Task-specific Graph Subsampling via the Ising Model
This addresses the need for task-specific graph reduction methods, which is incremental as it builds on existing unsupervised reduction techniques by incorporating task-specific learning.
The paper tackles the problem of reducing graph structures for specific downstream tasks by introducing a task-specific subsampling approach using an Ising model with a graph neural network to learn the external magnetic field, achieving versatility across applications such as image segmentation, explainability, 3D shape sparsification, and sparse matrix inverse determination.
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.