# Practitioner-Centric Approach for Early Incident Detection Using
Crowdsourced Data for Emergency Services

Yasas Senarath  George Mason University, USA
<EMAIL_ADDRESS>Ayan Mukhopadhyay  Vanderbilt University, USA
<EMAIL_ADDRESS>Sayyed Mohsen Vazirizade  Hemant Purohit
Vanderbilt University, USA
<EMAIL_ADDRESS>George Mason University, USA
<EMAIL_ADDRESS>Saideep Nannapaneni  Wichita State University, USA
<EMAIL_ADDRESS>Abhishek Dubey  Vanderbilt University, USA
<EMAIL_ADDRESS>
###### Abstract

Emergency response is highly dependent on the time of incident reporting.
Unfortunately, the traditional approach to receiving incident reports (e.g.,
calling 911 in the USA) has time delays. Crowdsourcing platforms such as Waze
provide an opportunity for early identification of incidents. However,
detecting incidents from crowdsourced data streams is difficult due to the
challenges of noise and uncertainty associated with such data. Further, simply
optimizing over detection accuracy can compromise spatial-temporal
localization of the inference, thereby making such approaches infeasible for
real-world deployment. This paper presents a novel problem formulation and
solution approach for practitioner-centered incident detection using
crowdsourced data by using emergency response management as a case-study. The
proposed approach CROME (Crowdsourced Multi-objective Event Detection)
quantifies the relationship between the performance metrics of incident
classification (e.g., F1 score) and the requirements of model practitioners
(e.g., 1 km. radius for incident detection). First, we show how crowdsourced
reports, ground-truth historical data, and other relevant determinants such as
traffic and weather can be used together in a Convolutional Neural Network
(CNN) architecture for early detection of emergency incidents. Then, we use a
Pareto optimization-based approach to optimize the output of the CNN in tandem
with practitioner-centric parameters to balance detection accuracy and
spatial-temporal localization. Finally, we demonstrate the applicability of
this approach using crowdsourced data from Waze and traffic accident reports
from Nashville, TN, USA. Our experiments demonstrate that the proposed
approach outperforms existing approaches in incident detection while
simultaneously optimizing the needs for real-world deployment and usability.

###### Index Terms:

Crowdsourcing, Emergency Response, Deep Learning, Waze, Multi-Objective
Optimization

##  I Introduction

Emergency response to incidents like road accidents and natural disasters is
one of the most pressing problems faced by communities today. Cities resort to
diverse responders like firefighters, paramedics, and police personnel to
manage such incidents. Traditionally, emergency response pipelines were
reactive, responding to incidents after they were reported officially.
However, cities have evolved over the last few decades and have adopted smart
emergency response, which acts proactively by allocating responders in
anticipation of future incidents [1]. Mukhopadhyay et al. [1] point out that
recently, incident detection has become an essential addition to the smart
emergency response pipeline. To understand the role of incident detection,
consider a traffic accident on a highway. In such a situation, first
responders dispatch resources only after a call is placed for aid (e.g., a 911
call in the USA). However, this mechanism can result in loss of time, which in
emergencies could prove to be fatal [2]. This delay is also problematic for
low severity incidents, which can lead to traffic congestion on the roads if
not cleared in time. Based on our discussions with the Tennessee Department of
Transportation, these kinds of incidents are often detected by the help trucks
on patrol and manually by personnel in transportation management centers using
cameras. This pipeline results in latency, which can be avoided if observers
passing by incident sites have access to a convenient mechanism for reporting
incidents (e.g., by using a single click of a button on a smartphone
application). Then, crowdsourced reports can be used to detect incidents
before they are reported officially.

Using crowdsourced data for emergency response is highly non-trivial as such
data is noisy and scattered in space and time. This uncertainty makes precise
spatial and temporal localization challenging. While early information about
incidents is critical, it is difficult to dispatch limited resources to
potential incidents based on uncertain information. Consider accident
reporting through the Waze application that allows users to press a smartphone
button to report accidents. Due to the vehicle’s motion and traffic, drivers
and passengers often pass the area of an incident before clicking the button
to report it. As a result, by the time the incident is reported, it typically
consists of both spatial and temporal deviations from the original place and
time of the incident. Therefore, an incident detection model must localize and
detect the incident in the presence of noise and uncertainty.

The goals of accurate detection and improved localization might appear
contradictory. Indeed, it seems intuitive that the accuracy of a data-driven
incident detector would degrade with an increased focus on localization.
However, localization is imperative to respond to an incident; it is not
possible to dispatch aid to an accident unless its precise location is known.
At the same time, lowering the latency of detection is also critical. If we
wait to acquire more information from various sources, the uncertainty
decreases; however, it increases latency. This paper focuses on optimizing the
balance between the goals of accurate detection and localization.

Recently, there has been a growing interest in leveraging crowdsourced data in
various public sector domains such as emergency management and transportation.
Crowdsourced data (such as Twitter, Instagram, Waze, and Foursquare)
represents another source of data that has been used for a variety of analyses
such as emergency disaster response [3] and traffic management [4]. Lenkei [5]
performed a comparative study of the accidents reported through Waze and the
traffic database in Sweden (Trafikverket) and observed that 27.5% of the
incidents in Trafikverket were detected earlier by Waze. Recently, Senarath et
al. [3] proposed a Bayesian information fusion approach which fused multiple
crowdsourced Waze reports for early incident detection.

We note that prior works using crowdsourced data for spatial-temporal incident
detection lack:  1. a principled approach for information fusion noisy data to
detect incidents that can generalize across crowdsourcing platforms because
existing approaches only consider simple aggregation methods of explicit
features without considering impacts of uncertainty associated with report
integration;  2. a systematic investigation of the effect of hyperparameters
(e.g., quality of discretization of a continuous region of interest) on the
quality and accuracy of the event detection models developed from crowdsourced
data; and  3. a flexible incident detection framework that accommodates
practitioner preferences regarding incident detection accuracy and spatial-
temporal localization.

This paper presents CROME: an approach that performs Crowdsourced Multi-
Objective Event Detection. We show how to combine spatial-temporal
crowdsourced data with arbitrary features to facilitate data-driven modeling.
Crucially, we show how to balance the trade-off between localization and
accuracy. We also show that balancing this trade-off is vital and naively
maximizing accuracy (or F-1 score) is not desirable in this problem domain.
Through experiments performed on accident data gathered from Nashville, TN,
USA, we show how our approach can detect accidents sooner than receiving 911
calls and outperforms state-of-the-art approaches.

##  II CROME: Crowdsourced Multi-Objective Event Detection

Consider a set of spatial-temporal incidents $D$; for example, $D$ can denote
a set of historical road accidents that occurred in a region of interest
during a specific period. In practice, it is difficult to know the exact time
of occurrence of such incidents. Instead, we assume that the reported time of
occurrence (for example, through a 911 call) can be used as a proxy for the
actual time of occurrence. Further, we assume access to a set of crowdsourced
reports about the incidents, denoted by $W$. Each report $w_{i}\in W$ can be
represented by the tuple $(t_{i},k_{i},l_{i},r_{i})$ where $t_{i}$, $k_{i}$,
$l_{i}$, and $r_{i}$ denote the time at which the report was generated,
longitude, latitude, and the reliability of report, respectively. The
reliability of a report is typically provided by the crowdsourcing platform
itself. For example, the long-term accuracy of the user who generated the
report can be used as a proxy for reliability.

Spatial Discretization: We divide the overall spatial area of interest into a
grid $G$ with square cells of length $\Delta s$. Each point in space
(represented by a pair of latitude and longitude) can therefore be mapped to a
unique cell in $G$. Upon mapping crowdsourced reports $W$ to $G$, each report
$w_{i}\in W$ is denoted by $(t_{i},x_{i},y_{i},r_{i})$, where $x_{i}$ and
$y_{i}$ represent a specific cell in $G$ containing the spatial coordinates
represented by $k_{i}$ and $l_{i}$.

Temporal Discretization: Crowdsourced reports are generated in continuous
time. However, incidents of interest, e.g., accidents, occur infrequently.
Further, multiple crowdsourced reports are generated in response to the same
incident. As a result, we aggregate crowdsourced reports temporally to aid
analysis. Let $\Delta t$ denote the temporal resolution for data aggregation.
We refer to $\Delta t$ as the step time-period. The input data $W$ can be
grouped in $\Delta t$ time intervals and aggregated to produce a real number
using a specific summary statistic for temporal discretization. For example,
the total number of reports generated in a time period in a cell or the
average reliability of the reports can be used for aggregation.

We also assume access to other potential determinants of incidents, e.g.,
weather and traffic congestion have been shown to be correlated with accident
occurrence [1]. We assume that information about such covariates is available
at the same granularity at which we choose to discretize space and time. We
refer to the covariates used (including the summary statistics of the
crowdsourced reports) as features. For example, features in the case of
accidents can correspond to the number of crowdsourced reports, weather,
congestion, and so on. For each time period (say a time period ending at
$t_{i}$), using a specific aggregation on $W$ produces a multi-dimensional
array (i.e., a tensor) $\chi_{i}$ of dimensions $(N_{x},N_{y},N_{f})$, where
$N_{x}$ and $N_{y}$ denote the number of cells along the horizontal and
vertical directions in $G$, and $N_{f}$ is the number of features. We show the
overall process of discretization in Figure 1. Note that as $\Delta s$
changes, the realizations of $N_{x}$ and $N_{y}$ change as well.

Figure 1: The overall process of data discretization and aggregation. This
diagram represents three time steps ($\Delta t$) aggregated to form
$\mathbb{X}_{i}$ and the corresponding labels ($L_{i}$) at time $t_{i}$.

In practice, once an incident occurs, crowdsourced reports are generated for
some extended duration of time after the incident. Consider an accident for
example; as people pass through the scene of the incident, they observe it and
log the presence of the accident on a relevant crowdsourcing platform. The
reporting can continue till the scene of the accident is responded to by first
responders and cleared. In order to accumulate reports generated over time, we
use $\mathbb{X}_{i}$ to denote $(\chi_{i-T^{\prime}}\dots\chi_{i})$, where
$T^{\prime}$ is an arbitrary period that practitioners can choose based on the
frequency of the reports, the number of incidents, and so on. Therefore,
$\mathbb{X}_{i}$ is a collection of tensors that provides a temporal snapshot
of reports generated from $t_{i}-T^{\prime}$ to $t_{i}$.

Label Assignment: Our goal is to detect incidents based on crowdsourced
reports and other potential determinants. While such a problem can be framed
as unsupervised anomaly detection, historical reports generated through
crowdsourcing platforms and ground-truth data about past incidents can be used
to create a labeled dataset that can be used for supervised learning. Ground
truth information about accidents can be obtained through historical records;
for example, information about accidents can be retrieved through first
responders or traffic/safety organizations. Based on such data, we assign a
label to each $\mathbb{X}_{i}$ generated by accumulating crowdsourced reports.
Intuitively, we say that a set of crowdsourced reports $\mathbb{X}_{i}$ match
with an actual incident (observed through ground truth historical data) if
there was an actual accident in proximity of the set, for some definition of
spatial-temporal proximity.

We define proximity using two temporal hyper-parameters $\alpha$ and $\beta$
and a spatial hyper-parameter $\delta$. Each $\mathbb{X}_{i}$ (recall that
$\mathbb{X}_{i}$ denotes a set of reports accumulated until time $t_{i}$) is
assigned a positive label (marked as 1) if there was an actual incident in the
time frame $t_{i}-\alpha$ to $t_{i}+\beta$ within a spatial proximity of
$\delta$. It is reported a negative label (marked as 0) otherwise. On a
cursory glance, it might seem non-intuitive to assign a crowdsourced report
with an actual incident that might have occurred after it; although
$\mathbb{X}_{i}$ consists of a set of reports obtained until time $t_{i}$ but
duration $t+\beta$ might consist of incidents that occurred after it. However,
our preliminary analysis revealed that in practice, it is not possible to
retrieve the true time of occurrence of incidents. For example, consider
traffic accidents. Once an accident occurs, some time elapses before the
victim (or an observer) calls for help and officially reports an estimated
time of occurrence. Crowdsourced reports, on the other hand, can be generated
as soon as the accident occurs, thereby precluding the officially reported
time of occurrence of the accident. Therefore, we use the hyper-parameter
$\beta$ to accommodate such scenarios.

###  II-A Problem Formalization

Given an aggregation of crowdsourced reports and other relevant features, our
goals are the following: 1) early detection of the locations of spatial-
temporal incidents like accidents through crowdsourced reports, and 2)
determine the best practitioner’s parameters regarding localization that can
be used for deployment. It is crucial to optimize parameters from the
perspective of first responders and practitioners since the optimal model
(based on some definition of optimality as defined in the context of data-
driven learning, like maximum likelihood) might not be the best choice for
deployment. For example, consider a model that detects accidents early in a
city accurately most of the time, but does poorly on spatial localization.
First responders would not be able to service the incident even if they are
provided with an alert. Similarly, consider a pipeline that detects accidents
accurately at the temporal resolution of a day; even if the pipeline shows
accurate spatial localization, it does not aid emergency response because of
the temporal delay it might incur. Below, we show how we formulate our
objective in terms of learning performance (accuracy or some measure of it) as
well as practitioner-centric parameters.

Let the random variable $I$ denote incident occurrence that the decision-maker
is unaware of ($I$ would denote the labels we generated for each
$\mathbb{X}$). It is important to note that such incidents have already
occurred but have not been reported when we make inferences about them; as
such, the problem we are interested in is not a canonical forecasting problem.
Our goal is to learn a function $f(I\mid\mathbb{X},\theta)$, where $f$ denotes
some measure of accuracy of detecting incidents $I$ conditional on features
$\mathbb{X}$ and a set of parameters $\theta$. For example, $f$ could
represent the F-1 score of the model or its detection accuracy. In order to
balance the accuracy of detection with the temporal and spatial granularity
that the model uses, we choose to maximize the accuracy of the model while
simultaneously aiming for higher spatial and temporal resolutions for
detection. Naturally, any approach to detection is difficult at finer spatial
and temporal resolutions. Formally, we define practitioner-centric incident
detection as the following multi-objective optimization problem:

$\displaystyle\max_{\theta}\gamma_{1}f(I\mid\mathbb{X},\theta)+\min_{\Delta
t}\gamma_{2}z_{1}(\Delta t)+\min_{\Delta s}\gamma_{3}z_{2}(\Delta s)$ (1)

where $\gamma_{1},\gamma_{2},$ and $\gamma_{3}$ denote the relative importance
of each term in the optimization problem. In the simplest case,
$\gamma_{1}=\gamma_{2}=\gamma_{3}=1$. The functions $z_{1}$ and $z_{2}$ denote
arbitrary (increasing) functions that practitioners can choose over spatial
and temporal discretization. In the simplest case (the one we use later in our
approach), $z_{1}$ and $z_{2}$ denote identity functions. While our problem
structure is general for any type of spatial-temporal incident and
crowdsourced report, we use road accidents as a case study. We use
crowdsourced reports from Waze that facilitates users to upload observed
accident locations.

(a) Performance of models for different $\Delta s$.

(b) Performance of models for different $\Delta t$.

Figure 2: Performance of models against different spatial and temporal
resolutions using the test data sets. We observe that the CNN model (part of
CROME) significantly outperforms the baseline approaches.

###  II-B Solution Approach

####  II-B1 Optimizing Detection Capability

Our goal is to solve optimization problem LABEL:eqn:optimization. We begin by
describing the function $f$. An approach to detecting incidents must be able
to balance between the precision and the recall of detection. First responders
typically work under resource constraints; while early detection is imperative
to minimizing response times, responders cannot be dispatched to attend to
falsely generated alerts. As a result, we choose to use F-1 score as our
metric of interest, which is the harmonic mean of precision and recall. Given
our choice of $f$, we now focus on the first term in Formula
LABEL:eqn:optimization, which seeks to find the parameters $\theta^{*}$ such
that $\theta^{*}=\text{argmax}_{\theta}f(I\mid\mathbb{X},\theta)$.

We leverage the structure of the incident detection problem while choosing a
model that can draw inferences from spatial-temporal crowdsourced data.
Intuitively, we try to capture the proximity of observation and reporting in
this domain. After users observe an incident, they move in space and a certain
amount of time elapses before they report it. However, it is natural to assume
that the displacement (both spatial and temporal) is not very high; it is
unlikely that users move many miles and report an incident hours after they
observe it. Therefore, reports generated in a cell (say $g_{i}\in G$) are most
likely to have been observed in cells that lie in close proximity to $g_{i}$.
In principle, it is possible to flatten $\mathbb{X}$ to a vector and minimize
some loss function (e.g., least square loss) that measures prediction
accuracy. However, to leverage the spatial structure of the problem, we use a
convolutional neural network (CNN) [6] to maximize $f$. We implement two
convolutional layer neural network with a max-pooling layer in between. The
last convolutional layer is followed by a ReLU activated layer and a sigmoid
layer. The CNN architecture enables us to consider how alerts generated in a
cell are correlated with incidents that occur in its spatial proximity.

####  II-B2 Optimizing Practitioner Parameters

Our goal is to maximize the accuracy of detection while also improving spatial
and temporal localization. The very structure of our formulation dictates that
no single solution can optimize all the objectives simultaneously. Indeed, we
show through experimental evaluation that as the spatial resolution increases,
the accuracy of the model degrades. As a result, we seek to find the set of
Pareto-optimal solutions. A solution is called Pareto-optimal or non-dominated
if none of the objective functions can be improved without sacrificing the
value of at least one of the other objective functions [7]. To find the Pareto
optimal solution, we use a multi-objective evolutionary algorithm [7] based on
the concept of $\epsilon$-dominance [8]. The idea of $\epsilon$-dominance
maintains a well distributed set of non-dominated solutions by not allowing
two solutions with a difference less than an exogenously specified threshold
($\epsilon_{i}$ in the $i$th objective) to be non-dominated to each other. We
refer readers to work by Deb et al. [7] for a detailed description of multi-
objective optimization.

####  II-B3 Feature Generation

We collect a set of crowdsourced reports about roadway accidents through the
Waze application. We remove duplicate reports that had the same identifier
(ID). Then, we generate input-output pairs $\\{\mathbb{X},I\\}$ based on the
spatial discretization, temporal discretization, report aggregation, and label
assignment as described in section II-A. We use three major categories of
features for incident detection – crowdsourced reports, traffic information,
and weather. Our choice is guided by prior work in the domain of accident
prevention and analysis [1]. To capture the volume as well as the reliability
of the crowdsourced reports, we generate the following three features: 1)
Volume: the total number of crowdsourced reports, 2) Sum of Reliability: the
sum of the reliability scores of the crowdsourced reports, and 3) Mean of
Reliability: the average reliability score of the crowdsourced reports. We
gather reliability scores for the reports from the crowdsourcing platform
(Waze) itself.

We generate two additional features from traffic and weather information. For
a point in space and time (based on the spatial-temporal discretization), we
gather the amount of precipitation from the nearest weather station. We also
calculate the mean traffic congestion in a cell through a two-step process.
First, for each roadway segment in a cell, we calculate congestion by
computing the ratio of the difference between free flow speed and the current
speed to free flow speed. Then, we average the value of congestion across all
the roadway segments within the cell.

##  III Data

We use the following data sources for learning the incident detection model:
1. Crowdsourced data: Waze is a GPS navigation application and crowdsourcing
platform [9]. We look at user reports concerning roadway accidents from
Sep/01/2019 to Dec/31/2009;  2. Ground-Truth Incident Data: we collect
accident data from the public safety office of Nashville, USA, with a size of
about 500 sq. miles We consider such incidents as the ground truth. To remove
noise, we map each incident to its closest roadway segment (typically at a
distance of less than 25m);  3. Traffic Data: we collect roadway traffic data
in a time resolution of 5-minute intervals for the area under consideration,
resulting in approximately 270 million measurements; and  4. Weather Data: we
collect weather information from Weatherbit [10].

##  IV Experimental Evaluation

###  IV-A Setup, Baseline, and Implementation

As indicated in Section III, we collect crowdsourced data from the Waze
platform for the period between Sep/01/2019 to Dec/31/2019. We divide the data
between training sets of three months and a test set of one month in a manner
that each month is used as the test set in an independent evaluation. Hyper-
parameters of the CNN (number of epochs and threshold for classification) are
tuned through $k$-fold cross-validation. We use 256 filters with filter size
of $2\times 2$ for both convolutional layers. Moreover, max pooling size is
set to $2\times 2$. Last two dense layers contain $2\times N_{o}$ and $N_{o}$
units accordingly. Moreover, we set $\alpha$ and $\beta$ equal to 1 hour and
$T^{\prime}$ equal to 30 minutes based on empirical analysis. To compare the
performance of CROME, we use our earlier implementation using Bayesian
Information Fusion (BF) shown in [3]. Our implementation for CROME as well as
the baseline approach is available at https://github.com/ysenarath/CROME.

###  IV-B Evaluation Measures

In order to evaluate the performance of the proposed approach, we use four
metrics chosen based on the priorities of first responders and practitioners.
Specifically, we evaluate using F-1 score (harmonic mean of precision and
recall), average early prediction ratio (the ratio of correctly early-
predicted incidents to total incidents reported), average early prediction
distance (the geodesic distance between the detected location of the incident
and the actual location), and the average early prediction time (the average
time difference between the actual reported time of the incident obtained
through ground-truth report and the time of detection).

TABLE I: Early detection performance of models. The F1 score is evaluated on
the test set.

Model |  $\Delta$s (km) |  $\Delta$t (min) | F1 Score | Early Pred % | Avg Distance (km) |  | Avg. Early
---
Time (min)
Precision | Recall
Best Early Pred %
BF | 1 | 5 | 0.60 | 77.56 | 3.27 | 15.02 | 0.00 | 0.14
CROME | 5 | 5 | 41.00 | 40.28 | 2.96 | 13.94 | 0.32 | 0.56
Best Avg. Distance
BF | 5 | 5 | 10.56 | 35.00 | 3.16 | 15.02 | 0.06 | 0.33
CROME | 1 | 5 | 16.41 | 18.35 | 2.67 | 14.32 | 0.16 | 0.18
Best Avg. Early Time
BF | 3 | 20 | 6.49 | 47.69 | 3.25 | 15.45 | 0.04 | 0.40
CROME | 3 | 30 | 30.40 | 24.67 | 3.03 | 14.92 | 0.23 | 0.45

###  IV-C Results

####  IV-C1 Detection Accuracy

We begin by comparing the detection accuracy of the CNN model (the first
component of CROME) with respect to the baseline approaches. We vary the
spatial and temporal resolutions ($\Delta s$ and $\Delta t$) for this
comparison and present the results without using the Pareto optimization
framework (we present complete results later). Our purpose of doing so is two-
fold. We seek to examine the robustness of the models with respect to varying
discretization parameters and also validate our hypothesis that detection
accuracy can suffer as spatial and temporal resolutions increase. We present
the results in Figure 2(a) and Figure 2(b) that show the influence of time and
space resolution on F1 score. We have the following major findings: 1) CROME
significantly outperforms the baseline models in terms of F-1 score in all
cases. 2) As the spatial resolution increases and localization becomes more
challenging, the F-1 score of all the models decrease. 3) Surprisingly,
temporal discretization does not affect the performance of any of the models
(barring minor variations). We hypothesize that this is due to the effects of
aggregating features over multiple time steps ($T^{\prime}$).

Figure 3: We show the non-dominated set of solutions obtained through CROME
(in red triangles). The learned CNN models are shown in blue squares. We also
show the baseline models (in gray circles).

####  IV-C2 Choosing the Pareto Frontier

Having shown that the CNN model we propose as part of CROME outperforms the
baseline approaches (in terms of F-1 score), we now focus on evaluating CROME
in its entirety. Recall that our goal is to simultaneously aid detection and
localization by solving optimization problem LABEL:eqn:optimization. We first
show how calculating the Pareto frontier helps us solve optimization problem
LABEL:eqn:optimization (see Figure 3). The plot shows the three dimensions
over which CROME optimizes, namely the spatial resolution ($\Delta s$), the
temporal resolution ($\Delta t$), and the F-1 score. Each point in the three-
dimensional plot represents a specific learned model. We show the non-
dominated set in red triangles. Notice that the non-dominated set consists of
several learned models. We leave the final choice of selecting one (or more)
models for deployment from the non-dominated set to the practitioners based on
the relative importance of the specific objective functions ($f,\Delta s,$ and
$\Delta t$).

Our key findings are as follows: 1) While BF outperforms CROME in terms of
early detection, $85\%$ of the alerts that it generates are incorrect (false
positives). Using such an approach is infeasible in practice as responders
cannot be dispatched based on incorrect alerts. CROME on the other hand,
balances precision and recall to detect more than $40\%$ of the incidents
early. 2) CROME performs nearly on-par with the baseline approach in terms of
localization. 3) We find that while tailoring models to specifically maximize
precision or recall can maximize certain metrics associated with incident
detection, the lack of consideration of practitioner-specific parameters can
lead to detrimental consequences. We note the need to consider a combination
of F-1 score and the metrics pertaining to detection and localization.
Consider a model that generates alerts at all time-steps on all cells. Such a
model would detect all possible incidents early with remarkable localization
(since localization is measured with respect to the ground-truth incidents).
As a result, the balance of precision and recall is crucial in this setting.
Table I shows the results of our experiments. We have selected the best model
of each approach (BF, CROME) with respect to three practitioner-centric
metrics. The model is considered better if there is a higher early prediction
rate, higher avg. early prediction time, or lower avg. distance. Based on
Table I, we conclude that the proposed approach, which seeks to include
practitioner-centric parameters in incident detection, results in a
significantly higher F-1 score, significantly lower number of false alerts,
and competitive spatio-temporal localization.

##  V Conclusion

This paper proposes a novel multi-objective optimization problem for early
detection of spatial-temporal incidents using crowdsourced data. We show how
crowdsourced data, historical ground-truth incident data, and relevant
determinants can be combined to detect potential incidents before they are
reported. We also show how practitioner-centric parameters can be incorporated
into our approach. The proposed approach, CROME (Crowdsourced Multi-objective
event detection), uses a combination of convolutional neural networks and
Pareto optimization to solve the optimization problem. While crowdsourced data
is often noisy and uncertain, we show that mining such non-traditional data
can benefit emergency incident response through a principled modeling approach
like CROME.

Acknowledgement. This project was supported by resources provided by the
Office of Research Computing at George Mason University and funded in part by
the National Science Foundation grants (1814958, 1815459, 1625039, 2018631)
and a grant from Tennessee Department of Transportation.

## References

  * [1] A. Mukhopadhyay, G. Pettet, S. Vazirizade, Y. Vorobeychik, M. Kochenderfer, and A. Dubey, “A review of emergency incident prediction, resource allocation and dispatch models,” _arXiv preprint arXiv:2006.04200_ , 2020.
  * [2] H. Jaldell, “How important is the time factor? saving lives using fire and rescue services,” _Fire Technology_ , vol. 53, no. 2, pp. 695–708, 2017\.
  * [3] Y. Senarath, S. Nannapaneni, H. Purohit, and A. Dubey, “Emergency incident detection from crowdsourced waze data using bayesian information fusion,” in _IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology_ , 2020, pp. 187–194.
  * [4] M. Amin-Naseri, P. Chakraborty, A. Sharma, S. B. Gilbert, and M. Hong, “Evaluating the reliability, coverage, and added value of crowdsourced traffic incident reports from waze,” _Transportation Research Record_ , vol. 2672, no. 43, pp. 34–43, 2018.
  * [5] Z. Lenkei, “Crowdsourced traffic information in traffic management: Evaluation of traffic information from waze,” Master’s thesis, KTH, Transport Planning, Economics and Engineering, 2018.
  * [6] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_. MIT press Cambridge, 2016.
  * [7] K. Deb, M. Mohan, and S. Mishra, “Evaluating the $\varepsilon$-domination based multi-objective evolutionary algorithm for a quick computation of pareto-optimal solutions,” _Evolutionary Computation_ , vol. 13, no. 4, pp. 501–525, 2005.
  * [8] M. Laumanns, L. Thiele, K. Deb, and E. Zitzler, “Combining convergence and diversity in evolutionary multiobjective optimization,” _Evolutionary computation_ , vol. 10, no. 3, pp. 263–282, 2002.
  * [9] Waze, “Driving directions, traffic reports & carpool rideshares by waze,” 2021. [Online]. Available: https://www.waze.com/
  * [10] Weatherbit, “Weatherbit – Historical Weather API,” 2021. [Online]. Available: https://www.weatherbit.io/


# Communication Optimization in Large Scale Federated Learning using
Autoencoder Compressed Weight Updates

Srikanth Chandar1,2 Pravin Chandran1 Raghavendra Bhat1&Avinash Chakravarthi1
1Intel Corporation, Bangalore
2PES University, Bangalore<EMAIL_ADDRESS>{pravin.chandran,
raghavendra.bhat<EMAIL_ADDRESS>
###### Abstract

Federated Learning (FL) solves many of this decade’s concerns regarding data
privacy and computation challenges. FL ensures no data leaves its source as
the model is trained at where the data resides. However, FL comes with its own
set of challenges. The communication of model weight updates in this
distributed environment comes with significant network bandwidth costs. In
this context, we propose a mechanism of compressing the weight updates using
Autoencoders (AE), which learn the data features of the weight updates and
subsequently perform compression. The encoder is set up on each of the nodes
where the training is performed while the decoder is set up on the node where
the weights are aggregated. This setup achieves compression through the
encoder and recreates the weights at the end of every communication round
using the decoder. This paper shows that the dynamic and orthogonal AE based
weight compression technique could serve as an advantageous alternative (or an
add-on) in a large scale FL, as it not only achieves compression ratios
ranging from 500x to 1720x and beyond, but can also be modified based on the
accuracy requirements, computational capacity, and other requirements of the
given FL setup.

##  1 Introduction

Federated Learning has been proposed as a new learning paradigm to overcome
the privacy regulations and communication overheads associated with central
training McMahan et al. (2017),Li et al. (2020). In this paper, for sake of
clarity, we assume an FL scheme where a central server (called Aggregator)
shares a global model with participating edge devices (called Collaborator),
and the model is trained on the local datasets available at the edge device.
The local dataset is never shared with the central server, instead, local
updates to the global model are shared with the central server. The central
server combines the local updates from the participating clients using an
Optimization or Aggregation Algorithm (FedAvg McMahan et al. (2017), FedProx
Li et al. (2018), FedMa Wang et al. (2020), FedMAXChen et al. (2020)) and
creates a new version of the global model. This process is repeated for the
required number of communication rounds until the desired convergence criteria
are achieved. The chosen scheme does not limit the technique from being
deployed in any alternative FL scheme.

In the proposed FL setup, an AE compresses the weight updates from each
collaborator at every communication round to reduce the communication
bandwidth and recreates the weights after communication during the aggregation
stage at the Aggregator. It is well understood that the weight updates are
non-isolated events and there is some relation and interlinking between the
parameters of the weight updates. A neural network such as an AE can find such
patterns hidden in the data and reduce the representation to a lower-
dimensional feature size (compression).

Figure 1: Autoencoder (Encoder and Decoder) Model

This paper investigates and shows that an AE can exploit this fact of
dependence between parameters in a weight update, and thus learn the encoding
of the weight update, and replicate it in a ”learnable” manner. An AE model
has a funnel structure where the hidden layers have neurons lesser in number
compared to the input and output layers. The idea is that the network is
trained to replicate the inputs, at the output level, by having certain
intermediate lower-dimensional representations in the hidden layers. This
”encoded” weight update, being smaller in size, is then communicated to the
server- thus reducing the communication overheads.

##  2 Past Work

Communication efficient FL has gained considerable attention over the past few
years, and several approaches towards compressing the collaborator-to-server
and server-to-collaborator model updates have been proposed. Traditional
methods like sub-sampling, and quantization as implemented in Reisizadeh et
al. (2020) compress the model update by the process of mapping weight
parameter values to a smaller set of discrete finite values. Communication
overheads can further be reduced by a certain more sophisticated quantization
approach by combining the universal vector quantization, following a similar
fundamental principle Shlezinger et al. (2020). Sub-sampling and Quantization
are simplified methods that do not capture the inherent nonlinearities in the
model while performing a compression but rather performs an approximation to
reduce the size of the weights being communicated. Pruning reduces the model
size by modifying architecture. Not all weights in a model are considered
important, and an importance metric is defined for each of the weights. This
metric is decided based on how each of these parameters causes the loss
function to change when faced with a gradient. Unimportant weights are assumed
a weight equal to zero, implying they can be removed from the network, finally
resulting in a smaller network.

Federated Dropout Caldas et al. (2018) proposes a compression scheme derived
from dropout regularization, where a fixed number of activations are dropped
at each connected layer. This ensures local updates have reduced architecture
and thus reduces communication bandwidth. DGC (sparsification)Lin et al.
(2017) only communicates the weights above the set threshold, and the others
are accumulated locally on the device till it reaches the threshold value, and
is only then communicated. The reasoning being 99% of the update are redundant
since they get altered during future communication rounds. CMFL Luping et al.
(2019) introduces an orthogonal compression method making use of the global
model update tendency. The weights of the local updates that do not align with
this tendency are not communicated, as they are deemed to have low importance
since they would get corrected as the communication rounds proceeds. STC
Sattler et al. (2019) is similar to DGC, and includes compression for server-
to-client communication, through the modification of the update rule to
include client-side and server-side updates. FetchSGD Rothchild et al. (2020)
uses sketching and streaming to compress weight updates by summarizing them
through a linear sketching algorithm (Count Sketch), using the accumulator and
momentum variables from update equations stored on the server, instead of
locally. Fedboost Hamer et al. (2020) treats the FL weight update compression
problem as an ensemble-based training optimization problem, by considering
each of the collaborators as a member of the ensemble and aggregating the
inferences instead of weights. The drawback is that it is applicable for
density estimations only, and does not solve the weight update compression in
itself. Similarly, Fedzip Malekijoo et al. (2021) proposes a quantization
approach using K-Means-Clustering, aided with sparsification and encoding, to
compress the weight updates. Quantization through clustering provides a better
reflection of tensor distribution, compared to other methods where a fixed set
is selected.

In Knowledge Distillation Hinton et al. (2015) the collaborator model is
translated to a smaller model that replicates the original model behavior to a
satisfactory level of accuracy, and the communication of weight updates during
each communication round is thus of a smaller size Seo et al. (2020). The
drawback of this approach is that the smaller model may not provide the entire
information encapsulated in the collaborator model. Even with stronger teacher
models Lan et al. (2018), there is a hesitation in commercially adopting this
approach, as there could be sub-optimal distillation if the student model is
too small and is over-fitting. There is also a cap on the amount of
compression that may be achieved, as the process is dependent on recreating
the collaborator model. Deriving from the idea of compressing the collaborator
model weights, this paper proposes an architecture that builds a model that
recreates the weight updates at each communication round via compression
through an autoencoder, instead of recreating the collaborator model itself.
While the AE model may be bigger than than the student model, the compression
achieved through the AE would be significantly higher as it learns the
patterns between the parameters of the weight updates, rather than between the
input and output of the collaborator model (which ideally necessitates a model
to be as big as the collaborator model, and hinders a wide range of
compression). AEs have been used in the image compression domain Zebang and
Sei-ichiro (2019). In the context of compressing another neural network using
an AE, there is limited investigation. The closest research along these lines
is the ALF Frickenstein et al. (2020) approach, proposed for the embedded
system track. Here, an AE is used to compress the weights at the end of every
convolutional layer, to save memory usage while storing intermediate weights
on the hardware. Whereas in the AE-based compression proposed in this paper,
the compression occurs for all layer weights (convolutional or not) and is for
the entire model. This provides the advantage of allowing the AE to learn the
dependencies of the parameters across layers, and perform compression
accordingly. This proposed method is suggested as a more dynamic approach
serving as an advantageous add-on for communication efficient federated
learning, by also considering the various trade-offs.

##  3 Architecture

Figure 2: Prepass Round

The compression scheme proposed in this paper works in a manner where an AE
neural network is trained to recreate the weight updates via an intermediate
compressed state. To train the AE to compress a model, the weights data at the
end of every batch/epoch of the training model (to be compressed) is required,
as the AE learns the encodings from such a dataset. This implies that in the
FL setup, a pre-pass round is required to generate the dataset containing
weights associated with periodic learning. This is achieved as such - The
server initiates the learning process on all collaborators by communicating a
global model. Each collaborator trains this particular model using the local
data available on the device. At this stage, the learning process happens
without aggregation of weights or Federation. While the collaborators’ models
are being trained locally on-device data, the intermediate weights (at the end
of every batch/epoch) are stored to form the weights dataset. The weights
dataset generated at every collaborator is used to train an AE at the
collaborator, in such a way that the AE can reproduce the weights, and also
compress them through its intermediate smaller dimensional layer. The decoder
part of the AE is communicated to the server, which also concludes the pre-
pass round. Beyond this stage, the FL is initiated by the server using a
global model. This time each collaborator starts training on the local data,
but with aggregation and federation at every communication round. The weight
updates from the collaborator to the server are compressed using the encoder
on the collaborator and reconstructed using the decoder on the server. The
compression ratio achieved per communication round, per collaborator is around
1500x, and this factor can be modified based on the AE structure. The encoding
network can be represented by the standard neural network function passed
through an activation function, where z is the latent dimension.

$\small z=\sigma(Wx+b)$ (1)

Similarly, the decoding network:

$\small x^{\prime}=\sigma^{\prime}(W^{\prime}z+b^{\prime})$ (2)

The loss function in terms of these network functions used to train the neural
network through the standard backpropagation procedure is:

$\small\mathcal{L}(x,x^{\prime})=\|x-x^{\prime}\|^{2}=\|x-\sigma^{\prime}(W^{\prime}\sigma(Wx+b)+b^{\prime})\|^{2}$
(3)

Figure 3: FL with AE compression

##  4 Detailed Methodology

###  4.1 Experimental setup

To test the AE-based weight compression on the weight updates of a training,
analyses are performed on image classifier model weights by compressing the
weights at the end of every epoch (analogous to communication round). The
collaborator model (image classifier) is allowed to completely train, and the
weights at regular intervals are stored in a dataset. This dataset is used to
train the AE. The Fully Connected (FC) AE construct has dense layers and the
input and output layer size is equal to the total number of parameters in the
classifier model (or each weight update). The layers’ size/shape of the AE is
such that it follows the funnel structure represented in Fig. 1, decreasing as
layers progress away from the encoder, reaching a minimum, and then
subsequently increasing till the end of the decoder. This symmetric AE is then
allowed to train on the classifier weights dataset generated earlier.
First, a fully connected AE approach is considered and the methodology is
explained using the MNIST classifier as the collaborator model. The classifier
model is comparatively simple with 15,910 parameters, and the convergence is
reached in 10 epochs. To train an AE to replicate a model’s weights, it is
required to have a wide spectrum of data points in terms of weights at
different instances of training, that can define the model uniquely to a good
degree.
To simulate a more complex scenario, the next stage of analysis has a more
complex classifier model, to generate a better and more widespread dataset in
terms of weights. The CIFAR-10 classifier model has 550,570 parameters, and
the convergence is reached in around 100 epochs. The weights being stored in
the dataset, cannot be directly passed as inputs to the AE, given that it’s of
an unflattened structure. Since the flattening process of this dataset which
has each element of size 550,570 is computationally challenging, the number of
epochs is restricted to 40. This is done to put a cap on the dataset size,
bearing in mind that a significant accuracy has been reached by this stage.

###  4.2 Dynamic AE architecture

The size of the AE is dependent on the size of the model whose weight updates
are to be compressed. The first layer of the AE, by it having the weight
updates from the collaborator model as inputs, has an input shape that matches
the parameter size list (flattened single dimensional copy of the weights of
the collaborator model). Unlike traditional compression algorithms, the
compression methodology is dependent on the compressing item which is the
collaborator model here. The complexity of the AE is also a feature that can
be set according to the user needs, and infrastructure dependencies. Other
than the first and last layer of the AE which has a size equal to that of the
number of parameters in the collaborator model, the layer architecture can be
varied to control the AE model complexity. By increasing the complexity, the
AE mimics the learning of the collaborator model better. However, to reduce
computational overheads, if accuracy can be compromised, then the complexity
of the model can be reduced to meet the exact design requirements in terms of
computation power usage vs accuracy trade-off for the given FL scenario.
The compression ratio in AE-based compression is not pre-defined. The general
observation is that as the compression ratio increases, more information loss
exists during the recreation phase through the decoder end at the aggregator,
and thus causes a dip in accuracy. This is because AE-based compression is
inherently a lossy-compression technique that tries to encode the inputs into
a smaller feature space by extracting certain relations between the parameters
of the weight updates. Lossy compression is acceptable in the FL setup,
because there is finally an aggregation of the weights, thus allowing for some
room for difference in predictions and actual weights. Thus, this approach can
be tailored to suit the needs of the particular FL scenario.
In many cases, the server requires an approximation of the weight updates from
the collaborator, to propose the next set of weights for each collaborator.
This is due to the aggregation process that ensures all weights are averaged
together using different techniques. In such scenarios, a less complex AE
could be used to save computational overheads of training the network on
collaborator devices. The compression ratio could also be higher, if the
accuracy obtained post lossy compression (and information loss), is sufficient
for the aggregator function to suggest an appropriate update from aggregator
to collaborator, for the next communication round. Alternatively, if higher
accuracy is required for a particular FL set-up, a more complex AE is used to
learn the relations between parameters of the weight updates better. The
compression ratio may also be reduced to ensure lesser information is lost
through the lossy compression done using AE. In addition, AE-based compression
is an orthogonal approach and can be applied in combination with certain other
traditional compression methods mentioned under the past work section.

###  4.3 Fully Connected AE limitation and proposing Convolutional AE as an
alternative

The drawback of a fully connected AE-based compression is that the AE network
is a large model, with the number of parameters being a few hundred times
bigger than the size of the original collaborator model in many cases. This
comes with a computational overhead while training this network, and also a
communication overhead while passing the decoder (half the size of the AE) at
the end of the pre-pass round in FL. To achieve useful results of compression,
the communication savings achieved by the AE compression ratio must be higher
than the cost of communicating this decoder model at the end of the pre-pass
round. This is possible if the number of collaborators and the number of
communication rounds in the FL setup increase, as it would account for more
communication overheads savings through AE compression. (Discussed in detail
in subsequent sections.)
An alternative approach is using a convolutional AE that will be significantly
smaller in size when compared to an FC AE. The underlying logic behind the
usage of convolutional AE is that weights across various layers are analogous
to the pixel values in images. The dependency between parameters that the AE
learns may be more evident between weights of layers that are closer to each
other as compared to the dependency between weights of layers that are much
further apart in the neural network. In this sense, a convolutional AE fits
the context of compression better, as a convolutional network can learn the
local (neighborhood) dependence better. A preliminary setup has been suggested
for the same [Appendix]. The authors include this here to probe further
research on convolutional AE with deeper networks or ones that implement
residual networks, etc.

##  5 Results and Analyses

###  5.1 Fully connected AE

To analyze the performance of AE compression, beyond just its training
metrics, a validation model is built as follows: once the AE has been trained,
the weights logged at the end of every epoch from the original collaborator
training are used to perform the validation. The trained AE is used to
compress and predict (recreate) these weights. These AE predicted weights are
then set as weights to another model following the same architecture as the
collaborator model, and the loss and accuracy are computed by allowing the
network to train for an epoch by ensuring the weights are fixed (trainable is
set to false). The idea of this validation model is to show that the loss and
accuracy values generated by setting the AE predicted weights to the
collaborator model, are similar to the loss and accuracy values generated
during the original training of the collaborator model. This would show that
the AE has successfully learned the encoding of the collaborator model
weights, performs compression, and recreates a set of weights that is similar
to the original weights- which is seen through the fact that the loss and
accuracy plots generated are similar.

####  5.1.1 AE compression on MNIST Classifier

Fig. 4 shows the accuracy plot of the FC AE during training and as the loss
converges. The FC AE can train accurately, as is seen with a maximum value of
0.78 in the accuracy metric (validation accuracy= 0.94). These results show
that an AE (with 1,034,182 parameters) can compress and recreate the weight
updates for a relatively simpler model such as an MNIST classifier. The
results of the validation model (as proposed in the previous section) are
shown next. As seen in Fig. 5, it is evident that the AE model can mimic the
accuracy (and loss) plot of the original classifier training through the
predicted (post-compression) weights. By the AE compression, the size of each
update is reduced to a 32 feature encoding, and thus achieves about 500x
compression. The reduced feature space size is a variable and can be modified
to achieve varying levels of compression and accuracy.

Figure 4: AE accuracy plot for MNIST classifier model compression

Figure 5: Accuracy variation when - MNIST model is set Original vs AE
Predicted weights

####  5.1.2 AE compression on CIFAR Classifier

The next analysis is on a more complex collaborator model. The CIFAR-10
classifier model is more complex and serves as the proof of concept for the
AE-based compression method. This model also has significantly more parameters
(352,915,690) and more layers. The weights in the dataset have a higher
variance and suit better for AE training as is seen in Fig. 6. The AE learns
the encodings and mimics the inputs successfully as is seen through the
accuracy plot. The highest accuracy reached is around 0.79 (validation
accuracy= 0.83) and the loss converges after around 25 epochs. The results of
the validation model also show that the loss and accuracy metrics are similar-
when a CIFAR classified model has been set with the original weights, and with
the AE predicted weights. This shows that while the AE compression is lossy,
it doesn’t affect/change the weights recreation at the server end to an extent
where the corresponding accuracy (and loss) changes drastically. This shows
that the AE is replicating the learning properties of the original
collaborator training Fig.7. The predicted accuracy is higher (even for MNIST)
due to finetuning during prepass AE construction. Increasing the threshold
between collected weights during prepass can reduce this.

Figure 6: AE accuracy for CIFAR classifier model compression

Figure 7: Accuracy variation when - CIFAR model is set Original vs AE
Predicted weights

###  5.2 Testing the Fully-Connected AE compression in an FL setup

Overfitting decreases however with an increase in AE model complexity, or with
a more complex model showing a greater gradient of weights through training.
Overfitting as such does not pose a threat as it does in traditional ML, as
the important task here is to finally compress and recreate the weights.
However, in some cases, the weight updates from the collaborator that have
been based on the previous round aggregations may vary significantly causing
the AE to perform poorly. Here the dynamic AE model is to be modified
accordingly, to increase complexity or reduce the compression ratio, to ensure
the AE model is recreating the weights accurately. To validate this, a two-
collaborator FL setup with color imbalances has been built, and the AE
compression has been implemented. One collaborator is a CIFAR-10 classifier
model on color images, while the other is on grayscale images (Colour
Imbalance in datasets for each collaborator). There are 40 communication
rounds, and each round has a local training running for 5 epochs. At the end
of every communication round, the converged weights from both the
collaborators are passed through their respective AE (compressed -
communicated - recreated). A simple averaging-based aggregation algorithm is
used to propose the global update for the next communication round. The graphs
below (Fig. 8 and 9) validate this, as is seen in the sawtooth plot for
accuracy (or loss). The dips occur at the start of every communication round
due to aggregation. These results show that the AE compression works for the
proposed FL setup, as both the collaborators train accurately, despite being
compressed by a factor of 1720x at the end of every communication round. (AE
properties similar to previous sections)

Figure 8: Loss for 2 collaborators (colour and grayscale classifier) in FL

Figure 9: Accuracy for 2 collaborators (colour and grayscale classifier) in FL

###  5.3 Dynamic compression- trade-off and break-even point for Fully-
Connected AE

AE-based compression is dynamic as it works managing variables such as
computational capacity, compression ratio, accuracy requirements, and other
such dependencies in the FL setup. The graphs below show the trade-off and the
respective break-even points between the cost of communicating the decoder
model(s) at the end of the pre-pass round and the communication savings
achieved through AE compression. There are 2 conditions shown- a) When one
decoder model suffices for the entire federated learning set-up, and b) where
each collaborator has a decoder model. The savings achieved while assuming the
single decoder condition are dependent on the number of communication rounds
and the number of collaborators. Similarly, the savings achieved in the
multiple decoder approach, is dependent only on the number of communication
rounds, as the number of collaborators is a factor present in both the cost
and the saving. Conditions (a) and (b) are extreme cases, and there may be a
scenario where a particular FL setup may require few decoders (less than the
number of collaborators). For each of these cases, the AE model has
352,915,690 parameters and achieves nearly 1720x compression. The Savings
Ratio, in general, is calculated according to this equation:

$\small SR=\frac{OriginalSize\times CommRounds\times
Collabs}{CompressedSize\times CommRounds\times Collabs+Cost}$ (4)

where- Original Size is the actual model size, Compressed Size is the
compressed model size, Comm Rounds are the number of communication rounds,
Collabs are the number of collaborators, and Cost is the Decoder overheads

$\small Cost=DecoderSize\times No.ofDecoders$ (5) $\small
Cost=\frac{AutoencoderSize}{2}\times No.ofDecoders$ (6)

Figure 10: Case (a) Savings Ratio- 120x Savings Ratio beyond 1000
collaborators, breakeven point at 40 collaborators

Figure 11: Case(b) Breakeven point when No. of Comm rounds= 320, SR improves
for large scale FL

## Conclusion

The dynamic and orthogonal nature that can set the exact compression ratio
makes this approach one that performs the maximum compression compared to any
other compression model. The caveat being that there could be a situation
where the loss of information becomes high. This compression allows for the
preservation of accuracy, by increasing the complexity of the AE, at the
expense of computational costs. Thus, a trade-off-based analysis proves to be
useful while employing an AE-based compression. This paper considers generic
collaborators models while performing the AE compression and shows that
compression ratios achieved can go nearly as high as 2000x, while also
maintaining required levels of accuracy. It investigates the efficacy of AE
compression for generic models in the FL setup and shows that collaborator
models can successfully train, while the updates are being AE compressed at
every communication round. Finally, trade-off analyses show that the
advantages are greater as the number of collaborators and communication rounds
increase.

## References

  * Caldas et al. [2018] Sebastian Caldas, Jakub Konečny, H Brendan McMahan, and Ameet Talwalkar.  Expanding the reach of federated learning by reducing client resource requirements.  arXiv preprint arXiv:1812.07210, 2018.
  * Chen et al. [2020] Wei Chen, Kartikeya Bhardwaj, and Radu Marculescu.  Fedmax: Mitigating activation divergence for accurate and communication-efficient federated learning.  arXiv preprint arXiv:2004.03657, 2020.
  * Frickenstein et al. [2020] Alexander Frickenstein, Manoj-Rohit Vemparala, Nael Fasfous, Laura Hauenschild, Naveen-Shankar Nagaraja, Christian Unger, and Walter Stechele.  Alf: autoencoder-based low-rank filter-sharing for efficient convolutional neural networks.  In 2020 57th ACM/IEEE Design Automation Conference (DAC), pages 1–6. IEEE, 2020.
  * Hamer et al. [2020] Jenny Hamer, Mehryar Mohri, and Ananda Theertha Suresh.  Fedboost: A communication-efficient algorithm for federated learning.  In International Conference on Machine Learning, pages 3973–3983. PMLR, 2020.
  * Hinton et al. [2015] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean.  Distilling the knowledge in a neural network.  arXiv preprint arXiv:1503.02531, 2015.
  * Lan et al. [2018] Xu Lan, Xiatian Zhu, and Shaogang Gong.  Knowledge distillation by on-the-fly native ensemble.  arXiv preprint arXiv:1806.04606, 2018.
  * Li et al. [2018] Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith.  Federated optimization in heterogeneous networks.  arXiv preprint arXiv:1812.06127, 2018.
  * Li et al. [2020] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith.  Federated learning: Challenges, methods, and future directions.  IEEE Signal Processing Magazine, 37(3):50–60, 2020.
  * Lin et al. [2017] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally.  Deep gradient compression: Reducing the communication bandwidth for distributed training.  arXiv preprint arXiv:1712.01887, 2017.
  * Luping et al. [2019] WANG Luping, WANG Wei, and LI Bo.  Cmfl: Mitigating communication overhead for federated learning.  In 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pages 954–964. IEEE, 2019.
  * Malekijoo et al. [2021] Amirhossein Malekijoo, Mohammad Javad Fadaeieslam, Hanieh Malekijou, Morteza Homayounfar, Farshid Alizadeh-Shabdiz, and Reza Rawassizadeh.  Fedzip: A compression framework for communication-efficient federated learning.  arXiv preprint arXiv:2102.01593, 2021.
  * McMahan et al. [2017] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In Artificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017.
  * Reisizadeh et al. [2020] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani.  Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization.  In International Conference on Artificial Intelligence and Statistics, pages 2021–2031. PMLR, 2020.
  * Rothchild et al. [2020] Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora.  Fetchsgd: Communication-efficient federated learning with sketching.  In International Conference on Machine Learning, pages 8253–8265. PMLR, 2020.
  * Sattler et al. [2019] Felix Sattler, Simon Wiedemann, Klaus-Robert Müller, and Wojciech Samek.  Robust and communication-efficient federated learning from non-iid data.  IEEE transactions on neural networks and learning systems, 31(9):3400–3413, 2019.
  * Seo et al. [2020] Hyowoon Seo, Jihong Park, Seungeun Oh, Mehdi Bennis, and Seong-Lyun Kim.  Federated knowledge distillation.  arXiv preprint arXiv:2011.02367, 2020.
  * Shlezinger et al. [2020] Nir Shlezinger, Mingzhe Chen, Yonina C Eldar, H Vincent Poor, and Shuguang Cui.  Federated learning with quantization constraints.  In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8851–8855. IEEE, 2020.
  * Wang et al. [2020] Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni.  Federated learning with matched averaging.  arXiv preprint arXiv:2002.06440, 2020.
  * Zebang and Sei-ichiro [2019] Song Zebang and Kamata Sei-ichiro.  Densely connected autoencoders for image compression.  In Proceedings of the 2nd International Conference on Image and Graphics Processing, pages 78–83, 2019.


11institutetext: ADAPT Centre for Digital Content Platform Research, Knowledge
& Data Engineering Group, School of Computer Science and Statistics, Trinity
College Dublin, Dublin 2, Ireland
11email<EMAIL_ADDRESS>22institutetext: Wolters Kluwer Deutschland, München, Germany
22email<EMAIL_ADDRESS>33institutetext: Wolters Kluwer
N.V., Chicago, USA
33email<EMAIL_ADDRESS>
# Using Mapping Languages for Building Legal Knowledge Graphs from XML
files††thanks: Copyright $\copyright$ 2019 for this paper by its authors. Use
permitted under Creative Commons License Attribution 4.0 International (CC BY
4.0).

Ademar Crotti Junior 11 Fabrizio Orlandi 11 Declan O’Sullivan 11 Christian
Dirschl 22 Quentin Reul 33

###### Abstract

This paper presents our experience on building RDF knowledge graphs for an
industrial use case in the legal domain. The information contained in legal
information systems are often accessed through simple keyword interfaces and
presented as a simple list of hits. In order to improve search accuracy one
may avail of knowledge graphs, where the semantics of the data can be made
explicit. Significant research effort has been invested in the area of
building knowledge graphs from semi-structured text documents, such as XML,
with the prevailing approach being the use of mapping languages. In this
paper, we present a semantic model for representing legal documents together
with an industrial use case. We also present a set of use case requirements
based on the proposed semantic model, which are used to compare and discuss
the use of state-of-the-art mapping languages for building knowledge graphs
for legal data.

###### Keywords:

Mapping languagesLegal Knowledge GraphsLegal semantic model

##  1 Introduction

The body of law to which citizens and businesses have to adhere is constantly
increasing in volume and complexity [2]. The information contained in such a
body of law is usually provided by unstructured text within legal documents,
for which a number of systems have been developed. The information made
available by such legal information systems, however, is often accessed with
simple, keyword-based search interfaces and presented as a simple list of hits
[7]. This makes the process of information retrieval time consuming and
inefficient, especially when dealing with large amounts of information [16].
Moreover, the usefulness of such information varies widely and depends on its
structure and its representation. In this context, although the information
may be available, users and legal professionals may find the exploration of
legal information problematic when interested in specific circumstances or
investigating a particular case [16]. Such issues have led to a need for
improving ways to search and structure large amounts of legal information.

This work presents ongoing efforts related to building RDF knowledge graphs
for representing legal documents. The key focus of building such knowledge
graphs is to improve search accuracy by understanding its intent and context.
The RDF (Resource Description Framework) [4] data model is used here as it is
a W3C Recommendation which allows one to describe resources and their
relationships by the means of vocabularies and ontologies in a way that
computerized agents are able to process. Ontologies, in this context, are seen
as formal, explicit specifications of conceptualizations [9]. The structure
and semantics provided by ontologies allows one to formulate complex questions
such as “”What are the documents in which a relation to a particular law
concept, or a more specific one, exists?””.

In this paper, we present a semantic model for legal documents, which is then
being used in a real-world use case. This use case comes from an ongoing
project with Wolters Kluwer Germany, where legal documents must be transformed
to RDF knowledge graphs. These documents are stored as XML files and follow a
specific schema. Considering the semantic model and the legal document’s
schema we have defined a set of requirements, which are used to compare and
discuss the use of different state-of-the-art mappings engines. Finally, we
present an evaluation comparing the performance of a mapping approach and an
ad hoc custom parser.

The remainder of this paper is organised as follows: Section 2 describes our
use case and the XML document schema. Section 3 presents a semantic model for
representing legal documents that has been developed. Section 4 describes the
semantic uplift of legal documents to RDF knowledge graphs through the use of
mapping languages. Section 5 presents a comparison evaluation between mapping
engines. Section 6 discusses related work. Section 7 concludes the paper and
discusses future work.

##  2 Use case

This section presents our industrial use case, which comes from an ongoing
project with Wolters Kluwer Germany (WKD). WKD is a leading knowledge and
information service provider in the domains of law, companies, and tax, which
offers high quality business information for professionals. Wolters Kluwer is
based in more than 40 countries and serves customers in more than 180
countries worldwide.

WKD’s use case contains millions of documents in the German language
containing legal information together with links to taxonomy concepts. As
mentioned, the documents are stored as XML files. Each document consists of
the key parts: document keywords, document taxonomy concepts, and fragments.
Each fragment has a type, such as main claim (tenor), court facts
(tatbestand), amongst others, which are represented by different XML element
tags. Just like documents, fragments may be annotated with taxonomy concepts.
The use of taxonomy concepts defines the specific legal matters and processes
contained in a document. In this sense, the shared use of such concepts across
documents reflect the relations between the legal information contained in
those documents. This characteristic, however, is not made explicit, since
each document is represented by a single different XML file. One possible way
of making such information explicit is through the use of knowledge graphs, as
will be discussed in Section 3. An example of an XML document is shown in
Figure 1.

Figure 1: Excerpt from a WKD’s XML legal document

The taxonomy concepts used to annotate documents and its fragments come from
WKD’s taxonomy ontology. This ontology contains information about legal
concepts, which are supplemented by technical terms of neighboring areas such
as economics, sociology or politics. The Simple Knowledge Organization System
111https://www.w3.org/TR/skos-reference/ (SKOS) vocabulary is used to describe
concepts and their relations in this taxonomy. SKOS is a W3C Recommendation
designed to support the use of knowledge organization systems. In WKD’s use
case, each legal concept is represented as a skos:Concept, with the main
relationships being expressed through the properties skos:narrower and
skos:broader. A major legal subdomain of WKD’s taxonomy is available for
download and accessible via a SPARQL
endpoint222http://taxonomy.wolterskluwer.de/.

##  3 A Semantic Model for Legal Documents

As stated in Section 2, our use case shares taxonomy concepts within and
across legal documents, which are not made explicit through the XML data
format. This section presents a semantic model designed for the representation
of those legal documents, with the aim of making such relationships explicit.

The proposed semantic model draws inspiration and extends an existing one
presented in [12]. Our semantic model is also leveraged by WKD’s taxonomy
concepts, which are used to link entire documents and fragments to the legal
concepts defined in the taxonomy. Figure 2 shows the proposed semantic model
used to represent the legal information contained in our use case (Section 2).

Figure 2: Semantic model for legal documents

The vocabularies being used in the semantic model are the Platform Content
Interface (PCI), which leverages the Functional Requirements for Bibliographic
Records (FRBR), the Simple Knowledge Organization System (SKOS) and the Dublin
Core (DC) terms ontologies. The PCI ontology is a proprietary vocabulary
describing legal documents and metadata. The
FRBR333http://purl.org/vocab/frbr/core ontology provides a vocabulary for
concepts and relations in bibliographic databases defined by the International
Federation of Library Associations444https://www.ifla.org/ initiative.
Finally, the DC terms555http://purl.org/dc/terms/ ontology provides a
vocabulary describing all metadata terms maintained by the Dublin Core
Metadata Initiative666http://dublincore.org/. The PCI ontology was also
extended in order to represent the content of fragments within a document with
the datatype property pcicore:hasContent, and with the object property
pcicore:isFragmentOf, which is also defined as an inverse property of
pcicore:hasFragment. The latter two properties allow one to reference
documents to its fragments, and vice-versa.

Each document is represented as a frbr:Manifestation. The keywords of the
document are described with the datatype property pcicore:hasKeyword, and the
related taxonomy concepts with the property dcterms:subject. Each fragment is
represented as a pcicore:Fragment, and includes a reference to the document it
belongs to through the property pcicore:isFragmentOf. The content of fragments
are represented with pcicore:hasContent. Fragments have a type represented
with the class pcicore:FragmentType. Each fragment may also have keywords
(pcicore:hasKeyword), and be annotated with taxonomy concepts
(dcterms:subject). The legal taxonomy concepts, which are described as
instances of the class skos:Concept, provide linkable anchors both to entire
documents and to smaller fragments. In this context, concepts are used to
connect legal documents and textual pieces of supporting evidence within and
across different documents.

As discussed in Section 1, the representation of legal information through
knowledge graphs allows one to formulate complex questions. An example, which
was stated in Section 1, is the question: “”What are the documents in which a
relation to a particular law concept, or a more specific one, exists?””. This
question can be answered with the SPARQL query presented in Listing 1. Note
that this query returns documents related to a specific concept (in this case
wkd-law:10046) at either the document or fragment level, and that the property
skos:narrower is used to refer to more specific concepts from the taxonomy
ontology.

Listing 1: Example of SPARQL query

⬇

PREFIX pcicore: <http://onto.wolterskluwer.com/pci/core/>

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>

PREFIX wkd-law: <http://taxonomy.wolterskluwer.de/law/>

PREFIX dcterms: <http://purl.org/dc/terms/>

SELECT distinct ?document

WHERE { BIND (wkd-law:10046 as ?concept)

?fragment a pcicore:Fragment; pcicore:isFragmentOf ?document.

{ ?fragment dcterms:subject ?concept . }

UNION { ?fragment dcterms:subject ?narrower . ?concept skos:narrower ?narrower
. }

UNION { ?document dcterms:subject ?concept . }

UNION { ?document dcterms:subject ?narrower . ?concept skos:narrower ?narrower
. }

}

##  4 Semantic Uplift

This section presents our use case requirements, which are defined based on
the XML document’s schema and the proposed semantic model, together with a
comparison between state-of-the-art semantic uplift engines applied to our use
case.

Several approaches have been developed in the area of semantic uplift through
mapping languages. Mapping languages can be described as declarative languages
used to express customized mappings defining how non-RDF data should be
represented in RDF [10]. An engine is usually associated with a mapping
language, being a software processor that uses a mapping file and the input
data to generate RDF datasets. A mapping file contains one or more mapping
definitions, which state how the RDF terms are generated, considering the
input data, the vocabularies being used, and how these are associated to each
other.

###  4.1 Use Case Requirements

In our case, the following requirements must be met by the semantic uplift
engine in order to transform the XML files (Section 2) into the semantic data
model (Section 3)777These requirements express both generic requirements for
building knowledge graphs as well as specific ones for our use case, such as
being capable to select and transform XML attributes to RDF resources..

  * •

R1. Data format. This requirement is related to legal documents in our use
case being stored as XML files, being also a common data format used in many
applications.

  * •

R2. Data selection. This requirement is related to selecting specific XML
elements and attributes during the mapping process. We note that this includes
the mapping of elements which contain other nested XML elements.

  * •

R3. Vocabulary independent. This requirement allows the mapping to be defined
using existing ontologies and vocabularies.

  * •

R4. Transformation functions. This requirement allows for values to be
manipulated during the mapping process. For instance, in our use case, some
elements in the XML documents contain string values that must be normalized in
order to be represented in RDF.

  * •

R5. Multi-attribute mapping. This requirement is related to the XML files in
our use case having a collection of value nodes that are mapped to one
property in the RDF representation.

  * •

R6. Literal values to IRI. This requirement is related to IRIs being stored as
literals in the XML documents, which are required to be transformed into valid
IRIs in the RDF representation.

###  4.2 Semantic Uplift Engines

The following semantic uplift engines were compared when considering our use
case. The rationale for selecting these being that, according to their
specification, they would have support for our use case requirements.

XSPARQL. XSPARQL [1] is a query language combining XQuery and SPARQL for
transformations between RDF and XML (lifting) and back (lowering). For the
former, XSPARQL uses a combination of XQuery expressions and SPARQL CONSTRUCT
queries. The XQuery expressions are used to access XML data, and the SPARQL
CONSTRUCT queries are used to convert the accessed XML data to RDF. For the
later, XSPARQL uses a combination of SPARQL and XQuery clauses. The SPARQL
clauses are used to access RDF data, and the XQuery clauses are used to format
the results in XML syntax. This combination of languages allows one to benefit
from the facilities of SPARQL for retrieving RDF data, and the use of a TURTLE
like syntax for constructing RDF graphs, while still having access to XQuery
features for XML processing. Transformation functions in XSPARQL are supported
through native functions found in SPARQL, XQuery, XPath and XSLT.

SPARQL-Generate. SPARQL-Generate [13] extends SPARQL with specific target
constructs which enable the generation of RDF from heterogeneous sources.
SPARQL-Generate supports the generation of RDF from any RDF dataset, and from
any set of documents in arbitrary formats, such as XML, CSV and so on. SPARQL-
Generate has been designed as an extension of SPARQL 1.1, which means that it
can be implemented on top of any existing SPARQL engine by leveraging the
SPARQL extension mechanism to deal with an open set of formats. In order to do
so, SPARQL-Generate introduced three clauses to their SPARQL extension. The
source clause is used to reference the input source data. The iterator clause
allows for the extraction of data attributes from a given source data. These
attributes are then bound to SPARQL variables. Finally, the generate clause
replaces and extends the SPARQL CONSTRUCT clause with SPARQL-Generate queries.
The bounded variables which refer to data attributes are used here to form the
RDF triples. SPARQL-Generate supports data transformation functions through
native SPARQL 1.1 functions.

RML-Mapper. R2RML888https://www.w3.org/TR/r2rml/ is the W3C standardized
mapping language for defining mappings of data in relational databases to the
RDF data model. The RML [5] extension of R2RML broadens its scope by also
covering the (semi-) structured formats CSV, XML and JSON. RML documents
contain rules defining how the input data will be represented in RDF. The main
building blocks of R2RML and RML mapping documents are Triples Maps. A Triples
Map defines how the RDF triples of the form (subject, predicate, object) will
be generated. A Triples Map consists of one Logical Source, one Subject Map
and zero or more Predicate-Object Maps. The Subject Map defines how
identifiers (IRIs) are generated for the mapped resources, which are used as
the subject of the RDF triples. A Predicate-Object Map consists of Predicate
Maps, which define how to generate the triple’s predicate and Object Maps or
Referencing Object Maps, which define how the triple’s object is generated.
The Subject Map, the Predicate Map and the Object Map may be called Term Maps.
Term Maps express how an RDF term – which may be an IRI, a blank node or a
literal – is generated. A Term Map can be a constant-valued term map which is
always generating the same RDF term, a reference-valued term map that is the
data value of a referenced attribute from a given Logical Source, or a
template-valued term map that is a valid string template that may contain
referenced attributes from a given Logical Source. The engine RML-Mapper
supports data transformation functions through the Function Ontology [14].

CARML. CARML999https://github.com/carml/carml is an engine which implements
the RML mapping language, just like the described RML-Mapper. In this sense,
CARML also supports the generation of RDF datasets from heterogeneous data
formats. Transformation functions are also supported through the Function
Ontology.

###  4.3 Discussion

In order to compare these engines, a mapping expressing the transformations
needed to convert the XML files, as described in Section 2, to the RDF
semantic model described in Section 3 was created for each of these mapping
engines. In order words, this comparison assesses if and how well such engines
support the our use case requirements.

Table 1 shows the mapping engines being evaluated in our use case, their
licenses, and the version used. A discussion on the support for each use case
requirement is presented next.

Mapping Engine | License | Version
---|---|---
XSPARQL | BDS | 4.0.0
SPARQL-Generate | Apache | 1.3.1
RML-Mapper | MIT | 4.3.3
CARML | MIT | 0.2.3
Table 1: Mapping engines

R1. Data format. All the mapping engines presented have support for the
conversion of XML files to RDF. XSPARQL uses XQuery, XPath and XSLT in order
to access the information contained in XML files. The SPARQL-Generate, RML-
Mapper and CARML engines rely on XPath expressions in order to access the data
contained in XML files.

R2. Data selection. All of the mapping engines have support for selecting XML
attributes. In order to select XML elements in XSPARQL one may use the XPath
function text() or string(). The function text() returns a set of individual
nodes contained in an XML element. For instance, if an XML element contains
one nested XML element, then this function returns two nodes. The function
string() returns the string value, or the string representation, of an XML
element. In other words, an element with a nested element would return one
string value containing the whole string within that XML element. The mapping
engines SPARQL-Generate and RML-Mapper only allow for the selection of XML
elements using the text() function, which means that instead of one string
representation of an XML element the engine produces a set of literals for an
ontology property. In our use case, this is problematic when mapping the
content of fragments –- represented in the XML files by an element, often
containing nested elements – to the property pcicore:hasContent. CARML, on the
other hand, allows for the selection of elements using both text() and
string() functions. Thus, only XSPARQL and CARML fully support this
requirement.

R3. Vocabulary independent. All the engines have support for this requirement,
being expressive enough for the definition of customized mappings. XSPARQL and
SPARQL-Generate have a similar syntax based on SPARQL CONSTRUCT queries to
define how the RDF triples are generated from XML files. The RML-Mapper and
CARML engines rely on Triples Maps, which as stated previously, allows one to
define how subjects, predicates and objects are generated from non-RDF source
data.

R4. Transformation functions. XSPARQL partially supports data transformation
functions, being limited to the expressiveness of SPARQL, XQuery, XPath and
XSLT. SPARQL-Generate also partially supports data transformation functions,
being limited to the ones supported in SPARQL 1.1. The RML-Mapper and CARML
approaches, as previously stated, fully support data transformation functions
through the Function Ontology. In our use case, data transformation functions
are required when mapping string values to literals where such values must be
normalized and validated.

R5. Multi-attribute mapping. All of the engines support this requirement. The
XSPARQL engine, however, has the word uri as part of its grammar. This word is
also the name of an attribute in the XML files in our use case, which results
in an error in the execution of the mapping.

R6. String values to IRI. All of the engines support this requirement. XSPARQL
allows one to define an IRI from a string value by enclosing the variable
representing the IRI with less ($<$) and greater ($>$) than symbols. SPARQL-
Generate allows the same transformation through the SPARQL function URI. The
RML-Mapper and CARML approaches allows such transformation by defining an IRI
term type to Term Maps.

Table 2 presents the support for each requirement by the mapping engines.
CARML is the only engine with full support for all use case requirements
(Section 2)101010A means full support, while a ( ) means partial support..

Mapping Engine | R1 | R2 | R3 | R4 | R5 | R6
---|---|---|---|---|---|---
XSPARQL |  |  |  | ( ) | ( ) |
SPARQL-Generate |  | ( ) |  | ( ) |  |
RML-Mapper |  | ( ) |  |  |  |
CARML |  |  |  |  |  |
Table 2:  Mapping engines comparison.

##  5 Evaluation

This section presents an evaluation comparing the performance of two
approaches applied to the semantic uplift of XML files. One approach utilizes
RML mappings through the CARML engine, which, as discussed, is the only one
with full support for our use case requirements. The second approach is an ad
hoc custom parser developed to generate the same RDF representation from XML
files.

The experiment was executed on a MacBook Pro 13” (3.1 GHz, i7, 16GB RAM),
where both approaches would transform the same input into the same RDF
representation. Each approach was executed 10 times considering 3 different
datasets containing 1000 (1k), 10000 (10k) and 50000 (50k) documents. These
datasets have been created by randomly selecting files from our use case which
contains over 1 million documents. These were selected randomly in order to
provide sets of documents with different characteristics (e.g. size). Table 3
presents the results of this experiment.

Performance Comparison | 1k | 10k | 50k
---|---|---|---
AVG | STD | AVG | STD | AVG | STD
Ad hoc custom parser | 4.09 | 0.47 | 38.7 | 3.95 | 212.8 | 30.01
CARML | 4.85 | 1.33 | 43.3 | 3.9 | 242.5 | 30.9
Table 3:  Time performance results for 10 runs (in seconds).

These results show that the use of mappings, namely RML with the CARML engine,
does impact performance. In order to assess whether these differences are
statistically significant we performed the Welch Two Sample T-Test with a
significance level of 0.05. The results suggest no statistical significance
between using an ad hoc custom parser and CARML for 1k documents (p-value of
0.12). However, for 10k and 50k documents the difference in performance is
statistically significant (p-values of 0.04 and 0.01, respectively). We do
note that, even though the use of mapping languages impact performance, this
is still the preferred approach for our use case. The reason being that
mapping languages separate mapping definitions from the implementations that
execute them, allowing the process to be reused and shared. Furthermore, the
maintenance of mappings is facilitated by the same reason when compared to an
ad hoc parser. For instance, any changes in the semantic model or in the input
data would require the mapping to be updated accordingly, without the need to
change the engine responsible for the execution of the mapping. An ad hoc
parser, on the other hand, would require the implementation, which is specific
to a certain use case, to be modified. Finally, implementations may be
improved with optimizations and other choices of software libraries, which
could be tailored to different use cases and thus positively impact
performance.

##  6 Related work

The representation of legal information through ontologies have been the focus
of several studies.

Ebenhoch [6] has proposed the representation of legal information through RDF,
where a key point to make such data more accessible is the process of
enriching it with metadata. Winkels et al. [17] describe the need of semantics
in a legal context from the practical point of view of the Dutch Tax and
Customs Administration, who have to deal with legal information from various
sources and formats. JURION [11] was a legal information platform which merges
and interlinks over one million documents of content and data from diverse
sources, such as national and European legislation and court judgments,
amongst others. The approaches presented in [6] and [17] used ad hoc parsers
for the creation of knowledge graphs from source data, while JURION’s
extraction process relies on XSLT scripts in order to convert the data stored
as XML files to RDF. This paper, in contrast, has investigated the use of
mapping languages for building knowledge graphs to represent legal documents.

Other studies have focused on investigating ontology design patterns in the
legal domain which are described together with examples [8]. A summary of
existing legal ontologies is provided in [3]. This work describes and
classifies 23 legal ontologies in distinct categories such in which type of
application the ontology has been used, how the ontology was constructed, its
language, and so on. Semantic Web technologies are also being used to describe
particular subdomains of law, such as licenses, and more recently the General
Data Protection Regulation [15]. As stated previously, a semantic model for
legal documents has been presented in [12], which was used as the base for our
semantic model (Section 2).

##  7 Conclusions and future work

In this paper, we have presented a semantic model for legal documents applied
to an industrial use case. This use case comes from Wolters Kluwer Germany’s
company, where their legal information is stored as XML files. By taking into
account the proposed semantic model and the XML’s document schema we have
defined a set of requirements which should be met by the mapping engine in
order for it to be able to produce the required RDF knowledge graph. We have
also compared and discussed the use of four different state-of-the-art mapping
engines based on our set of requirements. CARML, which implements the RML
mapping language, was found to be the only one supporting all our use case
requirements. Finally, we have also compared and discuss the use of CARML to
developing ad hoc parsers for the process of transforming XML files to RDF.

In future work, we will further investigate the use of mapping languages in
terms of its performance when considering large documents. Future work will
also investigate the performance of the RDF knowledge graph based on queries,
which may result in improvements on the semantic model, and in changes in the
mapping.

## Acknowledgments

This paper was supported by the Science Foundation Ireland (Grant 13/RC/2106)
as part of the ADAPT Centre for Digital Content Technology
(http://www.adaptcentre.ie/) at Trinity College Dublin.

## References

  * [1] Bischof, S., Decker, S., Krennwallner, T., Lopes, N., Polleres, A.: Mapping between rdf and xml with xsparql. Journal on Data Semantics 1(3) (2012)
  * [2] Boella, G., Caro, L.D., Humphreys, L., Robaldo, L., Rossi, P., van der Torre, L.: Eunomos, a legal document and knowledge management system for the web to provide relevant, reliable and up-to-date information on the law. Artificial Intelligence and Law 24(3) (2016)
  * [3] Breuker, J., Casanovas, P., Klein, M.C.A., Francesconi, E.: The flood, the channels and the dykes: Managing legal information in a globalized and digital world. In: Proceedings of the 2009 Conference on Law, Ontologies and the Semantic Web. IOS Press (2009)
  * [4] Cyganiak, R., Wood, D., Lanthaler, M., Klyne, G., Carroll, J.J., McBride, B.: Rdf 1.1 concepts and abstract syntax. W3C recommendation 25(02) (2014)
  * [5] Dimou, A., Vander Sande, M., Colpaert, P., Verborgh, R., Mannens, E., Van de Walle, R.: RML: A Generic Language for Integrated RDF Mappings of Heterogeneous Data. In: Proceedings of the 7th LDoW Workshop at WWW (2014)
  * [6] Ebenhoch, M.P.: Legal knowledge representation using the resource description framework (rdf). In: 12th International Workshop on Database and Expert Systems Applications. IEEE (2001)
  * [7] Filtz, E.: Building and processing a knowledge-graph for legal data. In: The Semantic Web. Springer (2017)
  * [8] Griffo, C., Almeida, J.P.A., Guizzardi, G.: A pattern for the representation of legal relations in a legal core ontology. In: JURIX (2016)
  * [9] Gruber, T.R.: Toward principles for the design of ontologies used for knowledge sharing? International journal of human-computer studies 43(5-6) (1995)
  * [10] Junior, A.C., Debruyne, C., Brennan, R., O’Sullivan, D.: An evaluation of uplift mapping languages. IJWIS 13(4) (2017), https://doi.org/10.1108/IJWIS-04-2017-0036.
  * [11] Kontokostas, D., Mader, C., Dirschl, C., Eck, K., Leuthold, M., Lehmann, J., Hellmann, S.: Semantically enhanced quality assurance in the jurion business use case. In: Sack, H., Blomqvist, E., d’Aquin, M., Ghidini, C., Ponzetto, S.P., Lange, C. (eds.) The Semantic Web. Latest Advances and New Domains. Springer (2016)
  * [12] Lee, S., Kim, P., Seo, D., Kim, J., Lee, J., Jung, H., Dirschl, C.: Multi-faceted navigation of legal documents. In: International Conference on IoT and 4th International Conference on Cyber, Physical and Social Computing (2011)
  * [13] Lefrançois, M., Zimmermann, A., Bakerally, N.: A SPARQL extension for generating RDF from heterogeneous formats. In: The Semantic Web - 14th International Conference, ESWC Proceedings (2017)
  * [14] Meester, B.D., Dimou, A., Verborgh, R., Mannens, E.: An ontology to semantically declare and describe functions. In: The Semantic Web-ESWC 2016 Satellite Events, Revised Selected Papers (2016)
  * [15] Pandit, H.J., Fatema, K., O’Sullivan, D., Lewis, D.: Gdprtext - GDPR as a linked data resource. In: The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings. pp. 481–495 (2018)
  * [16] Schweighofer, E.: Semantic Indexing of Legal Documents. Springer (2010)
  * [17] Winkels, R., Boer, A., de Maat, E., van Engers, T., Breebaart, M., Melger, H.: Constructing a semantic network for legal content. In: Proceedings of the 10th International Conference on Artificial Intelligence and Law. ICAIL’05, ACM (2005)