Comparative algorithm performance evaluation and prediction for the maximum clique problem using instance space analysis
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Neural NetworkSimilar Papers 제목 키워드 기반
Performance comparison of 3D correspondence grouping algorithm for 3D plant point clouds
Plant Phenomics can be used to monitor the health and the growth of plants. Computer vision applications like stereo reconstruction, image retrieval, object tracking, and object recognition play an important role in imag…
Image RetrievalObject RecognitionObject TrackingPlant Phenotyping+2A Comparative Evaluation of Machine Learning Algorithms for the Prediction of R/C Buildings' Seismic Damage
Seismic assessment of buildings and determination of their structural damage is at the forefront of modern scientific research. Since now, several researchers have proposed a number of procedures, in an attempt to estima…
BIG-bench Machine LearningA comparative study of general fuzzy min-max neural networks for pattern classification problems
General fuzzy min-max (GFMM) neural network is a generalization of fuzzy neural networks formed by hyperbox fuzzy sets for classification and clustering problems. Two principle algorithms are deployed to train this type …
BIG-bench Machine LearningClusteringGeneral ClassificationIncremental LearningFrom Conception to Deployment: Intelligent Stroke Prediction Framework using Machine Learning and Performance Evaluation
Stroke is the second leading cause of death worldwide. Machine learning classification algorithms have been widely adopted for stroke prediction. However, these algorithms were evaluated using different datasets and eval…
PredictionNMR shift prediction from small data quantities
Prediction of chemical shift in NMR using machine learning methods is typically done with the maximum amount of data available to achieve the best results. In some cases, such large amounts of data are not available, e.g…
Prediction