論文の概要: A Hidden Challenge of Link Prediction: Which Pairs to Check?

• arxiv url: http://arxiv.org/abs/2102.07878v1
• Date: Mon, 15 Feb 2021 22:37:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-18 12:13:44.577854
• Title: A Hidden Challenge of Link Prediction: Which Pairs to Check?
• Title（参考訳）: リンク予測の隠れた挑戦: どのペアをチェックするか?
• Authors: Caleb Belth, Alican B\"uy\"uk\c{c}ak{\i}r, Danai Koutra
• Abstract要約: リンク予測法は、しばしば近接埋め込みやノード類似性の概念に依存する。 LinkWaldoは、ノードペアのこの二次的で巨大なスキュー検索空間から選択するためのフレームワークです。 LinkWaldoは任意のノード表現を使用でき、任意のリンク予測方法の候補ペアを生成することができる。
• 参考スコア（独自算出の注目度）: 15.184004074137182
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The traditional setup of link prediction in networks assumes that a test set of node pairs, which is usually balanced, is available over which to predict the presence of links. However, in practice, there is no test set: the ground-truth is not known, so the number of possible pairs to predict over is quadratic in the number of nodes in the graph. Moreover, because graphs are sparse, most of these possible pairs will not be links. Thus, link prediction methods, which often rely on proximity-preserving embeddings or heuristic notions of node similarity, face a vast search space, with many pairs that are in close proximity, but that should not be linked. To mitigate this issue, we introduce LinkWaldo, a framework for choosing from this quadratic, massively-skewed search space of node pairs, a concise set of candidate pairs that, in addition to being in close proximity, also structurally resemble the observed edges. This allows it to ignore some high-proximity but low-resemblance pairs, and also identify high-resemblance, lower-proximity pairs. Our framework is built on a model that theoretically combines Stochastic Block Models (SBMs) with node proximity models. The block structure of the SBM maps out where in the search space new links are expected to fall, and the proximity identifies the most plausible links within these blocks, using locality sensitive hashing to avoid expensive exhaustive search. LinkWaldo can use any node representation learning or heuristic definition of proximity, and can generate candidate pairs for any link prediction method, allowing the representation power of current and future methods to be realized for link prediction in practice. We evaluate LinkWaldo on 13 networks across multiple domains, and show that on average it returns candidate sets containing 7-33% more missing and future links than both embedding-based and heuristic baselines' sets.
• Abstract（参考訳）: ネットワークにおける従来のリンク予測の設定は、通常バランスの取れたノードペアのテストセットが、リンクの存在を予測するために利用できると仮定している。 しかし、実際にはテストセットはありません:グラウンド・トラスは知られていないため、予測可能なペアの数はグラフ内のノードの数で2次です。 さらに、グラフはスパースであるため、これらの可能なペアのほとんどはリンクではない。 したがって、ノード類似性の近接保存埋め込みやヒューリスティックな概念に依存することが多いリンク予測方法は、近接しているが、それはリンクされるべきではない多くのペアで、広大な検索空間に直面します。 この問題を軽減するため,我々はlinkwaldoという,ノード対のこの二次的で大きめの探索空間から選択するフレームワークを導入し,近接するだけでなく,観測されたエッジにも構造的に類似する候補対の簡潔な集合を提案する。 これにより、いくつかの高確率対を無視することができるが、高確率対と低確率対を識別することができる。 我々のフレームワークは、理論上は確率ブロックモデル(sbms)とノード近接モデルを組み合わせたモデルに基づいている。 SBMのブロック構造は、検索スペース内で新しいリンクが落ちると予想される場所をマップし、近接部はこれらのブロックの中で最も妥当なリンクを識別し、局所性に敏感なハッシュを用いて高価な徹底的な検索を避ける。 LinkWaldoはノード表現の学習や近接のヒューリスティックな定義を利用でき、任意のリンク予測方法の候補ペアを生成することができ、実際のリンク予測のために現在および将来のメソッドの表現力を実現できます。 複数のドメインにまたがる13のネットワーク上でlinkwaldoを評価し、平均すると、埋め込みベースラインとヒューリスティックベースラインの両方のセットよりも、7-33%の欠落と将来のリンクを含む候補セットを返す。

関連論文リスト

• Efficient Link Prediction via GNN Layers Induced by Negative Sampling [86.87385758192566]
  リンク予測のためのグラフニューラルネットワーク(GNN)は、緩やかに2つの広いカテゴリに分けられる。 本稿では,新しいGNNアーキテクチャを提案する。このアーキテクチャでは,Emphforwardパスは,Emphboth陽性(典型的)と負陰性(アプローチに共通)のエッジに明示的に依存する。 これは、埋め込み自体を、正と負のサンプルの分離を好むフォワードパス特異的エネルギー関数の最小化子として再キャストすることで達成される。
  論文  参考訳（メタデータ） (2023-10-14T07:02:54Z)
• Refined Edge Usage of Graph Neural Networks for Edge Prediction [51.06557652109059]
  We propose a novel edge prediction paradigm named Edge-aware Message PassIng neuRal nEtworks (EMPIRE)。 まず,各エッジをトポロジや監督のためにのみ使用するエッジ分割手法を提案する。 監視エッジで接続されたペアと接続されていないペアの差を強調するために、さらにメッセージを重み付けして、その差を反映できる相対的なペアを強調します。
  論文  参考訳（メタデータ） (2022-12-25T23:19:56Z)
• Rethinking the positive role of cluster structure in complex networks for link prediction tasks [1.4695979686066065]
  クラスタリングは、ノードの密結合したグループを見つけるネットワーク分析における問題である。 リンク予測は、ネットワーク内の2つのノードにリンクがあるかどうかを予測することである。 単純なクラスタリング駆動型リンク予測フレームワークを構築した。
  論文  参考訳（メタデータ） (2022-11-04T12:02:40Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Neural Link Prediction with Walk Pooling [31.12613408446031]
  ウォークプールと呼ばれる新しいプール方式に基づくリンク予測を提案する。 トポロジカルアルゴリズムの表現性とニューラルネットワークの機能学習能力を組み合わせる。 これは、すべての一般的なリンク予測ベンチマークで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2021-10-08T20:52:12Z)
• Modelling Neighbor Relation in Joint Space-Time Graph for Video Correspondence Learning [53.74240452117145]
  本稿では、ラベルなしビデオから信頼できる視覚対応を学習するための自己教師付き手法を提案する。 接続時空間グラフでは,ノードがフレームからサンプリングされたグリッドパッチであり,2種類のエッジによってリンクされる。 学習した表現は、様々な視覚的タスクにおいて最先端の自己監督手法よりも優れています。
  論文  参考訳（メタデータ） (2021-09-28T05:40:01Z)
• Adversarial Permutation Guided Node Representations for Link Prediction [27.31800918961859]
  リンク予測(LP)アルゴリズムは、将来新たなエッジが成立する可能性のあるノードペアを特定する。 ほとんどのlpアルゴリズムは、現在不要なノード対のスコアを推定し、このスコアでランク付けする。 本研究では,リカレントで順序に敏感なアグリゲータを用いて隣り合う特徴を集約し,隣り合う順列の逆生成器によって攻撃されるlpロスを直接最小化するpermgnnを提案する。
  論文  参考訳（メタデータ） (2020-12-13T03:52:25Z)
• Interpretable Signed Link Prediction with Signed Infomax Hyperbolic Graph [54.03786611989613]
  ソーシャルネットワークにおけるサイン付きリンク予測は、ユーザ(すなわちノード)間の基盤となる関係(リンク)を明らかにすることを目的としている 我々は Signed Infomax Hyperbolic Graph (textbfSIHG) と呼ばれる統一されたフレームワークを開発する。 高次ユーザ関係と複雑な階層をモデル化するために、ノードの埋め込みを投影し、より低歪みの双曲空間で測定する。
  論文  参考訳（メタデータ） (2020-11-25T05:09:03Z)
• Benchmarking Network Embedding Models for Link Prediction: Are We Making Progress? [84.43405961569256]
  我々はリンク予測のためのネットワーク埋め込み手法の最先端について光を当てた。 私たちは、一貫した評価パイプラインを使用して、過去数年間でわずかに進歩しただけであることを示しています。 我々は、標準化された評価ツールがこの状況を修復し、この分野の将来的な進歩を促進することができると論じている。
  論文  参考訳（メタデータ） (2020-02-25T16:59:09Z)
• ALPINE: Active Link Prediction using Network Embedding [20.976178936255927]
  ネットワーク埋め込みに基づくリンク予測のための ALPINE (Active Link Prediction usIng Network Embedding) を提案する。 ALPINEは拡張性があり、より少ないクエリでリンク予測精度を向上させる。
  論文  参考訳（メタデータ） (2020-02-04T11:09:03Z)

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

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