論文の概要: Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS

• arxiv url: http://arxiv.org/abs/2605.05330v1
• Date: Wed, 06 May 2026 18:02:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 22:27:11.358002
• Title: Graph Normalization: Fast Binarizing Dynamics for Differentiable MWIS
• Title（参考訳）: グラフ正規化:微分可能MWISのための高速二元化ダイナミクス
• Abstract要約: グラフ正規化(GN)はNP-hard Maximum Weight Independent Set問題に対する微分可能近似エンジンとして機能する。 GNは、正確な偏極化-最小化ステップを通じて高速な準ニュートン降下を実現する。 GNは、最もよく知られた結果の1%以内のソリューションをCPU上で数秒で識別する。
• 参考スコア（独自算出の注目度）: 0.40611352512781856
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce Graph Normalization (GN), a principled dynamical system on graphs that serves as a differentiable approximation engine for the NP-hard Maximum Weight Independent Set (MWIS) problem. MWIS encompasses many combinatorial challenges, including optimal assignment, scheduling, set packing, and MAP inference in discrete Markov Random Fields. Unlike Belief Propagation, we prove GN always converges to a binary indicator of a Maximum Independent Set. GN realizes a fast quasi-Newton descent through an exact Majorization-Minimization step, systematically improving the MWIS relaxed primal objective. We establish an equivalence between GN and the Replicator Dynamics of a nonlinear evolutionary game, where vertices compete for inclusion in an independent set. While a non-potential game, the GN game follows Fisher's Fundamental Theorem of Natural Selection, where the average fitness equals the MWIS primal objective and strictly increases. This connection leads to a weighted extension of the Motzkin-Straus theorem, showing MISes are in bijection with the local minima of a quadratic form over a tilted simplex. For the Assignment Problem, GN acts as a variant of the Sinkhorn algorithm that naturally converges to a hard assignment while generalizing to arbitrary constraint graphs. We demonstrate GN's performance as a fast binarization engine for the state-of-the-art Bregman-Sinkhorn relaxed MWIS solver. On real-world benchmarks with up to 1M edges, GN identifies solutions within 1% of the best known results in seconds on a CPU. GN opens new avenues for deep learning architectures requiring differentiable, "hard" decisions under constraints, with applications in structured sparse attention, dynamic network pruning, and Mixture-of-Experts. Beyond core AI, the GN framework enables end-to-end learning of constrained optimization in computer vision, computational biology, and resource allocation.
• Abstract（参考訳）: NP-hard Maximum Weight Independent Set (MWIS) 問題に対する微分可能な近似エンジンとして機能するグラフ上の原理的力学系であるグラフ正規化(GN)を導入する。 MWISは、最適な割り当て、スケジューリング、セットパッキング、離散マルコフランダムフィールドにおけるMAP推論など、多くの組合せ問題を含んでいる。 リーフ伝播とは異なり、GN は常に最大独立集合の双対指標に収束する。 GNは、MWIS緩和原始目標を体系的に改善する、正確な偏極化-最小化ステップを通じて、高速な準ニュートン降下を実現する。 我々はGNと非線形進化ゲームにおけるReplicator Dynamicsの等価性を確立する。 非ポテンシャルゲームでは、GNゲームはフィッシャーの自然選択の基本定理に従い、平均的なフィットネスはMWISの主目的と等しく、厳格に増加する。 この接続はモツキン・ストラウスの定理の重み付き拡張につながり、MISeは傾いた単純体上の二次形式の局所ミニマと単射であることを示す。 割り当て問題に対して、GN はシンクホーンアルゴリズムの変種として機能し、任意の制約グラフに一般化しながら自然にハード代入に収束する。 本稿では,最先端のBregman-Sinkhorn緩和MWISソルバにおける高速二項化エンジンとしてのGNの性能を示す。 最大100万のエッジを持つ実世界のベンチマークでは、GNはCPU上で数秒で最もよく知られた結果の1%以内のソリューションを識別する。 GNは、構造化されたスパースアテンション、動的ネットワークプルーニング、Mixture-of-Expertsなど、制約下での微分可能で「ハード」な決定を必要とするディープラーニングアーキテクチャのための新しい道を開いた。 コアAI以外にも、GNフレームワークはコンピュータビジョン、計算生物学、リソース割り当てにおける制約付き最適化のエンドツーエンド学習を可能にする。

関連論文リスト

• DREAM: Dual-Standard Semantic Homogeneity with Dynamic Optimization for Graph Learning with Label Noise [53.55187452152358]
  本稿では,ラベル付きグラフ上での信頼度,関係インフォームド最適化のためのDREAM(Dual-Standard Semantic Homogeneity with Dynamic Optimization)を提案する。 具体的には、グラフ内の各ラベル付きノードの信頼性を反復的に再評価するリレーショナルインフォームド動的最適化フレームワークを設計する。
  論文  参考訳（メタデータ） (2026-01-24T12:54:18Z)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  連続時間量子ウォーク(CTQW)に基づく最小頂点被覆(MVC)問題に対する新しい量子アルゴリズムを提案する。 この枠組みでは、グラフ上の量子ウォーカーのコヒーレントな伝播は、その構造特性を状態振幅に符号化する。 我々は,CTQWに基づくアルゴリズムが優れた近似比を一貫して達成し,ネットワークトポロジに関して顕著な堅牢性を示すことを示す。
  論文  参考訳（メタデータ） (2025-12-02T17:04:57Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。 グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
  論文  参考訳（メタデータ） (2024-07-26T03:14:13Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• Graph Mamba: Towards Learning on Graphs with State Space Models [2.039632659682125]
  選択状態空間モデル(SSM)に基づくグラフニューラルネットワーク(GNN)の新しいクラスを提案する。 GMNは、長距離、小規模、大規模、ベンチマークのベンチマーク実験で優れたパフォーマンスを達成した。
  論文  参考訳（メタデータ） (2024-02-13T18:58:17Z)
• Maximum Independent Set: Self-Training through Dynamic Programming [56.670639478539485]
  本研究では、動的プログラミング(DP)にインスパイアされた最大独立集合(MIS)問題を解決するグラフニューラルネットワーク(GNN)フレームワークを提案する。 GNNをベースとしたDPライクな再帰アルゴリズムを提案し、まず2つの小さなサブグラフを構築し、より大きなMISを持つサブグラフを予測し、次に再帰呼び出しを行う。 MISサイズに関する異なるグラフの比較を注釈付けすると、自己学習プロセスが発生し、比較をより正確に自己アノテーションし、その逆も引き起こされる。
  論文  参考訳（メタデータ） (2023-10-28T10:58:25Z)
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers [0.0]
  我々は、Rydberg量子アニールの最適化問題を解くための非ユニットディスクフレームワークを提供する。 我々の構成は、局所制御可能な光シフトを個々の量子ビットに適用する多体相互作用Rydbergシステムからなる。 我々の数値シミュレーションでは、Rydbergアニーラーを所望の多体基底状態に大域的に駆動しながら、局所分解プロトコルを実装している。
  論文  参考訳（メタデータ） (2023-08-15T14:24:45Z)
• MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers [13.790116387956703]
  混合整数プログラミング(MIP)技術は最適化問題の定式化と解法を提供する。 MIP-GNNは、データ駆動の洞察でそのような問題を解決するための一般的なフレームワークである。 MIP-GNNを最先端のMIP解決器に統合し,ノード選択やウォームスタートといったタスクに適用する。
  論文  参考訳（メタデータ） (2022-05-27T19:34:14Z)
• Adaptive Kernel Graph Neural Network [21.863238974404474]
  グラフニューラルネットワーク(GNN)は,グラフ構造化データの表現学習において大きな成功を収めている。 本稿では,AKGNN(Adaptive Kernel Graph Neural Network)という新しいフレームワークを提案する。 AKGNNは、最初の試みで最適なグラフカーネルに統一的に適応することを学ぶ。 評価されたベンチマークデータセットで実験を行い、提案したAKGNNの優れた性能を示す有望な結果を得た。
  論文  参考訳（メタデータ） (2021-12-08T20:23:58Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  グラフニューラルネットワーク(GNN)は、グラフ上の新たな機械学習モデルである。 置換等価性と近接認識性は、GNNにとって非常に望ましい2つの重要な特性である。 既存のGNNは、主にメッセージパッシング機構に基づいており、同時に2つの特性を保存できないことを示す。 ノードの近さを保つため,既存のGNNをノード表現で拡張する。
  論文  参考訳（メタデータ） (2020-09-05T16:46:56Z)
• Pointer Graph Networks [48.44209547013781]
  グラフニューラルネットワーク(GNN)は通常、前もって知られていると仮定される静的グラフに適用される。 Pointer Graph Networks (PGNs) モデル一般化能力を改善するために、追加の推論エッジを備えた拡張セットまたはグラフ。 PGNは各ノードが別のノードを動的に指し、メッセージがこれらのポインタを渡ることを可能にする。
  論文  参考訳（メタデータ） (2020-06-11T12:52:31Z)

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

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