Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP

• URL: http://arxiv.org/abs/2508.08005v2
• Date: Wed, 03 Sep 2025 14:44:40 GMT
• Title: Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP
• Authors: Xiang Li, Shanshan Wang, Chenglong Xiao,
• Abstract summary: No single maximum clique algorithm consistently performs best across all instances.<n>We propose a learning-based framework that integrates both traditional machine learning and graph neural networks.
• Score: 8.6217237605907
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Extensive experiments and prior studies show that no single maximum clique algorithm consistently performs best across all instances, highlighting the importance of selecting suitable algorithms based on instance features. Through an extensive analysis of relevant studies, it is found that there is a lack of research work concerning algorithm selection oriented toward the Maximum Clique Problem (MCP). In this work, we propose a learning-based framework that integrates both traditional machine learning and graph neural networks to address this gap. We construct a labeled dataset by running four exact MCP algorithms on a diverse collection of graph instances, accompanied by structural and global statistical features extracted from each graph. We first evaluate four conventional classifiers: Support Vector Machine (SVM), Random Forest (RF), Decision Tree (DT), and K-Nearest Neighbors (KNN), across multiple dataset variants. Experimental results show that RF consistently shows strong performance across metrics and dataset variants, making it a reliable baseline. In addition, feature importance analysis indicates that connectivity and topological structure are strong predictors of algorithm performance. Building on these findings, we develop a dual-channel model named GAT-MLP, which combines a Graph Attention Network (GAT) for local structural encoding with a Multilayer Perceptron (MLP) for global feature modeling. The GAT-MLP model shows strong and consistent performance across all metrics. Our results highlight the effectiveness of dual-channel architectures and the promise of graph neural networks in combinatorial algorithm selection.

Related papers

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant [1.8606770727950463]
  We propose several GNN-based architectures to tackle the graph partitioning problem for Markov Chains described as kinetic networks. This approach aims to minimize how much a proposed partitioning changes the Kemeny constant. We show how simple GraphSAGE-based GNNs with linear layers can outperform much larger and more expressive attention-based models in this context.
  arXiv  Detail & Related papers  (2023-12-22T17:19:50Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  Graph networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data.<n>There remains a lack of analysis comparing GNNs and generalizations from an optimization and generalization perspective.
  arXiv  Detail & Related papers  (2023-06-24T10:21:11Z)
• Fisher Information Embedding for Node and Graph Learning [5.263910852465186]
  We propose a novel attention-based node embedding framework for graphs. Our framework builds upon a hierarchical kernel for multisets of subgraphs around nodes. We provide theoretical insights into generalizability and expressivity of our embeddings.
  arXiv  Detail & Related papers  (2023-05-12T16:15:30Z)
• Learnable Graph Convolutional Attention Networks [7.465923786151107]
  Graph Neural Networks (GNNs) compute the message exchange between nodes by either aggregating uniformly (convolving) the features of all the neighboring nodes, or by applying a non-uniform score (attending) to the features. Recent works have shown the strengths and weaknesses of the resulting GNN architectures, respectively, GCNs and GATs. We introduce the graph convolutional attention layer (CAT), which relies on convolutions to compute the attention scores. Our results demonstrate that L-CAT is able to efficiently combine different GNN layers along the network, outperforming competing methods in a wide
  arXiv  Detail & Related papers  (2022-11-21T21:08:58Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  We propose a radically different approach in that no data is required for training the neural networks that produce the solution. In particular, we reduce the optimization problem 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.
  arXiv  Detail & Related papers  (2022-03-15T19:21:31Z)
• Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
  Distributed Constraint Optimization Problems (DCOPs) are an important subclass of optimization problems. We propose a novel directed acyclic graph schema representation for DCOPs and leverage the Graph Attention Networks (GATs) to embed graph representations. Our model, GAT-PCM, is then pretrained with optimally labelled data in an offline manner, so as to boost a broad range of DCOP algorithms.
  arXiv  Detail & Related papers  (2021-12-08T09:24:10Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each.
  arXiv  Detail & Related papers  (2020-12-23T09:33:11Z)
• Deep Reinforcement Learning of Graph Matching [63.469961545293756]
  Graph matching (GM) under node and pairwise constraints has been a building block in areas from optimization to computer vision. We present a reinforcement learning solver for GM i.e. RGM that seeks the node correspondence between pairwise graphs. Our method differs from the previous deep graph matching model in the sense that they are focused on the front-end feature extraction and affinity function learning.
  arXiv  Detail & Related papers  (2020-12-16T13:48:48Z)
• Cross-Domain Facial Expression Recognition: A Unified Evaluation Benchmark and Adversarial Graph Learning [85.6386289476598]
  We develop a novel adversarial graph representation adaptation (AGRA) framework for cross-domain holistic-local feature co-adaptation. We conduct extensive and fair evaluations on several popular benchmarks and show that the proposed AGRA framework outperforms previous state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-08-03T15:00:31Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.