論文の概要: WeaveNet for Approximating Two-sided Matching Problems
- arxiv url: http://arxiv.org/abs/2310.12515v1
- Date: Thu, 19 Oct 2023 06:32:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-20 16:36:17.034009
- Title: WeaveNet for Approximating Two-sided Matching Problems
- Title(参考訳): WeaveNetによる双方向マッチング問題の近似
- Authors: Shusaku Sone, Jiaxin Ma, Atsushi Hashimoto, Naoya Chiba, Yoshitaka
Ushiku
- Abstract要約: 本稿では,二部グラフ用に設計された新しいグラフニューラルネットワーク(GNN, textitWeaveNet)を提案する。
我々のモデルは,少数のエージェントに対する安定マッチングのために特別に設計された最先端のアルゴリズムとの比較性能に到達した。
- 参考スコア(独自算出の注目度): 16.014942651874815
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Matching, a task to optimally assign limited resources under constraints, is
a fundamental technology for society. The task potentially has various
objectives, conditions, and constraints; however, the efficient neural network
architecture for matching is underexplored. This paper proposes a novel graph
neural network (GNN), \textit{WeaveNet}, designed for bipartite graphs. Since a
bipartite graph is generally dense, general GNN architectures lose node-wise
information by over-smoothing when deeply stacked. Such a phenomenon is
undesirable for solving matching problems. WeaveNet avoids it by preserving
edge-wise information while passing messages densely to reach a better
solution. To evaluate the model, we approximated one of the \textit{strongly
NP-hard} problems, \textit{fair stable matching}. Despite its inherent
difficulties and the network's general purpose design, our model reached a
comparative performance with state-of-the-art algorithms specially designed for
stable matching for small numbers of agents.
- Abstract(参考訳): 制約の下で限られた資源を最適に割り当てるタスクであるマッチングは、社会の基本的な技術である。
このタスクには様々な目的、条件、制約がある可能性があるが、マッチングのための効率的なニューラルネットワークアーキテクチャは過小評価されている。
本稿では,2部グラフ用に設計された新しいグラフニューラルネットワークである \textit{weavenet}を提案する。
双部グラフは一般に密度が高いため、GNNアーキテクチャは深く積み重ねられた場合、過剰なスムーシングによってノードワイズ情報を失う。
このような現象は一致する問題を解くには望ましくない。
WeaveNetは、エッジワイズ情報を保存し、メッセージを密に渡してよりよいソリューションに到達することで、それを回避する。
このモデルを評価するために, NP-hard} 問題の1つ, \textit{fair stable matching} を近似した。
その本質的な困難さとネットワークの汎用設計にもかかわらず、我々のモデルは少数のエージェントの安定したマッチングのために特別に設計された最先端アルゴリズムと比較性能に到達した。
関連論文リスト
- A GREAT Architecture for Edge-Based Graph Problems Like TSP [8.922883855120416]
グラフニューラルネットワーク(GNN)は、ルーティング問題などの高密度グラフを操作するには適していない。
グラフエッジ注意ネットワーク(GREAT)と呼ばれる新しいGNN関連エッジベースニューラルモデルを提案する。
GREATは最適エッジの大部分を維持しながらスパースグラフを生成することができることを示す。
論文 参考訳(メタデータ) (2024-08-29T17:07:43Z) - LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。
本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文 参考訳(メタデータ) (2024-07-18T22:05:21Z) - Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。
AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
論文 参考訳(メタデータ) (2024-06-05T02:43:41Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳(メタデータ) (2024-05-27T17:52:12Z) - Network Interdiction Goes Neural [26.308933674471895]
ネットワーク断面積問題は、2人のプレイヤーが関与する最適化問題である。
1つは、ネットワーク上の最適化問題を解決することを目的としており、もう1つは、最初のプレイヤーの目的を阻止するためにネットワークを変更することを目的としている。
論文 参考訳(メタデータ) (2024-05-26T02:34:26Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。
IID(non-graph)データをGNNに簡単に組み込むことはできない。
本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
論文 参考訳(メタデータ) (2022-06-16T22:46:33Z) - Learning to Drop: Robust Graph Neural Network via Topological Denoising [50.81722989898142]
グラフニューラルネットワーク(GNN)のロバスト性および一般化性能を向上させるために,パラメータ化トポロジカルデノイングネットワークであるPTDNetを提案する。
PTDNetは、パラメータ化されたネットワークでスパーシファイドグラフ内のエッジ数をペナル化することで、タスク非関連エッジを創出する。
PTDNetはGNNの性能を著しく向上させ,さらにノイズの多いデータセットでは性能が向上することを示す。
論文 参考訳(メタデータ) (2020-11-13T18:53:21Z) - Alleviating the Inconsistency Problem of Applying Graph Neural Network
to Fraud Detection [78.88163190021798]
不整合問題に対処するために、新しいGNNフレームワークである$mathsfGraphConsis$を導入します。
4つのデータセットの実証分析は、不正検出タスクにおいて不整合の問題が不可欠であることを示唆している。
我々はまた、SOTAモデルを実装したGNNベースの不正検出ツールボックスもリリースした。
論文 参考訳(メタデータ) (2020-05-01T21:43:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。