A differentiable approach to the maximum independent set problem using dataless neural networks

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 so...

Full description

Saved in:
Bibliographic Details
Published in:Neural networks 2022-11, Vol.155 (C), p.168-176
Main Authors: Alkhouri, Ismail R., Atia, George K., Velasquez, Alvaro
Format: Article
Language:English
Subjects:
Combinatorial optimization
Community detection
Computer Science
Dataless Neural Networks
MATHEMATICS AND COMPUTING
Maximum Clique problem
Maximum independent set problem
Neurosciences & Neurology
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0893-6080
1879-2782
DOI:10.1016/j.neunet.2022.08.008