A differentiable approach to the maximum independent set problem using dataless neural networks.
Neural Netw
; 155: 168-176, 2022 Nov.
Article
em En
| MEDLINE
| ID: mdl-36057182
ABSTRACT
The success of machine learning solutions for reasoning about discrete structures has brought attention to its adoption within combinatorial optimization algorithms. Such approaches generally rely on supervised learning by leveraging datasets of the combinatorial structures of interest drawn from some distribution of problem instances. Reinforcement learning has also been employed to find such structures. In this paper, we propose a different approach in that no data is required for training the neural networks that produce the solution. In this sense, what we present is not a machine learning solution, but rather one that is dependent on neural networks and where backpropagation is applied to a loss function defined by the structure of the neural network architecture as opposed to a training dataset. In particular, we reduce the popular combinatorial optimization problem of finding a maximum independent set to a neural network and employ a dataless training scheme to refine the parameters of the network such that those parameters yield the structure of interest. Additionally, we propose a universal graph reduction procedure to handle large-scale graphs. The reduction exploits community detection for graph partitioning and is applicable to any graph type and/or density. Experimental results on both real and synthetic graphs demonstrate that our proposed method performs on par or outperforms state-of-the-art learning-based methods in terms of the size of the found set without requiring any training data.
Palavras-chave
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Algoritmos
/
Redes Neurais de Computação
Tipo de estudo:
Prognostic_studies
Idioma:
En
Revista:
Neural Netw
Assunto da revista:
NEUROLOGIA
Ano de publicação:
2022
Tipo de documento:
Article
País de publicação:
EEUU
/
ESTADOS UNIDOS
/
ESTADOS UNIDOS DA AMERICA
/
EUA
/
UNITED STATES
/
UNITED STATES OF AMERICA
/
US
/
USA