weisfeiler_lehman_graph_hash

weisfeiler_lehman_graph_hash(G, edge_attr=None, node_attr=None, iterations=3, digest_size=16)

返回 Weisfeiler Lehman (WL) 图哈希。

此函数迭代地聚合并哈希每个节点的邻域。在对每个节点的邻居进行哈希以获得更新的节点标签后，将结果标签的哈希直方图作为最终哈希返回。

同构图的哈希值是相同的，并且强烈保证非同构图会获得不同的哈希值。有关详细信息，请参阅 [1]。

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

参数:

G图

要进行哈希的图。可以包含节点和/或边属性。也可以不包含任何属性。

edge_attr字符串，可选 (默认为 None)

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

node_attr: 字符串，可选 (默认为 None)

用于哈希的节点属性字典中的键。如果为 None，并且没有给定 edge_attr，则使用节点的度数作为标签。

iterations: 整数，可选 (默认为 3)

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

digest_size: 整数，可选 (默认为 16)

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

返回:

h字符串

对应于输入图哈希值的十六进制字符串。

另请参阅

weisfeiler_lehman_subgraph_hashes

说明

要返回图的每个子图的 WL 哈希值，请使用 weisfeiler_lehman_subgraph_hashes

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

参考文献

[1]

Shervashidze, Nino, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt。Weisfeiler Lehman Graph Kernels。《机器学习研究杂志》。2011 年。http://www.jmlr.org/papers/volume12/shervashidze11a/shervashidze11a.pdf

示例

两个具有边属性的图，它们是同构的，只是边标签不同。

>>> G1 = nx.Graph()
>>> G1.add_edges_from(
...     [
...         (1, 2, {"label": "A"}),
...         (2, 3, {"label": "A"}),
...         (3, 1, {"label": "A"}),
...         (1, 4, {"label": "B"}),
...     ]
... )
>>> G2 = nx.Graph()
>>> G2.add_edges_from(
...     [
...         (5, 6, {"label": "B"}),
...         (6, 7, {"label": "A"}),
...         (7, 5, {"label": "A"}),
...         (7, 8, {"label": "A"}),
...     ]
... )

省略 edge_attr 选项会导致相同的哈希值。

>>> nx.weisfeiler_lehman_graph_hash(G1)
'7bc4dde9a09d0b94c5097b219891d81a'
>>> nx.weisfeiler_lehman_graph_hash(G2)
'7bc4dde9a09d0b94c5097b219891d81a'

有了边标签，这些图将不再被分配相同的哈希摘要。

>>> nx.weisfeiler_lehman_graph_hash(G1, edge_attr="label")
'c653d85538bcf041d88c011f4f905f10'
>>> nx.weisfeiler_lehman_graph_hash(G2, edge_attr="label")
'3dcd84af1ca855d0eff3c978d88e7ec7'