FastPath

电梯演讲

FastPath 是一种轻量级的路径嵌入算法，用于处理时态图。它为与事件序列相关的基节点计算嵌入。事件与向量相关联，这取决于事件类型和（连续地）自事件发生以来经过的时间。这些向量被聚合成嵌入，可用于机器学习任务，如客户旅程分析，并可泛化到不同的时间段。

图论术语简要说明

FastPath 算法在概念上作用于图，因此本文档中提到图、节点、关系和属性。此外，这些图是异构的，因此节点标有节点标签，关系有类型。图与实际 Snowflake 表之间的对应关系在 [_node_tables] 和 [_relationship_tables] 部分中描述。

简介

FastPath 是一种路径嵌入算法。这意味着输入图是一个时态图，由以下部分组成：

  • 基节点 — 算法旨在为其计算嵌入的兴趣节点

  • 事件节点 — 标有时间戳并与基节点关联的节点

有两种支持的图模式用于编码事件链。

事件节点可以保存关于事件内容的信息。这些信息可以是特征向量、分类属性或与上下文节点的关系的形式。

总之，输入由一系列基节点组成，每个基节点都有一系列承载信息的事件时间序列。

对于每个基节点，都会指定一个输出时间。输出时间决定了嵌入的两个方面。首先，只有在输出时间之前的事件才用于计算嵌入。其次，算法使用经过时间而非绝对时间来计算嵌入。在确定事件对基节点嵌入的贡献时，经过时间是事件与基节点输出时间之间的时间量。

让我们举一个例子来更清楚地说明这一点：其中一个基节点是一个名为“Joe”的人，其中一个事件表示“Joe”服用了一剂阿司匹林。算法将存储

  • 事件类型——此处为“服用阿司匹林”

  • 经过时间——此处为 7 天

此外，每对事件类型和经过时间都与一个“半随机”向量相关联。这些向量的构建既使用了随机性（类似于所谓的 FastRP 算法），也使用了时间平滑机制。这使得“7 天前服用阿司匹林”的向量与“8 天前服用阿司匹林”的向量（相对）相似。

Joe 的嵌入将是“7 天前服用阿司匹林”向量和 Joe 发生的其他所有事件向量的加权和。加权如何工作将在下面详细描述。

上述内容似乎只提供了离散事件信息（如分类属性和与上下文节点的关系）的直观概念。然而，事件上的特征向量可以被视为对应于向量分量的离散事件的加权和。

输出节点嵌入例如可用于下游机器学习任务，以解决与客户旅程等相关的问题。由于依赖相对时间而非绝对时间，此类模型可以将过去图的嵌入泛化到当前图。此外，FastPATH 在时间上是等变的；如果基节点的所有事件都偏移 T 个时间步，并且输出时间也偏移 T 个时间步（方向相同），则基节点的嵌入保持不变。

语法

本节介绍执行 FastPath 算法所使用的语法。

运行 FastPath。
CALL graph.fastpath(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);
1 计算池选择器。
2 表引用的可选前缀。
3 项目配置。
4 计算配置。
5 写入配置。
表 1. 参数
名称 类型 默认值 可选 描述

computePoolSelector

字符串

不适用

否

用于运行 FastPath 作业的计算池选择器。

configuration

映射

{}

否

图项目、算法计算和结果写回的配置。

配置映射包含以下三个条目。

有关以下项目配置的更多详细信息，请参阅项目文档。
表 2. 项目配置
名称 类型

nodeTables

节点表列表。

relationshipTables

关系类型到关系表的映射。
表 3. 计算配置
名称 类型 默认值 可选 描述

baseNodeLabel

字符串

不适用

否

需要输出嵌入的节点标签

eventNodeLabel

字符串

不适用

否

与基节点相关的事件的节点标签

contextNodeLabel

字符串

无

是

描述事件的上下文节点的节点标签

timeNodeProperty

字符串

无

是

表示事件节点上时间的节点属性名称。可以是整型或浮点型。

nextRelationshipType

字符串

无

是

事件节点之间表示事件顺序的关系类型名称

firstRelationshipType

字符串

无

是

从基节点到事件节点的关系类型名称，指示每个基节点的第一个事件

eventFeatures

字符串

无

是

事件节点上持有向量形式数值特征的节点属性名称

categoricalEventProperties

字符串列表

无

是

事件节点上持有分类值或分类值列表的节点属性名称

ignoredEventCategory

整型

-1

是

一个分类值，表示分类缺失，并在构建事件嵌入时被忽略

outputTime

浮点型

无

是

应该生成嵌入的时间戳。在此时间戳或之后发生的事件将不被处理。

outputTimeProperty

字符串

无

是

基节点上持有数字的节点属性名称，该数字指示应该为哪个时间戳生成输出嵌入

numElapsedTimes

整型

不适用

否

“网格”中的时间点数量。从事件到输出的经过时间将四舍五入到此网格。如果设置为 1，事件的时间戳将无效。

decayFactor

浮点型

1.0

是

控制旧事件影响力衰减速度的系数

maxElapsedTime

整型

不适用

否

事件相对于输出时间的最大年龄，超出此年龄的事件不被考虑用于嵌入。

smoothingWindow

整型

0

是

事件嵌入在包含最多 2*smoothingWindow + 1 个网格时间点的窗口上聚合。

smoothingRate

浮点型

0.0

是

控制事件的预期相似性随着时间距离的增加而衰减的速度。

dimension

整型

不适用

否

嵌入的输出维度

randomSeed

整型

随机数

是

用于计算嵌入中所有随机性的随机种子。
有关以下写入配置的更多详细信息，请参阅写入文档。
表 4. 写入配置
名称 类型 默认值 可选 描述

nodeLabel

字符串

不适用

否

内存图中的节点标签，从中写入节点属性。

outputTable

字符串

不适用

否

Snowflake 数据库中用于写入节点属性的表。

配置概念解释

本节将更详细地介绍如何配置算法的某些方面。

图模式和关系配置

该算法支持两种不同的模式来连接基节点和事件节点。

  1. 要使用第一种模式配置，您需要提供 firstRelationshipType 和 nextRelationshipType，timeNodeProperty 是可选的。在此配置下，每个基节点和事件节点都被假定为以下模式路径的一部分：(:baseNodeLabel)-[:firstRelationshipType]-(:eventNodeLabel)-[:nextRelationshipType]-…​-[:nextRelationshipType]→(:eventNodeLabel) image4

  2. 要使用第二种模式配置，您只需提供一个 timeNodeProperty。此时假定每个基节点都与其每个事件节点具有出站关系：(:baseNodeLabel)-[:]→(:eventNodeLabel)

image5

（可选）模式还可以包含一个名为 contextNodeLabel 的节点标签，详见下面的事件输入特征。

定义事件时间戳

有两种方法可以为事件节点指定时间戳。第一种方法是提供一个 timeNodeProperty，在这种情况下，每个事件节点必须拥有一个以该名称命名的属性来表示时间戳。

但是，如果提供了 nextRelationshipType，则无需提供 timeNodeProperty。在这种情况下，时间戳将以如下图所示的直观方式生成。

Timestamp generation

图“时间戳生成”：nextRelationshipType 路径到事件的长度将定义其时间戳。因此，基节点事件链中的第一个事件节点（通过 firstRelationshipType 关系从基节点连接）将具有时间戳 0。下一个事件节点（通过 nextRelationshipType 关系从第一个事件节点访问）将具有时间戳 1，依此类推。

请注意，即使使用了 nextRelationshipType，您仍然可以提供 timeNodeProperty。在这种情况下，nextRelationshipType 将不用于推断时间戳，而是用于确定事件节点属于哪个基节点。

事件输入特征

事件的特征表示会受到三种不同输入源的影响。它们彼此独立，可以同时使用，也可以分开使用。事件特征向量将是所有已启用输入源的总和。

  1. 要启用上下文节点输入源，您需要提供 contextNodeLabel。在这种情况下，假定事件节点可能存在指向上下文节点的出站关系，即模式
    (:eventNodeLabel)-[:]→(:contextNodeLabel)

  2. 要启用事件特征向量属性输入源，您需要提供 eventFeatures。这应该是所有事件节点上存在的向量属性的名称。

  3. 要启用分类事件属性输入源，您需要提供 categoricalEventProperties。这应该是一个属性的名称，该属性包含表示类别的整数或此类整数的列表。该属性必须存在于所有事件节点上。

时间平滑

如果 smoothingRate 较大，实际上只会应用少量平滑，即使时间间隔很短（足以最接近不同的网格点）的事件通常也会具有非常不同的嵌入。

如果 smoothingWindow 为 0，则效果类似于具有大的 smoothingRate。另一方面，如果 smoothingWindow 相对于 numElapsedTimes 较大，并且同时 smoothingRate 较小，则即使时间戳差异很大，相同事件也将具有相似的嵌入。

输出

输出是一个包含两列的 Snowflake 表；

  • nodeid — 根据输入节点表的节点 ID

  • embedding — 节点的 FastPath 嵌入

表的名称和位置在写入配置中给出。

示例

我们假设有一个 Snowflake 模式 patient_db.general，包含以下表：

  • patient 表，包含列 nodeid 和 output_time

  • encounter 表，包含列 nodeid、embedding 和 time

  • has_encounter 表，包含列 sourcenodeid 和 targetnodeid

这些表代表了医疗患者记录的图。

要运行查询，需要为应用程序、您的消费者角色和您的环境设置授权。有关更多信息，请参阅入门页面。

我们还假设应用程序名称是默认的 Neo4j_Graph_Analytics。如果您在安装过程中选择了不同的应用程序名称，请将其替换。

FastPATH 算法可以通过执行以下语句在此图上运行：

CALL Neo4j_Graph_Analytics.graph.fastpath('CPU_X64_M', {
    'defaultTablePrefix': 'patient_db.general',
    'project': {
        'nodeTables': ['patient', 'encounter'],
        'relationshipTables': {
            'has_encounter': {
                'sourceTable': 'patient',
                'targetTable': 'encounter'
            }
        }
    },
    'compute': {
        'baseNodeLabel': 'patient',
        'eventNodeLabel': 'encounter',
        'eventFeatures': 'embedding',
        'outputTimeProperty': 'output_time',
        'timeNodeProperty': 'time',
        'dimension': 32, -- in reality, a higher value is recommended
        'numElapsedTimes': 30,
        'maxElapsedTime': 3650,
        'smoothingRate': 0.9,
        'smoothingWindow': 2,
        'decayFactor': 0.0
    },
    'write': [{
        'nodeLabel': 'patient',
        'outputTable': 'embeddings'
    }]
});

输出示例如下

作业 ID 作业开始时间 作业结束时间 作业结果

job_7bed5ef80dc24eec9b0d86d0cbe7baa4

2025-04-28 14:12:46.439

2025-04-28 14:12:57.447

{"node_output_stats": {"patient1": {"row_count": 1000, "table_name": "patient_db.general.embeddings"}}}

生成的节点嵌入可以像这样简单地探索：

SELECT * FROM patient_db.general.embeddings LIMIT 10;

它返回以下形式的数据

NODEID	EMBEDDING
0	    [5.341047,3.848688,-5.973229,-6.814521,4.745209,9.643475,-0.045684,4.210951,-2.004807,4.428759,13.497086,-6.179376,-0.986118,-7.707472,-0.555529,-6.073474,4.083053,1.602635,1.958997,12.649292,-0.603967,10.158164,-0.338394,-0.608493,-4.837356,15.097547,-6.569559,-2.797304,0.338724,6.874722,9.505033,-8.754766]
1	    [-6.724641,-11.390027,-4.453455,4.120544,-2.017518,-2.675358,2.027915,-7.672874,-2.879899,17.374033,11.240053,7.185143,10.593451,-0.032012,6.947659,-29.623604,0.166914,11.507900,-12.466205,-1.891875,-8.164936,7.390674,-10.806652,2.019349,-1.903723,29.574389,1.859032,3.853385,0.566263,-5.038345,4.792415,3.326340]
2	    [-2.920011,-2.048257,-5.708614,-2.373963,-0.244315,2.887959,-23.091557,-0.587305,4.643905,-0.775859,7.227013,-1.861291,-4.952862,-7.039846,-11.932112,-8.986797,-1.304907,2.019032,3.064439,-4.360886,-2.295964,6.218091,0.975781,-3.919339,8.686658,17.961964,-7.780995,-1.146844,-6.269790,20.006420,-1.216949,-3.596368]
3	    [-8.567083,-9.307947,-11.381653,-0.802077,-1.286643,-3.037168,5.494521,-1.814128,-1.623972,-0.085408,-8.678900,6.716533,-3.552778,10.777124,8.609731,2.346340,-6.656413,4.587024,-6.891663,0.081429,-3.976248,-3.998426,-0.445967,4.443917,-7.440049,15.908058,-6.126621,-9.205961,-3.693087,5.798036,-10.521414,25.272419]
4	    [-3.993221,-15.716671,-7.102195,-22.005224,-0.855417,9.282584,-2.253866,-16.234423,24.112732,2.810601,-13.975744,-12.062764,-2.387400,20.061924,-1.067919,12.701017,-4.327281,-17.721920,23.729225,-9.824536,-8.265147,-2.768445,-25.310749,8.047261,13.448681,51.172272,-15.435410,14.756327,-4.342721,11.190716,28.090958,9.425692]
5	    [-13.833055,-3.474358,-29.580704,15.354573,46.242706,13.694808,32.601025,26.757681,-7.090479,57.280357,-0.735581,38.106731,26.968494,3.217232,-23.623219,2.485056,-6.973878,0.877117,-15.995618,55.822735,18.801920,52.809269,-47.148773,39.193768,-4.173650,-12.601570,-14.213085,-21.923597,12.738949,-27.862555,-9.950893,-20.819094]
6	    [13.704840,13.533702,-5.135115,-6.226133,-5.701371,-2.703825,5.956636,3.647114,2.735878,2.559484,-15.129639,9.952298,2.568221,1.664974,-0.048340,-10.921870,-17.725523,1.495797,-9.043520,25.950590,-0.110576,9.694299,-18.446062,-6.852248,6.842557,35.075626,8.634172,7.099162,-5.890983,9.706918,-8.494190,6.583567]
7	    [-2.812654,2.941338,1.067755,-4.293394,-3.086962,-0.469450,3.613479,-2.819084,5.120227,7.050265,-2.466012,-2.169495,0.909174,2.145000,3.638202,-2.498263,-5.502569,-3.852499,5.146134,1.659534,-0.714558,-0.469029,2.176041,-1.869031,-4.940216,3.088835,3.752839,3.714232,-2.807177,-0.698254,-5.012471,2.528090]
8	    [-7.303960,-7.729638,-4.773112,-9.641366,2.609788,-20.279972,6.826665,8.960463,19.718428,3.388449,7.409564,-17.707247,-0.936261,28.070925,-3.749211,-9.148918,16.058552,4.065396,10.297297,9.403608,-10.898782,-10.801480,-25.112486,3.316337,17.157797,12.428331,19.813198,10.889541,-1.723780,-1.651543,-0.261916,9.012156]
9	    [-6.429783,-20.400585,16.191334,-16.042753,9.880158,-5.386495,-10.220762,15.675117,9.438731,-3.742106,10.518373,3.956760,6.789544,-0.625264,-8.893956,1.050145,-15.966327,-6.890019,-2.499497,8.597721,3.010286,3.782031,-10.274326,20.255251,1.046289,17.648533,-6.685064,13.613426,7.041289,13.350776,-3.143279,-5.788550]

附录

以下部分为对算法内部工作原理感兴趣的人提供了有关 FastPath 的更详细信息。

算法工作原理

下面将算法分解为各个步骤是概念性的。它不反映实际的实现细节，例如循环顺序、数据结构等。我们将描述如何为具有输出时间 to 的基节点 b 计算 FastPATH 嵌入。输出时间是根据所选的参数 outputTime 或 outputTimeProperty 计算的。属于 b 的任意事件将表示为 e，其时间戳假定为 te。在时间 to（我们希望计算 b 的嵌入的时间）时，e 的经过时间是
tel = to - te，即事件时间戳与相应基节点输出时间之间的时间量。

请注意，事件可能属于具有不同输出时间的多个基节点。这意味着涉及事件的一些计算必须为其每个关联的基节点重新计算，但幸运的是这些计算彼此独立。

  1. 预处理
    将输入预处理为包含基节点、事件节点和可选上下文节点的图。基节点和事件节点相互连接，事件和上下文节点也相互连接。如果未给出事件的时间戳，则通过遍历每个基节点的事件链来生成时间戳。

  2. 过滤相关事件
    在属于基节点 b 的事件中，任何经过时间超过 maxElapsedTime 的事件，或在时间 to 或之后发生的事件都将被移除。b 的剩余相关事件将被称为 E(b)。

  3. 创建网格
    创建一个时间网格，下文简称网格

  4. 生成随机向量
    稀疏随机向量是根据下方列出的输入源独立生成的，如果它们被选中。
    对于网格中的每个时间和输入源，按如下方式生成向量：

    1. 事件特征向量属性：对于输入事件特征向量的每个维度 i，生成一个向量 ri,t Image1

    2. 上下文节点：对于每个上下文节点 c，生成 rc,t

    3. 分类事件属性：对于每个分类节点属性 prop 以及该属性的每个值 v，初始化一个随机向量 rprop,v,t。
      如果任何事件的属性值是类别列表 [v1, v2, …​]，并且 v 是这些值中的任何一个，我们则初始化一个随机向量 r~prop,v。

  5. 计算事件节点预嵌入
    事件 e 在时间 t 的预嵌入表示为 xe,t，并初始化为全零。对于下方所有适用的输入源，将步骤 3 中生成的随机向量的加权和添加到 xe,t。

    1. 事件特征向量属性:
      xe,t += ∑i ri,t * inpi
      其中 inp 是 e 的输入向量，i 遍历 inp 的维度。

    2. 上下文节点:
      xe,t += ∑c rc,t
      其中 c 遍历事件 e 的所有邻居。

    3. 分类事件属性:
      xe,t += ∑prop rprop,e.prop,t
      或者当 e.prop 是一个列表时：xe,t = ∑prop ∑v in e.prop rprop,v,t
      计算事件嵌入

  6. 我们使用 e 先前在不同时间导出的预嵌入来计算其嵌入。我们找到网格中与经过时间 tel = to - te 最接近的时间 tcl。然后，在 tcl 两侧的网格中加上最多 smoothingWindow 个点，我们得到事件相关网格时间的窗口 We。在图中，smoothingWindow = 1 且 tcl=t4。因此 We = {t3,t4,t5}。对于 We 中的每个 t，我们将网格点 t 的权重设置为：
    Image2
    w(t) = exp(-|t - tel| * smoothingRate ) / Ze
    其中 Ze 是确保 ∑t in W_e w(t) = 1 的常数。,
    我们现在可以最终将事件在输出时间 to 的嵌入设置为
    emb(e|to) = ∑t in W_e w(t) * xe,t。因此，我们通过对预嵌入网格（或者您可以称之为基向量）取平均值来构建了时间平滑的嵌入。时间平滑机制的目的是确保嵌入随着经过时间的变化而连续变化，同时所有其他因素保持不变。
    计算基节点嵌入

  7. b 的嵌入最终由下式给出
    emb(b) = ∑e in E(b) wb,e * emb(e)
    其中
    wb,e = exp(-decayFactor * (to - te)) 并且 E(b) 在步骤 2 中定义。
    下图概述了影响事件嵌入的因素以及它们如何根据输出时间和经过时间流向基节点的嵌入。

快速随机投影 GraphSAGE

image3
© . All rights reserved.