HashGNN

为了清楚地说明 HashGNN 的工作原理，我们将通过一个虚拟的示例 如下，其中包含一个三节点图，供对特征选择细节感到好奇且更倾向于从示例中学习的读者参考。

HashGNN 算法只能在二进制特征上运行。 因此，算法有一个可选的第一步，将（可能是非二进制的）输入特征转换为二进制特征。

在多次迭代中，将使用上一迭代的嵌入为每个节点计算一个新的二进制嵌入。 在第一次迭代中，之前的嵌入是输入特征向量或二值化的输入向量。

在一次迭代中，每个节点嵌入向量都是通过取 `K` 个随机样本构建的。 随机采样是通过依次选择具有最低 min-hash 值的特征来进行的。 同时考虑了每个节点本身的特征及其邻居的特征。

涉及三种类型的哈希函数：1) 应用于节点自身特征的函数，2) 应用于邻居特征子集的函数，3) 应用于所有邻居特征的函数，用于选择哈希函数 2) 的子集。 对于每次迭代和采样轮 `k<K`，使用新的哈希函数，并且第三个函数也根据连接到应用它的邻居的关系类型而有所不同。

采样是一致的，也就是说，如果节点 (a) 和 (b) 具有相同或相似的局部图，那么 (a) 和 (b) 的样本也是相同或相似的。 局部图指的是包含所有最多 `iterations` 跳远的节点的特征和关系类型的子图。

数字 `K` 在算法的配置中称为 `embeddingDensity`。

该算法以另一个可选步骤结束，该步骤将二进制嵌入映射到稠密向量。

原始的 HashGNN 算法假设节点具有二进制特征作为输入，并生成二进制嵌入向量作为输出（除非选择输出稠密化）。 由于这并不总是适用于现实世界中的图，因此我们的算法还提供了一些选项来二值化节点属性，或从头开始生成二进制特征。

参数 `neighborInfluence` 决定了算法选择邻居特征而不是同一节点特征的倾向性。 `neighborInfluence` 的默认值为 `1.0`，在这种情况下，平均而言，特征将有 `50%` 的时间从邻居处选择。 提高该值会导致更多地选择邻居。 作为 `neighborInfluence` 函数，从邻居处选择特征的概率具有类似曲棍球棒的形状，类似于 `y=log(x)` 或 `y=C - 1/x` 的形状。 这意味着概率对 `neighborInfluence` 的低值更敏感。

GDS 中的 HashGNN 实现为异构图提供了一种新的推广，因为它可以区分不同的关系类型。 要启用异构支持，请将 `heterogeneous` 设置为 true。 推广与原始 HashGNN 算法相同，但只要将哈希函数应用于邻居节点的特征，算法就会使用一个哈希函数，该函数不仅取决于迭代和数字 `k < embeddingDensity`，还取决于连接到邻居的关系类型。 考虑一个示例，其中 HashGNN 以一次迭代运行，并且我们有 `(a)-[:R]→(x), (b)-[:R]→(x)` 和 `(c)-[:S]→(x)`。 假设 `(x)` 的一个特征 `f` 被选择用于 `(a)`，并且哈希值非常小。 这将使该特征也很有可能被选择用于 `(b)`。 但是，在考虑关系 `(c)-[:S]→(x)` 时，`f` 被选择用于 `(c)` 将没有任何关联，因为 `S` 使用了不同的哈希函数。 我们可以得出结论，具有相似邻域（包括节点属性和关系类型）的节点将获得相似的嵌入，而具有不太相似邻域的节点将获得不太相似的嵌入。

与运行 FastRP 等同构嵌入相比，运行异构 HashGNN 的一个优势在于，不需要手动选择多个投影或在 FastRP 上运行这些多个图之前创建元路径图。 使用异构算法，可以在一次执行中使用完整的异构图。

异构图通常对不同的节点标签具有不同的节点属性。 HashGNN 假设所有节点都具有相同的允许特征。 因此，在每个图投影中使用 `0` 作为默认值。 这在二进制输入情况下和应用二值化的情况下都适用，因为具有值为 `0` 的二进制特征的行为类似于没有该特征。 `0` 值以稀疏格式表示，因此存储许多节点的 `0` 值的内存开销很低。

在创建图时选择正确方向可能会产生很大影响。 HashGNN 对任何方向都适用，方向的选择取决于具体的问题。 给定一个有向关系类型，你可以选择一个方向，或者使用两个具有 `NATURAL` 和 `REVERSE` 的投影。 使用 GNN 的类比，对反向关系使用不同的关系类型会导致在考虑一个关系与其反向关系时使用不同的权重集。 对于 HashGNN，这意味着改为对这两个关系使用不同的 min-hash 函数。 例如，在引文网络中，引用另一篇论文的论文与被引用的论文非常不同。

由于二进制嵌入需要比稠密浮点数嵌入具有更高的维度才能编码相同的信息量，因此二进制嵌入需要更多内存，并且下游模型的训练时间更长。 输出嵌入可以选择性地进行稠密化，方法是使用随机投影，类似于使用节点属性初始化 FastRP 的方法。 该行为可以通过指定 `outputDimension` 来激活。 输出稠密化可以提高下游任务的运行时间和内存，但代价是由于投影的随机性而引入近似误差。 `outputDimension` 越大，近似误差越低，性能提升也越大。

在机器学习管道（如 链接预测管道 和 节点属性预测）中，将 HashGNN 作为节点属性步骤生成节点嵌入可能很有用。 由于 HashGNN 是一个随机算法，并且只有在给出 `featureProperties` 和 `randomSeed` 时才是 归纳性 的，因此需要注意一些事项。

为了使机器学习模型能够做出有用的预测，预测过程中产生的特征必须与模型训练期间产生的特征具有相似的分布。 此外，添加到管道中的节点属性步骤（无论是否使用 HashGNN）在训练期间和训练后的模型预测期间都会执行。 因此，当管道包含一个在训练和预测过程中产生截然不同的嵌入的嵌入步骤时，就会出现问题。

这对如何在节点属性步骤中使用 HashGNN 有一些影响。 一般来说，如果使用 HashGNN 作为节点属性步骤在一个图 "g" 上训练管道，那么生成的训练模型应该只应用于与 "g" 不太相似的图。

如果使用特征生成，则在运行预测的图中，大多数节点必须与训练期间使用的原始图 "g" 中的节点相同（在数据库意义上）。 这是因为 HashGNN 随机生成节点特征，在这种情况下，它基于节点在 Neo4j 数据库中的 ID 进行种子设置，这些节点来自该数据库。

如果未使用特征生成（提供 featureProperties），则随机的初始节点嵌入仅从节点属性向量派生，因此没有基于节点 ID 的随机种子设置。

此外，为了使 HashGNN 消息传递的特征传播在运行（训练和预测调用）之间保持一致，在将 HashGNN 节点属性步骤添加到训练管道时，必须提供 randomSeed 配置参数的值。

节点与其影响其嵌入的其他节点之间的最大跳数等于 HashGNN 的迭代次数，该次数由 iterations 配置。 这类似于 GNN 中的层数或 FastRP 中的迭代次数。 通常，2 到 4 的值就足够了，但有时更多迭代是有用的。

embeddingDensity 参数是原始论文用 k 表示的。 对于 HashGNN 的每次迭代，从前一次迭代的相同节点及其邻居的嵌入中选择 k 个特征。 选择的特征用集合表示，因此不同的选择特征的数量可能小于 k。 此参数设置得越高，运行算法所需的时间就越长，运行时间以线性方式增加。 在很大程度上，更高的值会产生更好的嵌入。 作为一个宽松的准则，可以尝试将 embeddingDensity 设置为 128、256、512 或大约嵌入维度的 25%-50%，即二进制特征的数量。

dimension 参数决定了应用特征生成时的二进制特征数量。 高维度会提高表达能力，但需要更多数据才能发挥作用，并且会导致下游机器学习任务的维度灾难。 此外，将需要更多计算资源。 但是，二进制嵌入每个维度只有一个信息位。 相反，密集的 Float 嵌入每个维度有 64 位信息。 因此，为了获得与产生密集嵌入的算法（例如 FastRP 或 GraphSAGE）类似的良好嵌入，通常需要更高的维度。 densityLevel 一些值得尝试的值是非常低的值，例如 1 或 2，或者根据需要增加。

dimension 参数决定了应用二值化时的二进制特征数量。 高维度会提高表达能力，但也提高特征的稀疏性。 因此，更高的维度也应该与更高的 embeddingDensity 和/或更低的 threshold 结合使用。 更高的维度也会导致下游模型的训练时间更长，以及更高的内存占用。 增加阈值会导致更稀疏的特征向量。

但是，二进制嵌入每个维度只有一个信息位。 相反，密集的 Float 嵌入每个维度有 64 位信息。 因此，为了获得与产生密集嵌入的算法（例如 FastRP 或 GraphSAGE）类似的良好嵌入，通常需要更高的维度。

0 的默认阈值会导致每个节点有相当多的特征处于活动状态。 通常，稀疏特征向量更好，因此将阈值提高到默认值以上可能是有用的。 选择良好阈值的一种启发式方法是使用超平面点积与节点特征向量的平均值和标准差。 例如，可以将阈值设置为平均值加上标准差的两倍。 要获得这些值，请运行 HashGNN 并查看数据库日志，您可以在其中读取这些值。 然后，您可以使用这些值相应地重新配置阈值。

如上所述，默认值是一个合理的起点。 如果使用超参数调整库，此参数可能通过具有递增导数的函数（如指数函数）或 a/(b - x) 类型的函数来有利地转换。 从不同节点选择（并在迭代中保留）特征的概率取决于 neighborInfluence 和到节点的跳数。 因此，在更改 iterations 时，应重新调整 neighborInfluence。

一般来说，在异构图中，需要存储大量关于包含多个关系类型路径的信息，因此在具有许多迭代次数和关系类型的情况下，可能需要非常高的嵌入维度。 这对于无监督嵌入算法（如 HashGNN）尤其如此。 因此，在异构模式下使用多次迭代时，应谨慎操作。

随机种子在该算法中具有特殊作用。 除了使算法的所有步骤确定性之外，randomSeed 参数还决定了算法内部使用哪些（在某种程度上）哈希函数。 这很重要，因为它会极大地影响每次迭代采样的特征。 哈希在图神经网络每一层的（通常是神经）转换中发挥着类似的作用，这告诉我们哈希函数的重要性。 事实上，人们经常会在算法输出的节点嵌入质量方面看到显著的差异，而这仅仅是因为配置中的 randomSeed 不同。

出于这些原因，实际上可以调整随机种子参数。 请注意，它应该作为分类（即非序数）数字进行调整，这意味着值 1 和 2 可以被认为与值 1 和 100 一样相似或不同。 开始执行此操作的一种好方法是选择 5-10 个任意整数（例如，值 1、2、3、4 和 5）作为随机种子的候选者。

randomSeed 与多个配置参数存在共依赖关系，尤其是与 neighborInfluence 参数存在共依赖关系，该参数也直接影响使用哪些哈希函数。 因此，如果更改了 neighborInfluence，则可能需要重新调整 randomSeed 参数。

首先，我们将使用 `estimate` 过程估算运行算法的成本。这可以在任何执行模式下完成。在本示例中，我们将使用 `stream` 模式。估算算法有助于理解在图上运行算法的内存影响。稍后，当您实际在某种执行模式下运行算法时，系统将执行估算。如果估算显示执行超出其内存限制的可能性很高，则会禁止执行。有关此的更多信息，请参见 自动估算和执行阻止。

有关 `estimate` 的更多详细信息，请参见 内存估算。

在 `stream` 执行模式下，算法会返回每个节点的嵌入。这使我们可以直接检查结果，或者在 Cypher 中对结果进行后处理，而不会产生任何副作用。例如，我们可以收集结果并将它们传递给相似性算法。

有关 `stream` 模式的更多详细信息，请参见 流。

算法的结果并不直观，因为节点嵌入格式是节点在其邻域内的数学抽象，专为机器学习程序设计。我们可以看到嵌入有四个元素（如使用 `binarizeFeatures.dimension` 配置的那样）。

在本示例中，嵌入维度变为 `1`，因为在没有二进制化的情况下，它表示特征的数量，由于单个 'hipster' 属性，特征数量为 `1`。

正如我们所见，每个节点至少有一个活动特征。密度约为 50%，没有节点超过两个活动特征（受 `embeddingDensity` 限制）。

`mutate` 执行模式通过一个重要的副作用扩展了 `stats` 模式：使用包含该节点嵌入的新节点属性更新命名图。新属性的名称使用强制配置参数 `mutateProperty` 指定。结果是类似于 `stats` 的单个摘要行，但具有一些额外的指标。`mutate` 模式在多个算法一起使用时特别有用。

有关 `mutate` 模式的更多详细信息，请参见 变异。

图 'persons' 现在具有一个名为 `hashgnn-embedding` 的节点属性，用于存储每个节点的节点嵌入。要了解如何检查内存中图的新模式，请参见 列出图。

也许下面的示例最适合用笔和纸来理解。

假设我们有一个带有特征 `f1` 的节点 `a`，一个带有特征 `f2` 的节点 `b`，以及一个带有特征 `f1` 和 `f3` 的节点 `c`。图结构为 `a—​b—​c`。我们想象运行 HashGNN 一次迭代，`embeddingDensity=2`。为简单起见，我们假设哈希函数在计算过程中返回一些虚构的数字。

在第一次迭代和 `k=0` 期间，我们计算 `(a)` 的嵌入。`f1` 的哈希值结果为 `7`。由于 `(b)` 是 `(a)` 的邻居，我们为其特征 `f2` 生成一个值，结果为 `11`。值 `7` 从我们称为 "one" 的哈希函数中采样，`11` 从 "two" 哈希函数中采样。因此，`f1` 被添加到 `(a)` 的新特征中，因为它具有较小的哈希值。我们对 `k=1` 重复此过程，这次哈希值分别为 `4` 和 `2`，因此现在 `f2` 被添加为 `(a)` 的特征。

现在我们考虑 `(b)`。特征 `f2` 使用 "one" 哈希函数获得哈希值 `8`。查看邻居 `(a)`，我们为 `f1` 采样一个哈希值，使用 "two" 哈希函数得到 `5`。由于 `(c)` 具有多个特征，因此我们必须在考虑 "获胜" 特征之前选择两个特征 `f1` 和 `f3` 之一作为 "two" 哈希函数的输入。我们使用第三个哈希函数 "three" 来实现这一点，`f3` 获得了较小的值 `1`。我们现在使用 "two" 计算 `f3` 的哈希值，结果为 `6`。由于 `5` 小于 `6`，因此 `f1` 是 `(b)` 的 "获胜" 邻居特征，由于 `5` 也小于 `8`，因此它是整体 "获胜" 特征。因此，我们将 `f1` 添加到 `(b)` 的嵌入中。我们继续进行类似的步骤，`k=1`，再次选择 `f1`。由于嵌入由二进制特征组成，因此第二次添加没有影响。

我们省略了计算 `(c)` 嵌入的细节。

在 2 轮采样后，迭代完成，由于只有一次迭代，因此我们已完成。每个节点都有一个二进制嵌入，其中包含原始二进制特征的某个子集。特别是，`(a)` 具有特征 `f1` 和 `f2`，`(b)` 仅具有特征 `f1`。