对DeepWalk和Node2vec进行理论分析,以在随机区块模型中准确恢复社区结构
IEEE transactions on pattern analysis and machine intelligence
|October 25, 2023
概括
本研究提供了DeepWalk和node2vec网络嵌入方法的理论保证,通过通过矩阵分解来分析它们. 研究表明,即使在稀疏的网络中,在随机区块模型图表中,社区也能完全恢复.
科学领域:
- 图形理论是指图形的理论.
- 机器学习 机器学习
- 网络分析 网络分析
背景情况:
- 基于随机走路的网络嵌入算法,如DeepWalk和node2vec,对于网络中的节点表示非常普遍.
- 现有的方法对其大样本行为缺乏理论解释.
- 社区检测是网络分析的关键下游任务.
研究的目的:
- 提供使用矩阵分解角度对DeepWalk和node2vec算法的理论分析.
- 为了获得由这些算法生成的节点嵌入的错误界限.
- 建立使用这些嵌入式的社区检测的理论保证.
主要方法:
- 矩阵分解方法来分析DeepWalk和node2vec.
- 在随机区块模型图形及其经度校正的变体中进行分析.
- 对于单一向量的行wise均扰动极限的利用.
- 对节点嵌入的高概率错误极限的推导.
- 应用K-手段/中位数用于社区恢复.
主要成果:
- 基于矩阵分解的node2vec/DeepWalk嵌入式的高概率误差极限.
- 通过使用 node2vec/DeepWalk 和 K-means/medians 证明了完美的会员恢复.
- 在稀疏的随机区块模型图形中保证了准确的社区恢复,具有足够的参数.
- 理论发现得到了数值实验和现实世界的数据的支持.
结论:
- 矩阵分解视角为理解DeepWalk和node2vec提供了一个理论基础.
- 这些算法,特别是node2vec,可以在各种网络类型中可靠地恢复社区结构.
- 该研究弥合了经验上的成功与网络嵌入技术的理论理解之间的差距.
相关概念视频
Block Diagram Reduction
221
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
221
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
531
This lesson introduces two critical methods in pharmacokinetics, the Wagner-Nelson and Loo-Riegelman methods, used for estimating the absorption rate constant (ka) for drugs administered via non-intravenous routes. The Wagner-Nelson method relates ka to the plasma concentration derived from the slope of a semilog percent unabsorbed time plot. However, it is limited to drugs with one-compartment kinetics and can be impacted by factors like gastrointestinal motility or enzymatic degradation.
On...
On...
531
Distributed Loads: Problem Solving
650
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
650
Model Approaches for Pharmacokinetic Data: Distributed Parameter Models
74
Pharmacokinetic models are mathematical constructs that represent and predict the time course of drug concentrations in the body, providing meaningful pharmacokinetic parameters. These models are categorized into compartment, physiological, and distributed parameter models.
The distributed parameter models are specifically designed to account for variations and differences in some drug classes. This model is particularly useful for assessing regional concentrations of anticancer or...
The distributed parameter models are specifically designed to account for variations and differences in some drug classes. This model is particularly useful for assessing regional concentrations of anticancer or...
74
Stability of structures
177
In mechanical engineering, the stability of systems under various forces is critical for designing durable and efficient structures. One fundamental way to explore these concepts is by analyzing systems like two rods connected at a pivot point, O, with a torsional spring of spring constant k at the pivot point. This system is similar in appearance to a scissor jack used to change tires on a car. In this case, the arms of the linkage (equivalent to the rods in this system) are entirely vertical,...
177
Cluster Sampling Method
12.0K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
12.0K


