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

Area of Science:

• Artificial Intelligence
• Computer Science
• Graph Theory

Background:

• Machine learning, particularly supervised and reinforcement learning, is increasingly used for combinatorial optimization.
• Existing methods often require large datasets of problem instances for training.
• Neural networks offer a promising avenue for solving complex discrete structure problems.

Purpose of the Study:

• To propose a novel, dataless training approach for neural networks in combinatorial optimization.
• To apply this method to the maximum independent set problem.
• To develop a universal graph reduction technique for large-scale graphs.

Main Methods:

• A dataless training scheme using neural networks, where backpropagation refines network parameters based on the architecture's loss function, not external data.
• Reduction of the maximum independent set problem to a neural network architecture.
• A universal graph reduction procedure leveraging community detection for partitioning large graphs.

Main Results:

• The proposed dataless neural network approach successfully finds maximum independent sets.
• Experimental results show performance on par with or exceeding state-of-the-art learning-based methods.
• The method requires no training data, making it data-efficient.

Conclusions:

• Dataless neural network training is a viable and effective approach for combinatorial optimization.
• This method offers a competitive alternative to data-dependent machine learning techniques.
• The universal graph reduction procedure enables scalability to large, complex graphs.