修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
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

      ✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

      概述

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

      尽管 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*。Rk(u) 表示图中距离节点 u 恰好 k ∈ [0, k*] 跳的节点集合,s(S) 表示节点集合 S ⊂ V 的有序度数序列。以下是一个示例:

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

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

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

      2. 构建多层加权图

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

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

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

      层之间通过有向边相连。每个节点与它在上一层和下一层(如果有的话)的对应节点相连,层之间的边权重如下:

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

      3. 为节点生成上下文

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

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

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

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

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

      4.模型训练

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

      特殊说明

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

      语法

      • 命令:algo(struc2vec)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      ids / uuids []_id / []_uuid / / 指定游走的起点的 ID/UUID;忽略表示指定全部点
      walk_length int ≧1 1 每次游走的深度,即访问的节点数量
      walk_num int ≧1 1 从每个指定节点开始的游走次数
      k int [1,10] / 构造的带权多层图的层数,不能超过图的直径
      stay_probability float (0,1] / 留在当前层游走的概率
      window_size int ≥1 / 上下文的最大长度
      dimension int ≥1 / 嵌入向量的维度
      loop_num int ≥1 / 训练迭代轮数
      learning_rate float (0,1) / 模型训练的初始学习率,学习率会在每次训练迭代后逐渐减小,直至达到 min_learning_rate
      min_learning_rate float (0,learning_rate) / 在训练过程中逐渐减小的学习率的最小阈值
      neg_num int ≥0 / 为每个正样本产生的负样本数量,建议设置在 0 到 10 之间
      resolution int ≥1 1 用于提高负采样效率的参数;较高的值能提供更接近原始噪声分布的近似分布;建议设置为 10、100 等
      sub_sample_alpha float / 0.001 影响高频节点下采样概率的因素;较高的值会增加这种概率;设置 ≤0 的值表示不应用二次采样
      min_frequency int / / 在训练“语料库”中出现次数低于此阈值的节点将被排除在“词汇表”之外,并在嵌入训练中被忽略;设置 ≤0 的值表示保留所有节点
      limit int ≥-1 -1 返回的结果条数,-1 返回所有结果

      示例

      文件回写

      配置项 回写内容
      filename _id,embedding_result
      algo(struc2vec).params({
        walk_length: 10,
        walk_num: 20,
        k: 10,
        stay_probability: 0.4,
        window_size: 5,
        dimension: 20,
        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'
      }})
      

      属性回写

      配置项 回写内容 回写至 数据类型
      property embedding_result 点属性 string
      algo(struc2vec).params({
        walk_length: 10,
        walk_num: 20,
        k: 10,
        stay_probability: 0.4,
        window_size: 5,
        dimension: 20,
        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'
      }})
      

      直接返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其嵌入结果 _uuid, embedding_result
      algo(struc2vec).params({
        walk_length: 10,
        walk_num: 20,
        k: 10,
        stay_probability: 0.4,
        window_size: 5,
        dimension: 20,
        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
      

      流式返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其嵌入结果 _uuid, embedding_result
      algo(struc2vec).params({
        walk_length: 10,
        walk_num: 20,
        k: 10,
        stay_probability: 0.4,
        window_size: 5,
        dimension: 20,
        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
      }).stream() as embeddings
      return embeddings
      
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写