Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

被引：16
作者：
Angelini, Maria Chiara [1 ,2 ]
Ricci-Tersenghi, Federico [1 ,2 ,3 ]
机构：
[1] Sapienza Univ Roma, Dipartimento Fis, Rome, Italy
[2] Ist Nazl Fis Nucl, Rome, Italy
[3] Inst Nanotechnol NANOTEC CNR, Rome unit, Rome, Italy
来源：
NATURE MACHINE INTELLIGENCE | 2023年 / 5卷 / 01期
基金：
欧盟地平线“2020”;
关键词：
D O I：
10.1038/s42256-022-00589-y
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
引用
收藏
页码：29 / 31
页数：3
相关论文
共 18 条
[1]   Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs [J].
Angelini, Maria Chiara ;
Ricci-Tersenghi, Federico .
PHYSICAL REVIEW E, 2019, 100 (01)
[2]   The hard-core model on random graphs revisited [J].
Barbier, Jean ;
Krzakala, Florent ;
Zdeborova, Lenka ;
Zhang, Pan .
ELC INTERNATIONAL MEETING ON INFERENCE, COMPUTATION, AND SPIN GLASSES (ICSG2013), 2013, 473
[3]   Machine learning for combinatorial optimization: A methodological tour d'horizon [J].
Bengio, Yoshua ;
Lodi, Andrea ;
Prouvost, Antoine .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 290 (02) :405-421
[4]   Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems [J].
Boettcher, Stefan .
NATURE MACHINE INTELLIGENCE, 2023, 5 (01) :24-25
[5]   APPROXIMATING MAXIMUM INDEPENDENT SETS BY EXCLUDING SUBGRAPHS [J].
BOPPANA, R ;
HALLDORSSON, MM .
BIT, 1992, 32 (02) :180-196
[6]  
Cameron C, 2020, AAAI CONF ARTIF INTE, V34, P3324
[7]  
Cappart Q., 2021, PREPRINT
[8]   Parallel tempering for the planted clique problem [J].
Chiara, Angelini Maria .
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2018,
[9]   On Independent Sets in Random Graphs [J].
Coja-Oghlan, Amin ;
Efthymiou, Charilaos .
RANDOM STRUCTURES & ALGORITHMS, 2015, 47 (03) :436-486
[10]  
Deshpande Y, 2015, FOUND COMPUT MATH, V15, P1069, DOI 10.1007/s10208-014-9215-y
12