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: graph

要散列的图。可以具有节点和/或边属性。也可以没有属性。

edge_attr: string, default=None

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

node_attr: string, default=None

节点属性字典中要用于哈希的键。如果无，且未指定edge_attr，则使用节点的度数作为标签。

iterations: int, default=3

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

digest_size: int, default=16

用于散列节点标签的blake2b散列摘要的大小(以位为单位)。

返回

h字符串

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

参见

weisfeiler_lehman_subgraph_hashes

笔记

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

散列之间的相似性并不意味着图之间的相似性。

工具书类

1

谢瓦希泽，尼诺，帕斯卡·施韦策，埃里克·扬·范列文，库尔特·梅尔霍恩和卡斯滕·M·博格沃德。雷曼-魏斯勒曲线图。机器学习研究杂志。2011http://www.jmlr.org/papers/volume12/shervasidze11a/shervasidze11a.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'