論文の概要: Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP
- arxiv url: http://arxiv.org/abs/2508.08005v1
- Date: Mon, 11 Aug 2025 14:09:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-12 21:23:29.134958
- Title: Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP
- Title(参考訳): MCPアルゴリズムの選択学習:従来のMLからデュアルチャネルGAT-MLPへ
- Authors: Xiang Li, Shanshan Wang, Chenglong Xiao,
- Abstract要約: 単一の最大傾きアルゴリズムは、全てのインスタンスで常に最善を尽くす。
従来の機械学習とグラフニューラルネットワークを統合した学習ベースのフレームワークを提案する。
- 参考スコア(独自算出の注目度): 6.60165643740835
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Extensive experiments and prior studies show that no single maximum clique algorithm consistently performs best across all instances, highlighting the importance of selecting suitable algorithms based on instance features. Through an extensive analysis of relevant studies, it is found that there is a lack of research work concerning algorithm selection oriented toward the Maximum Clique Problem (MCP). In this work, we propose a learning-based framework that integrates both traditional machine learning and graph neural networks to address this gap. We construct a labeled dataset by running four exact MCP algorithms on a diverse collection of graph instances, accompanied by structural and global statistical features extracted from each graph. We first evaluate four conventional classifiers: Support Vector Machine (SVM), Random Forest (RF), Decision Tree (DT), and K-Nearest Neighbors (KNN), across multiple dataset variants. Experimental results show that RF consistently shows strong performance across metrics and dataset variants, making it a reliable baseline. In addition, feature importance analysis indicates that connectivity and topological structure are strong predictors of algorithm performance. Building on these findings, we develop a dual-channel model named GAT-MLP, which combines a Graph Attention Network (GAT) for local structural encoding with a Multilayer Perceptron (MLP) for global feature modeling. The GAT-MLP model shows strong and consistent performance across all metrics. Our results highlight the effectiveness of dual-channel architectures and the promise of graph neural networks in combinatorial algorithm selection.
- Abstract(参考訳): 広範囲にわたる実験と先行研究により、すべてのインスタンスで最高の最大傾きアルゴリズムが一貫して機能しないことが示され、インスタンスの特徴に基づいて適切なアルゴリズムを選択することの重要性が強調された。
関連する研究を幅広く分析した結果,最大傾き問題(MCP)を指向したアルゴリズム選択に関する研究成果が不足していることが判明した。
本研究では,従来の機械学習とグラフニューラルネットワークを統合し,このギャップに対処する学習ベースのフレームワークを提案する。
各グラフから抽出した構造的およびグローバルな統計的特徴を伴って,グラフインスタンスの多様なコレクション上で4つの正確なMPPアルゴリズムを実行することでラベル付きデータセットを構築する。
まず、SVM(Support Vector Machine)、RF(Random Forest)、DT(Decision Tree)、K-Nearest Neighbors(KNN)の4つの従来の分類器を、複数のデータセットの変種にわたって評価した。
実験結果から,RFは測定値やデータセットの変動に対して常に強い性能を示し,信頼性の高いベースラインとなっている。
さらに,特徴量分析により,接続性やトポロジ的構造がアルゴリズム性能の強い予測因子であることが示唆された。
これらの知見に基づいて,局所構造符号化のためのグラフアテンションネットワーク(GAT)とグローバルな特徴モデリングのための多層パーセプトロン(MLP)を組み合わせた,GAT-MLPというデュアルチャネルモデルを開発した。
GAT-MLPモデルは、すべてのメトリクスに対して強力で一貫したパフォーマンスを示す。
本研究は,2チャネルアーキテクチャの有効性と,組合せアルゴリズム選択におけるグラフニューラルネットワークの有効性を明らかにするものである。
関連論文リスト
- Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳(メタデータ) (2024-03-11T06:34:05Z) - Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant [1.8606770727950463]
我々は,マルコフ連鎖のグラフ分割問題に対処するGNNアーキテクチャをいくつか提案する。
このアプローチは、提案されたパーティショニングがケメニー定数をどの程度変更するかを最小化することを目的としている。
線形層を持つグラフSAGEベースのGNNが、この文脈でより大きく、より表現力に富んだアテンションベースモデルよりも優れていることを示す。
論文 参考訳(メタデータ) (2023-12-22T17:19:50Z) - Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
グラフネットワーク(GNN)は、グラフ構造化データから学習する際、顕著な能力を示した。
最適化と一般化の観点から、GNNと一般化を比較した分析の欠如がまだ残っている。
論文 参考訳(メタデータ) (2023-06-24T10:21:11Z) - Fisher Information Embedding for Node and Graph Learning [5.263910852465186]
本稿では,グラフのための新しい注目型ノード埋め込みフレームワークを提案する。
我々のフレームワークはノード周辺のサブグラフの多重集合のための階層的カーネル上に構築されている。
埋め込みの一般化性と表現性に関する理論的知見を提供する。
論文 参考訳(メタデータ) (2023-05-12T16:15:30Z) - Learnable Graph Convolutional Attention Networks [7.465923786151107]
グラフニューラルネットワーク(GNN)は、ノード間のメッセージ交換を、隣接するすべてのノードの特徴を均一に(関連する)集約するか、あるいは特徴に一様でないスコア(動作)を適用することによって計算する。
最近の研究は、それぞれGCNとGATのGNNアーキテクチャの長所と短所を示している。
本稿では、注目スコアを計算するために、畳み込みに依存するグラフ畳み込みアテンション層(CAT)を紹介する。
以上の結果から,L-CATはネットワーク上の異なるGNN層を効率よく結合し,競合する手法よりも広い範囲で優れた性能を発揮することが示された。
論文 参考訳(メタデータ) (2022-11-21T21:08:58Z) - Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。
提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。
2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
論文 参考訳(メタデータ) (2020-12-23T09:33:11Z) - Deep Reinforcement Learning of Graph Matching [63.469961545293756]
ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。
GMのための強化学習ソルバを提案する。
rgmはペアワイズグラフ間のノード対応を求める。
本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
論文 参考訳(メタデータ) (2020-12-16T13:48:48Z) - Cross-Domain Facial Expression Recognition: A Unified Evaluation
Benchmark and Adversarial Graph Learning [85.6386289476598]
我々は,クロスドメイン全体的特徴共適応のための新しい逆グラフ表現適応(AGRA)フレームワークを開発した。
我々は,いくつかの一般的なベンチマークで広範囲かつ公平な評価を行い,提案したAGRAフレームワークが従来の最先端手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2020-08-03T15:00:31Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
グラフ自動エンコーダ(GAE)モデルは、半教師付きグラフ畳み込みネットワーク(GCN)に基づく
我々は、グラフクラスタリングのための特定のGAEベースのモデルを設計し、その理論、すなわち、埋め込みグラフオートエンコーダ(EGAE)と整合する。
EGAEは1つのエンコーダと2つのデコーダで構成される。
論文 参考訳(メタデータ) (2020-02-20T09:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。