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

Temporal networks are graphs where each edge is associated with a timestamp denoting when two nodes interact. Temporal Subgraph Isomorphism (TSI) aims at retrieving all the subgraphs of a temporal network (called target) matching a smaller temporal network (called query), such that matched target edges appear in the same chronological order of corresponding query edges. Few algorithms have been proposed to solve the TSI problem (or variants of it) and most of them are applicable only to small or specific queries. In this paper we present TemporalRI, a new subgraph isomorphism algorithm for temporal networks with multiple contacts between nodes, which is inspired by RI algorithm. TemporalRI introduces the notion of temporal flows and uses them to filter the search space of candidate nodes for the matching. Our algorithm can handle queries of any size and any topology. Experiments on real networks of different sizes show that TemporalRI is very efficient compared to the state-of-the-art, especially for large queries and targets.

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.

Background Graphs are mathematical structures widely used for expressing relationships among elements when representing biomedical and biological information. On top of these representations, several analyses are performed. A common task is the search of one substructure within one graph, called target. The problem is referred to as one-to-one subgraph search, and it is known to be NP-complete. Heuristics and indexing techniques can be applied to facilitate the search. Indexing techniques are also exploited in the context of searching in a collection of target graphs, referred to as one-to-many subgraph problem. Filter-and-verification methods that use indexing approaches provide a fast pruning of target graphs or parts of them that do not contain the query. The expensive verification phase is then performed only on the subset of promising targets. Indexing strategies extract graph features at a sufficient granularity level for performing a powerful filtering step. Features are memorized in data structures allowing an efficient access. Indexing size, querying time and filtering power are key points for the development of efficient subgraph searching solutions. Results An existing approach, GRAPES, has been shown to have good performance in terms of speed-up for both one-to-one and one-to-many cases. However, it suffers in the size of the built index. For this reason, we propose GRAPES-DD, a modified version of GRAPES in which the indexing structure has been replaced with a Decision Diagram. Decision Diagrams are a broad class of data structures widely used to encode and manipulate functions efficiently. Experiments on biomedical structures and synthetic graphs have confirmed our expectation showing that GRAPES-DD has substantially reduced the memory utilization compared to GRAPES without worsening the searching time. Conclusion The use of Decision Diagrams for searching in biochemical and biological graphs is completely new and potentially promising thanks to their ability to encode compactly sets by exploiting their structure and regularity, and to manipulate entire sets of elements at once, instead of exploring each single element explicitly. Search strategies based on Decision Diagram makes the indexing for biochemical graphs, and not only, more affordable allowing us to potentially deal with huge and ever growing collections of biochemical and biological structures.

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.

For a given pair of pattern and data graphs, the subgraph isomorphism finding problem locates all instances of the pattern graph into the data graph. For a given subgraph isomorphic image of the pattern graph in a data graph, the set of all ordered pairs of the pattern graph’s vertices and their respective images data graph is called an embedding. Many solvers, such as $\mathrm {Turbo_{ISO}}$ , Glasgow, and VF3 exist in the literature for subgraph isomorphism finding problem. Though each solver aims to minimize computing costs in its own way, computational efficiency is still a central issue for the subgraph isomorphism finding problem. In this paper, we present the development of an efficient solver, SubGlw, for subgraph isomorphism finding which first decomposes data graph into small-size candidate subgraphs using a ranking function and then searches the embeddings of the pattern graph in each of them separately. The ranking function is designed in such a way that it minimizes both number and size of the candidate subgraphs. The performance of SubGlw is empirically evaluated and compared with two state-of-the-art subgraph isomorphism solvers – SubISO and Glasgow over three benchmark datasets – Yeast, Human, and Hprd. The experimental findings reveal that SubGlw performs significantly better in terms of both embedding count and execution time. We have also presented an analysis for identifying saddle point, which is a timeout at which our solver achieves maximum embeddings in least execution time. This analysis provides a better understanding for parameter settings. The source codes of SubGlw can be downloaded from https://github.com/ZubairAliIgraph/SubGlw-master.

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.

Large graph networks frequently appear in the latest applications. Their graph structures are very large, and the interaction among the vertices makes it difficult to split the structures into separate multiple structures, thus increasing the difficulty of frequent subgraph mining. The process of calculating subgraph isomorphism often requires many calculations. Reducing the unessential structure of the graph is an effective method to improve the efficiency. Therefore, we propose a large graph sampling algorithm (RASI) based on random areas selection sampling and incorporate graph induction techniques to reduce the structure of the original graph. In addition, we find that constraining the weight of the number of vertices in the entire graph is essential to reduce the calculation of subgraph isomorphisms. This parameter is constrained in the sampling process to improve the efficiency of frequent subgraph mining. Experimental results show that RASI has more stable performance and performs better than other sampling algorithms in non-connected graphs. Mining frequent subgraphs by graph sampling can significantly improve the efficiency of mining, and the number of subgraphs before and after sampling is very similar.

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

The Glasgow Subgraph Solver provides an implementation of state of the art algorithms for subgraph isomorphism problems. It combines constraint programming concepts with a variety of strong but fast domain-specific search and inference techniques, and is suitable for use on a wide range of graphs, including many that are found to be computationally hard by other solvers. It can also be equipped with side constraints, and can easily be adapted to solve other subgraph matching problem variants. We outline its key features from the view of both users and algorithm developers, and discuss future directions.

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.