論文の概要: Consistency of random-walk based network embedding algorithms
- arxiv url: http://arxiv.org/abs/2101.07354v1
- Date: Mon, 18 Jan 2021 22:49:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-27 06:01:27.309689
- Title: Consistency of random-walk based network embedding algorithms
- Title（参考訳）: ランダムウォークに基づくネットワーク埋め込みアルゴリズムの一貫性
- Authors: Yichi Zhang, Minh Tang
- Abstract要約: node2vecアルゴリズムとDeepWalkアルゴリズムを行列ファクタリゼーションの観点から検討する。
その結果,観測ネットワークの幅,ランダムウォークのウィンドウサイズ,ノード2vec/DeepWalk埋め込みの収束率との微妙な相互作用が示唆された。
- 参考スコア（独自算出の注目度）: 13.214230533788932
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random-walk based network embedding algorithms like node2vec and DeepWalk are
widely used to obtain Euclidean representation of the nodes in a network prior
to performing down-stream network inference tasks. Nevertheless, despite their
impressive empirical performance, there is a lack of theoretical results
explaining their behavior. In this paper we studied the node2vec and DeepWalk
algorithms through the perspective of matrix factorization. We analyze these
algorithms in the setting of community detection for stochastic blockmodel
graphs; in particular we established large-sample error bounds and prove
consistent community recovery of node2vec/DeepWalk embedding followed by
k-means clustering. Our theoretical results indicate a subtle interplay between
the sparsity of the observed networks, the window sizes of the random walks,
and the convergence rates of the node2vec/DeepWalk embedding toward the
embedding of the true but unknown edge probabilities matrix. More specifically,
as the network becomes sparser, our results suggest using larger window sizes,
or equivalently, taking longer random walks, in order to attain better
convergence rate for the resulting embeddings. The paper includes numerical
experiments corroborating these observations.
- Abstract（参考訳）: node2vecやDeepWalkのようなランダムウォークベースのネットワーク埋め込みアルゴリズムは、ダウンストリームネットワーク推論タスクを実行する前にネットワーク内のノードのユークリッド表現を得るために広く使用されている。
しかし、その印象的な経験的パフォーマンスにもかかわらず、その振る舞いを説明する理論的結果の欠如がある。
本稿では行列分解の観点から, node2vec と DeepWalk のアルゴリズムについて検討した。
確率的ブロックモデルグラフに対するコミュニティ検出の設定において,これらのアルゴリズムを解析し,特に,大きなサンプル誤差境界を設定し,node2vec/deepwalk埋め込みとk-meansクラスタリングの一貫したコミュニティ回復を証明した。
理論的には,観測されたネットワークのスパース性,ランダムウォークのウィンドウサイズ,node2vec/deepwalk埋め込みの収束率と,真だが未知のエッジ確率行列の埋め込みとの微妙な相互作用を示す。
より具体的には、ネットワークがスペーサー化するにつれて、より大きなウィンドウサイズ、または同等に長いランダムウォークを用いて、結果としての埋め込みの収束率を改善することが提案される。
これらの観測を裏付ける数値実験を含む。
関連論文リスト
- Inference of Causal Networks using a Topological Threshold [0.10241134756773226]
本稿では,因果関係しきい値を自動的に決定する制約に基づくアルゴリズムを提案する。
このアルゴリズムは一般にPCアルゴリズムよりも高速で精度が高いことを示す。
論文 参考訳（メタデータ） (2024-04-21T21:56:39Z) - Optimization Guarantees of Unfolded ISTA and ADMM Networks With Smooth
Soft-Thresholding [57.71603937699949]
我々は,学習エポックの数の増加とともに,ほぼゼロに近いトレーニング損失を達成するための最適化保証について検討した。
トレーニングサンプル数に対する閾値は,ネットワーク幅の増加とともに増加することを示す。
論文 参考訳（メタデータ） (2023-09-12T13:03:47Z) - NODDLE: Node2vec based deep learning model for link prediction [0.0]
我々はNODDLE(NOde2vec anD Deep Learning mEthodの統合)を提案する。
実験結果から, この手法は, 従来のソーシャル・ネットワーク・データセットの手法よりも優れた結果が得られることがわかった。
論文 参考訳（メタデータ） (2023-05-25T18:43:52Z) - Binarizing Sparse Convolutional Networks for Efficient Point Cloud
Analysis [93.55896765176414]
我々は,効率的な点群解析のためのBSC-Netと呼ばれるバイナリスパース畳み込みネットワークを提案する。
我々は,移動したスパース畳み込みにおけるサイトマッチングに最適なオプションを見つけるために,異なる検索戦略を採用している。
我々のBSC-Netは、我々の厳格なベースラインを大幅に改善し、最先端のネットワーク双対化手法より優れています。
論文 参考訳（メタデータ） (2023-03-27T13:47:06Z) - Robust Training and Verification of Implicit Neural Networks: A
Non-Euclidean Contractive Approach [64.23331120621118]
本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。
組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。
MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
論文 参考訳（メタデータ） (2022-08-08T03:13:24Z) - Interpolation-based Correlation Reduction Network for Semi-Supervised
Graph Learning [49.94816548023729]
補間型相関低減ネットワーク(ICRN)と呼ばれる新しいグラフコントラスト学習手法を提案する。
提案手法では,決定境界のマージンを大きくすることで,潜在特徴の識別能力を向上させる。
この2つの設定を組み合わせることで、豊富なラベル付きノードと稀に価値あるラベル付きノードから豊富な監視情報を抽出し、離散表現学習を行う。
論文 参考訳（メタデータ） (2022-06-06T14:26:34Z) - Community detection using low-dimensional network embedding algorithms [1.052782170493037]
我々はDeepWalkとnode2vecという2つの主要なアルゴリズムが、標準ネットワークモデルのためのコミュニティを回復する際の性能を厳格に理解している。
固定された共起窓を考えると、非追跡確率の低いランダムウォークを用いた node2vec は、多くのスペーサーネットワークで成功することを示す。
論文 参考訳（メタデータ） (2021-11-04T14:57:43Z) - Ergodic Limits, Relaxations, and Geometric Properties of Random Walk
Node Embeddings [11.549910517683085]
ランダムウォークに基づくノード埋め込みアルゴリズムは,ネットワーク上のランダムウォークから計算したノード埋め込みベクトルとスキップバイグラム統計の客観的関数を最適化することにより,ノードのベクトル表現を学習する。
本稿では,ネットワーク内に隠されたブロック構造を発見するための教師なし設定において,ランダムウォークに基づくノード埋め込みの特性について検討する。
論文 参考訳（メタデータ） (2021-09-09T19:24:35Z) - Overlapping community detection in networks via sparse spectral
decomposition [1.0660480034605242]
各ノードが複数のコミュニティに属することができるネットワークにおいて,重複するコミュニティメンバシップを推定する問題を考える。
本アルゴリズムは,反復しきい値を用いたスパース主部分空間推定に基づく。
アルゴリズムの固定点がブロックモデルの下での正しいノードメンバシップに対応することを示す。
論文 参考訳（メタデータ） (2020-09-20T07:31:09Z) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳（メタデータ） (2020-06-28T23:09:27Z) - Binarized Graph Neural Network [65.20589262811677]
我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。
提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。
実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
論文 参考訳（メタデータ） (2020-04-19T09:43:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。