HashGG（#GNN）是一种节点嵌入技术，它采用了消息传递神经网络（MPNN）的概念来捕捉高阶接近性和节点属性。通过利用一种名为MinHashing的近似技术，它在计算速度上与传统神经网络相比显著加快。因此，它是一种基于哈希的方法，并引入了效率和准确性之间的权衡。在本文中，我们将了解所有这些含义，并将通过一个小例子来探索算法的工作原理。

节点嵌入：在嵌入空间中，具有相似上下文的节点应该靠近

许多图机器学习应用场景，如链接预测和节点分类，需要计算节点之间的相似度。在图的上下文中，当相似度捕捉到（i）节点的邻域（即图结构）和（ii）要嵌入的节点的属性时，这些相似度最具表现力。节点嵌入算法将节点投影到低维嵌入空间中，即为每个节点分配一个数值向量。这些向量，也就是嵌入向量，可以用于进一步的数值预测分析（例如机器学习算法）。嵌入算法优化的度量标准是：具有相似的图上下文（邻域）或属性的节点应该在嵌入空间中映射为靠近的位置。

HashGNN：规避神经网络的训练

HashGNN的关键在于它不需要我们根据损失函数来训练神经网络，这与传统的消息传递神经网络是不同的。由于节点嵌入算法优化的目标是“相似的节点应该在嵌入空间中靠近”，损失的评估涉及计算节点对的真实相似度。然后将其作为训练的反馈，以判断预测的准确性，并相应地调整权重。通常，余弦相似度被用作相似度度量。

HashGNN绕过了模型训练，实际上根本没有使用神经网络。它使用了一种随机哈希方案，将节点向量哈希为相同的签名，并以它们相似的概率来决定哈希。这意味着我们可以在不需要直接比较节点的情况下嵌入节点（即不需要计算余弦相似度）。这种哈希技术被称为MinHashing，最初是为了近似比较两个集合的相似性而定义的。由于集合被编码为二进制向量，HashGNN需要节点的二进制表示。为了理解如何使用这种方法来嵌入通用图的节点，需要使用多种技术。让我们来看一下。

MinHashing

首先，让我们谈谈MinHashing。MinHashing是一种近似计算两个集合的Jaccard相似度的局部敏感哈希技术。Jaccard相似度通过将交集的大小除以两个集合中出现的唯一元素的数量（并集）来衡量两个集合的重叠（交集）。它定义在集合上，集合被编码为二进制向量：宇宙（所有元素集合）中的每个元素被分配一个唯一的行索引。如果特定的集合包含一个元素，则在该集合的向量的相应行中表示为值1。MinHashing算法独立地对每个集合的二进制向量进行哈希，并使用K个哈希函数为其生成一个K维的签名。MinHashing的直观解释是通过选择具有最小哈希值的非零元素来随机选择K次。这将生成输入集合的签名向量。有趣的是，如果我们对两个集合都这样操作，而不进行比较，它们将以它们的Jaccard相似度的概率（如果K足够大）哈希到相同的签名。换句话说：概率收敛于Jaccard相似度。

在图示中，示例集合s1和s2被表示为二进制向量。我们可以通过比较这两个向量并计算它们共同拥有1的行数来轻松计算Jaccard相似度。这些操作非常简单，但是如果我们有很多向量，复杂性就存在于向量之间的成对比较中。

我们的宇宙U的大小为6，我们选择K（哈希函数的数量）为3。我们可以通过使用简单的公式和a、b和c的边界来轻松生成新的哈希函数。现在，我们实际上是将向量的索引（1-6）哈希化，每个索引对应宇宙中的一个元素，并使用每个哈希函数。这将给我们三个索引的随机排列，因此也是宇宙中的元素。然后，我们可以将集合向量s1和s2用作排列特征的掩码。对于每个排列和集合向量，我们选择集合中存在的具有最小哈希值的索引。这将得到两个三维向量，一个用于每个集合，这被称为集合的MinHash签名。

MinHashing只是从输入集中随机选择特征，并且我们只需要哈希函数作为一种手段，以便在所有输入集上均匀地重现这种随机性。我们必须在所有向量上使用相同的哈希函数集合，这样如果两个输入集都有选定的元素存在，它们的签名值才会发生冲突。签名值将以集合的Jaccard相似度的概率发生冲突。

WLKNN（Weisfeiler-Lehman核神经网络）

HashGNN使用了Weisfeiler-Lehman核神经网络（WLKNN）中定义的消息传递方案，以捕捉高阶图结构和节点属性。它为HashGNN定义了前面提到的上下文采样策略。WLKNN在T次迭代中运行。在每次迭代中，它通过将节点的当前向量与所有直接连接的邻居节点的向量结合来为每个节点生成一个新的节点向量。因此，它被认为是通过边向相邻节点传递消息（节点向量）。

经过T次迭代后，每个节点都包含T跳距离内节点的信息（高阶）。在第t次迭代中，计算新的节点向量实际上是将所有邻居消息（来自第t-1次迭代）聚合为单个邻居消息，然后将其与上一次迭代的节点向量结合。此外，WLKNN还使用了三个神经网络（权重矩阵和激活函数）：（i）用于聚合邻居向量，（ii）用于节点向量，以及（iii）用于两者的组合。值得注意的是，WLKNN的第t次迭代的计算仅依赖于第t-1次迭代的结果。因此，它可以被视为一个马尔可夫链。

HashGNN示例

让我们探讨一下HashGNN如何将这两种方法相结合，以高效地将图向量嵌入为嵌入向量。就像WLKNN一样，HashGNN算法在T次迭代中运行，为每个节点计算一个新的节点向量，通过聚合上一次迭代的邻居向量和自身的节点向量来实现。然而，与训练三个权重矩阵不同，它使用了三个局部敏感哈希的哈希方案。每个哈希方案都由K个随机构建的哈希函数组成，用于从二进制向量中提取K个随机特征。

在每次迭代中，我们执行以下步骤：

步骤1：计算节点的签名向量：使用哈希方案3对前一次迭代的节点向量进行MinHash（随机选择K个特征）。在第一次迭代中，节点使用它们的二进制特征向量进行初始化（稍后我们将讨论如何将节点二值化）。生成的签名（或消息）向量沿边传递给所有邻居节点。因此，在每次迭代中，我们首先针对所有节点执行此操作。

步骤2：构建邻居向量：在每个节点中，我们将接收所有直接相连的邻居节点的签名向量，并将它们聚合成一个单一的二进制向量。然后，我们使用哈希方案2从聚合的邻居向量中选择K个随机特征，并将结果称为邻居向量。

步骤3：将节点向量和邻居向量组合成新的节点向量：最后，我们使用哈希方案1从前一次迭代的节点向量中随机选择K个特征，并将结果与邻居向量结合起来。生成的向量是下一次迭代的起点，即新的节点向量。请注意，这与步骤1不同：在步骤1中，我们将哈希方案3应用于节点向量以构造消息/签名向量。

正如我们所看到的，生成的（新的）节点向量具有自身节点特征（3和5）以及邻居的特征（2和5）的影响。在第一次迭代后，节点向量将捕捉到与之相邻的节点的信息，距离为1跳。然而，当我们将其作为第二次迭代的输入时，它已经受到了2跳目标的特征的影响。

Neo4j GDS概括

HashGNN是由Neo4j GDS（图数据科学库）实现的，并对算法添加了一些有用的泛化功能。

在GDS中，一个重要的辅助步骤是特征二值化。MinHashing和因此HashGNN需要二进制向量作为输入。Neo4j提供了一个额外的准备步骤，将实值节点向量转换为二进制特征向量。他们利用了一种称为超平面舍入的技术。该算法的工作原理如下：

步骤1: 定义节点特征: 定义要用作节点特征的（实值）节点属性。这是使用参数featureProperties来完成的。我们将其称为节点输入向量f。

步骤2: 构建随机二进制分类器: 为每个目标维度定义一个超平面。结果维度的数量由参数dimensions控制。超平面是一个高维平面，并且只要它位于原点，就可以仅通过其法向量n来描述。n向量垂直于平面的表面，因此描述了它的方向。在我们的案例中，n向量需要与节点输入向量具有相同的维度（dim(f) = dim(n)）。为了构造超平面，我们只需从高斯分布中提取dim(f)个数据。

步骤3: 对节点向量进行分类: 计算节点输入向量和每个超平面向量的点积，从而得到超平面和输入向量之间的夹角。使用阈值参数，我们可以决定输入向量是在超平面之上（1）还是之下（0），并将相应的值分配给生成的二进制特征向量。这正是二分类中发生的事情-唯一的区别是我们不会迭代地优化超平面，而是使用随机的高斯分类器。

实质上，我们为每个目标维度绘制一个随机的高斯分类器，并设置一个阈值参数。然后，我们对每个目标维度对输入向量进行分类，得到一个d维的二进制向量，将其用作HashGNN的输入。

总结：

HashGNN使用局部敏感哈希将节点向量嵌入到嵌入空间中。通过使用这种技术，它绕过了基于迭代训练的神经网络（或其他优化）以及直接节点比较的计算密集型过程。论文的作者报告称，与基于学习的算法（如SEAL和P-GNN）相比，HashGNN的运行时间快了2-4个数量级，同时仍然具有高度可比（在某些情况下甚至更好）的准确性。

HashGNN 在 Neo4j GDS（图形数据科学库）中实现，因此可以在 Neo4j 图形上开箱即用。