Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

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

Created by
  • Haebom

Author

Xiang Li, Shanshan Wang, Chenglong Xiao

Outline

This paper proposes a learning-based framework to solve the algorithm selection problem for the maximum clique problem (MCP). We applied four existing accurate MCP algorithms to various graph instances to build a labeled dataset and extract structural and global statistical features from each graph. We evaluated existing classifiers, including support vector machines (SVMs), random forests (RFs), decision trees (DTs), and k-nearest neighbors (KNNs), and found that RFs demonstrated stable performance. Building on this, we developed GAT-MLP, a dual-channel model that combines graph attention networks (GATs) for local structural encoding and multilayer perceptrons (MLPs) for global feature modeling. The GAT-MLP model demonstrated robust and consistent performance across all metrics, highlighting the effectiveness of the dual-channel architecture and graph neural networks.

Takeaways, Limitations

•
Takeaways:
◦
We demonstrate the effectiveness of a learning-based framework for algorithm selection for the maximum clique problem.
◦
Presenting the possibility of algorithm selection using graph neural networks (especially GAT).
◦
We reveal that connectivity and topological structure are important factors in predicting algorithm performance.
◦
We suggest that RF and GAT-MLP models are effective algorithm selection models.
•
Limitations:
◦
Lack of specific description of the variety and scale of graph instances used.
◦
Further comparative analysis with other algorithms or models may be required.
◦
Further application and performance evaluation for real-world applications are required.
◦
There is a possibility that the results may be biased towards certain types of graphs.
👍
Made with Slashpage