論文の概要: Learning Optimal Dynamic Matching via Graph Neural Networks
- arxiv url: http://arxiv.org/abs/2607.28925v1
- Date: Fri, 31 Jul 2026 01:00:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-03 14:29:40.557735
- Title: Learning Optimal Dynamic Matching via Graph Neural Networks
- Title（参考訳）: グラフニューラルネットワークによる最適動的マッチング学習
- Abstract要約: ダイナミックなマッチング市場は、誰といつマッチングするかの判断を必要とします。
有限な重み付きグラフ上でこの問題に対する価値に基づく強化学習フレームワークを開発する。
残差グラフ値学習は、実現された接続情報や出口情報に適応する状態依存の動的マッチングポリシーをもたらすことを示す。
- 参考スコア（独自算出の注目度）: 5.353635078503719
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Dynamic matching markets require decisions about whom to match and when: matching now yields value but removes participants who may create better future opportunities. We develop a value-based reinforcement-learning framework for this problem on finite, evolving weighted graphs. We study an infinite-horizon continuous-time model with stochastic arrivals, node-type transitions, edge realizations, and exogenous exits. We prove an event-time reduction: without loss of optimality, the planner acts immediately after each exogenous event and then waits for the next one. We further show that the optimal edge-wise $Q$-function is characterized by a single continuation-value function on post-decision residual graphs, reducing the learned object from state-action values to graph values. Exact action selection still requires combinatorial matching optimization; we approximate the value with a graph neural network, train it by temporal-difference learning, and use it in a forward-greedy matching heuristic. In a binary-type benchmark, the learned policy substantially outperforms immediate and threshold-greedy rules by preserving common nodes for rare arrivals of valuable matches while forming lower-value matches only in thick pools. In a kidney paired donation benchmark, it performs similarly to immediate greedy when exits are unpredictable, recovers the logic of patient matching when warnings are reliable, and outperforms the better of Immediate Greedy and Patient Greedy across intermediate warning probabilities. These results show that residual-graph value learning yields state-dependent dynamic matching policies that adapt to realized connectivity and exit information.
- Abstract（参考訳）: ダイナミックなマッチング市場は、誰といつマッチングするかの判断を必要とします。
有限な重み付きグラフ上でこの問題に対する価値に基づく強化学習フレームワークを開発する。
確率的到着,ノード型遷移,エッジ実現,外因性出口を有する無限水平連続時間モデルについて検討する。
最適性を失うことなく、プランナーは各外生イベントの直後に行動し、次のイベントを待つ。
さらに、最適エッジの$Q$関数は、決定後の残差グラフ上の1つの連続値関数によって特徴づけられ、学習対象が状態作用値からグラフ値に還元されることを示す。
厳密な行動選択には相補的マッチングの最適化が必要であり、その値をグラフニューラルネットワークで近似し、時間差学習によってトレーニングし、前向きのマッチングヒューリスティックで使用する。
バイナリ型ベンチマークでは、学習されたポリシーは、貴重なマッチの稀な到着のための共通ノードを保存し、太いプールでのみ低い値のマッチを形成することにより、即時およびしきい値の規則を大幅に上回る。
腎臓ペアドドレナージベンチマークでは、出口が予測不可能な場合の即時グリーディと同様に、警告が信頼できる場合の患者マッチングの論理を回復し、中間警告の確率で即時グリーディと患者グリーディの成績を上回ります。
これらの結果から,残差グラフ値学習は,実効接続情報や出口情報に適合する状態依存動的マッチングポリシをもたらすことが示された。
関連論文リスト
- GCCM: Enhancing Generative Graph Prediction via Contrastive Consistency Model [10.481950161450948]
入力グラフが与えられた条件分布としてターゲットをモデル化することにより,条件生成モデルをグラフ予測に適用した。
本稿では,異なる雑音レベルにおける同一ターゲット間のペアワイズマッチングを超越したグラフコントラスト整合モデルGCCMを提案する。
我々はGCCMがショートカット解を緩和し、決定論的予測器と比較して、グラフ予測における一貫した性能改善をもたらすことを示す。
論文 参考訳（メタデータ） (2026-05-07T05:29:57Z) - Attribute-Enhanced Similarity Ranking for Sparse Link Prediction [6.774952925054741]
グラフニューラルネットワーク(GNN)がリンク予測の主要なフレームワークとなっている。
本稿では,リンク予測におけるGNNの性能が,より現実的な不均衡設定に反映されないことを示す。
実験により,類似性に基づくリンク予測手法であるGelatoが,既存のGNNベースの代替よりも優れていることが示された。
論文 参考訳（メタデータ） (2024-11-29T21:22:35Z) - Extreme Value Modelling of Feature Residuals for Anomaly Detection in Dynamic Graphs [14.8066991252587]
グラフの時間的シーケンスにおける異常の検出は、トランスポートネットワークにおける事故の検出や、コンピュータネットワークにおけるサイバー攻撃といった分野に適用することができる。
既存の異常グラフ検出方法は、高い偽陽性率や可変サイズのグラフの扱いの難しさ、非自明な時間ダイナミクスなど、複数の制限に悩まされることがある。
そこで本稿では,時間的依存を時系列解析によって時間的依存を明示的にモデル化し,残差を用いて依存を除去する手法を提案する。
論文 参考訳（メタデータ） (2024-10-08T05:00:53Z) - Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。
本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。
これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
論文 参考訳（メタデータ） (2023-10-14T07:02:54Z) - Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。
提案手法は,複数のMOTデータセット上での最先端性能を実現する。
画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
論文 参考訳（メタデータ） (2023-03-27T17:39:00Z) - Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
時間的ネットワーク上での機械学習の方法は、一般的に2つの制限のうちの少なくとも1つを示す。
ネットワークのライングラフは,各インタラクションのノードを含むもので,インタラクション間の時間差に基づいて,このグラフのエッジを重み付けする。
実世界のネットワークにおける実験結果から,エッジ分類と時間リンク予測の両方において,本手法の有効性と有効性を示す。
論文 参考訳（メタデータ） (2022-09-30T18:24:13Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
トレーニングセット内の既存グラフから直接正のグラフインスタンスを選択することを提案する。
私たちの選択は、特定のドメイン固有のペアワイズ類似度測定に基づいています。
さらに,ノードを動的にマスキングしてグラフ上に均等に分配する適応ノードレベルの事前学習手法を開発した。
論文 参考訳（メタデータ） (2022-06-23T20:12:51Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Deep Probabilistic Graph Matching [72.6690550634166]
本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。
提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
論文 参考訳（メタデータ） (2022-01-05T13:37:27Z) - PushNet: Efficient and Adaptive Neural Message Passing [1.9121961872220468]
メッセージパッシングニューラルネットワークは、最近、グラフ上での表現学習に対する最先端のアプローチへと進化した。
既存のメソッドは、複数のラウンドですべてのエッジに沿って同期メッセージパッシングを実行する。
我々は、収束するまで最も関連性の高いエッジに沿ってのみ情報をプッシュする、新しい非同期メッセージパッシングアプローチについて検討する。
論文 参考訳（メタデータ） (2020-03-04T18:15:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。