Jussi T Lindgren

Adrien Merlini

Anatole Lecuyer

Francesco P Andriulli

simBCI -A framework for studying BCI methods by simulated EEG

Brain-Computer Interface (BCI) methods are commonly studied using Electroencephalogram (EEG) data collected from human experiments. For understanding and developing BCI signal processing techniques real data is costly to obtain and its composition is apriori unknown. The brain mechanisms generating the EEG are not directly observable and their states cannot be uniquely identified from the data. Subsequently, we do not have generative ground truth for real data.

To allow studying BCI signal processing methods in controlled conditions, we propose an object-oriented framework called simBCI. The frawework is for generating artificial BCI data and to test classification pipelines with it. Parameters of interest on both data generation and the signal processing side can be iterated over to study the effects of different combinations. The architecture allows affordable exploration of how BCI signal processing approaches behave in different conditions by enabling precise control over the generative process. The proposed system does not intend to replace human experiments. Instead, it can be used to discover hypotheses, study algorithms, to educate about BCI, and to debug BCI signal processing pipelines.

The proposed framework is modular, extensible and freely available as open source 1 . The only requirement is Matlab.

Introduction

Brain-Computer Interfaces (BCIs) based on Electroencephalogram (EEG) attempt to translate measurements of the user's brain activity into commands for the computer. To obtain a discrete command, the BCI methods process and classify segments of the EEG signal. Unfortunately the current BCIs leave a lot to be desired in terms of accuracy [START_REF] Allison | Could Anyone Use a BCI?[END_REF][START_REF] Nicolas-Alonso | Brain Computer Interfaces, a Review[END_REF][START_REF]Brain-Computer Interfaces[END_REF]. Why is this the case? Studying this question from the signal processing viewpoint is difficult for several reasons. One is the cost of running large-scale human experiments for statistical validity, and the other is the nature of the obtained EEG data. As the generative sources in the brain cannot be uniquely identified from the EEG [START_REF] Baillet | Electromagnetic brain mapping[END_REF], we lack ground truth regarding the components of the data. In these conditions, we do not know what kind of performance an optimal BCI could have on such data. It is even hard to be sure if one method is better than another (see e.g. [START_REF] Lindgren | As above, so below? Towards understanding inverse models in BCI[END_REF]). It is also difficult to assess how the different elements of the BCI session contributed to the obtained results. How are the results affected by the user, the equipment, and the signal processing? Which properties of these elements had what effects?

In this paper, we propose to alleviate the study of signal processing methods in BCI by an open source framework called simBCI for simulating some central parts of BCI experiments. In particular, the framework can generate simulated BCI data and execute signal processing (or classification) pipelines. Parameters in both generation and classification can be varied, and the framework can provide aggregates for quantities of interest such as prediction accuracies per parameter configuration. The intent of the framework is to allow studying the behaviour of the model BCI systems with different configurations and parameters, and to numerically investigate how different generative or discriminative parameters affect the results such as accuracies and estimated model parameters. If the modelling assumptions hold, similar behavior may be encountered in real circumstances.

The simulation framework we propose is conceptually situated halfway between mathematics and human experiments. We do not propose it to replace either. The benefit of simulation is that it can provide affordable hypothesis discovery and insight, while only requiring explicit models of the systems under study and some computational power. For example, simulation may suggest that one method is more resistant to a specific type of noise or artifact, or less affected by the positions of the discriminable signal sources in the brain volume. Such discovered hypotheses can then be further studied with real experiments or mathematical analyses. Another possible use-case is to illustrate the behavior of the used models for pedagogical purposes. The student can control the simulator and observe the input-output relationships before and after different transformations of the signal. This can be done both during the data generation, and the signal processing. As yet another use-case, the generated data can be used to debug existing BCI systems: easy data can be generated that matches the modelling assumptions of the BCI systems' signal processing. If the system does not process such data as expected, an issue has been discovered. Further, if the user provides different head models and/or parameter sets, multiple datasets can be generated. In principle these datasets could be used to study behavior of techniques such as deep learning that may be able to benefit from a big data approach. However, we do not currently provide such learning algorithms in the system.

The presented framework is open source and available for free. We warmly welcome extensions and contributions to improve it. Due to the modular design, new components such as signal and noise models, head models, forward models, inverse algorithms and other signal processing plugins can be easily added to the system to improve its realism or to make it more applicable to study specific questions. Similarly to other Matlab-based systems, extensions can be simply added by depositing new scripts to the directory hierarchy. As the source code is hosted on a flexible and open git-based system, the community enthusiasts can easily clone their own versions of the framework and submit pull requests if they desire some components to be included in the upstream version.

The rest of this paper is organized as follows. We begin in section 2 by a more detailed description of the challenges that simulation can help with. We describe previous work in section 3. In section 4, we present an overview of the proposed architecture. In section 5 we describe how the framework models data generation and in section 6 we present the conventions used for signal processing. Then, section 7 shows how the generation and the processing components are put together to form a BCI simulator. Section 8 shows a few illustrative uses of the system with discussion in section 9. Finally, section 10 concludes.

Why simulation?

Since the introduction of computers, simulation has become an increasingly important technique in research and development in a multitude of fields [START_REF] Kaufmann | Supercomputing and the Transformation of Science[END_REF], ranging from manufacturing [START_REF] Mourtzis | Simulation in Manufacturing: Review and Challenges[END_REF] to brain research [START_REF] Markram | Introducing the Human Brain Project[END_REF]. Although real experiments are ultimately needed for testing and verification, simulation is useful in obtaining hypotheses about the studied systems when human experiments and analytical studies are challenging and costly. In the scope of BCI, we have identified three different reasons why studying signal processing techniques can be difficult with real data.

1. The cost of human experiments. A legion of different BCI signal processing pipelines have been proposed, typically with many parameters [START_REF] Lotte | A review of classification algorithms for EEG-based brain-computer interfaces[END_REF]. If some signal processing technique is promoted based on experiments with only a few subjects, there is a significant risk that these results are a statistical accident, unless very strict statistical controls are used. Large studies are to be preferred. Such statistically valid experiments require orchestrating a large number of subjects to perform long and fatiguing BCI sessions. The subjects have to be instructed, prepared and set up with the recording equipment. To attain successful BCI control, the users may also require preliminary training sessions. An overview of the work involved can be found e.g. in [START_REF] Graimann | Brain-Computer Interfaces: A Gentle Introduction[END_REF][START_REF] Nijboer | Usability of three electroencephalogram headsets for brain-computer interfaces: a within subject comparison[END_REF][START_REF]Brain-Computer Interfaces[END_REF].

2. Problems in controlling the data generation. Due to different physiologies, mental strategies and possibly other causes, EEG signals generated by different users have different properties (e.g. in motor imagery [START_REF] Pfurtscheller | EEG-based discrimination between imagination of right and left hand movement[END_REF][START_REF] Grosse-Wentrup | Beamforming in noninvasive brain-computer interfaces[END_REF][START_REF] Besserve | Improving quantification of functional networks with EEG inverse problem: Evidence from a decoding point of view[END_REF]). As adapting the signal processing to these user-specific characteristics improves the classification accuracy, understanding these differences and their effects can be seen to be directly relevant for BCI development.

In real experiments, some properties are either totally outside the control of the experimenter (such as the user anatomy, location of different functional areas in the brain, and electrical propagation through the tissues) or difficult to control and verify (used mental strategies). The knowledge of anatomical and functional details may be available in medical circumstances, but such information is not usually available in other use-cases.

3. Lack of ground truth. The ground truth regarding the signal generation cannot be easily obtained for real data. This is partly due to the information-losing physiological volume conduction process that blends, mixes and dampens the electrical activity when it propagates through the brain, the skull and the scalp before it can be measured by EEG [START_REF] Nunez | Electric Fields of the Brain[END_REF]. Since we do not have direct access to what happened between the user receiving some instructions and the eventually observed EEG recording, it is difficult to determine whether a particular result is due to the user's skill, physiology, artifacts, noise, bugs in the system, particular choices in the signal processing, amount of training data, or perhaps nonstationarity of the brain activity.

In simulations, these issues can be circumvented. The experiments can be as large as the available computational power and time permits, and all the various parameters can be controlled up to the capability of the researcher to reasonably model the phenomena of interest. Since the data is generated with an explicit specification, we know exactly what is in the data, and hence we have access to ground truth on all the levels that we model in the generation. Ultimately, the obtained hypotheses and intuition can be further studied with real experiments.

Previous work

Simulating EEG data has a long tradition. The generative models proposed for EEG can be used to hypothesize about the mechanisms behind the measurements, but also to synthesize simulated data [START_REF] Zetterberg | Analogue simulator of e.e.g. signals based on spectral components[END_REF][START_REF] Isaksson | An EEG simulator-a means of objective clinical interpretation of EEG[END_REF][START_REF] Kemp | Model-based analysis of neurophysiological signals[END_REF][START_REF] Kemp | Analysis of a sleep-dependent neuronal feedback loop: the slow-wave microcontinuity of the EEG[END_REF]. Simulated EEG data is commonly used to study EEG forward and inverse models in the context of source localization (e.g. [START_REF] Gutierrez | Estimating brain conductivities and dipole source signals with EEG arrays[END_REF][START_REF] Yao | Evaluation of different cortical source localization methods using simulated and experimental EEG data[END_REF][START_REF] Bradley | Evaluation of Electroencephalography Source Localization Algorithms with Multiple Cortical Sources[END_REF]) and to test blind source separation methods [START_REF] Bridwell | Spatiospectral Decomposition of Multi-subject EEG: Evaluating Blind Source Separation Algorithms on Real and Realistic Simulated Data[END_REF]. It can be also used to study connectivity measures [START_REF] Haufe | A critical assessment of connectivity measures for EEG data: a simulation study[END_REF]. Several software packages exist that can generate synthetic EEG data. These include the Brainstorm package [START_REF] Tadel | Brainstorm: A User-Friendly Application for MEG/EEG Analysis[END_REF], the Fieldtrip toolbox [START_REF] Oostenveld | FieldTrip: Open Source Software for Advanced Analysis of MEG, EEG, and Invasive Electrophysiological Data[END_REF], the SIFT toolbox [START_REF] Delorme | ERICA: New Tools for Advanced EEG Processing[END_REF] and the BESA Simulator2 . Of these packages, Fieldtrip provides a few different generators for EEG trials, and the SIFT toolbox can generate data using autoregressive models. In principle these approaches could be customized by an advanced user to generate multiclass data for BCI testing purposes. However, this may require significant expertise from the part of the user, for example understanding of autoregressive modelling for SIFT.

In the scope of BCI, some previous simulation work exists. One possible approach is to simulate the predictions of the classifier [START_REF] Millán | Combining Brain-Computer Interfaces and Assistive Technologies: State-of-the-Art and Challenges[END_REF][START_REF] Boland | Using Simulated Input into Brain-Computer Interfaces for User-Centred Design[END_REF][START_REF] Rohani | BCI using imaginary movements: The simulator[END_REF] in order to study how usable an application would be when it's controlled with an inaccurate BCI. Another way to use simulation is to apply real recordings in an offline manner [START_REF] Brunner | Improved signal processing approaches in an offline simulation of a hybrid brain-computer interface[END_REF]. For example, the standard approach of testing BCIs by cross-validation can be considered simulation. In a real BCI session, the prediction errors made by the classifier may distract the user and hence provide a feedback effect. This effect is not modeled by offline cross-validation.

Simulated BCI data has been proposed before. One application is to attempt to use artificial data to complement real data for training the signal processing models [START_REF] Lotte | Generating Artificial EEG Signals To Reduce BCI Calibration Time[END_REF]. Artificial datasets have also been used in at least one competition: the BCI Competition IV featured simulated motor imagery data [START_REF] Tangermann | Review of the BCI Competition IV[END_REF]. The competitors were not informed beforehand that a particular dataset was made synthetically. Our framework contains the first public, open source re-implementation of the used generative technique. A detailed description of the approach can be found elsewhere [START_REF] Tangermann | Review of the BCI Competition IV[END_REF].

Since the proposed framework not only simulates EEG data, but can also perform offline BCI signal processing and classification, it is in order to briefly explain the main difference of the proposed framework to the well-known BCI software platforms (for overview, see e.g. [START_REF] Brunner | BCI software platforms[END_REF][START_REF] Lindgren | OpenViBE and Other BCI Software Platforms[END_REF]). The proposed framework is mainly intended for offline study of model behavior. Researchers interested in running realtime BCI experiments can consider e.g. OpenViBE [START_REF] Renard | OpenViBE: An Open-Source Software Platform to Design, Test and Use Brain-Computer Interfaces in Real and Virtual Environments[END_REF] or BCI2000 [START_REF] Mellinger | BCI2000: A General-Purpose Software Platform for BCI Research[END_REF]. Although our framework can perform signal processing on real data if the data is converted to the framework's conventions, a more extensive collection of signal classification components can be found e.g. in BCILAB [START_REF] Delorme | ERICA: New Tools for Advanced EEG Processing[END_REF]. For EEG data analysis, EEGLAB [START_REF] Delorme | ERICA: New Tools for Advanced EEG Processing[END_REF] and Fieldtrip [START_REF] Oostenveld | FieldTrip: Open Source Software for Advanced Analysis of MEG, EEG, and Invasive Electrophysiological Data[END_REF] are classical choices. At present, our framework can carry out the signal processing in BCILAB if requested, and optionally export the data to EEGLAB for visualizations.

Framework overview

The proposed framework aims to simulate BCI-like data in a controlled and modular fashion and allow BCI signal processing pipelines to be constructed and tested in the framework as well. These pipelines can use machine learning techniques and/or inverse modelling as part of their operation if desired. For convenience, the framework provides a mechanism to test the effects of varying sets of parameters, both on the generation and the signal processing side. In the following, we provide a high-level overview of the framework. For more technical description, we invite the reader to look at the user documentation supplied with the framework.

The framework is designed with the goal that all the parameters of interest should be specifiable from a single high-level script. The various submodules that are used should fill in default values if some parameters are not given. The framework itself is agnostic about most of the parameters. They are simply provided to the submodules that recognize them. This convention allows the experimenter to see at a glance what the framework is requested to do and specify the experimental parameters from a single location.

The framework consists of three main classes as shown in Figure 1: The first is the Generative model that constructs simulated experiment timelines (sequences of event markers) and simulated EEG-like data using random generators 3 . The second class implements the BCI signal processing and classification. We call each realization of this class a pipeline. A pipeline is typically intended to be calibrated using the training data produced by the generator and tested by an independently generated test dataset. Finally, the BCI Simulator class is a convenience tool that can iterate over sets of parameters. It can also perform repeated sampling with the same parame- ters in order to smooth out statistical variations in the results. In the end, the simulator computes prediction accuracies by comparing the pipeline outputs to the known ground-truths from the generator. As part of its design, the BCI simulator does not let the tested pipeline see the parts of the data that would not be available in real BCI experiment (e.g. trial labels, cortical sources, etc). Note that the generator and the pipeline classes can also be used separately. For example, the data generator can be used to simulate test data for some third-party BCI system without relying on the simulator or the pipelines. We now turn to describe the main modules of the framework in more detail.

Train

The generative model

The default signal generation module in the system follows the common linear superposition model [START_REF] Baillet | Electromagnetic brain mapping[END_REF][START_REF] Grech | Review on solving the inverse problem in EEG source analysis[END_REF]

X = AS + N, (1)
where X is an [electrodes × samples] matrix of measured EEG observations over time, A is the leadfield matrix modelling the volume conduction and S is a [sources × samples] matrix of source activities in the volume. The matrix S can include both signal and noise components. N is a matrix of surface noise. The rows of X correspond to individual surface electrodes and the rows of S to source dipoles in the volume. The electrodes and the sources are assumed to have 3D coordinates in relation to a head model associated with the leadfield. The leadfield matrix coefficients encode the model of the electrical propagation from the sources to the surface. Depending on the used level of detail, such leadfields may vary from single-sphere models to physiologically realistic, subject-specific models with different compartments and their conductivities. For details, see e.g. [START_REF] Baillet | Electromagnetic brain mapping[END_REF][START_REF] Grech | Review on solving the inverse problem in EEG source analysis[END_REF].

Due to the linear superposition model, the different data components can be generated both in the volume (in S) and on the surface (in N). The framework by default mixes the components on the surface. Although it would be possible to work directly with matrices S and N, the dimensions of these matrices and the appropriate indexing depends on the used head model. Subsequently, their manipulation can become tedious and error-prone. For this reason, the framework provides a higher-lever interface to specify the signal components. With this interface, each signal component is assumed to have three properties: when, what and where. Their interpretation is intuitive. The when specifies the event times and durations on a timeline, what specifies the signal content that is introduced to the EEG by these events, and where is the placement of this activity either in the volume or on the surface. This is illustrated in Figure 2. Each component also has a power parameter (or Signal-To-Noise Ratio, SNR) which we have omitted from the figure for clarity. The whole process can be alternatively seen as rendering that realizes a concrete multichannel signal from a more abstract timeline.

Note that in the framework, the different signal components are, by default, independent of each other. The respective generators do not see the parameters or the outputs of the others. To introduce dependencies, the user can implement a monolithic generator that internally handles them. Alternatively, the user can design a timeline that has dependencies between the events.

To give an example of the workflow, the investigator (user) first specifies the desired event generators and their parameters (or even the actual event timeline), specifies signal generators that react to these events, and declares where each type of activity should occur with relation to the head model. The framework uses the head model to obtain the positions and indexes of the relevant dipoles in S, and uses the associated forward model to project the volume data to the surface using eq. 1. With this approach, the head models can be changed and the scripts remain interpretable as they are defined on a more semantical level. Geometrical information is encapsulated in the head model. The user can either use the example head models provided with the framework, provide their own, or assemble a head model with the assistance of third-party packages such as Fieldtrip [START_REF] Oostenveld | FieldTrip: Open Source Software for Advanced Analysis of MEG, EEG, and Invasive Electrophysiological Data[END_REF] or OpenMEEG [START_REF] Gramfort | OpenMEEG: opensource software for quasistatic bioelectromagnetics[END_REF].

The proposed abstraction allows relatively easy adaptation of generative recipes from one type of BCI to another. For example, let us assume that two-class SSVEP [START_REF] Vialatte | Steady-state visually evoked potentials: Focus on essential paradigms and future perspectives[END_REF] and Motor Imagery [START_REF] Pfurtscheller | Motor imagery and direct braincomputer communication[END_REF] experiments have similar noise profiles but different origin and nature of the signal part. Then, it suffices to change the 'what' and 'where' parts of the specification: going from Motor Imagery to a simple SSVEP model, the 'what' part is changed to a function that generates a specific SSVEP response frequency depending on the class of the trial, and the 'where' part is changed from left and right motor cortices to cover a region of the occipital lobe.

The framework provides heuristic methods to approximate certain locations of interest from the used head model geometry. Specific keywords such as eyes, occipital lobe and left and right motor cortex are recognized by the heuristic where function and use simple deterministic selection rules such as 'eyes are approximated by two dipoles that are about halfway in z, in front in x, and symmetrically about 1/4 skull-width from the y midline on both sides'. If accurate anatomical knowledge and cortical segmentation is provided in the head model, this can be used instead of the heuristic approach, simply by using an exact where function that refers to the head model.

The framework conventions also suggest that each callable function implements an optional visualization. By enabling the visualization, the function itself can illustrate the data it generates in a way that is suitable for such data. Additionally, the framework provides some simple visualizations for aggregated or surface signals.

Figure 3 shows the used concepts and some of their options available at the time of writing.

Data generation example: BCI Competition IV

We make the previously introduced concepts more concrete with a motor imagery example. We follow the technique used to create one of the datasets in the BCI Competition IV [START_REF] Tangermann | Review of the BCI Competition IV[END_REF]. The proposed framework includes the first public re-implementation of the generator.

A specification to make data in the style of BCI Competition IV is shown in Figure 4. As can be seen, the specifications in the framework are either lists or composed of key,value pairs, where the value can also be a list of a function and its parameters. The parameters are passed to the functions Gaussian and pink noise, eye movements [START_REF] Tangermann | Review of the BCI Competition IV[END_REF], eyeblinks [START_REF] Tangermann | Review of the BCI Competition IV[END_REF], noise with spectral dependencies [START_REF] Tangermann | Review of the BCI Competition IV[END_REF], single frequency noise (e.g. 50hz/60hz), beta desynchronization [START_REF] Tangermann | Review of the BCI Competition IV[END_REF], P300 template, SSVEP frequency responses 'when'

Trial generator supports trial length, rest length, burn-in, class count and class ordering parameters. Random event generator is also available.

Examples provided

Motor Imagery [START_REF] Tangermann | Review of the BCI Competition IV[END_REF], elementary SSVEP [START_REF] Vialatte | Steady-state visually evoked potentials: Focus on essential paradigms and future perspectives[END_REF], elementary P300 [START_REF] Fazel-Rezai | P300 brain computer interface: current challenges and emerging trends[END_REF] Head models 9417x247 MRI-based, constrained/nonconstrained dipole orientation, sphere that handle them. The specifications in Figure 4 make it apparent how to change the various parameters such as the timeline of the experiment and the used head model without modifying the actual signal generators. The head specification declares the forward model used to map volume data to the surface and to provide the positions of the dipoles for the signal generation. The timeline specification contains the parameters related to synthesizing the experiment timeline. The effects specification concerns the actual activity simulated. Here, four data generators in total are specified and called in sequence. The first two simulate beta desynchronization at 12 Hz. The framework is instructed to insert these activities to the left and right motor cortex dipoles, heuristically localized using the specified head model. The next directive requests the generation of artifact noise originating from the eyes, and finally generic noise activity to be placed on the surface. The framework projects the volume data to the surface using the specified head model and then merges the different parts of the data by linear superposition with weighting chosen to give the desired SNR (on the surface).

Figure 5 illustrates some visualizations related to the generative specification we just described.

EEG classification pipelines

In the presented framework, a signal processing chain is called a pipeline. A pipeline can be calibrated with training data, and used to process new data. Pipelines are made using one or more modules called processors. These Figure 4: Simplified specification generating 2-class motor imagery data resembling the approach of the BCI Competition IV. The timeline specification has an event generator to make a basic two class timeline and an eyeblink event generator. The framework then triggers signal generators to react to these events. For example, the 'right' class event triggers 'left' motor cortex desynchronization in the above specification. The parameters that follow the functions specified with @ are simply arguments to those functions. In the last signal component, the directive 'loop these()' tells the BCI Simulator to expand this specification to 3 new ones, each with different level of surface noise SNR. The beta desynchronization generators are driven by the timeline shown, whereas the eye artifact generator reacts to random events (not shown). The noise generator is simply always active. After generation, these signals will be inserted to the places that were selected by the heuristic 'where' function and projected to the surface using the leadfield of the head model. Note how the eye artifacts are stronger than the mixture of the two other components in the surface data. processors are used in the order they are specified in a list such as the one shown on the bottom of Figure 6. Separate specifications are not required for calibrating the pipeline and processing data with it, and neither separate processors are needed. Instead, the pipeline and all processors are classes that must provide 'train()' and 'process()' member functions. A pipeline is essentially constructed by feeding it training data with the 'train()' call, and data transformation results are obtained using the 'process()' call for some set of data. If the pipeline ends with a classifier, it is expected to output probability vectors, which can then be seen as just another data transformation.

With this design, only a single specification is needed for train and test. It avoids potential discrepancies between train and test runs. Yet the chosen approach can support components that do not need training (such as usual temporal filters, fixed arithmetic, etc) as well as machine learning and statistical components. The data-independent classes simply do nothing on train and just process the data when processing is requested. The classes that construct a model do this during the train() call and then encapsulate the estimated model inside the constructed class object. When a pipeline is calibrated, it calls the train function of each processor of the specification sequentially. The first processor gets the original dataset, and the second processor gets the data as it is after having been processed by the first processor, and so on. The processing of new data is performed in the same order. This is illustrated on the top of Figure 6. In the conventions of the framework, a pipeline is ultimately expected to return a class probability vector for each trial in the given dataset. However, this is not strictly necessary: a pipeline can return an arbritrary transformation of the data. Predictions are only used by the BCI Simulator class that compares the results to the trial labels. Note that the framework is in general agnostic to what the processors pass to each other, it just assumes that the processors are specified in an order that the next processor is able to consume the output of the previous processor.

Figure 6 illustrates also a pipeline defined with parts provided with the framework. It implements a classic CSP-bandpower based pipeline for classification of Motor Imagery [START_REF] Müller-Gerking | Designing optimal spatial filters for single-trial EEG classification in a movement task[END_REF]. In the specification, each processor is followed by parameters specific to that processor. It's worth noting that the pipeline could also be implemented as single monolithic class, if the described processing stages were carried out inside the class code. When implementing a new pipeline, the designer has to choose the preferred level of modularity.

Figure 7 lists processors bundled with the framework. The bundled set is meant to be illustrative and it is not intended to implement the full extent of the current BCI knowledge. Rather, the processors were written to sup-.process( ) .train( ) @proc1(params1) .process( ) .train( ) @proc2(params2) .process( ) .train( ) @procK(paramsK)

Trainset predictions

Testset predictions Pipeline pipeLDA = {'name','csp-bandpower-lda', 'processors', { ... {@proc_bandpass_filter, 'freqLow',8,'freqHigh',30}, ... {@proc_csp, 'dim', 2, 'tikhonov', 0.5, 'shrink', 0.5}, ... {@proc_power_transform, 'logFeats',true}, ... {@proc_normalize}, ... {@proc_lda} } };

Figure 6: Top. Schematic for a signal processing pipeline, expanding the Pipeline class of Figure 1. For efficiency, a train() call is not required to return any data. In that case, the framework simply calls the corresponding process() function with the training data to obtain input for the next processor (not shown). Bottom, an example of pipeline specification. The specification declares the usual CSP-Bandpower LDA pipeline (e.g. [START_REF] Müller-Gerking | Designing optimal spatial filters for single-trial EEG classification in a movement task[END_REF]) using 5 different processors in a sequence. Each processor is constructed with its own parameters.

Type

Variants provided Classifiers LDA [START_REF] Hastie | The Elements of Statistical Learning[END_REF], liblinear [START_REF] Fan | LIBLINEAR: A library for large linear classification[END_REF], MD Classifier (as in [START_REF] Edelman | EEG Source Imaging Enhances the Decoding of Complex Right-Hand Motor Imagery Tasks[END_REF]), fixed threshold, BCILAB bridge [START_REF] Delorme | ERICA: New Tools for Advanced EEG Processing[END_REF]

Filters

Temporal filter, bandpass filter, BCILAB Feat. extraction CSP [START_REF] Müller-Gerking | Designing optimal spatial filters for single-trial EEG classification in a movement task[END_REF], inverse transforms (MN & WMN [START_REF] Grech | Review on solving the inverse problem in EEG source analysis[END_REF], sLORETA [START_REF] Pascual-Marqui | Standardized low-resolution brain electromagnetic tomography (sLORETA): technical details[END_REF], ...), time/frequency features, ICA [START_REF] Bell | An information maximisation approach to blind separation and blind deconvolution[END_REF], time interpolation Other Correlation feature selector, normalization, downsampling Simple DSP Squaring+log, identity, BCILAB port specific studies regarding CSP-Bandpower-LDA and inverse modelling.

Hence, these modules suffice to illustrate how to design pipelines using the conventions of the framework. A user wishing to quickly evaluate a larger set of state of the art is suggested to use the 'BCILAB' processor provided in the framework. This way, any processing available in BCILAB can be used. The framework by default provides specifications to construct the CSP/Bandpower/LDA pipeline (e.g. [START_REF] Müller-Gerking | Designing optimal spatial filters for single-trial EEG classification in a movement task[END_REF]) as well as a few pipelines based on inverse models: One is inspired by Cincotti et al. [START_REF] Cincotti | High-Resolution EEG Techniques for Brain-Computer Interface Applications[END_REF] and the another is after Edelman, Baxter and He [START_REF] Edelman | EEG Source Imaging Enhances the Decoding of Complex Right-Hand Motor Imagery Tasks[END_REF]. The user is invited to look into the package archive to find these and other example specifications.

BCI simulation

Artificially generated data and signal processing pipelines provide the central components to carry out BCI simulations. In the proposed framework, we also include a third central component called the BCI Simulator. This is a convenience tool used to repeatedly call the data generation and the pipeline training and testing, to compare the results to ground truth, and to aggregate the results. By default, prediction accuracies are computed and stored. Given the definitions for generation and the pipelines, the Simulator can perform repeated experiments by resampling new sets of data while keeping the sampling parameters the same. This way, better statistical characterization of the results related to each parameter condition can be obtained: enough iterations allows the empirical estimates of the pipeline accuracy and variance to converge and reduces the chance that some particular result was due to a statistical accident.

The system allows testing the effects of parameter changes by providing a simple construct for the purpose. The specifications (such as those shown in Figures 2 and6) controlling the system can contain statements which essentially instruct the Simulator to run multiple experiments while taking the parameter values from given sets. For example, an SNR parameter for some signal component could be specified as a range of values to test, as in Figure 2. In the figure, the simulator will construct 3 experiments where each has a different value of the SNR but keeps the other parameters equal.

A similar mechanism is available in BCILAB [START_REF] Delorme | ERICA: New Tools for Advanced EEG Processing[END_REF] for classification. In our framework, the loop requests can be used both in the generating and the pipeline specifications. It is also possible to have multiple loop requests.

Then the total number of train/test runs in the experiment is a product of the sizes of the combinations times the number of repetitions. Note that for data generation, the parameters can also be different between the train and tests sets. The only compatibility requirement between the two sets is that the pipelines estimated with a training set must be able to return results comparable to the ground truth when they are provided the test set. For example, the specifications can differ in the number of trials or the nature of noise. Also, if inverse models are used in the pipelines, different head models can be used in the data generation and the pipeline definitions. This can simulate the effect that in practice we rarely have a perfect head model of the BCI user in question. On the other hand, the structural parameters such as the number of sources and electrodes should stay the same, unless the pipeline processors are modified to handle such differences, for example by interpolation.

Example simulations

We presume a typical use of the framework is to simulate experiments by repeatedly generating data with different characteristics (parameters) while possibly modifying the pipeline parameters at the same time and then analyze the resulting classification accuracies. This allows empirical discovery of what is easy and what is difficult for different algorithms. For example, signal generation parameters such as artifact occurrence frequency or SNR could be modified while observing how this affects the BCI pipeline prediction accuracy. Experiment parameters can also be modified, for example the number of trials, trial length and the sampling rate. On the pipeline side it is possible to change everything from algorithm parameters (e.g. regularization, filter bandwidths, CSP dimensions, etc) to the algorithms themselves.

The signal data used in the experiments described in this section has been generated using forward models based on a standard three-layer mesh (scalp, skull, brain) obtained from processing MRI data with FieldTrip [START_REF] Oostenveld | FieldTrip: open source software for advanced analysis of MEG, EEG, and invasive electrophysiological data[END_REF]. The three layers were assigned respective normalized conductivities of 1, 1/15 and 1 (as in [START_REF] Oostendorp | The conductivity of the human skull: results of in vivo and in vitro measurements[END_REF]) and were composed of up to 46 000 triangles for the high resolution cases. The generated models map 9417 cortical dipoles oriented along the normal to the cortical surface to 249 electrodes. An ajoint double layer formulation has been used to compute this mapping.

Eyeblink frequency vs eyeblink power. As an example, Figure 8 shows how the common CSP/LDA pipeline prediction accuracy behaves when the eyeblink artifact frequency and its SNR are changed. The data generation was following the BCI Competition IV style of Motor Imagery simulation using the model described earlier. In this case we replaced the data driven noise of the original approach [START_REF] Tangermann | Review of the BCI Competition IV[END_REF] with volumetric pink noise to ensure the results are not due to a particularities of a specific EEG recording that is normally used to obtain the method's spectral dependency model. The SNR of the pink noise was calibrated to give 80% pipeline prediction accuracy without any eyeblinks.

After the detrimental effect of the eyeblinks is observed, the experimenter could proceed e.g. by studying if the pipeline regularization parameters would help against the eyeblinks, or how much more training data would be needed (in principle) to compensate for them. In the framework, this would be just a matter of specifying ranges for these additional parameters of interest and let the computer perform the experiment. Alternatively, the researcher might attempt to implement an eyeblink removal technique and examine how well it performs, or route the data to some more robust signal processing technique. After satisfying intuition and solution to the problem has been obtained, real experiments could be carried out to validate the hypotheses formed with the simulated experiment.

Suppose that the experiment described above was done with real subjects. They would be asked to modulate the strength and frequency of their eyeblinks in addition to performing the challenging task of motor imagery at the same time. How much time would such a study take? In total, to draw the plot of Figure 8, we tested 60 parameter combinations with 25 resampled repetitions for each combination. This means 1500 simulated EEG sessions consisting of generating a train and a test set pair. The train set had 16 trials and the test set had 54. With trial length of 4 seconds, followed by rest of 2 seconds, the total length of the dataset is 1500 * (16s+54s) * (4s+2s) = 630000s or 175 hours of simulated EEG. A real recording session following the Graz BCI paradigm [START_REF] Pfurtscheller | Motor imagery and direct braincomputer communication[END_REF] would be much longer due to additional time needed for setup and dismantling of the electrode montage (from 7 to 20 minutes of setup per session in the study of Nijboer et al. [START_REF] Nijboer | Usability of three electroencephalogram headsets for brain-computer interfaces: a within subject comparison[END_REF]), possible initial burn-in period (e.g. 30sec per recording) and a few seconds overhead for cue on- set/offset per trial. In contrast, the simulated experiment can be run on a normal desktop PC in one night.

Effect of location of the discriminable sources. Figure 9 shows another simulated experiment where we compare the CSP/Bandpower pipeline to a method based on inverse models, inspired by Cincotti & al. [START_REF] Cincotti | High-Resolution EEG Techniques for Brain-Computer Interface Applications[END_REF]. The first pipeline optimizes a statistical spatial filter, whereas the second model reconstructs the sources in the cortical volume before classification. The source reconstructing pipeline also removes source dipoles from consideration which are not inside a hand-specified region of interest (ROI) roughly covering the motor cortices. The first pipeline was illustrated in Figure 6, and the second is included in the framework distribution. The data generation is the same as before, using 16 training trials of 4 seconds each and 54 test trials. We disabled the eyeblink artifacts. Instead, we change the location of the sources that generate the discriminable signal. We move the two cortical dipoles downwards along the cortex, starting from their usual location under the electrodes C3 and C4 and then move the sources lower until the moved distance is approximately 60% of the diameter of the cortex model. It can be noted that the inverse pipeline performs well compared to the CSP/Bandpower, but its accuracy drops significantly when the sources eventually go out of the cortical ROIs specified for the inverse approach. However, it is of interest that this accuracy drop is not a on-off phenomenon. This is due to a phenomenon called source leakage (e.g. [START_REF]Brain-Computer Interfaces[END_REF]): the imprecision of the source reconstruction spreads the source activities to nearby sources when the sources are reconstructed. Thus, when the volumetric sources are reconstructed in the method, some relevant information leaks to the ROI even if the source is not originally inside it. This leakage is then caught by the statistical feature selection and classification techniques of the method, suggesting that the used BCI method can benefit from source leakage. As the source leakage is usually considered a harmful phenomenon in source reconstruction, this appears as another interesting finding that simulated studies can provide for further consideration. Finally, the plot shows an accuracy anomaly near 30% depth. As both pipelines are affected, this suggests a sudden change in how the leadfield projects the sources to the surface. Note that since we used a constrained orientation leadfield, the dipole traversal along the cortex changes the directions the source dipoles radiate to according to the folding of the cortical model. Do electrode correlations require source correlations? In addition to providing quantitative results such as accuracies, the framework can be used to obtain qualitative insights about the model system. For example, using the framework to visualize the correlations of the generated data as in Figure 10 illustrates that the forward transform can introduce dependencies to the EEG. In the data, using the same head model as before, we specified all the sources in the volume to generate mutually independent pink noise. In the volume these sources were then approximately uncorrelated (not shown). However, after projection of the sources to the scalp EEG by the forward model, the surface data exhibits the typical EEG-like correlation patterns that in this case must emerge from the modeled volume conduction. For comparison, we also recorded a real dataset with an high-grade EGI system4 that the electrode set of the head model was modeled after. Note that the leadfield we used was not estimated from the same subject as the EEG was recorded from. Nevertheless, the correlation structure exhibits similar patterns both in simulated and real EEG. The correlations of real EEG data are stronger than those of the simulated data, suggesting that real brain activity has more dependencies in the volume than the independent noise we used. In both cases the correlations are qualitatively related to the electrode distance, as the image on the right in Figure 10 suggests. The image simply plots a Gaussian weighted distance between each electrode pair in the used electrode set.

The resemblance of CSP and WMN inverse model. Finally, for Figure 11, we generated one session of 2-class motor imagery data originating from 2 dipoles located on the left and right side motor cortexes and mixed these sources with pink volumetric noise as before, but with no artifacts. The figure illustrates the two most important CSP filters obtained with the data, as well as the corresponding projections obtained from the Weighted Minimum Norm estimate (WMN). The latter approach attempts to reconstruct the generating sources, using the generating leadfield and knowledge which sources generated the data, but not the data itself. The left and right are swapped in CSP as the algorithm does not order the filters in any manner. The integration performed by the WMN approach appears to focus tightly on the electrode locations close to the sources, whereas the CSP solution is less sparse and more spread across the electrodes. The CSP solution becomes less defined if eyeblink artifacts are present in the data, when the amount of training data is reduced, or the signal component is made weaker (not shown) but the WMN model is not affected by these changes as it does not use the data. With real data it would be more difficult to investigate the CSP reactions to different conditions, as the ground truth would not be available and some parameters such as the strength of Event-Related Desynchronization (ERD) or position of the sources would be difficult to modulate by a subject.

Discussion and future work

The proposed framework is not intended as a realistic brain simulator (a massive undertaking, see e.g. [START_REF] Markram | Introducing the Human Brain Project[END_REF]). Even if the used models are made to match the current knowledge, some properties of the real brain ale likely to be presently unknown. The simulated data can only exhibit such behavior that can result from the models that are used. If some behavior of the real brain is outside the scope of these models, it cannot be discovered from the simulated data alone. On the contrary, analysis of real data may be able to discover and use data characteristics which are outside the scope of the current generative models. Due to this, great care should be taken when drawing inferences regarding real BCI from simulated EEG. Instead of being a basis for such inferences, the framework should be used to gain insight about the interplay of the models being studied. Once some interesting hypotheses have been formulated, they can be used to guide the design of human experiments.

We stress that the user should apply our framework with consideration. For example, if a large set of different signal processing parameters are studied, it may be necessary to detect which differences are statistically significant and correct for multiple comparisons, for example using the functions from the Matlab's statistics toolbox. Even so, significant differences on simulated data do not guarantee the same differences on real data, and any findings should be taken only as hypotheses for additional study. Further, the data generation should be configured reasonably. As an example of the contrary, a long recording session of stationary EEG may be very difficult to obtain with a human subject, whereas for the simulator it is effortless. On the other hand, phenomena such as eyeblink frequency and modulating the strength of the Event-Related Desynchronization (ERD) in motor imagery may very well correspond to real phenomena.

In the future, the framework could be extended to many directions. One possibility involves adding connectivity modelling of brain areas over time. Another direction would involve implementing lower-level models of neuronal assemblies and even spiking neurons and model how their activities are aggregated into dipolar volume currents. The framework could also be extended to generate and test multiuser datasets for machine learning techniques that benefit from big data.

Conclusion

We have proposed a framework for studying BCI signal processing through simulation and have described the main aspects of its design. To summarize, the framework can generate and test multiclass EEG data and classification pipelines according to specifications given by the user. By its modular design, the framework allows mixing and matching of different kinds of signal generators, head models, BCI timelines, signal positioning, as well as noise and artifact generators. Similar mixing of parts is possible for the signal processing pipelines. For convenience, the framework can automatize the generation and testing of different parameter combinations of interest.

In the scope of the paper, we have illustrated that already simple simu-lated experiments can reveal interesting and apriori counterintuitive hypotheses for further consideration. As the proposed framework is open source and available free of charge, we hope that the community will find the proposed system useful in illustrating BCI systems to students, in debugging existing BCI systems with artificial data, and most of all for studying a variety of questions that remain in BCI signal processing.

Figure 1 :

 1 Figure 1: Data flow in the framework between the main components. Different parameter specifications define how the data is generated and what methods the signal processing pipeline uses.

Figure 2 :

 2 Figure2: EEG signal generation. First, one or more event generators are used to make a timeline of discrete events with durations. Then, different generators are specified to react to the events. Each generators' output is then inserted to the signal as requested. In the figure we show only one signal component generation for clarity, even though the user can mix and match any amount of such components and provide new generators.

Figure 3 :

 3 Figure 3: Various options provided for data generation. User-provided options can be alternatively used.

Figure 5 :

 5 Figure 5: Components of a generated motor imagery signal as visualized by the framework. Top left, the discriminable signal from two desynchronization generators combined to one display. Top right, eye artifacts. Bottom left, the noise. Note that since the noise originates from the whole volume, only the 6 first dipoles are shown. Bottom right, first 15 s of surface data for the 4 first electrodes.The beta desynchronization generators are driven by the timeline shown, whereas the eye artifact generator reacts to random events (not shown). The noise generator is simply always active. After generation, these signals will be inserted to the places that were selected by the heuristic 'where' function and projected to the surface using the leadfield of the head model. Note how the eye artifacts are stronger than the mixture of the two other components in the surface data.

Figure 7 :

 7 Figure 7: Basic processors provided in the framework to build pipelines. New processors can be inserted by adding new Matlab classes to the directory tree. The classes just need to conform to the interface conventions of the framework.

Figure 8 :Figure 9 :

 89 Figure 8: Effect of eyeblink frequency to simulated CSP/Bandpower/LDA two-class motor imagery classification. Each point is an average accuracy of 25 simulated experiments with resampled train and test sets. Low SNR indicates the eyeblink effect is stronger compared to the other signal components.Notice the apriori unintuitive result: having no eyeblinks is optimal for the accuracy, but many eyeblinks is generally better than having only a few of them. This may be due to the statistical pipeline possibly being able to take eyeblinks somewhat into account in the modelling when they are no longer rare. If eyeblinks are present, the SNR appears more important to the accuracy than the blink frequency. Approximately 175 hours of simulated BCI data was used to compute the plot.

Figure 10 :

 10 Figure 10: Correlation matrices of a specific kind of generated data (left) and real EEG data (middle). Right, a matrix showing pairwise electrode closeness measures. For details, see text.

Figure 11 :

 11 Figure 11: Spatial filters. Top, CSP filters obtained using simulated data. Bottow, filters from the WMN algorithm corresponding to reconstruction of the true sources. CSP uses only EEG data to build its model, whereas WMN relies on physiological information only and does not use data.

Downloadable from http://gitlab.inria.fr/sb/ . Until the paper has been accepted and the code can thus be publicly released, please use the login 'sbreviewer' and password 'Investigator35b22--' to obtain the code.

http://www.besa.de/

The framework is not tightly tied to EEG, and could in principle be modified for other streaming data.

256-channel EGI (Electrical Geodesics, USA) cap with EGI NetAmps 300 amplifier.

Acknowledgement

We thank Axelle Pillain, Lyes Rahmouni and John-Erick Guzmann for contributions to the framework. We also thank Camille Jeunet and Benoit le Gouis for comments on an earlier version of this manuscript. This work was funded by the Labex CominLabs project SABRE.


François Goasdoué

Paweł Guzewicz
email: pawel.guzewicz@inria.fr

Ioana Manolescu
email: ioana.manolescu@inria.fr

Incremental structural summarization of RDF graphs

Realizing the full potential of Linked Open Data sharing and reuse is currently limited by the difficulty users have when trying to understand the data modeled within an RDF graph, in order to determine whether or not it may be useful for their need.

We demonstrate our RDFQuotient tool, which builds compact summaries of heterogeneous RDF graphs for the purpose of first-sight visualizations. An RDFQuotient summary provides an overview of the complete structure of an RDF graph, while being typically many orders of magnitude smaller, thus can be easily grasped by new users. Our summarization algorithms are time linear in the size of the input graph and incremental: they incrementally update a summary upon addition of new data.

For the demo, we plan to show the visualizations of our summaries obtained from well-known synthetic and real data sets. Further, attendees will be able to add data to the summarized RDF graphs and visually witness the incurred changes.

INTRODUCTION

Semantic Web graphs are nowadays being published and shared at a massive scale, e.g., Linked Open Data (LOD) Cloud (https: //lod-cloud.net) lists 1.200 graphs, while the LOD Atlas portal (http://lodatlas.lri.fr) references more than 20.000 graphs. Some of these graphs are domain-oriented, that is, they reflect a certain application domain, e.g., education, medical etc. On the contrary, a few RDF graphs are encyclopedic, e.g., DBpedia (https://wiki. dbpedia.org) and YAGO [START_REF] Rebele | YAGO: A Multilingual Knowledge Base from Wikipedia, Wordnet, and Geonames[END_REF], covering many different topics; often, these are unions of many domain-specific ones, e.g., DBpedia is available for download as a set of domain-oriented "datasets". An overwhelming majority of the RDF graphs found in portals such as LOD Cloud or LODAtlas, https://data.gov.uk, https://data.gov etc. are domain-oriented.

Currently, a large obstacle toward exploiting this wealth of data is the difficulty for human users to make sense of a newly encountered RDF graph. The motivation for our work is to help users learn at first sight, without any prior knowledge about the graph and without having to set any parameter, the (ideally complete) structure of a domain-specific RDF graph. Given that RDF graphs can be very large, while the human information absorption capacity is relatively limited, RDF graph summaries have been used as intermediaries: from a given graph G a summary is extracted, then the summary is shown to the users in order to convey information about the structure and/or content of G.

We demonstrate RDFQuotient, a tool for constructing a complete summary of the structure of an RDF graph which does not require any user input. The particular advantage of RDFQuotient is its tolerance to heterogeneity, which enables it to build compact, easy-to-visualize summaries even from very large graphs, while preserving many of the important structural features of the graph. RDFQuotient summaries can be built efficiently, in linear time in the size of the graph. Further, they can be incrementally updated: upon addition of a triple t to a graph G, the summary of G ∪ {t } can be efficiently computed out of the current summary of G and t, without re-traversing the G triples.

Motivating example Figure 1 illustrates a possible visualization of an RDFQuotient summary of a BSBM [START_REF] Bizer | The Berlin SPARQL Benchmark[END_REF] benchmark graph of 10 8 triples. This visualization reflects the complete structure of the graph, using only 5 nodes and 11 edges, comparable to a simple small Entity-Relationship diagram. This summary reads as follows: (i) Non-leaf graph nodes belong to one of five disjoint classes, each represented by a summary node (boxes labeled N 1 to N 5 in Figure 1). The number of graph nodes in each class appears in parenthesis after the label Ni of their representative; (ii) Graph nodes from a class may have types. Each such type appears under the summary node label, together with its number of occurrences among graph nodes of that class, e.g., 5919 nodes represented by N 3 are of type Producer, while 3050 are of type Vendor; (iii) Graph nodes from a class may have outgoing properties whose values are leaf nodes in the graph; the set of all such properties appears in the corresponding summary node, one property per line. For each property, e.g. country for N 3, the summary node specifies how many graph nodes represented by this summary node have it (8969 in this case), and how many distinct leaf nodes are target of these edges (10 in this case); (iv) Graph nodes from a class may have outgoing properties whose values are non-leaf nodes in the graph. For each graph edge n 1 a -→ n 2 , where n 1 , n 2 are non-leaf graph nodes and a is the property (edge label), an a-labeled edge in the summary goes from the representative of n 1 to that of n 2 . Next to a, this summary edge is also labeled with the number of graph edges to which it corresponds; (v) Properties from a small, fixed vocabulary are considered metadata (as opposed to data) and therefore they are not used to group nodes in classes, e.g., rdf-schema#-comment and rdf-schema#-label in Figure 1. More such visualizations can be found online 1 ; below, we also work out an example leading from an RDF graph to its summary and then such a visualization.

We propose to demonstrate the incremental construction of four related (but different) summaries, i.e., show how summaries quickly adjust when triples are added to the summarized RDF graphs. Our summaries can be built from graphs where none, some or all nodes have one or more types; this is important because in many synthetic and real-life RDF graphs we studied, a large share of nodes is untyped [START_REF] Čebirić | Compact Summaries of Rich Heterogeneous Graphs[END_REF]. Two of our summaries give preeminence to types (when available) to build the summary; nodes are first grouped by types and then by the relationships to other nodes. By contrast, the two other (including the one in Figure 1) give preeminence to node relationships; nodes are first grouped according to their relationships with others, then, each group is typed with the types of the graph nodes it represents within the summary (this is how each type has been attached to a summary node in our figure). In the total absence of types, each Below, we define our summaries (Section 2) and summarization algorithms (Section 3). Then, we present the demonstration scenario based on summary visualizations (Section 5). Finally, we compare them with related work and we conclude (Section 6).

RDFQUOTIENT SUMMARIES

Let U be a set of URIs, L be a set of literals and B be a set of blank nodes as per the RDF specification. An RDF graph G is a set of triples of the form (s, p, o) where s ∈ U ∪ B ∪ L, p ∈ U and o ∈ U ∪ B ∪ L. The special URI type, part of the RDF standard, is used to attach types to nodes. An RDF graph may contain ontology (schema) triples; while there are interesting interactions between summarization and ontologies [START_REF] Čebirić | Compact Summaries of Rich Heterogeneous Graphs[END_REF], below we only focus on summarizing the non-schema triples, which make up the vast majority of all RDF graphs we encountered. Thus, we consider G consists exclusively of type triples and/or data triples (all those whose property is not type; we call these data properties).

An RDF equivalence relation denoted ≡ is a binary relation over the nodes of an RDF graph that is reflexive, symmetric and transitive. Given an equivalence relation ≡, an RDF graph quotient is an RDF graph having (i) one node for each equivalence class of nodes; (ii) for each edge n 1 a -→ n 2 , a summary edge n ≡ It is easy to see that the set of non-empty source (or target) cliques is a partition over the data properties of an RDF graph G. Further, if a G node n is source of some data properties, they are all in the same source clique; similarly, all the properties of which n is a target are in the same target clique. Based on these cliques, for any nodes n 1 , n 2 of G, we define: • n 1 is strongly equivalent to n 2 , denoted n 1 ≡ S n 2 , iff n 1 , n 2 have the same source clique and the same target clique. Further, we decide that in any RDF equivalence relation, any class node, i.e., a URI c appearing in a triple of the form (n, type, c), is (i) only equivalent to itself and (ii) represented by itself in any RDFQuotient summary. This ensures that RDF types (classes), which (when present) denote an important information that data producers added to help understand their RDF graphs, are preserved in the summary.

• n 1 is weakly equivalent to n 2 , denoted n 1 ≡ W n 2 , iff n
The equivalence relations ≡ W and ≡ S lead to the weak, respectively strong summaries, defined as quotients of G through ≡ W , denoted G /≡ W , respectively, through ≡ S , denoted G /≡ S . Figure 3 illustrates these on the sample graph in Figure 2. For brevity, in Figure 3 and from now on, we use a, w, te, ta, cd to denote respectively the properties advises, writes, teaches, takes, and coursedescr.

In G /≡ W , N 1 represents all the people (p 1 to p 5 ), N 2 represents the courses, N 3 the articles and N 4 the course descriptions. Note the self-loop from N 1 to itself; it denotes that some nodes represented by N 1 advise some nodes represented by N 1 . This summary has only 4 nodes and 5 edges. It conveys the essential information that some nodes advise, write, also they teach and take something that has course descriptions. The Professor and Grad-Student types of nodes p 1 , respectively p 2 , are attached to their common representative N 1 .

G /≡ S differs from G /≡ W by representing the person nodes in two separate groups: those represented by N 1 advise those represented by N 2 . This is because the target clique of p 1 , p 3 and p 4 is empty, while the target clique of p 2 and p 5 is {advises}. This example illustrates the fact (visible from the summary definitions) that G /≡ S summarizes at finer granularity than G /≡ W (or, equivalently, ≡ S entails ≡ W , but the opposite does not hold).

Clique-based structural summarization leads to compact summaries even in graphs with heterogeneous structure. This is because of the transitive aspect of the property cliques. For example, p 1 and p 3 have the same source clique, even though their property sets are disjoint: {a, w } for p 1 , {te} for p 3 ; they are in the same source clique e.g. due to p 4 , which has both a and te. In contrast, previously studied quotient summaries, in particular those aimed for indexing and query optimization, would not accept p 1 and p 3 as equivalent; in general, such summaries lead to more equivalence classes (summary nodes), thus also summary edges, making summaries hard to understand visually. Type-first summarization The weak and strong summary group nodes according to their incoming/outgoing data triples and then just "carry" their types to the summary. A different choice is to group nodes first by their set of types (if any) 2 , and use the data triples to group the nodes without types. We define:

• n 1 is typed-weak equivalent to n 2 , noted n 1 ≡ TW n 2 , iff (i) n 1 , n 2 have the same non-empty set of types or (ii) both n 1 , n 2 are untyped, and n 1 ≡ W n 2 ;

Figure 4: Typed weak graph summary.

• n 1 is typed-strong equivalent to n 2 , noted n 1 ≡ TS n 2 , iff (i) n 1 , n 2 have the same non-empty set of types or (ii) both n 1 , n 2 are untyped, and n 1 ≡ S n 2 .

These relations lead to the typed weak (G /≡ TW ), respectively, to the typed strong (G /≡ TS ) RDFQuotient summaries. Figure 4 illustrates typed weak summarization on our sample graph; on this simple example, G /≡ TS is identical (in general, it may differ).

BUILDING RDFQUOTIENT SUMMARIES

We have devised algorithms which build G /≡ W , G /≡ S , G /≡ TW and G /≡ TS through a single traversal of an RDF graph G, in two flavors: (i) global: traverse G, compute all the cliques, then traverse it again and represent nodes according to their cliques and/or types; (ii) incremental: in a single traversal of G, gradually build each source and target clique based on the triples traversed up to that point and simultaneously represent G nodes in a summary that is continuously updated; after traversing the last triple of G, each incremental summarization algorithm ends up with the respective summary of the full G. The algorithms are detailed and their correctness is proved in [START_REF] Čebirić | Compact Summaries of Rich Heterogeneous Graphs[END_REF]; below, we illustrate their interesting points on minimal examples. First, let us see on an example how ≡ W can grow during incremental weak summarization. Suppose the graph G in Figure 2 is traversed and summarized starting with: (p 1 advises p 2 ), then (p 1 wrote a 1 ), then (p 4 teaches c 2 ) (see the figure above). When we summarize this third triple, we do not know yet that p 1 is equivalent to p 4 , because no common source of teaches and advises (e.g., p 3 or p 4 ) has been seen so far. Thus, p 4 is so far not equivalent to any other node, and represented separately from p 1 . Now, assume the fourth triple traversed is (p 4 advises p 5 ): at this point, we know that advises, wrote and teaches are in the same source clique, thus p 1 ≡ W p 4 , and their representatives (highlighted in yellow) must be fused in the summary. More generally, it can be shown that ≡ W only grows as more triples are visited (i.e., is monotonic), in other words: if in a subset G ′ of G's triples, two nodes n 1 , n 2 are weakly equivalent, then this holds in any

G ′′ with G ′ ⊆ G ′′ ⊆ G.
Incremental strong summarization is even more complex because unlike ≡ W , ≡ S may grow and shrink during summarization (i.e., is non-monotonic). For instance, assume the summarization of the graph in Figure 2 starts with (p 1 wrote a 1 ), (p 2 wrote a 2 ), (p 2 takes c 2 ) (see the figure below). After these, we know p 1 ≡ S p 2 ; their source clique is {wrote, takes} and their target clique is ∅. Assume the next triple traversed is (p 3 advises p 2 ): at this point, p 1 is not ≡ S to p 2 any more, because p 2 's target clique is now {advises} instead of ∅. Thus, p 2 splits from p 1 , that is, it needs to be represented by a new summary node (shown in yellow below), distinct from the representative of p 1 . Further, note that the representative of p 1 and p 2 (at left above) had one takes edge (highlighted in red) which was solely due to p 2 's outgoing takes edge. By definition of a quotient summary, that edge moves from the old to the new representative of p 2 (the yellow node). If, above at left, p 1 had also had an outgoing edge labeled takes, at right, both nodes in the top row would have had an outgoing takes edge. It can be shown that splits only occur in such cases, i.e., a node whose target clique becomes non-empty (respectively whose source clique becomes non-empty) and the node was previously represented together with other nodes; if it was represented alone, the respective clique of its representative is just updated. The amortized complexity of our summarization algorithms is linear in the number of triples of G. Figure 5 illustrate this empirically on a variety of benchmark (LUBM and BSBM) and real-life (DBLP, Springer conference etc.) datasets ranging from a few hundred thousands to more than 100 million triples; note that both axes are in log-scale. The implementation is made in Java 1.8; RDF graphs are stored in Postgres 9.6 and traversed from there. Increm-W is the fastest overall; it traverses G only once, thus it is faster than global-W which performs one extra pass to compute the cliques. S, TW and TS, in this order, are more expensive, and finally incremental S, which pays an extra performance overhead for growing and shrinking the equivalence relation.

FROM SUMMARIES TO VIZUALIZATIONS

The core of our work is on defining and efficiently building summaries; here we present one possible way of rendering them through a vizualization like the one illustrated in Figure 1.

On our four summaries we apply leaf and type inlining, as follows. We remove type edges; instead, each type attached to a node in the summary is shown in the box corresponding to the node, after the node ID. Similarly, for each edge n a -→ m where m is a leaf, we include a as an "attribute" of n, and do not render m (we say it has been "inlined" within n). A sizable part of an RDF graph's nodes are leaves; as we will show, inlining them into their parent nodes greatly simplifies the visualization. 6 illustrates inlining for the S summary of our sample graph. This summary is extremely compact, yet rich with information; professors, students, and courses are visible at a glance. Articles have been inlined within their authors as they were leaves in G /≡ TS (Figure 3). This simplification can also be seen as a small loss of information: Figure 6 does not immediately suggest that Professors may have written articles together with GradStudents. However, (i) only leaf nodes are folded and (ii) after a first glance, users may pursue exploration by other means (e.g., queries to check for such joint articles).

DEMONSTRATION SCENARIO

Demonstration attendees will be able to pick an RDF graph from a list of well-known synthetic and real data sets, visualize their summaries, and compare with other close competitor summaries, such as those mentioned in Section 6; some of these vizualizations can be seen online (https://team.inria.fr/cedar/projects/ rdfquotient/). Attendees will also be able to add new triples to an RDF graph, to figure out through our summary visualization how changes in the original data are rapidly reflected into the summary thanks to incremental summarization. To make it entertaining, we plan to use RDF data on the conference attendees, from DBLP, other public sources, and made-up triples to get interesting summary changes.

RELATED WORK & CONCLUSION

The literature comprises many RDF summarization techniques, more than a hundred of which we covered in a recent co-authored survey [START_REF] Cebiric | Summarizing Semantic Graphs: A Survey[END_REF]. RDFQuotient summarizes the structure of the data triples, which form a vast majority of RDF graphs; complementary proposals summarize the ontology, the values, find the most frequent property groups etc. Closest to us are quotient summaries which group nodes by the set of their outgoing data properties ("characteristic sets" [START_REF] Neumann | Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins[END_REF]) and possibly also by by the set of their incoming data properties (forward and backward bisimulation [START_REF] Kaushik | Covering indexes for branching path queries[END_REF]). Our clique-based summarization differs from these by the transitive aspect of the cliques which leads to heterogeneitytolerant summarization. Indeed, as we plan to show during our demonstrations, more strict summaries such as [START_REF] Kaushik | Covering indexes for branching path queries[END_REF][START_REF] Neumann | Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins[END_REF] support query optimization and indexing well, but have too many nodes and edges, even after inlining, for a comfortable vizualization. In exchange, our summaries are not generally appropriate for indexing, as they do not give e.g. access to "all the resources having properties a and b": the graph nodes whose source clique is {a, b} may have one or another or both.

©

  2019 Copyright held by the owner/author(s). Published in Proceedings of the 22nd International Conference on Extending Database Technology (EDBT), March 26-29, 2019, ISBN 978-3-89318-081-3 on OpenProceedings.org. Distribution of this paper is permitted under the terms of the Creative Commons license CC-by-nc-nd 4.0.

Figure 1 :

 1 Figure 1: Visualization built from an RDFQuotient summary.

Figure 2 :

 2 Figure 2: Sample RDF graph. type-first summary coincides with a type-ignorant one (thus, our four summaries collapse into two).Below, we define our summaries (Section 2) and summarization algorithms (Section 3). Then, we present the demonstration scenario based on summary visualizations (Section 5). Finally, we compare them with related work and we conclude (Section 6).

2 ,

 2 where n ≡ i , i ∈ {1, 2}, is the summary node corresponding to the equivalence class of n i , also called representative of n i . The literature comprises many quotient graph summaries (seeSection 6), which differ by their equivalence relations.The equivalence relations we use are based on the concept of property cliques, which encodes a transitive relation of edge co-occurrence on graph nodes. Given an RDF graph G, two data properties p 1 , p 2 are in the same source clique iff: (i) there exists a G node n which is the source of p 1 and p 2 (i.e., (n, p 1 , x) ∈ G and (n, p 2 , y) ∈ G for some x and y), or (ii) there exists a data property p 3 such that p 3 is in the same source clique as p 1 , and p 3 is in the same source clique as p 2 . Symetrically, p 1 and p 2 are in the same target clique if there exists a G node which is the target of p 1 and p 2 , or a data property p 3 which is in the same target clique as p 1 and p 2 . In Figure2, the properties advises and teaches are in the same source clique due to p 4 . The same holds for advises and wrote due to p 1 ; consequently, advises and wrote are also in the same source clique. Further, the graduate student p 2 teaches a course and takes another, thus teaches, advises, wrote and takes are all part of the same source clique. In this example, p 1 , p 2 , p 3 , p 4 , p 5 have the source clique SC 1 = {advises, takes, teaches, wrote}, c 1 , c 2 , c 3 have the source clique SC 2 = {coursedescr} and a 1 , a 2 have the empty source clique SC 3 = ∅. Similarly, the target cliques are, respectively; TC 1 = {advises} for p 2 , p 5 , TC 2 = {teaches, takes} for c 1 , c 2 , c 3 , TC 3 = {coursedescr} for d 1 , d 2 , TC 4 = {wrote} for a 1 , a 2 and TC 5 = ∅ for p 1 , p 3 , p 4 .

  [START_REF] Bizer | The Berlin SPARQL Benchmark[END_REF] , n 2 have the same source clique or the same target clique;

Figure 3 :

 3 Figure 3: Weak (left) and strong (right) graph summary.

Figure 5 :

 5 Figure 5: Summarization time (s) vs. graph sizes |G|.

Figure 6 :

 6 Figure 6: Leaf and type inlining on the sample strong summary from Figure 3 (right).

Figure

  Figure6illustrates inlining for the S summary of our sample graph. This summary is extremely compact, yet rich with information; professors, students, and courses are visible at a glance. Articles have been inlined within their authors as they were leaves in G /≡ TS (Figure3). This simplification can also be seen as a small loss of information: Figure6does not immediately suggest that Professors may have written articles together with GradStudents. However, (i) only leaf nodes are folded and (ii) after a first glance, users may pursue exploration by other means (e.g., queries to check for such joint articles).

https://team.inria.fr/cedar/projects/rdfquotient/

We use set of types and not just "type" on purpose, because an RDF node may have more than one type. If we classified a node according to each of its types, as in e.g.[START_REF] Campinas | Efficiency and precision trade-offs in graph summary algorithms[END_REF], a node with many types would have more than one representative, which is incompatible with quotient summarization.