Faaiz Shah
email: faaiz.shah@lirmm.fr

Arnaud Castelltort

Anne Laurent

Handling Missing Values for Mining Gradual Patterns from NoSQL Graph Databases

Keywords:

Graph databases (NoSQL oriented graph databases) provide the ability to manage highly connected data and complex database queries along with the native graph-storage and processing. A property graph in a NoSQL graph engine is a labeled directed graph composed of nodes connected through edges with a set of attributes or properties in the form of (key : value) pairs. It facilitates to represent the data and knowledge that are in form of graphs. Practical applications of graph database systems have been seen in social networks, recommendation systems, fraud detection, and data journalism, as in the case for panama papers. Often, we face the issue of missing data in such kind of systems. In particular, these semi-structured NoSQL databases lead to a situation where some attributes (properties) are filled-in while other ones are not available, either because they exist but are missing (for instance the age of a person that is unknown) or because they are not applicable for a particular case (for instance the year of military service for a girl in countries where it is mandatory only for boys). Therefore, some keys can be provided for some nodes and not for other ones. In such a scenario, when we want to extract knowledge from these new generation database systems, we face the problem of missing data that arises need for analyzing them. Some approaches have been proposed to replace missing values so as to be able to apply data mining techniques. However, we argue that it is not relevant to consider such approaches because they may introduce biases or errors. In our work, we focus on the extraction of gradual patterns from property graphs that provide end-users with tools for mining correlations in the data when there exist missing values. Our approach requires first to define gradual patterns in the context of NoSQL property graph and then to extend existing algorithms so as to treat the missing values, because anti-monotonicity of the support can not be considered anymore in a simple manner. Thus, we introduce a novel approach for mining gradual patterns in the presence of missing values and we test it on real and synthetic data.

Introduction

With the provision of ever increasing data rates on Internet and open source technologies to the end users, it has become an increasingly challenging for many enterprises to process large volumes of data in an efficient manner. In some cases, traditional database management systems may not be able to store, process, manage, and analyze data to get insight of data for efficient decision making. Data mining involves collecting, cleaning, processing and gaining useful insight from data. Its applications are often closely related to one of the four main problems i.e., pattern mining, clustering, classification and outlier analysis [START_REF] Aggarwal | An introduction to data mining[END_REF]. Frequent pattern mining is a process in which the data patterns having more occurrences than a predefined threshold mined. It is one of the most investigated domain in data mining [START_REF] Aggarwal | Frequent pattern mining algorithms: A survey[END_REF]. Frequent pattern mining has rapidly extended from in transactional databases analysis to the analysis of complex structures having numerical attributes such as sequences, trees or graphs.

Association rule mining is generally referred to as frequent itemset (pattern) mining and it is used to discover the association rules (X → Y ) between items in transactional data. For mining quantitative data, [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF] proposes a new type of rules to express a kind of "tendency" aka a gradual dependence between attributes. [START_REF] Hüllermeier | Association rules for expressing gradual dependencies[END_REF] present a first interpretation of "gradual dependency" as co-variation constraint such that "the more A, the more B holds if an increase in A comes along with an increase in B". Therefore, a gradual dependency is defined as a pair of gradual itemsets on which a causality relationship is imposed [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF].

Gradual pattern mining is an extension of frequent pattern mining. Gradual pattern mining is the process of discovering knowledge from databases as comparable attributes of co-variations. In linguistic expression, it may be represented as, "the more/less the value of X i ,. . . , the more/less the value of X n ", where i = 1, 2, 3...n, and X 1 , X 2 , X 3 , . . . to X n are numerical ordinal attributes [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF]. These co-variations can be increasing or decreasing and these co-variations can be between two or more than two attributes such as: "The higher the age, the higher the salary, the higher the tax" or "The more the intensive-diet, the less the physical-activity-hours, the more the weight". A gradual pattern is considered as interesting pattern if it occurs frequently i.e., the support of that pattern is greater than the given threshold (minimum support).

Efficient mining of gradual patterns from large numerical databases is a non-trivial task. In particular, when considering the scalability issues due to ever increasing volume of data in enterprises. The application of gradual patterns mining can be found in various fields ranging from applications for analyzing client databases for marketing purposes, analyzing patient databases in medical studies, analysis of climate and environment change. The existing gradual pattern mining techniques presented in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF][START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] are mainly for relational databases while some other types are emerging, as for instance property graphs.

NoSQL graph database engines are purpose built systems to store nodes and edges natively. Nodes or vertices (data entities) are created and linked through edges, that results in much faster query response for this linked data. The increasing need for such systems has been observed in use cases including "social networks, recommendation engines, knowledge graphs, fraud detection, network and IT operations, and life sciences" [START_REF] Bebee | Amazon neptune: Graph data management in the cloud[END_REF]. In recent years, graph data management and mining is gaining a lot of interest in database research community due to its pervasiveness in the fields such as, social networks, knowledge graphs, genome and scientific databases, medical and government record [START_REF] Khan | Summarizing static and dynamic big graphs[END_REF].

A property graph data model is a graph structure containing nodes and edges with properties/attributes in form of (key:value) pairs. Nodes have Labels that define the role of a node. Edges between two nodes have a Type; they are directional and may contain (key:value) properties as nodes. As shown in Figure 1, P atient, Doctor, M edicine are node labels, whereas T akes, V isits and Advises are edge types. A node can have one or more labels at the same time such as nodes with label P atient and Doctor.

Graph modeling is generally an iterative process. For building a property graph model, labels and relevant properties are assigned to nodes. Then we identify and assign the edges between these nodes and the possible properties that they can have. Property graph data model enables us to represent the data in a natural way. It allows the flexibility to incorporate schema changes as and when required because it does not require a fixed schema prior to the database creation. Hence, they are also referred to as When trying to extract gradual patterns from a property graph, all the properties of a node may not be present. This is due to the reason of semi-structured nature of property graphs and often they do not have predefined schema. For example, Patient's age or lab-tests information may be missing for some nodes. So, regular algorithms can not be applied and the problem can be seen as a problem of handling missing data.

The research is being actively pursued for last one decade in gradual pattern mining such as mining the patterns from large numerical tabular datasets as well as addressing the scalability issues [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF][START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF][START_REF] Ayouni | Fuzzy gradual patterns: What fuzzy modality for what result?[END_REF][START_REF] Quintero | Fuzzy orderings for fuzzy gradual patterns[END_REF][START_REF] Do | PGLCM: efficient parallel mining of closed frequent gradual itemsets[END_REF][START_REF] Ayouni | Fuzzy set-based formalization of gradual patterns[END_REF][START_REF] Laurent | Efficient parallel mining of gradual patterns on multicore processors[END_REF][START_REF] Ngo | Mining spatial gradual patterns: Application to measurement of potentially avoidable hospitalizations[END_REF]. Also, the existing gradual pattern mining techniques presented in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF][START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF][START_REF] Do | PGLCM: efficient parallel mining of closed frequent gradual itemsets[END_REF] are mainly for tabular databases while some other types are emerging, as for instance property graphs.

To the best of our knowledge, the extraction of gradual patterns from property graphs is a novel idea. The objective of this work is to address the following two main aspects:

(1) Defining gradual patterns in the context of property graphs;

(2) Mining gradual patterns automatically from property graphs.

In order to achieve these objectives, we address the issue of missing data that arises as a consequence when we are mining graph data.

There may be several ways to define gradual patterns in the context of property graphs. For example, Intra-Node-Label gradual patterns, Inter-Node-Label gradual patterns, Node-properties-with-Edges-count gradual patterns, and Inter-Edge-properties gradual patterns. The focus of this paper is on two types i.e., Intra-Node-Label and Node-properties-with-Edges-count gradual patterns. The details of pattern extraction for these two scenarios are presented with relevant examples and experimental results on real and synthetic datasets.

The paper is organized as follows. Section 2 describes the preliminary concepts about gradual patterns, property graphs, missing data types and their handling techniques. Section 3 presents the problem statement. In section 4, we present our proposed approach for mining gradual patterns in presence of missing data, particularly in the context of property graphs. In section 5, we show experimental results and comparisons of proposed approach with imputation technique. Section 6 presents conclusion and future perspectives.

Preliminary Concepts

In this section we explain gradual patterns mining and property graphs with relevant examples. Later on, we present briefly about the types of missing data and their treatment approaches in literature.

Gradual Pattern Mining

The objective of gradual pattern mining is to discover frequent co-variations of the form "the more/less the X i , . . . , the more/less theX n ", between two or more attributes such as: "The higher the age, the higher the salary, the higher the tax" or "The more the intensive-diet, the less the physical-activity-hours, the more the weight". Gradual item and gradual pattern (aka gradual itemset) defined in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] are given as below.

Definition 2.1 (Gradual Item). Let τ be a set of items, i ∈ τ be an item and ∈ {↑, ↓} be a comparison operator. A gradual item i is defined as an item i associated to an operator .

Consequently, a gradual pattern is defined as follows: Definition 2.2 (Gradual Pattern). A gradual pattern P = (i 1 1 , . . . , i k k ) is a non empty set of gradual items. A k-itemset is an itemset containing k gradual itemsets.

Example 2.1. For example, let us consider the pattern "the higher the age, the higher the number of medications", formalized by the itemsets from Figure 1 are:

P 1 = (Age ↑ , N umberof M edications ↑)
In [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF], a precedence graph based algorithm for gradual pattern mining was proposed. In this method, every pattern of size n being processed is associated with an (n * n) binary matrix representing the order relations between tuples regarding that particular pattern. [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] uses vertical bitmap representation presented in [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF] to store the ordering in the binary matrix. It states, "if there exists an order relation between two tuples a and b, then the bit corresponding to the line of a and the column position of b is set to 1, and to 0 otherwise". For instance, Table 1 shows the example data of patients. When considering the pattern Age ↑, we have from this table that p3(Age30) precedes p2(Age35) which precedes p5(Age55), etc. This results in the fact that the value at the intersection between p3 and p2 in the matrix from Figure 2 (third line, second column) is 1 (in red bold font).

p1 p2 p3 p4 p5           p1 0 0 0 1 0 p2 1 0 0 1 1 p3 1 1 0 1 1 p4 0 0 0 0 0 p5 1 0 0 1 0 (Age ↑) p1 p2 p3 p4 p5           p1 0 0 0 0 1 p2 1 0 0 1 1 p3 1 1 0 1 1 p4 1 0 0 0 1 p5 0 0 0 0 0 (Lab-tests ↑)
When considering gradual patterns with several attributes, as for instance (Age ↑, Lab-tests ↑), the binary matrices of (Age ↑) and (Lab-tests ↑) are mixed to compute the resulting matrix as the Hadamard product. For instance, Figure 3 shows the precedence graph in which p3 (Age 30, Lab-tests 5) precedes p2 (Age 35, Lab-tests 7) because we both have 30 < 35 and 5 < 7 following the pattern (Age ↑, Lab-tests ↑) but p1 and p4 are incomparable as 45 < 55 but 13 > 10. This can also be seen in the matrix representation of Figure 4. Indeed, in the matrix the cells [p1][p4] and [p4][p1] are set to 0 which means that there is no order relation defined between p1 and p4.

The algorithm [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] exploits the rank correlation for gradual pattern extraction. It uses Kendall's tau rank correlation method of concordant and discordant pairs in order to mine gradual pattern. Kendall's tau is one of the most widely used non-parametric test to measure the associa-

p1 p2 p3 p4 p5           p1 0 0 0 0 0 p2 1 0 0 1 1 p3 1 0 0 1 1 p4 0 0 0 0 0 p5 0 0 0 0 0 (Age↑ , Lab-tests↑) p1 p2 p3 p4 p5           p1 0 1 1 0 0 p2 0 0 0 0 0 p3 0 0 0 0 0 p4 0 1 1 0 0 p5 1 1 1 0 0 (Age↓ , Time-in-hospital↓)
p1 p2 p3 p4 p5           p1 0 0 0 0 1 p2 1 0 1 1 1 p3 1 0 0 1 1 p4 1 0 0 0 1 p5 0 0 0 0 0 (Time-in-hospital ↑) p1 p2 p3 p4 p5           p1 0 1 1 1 0 p2 0 0 0 0 0 p3 0 1 0 0 0 p4 0 1 1 0 0 p5 1 1 1 1 0 (Time-in-hospital ↓)
Figure 5: Binary matrix representing orders for the dataset shown in Table 1 tion between two variables for rank correlations [START_REF] Papaioannou | Inequalities on Rank Correlation with Missing Data[END_REF]. The algorithm [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] uses binary matrices for representing orders as shown in Figure 5. It first presents the definition of gradual dependency based on the order concordance [START_REF] Berzal | An alternative approach to discover gradual dependencies[END_REF] in the context of ranking comparison measure and then computes the support. Referring to Theorem 1 in [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF] that a gradual pattern P for gradual items e.g., ( i 1 ↑ , i 2 ↓ ) can be generated, if the following relation holds :

P = (i 1 ↑ AND i 2 ↓)
The computation of binary matrices representing the set of concordant object pairs for gradual patterns (Age↑ AND Lab-tests↑) and (Age↓ AND Time-in-hospital↓) is shown in Figure 4. In order to enhance the performance of algorithm [START_REF] Di-Jorio | Mining frequent gradual itemsets from large databases[END_REF], a scalable implementation is presented in [START_REF] Do | PGLCM: efficient parallel mining of closed frequent gradual itemsets[END_REF] in which parallelism is exploited by employing multi-core processors for mining gradual patterns.

Property Graphs

A property graph helps to represent the information and knowledge in a natural way in form of graph-like structure. A NoSQL database engine is a system specifically designed to store, manage, and process such kind of graph-like data. Such kind of systems are gaining attention as mentioned in [START_REF] Sakr | Querying graph databases: An overview[END_REF] "increasing usage of graph data structure for representing data in different domains such as: chemical compounds, multimedia databases, social networks, protein networks and semantic web". Today, the well known NoSQL database systems are: Amazon's Neptune [START_REF] Amazon | Amazon neptune: Fast, reliable graph database built for the cloud[END_REF], Microsoft's Cosmos [START_REF]Azure cosmos db: Globally distributed, multi-model database service[END_REF], Titan [START_REF] Aurelius | Titan: Distributed graph database[END_REF], and Neo4j [START_REF]Neo4j, Neo4j -the fastest path to graph success[END_REF]. Neo4j is an open source NoSQL native graph database engine. Typically, a property graph does not have a predefined schema, therefore, the changes in graph can be incorporated as and when required. To present the definitions, we create a running example property graph in Neo4j as shown in Figure 6. The summary of labels with their properties and node count is given in Table 2 and Table 3 shows the summary about edge types. The definitions for property node, property edge, and property graph introduced in this paper are given as follows.

Definition 2.3 (Property Node). Let Λ N be a set of node Labels with N U LL ∈ Λ N , Π N be a set of properties where every property π ∈ Π N can take values over a domain dom(π). P N is the set of all possible pairs (π, v) with v ∈ dom(π). A property node n is given by the tuple (id n , Λ n , P n ) with

• id n the unique identifier of n,

• Λ n ⊆ Λ N the set of labels defining the node,

• and P n ⊆ P N is the set of properties of n. take values over a domain dom(π). P R is the set of all possible pairs (π, v) with v ∈ dom(π). A property oriented relation r is given by the tuple (id r , n 1 , n 2 , λ r , P r ) with

• id r the unique identifier of r,

• n 1 ∈ N , • n 2 ∈ N , • λ r ∈ Λ R the Type of the relation, • and P r ⊆ P R is the set of properties of r. Example 2.3. Λ R = { PUBLISH, RCV GRAN T , CO- LAB. }, Π R = {since, NULL}, r 1 = (4213,
{Person}, {Person}, {COLAB.}, {(since:2017)} is a property relation as shown in Figure 7.

Definition 2.5 (Property Graph). Let Λ N be a set of node Labels with N U LL ∈ Λ N , Π N be a set of properties of node, P N a set of (key:value) pairs over Π N , Λ R be a set of edge Types with N U LL ∈ Λ R , Π R be a set of properties of edge, P R a set of (key:value) pairs over Π R .

A property graph G is given by (N, R) where:

• N stands for a set of property nodes defined over Λ N and P N ,

• R stands for a set of property edges defined over N , Λ R and P R .

Neo4j uses "Cypher' ', a declarative query language that uses ASCII-art syntax. Cypher uses specific clauses to perform queries on graph database. An example Cypher query to find a node labeled Person, whose name property value is 'John' and who publishes a journal paper can be written as:

1 MATCH ( p : Person ) -[ v : PUBLISH ] -> ( q : Paper ) 2 WHERE p . name = ' ' John ' ' 3 AND
q . type = ' ' j o u r n a l ' ' 4 RETURN p AS PersonName , q AS Paper Listing 1: Person "John" with Edge "PUBLISH" and Paper The Listing 1 give the details of all papers published by "John" which are of type "journal". To visualize the property graph for edge type "COLLABORATE", we execute the following sample cypher query. The output in Figure 8 shows the "COLLABORATE" edge of user "John" with all users in graph database.

1 MATCH ( p : Person {name : ' ' John ' ' })- 2 [ r :COLLABORATE] -> ( n : Person ) 3 RETURN p , n , r
Listing 2: Person "John" with Edge "COLLABORATE"

Handling Missing Values

Missing data as defined in [START_REF] Newman | Missing data: Five practical guidelines[END_REF] "is a statistical problem characterized by an incomplete data matrix". The impact of "missing data bias and error in the reporting of research results" may vary depending on "the amount of missing data and the pattern of missing data" [START_REF] Newman | Missing data: Five practical guidelines[END_REF]. When dealing with missing data, it is important to consider the type or nature of missing data. For example, the missing data can be random, structured, forgotten or sometimes not available etc. The types of missing data were first described in [START_REF] Rubin | Inference and missing data[END_REF] as; (i) Missing Completely At Random (MCAR), (ii) Missing At Random (MAR), and (iii) Missing Not At Random (MNAR).

In MCAR, the missing data is not related to a specific value or observed response. When the missing data depends on a set of observed responses, but not related to specific values it is called MAR. The missing values are distributed randomly across all the data in MCAR, whereas in MAR, the missing values are distributed within one or more sub-samples. If the missing data is neither MCAR nor MAR, it is then categorized as MNAR. The reason for missing values in MNAR depends on the missing values themselves, for instance the unobserved data. The example for MNAR can be the people with high income are less likely to report their income [START_REF] Rubin | Inference and missing data[END_REF].

Handling missing data techniques

Primarily there are two main approaches to deal with missing values i.e., (i) ignoring / deletion and (ii) imputation. It is important to decide the best strategy that results the least biased results. This can be performed by evaluation of the source data and identifying type of missing data.

Ignoring or deleting techniques include list-wise deletion (i.e., ignoring a row/ object which contains missing data) and attribute deletion. Imputation techniques include replacing missing data with fixed constant for instance, replacing with mean of the objects of attribute. Expectation Maximization presented in [START_REF] Dempster | Maximum likelihood from incomplete data via the em algorithm[END_REF] is a missing data treatment technique in which missing values are estimated (parameter estimation) based on the maximum likelihood method.

We are not using list-wise or pair-wise deletion because in most of the real-case scenarios this could mean removing all the data. Indeed, the properties attached to nodes sharing the same label (e.g. Person) may be different (e.g. "salary and company" on the one side and "school and degree" on the other side). For instance, some nodes may have salary and company information but not school and degree information and vice-versa. In this case, when combining all properties of all nodes, it will result in the fact that no node will have all properties filled in. A list-wise approach will then result in the deletion of all data. Our approach is more parsimonious because it preserves the row as long as possible i.e., even if some attributes are missing, if they are not concerned by the current computation/step, they are disregarded.

Handling missing data with replacement

Imputation methods involve replacing missing data. However, we claim that we can not replace missing data in case of property graphs. Indeed, if the property is missing in a node, there is often no meaning to add it artificially, which creates a bias in results, particularly in the case of real datasets.

The treatment of missing data using imputation is studied by employing supervised learning algorithms [START_REF] Batista | An analysis of four missing data treatment methods for supervised learning[END_REF][START_REF] Hruschka | Evaluating a nearest-neighbor method to substitute continuous missing values[END_REF][START_REF] Shahzad | Missing data imputation using genetic algorithm for supervised learning[END_REF]. In [START_REF] Wu | Using association rules for completing missing data[END_REF][START_REF] Ben Othman | Missing values: Proposition of a typology and characterization with an association rule-based model[END_REF], an association rules based model is used to complete missing data.

The use of graphical models for processing of missing data is presented in [START_REF] Mohan | Graphical models for processing missing data[END_REF]. "Graphical models enable an efficient and transparent classification of the missingness" [START_REF] Mohan | Graphical models for processing missing data[END_REF] i.e., whether it is MCAR or MAR. The multiple imputation techniques such as "Amelia" assume the missingness of data as MAR [START_REF] Honaker | Amelia ii: A program for missing data[END_REF]. The authors in [START_REF] Mohan | Graphical models for processing missing data[END_REF] state that "Maximum Likelihood based techniques is a well known estimation method for missing data that require MAR assumption for consistent estimates".

Handling missing data without replacement

[15] has considered the question of dealing with missing data for the computation of rank correlation. However, the paper only considers the case where one or several individuals are missing, meaning in the tabular representation a full line has missing values, whereas we consider here the case where single values are missing.

As mentioned in [START_REF] Orchard | A missing information principle: theory and applications[END_REF], "obviously the best way to treat missing data is not to have them". In real world applications, where data is managed in relational databases, we often find missing values. [START_REF] Ragel | Treatment of missing values for association rules[END_REF] has proposed to mine association rules in relational databases in the presence of missing data by segmenting the database into several socalled valid databases ("vdb"), in such a way that a vdb does not contain any missing value. Hence, the authors redefined the concepts of support and confidence for vdb and suggest that these definitions are fully compatible with existing association rule mining algorithms.

Problem Statement

NoSQL databases rely on semi-structured data. Due to inherent nature of property graph, a node may not contain all the properties. This data may be missing because it is not available or it does not exist as it may not be applicable (for example no salary, or experience in the case of kids). So, they often contain such missing data where all properties may not be present for nodes and edges. We argue that in case of property graphs, it is not possible to apply directly existing methods for gradual patterns extraction. There are two main reasons:

(1) Property graphs are not the same as tabular data in their meaning and application; (2) Property graphs are semi-structured nature of data.

Therefore, the focus of this work is on handling missing data and extending the existing algorithms to deal with such missing values for extracting gradual patterns. The main steps of our approach are; (i) Retrieve the graph data, (ii) Treat missing data and (iii) Extract gradual patterns.

For mining the gradual patterns, there can be several ways to define them in the context of property graphs such as; (i) Intra-Node-Label-Properties, (ii) Inter-Node-Label -Properties, (iii) Node-Properties-with-Edges-count, and (iv) Inter-Edge-Properties. In the paper, we present (i) and (ii). In Intra-Node-Label-Properties, the pattern extraction process is performed among the properties/attributes of the "same label " nodes. In the Inter-Node-Label-Properties, gradual patterns are extracted from different labels. And, in Node-Properties-with-edges-count, the gradual patterns are extracted from node properties with the edges count that is retrieved from property graph.

Mining Gradual Patterns with Missing Values

Mining gradual patterns from property graphs is a novel idea as it involves automatic retrieval of graph data including nodes and edges. It becomes more challenging as the retrieved information often contains missing values due to inherent nature of property graphs. In such a case, the traditional mining techniques can not be applied without treatment of missing values. Therefore, we highlight two novelties of our approach. The first is that no method exists for dealing with missing value when extracting gradual patterns, which is not the same task as regular frequent patterns as the support cannot be computed object by object but requires to consider the ranking of all objects. The second is that we apply this on NoSQL property graphs which are more and more used in real world scalable applications, which is not trivial as all definitions and algorithms must be extended for this particular context.

An overall process flow of gradual pattern mining from a property graph in presence of missing data is shown in Figure 9. The process includes:

(1) Connect to graph database engine and retrieve the graph schema (node labels, edges types and the properties) (2) Processing the retrieved data from graph for handling missing data (3) Extract the gradual patterns by computing the support (Section 4.3)

In the first step we retrieve the graph schema from the databases, which means the retrieval of existing node labels, edges types, and their respective count. This information provides a summary of the nodes and edges as well as describes which label is connected with whom and in what frequency (i.e., number of edges). As we know that a property graph is semi-structured and does not have an enforced pre-defined schema, so whenever any deletion or addition of nodes and edges occur in the graph, the data summary for them will also change and the pattern extraction will be performed by accordingly.

Listing 3: Graph Node Count with Labels

The Listing 3 shows the details of all the labels for a given property graph with its node count. Similarly, the Listing 4 gives the details about Edges. Once this data is received, we extract the properties for each label and edge. The process then determines the completeness of data and if the data is missing in properties, then missing data handling takes palace.

In the second step of the process, we consider the approach presented in [START_REF] Ragel | Treatment of missing values for association rules[END_REF] for treatment of missing values in the context of property graphs. The approach was presented for relational databases to deal with the missing data present in items in order to mine association rules. The approach suggests to cut the dataset into valid database vdb i.e., by partially ignoring missing values from the data. For instance, the dataset shown in Table 4, with the classical definition of support, given the minimum support threshold is 40%, the resulting association rules will be:

X1 = a → X4 = c, supp = 50 X1 = b → X4 = d, supp = 50 X4 = c → X1 = a, supp = 50 X4 = d → X1 = b, supp = 50
Taking the same minimum support threshold of 40% for dataset shown in Table 5, no rules are formed because the support value except {X2 = b} for all the remaining items becomes less than 40% as given below:

{X1 = a} = 3 8 = 0.375, {X1 = b} = 3 8 = 0.375 {X2 = b} = 4 8 = 0.5, {X4 = c} = 3 8 = 0.375 {X4 = d} = 3 8 = 0.375
To avoid such a situation due to missing data, the authors [START_REF] Ragel | Treatment of missing values for association rules[END_REF] propose to partially disable missing data and calculate the valid database for items so as to form the association rules. It is important to recall that for gradual patterns mining we are only interested to compute the support.

In the later part of the section, we explain the vdb calculation based on [START_REF] Ragel | Treatment of missing values for association rules[END_REF] and thereby propose our approach. The next phase of the process includes mining gradual patterns that involves the matrix representation of items (properties) and support computation as shown in algorithm 1 and 2. To do so, we first begin by defining gradual item in property graph as below.

Definition 4.1 (PG Data Gradual Item). Let Λ N be a set of node Labels with N U LL ∈ Λ N , Π N be a set of properties, P N a set of (key:value) pairs over Π N , Λ R be a set of edge Types with N U LL ∈ Λ R , Π R be a set of properties, P R a set of (key:value) pairs over Π R .

Let G D = (N, R) be a graph defined over Λ N , P N , Λ R and P R . A graph data gradual item is a gradual item i where i ∈ Π N ∪ Π R .

Example 4.1. An example of such property graph data gradual item could be "The higher the Age" (Age ↑), where "Age" is a property of a node labeled with "Person".

We explain the concept of "vdb" by using the running example of property graph as discussed in Section 2.2. The nodes and edges visualization of property graph is shown in Figure 10. The transformation of label "Person" in tabular representation is given in Table 6. We represent the missing values in "Age" and "Sal" attributes with "?" sign.

The "vdb" is the cardinality of an attribute without missing values. For the sake of simplicity, this cardinality is said to be the "cardinality of an attribute". By this, we mean the cardinality of the subset of tuples for which the value on the given attribute is not null. In our case, this attribute is meant to represent a node's property. Let n be the number of tuples of an attribute and a m be the number of missing values in that attribute then the vdb of that attribute of the dataset is:

Person Paper Project RCV_G R R C V _ G R PU BL IS H PUBLISH PUBLISH C O LL A B O R A T E C O L L A B O R A T E C O L L A B O R A T E PUBLISH C O LL A B O R AT E C O L LA B O R A T E PU BL IS H C O L L A B O R A T E P U B L IS H PU B LI SH CO LLA BO RA TE RCV_GR P U B L IS H PUB LIS H P U B LI S H CO LLA BO RA TE C O L L A B O R A T E C O L L A B O R A T E P U B L IS H C O L L A B O R A T E C O LL A B O R AT E C O L L A B O R A T E PUB LIS H PUB LISH C O L L A B O R A T E RE CE IVE RE CE IV E R E C E IV E E V A L U A
|vdb(x)| = |n(x)| -|a m | (1)
Therefore, the "vdb" calculation for (Age) is 5 and for (Sal) is 6 as shown in Table 7 and Table 8 respectively.

As discussed in Section 3 that there can be several ways to first define and then mine the gradual patterns in property graphs. For the scope of this paper, we present following two methods:

(1) Intra-Node-Label Gradual Patterns (2) Node-Properties with Edges Gradual Patterns We describe the mining process for both of these methods as follows.

Intra-Node-Label Gradual Patterns

We investigate the scenario of Intra-Node-Label properties for gradual pattern extraction i.e., the pattern extraction process is performed among the properties/attributes of the "same label" nodes. For instance, for a particular label "Person", we try to find the correlation among the properties of nodes. An example of the final extracted pattern can be "the higher the age, the higher the experience". It is important to note that in this scenario there are no edges involved. Considering the label "Person" from graph Figure 10. First, the program retrieves the data from property graph using Noe4j bolt protocol for this label. The response of the Cypher query received from graph database is transformed into tabular representation as shown in Table 6. At this stage, program creates binary order matrix for given properties and then computes the support as described in algorithm [START_REF] Laurent | GRAANK: exploiting rank correlations for extracting gradual itemsets[END_REF] for gradual pattern extraction. But, it requires to handle missing values first, because the exiting algorithm does not allow to treat missing data.

Let us see with an example regarding the missing data and our approach to handle it. In property graph, in response to a projection Cypher query, a missing property (i.e., key) and a missing value of the property are treated as same. The result of the Cypher query will be "NULL", if the node contains a missing value or a missing property [START_REF] Bowman | Understanding non-existent properties and working with nulls[END_REF]. Once the data is received, we perform binary order of matrix as explained in Section 2.1. For example, the binary matrices of (Age ↑) and (Expr ↑) representing the order are shown in Figure 11. Since, we do not know the missing value of Dave's age, so when representing the order between John's age and Dave's age, we place "?" sign in the 2nd row of 1st column of the matrix (Age ↑) in Figure 11. The same procedure applies for John and Tim's missing age, we place "?" sign in the 4th row of 1st column in the matrix. For the binary AND operation of (Age ↑) and (Expr ↑), we consider the fact that any bit (1 or 0) multiplied with "?" sign will result in "?" sign. Hence, the resulting Hadamard product of these two gradual items in matrix representation is shown in Figure 12.

When combining several attributes, the value of vdb reduces. In our approach, it requires us to preserve the location of missing value, so as to maintain the cardinality for computing the support when combining multiple attributes. [START_REF] Ragel | Treatment of missing values for association rules[END_REF] states that, for a given itemset, we cut the dataset into a valid database "vdb", such that the "vdb" must not have any missing values. The vdb representations in tabular form when combining attributes are shown in Table 10,and

                 
1 0 ? 0 ? 0 0 0 2 ? ? ? ? ? ? ? 3 1 ? 0 ? 1 1 1 4 ? ? ? ? ? ? ? 5 1 ? 0 ? 0 0 0 6 1 ? 0 ? 1 0 0 7 1 ? 0 ? 1 1 0 (Age ↑)

1 2 3 4 5 6 7                  
1 0 0 0 0 1 0 0 2 1 0 0 1 1 1 0 3 1 1 0 1 1 1 0 4 1 0 0 0 1 0 0 5 0 0 0 0 0 0 0 6 1 0 0 1 1 0 0 7 1 1 0 1 1 1 0 (Expr ↑)

Figure 11: Binary matrix representing orders for Table 9 1 2 3 4 5 6 7

                 
1 0 ? 0 ? 0 0 0 2 ? ? ? ? ? ? ? 3 1 ? 0 ? 1 1 1 4 ? ? ? ? ? ? ? 5 0 ? 0 ? 0 0 0 6 0 ? 0 ? 1 0 0 7 1 ? 0 ? 1 1 0 For the gradual pattern extraction process, this vdb calculation is an essential part because the value of vdb is then used for support computation (Section 4.3).

Node-Properties-with-Edges Gradual Patterns

In "Node-Properties-with-edges-count" scenario, we try to extract the gradual patterns that involve node properties for a label as well as the corresponding edges count. The pattern extraction process will be processed to see if there exists any correlation between them. In this case, the correlation can be "the higher the age, the higher the number of collaborations" or "the higher the experience, the higher the collaboration".

To perform this mining we first extract graph summaries. "Graph summarization facilitates the identification of structure and meaning in data" [START_REF] Liu | Graph summarization methods and applications: A survey[END_REF]. There are various summarization techniques depending upon the nature and requirement of the task [START_REF] Khan | Summarizing static and dynamic big graphs[END_REF][START_REF] Liu | Graph summarization methods and applications: A survey[END_REF]. These graph summarization techniques include aggregation-based (topology), attribute-based (topology and attributes) [START_REF] Wu | Graph summarization for attributed graphs[END_REF], applicationoriented (e.g., graph pattern matching), and domain specific (e.g., bio-informatics) [START_REF] Khan | Summarizing static and dynamic big graphs[END_REF]. In our scenario, program first extracts the graph topology summary including the labels and edges count and further uses that for mining gradual patterns. The output of graph schema summary for running example is shown in Table 12.

After retrieving the graph schema summary, the program extracts summary per label with all its nodes and edges count. The output of this summary in tabular form for label "Person" is shown in Figure 13. From this point the process of handling missing values takes place as shown in Figure 9. After handling missing values, the support computation takes place to find out the gradual pattern that have support greater than the minimum support threshold.

Support Computation

The existing support and confidence measures are misleading when there exist missing data in such a way that they are lacking in the crucial monotonicity property of support [START_REF] Calders | Mining itemsets in the presence of missing values[END_REF]. We are interested to compute the "support" with valid databases. We are not computing the confidence as the objective over here is not rules formation. The anti-monotonicity of the support can not be considered anymore in a simple manner because support cannot be computed object by object but requires to consider the ranking of all objects.

In order to compute the support, we compute the logical AND of gradual items as explained in Section 4.1. From the resultant matrix, we take the sum of binary '1' bit from the matrices. Consequently, we calculate the support as given below:

Support(X i ) = Sum of concordant pairs |vdb(X i )| * (|vdb(X i )| -1)/2 (2)
where, X i = itemset

In [START_REF] Ragel | Treatment of missing values for association rules[END_REF], authors suggest, "To obtain good results a vdb must be a good sample of the database. This is normally true if values are missing at random" therefore, a new parameter "representativity" is introduced. The representativity is the proportion of the vdb(X i ) over the entire dataset tuples. The itemset should be representative so as to be considered for support computation. Representativity is a user defined parameter. It helps to ensure that support computation should not take place for the itemset which is not representative i.e., having value less than user defined value. For the running example, the representativity is calculated as follows:

Representativity(X i ) = |vdb(X i )| |n| (3)
where, X i = itemset, n = number of tuples An overall mining process is shown in Figure 9. Algorithm 1 shows the procedure for computing the support based on the vdb method as explained in Section 4.3. After the retrieval of data from the graph data, following are the main steps of Algorithm 1.

• Store the items (properties/attribute(s)) in an array list.

• Initialize the binary matrix for each item of the list.

• Compute the binary order matrix.

• Compute the sum of high "1" bits and missing data represented as "?".

• Compute the vdb (cardinality of valid data) to be used for support computation.

• Compute the support and update the list An explanation of these steps is presented as follows. After the retrieval of data from the graph data, binary matrix initialization for each property is performed. Then we calculate binary-ordered representation for each item. These matrices contain 0 or 1 and missing values are represented by "?" sign. We then calculate the sum of all high-bits i.e., 1 which represent the concordance for the respective item. A complete row with "?" sign in matrix represents the missing value in that attribute as shown in Figure 11, (Age↑) for row 4 i.e., Tim's age is missing. To keep track of this, a card variable is used. For instance, in Figure 11 (Age↑), the number of rows containing "?" are 2. The flag variable is used to track the the length of matrix that in turns helps to calculate vdb i.e., the cardinality of that item without missing values. Finally, the support is computed as expressed in Equation 1. If the item's support is less than the minimum support threshold, then it is removed from the list. for all rows of matrix M for listItem

L i do 4:
for all columns of row of M do 5: end if 20: end for 21: Update the list L with successful gradual items of size-1

if L i .M[row][col] == 1 then 6: sum ← sum + 1 7: else if L i .M[row][col]==?
Once we have the list of successful gradual items, i.e., those having (support > minSupport) the program checks for gradual patterns as defined in Definition 2.2. Therefore, the Hadamard product of binary AND operation of gradual items is performed and then the support is calculated. The successful gradual patterns are updated in the list and those which do not meet the minimum support requirement are removed. This is performed by Algorithm 2. Following are the main steps:

• Take the list of input gradual items that are result of Algorithm 1 and multiply L i item with L j item.

• Perform the Hadamard product for L i AND L j .

• Compute the binary order matrix.

• Compute the sum of high "1" bits and missing data represented as "?".

• Compute the vdb (cardinality of valid data) to be used for support computation and compute support.

• Update the list of gradual patterns and go for next item in L i

• Output the list of successful gradual patterns.

Pattern mining algorithms are known to be NP-hard. It is concluded that the complexity of enumeration problem for mining maximal frequent itemsets is NP-hard [START_REF] Yang | The complexity of mining maximal frequent itemsets and maximal frequent patterns[END_REF][START_REF] Han | Frequent pattern mining: current status and future directions[END_REF].

Experimental Results

The objective of these experiments is to see the feasibility of mining gradual pattern from property graphs and to compare the proposed approach (Section 4) with imputation of missing values approach. This section is subdivided into three subsections. The first subsection introduces the experimental protocol, the second subsection presents the datasets (synthetic or real data). Finally, we show and discuss the experimental results in the last subsection.

Experimental Protocol

In this section we briefly describe the program execution environment, the program's logical execution protocol, outlier removal method and memory consumption metrics used to calculate maximum heap utilization.

Environment

All the experiments have been run on the hardware, operating system and software packages given below. for all listItem L i do

3:
for all listItem L j = L i + 1 do

4:
for all rows of matrix M for listItem L i do

5:

for all columns of row of M do 6:

resultM [row][col] = L i .M [row][col]* L j .M [row][col] 7: if resultM[row][col] == 1 then 8:
sum ← sum + 1 Update the list L 25: end while 26: Output the frequent patterns

Experiments execution protocol

The execution protocol describes the steps necessary to produce the results given in the next section.

(1) The java program establishes the connection with graph database using Neo4j's bolt protocol (port 7867) (2) After the successful connection, the program queries the graph database to retrieve the label's data for the required attributes (3) Once the attribute data is received, for each attribute the binary matrix initialization is performed as discussed in Section 2 (4) After the matrix initialization and concordant object pairs AND operation, the vdb computation is performed as discussed in Section 4 (5) An executable is created and run 5 times. The average value of each metric is used (outliers are removed, as discussed in the next subsection)

The source code and output files are available at git [START_REF] Shah | Gradual pattern extraction-java code[END_REF]. The program takes as parameter the min support.

Outlier Removal

Each data point is plotted by taking the average of 5 executions. In case of any outlier result point in time or peak heap memory utilization, we use the Three Sigma rule also known as 68-95-97.7 or "empirical rule". It states that for a normal distribution almost all of the data will be within the range of 3 standard deviations (std.dev). Empirical rule has three parts i.e., 68% of data will fall with 1 standard deviation of the mean value, 95% of data within 2 standard deviations of the mean value and 97.7% of data within 3 standard deviations of the mean value. For removing the outliers, we adopt the rule of 2 standard deviations i.e., (Mean + 2×std.dev) for upper bound point and (Mean -2 × std.dev) for lower bound point [START_REF] Narasimhan | The normal distribution[END_REF].

Memory Consumption Metric

Choosing a metric for memory consumption is an essential task. Java has both heap and non-heap memory. JVM consider memory pools of type heap or nonheap [START_REF] Oracle | Java memory types[END_REF]. For the memory consumption we take peak used size of all the memory pools which are of type HEAP and NON HEAP. For this we use java M emoryP oolM XBean management interface for a memory pool and call the method getP eakU sage(). The plots for datasets show the sum of heap and non-heap peak memory usage. Details of the source code and its usage is given at [START_REF] Shah | Gradual pattern extraction-java code[END_REF].

For each program execution, we have used the same JVM settings. First of all, we have decided to use the G1 garbage Collector. First introduced with Java 7, this garbage collector has the unique ability to efficiently and concurrently deal with very large heaps. It can also be configured not to exceed a maximum pause time. It can so easily outperform other state-of-the-art GCs on large heaps that Garbage First (G1). GC is used as default garbage collector in Java 9. We also set the BiasedLockingStar-tupDelay to 0 for improving performance of unaccounted synchronization and we have tuned the Xmx parameter to fix the maximum size of memory allocation pool. To summarize, the jvm flags as arguments for program execution are; -XX:+UseG1GC, -XX:BiasedLockingStartupDelay = 0, and -Xmx10G for intra-node and -Xmx12G for nodes with edges datasets.

Datasets description

The experiments were performed on two different types of datasets for intra-node gradual pattern mining and nodes with edges gradual pattern mining as shown in Table 13 and Table 14 respectively. It is worth noticing that the proposed approach may be applied to numerical ordinal attributes only. Therefore, in case of intra-node gradual pattern mining, a pre-processing step is performed to opt the attributes of datasets that are numerical. For all these, we have created separated graph databases and run the program executions accordingly, with the exception of Hetionet dataset. The Hetionet is a real graph database which is publicly available at [START_REF] Himmelstein | Hetnets in neo4j[END_REF].

In each result, for the missing data imputation method, we made a separate program to perform comparisons of time consumption, peak memory and number of generated patterns. The missing data is imputed using R package Amelia 2 that uses the expectation minimization algorithm [START_REF] Honaker | Amelia ii: A program for missing data[END_REF] for multiple imputation of missing data. The complete details of source code is available at gitlab [START_REF] Shah | Gradual pattern extraction-java code[END_REF]. The rest of this subsection is devoted to describe more details about each dataset.

The Russian tweet troll

The Russian tweet troll is a real dataset taken from [44]. This dataset contains more than 200, 000 tweets that Twitter has tied to "malicious activity" from Russia-linked accounts during the 2016 U.S. presidential election.

User account file contains 14 attributes but we have selected 7 relevant attributes (userId, followersCount, sta-tusesCount, timeZone, favouritesCount, friendsCount, and listedCount) for our experiments. This data is used to create a graph DB using cypher import utility. The data is imported using the following command:

Synthetic Dataset

For this experiment, we creates a synthetic dataset by using the java class "Random" to generate a stream of pseudorandom numbers. The source code for generating dataset is available at gitlab [START_REF] Shah | Gradual pattern extraction-java code[END_REF]. We generated the dataset for 10, 000 nodes and 5 attributes. In order to introduce missing values of 25% in the generated file, we use R's package missF orest and its method prodN A. This package uses Random F orest supervised machine learning algorithm to introduce missing values completely at random (MCAR). The database creation command is given below.

Synthetic Graph Dataset

We have developed a synthetic graph generator to make property graphs in Neo4j database. This graph generator's web interface is available at [START_REF] Shah | Synthetic graph generator[END_REF]. The synthetic graph dataset contains 3 labels namely Label1, Label2, Label3 and 3 edge types R1, R2, and R3 respectively. The nodes and edges details are shown in Table 14. We created the graph database with these specifications to run the experiments for both vdb and imputation methods to compare the time and memory utilization as well as to observe the difference in generated patterns. The created Neo4j databases and complete source code is available at [START_REF] Shah | Gradual pattern extraction-java code[END_REF]. The output plots are shown in Figure 17.

Hetnets in bio-medicine

Hetnet is a research outcome published in [START_REF] Himmelstein | Systematic integration of biomedical knowledge prioritizes drugs for repurposing[END_REF], which shows a network of biology, disease, and pharmacology. It is an integrated network of nodes and edges in which "the knowledge from millions of biomedical studies over the last half century have been encoded into this single system" [START_REF] Himmelstein | Systematic integration of biomedical knowledge prioritizes drugs for repurposing[END_REF]. The details of the project and its relevant github resource is available at [START_REF] Daniel Himmelstein | Hetnets in biomedicine, page accessed[END_REF].

In this dataset, we choose the "Gene" label and its edges. The purpose to choose "Gene" because it has a relevant attribute i.,e number of chromosomes for every gene. We took all the gene nodes and their edges with other labels like chemical compound, biological process, etc. There are 7 edge types of "Gene" Label in Hetionet. The summary of its edges with other labels is shown in Table 15. The dataset has a total of 47,031 nodes and 2,250,197 edges. In the Gene label, there are 20,945 nodes and 1,289,190 edges with 7 edge types. For our experiments, we used all the nodes with 4 edge types that connect with labels other than Gene itself like, PARTICIPATES GpBP, PARTICIPATES GpMF, PARTICIPATES GpPW and PAR-TICIPATES GpCC. The output plots are shown in Figure 18.

Discussion

It is found from the results of both types of experiments i.e., intra-nodes and nodes with edge that the percentage of missing data has an impact on the total number of extracted patterns. That is, with higher missing data percentage in a dataset, we get more patterns. In the case of synthetic dataset at support threshold of 0.2, the imputation approach generates 24 patterns whereas vdb approach generates 13 patterns. Some of the excessive pattern generated by imputation approach are (A99RO↑ , B99RO↑), (A99RO↑, C99RO↑), (B99RO↑, C99RO ↑), (A99RO ↑, B99RO↑, C99RO↑), and (B99RO ↑, D99RO↑, E99RO↑). Similarly, for Hepatitis dataset at support threshold of 0.2, (BILIRUBIN ↑, Age↑, SGOT↓) is an excessive pattern. Also, there were some patterns in imputation methods that were not present in vdb such as, (ALKphosphate ↑, PROTIME↑, ALBUMIN↑) and (ALKphosphate↑ , PRO-TIME ↑, Age↓). We think that these excessive patterns may not resemble to the reality and can be better decided by the domain expert by looking at the actual available data.

In the experiments for intra-node gradual patterns, it was observed that imputation method generates more patterns than vdb-based method. This implies that the imputation method generates the patterns that might not actually correlate in reality. Since the Russian-tweet-troll dataset has only 3% missing data, so there is almost no difference between both methods (i.e., vdb and imputation) in terms of patterns being extracted as shown in the NumPatterns Vs Support Threshold plots Figure 14. The same fact is visible in Figure 15 for Hepatitis dataset. Whereas, in Synthetic dataset plot Figure 16, at smaller support thresholds like 0.2, the difference of generated patterns is almost double. This shows that with higher percentage of missing data, the imputation method generates more biased results.

In the experiments for nodes with edges scenario for the datasets shown in Table 14, we observed the similar fact that with more percentage of missing data the imputation method generates more patterns as shown in numPatterns in Figure 17. For the imputation method, this fact may be crucial in the case of real graph databases where practitioners or domain experts involvement becomes necessary to remove the false positives (i.e., the excessive patterns). The same is observed in Hetionet graph database at support threshold of 0.3, where we found (chromosome ↑ , PARTICIPATES GpPW ↑) as an excessive pattern.

For the memory utilization results, with the exception of couple of instances, the vdb based method performs better than imputation method for all the three datasets. The program's time utilization results also show that time difference is almost doubles between both methods in all the three datasets of intra-node experiments. whereas, the time utilization in case of node with edges scenario is almost same as observed in Figure 17 and Figure 18 respectively.

It is deduced form the results that when the percentage of missing values is higher the imputation method generates more pattern than vdb approach and these excessive patterns might now reflect to the reality. Because the data is artificially imputed in missing places, the imputation method generates more co-variance for the objects that are not actually present.

Conclusion

In this article, we are dealing with mining gradual patterns from NoSQL graph databases, which raises the problem of dealing with missing data. We propose a new approach based on valid databases and show the performance comparison with imputation method.

Further works include the integration of our proposal in the database engine. To achieve this goal, we aim at using GraphX Apache Spark's API for graphs and graphparallel computation. Indeed, one of our further work is to provide a scalable distributed implementation of gradual pattern mining algorithm compatible with the use of missing values.

Figure 1 :

 1 Figure 1: Property Graph Model

Figure 2 :

 2 Figure 2: Binary Matrices for Gradual Items of Size-1

Figure 3 :

 3 Figure 3: Precedence Graph ( Age ↑ , Lab-tests ↑)

Figure 4 :

 4 Figure 4: Binary AND of concordant object pairs for gradual patterns

Example 2 . 2 .

 22 Λ N ={Person, Student, NULL}, Π N = {Age, Expr, Sal}, n 1 = (2812, { Person, Student}, {(Age : 32), (Expr : 5), (Sal : 1400)}) is a property node as shown in Figure 7.Definition 2.4 (Property Edge). Let N be a set of property nodes, Λ R be a set of edge types with N U LL ∈ Λ R , Π R be a set of properties where every property π ∈ Π R can

Figure 7 :

 7 Figure 7: Property Node for Label "Person"

Figure 8 :

 8 Figure 8: Edges Types Details

Figure 9 :

 9 Figure 9: Property Graphs Gradual Pattern Mining Process

1

  MATCH ( ) -[ Edge ] -> ( ) 2 RETURN ty pe ( Edge ) AS Edge Type , 3 Count ( * ) AS Edge Count ; Listing 4: Graph Node Count with Labels

5 :

 5 Dataset 2 from[START_REF] Ragel | Treatment of missing values for association rules[END_REF]

  |vdb(Age)| = 5, |vdb(Sal)| = 6, |vdb(Expr)| = 7 |vdb(Age & Sal)| = 4, |vdb(Age & Expr)| = 5 |vdb(Sal & Expr)| = 6 |vdb(Age & Sal & Expr)| = 4

7 4

 7 |Rep(Age)| = 5/7, |Rep(Sal)| = 6/7, |Rep(Expr)| = 7/7 |Rep(Age & Sal)| = 4/7, |Rep(Age & Expr)| = 5/7 |Rep(Sal & Expr)| = 6/7, |Rep(Sal & Expr)| = 6/7 |Rep(Age & Sal & Expr)| = 4/

Algorithm 1 : 1 :

 11 Mining Gradual Property-based Items in the Presence of Missing Values Input: Properties, minSupport Output: List of gradual items having support greater than minSupport Initialize the matrices for each property and store into list L 2: for all items in list L do 3:

  then

  L i .M.length -flag) 16: support = sum / (vdb * (vdb-1)/2) 17: if support < minSupport then 18: remove L i 19:

•- 4 Algorithm 2 :

 42 Hardware: Intel Core i7-4610M, 3.00 GHz, quad core processor, 16 GB RAM • Operating System: Linux generic kernel 4.4.0-134, Ubuntu 16.04 LTS • Software: -JDK version "1.8.0 181", jre build 1.8.0 181-b13, HotSpot java 64-bit server VM (build 25.181-b13, mixed mode) Neo4j graph database community edition 3.4.7, bolt protocol enabled -Neo4j-java-driver version 1.4.Mining Gradual Patterns in the Presence of Missing Values from Gradual Items Input: List L i of gradual items, minSupport, Output: Frequent Property-based Gradual Patterns 1: while items in list |L i | ! = 0 do 2:

Figure 15 :

 15 Figure 14: Russia Tweet troll Dataset

  Figure 16: Synthetic Dataset

Figure 18 :

 18 Figure 18: Hetionet(Gene) Dataset

Table 1 :

 1 Patients

	Id Age Lab-tests Time-in-Hospital
	p1	45	13	35
	p2	35	7	20
	p3	30	5	25
	p4	55	10	28
	p5	40	14	38

Table 2 :

 2 Nodes Label Summary

		COLLAB.		Paper
			P U B L IS H
	Person
			RC V GR AN T	Project
	Figure 6: Example Graph Database Schema
	Label	Properties	Node Count
	Person id, name, age, desig, expr, sal	7
	Paper	id, pr title, type, year	5
	Project	id, prg title, lab, year	2
	Type	Properties Edge Count
	Collaborate	since	14
	Publish	date	13
	Rec Grant	date	3

Table 3 :

 3 Edges Type Summary

Table 6 :

 6 Label "Person" Tabular form

	GRAPH
			RDF
	Tim
			EVALUATE
		Carl		MUSE
	LOGIC			T E
		CNRS	EVALU ATE
	Chris		John	FUZZY
	David
	DB		Dave	Emily
	Figure 10: Graph Visualization
	Id Name Age Expr Sal
	1 John	45	13	3500
	2 Dave	?	7	2500
	3 Emily	30	5	?
	Tim	?	10	2800
	5 Carl	44	14	3800
	6 Cris	38	9	2600
	7 David	32	5	1400

Table 7 :

 7 |vdb (Age)|

	Id Name Age 1 John 45 3 Emily 30 5 Carl 44 6 Cris 38 7 David 32	Id Name Sal 1 John 3500 2 Dave 2500 4 Tim 2800 5 Carl 3800 6 Cris 2600 7 David 1400

Table 8 :

 8 |vdb (Sal)|

Table 9 :

 9 Table 11 respectively. We can observe that the size of vdb is the same for (Age & Sal) and (Age & Sal & Experience) because the Expr attribute does not have any missing value. The calculation of "vdb" for label Dataset for Age & Expr

	Id Name Age Expr
	1 John	45	13
	2 Dave	?	7
	3 Emily	30	5
	4 Tim	?	10
	5 Carl	44	14
	6 Chris	38	9
	7 David	32	5
	1 2 3 4 5 6 7

Table 10 :

 10 |vdb (Age & Expr)|

	Figure 12: Hadamard product for Age AND Expr

Table 11 :

 11 |vdb (Age & Sal & Expr)|

"Person" is given below:

Table 12 :

 12 Graph Schema Summary with Edge Count

	SrcLabel		Edge		DstLabel EdgeCnt
	Person	COLLABORATE	Person	14
	Person	PUBLISH		Paper	13
	Person	RCV GR		Project	3
	Paper	RECEIVE		Project	3
	Project	EVALUATE	Person	3
		Label "PERSON" Data		Edges Count
	Id	Name	Age	Expr	Sal	No. Of Collaboration	No. of Publications	No. of Grants
	1	John	45	13	3500	3	3	2
	2	Dave	?	7	2500	2	1	0
	3	Emily	30	5	?	1	1	0
	4	Tim	?	10	2800	1	2	0
	5	Carl	44	14	3800	3	3	1
	6	Chris	38	9	2600	3	1	0
	7	David	32	5	1400	1	2	0
	Figure 13: Property Graphs Gradual Pattern Mining Process

Table 13 :

 13 Intra-Node Gradual Pattern Mining

	S#	Dataset	Nodes Properties Missing %
	1	Russian tweet	393	6		3
	2	Hepatitis	155	6		13
	3	Synthetic	10,000	5		25
	S#	Dataset	N	R	P	RT M
	1	Synthetic Graph 15,000	999,268	6	3	10
	2	Hetionet(Gene)	20,945 1,289,190	1	4	1
		N = Nodes , R = edges, P = Node Properties,
		RT= edges Type, M = Missing Values %

Table 14 :

 14 Nodes with Edges Gradual Pattern Mining

  Hepatitis from UCI Machine Learning RepositoryHepatitis dataset is taken from UCI machine learning repository[START_REF]UCI-Machine-Learning-Repository[END_REF]. For this dataset, there are 20 attributes, but we consider only 6 relevant attributes (BILIRUBIN, ALKphosphate, PROTIME, ALBUMIN, Age, and SGOT]) that have been imported to graph database. Attributes selection is made considering the numerical attributes requirement of the approach.

	1 LOAD CSV WITH HEADERS FROM
	2	" f i l e : // / u s e r s r u s s i a n t w e e t t r o l l . c s v "
	3	AS row
	4 MERGE
	5	( : User { u s e r I d : row . u s e r I d ,
	6	f o l l o w e r s C o u n t : row . f o l l o w e r s C o u n t ,
	7	s t a t u s e s C o u n t : row . s t a t u s e s C o u n t ,
	8	timeZone : row . timeZone ,
	9	f a v o u r i t e s C o u n t : row . f a v o u r i t e s C o u n t ,
	10	f r i e n d s C o u n t : row . f r i e n d s C o u n t ,
	11	l i s t e d C o u n t : row . l i s t e d C o u n t } )
		Listing 5: Cypher import command for Russian-tweet-troll
	5.2.2. 1 LOAD CSV WITH HEADERS FROM
	2	" f i l e : // / h e p a t i t i s . c s v " AS row
	3 MERGE
	4	( : H e p a t i t i s {Age : row . Age ,
	5	BILIRUBIN : row . BILIRUBIN ,
	6	ALKphosphate : row . ALKphosphate ,
	7	SGOT: row .SGOT,
	8	ALBUMIN: row .ALBUMIN,
	9	PROTIME: row .PROTIME} )

Listing 6: Cypher import command for Hypatitis dataset

Table 15 :

 15 Hetionet "Gene"edges Summary

	Src	edge	Dst	RelCnt
	Gene	PARTICIPATES GpBP	Biological Process	559504
	Gene	REGULATES GrG	Gene	265672
	Gene	INTERACTS GiG	Gene	147164
	Gene	PARTICIPATES GpMF	Molecular Function	97222
	Gene	PARTICIPATES GpPW	Pathway	84372
	Gene	PARTICIPATES GpCC	Cellular Component	73566
	Gene	COVARIES GcG	Gene	61690

MATCH ( Nodes )

RETURN l a b e l s ( Nodes ) AS Node Label ,

Count ( * ) AS Node Count ;

Another field of research is to explore the other scenarios for gradual patterns from property graphs like, Inter-Node-Label-Properties i.e., gradual patterns are to be extracted from the properties of nodes with different labels and Inter-Edge-Properties i.e., gradual patterns are to be extracted from the properties of different edge types.


Abid Raza

Rameez Khan

Fahad Mumtaz Malik

Fahad Mumtaz

Sampled-Data Sliding Mode Control Design of Single-Link Flexible Joint Robotic Manipulator

Keywords: Sampled-data control, Sliding mode control, Robotic manipulator

In this paper, we have designed a sampled data control law for the single-link flexible joint robotic manipulator using two different approaches. First, we have designed the sampled-data sliding mode control (SMC) based on the continuous time system. In the second approach, we have obtained the approximate discrete model of the system and then designed discrete sliding mode control based on this approximate system. Simulation results have been obtained and a performance comparison has been presented for both techniques.

I. INTRODUCTION

Robotic manipulators are widely being used in industry are highly nonlinear systems which often suffer from unmodeled dynamics and uncertainties. Recently control engineers have designed controllers for flexible joint robots but it is still very less as compared to the rigid robots. However, in many applications, the robotic manipulators have some flexible joints as well. At the same time, the flexibility of joints may limits the performance and robustness of the controllers designed for robots or may lead to instability [START_REF] Sweet | Redefinition of the Robot Motion Control Problem: Effects of Plant Dynamics, Drive System Constraints, and User Requirements[END_REF]. Also, the flexibility of joints can be considered a step for the flexible robot link [START_REF] Asada | Inverse Dynamics of Flexible Robot Arms. MODELING and Computation for Trajectory Control[END_REF] so to by studying the flexible joint manipulator can lead us to the flexible link which helps to have link lighter in weight that ultimately results in fast robotic motions. If the flexibility of joint is modeled by the spring, dynamic model of flexible joints can be obtained. Some advantages of flexible joints robotic manipulators over rigid manipulators are less control effort, fast motion, light weight and smaller dimension [START_REF] Chien | Adaptive Control for Flexible-Joint Electrically Driven Robot with Time-Varying Uncertainties[END_REF]- [START_REF] Hassanzadeh | Model Following Adaptive Control for a Robot with Flexible Joints[END_REF].

To design sliding mode controller for the flexible joint manipulator, state variables of each joint, velocities, acceleration and jerks of the link must be known [START_REF] Tomei | An Observer for Flexible Joint Robots[END_REF]. Since last two decades, dynamic modeling and non-linear control of robotic manipulators (flexible) is the area of research which received notable consideration. To design a control topology that is efficient and robust, the first and fundamental step is to develop an accurate dynamic model of a flexible joint robot. In industrial and space applications, we need the controller that can reduce the disturbance effects and can cope with modeling uncertainties. For flexible joints, a robust controller should be designed for the stabilization or tracking purpose that has negligible link vibration.

For this purpose, different techniques have been suggested for last two decades. For example, linear quadratic regulation (LQR) control technique is widely used for such control [START_REF] Ahmad | Vibration and Input Tracking Control of Flexible Manipulator Using LQR with Non-Collocated PID Controller[END_REF], another technique which is vastly used is adaptive output feedback controller based on a back stepping [START_REF] Yim | Adaptive Control of a Flexible Joint Manipulator[END_REF]- [START_REF] Ghorbel | Adaptive Control of Flexible-Joint Manipulators[END_REF]. In the case of nonlinear control, feedback linearization is the most renowned technique that is used for robotic manipulators [START_REF] Moberg | On Feedback Linearization for Robust Tracking Control of Flexible Joint Robots[END_REF]. The integral control technique described in [START_REF] Lin | Control of Flexible Joint Robots via External Linearization Approach[END_REF] and [START_REF] Spong | An Integral Manifold Approach to the Feedback Control of Flexible Joint Robots[END_REF], robust control that uses PD control and H∞ control, PD fuzzy and optimal control and sliding mode control [START_REF] Yeon | Practical Robust Control for Flexible Joint Robot Manipulators[END_REF]. In [START_REF] Mondal | Adaptive Second Order Terminal Sliding Mode Controller for Robotic Manipulators[END_REF], an adaptive second order terminal sliding mode controller for robotic manipulators is proposed.

Almost all the research for control of robotic manipulators is carried out in the continuous time domain. However, due to the increasing availability of microprocessor hardware, control algorithms are now usually implemented in digital controllers. In this paper, we have focused on sampled data sliding mode control, as SMC is nonlinear control and is more robust as compared to most of the conventional control techniques.

In this paper, we have focused on the stabilization of flexible joint robotic manipulator in discrete time domain. Sliding mode control is designed using sampled data control techniques and their comparison is carried out on the basis of simulation results. This paper is divided into five sections. In section 2 dynamic modeling of single link flexible joint robot is discussed. In section 3, sliding mode controller is designed that would stabilize the robotic manipulator. In section 4 sampled data control techniques are discussed. Using these techniques SMC is designed for the system, simulation results are presented to show the comparison of sampled data control techniques. Section 5 discusses the conclusion on the basis of these simulation results.

II. DYNAMIC-MODELLING OF FLEXIBLE JOINT SINGLE-LINK ROBOTIC MANIPULATOR

In this work, we have focused upon the flexible joint single link robotic manipulator. The dynamic model of single-link robotic manipulator with the flexible joints is derived using the Euler-Lagrange equations and is given by [START_REF] Apa | Nonlinear Systems[END_REF], [START_REF] Spong | Robot Dynamics and Control[END_REF] Fig. 1 shows the model of single link flexible joint robotic manipulator [START_REF] Moez Belhaouane | Improved Results on Robust Stability Analysis and Stabilization for a Class of Uncertain Nonlinear Systems[END_REF].

are the link positions, describes the link inertia whereas is the actuator inertia, the nominal load is denoted by , represents the joint stiffness and input torque is denoted by . we have designed a sliding mode controller using this state space model for the stabilization of this system in next section.

III. STABILIZATION USING SAMPLED DATA SMC BASED ON EMULATION

Sampled-data control refers to the control of a continuous system with discrete controller. There are two main techniques for sampled data control [START_REF] Laila | Design and Analysis of Nonlinear Sampled Data Control Systems[END_REF] [START_REF] Mumtaz | Sampled Data Control Based on Discrete Time equivalent Models[END_REF].

• Emulation design

• Approximate discrete model based control design Emulation design is considered as a simpler method to design a controller for sampled-data systems. In terms of system stability and performance, it is also considered as inferior design technique as compared to other methods. In designing controller by this technique sampling is completely overlooked. The continuous controller is discretized, in next step implementation is done using sample and hold devices.

Fig. 2 shows the block diagram of steps that are followed during the emulation design. In this technique of control design, the control law derived for the continuous time system is discretized. The classical sliding mode control suffers from chattering. Chattering is a severe problem especially in the mechanical system because it causes wear and tear in the system. There are different methods developed to reduce chattering. A well-known method is the replacement of the Fig. 2. Emulation design discontinuous signum function with the saturation function [START_REF] Spong | Robot Dynamics and Control[END_REF]. In this method, the real sliding is replaced with the sliding in a small vicinity of the discontinuous surface. The chattering issue can be overcome if we use saturation function instead of signum function. Consider the sliding surface This shows that we have designed efficient control law using emulation that stabilizes all the system states.

IV. STABILIZATION USING SAMPLED DATA SMC BASED ON APPROXIMATE DISCRETE MODEL DESIGN

In approximate discrete model based control design technique, the controller is designed by using the approximate discrete model of the plant in discrete time domain. For nonlinear systems, exact modeling of the system is almost impossible so approximate discrete model of the plant is used to design a controller for nonlinear systems. Then, this discrete controller is implemented using sample-and-hold devices. In this paper, we have discussed the controller design for sampled data control. 4 shows the block diagram of steps that are followed during the sampled data control using approximate discrete model. Using this technique SMC is designed in this section. The discretization is done using Euler forward difference method. The Euler model approximation is

State space model of manipulator (1) is

Using the approximate discrete model of the manipulator we will design SMC that will stabilize the system. The approximate discrete model is given by Consider the following sliding surface To stabilize it globally using Sliding mode control law where The constants are . is the position of the link and we can see this state stabilizes to the origin within 4 seconds. All other states also stabilize to origin approximately within four seconds. This shows that SMC designed using approximate discrete model is more efficient as compared to the previous technique and it also stabilizes all the system states.

V. COMPARISON OF APPROXIMATE DISCRETE MODEL AND EMULATION DESIGN SMC

In this section, a comparison of both sampled-data control techniques is presented. The simulation is done using MATLAB/SIMULINK for the implementation of the controller on robotic manipulator. The results of the comparison of both techniques are shown in Fig. 6.

In simulation results, stabilization of Single link flexible joint robotic manipulator using SMC based on emulation design and SMC based on approximate discrete model are compared. It is obvious that stabilization of states using approximate discrete model is quicker than that of SMC based on emulation design. In the case of SMC based on emulation design, there are oscillations of states before settling down to the origin. Also, time taken to stabilize using emulation design is more than that of approximate discrete model design. Results of SMC based on approximate discrete model stabilize the states quickly which shows SMC based on approximate discrete model is better stabilization approach for single link robotic manipulator than that of SMC based on emulation design.

VI. CONCLUSION

In this paper, SMC feedback control for single-link flexible joint robotic manipulator system is discussed. Two approaches for the design of sampled data sliding mode control are studied and simulation results are presented. It is clear that the SMC based on approximate discrete model is better as it stabilizes the states in less time for the same parametric values of the system. Moreover, by using SMC based on approximate discrete model the region of attraction is increased as compared to emulation design. The main outcome of Sampled Data SMC is the robustness. It (SMC based on approximate discrete model) is more robust against disturbance to conventional techniques used for robotic manipulator control (feedback linearization). SMC based on approximate discrete model has the insensitivity to parameter variations to a larger extent (greater region of attraction), fast dynamic responses and better disturbance rejection which is required for the smooth motions of the robotic manipulator. Now sampled data control is becoming popular than the continuous time. The sampled data controls that are derived and simulated can be further extended to sampled data observer. The states can be estimated with the help of an observer so we do not need to have sensors on all states. This work can also be extended for the n-link flexible joint robotic manipulator. Based on this work, a robust controller can also be designed for the tracking problem for the robotic manipulator.

Fig. 1 .

 1 Fig. 1. Model of a single-link, flexible joint manipulator Using this dynamic model state space model of this robotic manipulator is derived. State space model of manipulator is given by

( 3 )Fig. 3 .

 33 Fig. 3. States Stabilization using Sampled Data SMC based on Emulation In Fig. 3, state stabilization based on Emulation design is shown. These simulation results are generated by using MATLAB/SIMULINK. State is the position of the link and we can see this state stabilizes to the origin within 12 sec. All other states also stabilize to the origin within a certain time.This shows that we have designed efficient control law using emulation that stabilizes all the system states.

Fig. 4 .

 4 Fig. 4. SMC based on approximate discrete model

Fig.

  Fig.4shows the block diagram of steps that are followed during the sampled data control using approximate discrete model. Using this technique SMC is designed in this section. The discretization is done using Euler forward difference method. The Euler model approximation is

Fig. 5 .

 5 Fig. 5. States Stabilization using sampled data SMC based on approximate discrete model

Fig. 6 .

 6 Fig. 6. Estimated States Comparison of approximate discrete model, Emulation SMC: (a) State X 1 stabilization, (b) State X 2 stabilization, (c) State X 3 stabilization, (d) State X 4 stabilization

Abid Raza is with the Department of Electrical Engineering at College of Electrical and Mechanical Engineering, National University of Science and Technology, Islamabad, Pakistan, E-mail: abid.raza@ceme.nust.edu.pk

Rameez Khan is with the Department of Electrical Engineering at College of Electrical and Mechanical Engineering, National University of Science and Technology, Islamabad, Pakistan