論文の概要: Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation

• arxiv url: http://arxiv.org/abs/2610.12119v1
• Date: Thu, 08 Oct 2026 15:16:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-10 02:36:54.1113
• Title: Using Weisfeiler-Leman Features for Algorithm Selection in Constraint Optimisation
• Title（参考訳）: 制約最適化におけるWeisfeiler-Leman特徴を用いたアルゴリズム選択
• Abstract要約: 本稿では,グラフ変換とWeisfeiler-Lehmanグラフカーネルを統合した自動特徴抽出手法を提案する。 我々の主な貢献は、構造分割をモデル化し、よりニュアンスな予測信号を提供するために設計されたカットベース表現(textttWLc)である。
• 参考スコア（独自算出の注目度）: 1.052782170493037
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Algorithm Selection is essential for efficient Constraint Programming. Over the years, many algorithm selectors based on machine learning methods have been successfully applied, yet traditional feature extraction methods often rely on manually decided instance-level statistics that fail to capture the underlying problem structure. In this paper we aim to bridge this gap by introducing a novel, automated feature extraction methodology that integrates graph conversion and Weisfeiler-Lehman graph kernels to generate robust structural representations of problem instances. The 1-WL test bounds the graph-distinguishing power of standard message-passing Graph Neural Networks (GNNs), and suitable GNN architectures match this bound \citep{Xuetal2018}. WL-based features offer an alternative that does not require training a GNN. Our primary contribution is a cut-based representation (\texttt{WLc}) designed to model structural partitions and provide a more nuanced predictive signal. We evaluate our approach on instances from the 2023--2025 MiniZinc Challenges across two tasks: maximizing Borda count scores and maximizing predictive accuracy. Experimental results across Support Vector Machines, Random Forests, and Multi-Layer Perceptrons demonstrate that cut-based features outperform \texttt{fzn2feat} with SVMs, while results with RFs and MLPs are closer.
• Abstract（参考訳）: アルゴリズムの選択は効率的な制約プログラミングに不可欠である。 機械学習手法に基づく多くのアルゴリズムセレクタが長年にわたって適用されてきたが、従来の特徴抽出手法は、根底にある問題構造を捉えるのに失敗する、手動で決定されたインスタンスレベルの統計に依存することが多い。 本稿では、グラフ変換とWeisfeiler-Lehmanグラフカーネルを統合して、問題インスタンスの堅牢な構造表現を生成する、新しい自動特徴抽出手法を導入することにより、このギャップを埋めることを目的とする。 1-WLテストは、標準メッセージパスグラフニューラルネットワーク(GNN)のグラフ識別能力に縛られ、適切なGNNアーキテクチャは、この制限付き \citep{Xuetal2018} と一致する。 WLベースの機能は、GNNのトレーニングを必要としない代替手段を提供する。 我々の主な貢献は、構造分割をモデル化し、よりニュアンスな予測信号を提供するために設計されたカットベース表現(\texttt{WLc})である。 我々は,2023-2025年のMiniZinc Challengesのインスタンスに対するアプローチを,ボルダカウントスコアの最大化と予測精度の最大化という2つのタスクにわたって評価した。 Support Vector Machines、Random Forests、Multi-Layer Perceptronsでの実験結果によると、カットベース機能はSVMでより優れており、RFやMLPではより近い。

関連論文リスト

• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  グラフニューラルネットワーク(GNN)は、リレーショナルデータを先行する強力なツールであるが、しばしば目に見えないグラフに一般化するのに苦労する。 textbfGraph textbfIn-context textbfL textbfTransformer (GILT)を導入する。
  論文  参考訳（メタデータ） (2025-10-06T08:09:15Z)
• Learning to Select MCP Algorithms: From Traditional ML to Dual-Channel GAT-MLP [8.6217237605907]
  単一の最大傾きアルゴリズムは、全てのインスタンスで常に最善を尽くす。 従来の機械学習とグラフニューラルネットワークを統合した学習ベースのフレームワークを提案する。
  論文  参考訳（メタデータ） (2025-08-11T14:09:58Z)
• Boosting Graph Neural Network Expressivity with Learnable Lanczos Constraints [7.605749412696919]
  グラフニューラルネットワーク(GNN)はグラフ構造化データの処理に優れるが、リンク予測タスクでは性能が劣ることが多い。 グラフラプラシア行列の固有基底に誘導された部分グラフを埋め込むことによりGNNの表現性を高める新しい手法を提案する。 本研究では,2-WLで区別できないグラフを,効率的な時間的複雑性を維持しながら識別できることを実証する。
  論文  参考訳（メタデータ） (2024-08-22T12:22:00Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  離散グラフオートエンコーダ(DGAE)という新しいフレームワークを導入する。 まず、置換同変オートエンコーダを用いてグラフを離散潜在ノード表現の集合に変換する。 2番目のステップでは、離散潜在表現の集合をソートし、特別に設計された自己回帰モデルを用いてそれらの分布を学習する。
  論文  参考訳（メタデータ） (2023-06-13T12:40:39Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。 我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
  論文  参考訳（メタデータ） (2021-10-27T11:48:50Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。