Deep Learning Approaches for Solving Graph Optimization Problems

Background Graph optimization is a subclass of combinatorial optimization with many NP‑hard problems such as traveling salesman, maximum independent set, and max‑cut, widely applied in network analysis, chip design, and image processing.

Traditional algorithms fall into exact, approximation, and heuristic categories, but they suffer from weak generalization, low efficiency, and high difficulty for large‑scale instances.

Motivation for Deep Learning Deep learning can automatically learn patterns from large data, offering better generalization across different graph problems, the ability to discover useful properties missed by handcrafted heuristics, and applicability to multiple optimization tasks.

Existing Research and Challenges Current work explores supervised, reinforcement, and unsupervised learning for graph optimization. Challenges include obtaining optimal labels for supervised learning, scalability of reinforcement methods, and designing effective unsupervised loss functions. Two major challenges remain: insufficient capture of structural/semantic information and over‑fitting to specific instances.

Solution Idea and Implementation The authors propose a self‑supervised framework for graph clustering optimization, dividing problems into centroid‑based (e.g., facility location) and non‑centroid‑based (e.g., balanced graph partitioning). The model consists of three stages: Pre‑Training with graph contrastive learning, Fine‑Tuning (partial or full) with task‑specific heads, and Rounding to obtain feasible solutions.

The graph encoder combines feature, degree, and distance encodings, and contrastive learning provides self‑supervised signals to improve clustering quality.

Experiments The method (GCOM) is evaluated on synthetic ER graphs and real‑world datasets (Starbucks store locations, citation networks). Results show competitive or superior performance compared to Gurobi, greedy heuristics, and other deep learning baselines on facility location and balanced partitioning tasks, with good generalization across graph sizes and distributions.

Additional studies examine the sensitivity of the balance coefficient λ, demonstrating that λ=10 yields a good trade‑off between edge density and partition balance, and ablation experiments confirm the effectiveness of contrastive learning, degree encoding, and distance encoding.

Future Outlook The authors aim to extend the approach to more constrained graph problems (e.g., graph coloring, maximum independent set), build a universal deep‑learning‑based graph optimizer (GOPT), and further integrate traditional operations research methods with deep learning techniques.