K-最近邻算法

引言

K-最近邻算法计算图中所有节点对的距离值，并在每个节点与其 k 个最近邻居之间创建新的关系。距离的计算基于节点属性。

此算法的输入是同构图；图中任何节点标签或关系类型信息都将被忽略。图不需要是连通的，事实上，节点之间已有的关系将被忽略——除非使用随机游走采样作为初始采样选项。每个节点与其 k 个最近邻居之间会创建新的关系。

K-最近邻算法比较每个节点的给定属性。这些属性最相似的 k 个节点是 K-最近邻。

初始邻居集是随机选择的，并在多次迭代中进行验证和完善。迭代次数受配置参数 maxIterations 限制。如果邻居列表只发生少量变化，算法可能会提前停止，这可以通过配置参数 deltaThreshold 控制。

具体实现基于 Wei Dong 等人的《用于通用相似性度量的 K-最近邻图高效构建》。该算法不比较每个节点与所有其他节点，而是基于节点的邻居的邻居很可能已经是最近的邻居这一假设来选择可能的邻居。该算法相对于节点计数呈准线性缩放，而不是二次方缩放。

此外，该算法在每次迭代中只比较所有可能邻居的一个样本，假设最终会看到所有可能的邻居。这可以通过配置参数 sampleRate 控制。

有效的采样率必须在 0（不含）到 1（含）之间。
默认值为 0.5。
该参数用于控制准确性和运行时性能之间的权衡。
更高的采样率将提高结果的准确性。
- 算法也需要更多的内存，并且计算时间会更长。
更低的采样率将提高运行时性能。
- 一些潜在节点在比较中可能会被遗漏，并且可能不会包含在结果中。

当遇到的邻居与已知最不相似的邻居具有相同的相似度时，随机选择保留哪个节点可以降低某些邻域未被探索的风险。此行为由配置参数 perturbationRate 控制。

算法的输出是节点与其 k-最近邻居之间的新关系。相似度分数通过关系属性表示。

有关此算法的更多信息，请参阅

相似度指标

KNN 算法中使用的相似度度量取决于配置的节点属性类型。KNN 支持标量数值和数字列表。

标量数字

当属性是标量数字时，相似度计算如下

图 1. 1 除以 1 加绝对差

这会得到一个在 (0, 1] 范围内的数字。

整数列表

当属性是整数列表时，相似度可以通过 Jaccard 相似度或重叠系数来衡量。

Jaccard 相似度: 图 2. 交集大小除以并集大小
重叠系数: 图 3. 交集大小除以最小集合大小

这两个指标都给出了 [0, 1] 范围内的分数，无需进行归一化。当未指定指标时，Jaccard 相似度用作比较整数列表的默认选项。

浮点数列表

当属性是浮点数列表时，计算两个节点之间相似度有三种方法。

默认使用的指标是余弦相似度。

余弦相似度: 图 4. 向量的点积除以它们的长度之积

请注意，上述公式给出的分数范围是 [-1, 1]。通过 score = (score + 1) / 2 将分数归一化到 [0, 1] 范围。

另外两个指标包括 Pearson 相关分数和归一化欧几里得相似度。

Pearson 相关分数: 图 5. 协方差除以标准差的乘积

如上所述，该公式给出的分数范围为 [-1, 1]，同样归一化到 [0, 1] 范围。

欧几里得相似度: 图 6. 每对元素平方差之和的平方根

此公式的结果是一个非负值，但不一定限定在 [0, 1] 范围内。为了将数字限定在此范围内并获得相似度分数，我们返回 score = 1 / (1 + distance)，即我们执行与标量值情况相同的归一化。

多重属性

最后，当指定多个属性时，两个邻居的相似度是各个属性相似度的平均值，即 [0, 1] 范围内每个数字的简单平均值，最终总分也在 [0, 1] 范围内。

这种平均值的有效性高度依赖于上下文，因此在将其应用于您的数据领域时请务必小心。

节点属性和指标配置

要使用的节点属性和指标通过 nodeProperties 配置参数指定。必须至少指定一个节点属性。

此参数接受以下任一值

表 1. nodeProperties 语法
单个属性名	`nodeProperties: 'embedding'`
属性键到指标的映射	nodeProperties: { embedding: 'COSINE', age: 'DEFAULT', lotteryNumbers: 'OVERLAP' }
字符串列表和/或映射列表	nodeProperties: [ {embedding: 'COSINE'}, 'age', {lotteryNumbers: 'OVERLAP'} ]

按类型划分的可用指标是

表 2. 按类型划分的可用指标
类型	指标
整数列表	`JACCARD`、`OVERLAP`
浮点数列表	`COSINE`、`EUCLIDEAN`、`PEARSON`

对于任何属性类型，也可以指定 DEFAULT 以使用默认指标。对于标量数字，只有默认指标。

初始邻居采样

算法首先为每个节点选择 k 个随机邻居。这种随机采样有两种选择。

均匀采样: 每个节点的前 k 个邻居从图中所有其他节点中均匀随机选择。这是进行初始采样的经典方法。它也是算法的默认设置。请注意，此方法实际上不使用输入图的拓扑结构。
随机游走: 从每个节点开始，我们进行一次深度偏置随机游走，并将在此游走中访问的前 k 个唯一节点作为我们的初始随机邻居。如果在内部定义的 O(k) 步随机游走后，仍未访问 k 个唯一邻居，我们将使用上述均匀采样方法填充剩余的邻居。随机游走方法利用了输入图的拓扑结构，如果它更有可能在拓扑上接近的节点之间找到良好的相似度分数，则可能适用。

所使用的随机游走偏向深度，这意味着它更可能选择远离其先前访问的节点，而不是返回到该节点或与其等距的节点。这种偏差的直觉是，后续的邻居的邻居比较迭代可能会覆盖每个节点的扩展（拓扑）邻域。

语法

本节介绍执行 K-最近邻算法所使用的语法。

运行 K-最近邻算法。

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

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

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

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

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

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

表 5. 计算配置
名称	类型	默认值	可选	描述
mutateProperty	字符串	`'similarity'`	是	将回写到 Snowflake 数据库的关系属性。
mutateRelationshipType	字符串	`'SIMILAR_TO'`	是	回写到 Snowflake 数据库的关系所使用的关系类型。
nodeProperties	字符串或映射或字符串/映射列表	`不适用`	否	用于相似度计算的节点属性及其选定的相似度指标。接受单个属性键、属性键到指标的映射，或属性键和/或映射的列表，如上所述。有关详细信息，请参阅节点属性和指标配置。
topK	整数	`10`	是	为每个节点查找的邻居数量。将返回 K 个最近邻居。此值不能低于 1。
sampleRate	浮点数	`0.5`	是	采样率，用于限制每个节点的比较次数。值必须介于 0（不含）和 1（含）之间。
deltaThreshold	浮点数	`0.001`	是	以百分比表示的值，用于确定何时提前停止。如果更新次数少于配置值，算法将停止。值必须介于 0（不含）和 1（含）之间。
maxIterations	整数	`100`	是	在达到该迭代次数后，硬性停止算法的限制。
randomJoins	整数	`10`	是	每次迭代中，每个节点根据随机选择连接新节点邻居的随机尝试次数。
initialSampler	字符串	`"uniform"`	是	用于为每个节点采样前 `k` 个随机邻居的方法。"uniform" 和 "randomWalk"（均不区分大小写）是有效输入。
randomSeed	整数	`不适用`	是	控制算法随机性的种子值。请注意，设置此参数时，`concurrency` 必须设置为 1。
similarityCutoff	浮点数	`0`	是	从 K-最近邻居列表中过滤掉相似度低于此阈值的节点。
perturbationRate	浮点数	`0`	是	用遇到且相似度相同的邻居替换已知最不相似邻居的概率。

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

表 6. 写入配置
名称	类型	默认值	可选	描述
sourceLabel	字符串	`不适用`	否	内存图中用于回写关系起始节点的节点标签。
targetLabel	字符串	`不适用`	否	内存图中用于回写关系结束节点的节点标签。
outputTable	字符串	`不适用`	否	Snowflake 数据库中写入关系的表。
relationshipType	字符串	`'SIMILAR_TO'`	是	将回写到 Snowflake 数据库的关系类型。
relationshipProperty	字符串	`'similarity'`	是	将回写到 Snowflake 数据库的关系属性。

KNN 算法不读取任何关系，但 relationshipProjection 或 relationshipQuery 的值仍用于并尊重图加载。

结果与在命名图上运行写入模式相同，请参见上面的写入模式语法。

运行算法时获得确定性结果

必须将 concurrency 参数设置为 1
必须显式设置 randomSeed。

示例

在本节中，我们将展示在具体图上运行 KNN 算法的示例。使用均匀采样器，KNN 均匀随机采样初始邻居，不考虑图拓扑。这意味着 KNN 可以在仅包含节点而没有任何关系的图上运行。考虑以下由五个不连通的 Person 节点组成的图。

CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.PERSONS (NODEID STRING, AGE INT);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS VALUES
  ('Alice', 24),
  ('Bob',   73),
  ('Carol', 24),
  ('Dave',  48),
  ('Eve',   67);

在此示例中，我们希望使用 K-最近邻算法根据人物的年龄或所有给定属性的组合来比较人物。

有了 Snowflake 中的节点和关系表，我们现在可以将其作为算法作业的一部分进行投影。在以下示例中，我们将演示在此图上使用介数中心性算法。

运行作业

运行 KNN 作业涉及三个步骤：投影、计算和写入。

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

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

以下将运行一个 KNN 作业

CALL Neo4j_Graph_Analytics.graph.knn('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'PERSONS' ],
        'relationshipTables': {}
    },
    'compute': {
        'nodeProperties': ['AGE'],
        'topK': 1,
        'mutateProperty': 'score',
        'mutateRelationshipType': 'SIMILAR'
    },
    'write': [{
        'outputTable': 'PERSONS_SIMILARITY',
        'sourceLabel': 'PERSONS',
        'targetLabel': 'PERSONS',
        'relationshipType': 'SIMILAR',
        'relationshipProperty': 'score'
    }]
});

表 7. 结果
作业 ID	作业开始时间	作业结束时间	作业结果
job_df2be9e531014fa186cdabd9c3c1099f	2025-04-29 19:40:25.960000	2025-04-29 19:40:31.701000	{ "knn_1": { "computeMillis": 70, "configuration": { "concurrency": 2, "deltaThreshold": 0.001, "initialSampler": "UNIFORM", "jobId": "b74ad39a-fa2d-4db0-be0a-0862518cf2ad", "logProgress": true, "maxIterations": 100, "mutateProperty": "score", "mutateRelationshipType": "SIMILAR", "nodeLabels": [ "" ], "nodeProperties": { "AGE": "LONG_PROPERTY_METRIC" }, "perturbationRate": 0, "randomJoins": 10, "relationshipTypes": [ "" ], "sampleRate": 0.5, "similarityCutoff": 0, "sudo": false, "topK": 1 }, "didConverge": true, "mutateMillis": 436, "nodePairsConsidered": 128, "nodesCompared": 5, "postProcessingMillis": 0, "preProcessingMillis": 6, "ranIterations": 2, "relationshipsWritten": 5, "similarityDistribution": { "max": 1.000007629394531, "mean": 0.4671443462371826, "min": 0.04999995231628418, "p1": 0.04999995231628418, "p10": 0.04999995231628418, "p100": 1.0000073909759521, "p25": 0.14285731315612793, "p5": 0.04999995231628418, "p50": 0.14285731315612793, "p75": 1.0000073909759521, "p90": 1.0000073909759521, "p95": 1.0000073909759521, "p99": 1.0000073909759521, "stdDev": 0.4363971449375242 } }, "project_1": { "graphName": "snowgraph", "nodeCount": 5, "nodeMillis": 249, "relationshipCount": 0, "relationshipMillis": 0, "totalMillis": 249 }, "write_relationship_type_1": { "exportMillis": 1978, "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY", "relationshipProperty": "score", "relationshipType": "SIMILAR", "relationshipsExported": 5 } }

表 7. 结果

作业 ID

作业开始时间

作业结束时间

作业结果

job_df2be9e531014fa186cdabd9c3c1099f

2025-04-29 19:40:25.960000

2025-04-29 19:40:31.701000

 {
    "knn_1": {
      "computeMillis": 70,
      "configuration": {
        "concurrency": 2,
        "deltaThreshold": 0.001,
        "initialSampler": "UNIFORM",
        "jobId": "b74ad39a-fa2d-4db0-be0a-0862518cf2ad",
        "logProgress": true,
        "maxIterations": 100,
        "mutateProperty": "score",
        "mutateRelationshipType": "SIMILAR",
        "nodeLabels": [
          "*"
        ],
        "nodeProperties": {
          "AGE": "LONG_PROPERTY_METRIC"
        },
        "perturbationRate": 0,
        "randomJoins": 10,
        "relationshipTypes": [
          "*"
        ],
        "sampleRate": 0.5,
        "similarityCutoff": 0,
        "sudo": false,
        "topK": 1
      },
      "didConverge": true,
      "mutateMillis": 436,
      "nodePairsConsidered": 128,
      "nodesCompared": 5,
      "postProcessingMillis": 0,
      "preProcessingMillis": 6,
      "ranIterations": 2,
      "relationshipsWritten": 5,
      "similarityDistribution": {
        "max": 1.000007629394531,
        "mean": 0.4671443462371826,
        "min": 0.04999995231628418,
        "p1": 0.04999995231628418,
        "p10": 0.04999995231628418,
        "p100": 1.0000073909759521,
        "p25": 0.14285731315612793,
        "p5": 0.04999995231628418,
        "p50": 0.14285731315612793,
        "p75": 1.0000073909759521,
        "p90": 1.0000073909759521,
        "p95": 1.0000073909759521,
        "p99": 1.0000073909759521,
        "stdDev": 0.4363971449375242
      }
    },
    "project_1": {
      "graphName": "snowgraph",
      "nodeCount": 5,
      "nodeMillis": 249,
      "relationshipCount": 0,
      "relationshipMillis": 0,
      "totalMillis": 249
    },
    "write_relationship_type_1": {
      "exportMillis": 1978,
      "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY",
      "relationshipProperty": "score",
      "relationshipType": "SIMILAR",
      "relationshipsExported": 5
    }
 }

返回的结果包含有关作业执行和结果分布的信息。此外，每个节点的相似度分数已回写到 Snowflake 数据库。我们可以这样查询它

SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY ORDER BY SCORE DESC;

显示数据库中存储的计算结果

表 8. 结果
源节点 ID	目标节点 ID	分数
Alice	Carol	1.0
Carol	Alice	1.0
Bob	Eve	0.14285714285714285
Eve	Bob	0.14285714285714285
Dave	Eve	0.05

我们对大多数参数使用过程配置参数的默认值。randomSeed 和 concurrency 设置为在每次调用时产生相同的结果。topK 参数设置为 1，以便仅返回每个节点的单个最近邻居。请注意，Dave 和 Eve 之间的相似度非常低。将 similarityCutoff 参数设置为 0.10 将过滤它们之间的关系，将其从结果中移除。