Fugu-MT 論文翻訳(概要): Online Bipartite Matching with Predicted Degrees

論文の概要: Online Bipartite Matching with Predicted Degrees

arxiv url: http://arxiv.org/abs/2110.11439v1
Date: Thu, 21 Oct 2021 19:15:44 GMT
ステータス: 処理完了
システム内更新日: 2021-10-25 15:23:54.184607
Title: Online Bipartite Matching with Predicted Degrees
Title（参考訳）: オンライン二部間マッチングと予測次数
Authors: Justin Y. Chen, Piotr Indyk
Abstract要約: オンライン二部作マッチングの古典的問題について検討する。経験的評価によると、MinPredictedDegreeと呼ばれる欲求的なアルゴリズムは、この問題に対する最先端のオンラインアルゴリズムと好意的に比較している。
参考スコア（独自算出の注目度）: 21.310807231082283
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a model for online graph problems where algorithms are given access to an oracle that predicts the degrees of nodes in the graph (e.g., based on past data). Within this model, we study the classic problem of online bipartite matching. An extensive empirical evaluation shows that a greedy algorithm called MinPredictedDegree compares favorably to state-of-the-art online algorithms for this problem. We also initiate the theoretical study of MinPredictedDegree on a natural random graph model with power law degree distribution and show that it produces matchings almost as large as the maximum matching on such graphs.
Abstract（参考訳）: 本稿では,グラフ内のノードの次数(例えば過去のデータに基づく)を予測するオラクルにアルゴリズムがアクセスできるような,オンライングラフ問題のモデルを提案する。このモデルでは,オンライン2部マッチングの古典的な問題について検討する。 MinPredictedDegreeと呼ばれる強欲なアルゴリズムは、この問題に対する最先端のオンラインアルゴリズムと好意的に比較している。また、自然ランダムグラフモデルにおけるMinPredictedDegreeの理論的研究を開始し、そのようなグラフ上での最大マッチングとほぼ同じ大きさのマッチングを生成することを示す。

関連論文リスト

Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
2つまたは複数のグラフの部分的マッチングのための宇宙マッチングスキームを開発する。不整合及び不整合検出のための微妙なロジックを、明確にモデル化することができる。これは、2グラフマッチング、複数グラフマッチング、オンラインマッチング、混合グラフマッチングを同時に扱うことができる最初のディープラーニングネットワークである。
論文参考訳（メタデータ） (2022-10-19T08:34:00Z)
Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation [34.30390182564043]
フィルタされた低域通過グラフ信号と、おそらく非白色および低ランクの励起の混合モデルについて検討する。本稿では,グラフのノード中心性に着目した推論問題を考える。本稿では,ストリーミングデータからの推論のための新しいオンラインEMアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-07-28T11:25:47Z)
Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文参考訳（メタデータ） (2022-05-06T03:37:00Z)
Graphon based Clustering and Testing of Networks: Algorithms and Theory [11.3700474413248]
ネットワークに価値のあるデータは、幅広いアプリケーションで遭遇し、学習の課題を提起する。本稿では,2つのクラスタリングアルゴリズムについて述べる。さらに、グラフ2サンプルテスト問題に対する提案した距離の適用性について検討する。
論文参考訳（メタデータ） (2021-10-06T13:14:44Z)
Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
グラフマッチング問題のMILP定式化を統合する手法を提案する。同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
論文参考訳（メタデータ） (2021-08-01T08:29:55Z)
Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural Networks [74.26734952400925]
ノード埋め込み次元選択(NEDS)のための最小グラフエントロピー(MinGE)アルゴリズムを提案する。ミンゲは、グラフ上の特徴エントロピーと構造エントロピーの両方を考えており、それらはそれらのリッチな情報の特徴に従って慎重に設計されている。ベンチマークデータセット上で人気のグラフニューラルネットワーク(GNN)を用いた実験は,提案したMinGEの有効性と一般化性を示す。
論文参考訳（メタデータ） (2021-05-07T11:40:29Z)
Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文参考訳（メタデータ） (2020-10-20T05:54:31Z)
Second-Order Pooling for Graph Neural Networks [62.13156203025818]
グラフプーリングとして2次プールを提案するが、これは上記の課題を自然に解決する。グラフニューラルネットワークによる2次プールの直接利用は、実用的な問題を引き起こすことを示す。本稿では,2次プールに基づく2つの新しいグローバルグラフプーリング手法,すなわちバイリニアマッピングと2次プールを提案する。
論文参考訳（メタデータ） (2020-07-20T20:52:36Z)
A continuum limit for the PageRank algorithm [1.2891210250935146]
半教師あり、教師なしの機械学習手法は、しばしばデータモデリングにグラフに依存する。本稿では,有向グラフ上での学習アルゴリズムの連続限界を厳密に研究するための新しいフレームワークを提案する。正規化グラフの一種であるラプラシアンを含む有向グラフ上の数値スキームとして解釈する方法を示す。
論文参考訳（メタデータ） (2020-01-24T12:56:09Z)
Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文参考訳（メタデータ） (2020-01-18T09:14:16Z)

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