快速随机投影

简介

快速随机投影（简称 FastRP）是随机投影算法系列中的一种节点嵌入算法。这些算法在理论上得到了 Johnsson-Lindenstrauss 引理的支持，根据该引理，可以将 n 个任意维度的向量投影到 O(log(n)) 维度中，并且仍然近似地保留点之间的成对距离。实际上，以随机方式选择的线性投影满足此属性。

因此，此类技术可以在保留大部分距离信息的同时，进行激进的降维。FastRP 算法作用于图，在这种情况下，我们关注的是保留节点与其邻居之间的相似性。这意味着具有相似邻域的两个节点应被分配相似的嵌入向量。反之，不相似的两个节点不应被分配相似的嵌入向量。

用于 Snowflake 的 Neo4j 图形分析中 FastRP 的实现以多种方式扩展了原始算法^[1]：

它允许使用节点属性来影响初始随机向量的创建。
它引入了 nodeSelfInfluence 参数。
它支持有向图。
它支持加权图。

FastRP 算法最初使用一种称为 非常稀疏的随机投影 的技术^[2]，为所有节点分配随机向量。从随机向量（节点投影）开始，并迭代地对节点邻域进行平均，算法为每个节点 n 构造了一系列 中间嵌入 e n 的 i 次方。更准确地说，

e n to the ith equals average of e m to the ith minus one

其中 m 遍历 n 的邻居，而 e n 的 0 次方是节点的初始随机向量。

节点 n 的嵌入 e n 是算法的输出，它是上述向量和嵌入的组合

e n equals w zero times normalise r n plus sum from i equals 1 to k of w i times normalise e n to the ith

其中 normalize 是将向量除以其 L2 范数的函数，nodeSelfInfluence 的值是 w 0 ，而 iterationWeights 的值是 w 1 逗号 w 2 逗号点点点 w k 。我们稍后将回到节点自影响。

因此，每个节点的嵌入都依赖于半径等于迭代次数的邻域。通过这种方式，FastRP 利用了图中更高阶的关系，同时仍然具有高度的可伸缩性。

节点属性

大多数真实世界的图包含节点属性，这些属性存储有关节点及其所代表的信息。用于 Snowflake 的 Neo4j 图形分析中的 FastRP 算法扩展了原始 FastRP 算法，使其能够考虑节点属性。因此，生成的嵌入可以更准确地表示图。

算法的节点属性感知方面通过参数 featureProperties 和 propertyRatio 进行配置。featureProperties 中的每个节点属性都与一个维度为 propertyDimension 的随机生成向量相关联，其中 propertyDimension = embeddingDimension * propertyRatio。然后，每个节点都用一个大小为 embeddingDimension 的向量初始化，该向量由两部分连接而成

第一部分按照标准 FastRP 算法形成，
第二部分是属性向量的线性组合，使用节点的属性值作为权重。

然后算法按照与 FastRP 算法相同的逻辑进行。因此，算法将输出大小为 embeddingDimension 的数组。嵌入中最后的 propertyDimension 坐标捕获有关附近节点属性值的信息（下面的“属性部分”），其余坐标（embeddingDimension - propertyDimension 个；“拓扑部分”）捕获有关附近节点存在的信息。

[0, 1, ...        | ...,   N - 1, N]
 ^^^^^^^^^^^^^^^^ | ^^^^^^^^^^^^^^^
  topology part   |  property part
                  ^
           property ratio

调优算法参数

为了使用 FastRP 改进图中某一图的嵌入质量，可以调优算法参数。为您的特定用例和图找到最佳参数的过程通常称为超参数调优。我们将逐一介绍每个配置参数并解释其行为。

为了获得统计学上可靠的结果，最好预留一个测试集，该测试集不参与参数调优。在选择一组参数值后，可以使用下游机器学习任务在测试集上评估嵌入质量。通过改变参数值并研究机器学习任务的精度，可以推断出最适合具体数据集和用例的参数值。为了构建这样的集合，您可能需要在图中使用专门的节点标签来表示不包含测试数据的子图。

嵌入维度

嵌入维度是生成向量的长度。更大的维度提供更高的精度，但操作成本更高。

最佳嵌入维度取决于图中的节点数量。由于嵌入可以编码的信息量受其维度限制，因此较大的图往往需要更大的嵌入维度。典型值是 128 - 1024 范围内的 2 的幂。至少 256 的值在 10⁵ 数量级的图上能产生良好的结果，但通常增加维度会改善结果。然而，增加嵌入维度会线性增加内存需求和运行时。

归一化强度

归一化强度用于控制节点度数如何影响嵌入。使用负值会降低高阶邻居的重要性，而正值则会增加其重要性。最佳归一化强度取决于图以及嵌入将用于的任务。在原始论文中，超参数调优是在 [-1,0] 范围内进行的（没有正值），但我们发现有些情况下正归一化强度会产生更好的结果。

迭代权重

迭代权重参数控制两个方面：迭代次数以及它们对最终节点嵌入的相对影响。该参数是一个数字列表，每个数字表示一次迭代，其中该数字是应用于该次迭代的权重。

在每次迭代中，算法将扩展图中所有关系。这有一些含义：

单次迭代时，每个节点嵌入只考虑直接邻居。
两次迭代时，每个节点嵌入将考虑直接邻居和二度邻居。
三次迭代时，每个节点嵌入将考虑直接邻居、二度邻居和三度邻居。直接邻居可能会在不同迭代中被访问两次。
通常，对应于第 i 次迭代的嵌入包含的特征取决于可通过长度为 i 的路径到达的节点。如果图是无向的，那么可以通过长度为 L 的路径到达的节点也可以通过长度为 L+2k 的路径到达，其中 k 是任意整数。
特别地，一个节点可能在每次偶数迭代中（取决于图中的方向）回溯到自身。

最好在偶数和奇数位置上至少有一个非零权重。通常建议使用至少几次迭代，例如三次。然而，过高的值会考虑距离较远的节点，可能无法提供信息，甚至有害。这里的直觉是，随着投影远离节点，邻域的特异性会降低。当然，更多的迭代次数也会花费更多的时间来完成。

节点自影响

节点自影响是原始 FastRP 算法的一个变体。

节点嵌入受第 i 次迭代中间嵌入影响的程度由 iterationWeights 的第 i 个元素控制。这也可以看作是从节点经过 i 跳可到达的节点的初始随机向量或投影对节点嵌入的影响程度。类似地，nodeSelfInfluence 的行为就像第 0 次迭代的迭代权重，或者节点投影对同一节点嵌入的影响量。

将此参数设置为非零值的原因是，如果您的图连接性较低或包含大量孤立节点。孤立节点与使用 propertyRatio = 0.0 结合会导致嵌入包含全零。然而，使用节点属性以及节点自影响可以为这些节点生成更有意义的嵌入。这可以看作是在图结构（局部）缺失时生成回退特征。此外，有时节点自身的属性只是信息丰富的特征，即使连接性很高，也值得包含。最后，节点自影响可以用于纯降维，以压缩用于节点分类的节点属性。

如果不使用节点属性，使用 nodeSelfInfluence 也可能产生积极影响，具体取决于其他设置和问题。

方向

在创建图时选择正确的方向可能会产生最大的影响。FastRP 算法旨在处理无向图，我们预计在大多数情况下这是最佳选择。如果您期望只有出站或入站关系对预测任务有信息量，那么您可能希望尝试分别使用 NATURAL 或 REVERSE 方向。

加权图

默认情况下，算法将图关系视为无权重。您可以使用 relationshipWeightProperty 参数指定关系权重，以指示算法计算相邻嵌入的加权平均值。

语法

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

运行 FastRP。

CALL Neo4j_Graph_Analytics.graph.fast_rp(
  'CPU_X64_XS',                    (1)
  {
    ['defaultTablePrefix': '...',] (2)
    'project': {...},              (3)
    'compute': {...},              (4)
    'write':   {...}               (5)
  }
);

1	计算池选择器。
2	表引用的可选前缀。
3	项目配置。
4	计算配置。
5	写入配置。

表 1. 参数
名称	类型	默认值	可选	描述
computePoolSelector	字符串	`不适用`	否	用于运行 FastRP 作业的计算池选择器。
configuration	映射	`{}`	否	图项目、算法计算和结果写回的配置。

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

有关下面的项目配置的更多详细信息，请参阅项目文档。

表 2. 项目配置
名称	类型
nodeTables	节点表列表。
relationshipTables	关系类型到关系表的映射。

表 3. 计算配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`'fast_rp'`	是	将写回 Snowflake 数据库的节点属性。
propertyRatio	浮点数	`0.0`	是	属性嵌入维度与总 `embeddingDimension` 的所需比率。正值要求 `featureProperties` 非空。
featureProperties	字符串列表	`[]`	是	应用作输入特征的节点属性名称。所有属性名称必须存在于投影图中，并且类型为浮点数或浮点数列表。
embeddingDimension	整数	`不适用`	否	计算出的节点嵌入的维度。最小值为 1。
iterationWeights	浮点数列表	`[0.0, 1.0, 1.0]`	是	包含每次迭代的权重。该权重控制该次迭代的中间嵌入对最终嵌入的贡献程度。
nodeSelfInfluence	浮点数	`0.0`	是	控制每个节点的初始随机向量对其最终嵌入的贡献程度。
normalizationStrength	浮点数	`0.0`	是	每个节点的初始随机向量根据其度数的 `normalizationStrength` 次幂进行缩放。
randomSeed	整数	`不适用`	是	用于计算嵌入中所有随机性的随机种子。
relationshipWeightProperty	字符串	`null`	是	用于加权随机投影的关系属性名称。如果未指定，算法将运行无权重。
迭代次数等于 `iterationWeights` 的长度。
要求 `iterationWeights` 非空或 `nodeSelfInfluence` 非零。

有关下面的写入配置的更多详细信息，请参阅写入文档。

表 4. 写入配置
名称	类型	默认值	可选	描述
nodeLabel	字符串	`不适用`	否	内存图中要写入节点属性的节点标签。
nodeProperty	字符串	`'fast_rp'`	是	将写回 Snowflake 数据库的节点属性。
outputTable	字符串	`不适用`	否	Snowflake 数据库中写入节点属性的表。

示例

在本节中，我们将展示在具体图上运行 FastRP 节点嵌入算法的示例。目的是说明结果如何以及提供如何在实际环境中利用该算法的指南。我们将在一个由少数节点以特定模式连接的小型社交网络图上进行此操作。示例图如下所示：

以下 SQL 语句将在 Snowflake 数据库中创建示例图表

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.PERSONS (NODEID STRING, AGE INT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS VALUES
  ('Dan',   18),
  ('Annie', 12),
  ('Matt',  22),
  ('Jeff',  51),
  ('Brie',  45),
  ('Elsa',  65),
  ('John',  64);

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.KNOWS (SOURCENODEID STRING, TARGETNODEID STRING, WEIGHT FLOAT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.KNOWS VALUES
  ('Dan',   'Annie', 1.0),
  ('Dan',   'Matt',  1.0),
  ('Annie', 'Matt',  1.0),
  ('Annie', 'Jeff',  1.0),
  ('Annie', 'Brie',  1.0),
  ('Matt',  'Brie',  3.5),
  ('Brie',  'Elsa',  1.0),
  ('Brie',  'Jeff',  2.0),
  ('John',  'Jeff',  1.0);

该图表示七个相互认识的人。关系属性 weight 表示两人之间知识的强度。

运行作业

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

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

以下将运行一个 FastRP 作业

CALL Neo4j_Graph_Analytics.graph.fast_rp('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'PERSONS' ],
        'relationshipTables': {
            'LINKS': {
                'sourceTable': 'PERSONS',
                'targetTable': 'PERSONS',
            }
        }
    },
    'compute': {
        'mutateProperty': 'embedding',
        'embeddingDimension': 4
    },
    'write': [{
        'nodeLabel': 'PERSONS',
        'outputTable': 'PERSONS_EMBEDDING',
        'nodeProperty': 'embedding'
    }]
});

表 5. 结果
作业 ID	作业开始时间	作业结束时间	作业结果
job_6f57b3e10a604422850630117caf0de7	2025-04-30 11:57:12.598000	2025-04-30 11:57:21.348000	{ "fast_rp_1": { "computeMillis": 32, "configuration": { "concurrency": 2, "embeddingDimension": 4, "featureProperties": [], "iterationWeights": [ 0, 1, 1 ], "jobId": "249f0d00-f957-426b-b15f-7b67dc898784", "logProgress": true, "mutateProperty": "fast_rp", "nodeLabels": [ "" ], "nodeSelfInfluence": 0, "normalizationStrength": 0, "propertyRatio": 0, "relationshipTypes": [ "" ], "sudo": false }, "mutateMillis": 2, "nodeCount": 7, "nodePropertiesWritten": 7, "preProcessingMillis": 14 }, "project_1": { "graphName": "snowgraph", "nodeCount": 7, "nodeMillis": 189, "relationshipCount": 9, "relationshipMillis": 326, "totalMillis": 515 }, "write_node_property_1": { "exportMillis": 2004, "nodeLabel": "FASTRP_PERSONS", "nodeProperty": "fast_rp", "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_EMBEDDING", "propertiesExported": 7 } }

表 5. 结果

作业 ID

作业开始时间

作业结束时间

作业结果

job_6f57b3e10a604422850630117caf0de7

2025-04-30 11:57:12.598000

2025-04-30 11:57:21.348000

 {
  "fast_rp_1": {
    "computeMillis": 32,
    "configuration": {
      "concurrency": 2,
      "embeddingDimension": 4,
      "featureProperties": [],
      "iterationWeights": [
        0,
        1,
        1
      ],
      "jobId": "249f0d00-f957-426b-b15f-7b67dc898784",
      "logProgress": true,
      "mutateProperty": "fast_rp",
      "nodeLabels": [
        "*"
      ],
      "nodeSelfInfluence": 0,
      "normalizationStrength": 0,
      "propertyRatio": 0,
      "relationshipTypes": [
        "*"
      ],
      "sudo": false
    },
    "mutateMillis": 2,
    "nodeCount": 7,
    "nodePropertiesWritten": 7,
    "preProcessingMillis": 14
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 7,
    "nodeMillis": 189,
    "relationshipCount": 9,
    "relationshipMillis": 326,
    "totalMillis": 515
  },
  "write_node_property_1": {
    "exportMillis": 2004,
    "nodeLabel": "FASTRP_PERSONS",
    "nodeProperty": "fast_rp",
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_EMBEDDING",
    "propertiesExported": 7
  }
}

返回的结果包含有关作业执行和结果分发的信息。此外，每个节点的嵌入已写回 Snowflake 数据库。我们可以这样查询：

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PERSONS_EMBEDDING;

表 6. 结果
节点 ID	FAST_RP
Annie	[1.0129523, -1.4094763, -0.64521426, 0.14176996]
Brie	[0.8979494, -1.0018919, -0.8030941, -0.14222366]
Dan	[1.1513789, -0.89023, -0.21288107, -0.06492126]
Elsa	[0.71804917, -0.9413747, -0.90776074, -0.060044557]
Jeff	[1.0402749, -1.3812861, -0.9326958, -0.08068423]
John	[0.9855986, -1.393847, -0.9855986, 0]
Matt	[0.9290148, -1.3734311, -0.550267, 0.10201697]

算法的结果不那么直观可解释，因为节点嵌入格式是节点在其邻域内的数学抽象，专为机器学习程序设计。我们可以看到，嵌入有四个元素（如使用 embeddingDimension 配置的），并且这些数字相对较小（它们都落在 [-2, 2] 范围内）。这些数字的大小由 embeddingDimension、图中节点的数量以及 FastRP 对中间嵌入向量执行欧几里德归一化这一事实控制。

由于算法的随机性，结果在不同运行之间会有所不同。然而，这并不一定意味着两个节点嵌入的成对距离会变化很多。

1. Chen, Haochen, Syed Fahad Sultan, Yingtao Tian, Muhao Chen, and Steven Skiena. "Fast and Accurate Network Embeddings via Very Sparse Random Projection." arXiv preprint arXiv:1908.11512 (2019)。

2. Achlioptas, Dimitris. "Database-friendly random projections: Johnson-Lindenstrauss with binary coins." Journal of computer and System Sciences 66, no. 4 (2003): 671-687。