Struc2Vec - 嬴图算法与分析

修改密码

提交

Change Email

Submit

修改昵称

当前昵称：

提交

基础信息

用户邮箱：

用户昵称：
手机号：
公司名称：
公司邮箱:
地区：
语言：

修改密码

申请证书

当前未申请证书.

申请证书

Certificate	Issued at	Valid until	Serial No.	File

Serial No.	Valid until	File

Not having one? Apply now! >>>

ProductName	CreateTime	ID	Price	File

ProductName	CreateTime	ID	Price	File

No Invoice

创建嬴图账号

已经有嬴图账号了?立即登录！

忘记密码

重置密码

返回登录

Struc2Vec

HDC

概述

Struc2Vec代表"结构到向量"。该算法生成的节点向量能保留图的内在结构，即拓扑相似性，是一个革命性的图嵌入技术。

L. Ribeiro, P. Saverese, D. Figueiredo, struc2vec: Learning Node Representations from Structural Identity (2017)

尽管Node2Vec能够在某种程度上捕获节点间的结构相似性，但它受其生成过程中使用的随机游走深度所限制。与之不同，Struc2Vec在其框架中克服了这一限制，能够确保具有相似结构特征的节点在嵌入空间中有靠近的表示。

选择使用Node2Vec或Struc2Vec时，要考虑下游任务的性质：

Node2Vec适用于优先考虑节点同质性、捕获属性和连接相似性的任务。
Struc2Vec在需要关注局部拓扑相似性、保留节点之间结构关系的任务中表现出色。

基本概念

结构相似性

在各种网络中，节点往往具有承担特定的功能或角色的结构身份（Structural Identity）。发挥类似功能的节点自然属于同一类，表示它们具有结构相似性。例如，在公司的社交网络中，所有的实习生具有相似的角色。

节点之间的结构相似性（Structural Similarity）意味着它们的邻域拓扑是同构或对称的。具有相似功能的节点与其邻居节点之间具有相似的连接关系。

如图所示，节点u和v在结构上是相似的（度数分别为5和4，分别连接到3和2个三角形，都通过2个节点连接到网络的其余部分）。然而，它们之间没有直接相连，也没有共同邻居，甚至在网络中可能相隔很远。

当节点之间的距离超过随机游走的深度时，就很难使用Node2Vec 等方法为它们生成类似的表示。Struc2Vec算法有效地解决了这个问题。

Struc2Vec框架

1. 计算结构相似性

关于结构相似性，直观评判标准是：如果两个节点的度相同，它们在结构上是相似的；如果两个节点的邻居的度也相同，它们的结构相似性就更高了。

考虑一个无向无权图，表示为G = (V, E)，其直径表示为k*。R_k(u)表示图中距离节点u恰好k ∈ [0, k*]跳的节点集合，s(S)表示节点集合S ⊂ V的有序度数序列。以下是一个示例：

f_k(u,v)表示考虑k跳邻域（所有距离小于或等于k的节点）时，u和v之间的结构距离（Structural Distance）：

其中函数g() ≥ 0用来计算两个度序列之间的距离。请注意，随着k增大，f_k(u,v)是递增的，并且仅当u和v都有k跳邻居时才有定义。

为了计算序列s(R_k(u))和s(R_k(v))之间的距离（两个序列的大小可能不同），可以采用动态时间规整（DTW）或其他适用的函数。请注意，如果节点u和v的k跳邻域是同构的，则f_k-1(u,v) = 0。

2. 构建多层加权图

Struc2Vec构建一个多层加权图M来反映节点间的结构相似性，其中第k层使用节点的k跳邻域来定义。

M的每层都是一个完全无向加权图，节点集为V，因此有 $\frac{|V|*(|V|-1)}{2}$ 条边。第k层节点u和v之间的边权重与它们的结构距离成反比，计算方式如下：

请注意，只有当f_k(u,v)有定义时，u、v间的边才有定义。

层之间通过有向边相连。每个节点与它在上一层和下一层（如果有的话）的对应节点相连，层之间的边权重如下：

其中Γ_k(u)表示在第k层与节点u相连的、权重大于该层平均边权重的边数量。Γ_k(u)实际上衡量了节点u与第k层中其他节点的相似性。如果节点u在第k层有许多相似节点，则需要转移到更高的层才能准确地描述它的结构身份。

3. 为节点生成上下文

Struc2Vec使用随机游走生成节点序列来确定给定节点的上下文。

考虑在图M中进行的有偏随机游走。游走从每个节点在第0层的对应节点开始，当到达第k层的节点u（表示为u_k）时，随机游走首先决定是（1）留在当前层，还是（2）跳到别层：

(1) 以大小为q的概率留在当前层：移动到节点v_k的概率与w_k(u,v)的大小成正比。请注意，随机游走倾向于访问与当前节点在结构上更相似的节点。

(2) 以大小为1-q的概率跳到别层：移动到节点u_k+1或u_k-1的概率与w_k(u_k,u_k+1)和w_k(u_k,u_k-1)的大小成正比。请注意，在这种情况下，节点u在随机游走序列中只记录一次。

随机游走具有固定且相对较短的深度（步数），并且该过程会重复一定次数。

4.模型训练

从随机游走获取的节点序列会作为输入进入Skip-gram模型。Struc2Vec基于预测误差使用SGD来调整模型参数，并且通过负采样（Negative Sampling）和二次采样（Subsampling）等技术进行优化。

特殊说明

在考虑节点度时，自环边计算两次。
Struc2Vec的结果与边的方向无关。

示例图集

创建示例图集：

// 在空图集中逐行运行以下语句
insert().into(@default).nodes([{_id:"A"},{_id:"B"},{_id:"C"},{_id:"D"},{_id:"E"},{_id:"F"},{_id:"G"},{_id:"H"},{_id:"I"},{_id:"J"}])
insert().into(@default).edges([{_from:"A", _to:"B"}, {_from:"A", _to:"C"}, {_from:"D", _to:"C"}, {_from:"D", _to:"F"}, {_from:"E", _to:"C"}, {_from:"E", _to:"F"}, {_from:"F", _to:"G"}, {_from:"G", _to:"J"}, {_from:"H", _to:"G"}, {_from:"H", _to:"I"}])

创建HDC图集

将当前图集全部加载到HDC服务器hdc-server-1上，并命名为 hdc_struc2vec：

CALL hdc.graph.create("hdc-server-1", "hdc_struc2vec", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
})

hdc.graph.create("hdc_struc2vec", {
  nodes: {"*": ["*"]},
  edges: {"*": ["*"]},
  direction: "undirected",
  load_id: true,
  update: "static",
  query: "query",
  default: false
}).to("hdc-server-1")

参数

算法名：struc2vec

参数名	类型	规范	默认值	可选	描述
`ids`	[]`_id`	/	/	是	通过`_id`指定随机游走的起点；若未设置则计算所有点
`uuids`	[]`_uuid`	/	/	是	通过`_uuid`指定随机游走的起点；若未设置则计算所有点
`walk_length`	Integer	≥1	`1`	是	每次游走的深度，即访问的节点数量
`walk_num`	Integer	≥1	`1`	是	从每个指定节点开始的游走次数
`k`	Integer	[1, 10]	/	否	构建的多层加权图中的层数，层数不能超过原始图的直径
`stay_probability`	Float	(0,1]	/	否	留在当前层游走的概率
`window_size`	Integer	≥1	/	否	上下文最大长度
`dimension`	Integer	≥2	/	否	嵌入向量的维度
`loop_num`	Integer	≥1	/	否	训练迭代轮数
`learning_rate`	Float	(0,1)	/	否	模型训练的初始学习率，在每轮训练迭代后逐渐减少，直至达到`min_learning_rate`
`min_learning_rate`	Float	(0,`learning_rate`)	/	否	学习率的最低阈值，在训练过程中逐渐减少
`neg_num`	Integer	≥0	/	否	每个正样本生成的负样本数量，建议设置在0到10之间
`resolution`	Integer	≥1	`1`	是	用于提高负采样效率的参数；数值越高，越能更好地接近原始噪声分布；建议设置为10、100等
`sub_sample_alpha`	Float	/	`0.001`	是	影响高频节点下采样概率的因子；数值越高，采样概率越大；设置为≤0时，不应用二次采样
`min_frequency`	Integer	/	/	否	训练“语料库”中出现次数低于该阈值的点将从“词汇表”中排除，并在嵌入训练中被忽略；设置为≤0时，保留所有点
`return_id_uuid`	String	`uuid`, `id`, `both`	`uuid`	是	在结果中使用`_uuid`、`_id`或同时使用两者来表示点
`limit`	Integer	≥-1	`-1`	是	限制返回的结果数；`-1`返回所有结果

文件回写

CALL algo.struc2vec.write("hdc_struc2vec", {
  params: {
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 5,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  },
  return_params: {
    file: {
      filename: "embeddings"
    }
  }
})

algo(struc2vec).params({
  project: "hdc_struc2vec",
  return_id_uuid: "id",
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 5,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  file:{
    filename: 'embeddings'
  }
})

数据库回写

将结果中的embedding_result值写入指定点属性。该属性类型为float[]。

CALL algo.struc2vec.write("hdc_struc2vec", {
  params: {
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 4,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  },
  return_params: {
    db: {
      property: "vector"
    }
  }
})

algo(struc2vec).params({
  project: "hdc_struc2vec",
  return_id_uuid: "id",
  walk_length: 10,
  walk_num: 20,
  k: 10,
  stay_probability: 0.4,
  window_size: 5,
  dimension: 4,
  loop_number: 10,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 9,
  resolution: 100,
  sub_sample_alpha: 0.001,
  min_frequency: 3
}).write({
  db: {
      property: "vector"
    }
})

完整返回

CALL algo.struc2vec("hdc_struc2vec", {
  params: {
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 4,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  },
  return_params: {}
}) YIELD embeddings
RETURN embeddings

exec{
  algo(struc2vec).params({
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 4,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  }) as embeddings
  return embeddings
} on hdc_struc2vec

流式返回

CALL algo.struc2vec("hdc_struc2vec", {
  params: {
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 5,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  },
  return_params: {
    stream: {}
  }
}) YIELD embeddings
RETURN embeddings

exec{
  algo(struc2vec).params({
    return_id_uuid: "id",
    walk_length: 10,
    walk_num: 20,
    k: 10,
    stay_probability: 0.4,
    window_size: 5,
    dimension: 5,
    loop_number: 10,
    learning_rate: 0.01,
    min_learning_rate: 0.0001,
    neg_number: 9,
    resolution: 100,
    sub_sample_alpha: 0.001,
    min_frequency: 3
  }) as embeddings
  return embeddings
} on hdc_struc2vec

ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息