Search

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

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time ∣V(H)∣o(∣V(H)∣). We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of ∣V(H)∣o(∣V(H)∣)-time algorithm deciding if graph G is a subgraph of H. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems. Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem. [ABSTRACT FROM AUTHOR]

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 analytical model based on the match of angular distance is developed to evaluate the validity of different subgraphs. • The analytical model provides guidance to choose reliable and effective subgraphs forstar identification algorithms. • The effective and reliable simplest general subgraphs are chosen to achieve fast and direct star identification. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This article addresses the problem of finding patterns in graphs. This is formally defined as the subgraph isomorphism problem and is one of the core problems in theoretical computer science. We consider the counting variation of this problem. The task is to count all instances of the pattern G occurring in a (usually larger) graph H. The vast majority of algorithms for this problem use a variation of backtracking. Most commonly they exhaustively search through the space of all possible monomorphisms between G and H. The size of the search tree depends heavily on the choice of the ordering of vertices ofG, which are systematically assigned to the vertices ofH. We use a method called heuristic sampling to estimate the size of the search tree for each ordering in advance. We use this estimation to select the most suitable order of vertices of G which minimizes the expected tree size. This approach is empirically evaluated on a set ofinstances, showing the practical potential of the method. [ABSTRACT FROM AUTHOR]

Featured Application: MUIS (Minimal Unique Induced Subgraph) query can be used in many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. In this paper, a novel type of interesting subgraph query is proposed: Minimal Unique Induced Subgraph (MUIS) query. Given a (large) graph G and a query vertex (position) q in the graph, can we find an induced subgraph containing q with the minimal number of vertices that is unique in G? MUIS query has many potential applications, such as subgraph retrieval, graph visualization, representative subgraph discovery and vertex property exploration. The formal definition of MUIS is given and the properties are discussed in this paper. The baseline and EQA (Efficient Query Answering) algorithms are proposed to solve the MUIS query problem under the filtering-validation framework. In the EQA algorithm, the Breadth First Search (BFS)-based candidate set generation strategy is proposed to ensure the minimality property of MUIS; the matched vertices-based pruning strategy is proposed to prune useless candidate sets and the unnecessary subgraph isomorphism; and the query position-based subgraph isomorphism is proposed to check efficiently the uniqueness of the subgraphs. Experiments are carried on real datasets and synthetic datasets to verify the effectiveness and efficiency of the proposed algorithm under novel measurements. The influencing factors of the process speed are discussed at last in the paper. [ABSTRACT FROM AUTHOR]

In this paper we consider a problem that arises from a strategic issue in the stable matching model (with complete preference lists) from the viewpoint of exact-exponential time algorithms. Specifically, we study the STABLE EXTENSION OF PARTIAL MATCHING (SEOPM) problem, where the input consists of the complete preference lists of men, and a partial matching. The objective is to find (if one exists) a set of preference lists of women, such that the men-optimal Gale-Shapley algorithm outputs a perfect matching that contains the given partial matching. Kobayashi and Matsui (Algorithmica 58:151-169, 2010) proved this problem is NP-complete. In this article, we give an exact-exponential algorithm for SEOPM running in time 2O(n), where n denotes the number of men/women. We complement our algorithmic finding by showing that unless Exponential Time Hypothesis (ETH) fails, our algorithm is asymptotically optimal. That is, unless ETH fails, there is no algorithm for SEOPM running in time 2o(n). Our algorithm is a non-trivial combination of a parameterized algorithm for SUBGRAPH ISOMORPHISM, a relationship between stable matching and finding an out-branching in an appropriate graph and enumerating all possible non-isomorphic out-branchings. Our results cover both the cases when the preference lists are strict and complete, and when they are strict but possibly incomplete. [ABSTRACT FROM AUTHOR]

In recent years, the MapReduce framework has become one of the most popular parallel computing platforms for processing big data. MapReduce is used by companies such as Facebook, IBM, and Google to process or analyze massive data sets. Since the approach is frequently used for industrial solutions, the algorithms based on the MapReduce framework gained significant attention within the scientific community. The subgraph isomorphism is a fundamental graph theory problem. Finding small patterns in large graphs is a core challenge in the analysis of applications with big data sets. This paper introduces two novel algorithms, which are capable of finding matching patterns in arbitrary large graphs. The algorithms are designed for utilizing the easy parallelization technique offered by the MapReduce framework. The approaches are evaluated regarding their space and memory requirements. The paper also provides the applied data structure and presents formal analysis of the algorithms. [ABSTRACT FROM AUTHOR]

Graph mining is a major area of interest within the field of data mining in recent years. A key aspect of graph mining is frequent subgraph mining. Central to the entire discipline of frequent subgraph mining is the concept of subgraph isomorphism. One major issue in early subgraph isomorphism research concerns computational complexity. Normally, the subgraph isomorphism problem is NP-complete. Previous studies of frequent subgraph mining have not solved NP-complete problem in the subgraph isomorphism. In this paper, we propose a new algorithm which can deal with this problem. The proposed algorithm can solve the subgraph isomorphism in polynomial time in some settings. Moreover, the new algorithm is proved theoretically more effective than previous studies in closed frequent subgraph mining. [ABSTRACT FROM AUTHOR]

Maximum common induced subgraph (MCIS) of a communication network graph database determine the common substructures which are always active and retain the links between any pair of nodes exactly as in all graphs of the database. Many benchmark graph algorithms to predict MCIS of a graph database deal only with two graphs at a time and seek isomorphism, for which a high computational cost is to be paid. This gradually reduces the performance of the existing algorithms when the database has huge graph data. The proposed binary caterpillar MCIS algorithm to predict all MCIS of the database works for communication network graph database each of whose vertices has a unique label (IP address). In this, a new data structure which is a caterpillar-based binary tree is defined to reduce the search space of the problem using the concept of vertex cover and it takes into account all graphs of the database simultaneously to predict all MCIS of the database. This has substantially reduced unwanted comparisons among the datasets, when compared to the existing algorithms, as well as the difficulty of seeking isomorphism is avoided due to unique vertex labels. The experimental results further ensure the efficiency of the proposed algorithm with respect to existing works. [ABSTRACT FROM AUTHOR]

Frequent subgraph mining (FSM) is defined as finding all the subgraphs in a given graph that appear more number of times than a given value. It consists of two steps broadly, first is generating a candidate subgraph and second is calculating support of that subgraph. When the input to FSM algorithm is a single graph, calculating support of subgraph needs identifying its isomorphisms in the input graph. Identifying subgraph isomorphisms is NP-Complete problem. Evidently, fewer the number of candidates, fewer the support computations needed. In this paper we present a filtration technique that reduces the number of candidate subgraphs thereby reducing the overall time complexity by 7 to 18% experimentally. [ABSTRACT FROM AUTHOR]

Given two graphs, Subgraph Isomorphism is the problem of deciding whether the first graph (the base graph ) contains a subgraph isomorphic to the second one (the pattern graph ). This problem is NP-complete even for very restricted graph classes such as connected proper interval graphs. Only a few cases are known to be polynomial-time solvable even if we restrict the graphs to be perfect. For example, if both graphs are co-chain graphs, then the problem can be solved in linear time. In this paper, we present a polynomial-time algorithm for the case where the base graphs are chordal graphs and the pattern graphs are co-chain graphs. We also present a linear-time algorithm for the case where the base graphs are trivially perfect graphs and the pattern graphs are threshold graphs. These results answer some of the open questions of Kijima et al. (2012). To present a complexity contrast, we then show that even if the base graphs are somewhat restricted perfect graphs, the problem of finding a pattern graph that is a chain graph, a co-chain graph, or a threshold graph is NP-complete. [ABSTRACT FROM AUTHOR]

Within a given collection of graphs, a graph retrieval system may seek all graphs that contain a given graph, or may instead seek all graphs that are contained within a given graph. Although subgraph isomorphism is worst-case exponential, it may be average-case polynomial if graphs are labeled so as to restrict possible correspondences between vertices of included and includer graphs. Degree reduction is a procedure that uses logical inference to preclude some such correspondences, thereby substantially increasing the size of includer graphs that can be processed, without preventing any existent isomorphism from being found. Degree reduction works only with labeled graphs, which may be directed or undirected, with or without edge labels. Inexact or approximate isomorphism is accommodated by reducing strictness of conditions for perfect isomorphism. Disk-based degree reduction, which is an order of magnitude slower than memory-based degree reduction, has successfully processed graphs that have millions of vertices. Although the principle of degree reduction is simple and fundamental, its efficient practical implementation involves intricate procedural detail. Its average-case complexity analysis is currently intractable, so cost-benefit assessment has to be experimental. [ABSTRACT FROM AUTHOR]

We show that solving (bounded-degree) jigsaw puzzles requires Θ ( n 2 ) edge matching comparisons both in the worst case and in expectation, making all jigsaw puzzles as hard to solve as the trivial upper bound. This result applies to bounded-degree puzzles of all shapes, whether pictorial or apictorial. For non-bounded degree puzzles, we show that Ω ( n log ⁡ n ) is a tight bound. [ABSTRACT FROM AUTHOR]

This paper presents techniques designed to minimise the number of states which are explored during subgraph isomorphism detection. A set of advanced topological node features, calculated from n -neighbourhood graphs, is presented and shown to outperform existing features. Further, the pruning effectiveness of both the new and existing topological node features is significantly improved through the introduction of strengthening techniques. In addition to topological node features, these strengthening techniques can also be used to enhance application-specific node labels using a proposed novel extension to existing pruning algorithms. Through the combination of these techniques, the number of explored search states can be reduced to near-optimal levels. [ABSTRACT FROM AUTHOR]

Discovering motifs in protein–protein interaction networks is becoming a current major challenge in computational biology, since the distribution of the number of network motifs can reveal significant systemic differences among species. However, this task can be computationally expensive because of the involvement of graph isomorphic detection. In this paper, we present a new algorithm (CombiMotif) that incorporates combinatorial techniques to count non-induced occurrences of subgraph topologies in the form of trees. The efficiency of our algorithm is demonstrated by comparing the obtained results with the current state-of-the art subgraph counting algorithms. We also show major differences between unicellular and multicellular organisms. The datasets and source code of CombiMotif are freely available upon request. [ABSTRACT FROM AUTHOR]

An important task in biological information extraction is to identify descriptions of biological relations and events involving genes or proteins. In this work, we propose a graph-based approach to automatically learn rules for detecting biological events in the life science literature. The event rules are learned by identifying the key contextual dependencies from full parsing of annotated text. The detection is performed by searching for isomorphism between event rules and the dependency graphs of complete sentences. When applying our approach to the data sets of the Task 1 of the BioNLP-ST 2009, we achieved a 40.71% F-score in detecting biological events across nine event types. Our 56.32% precision is comparable with the state-of-the-art systems. The approach may also be generalized to extract events from other domains where training data are available because it requires neither manual intervention nor external domain-specific resources. The subgraph matching algorithm we developed is released under the new BSD license and can be downloaded from . [ABSTRACT FROM AUTHOR]

Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Gąsieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph. [ABSTRACT FROM AUTHOR]

Purpose – Virtual assembly process plays an important role in assembly design of complex product and is typically time- and resource-intensive. This paper aims to investigate a dynamic assembly simplification approach in order to demonstrate and interact with virtual assembly process of complex product in real time. Design/methodology/approach – The proposed approach regards the virtual assembly process of complex product as an incremental growth process of dynamic assembly. During the growth process, the current-assembled-state assembly model is simplified with appearance preserved by detecting and removing its invisible features, and the to-be-assembled components are simplified with assembly features preserved using conjugated subgraphs matching method based on an improved subgraph isomorphism algorithm. Findings – The dynamic assembly simplification approach is applied successfully to reduce the complexity of computer aided design models during the virtual assembly process and it is proved by several cases. Originality/value – A new assembly features definition is proposed based on the notion of “conjugation” to assist the assembly features recognition, which is a main step of the dynamic assembly simplification and has been translated into conjugated subgraphs matching problem. And an improved subgraph isomorphism algorithm is presented to address this problem. [ABSTRACT FROM AUTHOR]

Mining frequent patterns in a single network (graph) poses a number of challenges. Already only to match one path pattern to a network under subgraph isomorphism is NP-complete. Classical matching algorithms become intractable even for reasonably small patterns, on networks which are large or have a high average degree. Based on recent advances in parameterized complexity theory, we propose a novel miner for rooted trees in networks. The miner, for a fixed parameter $$k$$ (maximal pattern size), can mine all rooted trees with delay linear in the size of the network and only mildly exponential in the fixed parameter $$k$$ . This allows us to mine tractably, rooted trees, in large networks such as the WWW or social networks. We establish the practical applicability of our miner, by presenting an experimental evaluation on both synthetic and real-world data. [ABSTRACT FROM AUTHOR]

Given a pattern graphHwithledges, and a host graphGguaranteed to contain at most one occurrence of a subgraph isomorphic toH, we show that the time complexity of the problem of finding such an occurrence (if any) inGas well as that of the decision version of the problem are within a multiplicative factorO(l) of the time complexity for the corresponding problem in the general case, whenGmay contain several occurrences ofH. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices ofHin the induced case when occurrences of induced subgraphs ofGisomorphic toHare sought. [ABSTRACT FROM AUTHOR]

Abstract: Inexact subgraph matching based on type-isomorphism was introduced by Berry et al. [J. Berry, B. Hendrickson, S. Kahan, P. Konecny, Software and algorithms for graph queries on multithreaded architectures, in: Proc. IEEE International Parallel and Distributed Computing Symposium, IEEE, 2007, pp. 1–14] as a generalization of the exact subgraph matching problem. Enumerating small subgraph patterns in very large graphs is a core problem in the analysis of social networks, bioinformatics data sets, and other applications. This paper describes a MapReduce algorithm for subgraph type-isomorphism matching. The MapReduce computing framework is designed for distributed computing on massive data sets, and the new algorithm leverages MapReduce techniques to enable processing of graphs with billions of vertices. The paper also introduces a new class of walk-level constraints for narrowing the set of matches. Constraints meeting criteria defined in the paper are useful for specifying more precise patterns and for improving algorithm performance. Results are provided on a variety of graphs, with size ranging up to billions of vertices and edges, including graphs that follow a power law degree distribution. [Copyright &y& Elsevier]

Data mining in structured and semi-structured data focuses on frequent data values. However, in graph data mining, the focus is on common specific topologies. Graph mining, although its ubiquity, is a difficult task since it requires subgraph isomorphism which is known to be NP-complete. In order to effectively prune the search space and thereby save computational time, a graph mining algorithm requires that the support measure of a pattern to be no greater than that of its subpatterns. This property of the support measure is referred to in the literature as the down-closure, anti-monotonicity or admissibility. Unfortunately, when mining a single labeled graph, simply counting the occurrences of a graph pattern may not have the down-closure property. For this, most existing approaches mine frequent substructures in a set of labeled graphs (called also the transactional setting) and few efforts have been devoted to mining frequent globally distributed substructures in a single labeled graph. In this paper, we propose a graph mining algorithm, called NODAR(Non-Overlapping embeDding based grAph mineR), for computing common and globally distributed substructures in a single labeled graph. NODAR adopts the Depth-First Search (DFS) strategy and is based on the SMNOES (Size of Maximum Non Overlapping Embedding Set) as support measure. The core idea of NODAR is to automatically extract frequent subpatterns; and thus without frequency computation thanks to the down-closure property of SMNOES. By adopting this strategy in the computation of frequent substructures, NODAR reduces the number of subgraph isomorphism tests needed to compute pattern frequencies. Experimental results on monograph and transactional graph databases; and comparison with well-known probabilistic and exact algorithms; prove the efficacy of NODAR. [ABSTRACT FROM AUTHOR]

Abstract: We investigate the computational complexity of the following restricted variant of Subgraph Isomorphism: given a pair of connected graphs and , determine if is isomorphic to a spanning subgraph of . The problem is NP-complete in general, and thus we consider cases where and belong to the same graph class such as the class of proper interval graphs, of trivially perfect graphs, and of bipartite permutation graphs. For these graph classes, several restricted versions of Subgraph Isomorphism such as Hamiltonian Path, Clique, Bandwidth, and Graph Isomorphism can be solved in polynomial time, while these problems are hard in general. [Copyright &y& Elsevier]

Abstract: In this paper an extension to index-based subgraph matching is proposed. This extension significantly speeds up the indexing time for graphs where the nodes are labeled with a rather small amount of different classes. Furthermore, the needed storage amount is significantly reduced. In order to reduce the complexity, we introduce a weight function for labeled graphs. Using this weight function, a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, and on real-world datasets. The number of permutations for the real-world datasets have been decreased to a fraction of 10−5 and 10−8 in average compared to the original approach by Messmer. The novel indexing strategy makes indexing of larger graphs feasible, allowing for fast detection of subgraphs. [Copyright &y& Elsevier]