論文の概要: Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

• arxiv url: http://arxiv.org/abs/2605.13673v1
• Date: Wed, 13 May 2026 15:33:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:28.135608
• Title: Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
• Title（参考訳）: マルチカット問題に対する三角形メッセージ付きグラフニューラルネットワーク
• Authors: Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres,
• Abstract要約: 本稿では,エッジのみに特徴を割り当てる,適応型グラフニューラルネットワークアーキテクチャを提案する。 最大200ノードの合成および実世界のインスタンスを用いた実験により,本手法は解法の品質において最先端の解法よりも優れていることが示された。
• 参考スコア（独自算出の注目度）: 9.392713637367661
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constraints. In this article, we introduce such an adapted graph neural network architecture in which features are assigned only to edges, and the computation of messages is based on triangles in the underlying graph. Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.
• Abstract（参考訳）: マルチカット問題は、バイオインフォマティクス、データマイニング、コンピュータビジョンといった分野の様々な応用を応用したNPハード組合せ最適化問題である。 グラフニューラルネットワークはマルチカット問題に対して定義されているが、その特定の目的関数や制約にさらに適応することができる。 本稿では,エッジのみに特徴が割り当てられるグラフニューラルネットワークアーキテクチャを導入し,その基礎となるグラフの三角形に基づいてメッセージの計算を行う。 最大200ノードの合成および実世界のインスタンスを用いた実験により、本手法は実現可能なランタイムを維持しながら、ソリューションの品質の観点から、最先端のヒューリスティックな解法よりも優れていることが示された。 いくつかのケースでは、最適解を数秒で見つけるのに対して、正確な解法には最適解の発見と証明に何時間もかかる。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  最適化問題のクラスに対して最適な近似アルゴリズムをキャプチャするグラフニューラルネットワークアーキテクチャを設計する。 我々は、OptGNNの学習した埋め込みから最適解のバウンダリを生成するアルゴリズムを設計するために、凸緩和を捕捉するOptGNNの能力を利用する。
  論文  参考訳（メタデータ） (2023-10-01T00:12:31Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks [13.985534521589257]
  グラフ畳み込みニューラルネットワーク(GNN)は、最適化の文脈で有望であることが証明されている。 我々は、グラフ畳み込みネットワーク、符号付きグラフ畳み込みネットワーク、グラフ等化ネットワークなど、さまざまなGNNに適応する。 エンドツーエンドのトレーニング可能なマルチカットへの最初のアプローチを提供する。
  論文  参考訳（メタデータ） (2022-04-04T10:21:02Z)
• Graph Coloring with Physics-Inspired Graph Neural Networks [0.0]
  正準グラフ着色問題の解法としてグラフニューラルネットワークを用いる方法を示す。 マルチクラスノード分類問題としてグラフカラー化を行い,教師なし学習戦略を利用する。
  論文  参考訳（メタデータ） (2022-02-03T14:24:12Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
  最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。 ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
  論文  参考訳（メタデータ） (2021-07-02T16:54:35Z)

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

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