論文の概要: Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings

• arxiv url: http://arxiv.org/abs/2107.10014v1
• Date: Wed, 21 Jul 2021 11:23:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-22 19:21:40.070057
• Title: Delving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings
• Title（参考訳）: Delving Into Deep Walkers: ランダムウォークに基づく頂点埋め込みの収束解析
• Authors: Dominik Kloepfer, Angelica I. Aviles-Rivero, Daniel Heydecker
• Abstract要約: ランダムウォークに基づく埋め込み手法の理論解析を行う。 いくつかの弱い仮定の下では、コーポラはランダムウォークの個数の極限$N to infty$と、ランダムウォークの2つの極限$N$と各ランダムウォークの長さ$Ltoinfty$の両方に収束する。
• 参考スコア（独自算出の注目度）: 0.7366405857677227
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph vertex embeddings based on random walks have become increasingly influential in recent years, showing good performance in several tasks as they efficiently transform a graph into a more computationally digestible format while preserving relevant information. However, the theoretical properties of such algorithms, in particular the influence of hyperparameters and of the graph structure on their convergence behaviour, have so far not been well-understood. In this work, we provide a theoretical analysis for random-walks based embeddings techniques. Firstly, we prove that, under some weak assumptions, vertex embeddings derived from random walks do indeed converge both in the single limit of the number of random walks $N \to \infty$ and in the double limit of both $N$ and the length of each random walk $L\to\infty$. Secondly, we derive concentration bounds quantifying the converge rate of the corpora for the single and double limits. Thirdly, we use these results to derive a heuristic for choosing the hyperparameters $N$ and $L$. We validate and illustrate the practical importance of our findings with a range of numerical and visual experiments on several graphs drawn from real-world applications.
• Abstract（参考訳）: ランダムウォークに基づくグラフ頂点埋め込みは近年ますます影響力を増しており、関連する情報を保存しながら、グラフを効率的に計算的に消化可能な形式に変換することにより、いくつかのタスクで優れたパフォーマンスを示している。 しかし、そのようなアルゴリズムの理論的性質、特にハイパーパラメータとグラフ構造が収束挙動に与える影響は、今のところ十分に理解されていない。 本研究では,ランダムウォークに基づく埋め込み手法に関する理論的解析を行う。 まず、いくつかの弱い仮定の下で、ランダムウォークに由来する頂点埋め込みは、ランダムウォークの数の唯一の極限である$n \to \infty$と、$n$と各ランダムウォークの2倍の極限である$l\to\infty$の両方に収束する。 第二に、単一および二重極限に対するコーパスの収束率を定量化する濃度境界を導出する。 第3に、これらの結果を用いて超パラメータを$N$と$L$を選択するヒューリスティックを導出する。 実世界のアプリケーションから抽出したいくつかのグラフについて,数値的および視覚的実験を行い,本研究の実用的重要性を検証・実証した。

関連論文リスト

• Sensitivity of quantum walk to phase reversal and geometric perturbations: an exploration in complete graphs [0.0]
  主連結グラフ $G$ と二次連結グラフ $G'$ の統合から生じるグラフ構造上の量子ウォークのダイナミクスを解析する。 この幾何学的摂動が量子ウォークに基づく探索アルゴリズムの成功確率に与える影響について検討する。
  論文  参考訳（メタデータ） (2024-02-13T06:17:07Z)
• Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
  我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。 また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
  論文  参考訳（メタデータ） (2023-04-27T06:27:37Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Recurrently Predicting Hypergraphs [30.092688729343678]
  問題は、$n$要素の集合に対して$mathcalO(2n)$でスケーリング可能なマルチウェイ関係(ハイパーエッジ)の数から生じる。 そこで本研究では,提案手法の初期推定を反復的に精算することにより,入射行列を予測する再帰型ハイパーグラフニューラルネットワークを提案する。
  論文  参考訳（メタデータ） (2021-06-26T01:12:41Z)
• Intervention Efficient Algorithms for Approximate Learning of Causal Graphs [22.401163479802094]
  我々は、潜時の存在下で観察された変数の集合間の因果関係を学習する問題を研究する。 我々の目標は、介入の最小限の費用で、すべての因果関係や祖先関係の方向性を$G$で回収することです。 我々のアルゴリズムは効率的な介入設計と低コストな分離集合系の設計を組み合わせる。
  論文  参考訳（メタデータ） (2020-12-27T17:08:46Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  大規模な非最適化問題は、現代の機械学習ではユビキタスである。 我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
  論文  参考訳（メタデータ） (2020-02-09T09:56:06Z)

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

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