TLAV Think Like A Vertex

Keywords: Big data, Big graphs, Pattern matching, Subgraph isomorphism, Graph algorithms, Parallel and Distributed computing. List of Acronyms BDSim Bounded Dual Simulation. BFS Breadth First Search. BSIM Bounded Simulation. BSP Bulk Synchronous Parallel. CC Connected Component. D3S Distributed Scalable Strong Simulation. D3S+ Distributed Scalable Strict Simulation MCS Multi-Constrained Simulation. MPI Message Passing Interface. PDSim Parallel Dual Simulation. PGSim Parallel Graph Simulation. RDD Resilient Distributed Dataset. RDF Resource Description Framework. RPC Remote Procedure Call. SGSIM Strong Simulation. SIMD Single Instruction Multiple Data. SJS Surjective Simulation. SSSP Single Source Shortest Path. STSIM Strict Simulation. STwig Star Twig. SubISO Subgraph Isomorphism TRS Time-Respecting Simulation. TSIM Tight Simulation. TXS Taxonomy Simulation. URS Unidirectional Relaxation Simulation

Graph Pattern Matching (GPM), usually evaluated through subgraph isomorphism, Ąnds subgraphs of a large data graph that are similar to an input query graph. It has many applications, such as pattern recognition and Ąnding communities in social networks. However, besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for GPM in the context of big data. As a result, relaxed GPM models such as graph simulation emerged as they yield interesting results in polynomial time. Moreover, massive graphs generated by mostly social networks require distributed storing and processing of the data over multiple machines. Therefore, the existing algorithms for relaxed GPM need to be revised to this context by adopting new paradigms for big graph processing, e.g. Think-Like-A-Vertex and its derivatives.

In this thesis, we investigate the use of distributed graph processing paradigms and systems in the evaluation of GPM queries. Our goal is to identify the programming models that are best suited for this problem. Furthermore, we study the existing GPM approaches, with more emphasis on the relaxed ones in the aim of proposing new parallel and distributed algorithms for relaxed GPM that guarantee linear scalability. Our contributions are summarized as follows. First, we propose a taxonomy of prior work on distributed GPM based on multiple criteria, such as the GPM model and the programming paradigm. Next, we introduce BDSim as a new model that captures more semantic similarities compared to the existing models while being feasible in cubic time. Besides, we design distributed vertex-centric algorithms that are adapted to the context of massive graphs for evaluating BDSim. Furthermore, we propose the Ąrst fully distributed and scalable approach for strong simulation, a relaxed GPM model that strikes a balance between Ćexibility and tractability. Finally, we propose the Ąrst efficient parallel edge-centric approach for evaluating graph simulation and dual simulation in distributed graphs. We validate the effectiveness and efficiency of our approaches through theoretical guarantees and reliable testing over synthetic and real-world graphs.

v

We conĄrmed in this thesis that different paradigms can be used in designing distributed GPM algorithms depending on the GPM model adopted. Indeed, algorithms for neighborhood-based models such as subgraph isomorphism and strong simulation perform better with a vertex-centric or subgraph-centric paradigm as the latter involves some data locality, while the most efficient algorithms for graph simulation and dual simulation are edge-based and offer linear scalability guarantees.

Résumé

LŠappariement des sous-graphes (ASG) est un problème classique, souvent modélisé à lŠaide de lŠisomorphisme de sous-graphes. Il est utilisé dans différents domaines dŠapplication tels que la reconnaissance de motifs et la détection de communautés dans les réseaux sociaux. Néanmoins, en plus du fait quŠil soit NP-Complet, lŠisomorphisme de sous-graphes sŠavère très strict pour lŠASG dans le contexte actuel des grands graphes. Par conséquent, de nouveaux modèles dŠASG relaxé ont apparu comme la Graph Simulation, permettant dŠavoir des résultats intéressants dans un temps polynomial. De plus, les graphes massifs qui sont issus des réseaux sociaux requièrent un stockage et un traitement distribués sur plusieurs machines, dŠoù la nécessité de revisiter les algorithmes dŠASG relaxé en adoptant de nouveaux paradigmes, dédiés au traitement des grands graphes, notamment le Think-Like-A-Vertex et ses variantes.

Dans cette thèse, nous étudions lŠintérêt des systèmes et paradigmes distribués de traitement des grands graphes dans lŠévaluation des requêtes dŠASG. LŠobjectif est dŠidentiĄer les modèles de programmation qui sont les mieux adaptés pour ce problème. Par ailleurs, nous visons à proposer de nouveaux algorithmes dŠASG qui sont parallèles, distribués et offrant une scalabilité linéaire. Nos contributions se résument en quatre points : (1) nous proposons une nouvelle classiĄcation des approches distribuées dŠASG, en nous basant sur plusieurs critères tels que le modèle dŠASG et le paradigme de programmation, (2) nous introduisons le nouveau modèle dŠASG relaxé BDSim qui permet de mieux capturer les similarités entre les graphes, tout en ayant une complexité cubique. En plus, nous proposons des algorithmes distribués centré sommet pour lŠévaluation de BDSim sur des grands graphes, (3) nous développons le premier algorithme scalable et complètement distribué pour évaluer Strong Simulation, un modèle dŠASG relaxé offrant un compromis entre la Ćexibilité et la faisabilité, (4) enĄn, nous proposons la première approche parallèle et centrée arêtes pour évaluer Graph Simulation et Dual Simulation dans les graphes massifs et distribués. Nous validons les différents algorithmes proposés théoriquement et expérimentalement sur des graphes massifs synthétiques et réels.

vii

A travers ce travail de recherche, nous avons conĄrmé que différents modèles de programmation peuvent être utilisés pour la conception dŠalgorithmes dŠASG et cela dépend du modèle dŠASG adopté. Effectivement, lŠisomorphisme de sous-graphes et Strong Simulation sont des modèles basés sur la localité et le voisinage à plusieurs sauts, ce qui nécessite un paradigme centré sommet ou encore centré sous-graphe. En revanche, les algorithmes les plus efficaces pour évaluer Graph Simulation et Dual Simulation effectuent des traitements centrés arêtes et garantissent une scalabilité linéaire.

Mots clés: Big data, Big graphs, Pattern matching, Subgraph isomorphism, Graph algorithms, Parallel and Distributed computing.

Introduction Motivations and challenges

With the rapid growth of the Internet, huge amounts of data are being generated with every passing minute. The challenges brought about by what is commonly known today as Şbig dataŤ have led to the research community revising traditional techniques and algorithms that were designed for collecting, storing, analyzing, and visualizing data. According to an IBM report published in the year 2017 [START_REF] Winans | 10 Key Marketing Trends for 2017 and Ideas for Exceeding Customer Expectations[END_REF], 90 percent of the data in the world has been generated in the last two years alone; i.e. during 2015Ű2016. Therefore, they support data scalability and are able to harness the computing resources available on every computing machine.

In this thesis, we address Graph Pattern Matching (GPM), which refers to the problem of Ąnding occurrences of a small pattern graph (a.k.a. query graph) in a relatively larger data graph. It is among the most analyzed problems in graph theory, and it has a wide range of applications like in-database analytics, biometric identiĄcation and social networks analysis. GPM queries are traditionally evaluated based on subgraph isomorphism that Ąnds a bijective mapping between the vertices of the query graph and a subgraph of the data graph, such that query edges are preserved by this mapping. Since several decades, different subgraph isomorphism algorithms have been put forward, aiming to reduce time and space complexity and addressing the problems of speciĄc graph classes, e.g. trees, bipartite graphs, and direct acyclic graphs. Nevertheless, subgraph isomorphism is known to have several limitations. It is an NP-Complete problem [START_REF] Garey | Computers and intractability: a guide to np-completeness[END_REF], which makes it impractical for massive graphs that may contain up to billions of nodes and trillions of edges. Indeed, the strict constraints imposed by this model are not interesting for the current real-world applications especially in social networks. Consequently, graph simulation [START_REF] Henzinger | Computing simulations on Ąnite and inĄnite graphs[END_REF][START_REF] Fan | Graph Pattern Matching: From Intractable to Polynomial Time[END_REF] has been considered as an alternative model that relaxes the matching constraints imposed by subgraph isomorphism, hence making it feasible in polynomial time. Furthermore, several other relaxed models emerged, aiming to reduce the time and space complexity while keeping an acceptable accuracy depending on the application domain and its requirements in terms of Ćexibility and response time. We cite for example bounded simulation [START_REF] Fan | Incremental graph pattern matching[END_REF], dual simulation and strong simulation [START_REF] Ma | Capturing topology in graph pattern matching[END_REF]. These newly introduced models consider not only the topological structure of the graphs, but also the semantic information carried by labels and attributes on both the graph vertices and edges.

Besides, programming models are being used to design distributed graph algorithms such as Hadoop MapReduce or the Bulk Synchronous Parallel model (BSP). However, recent studies have shown that the general-purpose programming models, especially Hadoop MapReduce, are inefficient in processing distributed graphs due to the complexity of graph data as opposed to other forms of data. Big data processing in Hadoop MapReduce is based on I/O operations that are time consuming. In addition, the data locality is an intrinsic property of iterative graph algorithms. It increases the number of I/O operations making this category of frameworks unsuitable for graph processing at large scale. This is a reason why new paradigms, specially designed for big graph processing, appeared such as the Think-Like-A-Vertex (TLAV) model and its derivatives adopted by Pregel [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF], Giraph [START_REF] Foundation | Apache giraph[END_REF], GPS [START_REF] Salihoglu | Gps: A graph processing system[END_REF] and GraphX [START_REF] Xin | Graphx: A resilient distributed graph system on spark[END_REF]. These paradigms consider the different properties of graph data and allow designing linearly scalable algorithms intended to run on clusters composed of dozens to hundreds of machines.

With the emergence of these distributed systems, important challenges need to be addressed in the Ąeld of graph pattern matching. The Ąrst challenge is distributed subgraph matching in general, while the second one is efficient and linearly scalable algorithms for relaxed subgraph matching. Even though the relaxed GPM models are appropriate for social network analysis due to their polynomial time complexity, only few works address them from a scalability point of view. In this thesis, we study the programming models that are used for distributed graph processing and their adaptation to the problem of graph pattern matching. We aim to propose, based on these models, new efficient parallel and distributed algorithms for evaluating relaxed GPM while considering the intrinsic properties of big graphs that are issued from real-world applications. The linear scalability of these algorithms will be proved through a detailed theoretical validation in addition to an experimental evaluation of their performance on several real graphs.

Contributions

To achieve the above mentioned objectives, we investigate in our Ąrst contribution the existing relaxed GPM models and compare them to subgraph isomorphism. This study allowed us to draw the relationships between these models and show how close they are to graph simulation and subgraph isomorphism. In addition, we study the existing graph processing paradigms to answer the following question; which programming models are better suited for the problem of GPM and whether the differences between these models affect the selection of the programming models that should be adopted or not? Furthermore, we conduct a thorough study over prior distributed graph pattern matching approaches to spot and discuss their shortcomings, notably in terms of scalability. Finally, we propose a new taxonomy of GPM algorithms based on multiple criteria, such as the GPM model involved and the programming paradigm adopted in designing the approach.

One conclusion drawn from this study is that strong simulation is an interesting extension of graph simulation that captures the topological structure of the query graph by bringing duality and locality. However, even though strong simulation allows preserving most of the important information of a query graph, this model has not been sufficiently covered in the context of massive graphs. Apart from the proposal of alternative models that remain limited in terms of scalability, i.e. strict simulation or tight simulation [START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF], few research papers have paid attention to distributed strong simulation. For these reasons, we tackle the problem of scalability of strong simulation from three different angles. First, we propose an alternative GPM model that answers relaxed GPM queries in distributed graphs while capturing duality and locality (properties present in strong simulation) and offering scalability guarantees. Second, we design a new distributed and scalable algorithm for evaluating strong simulation with performance guarantees on attributed and dynamic data graphs. Finally, since dual simulation is an important building block in the evaluation of strong simulation, we propose the Ąrst parallel and highly scalable algorithm for dual simulation in distributed graphs (in addition to graph simulation). These contributions are detailed below.

Our main contribution in this thesis is the proposal of a new relaxed GPM model called Bounded Dual Simulation (BDSim), and that sits between graph simulation and subgraph isomorphism. BDSim strikes a balance between tractability and accuracy of the returned results as it captures perfectly the cyclic structure of the query graph while being feasible in cubic time. We validate the scalability of BDSim through theoretical guarantees in addition to the design and implementation of a distributed vertex-centric algorithm that evaluates BDSim on massive data graphs. Finally, we conduct extensive experiments on synthetic and real data graphs and compare our approach to prior GPM models.

The existing approaches of strong simulation are either centralized or distributed. However, even the distributed ones do not provide scalability guarantees. In our second contribution, we propose the Ąrst fully distributed and vertex-centric algorithm for scalable evaluation of strong simulation on massive graphs, called D3S. An extension of this approach to evaluate strict simulation, referred to as D3S + , is also proposed. In addition to the theoretical guarantees on the convergence and correctness of this approach, the conducted experiments prove that D3S and D3S + can reduce the response time by up to Ąve times compared to the state-of-the-art distributed algorithm.

Our last contribution is designing an efficient parallel edge-centric approach for evaluating graph simulation and dual simulation. First, we introduce a new distributed data structure called ST whose elements can be processed in parallel. Next, we propose the Ąrst parallel and edge-based algorithm called PGSim to answer relaxed GPM queries through graph simulation. Based on ST and PGSim, we develop PDSim, a highly scalable split-andcombine approach to efficiently evaluate GPM queries via dual simulation. Furthermore, we provide guarantees on the convergence and correctness of the two algorithms. The conducted experiments show that our approach runs faster than the state-of-the-art vertex-centric algorithm of graph simulation by more than an order of magnitude. The obtained results also prove the linear scalability of the two parallel algorithms.

Thesis organization

Chapter 1 (Preliminaries) provides important preliminaries in addition to an overview of the two categories of graph pattern matching models that exist. The Ąrst category is structural GPM and includes mainly subgraph isomorphism, while the second category groups the relaxed GPM models such as graph simulation, dual simulation, strong simulation and many other extensions.

Chapter 2 (Graph Pattern Matching in Massive Graphs: State-of-the-art) is divided into two parts. The Ąrst part introduces and discusses the different programming models and systems used in distributed graph processing, whereas in the second part, we review the state-of-the-art distributed approaches of GPM on massive graphs. Finally, we classify these works and provide a new taxonomy based on multiple criteria.

In Chapter 3 (Distributed Graph Pattern Matching via Bounded Dual Simulation), we present our new model BDSim, along with details of the distributed vertex-centric algorithms proposed to evaluate GPM queries via BDSim.

Next, in Chapter 4 (A Distributed and Scalable Approach for Strong Simulation), we present and evaluate our new distributed vertex-centric algorithm for the scalable evaluation of the two relaxed models strong simulation and strict simulation.

Chapter 5 (An Efficient Parallel Edge-Centric Approach for Relaxed GPM) presents a new approach for parallel evaluation of relaxed GPM queries on distributed graphs. We introduce the new distributed data structure ST and the two parallel edge-centric algorithms PGSim and PDSim for graph simulation and dual simulation, respectively.

Finally, we conclude this thesis with a summary of the carried works and some future perspectives.

Introduction

Graphs, being a set of nodes connected to each other by links, are a natural way of representing information in a broad range of domains. Graphs are everywhere, they can be found in chemistry to model the molecule structure, in physics to study the threedimensional structure of atoms, in social networks to model users and the relationships between them, in the study of the World Wide Web where web pages and the hyperlinks connecting them are represented as a graph, and Ąnally, in computer systems to model computation Ćows. This chapter is an introduction to the world of graphs and graph pattern matching in particular. First, we deĄne important terms and concepts. Next, we introduce the problem of graph pattern matching and its application domains. Finally, the largest part of this chapter is dedicated to reviewing the existing formulations and models of graph pattern matching and drawing the relationships between them.

Terminologies

A graph is a structure that groups a set of objects where some pairs are related to each other. These objects are identiĄed by unique numbers and can be characterized by labels or attributes. They are known as the graph vertices (or nodes). When two vertices are related, the link between them is referred to as an edge (or an arc). Moreover, the edges can be labeled with values in R. In this case, the graph is called a weighted graph. An edge can also have a speciĄc direction (the graph is therefore directed), or it can be undirected (we talk about an undirected graph). Moreover, when an edge between two vertices v and v ′ is directed from v to v ′ , v is considered the source vertex and v ′ is the destination vertex of this edge. Finally, a graph is said to be simple when there is at most one edge between any pair of vertices and there are no edges from a vertex to itself. In other words, the graph does not contain parallel edges or loops.

Graphs are illustrated with a set of circles connected with simple lines (in undirected graphs) or arrows (in the case of directed graphs). Examples of an undirected unlabeled graph, undirected labeled graph and directed labeled graph are given in Figures 1.1a, 1.1b and 1.1c, respectively. A weighted graph is illustrated in Figure 1.1d. In what follows, we give the formal deĄnition of a directed labeled graph, a subgraph, induced subgraph and other important terms.

DeĄnition 1 (Directed labeled graph). A directed labeled graph G = (V, E, f ) is a simple graph where:

(1) V is a Ąnite set of all the vertices in G,

(2) E is the set of edges E ⊆ V × V in which (v, v ′ ) denotes an edge from v to v ′ , [START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF] f is a function that maps each vertex v ∈ V to a label value f (v) in Σ, the set of all labels.

DeĄnition 2 (Subgraph). A directed graph G

′ = (V ′ , E ′ , f ′ ) is considered subgraph of a directed graph G = (V, E, f ) if and only if (1) V ′ is a subset of V , (2) E ′ is a subset of E, (3) ∀v ∈ V ′ , f ′ (v) = f (v).
DeĄnition 3 (Induced subgraph). Given a data graph G = (V, E, f ) and a set of vertices V ′ ⊂ V , the induced subgraph of G with respect to V ′ is the subgraph of G that is composed of V ′ and all the edges connecting them from E.

Next, we deĄne a path, shortest path, graph distance, eccentricity, graph diameter and its center.

DeĄnition 4 (Path). A path in a graph

G = (V, E, f ) is a sequence of vertices ρ = (v 1 , v 2 , . . . , v n ) such that (v i , v i+1 ) ∈ E, ∀i ∈ 1, 2, . . . , n -1.
An elementary path is a path where no vertex is repeated twice; ∀v i , v j ∈ ρ, v i ̸ = v j .

DeĄnition 5 (Shortest path). Given an unweighted graph G = (V, E, f ) and two vertices v and v ′ such that v ̸ = v ′ . A shortest path between v and v ′ is the path ρ = (v, . . . , v ′ ) with the least number of edges.

DeĄnition 6 (Graph distance). The distance d(v, v ′ ) between two vertices v and v ′ in a connected graph G = (V, E, f ) is the minimum length of the paths connecting them. The length of a path p = (v 1 , v 2 , . . . , v n ) is the number of its edges.

DeĄnition 7 (Eccentricity of a vertex). Eccentricity ϵ(v) of a vertex v ∈ V in graph G = (V, E, f ) is deĄned as the maximum graph distance between v and any other vertex in G. ϵ(v) = max d(v, u), ∀u ∈ V - ¶v♢ DeĄnition 8 (Graph diameter). Given a graph G = (V, E, f ), the diameter of G is its maximum eccentricity.

DeĄnition 9 (Graph center and graph radius). Given a graph G = (V, E, f ), the centers of G are the vertices having the minimum eccentricity, while its radius is the value of minimum eccentricity.

Finally, a cycle is simply a closed path, and it is formally deĄned as follows.

DeĄnition 10 (Cycle).

A cycle is a path ρ = (v 1 , v 2 , . . . , v n ) where v 1 = v n . A simple cycle is a cycle formed by an elementary path; the Ąrst vertex is the only one repeated twice.

Problem deĄnition

Problem deĄnition

Graph pattern matching is the problem of Ąnding occurrences of a small input graph called pattern (a.k.a. query) graph Q such that Q = (V q , E q , f q ) in a larger graph called data graph G where G = (V, E, f ).

The problem of GPM has several formulations or representations. We Ąnd the structural graph pattern matching that includes graph isomorphism and subgraph isomorphism.

Other models based on simulation represent a Ćexible alternative, and are widely used in todayŠs real-world applications. Under this category, referred to as relaxed GPM, we Ąnd graph simulation and its extensions such as bounded simulation, dual simulation and relaxation simulation.

Structural matching considers the structural information contained in the graph, i.e. the information available is the edges between the graph vertices and it does not capture matches that are close to the query. Vertices and edges may contain semantic information in the form of labels making the matching semantic. On the other hand, the relaxed graph matching considers less the structural information and more the semantic one carried by labels on the data graph vertices or edges. These labels are very informative as they participate in the matching process, such that two nodes or edges with the same label are considered similar. A node/edge can have multiple labels, they are generally represented as a set of attributes in the form of (key, value) where key is the label type and value is the label itself. In this type of graph pattern matching, the structure of the answers may vary from that of the input query because the structural matching constraints are relaxed, seeking lower complexity and to capture more similarities.

A common property of these different GPM models is returning a match graph, which can be either the whole graph G or one to several parts of it. A match graph is built from a binary match relation R that maps the vertices of Q to the vertices of G w.r.t. the GPM model. The maximum match graph is the one containing all the possible match graphs. It is formally deĄned as follows.

DeĄnition 11 (Maximum match graph). Let G = (V, E, f ) be a data graph, Q = (V q , E q , f q ) a pattern graph and R ⊆ V q × V ′ the maximum match relation of Q in G w.r.t. a given GPM model. The maximum match graph is G ′ = (V ′ , E ′ , f ′ ), a subgraph of G verifying:

(1) R maps every vertex v in G ′ to a vertex u in Q, i.e. ∀v ∈ V ′ , ∃u ∈ V q such that (u, v) ∈ R.

(2) ∀(v, v ′ ) ∈ E ′ , ∃(u, u ′ ) ∈ E q such (u, v) ∈ R and (u ′ , v ′ ) ∈ R.

1.4 Applications of graph pattern matching

Applications of graph pattern matching

Graph matching and graph pattern matching have been used since many decades in multiple application areas. In document processing, we Ąnd two important applications. First, in handwritten recognition where documents are analyzed and the text is extracted and modeled as a graph. Then, these graphs are queried against an existing database of already identiĄed texts and characters to recognize the written text [START_REF] Lu | Hierarchical attributed graph representation and recognition of handwritten chinese characters[END_REF][START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF][START_REF] Fischer | A fast matching algorithm for graph-based handwriting recognition[END_REF][START_REF] Stauffer | Keyword spotting in historical handwritten documents based on graph matching[END_REF].

Similarly, graph matching was also used in symbols recognition [START_REF] Lladós | Graph matching versus graph parsing in graphics recognitionŮa combined approach[END_REF][START_REF] Xiaogang | An online composite graphics recognition approach based on matching of spatial relation graphs[END_REF].

Biometric identiĄcation is an important task in security to determine the identity of a person. It uses distinctive features of the person in the authentication process. A large set of identiĄcation metrics are extracted from images and modeled as graphs. Then, this set is queried with graph matching algorithms to Ąnd a correspondence with the input feature of the person to be identiĄed. Among these digital features, we Ąnd Ąngerprints [START_REF] Chikkerur | K-plet and coupled bfs: a graph based Ąngerprint representation and matching algorithm[END_REF][START_REF] Zhong | A hand-based multi-biometrics via deep hashing network and biometric graph matching[END_REF], retina [START_REF] Lajevardi | Retina veriĄcation system based on biometric graph matching[END_REF] and the face [START_REF] Wiskott | Face recognition by elastic bunch graph matching[END_REF]. In computer vision, graph matching is used for image analysis and image databases for both indexing and retrieval [START_REF] Duchenne | A graph-matching kernel for object categorization[END_REF][START_REF] Acosta-Mendoza | Frequent approximate subgraphs as features for graph-based image classiĄcation[END_REF][START_REF] Chaudhuri | Region-based retrieval of remote sensing images using an unsupervised graph-theoretic approach[END_REF][START_REF] Chaudhuri | Region-based retrieval of remote sensing images using an unsupervised graph-theoretic approach[END_REF][START_REF] Khan | Image correspondence with cur decomposition-based graph completion and matching[END_REF]. Moreover, it is also used in video analysis for object tracking [START_REF] Ta | Recognizing and localizing individual activities through graph matching[END_REF][START_REF] Pei | Scene video text tracking with graph matching[END_REF]150,[START_REF] Zhao | Human identiĄcation and interaction detection in cross-view multi-person videos with wearable cameras[END_REF][START_REF] He | Learnable graph matching: Incorporating graph partitioning with deep feature learning for multiple object tracking[END_REF].

Furthermore, different approaches of GPM are used for community detection in the World Wide Web graph [START_REF] Flake | Self-organization and identiĄcation of web communities[END_REF][START_REF] Newman | Detecting community structure in networks[END_REF] and community mining in social networks [START_REF] Brynielsson | Detecting social positions using simulation[END_REF][START_REF] Hung | Investigative simulation: Towards utilizing graph pattern matching for investigative search[END_REF]. Community outlier detection is addressed through graph matching in [START_REF] Mekouar | Community outlier detection in social networks based on graph matching[END_REF]. In social networks, the problem of expert Ąnding can be solved with graph pattern matching such that a pattern of the desired qualiĄcations and their relationships is used as an input query graph [START_REF] Fan | ExpĄnder: Finding experts by graph pattern matching[END_REF].

Fraud detection through the analysis of cyclic patterns in social networks and graph databases is addressed in [START_REF] Sadowski | Fraud detection: Discovering connections with graph databases[END_REF][START_REF] Qiu | Real-time constrained cycle detection in large dynamic graphs[END_REF][START_REF] Bodaghi | Automobile insurance fraud detection using social network analysis[END_REF]. These techniques employ GPM algorithms to Ąnd predeĄned patterns in the form of rings that are suspicious of fraudulent behaviour in banks and other data sources.

Finally, graph pattern matching has always been highly adopted in the Ąeld of information security for intrusion and anomaly detection in programs, networks and cyber-physical systems [START_REF] Kumar | A pattern matching model for misuse intrusion detection[END_REF][START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF][START_REF] Levchuk | Application of graphbased semi-supervised learning for development of cyber cop and network intrusion detection[END_REF][START_REF] Zhang | Unsupervised anomaly detection algorithm of graph data based on graph kernel[END_REF][START_REF] Menelet | Characterization of android malware based on subgraph isomorphism[END_REF].

Structural Graph Pattern Matching

We deĄne graph isomorphism and subgraph isomorphism, two of the most studied models in the literature. They are purely structural, i.e. emphasize the relations between vertices.

Graph isomorphism

Two graphs G = (V, E, f ) and G ′ = (V ′ , E ′ , f ′ ) are isomorphic if and only if there is a bijective mapping R(R :

V ′ → V ) that satisĄes the following condition: ∀u, u ′ ∈ V ′ , if R(u) = v ∈ V and (u, u ′ ) ∈ E ′ then ∃v ′ ∈ V such that R(u ′ ) = v ′ and (v, v ′ ) ∈ E.
While we are interested in techniques and models that Ąnd answers to a query graph in a larger graph, graph isomorphism is mainly used for comparing graphs of the same size (a.k.a. graph matching).

Subgraph isomorphism

Subgraph isomorphism (SubIso) is deĄned as an injective mapping between the vertices of the two graphs Q = (V q , E q , f q ) and G = (V, E, f ). In other words, it is the problem of Ąnding all the subgraphs of a data graph G that are isomorphic to a pattern graph Q. Formally, G matches Q via subgraph isomorphism if and only if:

∀u, u ′ ∈ V q , if R(u) = v ∈ V and (u, u ′ ) ∈ E q then ∃v ′ ∈ V such that R(u ′ ) = v ′ and (v, v ′
) ∈ E, we note here that the mapping is not bijective.

Subgraph isomorphism can also be used in graph matching where the two graphs are similar in size.

Algorithms for subgraph isomorphism

Subgraph isomorphism is an NP-Complete problem [START_REF] Garey | Computers and intractability: a guide to np-completeness[END_REF] that has been the subject of several studies over the past decades. We distinguish two types of algorithms to evaluate it; exact and approximate algorithms. The exact algorithms Ąnd all subgraphs isomorphic 2 An example of a data graph G 1 containing employees in a professional social network, where labels refer to their jobs and an edge between two vertices means that the source endorsed the destination. The pattern graph Q 1 represents the desired connections between the employees that should be retrieved.

to the input query which leads to an exponential time complexity, whereas the other algorithms provide approximate matches yielding to some improvements in the required running time and space but with a loss in the quality of results. The comprehensive Surveys [START_REF] Conte | Thirty Years of Graph Matching in Pattern Recognition[END_REF][START_REF] Gallagher | Matching Structure and Semantics : A Survey on Graph-Based Pattern Matching[END_REF][START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]131] give an overview of the different techniques used to evaluate exact and inexact subgraph isomorphism since the seventies until 2015.

In its basic deĄnition, subgraph isomorphism does not capture the semantic similarities that are generally represented by labels on both graph vertices and edges. However, recent approaches consider the semantic information in addition to the pattern structure.

In [START_REF] Ullmann | An Algorithm for Subgraph Isomorphism[END_REF], Ullmann suggested a tree-based algorithm for solving graph isomorphism. It enumerates all the possible ways of matching query vertices with the data graph vertices starting from a mapping matrix. It also uses a reĄnement procedure that prunes the search space by eliminating unfruitful matches. It is based on the observation that a query vertex u and a data vertex v that are mapped together must also have their neighbors matched together. Thus, any match that does not satisfy this constraint is eliminated from the beginning. All the works that followed are based on this seminal work. They address two common challenges. First, how to minimize the size of intermediate results by ordering the query vertices. Second, Ąnding pruning strategies that avoid useless computations.

The Ąrst algorithm is VF2 [START_REF] Cordella | An improved algorithm for matching large graphs[END_REF]. It is based on the state space representation for solving graph isomorphism. VF2 explores the search space starting from the neighbors of each matched query vertex. VF2Plus [START_REF] Carletti | Vf2 plus: An improved version of vf2 for biological graphs[END_REF] improves the ordering of VF2 by picking the query vertices with the lowest chance of Ąnding matches in the data graph and the highest number of neighbors among prior vertices in the ordering. VF3 [START_REF] Carletti | Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3[END_REF] also improves VF2 by proposing heuristics for reducing the search space size and the time used for processing each state. Moreover, VF3-Light [START_REF] Carletti | Vf3-light: A lightweight subgraph isomorphism algorithm and its experimental evaluation[END_REF] is another algorithm that eliminates some of VF3Šs heuristics which results in shorter running time.

Furthermore, we Ąnd algorithms that use exploration of the data graph to evaluate subgraph isomorphism such as QuickSI [START_REF] Shang | Taming veriĄcation hardness: an efficient algorithm for testing subgraph isomorphism[END_REF], RI [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF] or VF2++ [START_REF] Jüttner | Vf2++-an improved subgraph isomorphism algorithm[END_REF]. Others create tree/graph indices for storing the candidatesŠ sets like GraphQL [START_REF] He | Graphs-at-a-time: Query language and access methods for graph databases[END_REF], TurboIso [START_REF] Han | Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases[END_REF], BoostIso [START_REF] Ren | Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs[END_REF], CFL-Match [START_REF] Bi | Efficient subgraph matching by postponing cartesian products[END_REF], TurboFlux [START_REF] Kim | TurboĆux: A fast continuous subgraph matching system for streaming graph data[END_REF], DAF [START_REF] Han | Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together[END_REF] and VC [START_REF] Sun | Subgraph matching with effective matching order and indexing[END_REF], while some construct indices based on the data graph and use them to assist the embeddings enumeration; GADDI [START_REF] Zhang | Gaddi: distance index based subgraph matching in biological networks[END_REF] and SPath [START_REF] Zhao | On graph query optimization in large networks[END_REF]. Finally, MQO-iso [START_REF] Ren | Multi-query optimization for subgraph isomorphism search[END_REF] constructs a Direct Acyclic Graph (DAG) based on the relationships between multiple queries to guide subgraph isomorphism search.

As opposed to Ullmann that does not deĄne an ordering of the query vertices, QuickSI [START_REF] Shang | Taming veriĄcation hardness: an efficient algorithm for testing subgraph isomorphism[END_REF] proposed to process vertices with infrequent vertex labels in the data graph as quickly as possible, which allows avoiding useless computations. QuickSI processes the edges/vertices having a lower number of possible embeddings Ąrst, hence, reduces the size of explored search space. It Ąrst selects a spanning tree that minimizes the number of possibly generated embeddings in the data graph. Then, it selects an order of processing by setting the Ąrst edge to explore as the one having minimum size of candidates for its source and destination. Finally, a Depth First Search (DFS) traversal of the spanning tree is conducted to enumerate all the possible embeddings. The two algorithms RI [START_REF] Bonnici | A subgraph isomorphism algorithm and its application to biochemical data[END_REF] and VF2++ [START_REF] Jüttner | Vf2++-an improved subgraph isomorphism algorithm[END_REF] are similar to QuickSI as they all explore the data graph directly without generating any candidate sets. However, RI picks query vertices based on their degrees by Ąrst selecting the one with the highest degree, and then the ones with most neighbors in the current ordering. VF2++ picks query vertices with the least frequent labels in G and the highest degree in Q.

To improve the existing pruning rules, GraphQL [START_REF] He | Graphs-at-a-time: Query language and access methods for graph databases[END_REF] proposed to use a neighborhood signature of a query vertex u which is the set of its neighborsŠ labels. A data vertex v is pruned out if its neighborhood signature does not include the neighborhood signature of its matched query vertex. GraphQL picks the query vertex that is connected to an already matched vertex and that has a minimum number of candidates. Similarly, SPath [START_REF] Zhao | On graph query optimization in large networks[END_REF] used an improved neighborhood signature to minimize the size of the candidatesŠ set. It also matches a path-at-time.

TurboISO [START_REF] Han | Turboiso: Towards ultrafast and robust subgraph isomorphism search in large graph databases[END_REF] is another algorithm that groups query vertices having the same label and the same neighborhood into one node to reduce the duplicated generation of unfruitful matches. It divides the data graph into separate Candidate Regions (CRs), where the root of every CR is a data node matched to the query tree root. For each CR, TurboISO enumerates the possible mappings based on a combine/permute strategy. Given a sequence order and a candidate region CR, only one query vertex is processed and if it leads to an accepted answer, other combinations are generated from other vertices in its group. Otherwise, they are all eliminated.

Inspired by the query compression in TurboISO, BoostISO [START_REF] Ren | Exploiting vertex relationships in speeding up subgraph isomorphism over large graphs[END_REF] compresses the data graph based on the relationships between data vertices. It groups the data vertices having the same matches to one hypernode in a new adapted graph that has a smaller size. BoostISO also groups similar query vertices which allows it to prune unfruitful matches as quickly as possible. A follow up revision of the Ąltering phase was made by the same authors in [START_REF] Wang | Correct Ąltering for subgraph isomorphism search in compressed vertex-labeled graphs[END_REF]. Furthermore, in [START_REF] Ren | Multi-query optimization for subgraph isomorphism search[END_REF], Ren et al. propose a multi-query optimization plan (MQO-iso) to reduce the processing time of multiple queries. The input query set is processed to detect the common subgraphs, then a DAG is built based on the isomorphic relationships between the queries such that there is an edge from q to q ′ if q is a subgraph isomorphic to q ′ . This DAG guides the subgraph isomorphism search while exploiting the already generated intermediate results. The parents in the DAG are processed Ąrst and their results are cached then used to process their children. [START_REF] Bi | Efficient subgraph matching by postponing cartesian products[END_REF] proposes to decompose the query graph into three substructures. It matches the cores Ąrst because they are less likely to be highly present in the data graph. Second, it processes the forest substructures that have high chances of being present in the graph, while leaves (one-degree vertices) are left to the end as they are most likely to generate most of the unnecessary embeddings that must be avoided. The core is a dense connected subgraph containing every single edge that is not present in a spanning tree of the query. Such substructure, when processed earlier, reduces the number of unpromising partial mappings by avoiding generating unnecessary Cartesian products. The forest is the complement of the core in the query graph without the leaves. To evaluate subgraph isomorphism, CFL-Match uses a Compact Path Index (CPI) having the same structure as a Breath First Search (BFS) tree q t of the query graph. Its nodes represent a query vertex u with its label and candidate set. For every edge (u 1 , u 2 ) in q t , the CPI keeps the edges between the candidate sets of u 1 and u 2 . This CPI is then traversed to enumerate subgraph isomorphism embeddings by processing the core, then the forest and Ąnally the leaves. For the core, it uses a path-based ordering that minimizes the number of generated embeddings while favoring the paths with non-tree edges.

CFL-Match

On the other hand, DAF [START_REF] Han | Efficient subgraph matching: Harmonizing dynamic programming, adaptive matching order, and failing set together[END_REF] addresses the limitations of TurboISO and CFL-Match by converting the query graph into a DAG instead of a spanning tree. The algorithm uses dynamic programming to Ąnd the candidate set for all the subgraph isomorphism embeddings then follows an adaptive, DAG-based ordering to build the possible embeddings. Moreover, VC [START_REF] Sun | Subgraph matching with effective matching order and indexing[END_REF] improves the path-based ordering with a cost function that considers edges also between the paths. VC uses a bigraph index for holding the candidate edges instead of a spanning tree as it is the case for CFL-Match.

Finally, to detect patterns in a dynamic graph, TurboFlux [START_REF] Kim | TurboĆux: A fast continuous subgraph matching system for streaming graph data[END_REF] uses a data-centric graph (DCG) representation of the intermediate results. A DCG is composed of the data graph such that for each data node, its candidate query vertices are represented by incoming edges. This DCG is then traversed to Ąnd subgraph isomorphism matches. TurboFlux deĄnes transition rules on every edge in the DCG, then, whenever an edge is inserted or deleted, it Ąrst checks whether it matches an edge in the query graph or not and then updates the results according to the transition rules.

Parallel algorithms for subgraph isomorphism

In order to scale up the existing algorithms, two categories of parallel approaches showed up addressing the problem of subgraph isomorphism, namely relational join-based and exploration-based. We also Ąnd the GPU-friendly algorithms that use joins or exploration to implement subgraph isomorphism enumeration on massively parallel architectures.

Join-based approaches

The data graph edges are considered as relational database tables, such that each pair of labels forms a table, the attributes represent the two labels and the edge identiĄers are the attribute values. These tables are Ąltered and a series of joins is applied to get the matching answers. However, joins are very costly and many works addressed this problem through different categories of joins: binary joins where the Ąrst two tables (edge candidates) are joined, then, the result is joined again with a third table of edge candidates until obtaining the end result [START_REF] Plantenga | Inexact subgraph isomorphism in mapreduce[END_REF][START_REF] Zeng | A distributed graph engine for web scale rdf data[END_REF][START_REF] Gurajada | Triad: a distributed shared-nothing rdf engine based on asynchronous message passing[END_REF][START_REF] Tran | Fast subgraph matching on large graphs using graphics processors[END_REF]. These works propose different join orders that aim at optimizing the size of intermediate results. Other works attempted to join substructures larger than edges which resulted into reducing further the size of intermediate results. In [START_REF] Sun | Efficient subgraph matching on billion node graphs[END_REF], the pattern graph was decomposed into stars (two level trees) that can be found through data graph exploration (they require only information about direct neighbors of each data vertex). After that, the matched substructures were joined to form a complete subgraph match. More recent works used different joining units such as the TwinTwig [START_REF] Lai | Scalable subgraph enumeration in mapreduce[END_REF], Crystal [START_REF] Qiao | Subgraph matching: on compression and computation[END_REF] or Clique [START_REF] Lai | Scalable distributed subgraph enumeration[END_REF][START_REF] Lai | Distributed subgraph matching on timely dataĆow[END_REF].

On the other hand, Afrati et al. [START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF] used the multiway joins where all the edge candidate sets are joined at the same time. Furthermore, worst-case optimal join algorithms are also used for multiway joins. Two common algorithms are GenericJoin [START_REF] Ngo | Skew strikes back: New developments in the theory of join algorithms[END_REF] and LeapFrog TrieJoin [START_REF] Veldhuizen | Leapfrog triejoin: a worst-case optimal join algorithm[END_REF]. Parallel approaches for Ąnding subgraph isomorphism based on these algorithms were proposed by [START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF] and [START_REF] Fuchs | Edgeframe: Worst-case optimal joins for graph-pattern matching in spark[END_REF] respectively. Mhedhbi et al. combined both binary joins and the GenericJoin algorithm to evaluate subgraph isomorphism in [START_REF] Mhedhbi | Optimizing subgraph queries by combining binary and worst-case optimal joins[END_REF].

In [START_REF] Lai | Distributed subgraph matching on timely dataĆow[END_REF], Lai et al. surveyed and conducted an experimental comparison of a set of join-based GPM algorithms and classiĄed them into three categories based on the join strategy applied.

Exploration-based approaches

These are approaches based on data graph exploration, which naturally Ąt into the newly TLAV paradigms for distributed graph processing. We discuss this category more in detail in Chapter 3 after introducing the different concepts and programming models for distributed graph processing in Chapter 2. However, as an exception, we present here the four works QFrag [START_REF] Seraąni | Qfrag: Distributed graph search via subgraph isomorphism[END_REF], CECI [START_REF] Bhattarai | Ceci: Compact embedding cluster index for scalable subgraph matching[END_REF], PSM [START_REF] Csun | Parallelizing recursive backtracking based subgraph matching on a single machine[END_REF] and BENU [START_REF] Wang | Benu: Distributed subgraph enumeration with backtracking-based framework[END_REF]. First, QFrag and CECI replicate the data graph on multiple machines where each processor runs subgraph isomorphism search on different parts of the data graph. Moreover, PSM evaluates subgraph isomorphism in parallel on a single machine, while BENU is presented here because it is also a parallel system that uses a similar approach to answer GPM queries.

QFrag [START_REF] Seraąni | Qfrag: Distributed graph search via subgraph isomorphism[END_REF] replicates the data graph on k workers and parallelizes TurboISO to evaluate subgraph isomorphism while using task fragmentation to achieve load balance. QFrag decomposes the Ąrst super-step of processing into two phases. In the Ąrst phase, each worker is assigned a list of roots from which it builds the corresponding CRs. It considers the embeddings enumeration of each CR as one subtask and estimates the processing time of each tree to detect any outliers that cannot be processed locally. Embedding enumeration of regular trees is conducted locally in the Ąrst super-step, while the outlier trees are split into equal subtasks and distributed over the workers to be processed in the second super-step. CECI [START_REF] Bhattarai | Ceci: Compact embedding cluster index for scalable subgraph matching[END_REF] is based on a spanning tree index constructed from a BFS traversal of the query graph. Each node in this tree maps a query node u to a data node v matched to it and to its neighbor for representing the tree edge candidates. It also keeps candidates of uŠs neighbors that are connected by a non-tree edge. This index is then used to enumerate subgraph isomorphism embeddings in parallel. Every candidate of the query tree root is used as a pivot of an Embedding Cluster (EC) that will be processed in parallel. To achieve load balancing, CECI estimates the cost of evaluating each EC, then decomposes the costly ones into multiple ECs. Each worker processes an equal number of ECs. Finally, CECI keeps the candidates of the non-tree edges in its index and uses an intersection between the two sets, i.e. tree-edge candidates and non-tree edges candidates, to enumerate the embeddings. Furthermore, PSM [START_REF] Csun | Parallelizing recursive backtracking based subgraph matching on a single machine[END_REF] parallelizes backtracking based algorithms that adopt a DFS traversal of the candidates tree index on a single machine. PSM decomposes the tree index into search regions and each worker is assigned a region that it can expand independently in parallel. Load balancing is conducted dynamically where busy workers split their search regions into two equal subtasks. Finally, BENU [START_REF] Wang | Benu: Distributed subgraph enumeration with backtracking-based framework[END_REF] also uses backtracking and decomposes the search tree into regions to be processed by different workers. The workers use adjacency lists of the data graph to enumerate possible embeddings through the application of set intersections. Load balancing is achieved by splitting a tree task into subtasks if the degree of the current tree root vertex is larger than a certain threshold.

GPU-friendly approaches

Under this category, we Ąnd the approaches aiming to accelerate graph processing tasks with the help of GPU friendly algorithms. A CPU is characterized by a limited number of powerful cores, whereas a GPU has thousands of cores with lower individual performance. Graphics processors are highly used nowadays to implement solutions for graph problems, e.g. shortest path [START_REF] Harish | Accelerating large graph algorithms on the gpu using cuda[END_REF][START_REF] Katz | All-pairs shortest-paths for large graphs on the gpu[END_REF], BFS [START_REF] Luo | An effective gpu implementation of breadth-Ąrst search[END_REF][START_REF] Zhang | Dynamic parallelism for simple and efficient gpu graph algorithms[END_REF], and minimum spanning tree [START_REF] Vineet | Fast minimum spanning tree for large graphs on the gpu[END_REF][START_REF] Rostrup | Fast and memory-efficient minimum spanning tree on the gpu[END_REF]. Each core in the GPU works in a single-instruction-multiple-data (SIMD) fashion, i.e. the same instruction is executed on different input data in parallel. For speeding up the computing process, GPUs use a global memory with a large amount of device memory and a shared memory for each multiprocessor with a limited amount of device memory. A comprehensive survey on the challenges of GPU-based graph processing models and algorithms can be found in [START_REF] Shi | Graph processing on gpus: A survey[END_REF].

Many GPU based algorithms were suggested tackling the GPM problem. GpSM [START_REF] Tran | Fast subgraph matching on large graphs using graphics processors[END_REF] is a graph pattern matching algorithm based on subgraph isomorphism that was designed for massively parallel architectures. The authors proposed a Ąlter-and-join approach that takes on edges as a basic processing unit. A selection order is Ąrstly obtained for the query vertices based on some selection criteria. They get such order by extracting a query tree from the query graph. Edges are added to the tree iteratively by selecting at each step the ones maximizing the ratio between the vertices degree and their labels frequency. This selection order was proven to reduce the size of the search space. Then, for each query vertex in the tree, a Ąlter phase is conducted in parallel to check the candidacy of every data vertex against it. To Ąlter out more data vertices, the neighborhood of each query vertex is explored in parallel. A candidate vertex v is pruned out if there is a query vertex u ′ adjacent to u such that u ′ does not have any candidate vertex in the adjacency list of v. Another reĄnement strategy is also executed to prune low-connectivity vertices with a degree less than a certain threshold. In the joining phase, candidate edges are gathered then combined to form partial subgraph matches incrementally. They collect candidate edges for each query edge, given a query edge (u, u ′ ) such that C(u) and C(u ′ ) are the respective candidate sets of u and u ′ , candidate edges of (u, u ′ ) are all the edges

(v, v ′ ) verifying v ∈ C(u) and v ′ ∈ C(u ′ ).
At the end of this phase, each query edge is assigned a set of candidate edges. Then, the algorithm combines partial matches starting from the smallest set of candidate edges to the largest one. Here, subgraph matches are constructed iteratively by picking up at each step an edge from the candidate edges, then joining it to the already built partial matches. One of the main assets of GpSM is the graph representation in memory, it uses a different representation for storing the candidate vertices and candidate edges.

GpSense [START_REF] Tran | Towards gpu-based commonsense reasoning: Using fast subgraph matching[END_REF] is an algorithm that enhances the performance of GpSM allowing to Ąnd subgraph isomorphism efficiently on large common-sense knowledge graphs. The main issue with knowledge graphs is their huge size not allowing them to be stored on the memory of a single GPU, which led the authors to propose a new graph compression technique that permits to reduce the graph size while preserving the same subgraph isomorphism results. In a knowledge graph, they noticed that multiple data nodes playing the same role have the same adjacency list, based on this observation, the authors propose a multiple-level compression technique that merges such data nodes into one hyper-node.

In [START_REF] Wang | A comparative study on exact triangle counting algorithms on the gpu[END_REF], the authors proposed a GPU-friendly algorithm for Ąnding subgraph isomorphism in a large graph dataset. The initial problem that consists of counting triangles in a large network is converted into a subgraph matching problem. They built a Ąlter-and-join strategy for subgraph isomorphism based on the Gunrock [START_REF] Wang | Gunrock: A high-performance graph processing library on the gpu[END_REF] programming model.

Gunrock allows programmers to design primitives for graph processing on the GPU with a high level of abstraction and higher performance. ItŠs a parallel, high-level data-centric model manipulating a basic subset of edges or vertices that are actively participating in the computation (such subset is called frontier). A program within the Gunrock framework consists of three steps: advance, Ąlter and compute. The advance step generates a new frontier from the current frontier by exploring the neighbors of its vertices or edges . The Ąlter step generates a new frontier from the current one by extracting a subset of it based on some criteria deĄned by the programmer. Finally, the compute step that consists of a programmer-speciĄed function to be executed in parallel on the elements of current frontier.

To enumerate subgraph isomorphism matches, this approach proceeds as follows. First, the candidate vertices initialization is executed where the candidate set is Ąlled according to the information held by every data vertex, this phase is executed within an advance operator. In the second step, candidate edges are collected using the advance and Ąlter operators. Finally, the joining step combines together candidate edges is executed to incrementally build subgraph matches in parallel. This approach showed better performances in the running time compared to the GpSM implementation of subgraph isomorphism when the size of the query graph increased.

Other works such as [START_REF] Lin | Network motif discovery: A gpu approach[END_REF][START_REF] Zeng | Gsi: Gpu-friendly subgraph isomorphism[END_REF][START_REF] Chen | Partition-oriented subgraph matching on gpu[END_REF] also propose new algorithms, partitioning strategies or data structures that are GPU-based to solve the problem of subgraph isomorphism in massively parallel architectures.

Limitations of subgraph isomorphism

Although discussions regarding the approximate solutions have dominated the research on subgraph matching over the recent years, their performance is not yet able to manage the actual size of the GPM problem. We are facing today a growing need for more performing techniques and tools that can process big graphs; that are highly dynamic and distributed over hundreds of machines because of their enormous size. For example, Facebook is the largest social network with 2.4 billion monthly active users in June 2019 [START_REF] Dustin | Social media statistics 2020: Top networks by the numbers[END_REF]. Furthermore, subgraph isomorphism requires the input graph to be structurally identical to the data graph. In its stringent formulation, it does not consider the intrinsic deformations of an object from its ideal model. Such drawbacks have led the research community to investigate other models of GPM that are less expensive in time and space and exploit better the semantic information held by labels. Graph simulation and its extensions are considered nowadays the best Ąt techniques for GPM in many of the emerging applications like analyzing associations in social networks [START_REF] Ogaard | Discovering patterns in social networks with graph matching algorithms[END_REF].

Relaxed Graph Pattern Matching

In this section, we review graph simulation and the other models proposed as an alternative to structural GPM. Models in this category aim to capture more similarities by relaxing the matching constraints imposed by structural GPM, which may result into answers that do not have the same structure of the query. This way of deĄning similarity is highly needed in the current real-world applications such as plagiarism detection. For example, Chao et al. proposed an approach based on graph pattern matching to detect plagiarism in programs having thousands of lines of code [START_REF] Liu | Gplag: Detection of software plagiarism by program dependence graph analysis[END_REF]. They use the program dependence graph to Ąnd similar graphs in an available code base.

Graph simulation

Graph simulation (GSIM) is a Ćexible model that allows one query vertex to be mapped to multiple data vertices. It maps separately every edge from the pattern graph to edges in the data graph resulting into one-to-many matching as an output. A vertex v in the data graph G(V, E, f ) is mapped to a vertex u in the query graph Q(V q , E q , f q ) if they have the same labels and the vertices on the outgoing edges of u have matches among the children of v. In a formal way: given a data graph G and a pattern graph Q, a binary relation R ⊆ V q × V is said to be a match if:

(1) ∀ (u, v) ∈ R, f (u) = f q (v), (2) ∀(u, u ′ ) ∈ E q , ∃(v, v ′ ) ∈ E such that (u ′ , v ′ ) ∈ R.
Graph G matches pattern Q via graph simulation, if there exists a total match relation R where ∀u ∈ V q , ∃v ∈ V , such that (u, v) ∈ R. It was proved that a total match can be found in polynomial time (quadratic time) using a reĄned version of the Ąrst algorithm of graph simulation, called HHK [START_REF] Henzinger | Computing simulations on Ąnite and inĄnite graphs[END_REF]. Another algorithm for graph simulation was proposed in [START_REF] Fan | Graph Pattern Matching: From Intractable to Polynomial Time[END_REF].

Given the data graph G 1 in Figure 1.2b and the pattern graph Q 1 in Figure 1.2a, the application of graph simulation returns a match set R containing all the vertices of G 1 except three vertices ¶11, 27, 34♢, as it is shown in Figure 1.4. We notice that several vertices appearing in R should not have been conserved, notably ¶10, 33♢. Graph simulation may appear like inexact graph pattern matching, but this is not true. Error-tolerant approaches allow mismatches while graph simulation does not, i.e. the answers returned by graph simulation respect the constraints deĄned by the model when inexact matching tolerates incorrect matches to some degree. Besides its low complexity, graph simulation is a natural Ąt for performing graph matching on a fragmented data graph [START_REF] Fan | Graph Pattern Matching: From Intractable to Polynomial Time[END_REF]. However, its weak part is failing to capture topological similarities between matched graphs, since a disconnected graph can be correctly set as a match for a connected one (a query example is given in Figure 1.5a and its answer in Figure 1.5b), and a cyclic pattern can be matched to tree subgraphs (a cyclic pattern example is shown in Figure 1.5c and its answer in Figure 1.5d).

𝐵

Dual simulation

Dual simulation (DSIM) [START_REF] Ma | Capturing topology in graph pattern matching[END_REF] considers parent relationships in addition to the child relationships imposed by graph simulation. A vertex v from G = (V, E, f ) is mapped to a vertex u in Q = (V q , E q , f q ), if they have the same labels and the vertices on their incoming and outgoing edges are also mapped together. Formally, a data graph G matches a pattern graph Q via dual simulation if there exists a binary match relation

R ⊆ V q × V such that:
(1) ∀(u, v) ∈ R, f q (u) = f (v), i.e. u and v have the same label,

(2) ∀u ∈ V q , ∃v ∈ V such that (u, v) ∈ R and:

(a) ∀(u, u ′ ) ∈ E q , ∃(v, v ′ ) ∈ E such that (u ′ , v ′ ) ∈ R (child relationship), (b) ∀(u ′′ , u) ∈ E q , ∃(v ′′ , v) ∈ E such that (u ′′ , v ′′ ) ∈ R (parent relationship).
Moreover, the maximum dual match set is deĄned as follows.

DeĄnition 12 (Maximum dual match set). Given a data graph G = (V, E, f ) and a query graph Considering that a connected graph is said to be an answer to a certain query if and only if ∀u ∈ V q , ∃v ∈ V that matches u. Dual simulation brings duality into graph simulation i.e. it eliminates cases where disconnected graphs are considered answers to connected graph queries (back to the example in Figure 1.5, the partial answer composed of vertices ¶1, 2, 3♢ in Figure 1.5b is not valid as an answer on its own to the query in Figure 1.5a in the case of dual simulation due to the absence of label C).

Q = (V q , E q , f q ). Let R ⊆ V q × V
Even though dual simulation returns answers of better quality, it does not take into account the data locality compared to graph simulation. Data locality indicates the scope in which we should look for answers to our query. It could be the distances between vertices in the resulting graph or its size. It is obvious that dual simulation does not take into account data locality since cycles in the query graph can be matched to very long cycles in the data graph. The data locality problem becomes relevant when the returned answers are very large, thus difficult to analyze and also when the distances between data vertices are not kept, making the relationships between distant vertices lose their meaning. That is why this model was reinforced by introducing strong simulation.

Strong simulation

Strong simulation (SGSIM) [START_REF] Ma | Capturing topology in graph pattern matching[END_REF] improves dual simulation by adding data locality such that matches are only searched in a ball b of center v and having as radius d q , the diameter of the pattern graph Q. (1) Q matches Ĝ [v, d q ] with maximum dual match set R b dq in ball b of radius d q , (2) v is member of at least one of the pairs of R b dq . For every vertex v in the data graph, the connected part of the result match graph of each ball with respect to its R b dq containing v is called a maximum perfect subgraph (Max-PG) of G with respect to Q. By proposing a cubic time algorithm, the authors proved that strong simulation not only succeeds to capture more topological similarities, but it also keeps the same polynomial time complexity as graph simulation.

Applying strong simulation to the example given in Figure 1.2 eliminates matches that fall within the long cycle composed of ¶18, 19, 20, 21, 22, 23, 24, 25♢, because the distance between vertices 18 and 25 is greater than the patternŠs diameter, which is equal to 4. The maximum match set contains the vertices ¶1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 26, 28, 29, 32♢ as shown in Figure 1.7. However, strong simulation is limited in terms of scalability since it incurs very long processing time and memory consumption for locality balls creation, especially when the data graph is very large.

Strict simulation

Strict simulation (STSIM) improves strong simulation with a revised deĄnition of locality which enables achieving better quality of results with performance enhancements [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF]. Locality balls are created from the members of the dual match graph instead of generating them directly from the dual match set in the initial data graph as it is the case in strong simulation. The difference is that in strong simulation the balls may contain data vertices that are not in the dual match graph while in strict simulation the balls contain only members from the dual match graph.

Let us deĄne the dual match graph Ąrst.

DeĄnition 13 (Dual match graph). Given a data graph G = (V, E, f ) and a query graph Q = (V q , E q , f q ). The dual match graph is the subgraph

G ′ = (V ′ , E ′ , f ) of G composed of V ′ and E ′ such that : (1) V ′ is the set of all vertices in R d (the maximum dual match relation for Q in G), (2) E ′ ⊂ E such that ∀(v, v ′ ) ∈ E ′ , ∃(u, u ′ ) ∈ E q verifying (u, v) ∈ R d and (u ′ , v ′ ) ∈ R d .
Given a data graph G = (V, E, f ) and a query graph

Q = (V q , E q , f q ) such that G d = (V d , E d , f d ) is the dual match graph. G matches Q via strict simulation if there exists a vertex v ∈ V d , such that: (1) Ĝd [v, d q ] matches Q where Ĝd is a subgraph of G d centered at v with radius d q ,
(2) v is member of the resulting Max-PG.

Strict simulation results into better efficiency by decreasing the size of the locality balls, while obtaining better matches. The authors proposed an algorithm for calculating the Max-PGs in cubic time. When applying this model on the example of Figure 1.2, it results into the same match graph as strong simulation. However, we notice that the size of the balls created is smaller than in the case of strong simulation because the latter contains also non candidate vertices, the results are shown in Figure 1

Tight simulation

It is based on strict simulation where only the most important vertices of the query graph are considered in locality balls creation [START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF]. If strong simulation generates a ball centered at each data vertex, and strict simulation creates a ball for each member of the dual match graph, then tight simulation picks only data vertices candidate to the query vertex with the highest selectivity score. The selectivity score here is a measure computed for each query vertex based on its degree and label frequency. This measure allows us to choose the most important vertex among the graph vertices. Tight simulation reduces the number of locality balls, resulting in shorter processing time, because the size of intermediate results is reduced and duplicated partial answers are minimized. It is formally deĄned as follows: Given a pattern graph Q = (V q , E q , f q ) and a data graph

G = (V, E, f ). G matches Q, if there are vertices u in Q and u ′ in G such that:
(1) u is a center of Q with highest deĄned selectivity,

(

) (u, u ′ ) ∈ R D , where R D is dual match set between Q and G, (3) Q matches ĜD [u ′ , d q ] 2
where ĜD is a ball extracted from G D (result of dual simulation) with radius d q , (4) u ′ is member of the result Max-PG.

Among the centers of the query graph, the authors pick the one with the highest ratio of its degree to its label frequency (max u∈C (deg(u)/f req(f q (u))), where C is the set of query centers). The locality balls are created with a radius equal to the eccentricity of the query graph. They proposed a distributed algorithm with cubic time complexity for Ąnding all the Max-PGs with respect to tight simulation [START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF].

We apply tight simulation on the example of Figure 1.2, the list of eccentricities for each query vertex is ¶(A : 3), (B : 4), (C : 2), (D : 3), (E : 4)♢. There is only one center in Q 1 having a minimum eccentricity equal to 2 which is C. The data vertices ¶4, 9, 17, 26, 30♢ are part of the dual match graph between Q 1 and G 1 . Hence, according to tight simulation, we only create balls centered at these vertices with radius equal to 2.

Then, for each ball, we verify the dual match relation between the ball members and the query vertices. The ball centered at 4 gives a match set containing the following data vertices: ¶1, 2, 3, 4, 5, 6♢. The ball centered at 9 gives us the same previous match set. Then, the balls centered at 17, 26 and 30 result all in zero matches. We notice that tight simulation here gives the exact same result as subgraph isomorphism (results are shown in Figure 1.9), while it can be computed in cubic time. The limitation of tight simulation is that it is too strict for some applications of GPM where zero answers are not welcomed.

𝐵

Bounded simulation

Bounded simulation (BSIM) [START_REF] Fan | Incremental graph pattern matching[END_REF] is an extension of graph simulation that came as a revision for the traditional subgraph isomorphism model, that falls short of capturing similarities in the actual emerging applications, e.g. detecting communities in social networks. A bounded path p in G is a sequence of vertices

v 1 , v 2 , . . . , v n ∈ V , such that ∀i ∈ ¶1, . . . , n -1♢, (v i , v i+1 ) ∈ E.
In this model, a data graph is deĄned as

G = (V, E, f A ), such that f A is used instead of the labeling function f . For each node u in V , f A (u) is a tuple of attributes (A 1 = a 1 , . . . , A n = a n ). Furthermore, a pattern graph is given as Q = (V q , E q , f v , f e )
where two functions f v and f e are introduced. First, f v (u) is a conjunction of predicates on the attributes of u. f e is another function deĄned on E q to limit the length of paths matched to each edge of E q (f e (u, u ′ ) = ¶k, * ♢ where * means no requirement on the path length).

A data graph G matches a pattern graph Q via bounded simulation if there exists a binary relation R ⊆ V q × V such that:

(1) ∀u ∈ V q , ∃v ∈ V such that (u, v) ∈ R, (2) ∀ (u, v) ∈ R: (a) The attributes f A (v) of v satisfy the predicate f v (u) of u, (b) ∀ (u, u ′ ) ∈ E q , (u, u ′
) is mapped to a non-empty, bounded path p of length

k from v to v ′ in G such that (u ′ , v ′ ) ∈ R and len (p) ≤ k if f e (u, u ′ ) is a constant k.
Graph simulation is a special case for bounded simulation where only edge-to-edge mappings are allowed. In the same paper, the authors proposed an algorithm for computing bounded simulation that runs in cubic time. Incremental algorithms for bounded simulation were also proposed for the case of a continuously updated data graph.

Example 2. We present in Figure 1.10 another example of, respectively, a pattern graph Q 2 and a data graph G 2 . By applying bounded simulation, we get the edge (B, A) mapped to the edge (2, 1), edge (A, C) mapped to the path [START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF][START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF][START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF] of length 2, (C, D) mapped to paths [START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF][START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF] and [START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF][START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF][START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF]. Also, the edges (D, E) and (E, D) are mapped respectively to (5, 7) and [START_REF] Bhattarai | Ceci: Compact embedding cluster index for scalable subgraph matching[END_REF][START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF][START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF]. Note that (D, E) cannot be mapped to the path [START_REF] Bhattarai | Ceci: Compact embedding cluster index for scalable subgraph matching[END_REF][START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF][START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF][START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF] because this latter is of length 3, which does not satisfy the constraint on the edge (D, E) in Q 2 . The result of applying bounded simulation is shown in the same Ągure.

Relaxation simulation

This model is an extension of graph simulation that allows partially absent vertices with the condition of substituting them with their children and / or parents [START_REF] Gao | Prs: parallel relaxation simulation for massive graphs[END_REF]. To avoid the problem of zero answers, the authors relax the constraints imposed by graph simulation and dual simulation with respectively two models: unidirectional relaxation simulation (URS) and dual relaxation simulation (DRS).

Given a data graph G = (V, E, f ), a pattern graph Q = (V q , E q , f q ) and a matching relation R ⊆ V q × V with (u, u ′ ) ∈ R. If graph simulation requires all children of u ∈ V q to be matched with some or all the children of u ′ ∈ V , then URS relaxes this constraint by accepting also that grand-children of u ′ replace their absent parents if they match the children of u. The same goes for DRS such that in addition to children constraints, if there are no parents to u ′ matching some parents of u ′ , the grand-parents of u ′ that respect the matching constraints are considered in the Ąnal match relation.

Surjective simulation

Surjective simulation (SJS) [START_REF] Shemshadi | Efficient pattern matching for graphs with multi-labeled nodes[END_REF] extends bounded simulation by relaxing the matching constraints for the context of multi-labeled graphs. Vertices may have multiple labels and this model redeĄnes the problem of graph pattern matching by instead of imposing that all the labels of a query graph exist on its matched data vertex, surjective simulation is deĄned such that a query vertex u from the query graph can be correctly matched to a data vertex v if the two share a minimum number of common labels. Moreover, the answers to surjective simulation must fall within a ball that has at most the diameter of the input query graph. Shemshadi et al. [START_REF] Shemshadi | Efficient pattern matching for graphs with multi-labeled nodes[END_REF] proposed an algorithm for Ąnding the top-k matches w.r.t. surjective simulation.

Taxonomy simulation

Taxonomy simulation (TXS) [START_REF] Li | Relaxing graph pattern matching with explanations[END_REF] relaxes the label constraints in graph simulation by allowing the mapping of different labels. This model introduces taxonomy to the context of relaxed GPM through the use of a taxonomy graph in the matching process. A taxonomy graph is a labeled rooted forest T that represents the existing relationships between different labels. It deĄnes a specialization-generalization hierarchy in the data graphs. The edges of T model an is-a relationship between two vertices.

Taxonomy simulation redeĄnes the problem of graph pattern matching by allowing a query vertex u in Q (labeled with l) and a data vertex v in G (labeled with l ′ ) to be matched if and only if l ′ is a descendent of l in the taxonomy hierarchy tree T .

Multi-constrained simulation

Multi-constrained simulation (MCS) [START_REF] Shi | Multi-Constrained Top-K Graph Pattern Matching in Contextual Social Graphs[END_REF] addresses the problem of multiple constraints on edges by providing a non-trivial extension to bounded simulation. As opposed to bounded simulation that supports only one constraint on the edge, i.e. the path length, multi-constrained simulation allows for multiple constraints on the edge attributes. In the same paper, a multi-threading heuristic algorithm was proposed for evaluating GPM queries based on multi-constrained simulation.

Limited simulation

Limited simulation (LSIM) [START_REF] Du | Personalized graph pattern matching via limited simulation[END_REF] is a model that considers the attributes on both vertices and edges. It uses a similarity measure between vertices called k-similarity. Given a data graph G (V, E, f V , f E ) and a pattern graph Q (V q , E q , f V q , f Eq , w) where (i) f V and f V q are the respective vertex labeling functions associated to G and Q, (ii) f E and f Eq are the respective edge labeling functions associated to G and Q, (iii) w is a weight function that maps each u ∈ Q to an element in N ∪ ∞. This weight is deĄned based on the application domain, it could be for example the diameter of a circle of authority of a manager in a social network.

DeĄnition 14 (k-limited similarity). k-limited similarity is a relation between two nodes

v in G and u in Q denoted by v ≥ k u. Formally, v is k-limited similar to u if: (1) f V (v) = f V q (u) when k = 0, (2) v ≥ 0 u; ∀e q = (u, u ′ ) ∈ Eq, ∃e = (v, v ′ ) ∈ E with f Eq (e q ) = f E (e) and v ≥ k-1 u when k > 0.
G matches Q via limited simulation if there exist a node mapping relation R v ⊆ V q × V and an edge mapping relation R E ⊆ E q × E such that:

(1)

∀ (u, v) ∈ R v , v ≥ w(u) u, (2) ∀ (e = (u, u ′ ), e ′ = (v, v ′ )) in R E , we have f Eq (e) = f E (e ′ ), (u, v) ∈ R V and (u ′ , v ′ ) ∈ R V .
This model is better suited for applications in social media since it considers also the types of vertices and edges. The authors proposed also a polynomial algorithm to evaluate limited simulation.

Time-respecting simulation

Time-respecting simulation (TRS) [START_REF] Zhang | Distributed time-respecting Ćow graph pattern matching on temporal graphs[END_REF] also revises bounded simulation for the context temporal data graphs. The data graph edges are timestamped which implies that the matching process not only looks for vertices satisfying bounded simulation constraints but also veriĄes the time validity of the answer. Given a query graph Q = (V q , E q , f q ) and a data graph G = (V, E, f, f t ), where f t maps edges to timestamps. A path p = (e 1 , e 2 , .., e n ), such that ∀i, e i ∈ E, is considered a match to a query edge e ∈ E q if and only if p is a time-respecting path. A time-respecting path is a sequence of edges with non-decreasing time.

Double simulation

The most recent model in the relaxed GPM category is double simulation (DBS) [START_REF] Wu | Leveraging double simulation to efficiently evaluate hybrid patterns on data graphs[END_REF]. It extends bounded simulation by imposing the matching constraints on both children and parents of a data vertex. On the other hand, double simulation can be seen as an extension of dual simulation that maps edges in the query graph to paths in the data graph.

Chapter summary

To sum up what has been presented in this chapter, graph simulation was the Ąrst model that came to relax the matching constraints imposed by subgraph isomorphism.

Three extensions to this model were proposed, bringing a new deĄnition of similarity; dual simulation that captures more topological structures (connected components and undirected cycles), bounded simulation that matches edges with paths of bounded length, and limited simulation that considers a new similarity information called k- Figure 1.11 illustrates how these extensions, based on graph simulation, make the constraints more or less relaxed or more stringent. The schema does not consider limited simulation as an extension since it redeĄnes the notion of similarity rather than adding or omitting some constraints to / from the original model.

The following propositions were given in [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF][START_REF] Ma | Capturing topology in graph pattern matching[END_REF][START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF] to describe the relations between some GPM models:

(1) If Q matches G via subgraph isomorphism, then Q matches G via tight simulation.

(2) If Q matches G via tight simulation, then Q matches G via strict simulation.

(3) If Q matches G via strict simulation, then Q matches G via strong simulation.

(4) If Q matches G via strong simulation, then Q matches G via dual simulation.

(5) If Q matches G via dual simulation, then Q matches G via graph simulation.

Furthermore, Figure 1.12 depicts the inclusion relationships between the different models.

Based on the application needs, we should decide to opt for graph simulation when interested in Ćexibility and short response time. Moving from graph simulation toward tight simulation and subgraph isomorphism will result in longer response time, but will allow us to get better quality results compared to dual simulation and graph simulation.

GSIM DSIM SGSIM STSIM TSIM ISO BSIM Figure 1.
12 The inclusion relationships between results obtained by the different GPM models discussed.

However, even with the progress made in reducing subgraph matching complexity from exponential to a polynomial time, massive graphs containing billions of nodes and trillions of edges cannot be stored or processed in a single machine. The following chapter discusses this issue and presents the different mechanisms used in handling graphs distributed over multiple machines.

Chapter 2 Graph Pattern Matching in Massive

Graphs: State-of-the-art

Introduction

Huge amounts of raw data that need to be analyzed are collected every minute. It is common to partition and distribute them over multiple machines, so that queries can be efficiently evaluated in a distributed fashion. Therefore, sequential algorithms used in Ąnding subgraph isomorphism or graph simulation need to be adapted for this context. In this chapter, we provide an overview of the paradigms used in distributed graph processing. In a second part, we dive deeper into how these paradigms for massive graph processing are used in the context of graph pattern matching. Finally, we draw a taxonomy of the distributed GPM approaches based on multiple classiĄcation criteria.

Distributed graph processing

The most common distributed architecture used for handling massive graphs is the master-slave architecture. The master is a machine of the cluster executing tasks of coordination between different slave machines (a.k.a. workers) that are responsible for parallel computations. The master machine also performs some monitoring tasks to maintain a green state of the cluster so that all workers keep running smoothly. According to Yan et al. in [START_REF] Yan | Big Graph Analytics Platforms[END_REF], a cluster is composed of mainly four components starting from local storage, to distributed storage, communication layer and Ąnally the computing module. (this architecture is sketched in Figure 2.1). Component (1): Data graphs reside physically on distributed storage. HDFS [START_REF] Borthakur | The hadoop distributed Ąle system: Architecture and design[END_REF] and GoogleŠs Ąle system (GFS) [START_REF] Ghemawat | The google Ąle system[END_REF] are two of the most popular distributed Ąle systems used currently by several high-scale graph processing systems. These two Ąle systems share the same aspects but do have some differences including the block size, node division and the deletion strategy adopted.

Component (2):

This part of the distributed architecture is responsible of loading graphs from the distributed Ąle system to memory. In a parallel manner, the computation module performs the computations on each machine.

Component (3):

The communication layer deĄnes the technique used to exchange messages between machines in the cluster, e.g. by using the paradigms Message Passing Interface (MPI) or Remote Procedure Call (RPC).

Component (4):

Each machine is responsible of its own local storage, which can be used in out-of-memory systems that need to offload data graphs from memory to local disks during computations.

Since data graphs must be split over multiple data stores, we deĄne a distributed graph along with other related terminologies, i.e., fragment and partitioning strategies.

DeĄnition 15 (Distributed graph). A distributed data graph is a graph G partitioned into k fragments (F 1 , F 2 , . . . , F k ), each fragment is located on a separate machine. (V 1 , V 2 , . . . , V k ) is a partition of G(V, E, L) if and only if: (1) ∪ k i=1 V i = V and (2) for any i ̸ = j ∈ [1, k]V i ∩ V j = ∅.
Fragments of a data graph can depend on each other because of the crossing-edges between vertices in different partitions and such vertices are called boundary nodes.

DeĄnition 16 (Fragment). A fragment

F i is denoted as (G [V i ] , B i ) where G [V i ]
is the subgraph of G stored at machine i and B i is the set of all boundary nodes in this subgraph. We denote B V as the set of all boundary nodes and B E as the set of all crossing-edges.

The partitioning strategy we have just described is commonly used for distributing graphs in the context of GPM and it is called Edge-Cut partitioning. The example shown in Figure 2.2 has three fragments ¶F 1 , F 2 , F 3 ♢, the global boundary set B V is composed of the vertices ¶3, 5, 8, 9, 11♢. The alternative to Edge-Cut strategy is the Vertex-Cut partitioning where edges of the data graphs are split between the different machines. In this case, we have crossing vertices that are shared between multiple machines.

Programming models for distributed graph processing

A programming model speciĄes an abstraction of how a parallel algorithm is designed and executed. MapReduce [START_REF] Dean | Mapreduce: SimpliĄed data processing on large clusters[END_REF] is one of the leading paradigms employed for processing large data sets. However, algorithms that deal with graphs are different since they incur poor data locality and little processing on every vertex of the graph, which results into MapReduce job spending most of the time in I/O operations. This limitation of MapReduce makes it unsuitable for handling distributed graphs. As a result, Pregel framework was proposed in [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF], along with other paradigms that have emerged later challenging the programmer to think like a vertex. In Figure 2.3, we give a classiĄcation of the commonly employed programming models for each layer in a big graph processing system. These models are classiĄed based on three criteria namely execution model, communication and timing. Each one offering two or more ways of deĄning how certain tasks are performed by the system.

Classes of programming models

Timing

The timing deĄnes the synchronization type used to schedule tasks in parallel. Thus, a parallel program can be either synchronous or asynchronous. In synchronous programming models like Bulk Synchronous Parallel (BSP) [START_REF] Valiant | A bridging model for parallel computation[END_REF], programs are composed of super steps separated with synchronization points. After Ąnishing a super step, a process is blocked until all the other processes, executed in parallel, terminate their tasks before moving to the next super step. Asynchronous programming models do not set any constraints on the order in which processes are executed, every process can send any message or execute a task whenever CPU and bandwidth are available.

Considered as the most common model used for parallel processing, the bulk synchronous parallel was proposed by Valiant in 1990 [START_REF] Valiant | A bridging model for parallel computation[END_REF]. A BSP computer is composed of three parts: [START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF] Components that can perform computations locally, (2) A router for exchanging messages between each pairwise of such components, (3) A module allowing for synchronization of these components. Every component carries out a computation in a sequence of global super steps: (a) concurrent computation, (b) communication and (c) barrier synchronization. Figure 2.4 illustrates the functioning of BSP.

Communication

This criterion deĄnes the way messages are exchanged between distant machines in the cluster. We use either a message passing approach or shared memory abstraction. In the Ąrst communication type, a message with its ID, containing information about the source, destination and the needed information is sent from one machine to another while in shared memory abstraction, vertices (programs) are considered as shared variables that are accessed directly from any machine in the cluster.

Execution model

The execution model determines the way a data graph is seen and iterated over. It could be vertex-centric, edge-centric or subgraph centric.

Vertex-centric

The vertex-centric concept was introduced by Google in their paper on Pregel system [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF].

A graph algorithm is executed from the perspective of a vertex that can perform a list of operations as getting its ID, getting/setting its value or getting/counting its edges.

A vertex is analogous to a process in the BSP model. We also deĄne the notion of neighboring processes, i.e. a process can send or receive messages only from its neighbors (An illustration of the vertex-centric model is given in Figure 2.5).

Pregel deĄnes the way a graph processing algorithm is executed in parallel. It is based on the BSP model, and adopts a message passing mechanism to communicate between vertices. The data graph vertices are partitioned among several workers where each vertex executes a compute() function, which is the same for all the vertices. A vertex can have an active or inactive state. A Pregel program consists of a number of synchronized iterations conducted in parallel by several vertices, and that can terminate only if all the processes vote to halt and there are no pending messages waiting to be achieved.

Since its apparition, this model has revolutionized the world of graph processing. Ever after, several open source frameworks were developed, adopting the same model while providing improvements on the communication mechanism, load balancing or fault tolerance. For example, Giraph [START_REF] Foundation | Apache giraph[END_REF] is the most popular framework with a large community working on it, including engineers from Yahoo, Facebook, LinkedIn and Twitter. This system enhanced the initial model of Pregel with three improvements by Ąrst, introducing parallelism at a Ąne grain using multi-threading on each worker. Also, to reduce the communication cost, Giraph serializes Java objects before sending them from one machine to another. Finally, to reduce the out-of-memory problems that occur generally with longer super-steps with too many messages to send, Giraph adopts splits large super-steps into smaller ones. We can cite other systems like GPS [START_REF] Salihoglu | Gps: A graph processing system[END_REF], MocGraph [START_REF] Zhou | MOCgraph : Scalable Distributed Graph Processing Using Message Online Computing[END_REF], Mizan [START_REF] Khayyat | Mizan: A system for dynamic load balancing in large-scale graph processing[END_REF], GraphX [START_REF] Xin | Graphx: A resilient distributed graph system on spark[END_REF], Pregel+ [START_REF] Yan | Effective techniques for message reduction and load balancing in distributed graph computation[END_REF] and GraphD [START_REF] Yan | Efficient processing of very large graphs in a small cluster[END_REF] that propose an improvement of PregelŠs model in a way or another.

Edge-centric

In this class of programming models, the parallel program iterates over the graph edges. Therefore, the computing unit is an edge that can fulĄll some basic operations, e.g. get/set its value or ID, or get the value of its target vertex. An edge can also communicate with its neighboring edges by sending and receiving messages (see the illustration provided in Figure 2.6). This paradigm is well-suited for data Ćows, and X-Stream [START_REF] Roy | X-stream: Edge-centric graph processing using streaming partitions[END_REF] is one of the frameworks adopting it.

Subgraph-centric

Unlike vertex-centric programming where vertices cannot know whether a vertex is located at the same machine or not, subgraph-centric programming considers the fragment of vertices located at the same machine as one computing unit. Here, communications between vertices of the same subgraph are not delayed to the next super-step but executed immediately. Such improvements result to better performance in computing time, number of messages and total super-steps (see illustration of this model in Figure 2.7). In [START_REF] Yan | Big Graph Analytics Platforms[END_REF], Yan et al. recommended this programming model in solving graph pattern matching. Several frameworks support this paradigm including Giraph++ [START_REF] Tian | From "think like a vertex" to" think like a graph[END_REF], GoFFish [START_REF] Simmhan | Goffish: A sub-graph centric framework for large-scale graph analytics[END_REF] and Blogel [START_REF] Yan | Blogel: A block-centric framework for distributed computation on real-world graphs[END_REF], but they are basically vertex-centric.

Subgraph mining systems

On the other hand, there are subgraph mining systems that are dedicated for speciĄc graph applications like subgraph matching, triangles Ąnding or frequent subgraphs listing, e.g. Arabesque [START_REF] Teixeira | Arabesque: a system for distributed graph mining[END_REF], Quegel [START_REF] Yan | A general-purpose query-centric framework for querying big graphs[END_REF], G-miner [START_REF] Chen | G-miner: an efficient task-oriented graph mining system[END_REF], Rstream [START_REF] Wang | Rstream: marrying relational algebra with streaming for efficient graph mining on a single machine[END_REF], Fractal [START_REF] Dias | Fractal: A general-purpose graph pattern mining system[END_REF] and G-thinker [START_REF] Yan | G-thinker: A distributed framework for mining subgraphs in a big graph[END_REF]. The most recent one is G-thinker which differs from previous frameworks that are known to be IO-bound, i.e. their processing time is mostly dominated by I/O operations. G-thinker is CPU-bound thanks to always keeping CPUs busy by switching to tasks that have their data ready instead of waiting for the current task to receive its requested data through the network. It handles two data tables: one for storing the graph available locally and another cache table for remote vertices. The latter is shared by the different subgraphs without the need to duplicate data within each subgraph. A subgraph is handled by one thread independently and hence no synchronization is needed between the different threads. Each thread, called comper, will construct its subgraph and work on it to evaluate subgraph isomorphism or to count the number of local triangles, etc.

V i e 1 e 2 e 3 V i1 V i2 V i3
GRAPE [START_REF] Fan | Parallelizing sequential graph computations[END_REF] is a system that is different from the above mentioned ones. It allows parallelization of sequential graph computations without adopting a TLAV paradigm. Given a data graph G that is composed of k fragments ¶F 1 , F 2 , . . . , F k ♢, GRAPE assigns each fragment to a processor. It uses partial evaluation to solve the graph problem on one fragment of the data graph, i.e. a processor P i evaluates the problem based on the known data available in fragment F i and exchanges messages based on the BSP model to get the missing information updated. Then, each processor updates its partial answer based on the received updates. When no processor emits new messages, an assemble procedure is triggered at a coordinator machine to combine the partial answers.

Each one of the programming models presented in this section is well adapted for designing algorithms that respond to speciĄc problems but not to others. For example, the vertex-centric programming model is adapted for algorithms based on communications where the vertex program does not need to access neighborhood information, e.g. Single Source Shortest Path (SSSP), Page Rank. On the other hand, the subgraph-centric programming model is better suited for algorithms where the vertex-program requires its neighborhood information in addition to its local information to update its local context, which is the case for GPM. Finally, the edge-centric model is used to design Ćow-centric algorithms where the main processing is executed on the graph edges and not on its vertices.

Other programming models also exist, but they are not as commonly used as the ones discussed above. For example, the partition-centric model is a special case of subgraphcentric where all nodes and edges that are located in the same machine are considered as one computing unit. Moreover, neighborhood-centric is another model considering that the scope of a single vertex is composed of its local state and the states of its multi-hop neighborhood. We also Ąnd other programming models similar to the vertex-centric one such as Scatter-Gather and Gather-Sum-Apply-Scatter (GAS). These two models are slightly different from the vertex-centric model. For example, Scatter-Gather deĄnes for each vertex two functions Scatter and Gather. The Scatter function deĄnes and sends messages to its neighbors, while the Gather function allows a vertex to read the received messages and edit its local information. Both functions are executed in the same iteration respecting the BSP model. A comprehensive survey of the programming abstractions used for distributed graph processing can be found in [START_REF] Kalavri | High-level programming abstractions for distributed graph processing[END_REF].

Distributed graph pattern matching approaches

There are several previous works that reviewed and proposed different taxonomies of sequential subgraph isomorphism algorithms such as [START_REF] Conte | Thirty Years of Graph Matching in Pattern Recognition[END_REF][START_REF] Gallagher | Matching Structure and Semantics : A Survey on Graph-Based Pattern Matching[END_REF][START_REF] Foggia | Graph matching and learning in pattern recognition in the last 10 years[END_REF]131]. Other works like [START_REF] Lee | An in-depth comparison of subgraph isomorphism algorithms in graph databases[END_REF][START_REF] Carletti | Comparing performance of graph matching algorithms on huge graphs[END_REF][START_REF] Sun | In-memory subgraph matching: An in-depth study[END_REF] conducted a benchmarking to compare some of the very well known subgraph isomorphism algorithms on the same environment. Unlike previous works, we provide in this section a taxonomy of the distributed GPM approaches based on graph exploration and which adopt the emerging TLAV paradigm and its derivatives. We also discuss these programming models and how they improve solving GPM in massive graphs. This section synthesizes the work conducted recently in GPM on distributed graph processing systems with a narrow focus on relaxed matching that has gained an increased interest during the past ten years.

Querying distributed data graphs

When evaluating a subgraph matching query, fragments of the data graph can be processed separately. Actually, the real challenge here is how we should evaluate GPM for the boundary nodes. Because, as we mentioned earlier in Chapter 1, to verify if a data vertex is a match to a certain query vertex, the matching information of its neighborhood is necessary in the evaluation of the modelŠs constraints. Several answers to this question have been proposed in the literature, we present in this section some of the most relevant.

To Ąnd matches of a query graph in a data graph that is fragmented over multiple sites, a general algorithm follows these steps: a coordinator machine receives the pattern graph Q, then transfers it to the workers which, in turn, perform a local evaluation of the query resulting into a partial matching set. Such partial matches are then sent to the coordinator to combine them into one Ąnal result. Different mechanisms and techniques are involved in the evaluation of GPM for the set of boundary nodes. This can be achieved by either communicating intermediate results between workers or even shipping parts of the fragmented graph from one worker to another. We notice that some GPM propositions rely on the existing frameworks of distributed graph processing while others simply provide a from-scratch implementation of the distributed algorithms.

Different evaluation criteria are used to measure the performance of distributed graph algorithms. Firstly, we have data shipment as the amount of data exchanged between distinct machines during the execution of the algorithm. The second criterion is visit times, the number of messages that are exchanged between workers in the cluster. Finally, there is the make-span (a.k.a. response time) that refers to the duration between receiving the query and Ąnding the result.

Distributed structural graph pattern matching

In this section, we review the latest works proposed for Ąnding subgraph isomorphism in a distributed environment. We classify them based on the timing and execution model applied. The studied works are divided into four classes: synchronous master-slave, asynchronous master-slave, synchronous vertex-centric and asynchronous vertex-centric.

The works presented under this section are considered structural because they aim to Ąnd answers that have the exact same structure as that of the input query.

Synchronous master-slave

This model synchronizes the computation through super-steps separated by communications between workers or between workers and a coordinator. The main difference between an algorithm using a master-slave execution approach and the one adopting subgraph-centric is that the latter is fully centric while the Ąrst one involves a coordinator for exchanging data between different workers or to orchestrate the graph matching process. Both consider the subgraph as one computing unit on which all the operations are made at the same time.

Peng et al. [START_REF] Peng | Processing sparql queries over distributed rdf graphs[END_REF] adopt partial evaluation to Ąnd matches locally to each partition of the distributed data graph. For the cross matches that include data vertices between multiple fragments, each worker evaluates subgraph isomorphism based on its local information and leaves some matches unanswered. Then, the partial matches are assembled on a coordinator site to get cross matches. The assembly algorithm collects all the partial matches, joins them by starting with two partial matches from connected fragments and considers a new match at a time. If the match is complete, another assembly is started, otherwise, other partial matches are joined to form a Ąnal answer. The authors introduce a partitioning of the partial matches to avoid unfruitful joins. Partial matches that share an internal data vertex are collected in the same partition and the assembly is made between different partitions. Another distributed assembly that follows a BSP master-slave was proposed: in the Ąrst super-step the partial-evaluation part is conducted locally, then partial matches are shared between workers to assemble the cross-matches in a distributed way such that an intermediate result is communicated each super-step.

A one-direction communication is used to avoid duplicate answers.

To parallelize TurboISO on a fragmented data graph. Fan et al. [START_REF] Fan | Parallelizing sequential graph computations[END_REF] expand each fragment F i with data vertices from other fragments such that subgraph isomorphism can be evaluated locally on each worker. Subgraph isomorphism is determinable locally for a fragment F i if and only if, for every vertex v ∈ F i , v can reach all its neighborhood within d hops such that d is the diameter of the query graph. This work is based on GRAPE that offers the three functions: partial evaluation (PEval), incremental evaluation (IncEval) and assemble. In PEval, each worker gathers the d-neighborhood of its boundary nodes. Then, it sends them to the coordinator that, in turn, sends each d-neighborhood to where its center resides. IncEval is simply a sequential implementation of TurboISO. Finally, the assemble function takes the union of the subgraph isomorphism matches returned by each worker. The limitation of this approach is that large parts of the data graph may end up duplicated among workers, especially for small diameter graphs and when dealing with complex queries of large diameters.

Asynchronous master-slave

We present the asynchronous approaches that allow workers to communicate with the coordinator machine without synchronization barriers, hence allowing to reduce their waiting time and consequently optimizing the overall response time.

The Ąrst approach under this category is COSI [START_REF] Bröcheler | Cosi: Cloud oriented subgraph identiĄcation in massive social networks[END_REF]. COSI relies on the RDF format1 for describing both the data graph and query graph. The architecture used for evaluating subgraph isomorphism consists of a set of workers that communicate directly with each other and a master node behaving as an interface with the end user. This system uses a partitioning strategy that minimizes the edge cuts between different sites of the distributed architecture. It is based on the idea of keeping on the same machine every two vertices that are likely to be retrieved together by a random query. The query is received by the master that routes it to one or more workers. The worker process the query locally and send back a complete subgraph matching answer to the master node. The local algorithm uses a local index for retrieving neighbors of a data vertex. It deĄnes an order for processing the query variables, Ąnds data candidates of the current query variable, substitutes it with a data vertex v then searches for candidates of the next variable in the set of neighbors of v. It continues executing this operation until no candidates are found in the current partition. At the end of this step, the algorithm veriĄes if a valid match set is obtained or not to send back an answer to the master. So here, the algorithm explores the tree search in a depth Ąrst search fashion where each branch is traversed in parallel to reduce the processing time. This approach for Ąnding subgraph isomorphism performs well in terms of time and data shipment. However, even though neighborhood indexes accelerate and facilitate the access to the data graph vertices, they have generally a super-linear creation time.

In [START_REF] Sun | Efficient subgraph matching on billion node graphs[END_REF], a GPM system developed on top of Trinity [START_REF] Shao | Trinity: A distributed graph engine on a memory cloud[END_REF] was proposed that is based on query decomposition and graph exploration. The aim is to reduce the amount of data shipment involved in the processing and also limit the size of intermediate results by avoiding joins. It includes three major steps: Query decomposition and STwig ordering, Exploration and Ąnally a Joining phase. The query graph is Ąrstly decomposed into STwigs (trees of two levels). After that, a selection algorithm is executed to Ąnd the best order in which these STwigs will be processed minimizing further the size of intermediate results (the output is an ordered sequence of STwigs S 1 , S 2 , . . . , S N ). The STwigs sequence is next delivered to each worker which will process it, explore the graph while joining the partial matches obtained for each STwig (M 1 , M 2 , . . . , M N ), then send back the result R to the coordinator machine. The most important contribution here, is using exploration instead of joining whenever it is possible, which considerably reduces the size of intermediate results. The local evaluation of subgraph isomorphism requires accessing STwig root children located on different workers, and hence involves network communication. Compared to the propositions from previous approaches that rely on indexes, this work has shown performances in response time when handling a graph of one billion nodes. The only index required was intended to accelerate the access to each data vertex by mapping identiĄers to their labels.

Synchronous vertex-centric

We review under this category the synchronous vertex-centric approaches proposed for GPM.

Lighthouse [START_REF] Filip | A scalable graph pattern matching engine on top of Apache Giraph[END_REF] is a system that evaluates subgraph isomorphism and accepts as input a graph query language equivalent to Cypher (the one used by Neo4J [START_REF] Hunger | Neo4j 2.0: Eine Graphdatenbank für alle. entwickler[END_REF]). It is an improvement for the approach proposed in [START_REF] Sun | Efficient subgraph matching on billion node graphs[END_REF]. Similarly, the query graph is decomposed into STwig data structures that will be matched individually using the vertex-centric approach, then, the matching results are joint to build the match result. This work discusses the possibility of simply processing the STwigs in parallel then joining them sequentially. Such optimization may require more memory to hold the intermediate results but will deĄnitely reduce the number of super-steps and hence the query processing time. So here, the main contribution was taking the query decomposition approach of [START_REF] Sun | Efficient subgraph matching on billion node graphs[END_REF] and transforming it into a vertex-centric one and thus, enabling the system to achieve better performance and gain in scalability.

PSgL [START_REF] Shao | Parallel subgraph listing in a large-scale graph[END_REF] evaluates subgraph isomorphism based on a parallel traversal of both the pattern graph Q and the data graph G to map vertices in Q with vertices in G. Each data vertex v is Ąrst mapped to a query vertex u (selected based on a cost function that minimizes the size of intermediate results). Then, in the next super-step, the mapping is expanded by mapping neighbors of u to the neighbors of v if the mapping satisĄes the matching constraints. In this step, u is colored black, its neighbors are gray, and the rest of the pattern is white. In the next super-step, this mapping (tree) is forwarded to the neighbors of v that can expand it further. A neighbor v ′ will expand a gray vertex (that becomes black), its white neighbors (not yet mapped) are now mapped to neighbors of v ′ . Every mapping is expanded in the same way until all the query vertices are mapped (it returns the subgraph) or there is no way to expand it, i.e. no remaining neighbors of v ′ . The authors propose heuristics that guide the tree forwarding among the data vertices. This approach that adopts a BSP-based vertex-centric paradigm was implemented on top of Giraph.

In [START_REF] Gao | Continuous pattern detection over billion-edge graph using distributed framework[END_REF], the authors use a Single Sink DAG extracted from an undirected pattern to guide the evaluation of subgraph isomorphism in a distributed data graph. The sink of the DAG is a query vertex that has no outgoing vertices, only incoming vertices. Every data vertex candidate to this sink will be responsible for collecting a subgraph match if it exists. Transition rules are attached to every edge in the DAG, then each data vertex considered a candidate to a non sink query vertex will generate and transfer the received messages that end at the sink data node. The data node accumulates the received messages to form a correct match or drop the messages if there are non respected subgraph isomorphism constraints. Furthermore, to support the detection of the same query on an evolving graph, any update event triggers a message broadcast received by the data vertices that will verify the transition rules and transfer these messages to their neighbors if the transition rules become unsatisĄed. The receiving nodes will do the same recursively until reaching the sink nodes that will update their matching information accordingly.

Asynchronous vertex-centric

Reza et al. [START_REF] Reza | Towards practical and robust labeled pattern matching in trillion-edge graphs[END_REF] proposed recently a distributed algorithm for evaluating subgraph isomorphism on one trillion-edge graphs based on HavoqGT, a platform for asynchronous vertex-centric graph processing [START_REF] Pearce | Highly asynchronous visitor queue graph toolkit[END_REF]. The algorithm is composed of two phases. Firstly, a Local Constraint Checking procedure eliminates aggressively the vertices that do not satisfy the subgraph isomorphism constraints, several iterations can be executed until no vertex is eliminated. Then, a Cycle Checking procedure is executed only for cyclic queries. The Ąrst phase can successfully eliminate all the data vertices that do not participate in answering the input query. But when the query graph contains cycles, there can still be remaining vertices that do not verify the whole matching constraints. The idea proposed by the authors consists of checking the existence of cycles based on some cyclic constraints introduced by the user to keep only matches respecting them in the data graph. If the algorithm Ąnds a cycle having a deĄned length d in the query graph then, each data vertex already matched to a member of this cycle will execute a token passing routine. This routine is used to verify if it is also part of a cycle with the same length in the data graph. The data vertex sends a token to its neighbors in a diameter of d such that if the data vertex does not get back its token at the end of d iterations, it will be eliminated because it is not part of any cycle. This approach showed good results for handling undirected graphs of more than one trillion edges.

PruneJuice [START_REF] Reza | Prunejuice: Pruning trillion-edge graphs to a precise pattern-matching solution[END_REF] uses graph pruning to evaluate subgraph isomorphism. The data graph is pruned based on a set of constraints extracted from the query graph so that every data vertex respecting these constraints will be part of a match. The embedding enumeration can then be performed on the resulting pruned graph having the smallest size possible. These constraints are divided into local constraints such as the vertex label and the neighbor labels and that will be veriĄed by exchanging direct messages between the data vertices. Non-local constraints require walks within the data graph such as path search, cycle checking when a query label is repeated in the pattern or a query edge is part of a cycle respectively. Both types of constraints require a token passing to verify the cycle membership and to verify that two data vertices having the same label have a speciĄc labeled path . Another type of non-local constraints that ensure that the pruned graph contains exactly all the subgraph isomorphism matches is the Template-Driven Search (TDS). The TDS prunes further the data graph by walking through the pruned graph and checking for the union of cycle constraints and the union of repeated label constraints and eliminating every data vertex not satisfying them.

Furthermore, Reza et al. [START_REF] Reza | Approximate pattern matching in massive graphs with precision and recall guarantees[END_REF] use k edit-distance to Ąnd approximate matches. Here, a k edit-distance is the subgraphs of the data graph that become isomorphic to the input query upon the deletion of up to k edges from the query. The authors have already deĄned in [START_REF] Reza | Prunejuice: Pruning trillion-edge graphs to a precise pattern-matching solution[END_REF] a set of local and non-local constraints that help pruning the data graph to keep only exact matches and thus enumerate subgraph isomorphism embeddings. In this contribution, they deĄne a set of prototypes from the query graph (variations of the query graph within distance k) and then, they use the common local and non-local constraints to avoid reevaluating subgraph isomorphism for every single prototype separately. A data vertex that satisĄes a non-local constraint for k = δ + 1, will also satisfy this constraint for k = δ. So, every time a data vertex meets speciĄc non-local constraint x, this information is saved in the context of that vertex so that it can be reused in the constraints veriĄcation for prototypes of smaller k.

In [START_REF] Stein | Scaling topology pattern matching: A distributed approach[END_REF], a vertex-centric approach was presented for performing topology pattern matching (subgraph isomorphism) in a distributed environment composed of a Wireless Sensor Network (WSN). Each sensor in this WSN is analogous to a data vertex having a partial view of its closest neighbors in the network topology. Different from the previous works, this proposition aims to reduce the disk storage and message overhead in a resourcelimited context. There is an initiator node v 0 that starts the matching process and builds a partial match set if possible. Then, it will ask its neighbors to further extend the partial match set with their local views of the graph. When a node receives a request from its neighbor to complete the match set, if it Ąnds a complete match set, it will send back the result to v 0 . Otherwise, it will propagate its partial answer to other nodes in the data graph. The authors conĄrmed that such approach can also be used in contexts other than a WSN. However, the solution was only tested on 400 nodes.

Distributed relaxed graph pattern matching

Since the recent works on graph pattern matching are mostly oriented toward reaching higher performance and scaling up the existing algorithms into larger graphs, we will focus on distributed relaxed GPM. Graph simulation along with its induced models gave an evidence of superiority over its conventional counterpart, and this is due to relaxing the structural constraints imposed by subgraph isomorphism. The works discussed here are divided into four categories. First, we have the master-slave execution model with both synchronous and asynchronous timing. Then, we have BSP-based approaches adopting a vertex-centric or subgraph-centric abstraction.

Synchronous master-slave

We review under this section a work that distributes processing following a master-slave model where the workers communicate only with the master.

Graph simulation: Similar to the work presented in [START_REF] Fan | Distributed graph simulation: Impossibility and possibility[END_REF], graph simulation is evaluated on top of GRAPE [START_REF] Fan | Parallelizing sequential graph computations[END_REF] by incrementally updating the match set of a query vertex u in each fragment F i . Then, the matching information of a vertex v in F i is needed by their original fragments to complete their matching. So, at the end of partial evaluation (PEval), each processor sends a variable X(u, v), with true or false value to indicate whether u ∈ Q is matched to v ∈ G or not, to the coordinator. The coordinator will then propagate these variables into the processors that need to complete their matching information. Upon the reception of these variables (in IncEval), each processor will verify the matching constraints and update its local variables accordingly. If a variable X(u, v) switches to false, it will propagate this update by sending a message to the coordinator, which in turn propagates the change to the appropriate processors until there is no update issued. Finally, the coordinator will execute the assemble function which is the union of partial matches generated by each processor.

Asynchronous master-slave

We present under this section the recent works adopting an asynchronous programming model where the evaluation of the query is triggered on a master and then executed on the different worker machines.

Graph simulation:

The Ąrst work ever to address graph simulation in a distributed environment was published in 2012 [START_REF] Ma | Distributed graph pattern matching[END_REF]. The authors adopted a message-passing approach for solving graph simulation in the context of big graphs. Their solution is based on the following Ąndings: they proved that evaluating separately the connected components (CCs) of a data graph allows us to Ąnd a correct matching set by just computing the union of different partial matches found for each CC. First, each worker receives the query graph and Ąnds candidate vertices for each query vertex in parallel with other workers. After this Ąltering step, the graph will contain a set of connected components, some of which reside on the same worker while others are distributed over multiple machines. Each worker executes locally the algorithm localHHK (an updated version of HHK algorithm [START_REF] Henzinger | Computing simulations on Ąnite and inĄnite graphs[END_REF]) on the CCs that reside fully on it. Then, it sends back its partial matching set to a coordinator machine, along with the information about vertices in a CC across several machines. The coordinator executes a scheduling algorithm to assign the remaining CCs to a set of workers while minimizing make-span and data shipment at the same time. The assignment is then sent back to these workers that will ship the CCs to their corresponding workers. The assigned workers will perform local graph simulation on the received CCs and send back their results to the coordinator. At the end, a set of partial matches for each connected component will be available on the coordinator that builds a Ąnal matching set from their union. It is important to mention that the proposed solution lies much more on distributing the data while executing the same algorithms in parallel (data-parallel approach) rather than on the notion of distributed processing.

In [START_REF] Fan | Distributed graph simulation: Impossibility and possibility[END_REF], Fan et al. proposed a distributed algorithm for solving GPM via graph simulation with bounded response time and data shipment. Each worker maintains locally a dependency graph for tracking linked vertices that are situated on other workers. To perform local graph simulation correctly, the boundary nodes and crossing edges are duplicated on both the source and destination machine and treated separately. Here, instead of shipping parts of the data graph from one site to another, a Boolean variable

X (v,u
) is used to indicate whether the data vertex v is a match to the query vertex u or not. If the two vertices v and u share the same label, then there must be at least one matching relation between the child node u i of u and a child node v i of v to add this tuple to the match set. This constraint is formulated as follows:

X (v,u) = ∨(∧X (v i ,u i ) ).
To evaluate graph simulation, the algorithm simply propagates the values of these variables inside each worker such that each variable will be written in function of only the variables that relate to virtual nodes (nodes copied from other fragments) in this machine. Then, a message passing is conducted where each machine broadcasts the values of its in-node variables (nodes considered as virtual-nodes in other fragments) following the dependency graph. After receiving new values of variables related to its virtual-nodes, each machine propagates this information among its local variables. Next, it updates them and conduct a new message passing phase if one or more of its in-node variables were updated. The algorithm converges when no more messages are exchanged. Adopting asynchronous communication made it possible for this system to achieve better response time compared to the solutions proposed in [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF].

Strong simulation: In an earlier paper [START_REF] Ma | Capturing topology in graph pattern matching[END_REF], the outlines of a distributed algorithm were given for computing strong simulation. It was the Ąrst algorithm proposed in this category but with no performance guarantees. The algorithm simply ships the contents of each data locality ball that is stored across different machines to the machine with the smallest index, then it evaluates strong simulation locally. After this step, the workers send their partial results to a coordinator machine that merges them into a Ąnal match set.

In [START_REF] Wang | Parallel algorithms for Ćexible pattern matching on big graphs[END_REF], the process of Ąnding matches of a pattern graph is split into two phases: An off-line redistribution phase is conducted to make the data graph locally determinable, then an on-line evaluation phase is held for evaluating strong simulation. The main challenge brought by strong simulation in the distributed setting is the data shipment incurred. Indeed, we need to ship data vertices from different machines for each locality ball created. Thus, the larger the query graph, the larger its diameter d q and the larger the locality balls. As a reĆection, for reducing the size of these balls and hence the amount of data shipped, we can think of reducing the diameter of query graphs. The idea on which this paper is based is to set a maximal query diameter d q , and use it to further optimize data shipment by redistributing the data graph offline. The redistribution is made such that all the balls centered at v ∈ V will reside on the same machine.

An online processing algorithm is conducted at the reception of every query graph Q. The online phase consists of partitioning the query graph into partition-trees (a tree rooted at each query vertex and having as diameter d q ) locally on each worker. Then, p-match-graph is computed for every partition-tree, knowing that p-match here is a revision of graph simulation allowing to Ąnd partial results of a query graph locally when using its partition-trees as input. Then the local p-match-graph obtained is sent to a coordinator. This latter merges the local p-match-graphs received into one Ąnal p-match-graph, then conducts strong simulation locally to Ąnd a Ąnal answer to the query. Even though this algorithm achieved controllable data shipment in the online phase, it is not well adapted for highly dynamic graphs. (a redistribution phase has to be executed after each update event). Also, this proposal puts too much effort into reducing the data shipment at the expense of response time, another drawback is that no data shipment was involved between different workers but the algorithm still uses network traffic between workers and master (which may lead to a load-balance problem). Such proposition does not take advantage of the distributed systems and their optimizations.

Synchronous vertex-centric

We Ąnd several works adopting this programming model to evaluate graph simulation, strong simulation, strict simulation or tight simulation. All the studied works adopt a BSP-based vertex-centric abstraction.

Graph simulation:

We review here three different algorithms of graph simulation and dual simulation since the latter is a simple extension of the Ąrst.

In [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF], the Ąrst algorithm to adopt a BSP-based vertex-centric approach to evaluate graph simulation was proposed. Each vertex in the data graph has a local context composed of two variables: a match Ćag and a match set. Upon receipt of the query graph, it sets its matching Ćag to true if its label is the same as one of the query verticesŠ, and the match set will contain identiĄers of the similar query vertices. Then, if the match Ćag is true, it will also ask its children for their match sets. In the second super-step, vertices that receive a request while their match Ćags are true will respond with their match sets. In a third round, each vertex receiving information from its children will update its match Ćag and match set according to the received match sets and the query graph, it will then inform its parents of any update made. In the fourth round and beyond, each vertex that receives an updated match set will update its match Ćag and match set accordingly and inform its parents. This algorithm stops when all the vertices stop sending messages, it takes at minimum 4 super-steps to evaluate graph simulation. The same goes for dual simulation when each vertex will ask for information about its children and parents. Similarly, In the following super-steps, when a match set is updated, the vertex will inform its children and parents about the updates made.

In [START_REF] Schätzle | S2x: Graph-parallel querying of rdf with graphx[END_REF], S2X was proposed for evaluating dual simulation on RDF data, on top of GraphX. Spark allows for data-parallelism thanks to its Resilient Distributed Datasets (RDDs) that apply an efficient partitioning strategy permitting to minimize the cut-edges between worker machines. Moreover, graph-parallel computation is made possible with its vertex-centric programming model called GraphX. The query graph consisting of a set of triplets (edges) is broadcast to every data vertex that will verify dual simulation constraints locally. Then, it will exchange its partial match sets with its neighbors to further validate the matching sets built in the Ąrst super-step. At the end and after receiving the partial results obtained by each data vertex, a joining phase is executed to construct the Ąnal answer. If we compare the contribution made by this paper with the algorithms in [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF], here the authors addressed RDF graphs that are characterized by labeled edges and that may have multiple edges between two nodes.

Another recent work proposed two vertex-centric algorithms to evaluate graph simulation for acyclic queries and cyclic queries separately [START_REF] Li | A vertex-centric graph simulation algorithm for large graphs[END_REF]. The Ąrst algorithm uses a Boolean variable local to each data vertex which holds the matching information that can be either True, False or Unknown. The algorithm is executed in three different stages: Initialization, Message Broadcast and Match trial. In the Ąrst step, matching information for data vertices verifying the match constraints are set to true (the vertices candidates to a query vertex that has no children in the query graph), the remaining vertices set their values to unknown. Then, a message broadcasting step is carried out to propagate these truth values to parents. The vertices having their local matching variables set to True send their labels to their parents and go inactive. On the other side, vertices with unknown values will wait for messages from their children to complete their matching information. Once a data vertex with unknown value receives the labels from all its children, it will compare this label set with the label set needed for satisfying the graph simulation constraints. If the two sets are equal, then it sets its local variable to true and inform its parents. Otherwise, it will set it to false. But, if it does not receive all the matching information from its children, then it will wait for the next super-step. In this super-step, messages from the previous super-step will be delivered and data vertices that did not yet compute their matching value will evaluate it depending on the set of labels received from children. The algorithm proposed is not general since it sets another constraint on the query graph. Indeed, it does not allow repeated labels while it is almost impossible to Ąnd practical queries in real-world applications with a no repeated labels.

Relaxation simulation: Gao et al. [START_REF] Gao | Prs: parallel relaxation simulation for massive graphs[END_REF] proposed two BSP-Based vertex-centric algorithms to evaluate their models URS and DRS on distributed graphs. In URS, the authors deĄne the condition set of a query vertex u in Q as the set of labels that should be satisĄed if two vertices are matched together. It is composed of the set of labels of the children of u that can be substituted by its grand childrenŠs labels. The initial set is composed of the children of u, then new combinations are generated by replacing a child in the initial set with its children set. To evaluate an input query in a distributed way, the query is Ąrst broadcast to all the data vertices in the graph. Then, each node sets its match Ćag true if its label is equal to that of a query vertex. It propagates its label to its children and parents during the next two iterations. Then, in the third super-step, if its match Ćag is true, it computes its condition set and checks whether there is a satisĄed condition set among the labels of its children. If yes, it votes for halt, otherwise it sets its match value to false and informs its parents to update their matching information accordingly. The same goes for DRS, such that both grand-parents and grand-children may substitute the parents and children of a query vertex respectively in the condition set. In this case, a data vertex will compute both parent and child condition sets and exchange its matching information with its parents and children. Data vertices that do not Ąnd candidates satisfying the two condition sets will set their match value to false and inform their parents and children so they update their matching information accordingly. It is the only distributed approach found in literature that treats a model as interesting as URS and DRS. Nevertheless, the proposed algorithms only consider patterns with unique labels which is not always the case in real-word applications.

Strong simulation: In [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF], the authors proposed an algorithm that, Ąrstly, conducts dual simulation in a distributed manner. Secondly, each vertex having a match Ćag set to true will execute a BFS traversal to collect the contents of a ball, of which it is the center, with a radius equal to d q (diameter of the input query). It then evaluates dual simulation locally to each data vertex to get only matches falling inside these locality balls. This approach is not scalable as it showed poor performance guarantees when dealing with average data graphs. Its limit lies in the way data locality are generated, because if we try to duplicate the neighborhood of every single node that has a true match Ćag, up to d q hops, this will certainly create a bottleneck as the query graph gets larger. That is why the authors proposed a distributed algorithm for strict simulation which scales better as it uses only the dual match graph. The authors used the same approach to evaluate tight simulation in [START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF], i.e. the locality balls are collected by a subset of the dual match vertices.

Furthermore, G-thinker [START_REF] Yan | G-thinker: A distributed framework for mining subgraphs in a big graph[END_REF] can be used for evaluating strong simulation as the locality balls creation will not require the duplication of neighborhood data inside every single subgraph generated leading to an intermediate data graph of exponential size. Since strong simulation does not require communication between the subgraphs whose diameter is well deĄned, using G-thinker will allow it to scale to very large graphs.

Synchronous subgraph-centric

Generally, when we use the vertex-centric model, it becomes difficult for the system to achieve an optimal make-span since vertices do not know whether their neighbors reside on the same worker or not. Consequently, even the use of information from vertices on the same machine needs to be delayed to the next super-step. This generally leads to a greater response time. Thus, approaches that focus on the multi-hop neighborhood of a data vertex, i.e. subgraph-centric approaches, can be well adapted for distributed GPM.

Graph simulation:

In [START_REF] Kao | Distributed Incremental Pattern Matching on Streaming Graphs[END_REF], the authors focused on the big data velocity issue, i.e. streaming graphs by adopting a BSP-based subgraph-centric approach on top of GPS. The data graph is partitioned into several subgraphs that are mapped to the GPS vertices.

The proposed incremental algorithm evaluates graph simulation in a vertex-centric fashion (an improvement to the proposition in [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF]). Each data vertex is analogous to a BSP process and uses two local variables; a match Ćag and a match set. They take into account different kinds of events that come in to update the data graph, e.g. vertex addition/removal, edge addition/removal and attribute addition/removal. To evaluate the same query while having a graph updated every couple of seconds for example, the algorithm maintains the previous matching information instead of resetting the variables and starting from nothing. The update event will trigger a new iteration of graph simulation. The vertices concerned will update their match Ćags and match sets accordingly, inform their children that will conduct the basic updating process, and so on. In streaming graphs, the data graph is updated quite often with the reception of new events in a continuous way. Here, the main improvement brought was to avoid computing the maximum perfect match from zero for the same query graph whenever the data graph is modiĄed. Also, the use of subgraph-centric programming model reduced the amounts of network traffic signiĄcantly.

Several other incremental algorithms were already proposed, but they do not deal with the problem at high scale (no distributed algorithms were found except this work). Fan et al. proposed in [START_REF] Fan | Incremental graph pattern matching[END_REF] three algorithms for incrementally evaluating graph matching via graph simulation, bounded simulation and subgraph isomorphism. A recent work addressing the same problem was done in [START_REF] Zhang | Incremental Graph Pattern Matching Algorithm for Big Graph Data[END_REF] where the authors proposed incremental algorithms for performing dual simulation when no more than half of the data graph edges are updated.

ClassiĄcation of distributed GPM approaches

Table 2.1 summarizes the presented GPM approaches, where every work is cited with the programming paradigm adopted and the GPM model applied. We also give the size of the largest graph tested within each work. The different approaches were not tested in the same context. In addition to the size of graphs, there is also the nature of graphs that differs from one experimentation to another; e.g. the density of the data graph, number of the cycles appearing in it, and the number of present labels. Moreover, these different works use very different system conĄgurations as the number of CPU cores varied from tens to thousands of cores. We cannot compare the response times since the size and nature of patterns used in the experiments change from one to another work. We give such details only to show how far the authors went in their experimentation to validate their approaches. The largest graph that has been tested contains 137 billion vertices of synthetic data. It is common to reach such size in the current big graphs issued from social networks, the World Wide Web and many other applications.

Some of the conclusions drawn out of this comparative study are as follows. First, graph simulation is a promising model that aims to address the challenges of actual GPM applications like network motif discovery, Ąnding communities in social networks, and many other applications. That is why it is important to consider this research area as one of the main current challenges of subgraph matching on big graphs. Second, strong simulation is a challenging model that should be considered in future work. The way its algorithm was distributed is not efficient and needs to be revised. Although, Ref. [START_REF] Wang | Parallel algorithms for Ćexible pattern matching on big graphs[END_REF] provided a new distributed algorithm for strong simulation, it does not beneĄt from the aforementioned programming paradigms. Furthermore, redistributing the data graph after every single update of its contents would arise a performance bottleneck when dealing with highly dynamic graphs. Finally, even though relaxed graph pattern matching is highly common among the recent works addressing GPM for social networks, subgraph isomorphism approaches are also present and they showed high performance guarantees when tested on massive graphs.

In Figure 2.8, we provide a taxonomy for the distributed algorithms we discussed earlier.

Our classiĄcation is based on three selection criteria: the programming paradigm used, [103] Inexact SubIso Async. Vertex-centric 34B nodes [START_REF] Ma | Capturing topology in graph pattern matching[END_REF] Strong sim. Async. Master-slave 548K nodes [START_REF] Ma | Distributed graph pattern matching[END_REF] Graph sim. Async. Master-slave 875K nodes [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF] Graph sim. BSP Vertex-centric 3M nodes Dual sim. Strong sim. Strict sim. [START_REF] Fan | Distributed graph simulation: Impossibility and possibility[END_REF] Graph sim. Async. Master-slave 3M nodes [START_REF] Fard | Distributed and Scalable Graph Pattern Matching: Models and Algorithms[END_REF] Tight sim. BSP Vertex-centric 5M nodes [START_REF] Gao | Prs: parallel relaxation simulation for massive graphs[END_REF] Relaxation sim. BSP Vertex-centric 1M nodes [START_REF] Schätzle | S2x: Graph-parallel querying of rdf with graphx[END_REF] Dual sim. BSP Vertex-centric 10M nodes [START_REF] Kao | Distributed Incremental Pattern Matching on Streaming Graphs[END_REF] Graph sim. BSP Subgraph-centric 9.5 M nodes [START_REF] Wang | Parallel algorithms for Ćexible pattern matching on big graphs[END_REF] Strong sim.

Async. Master-slave 1M nodes [START_REF] Li | A vertex-centric graph simulation algorithm for large graphs[END_REF] Graph sim. BSP Vertex-centric 403K nodes the pattern matching model evaluated and whether the algorithm proposed is synchronous or asynchronous.

Based on this comparative study, we notice that both synchronous and asynchronous approaches were employed with more works adopting the BSP model. The master-slave paradigm is the oldest one used in distributed graph processing. The vertex-centric approaches form the largest part of these works, and Ąnally subgraph-centric is the least frequent paradigm with only one work addressing graph simulation. Even though Ref. [START_REF] Yan | G-thinker: A distributed framework for mining subgraphs in a big graph[END_REF] proposed an asynchronous subgraph-centric algorithm to evaluate subgraph isomorphism on G-thinker, they did not give the algorithmic details of their approach. The edge-centric paradigm was not adopted in distributed GPM. GpSM [START_REF] Tran | Fast subgraph matching on large graphs using graphics processors[END_REF] can be implemented in an edge-centric way. Similarly, this paradigm can be applied to implement graph simulation that maps edges of the two graphs. Furthermore, the edge-centric paradigm naturally supports dynamic graphs as events occur on the graph edges and need to be processed at the edge level. Therefore, it is interesting to explore this area of research by proposing edge-centric GPM approaches. Besides, we note that the synchronous algorithms can be easily designed and they are better understood compared to the asynchronous ones. A synchronous algorithm endures less communication costs.

However, an asynchronous one allows a considerable improvement in the response time.

Actually, the computing units (vertices, edges or even subgraphs) do not have to wait the termination of another process to send and receive requests or data to and from their neighbors.

The taxonomy provided categorizes only the existing distributed GPM approaches, some combinations were not employed and that is why we do not see them in this taxonomy.

An open question would be: Why do all combinations not appear in the literature of distributed GPM? One reason could be that the vertex-centric paradigm, which is the most common one, has been widely studied in the Ąeld of networks where machines behave naturally in a vertex-centric way. Moreover, as we stated earlier, the most intuitive way to evaluate subgraph matching is by a subgraph-centric algorithm since the neighborhood of a data vertex is needed to decide whether it is a match or not. This could be a reason that makes the subgraph-centric paradigm more interesting compared to the vertex-centric one. However, subgraph-centric computing needs an additional level of abstraction to make the neighbourhood of multiple hops available locally to every single node in the graph. Such an abstraction layer is responsible for shipping data from one node to its neighbors whenever a local update is made, which may cause additional data shipment increasing the overall response time. Apart from the subgraph mining systems proposed such as Arabesque, Rstream or G-thinker, few works adopt this model even though adding an abstraction layer would certainly reduce the efforts for designing graph algorithms.

Chapter summary

This chapter presented recent advances in graph processing systems for big graphs. We discussed several programming models that are currently used in designing graph algorithms for the context of distributed graphs. However, less work has been done to take advantage of such paradigms in evaluating graph pattern matching at a high scale. Subgraph-centric programming models are recommended for this kind of problem together with asynchronous timing. Noticeably, studies were recently focused on graph simulation due to its quadratic-time complexity. Furthermore, the recent research works are either addressing the velocity of data generation or the size of data graphs, seeking to reduce the time and space complexity of previously proposed algorithms. However, it is rare to Ąnd both issues handled in the same work.

Moreover, we identiĄed categories of distributed GPM approaches and classiĄed them based on multiple criteria. We gave more attention to the relaxed pattern matching since it is widely used in the current applications of social networks and massive graphs in general. An abundant literature exists discussing subgraph isomorphism queries, but the limitations of this model make it impractical for current applications of graph pattern matching. Hence, beneĄting from subgraph isomorphism techniques to build an enhanced approach for strong simulation is one of the current challenges in this domain, especially in the distributed and parallel contexts. That is to say, we can combine the inherent Ćexibility of the model itself and exploit the strong background behind subgraph isomorphism to achieve better results.

In the second part of this thesis, we address this research direction by proposing an alternative to strong simulation with scalability guarantees. Furthermore, motivated by the shortcomings of the approaches discussed in this chapter, we design scalable distributed algorithms to evaluate strong simulation, graph simulation and dual simulation.

Part II

Parallel and Distributed Algorithms for Relaxed GPM Chapter 3

Distributed Graph Pattern Matching via Bounded Dual Simulation

Introduction

Even though graph simulation is considered to be the Ąrst model that can be evaluated in quadratic time, its weak part is that it does not capture the complete topological structure of the pattern graph. Indeed, we often end up with answers having a structure different from the input query. This is why dual simulation was proposed, allowing to capture more topological structures via the duality property. The difference between the two models is that graph simulation requires the matching constraints to be satisĄed only for the children of the data vertex, while dual simulation brings duality by requiring those constraints to be satisĄed for both the children and parents. Such speciĄcation captures better the topology of the query; undirected cycles are preserved and connected graphs are matched only to connected graphs. However, it is true that dual simulation improves the quality of the results returned by graph simulation, yet, this model may result in answers of much larger size, because cycles in the query graph can be translated into cycles of unbounded length in the resulting match graph. This limitation motivated the appearance of strong simulation, another model that captures the structure in graph simulation while maintaining a low complexity, hence giving a compromise between Ćexibility and tractability. Strong simulation is deĄned as graph simulation reinforced by duality and locality. The locality property limits the accepted answers to only subgraphs falling within a Ąxed diameter. Thus, cycles that are longer than the queryŠs diameter are Ąltered out to keep answers of reasonable size. Although prior works addressed strong simulation for large graphs, they did not give any scalability guarantees when the size of data graphs increases reaching at least millions of vertices.

In this chapter, we propose Bounded Dual Simulation (BDSim) to answer relaxed GPM queries on massive graphs. BDSim is an extension to dual simulation that allows not only to capture duality and locality of the pattern graph, but it also preserves its cyclic structure. As opposed to strong simulation that duplicates data graph vertices in an exponential way when creating data locality balls, BDSim extends dual simulation by eliminating cycles that have unbounded length from the match graph, hence allowing to capture the locality and obtain results of reasonable size that are semantically correct.

The contributions made by this work are improving the response time because no data locality balls are created. The number and size of messages communicated are also reduced (tokens are exchanged instead of the whole vertex matching information). BDSim scales well with the size of the data graph and can handle massive graphs. Finally, our approach is adaptive because it uses a conĄgurable parameter k for limiting the size of cycles in the resulting match graph, thus allowing more Ćexibility based on the input query and application domain, which ensures avoiding the problem of zero answers.

The remainder of this chapter is organized as follows. Section 3.2 introduces the new GPM model BDSim, whereas distributed vertex-centric algorithms for evaluating BDSim on massive graphs are presented in Section 3.3. Section 3.4 provides a formal validation of the proposed algorithms, and Section 3.5 is dedicated for their experimental evaluation on synthetic and real-world datasets.

Bounded Dual Simulation (BDSim)

When addressing the problem of subgraph matching, the cyclic structure of the query graph is an important property that captures the locality between query vertices. However, dual simulation preserves only the child and parent relationships, which results into a model that maps cycles in the query to cycles of unbounded length in the resulting match graph. Actually, a cycle in the query graph can be translated to cycles having a multiple length in the match graph. As a result, we end up having answers of large size that do not necessarily resemble the input query.

Preserving the cyclic structure of the query and hence its locality is an important task in GPM, because it allows to reduce further the size of returned answers, and to improve their quality. Based on this observation, we notice that eliminating such unbounded cycles reĄnes further the returned match graph compared to dual simulation and captures better the topology of the query.

To address this challenge, we introduce BDSim, an adaptive relaxed GPM model that lies between dual simulation and strong simulation. A cycle in the Ąnal match graph is said to be bounded (or length-bounded) if its length is k times the length of the cycle to which it is matched in the query, such that k is a Ąxed parameter. By introducing BDSim, we aim to limit the size of cycles in the Ąnal match graph by checking if a data vertex is in a cycle of bounded length or not, and this can be achieved by tracking all the cycles of the query graph. Nevertheless, we will see that the set of short cycles is enough to capture the closeness and proximity between the query vertices.

DeĄnition 17 (Short cycle).

Given an unweighted graph G = (V, E, f ) and two vertices v and v ′ such that e = (v, v ′ ) ∈ E. We call a short cycle, if it exists, a cycle composed of the edge e and an undirected shortest path between v and v ′ in

G ′ = (V, E \ ¶e♢, f ).
Note that, we deĄne an undirected shortest path in a directed graph as a shortest path in the underlying undirected graph, i.e. when we ignore edge directions. We deĄne an undirected cycle in a directed graph as a cycle in the underlying undirected graph, i.e. we ignore edge directions. Unless expressly stated otherwise, we shortly use cycle to refer to an undirected cycle. Furthermore, we omit the repeated vertex of a cycle when giving its elements for simplicity purposes. In a graph, a long cycle is a cycle that is not short.

Dual simulation is a Ćexible model by deĄnition, it allows mapping an edge in query graph Q to one or more edges in the dual match graph G D . In addition to that, two query edges can be mapped to the same edge in G D . Consequently, given a cycle c ∈ Q and one of its matched cycles c ′ ∈ G D , c ′ may have the same length as c, be longer or even shorter, i.e.

♣c ′ ♣ = r × ♣c♣ where r ∈ Q * + , with ♣c ′ ♣ ≥ 2.
An example illustrating such different possibilities is given in Figure 3.1.

Lemma 1. Given a query graph Q, a cycle in Q is either a short cycle or a cycle composed of edges from other short cycles.

Proof. By deĄnition, a short cycle is a cycle for which, the incident vertices of at least one edge have their shortest path in this cycle (when excluding the corresponding edge in computing the shortest path). Consequently, a long cycle c l is a cycle where all the shortest paths between the incident vertices of any considered edge are not entirely in c l , and we refer to such paths as bridges. These bridges decompose c l into adjacent cycles that are all short. Actually, an edge e ∈ c l that has its shortest path p outside c l results into a new cycle c = e ∪ p. c is effectively a short cycle from the deĄnition of short cycles. The same thing applies for all the other edges in c l . Therefore, all the edges in c l belong to at least one short cycle; i.e. c l Ůwhich is a long cycleŮis composed of edges from the short cycles of Q.

Example 3. In the graph of Figure 3.2, the cycle c 1 = ¶1, 2, 3, 4, 5, 1♢ is composed of Ąve edges whose shortest paths do not belong to c 1 . Actually, the edge (1, 2) has the shortest path ¶2, 4, 1♢ that forms the short cycle ¶1, 2, 4, 1♢. Similarly, the remaining edges (2, 3), (4, 3), (4, 5) and (1, 5) result in the short cycles ¶2, 3, 4, 2♢, ¶4, 3, 2, 4♢, ¶4, 5, 1, 4♢ and ¶1, 5, 4, 1♢, respectively. Indeed, enumerating all the simple cycles in the graph returns exactly 21 cycles, whereas the set of short cycles contains only 5 cycles. When using these short cycles to bound the size of a match graph, we reduce the number of tracked cycles by a fourth while still giving the same result. As a result, we minimize the number of computations signiĄcantly and reduce the overall evaluation time of BDSim.

Lemma 2. Given a query graph Q and a data graph G. Let G D be the dual match graph of Q in G. If the matches of the short cycles of Q are length-bounded in G D , then all the matched cycles in G D will also be length-bounded.

Proof. We know that every cycle in Q is matched to a cycle in G D (from the deĄnition of dual simulation). First, we assume that all the short cycles in Q have bounded matches in G D . Then, we suppose that there exists a cycle c in Q having a match of an unbounded length in G D . First, if c is a short cycle, then all its matches are bounded by supposition. Second, if c is long, then it is composed of edges from other short cycles (See Lemma 1). Besides, its matches are composed of the matches of these short cycles. Hence, it must be bounded because all the short cycles are already bounded, and the composition of a set of bounded cycles cannot be unbounded.

Theorem 1. In the dual match graph G D of query graph Q in data graph G, using only the set of short cycles of Q is sufficient to bound the length of the matches of all the cycles of Q in G D .

Proof. The proof of this theorem is directly derived from Lemma 1 and Lemma 2. From Lemma 1, every cycle in Q is either a short cycle or composed of other short cycles.

According to Lemma 2, bounding the length of the matches of the short cycles of Q in G D results into bounding the matches of all the cycles in Q.

BDSim extends dual simulation with a cycle constraint, such that a data vertex matched with query vertices in a short cycle c i of Q must be a member of a matched cycle that have the maximum length k × l i in the match graph, where l i is the length of c i and k ∈ N * . Moreover, BDSim is adaptive thanks to the parameter k that allows for more Ćexibility. Actually, we may have a context where it is required to keep only cycles of the same length, while in other cases, the allowed length would be equal to twice the initial cycle length or even more. Hence, k is deĄned depending on the semantics of the data graph and application domain.

The example below explains how BDSim works and demonstrates its adaptability based on the application needs.

Data vertex in G

D A 1 A 2 A 3 C 1 C 2 C 3 C 4 D 1 D 2 D 3 D 4 Length of 1 st matched cycle in G D 6 6 3 6 6 3 3 6 6 3 3 Length of 2 nd matched cycle in G D 3 3 / / / / 3 / / 3 / Vertex satisĄes BDSim for k = 2? ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓ Vertex satisĄes BDSim for k = 1? ✓ ✓ ✓ X X ✓ ✓ X X ✓ ✓
Varying the value of parameter k while answering the same query allows for more Ćexibility, especially to deal with the problem of zero answers when k is initially set to 1.

A formal deĄnition of BDSim is given below.

DeĄnition 18 (BDSim). Let G = (V, E, f ) be a data graph, Q = (V q , E q , f q ) a query graph, ζ the set of short cycles related to every single edge in Q and k ∈ N * a Ąxed parameter. G matches Q via BDSim, if there exists a maximum match relation R ⊆ V q × V and a subgraph G R of G, such that:

(1) G matches Q via dual simulation with maximum match relation R,

(2) G R is the match graph w.r.t. R,

(3) ∀(u, v) ∈ R, if u ∈ c i and c i ∈ ζ, then ∃c ′ i , a cycle in G R that matches c i and veriĄes: (a) v ∈ c ′ i , (b) c ′ i has a maximal length (k × l i ) in G R
where l i is the length of c i . Indeed, BDSim aims to keep only matches that preserve locality. If a data vertex v is a match to a query vertex u ((u, v) ∈ R) and u ∈ c i such that c i ∈ ζ, this mapping is kept only if v belongs to a cycle c ′ i that matches c i and has a bounded length in the match graph.

Propositions 1 and 2 give the relationships that BDSim has with dual simulation and subgraph isomorphism, respectively.

Proposition 1. If a data graph matches a query graph via BDSim, then it also matches the same query graph via dual simulation.

Proof. By deĄnition, BDSim is a restriction of dual simulation, i.e. every data vertex that matches a query vertex via BDSim must match that vertex w.r.t. dual simulation. Hence, the proposition above is correct.

Proposition 2. If a data graph matches a query graph via subgraph isomorphism, then it also matches this query w.r.t. BDSim.

Proof. First, a data graph that matches a query graph via subgraph isomorphism matches the same query via dual simulation (Proposition 1 in [START_REF] Ma | Capturing topology in graph pattern matching[END_REF]). Moreover, DeĄnition 18 states that a data vertex matches a query vertex w.r.t. BDSim, if it satisĄes at least dual simulation constraints. Thus, this data graph already satisĄes the Ąrst two constraints of BDSim.

Next, we prove that subgraph isomorphism already satisĄes constraint 3 of BDSim. Let G I = (V I , E I , f ) be a match graph of G for Q w.r.t. subgraph isomorphism and R ⊆ V q × V I is the corresponding bijective match relation. According to Theorem 3 in [START_REF] Ma | Capturing topology in graph pattern matching[END_REF], given a cycle c i = u 1 , u 2 , . . . , u l in ζ, c i must be matched to a cycle c ′ j = v 1 , v 2 , . . . , v l in G I where every single vertex u in c i is mapped to exactly one vertex v in c j . Formally, ∀m ∈ ¶1, . . . , l♢, (u m , v m ) ∈ R. Constraint 3 in DeĄnition 18 of BDSim intends to eliminate the data vertices v ∈ V I where (u, v) ∈ R and u ∈ c i in ζ, such that v belongs only to cycles of unbounded length. However, subgraph isomorphism does not allow these cases by deĄnition, hence, G I already satisĄes this constraint. Therefore, a data graph that matches a query graph via subgraph isomorphism necessarily matches the same query graph via BDSim. Figure 3.4 illustrates the inclusion relationships between BDSim and the other GPM models. BDSim adaptability, ensured by the parameter k, allows it to be as Ćexible as dual simulation or as strict as subgraph isomorphism. The smaller the value of k, the closer we get to subgraph isomorphism and the larger it is, the closer we get to dual simulation. Graph simulation, on the other hand, is more Ćexible than dual simulation. We propose an approach composed of the following four phases to evaluate BDSim: (1) a preprocessing phase to extract the set of short cycles from the input query graph, (2) evaluation of dual simulation and extraction of the dual match graph, (3) detection of invalid matches (data vertices that are in cycles of unbounded length), and (4) elimination of these matches to get the Ąnal match graph. The next section is dedicated for presenting these phases one by one.

Distributed evaluation of BDSim

After extracting the set of short cycles from the input query graph using a sequential algorithm, we evaluate dual simulation and extract the dual match graph in a distributed way by adopting a TLAV paradigm and Pregel computation model. After that, we use a distributed token passing algorithm to detect invalid matches that do not satisfy the third constraint of DeĄnition 18. Finally, a distributed Ąltering phase allows to keep only the correct matches w.r.t. BDSim.

In what follows, we present in detail the four phases of BDSim along with the proposed algorithms.

Extracting short cycles from the query graph

We use a simple and yet efficient algorithm to compute the set of all the short cycles of the query graph in quadratic time. Given a query graph Q = (V q , E q ) and the set of its short cycles ζ. To compute ζ, we verify for every edge in E q , if it is part of a short cycle c i and then add c i to ζ.

For each edge (u, v) in E q , proceed as follows.

(1) Remove (u, v) from E q ,

(2) Check if u is still reachable from v,

(3) For every shortest path p i between v and u, let c i = p i ∪ (u, v) be a short cycle and add c i to ζ.

To test the reachability of u from v, we execute a BFS traversal from vertex v that returns the set of shortest paths between v and u if they exist. Since Q is an unweighted graph, such traversal runs in O(♣V q ♣ + ♣E q ♣ -1) [START_REF] Diestel | Graph theory[END_REF]. This routine will be executed for every edge in the graph. Hence, the time complexity for Ąnding

ζ is O(♣E q ♣ 2 ).
Next, we give the vertex-centric algorithms for evaluating dual simulation, the token passing procedure and Ąnal Ąltering to get BDSim match graph. The notations used by these algorithms are given in Table 3.2.

Vertex-centric algorithm for dual simulation

Algorithm VC-DSim depicts the steps of the vertex program used in evaluating dual simulation in a distributed vertex-centric way. The match set of a data vertex v is the set of query vertices it matches, whereas a matching constraint of a query vertex u in M includes its parents C p (u) and children

C c (u).
The local context of a data vertex v is composed of its local match set M , the match sets of its parents M p and its children M c . In addition to that, the matching constraints related to M are kept locally.

We introduce the notion of matching constraints that are used in the evaluation of dual simulation and BDSim. Indeed, instead of duplicating the whole query graph inside every data vertex during the execution of our distributed algorithm, we generate a set of constraints that are maintained locally by each data vertex. A data vertex keeps only the constraints related to the query vertices that match it, therefore reducing the size of replicated data.

DeĄnition 19 (Matching constraint).

Given a query graph Q(V q , E q , f q ), a candidate data vertex (a vertex that has a similar label) is said to be a match for the query vertex u ∈ V q if and only if it satisĄes the parent and child relationship constraints of dual simulation. Let C p : V q → 2 Vq (C c : V q → 2 Vq ) be the function that maps a query vertex u ∈ V q to its parent constraints C p (u) ⊆ V q (child constraints C c (u) ⊆ V q ), respectively. Each edge (u ′ , u) ∈ E q deĄnes a parent matching constraint u ′ for u. Similarly, every edge (u, u ′′ ) ∈ E q deĄnes a child matching constraint u ′′ for u. Consequently, C p (or C p ) maps a vertex with zero parents (or children) to an empty set of constraints, respectively.

The distributed algorithm starts by an initial broadcast message to all the vertices of G. The vertex program is then triggered by every vertex in G to start the evaluation of dual simulation. Then, two types of messages are exchanged between the data graph vertices: data messages D msg and removal messages R msg . When a data vertex v receives the initial message containing the query graph Q, it stores locally in M a copy of the query vertices that have the same label as v, along with the set of constraints for each query vertex (set of parents C p and children C c of each u ∈ M ) (Lines 1Ű6). After that, if M is not empty, v sends it with its identiĄer to its neighbors (Lines 7Ű9). Otherwise, M is empty, v goes inactive (Lines 10Ű11).

In the next super-step, at the reception of these local match sets by neighbors, every data vertex stores the parents and children match sets in separate variables M p and M c , respectively (Lines 12Ű13). Then, it invokes Procedure EvalDSim (Line 14) to verify the matching constrains in C p and C c using both match sets M p and M c , respectively. Invalid matches are removed from M and added to R (a temporary variable that stores the removed matches in the form of pairs (v, u)). It also removes these query vertices from C p and C c as they will not serve in evaluating the matching constraints anymore. The same routine is repeated until no new changes are made in M . If R is not empty, v sends a removal message with R to all its neighbors, then it goes inactive (Lines 15Ű18).

In Super-step 3 and upon the reception of a removal message R msg , v removes the mappings in R msg from M p and M c (Lines 19Ű20). Afterwards, it reevaluates the matching constraints again, removes invalid matches from M , adds them to R and updates C p and C c (call of Procedure EvalDSim in Line 21). The set of removed matches is then shared with direct neighbors if it is not empty (Lines 22Ű25). The same process will be repeated in the next super-steps until the algorithm converges.

At the end of this algorithm, every data vertex will have its local match set w.r.t. dual simulation. If every single query vertex has at least one match, then, the union of these local matches is exactly the global match set w.r.t. dual simulation. Otherwise, we return an empty match set. Now, to extract the dual match graph, we Ąlter out vertices having an empty match set and also the edges that does not represent a match.

Example 5. To illustrate the execution steps of Algorithm VC-DSim, we use the query graph Q 3 of Figure 3.3a and the data graph G 3 of Figure 3.3b. At the end of the Ąrst super-step, only data vertex E 1 will have an empty match set, whereas all the remaining vertices share their non empty matches to their direct neighbors. In the second iteration, all the data vertices with a non-empty match set reevaluate dual simulation constraints. However, since all the vertices except E 1 satisfy already dual simulation, no removal

Vertex-centric algorithm for detecting invalid matches

In this section, we propose the distributed vertex-centric algorithm VC-TPass that ensures the detection (and then removal) of cycles of unbounded length from the dual match graph G D , i.e. not satisfying the closeness property represented by the third constraint in the deĄnition of BDSim. Algorithm VC-TPass handles the following cases: (i) multiple query vertices with the same label, (ii) multiple short cycles in the query graph, (iii) the same vertex being part of more than one short cycle and (iv) data vertices that are matched to different query vertices within the same short cycle.

Every data vertex in G D that is matched to a query vertex in c i ∈ ζ veriĄes its membership to a similar, yet bounded cycle in G D . It initiates a token with its identiĄer and forwards it to its neighbors based on some predeĄned conditions. Then, every vertex that receives such token will decrement its expiration value and forward it to potential next hops in the cycle. After k × l i steps of forwarding the tokens, if an initiator does not receive back its own token, this means that it does not belong to a bounded cycle that is matched to

c i in G D .
Hence, it should be Ąltered out in the next phase.

The main challenge during this phase is to generate a small number of messages while exploring the whole graph to detect unbounded cycles. Since the cycles are undirected, knowing to which neighbor a token should be forwarded can be tricky. Hence, we guide the token passing procedure with a set of seeds that are assigned to the query vertices of every short cycle. Such data structure ensures that tokens are only forwarded to eligible neighbors, i.e. vertices that are most likely to participate in this cycle detection phase. It also allows the data vertices to explore a given cycle in the same way. We deĄne the set of global seeds S g computed directly from ζ and a set of local seeds S l , a subset of S g that corresponds to only a given data vertex. The diagram given in Figure 3.5 illustrates the different steps of the token passing algorithm for BDSim. After computing the short cycles ζ and set of global seeds S g , they are broadcast to all the data vertices in G D . When a data vertex v receives the set of seeds, it checks for each seed s whether its matched query vertex s.m is a member of the local match set. If it is the case, v will store s locally (Lines 1Ű3). Then, it generates a token with an expiration value equal to k × l i , such that l i is the length of the short cycle c i of this seed. Finally, it sends the token only to eligible neighbors that might be part of a bounded cycle (Lines 4Ű11). An eligible neighbor is a data vertex matched to the next hop vertex following the direction of the seed (a parent if the direction is IN and a child if the direction is OU T ).

DeĄnition 20 (Set of Seeds

During the next super-steps and upon the reception of a token t, the data vertex v decrements the expiration value of t (Lines 13Ű14). When v receives back its own token, it sets the local token Ćag to true for that seed and stop forwarding it (Lines 15Ű17). However, if v is not the initiator and the token has expired already, it will drop it as it is not valid anymore (Lines 18Ű19). If the token is still valid and v is not the initiator, it veriĄes among its neighbors for eligible next hops and forward the token to them, then goes inactive (Lines 20Ű29). The same super-step is executed in the next iterations. The maximum number of super-steps is set to k × l m , where l m is the size of the longest short cycle in ζ and l m ≤ ♣V q ♣.

Example 7. The detection of invalid matches for G D of Figure 3.3c proceeds as follows. The data vertices that will generate tokens are ¶A 1 , . . . , A 3 ♢, ¶D 1 , . . . , D 4 ♢ and ¶C 1 , . . . , C 4 ♢. These sets of vertices are assigned to s 1 , s 2 , s 3 from S g , respectively. We recall that S g = ¶(c 1 , 1, 0, OU T, 3, f alse), (c 1 , 3, 1, IN, 4, f alse), (c 1 , 4, 2, IN, 1, f alse)♢. Let k = 1, hence, the longest matched cycle allowed must be of length l = 3. For example, during the Ąrst super-step, the data vertex D 1 will generate a token t 1 = (T oken(D 1 , c 1 , 4, 3)), then, it will send it to the only parent vertex mapped to t 1 .next = 3 which is data vertex C 1 . At the reception of t 1 in the second super-step, C 1 will decrement t 1 and look for a local seed that corresponds to the short cycle c 1 and query vertex 4, it Ąnds s 3 . C 3 will then look for the next eligible neighbor, i.e. a parent mapped to query vertex 1. This neighbor happens to be A 2 , hence, C 1 will forward the updated token t 1 = T oken(D 1 , c 1 , 1, 2) to it. In the third super-step, A 2 receives t 1 and decrements its expiring value. It updates the token in the same way which results into t 1 = T oken(D 1 , c 1 , 3, 1), therefore, it will forward it to data vertices D 2 and D 4 . In the last super-step, both vertices D 2 and D 4 drop t 1 since they are not its initiators and the token has expired. At the end of the distributed algorithm, data vertices D 1 , D will all have their token Ćags unchanged (set to false) while the other initiators would get back their initiated tokens and set the corresponding Ćag to true.

Vertex-centric algorithm for Ąltering invalid matches

The local vertex program for every data vertex is given in Algorithm VC-FFilter. After the convergence of Algorithm VC-TPass, a new broadcast message is sent to all the graph vertices. Every data vertex that triggered a token passing, i.e. has a non-empty set of local seeds, will verify the reception of its initiated tokens and update its local match set accordingly (Lines 1Ű6). An initiator is considered no longer a match to a certain query vertex if it does not receive any token for the cycle c i ∈ ζ containing that query vertex.

Any removal from the local match set triggers the creation of a removal message that will be sent to both parents and children (Lines 7Ű9).

Afterwards, at the reception of a removal message R msg , every data vertex having a non empty match set updates Ąrst its neighbors match sets (Lines 11Ű12), then, veriĄes the matching constraints and updates its match set and local constraints accordingly (Line 13). Next, it creates a removal message if there are changes in M and sends it to all its neighbors (Lines 14Ű17), that will execute the same routine until no more removal messages are received announcing the end of the algorithm.

At the end of Algorithm VC-FFilter, every data vertex in the dual match graph will have its local matches for BDSim. One last step veriĄes that every query vertex has at least one match. If it is the case, then, the union of the local match sets is the maximum match set w.r.t. BDSim. Otherwise, the returned answer must be empty. Example 8. After the detection of invalid matches from the dual match graph G D of Figure 3.3c, the Ąltering phase proceeds as follows. In the Ąrst super-step, the vertices D 1 , D 2 , C 1 , C 2 will update their local match sets resulting all to an empty match set. Consequently, they will send a removal message to their direct neighbors. Nevertheless, the algorithm stops at the second super-step since no removal messages will be generated during this iteration. Indeed, the removal of these data vertices gives us the match graph of Figure 3.3e.

Algorithm VC-FFilter

Theoretical guarantees

In this section, we prove the convergence and correctness of the proposed algorithms.

Convergence of the distributed algorithms

Given the data graph G = (V, E, f ), the query graph Q = (V q , E q , f q ) and corresponding dual match graph G D = (V D , E D , f ). Let ∆ be the maximum vertex degree in the data graph, Γ ≤ ♣V q ♣ the maximum size of a local match set, σ the size of ζ the set of short cycles and ρ ≤ ♣V q ♣ the length of the longest cycle in ζ. In a distributed environment, let P be the number of processors running in parallel. We are using local data structures that take effective constant time to add, remove, update or Ąnd an element. In the following, we prove the convergence of the proposed algorithms. Theorems 2, 3 and 4 give an upper bound time complexity for each distributed algorithm.

Theorem 2. Algorithm VC-DSim has a time complexity of

O ((♣V ♣ × ♣E♣ × ∆ × ♣V q ♣ 2 )/P )
Proof. The Ąrst super-step for verifying the label similarity takes O(♣V q ♣), because each data vertex iterates over the vertices of the query.

In the second super-step, at the reception of the match sets of its neighbors (∆ messages in the worst case where every neighbor sends its local matches) M c and M p are updated in constant time. Procedure EvalDSim executes the repeat loop for Γ iterations in the worst case when a single member of the local match set is removed in every iteration. The inner loop veriĄes the matching constraints for each member of the match set w.r.t. dual simulation O(Γ). This results into a complexity of O(∆ × ♣V q ♣ 2 ).

When a data vertex is removed, the removal message can propagate to cross the edges of the data graph in the worst case resulting to ♣E♣ additional iterations. When receiving removal messages (∆ messages in the worst case), the data vertex updates the match sets of its neighbors in constant time, and reevaluate the matching constraints in O(Γ 2 ), therefore, the complexity of this super-step is also O(∆ × ♣V q ♣ 2 ). Hence, the algorithm complexity in a fully distributed environment is equal to

O(♣E♣ × ∆ × ♣V q ♣ 2 ). The time complexity in an environment with P processors is O ((♣V ♣ × ♣E♣ × ∆ × ♣V q ♣ 2 )/P ).

Theorem 3. The time complexity for Algorithm

VC-TPass is O ((♣V D ♣ × ∆ 2 × ♣V q ♣ 3 × σ)/P ).
Proof. The Ąrst super-step is composed of a simple operation executed for every seed in S g , hence, the number of iterations is at most (σ × ρ). The body of the loop iterates over local match set M to check the membership of a seed, adds it to S l in constant time. Then, it iterates over the match sets of the neighbors having a size of ∆ × Γ to Ąnd eligible next hops. Hence, time complexity of this super-step is O(σ × ρ × ∆ × Γ).

In the next super-step and beyond, a data vertex can receive up to ∆ × σ × ρ tokens in the worst case, where ∆ is the maximum number of neighbors from which a token is issued and σ × ρ is the maximum size for S l . One token is processed in O(∆ × Γ), because we Ąrst get the related matched vertex from S l in constant time, then iterate over the neighborsŠ match sets to check if one of them is matched to the next hop for the processed token. Therefore, the time complexity of a single iteration is equal to

O(∆ 2 × σ × ρ × Γ).
The number of the remaining super-steps is equal to k × ρ in the worst case (k is the parameter of BDSim). Therefore, in a fully distributed environment, the time complexity of this local program is equal to

O(k × ∆ 2 × ρ 2 × σ × Γ). The algorithm complexity in an environment composed of P processors is equal to O ((♣V D ♣ × ∆ 2 × ♣V q ♣ 3 × σ)/P ). Theorem 4. Algorithm VC-FFilter has a time complexity of O ((♣V D ♣ × ♣E♣ × ∆ × ♣V q ♣ 2 )/P ).
Proof. The Ąrst super-step of Algorithm VC-FFilter iterates over local seeds S l and removes a matched vertex from its local match set if it did not receive back any tokens for this matched vertex. The removal operation takes constant time. The maximum size of S l can be equal to σ × ρ, which is the size of S g . Thus, the time complexity of this super-step is equal to O(σ × ρ). The remaining super-steps are similar to super-step three and beyond in Algorithm VC-DSim, hence, the time complexity of this algorithm in a fully distributed system is equal to

O (♣E♣ × ∆ × ♣V q ♣ 2 ). The time complexity in an environment having P processors is O ((♣V D ♣ × ♣E♣ × ∆ × ♣V q ♣ 2 )/P ).

Correctness of the distributed algorithms

We give Theorems 5, 6 and 7 that prove the correctness of Algorithms VC-DSim, VC-TPass and VC-FFilter, respectively.

Theorem 5. Algorithm VC-DSim computes the correct and complete match set w.r.t. dual simulation.

Proof. The correctness of Algorithm VC-DSim is guaranteed by the following properties (1) the algorithm will terminate (Theorem 2) , ( 2) the algorithm returns a correct match set w.r.t. dual simulation, and (3) the algorithm returns the complete match set w.r.t. dual simulation.

The second property is proved as follows. We suppose that at the end of the algorithm, at least one match (u, v) ∈ V q × V that is kept even though (u, v) does not satisfy dual simulation. First, if (u, v) does not respect dual simulation, this means that (i) u and v do not share the same label value, or (ii) the parent or child constraints of u are not satisĄed by v. Case (i) cannot happen because we only keep in M the query vertices having the same label as v in the beginning of Super-step 1. Case (ii) also cannot happen because every time M c or M p is updated, v receives a removal message and reevaluates the matching constraints according to the new values of M c and M p . Therefore, all the matches stored locally are correct matches.

The third property can be veriĄed as follows. We suppose that at the end of the algorithm there exists at least one match (u, v) ∈ V q × V that respects dual simulation while the match set M of v does not contain u. Actually, if (u, v) is a correct match, this means the two vertices share the same label, hence, u has necessarily been added to M during the Ąrst super-step. During the remaining super-steps of the algorithm, the only removals made from M are for query vertices that do not satisfy dual simulation constraints anymore (Lines 3Ű5 in Procedure EvalDSim). Therefore, the computed match sets are complete.

Furthermore, every single vertex of the query graph must have at least one match which is guaranteed by the last step of phase one that checks such constraint and extracts the dual match graph, hence, the union of the computed local match sets gives the correct and complete match set w.r.t. dual simulation. Theorem 6. At the end of Algorithm VC-TPass, all data vertices that triggered the token passing procedure will receive back at least one token for every bounded cycle to which they belong.

Proof. The correctness of Algorithm VC-TPass is ensured by the following properties (1) the algorithm will terminate (Theorem 3), (2) a data vertex that is part of a bounded cycle in the dual match graph G D will receive back its token, and (3) a data vertex that does not belong to a bounded cycle for a given seed will not receive back any tokens.

The second property is guaranteed by the following. We suppose that at the end of the algorithm, there exists at least one vertex v 0 that is member of a bounded cycle which did not receive back its token. If v 0 is part of a matched bounded cycle c ′ in G D , then, it already has the seeds related to c, the related query graph, stored locally in S l , hence, v 0 has indeed generated at least one token t for this seed. Therefore, if v 0 did not receive back its initiated token t then, either t did not traverse c ′ , or t has been dropped before reaching v 0 . First, if t did not traverse c ′ , then there exists v i in c ′ that did not forward t to the next hop v j in c ′ . However, if v i and v j belong to c ′ , then the matches of v j are already stored in M p and M c of v i . Therefore, v j cannot be ignored by v i when forwarding t because v j is matched to the next hop in c. Consequently, t necessarily traverses the bounded cycle. Furthermore, we know that the initial expiration value of t is set to l × k where l is the length of c and a token is only dropped if it has expired, meaning t has traversed c ′ but it did not reach v 0 . Hence, c ′ has a length l ′ greater than the tokenŠs expiration value (l ′ > l × k), but this contradicts the supposition that c ′ is a bounded cycle. Therefore, every data vertex that has received back its initiated token is member of a bounded cycle in G D .

To prove the third property, we suppose that there is at least one data vertex v 0 that receives back its generated token even though v 0 does not belong to a bounded cycle. First, the token expiration value is initialized to k × l, the maximum allowed cycle length, where l is the length of the corresponding short cycle c in the query graph. Additionally, the token expiration value is decremented in every super-step by the data vertex receiving it. Moreover, an expired token that is not received by its initiator is immediately dropped (Lines 18Ű19), hence, if a token is forwarded back to its initiator, then it must have taken at most k × l hops (the length of the traversed path) to reach back v 0 . Therefore, v 0 belongs to a bounded cycle that has a length ≤ k × l. Theorem 7. Algorithm VC-FFilter computes the correct and complete match set w.r.t. BDSim.

Proof. Algorithm VC-FFilter will terminate (Theorem 4. Moreover, we already proved that every data vertex in the dual match graph satisĄes dual simulation constraints. Furthermore, the data vertices not satisfying constraint 3 in DeĄnition 18 are the ones matched to a seed in S g but that did not receive back any token for those seeds. They must be eliminated, which is what we do in the Ąrst super-step of the algorithm. Each initiator having the token Ćag set to false for a given local seed in S l will remove its related query vertex from its local match set. At the end of this super-step, all the data vertices not satisfying the cycle constraint have an updated matching information. Hence, their neighbors need an updated version of their match sets, which we ensure by the removal messages sent to all direct neighbors. When a removal message is received by a data vertex with a non-empty match set, it will update its overview of the matching information for its parents and children accordingly. Then, it reevaluates dual simulation and updates its local match set. If this reevaluation results into any removal, a removal message will be sent to its neighbors that need an updated version of the local match set of their parents and children. The third super-step and the following super-steps guarantee that every data vertex not satisfying dual simulation anymore is Ąltered out (its local match set is reduced as we proved it in Theorem 5). Now, we need to ensure that all the vertices satisfying constraint 3 of DeĄnition 18 at the end of the Ąrst super-step are still satisfying the same constraint after reevaluating dual simulation. Intuitively, vertices that do not satisfy BDSim are only those not satisfying dual simulation, but these vertices have already been Ąltered out. Super-step two and beyond cannot result into a data vertex that satisĄes dual simulation and not BDSim because if this happens, it simply means that this vertex belongs to only unbounded cycles mapped to c ∈ ζ. Nevertheless, the only changes made in this stage to the dual match graph are removals, hence, such data vertices cannot exist. This proves that every data vertex contains the correct and complete matches w.r.t. BDSim.

Finally, the veriĄcation made at the end of this phase ensures that each query vertex has at least one match which, in turn, guarantees that the union of these local matches is the correct and complete match set w.r.t. BDSim.

Experimental evaluation

We conducted different experiments on synthetic and real datasets with the goal of measuring the performance of the proposed approach and compare it to the three models: graph simulation, dual simulation and strict simulation. Another aim is to identify the bottlenecks of the proposed algorithms.

Experimental data sets

In addition to synthetic graphs generated using the R-MAT model [START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF], we worked on two real datasets from SNAP Library [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF], their characteristics are given in Table 3.3. Amazon0601: This graph represents the recommendation system of the online store Amazon. The graph vertices are Amazon products, while the links between these products mean that the two are usually ordered together, i.e. ŞUsers Who Bought This Also Bought ThisŤ relationships. LiveJournal: It is another social network that allows users to share and write blogs. Vertices represent users while edges represent the friendships among them.

Synthetic graphs:

The R-Mat model is used to generate the synthetic data graphs. It takes as input ♣V ♣, ♣E♣ and ♣Σ♣ such that ♣Σ♣ is the number of distinct labels and ♣E♣ = 20 × ♣V ♣.

Experimental setup

The experiments presented in this thesis were carried on the High Performance Computing Platform IBNBADIS. This platform is composed of 32 compute nodes, each composed of two processors Intel(R) Xeon(R) CPU E5-2650 2.00GHz. Each processor has 8 cores, which gives a total of 512 cores to the cluster. The theoretical power of IBNBADIS is around 8 TFLOPS. Moreover, each node has 32GB memory with 100GB of disk capacity.

We deployed a 20-node cluster of Apache Spark [START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF] on top of IBNBADIS, where one node plays the role of the master while the remaining nodes are considered workers.

All the algorithms proposed in this thesis were implemented using GraphX [START_REF] Xin | Graphx: A resilient distributed graph system on spark[END_REF] and SCALA programming language. GraphX is a module provided by Apache Spark that allows vertex-centric graph processing through the exposed API of Pregel [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF].

Pattern generation

We have tested the proposed algorithms of BDSim on real-world graphs by varying the size of the pattern graph such that for each value ♣V q ♣, we extract 50 different patterns randomly.

For this purpose, we implemented an algorithm that extracts patterns of small size randomly from a data graph. The algorithm takes two input parameters that are ♣V q ♣, the size of the subgraph and its density α such that ♣E q ♣ = ♣V q ♣ α . The default value of α is set to α = 1.2 in all our experiments. This algorithm executes a BFS starting from a random vertex in the graph, collects vertices randomly based on a Ąxed value of average out degree d O computed such that α = 1.2, then we extract the subgraph connecting these vertices and add up edges to match the input parameters.

Experimental results

In Figure 3.6, we compare the number of short cycles in a given query graph to the number of all simple cycles (Amazon0601 in Figure 3.6a and LiveJournal in Figure 3.6b). Bounding the length of the cycles in the resulting match graph becomes intractable if we decide to track all the simple cycles of the query graph. The reason is because we have to deal with an exponential number of cycles. Nevertheless, the number of short cycles increases linearly w.r.t. the size of query graphs. Therefore, using the set of short cycles allows us to reduce signiĄcantly the number of processed cycles, resulting to a controlled number of tokens and messages, which allows us to bound the length of all the existing cycles in the dual match graph in a reasonable time. We can see in Figures 3.7a and 3.7e that for Amazon0601 and LiveJournal, BDSim gives a response time better than strict simulation and it yields to better quality answers since the number of returned matches is reduced in comparison to the other models (Figures 3.7b and 3.7f).

The number of super-steps for BDSim is almost always the highest (Figures 3.7c and 3.7g). However, it does not affect negatively the Ąnal response time, because as we can see in the the four charts of Figure 3.8, the number of active vertices during every super-step, for different values of ♣V q ♣ and for the two datasets, is always lower than that of strict simulation, without forgetting that for strict simulation the last iteration will involve all the vertices present in the dual match graph.

The average response time increases with the query size because more vertices in the query graph will most likely lead to larger intermediate results. Hence, having more active vertices which will increase the size of match sets processed in every super-step resulting into higher response time.

The number of exchanged messages shown in Figure 3.7d and Figure 3.7h for Amazon0601 and LiveJournal, respectively, is sensitive to the size of the query graph for the same reason explained above. Actually, large intermediate results lead to more exchanges between the graph vertices. We notice that the number of messages for BDSim is very close to that of dual simulation. This is possible thanks to the token passing approach that limits the search space into only eligible neighbors of a data vertex.

Exp-2:

In this set of experiments, we evaluate our algorithms by varying the size of the data graph. We use the R-Mat graph generator implementation provided by GraphX, we give as an input the graph scale such as ♣V ♣ = 2 scale , ♣E♣ = 20 × ♣V ♣ and Σ = 100. We vary the graph scale from 13 to 21, and for each generated graph, we extract 50 different patterns of the same size ♣V q ♣ = 9 with α = 1.2. After that, we report the average response time, number of super-steps, number of exchanged messages and number of returned matches in Figure 3.9.

BDSim scales well with the size of the data graph. Actually, our algorithm runs in a cubic time in function of the data graph size as it is shown in Figure 3.9a. Moreover, Figure 3.9c gives the number of super-steps following logarithmic curve with an average difference of 6 additional super-steps compared to dual simulation when ♣V q ♣ = 9. We also notice that our approach performs better in terms of quality of results when the data graph is larger where the number of returned matches is reduced by 2/3 times compared to dual simulation. Furthermore, the number of exchanged messages follows the same pace as dual simulation (Figure 3.9d).

Exp-3:

In this set of experiments, we evaluate our approach by varying the number of distinct labels using the same R-Mat generated data graph (♣V ♣ = 0.45M , ♣V q ♣ = 9 ). We vary ♣Σ♣ from 100 to 500. After that, we report the average response time, number of super-steps, number of exchanged messages and number of returned matches. The obtained results are given in Figure 3.10.

The response time is also sensitive to ♣Σ♣ (Figure 3.10a). It decreases when increasing ♣Σ♣ for both BDSim and dual simulation. Actually, having more distinct labels in the data graph will lead to decreasing largely the size of intermediate results and this happens right from super-step one, hence, less data vertices are likely to share their match sets, resulting into a decrease in the number of returned matches and number of exchanged messages (Figures 3.10b and 3.10d respectively). The number of super-steps also decreases (Figure 3.10c) since more data vertices are Ąltered during the Ąrst few iterations of the algorithm unlike when ♣Σ♣ is high where more data vertices are considered as candidates, which requires more iterations to Ąlter out incorrect matches, thus resulting into higher response time.

(a) Amazon0601, ♣V q ♣ = 4 6XSHUVWHS DFWLYHYHUWLFHV *6LP '6LP %'6LPN 676LP (b) Amazon0601, ♣V q ♣ = 7 6XSHUVWHS DFWLYHYHUWLFHV *6LP '6LP %'6LPN 676LP (c) LiveJournal, ♣V q ♣ = 4 6XSHUVWHS DFWLYHYHUWLFHV *6LP '6LP %'6LPN 676LP (d) LiveJournal, ♣V q ♣ = 7
The obtained results conĄrm that BDSim improves the quality of the returned matches compared to the existing models. Furthermore, the approach used to detect and Ąlter out unbounded cycles ensures an effective and efficient elimination of invalid matches without requiring large amounts of data shipment. BDSim can handle the problem of failing query thanks to parameter k. This adaptability of BDSim guarantees that only results of good quality are returned Ąrst when k is initialized to a small value. Nevertheless, k can be increased by one step in the case of zero answers to allow returning more Ćexible results. Finally, even though BDSim returns answers of better quality, it remains a scalable model that requires a processing time comparable to that of dual simulation.

Chapter summary

Despite the abundant work on graph pattern matching, it is only recently that research works started focusing on the challenges brought about by current real-world applications, mainly scalability. In this chapter, we proposed BDSim, an extension of dual simulation that captures the cyclic structure of the input query graph. Our main contribution is preserving proximity between the query vertices by tracking and Ąltering out cycles of unbounded length from the Ąnal match graph. Indeed, we proved that the set of short cycles of a query graph is sufficient to bound the length of all the matched cycles of the match graph. Besides, we proposed distributed vertex-centric algorithms to evaluate BDSim and demonstrated their effectiveness and efficiency through theoretical guarantees and extensive experiments on real-world and synthetic data sets. The obtained results showed that BDSim signiĄcantly improves the quality of the returned answers while requiring a response time comparable to dual simulation.

BDSim and strong simulation are both relaxed GPM models that preserve duality and locality. However, even though it is not intuitive to scale up strong simulation, this model is interesting since it returns separate subgraphs as an answer to the input query graph, while BDSim returns a single match graph. Therefore, we give particular attention to strong simulation in the next chapter by proposing fully distributed and scalable algorithms that evaluate strong simulation and strict simulation with performance guarantees.

Chapter 4

A Distributed and Scalable Approach for Strong Simulation

Introduction

Strong simulation was introduced to improve the quality of graph simulation by imposing two properties, namely duality and locality. The duality ensures preserving the connectivity of the answers, while the locality property guarantees that the returned subgraphs have bounded size. Strong simulation is particularly interesting as it is close to subgraph isomorphism in terms of quality while it can still be evaluated in cubic time.

Prior distributed algorithms of strong simulation [START_REF] Ma | Capturing topology in graph pattern matching[END_REF][START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF][START_REF] Fan | Querying big graphs within bounded resources[END_REF][START_REF] Wang | Parallel algorithms for Ćexible pattern matching on big graphs[END_REF] did not provide any guarantees when it comes to scalability. Indeed, these approaches require moving large parts of the data graph across the cluster workers in order to make the locality balls available inside each machine, therefore resulting in large amounts of data shipment that may create a bottleneck in the case of data graphs not having a uniform degree distribution.

Motivated by these limitations, we propose D3S, a distributed and scalable algorithm that evaluates strong simulation with performance guarantees. First, D3S does not duplicate any parts of the data graph which ensures reduced communication costs. Moreover, D3S addresses the natural skewness in real graphs by processing the locality balls in a vertex-centric fashion, i.e. each member of a given locality ball participates in computing the answer related to it. Furthermore, based on D3S, we design a distributed algorithm for the more restricted model; strict simulation that reduces the size of the generated locality balls, resulting in answers of better quality compared to strong simulation. We refer to the algorithm of strict simulation as D3S + . Finally, we provide theoretical guarantees in addition to extensive experiments on synthetic and real-world datasets to validate the different algorithms proposed. The test results conĄrm that our approach can be Ąve times faster than the state-of-the-art work.

The remainder of this chapter is structured as follows. Section 4.2 details the distributed vertex-centric algorithms proposed in addition to their formal validation. Strict simulation is discussed in Section 4.3. Finally, the performance evaluation of D3S and D3S + is presented in Section 4.4.

D3S: A distributed and scalable approach for strong simulation

Strong simulation strikes a balance between Ćexibility and tractability. It guarantees a number of properties such as (1) preserving the child relationships, i.e., if a query vertex u matches a data vertex v, then each child of u matches a child of v, (2) similarly, it preserves the parent relationships, (3) strong simulation preserves directed and undirected cycles, i.e., each undirected (directed) cycle in the query graph matches an undirected (respectively directed) cycle in the match graph, (4) locality is also preserved by strong simulation such that subgraph matches are searched in a locality ball having a diameter equal to 2 × d where d is the query diameter, and Ąnally (5) the number of subgraph matches returned by strong simulation is bounded by the number of vertices in the input data graph. Indeed, each data vertex can result to a locality ball that may return a match subgraph.

The above properties guarantee for strong simulation to be the best Ąt model for modern GPM applications. In a spectrum of several models varying in Ćexibility and tractability, strong simulation stands in the middle between subgraph isomorphismŮbeing NP-Complete while having rigid constraintsŮand graph simulation, which is considered too loose for capturing the structural information of a query graph. Nevertheless, massive graphs of today are generally distributed over clusters of machines, therefore requiring the sequential graph algorithms, including strong simulation, to be revisited for such complex environments. The challenges we aim to address are the following. First, designing a scalable algorithm for evaluating strong simulation in massive graphs. Second, how to make this algorithm fully distributed so it can beneĄt from all the computing resources available, and hence gain in terms of performance? Next, how can we avoid duplicating the graph data, therefore allowing a scalability of the approach? In fact, avoiding the replication of graph data is crucial, especially in the case of massive and dynamic graphs where update events need to be reĆected while making minimum changes to the data graph.

To address these challenges, our approach for a distributed and scalable evaluation of strong simulation (D3S) is designed to work in three stages. First, a vertex-centric algorithm enumerates the dual simulation matches in a distributed way. After that, we propose a novel algorithm that performs a distributed neighborhood discovering. This step allows every data vertex being part of some locality ball to receive the identiĄer of the center of this ball. Finally, strong simulation is evaluated in a fully distributed way among all the data graph vertices to get the Ąnal maxPGs.

Overview of D3S

In this section, we give an overview of the distributed algorithm D3S. After that, we proceed with the design of each phase apart. However, it is important to Ąrst recall the notion of strong simulation. Strong simulation uses the notion of locality balls that are subgraphs of the data graph in which a match graph is computed. Looking for a match graph inside such locality balls guarantees preserving distances between the match graph vertices. It is formally deĄned as follows.

DeĄnition 21 (Locality ball). Given a data graph G = (V, E, f ), vertex v ∈ V and positive integer d. The induced subgraph of G that contains v and all the vertices in G within a maximum distance d from v is referred to as a locality ball. This ball is denoted as Ĝ [v, d] such as v is its center and d is its radius.

In Figure 4.1, we give query graph Q 4 and data graph G 4 . Strong simulation evaluates a graph pattern matching query by Ąrst, creating locality balls centered at every vertex in G 4 and having a radius = 2 (diameter of Q 4 ). The locality ball Ĝ [START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF][START_REF] Acosta-Mendoza | Frequent approximate subgraphs as features for graph-based image classiĄcation[END_REF] centered at data vertex 4 is illustrated in Figure 4.1c. When evaluating dual simulation inside this ball, the maximum dual match set returned is ∅. On the other hand, locality ball Ĝ [START_REF] Bhattarai | Ceci: Compact embedding cluster index for scalable subgraph matching[END_REF][START_REF] Acosta-Mendoza | Frequent approximate subgraphs as features for graph-based image classiĄcation[END_REF] contains one maxPG denoted G s (illustrated in Figure 4.1d) that will be returned as an answer by strong simulation.

We also use the notion of matching constraints introduced in DeĄnition 19 in evaluating dual simulation and strong simulation. For query graph Q 4 , the set of parent constraints Algorithm D3S

C p for query vertex A is C p (A) = ∅, while the child constraints C c is C c (A) = ¶B,
1 Input: G, Q; 2 Output: G s ; 3 Broadcast(Q); 4 G 1 ← D3S A (G, Q); 5 G 2 ← InducedSubgraph(G 1 ) // filter out vertices having empty M in parallel 6 G 3 ← D3S B (G 2 ); 7 G 4 ← D3S C (G 3 ); 8 G s ← ExtractMaxPGs(G 4 ); 9 return G s ;
Algorithm D3S takes as input a data graph G and a query graph Q. The Ąrst step of the algorithm is broadcasting Q to the data graph vertices that will run in a vertexcentric way. The reception of this message triggers D3S A , a distributed and vertex-centric algorithm that evaluates dual simulation locally to each data vertex (Lines 1Ű4). At the end of Algorithm D3S A , every data vertex will have its correct matching information computed locally. We note that the union of these local matches gives the maximum dual match set R d . Nevertheless, we use directly the current state of the data graph to Ąlter out vertices that will not participate in evaluating strong simulation (call of Procedure InducedSubgraph in Line 5). A detailed discussion of the importance of this Ąltering phase is provided under Section 4.2.3. On a relatively smaller data graph, where each data vertex has its matching information stored locally, we execute the vertex-centric neighborhood discovery algorithm D3S B . This algorithm allows the remaining vertices to get the information of their locality balls (Line 6). Afterward, each vertex will execute a local vertex-centric algorithm, referred to as D3S C , to evaluate dual simulation for the locality balls where it is considered a member (Line 7). Indeed, each data vertex will have different matching information stored locally depending on which locality ball is considered as the main one. We note that these locality balls are identiĄed by their centers. Finally, Algorithm D3S calls Procedure ExtractMaxPGs (Lines 8) to extract the maximum perfect subgraphs from the resulting match sets related to each locality ball.

In what follows, we present the different stages of Algorithm D3S separately with examples and give their respective vertex-centric algorithms in addition to the proofs of correctness and convergence.

Vertex-centric dual simulation

The distributed and vertex-centric algorithm for evaluating dual simulation is denoted

D3S A .
It is presented and discussed in details in Section 3.3.2. D3S A is a constraint-based algorithm that generates the matching constraints related to each query vertex, then, it broadcasts them among the data graph vertices. After that, each data vertex maintains a local context composed of its match set M and the set of constraints for every member in this match set. At the reception of the query graph, every data vertex v initializes M with the set of query vertices that has a similar label. Moreover, it keeps locally the set of constraints related to these query vertices for verifying dual simulation. If M is not empty, then, vertex v will share it with its direct neighbors at the end of this super-step.

Algorithm D3S A takes as input C c and C p . Each data vertex v maintains a local context composed of its match set M and the set of constraints for every member in this match set. The data vertices can exchange two types of messages: data messages D msg and removal messages R msg . The data messages are used in propagating the matching information of a vertex to its neighbors, while the removal messages carry an update event of the local matching information to the neighbors.

At the reception of the Ąrst broadcast message containing Q, data vertex v initializes M with the set of query vertices in Q that have a similar label. It also keeps the constraints related to them locally (Lines 1Ű6). If M is not empty, then, data vertex v will share M with its direct neighbors in the form of a data message D msg (Lines 7Ű9). Otherwise, v becomes inactive because it does not belong to the global match set w.r.t. dual simulation (Lines 10Ű11).

In the second super-step of D3S A , every data vertex v having a non empty match set will be activated. If it receives a data message D msg , then, it stores the received match sets of its parents and children locally in separate variables M p and M c , respectively (Lines 12Ű 13). Next, even if it does not receive any data, it must evaluate the constraints of dual simulation using its local information, i.e., M, C p , C c , M p and M c (call of Procedure EvalDSim in Line 14). If the evaluation leads to having one or more non satisĄed constraints for a given query vertex u, then u will be removed from M and its related constraints C p (u) and C c (u) will also be removed. A removal message R msg containing the removed matches R m will be generated and broadcast to the neighbors of v (Lines 15Ű18). Every time a removal of a query vertex from M happens, it will be followed by the removal of its related constraints in local C p and C c .

In the next super-steps, the reception of a removal message will trigger two operations. First, each data vertex receiving this removal message will update the match sets of its parents M p and children M c accordingly (Lines 19Ű20). Then, it will reevaluate the matching constraints w.r.t. dual simulation (call of Procedure EvalDSim in Line 21). If the matching constraints are not satisĄed for a given query vertex u in M , then M is updated, u is added to R m , and a removal message R msg containing R m is generated and broadcast to the direct neighbors of v (Lines 22Ű25). The same process is repeated in the following super-steps until the local match sets converge and no new removal messages are generated anymore. At the end of the distributed algorithm, every data vertex will have its local match set w.r.t. dual simulation. If every single query vertex has at least one match, then, the union of these local matches is exactly the global match set w.r.t. dual simulation. Otherwise, the global match set is ∅.

Example 9.

In data graph G 4 and query graph Q 4 , if we notice data vertex 15 that has label D, its parent constraints are C p (D) = ¶C♢ and it has an empty child constraints C c (D) = ∅. On the other hand, its parents in G 4 are ¶10, 14♢ and their respective mappings from the Ąrst iteration are ¶(10, A), (14, D)♢. Since vertex 15 does not have a parent that satisĄes the parent constraints (a parent matched to query vertex C), then it will remove C from its local match set (along with the related constraints). After that, it will create a removal message R msg with the mapping (15, D). Then, it will share it with neighbors 10 and 14. since the removal of vertex 15 will not affect the match sets of vertices 10 and 14, the next super-step is the last one in Algorithm D3S A .

Vertex-centric neighborhood discovery

Let G = (V, E, f ) be a data graph, Q = (V q , E q , f q ) a query graph and d the diameter of Q. Strong simulation improves the quality of dual simulation by imposing an additional constraint which is the locality. This property requires dual simulation matches to be located inside a locality ball of radius d and centered at data vertices that are already part of the maximum dual match set R d .

Moreover, given G ′ the induced subgraph of G w.r.t. V ′ (set of vertices in R d ), it has been shown in [START_REF] Ma | Capturing topology in graph pattern matching[END_REF] that strong simulation can be directly evaluated on G ′ instead of G. Indeed, for every v ∈ V , the maxPG resulting from the locality ball b centered at v with radius d in G is equivalent to the maxPG extracted from locality ball b ′ centered at v with radius d in G ′ . Therefore, we use G ′ in this phase to reduce the size and number of locality balls, hence, avoiding unnecessary computations. Working on the induced subgraph G ′ eliminates locality balls centered at vertices with an empty match set w.r.t. dual simulation. It also ensures that locality balls are composed of only valid dual simulation matches.

We propose discovering the d-neighborhood of each data vertex in R d , then evaluating dual simulation for the resulting locality balls in a distributed way. To do so, we give the vertex-centric algorithm D3S B that allows each vertex in G ′ to propagate its identiĄer in a ball of radius d. This propagation allows other vertices that share the same locality to discover it.

D3S B is triggered by an initial broadcast message I msg . At the reception of I msg , the centers of locality will generate and send a data message with their identiĄers to their locality members (Lines 1Ű3). Upon the reception of a locality ball center c, the receiving vertex will add it to a local set named L b . It will also map it in a [key, value] form with its local match set M (c) and its parent and child match set M p (c) and M c (c), respectively (Line 4Ű5). An illustration of partial local context of data vertex 4 is given in Figure 4.2. After that, a data vertex will propagate the received centers to its neighbors (Lines 6Ű7). The propagation will follow in the next super-steps until Super-step d + 1 where every data vertex will have the list of centers of all the locality balls to which it belongs (Lines 8Ű10). At the end of Super-step d + 1, each data vertex with a non empty list of centers will share this list with its direct neighbors (Lines 11Ű13). When a data vertex receives such list, it will store it locally in a variable named N b (Lines 14Ű16). At this point, every data vertex has a list of locality balls centers attached to their corresponding local match sets. The parent and child match sets are also kept locally as they help in identifying the matches to be removed in the next phase. , hence the locality balls will have a radius equal to 2. Moreover, since data vertex 4 belongs to the maximum dual match set, it must propagate its identiĄer in a 2-neighborhood. In the next super-step, vertex 4 will also discover the locality balls to which it belongs and that are at one hop, i.e. it will get the set ¶1, 2, 3, 5♢. Vertex 4 will store these centers locally in variable L b , then it will receive centers ¶6, 7, 8, 10♢ at the beginning of the third super-step. It will also share this list with its direct neighbors ¶1, 2, 3, 5♢. Finally, it will receive the locality centers of these neighbors and store them in N b . Figure 4.3 illustrates the execution of this phase.

M c (c 1 ) M(c 1 ) M p (c 1 ) M c (c 2 ) M(c 2 ) M p (c 2 ) M c (c 3 ) M(c 3 ) M p (c 3 ) 4 c 1 c 2 c 3
Lemma 3. At the end of Algorithm D3S B , every data vertex having a non-empty match set will have the set of locality balls centers to which it belongs.

Proof. The correctness of Algorithm D3S B is guaranteed by the following properties. ( 1) the algorithm will terminate (Lemma 4), ( 2) every vertex v has the correct and complete set of centers for each locality ball in which it is a member.

First, we suppose that the algorithm collects an invalid center, and then prove the impossibility of this case. The set L b contains vertices that are in a d-neighborhood from v and that have a non empty match set, hence, an incorrect center is either a vertex with a non empty match set or a vertex that is located in a distance > d from v. In every super-step of the algorithm, a data vertex is activated only if it has a non empty match set, hence, a vertex that communicates data with its neighbor must have a non empty match set. Furthermore, L b is constructed in an iterative way between the super-steps 1 and d + 1 where a message generated in Super-step i arrives at the next hop in Super-step Proof. We know that the maximum number of super-steps of D3S B is Ąnite (d + 2 such that d is the diameter of the query graph). Moreover, each super-step will terminate.

Actually, the Ąrst super-step is an atomic operation that will terminate. The second super-step will also terminate because it iterates over a list of Ąnite size (number of received messages from neighbors is Ąnite). The same thing applies to the super-steps from 3 to d + 1 that will terminate. The last super-step involves an atomic operation for storing the received data locally, hence, the algorithm will terminate.

Vertex-centric strong simulation

The last phase of our approach consists of evaluating strong simulation according to every locality ball in a distributed way. Each data vertex in G ′ uses the N b as a guide to update M p (c) and M c (c) for each center c in L b (lines 1-4). Actually, if a neighbor n does not belong to a locality ball centered at c ∈ L b , then, its entries in M p (c) and M c (c) will be Ąltered out. Indeed, the membership of n is retrieved from N b .

Next, each data vertex v reevaluates the matching constraints w.r.t. dual simulation according to each center in ¶L b ♢ (the call of Procedure EvalDSim in Line 5). If the dual simulation constraints are not satisĄed anymore for some speciĄc center c, this means that v does not belong to a maxPG resulting from the locality ball centered at c, hence, a removal message R msg must be generated to inform its neighbors. The removal message is composed of the related locality ball center, the data vertex identiĄer and removed query vertex (Lines 6Ű8). Furthermore, v will also remove itself from a locality ball if its corresponding match set becomes empty, i.e. it removes the center entry from variable L b (Lines 9Ű11). Afterward, v continues processing all the locality centers while generating removal messages if there are any non respected constraints.

Upon the reception of a removal message R msg in the second super-step, each data vertex checks Ąrst if it belongs to the related locality ball, if not, the message is ignored (Line 14). Otherwise, the vertex updates the parents and children local match sets for that center c (Line 15). After that, it reevaluates again the matching constraints w.r.t. dual simulation (call of Procedure EvalDSim in Line 16). This call returns the updated match set M (c) in addition to the set of removed matches R m . If R m is not empty, a removal message R msg is generated and sent to all the direct neighbors (Lines 17Ű19). Similar to the previous super-step, if the local match set w.r.t. center c becomes empty, then v removes itself from the corresponding locality ball, i.e., it removes c from L b (Lines 20Ű22).

In the following super-steps, every removal message will trigger the reevaluation of dual simulation constraints with possible updates of the local match sets and generation of new removal messages. The same process is triggered in each super-step until no messages are exchanged anymore announcing the convergence of the distributed algorithm. At this point, every data vertex has locally the set of locality balls in which it has matches. The union of matches for each locality ball forms the maxPG of that center. Finally, Procedure ExtractMaxPGs will check for each returned maxPG if its center has a non-empty local match set and that every query vertex has at least one match. Otherwise, this maxPG is Ąltered out. To evaluate dual simulation for any locality ball, it must Ąrst update the parent and child match sets related to it according to the contents of N b . If we take the locality ball b 6 centered at 6 ∈ L b , the neighbors ¶1, 2, 5♢ do not belong to it, hence, their entries are removed from M p (6) and M c [START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF]. We end up with only one entry in the neighbors match sets of center 6, i.e., (3, A). The local dual simulation constraints are not satisĄed for b 6 , hence, vertex 4 will remove itself from b 6 , i.e., remove 6 from L b and generate a removal message with this information. This removal message is sent to the direct neighbors that will update their match sets for b 6 . This data vertex will do the same thing for the other centers in L b . The remaining vertices in G ′ will execute the same routine resulting in new removal messages that will be propagated among the graph vertices. At the end of the algorithm, only the centers ¶3, 6, 7, 11, 12, 13♢ will remain. If we take center 7, the Ąve vertices ¶3, 6, 7, 11, 12, 13♢ all satisfy dual simulation for its locality ball. These vertices form the maxPG that will be returned by the algorithm.

Algorithm

Lemma 5. Algorithm D3S C returns the correct and complete set of maxPGs w.r.t. strong simulation.

Proof. In the same way we proved the correctness of D3S A , one can see that, considered separately, each data locality center represents a locality ball in which we evaluate dual simulation in a distributed vertex-centric way (using the same routines in algorithm Given a data graph G = (V, E, f ) and a query graph Q = (V q , E q , f q ), to Ąnd the maxPGs Proof. The correctness of D3S results directly from Theorem 5, Lemma 3 and Lemma 5.

D3S + : Distributed and scalable evaluation of strict simulation

Strict simulation is an extension of strong simulation where the data locality balls are generated from the dual match graph instead of the induced subgraph. This optimization reduces the size of locality balls and restricts further the size of returned matches. Consequently, the data shipment is reduced and the returned maxPGs are of better quality. We name the distributed vertex-centric algorithm for strict simulation D3S + . This variant of Algorithm D3S uses a dual match graph instead of the induced subgraph (call of Procedure DualMatchGraph in Line 7 of Algorithm D3S + ).

The implementation provided by GraphX for Pregel executes a distributed algorithm as a series of super-steps where each vertex that receives a message at the end of the previous super-step is activated to execute its local program and prepare messages for the next super-step. These super-steps are separated by synchronization barriers following the BSP model. GraphX offers an additional feature for exchanging messages. A data vertex can access its neighborsŠ local context to decide whether it needs to exchange messages with them or not. We use the exposed information from each data vertex to decide whether or not to send a message in three scenarios. The Ąrst scenario is related to the evaluation of dual simulation, a data vertex shares its local match set only with data vertices that can beneĄt from it in building their local match sets. Actually, a neighbor is interested in receiving a match set if the vertex sending it matches their parent and/or child constraints. Hence, if there is no intersection between the vertex constraints and this neighborŠs match set, the match set will not be shared with it, which eliminates useless messages and avoids unnecessary computations. The second scenario appears in the phase of neighborhood discovery when a data vertex decides to propagate its list of centers, it only sends the ones not already known by each neighbor. This optimization reduces the size and number of exchanged messages. Finally, the removal messages are only shared with data vertices having a non empty match set, because there is no need to activate data vertices that are already eliminated from the global match set. These improvements reduce the number and size of exchanged messages which optimizes signiĄcantly the response time of D3S and D3S + .

Experimental environment

We worked on four real-world graphs from SNAP Datasets [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. The characteristics of these real graphs are given in Table 4.1. Unless expressly stated otherwise, the number of distinct labels in each data graph is Ąxed to ♣Σ♣ = 500.

Furthermore, the R-Mat model [START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF] is used to generate synthetic data graphs. It takes as an input ♣V ♣, ♣E♣ and ♣Σ♣ such that ♣Σ♣ is the number of distinct labels and ♣E♣ = 20×♣V ♣. When varying the values of ♣V q ♣, we use the algorithm given in Section 3.5.3 to extract 50 different patterns randomly for each value.

We executed our experiments on a Spark cluster composed of 10 nodes with 32GB memory and 16 cores for each; one node plays the role of the master while the remaining nodes are considered as workers.

Experimental results

The results of performance evaluation for D3S and D3S + and comparison with the stateof-the-art distributed algorithm for evaluating strict simulation Strict13 from [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF] are presented and discussed in this section.

Exp-1:

In the Ąrst set of experiments, we evaluate the performance of D3S by varying the following graph parameters: The size of query graph ♣V q ♣, the query diameter d and the number of distinct labels ♣Σ♣. The obtained results are discussed below.shown in Figure 4.5. In Figure 4.5a, we notice that the size of the query graph does not affect greatly the overall running time of D3S, especially for small and average data graphs. The number of super-steps (Figure 4.5b), on the other hand, depends largely on the size of the query graph and follows a logarithmic growth in function of the query size. In Figure 4.5c, we see that the number of exchanged messages is almost constant and does not seem to be dependant of the size of query graphs. In Figures 4.5d, 4.5e and 4.5f, we see that the highest number of active vertices is reached mainly in the Ąrst few iterations where data vertices not satisfying dual simulation are being eliminated. After that, the number of active vertices remains stable until the end which conĄrms that the two algorithms D3S B and D3S C converge with a bounded number of active vertices.

Since the number of iterations of the distributed algorithm is given in function of the diameter of the query graph, we vary this parameter. We report the average response time in Figure 4.5j, number of super-steps in Figure 4.5k and number of exchanged messages in Figure 4.5l. The results obtained show that, indeed, the number of super-steps grows linearly when d increases, reaching at most 20 iterations for queries having a diameter equal to 8. The response time is also sensitive to the change in query diameters. It increases faster for larger data graphs, namely LiveJournal. Moreover, the data shipment, represented by the total number of messages, remains constant when varying d, which proves that D3S is insensitive to the query diameter in terms of data shipment.

Finally, since the number of distinct labels plays in important role in the Ąltering phase where only the candidate vertices are kept active, we evaluate the performance of D3S when varying ♣Σ♣ in the data graph. We report the average response time in Figure 4.5g, average number of super-steps in Figure 4.5h and average number of exchanged messages in Figure 4.5i. The number of labels also has a little effect on the performance of D3S. Actually, the less labels are in the data graph, the more computations are triggered to eliminate invalid matches among the remaining candidates. This is explained by the fact that the number of initial candidates gets larger when the number of distinct labels decreases. The same thing applies to the number of super-steps. However, the number of messages is almost the same for all values of ♣Σ♣ which proves that D3S is insensitive to this parameter.

Exp-2:

In this set of experiments, we compare D3S and D3S + to Strict13 when varying the size of query graph. The average response time, the average number of super-steps the average number of exchanged messages with respect to ♣V q ♣ are presented in Figure 4.6. We conducted the comparison on the real datasets Epinions, Amazon0601, GoogleWeb and LiveJournal.

These experiments show that D3S and D3S + are faster than Strict13 by up to Ąve times. The number of super-steps is, in turn, larger for D3S and D3S + because all the computations are conducted in a vertex-centric way while in Strict13, the last iteration is the longest as it evaluates strict simulation for every data locality ball in a sequential way. This explains why D3S and D3S + are faster even though they require additional super-steps. D3S + runs more super-steps than D3S to get the Ąnal maxPGs because strict simulation is more stringent than strong simulation, hence, D3S + involves the removal of extra invalid matches that were accepted by D3S. The data shipment is larger in Strict13 which slows down the computations compared to D3S and D3S + for the four datasets. In Figures 4.6c, 4.6f, 4.6i and 4.6l, we see that the larger the query graph, the larger becomes the gap between the number of messages exchanged in D3S (or D3S + ) and Strict13.

Exp-3:

In these experiments, we test the weak scalability of our approach in comparison to Strict13 by increasing the size of the data graph. We varied the scale of R-Mat graphs from 13 to 22 (size of data graphs from 2 13 to 2 22 ) and compared D3S and D3S + to Strict13 (♣V q ♣ is set to 9). The results are given in Figure 4.7.

In Figure 4.7c, the data shipment is slightly larger for Strict13. Even though the number of super-steps (Figure 4.7b) is larger for both D3S and D3S + , the response time in Figure 4.7a, on the other hand, is shorter by two thirds compared to Strict13.

Chapter summary

In this chapter, we studied strong simulation, an interesting model for answering GPM queries. It allows capturing the topology of the query graph compared to graph simulation while still feasible in cubic time. We proposed the distributed approaches D3S and D3S + for evaluating strong simulation and strict simulation, respectively. To achieve higher levels of scalability, D3S and D3S + were designed to be fully distributed such that the data graph parts are never shipped between workers or between vertices residing on the same worker. Consequently, strong simulation (and strict simulation) can be extended to cases where the semantic similarity is deĄned based on multiple attributes. We validated the effectiveness and efficiency of our algorithms through theoretical guarantees in addition to extensive experiments on synthetic graphs and real-world datasets. Furthermore, the test results show that D3S and D3S + run faster than the state-of-the-art work, which makes them suitable for massive graphs and the current applications of GPM in social networks.

Notably, the acceleration achieved by D3S and D3S + mostly concerns the neighborhood discovery and strong simulation evaluation. Although we used a distributed vertex-centric algorithm to evaluate dual simulation, an important portion of the processing time of D3S and D3S + is spent in dual simulation. Moreover, the two GPM models dual simulation and graph simulation are particular as they do not require locality during the matching process, which raises a question on the need for a vertex-centric processing to Ąnd answers w.r.t. these two models. We attempt to answer this question in the next chapter by proposing two parallel and edge-centric algorithms that outperform signiĄcantly the vertex-centric versions. Accordingly, we can use the parallel dual simulation to accelerate further the two algorithms D3S and D3S + .

Chapter 5

An Efficient Parallel Edge-Centric Approach for Relaxed GPM

Introduction

Even though many works have addressed the problem of GPM for large graphs, the actual size of data graphs is still challenging. In fact, social networks are generating huge amounts of data continuously, e.g., Facebook was the largest network with 2.4 billion monthly active users in June 2019 [START_REF] Dustin | Social media statistics 2020: Top networks by the numbers[END_REF]. These networks cannot Ąt on the memory of a single machine due to their large size; hence, they need distributed storage and processing. Among the challenges we encounter in such distributed environments, there is linear scalability, a key property for distributed graph algorithms. Yet, prior works addressing relaxed GPM in this context are limited due to the bounded level of parallelism that can be reached [START_REF] Ma | Distributed graph pattern matching[END_REF][START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF][START_REF] Fan | Distributed graph simulation: Impossibility and possibility[END_REF][START_REF] Schätzle | S2x: Graph-parallel querying of rdf with graphx[END_REF][START_REF] Kao | Distributed Incremental Pattern Matching on Streaming Graphs[END_REF][START_REF] Li | A vertex-centric graph simulation algorithm for large graphs[END_REF][START_REF] Fan | Parallelizing sequential graph computations[END_REF].

In this chapter, we show that graph simulation and dual simulation can be both efficiently evaluated by parallel algorithms that achieve linear scalability. Actually, the different algorithms given by [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF][START_REF] Schätzle | S2x: Graph-parallel querying of rdf with graphx[END_REF][START_REF] Kao | Distributed Incremental Pattern Matching on Streaming Graphs[END_REF][START_REF] Li | A vertex-centric graph simulation algorithm for large graphs[END_REF] adopt the vertex-centric paradigm of Pregel [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF]. In Pregel, the data graph is seen as a distributed system where vertices are analogous to computing units that can execute their local programs in parallel and exchange messages with their neighbouring vertices. The algorithm runs in a series of computations separated by a synchronization barrier and message exchanges. An initial message consisting of the query graph is sent to all the data vertices that will store their matching information locally. In each iteration the graph vertices share their matching information or removal messages with their neighbors that update their local matches accordingly.

The distributed algorithm converges when no further messages are exchanged anymore. Nevertheless, the vertex-centric paradigm is limited because it generally exhibits a heavy message passing. Additionally, the natural skew present in real-world graphs does not allow for a higher degree of parallelism. Finally, the vertex-centric paradigm is more suitable for graph algorithms that require data locality. Indeed, data locality is important for graph problems where a large neighbourhood of a vertex is required to evaluate the GPM model, e.g. subgraph isomorphism and strong simulation.

Furthermore, the algorithms proposed in [START_REF] Fan | Distributed graph simulation: Impossibility and possibility[END_REF][START_REF] Li | A vertex-centric graph simulation algorithm for large graphs[END_REF][START_REF] Fan | Parallelizing sequential graph computations[END_REF] adopt partial evaluation in answering graph simulation queries. In partial evaluation, each worker of the distributed system evaluates graph simulation based only on the data stored locally, then, it communicates with a coordinator machine that propagates the newly computed matching information among the workers. At the reception of the matching information of other workers, a worker will update its local matching information accordingly. If there are any updates, another round of message exchange and computations are carried out until the algorithm convergence. Depending on the partitioning strategy adopted, some workers may remain inactive for most of the processing time. Moreover, these works do not provide mechanisms for parallelizing computations on the same machine, hence, limiting the degree of parallelism that can be achieved. These shortcomings motivated our work to propose PGSim and PDSim, two parallel edge-based algorithms to answer GPM queries in parallel for the two models, respectively. Our main contributions are summarized as follows.

(1) We introduce ST, a novel distributed data structure for storing the data graph edges which ensures a high degree of parallelism. ST is composed of basic computing units called STwigs; a set of edges having the same source or the same destination vertex. ST ensures high scalability due to the independence between its elements that can be processed in parallel.

(2) We propose PGSim, an edge-centric algorithm for evaluating graph simulation in parallel on distributed data graphs. To the best of our knowledge, this is the Ąrst work on graph simulation that adopts an edge-centric programming model.

(3) Based on ST and PGSim, we propose PDSim, a fast parallel algorithm for evaluating dual simulation in the same context of massive graphs.

(4) In addition to that, we prove the effectiveness of our approach by giving theoretical guarantees on the correctness of the different algorithms proposed in this chapter.

(5) Furthermore, we propose an implementation of the parallel algorithms on top of the in-memory distributed system Apache Spark [START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF].

(6) Finally, we prove the efficiency of PGSim and PDSim through extensive experiments and compare them to the state-of-the-art vertex-centric approach on different realworld and synthetic data graphs. The obtained results veriĄed that PGSim and PDSim can be ten times faster than their vertex-centric counterparts.

The remainder of this chapter is organized as follows. First, we introduce PGSim in Section 5.2 and give a formal validation of the proposed algorithm. In Section 5.3, we propose the parallel edge-centric algorithm for dual simulation with theoretical guarantees. Finally, Section 5.4 gives the implementation details in addition to the results of experimental evaluation of PGSim and PDSim.

Parallel edge-centric graph simulation

A particularity of graph simulation is that it requires availability of only the matching information from the children of a data vertex to decide whether it is a correct match or not. To design an efficient and scalable algorithm, we consider the fact that only children of a data vertex are required in graph simulation, which allows us to avoid a sequential traversal of the data graph. Exploiting this property will decouple the different parts of the data graph and the computations performed on them, hence, increasing the degree of parallelism. Moreover, the data locality preserved by the vertex-centric programming model is more important for graph problems where a large neighbourhood of a vertex is required to evaluate the GPM model, e.g. subgraph isomorphism and strong simulation. Therefore, this paradigm is more suitable for such problems, but is less accurate for the case of graph simulation because the message passing communication adopted causes a very low speed of computations. Moreover, the vertex-centric paradigm requires message passing even for vertices residing on the same physical machine even though the exchanged In what follows, we introduce the different data structures used by our approach. Then, we present the steps of the parallel algorithm PGSim and give its formal validation.

Data structures

Graph simulation deĄnes a set of matching constraints that must be respected by each data vertex in order to be considered as a correct match for a given query vertex. We deĄne a matching constraint as follows.

DeĄnition 22 (Matching constraint of a vertex). Given a query graph Q = (V q , E q , f q ), the matching constraints of a query vertex u ∈ V q are given as the set of its children in Q. Let C : V q → 2 Vq be the function that maps a query vertex u ∈ V q to its constraints C (u) ⊆ V q . Each edge (u, u ′ ) ∈ E q deĄnes a matching constraint u ′ for u. Consequently, C maps a vertex with zero children to an empty set of constraints.

As an example, the set of constraints of query graph Q 5 are given as ¶C (A) = ¶B, C♢,

C (B) = ¶C♢, C (C) = ¶B♢♢.
Now, let G = (V, E, f ) be a data graph, a data vertex v ∈ V is matched to a query vertex u ∈ V q , if and only if, f (v) = f q (v) and v respects the matching constraints C (u) of u. We say that constraints of u are also constraints of its candidates such that a candidate is a data vertex having the same label as u. Therefore, a data vertex can have multiple constraints that should be met by its children, such that each constraint must be met by one or more of its outgoing edges. These edges sharing the same source vertex are grouped together to form a data structure that we call STwig, which will be deĄned next. Moreover, we call ST, the set of all STwigs extracted from a data graph. An STwig with a non empty match set has its root mapped to at least one query vertex.

Consequently, an STwig that has an empty match set is not a correct match and therefore can be eliminated from ST. Intuitively, an empty STwig can only be mapped to query vertices having an empty set of constraints. Hence, its local match set is initialized but never updated afterwards. Since we deĄned the basic concepts and data structures used by ST, we are now ready to introduce PGSim in the following section.

Parallel graph simulation via PGSim

Our approach for evaluating graph simulation in parallel consists of three points. First, a preliminary phase builds ST off-line by simply grouping the data graph edges that share the same source vertex together. Moreover, vertices without outgoing edges result into empty STwigs. Next, at the reception of an input query graph Q, we extract the set of constraints C in a straightforward way, as they are directly retrieved from the edges of Q.

(∆ O × ♣V q ♣).

Lemma 9. The time complexity of Algorithm

ComputeSTwig is equal to O(Γ × ♣V q ♣).
Proof. The Update program of an STwig t updates M c in at most O(Γ), then it reevaluates graph simulation in O(Γ × ♣V q ♣). Finally, it updates M and I t in O(Γ). Hence, the time complexity of Algorithm ComputeSTwig is O(Γ × ♣V q ♣).

Theorem 9. Algorithm PGSim for evaluating graph simulation in parallel will terminate with time complexity

O(♣V ♣/P × ♣V q ♣ 2 × ♣E♣).
Proof. The data structure ST has a maximum length equal to ♣V ♣. After its construction, it contains exactly ♣V ♣ STwigs. After the Ąrst iteration it gets smaller in size because the reĄne procedure can only remove elements from ST. Algorithm PGSim starts by iterating over ST, the set of STwigs and updating each STwig in parallel. Given P , the number of processors running in parallel, it will take O(♣V ♣/P × ♣V q ♣ × ∆ O ) to Ąnish the loop. After that, the second loop runs for at most ♣E♣ iterations (from Lemma 7) such that in each iteration, it takes O(♣V ♣/P ) to reĄne ST in parallel and O(♣V ♣/P × ♣V q ♣ × Γ) to update the STwigs in parallel. The global match set is extracted in O(♣V ♣/P ). Therefore, the time complexity of Algorithm PGSim in an environment with P processors is

O(♣V ♣/P × ♣E♣ × ♣V q ♣ 2

Parallel edge-centric dual simulation

In this section, we introduce our split-and-combine approach to evaluate dual simulation. We also introduce the parallel algorithm used by this approach, dubbed PDSim, and give theoretical guarantees on its correctness. Dual simulation requires the availability of both the child and parent information to decide on the matching of any data vertex.

In addition, the existing algorithms for dual simulation (whether centralized or vertexcentric) all process the matching information for incoming and outgoing edges of a data vertex sequentially. However, in the case of high degree vertices, this strategy can lead to a load imbalance. Therefore, to address this problem, we run the computations related to the parent constraints and those related to the child constraints in parallel.

Compute ST 1

STwigs by children

A split-and-combine approach for parallel dual simulation

The split-and-combine approach considers dual simulation as a set of constraints of two types: parent-based and child-based constraints. This separation allows generating two types of STwigs, the Ąrst type is the same as the STwig we have seen in PGSim, while the second type is based on the parents of a data vertex v, i.e. each data vertex results into an STwig that groups the edges having v as their destination. In the same way, the empty parent based STwigs have only a root and represent vertices with zero parents in the data graph. This phase is referred to as the Split phase. Figure 5.6 illustrates the different steps of computation followed by Algorithm PDSim for parallel dual simulation.

Algorithm PDSim takes as input the two distributed data structures ST 1 and ST 2 , that were constructed before the Split phase (performed only once for each data graph off-line). The Ąrst ST contains the STwigs based on child relationship and the second one is built based on the parent relationship.

During the Split phase, we execute Algorithm PGSim on ST 1 using C 1 , the child constraints of the input query (Line 3), while a modiĄed version of PGSim that checks the parent constraints C 2 is executed on ST 2 (Line 4). We note that, here PGSim returns the reĄned ST without computing the global match set. At the end of this phase, the two reĄned data structures will have only edges of the data graph respecting the child constraints and parent constraints separately. However, dual simulation requires that the two types of constraints are met by these edges at the same time, hence, we call Algorithm Combine that takes as input ST 1 and ST 2 to Ąnd the match set M of each STwig w.r.t. dual simulation (Line 5).

Algorithm Combine groups the matching information of children M c and parents M p of a given STwig. It also computes a next local match set M by eliminating matches that do not satisfy dual simulation (Line 3). The match set M of a given STwig t is computed as the intersection of the match sets M 1 and M 2 for t in ST 1 and ST 2 , respectively (Lines 4Ű8). Indeed, a data vertex is said to be a match of a given query vertex u w.r.t. dual simulation if and only if it satisĄes the label constraint and both child constraints C 1 (u) and parent constraints C 2 (u). In addition to that, the Ąltered out matches are stored in I and returned by the parallel algorithm.

Nevertheless, the evaluation of dual simulation does not stop here. Actually, the same removal process that we have seen in PGSim must be triggered after each update made to a local match set M in the combined ST to propagate the removed matches across the other STwigs. Therefore, the same routine will be executed such that the set of removed matches I is broadcast at the end of every iteration and dual simulation is reevaluated again (based on both M c and M p ) for each STwig affected by this removal until I becomes empty (Lines 6Ű13 of Algorithm PDSim). Consequently, Algorithm PDSim converges with the correct Ąnal match graph. The global match set M g is then computed in the same way as the match set of graph simulation (Lines 14Ű15).

To illustrate the execution steps of PDSim, we use the same data graph G 5 and query graph Q 5 . The two graphs G s1 of Figure 5.7 and G s2 of Figure 5.8 represent ST 1 and ST 2 , respectively. Let us take the STwig rooted at 6, it has a non-empty local match set M 1 = ¶(B, 6)♢ in ST 1 but that match set M 2 is empty in ST 2 . Intuitively, the local match set of this STwig, named M , should be empty after calling Algorithm Combine because it does not respect the constraints of dual simulation. Indeed, M is given as the intersection between M 1 and M 2 . We should inform the other STwigs of the combined ST about the removal of the match (B, 6). The set of removed matches I contains elements that do not appear in both M 1 and M 2 , i.e., M 1 ⊕ M 2 . Indeed, the local match set of STwig rooted at 6 becomes empty. The remaining iterations of Algorithm PDSim eliminates the STwig rooted at vertex 7. Next, the STwigs rooted at data vertices 5 and 2 will be Ąltered out one after another. The remaining STwigs form the Ąnal match graph given in Figure 5.9.

Convergence and Correctness of PDSim

We give Theorem 11 and Theorem 12 that prove the convergence and correctness of Algorithm PDSim, respectively.

Theorem 11. Algorithm PDSim will terminate with a time complexity O(♣V ♣/P × ♣V q ♣ 2 × ♣E♣).

Proof. PDSim takes the same time complexity to process ST 1 and ST 2 , which results into O(♣V ♣/P × ♣E♣ × ♣V q ♣ 2 ). After that the combine method takes O(♣V ♣/P ) to combine ST 1 and ST 2 , the remaining steps for dual simulation take at most O(♣V ♣/P × ♣E♣ × ♣V q ♣ 2 ) to converge (similar to the evaluation of graph simulation). Moreover, the global match set is extracted in at most O(V /P ). Consequently, the time complexity of Algorithm PDSim is O(♣V ♣/P × ♣E♣ × ♣V q ♣ 2 ).

Theorem 12. Algorithm PDSim returns the correct and complete match set w.r.t. dual simulation.

Proof. The correctness of PDSim is ensured by the following properties. [START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF] The parallel algorithm will terminate (Theorem 11), (2) the parallel algorithm returns the correct match set of dual simulation, (3) the algorithm returns the complete set of matches of dual simulation.

First, we suppose that at the end of the algorithm, there exists an incorrect match (u, v) in the returned match set M g . If (u, v) is an incorrect match, then either the two vertices have different labels or v does not satisfy some of the constraints in C 1 (u) or C 2 (u). The Ąrst case cannot occur because every local match set is initialized with query vertices having similar labels and M g is formed by the union of these local matches. Moreover, the local match set M of the STwig rooted at v in ST is initialized by the intersection of M 1 (only matches satisfying C 1 ) and M 2 (only matches satisfying C 2 ). Moreover, the next iterations of the parallel algorithm always remove the members of M not satisfying dual simulation. Furthermore, the only operations performed on M are removal operations, which ensures that invalid matches cannot be added to M during this stage, hence, the initial supposition is not valid. Therefore, Algorithm PGSim returns the correct matches w.r.t. dual simulation.

Next, we suppose that there exists a correct match (u, v) such that (u, v) is not part of the returned match set M g . A match (u, v) is considered correct if and only if f q (u) = f (u), and v satisĄes the child constraints C 1 (u) and parent constraints C 2 (u). Since we proved the correctness of Algorithm PGSim in Theorem 10, then a correct match is necessarily part of both M 1 (v) and M 2 (v). Therefore, if such match exists, then it has been Ąltered out during the combine phase or removal iterations following it in PDSim. However, the only removals made from the local match set M (v) happen after evaluating dual simulation based on the updated child and parent match sets. Hence, Algorithm PGSim returns the complete matches w.r.t. dual simulation.

Experimental evaluation

In this section, we evaluate the performance of the proposed parallel edge-centric algorithms and compare them to the vertex-centric one. First, we give details on the distributed implementation of ST, PGSim and PDSim. Then, we present the data sets used during the different experiments and give their characteristics. Next, we give the cluster conĄguration used and the environment in which these experiments were carried out. Finally, we present the different sets of experiments and discuss their results.

Distributed implementation of PGSim and PDSim

We implemented the distributed data structure ST on top of Apache Spark [START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF]. Apache Spark is an in-memory data processing framework that offers a distributed computation model based on Resilient Distributed Datasets (RDDs). An RDD is a distributed data structure that can be processed in parallel by applying a transformation on each element of the RDD. The immutability of Spark RDDs guarantees their resilience. If an RDD is lost while the distributed algorithm is running, it will be directly recomputed based on the set of operations that generated it Ąrst, hence allowing Spark to be faulttolerant while avoiding costly I/O operations except for loading the initial RDD. ST inherits the properties of Spark RDDs, which makes it a distributed data structure for in-memory processing on a computing cluster. PGSim is implemented as a series of successive RDD transformations applied to the initial ST. Moreover, we implemented the Split-and-Combine approach of PDSim on top of Spark, using RDDs.

Experimental environment

We use four real-world datasets from SNAP Library [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. Characteristics of these graphs are given in Table 5.1. Unless expressly stated otherwise, the number of distinct labels is Ąxed to ♣Σ♣ = 500.

Furthermore, the R-Mat model [START_REF] Chakrabarti | R-mat: A recursive model for graph mining[END_REF] is used to generate synthetic data graphs. The generator takes as an input ♣V ♣, ♣E♣ and ♣Σ♣ such that ♣Σ♣ is the number of distinct labels. We Ąx ♣E♣ = 20 × ♣V ♣ for all the synthetic graphs generated in these experiments. To extract patterns of different sizes, we use the algorithm given in Section 3.5.3 to extract 50 different patterns randomly for each value of ♣V q ♣.

We executed our experiments on a Spark cluster composed of 10 nodes with 32GB memory and 16 cores for each; one node plays the role of the master while the remaining nodes are considered as workers.

Experimental results

In this section, we present and discuss the results of performance evaluation for PGSim and PDSim in comparison to the state-of-the-art vertex-centric algorithm (VC-GSim) proposed in [START_REF] Fard | A distributed vertex-centric approach for pattern matching in massive graphs[END_REF]. We implemented VC-GSim on top of GraphX [START_REF] Xin | Graphx: A resilient distributed graph system on spark[END_REF], a graph processing system that offers an implementation of Pregel [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF] on top of Apache Spark.

Varying the graph parameters

In this set of experiments, we evaluate the impact of three different parameters, ♣V q ♣; the size of query graph, d; the diameter of the query graph and ♣Σ♣; the number of distinct labels in the data graph, on the performance of PGSim and PDSim. The results are given in Figure 5.10.

First, we discuss the average response time when varying ♣V q ♣. As we can see, the obtained results prove the superiority of our approach. PGSim is faster than VC-GSim for the four real datasets Epinions, Amazon0601, WebGoogle and LiveJournal. The improvement in response time achieved becomes more signiĄcant when the size of the data graph increases. Indeed, PGSim is ten times faster than the vertex-centric version for LiveJournal. Moreover, PGSim is sensitive to the size of the query graph as it increases in a linear curve with respect to ♣V q ♣. On the other hand, the parallel algorithm PDSim for evaluating dual simulation behaves slower than VC-GSim for Epinions, which can be explained by the fact that dual simulation requires more computations to prune out invalid matches compared to graph simulation. However, it takes a shorter time to process queries from the other data sets. Actually, PDSim is very scalable when varying the size of query graphs or when varying the size of datasets, for a massive graph like LiveJournal, PDSimŠs response time is closer to that of PGSim.

Next, we evaluate the behavior of PGSim and PDSim compared to VC-GSim with respect to the diameter of pattern graphs d, using the same data sets. For small to average graphs, we notice that the response time is not affected by d. However, for

LiveJournal, the response time increases slightly w.r.t. this parameter, since the larger d Finally, the number of distinct labels of the data graph ♣Σ♣ is an important parameter that affects generally the size of the initial candidates set. We vary ♣Σ♣ from 200 to 900 for the four real-world data sets. Here, the same query graphs are used with ♣V q ♣ = 9. Moreover, we use the same generated Σ on both data graphs and query graphs for each experiment. We evaluate graph simulation with PGSim and VC-GSim, dual simulation with PDSim and note the average response time. The response time decreases when increasing ♣Σ♣, this is a normally expected behavior for PGSim and PDSim as we use a reĄnement right after the Ąrst iteration of the algorithm to prune out all the data vertices not having a label that exists in the query graph. The number of invalid matches increases when the data graph has a large set of distinct labels and inversely. On the other hand, the change in response time for VC-GSim is slow and the algorithm takes longer time to evaluate graph simulation in the different data sets.

Weak scaling experiment

In this set of experiments, we evaluate the weak scalability of PGSim and PDSim. This type of experiments consists of Ąxing the number of workers/cores of the cluster and increasing the size of the problem, which is the data graph G in our case. We generate synthetic data graphs of different sizes by varying the scale of the R-Mat model from 13 to 22 (resulting to ♣V ♣ that varies from 2 13 to 2 22 ). We report the average response time for running graph simulation and dual simulation over 50 instances of queries having the same size (♣V q ♣ = 9). The results of comparing PGSim and PDSim to VC-GSim are given in Figure 5.11a.

PGSim outperforms VC-GSim by one order of magnitude. We can see how the difference in response time between the two algorithms gets larger when the size of the data graph increases. For the Ąrst data graph having only 7.7k vertices, the two algorithms are very close with 600 ms while PDSim evaluates dual simulation for the same data graph in one second. Nevertheless, when increasing the size of data graphs, PGSim takes only 1.4 seconds to process the largest synthetic graph containing 3.5M vertices and 83.9M edges, while VC-GSim takes 42.6 seconds to get the same result.

Moreover, we can see in Figure 5.11b, the difference between the number of matches returned by graph simulation and dual simulation. PDSim prunes out a big part of the matches returned by graph simulation, which happens during the combine phase along with the remaining iterations that allow the parallel algorithm to converge to the correct match set. Even with these additional computations performed by PDSim, our approach for evaluating dual simulation outperforms signiĄcantly VC-GSim when increasing ♣V ♣. Indeed, it only takes 7.5 seconds to process the largest synthetic graph. Consequently, this set of experiments proves the scalability of our parallel algorithms.

Strong scaling experiment

We test the strong scalability of PGSim and PDSim by Ąxing the problem size (Ąxing the data graph) and varying the number of cores in the cluster. We report the average response time and speedup when evaluating graph simulation and dual simulation, respectively, on 50 instances of query graphs having the same size (♣V q ♣ = 9). We run this set of experiments on the four real-world data sets in addition to synthetic graphs of different size. Figure 5.12 presents the obtained results.

PGSim scales very well with the number of cores. Indeed, the algorithm speedup increases linearly when increasing the number of cores for all the data graphs. We notice that the larger the data graph size, the higher speedups can be achieved. Indeed, the highest speedups of 16 and 18 are achieved by PGSim and PDSim, respectively, on the synthetic graph having the largest size (♣V ♣ = 3.5M and ♣E♣ = 83.9M ). Nevertheless, for remaining data graphs, the speedup curve starts Ćattening after some point due to reaching a maximum level of parallelism. For example, for the three data sets Epinions (Figure 5.12a), Amazon0601 (Figure 5.12a) and WebGoogle (Figure 5.12a), the speedup of the two algorithms increases very fast when adding up 16 to 32 cores. After that, the speedup increases very slowly even when doubling the number of cores used.

The different experiments presented in this section prove the strong scalability of the distributed data structure ST and the two parallel algorithms PGSim and PDSim.

Chapter summary

In this chapter, we proposed PGSim, an efficient parallel edge-centric approach for evaluating graph simulation on distributed graphs. PGSim relies on the distributed data structure ST that groups the edges of the data graph and allows reaching higher degrees of parallelism while avoiding locality issues generally present in the vertex-centric graph algorithms. Moreover, we proposed PDSim, a split-and-combine approach for evaluating dual simulation based on ST and PGSim. We provided theoretical guarantees on the correctness and the convergence of PGSim and PDSim. Moreover, the experimental results proved that the two propositions outperform the vertex-centric graph simulation by one order of magnitude. Therefore, we can use PDSim directly in evaluating BDSim, strong simulation and strict simulation which will guarantee a noticeable improvement in their response time.

Conclusions and Perspectives Conclusion

In this thesis, we addressed the problem of scalability of relaxed GPM models. Graph pattern matching is an important problem in graph theory and it has been extensively studied for the past 50 years with applications almost everywhere. This problem has been widely used for biological identiĄcation through Ąngerprint recognition, retina recognition and face recognition. In addition, intrusion detection is an important application domain where malicious behaviours of programs that are modeled as a pattern are queried against the program dependence graph. Moreover, GPM is being highly used nowadays in social networks for recommendation, expert Ąnding and social community detection.

As a Ąrst part of this manuscript, we studied the different models proposed for formalizing this problem, from subgraph isomorphism, the most stringent model to the most Ćexible ones such as graph simulation and bounded simulation that belong to the category of relaxed GPM. All these GPM models differ both in terms of Ćexibility and tractability, which makes them more suitable for speciĄc application domains than other ones. In the second part, we investigated the use of TLAV programming models and systems in scaling up the existing GPM approaches. Our main contributions are summarized as follows.

First, we proposed a new taxonomy of distributed GPM approaches based on the GPM model and programming paradigm applied. Among the drawn up conclusions, we suggest that the vertex-centric and subgraph-centric programming models are best suited for evaluating GPM models that impose a locality property, since the neighborhood of a single vertex is required in evaluating its matching information. Additionally, strong simulation is considered among the top GPM models that strike a balance between Ćexibility and tractability, which makes it suitable for a wide range of applications.

The second contribution of this thesis is BDSim, a new relaxed GPM model that captures better the topological structure of the query graph while being feasible in cubic time. We showed that BDSim is more stringent than dual simulation allowing it to return accurate answers. It is more Ćexible than subgraph isomorphism, which makes it scalable to massive data graphs. Our model preserves the proximity between query vertices by eliminating cycles of unbounded length from the resulting match graph. Besides, the experimental evaluation of the proposed vertex-centric algorithms for evaluating BDSim allowed us to validate the effectiveness and efficiency of this approach.

As a third contribution, we designed the Ąrst fully distributed vertex-centric algorithms for a scalable evaluation of strong simulation and strict simulation in massive graphs (named D3S and D3S + , respectively). Our approach ensures that the locality ball members perform strong simulation in a distributed way, hence avoiding duplication of the graph data while increasing the algorithm scalability. Moreover, even though our approach still requires exchanging the matching information between the data graph vertices, D3S outperforms prior work signiĄcantly, notably in applications where the vertex similarity depends on multiple attributes. Therefore, unlike previous work that would ship and duplicate all the vertex information, D3S will only require shipping the matching information. Consequently, D3S allows strong simulation to support further extensions on the semantic similarity adopted. Based on the same approach, we designed D3S + as an extension of D3S which inherits its different properties for the evaluation of strict simulation.

Finally, we designed and implemented the Ąrst parallel edge-centric approach for evaluating graph simulation and dual simulation. We proposed the distributed data structure ST that ensures a Ąne-grain parallelism. PGSim, which is our parallel algorithm for evaluating graph simulation, relies on ST that allows it to reach linear scalability and handle the problem of skewed degree distribution present in real-world graphs. Moreover, the vertex-centric programming algorithms would incur heavy message passing even for vertices residing on the same machine, which slows down the processing of a distributed graph and results in many rounds of computation. In contrast, PGSim uses shared memory abstraction to propagate updates along the different rounds of the algorithm. Furthermore, the parallel algorithm PDSim uses a split-and-combine approach based on ST and PGSim to increase the degree of parallelism when evaluating dual simulation. This approach is faster even than the vertex-centric graph simulation. PDSim can be then used as a building block in the evaluation of BDSim and strong simulation. Some of the conclusions of this research work are the following. The new adaptive GPM model BDSim strikes a balance between tractability and Ćexibility while offering guarantees on the preservation of connectivity, duality, closeness and locality of the input pattern graph. Thanks to its conĄgurable parameter ŞkŤ, BDSim can be used for different application needs depending on the required level of Ćexibility. Furthermore, we conĄrmed in this thesis that among the TLAV programming models, no one can be considered the best for designing distributed GPM algorithms for all existing GPM models. As shown by the conducted experiments, our edge-based algorithm for evaluating graph simulation outperforms the vertex-centric version by up to one order of magnitude, hence validating our Ąndings about the importance of all the TLAV paradigms. On the other side, many studies have shown that subgraph isomorphism and strong simulation algorithms are better designed with a subgraph-centric programming model. In fact, the model itself imposes a locality constraint which requires a data vertex to have access to a multi-level neighborhood in order to compute its matching information. Moreover, we proved, through the proposal of a fully distributed vertex-centric algorithm of strong simulation, that the Pregel-based vertex-centric paradigm also gives interesting results with strong simulation when employed properly.

Future directions

Among the perspectives of this thesis, we suggest addressing the following three points.

First, we intend to work on the proposal of parallel algorithms for relaxed GPM in attributed and weighted graphs. Indeed, these graphs carry more information that is currently present in real-world graphs and combining all the available vertex and edge attributes in the matching process guarantees a better reliability in the returned results.

In another research direction, we plan to address another important challenge; relaxed GPM in the context of highly dynamic graphs. We want to answer the following questions regarding the contributions made in this thesis. ŞIn BDSim, will the proposed vertexcentric algorithms remain efficient in highly dynamic graphs?Ť. The next question is ŞHow good can D3S and D3S + perform on frequent graph updates?Ť. A last important question that is worth answering is ŞWhether or not the distributed data structure ST will maintain the same performance when update events arrive at a high frequencyŤ.

Furthermore, learning graph matching has been the subject of several recent studies whether it is addressing subgraph matching and graph matching directly as in [START_REF] Nie | Subgraph learning for graph matching[END_REF][START_REF] Lou | Neural subgraph matching[END_REF][START_REF] Lan | Sub-gmn: The subgraph matching network model[END_REF][START_REF] He | Learnable graph matching: Incorporating graph partitioning with deep feature learning for multiple object tracking[END_REF] or solving problems that are useful in graph pattern matching such as Ąnding the maximum common subgraph between two input graphs as in [START_REF] Bai | Fast detection of maximum common subgraph via deep q-learning[END_REF]. However, these works only focused on subgraph isomorphism that can be rigid for many applications. Therefore, a challenging task in learning subgraph matching is to learn a relaxed model of subgraph matching that will be based on the semantics of the available data. With these considerations, different Ćexibility levels will be permitted depending on the query purpose and the application domain with its own deĄnition of similarity between graphs.

  (a) Undirected simple graph. (b) Undirected labeled simple graph. (c) Directed labeled simple graph. (d) Weighted simple graph.

Figure 1 . 1

 11 Figure 1.1 Illustrative examples of different categories of graphs

G 1 Figure 1 .

 11 Figure1.2 An example of a data graph G 1 containing employees in a professional social network, where labels refer to their jobs and an edge between two vertices means that the source endorsed the destination. The pattern graph Q 1 represents the desired connections between the employees that should be retrieved.

Figure 1 . 3

 13 Figure 1.3 Results of applying subgraph isomorphism between query graph Q 1 and data graph G 1 are colored in blue.

Figure 1 . 4

 14 Figure 1.4 Results of applying graph simulation between query graph Q 1 and data graph G 1 are colored in blue.

Figure 1 . 5

 15 Figure 1.5 An example showing the limitations of graph simulation.

Figure 1 . 7

 17 Figure 1.7 Results of applying strong simulation between query graph Q 1 and data graph G 1 are colored in blue.

Figure 1 . 9

 19 Figure 1.9 Results of applying tight simulation between query graph Q 1 and data graph G 1 are colored in blue while the selected centers are gray.

2 Figure 1 .

 21 Figure 1.10 An example of a labeled data graph G 2 , a query graph Q 2 and the results of bounded simulation where the matched vertices are colored in blue.

Figure 1 .

 1 Figure 1.11 Extensions of graph simulation where the direction of the arrows indicates whether this extension came to restrict further the constraints imposed by graph simulation or to relax them when the arrow is reversed (e.g. URS).

Figure 2 . 1

 21 Figure 2.1 Components of a distributed architecture.

Figure 2 . 2

 22 Figure 2.2 Graph fragmentation based on edge-cut partitioning strategy.

Figure 2 . 4

 24 Figure 2.4 Bulk Synchronous Parallel model.

Figure 2 . 5 Figure 2 . 6 Figure 2 . 7

 252627 Figure 2.5 The vertex-centric paradigm.

Figure 2 . 8

 28 Figure 2.8 Taxonomy of the distributed GPM approaches.

Figure 3 . 1 A

 31 Figure 3.1 A cyclic query with three matches respecting dual simulation.

Figure 3 . 2 A

 32 Figure 3.2 A graph with its Ąve short cycles.

Example 4 .for k = 1 Figure 3 . 3

 4133 Figure 3.3 Example of a query graph Q 3 , a data graph G 3 and the different match graphs resulting from dual simulation G D and BDSim (for both cases k = 1, 2). Q 3 contains one short cycle (c 1 of length 3) that is translated into four cycles of different lengths in G D , colored in orange or blue. Setting k = 2 allows capturing cycles of length up to 6 (Figure 3.3d), while k = 1 limits the answer of BDSim to cycles of exactly the same size as c 1 , i.e. only cycles colored in blue from G D (Figure 3.3e).

Figure 3 . 4

 34 Figure 3.4 The inclusion relationships between BDSim for different values of k (BDSim k ) and the other models subgraph isomorphism (SubISO), dual simulation (DSim) and graph simulation (GSim).

Figure 3 . 5

 35 Figure 3.5 Diagram of the distributed token passing procedure for detecting invalid matches.

1 Super-step 1 : 4 5 Update C p and C c ; 6 7 if R ̸ = ∅ then 8 R 9 Send 15 R

 145678915 At the reception of an initial message whileS l ̸ = ∅, do ; 2 foreach s ∈ S l do 3 if s.f = f alse then Remove s.m from M ; Add s.m to R; msg ← (v,R); R msg to all neighbors ; 10 Vote to halt; 11 Super-step 2 and beyond: At the reception of R msg while M ̸ = ∅, do ; 12 Update M p and M c ; 13 R ← EvalDSim(M, C p , C c , M p , M c ); 14 if R ̸ = ∅ then msg ← (v, R); 16 Send R msg to all neighbors; 17 Vote to halt;

Figure 3 . 6 Exp- 1 :

 361 Figure 3.6 The number of cycles w.r.t. the size of query graph.

Figure 3 . 7

 37 Figure 3.7 Varying the pattern graph size ♣V q ♣ for real datasets Amazon0601 and Live-Journal.

Figure 3 . 8

 38 Figure 3.8 Active vertices during the execution of the distributed algorithms on real-world datasets

Figure 3 . 9 Figure 3 .

 393 Figure 3.9 Varying the size of data graph ♣V ♣ for synthetic graphs, ♣V q ♣ = 9.

Figure 4 . 1

 41 Figure 4.1 Strong simulation

  C♢. Similarly, query vertex C has ¶A, B♢ as parent constraints and ¶D, E♢ as child constraints. Given the data graph G 4 of Figure 4.1b, data vertex 4 is labeled C. Hence, it will only keep constraints related to query vertices labeled C, i.e., C p (C) = ¶A, B♢ and C c (C) = ¶D, E♢ should be maintained locally by vertex 4.

Figure 4 . 2 Figure 4 . 3

 4243 Figure 4.2 Local context of vertex 4

B 1 Super-step 1 : 12 NExample 10 .

 111210 The variable N b is used to reĄne M p and M c for each center c ∈ L b . Algorithm D3S At the reception of I msg while M ̸ = ∅, do; 2 Send v to direct neighbors; 3 Vote to halt; 4 Super-step 2 to d: at the reception of S b while M ̸ = ∅, do; 5 Add new S b to L b ; 6 Send new S b to direct neighbors; 7 Vote to halt; 8 Super-step d + 1: if M ̸ = ∅, then do; 9 if Received S b ̸ = ∅ then 10 Add new S b to L b ; 11 if L b ̸ = ∅ then b ← (v, L b ) Send N b to direct neighbors; 13 Vote to halt; 14 Super-step d + 2: at the reception of N b while M ̸ = ∅, do; 15 Store N b locally; 16 Vote to halt; In Example query graph Q 4 and data graph G 4 , we have the query diameter d = 2

i + 1 .Lemma 4 .

 14 Consequently, a message triggered by a vertex v ′ reaches hop v which has a distance d ′ > d from v after exactly d ′ super-steps. However, the construction of L b takes exactly d + 1 super-steps. Therefore, v cannot receive a center of a locality ball b such that v / ∈ b. Second, we suppose that the algorithm misses a center c for a vertex v and we prove that this cannot happen. A center c is added to L b for data vertex v if and only if: v has a non empty match set, c has a non empty match set, the undirected distance between v and c is ≤ d. We distinguish two scenario cases, c is a direct neighbor of v, it is directly add to L b in Super-step 2 (Line 5) where the new S b is exactly the received S b because L b is empty at the beginning of this super-step. The other case is where c has a distance d ′ > 1 from v. If ′ = 2, then c and v share a common neighbor v ′ , thus, c has already been communicated to v ′ in the Ąrst two super-steps. At the beginning of Super-step 2,v ′ has c in its new S b , hence, it will share it with its direct neighbors including vertex v.In the same way, we prove that c will reach v in d ′ super-steps at most (2 < d ′ ≤ d) and will be added to L b . Algorithm D3S B for discovering the d-neighborhood of a data vertex will terminate.

D3S C 1 Super-step 1 : 3 M 4 M 5 ( 6 if R m ̸ = ∅ then 7 R 8 Send R msg to neighbors ; 9 if M (c) = ∅ then 10 Add c to R c ; 11 16 ( 17 if R m ̸ = ∅ then 18 R 19 Send R msg to neighbors ; 20 if M (c) = ∅ then 21 Remove c from L b ; 22 Example 11 .

 11345678910111617181920212211 At the reception of I msg while M ̸ = ∅, do;2 foreach c in L b do p (c) ← updated M p based on N b ; c (c) ← updated M c based on N b ; M (c), R m ) ← EvalDSim(C, M , M p (c),M c (c)) ; msg ← (c, v, R m ); Remove R c fromL b ; 12 Vote to halt ; 13 Super-step 2 and beyond: At the reception of R msg ; 14 if L b contains R msg .c then 15 Update M p (c) and M c (c); M (c), R m ) ← EvalDSim(C, M , M p (c),M c (c)) ; msg ← (c, v, R m ); Vote to halt; In the data graph G 4 , vertex 5 has the same child match set M c = ¶(1, D), (2, E)♢ and the parent match set M p = ¶(3, A), (5, B)♢ for every center c ∈ L b .

Lemma 6 .

 6 D3S A ). Each locality ball b c centered at vertex c has its own local match set M (c), parent match set M p (c) and child match set M c (c). Furthermore, we evaluate the matching constraints separately and every removal in M (c) triggers a removal message that is propagated among the the members of b c . Algorithm D3S C for evaluating strong simulation will terminate.Proof. The Ąrst super-step of the algorithm simply iterates over the local set L b that has a Ąnite size. Inside this loop, we update the two sets M p (c) and M c (c) by iterating over a Ąnite set N b and updating one element at a time. Procedure EvalDSim iterates over Ąnite sets. Therefore, it will terminate. The remaining operations in the loop body are atomic, hence the loop body will terminate. At the end of this iteration L b is updated in constant time. Therefore, the Ąrst super-step will terminate. In the next super-steps, every data vertex updates its local match sets based on the received removal messages. Removing invalid matches from M p (c) and M c (c) takes constant time. Reevaluating dual simulation for the locality center c also takes Ąnite time. The remaining operations in this super-step are atomic operations of message creation, and removal of invalid elements elements from a Ąnite set L b . Hence, the second super-step will terminate. The maximum number of the remaining super-steps is ♣E♣ in the worst case where a locality ball is composed of the whole match graph G ′ and a removal message is propagated across all the locality ballŠs edges. Consequently, Algorithm D3S C will terminate.

  w.r.t. strong simulation we use the distributed vertex-centric algorithm D3S which is given as the successive execution of D3S A , D3S B and D3S C . MaxPGs returned by strong simulation

Figure 4 . 4 4 . 8 .

 4448 Figure 4.4 Difference between maxPGs returned by strict simulation and the one returned by strong simulation in the case of query graph Q 4 and data graph G ′ 4 .

  Response time w.r.t. ♣V q ♣ Super-steps w.r.t. ♣V q ♣ Messages w.r.t. ♣V q ♣ 6XSHUVWHS DFWLYHYHUWLFHV (d) Actives vertices, ♣V q ♣ = 3 6XSHUVWHS DFWLYHYHUWLFHV (e) Actives vertices, ♣V q ♣ = 9 6XSHUVWHS DFWLYHYHUWLFHV (f) Actives vertices, ♣V q ♣ =15 Response time w.r.t. ♣Σ♣ Super-steps w.r.t. ♣Σ♣ Messages w.r.t. d

Figure 4 Figure 4 . 6 Figure 4 . 7

 44647 Figure 4.5 Performance evaluation of D3S

Figure 5 . 2 Figure 5 . 3

 5253 Figure 5.1 Query graph Q 5

Figure 5 . 4 DeĄnition 24 (DeĄnition 25 (

 542425 Figure 5.4 The set of STwigs extracted from the data graph G 5 . The different STwig roots are colored in gray

Figure 5 . 5 A

 55 Figure 5.5 A running example of PGSim on pattern graph Q 1 and data graph G 1 . We illustrate the initial ST and the different transformations applied by PGSim to get the Ąnal match graph w.r.t. graph simulation. Values of the Ćag b of each match in M (t) are illustrated by two colors; blue for true and red for false

Compute ST 2 Figure 5 . 6

 256 Figure 5.6 The split-and-combine approach for parallel dual simulation

Figure 5 . 7 G 1 Figure 5 . 8 G 2 Figure 5 . 9

 57158259 Figure 5.7 G s1 resulting from ST 1 Figure 5.8 G s2 resulting from ST 2

  Varying ♣V q ♣ (WebGoogle) Varying ♣Σ♣ (LiveJournal)

Figure 5 .Figure 5 .

 55 Figure 5.10 Performance evaluation of the parallel algorithms PGSim and PDSim in comparison to the vertex-centric one VC-GSim when varying the graph parameters: query graph size ♣V q ♣, query graph diameter d and the number of distinct labels ♣Σ♣

  Synthetic graph, scale = 22

Figure 5 .

 5 Figure 5.12 Strong scaling of the parallel algorithms PGSim and PDSim

  33♢ from the match set returned by graph simulation. The dual match graph is the induced subgraph containing only vertices of the data graph G 1 that are already in the dual match relation. For example, even though vertices 26 and 28 belong to the dual match set, the edge linking them is not in the dual match graph because there is no edge with labels (C, B) in Q 1 .

	be a match relation between Q and G
	w.r.t. dual simulation (also called dual match relation). The maximum dual match set
	R d is a dual match relation such that for any dual match relation R, R ⊆ R d .
	The results of evaluating dual simulation on the example of Figure 1.2 are shown in
	Figure 1.6. It removes vertices ¶10,

  The subgraph of G contained in this ball is denoted Ĝ [v, d q ]. Formally, G matches Q via strong simulation, if there exists a vertex v ∈ V

	𝐵	1													𝐸	6
	𝐵	2		𝐴	3				𝐶		4	𝐷	5		𝐵	7
	32	𝐹 𝐵	11	𝐴 𝐴 16	10	33	𝐶 𝐸	9	𝐷	𝐴 12	8	𝐸 𝐸	13 15	𝐷	14	𝐹	27
	𝐶 𝐴 30 31	17	𝐶 19	𝐸	𝐷	𝐷 20 18	𝐸 25	𝐸 21 24 𝐷	𝐷 𝐸 23 22	𝐸	34	26	𝐶	28	𝐵	𝐴 29
	Figure 1.6 Results of applying dual simulation between query graph Q 1 and data graph
	G 1 are colored in blue.
	such that:

Table 2 .

 2 1 Distributed graph pattern matching approaches.

	Work Year Model	Timing Execution model size of graph
	[12]	SubIso	Async. Master-slave	778M edges
	[122] SubIso	Async. Master-slave	1B nodes
	[40]	SubIso	BSP	Vertex-centric	100K nodes
	[48]	Inexact SubIso BSP	Vertex-centric	105M nodes
	[113] SubIso	BSP	Vertex-centric	42M nodes
	[96]	SubIso	BSP	Master-slave	1.3B nodes
	[102] Inexact SubIso Async. Vertex-centric	68B nodes
	[104] SubIso	Async. Vertex-centric	137B nodes
	[119] SubIso	Async. Vertex-centric	400 nodes
	[37]	SubIso	BSP	Master-slave	65M nodes
		Graph sim.

  and some join-based algorithms process the data graph edge by edge. Their distributed version

					(Peng et al., 2016)
				Subgraph ISO
			BSP		(Fan et al., 2018)
				Graph Sim	(Fan et al., 2018)
		Master-Slave		Subgraph ISO	(Bröcheler et al., 2010)
					(Sun et al., 2012)
					(Ma et al., 2012)
			Async.	Graph Sim
					(Fan et al., 2014)
					(Ma et al., 2011)
				Strong Sim
					(Wang et al., 2018)
	GPM				(Filip et al., 2014)
	of Distributed		BSP	Subgraph ISO Graph Sim	(Gao et al., 2014) (Shao et al., 2014) (Fard et al., 2013) (Li et al., 2018)
	Taxonomy	Vertex-centric		Dual Sim Strong, strict, tight Sim Relaxation Sim	(Schätzle et al., 2015) (Fard et al., 2014) (Gao et al., 2016)
					(Reza et al., 2017)
					(Stein et al., 2018)
			Async.	Subgraph ISO
					(Reza et al., 2019)
					(Reza et al., 2020)
		Subgraph-centric	BSP	Graph Sim	(Kao et al., 2016)

Table 3 .

 3

1 Different possible BDSim matches in data graph G 3 for cycles in Q 3 when k = 2 and k = 1.

Table 3 .

 3 2 Notations used in the distributed algorithms of BDSim

	Object	Notation
	Local vertex ID	v
	Parent and child constraints	C p , C c
	Local, parent and child match sets	M, M p , M c
	Set of locally removed query vertices R
	Data message, removal message	D msg , R msg
	Set of global seeds	S g
	Set of local seeds	S l
	A short cycle in S g or S l	c i
	Length of a short cycle c i	l i
	A seed	s
	The short cycle corresponding to s	s.c
	The matched query vertex of seed s	s.m
	Position of s.m in s.c	s.p
	Direction of s.m in s.c	s.d
	Next hop after vertex s.m in s.c	s.h
	Received tokens Ćag for s	s.f
	A token	t
	The next matched vertex in t	next
	A token expiration value	exp

  Ćag f to indicate if the vertex has received tokens for this seed or not.A data vertex matching one or more query vertices in c i keeps the set of their seeds locally in S l . Then, guided by S l , it will send or forward tokens only to neighbors that can be part of the currently explored cycle c i , i.e. only data vertices matched to the next hop vertex in c i . In the query graph of Figure3.3a, there is one short cycle c 1 composed of query edges[START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF][START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF],[START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF][START_REF] Afrati | Enumerating subgraph instances using map-reduce[END_REF] and[START_REF] Abuhaiba | Offline signature veriĄcation using graph matching[END_REF][START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF]. The set of global seeds is therefore given asS g = ¶(c 1 , 1, 0, OU T, 3, f alse), (c 1 ,3, 1, IN, 4, f alse), (c 1 , 4, 2, IN, 1, f alse)♢ where OUT and IN indicate whether the vertex is considered as a source or destination in this cycle, respectively.

	(1) The cycle identiĄer c i , (2) The query vertex identiĄer m , If (local match set ∩ set of seeds ≠ ∅), store the Yes Token expired Dual match graph G D intersection locally For each local seed : generate and send a token to eligible neighbors Set of global seeds S g At the reception of token t Drop token and vote to halt Yes No Self-generated token? (3) The position of m in O Example 6. No Update Update token and token flag forward it to eligible and vote to halt neighbors

). The set of seeds S g is a data structure maintained by the graph data vertices to guide the token passing procedure. An element of S g is called a seed, and it represents a matching query vertex m in the short cycle c i ∈ ζ. Moreover, a seed is composed of multiple Ąelds that are deĄned as follows. Given the sequence of ordered vertices O i = ¶m 1 , m 2 , . . . , m n ♢ in c i , we keep for each vertex m in c i . i , given as p,

[START_REF] Ammar | Distributed evaluation of subgraph queries using worst-case optimal low-memory dataĆows[END_REF]

The direction of m in its edge, given as d,

[START_REF] Anwar | Anomaly detection in electric network database of smart grid: Graph matching approach[END_REF]

The next hop after m in O i , given as h and, (6) A

Table 3 .

 3 3 Characteristics of the data graphs used in the different experiments

	Dataset (G)	♣V ♣	♣E♣ ♣Σ♣
	Amazon0601	403,394	3,387,388	10
	LiveJournal 4,847,571 68,993,773 100

Table 4 .

 4 1 Characteristics of the data graphs used in the different experiments

	Dataset (G)	♣V ♣	♣E♣
	Epinions	75,879	508,837
	Amazon0601	403,394	3,387,388
	WebGoogle	875,713	5,105,039
	LiveJournal 4,847,571 68,993,773

  DeĄnition 23(STwig). Given a data graph, each vertex in this graph generates an STwig structure. Every STwig is composed of the set of outgoing edges from this vertex, that we refer to as root. The destination vertex of each edge is considered a child of this STwig.An STwig has exactly one root but it can have zero or more children. An empty STwig is an STwig that has a root but no children, it represents an isolated data vertex or a data vertex with no children.The set of STwigs related to our data graph G 5 is illustrated in Figure5.4. PGSim processes these STwigs in parallel to evaluate graph simulation.

  DeĄnition 26(ST). The set of all STwigs of a given data graph are stored in the distributed data structure ST. Each STwig in ST is mapped to a local context composed of a match set M and a child match set M c .ST is constructed off-line from the initial data graph and then processed in parallel. Furthermore, the global match set for graph simulation is deĄned as follows.DeĄnition 27 (Global match set). Given a query graph Q, and ST, the distributed set of STwigs extracted from data graph G. We compute the union of all the local match sets in ST w.r.t. C , the set of constraints of Q. If there is at least one constraint in C that is not present in this union, the global match set M g is ∅. Otherwise, it is given as this union.

  Finally, we compute the global match set w.r.t. graph simulation based on ST and C .We give Algorithm PGSim that takes as input ST and C . It is an iterative algorithm that applies a set of transformations on the initial ST, resulting each time to a new reĄned data structure that is closer to the Ąnal match graph. Each iteration of PGSim transforms a given STwig by updating its local match set M in addition to its child match set M c in parallel. The parallel algorithm executes two categories of steps (iterations); the initialization step and the computation steps. After its convergence, PGSim extracts the global match set M g from the reĄned ST, also in parallel.Back to the example of query graph Q 5 and data graph G 5 . At the end of the Ąrst iteration, the two STwigs rooted at 8 and 9 have both empty match sets, consequently, they are eliminated during the reĄnement phase of the ST before the next iteration. Since I is not yet empty, a second iteration of computation starts where each STwig in the reĄned ST updates its child match set based on the invalid matches of I. For example, both STwigs rooted at data vertices 6 and 7 are affected by the previous iteration. Actually, the child constraint for the STwig rooted at 6 is ¶C♢, but since the two children ¶8, 9♢ were Ąltered out, it eliminates them from its local M c . Nevertheless, the third child 5 has a valid match, therefore, the local match set remains the same. The same thing applies for the STwig rooted at vertex 7 that updates only its local M c without changing its local match set (see the updated ST in Figure5.5). At the end of this iteration, I remains empty which announces the end of the parallel algorithm in only two iterations. The global match set is the union of the local match sets for the

the global match set M g is computed based on the Ąnal match set of each remaining STwig in ST (Lines 15Ű16).

  ). However, the Ąrst case is impossible because M (t) is initialized in Procedure InitMatch with only query vertices that share the same label. Moreover, if v does not satisfy C (u), it should have been already Ąltered out in the initialization program of t where we evaluate graph simulation through Procedure GraphSim, or during the following iterations where the matching constraints are reevaluated at every childŠs update. Furthermore, the only operation performed on the initial match set is removal, thus, M (t) contains correct matches at the end of PGSim.One can verify that M g contains the complete matches w.r.t. graph simulation as follows. Actually, we are sure that any correct match necessarily belongs to the initial match set of a given t that was generated by Procedure InitMatch for every single data vertex v in the data graph. Next, we suppose that PGSim Ąlters out incorrectly a correct PGSim returns the complete match set M g for graph simulation.

	Theorem 10. Algorithm PGSim computes the correct and complete match set w.r.t.
	graph simulation.

Proof. The correctness of PGSim can be veriĄed by the following. (1) the parallel algorithm terminates (Theorem 9), (2) the parallel algorithm computes the correct matches w.r.t. graph simulation and (3) the parallel algorithm returns the complete set of matches w.r.t. graph simulation.

To prove the second property, we suppose that at the end of the parallel algorithm, there exists a match (u, v) ∈ M g not satisfying the constraints of graph simulation for u ∈ V q . If (u, v) ∈ M g , this means that at the end of PGSim, the STwig rooted at v has u in its local match set M (t). If (u, v) does not satisfy graph simulation, then, either u and v do not have the same label or v does not satisfy the set of constraints C (u). match (u, v) from local M (t). For any STwig t ∈ ST , M (t) is only updated inside Procedure GraphSim and the only removal of (u, v) made happens when C (u) are not satisĄed anymore. Therefore,

Table 5 .

 5 1 Characteristics of the data graphs used in the different experiments

	Dataset (G)	♣V ♣	♣E♣
	Epinions	75,879	508,837
	Amazon0601	403,394	3,387,388
	WebGoogle	875,713	5,105,039
	LiveJournal	4,847,571	68,993,773
	Synthetic	up to 3,504,383 up to 83,886,080

The RDF format stands for Resource Description Framework, which is a graph data model for describing graphs using a set of triples of the form: subject-predicate-object.

return ST ;

Acknowledgements

I would like to thank my three supervisors without whom the completion of this project would not have been possible. Thank you Prof Hamamache Kheddouci and Dr Nadia Nouali for your support and guidance throughout my four years of PhD. Your vision and

Algorithm VC-DSim

1 Super-step 1: At the reception of Q, do; messages will be generated, announcing the end of the distributed algorithm. The dual match graph is therefore the same as G D given in Figure 3.3c.

Algorithm VC-TPass

1 Super-step 1: At the reception of S g while M ̸ = ∅ , do; 2 foreach s ∈ S g where M contains s.m do 3 Add s to S l ;

) // Filter out vertices and edges not having a match in

To show how strict simulation reduces the size of locality balls, we use data graph G ′ 4 given in Figure 4.4 and the query graph Q 4 . Strong simulation returns two maxPGs composed of the whole data graph except data vertex 15 (Figure 4.4c). This is due to the additional edge (4, 9) that allowed data vertices 4 and 9 to Ąnd the same large maxPG inside their locality balls. However, since strict simulation is based on the match graph resulting from dual simulation, this particular edge will be removed, because no edges labeled (C, C) are present in Q 4 . Now, we build the data locality balls on top of this Ąltered graph, which results into only one maxPG given in Figure 4.4b. The locality balls collected by vertex 4 in strong simulation and strict simulation are ¶1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14♢ and ¶1, 2, 3, 4, 5, 6, 7, 8, 10♢, respectively. Evaluating strong simulation on the Ąrst locality ball gives the maxPG composed of data vertices ¶1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14♢, while strict simulation does not Ąnd any matches inside the second ball. This example proves that not only the locality balls are smaller in size but also the quality of results is always similar or better.

Experimental evaluation

We conducted our experiments on real and synthetic data sets. The goal is to measure the performance of D3S and D3S + , identify their bottlenecks and compare them to an algorithm from the state-of-the-art.

Distributed implementation

We implemented the two algorithms D3S and D3S + on top of GraphX using the programming language SCALA. GraphX [START_REF] Xin | Graphx: A resilient distributed graph system on spark[END_REF] is a module provided by Apache Spark that allows vertex-centric graph processing through its exposed API of Pregel [START_REF] Malewicz | Pregel: A system for large-scale graph processing[END_REF].

Algorithm

Initialization step

During the initialization (Algorithm InitializeSTwig), we evaluate for each STwig t its local match set based on the root label and the different children labels only. Each STwig runs a local program in parallel where it initializes the children match set M c (Call of Procedure InitMatch in Lines 3Ű5) and its local match set M (Call of Procedure InitMatch in Line 6). Initially, M is composed of matches based only on the label constraint. Then, t veriĄes for each match in M (a pair (u, v)) whether the child constraints are respected or not by assigning a true or false value (Call of Procedure GraphSim in Line 7). The Boolean Ćag b attached to each pair (u, v) indicates whether this pair passes the child constraints or not. The matches that do not pass child constraints are collected in I and returned by the parallel algorithm (Lines 6Ű12). For now, an STwig root does not know whether its children satisfy the child constraint themselves or not, so here, I allows us to update the local child match set M c . After that, the local match set M must be recomputed based on the new M c . After the initialization, Algorithm PGSim reduces the size of ST by invoking Procedure Refine (Line 7) that removes from ST all the STwigs having an empty local match set. Procedure GraphSim takes both M (t) and M c (t) in addition to the set of constraints C as input parameters and veriĄes for each pair (u, v) in M (t) whether there exist children of t that are matched to C (u). If at least one constraint in C (u) remains unmatched, (u, v) is mapped to b = f alse, otherwise the match Ćag b is set to true.

Procedure

In the example of query graph Q 5 and data graph G 5 , PGSim starts by building the initial ST data structure from G 5 where each vertex in G 5 results into an STwig. The initial ST contains the two types of STwig described earlier, i.e. seven non empty STwig and two empty STwig. In the initialization step, each STwig computes its local match set M and children match set M c . Then, it updates M based on M c which gives the local matches shown in Figure 5.5. The two empty STwigs rooted at 8 and 9 are initially mapped to query vertex C during the initialization phase. However, C has a child constraint that requires a vertex to have at least one of its children matched to query vertex B, but both STwigs are empty (they do not have any children), hence their initial matches become invalid (they are colored in red) and therefore will be broadcast and added to I, the global set of invalid matches for this Ąrst iteration of the parallel algorithm.

Computation steps

A computation step starts if the set of invalid matches I is not empty. I is composed of the pairs (u, v) in every local match set M that did not pass the child constraints (Lines 8Ű13 in Algorithm InitializeSTwig). Consequently, the STwigs having a non Algorithm InitializeSTwig

Convergence and Correctness of PGSim

First, we prove the convergence of the proposed algorithm through the following Lemmas.

Lemma 7. The maximum number of super-steps to run PGSim is ♣E♣.

Proof. In the worst case, we have a successive elimination of matches one by one, such that only one match is Ąltered out in each iteration. A removed match in a given STwig is only propagated to its childrenŠs STwigs and such removal information can propagate over a path from the Ąrst removed STwig to cross all the edges of G. Therefore, the maximum number of iterations is equal to ♣E♣.

Let ∆ O be the maximum out degree of G and Γ be the maximum size of a local match set. We know that Γ ≤ l q where l q ≤ ♣V q ♣ is the highest label frequency in Q.

Lemma 8. The time complexity of Algorithm

Proof. The Initialize program of a given STwig t initializes the match set of every child in t in O(∆ O × ♣V q ♣), then it initializes the match set of its root in O(♣V q ♣). After that, The Split-and-Combine approach increases the degree of parallelism because Ąrst, we process the two distributed data structures ST 1 and ST 2 in parallel, which prunes out invalid matches as early as possible. After that, the remaining computations are also performed in parallel on a much smaller ST.