arXiv:2508.08005cs.LGcs.AI2025-08

用双通道神经网络自动选最优图算法,准确率达90.43%。

Learning to Select Maximum Clique Algorithms: From Traditional Machine Learning to a Dual-Channel Hybrid Neural Architecture

  • 融合图注意力与多层感知机,同时捕捉局部与全局图特征。
  • 在多个图数据集上,选优准确率达90.43%,优于单个最佳求解器。
  • 适合需要高效解决最大团问题的研究者,如生物信息学与社交网络分析。

最大团问题(MCP)是广泛应用于生物信息学、网络科学和社交计算中的NP难问题,但现有算法在不同图实例上表现差异大,缺乏普适性。为此,我们提出一种结合传统机器学习与图神经网络的新型学习框架。首先,基于四种先进精确求解器在多样化图上的运行结果,构建了基准数据集,并提取结构特征。实验表明,随机森林为强基线,连通性与拓扑特征是性能的关键预测因子。在此基础上,我们设计了GAT-MLP双通道模型:利用图注意力网络(GAT)编码局部图结构,通过多层感知机(MLP)建模全局特征。实验显示,GAT-MLP优于所有基线,所提选择器显著超越单一最优求解器,实现90.43%的最优求解器选择准确率。结果验证了双通道架构的有效性及图神经网络在组合算法选择中的潜力。代码与模型已公开于https://anonymous.4open.science/r/GAT-MLP-7E5F。

原文摘要 · Abstract (English)

The Maximum Clique Problem (MCP) is an NP-hard problem with wide-ranging applications in fields such as bioinformatics, network science, and social computing, yet no single algorithm consistently outperforms all others across diverse graph instances. This underscores the critical need for instance-aware algorithm selection, a domain that remains largely unexplored for the MCP. To address this gap, we propose a novel learning-based framework that integrates both traditional machine learning and graph neural networks. We first construct a benchmark dataset by executing four state-of-the-art exact MCP solvers on a diverse collection of graphs and extracting structural features. An evaluation of conventional classifiers establishes Random Forest as a strong baseline and reveals that connectivity and topological features are key predictors of performance. Building on these insights, we develop GAT-MLP, a dual-channel model that combines a Graph Attention Network (GAT) to encode local graph structure with a Multilayer Perceptron (MLP) to model global features. Experiments demonstrate that GAT-MLP outperforms all baselines, and our selector significantly outperforms the Single Best Solver. Our results highlight the effectiveness of the dual-channel architecture and the promise of graph neural networks for combinatorial algorithm selection, achieving 90.43% accuracy in choosing the optimal solver. Code and models are available at: https://anonymous.4open.science/r/GAT-MLP-7E5F.

图神经网络算法选择最大团问题双通道架构

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。