Exact Graph Pattern Matching:Applications,Progress and Prospects

Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.

Inexact graph matching using a hierarchy of matching processes

Inexact graph matching algorithms have proved to be useful in many applications,such as character recognition,shape analysis,and image analysis. Inexact graph matching is,however,inherently an NP-hard problem with exponential computational complexity. Much of the previous research has focused on solving this problem using heuristics or estimations. Unfortunately,many of these techniques do not guarantee that an optimal solution will be found. It is the aim of the proposed algorithm to reduce the complexity of the inexact graph matching process,while still producing an optimal solution for a known application. This is achieved by greatly simplifying each individual matching process,and compensating for lost robustness by producing a hierarchy of matching processes. The creation of each matching process in the hierarchy is driven by an application-specific criterion that operates at the subgraph scale. To our knowledge,this problem has never before been approached in this manner. Results show that the proposed algorithm is faster than two existing methods based on graph edit operations.The proposed algorithm produces accurate results in terms of matching graphs,and shows promise for the application of shape matching. The proposed algorithm can easily be extended to produce a sub-optimal solution if required.

Multi-Target Track-Correlation Algorithm of the Graph-Matching-Based Sensor Network

For the problem of track correlation failure under the influence of sensor system deviation in wireless sensor networks,a new track correlation method which is based on relative positional relation chart matching is proposed.This method approximately simulates the track correlation determination process using artificial data,and integrally matches the relative position relation between multiple targets in the common measuring space of various sensors in order to fulfill the purpose of multi-target track correlation.The simulation results show that this method has high correlation accuracy and robustness.

Bin-scanning:Segmentation of X-ray CT volume of binned parts using Morse skeleton graph of distance transform

X-ray CT scanners,due to the transmissive nature of X-rays,have enabled the non-destructive evaluation of industrial products,even inside their bodies.In light of its effectiveness,this study introduces a new approach to accelerate the inspection of many mechanical parts with the same shape in a bin.The input to this problem is a volumetric image(i.e.,CT volume)of many parts obtained by a single CT scan.We need to segment the parts in the volume to inspect each of them;however,random postures and dense contacts of the parts prohibit part segmentation using traditional template matching.To address this problem,we convert both the scanned volumetric images of the template and the binned parts to simpler graph structures and solve a subgraph matching problem to segment the parts.We perform a distance transform to convert the CT volume into a distance field.Then,we construct a graph based on Morse theory,in which graph nodes are located at the extremum points of the distance field.The experimental evaluation demonstrates that our fully automatic approach can detect target parts appropriately,even for a heap of 50 parts.Moreover,the overall computation can be performed in approximately 30 min for a large CT volume of approximately 2000×2000×1000 voxels.

Graphs Isomorphic to Their Maximum Matching Graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.

Fuzzy-Constrained Graph Pattern Matching in Medical Knowledge Graphs

The research on graph pattern matching(GPM) has attracted a lot of attention. However, most of the research has focused on complex networks, and there are few researches on GPM in the medical field. Hence, with GPM this paper is to make a breast cancer-oriented diagnosis before the surgery. Technically, this paper has firstly made a new definition of GPM, aiming to explore the GPM in the medical field, especially in Medical Knowledge Graphs(MKGs). Then, in the specific matching process, this paper introduces fuzzy calculation, and proposes a multi-threaded bidirectional routing exploration(M-TBRE) algorithm based on depth first search and a two-way routing matching algorithm based on multi-threading. In addition, fuzzy constraints are introduced in the M-TBRE algorithm, which leads to the Fuzzy-M-TBRE algorithm. The experimental results on the two datasets show that compared with existing algorithms, our proposed algorithm is more efficient and effective.

Matching user identities across social networks with limited profile data

Privacy preservation is a primary concern in social networks which employ a variety of privacy preservations mechanisms to preserve and protect sensitive user information including age,location,education,interests,and others.The task of matching user identities across different social networks is considered a challenging task.In this work,we propose an algorithm to reveal user identities as a set of linked accounts from different social networks using limited user profile data,i.e,user-name and friendship.Thus,we propose a framework,ExpandUIL,that includes three standalone al-gorithms based on(i)the percolation graph matching in Ex-pand FullName algorithm,(i)a supervised machine learning algorithm that works with the graph embedding,and(ii)a combination of the two,ExpandUserLinkage algorithm.The proposed framework as a set of algorithms is significant as,(i)it is based on the network topology and requires only name feature of the nodes,(i)it requires a considerably low initial seed,as low as one initial seed suffices,(ii)it is iterative and scalable with applicability to online incoming stream graphs,and(iv)it has an experimental proof of stability over a real ground-truth dataset.Experiments on real datasets,Instagram and VK social networks,show upto 75%recall for linked ac-counts with 96%accuracy using only one given seed pair.

The Characterization of p-factor-critical Graphs

A graph G is said to be p-factor-critical if G-u1-u2-···-up has a perfect matching for any u1,u2,···,up∈V(G).The concept of p-factor-critical is a generalization of the concepts of factor-critical and bicritical for p=1 and p=2,respectively.Heping Zhang and Fuji Zhang[Construction for bicritical graphs and k-extendable bipartite graphs,Discrete Math.,306(2006)1415–1423]gave a concise structure characterization of bicritical graphs.In this paper,we present the characterizations of p-factor-critical graphs and minimal p-factorcritical graphs for p≥2.As an application,we also obtain a class of graphs which are minimal p-factor-critical for p≥1.

Heuristic multistep attack scenarios construction based on kill chain

Network attacks evolved from single-step and simple attacks to complex multistep attacks.Current methods of multistep attack detection usually match multistep attacks from intrusion detection systems(IDS)alarms based on the correlation between attack steps.However,IDS has false negatives and false positives,which leads to incomplete or incorrect multistep attacks.Association based on simple similarity is difficult to obtain an accurate attack cluster,while association based on prior knowledge such as attack graphs is difficult to guarantee a complete attack knowledge base.To solve the above problems,a heuristic multistep attack scenarios construction method based on the kill chain(HMASCKC)model was proposed.The attack model graph can be obtained from dual data sources and heuristic multistep attack scenarios can be obtained through graph matching.The model graph of the attack and the predicted value of the next attack are obtained by calculating the matching value.And according to the purpose of the multistep attack,the kill chain model is used to define the initial multistep attack model,which is used as the initial graph for graph matching.Experimental results show that HMASCKC model can better fit the multistep attack behavior,the effect has some advantages over the longest common subsequence(LCS)algorithm,which can close to or match the prediction error of judge evaluation of attack intension(JEAN)system.The method can make multistep attack model matching for unknown attacks,so it has some advantages in practical application.

Communicating Is Crowdsourcing: Wi-Fi Indoor Localization with CSI-Based Speed Estimation

Numerous indoor localization techniques have been proposed recently to meet the intensive demand for location- based service （LBS）. Among them, the most popular solutions are the Wi-Fi fingerprint-based approaches. The core challenge is to lower the cost of fingerprint site-survey. One of the trends is to collect the piecewise data from clients and establish the radio map in crowdsourcing manner. However the low participation rate blocks the practical use. In this work, we propose a passive crowdsourcing channel state information （CSI） based indoor localization scheme, C2IL. Despite a crowdsourcing based approach, our scheme is totally transparent to the client and the only requirement is to connect to our 802.11n access points （APs）. C2IL is built upon an innovative method to accurately estimate the moving speed solely based on 802.11n CSI. Knowing the walking speed of a client and its surrounding APs, a graph matching algorithm is employed to extract the received signal strength （RSS） fingerprints and establish the fingerprint map. For localization phase, we design a trajectory clustering based localization algorithm to provide precise real-time indoor localization and tracking. We develop and deploy a practical working system of C2IL in a large office environment. Extensive evaluations indicate that the error of speed estimation is within 3%, and the localization error is within 2 m at 80% time in a very complex indoor environment.

Codimensional matrix pairing perspective of BYY harmony learning:hierarchy of bilinear systems,joint decomposition of data-covariance,and applications of network biology

One paper in a preceding issue of this journal has introduced the Bayesian Ying-Yang(BYY)harmony learning from a perspective of problem solving,parameter learning,and model selection.In a complementary role,the paper provides further insights from another perspective that a co-dimensional matrix pair(shortly co-dim matrix pair)forms a building unit and a hierarchy of such building units sets up the BYY system.The BYY harmony learning is re-examined via exploring the nature of a co-dim matrix pair,which leads to improved learning performance with refined model selection criteria and a modified mechanism that coordinates automatic model selection and sparse learning.Besides updating typical algorithms of factor analysis(FA),binary FA(BFA),binary matrix factorization(BMF),and nonnegative matrix factorization(NMF)to share such a mechanism,we are also led to(a)a new parametrization that embeds a de-noise nature to Gaussian mixture and local FA(LFA);(b)an alternative formulation of graph Laplacian based linear manifold learning;(c)a codecomposition of data and covariance for learning regularization and data integration;and(d)a co-dim matrix pair based generalization of temporal FA and state space model.Moreover,with help of a co-dim matrix pair in Hadamard product,we are led to a semi-supervised formation for regression analysis and a semi-blind learning formation for temporal FA and state space model.Furthermore,we address that these advances provide with new tools for network biology studies,including learning transcriptional regulatory,Protein-Protein Interaction network alignment,and network integration.