在本文中，我们将通过一个小例子探索HashGNN如何将图节点哈希到嵌入空间中。
如果您喜欢观看视频，请点击这里。
HashGG（#GNN）是一种节点嵌入技术，它采用消息传递神经网络（MPNN）的概念来捕捉高阶邻近性和节点属性。它通过使用一种名为MinHashing的近似技术显著加快了计算速度，与传统神经网络相比具有更高的效率。因此，它是一种基于哈希的方法，并在效率和准确性之间引入了一种权衡。在本文中，我们将了解这一切的含义，并通过一个小例子来探索算法的工作原理。
节点嵌入：相似上下文的节点应该在嵌入空间中靠近
许多图机器学习应用场景，如链接预测和节点分类，需要计算节点之间的相似性。在图的上下文中，当相似性捕捉到（i）邻域（即图结构）和（ii）要嵌入的节点的属性时，这些相似性最具表现力。节点嵌入算法将节点投影到低维嵌入空间中，即为每个节点分配一个数值向量。这些向量（嵌入）可用于进一步的数值预测分析（例如机器学习算法）。嵌入算法优化的度量标准是：具有相似图上下文（邻域）和/或属性的节点应该在嵌入空间中靠近。图嵌入算法通常采用两个基本步骤：（i）定义一种机制来采样节点的上下文（Random walk in node2vec，k-fold transition matrix in FastRP），以及（ii）在保持成对距离的同时减小维度（SGD in node2vec，random projections in FastRP）。
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）哈希化，每个索引都与宇宙中的一个单独元素相关联，使用我们的每个哈希函数。这将给我们3个索引的随机排列，因此也是我们宇宙中的元素。随后，我们可以将集合向量s1和s2用作我们排列特征的掩码。对于每个排列和集合向量，我们选择存在于集合中的最小哈希值的索引。这将得到两个3维向量，一个用于每个集合，这被称为集合的MinHash签名。
MinHashing只是从输入集合中选择随机特征，我们只需要哈希函数作为一种手段，在所有输入集合上平等地重现这种随机性。我们必须在所有向量上使用相同的哈希函数集，这样如果两个输入集都有选定的元素存在，它们的签名值就会发生碰撞。签名值将以集合的Jaccard相似度的概率发生碰撞。
WLKNN（Weisfeiler-Lehman核神经网络）
HashGNN使用Weisfeiler-Lehman核神经网络（WLKNN）中定义的消息传递方案来捕捉高阶图结构和节点属性。它为HashGNN定义了前面提到的上下文采样策略。WLK运行T次迭代。在每次迭代中，它通过将节点当前向量与所有直接连接的邻居的向量相结合，为每个节点生成一个新的节点向量。因此，它被认为是在边缘上向相邻节点传递消息（节点向量）。
经过T次迭代，每个节点都包含T跳跃距离（高阶）的节点信息。在第t次迭代中，计算新的节点向量实质上是将所有邻居消息（来自第t-1次迭代）聚合为单个邻居消息，然后将其与前一次迭代的节点向量相结合。此外，WLKNN使用三个神经网络（权重矩阵和激活函数）；（i）用于聚合的邻居向量，（ii）用于节点向量，（iii）用于两者的组合。WLK的计算在第t次迭代中仅依赖于第t-1次迭代的结果。因此，它可以被视为马尔可夫链。
通过示例了解HashGNN
让我们探索一下HashGNN如何将这两种方法结合起来，以有效地将图向量嵌入到嵌入向量中。就像WLKNN一样，HashGNN算法在T次迭代中运行，通过聚合相邻向量和上一次迭代的自身节点向量，为每个节点计算一个新的节点向量。然而，它不是训练三个权重矩阵，而是使用三个局部敏感哈希方案进行哈希。每个哈希方案由K个随机构建的哈希函数组成，用于从二进制向量中绘制K个随机特征。
在每次迭代中，我们执行以下步骤：
步骤1：计算节点的签名向量：使用哈希方案3对上一次迭代的节点向量进行Min-hash（随机选择K个特征）。在第一次迭代中，节点使用它们的二进制特征向量进行初始化（稍后我们将讨论如何对节点进行二值化）。得到的签名（或消息）向量是通过边传递给所有邻居的向量。因此，在每次迭代中，我们首先为所有节点执行此操作。
步骤2：构建邻居向量：在每个节点中，我们将从所有直接相连的邻居接收签名向量，并将它们聚合成一个单一的二进制向量。随后，我们使用哈希方案2从聚合的邻居向量中选择K个随机特征，并将结果称为邻居向量。
步骤3：将节点向量和邻居向量组合成新的节点向量：最后，我们使用哈希方案1从上一次迭代的节点向量中随机选择K个特征，并将结果与邻居向量组合。得到的向量是新的节点向量，也是下一次迭代的起点。请注意，这与步骤1不同：在步骤1中，我们对节点向量应用哈希方案3来构造消息/签名向量。
正如我们所看到的，结果（新）节点向量既受到自身节点特征（3和5）的影响，也受到邻居特征（2和5）的影响。经过第一次迭代后，节点向量将捕捉到1跳跃距离的邻居信息。然而，当我们将其用作第2次迭代的输入时，它已经受到了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：对节点向量进行分类：计算节点输入向量和每个超平面向量的点积，得到超平面和输入向量之间的夹角。使用threshold参数，我们可以决定输入向量是在超平面上方（1）还是下方（0），并将相应的值分配给结果二进制特征向量。这与二进制分类中发生的事情完全相同，唯一的区别是我们不是迭代优化超平面，而是使用随机高斯分类器。
实质上，我们为每个目标维度绘制一个随机高斯分类器，并设置一个阈值参数。然后，我们为每个目标维度对输入向量进行分类，获得一个d维二进制向量，将其作为HashGNN的输入。
结论
HashGNN使用局部敏感哈希将节点向量嵌入到嵌入空间中。通过使用这种技术，它绕过了计算密集型的迭代训练神经网络（或其他优化）以及直接节点比较的过程。论文作者报告称，与SEAL和P-GNN等基于学习的算法相比，HashGNN的运行时间快2-4个数量级，同时产生高度可比较（在某些情况下甚至更好）的准确性。
HashGNN是在Neo4j GDS（图形数据科学库）中实现的，因此可以直接在您的Neo4j图形上使用。在下一篇文章中，我将详细介绍如何使用它以及需要注意的事项。
感谢您的光临，下次再见。🚀
参考资料
- 原始论文：基于哈希加速的图神经网络用于链接预测
- Neo4j GDS文档：HashGNN