論文の概要: Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining
- arxiv url: http://arxiv.org/abs/2512.20915v1
- Date: Wed, 24 Dec 2025 03:43:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-12-25 19:43:21.66673
- Title: Towards a General Framework for Predicting and Explaining the Hardness of Graph-based Combinatorial Optimization Problems using Machine Learning and Association Rule Mining
- Title（参考訳）: 機械学習とアソシエーションルールマイニングを用いたグラフベースの組合せ最適化問題の難易度予測と説明のための汎用フレームワーク
- Authors: Bharat Sharman, Elkafi Hassini,
- Abstract要約: GCO-HPIFは、グラフ上で表現できる最適化問題の計算困難性を予測し、説明するための機械学習ベースのフレームワークである。
これは、COLLAB、IMDB、TWITTERグラフデータセットからコンパイルされた3287の最大傾き問題のデータセットに適用された。
このフレームワークは、重み付きF1スコアが0.9921、マイノリティークラスF1スコアが0.878、ROC-AUCスコアが0.9083、インスタンスの硬さを予測するのに優れた性能を示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This study introduces GCO-HPIF, a general machine-learning-based framework to predict and explain the computational hardness of combinatorial optimization problems that can be represented on graphs. The framework consists of two stages. In the first stage, a dataset is created comprising problem-agnostic graph features and hardness classifications of problem instances. Machine-learning-based classification algorithms are trained to map graph features to hardness categories. In the second stage, the framework explains the predictions using an association rule mining algorithm. Additionally, machine-learning-based regression models are trained to predict algorithmic computation times. The GCO-HPIF framework was applied to a dataset of 3287 maximum clique problem instances compiled from the COLLAB, IMDB, and TWITTER graph datasets using five state-of-the-art algorithms, namely three exact branch-and-bound-based algorithms (Gurobi, CliSAT, and MOMC) and two graph-neural-network-based algorithms (EGN and HGS). The framework demonstrated excellent performance in predicting instance hardness, achieving a weighted F1 score of 0.9921, a minority-class F1 score of 0.878, and an ROC-AUC score of 0.9083 using only three graph features. The best association rule found by the FP-Growth algorithm for explaining the hardness predictions had a support of 0.8829 for hard instances and an overall accuracy of 87.64 percent, underscoring the framework's usefulness for both prediction and explanation. Furthermore, the best-performing regression model for predicting computation times achieved a percentage RMSE of 5.12 and an R2 value of 0.991.
- Abstract（参考訳）: 本稿では,グラフ上で表現可能な組合せ最適化問題の計算困難さを予測・説明するための一般機械学習ベースのフレームワークであるGCO-HPIFを紹介する。
フレームワークは2つのステージで構成されます。
第一段階では、問題に依存しないグラフ特徴と問題インスタンスの硬度分類からなるデータセットを作成する。
機械学習に基づく分類アルゴリズムは、グラフの特徴を硬度カテゴリにマップするために訓練される。
第2段階では、このフレームワークは相関ルールマイニングアルゴリズムを用いて予測を説明する。
さらに、機械学習に基づく回帰モデルは、アルゴリズムの計算時間を予測するために訓練される。
GCO-HPIFフレームワークは、COLLAB、IMDB、TWITTERグラフデータセットからコンパイルされた3287の最大傾き問題のデータセットに適用された。
このフレームワークは、重み付きF1スコアが0.9921、マイノリティークラスF1スコアが0.878、ROC-AUCスコアが0.9083、インスタンスの硬さを予測するのに優れた性能を示した。
FP-Growthアルゴリズムがハードネス予測を説明するための最良の関連ルールは、ハードインスタンスに対する0.8829、全体的な精度87.64パーセントであり、このフレームワークが予測と説明の両方に有用であることを示している。
さらに,計算時間予測における最良の回帰モデルでは,RMSEが5.12,R2が0.991であった。
関連論文リスト
- Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP [8.6217237605907]
単一の最大傾きアルゴリズムは、全てのインスタンスで常に最善を尽くす。
従来の機械学習とグラフニューラルネットワークを統合した学習ベースのフレームワークを提案する。
論文 参考訳（メタデータ） (2025-08-11T14:09:58Z) - A Structure-Aware Framework for Learning Device Placements on Computation Graphs [15.282882425920064]
我々は,OpenVINOツールキットから抽出したより小さな計算グラフに頼って,デバイス配置作業のための新しいフレームワークを提案する。
このフレームワークは、グラフの粗大化、ノード表現学習、ポリシー最適化を含む5つのステップで構成されている。
フレームワーク全体をトレーニングするために,配置の実行時間を用いた強化学習を報奨として使用する。
論文 参考訳（メタデータ） (2024-05-23T05:29:29Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - M3C: A Framework towards Convergent, Flexible, and Unsupervised Learning
of Mixture Graph Matching and Clustering [57.947071423091415]
本稿では,理論収束を保証する学習自由度アルゴリズムであるM3Cを提案する。
我々は、新しいエッジワイド親和性学習と擬似ラベル選択を組み込んだ教師なしモデルUM3Cを開発した。
提案手法は,最先端のグラフマッチングと混合グラフマッチングとクラスタリングの手法を精度と効率の両面で優れている。
論文 参考訳（メタデータ） (2023-10-27T19:40:34Z) - Learning Regularized Graphon Mean-Field Games with Unknown Graphons [155.38727464526923]
グラフィック平均フィールドゲーム(GMFG)のための強化学習アルゴリズムを設計する。
我々は、正規化されたGMFGのナッシュ平衡(NE)を、グラフンが未知のときに学習することを目指している。
これらのアルゴリズムは、サンプルエージェントからグラモンを学習するために設計された最初のものである。
論文 参考訳（メタデータ） (2023-10-26T16:19:24Z) - Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。
すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-06-15T16:25:27Z) - Node Feature Extraction by Self-Supervised Multi-scale Neighborhood
Prediction [123.20238648121445]
我々は、新しい自己教師型学習フレームワーク、グラフ情報支援ノード機能exTraction (GIANT)を提案する。
GIANT は eXtreme Multi-label Classification (XMC) 形式を利用しており、これはグラフ情報に基づいた言語モデルの微調整に不可欠である。
我々は,Open Graph Benchmarkデータセット上での標準GNNパイプラインよりもGIANTの方が優れた性能を示す。
論文 参考訳（メタデータ） (2021-10-29T19:55:12Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Neural Stochastic Block Model & Scalable Community-Based Graph Learning [8.00785050036369]
本稿では,グラフ学習のためのスケーラブルなコミュニティベースニューラルネットワークを提案する。
このフレームワークは,コミュニティ検出とリンク予測のタスクを通じて,グラフトポロジを学習する。
グラフアライメントと異常相関検出の2つの応用について検討する。
論文 参考訳（メタデータ） (2020-05-16T03:28:50Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳（メタデータ） (2020-02-20T09:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。