K-近邻 (K-Nearest Neighbors)

简介

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

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

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

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

该特定实现基于 Wei Dong 等人撰写的 通用相似度度量的有效 K-最近邻图构建。算法不是将每个节点与所有其他节点进行比较，而是基于“邻居的邻居很可能已经是最近邻居”这一假设来选择可能的邻居。该算法的时间复杂度相对于节点数呈准线性增长，而非二次方增长。

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

  • 有效的采样率必须介于 0（不含）和 1（含）之间。

  • 默认值为 0.5。

  • 此参数用于控制准确性和运行时性能之间的权衡。

  • 较高的采样率会提高结果的准确性。

    • 算法也将需要更多内存并需要更长的计算时间。

  • 较低的采样率会提高运行时性能。

    • 比较中可能会错过一些潜在节点，因此它们可能不会包含在结果中。

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

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

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

相似度度量

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

标量数字

当属性为标量数字时，相似度的计算方式如下

knn scalar similarity
图 1. 1 除以 (1 + 绝对差值)

这给出的数字范围在 (0, 1]。

整数列表

当属性为整数列表时，可以使用 Jaccard 相似度或重叠系数来衡量相似度。

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

这两种度量给出的分数范围都在 [0, 1]，不需要进行归一化。当未指定度量标准时，Jaccard 相似度是比较整数列表的默认选项。

浮点数列表

当属性为浮点数列表时，计算两个节点之间的相似度有三种替代方案。

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

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

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

另外两种度量包括 Pearson 相关系数和归一化欧几里得相似度。

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

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

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

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

多个属性

最后，当指定多个属性时，两个邻居之间的相似度是各个属性相似度的平均值，即这些数值的简单平均值，每个数值都在 [0, 1] 范围内，从而得到一个总得分，该得分也处于 [0, 1] 范围内。

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

节点属性和度量配置

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

此参数接受以下之一

表 1. nodeProperties 语法

单个属性名称

nodeProperties: 'embedding'

属性键到度量的映射 (Map)

 
nodeProperties: {
    embedding: 'COSINE',
    age: 'DEFAULT',
    lotteryNumbers: 'OVERLAP'
}

字符串和/或映射的列表

 
nodeProperties: [
    {embedding: 'COSINE'},
    'age',
    {lotteryNumbers: 'OVERLAP'}
]

按类型划分的可用度量如下

表 2. 按类型划分的可用度量
type 度量

整数列表

JACCARD, OVERLAP

浮点数列表

COSINE, EUCLIDEAN, PEARSON

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

初始邻居采样

算法通过为每个节点随机选择 k 个邻居开始。关于如何进行这种随机采样，有两种可选方案。

均匀 (Uniform)

第一种，每个节点的初始 k 个邻居是从图中所有其他节点中均匀随机选择的。这是进行初始采样的经典方式，也是算法的默认设置。注意，此方法实际上并未使用输入图的拓扑结构。

随机游走 (Random Walk)

第二种，我们从每个节点进行深度偏置的随机游走，并选择游走过程中访问的前 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 作业的计算池选择器。

配置

Map

{}

否

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

配置映射由以下三个条目组成。

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

nodeTables

节点表列表。

relationshipTables

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

resultProperty

字符串

'similarity'

是

将回写到 Snowflake 数据库的关系属性。

resultRelationshipType

字符串

'SIMILAR_TO'

是

用于回写到 Snowflake 数据库的关系类型。

nodeProperties

字符串或 Map 或字符串/Map 的列表

不适用

否

用于相似度计算的节点属性及其选定的相似度度量。接受单个属性键、属性键到度量的映射（Map），或属性键和/或映射的列表（如上所述）。详情请参阅 节点属性和度量配置。

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 算法的示例。使用均匀采样器 (Uniform sampler)，KNN 会均匀随机地采样初始邻居，而不考虑图的拓扑结构。这意味着 KNN 可以在仅包含节点而没有任何关系的图上运行。考虑以下包含五个断开连接的 Person（人）节点的图。

Visualization of the example graph 
CREATE OR REPLACE TABLE EXAMPLE_DB.DATA_SCHEMA.PERSONS (NODEID VARCHAR, AGE NUMBER, LOTTERYNUMBERS ARRAY, EMBEDDING ARRAY);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS SELECT 'Alice', 24, ARRAY_CONSTRUCT(1, 3),    ARRAY_CONSTRUCT(1.0::FLOAT, 3.0);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS SELECT 'Bob',   73, ARRAY_CONSTRUCT(1, 2, 3), ARRAY_CONSTRUCT(2.1, 1.6);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS SELECT 'Carol', 24, ARRAY_CONSTRUCT(3),       ARRAY_CONSTRUCT(1.5, 3.1);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS SELECT 'Dave',  48, ARRAY_CONSTRUCT(2, 4),    ARRAY_CONSTRUCT(0.6, 0.2);
INSERT INTO EXAMPLE_DB.DATA_SCHEMA.PERSONS SELECT 'Eve',   67, ARRAY_CONSTRUCT(1, 5),    ARRAY_CONSTRUCT(1.8, 2.7);

构建上述嵌入数组时，我们需要确保第一行数组中的第一个值在 Snowflake 中为浮点类型。如果我们不附加 ::FLOAT 构造，Snowflake 会将其强制转换为长整型 (long)。其后果是 KNN 算法最初读取到一个长整型，并期望后续所有值也都是长整型，这会导致失败。

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

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

运行作业

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

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

我们还假设应用程序名称为默认的 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,
        'resultProperty': 'score',
        'resultRelationshipType': 'SIMILAR'
    },
    'write': [{
        'outputTable': 'PERSONS_SIMILARITY',
        'sourceLabel': 'PERSONS',
        'targetLabel': 'PERSONS',
        'relationshipType': 'SIMILAR',
        'relationshipProperty': 'score'
    }]
});
表 7. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_df2be9e531014fa186cdabd9c3c1099f

SUCCESS

2025-04-29 19:40:25.960000

2025-04-29 19:40:31.701000

 
 {
  "knn_1": {
    "computeMillis": 25,
    "configuration": {
      "concurrency": 6,
      "deltaThreshold": 0.001,
      "initialSampler": "UNIFORM",
      "maxIterations": 100,
      "nodeLabels": [
        "*"
      ],
      "nodeProperties": {
        "AGE": "DEFAULT"
      },
      "perturbationRate": 0,
      "randomJoins": 10,
      "relationshipTypes": [
        "*"
      ],
      "resultProperty": "score",
      "resultRelationshipType": "SIMILAR",
      "sampleRate": 0.5,
      "similarityCutoff": 0,
      "topK": 1
    },
    "didConverge": true,
    "nodePairsConsidered": 126,
    "nodesCompared": 5,
    "ranIterations": 2,
    "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,
    "nodeLabels": ...,
    "nodeMillis": 494,
    "relationshipCount": 0,
    "relationshipMillis": 0,
    "relationshipTypes": ...,
    "totalMillis": 494
  },
  "write_relationship_type_1": {
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY",
    "relationshipProperty": "score",
    "relationshipType": "SIMILAR",
    "rowsWritten": 5,
    "writeMillis": 1895
  }
}

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

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

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

表 8. 结果
SOURCENODEID TARGETNODEID SCORE

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 将过滤掉他们之间的关系，并将其从结果中移除。

多属性计算

如果我们想基于多个度量来计算相似度，我们可以分别计算每个属性的相似度并取其平均值。例如，除了年龄属性外，我们还可以对嵌入属性使用归一化欧几里得相似度度量，并对彩票号码属性使用重叠 (Overlap) 度量。

以下示例展示了使用多个属性来计算相似度的方法
CALL Neo4j_Graph_Analytics.graph.knn('CPU_X64_XS', {
    'defaultTablePrefix': 'EXAMPLE_DB.DATA_SCHEMA',
    'project': {
        'nodeTables': [ 'PERSONS' ],
        'relationshipTables': {}
    },
    'compute': {
        'resultProperty': 'score',
        'resultRelationshipType': 'SIMILAR',
        'topK': 1,
        'nodeProperties': [
            { 'EMBEDDING': 'EUCLIDEAN' },
            'AGE',
            { 'LOTTERYNUMBERS': 'OVERLAP'}
        ]
    },
    'write': [{
        'outputTable': 'PERSONS_SIMILARITY',
        'sourceLabel': 'PERSONS',
        'targetLabel': 'PERSONS',
        'relationshipType': 'SIMILAR',
        'relationshipProperty': 'score'
    }]
});
表 9. 结果
JOB_ID JOB_STATUS JOB_START JOB_END JOB_RESULT

job_3b880e26ced04fb986b794fce6e7f4a4

SUCCESS

2025-06-30 10:46:01.906

2025-06-30 10:46:07.002

 
 {
  "knn_1": {
    "computeMillis": 30,
    "configuration": {
      "concurrency": 6,
      "deltaThreshold": 0.001,
      "initialSampler": "UNIFORM",
      "maxIterations": 100,
      "nodeLabels": [
        "*"
      ],
      "nodeProperties": {
        "AGE": "DEFAULT",
        "EMBEDDING": "EUCLIDEAN",
        "LOTTERYNUMBERS": "OVERLAP"
      },
      "perturbationRate": 0,
      "randomJoins": 10,
      "relationshipTypes": [
        "*"
      ],
      "resultProperty": "score",
      "resultRelationshipType": "SIMILAR",
      "sampleRate": 0.5,
      "similarityCutoff": 0,
      "topK": 1
    },
    "didConverge": true,
    "nodePairsConsidered": 124,
    "nodesCompared": 5,
    "ranIterations": 2,
    "similarityDistribution": {
      "max": 0.8874320983886718,
      "mean": 0.5802093505859375,
      "min": 0.2887096405029297,
      "p1": 0.2887096405029297,
      "p10": 0.2887096405029297,
      "p100": 0.8874301910400391,
      "p25": 0.37003517150878906,
      "p5": 0.2887096405029297,
      "p50": 0.4674415588378906,
      "p75": 0.8874301910400391,
      "p90": 0.8874301910400391,
      "p95": 0.8874301910400391,
      "p99": 0.8874301910400391,
      "stdDev": 0.25715020163461305
    }
  },
  "project_1": {
    "graphName": "snowgraph",
    "nodeCount": 5,
    "nodeLabels": ...,
    "nodeMillis": 248,
    "relationshipCount": 0,
    "relationshipMillis": 0,
    "relationshipTypes": ...,
    "totalMillis": 248
  },
  "write_relationship_type_1": {
    "outputTable": "EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY",
    "relationshipProperty": "score",
    "relationshipType": "SIMILAR",
    "rowsWritten": 5,
    "writeMillis": 2310
  }
}
 
SELECT * FROM EXAMPLE_DB.DATA_SCHEMA.PERSONS_SIMILARITY ORDER BY SCORE DESC;
表 10. 结果
SOURCENODEID TARGETNODEID SCORE

Alice

Carol

0.8874315534

Carol

Alice

0.8874315534

Bob

Carol

0.4674429487

Eve

Bob

0.3700361866

Dave

Bob

0.2887113179