Ising on the Graph: Task-specific Graph Subsampling via the Ising Model
Reducing a graph while preserving its overall structure 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. For this, the task's loss function does not have to be differentiable. 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph ClassificationGraph Neural NetworkImage SegmentationSemantic SegmentationSimilar Papers 제목 키워드 기반
Graph-Based Model-Agnostic Data Subsampling for Recommendation Systems
Data subsampling is widely used to speed up the training of large-scale recommendation systems. Most subsampling methods are model-based and often require a pre-trained pilot model to measure data importance via e.g. sam…
Recommendation SystemsModel-based Subsampling for Knowledge Graph Completion
Subsampling is effective in Knowledge Graph Embedding (KGE) for reducing overfitting caused by the sparsity in Knowledge Graph (KG) datasets. However, current subsampling approaches consider only frequencies of queries t…
Graph EmbeddingKnowledge Graph CompletionKnowledge Graph EmbeddingmodelSubsampling for Knowledge Graph Embedding Explained
In this article, we explain the recent advance of subsampling methods in knowledge graph embedding (KGE) starting from the original one used in word2vec.
Graph EmbeddingKnowledge Graph EmbeddingSubsampling Graphs with GNN Performance Guarantees
How can we subsample graph data so that a graph neural network (GNN) trained on the subsample achieves performance comparable to training on the full dataset? This question is of fundamental interest, as smaller datasets…
Graph Neural NetworkModel SelectionSubsampling of Correlated Graph Signals
Graph signals are functions of the underlying graph. When the edge-weight between a pair of nodes is high, the corresponding signals generally have a higher correlation. As a result, the signals can be represented in ter…