如何使用networkx（Python）计算图形编辑距离？

Question

我正在使用图编辑距离；根据定义，它是将原始图G1转换成同构于G2的最小花费总和；

图编辑操作通常包括：

- 插入顶点以向图中引入单个标记顶点； - 删除顶点以从图中删除单个（常常是不相关的）顶点； - 顶点替换以更改给定顶点的标签（或颜色）； - 插入边以在一对顶点之间引入新的彩色边； - 删除边以从一对顶点之间移除单条边； - 边替换以更改给定边的标签（或颜色）。

现在我想要使用networkx提供的实现 - 我没有任何边标签，G1和G2的节点集合相同，而且我不想要同构于G2的图，我想要的是G2本身；

这主要是因为G1：1->2->3和G2: 3->2->1 在同构上是等价的，但如果节点代表某些事件，则从因果关系的角度来看，它们非常不同；

因此，在这种情况下，我一直在运行类似以下的测试：

import networkx as nx

G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])


nx.graph_edit_distance(G,G2)

但是它返回距离为零，这是有道理的，因为这两个图是同构的；

所以我尝试设置node_match，但还是没有成功。

import networkx as nx

def nmatch(n1, n2):
    return n1==n2 

G=nx.DiGraph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1)
G2.add_node(2)
G2.add_node(3)
G2.add_edges_from([(3, 2),(2, 1)])


nx.graph_edit_distance(G,G2, node_match=nmatch)

如果我们假设删除或添加边缘/顶点的成本为1，则编辑距离应为4，因为我们可以：

• 删除G中的两个边，添加G2的两个边

如何计算编辑距离而不考虑同构而仅考虑等价性将更加合适？

- Johannes

Answer 1

似乎您没有比较您想要比较的内容。在nmatch中，n1和n2始终为{}。根据文档(

(...) 换句话说，该函数将接收n1和n2的节点属性字典作为输入。

)，您并未比较节点对象，而是与它们相关联的字典（包括任何所需的数据）。例如，在添加节点时，您可以向该字典中添加自定义数据。

import networkx as nx

def nmatch(n1, n2):
    return n1==n2

G=nx.DiGraph()
G.add_node(1, id=1)
G.add_node(2, id=2)
G.add_node(3, id=3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1, id=1)
G2.add_node(2, id=2)
G2.add_node(3, id=3)
G2.add_edges_from([(3, 2),(2,1)])


nx.graph_edit_distance(G,G2, node_match=nmatch)

返回2，因为您可以执行2个边缘替换。如果需要结果为4（2个插入，2个删除），则可以增加替换成本。

- Tomáš Zahradníček

---

运行您的算法，奇怪的是结果仍然是0.0而不是2 - 这可能是什么原因？ - Johannes

对我来说，也许是Python或networkx版本。分别为3.7.2和2.3。你可以尝试在nmatch中添加一些调试打印代码，以查看什么被认为是相等的（只有9个比较中的3个应该是真的）。此外，该代码并没有返回任何内容（最后一个语句抛弃了返回值），所以也许你没有编辑所有必要的内容或没有分配变量。 - Tomáš Zahradníček

Answer 2

这是另一种解决方案，可以产生2

import networkx as nx

G=nx.DiGraph()
G.add_node(1, id=1)
G.add_node(2, id=2)
G.add_node(3, id=3)
G.add_edges_from([(1, 2),(2,3)])


G2=nx.DiGraph()
G2.add_node(1, id=1)
G2.add_node(2, id=2)
G2.add_node(3, id=3)
G2.add_edges_from([(3, 2),(2,1)])

# arguments
# arguments for nodes
def node_subst_cost(node1, node2):
    # check if the nodes are equal, if yes then apply no cost, else apply 1
    if node1 == node2:
        return 0
    return 1

def node_del_cost(node):
    return 1  # here you apply the cost for node deletion

def node_ins_cost(node):
    return 1  # here you apply the cost for node insertion

# arguments for edges
def edge_subst_cost(edge1, edge2):
    # check if the edges are equal, if yes then apply no cost, else apply 3
    if edge1==edge2:
        return 0
    return 1

def edge_del_cost(node):
    return 1  # here you apply the cost for edge deletion

def edge_ins_cost(node):
    return 1  # here you apply the cost for edge insertion

paths, cost = nx.optimal_edit_paths(
    G,
    G2,
    node_subst_cost=node_subst_cost,
    node_del_cost=node_del_cost,
    node_ins_cost=node_ins_cost,
    edge_subst_cost=edge_subst_cost,
    edge_del_cost=edge_del_cost,
    edge_ins_cost=edge_ins_cost
)

print(cost)

如果你在 Python 2.7 上运行它，请将以下行添加到头部

# This Python file uses the following encoding: utf-8
from __future__ import print_function, unicode_literals
from __future__ import absolute_import, division 

- Olha Kholod