論文の概要: Faster Graph Embeddings via Coarsening

• arxiv url: http://arxiv.org/abs/2007.02817v3
• Date: Thu, 22 Oct 2020 13:49:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-13 02:09:42.095953
• Title: Faster Graph Embeddings via Coarsening
• Title（参考訳）: 粗大化によるグラフ埋め込みの高速化
• Authors: Matthew Fahrbach, Gramoz Goranci, Richard Peng, Sushant Sachdeva, Chi Wang
• Abstract要約: グラフ埋め込みは、グラフ構造化データ上のノード分類やリンク予測といった機械学習タスクのためのユビキタスツールである。 大規模グラフに対する埋め込みの計算は、関連する頂点の小さな部分集合のみに関心がある場合でも、非効率的である。 我々は、関連する頂点の埋め込みを計算するために、Schur補数に基づく効率的なグラフ粗大化手法を提案する。
• 参考スコア（独自算出の注目度）: 25.37181684580123
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph embeddings are a ubiquitous tool for machine learning tasks, such as node classification and link prediction, on graph-structured data. However, computing the embeddings for large-scale graphs is prohibitively inefficient even if we are interested only in a small subset of relevant vertices. To address this, we present an efficient graph coarsening approach, based on Schur complements, for computing the embedding of the relevant vertices. We prove that these embeddings are preserved exactly by the Schur complement graph that is obtained via Gaussian elimination on the non-relevant vertices. As computing Schur complements is expensive, we give a nearly-linear time algorithm that generates a coarsened graph on the relevant vertices that provably matches the Schur complement in expectation in each iteration. Our experiments involving prediction tasks on graphs demonstrate that computing embeddings on the coarsened graph, rather than the entire graph, leads to significant time savings without sacrificing accuracy.
• Abstract（参考訳）: グラフ埋め込みは、グラフ構造化データ上のノード分類やリンク予測といった機械学習タスクのためのユビキタスツールである。 しかし、大規模グラフの埋め込みの計算は、関連する頂点の小さなサブセットだけに興味があるとしても、非常に非効率である。 これに対処するために,schur補数に基づく効率的なグラフ粗さ化手法を提案し,関連する頂点の埋め込み計算を行う。 これらの埋め込みは、非関係頂点上のガウス除去によって得られるシューア補グラフによって正確に保存されていることが証明される。 シュア補数計算は高価であるため、関連する頂点上の粗いグラフを生成するほぼ線形時間アルゴリズムを、各反復においてシュア補数と確実に一致させる。 グラフ上の予測タスクに関する実験は、グラフ全体ではなく粗いグラフへの埋め込みの計算が、精度を犠牲にすることなくかなりの時間節約をもたらすことを示している。

関連論文リスト

• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。 MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。 本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
  論文  参考訳（メタデータ） (2024-05-31T09:26:26Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure [18.00833762891405]
  Graph Lottery Ticket (GLT)仮説: グラフごとに非常に疎いバックボーンが存在する。 本研究は,グラフ学習アルゴリズムの性能に直接影響を及ぼす関心の指標を8つ研究する。 任意のグラフでこれらのGLTを見つけるための単純で効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T00:24:44Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  本研究では,スムーズなグラフ信号分布の空間への埋め込みを通じて,グラフ平均を定義する新しいフレームワークを提案する。 この埋め込み空間において平均を求めることにより、構造情報を保存する平均グラフを復元することができる。 我々は,新しいグラフの意味の存在と特異性を確立し,それを計算するための反復アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-05-31T11:04:53Z)
• Inference Attacks Against Graph Neural Networks [33.19531086886817]
  グラフの埋め込みは、グラフ分析問題を解決する強力なツールである。 グラフ埋め込みの共有は興味深いが、関連するプライバシーリスクは未調査だ。 3つの推論攻撃を組み込むことで,グラフ埋め込みの情報漏洩を系統的に調査する。
  論文  参考訳（メタデータ） (2021-10-06T10:08:11Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  本稿では,重要なグラフ構造情報を活用するために,クロスビューグラフプーリング(Co-Pooling)手法を提案する。 クロスビュー相互作用、エッジビュープーリング、ノードビュープーリングにより、相互にシームレスに強化され、より情報的なグラフレベルの表現が学習される。
  論文  参考訳（メタデータ） (2021-09-24T08:01:23Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  本稿では,AGE という逆グラフ埋め込みのための頑健なフレームワークを提案する。 AGEは、暗黙の分布から強化された負のサンプルとして偽の隣接ノードを生成する。 本フレームワークでは,3種類のグラフデータを扱う3つのモデルを提案する。
  論文  参考訳（メタデータ） (2021-05-22T07:05:48Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL)は、グラフ全体をベクトル空間に埋め込むフレームワークである。 グラフ間の類似性をノード埋め込み分布間の類似性の関数として定義する上で,新たな知見を活用する。 各種ベンチマークグラフ固有性予測タスクにおける新しいグラフ埋め込み手法の評価を行った。
  論文  参考訳（メタデータ） (2020-06-16T18:23:00Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  グラフオートエンコーダ(GAE)は、グラフ埋め込みのための表現学習において強力なツールである。 本稿では,2つの新しい教師なしグラフ埋め込み法,適応グラフ学習(BAGE)による教師なしグラフ埋め込み,変分適応グラフ学習(VBAGE)による教師なしグラフ埋め込みを提案する。 いくつかのデータセットに関する実験的研究により、我々の手法がノードクラスタリング、ノード分類、グラフ可視化タスクにおいて、ベースラインよりも優れていることが実証された。
  論文  参考訳（メタデータ） (2020-03-10T02:33:14Z)

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

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