Search

Consider a large labeled graph (network), denoted the target. Subgraph matching is the problem of finding all instances of a small subgraph, denoted the query, in the target graph. Unlike the majority of existing methods that are restricted to graphs with labels solely on vertices, our proposed approach, named can effectively handle graphs with labels on both vertices and edges. ntroduces an efficient new vertex/edge domain data structure filtering procedure to speed up subgraph queries. The procedure, called path-based reduction, filters initial domains by scanning them for paths up to a specified length that appear in the query graph. Additionally, ncorporates existing techniques like variable ordering and parent selection, as well as adapting the core search process, to take advantage of the information within edge domains. Experiments in real scenarios such as protein–protein interaction graphs, co-authorship networks, and email networks, show that s faster than state-of-the-art systems varying the number of distinct vertex labels over the whole target graph and query sizes. [ABSTRACT FROM AUTHOR]

A key function of mobile networks is the ability to dynamically reshape itself to any desired geometry. Lacking absolute position awareness, agents often rely on distance-limited inter-agent spatial measurements to maintain state awareness. Methods of formation control must therefore ensure a minimal level of persistent pairwise measurement feedback throughout transition, giving rise to the classic connectivity maintenance problem. To address this problem, we propose a method of structure-preserving assignment, matching agents to desired positions such that persistent global connectivity is naturally and automatically satisfied under smooth transition. Compared to other approaches, this complementary technique reduces reliance on aggressive or costly mid-flight formation control protocols. The technique is shown to scale and even improve with network size. [ABSTRACT FROM AUTHOR]

Abstract Deep Learning (DL) has been widely used in many applications, and its success is achieved with large training data. A key issue is how to provide a DL solution when there is no large training data to learn initially. In this paper, we explore a meta-learning approach for a specific problem, subgraph isomorphism counting, which is a fundamental problem in graph analysis to count the number of a given pattern graph, p, in a data graph, g, that matches p. There are various data graphs and pattern graphs. A subgraph isomorphism counting query is specified by a pair, (g, p). This problem is NP-hard and needs large training data to learn by DL in nature. We design a Gaussian Process (GP) model which combines Graph Neural Network with Bayesian nonparametric, and we train the GP by a meta-learning algorithm on a small set of training data. By meta-learning, we can obtain a generalized meta-model to better encode the information of data and pattern graphs and capture the prior of small tasks. With the meta-model learned, we handle a collection of pairs (g, p), as a task, where some pairs may be associated with the ground-truth, and some pairs are the queries to answer. There are two cases. One is there are some with ground-truth (few-shot), and one is there is none with ground-truth (zero-shot). We provide our solutions for both. In particular, for zero-shot, we propose a new data-driven approach to predict the count values. Note that zero-shot learning for our regression tasks is difficult, and there is no hands-on solution in the literature. We conducted extensive experimental studies to confirm that our approach is robust to model degeneration on small training data, and our meta-model can fast adapt to new queries by few-shot and zero-shot learning.

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.

Deep Learning (DL) has been widely used in many applications, and its success is achieved with large training data. A key issue is how to provide a DL solution when there is no large training data to learn initially. In this paper, we explore a meta-learning approach for a specific problem, subgraph isomorphism counting, which is a fundamental problem in graph analysis to count the number of a given pattern graph, p, in a data graph, g, that matches p. There are various data graphs and pattern graphs. A subgraph isomorphism counting query is specified by a pair, (g, p). This problem is NP-hard and needs large training data to learn by DL in nature. We design a Gaussian Process (GP) model which combines Graph Neural Network with Bayesian nonparametric, and we train the GP by a meta-learning algorithm on a small set of training data. By meta-learning, we can obtain a generalized meta-model to better encode the information of data and pattern graphs and capture the prior of small tasks. With the meta-model learned, we handle a collection of pairs (g, p), as a task, where some pairs may be associated with the ground-truth, and some pairs are the queries to answer. There are two cases. One is there are some with ground-truth (few-shot), and one is there is none with ground-truth (zero-shot). We provide our solutions for both. In particular, for zero-shot, we propose a new data-driven approach to predict the count values. Note that zero-shot learning for our regression tasks is difficult, and there is no hands-on solution in the literature. We conducted extensive experimental studies to confirm that our approach is robust to model degeneration on small training data, and our meta-model can fast adapt to new queries by few-shot and zero-shot learning. [ABSTRACT FROM AUTHOR]

Graphs have been used in different fields of research for performing structural analysis of various systems. In order to compare the structure of two systems, the correspondence between their graphs has to be verified. The problem of graph matching, especially subgraph isomorphism (SI), has been well studied in case of static graphs. However, many applications require incorporating temporal information, making the corresponding graphs dynamic. In this paper, we apply SI to detect dynamic patterns in dynamic graphs. We propose an algorithm for induced SI to detect all the matchings for a given pattern graph while considering snapshot-based representation of dynamic graphs and taking into account the chronological order of these snapshots. This is the novelty of the proposed approach since the existing state-of-the-art algorithms model dynamic graphs using an aggregated model with time-stamped edges. To the best of our knowledge, there does not exist another approach which considers snapshot-based representation of dynamic pattern and dynamic target graphs for this problem. We discussed the time complexity of our algorithm and tested its performance while comparing it with two existing algorithms using the real-world datasets. It was found that our algorithm is the second best overall in terms of the execution time. The results are promising given the fact that the choice of dynamic graph model affects the algorithmic design for solving the problem of SI. For the applications where aggregated model of dynamic graphs is not applicable and snapshot-based representation is indispensable, our algorithm can be directly applied as opposed to the existing ones. [ABSTRACT FROM AUTHOR]

NP-complete and NP-hard problems, such as subgraph isomorphism, are well-known benchmarks to evaluate computation power of unconventional computing approaches. Optical computing, as one of the most important unconventional approaches, has determinant features such as massive parallelism that allows us to solve hard computational problems in an efficient time, while in the similar situations conventional computers require exponential time. In this paper, we solve subgraph isomorphism, as an NP-complete problem, using optical computing in a polynomial time after a polynomial preprocessing time. The proposed method has two main steps: first, possible solution space of the problem is generated using an optical manner and then all invalid solutions are eliminated from the space by several designed optical filters. The filters are made in the preprocessing phase in a polynomial time while the space of each filter is exponential. In this study, we have provided a solution to the YES/NO decision version of the problem. [ABSTRACT FROM AUTHOR]

The resource scheduling problem of UAV communication networks has always been a hot research issue in the current environment. However, most of the current research focuses on meeting the user's time cost requirements and rarely considers the user's security requirements in the scheduling process. To solve the problems of low efficiency, more resource fragments, low network reliability, and unbalanced load, this paper improves the virtual network mapping model into a three-layer structure consisting of a security service request layer, virtual network provider layer, and security resource layer, so that it can be applied to the special scenario of security resource scheduling in an unmanned aerial communication network. An intelligent UAV communication network security resource scheduling algorithm based on optimized subgraph isomorphism and link segmentation is proposed. Intelligent UAVs can predict all possible access nodes and intelligently provide network services. The algorithm first improves and enriches the node constraint conditions and evaluation indicators, integrates the node resource attributes and topology attributes, optimizes the sorting process, then calculates the mapping domain in advance, considers the regional comprehensive resource capacity to balance the load, and finally combines the subgraph isomorphism and link segmentation technology to carry out a one-stage mapping scheduling to achieve the security service request in the network and the efficient allocation of network resources required to provide security services. The simulation results of the OMNeT++ show that the proposed algorithm improves the mapping success rate and the long-term average cost-benefit ratio of the UAVs. [ABSTRACT FROM AUTHOR]

Automatic manufacturing feature recognition (AFR) is a critical technology for realizing CAD/CAPP/CAM integration in the era of intelligent manufacturing. Despite the numerous feature recognition approaches that have been proposed, the recognition of intersecting features remains a challenge. The most important reason is that the boundaries of features and their geometric topological information are altered or destroyed when interacting with other features. To address this problem, this paper proposes a manufacturing feature recognition method based on graph and minimum non-intersection feature volume suppression. Firstly, the geometric and topological information of a part is extracted and represented as an attributed adjacency graph. Then, a subgraph isomorphism algorithm is designed to recognize the features corresponding to each subgraph. After that, a method to construct and suppress the minimum non-intersection volume of the recognized features is introduced to repair the boundaries of intersecting features. On this basis, intersecting features are separated and recognized at different stages. The experimental results indicate that the proposed approach is effective in recognizing intersection features. Moreover, the recognition result of the proposed method incorporates the surface and volume of a feature, providing enriched feature information for engineering applications. [ABSTRACT FROM AUTHOR]

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]

The subgraph matching problem associated with large graphs is an emerging research challenge in graph search due to the growing size of the web, social, and metabolic graphs, and the wide availability of graph databases. Such problems involve finding all instances (aka embedding) of the small-sized query graph in the associated large-sized reference graph. Many state-of-the-art algorithms, including VF3, RI, CFL-Match, and Glasgow, exist to solve subgraph matching problem. RI is one of the fastest subgraph matching algorithms focusing mainly on time efficiency performance measures. However, other performance measures, such as the number of found instances of the query graph (embedding count), the method of ordering the query graph’s vertices, and the number of recursive calls, are crucial for the efficiency and effectiveness of the subgraph matching. In this paper, the RI+ algorithm is proposed as an enhanced version of RI, which has been designed using candidate region-based decomposition and ordering. Three novel candidate region orderings have been introduced, namely vertex-count, density, and average-path-length, based on the structural properties of the candidate regions. On empirical analysis of RI+ on real-world data sets, it was observed that RI+ shows significant improvement in efficiency and effectiveness over RI on both performance evaluation measures, namely, embedding count and search time. The influence of the proposed candidate region orderings on the search time of RI+ was also analyzed, revealing that a suitable candidate region ordering has the potential to improve the search time of the proposed algorithm.

In order to implement a quantum circuit on an NISQ device, it must be transformed into a functionally equivalent circuit that satisfies the device's connectivity constraints. However, NISQ devices are inherently noisy, and minimizing the number of SWAP gates added to the circuit is crucial for reducing computation errors. To achieve this, we propose a subgraph isomorphism algorithm based on the timing weight priority of quantum gates, which provides a better initial mapping for a specific two-dimensional quantum architecture. Additionally, we introduce a heuristic swap sequence selection optimization algorithm that uses a distance optimization measurement function to select the ideal sequence and reduce the number of SWAP gates, thereby optimizing the circuit transformation. Our experiments demonstrate that our proposed algorithm is effective for most benchmark quantum circuits, with a maximum optimization rate of up to 43.51% and an average optimization rate of 13.51%, outperforming existing related methods. [ABSTRACT FROM AUTHOR]

With the rapid development of information technologies, multi-source heterogeneous data has become an open problem, and the data is usually modeled as graphs since the graph structure is able to encode complex relationships among entities. However, in practical applications, such as network security analysis and public opinion analysis over social networks, the structure and the content of graph data are constantly evolving. Therefore, the ability to continuously monitor and detect interesting patterns on massive and dynamic graphs in real-time is crucial for many applications. Recently, a large group of excellent research works has also emerged. Nevertheless, these studies focus on different updates of graphs and apply different subgraph matching algorithms; thus, it is desirable to review these works comprehensively and give a thorough overview. In this paper, we systematically investigate the existing continuous subgraph matching techniques from the aspects of key techniques, representative algorithms, and performance evaluation. Furthermore, the typical applications and challenges of continuous subgraph matching over dynamic graphs, as well as the future development trends, are summarized and prospected. [ABSTRACT FROM AUTHOR]

For a fixed "pattern" graph G, the colored G-subgraph isomorphism problem (denoted by SUB(G)) asks, given an n-vertex graph H and a coloring V (H) → V (G), whether H contains a properly colored copy of G. The complexity of this problem is tied to parameterized versions of P =? NP and L =? NL, among other questions. An overarching goal is to understand the complexity of 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 formula complexity of SUB(G) and an invariant known as tree-depth (denoted by\sanst \sansd (G)). SUB(G) is known to be solvable by monotone AC0 formulas of size O(ntd(G)). Our main result is an nΩtd (G)1/3) lower bound for formulas that are monotone or have sublogarithmic depth. This complements a lower bound of Li, Razborov, and Rossman [SIAM J. Comput., 46 (2017), pp. 936--971] relating tree-width and AC0 circuit size. As a corollary, it implies a stronger homomorphism preservation theorem for firstorder logic on finite structures [B. Rossman, An improved homomorphism preservation theorem from lower bounds in circuit complexity, in 8th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform. 67, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2017, 27]. The technical core of this result is an nΩ (k) lower bound in the special case where G is a complete binary tree of height k, which we establish using the pathset framework introduced in B. Rossman [SIAM J. Comput., 47 (2018), pp. 1986--2028]. (The lower bound for general patterns follows via a recent excluded-minor characterization of tree-depth [W. Czerwi, W. Nadara, and M. Pilipczuk, SIAM J. Discrete Math., 35 (2021), pp. 934--947; K. Kawarabayashi and B. Rossman, A polynomial excluded-minor approximation of treedepth, in Proceedings of the 2018 Annual ACMSIAM Symposium on Discrete Algorithms, 2018, pp. 234--246]. 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 SUB(G) when G is a path. [ABSTRACT FROM AUTHOR]

We introduce the concept of a k-dimensional matrix product D of k matrices A 1 , ... , A k of sizes n 1 × n , ... , n k × n , respectively, where D [ i 1 , ... , i k ] is equal to ∑ ℓ = 1 n A 1 [ i 1 , ℓ ] × ... × A k [ i k , ℓ ] . We provide upper bounds on the time complexity of computing the product and solving related problems of computing witnesses and maximum witnesses of the Boolean version of the product in terms of the time complexity of rectangular matrix multiplication. The multi-dimensional matrix product framework is useful in the design of parameterized graph algorithms. First, we apply our results on the multi-dimensional matrix product to the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a reduction to triangle detection/counting. We provide an alternative simple method of detection/counting copies of fixed size cliques based on the multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of K 4 and K 5 . Next, we show an immediate reduction of the k-dominating set problem to the multi-dimensional matrix product. It implies the W [ 2 ] hardness of the problem of computing the k-dimensional Boolean matrix product. Finally, we provide an efficient reduction of the problem of finding the lowest common ancestors for all k-tuples of vertices in a directed acyclic graph to the problem of finding witnesses of the Boolean variant of the multi-dimensional matrix product. Although the time complexities of the algorithms resulting from the aforementioned reductions solely match those of the known algorithms, the advantage of our algorithms is simplicity. Our algorithms also demonstrate the versatility of the multi-dimensional matrix product framework. [ABSTRACT FROM AUTHOR]

In the electronic design automation field, many tools focus on obtaining the maximum amount of information about the input to which it is provided in order to determine the best algorithms in each instance. Many of these inputs originate from circuits, and the greater the amount of information that can be gathered about a particular circuit, the more accurately the problems can be addressed. Some of these tools are the Boolean satisfiability (SAT) problem solvers, which, for the most part, receive formulas described in conjunctive normal form (CNF) as input. Unfortunately, the circuits encoding the process of the CNF format destroy much of the information that could have been used to optimize SAT solvers, as part of this information must be recovered to avoid applying generic algorithms in the solution of SAT problems. One of the difficult aspects of retrieving this information corresponds to the matching of clauses to their respective logic gates, as well as which sets of logic gates correlate to a functional block. The present work makes use of subgraph isomorphism algorithms to recover circuits encoded in CNF-DIMACS maximizing the number of clauses handled, at the level of both logic gates and more complex structural blocks, which allows their identification at higher levels of abstraction. For this purpose, a tool named GRCircuit was created which was able to successfully recover all circuits generated as tests, in addition to recovering 100% of the circuits from ISCAS 85 and ITC 99 benchmarks. These results demonstrate that it is possible to recover the circuit's structure and identify functional blocks using only graph algorithms, without backtracking approaches, in addition to prioritizing the number of clauses used instead of the number of logic gates. [ABSTRACT FROM AUTHOR]

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: A induces a subgraph of G of treewidth O(√k log k), and 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 (2O(√k log² k)⋅nO(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-time parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log² k)nO(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 could 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. [ABSTRACT FROM AUTHOR]

Vehicular cloud computing has been emerged as a promising solution to fulfill users’ demands on processing computation-intensive applications in modern driving environments. Such applications are commonly represented by graphs consisting of components and edges. However, encouraging vehicles to share resources poses significant challenges owing to users’ selfishness. In this paper, an auction-based graph job allocation problem is studied in vehicular cloud-assisted networks considering resource reutilization. Our goal is to map each buyer (component) to a feasible seller (virtual machine) while maximizing the buyers’ utility-of-service, which concerns the execution time and commission cost. First, we formulate the auction-based graph job allocation as a 0-1 integer programming (0-1 IP) problem. Then, a Vickrey-Clarke-Groves based payment rule is proposed which satisfies the desired economical properties, truthfulness and individual rationality. We face two challenges: 1) the abovementioned 0-1 IP problem is NP-hard; 2) one constraint associated with the IP problem poses addressing the subgraph isomorphism problem. Thus, obtaining the optimal solution is practically infeasible in large-scale networks. Motivated by which, we develop a structure-preserved matching algorithm by maximizing the utility-of-service-gain, and the corresponding payment rule which offers economical properties and low computation complexity. Extensive simulations demonstrate that the proposed algorithm outperforms the contrast methods considering various problem sizes. [ABSTRACT FROM AUTHOR]

Spatio-temporal (ST) graphs have been used in many application domains to model evolving ST phenomenon. Such models represent the underlying structure of the phenomenon in terms of its entities and different types of spatial interactions between them. The reason behind using graph-based models to represent ST phenomenon is due to the existing well-established graph analysis tools and algorithms which can be directly applied to analyze the phenomenon under consideration. In this paper, considering the use case of two distinct, highly dynamic phenomena - invasive team sports, with a focus on handball and urban road traffic, we propose a spatio-temporal graph model applicable to both these phenomena. Different types of entities and spatial relations which make up these phenomena are highlighted to formalize the graph. Furthermore, the idea of graph-based pattern detection in both these phenomena is explored. Different types of ST patterns for both ST phenomena are discussed and the problem of pattern detection is formalized as the problem of subgraph isomorphism for dynamic graphs. Finally, the results of our algorithm to detect random ST patterns in random ST graphs are presented. The ideas discussed in this paper are applicable to other ST phenomena as well. [ABSTRACT FROM AUTHOR]

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

In this paper we investigate the parameterized complexity of counting and detecting small patterns in unit disk graphs: Given an n -vertex unit disk graph G with an embedding of ply p (i.e. G is an intersection graph of closed unit disks, and each point is contained in at most p disks) and a k -vertex unit disk graph P , count the number of (induced) copies of P in G. For general patterns P , we give an 2 O (p k / log ⁡ k) n O (1) time algorithm for counting pattern occurrences. We show this is tight, even for ply p = 2 : any 2 o (n / log ⁡ n) n O (1) time algorithm violates the Exponential Time Hypothesis (ETH). Our approach combines tools developed for planar subgraph isomorphism such as 'efficient inclusion-exclusion' from Nederlof (2020) [15] , and 'isomorphisms checks' from Bodlaender et al. (2016) [5] with a different separator hierarchy and a new bound on the number of non-isomorphic separations tailored for unit disk graphs. [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]

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

Graph databases are flexible NoSQL databases used to efficiently store and query complex and big data. One of the most difficult problems in graph databases is the problem of subgraph isomorphism, which involves finding a matching pattern in a given graph. Subgraph isomorphism algorithms generally encounter problems in the efficient processing of complex queries based on a lack of pruning methods and the use of a matching order. In this study, we present a new subgraph isomorphism approach based on the best-first search design strategy and name it BF-BigGraph. Our approach includes a machine learning technique to efficiently find the best matching order for various complex queries. The parameters we used in our approach as heuristics to improve the performance of complex queries on graph-based NoSQL databases are database volatility, database size, type of query, and the size of the query. We utilized the Random Forest machine learning method to narrow candidate nodes to a higher level of search and effectively reduce the search space for efficient querying and retrieval. We compared BF-BigGraph with state-of-the-art approaches, namely BB-Graph, Neo4j's Cypher, DualIso, GraphQL, TurboIso, and VF3 using publicly available databases including undirected graphs; WorldCup, Pokec, Youtube, and a big graph database of a real demographic application (a population database) with approximately 70 million nodes of a big directed graph. The performance results of our approach for different types of complex queries on all these databases are significantly better in terms of computation time and required memory than other competing approaches in the literature. • Introducing an efficient subgraph isomorphism method using best-first design strategy. • Approach uses random forest and centrality for diverse queries. • Evaluated on databases up to 70 million nodes, considering node size, volatility, and query type. • The approach was tested on databases from 45KB to 70M nodes. • BF-BigGraph showed superior efficiency in time and memory use. [ABSTRACT FROM AUTHOR]

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.

Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models. [ABSTRACT FROM AUTHOR]

In this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. Numerous algorithms for solving the problem exist in the literature and most of them are based on the backtracking approach. Since straightforward backtracking is usually slow, many algorithmic refinement techniques are used in practical algorithms. The main goal of this paper is to study such refinement techniques and to determine their ability to speed up backtracking algorithms. To do this we use a methodology of experimental algorithmics. We perform an experimental evaluation of the techniques and their combinations and, hence, demonstrate their usefulness in practice.

In order to implement a quantum circuit on an NISQ device, it must be transformed into a functionally equivalent circuit that satisfies the device’s connectivity constraints. However, NISQ devices are inherently noisy, and minimizing the number of SWAP gates added to the circuit is crucial for reducing computation errors. To achieve this, we propose a subgraph isomorphism algorithm based on the timing weight priority of quantum gates, which provides a better initial mapping for a specific two-dimensional quantum architecture. Additionally, we introduce a heuristic swap sequence selection optimization algorithm that uses a distance optimization measurement function to select the ideal sequence and reduce the number of SWAP gates, thereby optimizing the circuit transformation. Our experiments demonstrate that our proposed algorithm is effective for most benchmark quantum circuits, with a maximum optimization rate of up to 43.51% and an average optimization rate of 13.51%, outperforming existing related methods.