图嵌入算法

嵌入算法来源于数学中的 Embedding,目的是抽象高维的空间数据到低维的具象空间。图嵌入,即通过图的方式抽取高维数据形成低维可表示的因子,而不管高维还是低维,一般都为了表示某个点。

目前 Ultipa 服务支持了多种图嵌入算法,如随机游走,Node2Vec 和 Line 算法。

随机游走(Random Walk)

图上任意点开始按照某种规则进行遍历,形成路径集合,该集合作为 embedding 的训练样本。ULTIPA 提供三种规则:

  • 完全随机游走
  • node2vec 随机游走
  • struc2vec 随机游走

完全随机游走

完全随机游走的 [命令] 为:algo(random_walk)

完全随机游走的 [配置] 为:

名称 类型 规范 描述
walk_num int >0, 必填 number of walker
walk_length int >0, 必填 walking length
edge_property_name string / 沿着某一种边随机游走
limit int >0; -1 ,必填 需要返回的结果的条数,-1表示返回所有结果

Node2Vec 随机游走

Node2vec 随机游走的 [命令] 为: algo(random_walk_node2vec)

Node2vec 随机游走的 [配置] 为:

名称 类型 规范 描述
buffer_size int >0,必填 训练前需要完成的随机游走次数
walk_num int >0,必填 游走的次数
walk_length int >0,必填 每次游走的距离/步数
p float >0, 必填 值越大,向回走的概率越小
q float >0, 必填 设置能向远处走的概率
大于 1:倾向同级走
小于 1:倾向向远处走
edge_property_name string 属性类型: 数字 number 游走当中的边的权重来源,若不设置,则都为 1

Struc2Vec 随机游走

Struc2Vec 随机游走的[命令]为:algo(random_walk_struc2vec)

Struc2Vec 随机游走的[配置]为:

名称 类型 规范 描述
walk_num int >0, 必填 游走的次数
walk_length int >0, 必填 每次游走的距离/步数
k int 必填 层的数量(the number of layer),建议小于等予全图平均最短
stay_probability float 必填 保留在当前层的概率(0,1)

Node2Vec

Node2Vec 是一种综合考虑 DFS 邻域和 BFS 邻域的图嵌入方法,通过结合了 DFS 和 BFS 的随机游走产生训练样本,使用 Skip-gram 和 SGD 的 word2vec 模型训练得到图中节点的 embedding 向量。 Node2Vec 的图嵌入算法依赖于 Node2Vec 的随机游走算法。

Node2Vec 的 [命令] 为: algo(node2vec)

Node2Vec 的 [配置] 为:

名称 类型 规范 描述
walk_num int >0, 必填 游走的次数
walk_length int >0, 必填 每次游走的长度
p float >0, 必填 值越大,向回走的概率越小
q float 必填 设置能向远处走的概率
大于 1:倾向同级走
小于 1:倾向向远处走
window_size int > 0, 必填 window size
dimension int > 0, 必填 example: 100
learning_rate double > 0, < 1,必填 Recommend: 0.025
min_learning_rate double >0, <1,必填 example: learning_rate * 0.0001
sub_sample_alpha double 必填 -1 as default,can be 0.001 in word2vec, the equation is (sqrt(x / 0.001) + 1) * (0.001 / x)
resolution int 必填 Recommend: 10 or 100
neg_num int >0,必填 number of words in negative sampling phrase (0, 10)
min_frequency int >= 0,必填 remove nodes that occur fewer than 'min_frequency
loop_num int >0 ,必填 loop number (0, 100)
buffer_size int >0 ,必填 训练前需要完成的随机游走次数
limit int >0; -1, 必填 需要返回的结果的条数,-1表示返回所有结果

Struc2Vec 算法

Struc2Vec 是从空间结构相似性的角度定义顶点相似度的。

Struc2Vec 算法的 [命令] 为:algo(struc2vec)

Struc2Vec 算法的 [配置] 为:

名称 类型 规范 描述
walk_num int >0, 必填 游走的次数
walk_length int >0, 必填 每次游走的步数
k int 必填 随机游走当中,分层数量
stay_probability float 必填 保持在当前层游走的概率
window_size int > 0, 必填 window size
dimension int > 0, 必填 example: 100
learning_rate double > 0, < 1,必填 Recommend: 0.025
min_learning_rate double >0, <1,必填 example: learning * rate * 0.0001
sub_sample_alpha double 必填 -1 as default,can be 0.001 in word2vec, the equation is (sqrt(x / 0.001) + 1) _ (0.001 / x)
resolution int 必填 Recommend: 10 or 100
loop_num int >0 ,必填 loop number
neg_num int >0 , 必填 number of words in negative sampling phrase
min_frequency int >= 0, 必填 remove nodes that occur fewer than 'min_frequency'

LINE 算法(large information network embedding)

LINE 也是一种图嵌入的训练模型,使用节点的 BFS 信息(一阶或二阶相似度)构造训练样本,使用和 Node2Vec 类似的方式训练得到节点的 embedding 向量。

LINE 算法的 [命令] 为:algo(line)

LINE 算法的 [配置] 为:

名称 类型 规范 描述
edge_property_name string 必填 edge property name
dimension int >0, 必填 dimension of the embedded vector , 10~n100 (e.g : 100)
resolution int >0, 必填 Recommend: 10 or 100
start_alpha double >0, 必填 0.025 recommended
neg_num int >0, 必填 number of words in negative sampling phrase
total_sample int >0, 必填 number of samples (0,10)
train_order int 1 or 2, 必填 1(first order proximity)
2(second order proximity)