Matching graphs with unique node labels

A special class of graphs is introduced in this paper. The graphs belonging to this class are characterised by the existence of unique node labels. A number of matching algorithms for graphs with unique node labels are developed. It is shown that problems such as graph isomorphism, subgraph isomorphism, maximum common subgraph (MCS) and graph edit distance (GED) have a computational complexity that is only quadratic in the number of nodes. Moreover, computing the median of a set of graphs is only linear in the cardinality of the set. In a series of experiments, it is demonstrated that the proposed algorithms run very fast in practice. The considered class makes the matching of large graphs, consisting of thousands of nodes, computationally tractable. We also discuss an application of the considered class of graphs and related matching algorithms to the classification and detection of abnormal events in computer networks.     

Automatic learning of cost functions for graph edit distance

Graph matching and graph edit distance have become important tools in structural pattern recognition. The graph edit distance concept allows us to measure the structural similarity of attributed graphs in an error-tolerant way. The key idea is to model graph variations by structural distortion operations. As one of its main constraints, however, the edit distance requires the adequate definition of edit cost functions, which eventually determine which graphs are considered similar. In the past, these cost functions were usually defined in a manual fashion, which is highly prone to errors. The present paper proposes a method to automatically learn cost functions from a labeled sample set of graphs. To this end, we formulate the graph edit process in a stochastic context and perform a maximum likelihood parameter estimation of the distribution of edit operations. The underlying distortion model is learned using an Expectation Maximization algorithm. From this model we finally derive the desired cost functions. In a series of experiments we demonstrate the learning effect of the proposed method and provide a performance comparison to other models.     

A novel edge-centric approach for graph edit similarity computation

Graph similarity is an important notion with many applications. Graph edit distance is one of the most flexible graph similarity measures available. The main problem with this measure is that in practice it can only be computed for small graphs due to its exponential time complexity. This paper addresses the high complexity of graph edit distance computations. Specifically, we present CSI_GED, a novel edge-centric approach for computing graph edit distance through common sub-structure isomorphisms enumeration. CSI_GED utilizes backtracking search combined with a number of heuristics to reduce memory requirements and quickly prune away a large portion of the mapping search space. Experiments show that CSI_GED is highly efficient for computing graph edit distance; it outperforms the state-of-the-art methods by over three orders of magnitude. It also shows that CSI_GED scales the computation gracefully to larger and distant graphs on which current methods fail to run. Moreover, we evaluated CSI_GED as a stand-alone graph edit similarity search query method. The experiments show that CSI_GED is effective and scalable, and outperforms the state-of-the-art indexing-based methods by over two orders of magnitude.     

Self-organizing maps for learning the edit costs in graph matching.

Although graph matching and graph edit distance computation have become areas of intensive research recently, the automatic inference of the cost of edit operations has remained an open problem. In the present paper, we address the issue of learning graph edit distance cost functions for numerically labeled graphs from a corpus of sample graphs. We propose a system of self-organizing maps (SOMs) that represent the distance measuring spaces of node and edge labels. Our learning process is based on the concept of self-organization. It adapts the edit costs in such a way that the similarity of graphs from the same class is increased, whereas the similarity of graphs from different classes decreases. The learning procedure is demonstrated on two different applications involving line drawing graphs and graphs representing diatoms, respectively.     

Edit distance-based kernel functions for structural pattern classification

A common approach in structural pattern classification is to define a dissimilarity measure on patterns and apply a distance-based nearest-neighbor classifier. In this paper, we introduce an alternative method for classification using kernel functions based on edit distance. The proposed approach is applicable to both string and graph representations of patterns. By means of the kernel functions introduced in this paper, string and graph classification can be performed in an implicit vector space using powerful statistical algorithms. The validity of the kernel method cannot be established for edit distance in general. However, by evaluating theoretical criteria we show that the kernel functions are nevertheless suitable for classification, and experiments on various string and graph datasets clearly demonstrate that nearest-neighbor classifiers can be outperformed by support vector machines using the proposed kernel functions.     

Structure-based graph distance measures of high degree of precision

In recent years, evaluating graph distance has become more and more important in a variety of real applications and many graph distance measures have been proposed. Among all of those measures, structure-based graph distance measures have become the research focus due to their independence of the definition of cost functions. However, existing structure-based graph distance measures have low degree of precision because only node and edge information of graphs are employed in these measures. To improve the precision of graph distance measures, we define substructure abundance vector (SAV) to capture more substructure information of a graph. Furthermore, based on SAV, we propose unified graph distance measures which are generalization of the existing structure-based graph distance measures. In general, the unified graph distance measures can evaluate graph distance in much finer grain. We also show that unified graph distance measures based on occurrence mapping and some of their variants are metrics. Finally, we apply the unified graph distance metric and its variants to the population evolution analysis and construct distance graphs of marker networks in three populations, which reflect the single nucleotide polymorphism (SNP) linkage disequilibrium (LD) differences among these populations.     

A fast technique for comparing graph representations with applications to performance evaluation

Finding efficient, effective ways to compare graphs arising from recognition processes with their corresponding ground-truth graphs is an important step toward more rigorous performance evaluation.In this paper, we examine in detail the graph probing paradigm we first put forth in the context of our work on table understanding and later extended to HTML-coded Web pages. We present a formalism showing that graph probing provides a lower bound on the true edit distance between two graphs. From an empirical standpoint, the results of two simulation studies and an experiment using scanned pages show that graph probing correlates well with the latter measure. Moreover, our technique is very fast; graphs with tens or hundreds of thousands of vertices can be compared in mere seconds. Ease of implementation, scalability, and speed of execution make graph probing an attractive alternative for graph comparison.Received: 1 October 2002, Accepted: 15 January 2003, Published online: 6 February 2004Correspondence to: D. Lopresti     

Graph edit distance from spectral seriation

This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.     

A study of graph spectra for comparing graphs and trees

The spectrum of a graph has been widely used in graph theory to characterise the properties of a graph and extract information from its structure. It has also been employed as a graph representation for pattern matching since it is invariant to the labelling of the graph. There are, however, a number of potential drawbacks in using the spectrum as a representation of a graph. Firstly, more than one graph may share the same spectrum. It is well known, for example, that very few trees can be uniquely specified by their spectrum. Secondly, the spectrum may change dramatically with a small change structure.There are a wide variety of graph matrix representations from which the spectrum can be extracted. Among these are the adjacency matrix, combinatorial Laplacian, normalised Laplacian and unsigned Laplacian. Spectra can also be derived from the heat kernel matrix and path length distribution matrix. The choice of matrix representation clearly has a large effect on the suitability of spectrum in a number of pattern recognition tasks.In this paper we investigate the performance of the spectra as a graph representation in a variety of situations. Firstly, we investigate the cospectrality of the various matrix representations over large graph and tree sets, extending the work of previous authors. We then show that the Euclidean distance between spectra tracks the edit distance between graphs over a wide range of edit costs, and we analyse the accuracy of this relationship. We then use the spectra to both cluster and classify the graphs and demonstrate the effect of the graph matrix formulation on error rates. These results are produced using both synthetic graphs and trees and graphs derived from shape and image data.     

一种基于鲁棒Hausdorff距离的目标匹配算法

在传统的基于边缘位置的Hausdorff距离匹配的基础上,将边缘的梯度信息引入到距离度量当中,构造了一种新的三维距离函数。在此基础上,提出了一种鲁棒的三维Hausdorff距离及其目标匹配算法,采用粗匹配与精匹配相结合的两步匹配策略有效解决了由距离度量维数增加所导致的算法复杂性增大的问题。实验表明,该算法相对于传统的基于边缘位置的Hausdorff距离目标匹配算法在鲁棒性上有很大的提高。     

On the Impact of Using Utilities Rather than Costs for Graph Matching

The concept of graph edit distance constitutes one of the most flexible graph matching paradigms available. The major drawback of graph edit distance, viz. the exponential time complexity, has been recently overcome by means of a reformulation of the edit distance problem to a linear sum assignment problem. However, the substantial speed up of the matching is also accompanied by an approximation error on the distances. Major contribution of this paper is the introduction of a transformation process in order to convert the underlying cost model into a utility model. The benefit of this transformation is that it enables the integration of additional information in the assignment process. We empirically confirm the positive effects of this transformation on five benchmark graph sets with respect to the accuracy and run time of a distance based classifier.     

基于l1范数和k近邻叠加图的半监督分类算法*

为了构造一个能够较好反映数据真实分布的图以提高分类性能,文中提出基于l¹范数和k近邻叠加图的半监督分类算法。首先构造一个l¹范数图,作为主图,然后构造一个k近邻图,作为辅图,最后将二者按一定比例叠加,得到l¹范数和k近邻叠加(LNKNNS)图。实验中选择标记样本比例从5%到25%,将基于LNKNNS图的半监督分类算法在USPS数据库上对比其它图(指数权重图、k近邻图、低秩表示图和l¹范数图)的算法。实验表明,文中算法的分类识别率更高,更适合基于图的半监督学习。     

图模型匹配:一种新的凹松弛函数及算法

将问题中的置换矩阵放松为双随机矩阵是近年来近似图匹配算法的一个重要发展方向. 它的本质在于将离散的图匹配问题转换成一个连续优化问题,而一般来讲, 相对于离散优化,连续优化问题的近似求解将更为容易. 但随之带来的一个问题是如何有效地将连续优化得到的双随机矩阵重新映射回一个置换矩阵. 最近文献中提出了一种针对于无向无自环图的凹松弛(Concave relaxation)函数,使得算法中的双随机矩阵可以平滑地收敛到一个置换矩阵, 并得到优异的匹配精度.但除了无向且无自环图,文献中还没有针对其他类型图模型的凹松弛函数. 本文提出一种针对于有向无自环图匹配问题的凹松弛函数, 并在此基础上给出一种图匹配算法.大量对比实验验证了本文提出模型及算法的有效性.     

A survey of graph edit distance

Inexact graph matching has been one of the significant research foci in the area of pattern analysis. As an important way to measure the similarity between pairwise graphs error-tolerantly, graph edit distance (GED) is the base of inexact graph matching. The research advance of GED is surveyed in order to provide a review of the existing literatures and offer some insights into the studies of GED. Since graphs may be attributed or non-attributed and the definition of costs for edit operations is various, the existing GED algorithms are categorized according to these two factors and described in detail. After these algorithms are analyzed and their limitations are identified, several promising directions for further research are proposed.     

BIM 模型相似度计算方法

针对从业者不论是想从本地模型库还是线上共享网站获取所需的BIM 模型只能靠 逐个查找、人工识读的方法,而模型的数量越来越多,获取符合需求的模型需要花费大量的时 间和人力的问题,提出了一种构件级BIM 模型相似度计算方法。从模型的构件出发,以BIM 通用交互格式工业基础类(IFC)文件作数据源,以通用数据标准IFC 2×3 为数据基础,首先提取 模型中构件的几何信息、语义信息等,并利用改进的方向包围盒(OBB)碰撞检测算法查找相连 构件;然后以构件为顶点、构件间连接关系为边将BIM 模型构建为邻接图模型,并用图编辑距 离算法计算邻接图模型的编辑距离;最后即可计算出不同模型之间的相似度。该方法以构件级 BIM 模型的相似度为依据可以大大提升BIM 模型的检索速度与准确率。     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

基于相似度加权的自适应HD算法

Hausdorff距离(Hausdorff distance, HD)是一种点集与点集之间的距离测度, 常用于目标物体的匹配、跟踪和识别等. 本文在分析经典HD及改进算法的基础上, 提出了一种基于相似度加权的自适应HD (Adaptive Hausdarff distance, AHD)算法. AHD算法利用不同点到点集的最小距离的个数作为匹配相似度的测量, 并舍弃对判断匹配几乎没有作用的较大的点到点集的最小距离值; 同时根据点到点集的最小距离自适应选择权值, 从而得到一种基于相似度测量加权系数; 通过利用部分点到点集的最小距离和基于相似度的加权平均, 既增强了算法的鲁棒性, 又尽可能地保证了算法的精度. 实验结果显示, AHD算法在匹配准确性、抵抗噪声和遮挡干扰等方面性能良好.     

基于最优传输的层次化图核

已有的图核大多关注图的局部属性,利用局部的拓扑特征构建图的相似性度量,忽略图的层次结构信息.为了解决这个问题,文中提出基于最优传输的层次化图核.首先,将每个图表示成层次化的图结构.在层次化图结构构建过程中,利用K-means聚类算法构造每层图的节点,节点间的概率连接作为图的边.然后,利用带有熵约束的最优传输计算两图的层次结构上每层图之间的最优传输距离.最后,基于最优传输距离计算基于最优传输的层次化图核.在6个真实图数据集上的实验表明,文中方法可提升分类性能.     

基于变迁图编辑距离的流程相似性算法

为了提高从企业模型库中查询检索模型的效率,提出一种基于变迁图编辑距离的流程相似性算法。首先,给出了变迁图的概念及其生成方法;其次,提出边的长度概念,且删除和插入边的代价由该边的长度决定,基于此定义出图编辑操作及其代价,并用节点匹配算法计算最小图编辑距离;然后,给出两个过程模型的相似性概念和计算方法;最后,通过实验验证了算法的正确性且满足七条相似性性质,并验证了变迁图编辑距离满足四条距离性质。