概述
快速随机投影(Fast Random Projection,FastRP)是一种可扩展且高性能的算法,用于学习图中节点的嵌入表示。FastRP实现了节点嵌入的迭代计算,主要包含两个步骤:一是构造节点相似度矩阵构造,二是通过随机投影对矩阵进行降维。
FastRP算法是由H. Chen等人于2019年提出的:
- H. Chen, S.F. Sultan, Y. Tian, M. Chen, S. Skiena, Fast and Accurate Network Embeddings via Very Sparse Random Projection (2019)
FastRP工作框架
FastRP的作者提出,大多数图(节点)嵌入方法基本上由两部分组成:(1)构造一个节点相似度矩阵或从中隐式地采样节点对,然后(2)对该矩阵进行降维得到嵌入结果。
关于降维,许多流行的算法(如Node2Vec)都依赖于Skip-gram等耗时的方法。但作者认为,这些算法的成功并不归功于它们采用的降维方法,而是源于对相似度矩阵的正确构建。
因此,FastRP采用非常稀疏的随机投影(Very Sparse Random Projection)这种可扩展的高效降维技术。
非常稀疏的随机投影
随机投影(Random Projection)是一种降维方法,能够将数据点从高维空间嵌入到低维空间,同时大致保持数据点之间的相对的距离。随机投影的理论基础主要是约翰逊-林登斯特劳斯引理。
![](https://img.ultipa.cn/draw/draw_e93e6a3c89314525a8f5f2c05598284a.jpg?v='1663226696856')
随机投影背后的思想非常简单:要将矩阵Mn×m(对于图数据,有n = m)降维成矩阵Nn×d(d ≪ n),可以简单地将M乘以一个随机投影矩阵Rm×d,即N = M ⋅ R。
矩阵R中的每个元素是独立基于一个分布生成的。具体来说,FastRP采用非常稀疏的随机投影方法,其中R的元素基于以下分布生成:
![](https://img.ultipa.cn/2022-09-14-11-58-27-R.jpg)
其中s=sqrt(m)。
非常稀疏的随机投影具有优越的计算效率,因为它只需要进行矩阵乘法,并且R中占比(1-1/s)的元素都为零。
此外,嬴图支持使用一些数值类点属性(特征)来影响矩阵R的初始化。在这种情况下,矩阵R中的每一行由两部分拼接而成:
![](https://img.ultipa.cn/draw/draw_7aaffcfbcaad460b99db76f7b9e17a16.jpg?v='1707190840260')
- 元素d1 ~ dx由非常稀疏随机投影算法生成。
- 元素p1 ~ py是所选节点属性值的线性组合。
- x + y等于最终嵌入的维度,其中y称为属性维度。
- 所选节点属性的数量不必与属性维度相同。
构造节点相似性矩阵
FastRP算法在构建节点相似性矩阵时兼顾以下两点:
- 保留图的高阶接近性
- 对矩阵元素进行归一化处理
令S为图G = (V, E)的邻接矩阵,D为节点度矩阵,A为转移概率矩阵且A = D-1S。下面展示了一个例子,图中每条边上的数字代表边的权重:
![](https://img.ultipa.cn/draw/draw_5fdb4c3ac25f439eb8f8b6946fef80e2.jpg?v='1663141549257')
事实上,矩阵A中的元素Aij表示从节点i经过长度为1的随机游走到达节点j的概率。进一步地,如果将矩阵A与自身相乘k次得到矩阵Ak,Akij则表示从节点i经过长度为k的随机游走到达节点j的概率。如此,矩阵Ak保留了图的高阶接近性。
但是,当k → ∞,可以证明的是Akij → dj/2m,其中m = |E|,dj是第j个节点的度。由于许多真实世界的图是无标度的,因此Ak中的元素常呈现重尾分布。这意味着Ak中数据点之间的距离主要受具有异常大值的列影响,这使得它们的意义降低,并为下一步降维带来了挑战。
为了解决这个问题,FastRP进一步对矩阵Ak进行归一化处理,方法是将其乘以对角线归一化矩阵L,其中Lij = (dj/2m)β,β是归一化强度。归一化强度控制节点度对嵌入的影响:当β为负时,削弱高节点度邻居的重要性,β为正数时,则相反。
算法步骤
FastRP算法的步骤如下:
- 生成随机映射矩阵R
- 对归一化的1步转移矩阵进行降维:N1 = A ⋅ L ⋅ R
- 对归一化的2步转移矩阵进行降维:N2 = A ⋅ (A ⋅ L ⋅ R) = A ⋅ N1
- 重复步骤3直到对归一化的k步转移矩阵进行降维:Nk = A ⋅ Nk-1
- 生成矩阵A的不同幂次的加权组合结果:N = α1N1 + ... + αkNk,其中α1,...,αk为迭代权重
特殊说明
- FastRP算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(fastRP)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
dimension | int | ≥2 | / | 否 | 嵌入向量的维度 |
normalizationStrength | float | / | / | 是 | 归一化强度β |
iterationWeights | []float | >0 | [0.0,1.0,1.0] | 是 | 每次迭代结果的权重,数组长度就是算法的迭代轮数 |
edge_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 是 | 用作边权重的属性,权重值为所有指定属性值的和 |
node_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 是 | 用作特征的点属性;propertyDimension 和node_schema_property 需要同时配置或忽略 |
propertyDimension | int | (0,dimension ] |
/ | 是 | 属性维度的长度;propertyDimension 和node_schema_property 需要同时配置或忽略 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
文件回写
配置项 | 回写内容 |
---|---|
filename | _id , embedding_result |
algo(fastRP).params({
dimension : 10,
normalizationStrength: 1.5,
iterationWeights: [0, 0.8, 0.2, 1],
edge_schema_property: ['w1', 'w2'],
node_schema_property: ['@default.f1', '@default.f2'],
propertyDimension: 3
}).write({
file:{
filename: 'embedding'
}
})
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | embedding_result |
点属性 | string |
algo(fastRP).params({
dimension : 10,
normalizationStrength: 1.5,
iterationWeights: [0, 0.8, 0.2, 1],
edge_schema_property: ['w1', 'w2']
}).write({
db:{
property: 'embedding'
}
})
直接返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
algo(fastRP).params({
dimension : 10,
normalizationStrength: 1.5,
iterationWeights: [0, 0.8, 0.2, 1]
}) as embeddings
return embeddings
流式返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
algo(fastRP).params({
dimension : 10,
normalizationStrength: 1.5,
iterationWeights: [0, 0.8, 0.2, 1]
}).stream() as embeddings
return embeddings