A Framework for Solving Graph Optimization Problems Based on Graph Neural Networks

Background and Research Motivation

In solving Constraint Satisfaction Problems (CSPs) and Combinatorial Optimization Problems (COPs), a common method is the combination of backtracking and branch heuristics. Although branch heuristics designed for specific problems are theoretically efficient, their complexity and difficulty in implementation limit practical application. On the contrary, general branch heuristics, despite their broad applicability, often exhibit suboptimal performance. The authors of this paper propose a new solving framework by introducing Shannon Entropy into branch heuristics, aiming to strike a balance between generality and specificity. Specifically, the framework employs Graph Neural Network (GNN) models to learn these probability distributions from loss functions derived from probabilistic methods and applies them to two NP-hard problems: the Minimum Dominating Clique Problem and the Edge Clique Cover Problem.

Authors and Publication Information

The paper was authored by Congsong Zhang, Yong Gao, and James Nastos, who are affiliated with the University of British Columbia and Okanagan College in Canada. It was published in the IEEE Transactions on Neural Networks and Learning Systems, with the acceptance date of April 30, 2024.

Detailed Research Process

1. Research Process

a. Problem Modeling and Probability Distribution Learning: Initially, the authors use graphs as input and define corresponding models for the two aforementioned NP-hard problems. In these graph models, node features are mapped to multidimensional probability distributions. These probability distributions are obtained through training with the Graph Neural Network.

b. Branch Heuristic Based on Shannon Entropy: Based on the probability distributions learned from the GNN model, the paper uses Shannon Entropy as heuristics for branch selection; that is, guiding the search path towards areas of minimal uncertainty under the current partial assignment.

c. Design of the Loss Function: The authors incorporate probablistic methods into the loss function to optimize the probability space, ensuring that solutions to the graph optimization problem can be found in regions with the highest probability. Moreover, to minimize the size of the expected solution, the loss function is designed to combine Shannon Entropy with other attributes of the minimum dominating clique.

d. Implementation and Testing: The GNN model is implemented based on PyTorch and trained and tested on a large amount of graph-based data. The trained model is then applied to real datasets for validation.

2. Experiments and Results

a. Comparison with Existing Methods: By comparing it with existing algorithms, the paper demonstrates the effective performance of this framework in reducing the number of branches. For example, compared to the method by Culberson et al. (2005), this framework significantly reduces the number of generated branches in solving the Minimum Dominating Clique Problem.

b. Performance and Run-time: Although in some cases the runtime using this framework is longer, the reduction in the number of branches indicates the potential long-term advantages of this method in practical applications. Furthermore, by introducing parallel computing and Taylor Expansion approximations to solve the Shannon Entropy function, runtime is expected to improve significantly.

c. Validation with Real Data: Experiments on the “GitHub Stargazers” dataset further validate the effectiveness of this framework in real-world networks. Despite the training data being from random graph models, the framework still outperforms traditional algorithms on real datasets.

Conclusions and Extensions

The framework based on Graph Neural Networks proposed in this paper successfully demonstrates effectiveness in solving graph optimization problems, particularly in the Minimum Dominating Clique and Edge Clique Cover problems. Additionally, the paper suggests that in the future, this approach will be further explored in other types of graph optimization problems, such as SAT problems. The introduction of this method opens a new direction for integrating GNN technology to improve classical AI algorithms.

Research Highlights

• Innovation: A new branch selection heuristic is proposed by combining Shannon Entropy with the probability distributions of Graph Neural Networks.
• Generalization Capability: Despite training on random graph models, it exhibits outstanding performance on real datasets.
• Improvement in Results: Compared to traditional methods, this framework shows excellent performance in reducing branch numbers, providing a new perspective for reducing worst-case runtime.