Search

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$-Path, Weighted $k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

Subgraph isomorphism is a well known NP-hard problem that is to find all the matched subgraphs of a query graph in a large target graph. The state-of-the-art GPU-based solution is the vertex-oriented joining strategy, which is proposed by GSI. It effectively solves the problem of parallel write conflicts by taking vertices as processing units. However, this strategy may result in load-imbalance and redundant memory transactions. Moreover, due to the limitation of GPU memory, extending the existing frameworks to large-scale graph is difficult. To solve the first problem, we design a new storage structure Level-CSR and a new partition-oriented joining strategy. To avoid the influence of vertices with large degrees, we divide the dense vertices in traditional CSR into several GPU-friendly tasks and store them in Level-CSR. Then, an efficient execution strategy is designed based on the partitioned tasks. The partition strategy can reduce the load imbalance caused by the irregularity of real-world graphs, and further reduce the redundant global memory access caused by the redundant neighbor set accessing. To solve the second problem, we design a unified-memory-based hybrid processing strategy to support out-of-GPU subgraph matching. By leveraging unified-memory-based data movement and active vertex-based access mode switching strategy, our hybrid strategy can leverage the large storage of host memory and achieve efficient data movement between GPU and CPU. Besides, to further improve the performance, we propose a well-directed filtering strategy by exploiting a property of real-world graphs. The experiments show that compared with the state-of-the-art GPU based solutions, our approach can effectively reduce the number of unrelated candidates, minimize memory transactions, and achieve load balance between processors. And our unified-memory-based hybrid processing strategy can outperform the single access mode-based strategy under different parameter settings.

Subgraph searching is an essential problem in graph databases, but it is also challenging due to the involved subgraph isomorphism NP-Complete sub-problem. Filter-Then-Verify (FTV) methods mitigate performance overheads by using an index to prune out graphs that do not fit the query in a filtering stage, reducing the number of subgraph isomorphism evaluations in a subsequent verification stage. Subgraph searching has to be applied to very large databases (tens of millions of graphs) in real applications such as molecular substructure searching. Previous surveys have identified the FTV solutions GraphGrepSX (GGSX) and CT-Index as the best ones for large databases (thousands of graphs), however they cannot reach reasonable performance on very large ones (tens of millions graphs). This paper proposes a generic approach for the distributed implementation of FTV solutions. Besides, three previous methods that improve the performance of GGSX and CT-Index are adapted to be executed in clusters. The evaluation shows how the achieved solutions provide a great performance improvement (between 70% and 90% of filtering time reduction) in a centralized configuration and how they may be used to achieve efficient subgraph searching over very large databases in cluster configurations This work has been co-funded by the Ministerio de Economía y Competitividad of the Spanish government, and by Mestrelab Research S.L. through the project NEXTCHROM (RTC-2015-3812-2) of the call Retos-Colaboración of the program Programa Estatal de Investigación, Desarrollo e Innovación Orientada a los Retos de la Sociedad. The authors wish to thank the financial support provided by Xunta de Galicia under the Project ED431B 2018/28 SI

Subgraph isomorphism-based star identification algorithms require fewer stars than pattern-based algorithms and are suitable for practical application. Polygon algorithms and match group algorithms, as two typical subgraph isomorphism-based algorithms, both have disadvantages in efficiency and reliability. A novel star identification algorithm is presented in this study to solve this problem. We develop an analytical model to evaluate the validity of different subgraphs, which provides guidance to choose subgraphs. Based on the model, a series of effective and reliable subgraphs with different numbers of vertices, defined as the simplest general subgraphs, are chosen to achieve fast and direct star identification. The star matching strategy is divided into two basic steps. Based on the voting strategy, a star is initially identified by building match groups. It's further identified by building the simplest general subgraphs determined by the size of match groups. A verification approach of reprojection is adopted to improve the robustness of the algorithm. Compared with similar algorithms, the simulation test and night sky image test both show that the proposed algorithm is more robust to position noise, brightness noise, and false stars.

An important combinatorial problem is subgraph isomorphism, which formalizes the task of searching for occurrences of a known substructure within a larger structure represented by a graph: applications are in the fields of chemistry, biology, medicine, databases, social network analysis. Subgraph isomorphism has been proven to be NP-complete in the general case, but several algorithms exist that use heuristics to achieve an affordable run time for common classes of graphs. The need of working with larger and larger graphs makes attractive the idea of parallelizing this task; however, a consensus has not yet been reached on what is the best strategy for doing so. In this paper, we present two versions of a new, parallel algorithm that is based on a re-design of the well known VF3 algorithm. We discuss the changes that were made to efficiently distribute the work among multiple processors. The algorithms have been evaluated with a comprehensive experimentation, using several publicly available graph datasets, to demonstrate their effectiveness in exploiting the parallelism.

An active area of research in computational science is the design of algorithms for solving the subgraph matching problem to find copies of a given template graph in a larger world graph. Prior works have largely addressed single-channel networks using a variety of approaches. We present a suite of filtering methods for subgraph isomorphisms for multiplex networks (with different types of edges between nodes and more than one edge within each channel type). We aim to understand the entire solution space rather than focusing on finding one isomorphism. Results are shown on several classes of datasets: (a) Sudoku puzzles mapped to the subgraph isomorphism problem, (b) Erdős-Rényi multigraphs, (c) real-world datasets from Twitter and transportation networks, (d) synthetic data created for the DARPA MAA program.

For any fixed graph $G$, the subgraph isomorphism problem asks whether an $n$-vertex input graph has a subgraph isomorphic to $G$. A well-known algorithm of Alon, Yuster and Zwick (1995) efficiently reduces this to the "colored" version of the problem, denoted $G$-$\mathsf{SUB}$, and then solves $G$-$\mathsf{SUB}$ in time $O(n^{tw(G)+1})$ where $tw(G)$ is the treewidth of $G$. Marx (2010) conjectured that $G$-$\mathsf{SUB}$ requires time $\Omega(n^{\mathrm{const}\cdot tw(G)})$ and, assuming the Exponential Time Hypothesis, proved a lower bound of $\Omega(n^{\mathrm{const}\cdot emb(G)})$ for a certain graph parameter $emb(G) \ge \Omega(tw(G)/\log tw(G))$. With respect to the size of $\mathrm{AC}^0$ circuits solving $G$-$\mathsf{SUB}$ in the average case, Li, Razborov and Rossman (2017) proved (unconditional) upper and lower bounds of $O(n^{2\kappa(G)+\mathrm{const}})$ and $\Omega(n^{\kappa(G)})$ for a different graph parameter $\kappa(G) \ge \Omega(tw(G)/\log tw(G))$. Our contributions are as follows. First, we prove that $emb(G)$ is $O(\kappa(G))$ for all graphs $G$. Next, we show that $\kappa(G)$ can be asymptotically less than $tw(G)$; for example, if $G$ is a hypercube then $\kappa(G)$ is $\Theta\big(tw(G)\big/\sqrt{\log tw(G)}\big)$. This implies that the average-case complexity of $G$-$\mathsf{SUB}$ is $n^{o(tw(G))}$ when $G$ is a hypercube. Finally, we construct $\mathrm{AC}^0$ circuits of size $O(n^{\kappa(G)+\mathrm{const}})$ that solve $G$-$\mathsf{SUB}$ in the average case, closing the gap between the upper and lower bounds of Li et al., Comment: 31 pages. International Symposium on Parameterized and Exact Computation (IPEC) 2019

In this paper, we study a certain case of a subgraph isomorphism problem. We consider the Hasse diagram of the lattice $M_{k}$ (the unique lattice with $k+2$ elements and one anti-chain of length $k$) and want to find the maximal $k$ for which it is isomorphic to a subgraph of the reduction graph of a given one-rule string rewriting system. We obtain a complete characterization for this problem and show that there is a dichotomy. There are one-rule string rewriting systems for which the maximal such $k$ is $2$ and there are cases where there is no maximum. No other intermediate option is possible., 14 pages

Pattern matching is a fundamental tool for answering complex graph queries. Unfortunately, existing solutions have limited capabilities: They do not scale to process large graphs and/or support only a restricted set of search templates or usage scenarios. Moreover, the algorithms at the core of the existing techniques are not suitable for today’s graph processing infrastructures relying on horizontal scalability and shared-nothing clusters, as most of these algorithms are inherently sequential and difficult to parallelize. We present an algorithmic pipeline that bases pattern matching on constraint checking . The key intuition is that each vertex and edge participating in a match has to meet a set of constraints implicitly specified by the search template. These constraints can be verified independently and typically are less expensive to compute than searching the full template. The pipeline we propose generates these constraints and iterates over them to eliminate all the vertices and edges that do not participate in any match, thus reducing the background graph to a subgraph that is the union of all template matches—the complete set of all vertices and edges that participate in at least one match. Additional analysis can be performed on this annotated, reduced graph, such as full match enumeration, match counting, or computing vertex/edge centrality. Furthermore, a vertex-centric formulation for constraint checking algorithms exists, and this makes it possible to harness existing high-performance, vertex-centric graph processing frameworks. This technique (i) enables highly scalable pattern matching in metadata (labeled) graphs; (ii) supports arbitrary patterns with 100% precision; (iii) enables tradeoffs between precision and time-to-solution, while always selects all vertices and edges that participate in matches, thus offering 100% recall; and (iv) supports a set of popular data analytics scenarios. We implement our approach on top of HavoqGT, an open-source asynchronous graph processing framework, and demonstrate its advantages through strong and weak scaling experiments on massive scale real-world (up to 257 billion edges) and synthetic (up to 4.4 trillion edges) labeled graphs, respectively, and at scales (1,024 nodes / 36,864 cores), orders of magnitude larger than used in the past for similar problems. This article serves two purposes: First, it synthesises the knowledge accumulated during a long-term project [Reza et al. 2017, 2018; Tripoul et al. 2018]. Second, it presents new system features, usage scenarios, optimizations, and comparisons with related work that strengthen the confidence that pattern matching based on iterative pruning via constraint checking is an effective and scalable approach in practice. The new contributions include the following: (i) We demonstrate the ability of the constraint checking approach to efficiently support two additional search scenarios that often emerge in practice, interactive incremental search and exploratory search . (ii) We empirically compare our solution with two additional state-of-the-art systems, Arabsque [Teixeira et al. 2015] and TriAD [Gurajada et al. 2014]. (iii) We show the ability of our solution to accommodate a more diverse range of datasets with varying properties, e.g., scale, skewness, label distribution, and match frequency. (iv) We introduce or extend a number of system features (e.g., work aggregation, load balancing, and the ability to cap the generated traffic) and design optimizations and demonstrate their advantages with respect to improving performance and scalability. (v) We present bottleneck analysis and insights into artifacts that influence performance. (vi) We present a theoretical complexity argument that motivates the performance gains we observe.

In recent years, money laundering has become much easier to be achieved but more challenging to be detected than before, which has enormous adversary effects on finance, military, and other related fields. In the real-time scenario, every money laundering case has a unique structure in terms of transactions. It is not sufficient to detect suspicious behavior by just following the probability theory, where usually the thresholds are given by experts. Since the crime of money laundering is more prevalent and sophisticated nowadays, it will increase the complexity of the detection if the accounts with the personal information are combined with the form of the transaction topology. Hence, the graph topology analysis could be used for antimoney laundering tools. This article proposes eight common topologies based on coupling and connection from simple to much more complicated structures to solve various kinds of problems concerning money laundering in the real world. Moreover, we also propose an efficient solution based on graph and subgraph isomorphism and distance measurement to detect money laundering behavior. In this way, the detection of money laundering behavior will be more efficient and effective for various situations while referencing the proposed eight topological structures.

The problem of finding the least number of variables of a first-order formula expressing the statement that an input-graph contains a subgraph isomorphic to a given pattern-graph is studied. Input-graphs of sufficiently high connectivity are considered. This problem has previously been solved for all pattern-graphs on four vertices except the simple cycle and the diamond graph. In the paper, this number is found for the two remaining graphs.

We consider the pattern detection problem in graphs: given a constant size pattern graph $H$ and a host graph $G$, determine whether $G$ contains a subgraph isomorphic to $H$. We present the follow...

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do not scale to a dynamic setting of a continuous stream of queries. In this paper, we address the scalability challenges induced by a stream of subgraph isomorphism queries by caching and re-use of previous results. We first present a novel subgraph index based on graph embeddings that serves as the foundation for efficient stream processing. It enables not only effective caching and re-use of results, but also speeds-up traditional algorithms for subgraph isomorphism in case of cache misses. Moreover, we propose cache management policies that incorporate notions of reusability of query results. Experiments using real-world datasets demonstrate the effectiveness of our approach in handling isomorphic subgraph search for streams of queries.

RNA aptamer selection during SELEX experiments builds on secondary structural diversity. Advanced structural comparison methods can focus this diversity. We develop SICOR , which uses probabilistic subgraph isomorphisms for graph distances between RNA secondary structure graphs. SICOR outperforms other comparison methods and is applicable to many structural comparisons in experimental design.

Web APIs have been adopted as the de facto standard for exchanging data on the Web. However, engineering applications that orchestrate the invocation of multiple APIs and the data flow among them are still mostly manual and labor intensive. In fact, as the number of the potentially relevant APIs increases, compositions become opaque, difficult to maintain, and practically impossible to reuse. The recent advances around linked data formalisms have the potential to provide “usable” semantics, to enable automatic API composition methods. In this paper, we formalize a simplified description model, based on SPARQL graph patterns, for capturing the semantics of Web APIs. Based on this model, we propose a methodology for a fully automated process that produces semantically valid composition chains, using iterative subgraph isomorphism. We have validated the usefulness and accuracy of our approach, using a collection of publicly available Web APIs relevant to a real-world use cases.

In this paper, we study local subgraph counting, which is to count the occurrences of a user-given pattern graph p around every node v in a data graph G , when v matches to a given orbit o in p , where the orbit serves as a center to count p. In general, the orbit can be a node, an edge, or a set of nodes in p. Local subgraph counting has played an important role in characterizing high-order local structures that exhibit in a large graph, and has been widely used in denser and relevant communities mining, graphlet degree distribution, discriminative features selection for link prediction, relational classification and recommendation. In the literature, almost all the existing works support a k -node pattern graph, for k ≤ 5, with either 1 node orbit or 1 edge orbit. Their approaches are difficult to support larger k due to the fact that subgraph counting is to count by subgraph isomorphism. In this work, we develop a new general approach to count any k pattern graphs with any orbits selected. The key idea behind is that we do local subgraph counting by homomorphism counting, which can be solved by relational algebra using joins, group-by and aggregation. By homomorphism counting, we do local subgraph counting by eliminating counts for those that are not subgraph isomorphism matchings from the total count for any possible matchings. We have developed a distributed system named DISC on Spark. Our extensive experiments validate the efficiency of our approach by testing 114 local subgraph counting queries used in the existing work over real graphs, where no existing work can support all.

Network motifs are recurrent and over-represented patterns having biological relevance. This is one of the important local properties of biological networks. Network motif discovery finds important applications in many areas such as functional analysis of biological components, the validity of network composition, classification of networks, disease discovery, identification of unique subunits etc. The discovery of network motifs is a computationally challenging task due to the large size of real networks, and the exponential increase of search space with respect to network size and motif size. This problem also includes the subgraph isomorphism check, which is Nondeterministic Polynomial (NP)-complete. Several tools and algorithms have been designed in the last few years to address this problem with encouraging results. These tools and algorithms can be classified into various categories based on exact census, mapping, pattern growth, and so on. In this study, critical aspects of network motif discovery, design principles of background algorithms, and their functionality have been reviewed with their strengths and limitations. The performances of state-of-art algorithms are discussed in terms of runtime efficiency, scalability, and space requirement. The future scope, research direction, and challenges of the existing algorithms are presented at the end of the study.

Mathematical software and graph-theoretical algorithmic packages to efficiently model, analyze and query graphs are crucial in an era where large-scale spatial, societal and economic network data are abundantly available. One such package is JGraphT, a programming library which contains very efficient and generic graph data-structures along with a large collection of state-of-the-art algorithms. The library is written in Java with stability, interoperability and performance in mind. A distinctive feature of this library is the ability to model vertices and edges as arbitrary objects, thereby permitting natural representations of many common networks including transportation, social and biological networks. Besides classic graph algorithms such as shortest-paths and spanning-tree algorithms, the library contains numerous advanced algorithms: graph and subgraph isomorphism; matching and flow problems; approximation algorithms for NP-hard problems such as independent set and TSP; and several more exotic algorithms such as Berge graph detection. Due to its versatility and generic design, JGraphT is currently used in large-scale commercial, non-commercial and academic research projects. In this work we describe in detail the design and underlying structure of the library, and discuss its most important features and algorithms. A computational study is conducted to evaluate the performance of JGraphT versus a number of similar libraries. Experiments on a large number of graphs over a variety of popular algorithms show that JGraphT is highly competitive with other established libraries such as NetworkX or the BGL., Comment: Major Revision

With the rapid development of mobile Internet, Android applications are used more and more in people’s daily life. While bringing convenience and making people’s life smarter, Android applications also face much serious security and privacy issues, e.g., information leakage and monetary loss caused by malware. Detection and classification of malware have thus attracted much research attention in recent years. Most current malware detection and classification approaches are based on graph-based similarity analysis (e.g., subgraph isomorphism), which is well known to be time-consuming, especially for large graphs. In this paper, we propose NSDroid, a time-efficient malware multi-classification approach based on neighborhood signature in local function call graphs (FCGs). NSDroid uses a approach based on neighborhood signature to calculate the similarity of different applications’ FCGs, which is significantly faster than traditional approaches based on subgraph isomorphism. For each node in the FCGs, NSDroid uses a fixed-length neighborhood signature to capture the caller-callee relationship between different functions and combines neighborhood signatures of all nodes to form a vector that characterizes the function call relationship in the whole application. The generated signature vector is fed into a SVM-based classifier to determine which family the malware belongs to. Experimental results on large-scale benchmarks show that, compared with state-of-the-art solutions, NSDroid reduces average detection latency by nearly $$20\times $$ , and meanwhile improves many evaluation index such as recall rate and others.

With the rapid development of smart devices, mobile phones have permeated many aspects of our life. Unfortunately, their widespread popularization attracted endless attacks that are serious threats for users. As the mobile system with the largest market share, Android has already become the hardest hit for years. To Detect Android Malware by ORGB Anlysis, in this paper, we present DAMBA, a novel prototype system based on a C/S architecture. DAMBA extracts the static and dynamic features of apps. For further analyses, we propose TANMAD algorithm, a two-step Android malware detection algorithm, which reduces the range of possible malware families, and then utilizes subgraph isomorphism matching for malware detection. The key novelty of this paper is the modeling of object reference information by constructing directed graphs, which is called object reference graph birthmarks (ORGB). To achieve better efficiency and accuracy, in this paper, we present several optimization strategies for hybrid analysis. DAMBA is evaluated on a large real-world dataset of 2239 malicious and 1000 popular benign apps. The detection accuracy reaches 100% in most cases, and the average detection time is less than 5 s. Experimental results show that DAMBA outperforms the well-known detector, McAfee, which is based on signature recognition. In addition, DAMBA is demonstrated to resist the known malware attacks and their variants efficiently, as well as malware that uses obfuscation techniques.

Networks exhibit rich and diverse higher-order organizational structures. Network motifs, which are recurring significant patterns of inter-connections, are recognized as fundamental units to study the higher-order organizations of networks. However, the principle of selecting representative network motifs for local motif based clustering remains largely unexplored. We present a scalable algorithm called FSM for network motif discovery. FSM is advantageous in twofold. First, it accelerates the motif discovery process by effectively reducing the number of times for subgraph isomorphism labeling. Second, FSM adopts multiple heuristic optimizations for subgraph enumeration and classification to further improve its performance. Experimental results on biological networks show that, comparing with the existing network motif discovery algorithm, FSM is more efficient on computational efficiency and memory usage. Furthermore, with the large, frequent, and sparse network motifs discovered by FSM, the higher-order organizational structures of biological networks were successfully revealed, indicating that FSM is suitable to select network representative network motifs for exploring high-order network organizations.

Graph jobs represent a wide variety of computation-intensive tasks in which computations are represented by graphs consisting of components (denoting either data sources or data processing) and edges (corresponding to data flows between the components). Recent years have witnessed dramatic growth in smart vehicles and computation-intensive graph jobs, which pose new challenges to the provision of efficient services related to the Internet of Vehicles. Fortunately, vehicular clouds formed by a collection of vehicles, which allows jobs to be offloaded among vehicles, can substantially alleviate heavy on-board workloads and enable on-demand provisioning of computational resources. In this paper, we present a novel framework for vehicular clouds that maps components of graph jobs to service providers via opportunistic vehicle-to-vehicle communication. Then, graph job allocation over vehicular clouds is formulated as a non-linear integer programming with respect to vehicles' contact duration and available resources, aiming to minimize job completion time and data exchange cost. The problem is addressed for two scenarios: low-traffic and rush-hours. For the former, we determine the optimal solutions for the problem. In the latter case, given the intractable computations for deriving feasible allocations, we propose a novel low complexity randomized graph job allocation mechanism by considering hierarchical tree based subgraph isomorphism. We evaluate the performance of our proposed algorithms through extensive simulations., Comment: 11 pages, 6 Figures

3D process plant models(PPMs) in the process industry normally consists of thousands of components. And, there are many similar local structures in the PPM. Due to the complex process flow, the topology relationship among components is very complicated. Therefore, designing a new PPM is quite time consuming. In order to shorten the design cycle, content based model retrieval for PPMs is an imperative requirement. In this paper, we propose a partial matching framework for PPMs based on graph matching aiming at improving design efficiency and realizing design reuse. The random walk algorithm is employed to distinguish similar local structures. Specifically, each PPM is represented by an undirected labeled graph. The local topological feature of each component is extracted based on the random walk algorithm. For partial matching, a subgraph isomorphism algorithm is introduced. The matching process is accelerated by using the local topological feature to generate an optimized initial state and alleviate the computation of feasible rules. Experimental results show the feasibility and effectiveness of our matching framework.

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism in GPUs is well suited for solving subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing subgraph isomorphism on GPUs and develops an efficient GPU implementation. We also develop a GPU-friendly trie-based data structure to drastically reduce the intermediate storage space requirement, enabling large benchmarks to be processed. We also develop the first distributed sub-graph isomorphism algorithm for GPUs. Our experimental evaluation demonstrates the efficacy of our approach by comparing the execution time and number of cases that can be handled against the state-of-the-art GPU implementations.

In this paper is presented the GR2 Algorithm in the context of a study that encompassed elements of Parallel Programming and pruning techniques. Also there were executed circuits having 5, 10 and 15 qubits on quantum computers. For these circuits were used classical and quantum gates along with oracles and Grover’s Algorithm. The original contribution consists in highlighting the importance of Parallel Programming in classiscal computing as well as in quantum computing.

The purpose of the research presented in this paper is finding the best execution times for searching subgraph isomorphisms. For this was created the GR3 Algorithm, its design consisting of a combination of Parallel Programming and Quantum Computing. The obtained execution times are significantly small. Thus can be deduced that an approach such as this is superior in obtaining the required results. The original contribution consists in studying a Parallel Programming approach combined with Quantum Computing Circuits and Grover’s Algorithm for searching subgraph isomorphisms using a laptop and real quantum computers [16].

Graph homomorphism problems involve finding\ud adjacency-preserving mappings between two given\ud graphs. Although theoretically hard, these problems can often be solved in practice using constraint programming algorithms. We show how\ud techniques from the state-of-the-art in subgraph\ud isomorphism solving can be applied to broader\ud graph homomorphism problems, and introduce a\ud new form of filtering based upon clique-finding.\ud We demonstrate empirically that this filtering is effective for the locally injective graph homomorphism and subgraph isomorphism problems, and\ud gives the first practical constraint programming approach to finding general graph homomorphisms.

In the 3D model of parts, transition features not only increase the number of nodes in the Face-Edge Attributed Adjacency Graph(FAAG) of parts but also destroy the topological structure of the original features. This will reduce the manufacturing feature recognition efficiency and accuracy. In the present work, a machining feature recognition method based on Transition Feature Simplification (MFRTFS) is developed to accommodate parts with Transition Feature. The proposed approach divides the transition feature into two types: edge transition surface and point transition surface, and simplifies them on the FAAG to reduce the search space of the Subgraph Isomorphism Algorithm. In addition to that, a case of industrial part is given to verify the effectiveness of the proposed method using OpenCasCade and other tools.

With the popularity of storing large data graph in cloud, the emergence of subgraph pattern matching on a remote cloud has been inspired. Typically, subgraph pattern matching is defined in terms of subgraph isomorphism, which is an NP-complete problem and sometimes too strict to find useful matches in certain applications. And how to protect the privacy of data graphs in subgraph pattern matching without undermining matching results is an important concern. Thus, we propose a novel framework to achieve the privacy-preserving subgraph pattern matching in cloud. In order to protect the structural privacy in data graphs, we firstly develop a k-automorphism model based method. Additionally, we use a cost-model based label generalization method to protect label privacy in both data graphs and pattern graphs. During the generation of the k-automorphic graph, a large number of noise edges or vertices might be introduced to the original data graph. Thus, we use the outsourced graph, which is only a subset of a k-automorphic graph, to answer the subgraph pattern matching. The efficiency of the pattern matching process can be greatly improved in this way. Extensive experiments on real-world datasets demonstrate the high efficiency of our framework.

To meet the need for low delay of end-to-end data transmission in some particular application of mobile ad hoc network (MANET), the planning SDMA slot tables are usually adopted. Whether the message can be transmitted by the planning SDMA slot table must be judged to decide if the pattern topology graph according to the SDMA slot table is included in the target topology graph, which was solved by employing subgraph isomorphism model in this paper, and a new algorithm named SGI (subgraph isomorphism) was proposed based on the Ullmann’s. Simulation and analysis showed that compared with Ullmann’s, the SGI could judge the subgraph isomorphism relationship more quickly with lower computing overhead.

Graph pattern matching is a key problem in many applications which data is represented in the form of a graph, and this problem is generally defined as a subgraph isomorphism. In this paper, we analyze an incremental hybrid genetic algorithm for the subgraph isomorphism problem considering various design issues to improve the performance of the algorithm. An incremental hybrid genetic algorithm was previously suggested to solve the subgraph isomorphism problem and have shown good performance. It decomposes the problem into a sequence of consecutive subproblems which has an optimal substructure. Each subproblem is solved by the hybrid genetic algorithm and the solutions obtained are extended to be applied to the next subproblem as initial solutions. We examine a wide range of schemes that determine the overall performance of the incremental process and make a number of experiments to verify the effectiveness of each scheme with the synthetic dataset of random graphs. We show that the performance of incremental approach can be significantly improved compared to the previous representative studies by applying appropriate schemes found by the experiments. In addition, we also investigate the effect of different genetic parameters and identify the scalability of our method by conducting experiments using real world dataset with large-sized graphs.

In recent years, we have witnessed an increasing use of graph pattern matching in a wide variety of applications such as social networks analysis, knowledge discovery, software plagiarism detection and many more. It is typically defined in terms of subgraph isomorphism, an NP-Complete problem. To overcome this cost, many extensions of graph simulation have been proposed that allow graph pattern matching to be conducted in cubic-time. However, in emerging applications, more expressive patterns are needed, notably ones with counting quantifiers (CQs) which are not considered by simulation-based approaches. In this article, we propose a simulation-based graph pattern matching approach that supports CQs on edges of graph patterns. We first consider CQs that express numeric aggregates only. We show that our approach is in ptime as earlier extensions of graph simulation by providing a cubic-time quantified matching algorithm, i.e., an algorithm for matching graph patterns that contain CQs. In the second part, we discuss the problem of Label-Repetition Constraints (LRCs). We define a necessary and sufficient condition for the satisfaction of LRCs. Based on this condition, we give an extension of our quantified matching algorithm to deal with LRCs in ptime, together with an optimization technique. Finally, we show that our quantified graph pattern matching approach retains the same complexity bounds when dealing with ratio aggregates. To our knowledge, this is the first effort to deal with numeric aggregates, ratio aggregates, and LRCs on graph patterns in ptime.

In the metabolomics, glycomics, and mass spectrometry of structured small molecules, the combinatoric nature of the problem renders a database impossibly large, and thus de novo analysis is necessary. De novo analysis requires an alphabet of mass difference values used to link peaks in fragmentation spectra when they are different by a mass in the alphabet divided by a charge. Often, this alphabet is not known, prohibiting de novo analysis. A method is proposed that, given fragmentation mass spectra, identifies an alphabet of m/z differences that can build large connected graphs from many intense peaks in each spectrum from a collection. We then introduce a novel approach to efficiently find recurring substructures in the de novo graph results.

The biological network plays a key role in protein function annotation, protein superfamily classification, disease diagnosis, etc. These networks exhibit global properties like small-world property, power-law degree distribution, hierarchical modularity, robustness, etc. Along with these, the biological network also possesses some local properties like clustering and network motif. Network motifs are recurrent and statistically over-represented subgraphs in a target network. Operation of a biological network is controlled by these motifs, and they are responsible for many biological applications. Discovery of network motifs is a computationally hard problem and involves a subgraph isomorphism check which is NP-complete. In recent years, researchers have developed various tools and algorithms to detect network motifs efficiently. However, it is still a challenging task to discover the network motif within a practical time bound for the large motif. In this study, an efficient pattern-join based algorithm is proposed to discover network motif in biological networks. The performance of the proposed algorithm is evaluated on the transcription regulatory network of Escherichia coli and the protein interaction network of Saccharomyces cerevisiae. The running time of the proposed algorithm outperforms most of the existing algorithms to discover large motifs.

Graph data structure has been widely used across many application areas, such as web data, social network, and cheminformatics. The main benefit of storing data as graphs is there exists a rich set of graph algorithms and operations that can be used to solve various computing problems, including pattern matching, data mining, and image processing. Among these graph algorithms, the subgraph isomorphism problem is one of the most fundamental algorithms that can be utilized by many higher level applications. The subgraph isomorphism problem is defined as, given two graphs [Formula: see text] and [Formula: see text], whether [Formula: see text] contains a subgraph that is isomorphic to [Formula: see text]. In this paper, we consider a special case of the subgraph isomorphism problem called the subgraph matching problem, which tests whether [Formula: see text] is a subgraph of [Formula: see text]. We propose a protocol that solve the subgraph matching problem in a privacy-preserving manner. The protocol allows two parties to jointly compute whether one graph is a subgraph of the other, while protecting the private information about the input graphs. The protocol is secure under the semi-honest setting, where each party performs the protocol faithfully.

Keys for graphs incorporate the topology and value constraints needed to uniquely identify entities in a graph. They have been studied to support object identification, knowledge fusion, and social network reconciliation. Existing key constraints identify entities as the matches of a graph pattern by subgraph isomorphism, which enforce label equality on node types. These constraints can be too restrictive to characterize structures and node labels that are syntactically different but semantically equivalent. We propose a new class of key constraints, Ontological Graph Keys (OGKs) that extend conventional graph keys by ontological subgraph matching between entity labels and an external ontology. We show that the implication and validation problems for OGKs are each NP-complete. To reduce the entity matching cost, we also provide an algorithm to compute a minimal cover for OGKs. We then study the entity matching problem with OGKs, and a practical variant with a budget on the matching cost. We develop efficient algorithms to perform entity matching based on a (budgeted) Chase procedure. Using real-world graphs, we experimentally verify the efficiency and accuracy of OGK-based entity matching.

We present a revised filtering process that corrects an error in our previous work on subgraph isomorphism search over compressed graphs. We provide additional experiments to test the contribution of the compression itself and the candidate filtering to the performance of four representative backtracking-based subgraph isomorphism search algorithms.

International audience; This paper presents a method for recovering and identifying image regions from an initial oversegmentation using qualitative knowledge of its content. Compared to recent works favoring spatial information and quantitative techniques, our approach focuses on simple a priori qualitative inclusion and photometric relationships such as "region A is included in region B", "the intensity of region A is lower than the one of region B" or "regions A and B depict similar intensities" (photometric uncertainty). The proposed method is based on a two steps" inexact graph matching approach. The first step searches for the best subgraph isomorphism candidate between expected regions and a subset of regions resulting from the initial oversegmentation. Then, remaining segmented regions are progressively merged with appropriate already matched regions, while preserving the coherence with a priori declared relationships. Strengths and weaknesses of the method are studied on various images (grayscale and color), with various intial oversegmentation algorithms (k-means, meanshift, quickshift). Results show the potential of the method to recover, in a reasonable runtime, expected regions, a priori described in a qualitative manner. For further evaluation and comparison purposes, a Python opensource package implementing the method is provided, together with the specifically built experimental database.

In this article, the authors have proposed an integrated algorithm for instruction scheduling and register allocation, and implemented it for compiler optimization in a machine description in a trimaran infrastructure for exploitation of instruction-level parallelism. For this experimental work, the authors added machine descriptions (MDES) targeted to HL-PD architecture. As a result, only a few spills were needed and the quality of the code generated was improved. The application of abstract base graph has been applied for experimental purposes. For these experiments, this article used 20 benchmarks available with trimaran infrastructure for HPL-PD architecture. This article compares some of these results with results obtained performed on LLVM compiler on an MIPS architecture. The implemented algorithm is based on subgraph isomorphism. The input program is represented in the form of directed acyclic graph (DAG). The vertices of the DAG represent the instructions, input, and output operands of the program, while the edges represent dependencies among the instructions.

© 1989-2012 IEEE. Supergraph search is a fundamental problem in graph databases that is widely applied in many application scenarios. Given a graph database and a query-graph, supergraph search retrieves all data-graphs contained in the query-graph from the graph database. Most existing solutions for supergraph search follow the pruning-and-verification framework, which prune false answers based on features in the pruning phase and perform subgraph isomorphism testings on the remaining graphs in the verification phase. However, they are not scalable to handle large-sized data-graphs and query-graphs due to three drawbacks. First, they rely on a frequent subgraph mining algorithm to select features which is expensive and cannot generate large features. Second, they require a costly verification phase. Third, they process features in a fixed order without considering their relationships to the query-graph. In this paper, we address the three drawbacks and propose new indexing and query processing algorithms. In indexing, we select features directly from the data-graphs without expensive frequent subgraph mining. The features form a feature-tree that contains all-sized features and both the cost sharing and pruning power of the features are considered. In query processing, we propose a new algorithm, where the order to process features is query-dependent by considering both the cost sharing and the pruning power. We explore two optimization strategies to further improve the algorithm efficiency. The first strategy applies a lightweight graph compression technique and the second strategy optimizes the inclusion of answers. We further introduce how to efficiently maintain the index incrementally when the graph database is updated dynamically. Moreover, we propose an approximation approach to significantly reduce the computational cost for large data-graphs and/or query-graphs while preserving a high result quality. Finally, we conduct extensive performance studies on two real large datasets to demonstrate the efficiency and effectiveness of our algorithms.

Given the broad applications of service-oriented architecture (SOA) in service-oriented software engineering, service-based systems (SBSs) built from existing Web services are becoming increasingly popular. As a result, the selection of the appropriate component services to include in SBSs has become a crucial step in the SBS-engineering process. Unfortunately, most of the existing methods require that system engineers have a detailed knowledge of the corresponding SOA techniques, which can incur several limitations, including excessively demanding development conditions and a lengthy development cycle. To address this issue, we propose to use subgraph queries for SBSs (SQS), which is an efficient approach that allows system engineers to build SBSs based on previous development experience. The SQS converts the SBS engineering problem into a subgraph isomorphism problem and uses a customized algorithm inspired by the VF2 algorithm to build SBSs with quality constraints and optimization goals for system quality. The SQS offers a new paradigm for efficient SBS engineering that significantly reduces the time and effort required in the system-engineering process. We discuss a series of experiments that use two real-world Web service datasets to demonstrate the practicality, effectiveness, and efficiency of this approach.

Borne out of a surprising variety of practical applications, the maximum-weight connected subgraph problem has attracted considerable interest in recent years. This interest has not only led to not...

Recent advances in neuroscience have enabled the exploration of brain structure at the level of individual synaptic connections. These connectomics datasets continue to grow in size and complexity; methods to search for and identify interesting graph patterns offer a promising approach to quickly reduce data dimensionality and enable discovery. These graphs are often too large to be analyzed manually, presenting significant barriers to searching for structure and testing hypotheses. We combine graph database and analysis libraries with an easy-to-use neuroscience grammar suitable for rapidly constructing queries and searching for subgraphs and patterns of interest. Our approach abstracts many of the computer science and graph theory challenges associated with nanoscale brain network analysis and allows scientists to quickly conduct research at scale. We demonstrate the utility of these tools by searching for motifs on simulated data and real public connectomics datasets, and we share simple and complex structures relevant to the neuroscience community. We contextualize our findings and provide case studies and software to motivate future neuroscience exploration.

Subgraph counting, as a fundamental problem in network analysis, is to count the number of subgraphs in a data graph that match a given query graph by either homomorphism or subgraph isomorphism. The importance of subgraph counting derives from the fact that it provides insights of a large graph, in particular a labeled graph, when a collection of query graphs with different sizes and labels are issued. The problem of counting is challenging. On one hand, exact counting by enumerating subgraphs is NP-hard. % On the other hand, approximate counting by subgraph isomorphism can only support 3/5-node query graphs over unlabeled graphs. % Another way for subgraph counting is to specify it as an \SQL query and estimate the cardinality of the query in \rdbm. Existing approaches for cardinality estimation can only support subgraph counting by homomorphism up to some extent, as it is difficult to deal with sampling failure when a query graph becomes large. A question that arises is if subgraph counting can be supported by machine learning (ML) and deep learning (DL). The existing DL approach for subgraph isomorphism can only support small data graphs. The ML/DL approaches proposed in \rdbm context for approximate query processing and cardinality estimation cannot be used, as subgraph counting is to do complex self-joins over one relation, whereas existing approaches focus on multiple relations. In this paper, we propose an Active Learned Sketch for Subgraph Counting (\ALSS) with two main components: a sketch learned (ŁSS) and an active learner (\AL). The sketch is learned by a neural network regression model, and the active learner is to perform model updates based on new arrival test query graphs. % We conduct extensive experimental studies to confirm the effectiveness and efficiency of \ALSS using large real labeled graphs. Moreover, we show that \ALSS can assist query optimizers to find a better query plan for complex multi-way self-joins.

This paper proposes a scheme to reduce big graphs to small graphs. It contracts obsolete parts and regular structures into supernodes. The supernodes carry a synopsis $$S_\mathcal {Q}$$ S Q for each query class $$\mathcal {Q}$$ Q in use, to abstract key features of the contracted parts for answering queries of $$\mathcal {Q}$$ Q . Moreover, for various types of graphs, we identify regular structures to contract. The contraction scheme provides a compact graph representation and prioritizes up-to-date data. Better still, it is generic and lossless. We show that the same contracted graph is able to support multiple query classes at the same time, no matter whether their queries are label based or not, local or non-local. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by using the synopses when possible and decontracting the supernodes only when necessary. As a proof of concept, we show how to adapt existing algorithms for subgraph isomorphism, triangle counting, shortest distance, connected component and clique decision to contracted graphs. We also provide a bounded incremental contraction algorithm in response to updates, such that its cost is determined by the size of areas affected by the updates alone, not by the entire graphs. We experimentally verify that on average, the contraction scheme reduces graphs by 71.9% and improves the evaluation of these queries by 1.69, 1.44, 1.47, 2.24 and 1.37 times, respectively.

Subgraph isomorphism is an essential problem of graph theory. It has broad application on information retrieval in many research field, such as biology, chemistry, knowledge graph and social network. The settlement to graph isomorphism is to find the embedding details from a given query graph Gq to a given data graph G. Till now, most subgraph isomorphism research build on searching from one fixed query graph. However, in practice, fixed query graph will lead to heavy query graph building work. In this paper, we proposed a subgraph matching framework built on a hierarchical query graph to alleviate the burden of query graph building work. The vertices of query graph are classified into three type: compulsory vertex, optional vertex and forbidden vertex. We proposed a modified VF2 algorithm to tackle this task. It creatively handle the order problem by converting the vertices matching into label matching and using a sieving method to map the label to the vertex. We conducted experiments on a financial semantic relationship datasets. Results show our modified VF2 algorithm can accurately map the query graph Gq to the subgraph of data graph G with acceptable time efficiency.

Biological networks provide great potential to understand how cells function. Motifs in biological networks, frequent topological patterns, represent key structures through which biological networks operate. Studying motifs answers important biological questions. Finding motifs in biological networks remains to be a computationally challenging task as the sizes of the motif and the underlying network grow. Several algorithms exist in the literature to solve this problem. This chapter discusses the biological significance of network motifs, motivation behind solving the motif detection problem and the key challenges of this problem. We discuss different formulations of motif detection problem based on several orthogonal perspectives that change the problem definition as well as solution significantly. The first perspective considers the number of input networks involved (i.e., one or more than one networks). The second perspective focuses on the labeling (i.e., labeled or unlabeled) of the nodes and edges of the input network. The third one considers different frequency definitions of counting motif instances (i.e., F1, F2, and F3) in a network. The fourth perspective describes whether the underlying network is directed or undirected. The last one considers motif detection under different types of network models (i.e., deterministic, probabilistic, or dynamic model). As a case study for each formulation, we briefly discuss important existing methods from the literature. Finally, we conclude with future research directions.

Subgraph isomorphism is one of the most challenging problems on graph-based representations. Despite many efficient sequential algorithms have been proposed over the last decades, solving this problem on large graphs is still a time demanding task. For this reason, there is a recently growing interest in realizing effective parallel algorithms able to exploit at their best the modern multi-core architectures commonly available on servers and workstations. We propose a comparison of four parallel algorithms derived from the state-of-the-art sequential algorithm VF3-Light; two of them were presented in previous works, while the other two are introduced in this paper. In order to evaluate strong points and weaknesses of each algorithm, we performed a benchmark over six datasets of random large and dense graphs, both labelled and unlabelled, measuring memory usage, speed-up and efficiency. We also add a comparison with a different parallel algorithm, named Glasgow, that is not derived from VF3-Light.