Academic literature on the topic 'Subgraph isomorphism'

Graph is a widely used model to represent complicated data in many domains. Finding subgraph isomorphism is a fundamental function for many graph databases and data mining applications handling graph data. This thesis studies this classic problem by considering a set of novel techniques from three different aspects. This thesis first considers speeding up subgraph isomorphism search by exploiting relationships among data vertices. Most of the subgraph isomorphism algorithms of the In-Memory model (IM) are based on a backtracking method which computes the solutions by incrementally enumerating all candidate combinations. We observed that all current algorithms blindly verify each individual mapping separately, often leading to extensive duplicate calculations. We propose two novel concepts, Syntactic Equivalence and Query Dependent Equivalence, by using which we group specific candidate data vertices into a hypervertex. The data vertices belonging to the same hypervertex can be mapped to the same query vertex. Thus, all the vertices falling into the same hypervertex can be determined whether to contribute to a solution simultaneously instead of calculating them separately. Our extensive experimental study on real datasets shows that existing subgraph isomorphism algorithms can be significantly boosted by our approach. Secondly, this thesis considers multi-query optimization where multiple queries are processed together so as to reduce the overall processing time. We propose a novel method for efficiently detecting useful common subgraphs and a data structure to organize them. We propose a heuristic algorithm based on the data structure to compute a query execution order so that cached intermediate results can be effectively utilized. To balance memory usage and the time for cached results retrieval, we present a novel structure for caching the intermediate results. We provide strategies to revise existing single-query subgraph isomorphism algorithms to seamlessly utilize the cached results, which leads to significant performance improvement. Experiments over real datasets proved the effectiveness and efficiency of our multi-query optimization approach. In the third part, this thesis considers the subgraph isomorphism search under distributed environments. We observed that current state-of-the-art distributed solutions either rely on crippling joins or cumbersome indices, which leads those solutions hard to be practically used. Moreover, most of them follow the synchronous model whose performance is often bottlenecked by the machine with the worst performance in the cluster. Motivated by this, in this thesis, we utilize a dramatically different approach and propose PADS , a Practical Asynchronous Distributed Subgraph enumeration system. We conducted extensive experiments to evaluate the performance of Pads. Compared with existing join-oriented solution, our system not only shows significant superiority in terms of query processing efficiency but also has outstanding practicality. Even compared with heavy indexed solution, our approach also has better performance in many cases.<br>Thesis (PhD Doctorate)<br>Doctor of Philosophy (PhD)<br>School of Info & Comm Tech<br>Science, Environment, Engineering and Technology<br>Full Text

Notre objectif est d’évaluer et de rendre opérationnelle la décomposition de problèmes d’optimisation sous contraintes. Nous nous sommes intéressés à deux problèmes en particulier : le problème de la recherche d’un plus grand sous-graphe commun (MCIS), et le problème de somme coloration minimale (MSCP). Il s’agit de problèmes NP-difficiles pour lesquels les approches de résolution complètes passent difficilement à l’échelle, et nous proposons de les améliorer à cet égard en décomposant ces problèmes en sous-problèmes indépendants. Les décompositions que nous proposons s’appuient sur la structure du problème initial pour créer des sous-problèmes de tailles équilibrées. Pour le MCIS, nous introduisons une décomposition basée sur la structure du graphe de compatibilité, et nous montrons que cette décomposition permet d’obtenir des sous-problèmes plus équilibrés que la méthode EPS classiquement utilisée pour paralléliser la résolution de problèmes en programmation par contraintes. Pour le MSCP, nous introduisons une nouvelle décomposition arborescente de hauteur bornée, et nous montrons comment tirer partie de la complémentarité de la programmation par contraintes et de la programmation linéaire en nombres entiers pour obtenir et résoudre les sous-problèmes indépendants qui en découlent. Nous proposons également une approche portfolio qui utilise des techniques d’apprentissage automatique pour choisir dynamiquement l’approche la plus performante en fonction du problème à résoudre<br>The objective of this thesis is, from a general standpoint, to design and evaluate decomposition methods for solving constrained optimisation problems. Two optimisation problems in particular are considered: the maximum common induced subgraph problem, in which the largest common part between two graphs is to be found, and the sum colouring problem, where a graph must be coloured in a way that minimises a sum of weights induced by the employed colours. The maximum common subgraph (MCIS) problem is notably difficult, with a strong applicability in domains such as biology, chemistry and image processing, where the need to measure the similarity between structured objects represented by graphs may arise. The outstanding difficulty of this problem makes it strongly advisable to employ a decomposition method, possibly coupled with a parallelisation of the solution process. However, existing decomposition methods are not well suited to solve the MCIS problem: some lead to a poor balance between subproblems, while others, like tree decomposition, are downright inapplicable. To enable the structural decomposition of such problems, Chmeiss et al. proposed an approach, TR-decomposition, acting at a low level: the microstructure of the problem. This approach had yet to be applied to the MCIS problem. We evaluate it in this context, aiming at reducing the size of the search space while also enabling parallelisation. The second problem that caught our interest is the sum colouring problem. It is an NP-hard variant of the widely known classical graph colouring problem. As in most colouring problems, it basically consists in assigning colours to the vertices of a given graph while making sure no neighbour vertices use the same colour. In the sum colouring problem, however, each colour is associated with a weight. The objective is to minimise the sum of the weights of the colours used by every vertex. This leads to generally harder instances than the classical colouring problem, which simply requires to use as few colours as possible. Only a few exact methods have been proposed for this problem. Among them stand notably a constraint programming (CP) model, a branch and bound approach, as well as an integer linear programming (ILP) model. We led an in-depth investigation of CP's capabilities to solve the sum colouring problem, while also looking into ways to make it more efficient. Additionally, we evaluated a combination of integer linear programming and constraint programming, with the intention of conciliating the strong points of these highly complementary approaches. We took inspiration from the classical backtracking bounded by tree decomposition (BTD) approach. We employ a tree decomposition with a strictly bounded height. We then derive profit from the complementarity of our approaches by developing a portfolio approach, able to choose one of the considered approaches automatically by relying on a number of features extracted from each instance

Dans le cadre de l'étude des interactions de divers acteurs au sein d'un système, la recherche de schémas comportementaux trouve nombre d'applications. Les graphes temporels qui m'intéressent dans le cadre de cette thèse présentent des tailles d'historiques tau, à savoir le nombre d'instants temporels entre le premier instant t0 et le dernier instant tf pour lesquels G n'est pas vide, de l'ordre de plusieurs millions. Je cherche donc à minimiser l'impact de tau sur les complexités spatiales et temporelles de mes algorithmes. Étant donné Delta un entier naturel, l'énumération de Delta-modules est l'énumération de tous les sous-ensemble de sommets A d'un graphe temporel L(V,E,T) tels que pour tout instant temporel t dans un intervalle de Delta instants consécutifs ou plus, les voisinages instantanés de chaque sommet de A en dehors de A soient égaux. Je présente un algorithme utilisant l'affinage de partition et des structures de données d'arbre rouge-noir pour énumérer les Delta-modules en temps quadratique de tau. L'énumération des Delta-jumeaux, pour lesquels |A|=2 est réalisée en temps logarithmique de tau avec une utilisation mémoire indépendante de tau. Étant donné H(V',E',T') un graphe temporel appelé motif, l'énumération de sous-graphes de L(V,E,T) isomorphes à H est l'énumération de toutes les paires constituées d'un instant temporel t0 de T et d'une bijection f de V' vers un sous-ensemble A de V telles qu'à chaque instant temporel entre t0 et t0+tau', les sommets de H aient exactement le même comportement entre eux à l'instant t que leurs images par f dans L à l'instant t0+t. J'établis un algorithme énumérant les sous-graphes temporels isomorphes en temps linéaire de tau. Après avoir présenté et démontré la correction et les complexités de ces divers algorithmes, je conduis une étude expérimentale afin de confirmer par la pratique le comportement de mes algorithmes<br>In regards to the study of interactions of agents inside a system, the search for behavioural patterns has numerous applications. The temporal graphs I consider in this thesis present history length tau, which is to say the number of temporal instants between the first instant t0 and the last instant tf for which G is not empty, greater than multiple millions. I aim at minimizing the impact of tau on the spacial and temporal complexities of my algorithms Given Delta an intenger, the enumeration of Delta-modules is the enumeration of all vertex subsets A of a temporal graph L(V,E,T) such that for all temporal instant t in an interval of Delta or more consecutive time instants, instantaneous neighbourhoods of each vertex of A outside A are equal. I present an algorithm using partition refinment and red-black tree data structures in order to enumerate Delta-modules in time quadratic in tau. Enumeration of Delta-twins, for which |A|=2 is done in time logarithmic in tau with memory use independant of tau. Given H(V',E',T') a temporal graph called pattern, enumeration of subgraphs of L(V,E,T) isomorphic to H is the enumeration of all pairs formed of a temporal instant t0 of T and a bijection f from V' to a subset A of V such that for each temporal instant between t0 and t0+tau', vertices of H display the exact same behaviour between them at instant t than their images by f in L at time instant t0+t. I present an algorithme enumerating isomorphic temporal subgraphs in time linear of tau. After having presented and demonstrated correction and complexities of said algorithms, I conduct an experimental study in order to confirm behaviour of my algorithms

This thesis investigates the central issues underlying graph analysis, namely, scalability and quality. We first study the incremental problems for graph queries, which aim to compute the changes to the old query answer, in response to the updates to the input graph. The incremental problem is called bounded if its cost is decided by the sizes of the query and the changes only. No matter how desirable, however, our first results are negative: for common graph queries such as graph traversal, connectivity, keyword search and pattern matching, their incremental problems are unbounded. In light of the negative results, we propose two new characterizations for the effectiveness of incremental computation, and show that the incremental computations above can still be effectively conducted, by either reducing the computations on big graphs to small data, or incrementalizing batch algorithms by minimizing unnecessary recomputation. We next study the problems with regards to improving the quality of the graphs. To uniquely identify entities represented by vertices in a graph, we propose a class of keys that are recursively defined in terms of graph patterns, and are interpreted with subgraph isomorphism. As an application, we study the entity matching problem, which is to find all pairs of entities in a graph that are identified by a given set of keys. Although the problem is proved to be intractable, and cannot be parallelized in logarithmic rounds, we provide two parallel scalable algorithms for it. In addition, to catch numeric inconsistencies in real-life graphs, we extend graph functional dependencies with linear arithmetic expressions and comparison predicates, referred to as NGDs. Indeed, NGDs strike a balance between expressivity and complexity, since if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. A localizable incremental algorithm is developed to detect errors using NGDs, where the cost is determined by small neighbors of nodes in the updates instead of the entire graph. Finally, a rule-based method to clean graphs is proposed. We extend graph entity dependencies (GEDs) as data quality rules. Given a graph, a set of GEDs and a block of ground truth, we fix violations of GEDs in the graph by combining data repairing and object identification. The method finds certain fixes to errors detected by GEDs, i.e., as long as the GEDs and the ground truth are correct, the fixes are assured correct as their logical consequences. Several fundamental results underlying the method are established, and an algorithm is developed to implement the method. We also parallelize the method and guarantee to reduce its running time with the increase of processors.

Today, graphs are used for many things. In engineering, graphs are used to design circuits in very large scale integration. In computer science, graphs are used in the representation of the structure of software. They show information such as the flow of data through the program (known as the data flow graph [1]) or the information about the calling sequence of programs (known as the call graph [145]). These graphs consist of many classes of graphs and may occupy a large area and involve a large number of vertices and edges. The manual layout of graphs is a tedious and error prone task. Algorithms for graph layout exist but tend to only produce a 'good' layout when they are applied to specific classes of small graphs. In this thesis, research is presented into a new automatic graph layout technique. Within many graphs, common structures exist. These are structures that produce 'good' layouts that are instantly recognisable and, when combined, can be used to improve the layout of the graphs. In this thesis common structures are given that are present in call graphs. A method of using subgraph isomorphism to detect these common structures is also presented. The method is known as the ANHOF method. This method is implemented in the ANHOF system, and is used to improve the layout of call graphs. The resulting layouts are an improvement over layouts from other algorithms because these common structures are evident and the number of edge crossings, clusters and aspect ratio are improved.

This project introduces history and basic notions of the graph theory. It describes graph theory problems, possible graph representations and practical graph management in databases. Aims to subgraph and graph isomorphism. It describes possible ways to find graph isomorphism and chosen algorithms for subgraph and graph isomorphism. The experimental part aims to comparing two implemented algorithms. These are Ullmann and VF2 algorithm. Also searches difference between graphs stored in memory and graphs stored in database.

Maximum G Edge-Packing (E Pack_G) is the problem of finding the maximum number of edge-disjoint isomorphic copies of a fixed guest graph G in a host graph H. The problem is primarily considered for several guest graphs (stars, paths and cycles) and host graphs (arbitrary graphs, planar graphs and trees). We give polynomial-time algorithms when G is a 2-path or when H is a tree; we show the problem is NP-complete otherwise. Also, we propose straightforward greedy polynomial-time approximation algorithms which are at least 1/|E_G| optimal.<br>Master of Science

This thesis deals with the problem of searching of structures in large chemical compounds databases. The aim is to design and implement an efficient system that supports two basic types of search, which are identity and substructure search. This task is complicated not only by the large number of entries in databases but also by graph representation of chemical structures, for which many algorithms are hard to solve. The thesis will introduce concepts which will prove useful in solving these problems. A web service is also created as a part of the thesis in order to make the database searching available to the users.

Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphes<br>For past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters