Kronecker product graph matching

In this paper the Interpolator-based Kronecker product graph matching (IBKPGM) algorithm for performing attributed graph matching is presented. The IBKPGM algorithm is based on the Kronecker product graph matching (KPGM) formulation. This new formulation incorporates a general approach to a wide class of graph matching problems based on attributed graphs, allowing the structure of the graphs to be based on multiple sets of attributes. Salient features of the IBKPGM algorithm are that no assumption is made about the adjacency structure of the graphs to be matched, and that the explicit calculation of compatibility values between all vertices of the reference and input graphs as well as between all edges of the reference and input graphs are avoided.     

A fuzzy graph matching approach in intelligence analysis and maintenance of continuous situational awareness

In intelligence analysis a situation of interest is commonly obscured by the more voluminous amount of unimportant data. This data can be broadly divided into two categories, hard or physical sensor data and soft or human observed data. Soft intelligence data is collected by humans through human interaction, or human intelligence (HUMINT). The value and difficulty in manual processing of these observations due to the volume of available data and cognitive limitations of intelligence analysts necessitate an information fusion approach toward their understanding. The data representation utilized in this work is an attributed graphical format. The uncertainties, size and complexity of the connections within this graph make accurate assessments difficult for the intelligence analyst. While this graphical form is easier to consider for an intelligence analyst than disconnected multi-source human and sensor reports, manual traversal for the purpose of obtaining situation awareness and accurately answering priority information requests (PIRs) is still infeasible. To overcome this difficulty an automated stochastic graph matching approach is developed. This approach consists of three main processes: uncertainty alignment, graph matching result initialization and graph matching result maintenance. Uncertainty alignment associates with raw incoming observations a bias adjusted uncertainty representation representing the true value containing spread of the observation. The graph matching initialization step provides template graph to data graph matches for a newly initialized situation of interest (template graph). Finally, the graph matching result maintenance algorithm continuously updates graph matching results as incoming observations augment the cumulative data graph. Throughout these processes the uncertainties present in the original observations and the template to data graph matches are preserved, ultimately providing an indication of the uncertainties present in the current situation assessment. In addition to providing the technical details of this approach, this paper also provides an extensive numerical testing section which indicates a significant performance improvement of the proposed algorithm over a leading commercial solver.     

A graph isomorphism algorithm for object recognition

We present an algorithm to solve the graph isomorphism problem for the purpose of object recognition. Objects, such as those which exist in a robot workspace, may be represented by labelled graphs (graphs with attributes on their nodes and/or edges). Thereafter, object recognition is achieved by matching pairs of these graphs. Assuming that all objects are sufficiently different so that their corresponding representative graphs are distinct, then given a new graph, the algorthm efficiently finds the isomorphic stored graph (if it exists). The algorithm consists of three phases: preprocessing, link construction, and ambiguity resolution. Results from experiments on a wide variety and sizes of graphs are reported. Results are also reported for experiments on recognising graphs that represent protein molecules. The algorithm works for all types of graphs except for a class of highly ambiguous graphs which includes strongly regular graphs. However, members of this class are detected in polynomial time, which leaves the option of switching to a higher complexity algorithm if desired.     

Recognizing hand gestures using the weighted elastic graph matching (WEGM) method

This paper proposes a weighted scheme for elastic graph matching hand posture recognition. Visual features scattered on the elastic graph are assigned corresponding weights according to their relative ability to discriminate between gestures. The weights' values are determined using adaptive boosting. A dictionary representing the variability of each gesture class is expressed in the form of a bunch graph. The positions of the nodes in the bunch graph are determined using three techniques: manually, semi-automatically, and automatically. Experimental results also show that the semi-automatic annotation method is efficient and accurate in terms of three performance measures; assignment cost, accuracy, and transformation error. In terms of the recognition accuracy, our results show that the hierarchical weighting on features has more significant discriminative power than the classic method (uniform weighting). The hierarchical elastic graph matching (WEGM) approach was used to classify a lexicon of ten hand postures, and it was found that the poses were recognized with a recognition accuracy of 97.08% on average. Using the weighted scheme, computing cycles can be decreased by only computing the features for those nodes whose weight is relatively high and ignoring the remaining nodes. It was found that only 30% of the nodes need to be computed to obtain a recognition accuracy of over 90%.     

An eigendecomposition approach to weighted graph matching problems

An approximate solution to the weighted-graph-matching problem is discussed for both undirected and directed graphs. The weighted-graph-matching problem is that of finding the optimum matching between two weighted graphs, which are graphs with weights at each arc. The proposed method uses an analytic instead of a combinatorial or iterative approach to the optimum matching problem. Using the eigendecompositions of the adjacency matrices (in the case of the undirected-graph-matching problem) or Hermitian matrices derived from the adjacency matrices (in the case of the directed-graph-matching problem), a matching close to the optimum can be found efficiently when the graphs are sufficiently close to each other. Simulation results are given to evaluate the performance of the proposed method     

一种基于RDF图的本体匹配方法

本体匹配是建立两个本体之间映射关系的过程,一个高效、严格的相似度计算方法是本体匹配的前提条件,为此提出了一种基于RDF图匹配的方法。该方法用RDF图表示本体,使本体间的匹配问题转化为RDF图的匹配问题,并利用匹配树表示匹配的状态,通过匹配树计算出两个本体中各实体之间的相似度,进而得到两个本体之间的映射关系。实验结果表明,该方法在查全率和查准率方面都有很好的表现。     

A greedy approach to compute a minimum cycle basis of a directed graph

We consider the problem of computing a minimum cycle basis of a directed graph with m arcs and n nodes. We adapt the greedy approach proposed by Horton [A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 358] and hereby obtain a very simple exact algorithm of complexity , being as fast as the first algorithm proposed for this problem [A polynomial time algorithm for minimum cycle basis in directed graphs, Kurt Mehlhorn's List of Publications, 185, MPI, Saarbrücken, 2004, http://www.mpi-sb.mpg.de/~mehlhorn/ftp/DirCycleBasis.ps; Proc. STACS 2005, submitted for publication]. Moreover, the speed-up of Golynski and Horton [A polynomial time algorithm to find the minimum cycle basis of a regular matroid, in: M. Penttonen, E. Meineche Schmidt (Eds.), SWAT 2002, Lecture Notes in Comput. Sci., vol. 2368, Springer, Berlin, 2002, pp. 200-209] applies to this problem, providing an exact algorithm of complexity , in particular . Finally, we prove that these greedy approaches fail for more specialized subclasses of directed cycle bases.     

Generalized median graph computation by means of graph embedding in vector spaces

The median graph has been presented as a useful tool to represent a set of graphs. Nevertheless its computation is very complex and the existing algorithms are restricted to use limited amount of data. In this paper we propose a new approach for the computation of the median graph based on graph embedding. Graphs are embedded into a vector space and the median is computed in the vector domain. We have designed a procedure based on the weighted mean of a pair of graphs to go from the vector domain back to the graph domain in order to obtain a final approximation of the median graph. Experiments on three different databases containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results. These experiments on real data open the door to the application of the median graph to a number of more complex machine learning algorithms where a representative of a set of graphs is needed.     

A sparse nonnegative matrix factorization technique for graph matching problems

Graph matching problem that incorporates pairwise constraints can be cast as an Integer Quadratic Programming (IQP). Since it is NP-hard, approximate methods are required. In this paper, a new approximate method based on nonnegative matrix factorization with sparse constraints is presented. Firstly, the graph matching is formulated as an optimization problem with nonnegative and sparse constraints, followed by an efficient algorithm to solve this constrained problem. Then, we show the strong relationship between the sparsity of the relaxation solution and its effectiveness for graph matching based on our model. A key benefit of our method is that the solution is sparse and thus can approximately impose the one-to-one mapping constraints in the optimization process naturally. Therefore, our method can approximate the original IQP problem more closely than other approximate methods. Extensive and comparative experimental results on both synthetic and real-world data demonstrate the effectiveness of our graph matching method.     

A simple approximation algorithm for the weighted matching problem

We present a linear time approximation algorithm with a performance ratio of 1/2 for finding a maximum weight matching in an arbitrary graph. Such a result is already known and is due to Preis [STACS'99, Lecture Notes in Comput. Sci., Vol. 1563, 1999, pp. 259-269]. Our algorithm uses a new approach which is much simpler than the one given by Preis and needs no amortized analysis for its running time.     

Fast parallel algorithms for graph similarity and matching

This paper addresses the problem of global graph alignment on supercomputer-class clusters. We define the alignment of two graphs, as a mapping of each vertex in the first graph to a unique vertex in the second graph so as to optimize a given similarity-based cost function.¹ Using a state of the art serial algorithm for the computation of vertex similarity scores called Network Similarity Decomposition (NSD), we derive corresponding parallel formulations. Coupling this parallel similarity algorithm with a parallel auction-based bipartite matching technique, we obtain a highly efficient and scalable graph matching pipeline. We validate the performance of our integrated approach on a large parallel platform and on diverse graph instances (including Protein Interaction, Wikipedia and Web networks). Experimental results demonstrate that our algorithms scale to large machine configurations (thousands of cores) and problem instances, enabling the alignment of networks of sizes two orders of magnitude larger than reported in the current literature.     

An improved graph cut algorithm in stereo matching

In stereo matching tasks, the matching effect is often very poor when the texture of the region is weak or repeated. To solve this problem, an improved Graph Cut stereo matching algorithm based on Census transform is proposed. The Hamming distance of the corresponding pixels in the left and right images after Census transform is introduced as the similarity measure in the data term of the energy function. In this way, the dependence on the pixel value is reduced. The stereo matching experiments are implemented on the standard images of Middlebury stereo benchmark and the real scene images, and it demonstrates that our algorithm is robust and can obtain better performance in weak texture or repeated texture region.     

Detecting logical relationships in mechanical,electrical, and plumbing (MEP) systems with BIM using graph matching

The increasingly complex design has gained difficulty in conducting the rule compliance checking for the Mechanical, Electrical and Plumbing (MEP) system in the design phase. Useful rule-checking systems could contribute to a quicker project delivery time. Currently, an efficient method for checking the logical relationship is still lacking. This study aims to propose an MEP rule checking framework using the subgraph matching technology. First, the MEP components in the BIM model are extracted by utilizing the application programming interface (API), and a graph database is established with point-based and curve-based instances being nodes and relationships, respectively. Second, the graph database is simplified to increase the speed of graph matching. Third, the rules, which regulate how the MEP components should be connected, are represented by a knowledge graph. Finally, rule checking is achieved by comparing the graph database against the knowledge graph, and the critical path in a sub-system is detected by calculating the betweenness centrality. A case study with a rail station is used to evaluate the approach where the overall model checking and rule checking are conducted on the original and simplified graph databases sequentially. The results show that the proposed approach could achieve the rule compliance checking at a high speed, and 6 unconnected instances along with 155 problematic pipe fittings have been found. Besides, the critical path for the selected ACS system is from the water-cooled chiller to the condenser water pump. The proposed framework could help in the overall model checking and rule checking process, improving the efficiency of BIM engineers. This research demonstrates that converting a BIM model into a graph database can benefit conventional BIM analysis methods by incorporating advanced technologies (e.g., artificial intelligence) to enable a more flexible and accurate MEP design process.     

A Riemannian approach to graph embedding

In this paper, we make use of the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. To embark on this study, we review some of the basics of Riemannian geometry and explain the relationship between the Laplace-Beltrami operator and the graph Laplacian. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths on the manifold between nodes. For the particular case of a constant sectional curvature surface, we use the Kruskal coordinates to compute edge weights that are proportional to the geodesic distance between points. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold. To do this, we develop a method that can be used to perform double centring on the Laplacian matrix computed from the edge-weights. The embedding coordinates are given by the eigenvectors of the centred Laplacian. With the set of embedding coordinates at hand, a number of graph manipulation tasks can be performed. In this paper, we are primarily interested in graph-matching. We recast the graph-matching problem as that of aligning pairs of manifolds subject to a geometric transformation. We show that this transformation is Pro-crustean in nature. We illustrate the utility of the method on image matching using the COIL database.     

Inexact graph matching for structural pattern recognition

This paper is concerned with the inexact matching of attributed, relational graphs for structural pattern recognition. The matching procedure is based on a state space search utilizing heuristic information. Some experimental results are reported.     

A linear-time algorithm to compute a MAD tree of an interval graph

The average distance of a connected graph G is the average of the distances between all pairs of vertices of G. We present a linear time algorithm that determines, for a given interval graph G, a spanning tree of G with minimum average distance (MAD tree). Such a tree is sometimes referred to as a minimum routing cost spanning tree.     

Structure and attribute index for approximate graph matching in large graphs

The increasing popularity of graph data in various domains has lead to a renewed interest in developing efficient graph matching techniques, especially for processing large graphs. In this paper, we study the problem of approximate graph matching in a large attributed graph. Given a large attributed graph and a query graph, we compute a subgraph of the large graph that best matches the query graph. We propose a novel structure-aware and attribute-aware index to process approximate graph matching in a large attributed graph. We first construct an index on the similarity of the attributed graph, by partitioning the large search space into smaller subgraphs based on structure similarity and attribute similarity. Then, we construct a connectivity-based index to give a concise representation of inter-partition connections. We use the index to find a set of best matching paths. From these best matching paths, we compute the best matching answer graph using a greedy algorithm. Experimental results on real datasets demonstrate the efficiency of both index construction and query processing. We also show that our approach attains high-quality query answers.     

HEGM: A hierarchical elastic graph matching for hand gesture recognition

A hierarchical scheme for elastic graph matching applied to hand gesture recognition is proposed. The proposed algorithm exploits the relative discriminatory capabilities of visual features scattered on the images, assigning the corresponding weights to each feature. A boosting algorithm is used to determine the structure of the hierarchy of a given graph. The graph is expressed by annotating the nodes of interest over the target object to form a bunch graph. Three annotation techniques, manual, semi-automatic, and automatic annotation are used to determine the position of the nodes. The scheme and the annotation approaches are applied to explore the hand gesture recognition performance. A number of filter banks are applied to hand gestures images to investigate the effect of using different feature representation approaches. Experimental results show that the hierarchical elastic graph matching (HEGM) approach classified the hand posture with a gesture recognition accuracy of 99.85% when visual features were extracted by utilizing the Histogram of Oriented Gradient (HOG) representation. The results also provide the performance measures from the aspect of recognition accuracy to matching benefits, node positions correlation and consistency on three annotation approaches, showing that the semi-automatic annotation method is more efficient and accurate than the other two methods.     

A genetic algorithm and its parallelization for graph matching with similarity measures

Graph matching and similarity measures of graphs have many applications to pattern recognition, machine vision in robotics, and similarity-based approximate reasoning in artificial intelligence. This paper proposes a method of matching and a similarity measure between two directed labeled graphs. We define the degree of similarity, the similar correspondence, and the similarity map which denotes the matching between the graphs. As an approximate computing method, we apply genetic algorithms (GA) to find a similarity map and compute the degree of similarity between graphs. For speed, we make parallel implementations in almost all steps of the GA. We have implemented the sequential GA and the parallel GA in C programs, and made simulations for both GAs. The simulation results show that our method is efficient and useful. This work was presented, in part, at the Second International Symposium on Artificial Life and Robotics, Oita Japan, February 18–20, 1997