ترجمه فارسی مقاله PSNE: الگوریتم‌های پراکندگی طیفی کارآمد برای مقیاس‌بندی جاسازی شبکه

چکیده

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 stextbf{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.

چکیده به فارسی (ترجمه ماشینی)

تعبیه شبکه دارای برنامه های کاربردی بیشماری است و در یادگیری گراف توجه گسترده ای را به خود جلب کرده است ، که هدف آن نقشه برداری از رئوس ها در فضای وکتور متراکم کم و مداوم با حفظ خصوصیات ساختاری اساسی نمودار است.بسیاری از روشهای تعبیه شده شبکه ارائه شده است ، که از جمله این فاکتورسازی ماتریس شخصی PageRank (PPR برای کوتاه) به تازگی از نظر تجربی و نظری به خوبی پشتیبانی شده است.با این حال ، به چندین موضوع اساسی نمی توان رسیدگی کرد..بنابراین ، آنها برای به دست آوردن یک ماتریس PPR قابل اثبات ، باید $ n $ ($ n $ تعداد گره ها) را اجرا کنند ، و در نتیجه هزینه های محاسباتی بسیار بالایی برای بزرگ $ N $ ایجاد می شود.(2) ماتریس PPR قدرت محدودی در ضبط شباهت ساختاری بین راس ها دارد و منجر به تخریب عملکرد می شود.برای غلبه بر این معضلات ، ما PSNE را پیشنهاد می کنیم ، یک روش کارآمد S TextBF {P} برای TextBf {S} Caling textBf {n} etwork textBf {e} mdeddشباهت های ساختاری.به طور خاص ، PSNE ابتدا یک اسپارسر چند جمله ای ماتریس را برای تسریع در محاسبه ماتریس PPR ، که از نظر هنجار Frobenius یک ضمانت نظری دارد ، طراحی می کند.پس از آن ، PSNE یک استراتژی ساده اما مؤثر چند ساله برای افزایش قدرت بازنمایی ماتریس تقریبی PPR به دست آمده ارائه می دهد.سرانجام ، PSNE یک الگوریتم تجزیه و تحلیل ارزش مفرد تصادفی را بر روی ماتریس PPR پراکنده و چند منظوره برای به دست آوردن بردارهای تعبیه شده هدف اعمال می کند.ارزیابی تجربی مجموعه داده های دنیای واقعی و مصنوعی نشان می دهد که راه حل های ما در واقع در مقایسه با ده رقیب کارآمدتر ، مؤثر و مقیاس پذیر هستند.