Search

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.

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.

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].

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.

In this paper, we extend the algorithm of [6] to solve the k-densest maximum common subgraph problem. By solving the k-densest maximum common subgraph isomorphism problem, we find high complexity common substructures between input graphs. We prove that our proposed objective function always gives the right answer to the corresponding QUBO problem.

Field-Programmable Gate Arrays (FPGAs) are used almost everywhere, from smart-phones to datacenters. FPGA functionality is determined by the intellectual property (IP) encoded within a vendor-proprietary binary configuration file, or bitstream, that is deployed on these devices. The potential value offered by IP creates many incentives for an adversary to attempt to steal it. The opaque nature of vendor bitstream formats has thus far limited the ability to detect stolen IP in deployed FPGAs. In this work we demonstrate the ability to detect instances of IP piracy given ONLY the FPGA configuration bitstream and a golden user netlist. While prior works have shown it is possible to reverse-engineer FPGA bitstreams into an underlying structural netlist, in isolation this netlist is of limited utility. We take this a step further by introducing ReCon, a tool to automatically assist in detecting pirated IP within a bitstream. ReCon first extracts a netlist from an unknown bitstream, then applies subgraph isomorphism algorithms to detect IP within the extracted netlist that are pirated from an original, or user, IP. Our experiments demonstrate ReCon as an effective method for piracy detection because it allows for a composite comparison between two bitstreams without needing to manually reverse engineer circuits and identify submodules.

To enhance the controllability and trustworthiness of the Internet, a new network control architecture has been presented with control task extracted to the intra-domain control node and executed in distributed multi-domain cooperative style. The study on control task assigning approach plays a central role in this network control pattern and shares some features with virtual network mapping problem. Different from the previous heuristics-based algorithms, we designs a baseline assigning algorithm which tests if the control task request can be mapped to a sub-graph of substrate control network or not without control task migration. Subsequently, an extend version is described under task migration considered. Our experiment evaluations show the impact of parameters on the runtime and assigning accuracy rate.

This thesis focuses on the detection of malware in industrial Internet. The basic flow of the detection of malware contains feature extraction and sample identification. API graph can effectively represent the behavior information of malware. However, due to the high algorithm complexity of solving the problem of subgraph isomorphism, the efficiency of analysis based on graph structure feature is low. Due to the different scales of API graph of different malicious codes, the API graph needs to be normalized. Considering the difficulties of sample collection and manual marking, it is necessary to expand the number of malware samples in industrial Internet. This paper proposes a method that combines PageRank with TF-IDF to process the API graph. Besides, this paper proposes a method to construct the adversarial samples of malwares based on GAN.

For a fixed "pattern" graph $G$, the $\textit{colored $G$-subgraph isomorphism problem}$ (denoted $\mathrm{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H) \to V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this problem is tied to parameterized versions of $\mathit{P}$ ${=}?$ $\mathit{NP}$ and $\mathit{L}$ ${=}?$ $\mathit{NL}$, among other questions. An overarching goal is to understand the complexity of $\mathrm{SUB}(G)$, under different computational models, in terms of natural invariants of the pattern graph $G$. In this paper, we establish a close relationship between the $\textit{formula complexity}$ of $\mathrm{SUB}$ and an invariant known as $\textit{tree-depth}$ (denoted $\mathrm{td}(G)$). $\mathrm{SUB}(G)$ is known to be solvable by monotone $\mathit{AC^0}$ formulas of size $O(n^{\mathrm{td}(G)})$. Our main result is an $n^{\tilde\Omega(\mathrm{td}(G)^{1/3})}$ lower bound for formulas that are monotone $\textit{or}$ have sub-logarithmic depth. This complements a lower bound of Li, Razborov and Rossman (SICOMP 2017) relating tree-width and $\mathit{AC^0}$ circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for first-order logic on finite structures (Rossman, ITCS 2017). The technical core of this result is an $n^{\Omega(k)}$ lower bound in the special case where $G$ is a complete binary tree of height $k$, which we establish using the $\textit{pathset framework}$ introduced in (Rossman, SICOMP 2018). (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth (Czerwi\'nski et al, arXiv:1904.13077).) Additional results of this paper extend the pathset framework and improve upon both, the best known upper and lower bounds on the average-case formula size of $\mathrm{SUB}(G)$ when $G$ is a path., Comment: 49 pages, 18 figures

Frequent pattern mining in graph data is a hot topic in recent years. At present, most frequent graph pattern mining methods use the concept of subgraph isomorphism for the matching of candidate graph pattern in data graph. However, in some applications where the accuracy of matching is not so strict, the topology constraints of subgraph isomorphism may lose some meaningful frequent patterns. Simulation matching plays an important role in graph pattern matching. However, in frequent graph pattern mining, it may lead to the matching between the connected candidate pattern and the disconnected substructure in the data graph. The topology of matching results can not be guaranteed, which greatly affects the quality of mining, and may lead to mining a large number of redundant graphics patterns with repeated structure. Therefore, this paper proposes a new concept of simulation matching - colSimulation, which can ensure the point-to-point matching between pattern graph and data graph, effectively avoid redundant mining results and improve the mining speed. The D-colSimulation proposed in this paper is a distributed frequent graph pattern mining method based on colSimulation for large-scale graph data. Experiments on datasets show that our method not only improves the mining efficiency, but also performs well on data sets with poor performance of subgraph isomorphism.

Circuit identification and classification is an important field of research in Electronic Design Automation (EDA). This paper provides a novel framework for circuit classification based on a Continuous Restricted Boltzmann Machine and Logistic Regression. An undirected graph representation of a circuit CNF instance is created and employed to perform CNF-signatures’ search, thereof we classify it. A library with CNF-signatures of thousands of logic gates and functional blocks was pre-generated by our framework. These signatures are searched in the original CNF instance graph via traditional subgraph isomorphism algorithm and the results are applied as inputs for the Boltzmann Machine. Finally, a Logistic Regression classifier can determine to which class of the circuit each instance belongs. Our implementation is capable to correctly identify several circuit classes such as adders, multipliers and dividers with accuracy over 92%.

Structural Equivalence refers to the ability to exchange two vertices in a graph without changing the structure of the graph. We provide basic definitions and properties applicable to the subgraph isomorphism problem. We show examples of structural equivalence that reduce the size of the search tree for subgraph isomorphism counting and enumeration, applied to multichannel networks.

A well-known $\mathcal{N}\mathcal{P}$-hard problem from graph theory is the subgraph isomorphism problem where the goal is for given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. A plethora of algorithms for solving the problem exist in literature and most of them are based on the backtracking approach. In this paper, we explore several such algorithms. In particular, we focus on algorithmic techniques as well as code tuning and optimization approaches with the goal of refining basic backtracking algorithms. We also experimentally compare the performance of algorithms in order to evaluate and demonstrate their usefulness in practice.

Research on networks is commonly performed using anonymized network data for various reasons such as protecting data privacy. Under such circumstances, it is difficult to verify the source of network data, which leads to questions such as: Given an anonymized graph, can we identify the network from which it is collected? Or if one claims the graph is sampled from a certain network, can we verify it? The intuitive approach is to check for subgraph isomorphism. However, subgraph isomorphism is NP-complete; hence, infeasible for most large networks. Inspired by biometrics studies, we address these challenges by formulating two new problems: network identification and network authentication. To tackle these problems, similar to research on human fingerprints, we introduce two versions of a network identity: (1) embedding-based identity and (2) distribution-based identity. We demonstrate the effectiveness of these network identities on various real-world networks. Using these identities, we propose two approaches for network identification. One method uses supervised learning and can achieve an identification accuracy rate of 94.7%, and the other, which is easier to implement, relies on distances between identities and achieves an accuracy rate of 85.5%. For network authentication, we propose two methods to build a network authentication system. The first is a supervised learner and provides a low false accept rate and the other method allows one to control the false reject rate with a reasonable false accept rate across networks. Our study can help identify or verify the source of network data, validate network-based research, and be used for network-based biometrics.

The development of multi-core processors has been providing benefits to many industries. However, some issues may arise among these benefits because of the potential conflicts between parallel applications. One of the important concerns is the reliability of the safety critical applications. This paper proposes two algorithms for computing a probability of failure of the safety-critical application on reconfigurable multi-core architecture. One is based on the exact analytical computation; whereas, the other one is the approximated of the former with less computational expensive. These algorithms adopts a combination of a fault tree analysis and a subgraph isomorphism problem to apply for avionics application. Their numerical results and performance analysis are also included.

This work presents an update to the triangle-counting portion of the subgraph isomorphism static graph challenge. This work is motivated by a desire to understand the impact of CUDA unified memory on the triangle-counting problem. First, CUDA unified memory is used to overlap reading large graph data from disk with graph data structures in GPU memory. Second, we use CUDA unified memory hints to solve multi-GPU performance scaling challenges present in our last submission. Finally, we improve the single-GPU kernel performance from our past submission by introducing a work-stealing dynamic algorithm GPU kernel with persistent threads, which makes performance adaptive for large graphs without requiring a graph analysis phase.

A subgraph query finds all data graphs in a graph database each of which contains the given query graph. Existing work takes the indexing-filtering-verification (IFV) approach to first index all data graphs, then filter out some of them based on the index, and finally test subgraph isomorphism on each of the remaining data graphs. This final test of subgraph isomorphism is a sub-problem of subgraph matching, which finds all subgraph isomorphisms from a query graph to a data graph. As such, in this paper, we study whether, and if so, how to utilize efficient subgraph matching to improve subgraph query processing. Specifically, we modify leading subgraph matching algorithms and integrate them with top-performing subgraph querying algorithms. Our results show that (1) the slow verification method in existing IFV algorithms can lead us to over-estimate the gain of filtering; and (2) our modified subgraph querying algorithms with efficient subgraph matching are competitive in time performance and can scale to hundreds of thousands of data graphs and graphs of thousands of vertices.

Subgraph Matching is a fundamental problem in graph analysis, and is widely used in many application scenarios in biology, chemistry and social network. Given a data graph and a query graph, subgraph matching aims to compute all subgraphs of the data graph that are isomorphic to the query graph. The problem is computationally expensive as the core operation it depends on, known as subgraph isomorphism, is NP-complete. In recent years, graph is increasing extensively and it is hard to compute subgraph matching on massive graph data using existing serial algorithm. Meanwhile, there exist distributed solutions, but they are mostly limited to the case where the graphs are unlabelled. In response to this gap, we study the subgraph matching problem in the multi-core environment. From the algorithm level, we propose a multi-core parallel subgraph matching algorithm called MPMatch. From the research level, we explore the concurrent allocation of subgraph matching search space to approach load balancing. We conduct extensive empirical studies on real and synthetic graphs to demonstrate that our techniques improve the performance of serial subgraph matching algorithm via parallelization and well-developed load balancing schema.

Graph database query languages feature expressive yet computationally expensive pattern matching capabilities. Answering optional query clauses in SPARQL for instance renders the query evaluation problem immediately PSPACE-complete. Light-weight graph pattern matching relations, such as simulation, have recently been investigated as promising alternatives to more expensive query mechanisms like, e.g., computing subgraph isomorphism. Still, pattern matching alone lacks expressive query capabilities: graph patterns may be combined by usual inner joins. However, including more sophisticated operators is inevitable to make solutions more useful for emerging applications. In this paper we bridge this gap by introducing a new dual simulation process operating on SPARQL queries. In addition to supporting the full syntactic structure of SPARQL queries, it features polynomial-time pattern matching to compute an overapproximation of the query results. Moreover, to achieve running times competing with state-of-the-art database systems, we develop a novel algorithmic solution to dual simulation graph pattern matching, based on a system of inequalities that allows for several optimization heuristics. Finally, we achieve soundness of our process for SPARQL queries including UNION, AND and OPTIONAL operators not restricted to well-designed patterns. Our experiments on synthetic and real-world graph data promise a clear gain for graph database systems when incorporating the new dual simulation techniques.

Subgraph isomorphism problem on specialized graphs is an open research area. Most of the algorithms that had been developed for subgraph isomorphism problem are designed for general graphs. Although, they can be utilized for any graph type, this generic design prevents to take advantages of characteristics of the specialized graphs to burst performance of the subgraph isomorphism search. In this study, we will introduce a novel branch and bound algorithm for subgraph isomorphism problem on bipartite graphs. Bipartite feature of these graphs is utilized to improve search performance by limiting the size of possibility set and by getting rid of backtracking phase of branch and bound technique. Experimental results show that the algorithm provides between 10 and 120 fold better performance results on bipartite graphs when it is compared with the state-ofart algorithms.

We propose an extended Darwinian Genetic Algorithm that builds upon the traditional genetic algorithm in the efforts to more accurately depict the process of natural selection We demonstrate the capabilities of this algorithm by employing it with an existing state encoding based watermarking system for sequential circuits that was previously hindered by attempting to naively solve the subgraph isomorphism problem that arises during the watermark embedding process. Wherein using the proposed approach we are able to demonstrate maximal savings for a 64-bit watermark of 26%, 23%, and 20%, in addition to the 128-bit watermark where maximal savings were 30%, 29%, and 20% over the current state-of-the-art in terms of literals, area, and delay required for synthesizing the watermarked finite state machines, respectively. Additionally, average savings for the 64-bit watermark were 1%, and 2% with 4% overhead and for the 128-bit watermark average savings were 12%, 7%, and 2%, in terms of literals, area, and delay.

Querying large graphs to retrieve information in permissible time is an emerging research problem, and it has roots in various application domains, mainly to analyse large networks. For a given query graph, the aim of subgraph isomorphism finding in a data graph is to identify all its subgraphs that are isomorphic to the query graph, and it has become the central problem for querying large graphs. Though different research groups have proposed many techniques using graph compression, postponing cartesian products, and candidate region exploration in the recent past, most of them show exponential behaviour for some query graphs on a large data graph. In this paper, we propose a subgraph isomorphism finding method, SubISO, which uses an objective function based on the eccentricity and some isomorphic invariants of the vertices of the query graph to minimize the number and size of the candidate regions in the data graph. Since subgraph isomorphism finding has a large number of solutions, especially in a large graph with repeated node labels, we propose to limit the maximum number of recursive calls of the generic subgraph search function to complete the execution of SubISO and return at most k-relevant matches. The SubISO finds at most k-relevant solutions in reasonable elapsed time over the queries for which existing state-of-the-art methods show exponential behaviour.

Subgraph discovery in a single data graph---finding subsets of vertices and edges satisfying a user-specified criteria---is an essential and general graph analytics operation with a wide spectrum of applications. Depending on the criteria, subgraphs of interest may correspond to cliques of friends in social networks, interconnected entities in RDF data, or frequent patterns in protein interaction networks to name a few. Existing systems usually examine a large number of subgraphs while employing many computers and often produce an enormous result set of subgraphs. How can we enable fast discovery of only the most relevant subgraphs while minimizing the computational requirements? We present Nuri, a general subgraph discovery system that allows users to succinctly specify subgraphs of interest and criteria for ranking them. Given such specifications, Nuri efficiently finds the k most relevant subgraphs using only a single computer. It prioritizes (i.e., expands earlier than others) subgraphs that are more likely to expand into the desired subgraphs (prioritized subgraph expansion) and proactively discards irrelevant subgraphs from which the desired subgraphs cannot be constructed (pruning). Nuri can also efficiently store and retrieve a large number of subgraphs on disk without being limited by the size of main memory. We demonstrate using both real and synthetic datasets that Nuri on a single core outperforms the closest alternative distributed system consuming 40 times more computational resources by more than 2 orders of magnitude for clique discovery and 1 order of magnitude for subgraph isomorphism and pattern mining.

This paper presents an updated CUDA implementation of the triangle counting and k-truss decomposition, the two analytics of the Subgraph Isomorphism Graph Challenge. Algorithmic improvements and a new GPU architecture (Volta) resulted in an order of magnitude speedup.

As part of the 2018 MIT-Amazon Graph Challenge on subgraph isomorphism, we propose a novel joint hierarchical clustering and parallel counting technique called the PHC algorithm that can compute the exact number of triangles in large graphs. The PHC algorithm consists of first pruning followed by hierarchical clustering based on geodesic distance and then triangle counting in parallel. This allows scalable software framework such as MapReduce/Hadoop to count triangles inside each cluster as well as those straddling between clusters in parallel. We characterize the performance of the PHC algorithm mathematically, and its performance evaluation using representative graphs including random graphs demonstrates its computational efficiency over other existing techniques.1

Real-life graph datasets extracted from Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. One of the main issues is to automatically repair the graph with some repairing rules. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair the graph data. In this paper, we introduce an automatic repairing semantic for graphs, called Graph-Repairing Rules (GRRs). This semantic can capture the incompleteness, conflicts, and redundancies in the graphs and indicate how to correct these errors. We study three fundamental problems associated with GRRs, implication, consistency and termination, which show whether a given set of GRRs make sense. Repairing the graph data using GRRs involves a problem of finding isomorphic subgraphs of the graph data for each GRR, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our GRR semantic and corresponding repairing algorithms can effectively and efficiently repair real-life graph data.

We investigate the problem of mining graph-based usage patterns for large, object-oriented frameworks like Android—revisiting previous approaches based on graph-based object usage models (groums). Groums are a promising approach to represent usage patterns for object-oriented libraries because they simultaneously describe control flow and data dependencies between methods of multiple interacting object types. However, this expressivity comes at a cost: mining groums requires solving a subgraph isomorphism problem that is well known to be expensive. This cost limits the applicability of groum mining to large API frameworks. In this paper, we employ groum mining to learn usage patterns for object-oriented frameworks from program corpora. The central challenge is to scale groum mining so that it is sensitive to usages horizontally across programs from arbitrarily many developers (as opposed to simply usages vertically within the program of a single developer). To address this challenge, we develop a novel groum mining algorithm that scales on a large corpus of programs. We first use frequent itemset mining to restrict the search for groums to smaller subsets of methods in the given corpus. Then, we pose the subgraph isomorphism as a SAT problem and apply efficient pre-processing algorithms to rule out fruitless comparisons ahead of time. Finally, we identify containment relationships between clusters of groums to characterize popular usage patterns in the corpus (as well as classify less popular patterns as possible anomalies). We find that our approach scales on a corpus of over five hundred open source Android applications, effectively mining obligatory and best-practice usage patterns.

A hypergraph consisting of nodes and hyperedges that connects multiple nodes can model complex relationships among entities effectively. In this work, we study a subhypergraph isomorphism search method that finds all isomorphic subhypergraphs to the query. Existing works of subgraph isomorphism in an ordinary graph try to reduce search space for a query graph to decrease computational costs, since a subgraph isomorphism problem is known to be NP-hard. However, previous methods of finding isomorphic subhypergraphs for hypergraphs do not make much effort for decreasing costs. In this paper, we propose a method that finds subhypergraph isomorphism efficiently. We first select nodes and edges that are likely to match to a query hypergraph, with consideration for characteristics of hyperedges. Then, we verify isomorphism between remaining subgraphs of data hypergraph and a query hypergraph. Experimental results show that our proposed method outperforms existing methods.

Reifying a constraint c consists in associating a Boolean variable b with c such that c is satisfied if and only if b is true, which can be denoted by c^{reif}: c b. Reification is useful for logically combining constraints and counting how many reified constraints can be satisfied. Since table constraints play an important role within constraint programming, in this paper, we are interested in their reification. We introduce a filtering algorithm that allows us to establish generalized arc consistency on reified table constraints, with no spatial overhead. We also propose a flexible approach that can generally reify any subsets of constraints. We show the practical interest of our work on the Max-CSP problem and a variation of the subgraph isomorphism problem.

Subgraph isomorphism is one of the fundamental search problems in computer science. In this article 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. All algorithms for this problem use a variation of backtracking. Most commonly they assign one vertex of G to one vertex of H at each level of the search tree. The order of vertices for the assignment is the crucial factor determining the size of this search tree. But it is very hard to determine in advance the impact of the order for a particular instance. We use a method called heuristic sampling to estimate the size of the tree. 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 of instances, showing the practical potential of the method.

Graph pattern matching has wide applications in social network analysis, such as identifying important communities, social roles and hidden behavior structures. Existing algorithms are mainly designed for single-pattern tasks, where patterns are processed sequentially and independently. However, many scenarios require multiple patterns to be processed as a batch, where single-pattern scheme will cost much redundant computation caused by matching similar sub-structures in the pattern set. Therefore, the sequential graph pattern matching scheme is not always the most efficient. This paper aims to propose a multiple pattern graph optimization algorithm for the subgraph isomorphism task. We comprehensively study the structural correlations among the multiple patterns and represent them by a compact tree-structured index. To support fast insertion and deletion of the pattern index, we present a dynamic updating algorithm to avoid index reconstruction from scratch. Based on the index, an efficient matching algorithm is proposed to answer multiple patterns in a heuristic scheduling order and avoid redundant computation. Extensive experiments on real and synthetic datasets prove that our solution is several times faster comparing with the state-of-the-art work.

This paper presents the details of a CUDA implementation of the Subgraph Isomorphism Graph Challenge, a new effort aimed at driving progress in the graph analytics field. challenge consists of two graph analytics: triangle counting and k-truss. We present our CUDA implementation of the graph triangle counting operation and of the k-truss subgraph decomposition. Both implementations share the same codebase taking advantage of a set intersection operation implemented via bitmaps. The analytics are implemented in four kernels optimized for different types of graphs. At runtime, lightweight heuristics are used to select the kernel to run based on the specific graph taken as input.

In this paper, we present collaborative CPU + GPU algorithms for triangle counting and truss decomposition, the two fundamental problems in graph analytics. We describe the implementation details and present experimental evaluation on the IBM Minsky platform. The main contribution of this paper is a thorough benchmarking and comparison of the different memory management schemes offered by CUDA 8 and NVLink, which can be harnessed for tackling large problems where the limited GPU memory capacity is the primary bottleneck in traditional computing platform. We find that the collaborative algorithms achieve 28× speedup on average (180× max) for triangle counting, and 165× speedup on average (498× max) for truss decomposition, when compared with the baseline Python implementation provided by the Graph Challenge organizers.

The rise of graph analytic systems has created a need for ways to measure and compare the capabilities of these systems. Graph analytics present unique scalability difficulties. The machine learning, high performance computing, and visual analytics communities have wrestled with these difficulties for decades and developed methodologies for creating challenges to move these communities forward. The proposed Subgraph Isomorphism Graph Challenge draws upon prior challenges from machine learning, high performance computing, and visual analytics to create a graph challenge that is reflective of many real-world graph analytics processing systems. The Subgraph Isomorphism Graph Challenge is a holistic specification with multiple integrated kernels that can be run together or independently. Each kernel is well defined mathematically and can be implemented in any programming environment. Subgraph isomorphism is amenable to both vertex-centric implementations and array-based implementations (e.g., using the Graph-BLAS.org standard). The computations are simple enough that performance predictions can be made based on simple computing hardware models. The surrounding kernels provide the context for each kernel that allows rigorous definition of both the input and the output for each kernel. Furthermore, since the proposed graph challenge is scalable in both problem size and hardware, it can be used to measure and quantitatively compare a wide range of present day and future systems. Serial implementations in C++, Python, Python with Pandas, Matlab, Octave, and Julia have been implemented and their single threaded performance have been measured. Specifications, data, and software are publicly available at GraphChallenge.org.

We propose algorithms that uses fast graph mining for resolving the network topology to a locally regulated area defined as a component of network topology. Though the IP backbone network should be reconfigured periodically in accordance with environmental changes, reconfiguration results in heavy workload, such as routing re-designs or testing these re-designs for network operators. If a network can be reconfigured within the component, however, we can drastically reduce the operation workload for network reconfiguration. For finding the components from the network topology, we should solve the subgraph isomorphism problem, which is NP-hard. We propose the heuristic graph mining algorithm that reduces the size of search space by considering network operating conditions. We visualize the results of components analysis, and show that the computation finishes within the practical time.

Hardware Trojan detection, which is very important to the chip security, has drawn more and more attention in both academia and industry. In this paper, we propose a novel hardware Trojan detection scheme named HTChecker, which detects hardware Trojans with subgraph isomorphism based on static characteristics of Trojans. Unlike other schemes, HTChecker pay more attention to preventing the replication and dissemination of hardware Trojans. We evaluate the HTChecker with random mixtures of Trojans and circuits from ITC'99 benchmarks and OpenCores. Experiments show that HTChecker can detect Trojans quickly and accurately without “Golden Chip” and it can cope with actual VLSI designs with large scale efficiently.

We investigate a subgraph mining framework, that can connect similar entities according to their structure and attribute similarities. We take one mapping between two related points chosen from the query and target graph as one vertex in the correspondence graph and decide the weight of the edge based on the similarity score. In this way, we transform the problem to a dense subgraph discovery problem. To adapt this method to large scale, we choose the candidate group by some effective pruning methods. We also add some techniques to make our method more flexible to fit uncertain user sketched input. We investigate how changes to certain parameters in the algorithm can influence the results. By integrating all these adjustments into the framework, we can provide a method that exhibits both accuracy and flexibility in many situations with a degree of generality. Experiments on both certain and uncertain query graphs can give satisfactory and informative results.

Graph pattern mining is an important part of the emerging social network science, and the research of the maximum clique problem is one of the most important research branches. In the big data environment, the mass of nodes and complexity of edges in the graph set a higher requirement on the speed and accuracy of the maximum clique (MCP) study. In this paper, we present a parallel graph partitioning framework for solving the maximum clique problem(PPMC) based on Hadoop. Firstly, This paper presents a new graph partition method based on degree sorting(GPD), the subgraph scale is greatly reduced. In order to balance the workload of solving the maximum clique problems. Secondly, the improved ant algorithm proposed by our team is used to solve the maximum clique of each subgraph. Finally, the framework is deployed on Hadoop distributed cloud computing platform and tested by Stanford large-scale datasets. The experimental results show that GPD algorithm can greatly reduce the subgraph scale, the subgraph number, and the complexity of time and space of solving the maximum clique problem of large-scale instances. And the efficiency and scalability of the Hadoop based parallel graph partitioning framework for solving the maximum clique problems has been further proved.

We describe a test statistic based on the L1-norm of the eigenvectors of a modularity matrix to detect the presence of an embedded Erdős Renyi (ER) subgraph inside a larger ER random graph. An embedded subgraph may model a hidden community in a large network such as a social network or a computer network. We make use of the properties of the asymptotic distribution of eigenvectors of random graphs to derive the distribution of the test statistic under certain conditions on the subgraph size and edge probabilities. We show that the distributions differ sufficiently for well defined ranges of subgraph sizes and edge probabilities of the background graph and the subgraph. This method can have applications where it is sufficient to know whether there is an anomaly in a given graph without the need to infer its location. The results we derive on the distribution of the components of the eigenvector may also be useful to detect the subgraph nodes.

In the real world, many problems on massive graphs can be mapped to an underlying critical problem of discovering top-k subgraphs. For massive graphs, subgraph queries may have enormous number of matches, and so it is inefficient to compute all matches when only top-k matches are desired. Meanwhile, parallel algorithm is urgent for the scalability of massive graph computing. In this paper, we address the challenges of top-k subgraph query in massive graph. Firstly, we present a new graph matching notion: “approximate graph simulation”. With approximate graph simulation, top-k subgraph query can be customized by appointing a weighted query graph, which provides good flexibility for different application scenarios. Secondly, we propose a parallel top-k subgraph query algorithm at the level of vertex. With such algorithm, each vertex in massive graph obtains its matching state separately without requiring global graph information. In the algorithm, we also design a filter mechanism to speed up the the computation and a aggregation mechanism to obtain top-k vertices for query focus. Using real-life datasets, we experimentally verify that our approach of parallel top-k subgraph query are efficient.

Subgraph isomorphism is a fundamental graph problem with many applications. Due to its NP-Hard nature, subgraph isomorphism in large dynamic graphs is considered as a challenging problem. In this paper, we present a distributed graph pruning algorithm (D-IDS) for dynamic graphs to enable efficient subgraph isomorphism. D-IDS continuously maintains the maximum dual simulation match in a dynamic graph. We develop D-ISI, a distributed incremental algorithm for subgraph isomorphism that utilizes D-IDS. We evaluated our algorithms on a commodity cluster in Amazon EC2 using real world graph datasets. Our evaluation results show that the graph pruning technique is highly effective on graphs with small diameter where it achieves over 60% reduction in graph size.

The k-ary n-cube is one of the most attractive interconnection networks for parallel and distributed computing systems. In this paper, we investigate Hamiltonian cycle and path embeddings in 3-ary 3-cubes based on K1,3-structure faults, which means each faulty element is isomorphic to any connected subgraph of a connected graph K1,3. We show that for two arbitrary distinct healthy nodes of a faulty 3-ary 3-cube, there exists a fault-free Hamiltonian path connecting these two nodes if there exists at most one faulty element that is isomorphic to any connected subgraph of K1,3. We also show that there exists a fault-free Hamiltonian cycle if the number of faulty elements are at most 2 and each faulty element is isomorphic to any connected subgraph of K1, 3.

The identification and enumeration of small, nonisomorphic graphs, called graphlets, within larger graphs is an analytic tool used for graph analytics. The problem of identifying graphlets embedded within a larger graph is a larger implementation of the graph isomorphism problem, with no known polynomial time algorithmic solution. One common method to identify the class of a given subgraph embedded within a supergraph is to make a degree list, called a signature, of it, and compare it to a list of known signatures and their corresponding graphlets. However, some graphlets have the same signature. Extra processing is needed to differentiate between them, and the existing method for determining how to differentiate them is by inspection and on a case by case basis. This paper proposes an algorithm to differentiate graphlets with identical signatures which significantly outperforms the existing method. A search space reduction technique is also proposed to reduce the computation cost.

While numerous applications, such as social networks, protein-protein interaction networks, and bibliographic networks, mainly consist of graph-structured data, massive graphs, of which the scales range from million nodes to billion nodes, are common-place. Searching within these kinds of graphs is urged to be efficient. Unfortunately, since the subgraph isomorphism problem is NP-complete, querying on large graphs is still challenging.

Recently, subgraph matching has been implemented in more and more domains, such as social network and semantic web. An approximated solution for subgraph matching named strong simulation has been put forward. Strong Simulation can preserve the topology of data graphs and find a bounded number of matches, but the complexity further holds a cubic-time, so it's yet intractable to deal with large graphs. To solve the problem, this paper focuses on a partition scheme to reduce the search space of subgraph matching algorithm. Firstly, we present a pruning method on data graph based on the connection relationships of nodes and edges in query graph. Secondly, we propose to use a multilevel partitioning algorithm when the subgraphs we get from former step are too large. Thirdly, we propose an algorithm for subgraph matching based on the partitioning scheme, which can preserve the topology of query graph and guarantee the correctness of results. Lastly, we experimentally prove the effectiveness and efficiency of this scheme, both using real-life data and synthetic data. It turns out that our method is quite efficient and the matching results are also satisfactory.

A major aspect of Cyber-physical production systems is to increase adaptability regarding the physical structure of manufacturing components as well as of the applied software systems. This is motivated by the increasing engineering efforts of manufacturing systems due to changing requirements, varying product variants and also malfunctions. In context of the method plug and produce physical adaptability, the customization of the plant layout of a production system, is an integral part. Physical adaptions become necessary when e.g. the production process is changed, the process performance requires to be optimized or manufacturing components need to be replaced. Consequently, a technique for determining appropriate manufacturing modules for a given production process is needed. In contrast to current methods this paper presents a novel approach for physical adaptability especially respecting the discrete system behavior of manufacturing modules. For this purpose, subgraph isomorphism is combined with a semantic matching filter together with additional matching criteria. Both, matching filter and matching criteria are tailored to the use case of plug and produce. Based on a case-study the proposed method is evaluated. The matching quality is assessed using macro-averaged precision and the normalized discounted cumulative gain.

Kinematic chain Isomorphism identification (KCII), as an important application of graph isomorphism, plays a crucial role in mechanism creative design. However, traditional methods used in KCII lack efficiency and usually occupy high memory space. In this paper, a highly efficient algorithm is proposed, and an optimized circuit simulation method and the adjacency list are applied. The experimental results for KCII demonstrate a great improvement in computation efficiency compared with the original circuit simulation method and VF2 algorithm (in the symmetrical graphs situation).

The maximum common subgraph of two graphs, G1 and G2, is the largest subgraph in G1 that is isomorphic to a subgraph in G2. Finding the maximum common subgraph of two given graphs is known to be a NP-complete problem. An exact solution for the maximum common subgraph problem can be found by an algorithm that transforms the maximum common subgraph problem into a maximal clique enumeration problem. However, as the size of the graph increases, the solution space of the maximal clique enumeration problem increases combinatorially. A serial solution to the computationally intensive problem of complete maximal clique enumeration is tedious. This paper presents a parallel approach using Graphic Processing Unit to compute the maximum common subgraph of the given graphs. The parallel procedure achieves more than tenfold improvement in computational performance. As an application of the proposed parallel maximum common subgraph algorithm, two new tools, LIGANDMATCHER and GRAPHSCREEN are developed. These tools can be used to narrow down the large ligand search space to a small number in the screening phase of drug discovery process.

Given a query graph $q$ , retrieving the data graphs $g$ from a set $D$ of data graphs such that $q$ contains $g$ , namely supergraph containment search, is fundamental in graph data analysis with a wide range of real applications. It is very challenging due to the NP-Completeness of subgraph isomorphism testing. Driven by many real applications, in this paper, we study the problem of probabilistic supergraph search; that is, given a set $D$ of uncertain data graphs, a certain query graph $q$ and a probability threshold $\theta$ , we retrieve the data graphs $g^{u}$ from $D$ such that the probability of $q$ containing $g^{u}$ is not smaller than $\theta$ . We show that besides the NP-Completeness of subgraph isomorphism testing, the problem of calculating probabilities is #P-Complete; thus, it is even more challenging than the supergraph containment search. To tackle the computational hardness, we first propose two novel pruning rules, based on probabilistic connectivity and features, respectively, to efficiently prune non-promising data graphs. Then, efficient verification algorithms are developed with the aim of sharing computation and terminating non-promising computation as early as possible. Extensive performance studies on both real and synthetic data demonstrate the efficiency and effectiveness of our techniques in practice.