用实例空间分析法对比了最大团问题的算法表现并预测最佳选择。
Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
- 基于图特征与性能指标构建实例空间，系统评估算法表现。
- 精确算法MOMC在74.7%的实例中表现最优，Gurobi和CliSAT分别覆盖13.8%和11%。
- 对34个挑战性测试实例的预测准确率达97%（前两名），适合算法选型研究者。
最大团问题作为经典的图论组合优化问题，已有多种算法方法，但对问题实例的系统分析仍不足。本研究采用实例空间分析（ISA）方法，系统分析该问题的实例空间，并评估与预测当前先进算法（包括精确、启发式及图神经网络方法）的表现。数据集来自图机器学习常用基准TWITTER、COLLAB和IMDB-BINARY。采用33个通用与问题特异性多项式可计算的图特征（含若干谱属性）进行分析。使用结合解质量与运行时间的综合性能度量。对比结果显示，精确算法混合顺序最大团（MOMC）在所编数据集构成的约74.7%实例空间中表现最优；Gurobi与CliSAT分别在13.8%和11%的实例空间中领先。基于ISA的算法性能预测模型在34个来自BHOSLIB和DIMACS的挑战性测试实例上，实现前1名与前2名预测准确率分别为88%和97%。
原文摘要 · Abstract (English)
The maximum clique problem, a well-known graph-based combinatorial optimization problem, has been addressed through various algorithmic approaches, though systematic analyses of the problem instances remain sparse. This study employs the instance space analysis (ISA) methodology to systematically analyze the instance space of this problem and assess & predict the performance of state-of-the-art (SOTA) algorithms, including exact, heuristic, and graph neural network (GNN)-based methods. A dataset was compiled using graph instances from TWITTER, COLLAB and IMDB-BINARY benchmarks commonly used in graph machine learning research. A set of 33 generic and 2 problem-specific polynomial-time-computable graph-based features, including several spectral properties, was employed for the ISA. A composite performance measure incorporating both solution quality and algorithm runtime was utilized. The comparative analysis demonstrated that the exact algorithm Mixed Order Maximum Clique (MOMC) exhibited superior performance across approximately 74.7% of the instance space constituted by the compiled dataset. Gurobi & CliSAT accounted for superior performance in 13.8% and 11% of the instance space, respectively. The ISA-based algorithm performance prediction model run on 34 challenging test instances compiled from the BHOSLIB and DIMACS datasets yielded top-1 and top-2 best performing algorithm prediction accuracies of 88% and 97%, respectively.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。