weisfeiler_lehman_graph_hash#

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

返回 Weisfeiler Lehman (WL) 图哈希值。

该函数迭代地聚合和哈希每个节点的邻域。在每个节点的邻居被哈希以获得更新后的节点标签后，返回结果标签的哈希直方图作为最终哈希值。

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

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

Parameters:
G图

要进行哈希的图。 可以具有节点和/或边属性。也可以没有任何属性。

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

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

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

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

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

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

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

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

Returns:
h字符串

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

See also

weisfeiler_lehman_subgraph_hashes

Notes

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

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

References

[1]

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

Examples

两个具有边属性的图是同构的，除了边标签的差异。

>>> 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'
On this page