weisfeiler_lehman_subgraph_hashes#

weisfeiler_lehman_subgraph_hashes(G, edge_attr=None, node_attr=None, iterations=3, digest_size=16, include_initial_labels=False)[source]#

按节点返回一个子图哈希字典。

字典的键是 G 中的节点，值是哈希列表。每个哈希对应于以 G 中给定节点 u 为根的子图。子图哈希列表按与根节点的深度升序排序，索引 i 处的哈希对应于与 u 的边缘距离最多为 i 的节点组成的子图。因此，每个列表将包含 iterations 个元素 - 每个深度对应一个子图的哈希。如果 include_initial_labels 设置为 True，则每个列表还会额外在开头包含初始节点标签（或等效地，深度为 0 的子图）的哈希，总共有 iterations + 1 个元素。

该函数迭代地聚合并哈希每个节点的邻域。每一步通过用其哈希化的一跳邻域聚合结果替换每个节点在前一次迭代中的标签来实现。然后将新的节点标签附加到每个节点的节点标签列表中。

为了在每一步聚合节点 \(u\) 的邻域，与 \(u\) 相邻的所有节点的标签被连接起来。如果设置了 edge_attr 参数，每个相邻节点的标签都会在其前面加上沿此邻居到节点 \(u\) 的连接边缘上此属性的值。然后对结果字符串进行哈希处理，将此信息压缩为固定摘要大小。

因此，在第 \(i\) 次迭代中，距离任何给定哈希节点标签 \(i\) 跳以内的节点都会对其产生影响。因此，我们可以说，在节点 \(u\) 的深度 \(i\) 处，我们得到了由 \(u\) 的 \(i\) 跳邻域诱导的子图的哈希值。

输出可用于创建通用的 Weisfeiler-Lehman 图核，或为图或节点生成特征 - 例如，生成图中的“词”，如“graph2vec”算法所示。有关详细信息，请参阅 [1] 和 [2]。

同构子图的哈希是相同的，并且对于非同构图，有很强的保证会得到不同的哈希。有关详细信息，请参阅 [1]。

如果未提供节点或边缘属性，则使用每个节点的度作为其初始标签。否则，使用节点和/或边缘标签来计算哈希。

参数:
G图

要进行哈希处理的图。可以有节点和/或边缘属性。也可以没有属性。

edge_attr字符串, 可选 (默认值=None)

边缘属性字典中用于哈希的键。如果为 None，则忽略边缘标签。

node_attr字符串, 可选 (默认值=None)

节点属性字典中用于哈希的键。如果为 None，且未给出 edge_attr，则使用节点的度作为标签。如果为 None，且给出了 edge_attr，则每个节点都以相同的标签开始。

iterations整数, 可选 (默认值=3)

执行邻居聚合的次数。对于较大的图应设置得更大。

digest_size整数, 可选 (默认值=16)

用于哈希节点标签的 blake2b 哈希摘要的大小（以位为单位）。默认大小为 16 位。

include_initial_labels布尔值, 可选 (默认值=False)

如果为 True，则将哈希化的初始节点标签作为每个节点的第一个子图哈希包含在内。

返回:
node_subgraph_hashes字典

一个字典，其中每个键是 G 中的一个节点，每个值是按与键节点的深度顺序排列的子图哈希列表。

另请参阅

weisfeiler_lehman_graph_hash

注意

当不需要子图哈希时，为了提高效率，请使用 weisfeiler_lehman_graph_hash 来哈希整个图。

哈希之间的相似性不意味着图之间的相似性。

参考文献

[1] (1,2)

Shervashidze, Nino, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler Lehman Graph Kernels. Journal of Machine Learning Research. 2011. http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

[2]

Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu and Shantanu Jaiswa. graph2vec: Learning Distributed Representations of Graphs. arXiv. 2017 https://arxiv.org/pdf/1707.05005.pdf

示例

在不同图中查找相似节点

>>> G1 = nx.Graph()
>>> G1.add_edges_from([(1, 2), (2, 3), (2, 4), (3, 5), (4, 6), (5, 7), (6, 7)])
>>> G2 = nx.Graph()
>>> G2.add_edges_from([(1, 3), (2, 3), (1, 6), (1, 5), (4, 6)])
>>> g1_hashes = nx.weisfeiler_lehman_subgraph_hashes(
...     G1, iterations=3, digest_size=8
... )
>>> g2_hashes = nx.weisfeiler_lehman_subgraph_hashes(
...     G2, iterations=3, digest_size=8
... )

尽管 G1 和 G2 不同构（它们的边数不同），但 G1 中节点 1 和 G2 中节点 5 的深度为 3 的哈希序列是相似的

>>> g1_hashes[1]
['a93b64973cfc8897', 'db1b43ae35a1878f', '57872a7d2059c1c0']
>>> g2_hashes[5]
['a93b64973cfc8897', 'db1b43ae35a1878f', '1716d2a4012fa4bc']

前 2 个 WL 子图哈希匹配。由此我们可以得出结论，这些节点周围 2 跳范围内的邻域很可能是同构的。

然而，G1 和 G2 的 3 跳邻域不是同构的，因为上面列表中第三个哈希不相等。

这些节点可能是被一起分类的候选，因为它们的局部拓扑相似。

本页内容