Mehwish Alam
email: mehwish.alam@loria.fr

Amedeo Napoli
email: amedeo.napoli@loria.com

Interactive Exploration over RDF Data using Formal Concept Analysis

With an increased interest in machine processable data, many datasets are now published in RDF (Resource Description Framework) format in Linked Data Cloud. These data are distributed over independent resources which need to be centralized and explored for domain specific applications. This paper proposes a new approach based on interactive data exploration paradigm using Pattern Structures, an extension of Formal Concept Analysis, to provide exploration and navigation over Linked Data through concept lattices. It takes RDF triples and RDF Schema based on user requirements and provides one navigation space resulting from several RDF resources. This navigation space allows user to navigate and search only the part of data that is interesting for her.

I. INTRODUCTION

With the efforts of Semantic Web community many technologies have been offered for publishing machine-readable data on web. It annotates textual data with meta-data and makes it available in the form of ontologies and RDF graphs. One of the emerging source of data in the form of entityrelationship are published as Linked Open Data (LOD) cloud [START_REF] Bizer | Linked data -the story so far[END_REF]. As a contrast to textual resources, LOD does not need extensive preprocessing as it is already annotated in the form of entities and relationships. This structured format leads to other kind of challenges. One of the basic characteristics of LOD is that it follows a decentralized publication model [START_REF] Oren | Sindice.com: a document-oriented lookup index for open linked data[END_REF], meaning that the RDF graphs are published in several distributed resources, instead of creating one knowledge-base of statements any one can contribute new statements and make it publicly available. These resources have nothing in common except some shared terms. These decentralized graphs should be integrated through machine/software agents to provide domain specific applications. Moreover, external schemas in the form of ontologies or taxonomies can be linked to these data to make sense based on real world conception. Some of the resources in LOD only contain the schema without the instances such as SWRC ontology [START_REF] Sure | The swrc ontology -semantic web for research communities[END_REF] and some semantic web documents may only contain RDF triples without the RDF Schema such as DBLP 1 . The problem of how to provide applications which allow guided navigation and exploration over these data sources still persists. This paper introduces a framework based on interactive data exploration [START_REF] Van Leeuwen | Interactive data exploration using pattern mining[END_REF] paradigm using Pattern Structures [START_REF] Ganter | Pattern structures and their projections[END_REF] which is an extension of Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF].

The goal of exploratory data mining is to provide an expert with an insight into the data. One of the basic principals is to take into account the user-requirements and task-specific information. This way the patterns obtained by pattern mining algorithms are more relevant and interesting. For doing so, the pattern mining algorithms need to be combined with visualization tools for providing human-computer-interaction. Moreover, in order to make these pattern mining algorithms useful, there is a need to apply these algorithms to smaller datasets or only interesting and relevant subsets of the datasets. This enables user to interactively explore the data and identify patterns of interest.

In the current study, we use small datasets/subsets of datasets present in the form of RDF graphs over Linked Open Data and use FCA for giving the user an insight into the RDF datasets with the help of a visualization tool. During this process we directly involve the user in defining the datasets or part of datasets she is interested in. Then FCA is applied to these data and then patterns are obtained. Finally, the patterns computed are explored with the help of visualization tool. A complete iterative process of interactive data exploration on Linked Open Data is shown in Figure 1. This framework takes into account the prior requirements of the user and selects the data sources which are relevant to the user application distributed over several resources over Linked Open Data Cloud in the form of RDF triples and RDF Schema. This new approach called RDF-Pattern Structures, takes RDF triples and the RDF Schema present on distributed locations as an input and integrates them into one navigation space. This navigation space provides centralization over distributed RDF resources and keeps a partially ordered organization of RDF triples with respect to RDF Schema. It serves as a navigational as well as an interactive exploratory space for the user where she can identify the samples of the data which are not relevant to her while navigation. These identified samples are then hidden from the user and are recorded as irrelevant. In the second iteration a new navigation space is built on user demand which keeps only the information that is relevant to the user. This navigation space is explored and navigated for the purpose of data analysis and information retrieval over several data sources. To date this is the first attempt to deal with RDF data and exploration techniques with Pattern Structures and FCA.

The paper is structured as follows: section II gives the motivating example, section III introduces the background on the methodology used. Section IV details on creating a navigation space for RDF. Section V explains the process of interactive data exploration over the obtained navigation space. Section VI describes the experimental results of the framework. Section VII discusses the related work while Section VIII concludes the paper. ' She looks-up DBLP page of the authors working in her field. In that case she has to go through all the publications of each author and then browse through the DBLP pages of the co-authors of this author.

' Moreover, if she is searching for the papers which are targeting more than one problem areas such as information retrieval and World Wide Web then it is not possible to retrieve such papers directly.

' Finally, she will also not be able to detect the communities of the author who often work together to retrieve the relevant papers or establish the collaboration with these authors.

Accordingly we try to guide such kind of research based on a concept lattice which is built from an initial query and then is explored by the user according to her preferences.

III. PRELIMINARIES

A. Linked Open Data

Recently, Linked Open Data (LOD) [START_REF] Bizer | Linked data -the story so far[END_REF] has become a standard for publishing data on-line in the form of Resource Description Framework (RDF) 2 which can further be linked to other data sources published in the same format. The idea underlying RDF is based on storing statements about a particular resource, where each statement is represented as xsubject, predicate, objecty. A set of linked statements is referred to as RDF graph which constitutes an RDF triple store. For instance, i.e., t1, t2, t3, t4, t5, t6. DBLP is provided by University of Mannheim in the form of RDF triples generated by using D2R Server [START_REF] Bizer | D2r server -publishing relational databases on the semantic web[END_REF] which provides mappings from SQL Databases to RDF. The prefixes and full forms of all the abbreviations used in this paper are shown in Table I. Consider t1 i.e., xs 1 , p 1 , o 11 y, here s 1 is subject, p 1 is a predicate and o 11 is the object. Here, s represent the titles of the paper, p represent the predicates p 1 , p 2 , p 3 , o represent the authors or keywords. Each resource is defined in the form of URI. The subject denotes the resource and the predicate denotes properties of the resource and defines relationship between the subject and the object. In the rest of the paper we use dereferenced resources i.e., s 1 instead of complete URI. The information about the background knowledge related to topics related to the keywords of the papers is represented in the ACM Computing Classification System3 (ACCS) and are shown in triples t7, t8, t9. For the sake of simplicity here we use only two resources.

B. SPARQL

A standard query language for RDF graphs is SPARQL 4which mainly focuses on graph matching. A SPARQL query is composed of two parts the head and the body. The body of the query contains the Basic Graph Patterns (present in the WHERE clause of the query). It is composed of complex graph patterns that may include RDF triples with variables, conjunctions, disjunctions and constraints over the values of the variables. These graph patterns are matched against the RDF graph and the matched graph is retrieved and manipulated according to the conditions given in the query. The head of the query is an expression which indicates how the answers of the query should be constructed. Continuing the scenario in section II, the required data sets will be DBLP. A subset of these triples is selected based on user needs. For instance if user only wants the papers from the field of classification then for extracting this information the SPARQL query is given in Listing 1.

PREFIX rdfs:<http://www.w3.org/2000/01/rdf-schema#> PREFIX dc:<http://purl.org/dc/terms/> SELECT distinct ?title ?keywords ?author where { ?paper dc:creator ?a . ?a rdfs:label ?author . ?paper dc:subject ?keywords . ?paper dc:title ?title . FILTER( regex(STR(?keywords), "pattern based classification", "i") || regex(STR(?keywords), "unsupervised classification", "i"))

Listing 1: SPARQL for extracting triples. Prefixes are also defined in Table I.

C. Formal Concept Analysis

Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] is a mathematical framework used for a number of purposes, among which are classification and data analysis, information retrieval and knowledge discovery [START_REF] Carpineto | Concept data analysis -theory and applications[END_REF]. This section is based on the definitions from [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF]. A formal context K " pG, M, Iq, consists of a set of entities 5 This formal context is represented as a binary table. Table III presents a formal context related to papers and their authors. The titles of the paper are kept as entities while their authors are kept as attributes in the context. The fact that the paper has an author defines a relationship I and is represented as a cross in the binary context. According to the first row in Table III, the paper s 1 has the author o 21 .

From this binary context formal concepts are obtained keeping the classes of entities sharing some attributes. These concepts are computed by applying derivation operators. Given A Ď G and B Ď M , two derivation operators, both denoted by 1 , formalize the sharing of attributes for objects. Dually, the sharing of objects for attributes:

A 1 " tm P M | gIm f or all g P Au (1) B 1 " tg P G | gIm f or all m P Bu (2)
The two derivation operators 1 form a Galois connection between the powersets ℘pGq and ℘pM q. Maximal sets of objects related to maximal set of attributes correspond to closed sets of the composition of both operators 1 (denoted by 2 ). Let BpG, M, Iq be the set of all formal concepts for K " pG, M, Iq . Let K#1 " pA 1 , B 1 q and K#2 " pA 2 , B 2 q be two concepts, then

Consider the binary context in

K#1 is a subconcept of K#2 and K#2 is a superconcept of K#1, denoted by K#1 ď K#2, iff A 1 Ď A 2 and B 2 Ď B 1 .
An example of ď-relation between two concepts with respect to Table III will be: pts 5 u, to 22 , o 23 , o 25 uq ď pts 2 , s 5 u, to 22 , o 23 uq (see Figure 2). Figure 2 shows a complete lattice for Table III. In this figure the concept lattice is labeled using reduced labeling which means that all the sub-concepts of a concept also contain the attributes present in the intent of that concept by inheritance.

D. Pattern Structures

FCA [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] can process only binary context, more complex data such as graphs can not be directly processed by FCA. The concept lattice obtained by a binary context mixes between several types of attributes. Pattern structures, an extension of FCA, allows direct processing of such kind of context. The pattern structures were introduced in [START_REF] Ganter | Pattern structures and their projections[END_REF]. A pattern structure is a triple pG, pD, [q, δq, where G is the set of entities, pD, [q is a meet-semilattice of descriptions D and δ : G Ñ D maps an entity to a description. More intuitively, a pattern structure is the set of entities with their descriptions with a similarity operation [ on them which represents the similarity of entities. This similarity measure is idempotent, commutative and associative. If pG, pD, [q, δq is the pattern structures then the derivation operators can be defined as:

A l :" ę gPA δpgq f or A Ď G d l :" tg P G|d Ď δpgqu f or d P D
Each element in D is referred to as a pattern. The subsumption order over these patterns is give as follows:

c Ď d ô c [ d " c
The operator p.q l makes a Galois connection as described in section III-C. Now the pattern concept can be defined as follows:

Definition 3 (Pattern Concept): A pattern concept of a pattern structure "G, pD, [q, δ" is a pair pA, dq where A Ď G and d P D such that A l " d and A " d l , where A is called the concept extent and d is called the concept intent. Let us take an example of numeric data being processed by pattern structures in Table IV, The first record shows that the entity g 1 has the numeric value 5. The mapping δ : G Ñ D is given by δpg 1 q " xr5, 5s, r7, 7s, r6, 6sy which returns a description of a set of entities as a set of attributes. The lattice operation in the semi-lattice p[q is called a similarity operation between two descriptions. For example, let δpg 1 q " xr5, 5s, r7, 7s, r6, 6sy and δpg 2 q " xr6, 6s, r8, 8s, r4, 4sy then δpg 1 q[δpg 2 q " xr5, 6s, r7, 8s, r4, 6sy. Following the definition of a pattern concept in definition 3, ptg 1 , g 2 u, xr5, 6s, r7, 8s, r4, 6syq is a pattern concept. The obtained concept lattice is called as pattern concept lattice (see Figure 3)). The pattern structure dealing with numeric data is called as interval pattern structure [START_REF] Kaytoue | Revisiting numerical pattern mining with formal concept analysis[END_REF].

IV. TOWARDS RDF-PATTERN STRUCTURES

For creating navigation spaces over RDF as well as RDF Schema to provide navigation and exploration, the first operation is to select the RDF data set with no RDF Schema information and a suitable RDF Schema associated to these RDF triples from distributed data sources. This RDF schema will be used for organizing the RDF triples. An RDF Schema which will be used as a reference for comparing objects in the RDF triples is referred to as reference schema. This RDF Schema could also be a semantic resource such as Word Net or YAGO [START_REF] Suchanek | Yago: A core of semantic knowledge[END_REF] or DBpedia ontology. In the running scenario as we are targeting the organization of RDF triples in DBLP, we use ACCS as our reference schema. IV.

A subset of RDF triples is extracted according to user requirements and these RDF triples are defined in terms of patterns structures i.e., specifying the entities, their descriptions and the mapping from entities to description. After these two operations, we define a similarity measure [ over two descriptions which we generalize to the set of descriptions. After defining the similarity measure, we explain how an RDFpattern concept lattice is built using this similarity measure. More generally, an organization of RDF triples is built, based on concept lattice, w.r.t background knowledge. Finally, this lattice is used for navigation and interactive exploration purposes.

A. From RDF Triples to RDF-Pattern Structures

Firstly, we represent RDF triples extracted by the SPARQL query in Listing 1 as entities and their descriptions. The pattern structures are given as pG, pD, [q, δq. A subject in an RDF triple is mapped to an entity g in the set of entities G and predicate object pair (p:o) is mapped to a description d P D. As the set of entities G represent the subjects in triples, we represent it as S. The descriptions D are termed as descriptions and are denoted as D s .

The mapping of entities to description δ : S Ñ D s is given as follows: let s i P S then δps i q " td i1 , . . . , d iq u where i P t1, . . . , nu and d ij " tp j : to 1 , o 2 , . . . , o m uu where j P t1, . . . , qu. In the running scenario, we have p 1 " dc : subject and p 2 " dc : creator as shown in Table I. For p 1 the elements in the range can be compared with the help of reference schema and for p 2 the elements in the range are names of the author which can not be compared. After this organization a suitable RDF Schema is selected based on what user needs and the fact that it contains the objects in the triples. RDF Schema contains many constructs such as property, sub-property etc. along with rdfs: subClassOf information but in this work we use the RDF Schema predicates such as rdfs:subClassOf, skos:broader which lead to a tree structure in an RDF graph. An RDF Schema from ACM Computing Classification System is shown in Figure 4 for the set of objects connected to predicate p 1 . While the objects connected to the second predicate p 2 do not have any associated schema. The circles represent classes and the lines between these circles represent predicate rdfs:subClassOf/skos:broader. Each object is replaced with their classes i.e., C 1 po 11 q meaning that o 11 is an instance of class C 1 . Then, the description

B. Similarity Operation Over Classes

The similarity operation between two different classes is computed w.r.t. the Least Common Subsumer (LCS) of two classes. Definition 4 is the definition of Least Common Subsumer in a partially ordered set. We denote Ď as ĺ to avoid confusion between the concept lattice subsumption order. Definition 4 (Least Common Subsumer): Given a partially ordered set pS, ĺq, a least common subsumer E of two classes C and D (lcs(C,D) for short) in a partially ordered set is a class such that C ĺ E and D ĺ E and E is least i.e., if there is a class

E 1 such that C ĺ E 1 and D ĺ E 1 then E ĺ E 1 .
Given a reference schema which in our case is a tree, two elements whose LCS is J are considered as non-similar. Now we are in the reference schema, we consider classes (these are classes of the objects in triples). We want to compute the similarity of descriptions p i : X and p j : Y . First, we compute the similarity with the following constraints:

' Case 1: p i " p j .
' Case 2: we consider X and Y be the set of objects such that X " to i u, Y " to j u where i P t1, . . . , nu and j P t1, . . . , mu. Here we consider the case when there is no reference schema for the elements in X and Y . If

o i " o j then X X Y " to i u otherwise H.
For instance, in ' Case 3: In this case, let X " tCu and Y " tDu and the elements of X and Y are in the reference schema, we consider the classes of the elements and then the LCS of these elements. More formally, it can be defined as follows: Let us take two descriptions c " p 1 : C and d " p 1 : D then:

c Ď d " p 1 : C Ď p 1 : D ô p 1 : C [ p 1 : D " p 1 : C ô p 1 : lcspC, Dq " p 1 : C ô D ĺ C in the
C Ď D " p 1 : C Ď p 1 : D ô p 1 : C [ p 1 : D " p 1 : C ô p 1 : lcspc i , d j q " p 1 : c i where c i P C and d j P D It means that @c 1 P C, Dd 1 P D, d 1 ĺ c 1 .
The process is explained with the help of only one reference schema, multiple schemas can also be considered for several sets of objects.

For instance, lets choose two sets of classes C " tC 1 , C 2 , C 7 u and D " tC 4 , C 7 , C 8 u then the LCS between each pair will generate the set tC 12 , C 7 , C 14 u. As only the specific elements are retained, the final set obtained is E " tC 12 , C 7 u. Accordingly, E Ď C and E Ď D.

C. Building the RDF Pattern Concept Lattice

A representation of RDF triples as the set of descriptions given in Table V can be formalized as a pattern structure Firstly, we explain how to build the lattice for the descriptions having the reference schema. So we build the lattice only with the descriptions d i1 in Table V. The similarity between two subjects can be given as: A set of all pattern concept creates a pattern concept lattice shown in Figure 6. The subsumption order Ď between two patterns in pattern concepts pA 1 , d 1 q and pA 2 , d 2 q is given as follows: pA 2 , d 2 q Ď pA 1 , d 1 q ðñ @c 2 P d 2 , Dc 1 P d 1 , c 1 ĺ c 2 (in the reference schema). Similarly, it can be seen that pA 2 , d 2 q Ď pA 1 , d 1 q ðñ pA 1 , d 1 q [ pA 2 , d 2 q " pA 2 , d 2 q. Fig. 6: Pattern Concept lattice for DBLP and ACCS. Now we consider an example with all the cases described in the previous section. From Table V we have δps 1 q " pp 1 : In this case, the first description pp 1 : tC 1 , C 2 , C 7 uq has an associated reference schema, while the reference schema for second description pp 2 : to 21 uq is absent. Then the similarity between these two subjects is given as follows: The pair pA, dq " pts 1 , s 3 , s 4 u, xpp 1 : tC 12 uqpp 2 : tuqyq is a pattern concept (K#2 in Table VII) meaning that A l3 " d and d l3 " A. A set of all pattern concept creates a pattern concept lattice shown in Figure 7 and is termed as navigation space. Further details about the algorithm used for computing Least Common Subsumer are discussed in [START_REF] Alam | Revisiting pattern structures for structured attribute sets[END_REF]. It discusses how pattern structures is adapted for dealing with structured attribute sets.

K#ID Extent Intent K#1 s 1 ,
ts 1 , s 3 u 3 " ę sPts1,s3u δpsq " δps 1 q [ δps 3 q " xpp 1 : tC 1 , C 2 ,
K#ID Extent Intent K#1 s1, s2,
ts 1 , s 3 u l3 " ę sPts 1 ,s 3 u δpsq " δps 1 q [ δps 3 q " xpp 1 : tC 1 , C 2 ,

V. NAVIGATION AND INTERACTIVE EXPLORATION OVER PATTERN CONCEPT LATTICE

A. Navigation Operations:

Several navigation operations can be applied over the navigation space for obtaining precise information by navigation [START_REF] Codocedo | A semantic approach to concept lattice-based information retrieval[END_REF]. Here, each concept contains a group of subjects connected to the classes of the objects. The most general concepts near the top of the pattern concept lattice contain more number of subjects (entities) and lesser number of classes (description) meaning that the descriptions are very general. As the lattice is navigated downward more specific descriptions exist with lesser number of subjects.

Let us consider the scenario discussed in section II. We consider the navigation space shown in Figure 7. If user wants to retrieve the scientific papers on some specific topic such as World Wide Web, she would easily locate the concept containing only the papers about this topic i.e., K#2. The retrieved papers will be s 1 , s 3 , s 4 . For narrowing down her papers which are related to World Wide Web and Question Answering, the lattice can be navigated downwards to obtain K#5 which contain the two papers s 1 , s 4 . Now the user has the choice for further narrowing down w.r.t. more specified classes such as papers on Question Answering and recommender systems over RDF i.e., K#8. Fig. 8: Sublattices from Figure 7 The obtained concept lattice keeps sub-spaces (sub-lattices) which are interpreted as the space related to some topic or author. Figure 8 shows three example subspaces (Note that these subspaces are not extracted, these are just drawn separately to give a clear look into what the navigation space contains).

Figure 8 shows the sub-space related to an author o 22 which represents the community of the authors who work with this author. It contains 5 concepts K#3, K#7, K#10, K#11, K#12, K#13. K#3 contains all the papers published by the author o 22 , then this sub lattice can be navigated downwards to obtain specific concepts such as K#7 and K#11. These two concepts show co-authors of o 2 2 i.e., o 23 and o 25 . Based on the support of the concept i.e., It can also be seen that these two concepts represent the community of authors that often work together. The author o 22 has stronger communication with the authors in this concept. However, when we move downwards in the lattice the communication becomes weaker as the number of papers published together decrease. Based on the concepts K#7 and K#10, recommendation can be given to author o 25 to work with author o 23 . This way this navigation space can be used for recommending the social collaborations of the authors working in the similar field. Navigating from K#3 to K#11 the papers of the author o 22 are filtered with respect to the topic of the paper. Now let us consider two more sub-spaces w.r.t. the topic of the paper. Figure 8 provide the subspaces w.r.t. the topics World Wide Web and Retrieval tasks and goals respectively. Both the subspaces can navigated from top to bottom to obtain papers on general topics and can be navigated down to get a smaller list of papers based on sub-topics or the list of authors. The important point to notice is that the dotted part in both the subspaces represent the common space of the two topics C 12 and C 14 meaning that this common sub-sub-space keep the papers which are common to both the topics. It also keeps the combination of different classes which benefits the user while finding the subjects which related to more than one object or class of object simultaneously. The cases indicated in the navigation and interpretation scenario above is very generic and can be used in any domain.

B. Interactive Data Exploration over Navigation Space:

The navigation space obtained using the RDF-Pattern Structures serves as an interactive exploration space for the user. The user can perform interactive exploration while navigating from any of the dimensions (in our case authors and topic). Each concept act as a sample for exploration. These concepts keep classes of RDF triples as described before. Now the user can mark these samples as irrelevant. If the dimension explored by the user does not have a reference schema then all the sub-concepts of the selected concept are marked irrelevant automatically (i.e., author dimension) because the descriptions in this concept are inherited by its sub-concepts as described ins section III-C. However, if the dimension is organized w.r.t. a reference schema then all the subclasses of the class in the marked concept are also marked irrelevant. So, all the subconcepts of the marked concept containing the classes as well as its subclasses are marked irrelevant and are hidden from the user.

Suppose that the user is not interested in the papers on the topic of Semantic Web Description Languages i.e., C 11 . The navigation space shown in Figure 7 works as the exploration space, while navigating the user sees K#2 which contains papers on World Wide Web i.e., C 12 , she will mark this concept as irrelevant then the sub-concepts K#5, K#6, K#8, K#9, K#10 are also marked as irrelevant because these concepts either keep the class C 12 or a subclass of C 12 i.e., C 1 , C 2 , C 4 . Consider that the user is exploring the navigation space w.r.t author dimension and she marks K#3 as irrelevant because of the author o 22 then the sub-lattice obtained by following the links from K#3 until the bottom will be marked as irrelevant i.e., the concepts K#7, K#10, K#11, K#12, K#13.

VI. EXPERIMENTATION

In this section we discuss the experimental results for the RDF Pattern Structures. The proposed algorithm was coded in C++ and the experiments were performed using 3GB RAM on Ubuntu version 12.04. the papers from 2010-2014 published in international journals and conferences were selected. The papers chosen for this purpose were all in English Language. A pattern concept lattice (navigation space) was built using the paper titles, their keywords and authors. The results were visualized using the tool RV-Xplorer (Rdf View eXplorer) [START_REF] Alam | RV-Xplorer: A way to navigate lattice-based views over RDF graphs[END_REF]. It visualizes and allows interaction over the view defined over RDF graph through SPARQL queries by classifying SPARQL query answers in the form of a concept lattice. A dedicated web page to visualize and interact with the navigation space is available http://webloria.loria.fr/"alammehw/rdfps/#/. about Database Management System. Figure 11 shows the selected concept (K#139). This visualization allows the user to navigate upwards and downwards in the navigation space to access specific as well as general information as discussed in section V-A. If the user wants to navigate downwards in the lattice she should select one of the concepts in the yellow part of the selected concept which keep the sub-concepts (K#405, K#417, K#688). As the sub-concepts can be large in number we display what kind of papers the sub-concept of the lattice contains on mouse hover (see Figure 12). This phenomena guides the user in deciding which path to take while navigating. Now the user wants to narrow down papers about Relational database query languages, she will click on K#688 in the yellow part of the selected concept and then K#688 becomes the selected concept. This navigation is referred to as levelwise navigation. The navigation space on the left hand side of the visualization shows the complete lattice to track the position of the user. The selected concept is highlighted in red color. Now if the user is on the current concept and she is interested in the papers in this concept and wants to find other papers similarly to this paper then on mouse hover on this paper title. This will highlight all the concepts where this paper is present and the user can then directly navigate to the concept of interest. Toolkit also allows direct navigation from one concept to another without going from one hop to another. Such kind of navigation is referred to as direct navigation. Finally, it helps in decreasing the navigation space of the user by enabling her to focus on only the interesting parts in the navigation space and hide the rest of the lattice (see section V-B). If the user right-clicks on a concept in the navigation space, it is marked as irrelevant to the user and is hidden from the user. Once marked irrelevant the hidden part can not be accessed unless marked relevant.

VII. RELATED WORK

There have been several studies which apply FCA to RDF data but to-date this is the first attempt to deal with RDF graph and pattern structures. In [START_REF] Ferré | Conceptual navigation in RDF graphs with sparql-like queries[END_REF], the author focuses on allowing conceptual navigation to RDF graphs, where each concept is accessed through SPARQL-like queries. However, in our case several RDF resources can be navigated from one platform based on user requirements. Hiding the noninteresting part of the concept lattice is the feature very unique to our approach. Moreover, [START_REF] Coulet | Using pattern structures for analyzing ontology-based annotations of biomedical data[END_REF] introduces ontological pattern structures for enriching raw data with EL ontologies. But both the approaches consider only one resource at a time, hence not targeting the problem of decentralization. As a contrast to [START_REF] Coulet | Using pattern structures for analyzing ontology-based annotations of biomedical data[END_REF], RDF-Pattern Structures provide navigation space over RDF graphs as well as schema level information from several resources allowing user to access information from one platform.

In [START_REF] Amato | Categorize by: Deductive aggregation of semantic web query results[END_REF], the authors focus on clustering the SPARQL query answers based on some background knowledge and provide access to these clusters using a tree structure. As a contrast our approach can directly deal with RDF graphs. Moreover, several reference schemas related to different types of objects can be used through RDF Pattern Structures. Also, our approach can handle the objects which do not have any existing reference schema.

VIII. CONCLUSION

This paper proposes a new approach for navigating semantic web data and targets the capabilities of Pattern Structures to deal with RDF data. It provides navigation space over RDF data by organizing RDF triples with respect to reference schema with the help of RDF Pattern Structures.

To deal with such an organization, this paper proposes a new similarity measure. The pattern concepts in the concept lattice are considered as clusters of RDF triples used for information retrieval purposes over RDF data. The proposed framework is very general and can be applied to any RDF data set having heterogeneity i.e., some of the objects containing the reference schema and some of the objects containing no schema. One such application is the RDF triples contained in Drugbank where the objects are considered as drugs and the attributes are side effects, their categories and proteins. There are reference schemas regarding the side effects and categories of the such as MeSH and MedDRA but there is no reference schema defined for protein targeted by these drugs. One of the future directions is to use complete RDF Schema i.e., all the predicates instead of using only those predicates which are defining taxonomical structure. In such a case, the similarity measure can be modified to path between two classes instead of only computing the Least Common Subsumer.

Fig. 1 :

 1 Fig. 1: Interactive Data Exploration over RDF Data through Concept Lattices

  G and a set of attributes M and a binary relation I between G and M . Definition 1 (Formal Context): A formal context K :" pG, M, Iq, consists of two sets, a set of objects G and a set of attributes M and a binary relation I between G and M . The binary relation pg, mq P I or gIm is interpreted as "object g is in a relation I with an attribute m".

Definition 2 (

 2 Formal Concept): A formal concept of the context K :" pG, M, Iq is a pair pA, Bq with A Ď G, B Ď M , A 1 " B and B 1 " A. A is the extent and B is the intent of the concept pA, Bq. BpG, M, Iq denotes the set of all concepts of the context pG, M, Iq.

Fig. 2 :

 2 Fig. 2: Concept Lattice for the context in TableIII

Fig. 3 :

 3 Fig. 3: Pattern Concept lattice for TableIV.

Fig. 4 :

 4 Fig. 4: A small part from ACM Computing Classification System.

tpp 1 :

 1 to 11 , o 12 , . . . uqu is given as tpp 1 : tC 1 , C 2 , . . . uq This replacement is only performed for the description for which there is some RDF Schema present. The triples t1, t2, t3 in Table II are represented as entities and descriptions where the entity s 1 has the description δps 1 q " td 11 , d 12 u where d 11 " p 1 : tC 1 , C 2 , C 4 , C 7 u and d 12 " p 2 : to 21 , o 22 u.TableVshows a final representation of the RDF triples after replacing the objects with their corresponding classes (if reference schema is available) as entity descriptions.

Fig. 5 :' Case 4 :

 54 Fig. 5: (D s , [)

  C 7 uq [ pp 1 : tC 4 , C 5 uqy " xpp 1 : tlcspC 1 , C 4 q, lcspC 1 , C 5 q, . . . uqy " xpp 1 : tC 12 uqy xpp 1 : tC 12 uqy 3 " ts P S|xpp 1 : tC 12 uqy Ď δpsqu " ts 1 , s 3 , s 4 uThe pair pA, dq " pts 1 , s 3 , s 4 u, xpp 1 : tC 12 uqyq is a pattern concept (K#2 in Table VI) meaning that A 3 " d and d 3 " A.

Fig. 7 :

 7 Fig. 7: Pattern Concept lattice for DBLP and ACCS with and without reference schema.

Fig. 10 :

 10 Fig. 10: Concept

Fig. 9 :

 9 Fig. 9: Experimental Results.

Fig. 12 :

 12 Fig. 12: Details of Subconcept K#688

Fig. 13 :

 13 Fig. 13: Selected Sub-concept

  Table II keeps the RDF triples for papers with their keywords and authors present on DBLP

		(dc:title)	1/title	p4	rdfs:subClassOf
	C1	Web Crawling		C8	Recommender Systems
	C2	Web Indexing		C9	Clustering and Classification
	C3	Page and site Ranking		C10	Web Search Engines
	C4	RDF		C11	Semantic Web Description
	C5	OWL		C12	World Wide Web
	C6	Similarity Measure		C13	Retrieval Models and Ranking
	C7	Question Answering		C14	Retrieval Tasks and Goals

2 http://www.w3.org/RDF/ Index Term Index Term p1 http://purl.org/dc/elements/1.1/subject (dc:subject) p2 http://purl.org/dc/elements/1.1/creator (dc:creator) p3 http://purl.org/dc/elements/1.

TABLE I :

 I Prefixes and Abbreviations of the terms used in the rest of the paper.

	tid	Subject	Predicate	Object	Dataset
	t1	s1	p1	o11	DBLP
	t2	s1	p2	o12	DBLP
	t3	s2	p1	o16	DBLP
	t4	s2	p2	o22	DBLP
	t5	s1	rdf:type	Publication	DBLP
	t6	o12	rdf:type	Author	DBLP
	t7	o11	p4	C1	ACCS
	t8	o12	p4	C1	ACCS
	t9	C1	p4	C3	ACCS
	. . .	. . .	. . .	. . .	. . .

TABLE II :

 II RDF triples about papers with their authors and keywords from DBLP.

  Table III, the pair ({s 2 , s 5 }, {o 22 , o 23 }) is a formal concept because ts 2 u 1 = to 22 , o 23 u. and to 22 , o 23 u 1 = ts 2 , s 5 u, which means that the set of authors which are common to s 2 and s 5 are to 22 , o 23 u. It is represented as a maximal rectangle, highlighted in grey in Table III.

TABLE IV :

 IV Context with Numeric Data.

TABLE V :

 V RDF Triples as entities S and semantic descriptions D s .

  Table V we have d i2 for which there is no reference schema available. Lets choose two sets of objects then accordingly we have, p 2 : tto 22 , o 23 uX to 22 , o 23 , o 25 uu " p 2 : to 22 , o 23 u.

  s 2 , s 4 , s 5 pp 1 : tC 14 uq K#2 s 1 , s 3 , s 4 pp 1 : tC 12 uq K#3 s 1 , s 4 pp 1 : tC 7 , C 12 uq K#4 s 2 , s 4 , s 5 pp 1 : tC 8 uq

	K#5	s 3 , s 4	pp 1 : tC 4 uq
	K#6	s 1	pp 1 : tC 1 , C 2 , C 7 uq
	K#8	s 2 , s 5	pp 1 : tC 8 , C 9 uq
	K#7	s 4	pp 1 : tC 4 , C 7 , C 8 uq
	K#9	s 3	pp 1 : tC 4 , C 5 uq
	K#10	s 2	pp 1 : tC 6 , C 8 , C 9 uq

TABLE VI :

 VI Details of Pattern Concept lattice in Figure6. pS, pD s , [q, δq. When A Ď S is a set of entities and d P pD s , [q is a semantic description containing classes and objects then A l returns a set of common objects (if reference schema is absent) present in the descriptions of each subject in A and A ˛returns LCS of the classes (when reference schema is available) in the description of A. On the other hand, d l3 returns the set of subjects which are described by the objects/classes of objects included in d.

TABLE VII :

 VII Details of Pattern Concept lattice in Figure 7. tC 1 , C 2 , C 7 uq, pp 2 : to 21 uq and δps 3 q " pp 1 : tC 4 , C 5 uq, pp 2 : to 22 , o 24 , o 25 uq, where p stands for a predicate, C stands for a class and o stands for an object having no class.

  C 7 uqpp 2 : to 21 uq [pp 1 : tC 4 , C 5 uqpp 2 : to 22 , o 24 , o 25 uqy " xpp 1 : tC 1 , C 2 , C 7 uq [ pp 1 : tC 4 , C 5 uq, pp 2 : to 21 uq [ pp 2 : to 22 , o 24 , o 25 uqy " xpp 1 : tC 12 uqpp 2 : tuqy xpp 1 : tC 12 uqpp 2 : tuqy l3 " ts P S|xpp 1 : tC 12 uqpp 2 : tuqy Ď δpsqu " ts 1 , s 3 , s 4 u

https://www.acm.org/about/class/2012

http://www.w3.org/TR/rdf-sparql-query/

we name objects in FCA as entity to avoid confusion with the object in an RDF triple.

http://dblp.l3s.de/d2r/

http://www.rdfhdt.org/datasets/

http://www.w3.org/TR/2005/WD-swbp-skos-core-spec-20051102/

A. DBLP

The dataset used for experimentation was DBLP which keeps bibliographic information about millions of journals, conferences and authors. DBLP is converted to RDF and made available with the help of D2R server 6 . D2R server [START_REF] Bizer | D2r server -publishing relational databases on the semantic web[END_REF] provides a mapping from SQL database schema to RDF triples. However, in the current experiment the triple store used is the RDF data dump for DBLP is made available at RDF-HDT 7 [START_REF] Fernández | Binary RDF representation for publication and exchange (HDT)[END_REF]. RDF-HDT (Header, Dictionary, Triples) is a compact data structure for RDF data which provides efficient storage by compressing big datasets. It also provides search and browse operations without prior decompression. For the experimentation two subsets of datasets were extracted from DBLP. First includes all the papers on Artificial Intelligence (AI) and the second dataset includes all the papers on Machine Learning (ML). The reference schema used for this purpose is ACM Computing Classification System (ACCS) which is available on-line in several formats. The RDF Format used for ACCS uses SKOS 8 vocabulary, an application of RDF, to define the background knowledge about the topics of the papers. For conducting the experiments, titles were considered as entities and keywords and authors were kept as descriptions. ACCS was used as a reference schema for keywords and authors did not have any reference schema. After extracting the datasets navigation spaces are built on each of the data sets using RDF Pattern Structures. The statistics regarding both the data sets are shown in Table VIII. The number of triples extracted for AI dataset are 31045 and for ML are 18141. Figure 9(a) depicts the size of the navigation spaces created for AI and ML data sets. It can be seen that the size of navigation space is suitable for exploration purposes, however the interactive data exploration will further reduce its size when the user will mark the concepts as irrelevant. For example, in AI if the user is not interested in the papers about robotics then she can choose the general class as irrelevant. This will further decrease the navigation space of the user. Figure 9(b) illustrates the runtime for creating the navigation space. In the current experiments we extracted the RDF data using SPARQL queries. These SPARQL queries specify the initial user and task-specific requirements and extract only small subsets of data interesting for the user. Following this line it is safe to assume that our approach is well adapted to exploratory data mining as we are using small subsets of data for exploration and visualization using a visualization tool discussed in next section. Finally, the main focus of our approach is the qualitative analysis of the data and allow user with interaction and exploration.

B. Visualization

Another experiment was performed on the papers published by a Data Mining Team in a research lab. For this purpose all