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 时才是 归纳式 (inductive) 的，因此有一些注意事项。

为了使机器学习模型能够做出有用的预测，生产预测期间生成的特征与模型训练期间生成的特征具有相似的分布非常重要。此外，添加到流水线中的节点属性步骤（无论是否为 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）同样好的 HashGNN 嵌入，通常需要显著更高的维度。densityLevel 可以尝试一些很小的值，如 1 或 2，并根据需要增加。

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

然而，二进制嵌入在每个维度上仅具有一位信息。相比之下，稠密的 Float 嵌入在每个维度上具有 64 位信息。因此，为了获得与产生稠密嵌入的算法（如 FastRP 或 GraphSAGE）同样好的 HashGNN 嵌入，通常需要显著更高的维度。

默认的 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' 属性而产生的特征数量。

我们可以看到，每个节点至少有一个激活特征。密度约为 50%，且没有节点超过两个激活特征（受 embeddingDensity 限制）。

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

有关 mutate 模式的更多详细信息，请参阅 修改模式。

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

write 执行模式扩展了 stats 模式，具有一个重要的副作用：将每个节点的嵌入作为属性写入 Neo4j 数据库。新属性的名称使用强制配置参数 writeProperty 指定。结果是一个单一的摘要行，类似于 stats，但带有一些额外的指标。write 模式实现了将结果直接持久化到数据库中。

有关 write 模式的更多详细信息，请参阅 写入模式。

也许以下示例最好备好笔和纸来阅读。

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

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

我们现在考虑 (b)。特征 f2 使用哈希函数“一”得到哈希值 8。查看邻居 (a)，我们为 f1 采样一个哈希值，使用哈希函数“二”得到 5。由于 (c) 拥有不止一个特征，我们也必须在考虑“获胜”特征之前从 f1 和 f3 中选择一个，作为哈希函数“二”的输入。为此我们使用第三个哈希函数“三”，且 f3 得到了较小的值 1。我们现在使用“二”计算 f3 的哈希值，结果为 6。由于 5 小于 6，f1 是 (b) 的“获胜”邻居特征，并且由于 5 也小于 8，它是整体的“获胜”特征。因此，我们将 f1 添加到 (b) 的嵌入中。我们对 k=1 进行类似处理，f1 再次被选中。由于嵌入由二进制特征组成，第二次添加没有任何效果。

我们省略计算 (c) 嵌入的详细信息。

经过 2 轮采样后，迭代完成。由于只有一次迭代，我们已经完成。每个节点都有一个包含原始二进制特征子集的二进制嵌入。具体而言，(a) 具有特征 f1 和 f2，(b) 仅具有特征 f1。