그래프 신경망은 네이처(Nature) 하위저널에 게재됐으나 일반 알고리즘보다 104배 느린 것으로 드러났다. 질문자: 새로운 높이인가?

GNN은 최근 몇 년간 매우 인기 있는 분야입니다. 최근 Nature 하위 저널 논문에서는 조합 최적화 문제를 해결하기 위해 GNN을 사용하는 방법을 제안했으며 GNN 최적화 프로그램의 성능이 기존 솔버와 동일하거나 심지어 그 이상이라고 주장했습니다. 그러나 이 논문은 몇 가지 의구심을 불러일으켰습니다. 일부 사람들은 이 GNN의 성능이 실제로 고전적인 탐욕 알고리즘만큼 좋지 않으며 속도가 탐욕 알고리즘보다 훨씬 느리다는 점을 지적했습니다(변수가 백만 개인 문제의 경우 탐욕스러운 알고리즘). 알고리즘은 GNN보다 104배 빠릅니다. 그래서 회의론자들은 "이 문제를 해결하기 위해 이러한 GNN을 사용해야 할 타당한 이유가 없습니다. 이는 큰 망치를 사용하여 견과류를 깨뜨리는 것과 같습니다."라고 말했습니다. 그들은 이 논문의 저자가 문제를 주장하기 전에 먼저 어려운 문제를 해결할 수 있기를 바랍니다. 방법의 우수성을 벤치마크와 비교해 보세요.

최근 몇 년 동안 신경망은 이산 조합 최적화 문제를 포함하여 응용 및 기초 과학의 많은 어려운 문제를 해결했으며 이는 컴퓨팅의 한계에 대한 이해의 기초이기도 합니다.

Martin JA Schuetz et al.의 2022년 연구 "물리학에서 영감을 받은 그래프 신경망을 사용한 조합 최적화"[4]에서는 물리학에서 영감을 받은 비지도 그래프 신경망(GNN)을 사용하여 그래프의 조합 최적화 문제를 해결할 것을 제안합니다. 접근 방식은 유망해 보이며 영향력이 큰 저널(Nature Machine Intelligence)에 게재되었습니다. 이 연구에서는 최대 절단 및 최대 독립 집합(MIS)이라는 두 가지 표준 최적화 문제에 대해 GNN의 성능을 테스트했습니다. 새로 제안된 이 GNN 최적화 프로그램은 매우 좋은 특성을 가지고 있습니다. 즉, 더 큰 인스턴스 문제로 확장될 수 있습니다.

논문 주소: https://arxiv.org/pdf/2107.01188.pdf

그러나 최근 새로운 논문 "큰 망치로 견과류 깨기: 현대 그래프 신경망이 다음보다 나쁠 때" 고전적인 탐욕 알고리즘"은 Martin JA Schuetz 등이 제안한 GNN 최적화 프로그램이 "모기를 때리는 박격포와 유사한 큰 망치로 견과류를 깨는 것"이라고 믿으며 Martin JA Schuetz 등의 연구에 의문을 제기했는데 이는 자원 낭비입니다. 그리고 결과가 좋지 않습니다.

문서 주소: https://arxiv.org/abs/2206.13211

MIS 문제는 다음과 같이 정의됩니다. n 노드와 차수가 d 그래프로 고정된 무방향 무작위 정규가 주어지면( d-RRG), 독립 집합(IS)은 가장 가까운 이웃 쌍을 포함하지 않는 정점의 하위 집합을 나타냅니다. MIS 문제는 크기가 α라고 불리는 가장 큰 IS를 찾는 데 필요합니다. MIS는 NP-하드 문제이지만 다항식 시간의 최대값에 최대한 가까운 크기를 가진 IS를 찾는 알고리즘을 찾고 싶습니다. 게다가, 좋은 알고리즘은 더 큰 n 값에 대해 성능 저하를 겪어서는 안 됩니다.

Martin JA Schuetz et al.이 제안한 새로운 GNN은 매우 큰 그래프(n≤ 10^6)에 대해 IS를 찾을 수 있습니다. 알고리즘 실행 시간은 문제 크기(t∼n^1.7)에 비례하며, 알고리즘은 n에 따라 성능이 증가합니다. 아래 그림 1에서 볼 수 있듯이 증가는 안정적으로 유지됩니다.

​

그러나 제안된 GNN의 성능을 다른 사용 가능한 알고리즘과 비교할 때 연구에서는 n≤일 때 사용되는 Boppana-Halldorsson(BH) 근사 알고리즘[8]과만 비교했습니다. 500일 때, 실행 시간은 t∼n^2.9입니다. ​

실제로 BH보다 훨씬 빠른 IS를 계산하는 다른 알고리즘이 많이 있으며 연구에서는 제안된 GNN 최적화 프로그램을 이러한 알고리즘과 비교해야 합니다. 그 중 가장 간단한 알고리즘은 탐욕 알고리즘(GA)이다[9]. DGA(Degree-Based Greedy Algorithm)가 최적화된 후 실행 시간은 노드 수 n에 거의 선형입니다. ​

이 연구는 d=3 및 d=5인 d-RRG에서 MIS를 찾는 데 있어 Martin JA Schuetz et al.이 제안한 GNN 옵티마이저(개방형)와 DGA(솔리드)의 성능을 비교합니다. 그림 1(오른쪽)과 같이 실행 시간과 문제 크기(노드 수)의 관계 측면에서 보면 DGA가 GNN보다 훨씬 낫습니다. 노드 n개(지수는 1.15임. 아마도 사전 점근 효과로 인해) GNN의 실행 시간은 노드 수 n과 거의 2차 관계를 갖습니다.

본 연구는 "그래프 신경망 기반 옵티마이저의 성능은 기존 솔버와 동등하거나 더 우수하며, 현재 SOTA 모델을 능가하는 능력을 갖고 있으며, "수백만 개의 변수 문제"는 정밀 조사를 견딜 수 없으며 실제 실험 결과와 일치하지 않습니다. Martin JA Schuetz와 다른 사람들은 논문을 수정해야 합니다. ​

이 연구에서는 DGA의 성능을 자세히 설명하고 이 단순한 그리디 알고리즘이 최소 벤치마크로 간주되어야 하며 새로운 알고리즘의 성능은 채택되기 전에 최소한 DGA보다 좋아야 한다고 믿습니다.

물론 DGA는 극히 단순한 알고리즘일 뿐이고, DGA보다 나은 다른 표준 알고리즘도 많이 있습니다. Maria Chiara 등의 2019년 논문 "Monte Carlo 알고리즘은 희소 무작위 그래프에서 가장 큰 독립 세트를 찾는 데 매우 효과적입니다."는 MIS 문제를 해결하기 위한 여러 알고리즘의 성능에 대한 심층적인 연구를 제공합니다. ​

이 연구는 "새로운 최적화 알고리즘을 평가할 때 알고리즘의 성능을 테스트하기 위한 벤치마크로 사용해야 하는 정말 어려운 문제는 무엇인가?"라는 질문을 던집니다. 연구에서는 d-RRG의 d 16 MIS를 믿습니다. 여기서 d=20 및 d=100에 대한 결과는 2019년 논문 "몬테카를로 알고리즘은 희소 무작위 그래프에서 가장 큰 독립 세트를 찾는 데 매우 효과적입니다"에 제공된 결과와 비교할 수 있습니다.

분명히 좋은 최적화 알고리즘은 n의 다항식 시간에 완료되어야 합니다. 관계가 선형이면 더 좋을 것입니다. 발견된 솔루션의 품질은 기존의 단순한 알고리즘보다 좋아야 하며 증가해서는 안 됩니다. n은 증가했지만 품질은 감소했습니다.

연구 결론: 현재 신경망 기반 최적화 프로그램(예: Martin JA Schuetz 등이 제안한 것)은 위의 요구 사항을 충족하지 않으며 어려운 최적화 문제를 해결하기 위해 간단한 표준 알고리즘과 경쟁할 수 없습니다. 신경망이 이 요구 사항을 충족할 수 있는지, 아니면 실패에 대한 더 깊은 이유가 있는지 탐색하는 것이 중요합니다.

위 내용은 그래프 신경망은 네이처(Nature) 하위저널에 게재됐으나 일반 알고리즘보다 104배 느린 것으로 드러났다. 질문자: 새로운 높이인가?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!