文章简介：

1. 文章标题：
   New binary linear programming formulation to compute the graph edit distance
2. 论文初稿链接
3. 文章来源：2017 期刊 Pattern Recognition

文章思路

  精确计算GED是NP-Hard问题，需要的时间是指数级。因此，设定计算的GED的下限是十分必要的，可以在下界的基础上更加容易判定图GED。(这里的lower bound:不是过滤的意思，是指最小计算的运算量)文章以二进制数的线性规划问题，模拟了GED的计算过程，把计算成本的{0,1}的离散值分解为（0,1）区间的连续值。文中将编辑距离的六种操作都定义为取值为0或者1的变量：

并且给出了编辑距离的目标函数：

以及基于目标函数的约束条件：

三种约束：

1. 顶点映射
2. 边映射
3. 考虑图的拓扑结构

基于约束条件，可以通过F1和F2求解:
F1:

F2:

文章缺点：

  凡是计算GED的问题，都是通过计算编辑成本的方法。如，定义$dis(G_1,G_2)$dis(G1​,G2​)=${\sum_{i=0}}^{p}cost(operation(i))$∑i=0​pcost(operation(i))，类似的成本公式，在公式中考虑到了顶点和边之间的六种操作。但是，编辑距离在度量相似度时候，不能考虑到顶点的结构信息，比如一个顶点的出度和入度信息，即拓扑信息。这是不精准的；另外一个方面，应该改变cost(operation)的权重，不应该设定统一的代价，因为每个操作的复杂情况根据其拓扑环境来讲是不同的。