論文の概要: Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2602.14772v1
• Date: Mon, 16 Feb 2026 14:26:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-17 16:22:50.459879
• Title: Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks
• Title（参考訳）: 組合せオークションのための構造的難しさを学習する:グラフニューラルネットワークによるインスタンス依存アルゴリズムの選択
• Authors: Sungwoo Kang,
• Abstract要約: オークションにおける勝者決定問題はNPハードである。 既存の方法では、どのインスタンスが高速なグリーディを倒すかを確実に予測することはできません。 近年の証拠は、グラフニューラルネットワーク(GNN)が、よく調整された古典的手法を上回ることは滅多にないことを示している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to \emph{replace} solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict \emph{when} a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7\% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ${\approx}0\%$ optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24\% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51\% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning \emph{when} to deploy expensive solvers is more tractable than learning to replace them.
• Abstract（参考訳）: 組み合わせオークションにおける勝者決定問題(WDP)はNPハードであり、どの事例が高速な欲求的ヒューリスティックを破るかを確実に予測する既存の手法は存在しない。 ML-for-combintorial-optimizationコミュニティは、emph{replace}ソルバの学習に重点を置いているが、近年の証拠は、グラフニューラルネットワーク(GNN)が標準ベンチマークでよく調整された古典的手法を上回ることは滅多にないことを示している。 我々は、異なる目的を追求する: 与えられたインスタンスをemph{when}を予測することは、グレディアロケーションには困難であり、インスタンスに依存したアルゴリズムの選択を可能にする。 我々は,20次元構造特徴ベクトルを設計し,平均絶対誤差0.033,ピアソン相関0.937,二進分類精度94.7\%でグリーディ最適性ギャップを予測できる軽量MLP硬度分類器を訓練する。 greedyが確実に失敗する ``whale-fish'' のトラップ構造を示す、難しいものとして特定されたインスタンスに対して、テスト対象の6つの対向構成(vs.\ 3.75--59.24\% for greedy)に対して、${\approx}0\%$の最適化ギャップを達成した異種なGNNスペシャリストをデプロイします。 硬度分類器とGNNとグリージー解器を組み合わせたハイブリッドアロケータは混合分布における0.51\%の全体ギャップを達成できる。 CATSベンチマークの正直な評価は、GNNがGurobi(0.45--0.71対0.71)を上回りません。 0.20のギャップ)、アルゴリズム選択フレーミングを動機付けます。 高価なソルバをデプロイするために‘emph{when}’を学ぶことは、それを置き換えるための学習よりも、はるかに難しい。

関連論文リスト

• Learning to Reweight for Graph Neural Network [63.978102332612906]
  グラフニューラルネットワーク(GNN)は、グラフタスクに対して有望な結果を示す。 既存のGNNの一般化能力は、テストとトレーニンググラフデータの間に分散シフトが存在する場合に低下する。 本稿では,分布外一般化能力を大幅に向上させる非線形グラフデコリレーション法を提案する。
  論文  参考訳（メタデータ） (2023-12-19T12:25:10Z)
• E(2) Equivariant Neural Networks for Robust Galaxy Morphology Classification [0.0]
  我々は、Galaxy10 DECalsデータセット上で$E(2)$の離散サブグループに同値なGCNNを訓練し、検証し、テストする。 D_16$に同値なアーキテクチャは、テストセットの精度が9,5.52 pm 0.18%である。 全てのGCNNは、同一に構築されたCNNよりも1ピクセルの摂動の影響を受けにくい。
  論文  参考訳（メタデータ） (2023-11-02T18:00:02Z)
• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。 本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。 これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
  論文  参考訳（メタデータ） (2023-10-14T07:02:54Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。 実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-10-05T02:58:29Z)
• Improved techniques for deterministic l2 robustness [63.34032156196848]
  畳み込みニューラルネットワーク(CNN)を$l_2$ノルムの下で厳密な1-Lipschitz制約で訓練することは、対向的堅牢性、解釈可能な勾配、安定した訓練に有用である。 我々は,最後の線形層を1重層に置き換えることで,1-Lipschitz CNNのロバスト性を証明する手法を提案する。 我々は,CIFAR-10およびCIFAR-100における標準および証明可能な堅牢な精度の最先端化を図る。
  論文  参考訳（メタデータ） (2022-11-15T19:10:12Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。 また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
  論文  参考訳（メタデータ） (2022-03-19T14:26:43Z)
• Rethinking Nearest Neighbors for Visual Classification [56.00783095670361]
  k-NNは、トレーニングセット内のテストイメージとトップk隣人間の距離を集約する遅延学習手法である。 我々は,教師付き手法と自己監督型手法のいずれでも,事前学習した視覚表現を持つk-NNを2つのステップで採用する。 本研究は,幅広い分類タスクに関する広範な実験により,k-NN統合の汎用性と柔軟性を明らかにした。
  論文  参考訳（メタデータ） (2021-12-15T20:15:01Z)
• The Interplay between Distribution Parameters and the Accuracy-Robustness Tradeoff in Classification [0.0]
  アドリラルトレーニングは、通常のモデルに比べて自然(未成熟)の例では正確でないモデルをもたらす傾向にある。 これは、アルゴリズムの欠点か、トレーニングデータ分散の基本的な性質によるものとみなすことができる。 本研究では,二進ガウス混合分類問題の下で後者のケースに焦点をあてる。
  論文  参考訳（メタデータ） (2021-07-01T06:57:50Z)
• On the robustness of randomized classifiers to adversarial examples [11.359085303200981]
  確率指標を用いて局所リプシッツ性を強制するランダム化分類器の堅牢性の新しい概念を紹介する。 本研究の結果は,温和な仮説下での幅広い機械学習モデルに適用可能であることを示す。 トレーニングしたすべての堅牢なモデルは、最新の精度を同時に達成できます。
  論文  参考訳（メタデータ） (2021-02-22T10:16:58Z)
• Distributionally Robust Weighted $k$-Nearest Neighbors [21.537952410507483]
  少数のサンプルから堅牢な分類器を学ぶことは、マシンラーニングにおける重要な課題である。 本稿では, 重み付き$k$-アネレスト近傍のミニマックス分布に頑健な定式化について検討する。 我々は,この関数最適化問題を効率的に解くアルゴリズムである textttDr.k-NN を開発した。
  論文  参考訳（メタデータ） (2020-06-07T00:34:33Z)

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

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