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 个元素。

该函数通过迭代聚合和哈希每个节点的邻域来实现。这是通过在每个步骤中，将每个节点在前一次迭代中的标签替换为其哈希的 1-跳邻域聚合来实现的。然后将新的节点标签附加到每个节点的节点标签列表中。

为了在每个步骤中聚合节点 \(u\) 的邻域，将所有与 \(u\) 相邻节点的标签连接起来。如果设置了 edge_attr 参数，每个相邻节点的标签将以前缀形式包含从该邻居到节点 \(u\) 的连接边的该属性的值。然后将生成的字符串哈希以将此信息压缩为固定大小的摘要。

因此，在第 \(i\) 次迭代中，距离 \(i\) 跳以内的节点影响任何给定的哈希节点标签。因此，对于节点 \(u\) 在深度 \(i\) 处，我们有一个由 \(u\) 的 \(i\)-跳邻域诱导的子图的哈希。

输出可用于创建通用的 Weisfeiler-Lehman 图核，或生成图或节点的特征 - 例如在 ‘graph2vec’ 算法中生成图的 ‘单词’。详情分别见 [1] 和 [2]。

同构子图的哈希相同，并且存在强有力的保证，非同构图将获得不同的哈希。详情见 [1]。

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

Parameters:

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，则将哈希的初始节点标签作为每个节点的第一个子图哈希包含在内。

Returns:

node_subgraph_hashes字典: 一个字典，每个键由 G 中的一个节点给出，每个值由从键节点开始的深度顺序的子图哈希给出。

See also

weisfeiler_lehman_graph_hash

Notes

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

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

References

[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

Examples

在不同图中找到相似的节点：

>>> 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 跳邻域不是同构的，因为上述列表中的第 3 个哈希不相等。

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