論文の概要: PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding
- arxiv url: http://arxiv.org/abs/2408.02705v1
- Date: Mon, 5 Aug 2024 10:38:30 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-07 16:08:09.266937
- Title: PSNE: Efficient Spectral Sparsification Algorithms for Scaling Network Embedding
- Title（参考訳）: PSNE: ネットワーク埋め込みのスケーリングのための効率的なスペクトルスカラー化アルゴリズム
- Authors: Longlong Lin, Yunfeng Yu, Zihao Wang, Zeli Wang, Yuying Zhao, Jin Zhao, Tao Jia,
- Abstract要約: PSNEはtextbfScaling textbfNetwork textbfEmbeddingのための効率的なスペクトルstextbfParsification法である。
PSNEは10の競合相手よりも効率的で効果的でスケーラブルであることを示す。
- 参考スコア（独自算出の注目度）: 13.049244862795637
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Network embedding has numerous practical applications and has received extensive attention in graph learning, which aims at mapping vertices into a low-dimensional and continuous dense vector space by preserving the underlying structural properties of the graph. Many network embedding methods have been proposed, among which factorization of the Personalized PageRank (PPR for short) matrix has been empirically and theoretically well supported recently. However, several fundamental issues cannot be addressed. (1) Existing methods invoke a seminal Local Push subroutine to approximate \textit{a single} row or column of the PPR matrix. Thus, they have to execute $n$ ($n$ is the number of nodes) Local Push subroutines to obtain a provable PPR matrix, resulting in prohibitively high computational costs for large $n$. (2) The PPR matrix has limited power in capturing the structural similarity between vertices, leading to performance degradation. To overcome these dilemmas, we propose PSNE, an efficient spectral s\textbf{P}arsification method for \textbf{S}caling \textbf{N}etwork \textbf{E}mbedding, which can fast obtain the embedding vectors that retain strong structural similarities. Specifically, PSNE first designs a matrix polynomial sparser to accelerate the calculation of the PPR matrix, which has a theoretical guarantee in terms of the Frobenius norm. Subsequently, PSNE proposes a simple but effective multiple-perspective strategy to enhance further the representation power of the obtained approximate PPR matrix. Finally, PSNE applies a randomized singular value decomposition algorithm on the sparse and multiple-perspective PPR matrix to get the target embedding vectors. Experimental evaluation of real-world and synthetic datasets shows that our solutions are indeed more efficient, effective, and scalable compared with ten competitors.
- Abstract（参考訳）: ネットワーク埋め込みは、多くの実用的な応用があり、グラフの構造的特性を保ちながら、頂点を低次元で連続的な高密度ベクトル空間にマッピングすることを目的として、グラフ学習において大きな注目を集めている。
多くのネットワーク埋め込み手法が提案され、その中ではPersonalized PageRank (PPR) 行列の分解が経験的、理論的に支持されている。
しかし、いくつかの根本的な問題は解決できない。
1) PPR行列の行や列を近似するために、既存のメソッドがセミナルなローカルプッシュサブルーチンを呼び出します。
したがって、彼らは証明可能なPPR行列を得るために$n$$$(n$はノード数)ローカルプッシュサブルーチンを実行しなければなりません。
2) PPRマトリックスは, 頂点間の構造的類似性を捉え, 性能劣化を招いた。
これらのジレンマを克服するために、効率的なスペクトル s\textbf{P}arsification method for \textbf{S}caling \textbf{N}etwork \textbf{E}mbedding を提案する。
具体的には、PSNE は最初に行列多項式スペーサーを設計し、フロベニウスノルムの理論的保証を持つ PPR 行列の計算を高速化する。
その後、PSNEは、得られた近似PPR行列の表現力をさらに高めるために、単純だが効果的な多重パースペクティブ戦略を提案する。
最後に、PSNEはターゲット埋め込みベクトルを得るためにスパースおよび多重パースペクティブPPR行列にランダム化特異値分解アルゴリズムを適用する。
実世界のデータセットと合成データセットの実験的評価は、我々のソリューションが10の競合相手と比較して、確かに効率的で効果的でスケーラブルであることを示している。
関連論文リスト
- Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective [7.392815088603314]
まず、PPR関連行列を分解する最先端の埋め込み手法がクローズドフォームフレームワークに統合可能であることを示す。
そして,この戦略によって生成された埋め込みを逆転して,グラフトポロジ情報をよりよく復元できるかどうかを考察する。
我々の知る限りでは、PPRベースのノード埋め込みアプローチの解釈可能性に焦点を当てた最初の研究である。
論文 参考訳（メタデータ） (2024-05-30T03:02:23Z) - Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement
Learning [53.445068584013896]
低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。
低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。
簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
論文 参考訳（メタデータ） (2023-10-10T17:06:41Z) - Low-Rank Prune-And-Factorize for Language Model Compression [18.088550230146247]
マトリックスの分解は、中程度から高い圧縮速度で良好な性能を維持することができない。
スパシティ対応SVDとミックスランクファインチューニングの2つの手法を提案する。
論文 参考訳（メタデータ） (2023-06-25T07:38:43Z) - Sparse high-dimensional linear regression with a partitioned empirical
Bayes ECM algorithm [62.997667081978825]
疎高次元線形回帰に対する計算効率が高く強力なベイズ的手法を提案する。
パラメータに関する最小の事前仮定は、プラグイン経験的ベイズ推定(英語版)を用いて用いられる。
提案手法はRパッケージプローブに実装されている。
論文 参考訳（メタデータ） (2022-09-16T19:15:50Z) - Entrywise Recovery Guarantees for Sparse PCA via Sparsistent Algorithms [9.112172220055431]
一般的な高次元のガウス設計の下で、スパースPCAに対して入出力$ell_2,infty$boundsを提供する。
提案手法は,確率の高い正しいサポートを選択するアルゴリズムであり,スパーシスタントなアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-08T18:50:35Z) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Sparse PCA: Algorithms, Adversarial Perturbations and Certificates [9.348107805982604]
標準統計モデルにおけるスパースPCAの効率的なアルゴリズムについて検討する。
私たちのゴールは、小さな摂動に耐性を持ちながら、最適な回復保証を達成することです。
論文 参考訳（メタデータ） (2020-11-12T18:58:51Z) - Positive Semidefinite Matrix Factorization: A Connection with Phase
Retrieval and Affine Rank Minimization [71.57324258813674]
位相探索(PR)とアフィンランク最小化(ARM)アルゴリズムに基づいてPSDMFアルゴリズムを設計可能であることを示す。
このアイデアに触発され、反復的ハードしきい値(IHT)に基づくPSDMFアルゴリズムの新たなファミリーを導入する。
論文 参考訳（メタデータ） (2020-07-24T06:10:19Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。