Maximum Independent Set: Self-Training through Dynamic Programming
This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursive call. To train our algorithm, we require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-world datasets.
Code (1)
Tasks
Graph Neural NetworkMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Learning for Dynamic Combinatorial Optimization without Training Data
We introduce DyCO-GNN, a novel unsupervised learning framework for Dynamic Combinatorial Optimization that requires no training data beyond the problem instance itself. DyCO-GNN leverages structural similarities across t…
Combinatorial OptimizationTraveling Salesman ProblemEBMs Trained with Maximum Likelihood are Generator Models Trained with a Self-adverserial Loss
Maximum likelihood estimation is widely used in training Energy-based models (EBMs). Training requires samples from an unnormalized distribution, which is usually intractable, and in practice, these are obtained by MCMC …
Self-supervised Low Light Image Enhancement and Denoising
This paper proposes a self-supervised low light image enhancement method based on deep learning, which can improve the image contrast and reduce noise at the same time to avoid the blur caused by pre-/post-denoising. The…
DenoisingImage EnhancementLow-Light Image EnhancementMultimodal Functional Maximum Correlation for Emotion Recognition
Emotional states manifest as coordinated yet heterogeneous physiological responses across central and autonomic systems, posing a fundamental challenge for multimodal representation learning in affective computing. Learn…
Self-Supervised LearningRepresentation LearningEmotion RecognitionMaximum Entropy Population-Based Training for Zero-Shot Human-AI Coordination
We study the problem of training a Reinforcement Learning (RL) agent that is collaborative with humans without using any human data. Although such agents can be obtained through self-play training, they can suffer signif…
DiversityReinforcement Learning (RL)