Romain Mercier

Cédric Killian

Angeliki Kritikakou

Youri Helen

Daniel Chillet

Tolerating Errors in NoC: A Lightweight Region-Based Fault-Mitigation Method

Keywords: Network-on-Chip, Fault Mitigation, Approximate Computing, Hardware Costs Saving, Bit-Shuffling, BiSu, R-BiSu

Due to transistor shrinking and core number increasing in System-on-Chip (SoC), fault tolerance has become essential. Faults occurring to Network-on-Chips (NoCs) of those systems have a significant impact, due to the high amount of data crossing the NoC for communication. However, existing fault correction approaches cannot efficiently address several permanent faults on NoC NoC, due to their high hardware costs. To mitigate the impact of faults, existing works shuffle the bits inside a flit, transferring the impact of faults on the least significant bits. However, such approaches are applied at a fine-grained level, providing fault mitigation efficiency but with significant hardware costs. To address this limitation, this work proposes a region-based bit-shuffling technique, applied at a coarse-grain level, that trades off fault mitigation efficiency in order to save hardware costs.

I. INTRODUCTION

Since several decades, technology evolution enabled high transistor density reaching today billions of transistors per chip. While frequencies and chip density met the power limit, performance increase has been reached by adding more cores into a single chip, giving birth to System-on-Chips (SoCs). However, the increase in number of cores induced more and more data transfers, which cannot be handled by conventional communication means. To address this gap, Network-on-Chip (NoC) appeared as a scalable solution to manage communications between a large number of cores [START_REF] Xu | A Methodology for Design, Modeling, and Analysis of Networks-on-chip[END_REF].

In this technology era, NoC became more sensitive to permanent faults. As the transistor size reaches 10 nm and below [START_REF] Bohr | Logic Technology Scaling to Continue Moore's Law[END_REF], the engraving thinness causes more and more hardware defects, due to manufacturing process [START_REF] Dubrova | Fault-Tolerant Design[END_REF]. During system operation, aging defects [START_REF] Kundu | Network-on-Chip: The Next Generation of System-on-Chip Integration[END_REF], like electromigration, Negative-Bias Temperature Instability (NBTI), Hot Carrier Injection (HCI) and Time-Dependent Dielectric Breakdown (TDDB), and radiations [START_REF]Space Product Assurance: Techniques for Radiation Effects Mitigation in AASIC and FPGAs Handbook[END_REF] become additional sources of permanent faults. Manufacturing and aging defects are well known sources of Single Bit Upsets (SBUs), whereas radiations can lead to SBUs and Multiple Bit Upsets (MBUs) [START_REF]Single Event Effects Mitigation Techniques Report[END_REF]. While SBUs are composed by several Single Event Upsets (SEUs), which affect several bits in the same word, MBUs, also called burst faults, are induced by a single SEU, which affects several adjacent bits of the same data word.

In this context, fault tolerant techniques are commonly applied on the NoC to correct/mitigate permanent faults [START_REF] Khalil | Self-Healing Hardware Systems: A Review[END_REF].

These techniques are usually based on i) mitigation through routing algorithms [START_REF] Fu | ZoneDefense: A Fault-Tolerant Routing for 2-D Meshes Without Virtual Channels[END_REF], ii) hardware reconfiguration through spare resources or default backup path [START_REF] Ebrahimi | Minimal-Path Fault-Tolerant Approach Using Connection-Retaining Structure in Networks-on-Chip[END_REF], iii) correction through circuit replication [START_REF] Dubrova | Fault-Tolerant Design[END_REF] and iv) information redundancy [START_REF] Liva | Code Design for Short Blocks: A Survey[END_REF]. Although the aforementioned approaches are efficient for single permanent fault, they are less adequate for multiple permanent faults. They induce high hardware costs while their mitigation capabilities are limited, as discussed in Section II. A run-time approach, named Bit-Shuffling (BiSu), reduces the impact of multiple faults, by shuffling the bits inside a flit and transferring the impact of faults on the Least Significant Bits (LSBs) [START_REF] Mercier | Multiple Permanent Faults Mitigation Through Bit-Shuffling for Network-on-Chip Architecture[END_REF]. Although BiSu provides a finegrained protection, leading to high data protection, it requires a large number of additional hardware blocks in the NoC routers.

To reduce the hardware costs, while providing data protection, we propose a Region-based Bit-Shuffling technique (R-BiSu). Regarding environment conditions and the application error tolerance, we claim that the fault tolerance efficiency can be maintained with a coarse-grained mitigation. To achieve the R-BiSu technique, the NoC is divided into regions, and the shuffling/deshuffling technique is then applied at their borders. We propose a hierarchical method to compute the bit shuffling of region X × X from the bit shuffling of region (X -1) × (X -1). We design a hardware block that computes the register shuffling values, instead of using the dedicated core Intellectual Property (IP) of the routers. Last, but not least, we study in details the trade-off between the provided protection level and the required hardware costs of R-BiSu approach.

The rest of the paper is organized as follows: Section II presents the related work. Section III describes the R-BiSu method and Section IV presents the efficiency and the hardware costs of the method, when faults are injected in the NoC. Finally, Section V concludes this work.

II. RELATED WORK

The correction/mitigation of permanent faults in the NoC can be grouped into four sub-categories, summarised in the next paragraphs. Then, we present a fifth category that uses approximate approaches to mitigate faults in NoCs.

Routing algorithms are used to avoid faulty paths or faulty regions in NoCs, keeping only the healthy resources [START_REF] Fu | ZoneDefense: A Fault-Tolerant Routing for 2-D Meshes Without Virtual Channels[END_REF]. Typical techniques are adaptive routing algorithms [START_REF] Chen | A Deterministic-Path Routing Algorithm for Tolerating Many Faults on Wafer-Level NoC[END_REF] including rules to avoid congestion and deadlock during packet transmissions. Therefore, the hardware cost drastically increases with the size of the NoCs. Using routing algorithms can be efficient, as long as the number of faults is limited. Otherwise, the latency may become higher than the acceptable limit, leading potentially to unreachable IPs. Therefore, this solution is less suitable for large NoCs and multiple faults.

Reconfiguration replaces a faulty element of the NoC by spare resources at different levels [START_REF] Khalil | Self-Healing Hardware Systems: A Review[END_REF]. As spare resources can be used only once, these techniques have large overhead in terms of area and power consumption, while they can tolerate few faults. Other reconfiguration approaches use default-backup paths to avoid data corruptions and packet retransmissions [START_REF] Ebrahimi | Minimal-Path Fault-Tolerant Approach Using Connection-Retaining Structure in Networks-on-Chip[END_REF] with low area and power consumption. However, the latency drastically increases under multiple faults, due to the routing complexity and, in the worst case, several IPs become unreachable. Last, NoCs can be reconfigured in degraded mode, using only the remaining healthy resources [START_REF] Chen | A Deterministic-Path Routing Algorithm for Tolerating Many Faults on Wafer-Level NoC[END_REF]. Although this method handles permanent faults with lower hardware costs, the latency, throughput and network congestion increase and some IPs can become unreachable.

Circuit replication, called N-Modular Redundancy (N-MR), replicates N times, fully or partially, the architecture and votes the replicated outputs. The most popular approach is Triple Modular Redundancy (TMR) [START_REF] Dubrova | Fault-Tolerant Design[END_REF], where a module is replicated three times. Despite several approaches which focus on reducing the hardware costs [START_REF] Mukherjee | Triple Transistor Based Triple Modular Redundancy With Embedded Voter Circuit[END_REF], the area and power consumption overhead remains significantly high, e.g., more than three times for TMR. Moreover, multiple faults are masked if they occur in the same module and if more than one module is affected, the voter cannot correct the output.

Information redundancy inserts additional bits inside messages using Error-Correcting Codes (ECCs). The most commonly used coding scheme for NoC is the extended Hamming code, which can detect two faulty bits and correct only one. Despite the increase of the bus size of the complete NoC, Hamming code is efficient for correcting single faults [START_REF] Liva | Code Design for Short Blocks: A Survey[END_REF]. The number of correctable faulty bits can be increased by encoding the message on two dimensions [START_REF] Chen | Multi-Bit Transient Fault Control For NoC Links Using 2D Fault Coding Method[END_REF] and interleaving several ECCs [START_REF] Yu | Adaptive Error Control for NoC Switch-to-Switch Links in a Variable Noise Environment[END_REF]. However, using ECCs to correct more than one bit dramatically increases the hardware costs [START_REF] Sánchez-Macián | Hamming SEC-DAED and Extended Hamming SEC-DED-TAED Codes Through Selective Shortening and Bit Placement[END_REF]. As a result, the use of ECC approaches is limited against multiple faults.

The fifth category uses approximate computing for fault mitigation for NoC. In [START_REF] Najafi | Integer-Value Encoding for Approximate On-Chip Communication[END_REF], an approach statically changes the assignment of lines in datapath busses, by placing the Most Significant Bits (MSBs) on the borders of the bus, to attenuate the electromagnetic influences between neighbored lines. Contrary to our method, the assignment of lines cannot be modified at run-time, and thus, external effects and manufacturing defects cannot be addressed by this technique. In [START_REF] Wang | An Approximate Multiplane Network-on-Chip[END_REF], a multiplane NoC is proposed to ensure accurate and approximate communications using a second bufferless NoC. This method needs two parallel networks to operate increasing drastically the hardware costs. In [START_REF] Mercier | Multiple Permanent Faults Mitigation Through Bit-Shuffling for Network-on-Chip Architecture[END_REF], a bit-shuffling technique exploits the position of permanent faults and changes the order of bits inside a flit. However, this approach requires a large number of additional hardware blocks in the NoC routers. To reduce the hardware overhead, we propose a region-based bit-shuffling technique.

III. PROPOSED APPROACH

This section presents the proposed Region-based Bit-Shuffling approach (R-BiSu) aiming at hardware costs savings. Section III-A presents the target domain and assumptions. Section III-B provides the required background on the basic BiSu technique, whereas details are available in [START_REF] Mercier | Multiple Permanent Faults Mitigation Through Bit-Shuffling for Network-on-Chip Architecture[END_REF]. Last, the proposed R-BiSu method is described in Section III-C.

A. Target Domain and Assumptions

The BiSu approach mitigates multiple permanent faults, which can occur in NoC, and especially on the datapath part of the interconnect. As illustrated by the red flashes in Fig. 1, faults can be located in i) the interconnections between routers, or ii) the buffers and the crossbar within each router. Due to nanoscale technologies and power scaling, devices and components become more susceptible to multiple permanent faults [START_REF]Single Event Effects Mitigation Techniques Report[END_REF]. As the buffers and the crossbar are the biggest components of a router [START_REF] Deorio | A Reliable Routing Architecture and Algorithm for NoCs[END_REF], they have higher probability of accumulating faults due to radiation effects, manufacturing defects or other intrinsic failures. For the same reasons, interconnections are often impacted by permanent faults, usually expressed as stuck-at, short or bridge faults [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF]. Such faults are managed similarly by the proposed method.

In this work, we assume that the positions of the faults (described by an error mask) are provided by methods such as Built-In Self-Test (BIST) techniques [START_REF] Mohammed | Tolerating Permanent Faults in the Input Port of the Network on Chip Router[END_REF], which diagnose faults in interconnections and routers using Test Pattern Generator (TPG) and Output Response Analyzer (ORA) blocks. In these techniques, TPGs send test packets through the NoC, while ORAs analyze the received packets to identify if faults occurred between these two blocks, providing the fault position and type. Further details can be found in [START_REF] Bhowmik | A Low-Cost Test Solution for Reliable Communication in Networks-on-Chip[END_REF]. Other techniques available in the literature can be used to diagnose the permanent faults in a NoC [START_REF] Xiang | A Unified Test and Fault-Tolerant Multicast Solution For Network-on-Chip Designs[END_REF]. Some methods propose to locate faults inside a NoC region [START_REF] Hervé | Functional Test of Mesh-Based NoCs with Deterministic Routing: Integrating the Test of Interconnects and Routers[END_REF], but their error coverage is lower than the methods able to locate faults in a single interconnection or router. As the aforementioned techniques are largely studied in the literature, they are not detailed further.

As the objective of the proposed approach is to reduce the impact of multiple faults, instead of correcting them, the targeted domains are error resilient applications used in approximate computing and communication fields, i.e., applications which can tolerate errors until a certain level, such as image processing and machine learning [START_REF] Ahmed | AxNoC: Low-power Approximate Network-on-chips Using Criticalpath Isolation[END_REF].

B. Background: The basic BiSu Technique (BiSu)

The basic BiSu technique is implemented by extending a NoC router with extra hardware blocks, i.e., Shuffler (S) and De-shuffler (D) blocks, as shown in Fig. 1-(a). The flits of size S F bits, which transit the NoC, are divided into N SF blocks of bits, called Subflit (SF). Each SF consists of S SF bits. The shuffler block re-organizes the SFs with the objective of minimizing the impact of the faults. The de-shuffler block brings back the initial order of the SFs, as illustrated in Fig. 1-(b). The BiSu technique is applied to mitigate errors on the interconnection bus and inside the router. One extra D block is added in the routing controller (CTRL) to read the routing information of the shuffled header and forward the current packet towards the expected output.

S SF SF 0 SF 1 SF 2 SF 3 SF 0 SF 1 SF 2 SF 3 SF 0 SF 1 SF 2 SF 3 SF 0 SF 1 SF 2 SF 3 SF 0 SF 1 SF 2 SF 3 SF 0 SF 1 SF 2 SF 3 SF 3 SF 1 SF 2 SF 0 SF 3 SF 1 SF 2 SF 0 SF 3 SF 1 SF 2 SF 0 Shuffling De-Shuffling X X X X X X X X X X X X
The hardware architecture of the S and D blocks is composed of N SF multiplexers of N SF inputs of S SF bits to one output of S SF bits and registers, whose values give the multiplexers selections. The S and D blocks differ in the values of their registers, which are computed with the help of an algorithm that minimizes the impact of faults. The algorithm is executed on the dedicated IP core of the router based on the error mask, i.e., the position of the permanent faults.

Faults cannot be tolerated in the header flits, since they contain control information. When the header contains several unused bits, the BiSu technique uses them to mitigate faults. When the header contains few unused bits, the BiSu technique distributes the header information into two flits. In this way, the number of unused bits is artificially increased (by duplicating the header flit) with a small impact on the NoC latency, i.e., adding a single flit in a packet. The same technique is used for sensible data, e.g., instructions. Notice that, today's NoC are typically based on large buses. Hence, the header duplication is a solution that is applied only when BiSu technique cannot provide full protection using the unused header bits.

The BiSu technique takes into account differences between both data and flit sizes, when organizing the flits inside the Network Interfaces (NIs). To achieve this, a merger block and a de-merger block are added to the NIs, and more precisely, to the packetization and de-packetization blocks always included in classic NoC. These blocks sort the data in the flits at the subflit scale, to reduce as much as possible the fault impact on the data forwarded in the flits. Further details exist in [START_REF] Mercier | Multiple Permanent Faults Mitigation Through Bit-Shuffling for Network-on-Chip Architecture[END_REF].

C. Region-based Bit-Shuffling approach (R-BiSu)

In this work, we propose a region-based bit-shuffling technique that reduces hardware costs in terms of area and power consumption by relaxing the mitigation efficiency of the BiSu technique. The basic idea of R-BiSu is to split the NoC into regions of routers, which are globally protected with the BiSu method. We consider regular square regions, but the method is applicable for other region sizes and shapes.

Fig. 2 illustrates the notion of R-BiSu regions for a 4 × 4 NoC, where the regions are distinguished by the red dotted squares. The basic BiSu technique protects each interconnection and each router, as displayed in Fig. 2a, and corresponds to a region of size 0. To implement the R-BiSu technique, the registers of the S and D blocks need to be computed taking into account all faults that are present inside a region, which can be accumulated for a packet crossing the region. To achieve that, we propose a method to compute the error mask for a region, based on the error masks of each router and interconnection. Then, we design a hardware block to compute the values of the S and D registers, reducing the pressure on the dedicated core IP of the routers, which is used for the register computations in the basic BiSu method.

1) Region Error Mask (REM) Computation: The R-BiSu method uses information regarding the faulty state of the region, given by the REM, in order to reduce as much as possible the impact of faults. This is achieved through a hierarchical method, which computes the error mask of X ×X region based on error masks of (X -1)×(X -1) regions. Once the final REM is obtained, the registers of S and D blocks can be computed with low hardware costs, as shown in Section IV Fig. 2 shows an example of 4 × 4 NoC with 8-bit flit size and 2-bit subflit size. The NoC is affected by three faults on i) the bit number 4 of the router R 0 , ii) the bit number 2 of the router R 0 local interconnection and iii) the bit number 7 of the router R 5 north interconnection. The associated error masks indicating faults (highlighted by red color) for the different region sizes are displayed on the Fig. 2. Fig. 3 depicts how the REMs are computed for size 1 and size 2 based on the available error masks of the size 0. First, as depicted by the blue squares, the REMs of size 1 (REM 1 ) are computed based on an OR operation between the error mask of the router and the error masks of the local, north and east interconnections. As Fig. 2b depicts, the resulted error masks indicate the faulty bits of all the 1×1 regions. For example, the REM 1 0 indicates that the bit number 2 and 4 are faulty, which correspond to the error masks of size 0. To compute the REMs of size 2 (REM 2 ), the same operation is performed, as depicted by the green square of Fig. 3, based on the REMs of size 1 (REM 1 ). As displayed in Fig. 2c, the obtained error mask indicates the faulty bits for all the considered 1 × 1 regions.

Comparing the error masks of Fig. 2, we note that the faults are individually addressed when the region size is low, guaranteeing a high efficiency of the R-BiSu method. In this case, the least significant subflit is able to tackle several faults since. In our example, only one subflit is faulty at the same time during one shuffling operation, since the faults are scattered throughout the region, in several routers and interconnections. In this case, the impact of the faults on the data is reduced as possible. However, when the region size is increased, the scattered faults are now managed by a single shuffling operation, impacting the efficiency of the R-BiSu since the faults are impacting several subflits.

2) Computation of shuffler and de-shuffler registers: The computation of the shuffler and de-shuffler registers of the basic BiSu method is performed by the dedicated core of the IPs. The results are distributed to the shuffler and de-shuffler blocks through dedicated wires. Although the computation by the dedicated core of the IPs enables the hardware costs reduction, it increases the workload on the dedicated cores since the computation of the registers is added to the standard application workload. In order to remedy this issue, we design a dedicated hardware block inside the region that computes the value of the registers which control the multiplexers of the shuffler and de-shuffler blocks.

IV. EXPERIMENTAL RESULTS

This section presents the results in terms of efficiency and hardware costs. First, we present the experimental setup. Then, we analyse the impact of the region size on the efficiency of the R-BiSu technique, when data travel on a faulty NoC, using the Mean Square Error (MSE) and Bit Error Rate (BER) metrics. Last, we present the hardware costs in terms of area and power consumption. R-BiSu has similar impact on the latency as basic BiSU, which is negligible as shown in [START_REF] Mercier | Multiple Permanent Faults Mitigation Through Bit-Shuffling for Network-on-Chip Architecture[END_REF].

A. Experimental Setup

For our experiments, we consider a 8×8 NoC using the XY routing algorithm where the R-BiSu method is implemented into square regions. Packets of 16 flits are injected according to the TORNADO injection model, where each IP sends a packet at any other IP. The faults are randomly injected in the NoC datapath and modeled using the stuck-at fault model [START_REF] Dally | Principles and Practices of Interconnection Networks[END_REF]. We consider that the injected faults have always an impact on the data by applying a bit-flip on the affected bits. In this way, the masking effect due to data values is avoided and the fault impact is always visible. The MSE and the BER metrics, used to quantify the efficiency of the R-BiSu method, are computed based on 10, 000 fault injection sets. The CONNECT router [START_REF] Papamichael | CONNECT: Re-examining Conventional Wisdom for Designing Nocs in the Context of FPGAs[END_REF] is used as baseline for the hardware implementation. The header duplication is also implemented in R-BiSu technique in order to compute the worst case in terms of hardware costs. The results are synthesized on 28 nm FDSOI technology through High Level Synthesis (HLS) tools of Mentor Graphic, targeting a clock Fault Density (Per Router)

B. Efficiency Results

Fig. 4 depicts the MSE and the BER according to the fault density, i.e., the number of faults per router. Note that one fault per router does not mean that each router is affected by one fault, but that the mean of faults in routers is equal to one. The figures show the results obtained for different region sizes considering 64-bit flits divided into 4-bit subflits.

Fig. 4a depicts the MSE according to the fault density in the NoC. This figure shows that the size of the region has an impact on the efficiency of the R-BiSu method. It is observed that the MSE increases with the region size, until it reaches the same results with the unprotected NoC, when the density of faults is high. However, we observe that the size of the region can be increased from 0 to 1 with only a small impact on the MSE. For example, for a fault density equal to one fault per router, increasing the region size from the size 0 to the size 1 it increases the MSE only from 2.17 × 10 8 to 3.99 × 10 9 .

Fig. 4b displays the relative BER, taking as bases the BER obtained with the size 0, according to the fault density in the NoC. In this figure, we can note that the BER increases with the region size until reaching the same results than the unprotected case for the large region size with high fault density. Note that obtaining the same results than the unprotected case does not mean that the method is inefficient since the faults are deferred on the LSBs. For example, for a fault density equal to one fault per router, we observe that the relative BER is increased by 3% when the region size are increased from size 0 to size 1. This metric highlights the fact that faults are mitigated through the same LSB, when several shuffling operations are successively applied on the flit. As shown in Fig 4b, this effect is more perceptible with a high fault density and with low region sizes since the number of shuffling operations is higher for packet transmission. As the fault overlay reduces the BER, we can conclude that the method efficiency is higher when the region size is reduced.

C. Hardware Results

Fig. 5 presents the hardware costs of the R-BiSu method in terms of area and power overhead for different region sizes and subflit sizes. We observe that both area and power overheads decrease with the subflit size and the region size increase. Especially when the region size increases from size 0 to size 1, the area overhead is reduced from 48.3% to 31.4% and the power overhead is reduced from 31.5% to 22.3%.

The hardware block for the value computation of the shuffling and de-shuffling registers has a small impact on the global hardware cost of the method. For example, the area and power overheads are increased by 5.3% and 5.9%, respectively, for a region of size 1, and by 1.3% and 1.4%, for a region of size 2. The latency to compute the register values depends on the number of subflits present inside a flit. For example, if the flit is composed of 16 subflits, then the latency to update the registers is equal to 370ns. When the flit is composed of 8 and 4 subflits, the latency is 120 ns and 44 ns, respectively. Therefore, these hardware blocks have low hardware costs and can be used to relax the computation pressure on the dedicated core of the IPs. Moreover, these blocks can be shared between several regions to further reduce the hardware costs.

D. Trade-off between costs and efficiency

As previously mentioned, the hardware costs reduce when the size of the region is increased. Moreover, as shown in Section IV-B, the efficiency of the method is decreased when the region size increases. Based on these observations, a Pareto front exists between the hardware costs in terms of area and power consumption and the fault mitigation efficiency of the proposed method. Fig. 6 plots the Pareto front for different subflit sizes and region sizes considering 64-bit flits and a fault density equal to one fault per router. From the obtained result, we observe that there are cases where the basic BiSu does not belong to the Pareto front. Furthermore, the region size can be increased from size 0 to size 2 with a small impact on the efficiency, while the area and the power overheads are reduced from 48% to 33% and from 34% to 22%, respectively. Moreover, an increase of the subflit size, reducing hardware overheads, has a higher impact on the efficiency. Last, we conclude that increasing the region size is a better way to reduce the hardware overheads than increasing the subflit size.

V. CONCLUSION

In this work, we proposed a region-based bit-shuffling method with reduced hardware costs. To achieve that, a hierarchical method is proposed to compute the mask error of a complete region. In addition, we design a hardware block to compute the values of the registers of shuffler and de-shuffler blocks, relaxing the pressure on the dedicated core of the IPs. The obtained results show that an increase of the region size from size 0 to size 2 can reduce the hardware costs in terms of area and power consumption from 48% to 33% and from 34% to 22%, respectively, with a small impact on the MSE.

  NoC extended with the BiSu method.

Fig. 1 :

 1 Fig. 1: NoC extended with the BiSu method.

  Fig. 2b depicts a R-BiSu configuration of size 1, i.e., the NoC is divided in regions of 1 × 1 including the local IP. Fig. 2c depicts a R-BiSu configuration of size 2, i.e., the NoC is divided in regions of 2 × 2 routers including local IP. Comparing basic BiSu and R-BiSu techniques, the basic BiSu technique requires 304 S and D blocks, whereas the 1 × 1 configuration reduces the number of S and D blocks to 164, reducing area and power consumption. When the size of the regions is increased to 2 × 2, the number of S and D blocks decreases to 80, as shown in Fig. 2c.

2 Fig. 2 : 5 Fig. 3 :

 2253 Fig. 2: Illustration of the R-BiSu technique for different region sizes.

Fig. 4 :

 4 Fig. 4: Experimental efficiency of the R-BiSu method at the NoC-scale. (S F = 64, S SF = 4)

Fig. 5 :

 5 Fig. 5: Hardware overhead comparison for the R-BiSu method.

Fig. 6 :

 6 Fig. 6: Highlighting of the Pareto front at the NoC-scale.


Sébastien Ferré
email: ferre@irisa.fr

Conceptual Navigation in Large Knowledge Graphs

A growing part of Big Data is made of knowledge graphs. Major knowledge graphs such as Wikidata, DBpedia or the Google Knowledge Graph count millions of entities and billions of semantic links. A major challenge is to enable their exploration and querying by end-users. The SPARQL query language is powerful but provides no support for exploration by endusers. Question answering is user-friendly but is limited in expressivity and reliability. Navigation in concept lattices supports exploration but is limited in expressivity and scalability. In this paper, we introduce a new exploration and querying paradigm, Abstract Conceptual Navigation (ACN), that merges querying and navigation in order to reconcile expressivity, usability, and scalability. ACN is founded on Formal Concept Analysis (FCA) by defining the navigation space as a concept lattice. We then instantiate the ACN paradigm to knowledge graphs (Graph-ACN) by relying on Graph-FCA, an extension of FCA to knowledge graphs. We continue by detailing how Graph-ACN can be efficiently implemented on top of SPARQL endpoints, and how its expressivity can be increased in a modular way. Finally, we present a concrete implementation available online, Sparklis, and a few application cases on large knowledge graphs.

Introduction

A growing part of Big Data is made of knowledge graphs. The World Wide Web Consortium 2 has defined a number of standards for representing them (RDF), reasoning about them (RDFS and OWL), and querying them (SPARQL) [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF]. A knowledge graph is a collection of entities and values interlinked with semantic relationships. In RDF, every link is a triple (source entity, relation, target entity). Examples of entities are France and Paris, and examples of triples are (France, capital, Paris) and (France, population, 66000000). The notion of knowledge graph has been popularized by the Google Knowledge Graph, and the several web search engines have agreed on the schema.org vocabulary to support semantic search [START_REF] Mika | On schema.org and why it matters for the web[END_REF], i.e. search in terms of entities and relationships rather than search in terms of pages and keywords. The two main open sources of knowledge graphs are Linked Open Data 3 (LOD) and microdata 4 . Both count more than 30 billions of triples each. Examples of large open datasets are DBpedia, Wikidata, or YAGO, each of which contains billions of triples.

A major challenge with knowledge graphs is to enable their exploration and querying by people who are interested in the data but are not necessarily proficient in the semantic technologies. A simple kind of exploration is to browse the knowledge graph, surfing from entity to entity by following links. However, this kind of exploration can only answer the simplest questions, like "What is the capital of Paris?" or "What is the birth date of the president of the commission of the European Union?". We are interested in answering questions that involve sets of entities, and shared properties, like "Who are the actors playing most often in films directed by Tim Burton since 2000?". The SPARQL query language [START_REF]SPARQL 1.1 query language[END_REF] allows to answer a wide range of questions (high expressivity) but it is a formal language targeted at computer scientists. Even for SPARQL practitioners, writing SPARQL queries is a tedious task because of the need to know the data schema, and because of inevitable trial and errors. Question Answering (QA) approaches [START_REF] Höffner | Overcoming challenges of semantic question answering in the semantic web[END_REF] are attractive because they rely on spontaneous natural language but they lack expressivity and reliability in practice, because of the challenge of natural language understanding. There exist yet other approaches to help with the exploration and querying of knowledge graphs (e.g., semantic faceted search [START_REF] Hildebrand | /facet: A browser for heterogeneous semantic web repositories[END_REF][START_REF] Arenas | SemFacet: Semantic faceted search over YAGO[END_REF], query builders [START_REF] Kaufmann | Evaluating the usability of natural language query languages and interfaces to semantic web knowledge bases[END_REF]) but they all tend to trade expressivity for usability.

Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis -Mathematical Foundations[END_REF] automatically defines from data a navigational structure, called concept lattice, which has been used early for data exploration and analysis [START_REF] Godin | Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods[END_REF][START_REF] Carpineto | A lattice conceptual clustering system and its application to browsing retrieval[END_REF][START_REF] Ferré | A file system based on concept analysis[END_REF]. Each concept can be understood as the equivalence class of questions that have the same answers. The extent of the concept is that set of answers, and the intent of the concept is the most specifc question in the equivalence class. The intent represents what all answers have in common. The lattice structure partially orders the concepts according to inclusion between concept extents, with more general concepts (larger extents, smaller intents) at the top, and more specific concepts (smaller extents, larger intents) at the bottom. The concept lattice can be used for exploration and querying as follows. The user starts at the top concept, i.e. with the empty question, and with all entities as answers. She can then move in the lattice down and up according to the lattice structure. For example, she can move down to the concept of films, then down again to the concept of films directed by Tim Burton, and again to films directed by Tim Burton since 2000. From there, she can move down for each actor playing in those films; or she can move up to films since 2000. The major advantage of concept lattices is that they materialize a possibly infinite set of questions into a finite navigational structure that is automatically derived from data. However, their major drawback is that their size explodes with the amount of data, and the range of questions.

In this paper, we show how to reconcile expressivity, usability, and scalability in the exploration and querying of knowledge graphs. Compared to a previous paper [START_REF] Ferré | Conceptual navigation in RDF graphs with SPARQL-like queries[END_REF], our approach has improved a lot in expressivity (from a subset of SPARQL 1.0 to most of SPARQL 1.1), in usability (introducing a natural language interface), and in scalability (from tens of thousands of triples to billions of triples). First, to address expressivity, we present an extension of FCA to knowledge graphs, Graph-FCA, where questions and concept intents are analogous to conjunctive SPARQL queries (Section 2). Second, we introduce Abstract Conceptual Navigation (ACN) as an exploration and querying paradigm that reconciles expressivity and usability by relying on the concept lattice to guide end-users in the building of complex queries, and we instantiate it to Graph-FCA (Section 3). Third, we address scalability on large knowledge graphs by leveraging the computation power of SPARQL endpoints (Section 4). From there, we demonstrate how our paradigm can rise in expressivity (e.g., logical operators, expressions, aggregations) in an incremental way without losing on usability and scalability (Section 5). We then present Sparklis, a concrete implementation of our approach available online, and we illustrate it on a few application cases (Section 6). Readers more interested by practical aspects can read this section first, before diving into the more technical sections. Finally, we conclude and draw a few perspectives (Section 7).

2 Graph-FCA: Extending FCA to Knowledge Graphs Graph-FCA [START_REF] Ferré | A proposal for extending formal concept analysis to knowledge graphs[END_REF][START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF] is an extension of FCA for multi-relational data, and in particular for knowledge graphs of the Semantic Web [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF]. The specific nature of Graph-FCA is to extract n-ary concepts from a knowledge graph using k-ary relations. The extents of n-ary concepts are sets of n-ary tuples of graph nodes, and their intents are expressed as a graph pattern with n distinguished nodes, which are called the projected nodes. For instance, in a knowledge graph that represents family members with a "parent" binary relation, the "sibling" binary concept can be discovered, and described as "a pair of persons having a parent in common".

Classical FCA corresponds to the case where all relations are unary (k = 1), i.e. when graph nodes are disconnected, and where all concepts are unary too (n = 1), i.e. when concept extents are sets of graph nodes. Graph-FCA differs from Graal [START_REF] Liquiere | Structural machine learning with galois lattice and graphs[END_REF] and applications of Pattern Structures to graphs [START_REF] Kuznetsov | Learning closed sets of labeled graphs for chemical applications[END_REF] in that here objects are the nodes of one large knowledge graph, instead of having each object being described by a small graph. Graph-FCA shares theoretical foundations with the work of Kötters [START_REF] Kötters | Concept lattices of a relational structure[END_REF], where PGPs are called windowed structures. Another extension of FCA to multi-relational data is Relational Concept Analysis (RCA) [START_REF] Rouane-Hacene | Relational concept analysis: mining concept lattices from multi-relational data[END_REF]. Compared to Graph-FCA, RCA is limited to unary and binary relations and to unary concepts, and its concept intents are tree-shaped graph patterns. However, RCA supports various quantifiers (called relational scaling operators, while Graph-FCA is limited to existentials.

Graph Context

Whereas FCA defines a formal context as an incidence relation between objects and attributes, Graph-FCA defines a graph context as an incidence relation between tuples of objects and attributes. A graph context is a triple K = (O, A, I), where O is a set of objects, A is a set of attributes, and I ⊆ O * ×A is an incidence relation between object tuples o = (o 1 , . . . , o k ) ∈ O k , for any arity k, and attributes

a ∈ A. O * = k∈N O k = O ∪ (O × O) ∪ (O × O × O) ∪ . . .
denotes the set of all tuples of objects. A graph context is therefore a labeled multi-hyper-graph, where objects are the nodes, incidence elements are the hyper-edges, and attributes are hyper-edge labels. Note that attributes can be interpreted as k-ary predicates, and graph contexts as First Order Logic (FOL) models (without functions and constants). An hyperedge ((o 1 , . . . , o k ), a) can be seen as the FOL atom a(o 1 , . . . , o k ), and represents a knowledge fact. In the following, we indifferently use the terms hyper-edge, atom, and fact. Different kinds of knowledge graphs, such as Conceptual Graphs [START_REF] Sowa | Conceptual structures. Information processing in man and machine[END_REF], RDF graphs, or RCA contexts, can be directly mapped to a graph context.

We illustrate Graph-FCA on an example taken from project KNOMANA 5 and used in the RCA literature. It is about plants that treat pests found in African countries, which possess such plants. Figure 1 shows a graphical rep- resentation of the graph context. The objects are plants (e.g. aspiliaAfricana), pests (e.g. aspergillusParasiticus), and countries (i.e. Benin). They are represented as rectangles. The attributes are either unary attributes, like classical FCA attributes (e.g., plant, westernAfrica, aromatic), or binary attributes (e.g., treats, isFoundIn, possesses). The former are represented in the bottom part of object rectangles, and the latter are represented as directed edges between objects. More generally, a unary edge a(x) is represented as a label in the bottom part of the rectangle representing object x; a binary edge a(x, y) is represented by an edge from x to y labeled by a; and other edges a(x 1 , . . . , x k ), for k > 2, are represented as ellipses labeled by a, having an edge labeled i to each node x i .

Graph Patterns

Whereas FCA is about finding closed sets of attributes, Graph-FCA is about finding closed graph patterns. A graph pattern is similar to a graph context but with variables instead of objects as nodes, in order to generalize over particular objects. A key aspect of Graph-FCA is that closure does not apply directly to graph patterns but to Projected Graph Patterns (PGP), i.e. graph patterns with one or several distinguished nodes. Those projected nodes define a projection on the occurences of the pattern, like a projection in relational algebra. For example, the PGP (x, y) ← parent(x, z), parent(y, z) defines a graph pattern with two edges, parent(x, z) and parent(y, z), and with projection on variables x and y. It means that for every occurence of the pattern in the context, the valuation of (x, y) is an occurence of the PGP. It can be used as a definition of the "sibling" relationship, i.e. the fact that x and y are siblings if they have a common parent z.

PGPs are analogous to anonymous definitions of FOL predicates and to conjunctive SPARQL queries. They play the same role as sets of attributes in FCA, i.e. as concept intents. Set operations are extended from sets of attributes to PGPs. PGP inclusion ⊆ q is based on graph homomorphisms [START_REF] Hahn | Graph homomorphisms: structure and symmetry[END_REF]. It is similar to the notion of subsumption on queries [START_REF] Chekol | SPARQL query containment under SHI axioms[END_REF] or rules [START_REF] Muggleton | Inductive logic programming: Theory and methods[END_REF]. PGP intersection ∩ q is defined as a form of graph alignment, where each pair of variables from the two patterns becomes a variable of the intersection pattern. It corresponds to the categorical product of graphs (see [START_REF] Hahn | Graph homomorphisms: structure and symmetry[END_REF], p. 116), and to the least general generalization of Plotkin [START_REF] Plotkin | Automatic methods of inductive inference[END_REF].

Graph Concepts

The Galois connection that is the basis for computing concepts is defined in Graph-FCA between n-ary PGPs (Q n , ⊆ q ) and n-ary object relations (R n , ⊆), where an n-ary object relation is a set of n-ary object tuples (R n = 2 O n ). The connection from PGP Q ∈ Q n to object relation Q ∈ R n is analogous to query evaluation, and the connection from object relation R ∈ R n to PGP R ∈ Q n is analogous to relational learning [START_REF] Muggleton | Inductive logic programming: Theory and methods[END_REF]. In the definitions of Q and R below, the PGP (o, I) represents the description of an object tuple o by the whole incidence relation I seen from the relative position of o.

Q := {o ∈ O n | Q ⊆ q (o, I)}, for Q ∈ Q n , for n ∈ N R := q {(o, I)} o∈R , for R ∈ R n , for n ∈ N
From there, concepts can be defined in the usual way, and proved to be organized into lattices. A concept is a pair (Q, R) such that Q = R and R = q Q. The arity of the projected tuple of Q must be the same as the arity of object tuples in R. It determines the arity of the concept. Unary concepts are about sets of objects, while binary concepts are about relationships between objects, and so on. Note however that the intent of an unary concept can mix attributes of different arities. Unlike RCA, there is a concept lattice for each concept arity rather than for each object type. Figure 2 displays a compact representation of the graph concepts about plants, pests, and countries as a set of graph patterns. Each rectangle node x identifies a unary concept (e.g., Q1a) along with its extent (here, aspili-aAfricana, chromolaenaOdorata). The concept intent is the PGP x ← P , where P is the subgraph containing node x and all dark-colored nodes (called the pattern core). In the first pattern, all concepts belong to the core, while on the second pattern, only Q2a, Q2b, Q2c belong to the core. By reading the graph, we learn that Concept Q1a is the concept of "plants that treat pests attacking peanuts, which are found in Western Africa countries that possess the plant, where the plant has a number of features such as being toxic, aromatic, applicable to essential oil, etc." This concept therefore identifies the valuable situation where a country possesses plants to treat some pests they have. Concepts Q1b and Q1c have the same graph pattern as Q1a but a different projected node, on pests for Q1b and on countries for Q1c. N-ary concepts are obtained by picking several projected nodes. For example, (Q1a,Q1b,Q1c) is a ternary concept whose instances are the object triples (aspiliaAf ricana, aspergillusP arasiticus, Benin) and (chromolaenaOdarata, aspergillusOchraceus, N igeria). It represents the cyclic relationship existing between plants, pests, and countries in Western Africa countries. Pattern Q2 shows that every plant (Q2f) treats some pest (Q2c), and every pest (Q2d) is found in some country (Q2e) but not all countries possess a plant treating a pest. The concept identifiers between bracket, e.g. Q2d(fe), indicate which nodes of the pattern belong to the concept intent, in addition to the core. For Q2d(fe), it means that "all four pests are found in some country (Q2e), and are treated by some plant (Q2f ) that also treats a pest (Q2c) that can be treated by a more specific kind of plant (Q2b), one that is toxic and can be used for essential oils and extracts."

Graph Concept Lattice

The generalization ordering between concepts, hence (part of) the concept lattice, is shown in Figure 3. The relation from concepts to their children is represented by dashed arrows. The top concept that contains all objects is omitted for clarity. In this representation, the hyper-edges with arity at least 2 are shown inside rectangles with unary attributes. For example in Q1a, the label possesses c _ says that there is a binary edge labeled possesses from concept Q1c to this concept Q1a; and label treats _ b says that there is a binary edge from Q1a to Q1b (edges are never across patterns). For example, concepts Q1a, Q1b, Q1c are respectively specializations, hence sub-concepts, of concepts Q2b, Q2c, Q2a. The latter are more general concepts respectively for plants, pests, and countries.

Conceptual Navigation in Graph-FCA Lattices

The idea of conceptual navigation is to see the concept lattice as a navigation structure, with concepts as navigation places, and the lattice structure as a set of navigation links between concepts. In a basic setting, the concept lattice is displayed graphically, and the user can visually navigate it. However, this only works for very small datasets generating at most a few dozen concepts. A more scalable approach consists in displaying only a local view centered on the current concept in the navigation process [START_REF] Ferré | An introduction to logical information systems[END_REF][START_REF] Ducrou | An intelligent user interface for browsing and search MPEG-7 images using concept lattices[END_REF][START_REF] Alam | Exploratory knowledge discovery over web of data[END_REF]. Typically, the local view consists of the extent and intent of the current concept, and navigation links to the neighbour concepts. The neighbour concepts are generally the parents and children of the current concept in the Hasse diagram of the concept lattice, but nothing prevents to have links to more distant concepts. Navigation links are generally labeled by the properties that have to be added or removed from the current intent in order to get the intent of the target concept.

The major advantage of local views over concept lattices is that the amount of information to be displayed does not grow exponentially with the size of data, like concept lattices, but rather linearly. This fosters expressivity because higher expressivity leads to many more concepts but not to bigger representations of individual concepts. Conceptual navigation with local views also satisfies usability because the user experience is similar to that of faceted search [START_REF]Dynamic taxonomies and faceted search. The information retrieval series[END_REF], which is commonly used in e-commerce websites. Indeed, users simply have to make a choice among navigation links at each step, and they get a clear view of their current state at all time.

Abstract Conceptual Navigation (ACN)

We first introduce and formalize a very generic framework for conceptual navigation based on local views, called Abstract Conceptual Navigation (ACN). We call it abstract by analogy with an abstract class in object-oriented programming, where class members are given a specification but not yet an implementation. The genericity concerns two aspects: (1) the nature of con- cept intents and extents in order to foster expressivity, and (2) the contents of local views in order to foster usability. In the next section, we instantiate ACN to Graph-FCA concept lattices, where intents are PGPs (projected graph patterns), and extents are object relations. An instantiation on classical FCA would have sets of attributes as intents, and sets of objects as extents.

The main novelty of ACN w.r.t. conceptual navigation, as presented above, is the replacement of the concept intent by a query and an index in the local view (see Figure 4). The motivation is that concept intents are often at the same time overly specific, and not informative enough. This is because the concept intent is defined as the set of all and only the properties that are shared by all elements of the concept extent. The query is a subset of the intent that contains only intensional elements selected by the user during her navigation. The query is related to the intent in that both characterize the same extent. The query is useful to the user to let her know the current state of the navigation in a concise way. The index is typically a superset of the intent by including properties that are shared only by a subset of the extent, along with their frequencies in the extent. This provides the user with the distribution of the extent elements over the set of properties: e.g. "80% films by Tim Burton have genre Fantastic". Those properties can then be used as navigation links to more specific concepts. Finally, the extensional component is replaced by result to allow for diverse representations of the extent, e.g. tables, maps or charts.

ACN is formally defined by the following components:

knowledge base (K). K is a knowledge base that contains the formal representation of facts, rules, ontological axioms, taxonomies, etc. Its content is constrained by the needs of the application, and the availability of data and domain knowledge. It is an implicit parameter of all ACN operations defined below. query language (Q) and initial query (q 0 ). Q is a query language, i.e. a set of expressible queries. A query is a summary of the navigation history, and expresses the user information needs. The current query q ∈ Q characterizes the current concept, and is part of its intent. Here, query should be understood in a broad sense, and may include closed and open questions, analytical questions (OLAP), sets of keywords, folder paths, updates, commands, ontological assertions, etc. The initial query q 0 is a fixed query, generally very simple, that determines the starting point of the navigation process. result (R and result ∈ Q → R). R is the set of all possible results (a.k.a., query results), and result is a function from queries to their result, given a knowledge base K. The query result is any piece of data representing the concept extent, returned to users from the query evaluation. It can be a set of values, an answer list, a table, etc. For some queries, e.g. updates, the knowledge base may be modified as a side effect. index (S and index ∈ Q × R → S). S is the set of all possible indices over the extent, and index is a function from queries and their result to their index. An index is at the same time a summary over the extent, and a set of query refinements. The intent of the current concept is typically part of the index. Its role is to provide feedback and guidance. links (links ∈ Q × R × S → 2 Q ). Function links defines a set of navigation links from the current concept to related concepts. Links can be derived from any component of the current concept: the query, the result, or the index.

The main benefit of ACN is to subsume three paradigms of information access: query languages, navigation structures, and interactive views.

• ACN as a query language. Q is the query language, and result defines query results for each query. Indices and links are void. For instance, SPARQL editors can be seen as partial ACN instances where the query language is SPARQL, and where results are tables of RDF nodes or RDF graphs. • ACN as a navigation structure. Navigation places are specified by queries in Q, and navigation links are given by the ACN component links. Results and indices may be used to compute the links, and may be used to define the contents of navigation places. For instance, file system hierarchies can be seen as partial ACN instances where queries are directory paths, results are file lists, and navigation links lead to children directories and the parent directory. • ACN as an interactive view. Interactive views follow the MVC architecture (model-view-controller). In ACN, the model is the knowledge base K. The view is the composition of a query, its result, and its index (an element of

Q × R × S).
The controller is made of the links, which are derived from the view contents. Each link activation generates a new view by computing a new result (result) and a new index (index ) from the target query. For instance, faceted search can be seen as an ACN instance where a query is a set of facet-values, a result is a selection of items, an index gives the frequency of facet-values among those items, and links allow the addition and removal of facet-values to the query.

ACN inherits expressivity from query languages, and guidance from navigation structures and interactive views, which achieves our main objective to reconcile expressivity and usability. However, it must be noted that the actual expressivity may be less than the expressivity of the query language in the case where navigation links are not rich enough to reach all valid queries. Ideally, links should be both safe and complete. Safeness means that no navigation path leads to dead-ends (e.g., empty results). Completeness means that every safe query can be reached through a finite navigation path. Safeness is important for the quality of guidance as it avoids users to "bump into the walls", and completeness is important to leverage the expressivity of the query language. Therefore, a critical issue in ACN is the definition of links, and hence the definition of results and indices because links are derived from them.

Graph-ACN: Instantiating ACN to Knowledge Graphs

We here instantiate ACN to Knowledge Graphs, which we call Graph-ACN, by defining each ACN component in Graph-FCA terms (see Section 2).

Knowledge base.

A knowledge base is formalized as a graph context K = (O, A, I), where objects O are the KG entities, attributes A are the KG k-ary relations, and the incidence relation I is the set of relational facts. As a running example, we consider the graph context displayed in Figure 1.

Query.

A query is an unary PGP Q = x ← P , where P is a graph pattern that uses variable x unless it is empty, and that has a single connected component (connected pattern). The motivation for excluding disconnected patterns is that each connected component can be navigated to independently of others. The projected variable x is called the focus of the query. It determines the contents of the index, and the behaviour of navigation links. Some navigation links defined below allow users to move it on other variables in the pattern.

The initial query is the empty query q 0 := x 1 ← ∅. In our running example, we consider the query q := x 2 ← plant(x 1 ), toxic(x 1 ), treats(x 1 , x 2 ), which corresponds to concept Q2c in Figure 3. It selects "everything treated by a toxic plant."

Result.

A result is a table with variables in headers, and objects in cells. A result is therefore a pair r = ((x 1 , . . . , x n ), R) composed of a tuple of n variables, and an n-ary object relation R ∈ R n . A result is said empty if its object relation R is the empty set.

The function from queries to results is defined as result(Q := x ← P ) := (vars(P ), (vars(P ) ← P ) ),

where vars(P ) is the row of variables occuring in P . This definition has the same effect as a SELECT * in SPARQL, and provides a richer result than the set of objects Q that only contains objects at the focus. The result of the initial query q 0 is a one-column table that contains the list of all objects in O. The result of our running query is the following table. Here, there is a bijection between x 1 -values and x 2 -values but this need not be the case.

r := result(q) = x 1
x 2 ageratumConyzoides aspergillusFlavus chromolaenaOdorata aspergillusOchraceus aspiliaAfricana aspergillusParasiticus

Index.

An index is a set that contains two kinds of elements: variables and attribute positions. An attribute position is a pair (a, i) where a ∈ A is an attribute of arity k belonging to the graph context, and i ∈ [1, k] is an argument position of the attribute. In the above example about plants, attribute treats has two positions: position 1 denotes the plants that treat some pest, while position 2 denotes pests that are treated by some plant. Given a query q := x ← P and its result r = result(q), the index s = index (q, r) contains all and only the elements that are relevant at focus x.

Here, "relevant" means that when the element e is inserted into the query q at focus (as defined right below), the new query has a non-empty result. The insertion function insert(q, e) is defined as follows.

• Inserting a variable y modifies the query by replacing every occurences of x by y in q. For example, the insertion of x 1 in the running query q, i.e.

insert(q, x 1 ) = x 1 ← plant(x 1 ), toxic(x 1 ), treats(x 1 , x 1 ),

generates a new query where occurences of x 2 is replaced by x 1 . That query has obviously an empty result as no pest treats a pest. • Inserting an attribute position (a, i) modifies the query by adding atom a(y 1 , . . . , y k ), where variable y i is focus variable x and every other variable is a fresh variable. For example, the insertion of (isFoundIn, 1) in the running query, i.e.

insert(q, (isFoundIn, 1)) = x 2 ← plant(x 1 ), toxic(x 1 ), treats(x 1 , x 2 ), isFoundIn(x 2 , x 3 ),

generates a new query with an additional atom. That query has a nonempty result with an additional column x 3 .

x 1 x 2 x 3 ageratumConyzoides aspergillusFlavus Namibia chromolaenaOdorata aspergillusOchraceus Nigeria aspiliaAfricana aspergillusParasiticus Benin

The insertion of attribute positions allows to make patterns grow, and the insertion of variables allows to form cycles in patterns. From there, the index can be defined as

index (q, r) := {y | y ∈ vars(P ), y = x, result(insert(q, y)) = ∅} ∪ {(a, i) | a ∈ A, i ∈ [1, k], result(insert(q, (a, i)) = ∅}
A frequency value can be associated to each index element e as the number of objects at focus after inserting it in the query.

freq(e) := |insert(q, e) | Frequencies of attribute positions provide a hint on their distribution over objects at focus. The index of our running query is given in the following table listing index elements along with their frequency. index element frequency (pest,1) 3 (isFoundIn,1) 3 (treats,2)

(attacksPeanut,1) 2

Links.

There are two kinds of links: focus moves and insertion of index elements.

A focus move simply changes the focus variable in the query. The insertion of an index element applies function insert(q, e) defined above on any index element e ∈ s. The ACN function links is therefore defined as follows, where

q = x ← P . links(q, r, s) = {y ← P | y ∈ vars(P ), y = x} ∪ {insert(q, e) | e ∈ s}
The number of links is therefore bounded by the number of variables in the current query plus the number of attribute positions. In our running examples, there are 5 links: 1 focus move on x 1 , leading to concept Q2b; and 4 insertions for the above index elements, 3 staying on Q2c and the last one leading to Q1b.

Safeness.

We define a navigation state as safe in Graph-ACN when it has non-empty result. Indeed, empty results are like dead-ends in the navigation process, and they are frustrating in a user experience. This is why it should be avoided as much as possible. We can prove safeness by showing that the initial navigation place is safe, and that every navigation link preserves safeness. In our instance, the initial place is obviously safe as the result contains all objects, i.e. all entities of the knowledge graph (otherwise, the KG is empty). Then, there are two kinds of navigation links to consider. Focus moves do not change the query pattern, and by definition of results, they do not change the result either. Therefore, if the source place of the link is safe, then so is the target place. Insertions of index elements also preserve safeness by definition of index elements because their insertion into the current query must lead to queries with non-empty results.

Completeness.

We consider Graph-ACN as complete if every connected graph pattern P that has a non-empty extension can be reached in a finite sequence of navigation links, starting from the initial place. We can prove completeness by building a navigation path from the initial query q 0 = x ← ∅ to the target query q = x ← P . This can be done by induction. If the pattern has 0 atoms, then it is the initial query, and no navigation link is required. Now, assuming that all patterns with n atoms are reachable, let us consider a pattern P n+1 with n+1 atoms. It is always possible to remove a pattern atom a(x 1 , . . . , x k ) from P n+1 , and still have a connected pattern P n with n atoms. Moreover, given that P n+1 has a non-empty result, so does P n because of the Galois connection that exists between PGPs and object relations. By induction hypothesis, there is a navigation path to P n . From there, P n+1 can be reached by moving the focus on a variable x i that already belongs to P n (it must exist as P n+1 is connected); then by inserting the attribute position (a, i); and finally, for every other position j of the new atom where x j ∈ vars(P n ), move the focus on that position, and insert variable x j .

Scaling to Large RDF Graphs with SPARQL Endpoints

We here address the concrete implementation of Graph-ACN to knowledge graphs, using semantic web technologies [START_REF] Hitzler | Foundations of Semantic Web Technologies[END_REF]. The objective is to run the navigation process on top of SPARQL endpoints. SPARQL endpoints are web services that can answer complex SPARQL queries over large RDF graphs. Compared to a previous work [START_REF] Ferré | Conceptual navigation in RDF graphs with SPARQL-like queries[END_REF], our approach has scaled from tens of thousands of triples to billions of triples (e.g., DBpedia). In the following we first describe the correspondence between Graph-FCA and both RDF and SPARQL. Then, we describe how to compute results and indices of navigation places from the queries, taking into account that SPARQL engines often return only partial results on large knowledge graphs.

From Graph-FCA to RDF and SPARQL

An RDF graph has three kinds of nodes: URIs (entity identifiers), literals (strings and typed values such as numbers and dates), and blank nodes (anonymous nodes). It has one kind of edge, called triple (s, p, o), whose components are respectively called subject (the source of the edge), predicate (the label of the edge), and object (the target of the edge). When a URI is used as a predicate, it is called a property, and denotes a binary relationship between RDF nodes. When a URI is used as an object with predicate rdf:type, it is called a class, and denotes a set of RDF nodes. An RDF graph is simply defined as a set of triples.

In order to apply Graph-ACN on RDF graphs, we need to map RDF graphs to graph contexts. This can be done by applying the following rules:

1. each RDF node n becomes a Graph-FCA object o n ; 2. each URI u and literal l also becomes a Graph-FCA unary attribute, in order to allow for the identification of individual entities and values. This is analogous to nominal scaling in FCA; 3. each RDF class c becomes a Graph-FCA unary attribute; 4. each RDF property p becomes a Graph-FCA binary attribute; 5. triple is a Graph-FCA ternary attribute, in order to allow for reified triples; 6. for each URI u, fact u(o u ) represents the identity of the object as a URI; 7. for each literal l, fact l(o l ) represents the value of the object as literal; It can be observed that the arity of attributes is maximum 3. The unary attributes that are derived from URIs and literals are special in that there is single fact that uses them in the graph context. They are singleton classes.

Conceptual navigation in Graph-ACN produces PGPs that have to be translated to SPARQL queries in order to use SPARQL endpoints for the computation of results and indices. A SPARQL query has the form SELECT ?x 1 ... ?x n WHERE { GP }, where x i s are variable names, and GP is a SPARQL graph pattern. SPARQL has a rich language of graph patterns but we here only need basic graph patterns, which are concatenations of triple patterns; and equality filters FILTER (?x = n) between variable x and RDF node n. A triple pattern s p o. is like an RDF triple except that variables can be used as components in addition to RDF nodes. The function σ translating PGPs Q to SPARQL queries can be defined as follows:

1. σ(Q) = 'SELECT ?x 1 ... ?xn WHERE { σ(P ) }' with Q = (x 1 , . . . , x n ) ← P ; 2. σ(P ) = 'σ(atom 1 ) . . . . . σ(atomm)'

with P = {atom 1 , . . . , atom m };

3. σ(u(x)) = 'FILTER (?x = <u>)'
where u is a URI; 4. σ(l(x)) = 'FILTER (?x = "l")'

where l is a literal; 5. σ(c(x)) = '?x rdf:type <c>'

where c is a class; 6. σ(p(x, y)) = '?x <p> ?y'

where p is a property; 7. σ(triple(x, y, z)) = '?x ?y ?z'

The generated SPARQL query can be simplified by eliminating the equality filters. Each equality filter FILTER (?x = n) can be eliminated by replacing in the query all occurences of ?x by n.

Computing the Result, Index, and Links

We here detail the computation of the result, index, and links, assuming that the query q of the current place is the PGP Q := x ← P .

Result.

The result of the current place is directly obtained by evaluating the SPARQL translation of the PGP vars(P ) ← P . Indeed, the evaluation of a SPARQL query amounts to find all homomorphisms from the graph pattern to the knowledge graph, and it is therefore equivalent to the Galois connection from PGPs to object relations. The output of SPARQL query evaluation is a table with projected variables as headers, and one row per found homomorphism, binding variables to RDF nodes. This is exactly the expected structure for Graph-ACN results.

Index.

As defined above, the index is composed of variables and attribute positions whose insertion in q produces a new query with a non-empty result. For efficiency reasons, we want to avoid to compute the result, i.e. to evaluate a SPARQL query, for each variable, and for each attribute position. In other words, we want to decide on condition result(insert(q, e)) = ∅ without actually computing the result nor the insertion.

First, we show that the above condition can be decided for variables only by looking at the current result.

Lemma 1. Let r := result(q) = ((x 1 , . . . , x n ), R), let x i = x for some i ∈ [1, n], and let y = x j for some j ∈ [1, n], j = i. The insertion of variable y does not lead to an empty result iff there is a row in the current result s.t. both variables x and y have the same value.

result(insert(q, y)) = ∅ ⇐⇒ ∃(o 1 , . . . , o n ) ∈ R : o i = o j
The frequency of index element y can be computed as follows.

freq(y) = |{o i | (o 1 , . . . , o n ) ∈ R, o i = o j }|
The variables in the index, and their frequencies can therefore be computed in one pass over the result.

Second, we show that the above condition can be decided for attribute positions only by looking at the adjacent edges of the focus objects, i.e. by looking at facts that contain an object that is the value of the focus variable in some row of the current result.

Lemma 2. Let r := result(q) = ((x 1 , . . . , x n ), R), let x i = x for some i ∈ [1, n], and let (a, j) be an attribute position. The insertion of attribute position (a, j) does not lead to an empty result iff there is a row in the current result, and a fact in the graph context s.t. the value of x in the row is the same as the object at position j in the fact. result(insert(q, (a, j))

) = ∅ ⇐⇒ ∃(o 1 , . . . , o n ) ∈ R : ∃a(w 1 , . . . , w k ) ∈ K : o i = w j
The frequency of index element (a, j) can be computed as follows.

freq((a, j))

= |{o i | (o 1 , . . . , o n ) ∈ R, a(w 1 , . . . , w k ) ∈ K, o i = w j }|
Assuming that the graph context is only available through the SPARQL endpoint, we need to come up with SPARQL queries that will retrieve the attribute positions. In spirit, we would like to evaluate the conjunctive query (a, j) ← P ∪ {a(x 1 , . . . , x j-1 , x, x j+1 , . . . , x k )} in order to retrieve all valid attribute positions. Unfortunately, attributes and positions are not valid variables in Graph-FCA queries. However, when considering its translation to SPARQL for the different kinds of attributes available in RDF, we obtain valid SPARQL queries as we show below.

For attributes that represent RDF nodes (1 position), the additional query atom translates as FILTER (?x = ?n), and the SPARQL query simplifies to SELECT ?x WHERE { GP }. This is actually a projection on the focus variable of the query that computes the result. Those attribute positions can therefore be obtained simply by reading column x of the current result, without any request to the SPARQL endpoint.

For attributes that represent RDF classes (1 position), the SPARQL query is SELECT ?x ?c WHERE { GP . ?x rdf:type ?c }. It retrieves all types of focus objects. The inclusion of ?x in the select clauses enables to compute frequencies as a post-processing, and also to use the relationships between focus objects and classes in rich user interfaces.

For attributes that represent RDF properties, there are two positions. The SPARQL query for position 1 is SELECT ?x ?p WHERE { GP . ?x ?p [] }, and for position 2 it is SELECT ?x ?p WHERE { GP . [] ?p ?x }, where [] denotes an anonymous variable.

Finally, for attribute triple that has 3 positions, there are three queries similar to the queries for properties, except that the additional triple patterns are respectively (? and([] [] ?x), and only ?x is in the SELECT-clause.

x [] []), ([] ?x []),
The above SPARQL queries have the drawback that GP has to be evaluated 7 times, including the computation of the result. This is a serious issue for complex patterns. Fortunately, several optimizations are possible. First, all above queries only need the values of x in the pattern. The translated pattern GP can therefore be replaced by an enumeration of values for x, as already available in column x of the result: VALUES ?x { o 1 ... o m }, where {o 1 , . . . , o m } is the projection of result r on column x. This kind of SPARQL pattern is very efficiently evaluated. Second, the results for attribute triple at positions 1 and 3 can be deduced from the results about properties because the latter are generalizations of the former. For instance, if (p, 1) is a valid attribute position, then so is (triple, 1). The related SPARQL queries can therefore be dropped. Third, the remaining queries can be factorized by using a UNION-pattern, as follows.

SELECT ?x ?c ?p1 ?p2 WHERE { VALUES ?x { o1 ... om } { ?x rdf:type ?c } UNION { ?x ?p1 [] } UNION { [] ?p2 ?x } UNION { [] ?x [] } }
Each result of that query will bind at most one variable of c, p1, p2 (none of them for attribute position (triple, 2)), so that there is no ambiguity in the interpretation of results. In total, only two requests are done to the SPARQL endpoint per navigation place. The first one to compute the result and part of the index (URIs and literals), and the second one to compute the rest of the index (classes, properties, and triple).

Links.

The computation of links is immediate once the index is computed. A natural optimization here is to compute the target queries in a lazy way, delaying the actual computation (focus move or index element insertion) to when the user triggers a link.

Living with Partial Results

On large knowledge graphs and for some complex queries, the number of results may be impractical for exhaustive computation, transmission from the endpoint, and display to the end-user. In fact, SPARQL endpoints enforce limits in the number of results (e.g., 10,000 for DBpedia). It is therefore necessary to live with this constraint that entails that only partial results may be available. Using such a limit also allows to tune the responsiveness of the system: the lower the limit, the more responsive the system is.

What are the consequences on Graph-ACN navigation? The fact that the result is partial is not really an issue as it does not make sense to display thousands or millions of results to the end-user. This is similar to web search engines that only show the first 10 results by default, and never show thousands of results at once. Now, a partial result entails a partial index because attribute positions in the index are computed from objects found in the focus column of the result. For RDF nodes (URIs and literals), like for results, it does not make sense to display all of them when there are thousands of them. For classes and properties, their number is generally much smaller than for RDF nodes but in some cases it can still be too high for complete display (e.g., classes in YAGO).

The completeness of conceptual navigation is broken by partial indices. However, experience has shown us that the partial results act as a sample from which the most common classes and properties are retrieved, and the missing index elements are generally unfrequently used. The main limitation of partial indices in practice is when one wants to insert in the query a specific RDF node (e.g., selecting a specific film director among all of them), or occasionally a rare class or property. In order to overcome missing in-dex elements and recover completeness, the solution we have adopted is to let the user enter keywords, and to refine the SPARQL queries with filters using those keywords. For instance, if the user enters keywords "Tim Burton" about focus objects, the SPARQL query computing the result will be SELECT ?x 1 ... ?x n WHERE { GP FILTER (REGEX(?x, "Tim", i) && REGEX(?x, "Burton", i)) }. It retrieves only results where the focus value contains words "Tim" and "Burton". When the keywords are about classes and properties, it is the SPARQL query retrieving them that is modified accordingly. A further refinement is to match the keywords on the RDFS labels of URIs rather than on the URIs themselves. We omit the details here.

Rising in Expressivity

SPARQL has a lot to offer beyond conjunctive queries. It features relational algebra operators (UNION, MINUS, OPTIONAL); scalar expressions that can be used in filters, variable bindings (BIND), and in the SELECT-clause; aggregations with GROUP BY; and yet other features. It is desirable to extend our conceptual navigation framework to cover such expressive features. The difficulty is that operators like UNION and MINUS do not apply on the whole query, nor on the focus variable but on a subset of query atoms. We therefore need a representation of queries and their focus that is more adequate to the insertion of those SPARQL features.

An Algebraic Form of Queries

We introduce an algebraic form of queries. A pattern tree is a pair T = x, D , where x is a variable, and D is a description of x possibly containing a number of subtrees. A description D is one of the following forms, where • denotes the described node x:

1. : the void description; 2. a(T 1 , . . . , T i-1 , • , T i+1 , . . . , T k ) with T j = x j , D j for j ∈ [1, k], j = i: a description stating that the described variable is the i-th argument of the hyper-edge a(x 1 , . . . , x i-1 , x , x i+1 , . . . , x k ), and that each x j is recursively described by D j ; 3. • = y: a description stating that the described variable is equal to y; 4. D 1 ∧ D 2 : a conjunction of two descriptions, stating that x satisfies both descriptions.

An algebraic query is a pattern tree with the focus localized on a part of the tree, either a subtree or a description. Every subtree has a distinct variable, and cycles are expressed with descriptions like • = y.

For example, the algebraic query (with focus underlined)

x, plant(•) ∧ treats(•, y, isFoundIn(•, z, country(•) ) ) ∧ possesses( w, • = z , •)
is equivalent to the PGP query z ← plant(x), treats(x, y), isFoundIn(y, z), country(z), possesses(z, x).

The algebraic form can be easily obtained from the PGP form x ← P by using a tree traversal of P , and by putting the focus on the subtree with variable x. For binary attributes, description a(•, T 2 ) corresponds to cross the binary relation forward, while a(T 1 , •) corresponds to cross it backwards.

The computation of the result of algebraic queries requires to translate them to SPARQL, which is defined as follows:

1. σ(T ) = σ x (D), with T = x, D (trees) 2. σ x ( ) = '' (void description) 3. σ x (u(•)) = 'FILTER (?x = <u>)'

(URIs) 4. σ x (l(•)) = 'FILTER (?x = "l")'

(literals) 5. σ x (c(•)) = '?x rdf:type <c>'

(classes) 6. σ x (p(•, y, D y )) = '?x <p> ?y . σy(Dy)'

(properties) 7. σ x (p( y, D y , •)) = '?y <p> ?x . σy(Dy)'

(properties) 8. σ x (triple(•, y, D y , z, D z )) = '?x ?y ?z . σy(Dy) . σz(Dz)'

(triples) 9. σ x (triple( y, D y , •, z, D z )) = '?y ?x ?z . σy(Dy) . σz(Dz)'

(triples) 10. σ x (triple( y, D y , z, D z , •)) = '?y ?z ?x . σy(Dy) . σz(Dz)'

(triples) 11.

σ x (D 1 ∧ D 2 ) = 'σx(D 1 ) . σx(D 2 )' (conjunction)
Finally, it remains to redefine the insertion of variables and attribute positions at the current focus. The insertion of a variable y introduces a new conjunct at the focus. If the focus is on a description D, it is replaced by D ∧ • = y. If the focus is on a subtree T = x, D , then the insertion applies on D. Similarly, the insertion of an attribute position (a, i) introduces at the focus the new conjunct a(T 1 , . . . , T k ) where T i = • and other T j are fresh variables with void descriptions.

The index and navigation links are then computed in exactly the same way because they rely on the result, which is left unmodified.

Extensions of the Query Algebra

Each extension of the query algebra, aimed at covering some SPARQL feature, consists in introducing new algebraic query constructs. For each new construct, one needs to extend the SPARQL translation, and to define new links to introduce the new construct in a query. The index is generally left unmodified because most additional constructs do not contribute to the description of data. As a consequence, those extensions have almost no impact on usability and scalability. From the user point of view, there are only a few additional navigation links, which can be ignored if she is not interested in the feature. From the point of view of scalability, the query computing the index is the same, and the only impact is on the computation of results depending on which features are used. For example, aggregations are typically costly to evaluate.

We illustrate such an extension with SPARQL UNION, which expresses a disjunction between two patterns. First, we introduce a new description D 1 ∨ D 2 , a disjunction of descriptions. Second, we define its translation to SPARQL, using the UNION operator:

σ x (D 1 ∨ D 2 ) = '{ σx(D 1 ) } UNION { σx(D 2 ) }'.
Third, we add a link from a query whose focus is on a description D to the same query where that description is replaced by D ∨ , introducing the disjunction with an alternative description that is initially void. The focus can be moved on the void description, ready to be refined by insertion of an attribute position for instance.

The query algebra can be extended in a similar way with SPARQL MINUS, which expresses negation on a pattern. The new description is D 1 ∧ ¬D 2 , whose translation to SPARQL is 'σx(D 1 ) MINUS { σx(D 2 ) }'. The additional link replaces description D at focus by D ∧ ¬ .

Other description extensions express numeric inequalities (e.g., ≥ 10) or string matching (e.g. contains "foo", matches "[0-9]+"). Query trees can be extended with binding of variables by complex expressions (e.g., computing people's age as the difference between current date and their birthdate), filtering of results by complex expressions (e.g., filtering people whose age is at least 18), and by aggregations over results (e.g., computing the average age of people per country). Expressions constitute a third kind of part in queries, in addition to trees and descriptions, and have thus their own SPARQL translations and navigation links (see [START_REF] Ferré | A SPARQL 1.1 query builder for the data analytics of vanilla RDF graphs[END_REF] for technical details).

An advantage of the algebraic form of queries, beyond rising in expressivity, is that it is more amenable to verbalization in natural language. Indeed, every tree can be verbalized as a noun phrase, while every description can be verbalized as a relative clause. For instance, the example query above can be verbalized as "a plant that treats something found in a country, and that the country possesses." This idea has been formalized with the N<A>F design pattern [START_REF] Ferré | Bridging the gap between formal languages and natural languages with zippers[END_REF].

The Sparklis Tool and Application Cases

The Graph-ACN framework presented above is implemented in full in the Sparklis tool 6 , though historically Graph-FCA was formalized later than the first implementation. After presenting the implementation, user interface and capabilities of Sparklis, we discuss a few application cases on large knowledge graphs.

Sparklis

Sparklis implements Graph-ACN as a web application that runs on top of SPARQL endpoints. It runs in the web browser as JavaScript (compiled from OCaml with tool js of ocaml7 ), and computes extensions and indices by sending SPARQL requests to the SPARQL endpoint.

The user interface of Sparklis is made of a view of the current navigation place, plus configuration widgets. Figure 5 shows a screenshot of Sparklis on a core subset of DBpedia. The main configuration widget is a text input at the top where the URL of the SPARQL endpoint has to be entered. Other configuration widgets are available through the "Configure" menu but defaults are generally fine.

The current place view is made of three parts, in accordance with the ACN framework: the query (top), the index (middle), and the result (bottom). The query is fully verbalized in (controlled) natural language, using RDF classes and properties as nouns, and entities as proper nouns. The focus part is highlighted in light green, and can be moved simply by clicking on different parts of the query. At the end of the focus part, the cross allows to delete the focus part, and the hamburger-icon provides a few navigation links to insert operators like conjunction, disjunction, negation, or sorting of results. In the current version, Sparklis covers all SELECT-queries with the exclusion of queries that need disconnected graph patterns.

The index is splitted into three lists: attribute positions for RDF classes, properties, and triple (left), attribute positions for RDF nodes (center), and other navigation links for introducing various operators (right). Each index element can be inserted at the query focus simply by clicking it. By default, index elements are sorted by decreasing frequency but they can also be sorted in lexicographic order. Filter inputs at the top of each list allows to force the retrieval of index elements matching some constraint (matching some keywords or satisfying numerical inequalities).

The result is displayed as a table where headers are verbalizations of variables, and the focus column is highlighted in light green. Headers can be clicked to move the focus, and the RDF nodes in the cells can be inserted in the query by clicking them. Depending on the result contents, Sparklis can offer additional views on the concept extent: a slideshow of all images occuring in the result, or a map of all geolocalized objects in the result.

The "Learn" menu provides a large number of example queries, and for some of them, a screencast showing how to build them step by step. The user interface and verbalization of queries are available in several languages: English, French, Spanish and Dutch.

Application Cases

The first version of Sparklis was put online in Spring 2014. Since then, it has been regularly used by thousands of unique users over hundreds of different knowledge graphs (SPARQL endpoints) covering many domains (ency-clopaedias, bioinformatics, medicine, bibliography, administrations, etc.). At the time of writing, Sparklis earned consistently around 1000 hits per month over the last years. Those figures demonstrate that our approach is successful in supporting exploration and querying of real knowledge graphs.

In the following, we shortly present four application cases on large knowledge graphs. In each case, we describe the knowledge graph, i.e. its contents, its size, its peculiarities, and we list a few questions that can be built and answered in Sparklis. For some of the questions, we provide a short link to its navigation place in Sparklis.

Encyclopedic Graphs: DBpedia and Wikidata.

The most commonly used knowledge graphs are those that have encyclopedic contents. For example, DBpedia [START_REF] Lehmann | DBpedia -a large-scale, multilingual knowledge base extracted from wikipedia[END_REF] is a KG version of Wikipedia, where triples are mostly extracted from the infoboxes included in Wikipedia pages. This implies that DBpedia covers all kinds of topics (e.g., people, organizations, creative works, species, places), and for this reason, it stands in the middle of Linked Open Data (LOD). It is one of the biggest open knowledge graph with more than 3 billions of triples. We list a few questions, taken from QALD-4 challenge, along with the Sparklis link.

1. Which rivers flow into a German lake? (http://bit.ly/2NpuIlY) 2. Give me all films produced by Steven Spielberg with a budget of at least $80 million. (http://bit.ly/2WSlmlX) 3. How many languages are spoken in Colombia? (http://bit.ly/2WQyfNo) 4. Which poet wrote the most books? (http://bit.ly/32mWRP6) Another important encyclopedic KG is Wikidata 8 . Unlike DBpedia, it can be directly edited by people (like a wiki) in a structured way. Editors can create new entities (called items), and add statements about entities. Some of the contents is automatically imported from existing structured sources but a lot of its contents is also added manually. Wikidata does not follow the RDF model, although an RDF version exists. In particular, it is possible to make statements about statements. For instance, it is possible to say that Barack Obama is a president of the Unites States, and then say that this presidency started in 2008, and ended in 2016. This specificity and others required several adaptations in Sparklis. Here are a few questions that can be answered in Wikidata. Persée9 is a French organization that provides free access to more than 600,000 scientific publications, notably in the domain of humanities and social sciences. It maintains a SPARQL endpoint that gives access to their metadata10 , and they have officially adopted Sparklis as an exploration and querying tool in 2017. Their motivation was to empower their researchers by enabling them to build complex questions in a free way. The dataset contains about 42 millions of triples. Here are a few questions that they give as example on their web site (translated from French).

1. Co-authors of Pierre Bourdieu, ordered by lastname and firstname 2. Authors with the largest number of co-authors 3. For each author, and for each co-author, how many articles in common 4. For a given author, the journal titles where he/she published, along with the number of articles and the publication dates Pharmacovigilance Data in PEGASE.

In the context of the PEGASE11 research project on pharmacovigilance, we have designed a large knowledge graph about (anonymous) patients taking drugs and having adverse drug reactions (ADR) [START_REF] Bobed | Sparklis over PEGASE knowledge graph: a new tool for pharmacovigilance[END_REF]. It includes patient data from FAERS (about 25 millions of triples for three months of records), and terminological data from SNOMED CT and MedDRA (about 3 millions of triples). The first specificity of this dataset is that there are statements about statements like in Wikidata: e.g., there are statements about how patients have taken drugs (how many, how often, etc.). The second specificity is that MedDRA and SNOMED CT are two large hierarchies that required extensions of Sparklis for querying and visualizing them. There is a maintained SPARQL endpoint but it is not publicly available because of license restrictions on MedDRA and SNOMED CT. Here are a few examples of questions that can be answered on the PEGASE knowledge graphs.

1. Are there patients who experienced renal failure after taking Cloxacillin? patients being more than 60 years old? 2. Which MedDRA terms describe an inflammatory ADR in the brain? Government Data.

The QALD-6 challenge (Question Answering over Linked Data) introduced a new task (Task 3) on "Statistical question answering over RDF datacubes" [START_REF] Unger | 6th open challenge on question answering over linked data (QALD-6)[END_REF]. The dataset contains about 4 million transactions on government spendings all over the world, organized into 50 datacubes, all modeled in RDF. The specificity of the dataset is that it contains a lot of numeric data, and that most questions on it consists in computing aggregations such as averages and totals. The KG contains about 16 millions of triples in total. Unfortunately, the SPARQL endpoint is not maintained so that it is no more possible to explore it in Sparklis. Sparklis could build 148 out of the 150 questions of the challenge. We list here a few questions as examples.

1. How much was spent on public safety by the Town of Cary in 2010? 2. Which expenses had the highest total amount of proposed expenditures for the Maldives? 3. How many suppliers did the Newcastle city council use for education?

Conclusion and Perspectives

We have introduced Abstract Conceptual Navigation (ACN), a general paradigm based on concept lattices to reconcile expressivity, usability, and scalability in the exploration and querying of a knowledge base. Users are guided in a safe and complete way through the concept lattice, and the user navigation state is represented at all time as a readable query, which is updated according to the navigation links chosen by users. Only a local view centered on the current concept is shown, but ACN gives room to enriched representations of the extent (called result) and intent (called index) that can provide hints about the concept neighborhood.

We have instantiated ACN to knowledge graphs (Graph-ACN) with Graph-FCA as a formal ground. We have shown how to implement it on top of SPARQL endpoints in a scalable way. In Graph-ACN, queries are conjunctive queries to start with, and are then extended to advanced features available in SPARQL. Results are tables, like for SPARQL queries, thus going beyond the usual sets of objects in other FCA approaches. We have shown an effective implementation of Graph-ACN through the Sparklis tool, and effective applications on real and large knowledge graphs.

In terms of scalability, a perspective is to improve efficiency by designing specialized data structures and algorithms in the SPARQL endpoint to optimize the Graph-ACN-specific SPARQL queries. In terms of expressivity, beyond the SELECT-queries of SPARQL, there are also CONSTRUCT-queries that return graphs, and updates. Beyond SPARQL, we can imagine ACN instances for other query languages such as SQL, XQuery or Cypher. Another perspective for increasing expressivity is to enrich the index in order to support knowledge extraction tasks, e.g. with association rules or functional dependencies.

Fig. 1

 1 Fig. 1 Graph context about plants, pests, and countries. Rectangles are objects, with their labels in the top part, and unary attributes applying to them in the bottom part. Links are binary edges, with the binary attribute as label.

Fig. 2

 2 Fig. 2 Compact representation of graph concepts about plants, pests, and countries, with minimum support 2.

Fig. 3

 3 Fig. 3 Generalization ordering of unary graph concepts about plants, pests, and countries, with minimum support 2.

Fig. 4

 4 Fig. 4 Schema showing the different components of Abstract Conceptual Navigation (ACN), and their interactions.

8 .

 8 for each triple (s, rdf:type, c), fact c(o s ) represents the membership of the subject to the class; 9. for each triple (s, p, o), facts p(o s , o o ) and triple(o s , o p , o o ) represent respectively the binary relationship between the subjet and the object, and the reified triple.

Fig. 5

 5 Fig. 5 Screenshot of Sparklis where the current query is "the films directed by Tim Burton and starring somebody born in England", with focus on the actors.

1 . 2 . 3 .

 123 Show me a map of French hospitals. (http://bit.ly/2CoTeNP) What are the popular given names among the French people? (http:// bit.ly/33swvfI) Give me a slideshow of French prime ministers (since 1815) by decreasing total length of service. (http://bit.ly/2NtNNUp) 8 https://www.wikidata.org/ Bibliographic Data at Persée.

Available online at http://www.irisa.fr/LIS/ferre/sparklis/

https://ocsigen.org/js_of_ocaml/3.1.0/manual/overview

http://www.persee.fr/

http://data.persee.fr/

https://anr.fr/Project-ANR-16-CE23-0011

This research is supported by ANR project PEGASE (ANR-16-CE23-0011-08). 1

2 http://www.w3.org/ 3 See https://lod-cloud.net/ 4 See