GraphWorld: Fake Graphs Bring Real Insights for GNNs

John Palowitch

Google Research

Anton Tsitsulin

Google Research

Brandon Mayer

Google Research

Bryan Perozzi

Google Research

<concept_desc>Computing methodologies Model verification and validation</concept_desc>
<concept_desc>Computing methodologies Network science</concept_desc>
<concept_desc>Computing methodologies Neural networks</concept_desc>

[500]Computing methodologies Model verification and validation
[500]Computing methodologies Network science
[500]Computing methodologies Neural networks

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

titleTensorflow GNN.

authorpersonEmmanuel Abbe.
Community detection and stochastic block models:
recent developments.
journalJMLR (year2017).

[Adamic and Adar(2003)]
authorpersonLada A Adamic and personEytan
Adar. year2003.
Friends and neighbors on the web.
journalSocial networks (year2003).

[Bianchi et al(2021)]
authorpersonFilippo Maria Bianchi,
personDaniele Grattarola, personLorenzo Livi, and
personCesare Alippi. year2021.
Graph neural networks with convolutional arma
journalIEEE Transactions on Pattern Analysis and
Machine Intelligence (year2021).

[Brin and Page(1998)]
authorpersonSergey Brin and personLawrence
Page. year1998.
The anatomy of a large-scale hypertextual web
search engine.
journalComputer networks and ISDN systems

authorpersonMarc Brockschmidt.
Gnn-film: Graph neural networks with feature-wise
linear modulation. In booktitleICML. PMLR.

[Brody et al(2021)]
authorpersonShaked Brody, personUri Alon,
and personEran Yahav. year2021.
How Attentive are Graph Attention Networks?
journalarXiv preprint arXiv:2105.14491

[Chami et al(2020)]
authorpersonInes Chami, personSami
Abu-El-Haija, personBryan Perozzi, personChristopher
Ré, and personKevin Murphy.
Machine learning on graphs: A model and
comprehensive taxonomy.
journalarXiv preprint arXiv:2005.03675

[Chen et al(2020)]
authorpersonZhengdao Chen, personLei Chen,
personSoledad Villar, and personJoan Bruna.
Can graph neural networks count substructures?
journalarXiv preprint arXiv:2002.04025

[Cobbe et al(2020)]
authorpersonKarl Cobbe, personChris Hesse,
personJacob Hilton, and personJohn Schulman.
Leveraging procedural generation to benchmark
reinforcement learning. In booktitleICML.

[Dacrema et al(2019)]
authorpersonMaurizio Ferrari Dacrema,
personPaolo Cremonesi, and personDietmar Jannach.
Are we really making much progress? A worrying
analysis of recent neural recommendation approaches. In

authorpersonLee R Dice.
Measures of the amount of ecologic association
between species.
journalEcology (year1945).

[Dwivedi et al(2020)]
authorpersonVijay Prakash Dwivedi,
personChaitanya K Joshi, personThomas Laurent,
personYoshua Bengio, and personXavier Bresson.
Benchmarking graph neural networks.
journalarXiv preprint arXiv:2003.00982

[Errica et al(2020)]
authorpersonFederico Errica, personMarco
Podda, personDavide Bacciu, and personAlessio
Micheli. year2020.
A fair comparison of graph neural networks for
graph classification. In booktitleICLR.

[Fey and Lenssen(2019)]
authorpersonMatthias Fey and personJan E.
Lenssen. year2019.
Fast Graph Representation Learning with PyTorch
Geometric. In booktitleICLR Workshop on Representation
Learning on Graphs and Manifolds.

[Grover and Leskovec(2016)]
authorpersonAditya Grover and personJure
Leskovec. year2016.
node2vec: Scalable feature learning for networks.
In booktitleKDD.

[Hamilton et al(2017)]
authorpersonWilliam L Hamilton, personRex
Ying, and personJure Leskovec.
Inductive representation learning on large graphs.
In booktitleNIPS.

[Hu et al(2020)]
authorpersonWeihua Hu, personMatthias Fey,
personMarinka Zitnik, personYuxiao Dong,
personHongyu Ren, personBowen Liu,
personMichele Catasta, and personJure Leskovec.
Open Graph Benchmark: Datasets for machine learning
on graphs. In booktitleNeurIPS.

authorpersonPaul Jaccard.
The distribution of the flora in the alpine zone.
journalNew Phytologist (year1912).

[Karrer and Newman(2011)]
authorpersonBrian Karrer and personMark EJ
Newman. year2011.
Stochastic blockmodels and community structure in
journalPhysical review E volume83,
number1 (year2011), pages016107.

[Khosla et al(2019)]
authorpersonMegha Khosla, personVinay
Setty, and personAvishek Anand.
A comparative study for unsupervised network
representation learning.
journalTKDE (year2019).

[Kim and Oh(2021)]
authorpersonDongkwan Kim and personAlice
Oh. year2021.
How to Find Your Friendly Neighborhood: Graph
Attention Design with Self-Supervision. In booktitleICLR.

[Kipf and Welling(2016)]
authorpersonThomas N Kipf and personMax
Welling. year2016.
Semi-supervised classification with graph
convolutional networks.
journalarXiv preprint arXiv:1609.02907

[Klicpera et al(2018)]
authorpersonJohannes Klicpera,
personAleksandar Bojchevski, and personStephan
Günnemann. year2018.
Predict then propagate: Graph neural networks meet
personalized pagerank.
journalarXiv preprint arXiv:1810.05997

[Koh et al(2021)]
authorpersonPang Wei Koh, personShiori
Sagawa, personSang Michael Xie, personMarvin Zhang,
personAkshay Balsubramani, personWeihua Hu,
personMichihiro Yasunaga, personRichard Lanas
Phillips, personIrena Gao, personTony Lee,
et al year2021.
Wilds: A benchmark of in-the-wild distribution
shifts. In booktitleICML.

[Leicht et al(2006)]
authorpersonElizabeth A Leicht, personPetter
Holme, and personMark EJ Newman.
Vertex similarity in networks.
journalPhysical Review E (year2006).

[Li et al(2021)]
authorpersonGuohao Li, personJesus Zarzar,
personHesham Mostafa, personSohil Shah,
personMarcel Nassar, personDaniel Cummings,
personSami Abu-El-Haija, personBernard Ghanem, and
personMatthias Müller. year2021.
DEEPERBIGGERBETTER for OGB-LSC at KDD cup 2021.

[Lipton and Steinhardt(2018)]
authorpersonZachary C Lipton and
personJacob Steinhardt. year2018.
Troubling trends in machine learning scholarship.
journalarXiv preprint arXiv:1807.03341

[Luzhnica et al(2019)]
authorpersonEnxhell Luzhnica, personBen
Day, and personPietro Liò.
On graph classification networks, datasets and
journalarXiv preprint arXiv:1905.04682

[Mara et al(2021)]
authorpersonAlexandru Mara, personJefrey
Lijffijt, and personTijl de Bie.
Reproducible Evaluations of Network Representation
Learning Models Using EvalNE.
journalWWW'21, Workshop on Graph Learning
Benchmarks (year2021).

[Morris et al(2020)]
authorpersonChristopher Morris, personNils M
Kriege, personFranka Bause, personKristian Kersting,
personPetra Mutzel, and personMarion Neumann.
Tudataset: A collection of benchmark datasets for
learning with graphs.
journalarXiv preprint arXiv:2007.08663

[Nie et al(2019)]
authorpersonYixin Nie, personAdina
Williams, personEmily Dinan, personMohit Bansal,
personJason Weston, and personDouwe Kiela.
Adversarial NLI: A new benchmark for natural
language understanding.
journalarXiv preprint arXiv:1910.14599

[Ravasz et al(2002)]
authorpersonErzsébet Ravasz,
personAnna Lisa Somera, personDale A Mongru,
personZoltán N Oltvai, and personA-L
Barabási. year2002.
Hierarchical organization of modularity in
metabolic networks.
journalScience (year2002).

[Recht et al(2018)]
authorpersonBenjamin Recht, personRebecca
Roelofs, personLudwig Schmidt, and personVaishaal
Shankar. year2018.
Do cifar-10 classifiers generalize to cifar-10?
journalarXiv preprint arXiv:1806.00451

[Rossi and Ahmed(2015)]
authorpersonRyan A. Rossi and
personNesreen K. Ahmed. year2015.
The Network Data Repository with Interactive Graph
Analytics and Visualization. In booktitleAAAI.

authorpersonNeil Shah.
Scale-Free, Attributed and Class-Assortative Graph
Generation to Facilitate Introspection of Graph Neural Networks.
journalWWW'21, Workshop on Graph Learning
Benchmarks (year2020).

[Shchur et al(2018)]
authorpersonOleksandr Shchur,
personMaximilian Mumme, personAleksandar Bojchevski,
and personStephan Günnemann.
Pitfalls of graph neural network evaluation.
journalarXiv preprint arXiv:1811.05868

[Shi et al(2021)]
authorpersonYunsheng Shi, personZhengjie
Huang, personShikun Feng, personHui Zhong,
personWenjin Wang, and personYu Sun.
Masked label prediction: Unified message passing
model for semi-supervised classification.

[Shridhar et al(2020)]
authorpersonMohit Shridhar, personJesse
Thomason, personDaniel Gordon, personYonatan Bisk,
personWinson Han, personRoozbeh Mottaghi,
personLuke Zettlemoyer, and personDieter Fox.
Alfred: A benchmark for interpreting grounded
instructions for everyday tasks. In booktitleCVPR.

authorpersonGeorge W Snedecor.
titleStatistical methods.

authorpersonTh A Sørensen.
A method of establishing groups of equal amplitude
in plant sociology based on similarity of species content and its application
to analyses of the vegetation on Danish commons.
journalBiol. Skar. (year1948).

authorpersonRobert L Thorndike.
Who belongs in the family?
journalPsychometrika (year1953).

[Tsitsulin et al(2020)]
authorpersonAnton Tsitsulin, personJohn
Palowitch, personBryan Perozzi, and personEmmanuel
Müller. year2020.
Graph clustering with graph neural networks.
journalarXiv preprint arXiv:2006.16904

[Tsitsulin et al(2021)]
authorpersonAnton Tsitsulin, personBenedek
Rozemberczki, personJohn Palowitch, and personBryan
Perozzi. year2021.
Synthetic Graph Generation to Benchmark Graph
journalWWW'21, Workshop on Graph Learning
Benchmarks (year2021).

[Veličković et al(2017)]
authorpersonPetar Veličković,
personGuillem Cucurull, personArantxa Casanova,
personAdriana Romero, personPietro Lio, and
personYoshua Bengio. year2017.
Graph attention networks.
journalarXiv preprint arXiv:1710.10903

[Wolfson et al(2020)]
authorpersonTomer Wolfson, personMor Geva,
personAnkit Gupta, personMatt Gardner,
personYoav Goldberg, personDaniel Deutch, and
personJonathan Berant. year2020.
Break it down: A question understanding benchmark.
journalACL (year2020).

[Wu et al(2019)]
authorpersonFelix Wu, personAmauri Souza,
personTianyi Zhang, personChristopher Fifty,
personTao Yu, and personKilian Weinberger.
Simplifying graph convolutional networks. In
booktitleICML. PMLR.

[Wu et al(2020)]
authorpersonZonghan Wu, personShirui Pan,
personFengwen Chen, personGuodong Long,
personChengqi Zhang, and personS Yu Philip.
A comprehensive survey on graph neural networks.
journalIEEE transactions on neural networks and
learning systems (year2020).

[Xu et al(2018)]
authorpersonKeyulu Xu, personWeihua Hu,
personJure Leskovec, and personStefanie Jegelka.
How powerful are graph neural networks?
journalarXiv preprint arXiv:1810.00826

[You et al(2020)]
authorpersonJiaxuan You, personZhitao Ying,
and personJure Leskovec. year2020.
Design space for graph neural networks. In

[Zhao et al(2020)]
authorpersonWentao Zhao, personDalin Zhou,
personXinguo Qiu, and personWei Jiang.
A pipeline for fair comparison of graph neural
networks in node classification tasks.
journalarXiv preprint arXiv:2012.10619

[Zhou et al(2009)]
authorpersonTao Zhou, personLinyuan Lü,
and personYi-Cheng Zhang. year2009.
Predicting missing links via local information.
journalThe European Physical Journal B

[Zhu et al(2020)]
authorpersonJiong Zhu, personYujun Yan,
personLingxiao Zhao, personMark Heimann,
personLeman Akoglu, and personDanai Koutra.
Beyond homophily in graph neural networks: Current
limitations and effective designs.
journalarXiv preprint arXiv:2006.11468


# Physics-informed and Unsupervised Riemannian Domain Adaptation for Machine
Learning on Heterogeneous EEG Datasets
††thanks: This work was supported by the grants ANR-20-CHIA-0016,
ANR-20-IADJ-0002, and ANR-20-THIA-0013 from Agence nationale de la recherche
(ANR).

Apolline Mellot21, Antoine Collas2, Sylvain Chevallier3, Denis Engemann4,
Alexandre Gramfort2  2University Paris-Saclay, Inria, CEA, Palaiseau, France.
3TAU Inria, LISN-CNRS, University Paris-Saclay, France.
4Roche Pharma Research and Early Development, Neuroscience and Rare Diseases,
Roche Innovation Center Basel, F. Hoffmann–La Roche Ltd. 1Email:
<EMAIL_ADDRESS>
###### Abstract

Combining electroencephalogram (EEG) datasets for supervised machine learning
(ML) is challenging due to session, subject, and device variability. ML
algorithms typically require identical features at train and test time,
complicating analysis due to varying sensor numbers and positions across
datasets. Simple channel selection discards valuable data, leading to poorer
performance, especially with datasets sharing few channels. To address this,
we propose an unsupervised approach leveraging EEG signal physics. We map EEG
channels to fixed positions using field interpolation, facilitating source-
free domain adaptation. Leveraging Riemannian geometry classification
pipelines and transfer learning steps, our method demonstrates robust
performance in brain-computer interface (BCI) tasks and potential biomarker
applications. Comparative analysis against a statistical-based approach known
as Dimensionality Transcending, a signal-based imputation called ComImp,
source-dependent methods, as well as common channel selection and spherical
spline interpolation, was conducted with leave-one-dataset-out validation on
six public BCI datasets for a right-hand/left-hand classification task.
Numerical experiments show that in the presence of few shared channels in
train and test, the field interpolation consistently outperforms other
methods, demonstrating enhanced classification performance across all
datasets. When more channels are shared, field interpolation was found to be
competitive with other methods and faster to compute than source-dependent
methods.

###### Index Terms:

Electroencephalography (EEG), Interpolation, Unsupervised Domain Adaptation,
Riemannian Geometry

##  I Introduction

Electroencephalography (EEG) has emerged as a valuable tool for brain health
monitoring and neuroscience studies due to its high temporal resolution and
non-invasive nature [1]. Supervised machine learning algorithms have driven
significant advances in EEG signal analysis, enabling applications such as
sleep staging [2], pathology diagnostics [3], and brain-computer interfaces
(BCIs) [4].

While machine learning is a promising tool for large-scale EEG analysis, its
effectiveness can be compromised by dataset shifts. This problem occurs when a
model is applied to unseen data (target) with a different distribution than
the data on which it was trained (source) [5]. In EEG data, this variability
arises from inter-subject differences, inter-session variability, and
differences in recording equipment, e.g., amplifiers and electrode nets. To
address this challenge, domain adaptation aims to bridge the gap between
source and target datasets, thereby reducing the impact of dataset shift. In
addition to dataset shift, EEG data often have varying numbers and positions
of electrodes in different recording setups, resulting in heterogeneous data.

Various methods have been proposed to address the challenge of dimension
mismatch in domain adaptation for EEG data. Methods based on projecting data
into lower-dimensional spaces [6] or selecting common channels [7, 8] risk
losing valuable information specific to EEG signals. End-to-end deep learning
approaches propose to leverage spatial attention mechanisms by using the
electrodes’ coordinates [9] but are computationally expensive. While
covariance-based imputation approaches like Dimensionality Transcending [10]
achieve state-of-the-art performance in BCI applications, they rely on
supervised learning, limiting their application to scenarios with labeled
target data.

In this work, we propose an unsupervised source free pipeline to combine
heterogeneous datasets: a model is trained on several labeled datasets
(sources) and then applied on an unseen and unlabeled dataset (target). We
propose to map EEG channels to a template of fixed positions by leveraging the
underlying physics of EEG data through field interpolation. Then, we leverage
the Riemannian re-centering operator to align the statistical distributions of
data from different source domains, mitigating dataset shift. We evaluated our
method on six BCI datasets using leave-one-dataset-out procedures.

This paper is organized as follows: Section II presents the Riemannian
classification pipeline, Section III introduces the methods explored in this
work to deal with heterogeneous EEG data, and Section IV describes the
experimental evaluation of these methods and reports on the advantages of
field interpolation compared to other methods.

Datasets | Subj. | Chan. | Sess. | Runs
---|---|---|---|---
BNCI2014_001 (B1) | 12 | 22 | 2 | 6
BNCI2014_004 (B4) | 9 | 3 | 5 | 1
PhysionetMI (P) | 109 | 64 | 1 | 1
Shin2017A (S) | 29 | 30 | 3 | 1
Weibo2014 (W) | 10 | 60 | 1 | 1
Zhou2016 (Z) | 4 | 14 | 3 | 2

Figure 1: Top: table of diverse characteristics of the datasets. Bottom: 2D
projection of sensor positions on the scalp.

##  II EEG covariance and Riemannian geometry

In this section, we introduce the Riemannian geometry concepts used for EEG
covariance-based classification and transfer learning in BCIs.

###  II-A Covariance matrix representation

EEG signals $\textbf{X}\in\mathbb{R}^{P\times T}$ are multivariate time series
recorded with $P$ sensors that capture the electrical activity of the brain at
$T$ time steps. We represent the EEG signal by its empirical covariance
matrix:

$\textbf{C}=\frac{\textbf{X}\textbf{X}^{\top}}{T}\in\mathbb{R}^{P\times
P}\enspace.$ (1)

As we deal with interpolated signals filled with linear combinations of the
sensors’ signals, we regularised the empirical covariance matrices with the
Ledoit-Wolf shrinkage to avoid rank deficiency:

$\hat{\textbf{C}}=(1-s)\textbf{C}+s\mu\mathbf{I}_{P}$ (2)

with $\mu=\operatorname{Tr}(\textbf{C})/P$ and $s$ the shrinkage coefficient
[11]. The regularised covariance matrix belongs to the set
$\mathcal{S}^{++}_{P}$ of Symmetric Positive Definite (SPD) matrices.

###  II-B Riemannian geometry

SPD matrices lie in a manifold that can be equipped with the affine-invariant
Riemannian distance [12]:

$\displaystyle\delta_{R}(\textbf{C}_{1},\textbf{C}_{2})=\left(\sum_{k=1}^{P}\text{log}^{2}\lambda_{k}\right)^{\frac{1}{2}}\enspace,$
(3)

where $\lambda_{k}$ are the eigenvalues of
$\textbf{C}_{1}^{-1}\textbf{C}_{2}$. With this distance, we define the
geometric Riemannian mean of a set of $N$ SPD matrices by minimizing:

$\displaystyle\bar{\textbf{C}}=\operatorname*{argmin}_{\textbf{C}\in\mathcal{S}_{P}^{++}}\sum_{i=1}^{N}\delta_{R}^{2}(\textbf{C},\textbf{C}_{i})\enspace.$
(4)

Endowed with a Riemannian metric, a Riemannian manifold $\mathcal{M}$ is a
differentiable manifold to which we can attach a Euclidean vector space at any
point of the manifold, called tangent space. Each element of the manifold can
be projected on the tangent space by a logarithmic mapping. The tangent vector
z is the vectorized projection of a SPD matrix C on the tangent space at point
$\bar{\textbf{C}}$:

$\displaystyle\textbf{z}=\textrm{Upper}(\textrm{log}(\bar{\textbf{C}}^{-\frac{1}{2}}\textbf{C}\bar{\textbf{C}}^{-\frac{1}{2}}))\in\mathbb{R}^{P(P+1)/2}\enspace,$
(5)

where $\textrm{Upper}()$ is the function returning a vector containing the
concatenation of the upper triangle values of a matrix with weights of 1 for
diagonal elements and $\sqrt{2}$ for other elements, and $\textrm{log}()$ the
matrix logarithm with the log applied to the eigenvalues in the eigenvalue
decomposition. This tangent space mapping transforms covariance matrices into
Euclidean vectors that can be used as input for classical linear machine
learning models [13].

###  II-C Transfer learning: re-center to Identity

In covariance-based BCI classification, the preferred transfer learning
technique to reduce the shifts induced by subject and dataset variability is
re-centering the covariance distributions to a common reference point on the
Riemannian manifold [14]. Here, each covariance distribution, or domain, is
re-centered to the Identity by whitening them with their respective geometric
mean $\bar{\textbf{C}}$:

$\displaystyle\textbf{C}_{i}^{(\text{rct})}=\bar{\textbf{C}}^{-\frac{1}{2}}\textbf{C}_{i}\bar{\textbf{C}}^{-\frac{1}{2}}\enspace.$
(6)

One whitening is applied per domain separately. When applied to EEG data,
domains can be defined as the datasets, the subjects, or even the sessions. In
our experiments, we consider each subject as one domain.

##  III Matching EEG data dimensions

This work focuses on combining several heterogeneous datasets with varying
numbers of channels due to different recording devices. Figure 1 illustrates
the variability in positions of the sensors on the scalp across the six
datasets considered in the experimental evaluation. In this section, we
present existing strategies to deal with heterogeneous dimensionalities and
propose a new source free approach with channel interpolation.

###  III-A Common channel selection

Selecting EEG channels that are consistently present across all subjects and
datasets is the first strategy that comes to mind, particularly effective when
there is a sufficient number of shared channels to perform the desired
analytical tasks [7, 8]. However, as the number of subjects and datasets
increases, the variability in sensor positions due to the use of different
recording devices becomes more pronounced. This can lead to a situation where
there are too few common channels for the task, as was observed in our
experimental evaluation, where only one common channel in the middle of the
head (Cz) was insufficient for right/left-hand classification.

###  III-B Geometry-based imputation: Dimensionality Transcending (DT)

Rodrigues et al. [10] proposed to transform the data points into an expanded
common space with an isometric transformation, which preserves the distance of
the original data points in the new expanded space. We consider $M$ datasets
of different dimensionality (or different numbers of sensors) $P_{j}$ with
$j=1,\dots,M$. The expanded space dimension is $P_{\textrm{exp}}=\bigcup
P_{j}$. The resulting expanded version $\textbf{C}_{i}^{\uparrow}$ of a matrix
$\textbf{C}_{i}$ from the $j$-th dataset is:

$\displaystyle\textbf{C}_{i}^{\uparrow}=\begin{bmatrix}\textbf{C}_{i}&\textbf{0}_{P_{j}\times(P_{\textrm{exp}}-P_{j})}\\\
\textbf{0}_{(P_{\textrm{exp}}-P_{j})\times
P_{j}}&\mathbf{I}_{(P_{\textrm{exp}}-P_{j})}\end{bmatrix}\in\mathbb{R}^{P_{\textrm{exp}}\times
P_{\textrm{exp}}}$ (7)

This transformation is applied to all datasets to get covariances of size
$P_{\textrm{exp}}\times P_{\textrm{exp}}$. In addition, a permutation of the
expanded matrices rows and columns is performed to make the same channels
correspond across datasets. This expansion of covariances was originally
designed to be followed by a supervised transfer learning method called
Riemannian Procrustes Analysis (RPA) [15]. However, since we operate in an
unsupervised setting, we only apply the re-centering step introduced in
subsection II-C in our framework.

###  III-C Signal-based imputation

The “ComImp” method [16], offers a direct machine learning approach to handle
missing data in EEG recordings. First, the time series data are expanded to
match the union of the set of channels, hence generating missing values in the
data. In our case the EEG signal is expanded to be of size
$P_{\text{exp}}\times T$. Then, statistical imputation techniques can be
employed. Such approaches require fitting the imputation method on training
data that include at least one non-missing value per channel. Here, we
considered a multivariate imputer that models each feature with missing values
as a function of the other features with a regression. We used the
IterativeImputer class of the Scikit-Learn software [17] with a ridge
estimator.

###  III-D Physics-informed approach: Interpolation

Figure 2: Processing pipeline of EEG data. Depending on the method, dimensions
are matched either when data are represented as epochs for interpolations or
as covariances for DT. When there is no alignment performed, the Re-Center
step is removed.

Interpolation is a technique used in the context of EEG data processing to
reconstruct the signals of malfunctioning or too noisy channels, usually
referred to as ‘bad’ channels. It uses the signals from the functional
channels around the bad ones. In this work, we used interpolation to map the
different channels of EEG datasets: the EEG signal was reconstructed on fixed
final positions based on the existing signal from all sensors of the datasets.
Interpolation involves constructing a linear operator
$\textbf{A}\in\mathbb{R}^{P\times P_{j}}$ that maps the $P_{j}$ existing EEG
channels to the $P$ positions of a fixed template:

$\displaystyle\hat{\textbf{X}}=\textbf{AX}\enspace,$ (8)

where $\textbf{X}\in\mathbb{R}^{P_{j}\times T}$ are the recorded EEG signals
and $\hat{\textbf{X}}\in\mathbb{R}^{P\times T}$ are the reconstructed signals.
This operator can be estimated to reconstruct the EEG signal at any desired
position, even if there is no corresponding sensor at that location. In the
following, we present two common interpolation techniques used with EEG data:
the spherical spline interpolation and the field interpolation.

####  III-D1 Spherical spline interpolation (SSI)

The idea behind SSI is to model the data using smooth functions that are
defined on the surface of a sphere. The functions here are spherical splines
[18]. In practice, the existing sensors’ locations and desired final positions
are first projected onto a unit sphere. Then, the linear mapping matrix is
computed and finally used to interpolate the signal at the desired position
based on the existing signal.

Figure 3: Accuracy for different dimensionality matching methods on three
left-out datasets. One column (across panels A & B) corresponds to one target
dataset. (A) Comparative learning curves for an increasing number of target
channels seen during training with FI performance as reference. The increasing
number of seen target channels is obtained by gradually including datasets in
the train set, which is specified in the x-axis. The error bar represents the
95% confidence interval over the target subjects’ performance. (B) Boxplot of
accuracies when the classifier is trained on the five other datasets. One
point corresponds to one subject of the target dataset. A black line
represents the median of the box and the mean by a white circle. The black
lines indicate the chance level. The stars represent the results of a Wilcoxon
test (ns: $p>5\mathrm{e}{-2}$, *: $1\mathrm{e}{-2}<p\leq 5\mathrm{e}{-2}$,
****: $p\leq 1\mathrm{e}{-4}$).

####  III-D2 Field interpolation (FI)

The field mapping employed in the FI uses a canonical distribution of signal
generators in the brain and then estimates a forward model based on Maxwell’s
equations [19]. The forward model relates the distribution of estimated brain
activity to sensor data at any electrode location. To obtain electric
potential estimates at a missing electrode location, the available data are
mapped to brain space using a Tikhonov regularization referred to as Minimum
Norm Estimate (MNE) [20]. Then the forward model can be applied to the
estimated EEG generators to obtain potential values for any electrode
location. The MNE-python software provides an implementation of the FI [19].

##  IV Experimental evaluation

###  IV-A Data description

The methods described in section III were evaluated on six publicly available
BCI datasets from the MOABB repository [21]. The number of subjects, channels,
sessions, runs, and trials varies across the datasets. Figure 1 summarizes the
key details of the datasets. All datasets were recorded with the left mastoid
as reference, except for _Weibo2014_ where the reference was taken at the
nose. All datasets consist of EEG data recorded while participants performed
motor imagery tasks. The subjects were instructed to imagine moving either
their right or left hand without actually moving it in response to a visual
cue. The classification problem is thus a binary classification task.

###  IV-B Preprocessing and classification pipeline

All data were band-pass filtered between 8 and 32 Hz with an Infinite Impulse
Response (IIR) forward-backward filter and resampled at 128 Hz. The signals
were segmented in epochs at each trial and of duration corresponding to the
trial length with no overlap. Subsequently, spatial covariance matrices were
computed from the filtered epochs as presented in subsection II-A. Figure 2
illustrates the classification pipeline depending on the dimension-matching
method. Subjects are used as domains for re-centering. The geometric mean of
the subjects used in the train set is computed by considering all their data
points. For the test subject, the geometric mean is computed on the data from
its first session, or first run if there is only one session, or the first
half of the data if there is only one session and one run.

The six datasets we used have only one channel in common: the Cz channel,
located at the top of the head. The common channel selection thus resulted in
keeping the signal from the Cz channel, and the associated covariance matrices
came down to one value, the variance of this channel. As the union of the
channels across all datasets represents 84 channels, the time series were
expanded to 84 channels after ComImp, and the expanded covariance matrices
after DT were of size $84\times 84$. For both interpolation methods, we set
the final positions to which all epochs across all datasets were interpolated
to the following 17 channels: [Fp1, Fp2, F7, F3, Fz, F4, F8, C3, Cz, C4, P3,
Pz, P4, T3, T4, T5, T6]. The regularization term of the SSI was set to
$1\mathrm{e}{-7}$ and the one of the FI to $1\mathrm{e}{-3}$. For all methods,
we used as classifier a logistic regression from Scikit-Learn with a L2
regularization set to $C=1$.

In addition, we employed a subject-specific calibration procedure to estimate
the upper bound of achievable performance. Here we use a fraction of the
target subject’s data as part of the training set. This was achieved by
splitting the target subject’s data into two halves, utilizing the first half
for training and the second for evaluation. Consequently, this yielded a
single calibration accuracy value for each subject.

###  IV-C Leave-one-dataset-out validation

We evaluated the dimension-matching methods using a leave-one-data-out scheme.
We first performed this evaluation with an increasing number of target
channels seen in the training set by increasing the number of training
datasets. In a second step, five of the six datasets were combined to form the
training set, including all of their subjects. Each subject of the left-out
dataset was used as a test set, resulting in one performance value per subject
and method. This procedure was repeated six times so that each dataset was
left out once. To statistically evaluate the difference in performance between
SSI and FI, we performed a Wilcoxon signed-rank test on the classification
accuracies obtained from ingle-trial predictions per method.

###  IV-D Results

Results for the three datasets with the most subjects are shown in Figure 3.
The first row (A) illustrates the classification accuracy difference of each
subject of the target dataset as a function of the number of target channels
present in the training datasets. The difference was made by subtracting the
FI accuracy to other methods, subject per subject. For BNCI2014_001 and
PhysionetMI, ComImp and DT reach lower accuracies than FI with few target
channels seen during training. When more target channels are seen in train,
source free methods perform similarly to source dependent methods, with
accuracies comparable to those of the calibration (purple box on row (B). For
Shin2017A, FI consistently outperforms all other methods, especially ComImp,
DT and common channel selection. The reason is that Shin2017A shares very few
channels with the other datasets, and these channels are not located near the
motor cortex. The boxplots of the second row (B) correspond to the last point
of the learning curves, for which five of the datasets were used as training
set. The methods are sorted according to whether they require access to target
labels (supervised), source data (source dependent), or nothing (source free).
For BNCI2014_001 and PhysionetMI, interpolation methods performed similarly to
source dependent methods and calibration. For Shin2017A, the observations are
the same as on the learning curve. Out of all six datasets, the FI led to
accuracies significantly higher than the SSI for four datasets with p-values
$p\leq 5\mathrm{e}{-2}$. In addition, interpolation methods were faster to
compute than ComImp and DT due to the smaller size of the dimension matched
data (17 channels for interpolation compared to 84 for ComImp and DT).
Overall, it is important to note that FI achieved similar or better accuracies
than ComImp and DT with less information.

##  V Conclusion

In this work, we propose a physics-informed, unsupervised, and source free
domain adaptation approach for EEG analysis, specifically addressing
challenges arising from varying electrode configurations. Leveraging the
underlying physics of EEG signals with field interpolation led to performance
similar to supervised and source dependent approaches when a large variety of
data is available. Our approach showed to be better than other methods when
the training data included limited target channels. In addition, interpolation
is applied to the raw data before any feature extraction. It can therefore be
flexibly used with different EEG pipelines and is not confined to the
covariance framework.

## References

  * [1] E. Niedermeyer and F. L. da Silva, Electroencephalography: basic principles, clinical applications, and related fields.  Lippincott Williams & Wilkins, 2005.
  * [2] M. Perslev, S. Darkner, L. Kempfner, M. Nikolic, P. J. Jennum, and C. Igel, “U-sleep: resilient high-frequency sleep staging,” NPJ digital medicine, vol. 4, no. 1, p. 72, 2021.
  * [3] L. A. Gemein, R. T. Schirrmeister, P. Chraba̧szcz, D. Wilson, et al., “Machine-learning-based diagnostics of eeg pathology,” NeuroImage, vol. 220, p. 117021, 2020.
  * [4] M. Clerc, L. Bougrain, and F. Lotte, Brain-Computer Interfaces 2.  Wiley-ISTE, 2016.
  * [5] J. Dockès, G. Varoquaux, and J.-B. Poline, “Preventing dataset shift from breaking machine-learning biomarkers,” GigaScience, vol. 10, no. 9, p. giab055, 2021.
  * [6] T. Tveitstøl, M. Tveter, A. S. Pérez Teseyra, et al., “Introducing region based pooling for handling a varied number of eeg channels for deep learning models,” Frontiers in Neuroinformatics, vol. 17, p. 1272791.
  * [7] “2021 beetl competition: Advancing transfer learning for subject independence and heterogenous eeg data sets,”
  * [8] A. Mellot, A. Collas, P. L. C. Rodrigues, D. Engemann, and A. Gramfort, “Harmonizing and aligning M/EEG datasets with covariance-based techniques to enhance predictive regression modeling,” Imaging Neuroscience, vol. 1, pp. 1–23, 12 2023.
  * [9] D. Truong, M. A. Khalid, and A. Delorme, “Deep learning applied to eeg data with different montages using spatial attention,” arXiv preprint arXiv:2310.10550, 2023.
  * [10] P. L. Rodrigues, M. Congedo, and C. Jutten, “Dimensionality transcending: a method for merging bci datasets with different dimensionalities,” IEEE Transactions on Biomedical Engineering, vol. 68, no. 2, pp. 673–684, 2020.
  * [11] O. Ledoit and M. Wolf, “A well-conditioned estimator for large-dimensional covariance matrices,” Journal of multivariate analysis, vol. 88, no. 2, pp. 365–411, 2004.
  * [12] W. Förstner and B. Moonen, “A metric for covariance matrices,” Geodesy-the Challenge of the 3rd Millennium, pp. 299–309, 2003.
  * [13] A. Barachant, S. Bonnet, M. Congedo, and C. Jutten, “Multiclass brain–computer interface classification by riemannian geometry,” IEEE Transactions on Biomedical Engineering, vol. 59, no. 4, pp. 920–928, 2012.
  * [14] O. Yair, M. Ben-Chen, and R. Talmon, “Parallel transport on the cone manifold of spd matrices for domain adaptation,” IEEE Transactions on Signal Processing, vol. 67, no. 7, pp. 1797–1811, 2019.
  * [15] P. L. C. Rodrigues, C. Jutten, and M. Congedo, “Riemannian procrustes analysis: Transfer learning for brain–computer interfaces,” IEEE Transactions on Biomedical Engineering, vol. 66, no. 8, pp. 2390–2401, 2018.
  * [16] T. Nguyen, R. Khadka, N. Phan, A. Yazidi, P. Halvorsen, and M. A. Riegler, “Combining datasets to increase the number of samples and improve model fitting,” arXiv preprint arXiv:2210.05165, 2022.
  * [17] F. Pedregosa et al., “Scikit-learn: Machine Learning in Python ,” Journal of Machine Learning Research, vol. 12, pp. 2825–2830, 2011.
  * [18] F. Perrin, J. Pernier, O. Bertrand, and J. Echallier, “Spherical splines for scalp potential and current density mapping,” Electroencephalography and Clinical Neurophysiology, vol. 72, no. 2, pp. 184–187, 1989.
  * [19] A. Gramfort et al., “MEG and EEG data analysis with MNE-Python,” Frontiers in Neuroscience, vol. 7, no. 267, pp. 1–13, 2013.
  * [20] M. S. Hämäläinen and R. J. Ilmoniemi, “Interpreting magnetic fields of the brain: minimum norm estimates,” Medical & biological engineering & computing, vol. 32, pp. 35–42, 1994.
  * [21] B. Aristimunha, I. Carrara, P. Guetschel, S. Sedlar, P. Rodrigues, et al., “Mother of all BCI Benchmarks,” 2023.


# Universal Dependency Treebank for Odia Language

###### Abstract

This paper presents the first publicly available treebank of Odia, a
morphologically rich low resource Indian language. The treebank contains
approx. 1082 tokens (100 sentences) in Odia selected from “Samantar”, the
largest available parallel corpora collection for Indic languages. All the
selected sentences are manually annotated following the “Universal Dependency
(UD)” guidelines. The morphological analysis of the Odia treebank was
performed using machine learning techniques. The Odia annotated treebank will
enrich the Odia language resource and will help in building language
technology tools for cross-lingual learning and typological research. We also
build a preliminary Odia parser using a machine learning approach. The
accuracy of the parser is 86.6% Tokenization, 64.1% UPOS, 63.78% XPOS, 42.04%
UAS and 21.34% LAS. Finally, the paper briefly discusses the linguistic
analysis of the Odia UD treebank.

Keywords: Universal Dependency, Odia UD Treebank, UPOS tags

languageresourceLanguage Resources

Universal Dependency Treebank for Odia Language

Shantipriya Parida1, Kalyanamalini Sahoo2, Atul Kr. Ojha3,
---
Saraswati Sahoo4, Satya Ranjan Dash5 and Bijayalaxmi Dash6
1Silo AI, Helsinki, Finland
2University of Lille, France
3Insight Centre for Data Analytics, DSI, NUI, Galway, Ireland
4Institute of Mathematics and Applications, India
5KIIT University, Bhubaneswar, India
6Ravenshaw University, Cuttack, India
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

Abstract content

## 1\. Introduction

Odia (earlier known as Oriya) is an Indian language belonging to the Indo-
Aryan branch of the Indo-European language family. It is the predominant
language of the Indian state of Odisha. Odia is written in Odia script, which
is a Brahmic script. There are 37 million Odia speakers in
India.111https://censusindia.gov.in/2011Census/Language_MTs.html Odia is one
of the many official languages of India and is designated as a Classical
language.

Odia is an agglutinative language [Sahoo, 2001], and hence, a morphologically
rich language. Odia’s verb morphology is rich with a three-tier tense system,
person, number, and honorific markers. The prototypical word order is subject-
object-verb (SOV) [Parida et al., 2020a, Parida et al., 2020b]. Odia nominal
morphology differentiates between plural and singular numbers; case marking on
nouns; first, second, and third-person pronouns. But it does not have
grammatical gender marking, which reduces the complexities of learning the
language. Odia language allows Noun-verb, Adjective-verb, and Verb-verb
compounding but does not allow elision. It has 28 consonants, 6 vowels, 9
diphthongs, and 4 semivowel phonemes. Most vowels can be short or long, and
care must be taken to remember that the length of the vowel changes the word
meaning completely. Odia’s vocabulary is influenced by Sanskrit and also a
little influence from Arabic, Persian, and Austronesian languages as the
Kalinga empire (Odisha’s ancient name) was connected to different other
kingdoms.222https://www.nriol.com/indian-languages/oriya-page.asp Odia
language lacks online content and resources for natural language processing
(NLP) research.

Unlike Treebanks of widely accepted languages such as English, Mandarin,
Hindi, and Spanish for Natural Language Processing applications, applications
based on low resource language like Odia is stagnated due to low resources.
This paper is one step toward providing resources for such a low resource
language. To start with we have worked on making a treebank in the Odia
language. This project will surely help the Odia community and NLP researchers
in providing resources for NLP applications.

## 2\. Odia Language Grammar

Odia is an SOV language. Usually, a simple sentence begins with a subject and
ends with a finite verb. The major word classes found in Odia are nouns,
pronouns, verbs, adjectives, and postpositions. Certain minor categories like
classifiers, complementizers, and conjunctions are also found. The objects
occur between the subject and the verb, the Indirect Object precedes the
Direct Object. The modifier precedes the item it modifies: the adjective
precedes the substantive it qualifies, and the adverb precedes the verb.
Although scrambling is allowed, usually, the word-order sticks to the V-final
constructions except for poetic inversion [Sahoo, 2001].

### Declension

Odia has two numbers: singular and plural; and three persons: 1st person, 2nd
person, and 3rd person. The subject NP agrees with the verb in person, number,
and honorific. Honorificity goes along with person and number and it is marked
in various word classes like nouns, pronouns, verbs, and, interestingly
enough, with some of the post-positions that function as genitive, locative,
and ablative markers. Generally, the person-number suffixes also go together.

There are eight cases in Odia: nominative, accusative, instrumental, dative,
ablative, genitive, locative, and vocative. Except for the nominative case,
all the other cases are marked morphologically.

Phonologically, there is no distinction in the form of a word in masculine,
feminine, or neuter gender in Odia. E.g. pua ‘son’ (masc), jhia ‘daughter’
(fem), phaLa ‘fruit’ (neuter). But there are certain cases, where one finds
such differences between the masculine and the feminine form of the words
phonologically. E.g. chhaatra ‘male student’, chhaatri ‘female student’.

### Pronouns

Odia pronouns are shown in Figure 1.

(Sahoo, 2001)

Figure 1: Odia Pronouns

  * •

Personal: mun ‘I’, tu ‘you’, tume ‘you’, aapaNa ‘you’, se ‘she’ / ‘he’

  * •

Reflexive: se nije ‘he himself / she herself’

  * •

Reciprocal: paraspara ‘each other’

  * •

Correlative: jie ‘who (ever)’ —se ‘he’ / ‘she’

  * •

Relative: je ‘whoever’, jaahaaku ‘whomsoever’

  * •

Demonstrative: eha / ehi ‘this’, eguDika / eguDaaka ‘these’, sehi ‘that’ and
seguDika / seguDaaka ‘those’

  * •

Distributive: pratyeka ‘each’ / ‘every’

  * •

Universal: samaste ‘all’

  * •

Existential: jaNe ‘one person’, goTe ‘a’/ ‘one’

  * •

Interrogative: kie ‘who’, kaahaaku ‘whom’,’

  * •

Compound: kehi jaNe / kie jaNe ‘somebody’

### Case morphemes

Odia case morphemes are shown in Table 1.

Case |  Singular |  Plural/[+Hon] sg
---|---|---
Nominative (NOM) |  - |  -e
Accusative (ACC) |  ku |  nku, maananku
Instrumental (INST) |  re, dwaaraa, dei |  re, dwaaraa, dei
Dative (DAT) |  ku |  nku, maananku
Ablative (ABL) |  ru, Thaaru |  MaanankaThaaru
Genitive (GEN) |  ra |  nkara, maanankara
Locative (LOC) |  re, Thaare |  MaanankaThaare
Vocative (VOC) |  he, bho |
Table 1: The Case morphemes in Odia

### Postpositional words

The following postpositional words are used to express different case
relations.

  * •

aagare ‘before’

  * •

pare ‘after’

  * •

kari ‘by’

  * •

nimitte ‘for

  * •

parjyante ‘up to’

  * •

paain ‘for’

  * •

prati ‘to’, ‘against’

  * •

baahaara ‘out’, ‘outside’

  * •

byatita ‘without’

  * •

binaa ‘without’

  * •

boli ‘because of’, ‘literally speaking’, e.g. goli boli goTe pilaa thilaa
‘there was a child called Goli’

  * •

bhitare ‘in’, ‘inside’

  * •

majhire ‘inside’, ‘in the midst of’

  * •

laagi ‘for’ e.g. raatidina laagi ‘for day and night’

  * •

sahite ‘with’

### Conjunctions

Conjunction markers include o / eban / aau ‘and’, kimbaa / abaa/athabaa ‘or’,
madhya ‘also’, tathaapi ‘still’, kintu ‘but’ etc.

### Classifiers

A classifier is a noun-related element but has no independent nominal reading.
Having insufficient referential or predicative content, it is not fully
lexical. -Taa ‘one[+def]’, Topaa ‘drop’, muThaa ‘fist’, gochhaa ‘bundle’, jaNa
‘one[+Human]’, paTa ‘slice’, asaraa ‘shower’, menchaa, etc. are usually are
identified as classifiers.

### Complex verbs

Complex verb constructions like the combination of a verbal with a nominal
(N-V sequences), and the combination of a verbal with a verbal (V-v sequences)
are found in Odia.

### Serial verbs

Odia is a verb serializing language. A series of verbs along with their
complements and adjuncts (if any) can occur in a single clause having a common
subject. Very often, the series of verbs have a common object too.

### Verbal Nouns

Many verbal nouns are found in Odia, such as chaasa ‘ploughing’, chaaDa
‘release’, maajaNaa ‘bath’, rahaNi ‘stay’ bikaa ‘selling’, baahuDaa ‘return’.
Some verbal nouns have been borrowed from Sanskrit, e.g. anubhaba ‘feeling’,
bidroha ‘revolution’, prabesha ‘entrance’, sthiti ‘existence’, etc. which are
used along with a light verb in Odia.

### Copular sentences

Copular constructions are usually sentences with a subject and a predicate.
The predicate may be either a noun (nominal predicate) or an adjective
(adjectival predicate).

### Adverbs

Like English, Odia also has Time, Place, and Manner adverbials.

### Finite Verbal Forms

Agreement features contribute to the finiteness of a verbal form in Odia. All
the finite verbal forms have an agreement in concord with the subject NP. The
agreement features of the verbal form are marked for the person, number, and
honorific of the subject NP.

### The Infinitive

In Odia, the infinitival form is realized by the verbal ending – ibaaku ‘to
do’.

### The Conditional affix -ile (or –le)

The morpheme -ile (or –le) functions as a conditional marker. It is suffixed
to the bare verbal root. It is nonfinite as it does not carry any Agr feature
and thus can co-occur in a verbal form irrespective of person, number, or
gender of the subject.

Figure 2: Passivization with Adverbial modifier construction in UD Odia Figure
3: Finite intransitive verb construction in UD Odia Figure 4: Finite verb in
imperative sentence in UD Odia Figure 5: Main verb construction in UD Odia
Figure 6: Finite verb with Noun modifier construction in UD Odia

## 3\. Related Work

Under the leadership of IIIT-Hyderabad, a consortium was formed in 2013 to
start a project sponsored by TDIL (Government of India), called Development of
Dependency Treebank for Indian
Languages.333http://meity.gov.in/content/language-computing-group-vi This
project aimed to restore annotation work in monolingual treebanks for various
languages such as Hindi, Marathi, Bengali, Kannada, and Malayalam. To achieve
this model, the Pāṇinian Kāraka Dependency scheme was followed [Begum et al.,
2008, Husain et al., 2010, Bhat, 2017, Ojha and Zeman, 2020]. The same
annotation scheme was used to annotate data in Telugu, Urdu, and Kashmiri.

NLP research of Odia has led to development of a statistical POS tagger [Ojha
et al., 2015], neural network based POS tagger [Das and Patnaik, 2014], POS
tagging using Support Vector Machine (SVM) [Das et al., 2015], a shallow
parsing tool 444http://calts.uohyd.ac.in/calts/sptil-parser.html, and English-
Odia machine translation system [Parida et al., 2020a].

Within the Universal Dependencies framework, as of UD release 2.8, treebanks
and parsers are available for Bhojpuri, Hindi, Marathi, Sanskrit, Tamil,
Telugu and Urdu [Zeman and et al., 2021]. Nevertheless, there is no prior work
on Odia dependency treebanking and parser.

## 4\. Data and Methodology

To collect Odia text, we used Samanantar, the largest parallel corpora
collection for 11 Indian languages [Ramesh et al., 2021]. The parallel corpora
collection includes English-Odia parallel text that covers many domains. We
selected the Odia sentences of word length between 5 to 15 words per sentence.
For annotation, all selected sentences are converted into CoNLL-U format
consisting of 10 fields [Buchholz and Marsi, 2006]. The fields are “ID”,
“Word”, “Lemma”, “UPOS”, “XPOS”, “FEATS”, “HEAD”, “DEPREL”, “DEPS”, and
“MISC”. The “UPOS” tags are based on the universal POS tags
555https://universaldependencies.org/u/pos/ following the UD guidelines,
version 2. For “XPOS”, we annotated according to Bureau of Indian Standards
(BIS) Part of Speech (POS) tagset 666http://tdil-
dc.in/tdildcMain/articles/134692Draft%20POS%20Tag%20standard.pdf guideline
released by the department of information technology ministry of
communications & information technology, the government of India. The
guideline includes a POS tagset for the Odia language. The dependency
relations were marked on Universal dependency tags which is an updated version
of Stanford Dependencies [de Marneffe et al., 2014]. Out 17 UPOS tags, we use
15 UPOS tag in this dataset, while out of 37 dependency tags, we use only 24
tags (see the Table 2 & 3). The annotation task was performed by 6 native Odia
speakers including 2 linguists.

UPOS Tags | UPOS description | Statistics
---|---|---
NOUN | Noun | 570
VERB | Verb | 234
PUNCT | Punctuation | 192
PROPN | Proper noun | 170
ADJ | Adjective | 102
ADP | Adposition | 82
DET | Determiner | 75
PRON | Pronoun | 55
CCONJ | Coordinating conjunction | 48
ADV | Adverb | 45
NUM | Numeral | 26
PART | Particle | 23
AUX | Auxiliary | 13
SCONJ | Subordinating conjunction | 7
SYM | Symbol | 1
Table 2: Statistics of used UPOS Tags in the Odia treebank UD Relations | Description | Statistics
---|---|---
advmod | Adverbial modifier | 67
advmod | Locative adverbial modifier | 4
amod | Adjectival modifier of noun | 109
aux | Auxiliary verb | 9
case | Case marker | 1
cc | Coordinating conjunction | 1
ccomp | Clausal complement | 2
compound | Compound | 85
conj | Non-first conjunct | 2
cop | Copula | 1
det | Determiner | 72
fixed | Non-first word of fixed expression | 63
flat | non-first word of flat structure | 51
goeswith | Non-first part of broken word | 6
iobj | Indirect object | 72
mark | Subordinating marker | 52
nmod | Nominal modifier of noun | 287
nsubj | Nominal subject | 136
nummod | Numeric modifier | 33
obj | Direct object | 122
obl | Oblique nominal | 1
punct | Punctuation | 192
root | Root | 174
xcomp | Open clausal complement | 1
Table 3: UD relations used in Odia trebank

## 5\. Experiment and Results

As mentioned earlier, the Odia treebank was manually annotated using the UD
annotation framework. In this, we have built Odia parser on 2026 tokens using
the UDPipe open-source tool [Straka and Straková, 2017]. We conducted our
experiment in two parts. The first experiment was conducted on 50 sentences,
while the second experiment was conducted on the rest of the dataset. We used
a cross-validation 90:10 average for the data splitting where the batch size,
learning rate, and dropout were 50, 0.005, and 0.10, respectively; while the
other hyperparameters were randomized. The results are demonstrated in Table
4:

Tokenization | UPOS | XPOS | UAS | LAS
---|---|---|---|---
81.82% | 48.25% | 45.0% | 36.62% | 16.91%
86.6% | 64.1% | 63.78% | 42.04% | 21.34%
Table 4: Results of Odia Parser

Due to the small size of the data, the parser’s accuracy is very low except on
Tokenization.

## 6\. Linguistic Analysis

We are providing few sample tree constructions along with their linguistics
analysis in Figures 2, 3, 4, 6 and 5

In Figure 2, ‘karaajaaithilaa’ is a finite verb. So, it forms the root. The
adjective ‘guruttara’ modifies the noun ‘abasthaare’. The main verb has
‘taanku’ as the external argument (the subject) and ‘MKCG hospitalre’ as
internal argument (the object) of it. It has the adverbial modifier
‘prathame’.

In Figure 3, the finite intransitive verb ‘chaahinle’ ‘wanted’ is the root of
the sentence. It takes ‘shishyamaane’ ‘pupils’ as the subject argument. Being
intransitive, it does not take any object or internal argument.

In Figure 4, ‘pakaantu’ ‘put’ is the finite verb, which forms the root. Being
an imperative sentence, the subject noun is not realized, and ‘luNa o haLadi’
‘salt and turmeric’ functions as the object of the sentence. ‘taa pare’ ‘after
that’ functions as the adverbial modifier. ‘aabashyaka anujaayi’ ‘as per the
requirement’ functions as a nominal modifier for ‘luNa o haLadi’ ‘salt and
turmeric’.

In Figure 5, the main verb ‘karantu’ ‘do Pl/Honorific ‘ takes ‘aapaNa’ ‘you’
as the subject noun and ‘paaNi’ ‘water’ as the object. It is a negative
sentence, and the negative auxiliary ‘naahin’ ‘be-Neg’ occurs at the end of
the sentence. The object ‘paaNi’ ‘water’ is modified by the adjective ‘garama’
‘hot’. ‘ethipaain’ ‘because of this’ functions as the adverbial modifier for
the sentence.

In Figure 6, ‘karantu’ ‘do Pl/Honorific ‘ which is a finite verb, forms the
root of the sentence. the det ‘anya’ ‘another’ and the numeral modifier
‘eka’’one’ modify the locative modifier ‘paatrare’ ‘in a pot’. The nsubject
‘aapaNa’ ‘you Pl/Honorific ‘ is not realized in the sentence. The main verb
‘karantu’ ‘do Pl/Honorific ‘ takes ‘tela’ ‘oil’ as the object and ‘paatrare’
‘in a pot’ as the locative modifier.

## 7\. Conclusion and Future Work

We presented the first UD Odia treebank aimed for linguistic research and
applications in NLP, primarily for POS tagging, parser, semantic analyzer, and
machine translation. Also, we built a preliminary Odia parser using the UDPipe
tool. The accuracy of the Odia parser is 86.6% Tokenization, 64.1% UPOS,
63.78% XPOS, 42.04% UAS and 21.34% LAS.

Future research direction includes: i) enrich the Odia treebank with more
annotated data for training, development, and validation, ii) including lemma
for the Odia tokens, iii) perform detail morphological analysis, and iv)
experiment with neural network based models for performance evaluation.

## 8\. Acknowledgements

Atul Kr. Ojha would like to acknowledge the EU’s Horizon 2020 Research and
Innovation programme through the ELEXIS project under grant agreement No.
731015.

## 9\. References

## References

  * Begum et al., 2008 Begum, R., Husain, S., Dhwaj, A., Sharma, D. M., Bai, L., and Sangal, R.  (2008).  Dependency annotation scheme for Indian languages.  In Proceedings of the Third International Joint Conference on Natural Language Processing: Volume-II.
  * Bhat, 2017 Bhat, R. A.  (2017).  Exploiting linguistic knowledge to address representation and sparsity issues in dependency parsing of Indian languages.  Ph.D. thesis, PhD thesis, International Institute of Information Technology, India.
  * Buchholz and Marsi, 2006 Buchholz, S. and Marsi, E.  (2006).  Conll-x shared task on multilingual dependency parsing.  In Proceedings of the tenth conference on computational natural language learning (CoNLL-X), pages 149–164.
  * Das and Patnaik, 2014 Das, B. R. and Patnaik, S.  (2014).  A novel approach for odia part of speech tagging using artificial neural network.  In Proceedings of the International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA) 2013, pages 147–154. Springer.
  * Das et al., 2015 Das, B. R., Sahoo, S., Panda, C. S., and Patnaik, S.  (2015).  Part of speech tagging in odia using support vector machine.  Procedia Computer Science, 48:507–512.
  * de Marneffe et al., 2014 de Marneffe, M.-C., Dozat, T., Silveira, N., Haverinen, K., Ginter, F., Nivre, J., and Manning, C. D.  (2014).  Universal Stanford dependencies: A cross-linguistic typology.  In Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), pages 4585–4592, Reykjavik, Iceland, May. European Language Resources Association (ELRA).
  * Husain et al., 2010 Husain, S., Mannem, P., Ambati, B. R., and Gadde, P.  (2010).  The ICON-2010 tools contest on Indian language dependency parsing.  Proceedings of ICON-2010 Tools Contest on Indian Language Dependency Parsing, ICON, 10:1–8.
  * Ojha and Zeman, 2020 Ojha, A. K. and Zeman, D.  (2020).  Universal Dependency Treebanks for Low-Resource Indian Languages: The Case of Bhojpuri.  In Proceedings of the WILDRE5–5th Workshop on Indian Language Data: Resources and Evaluation, pages 33–38.
  * Ojha et al., 2015 Ojha, A. K., Behera, P., Singh, S., and Jha, G. N.  (2015).  Training & evaluation of pos taggers in indo-aryan languages: a case of hindi, odia and bhojpuri.  In the proceedings of 7th Language & Technology Conference: Human Language Technologies as a Challenge for Computer Science and Linguistics, pages 524–529.
  * Parida et al., 2020a Parida, S., Bojar, O., and Dash, S. R.  (2020a).  Odiencorp: Odia–english and odia-only corpus for machine translation.  In Smart Intelligent Computing and Applications, pages 495–504. Springer.
  * Parida et al., 2020b Parida, S., Dash, S. R., Bojar, O., Motlicek, P., Pattnaik, P., and Mallick, D. K.  (2020b).  OdiEnCorp 2.0: Odia-English parallel corpus for machine translation.  In Proceedings of the WILDRE5– 5th Workshop on Indian Language Data: Resources and Evaluation, pages 14–19, Marseille, France, May. European Language Resources Association (ELRA).
  * Ramesh et al., 2021 Ramesh, G., Doddapaneni, S., Bheemaraj, A., Jobanputra, M., AK, R., Sharma, A., Sahoo, S., Diddee, H., Kakwani, D., Kumar, N., et al.  (2021).  Samanantar: The largest publicly available parallel corpora collection for 11 indic languages.  arXiv preprint arXiv:2104.05596.
  * Sahoo, 2001 Sahoo, K.  (2001).  Oriya verb morphology and complex verb constructions.  NTNU Trondheim.
  * Straka and Straková, 2017 Straka, M. and Straková, J.  (2017).  Tokenizing, POS tagging, lemmatizing and parsing UD 2.0 with UDPipe.  In Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 88–99.
  * Zeman and et al., 2021 Zeman, D. and et al.  (2021).  Universal dependencies 2.8.1.  LINDAT/CLARIAH-CZ digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University.