未達成の期待：最大独立集合におけるAI手法と古典アルゴリズムの比較

arXiv stat.ML / 2026/4/28

💬 オピニオンDeveloper Stack & InfrastructureIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、最大独立集合（MIS）問題に対して、GPUベースのAIインスパイア手法（生成モデルや強化学習アプローチを含む）と古典的なCPUソルバをベンチマーク比較します。
イン分布のランダムグラフでさえ、シングルCPU上の最先端古典ソルバKaMISが、主要なAIインスパイア手法を一貫して上回り、さらにそれらはしばしば単純な次数ベースの貪欲法にも勝てないことが示されます。
後処理としてローカルサーチを追加してもギャップは埋まらず、AIインスパイア手法はKaMISに対して依然として劣ります。
著者らは「serialization」という新しい分析を導入し、非バックトラッキング型のAIインスパイア手法（例：GFlowNetsに基づくLTFT）が、実質的に最も単純な次数貪欲と同様の推論に行き着くことで性能が低い理由を説明します。
その結果は、AI for COの現行アプローチを見直し、より厳密なベンチマークと古典ヒューリスティックの原理に基づく統合を重視する必要があることを示唆し、加えてKaMISが疎なランダムグラフで強い性能を示す一方で、独立集合に関するシャッタリング閾値の予想は現実的な規模（例：ノード数10^6程度）では成り立たない可能性があると報告します。

要旨: 生成モデルや強化学習などのAI手法は、最近、組合せ最適化（CO）問題、特にNP困難な問題に適用されている。本論文では、最大独立集合（MIS）問題において、GPUベースの手法と、古典的なCPUベースの手法を比較する。驚くべきことに、分布内（in-distribution）のランダムグラフ上でさえ、AIに着想を得た主要な手法は、一つのCPU上で動作する最先端の古典的ソルバKaMISに一貫して劣り、さらにいくつかのAIに着想を得た手法は、最も単純な次数ベースの貪欲ヒューリスティックでさえ上回れずに失敗することが多い。局所探索のような事後処理技術を用いても、AIに着想を得た手法の性能はCPUベースのソルバより劣る。これらの失敗の原因をよりよく理解するために、本論文では新しい解析であるserialization（直列化）を導入し、非バックトラック型のAIに着想を得た手法、例えばLTFT（GFlowNetsに基づく）では、最も単純な次数ベースの貪欲と同様の推論に行き着き、したがってKaMISよりも劣ることを明らかにする。より一般に、本研究の結果は、COに対するAIの現在のアプローチを再考する必要性を示唆しており、より厳密なベンチマークと、原理に基づく古典的ヒューリスティックの統合を提唱する。さらに我々は、CPUベースのアルゴリズムであるKaMISが疎なランダムグラフで強い性能を示すことも見出しており、Coja-Oghlan & Efthymiou（2015）が提案した、大きな独立集合に対するシャッタリング閾値に関する予想が、実生活の規模（例えば10^6ノード）には当てはまらないことを示しているように見える。