weisfeiler_lehman_subgraph_hashes#

weisfeiler_lehman_subgraph_hashes(G, edge_attr=None, node_attr=None, iterations=3, digest_size=16)[源代码]#

按节点返回子图散列的字典。

词典以节点为关键字，在包含关键节点的2*k个边内的节点的递增大小的导出子图中的散列列表中增加整数k，直到包括所有节点为止。

该函数迭代地聚集和散列每个节点的邻域。对于每个步骤，这是通过为每个节点用其散列的1跳邻域聚集替换其来自前一迭代的标签来实现的。然后将新的节点标签附加到每个节点的节点标签列表。

在节点的每个步骤聚合邻域 \(n\) ，相邻节点的所有标签 \(n\) 是串联在一起的。如果 edge_attr 参数后，每个相邻结点的标注都会在从该相邻结点到结点的连接边上加上该属性值的前缀 \(n\) 。然后对生成的字符串进行哈希处理，以将该信息压缩为固定摘要大小。

因此，在 \(i\) 内的第4个迭代节点 \(2i\) 距离影响任何给定的散列节点标签。因此，我们可以说，深入地说 \(i\) 对于节点 \(n\) 我们有一个子图的散列，它由 \(2i\) -跳跃的邻居 \(n\) 。

可用于创建通用的Weisfeler-Lehman图核，或生成图或节点的特征，例如，在图中生成“单词”，如“graph 2vec”算法中所示。看见 [1] & [2] 分别为详细信息。

对于同构子图，散列是相同的，并且存在强保证，非同构的图将得到不同的散列。看见 [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散列摘要的大小(以位为单位)。默认大小为16位

返回

node_subgraph_hashesDICT: 一个字典，每个关键字由G中的一个节点给出，每个值由子图给出，按照从关键字节点开始的深度顺序散列。

参见

weisfeiler_lehman_graph_hash

笔记

要在不需要子图散列时对整个图进行散列，请使用 weisfeiler_lehman_graph_hash 为了提高效率。

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

工具书类

1(1,2): 谢瓦希泽，尼诺，帕斯卡·施韦策，埃里克·扬·范列文，库尔特·梅尔霍恩和卡斯滕·M·博格沃德。雷曼-魏斯勒曲线图。机器学习研究杂志。2011http://www.jmlr.org/papers/volume12/shervasidze11a/shervasidze11a.pdf
2: Annamalai Narayanan，Mahinthan Chandramohan，Rajasekar Venkatesan，Li Hed Chen，Yang Liu和Shantanu Jaiswa。Graph 2vec：学习图形的分布式表示。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']

前两个WL子图散列匹配。由此我们可以得出结论，这些节点周围的4跳邻域很可能是同构的：每次迭代聚合1跳邻域，这意味着深度散列 \(n\) 受其中的每一个节点影响 \(2n\) 啤酒花。

然而，6跳的邻域不再同构，因为它们的第三个散列不匹配。

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