Yuzhou Chen
email: yuzhouc@smu.edu

Yulia R Gel

Konstantin Avrachenkov
email: k.avrachenkov@inria.fr

LFGCN: Levitating over Graphs with Levy Flights

Keywords: semi-supervised learning, convolutional networks, Lévy flights, local graph topology

Due to high utility in many applications, from social networks to blockchain to power grids, deep learning on non-Euclidean objects such as graphs and manifolds, coined Geometric Deep Learning (GDL), continues to gain an ever increasing interest. We propose a new Lévy Flights Graph Convolutional Networks (LFGCN) method for semi-supervised learning, which casts the Lévy Flights into random walks on graphs and, as a result, allows both to accurately account for the intrinsic graph topology and to substantially improve classification performance, especially for heterogeneous graphs. Furthermore, we propose a new preferential P-DropEdge method based on the Girvan-Newman argument. That is, in contrast to uniform removing of edges as in DropEdge, following the Girvan-Newman algorithm, we detect network periphery structures using information on edge betweenness and then remove edges according to their betweenness centrality. Our experimental results on semi-supervised node classification tasks demonstrate that the LFGCN coupled with P-DropEdge accelerates the training task, increases stability and further improves predictive accuracy of learned graph topology structure. Finally, in our case studies we bring the machinery of LFGCN and other deep networks tools to analysis of power grid networks -the area where the utility of GDL remains untapped.

I. INTRODUCTION

Adaptation of deep learning (DL) to graphs and other non-Euclidean objects has recently witnessed an ever increasing interest, leading to the new subfield of geometric deep learning (GDL). In particular, geometric deep learning is an emerging direction in machine learning which generalizes concepts of deep learning for data in non-Euclidean spaces, e.g., graphs and manifolds, by bridging the gap between graph theory and deep neural networks [START_REF] Bronstein | Geometric deep learning: going beyond euclidean data[END_REF][START_REF] Monti | Geometric deep learning on graphs and manifolds using mixture model cnns[END_REF][START_REF] Monti | Geometric deep learning[END_REF].

Many such DL approaches for non-Euclidian objects are based on the idea of a convolution operation in the spectral domain with a suitably chosen nonlinear trainable filter [see an overview by 4]. As a result, node features are mapped into some Euclidian space. Next, graph filters are approximated with various finite order polynomials, e.g., Chebyshev polynomials [i.e., the ChebNet model family of [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF][START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF], Cayley transform [i.e., CayleyNet of 7] or the generalization of polynomial filters in a form of Auto-Regressive Moving Average (ARMA) models [START_REF] Bianchi | Graph neural networks with convolutional arma filters[END_REF]. However, deep learning approaches based on approximation with finite order polynomials tend to be non-robust to even minor changes in the graph structure and to largely disregard the local graph topology which often plays the critical role for learning on heterogeneous graphs. In contrast, as noted by [START_REF] Bianchi | Graph neural networks with convolutional arma filters[END_REF], one of the primary benefits of the ARMA filters over polynomial ones is that ARMA filters are not computed in the Fourier space induced by a graph Laplacian, and as a result, ARMA filters are local in the node space and enable to more flexibly and accurately capture the underlying graph topology.

Further advancing the localized approaches in GDL, we propose a new fractional generalized graph-based convolutional filter for semi-supervised learning which casts the Lévy Flights into random walks on graphs. As a result, our new Lévy Flights Graph Convolutional Network (LFGCN) method allows to more accurately account for the intrinsic local graph topology and to substantially improve classification performance, especially for heterogeneous graphs.

To fly or not to fly, and if to fly, why take a Lévy Flight? Lévy Flight is a random process with a scale-free, Lévy stable jump length distribution. Due to the scale-free character, throughout the graph exploration we move randomly according to a power-law distribution for hops, rather than with integer hops as in a standard random walk. As a result, Lévy Flight delivers more accurate and efficient search strategies, especially, in sparse environments, comparing to other types of random walks [START_REF] Riascos | Long-range navigation on complex networks using lévy random walks[END_REF]. While superiority of Lévy Flights as a primary search strategy has been proven in a broad range of settings, utility of Lévy Flights in graph-based learning remains unexplored. Hence, Lévy Flights offer a new learning perspective with multiple advantages comparing to the currently available architectures. First, due to a fractal character, Lévy Flights combines both local graph exploration and long-range excursions, which reduces oversampling comparing to a normal random walk (i.e., lower probability to revisit the nodes we have already seen). Second, Lévy Flights allow to directly reach long-distance nodes without intervention of intermediate nodes. Third, based on average global time, Lévy Flights average return probability is of power-law distr., i.e. p γ 0 (t) ∼ t -1/2γ and is lower than average return probability of a normal random walk p 1 0 (t) ∼ t -1/2 , thereby leading to more efficient graph exploration. Forth, Lévy Flights are known to exhibit a particularly high utility for unbalanced and directed data which can explain higher LFGCN accuracy we have obtained in directed networks.

In addition, to abate over-fitting and over-smoothing in GDL, we develop a new preferential P-DropEdge method based on censoring edge order statistics at each training epoch. Our P-DropEdge idea is inspired by the recent DropEdge algorithm of [START_REF] Rong | The truly deep graph convolutional networks for node classification[END_REF] and is rooted in nonparametric methods, specifically, various censoring schemes, for statistical inference To Appear in the 2020 IEEE International Conference on Data Mining (ICDM).

arXiv:2009.02365v1 [cs.

LG] 4 Sep 2020 on order statistics [START_REF] Balakrishnan | The art of progressive censoring[END_REF]. In contrast to uniformly removing edges as in the recent DropEdge algorithm of [START_REF] Rong | The truly deep graph convolutional networks for node classification[END_REF], we follow the Girvan-Newman argument and target edges that tend to contribute more to the intrinsic graph topology. That is, we randomly remove edges with higher betweenness centrality, or the corresponding higher edge order statistics. The intuition is the following. In both P-DropEdge and DropEdge the goal is to introduce randomness in the network structure. If we are to learn international political networks with GDL, DropEdge largely tends to remove connections among individual citizens while P-DropEdge randomly censors collaboration links among Presidents and Prime Ministers. Removal of such targeted connection is likely to lead to higher perturbation effects. We investigate utility of the new P-DropEdge approach vs. DropEdge in conjunction with LFGCN and GMMN (the best performing baseline) of [START_REF] Qu | Gmnn: Graph markov neural networks[END_REF].

Significance of our contributions can be summarized as: SOTAs on all 4 considered directed networks.

• the proposed architecture of LFGCN uses three state-ofthe-art operations -gated max-average pooling, residual block, and P-DropEdge. We provide an ablation study and investigate contribution of each component to the resulting classification accuracy as well as explore sensitivity of the overall system architecture to (hyper)parameter settings. • we provide theoretical foundations behind the proposed LFGCN architecture and show that the proposed LFGCN architecture leads to significant gains in the training convergence and model output stability.

• the developed preferential P-DropEdge based on censoring of higher edge betweenness order statistics is shown to exhibit utility in other GCN methods and, hence, might be applicable in broader GDL settings. • Last but not the least, while validating our LFGCN methodology, we bring the GDL concepts to the analysis of power grid networks, i.e., the area of critical societal importance where to the best of our knowledge, the GDL machinery has never been yet applied.

II. RELATED WORK Many earlier semi-supervised learning approaches on graphs, e.g., Gaussian mixture models, co-training, harmonic function, and label propagation, tend to employ only the label information (i.e., labeled instances) for training models based on the smoothness assumption over the labels [START_REF] Zhu | Introduction to semisupervised learning[END_REF] and to largely disregard the underlying graph structure. To enhance performance, several learning methods on graphs propose to incorporate intrinsic "graph-based" information by designing a classifying function via generalizing the normalized cut and adding a smooth function with respect to the intrinsic structure [START_REF] Zhou | Learning with local and global consistency[END_REF][START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF]. An optimization framework of [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] generalizes these approaches by considering the above two methods as particular cases. However, the major criticism to these graph-based semi-supervised learning methods is that important information contained in graph edges is largely disregarded.

To address these limitations, [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] propose a formulation of convolutional neural networks (CNN) based on spectral graph theory -ChebNet. ChebNet employs approximation via finite order polynomials and is based on the Chebyshev expansion for fast filtering instead of the expensive eigen-decomposition. Graph Convolutional Networks (GCN) of [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] simplifies ChebNet while further addressing the gradient vanishing problem and reducing the number of optimization. Other related approaches to graph learning with deep neural networks include, for instance, mixture model networks (MoNet) [START_REF] Monti | Geometric deep learning on graphs and manifolds using mixture model cnns[END_REF], graph attention networks (GAT) [START_REF] Veličković | Graph attention networks[END_REF], graph convolutional recurrent networks [START_REF] Seo | Structured sequence modeling with graph convolutional recurrent networks[END_REF], dual graph convolutional networks [START_REF] Zhuang | Dual graph convolutional networks for graph-based semi-supervised classification[END_REF], FastGCN [START_REF] Chen | Fastgcn: fast learning with graph convolutional networks via importance sampling[END_REF], and simplified version of GCN [START_REF] Wu | Simplifying graph convolutional networks[END_REF]. By directly powering the graph Laplacian, GCN based on random walks such as approximate personalized propagation of neural predictions (APPNP) [START_REF] Klicpera | Predict then propagate: Graph neural networks meet personalized pagerank[END_REF], variable power network (VPN) [START_REF] Jin | Power up! robust graph convolutional network based on graph powering[END_REF], and MixHop [START_REF] Abu-El-Haija | Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing[END_REF] can learn the relationships between multiple-hops neighborhood.

To extend the success of GCN on undirected graphs to directed graphs, MotifNet of [START_REF] Monti | Motifnet: a motif-based graph convolutional network for directed graphs[END_REF] replaces the normalized Laplacian with the motif Laplacian in a multivariate polynomial filter, where the motifs information can help capture the network structure. Finally, the most recent approach of [START_REF] Bianchi | Graph neural networks with convolutional arma filters[END_REF] provides more flexible responses than GCN by using parallel and periodic concatenations of the convolutional kernel via the ARMA filter. As a result, the ARMA approach which is applicable to both directed and undirected networks allows to more accurately incorporate the underlying local graph structure into the graph learning process. For a recent comprehensive overview of GCNs see [START_REF] Wu | A comprehensive survey on graph neural networks[END_REF].

III. METHODOLOGY

Consider a graph structure G = {V, E, W }, where V is a node set with cardinality |V| of N , and E ⊆ V × V is an edge set. An N × N -matrix W with entries {ω ij } 1≤i,j≤N represents the adjacency matrix of G, that is, ω ij = 0 for any e ij ∈ E and ω ij = 0, otherwise. For an undirected graph G, W = W . In reality, however, undirected graphs are often simplified representations of complex directed networks. If G is directed, we substitute W with W = (W +W )/2.

Let Q,Q ∈ Z >0 be the number of different node features associated each node v ∈ V. Then, a N ×Q feature matrix X serves as an input to an semi-supervised learning algorithm. To classify N data points into K classes (communities), we define a N ×K label matrix Y such that Y ik = 1 if vertex i is labeled as class k, and 0 otherwise. Here we refer to each column Y •k of matrix Y as a labeling function. Finally, we define an N ×K matrix F whose columns F •k are referred to as classification functions.

A. Graph signal processing

Given the adjacency matrix W of G, let D be the degree matrix where d ii = N j=1 w ij and L = U ΛU be the Standard Laplacian matrix. Here Λ = diag(λ 0 ,...,λ N -1 ) and U = [u 0 ,...,u N -1 ] is the matrix of eigenvectors.

In the following, we will revisit three popular semisupervised learning methods -graph-based semi-supervised learning, fractional graph-based semi-supervised learning, and graph convolutional networks and gain new insights for improving their modeling capabilities.

Graph-based semi-supervised learning Graph-based semi-supervised learning (G-SSL) has received much attention as an alternative approach to the population paradigm of supervised learning in recent years. G-SSL develops a generalized optimization framework, which has three particular cases (i) the Standard Laplacian (SL); (ii) Normalized Laplacian (NL); (iii) PageRank (PR). The general idea of graph-based semi-supervised learning (G-SSL) is based on two widely used optimization frameworks. The first formulation, the SL based formulation [START_REF] Zhou | Spectral clustering and transductive learning with multiple views[END_REF] as follows:

min F    N i=1 N j=1 w ij F i. -F j. 2 +µ N i=1 d i F i. -Y i. 2   
, where d ii is (i, i)-element in degree matrix D and w ij represents the edge weight for edge e ij in adjacency matrix W .

For the second formulation, the NL based formulation [START_REF] Zhou | Learning with local and global consistency[END_REF], is as follows:

min F    N i=1 N j=1 w ij F i. √ d ii - F j. d jj 2 +µ N i=1 F i. -Y i. 2   
The following lemma [START_REF] Avrachenkov | Generalized optimization framework for graph-based semi-supervised learning[END_REF] asserts that the generalized optimization framework, i.e., G-SSL, which has as particular cases the two above mentioned formulations: Lemma 1. Let σ denote an alternative parameter on the power of degree matrix D whose entries are the degrees d ii ; and let 0 ≤ σ ≤ 1. Then

min F N i=1 N j=1 w ij d σ-1 ii F i. -d σ-1 jj F j. 2 +µ N i=1 d 2σ-1 ii F i. -Y i. 2 .
The classification functions for the generalized semi-supervised learning are given by F

•k = (1-α) I -αD -σ W D σ-1 -1 Y •k .
Proof of Lemma 1 is in Appendix VII. The optimization formulation S(F ) with the following expression:

S(F ) = min F 2F T •k D σ-1 LD σ-1 F •k (1) + µ(F •k -Y •k ) T D 2σ-1 (F •k -Y •k ) ,
where µ is a regularization parameter. Minimization of the 1st term in (1) corresponds to the idea that if two nodes are close in graph with respect to some metric, they should belong to the same class; and by minimizing the 2nd term we aim to bring the classification function F •k as close as possible to the labeling function Y •k . Eq. ( 1) allows us to obtain the Standard Laplacian based formulation (σ = 1), the Normalized Laplacian formulation (σ = 0.5), and PageRank formulation (σ = 0).

Objective of the generalized optimization framework for G-SSL is a convex function and the corresponding classification function:

F •k = 1-α I -αD -σ W D σ-1 Y •k , α = 2 2+µ ,1 ≤ k ≤ K. (2)
By tuning the parameter σ on the power of degree matrix D, we can obtain three mentioned above particular semi-supervised learning methods:

σ = 1 -SL : F •k = (1-α) I -αD -1 W -1 Y •k , σ = 1 2 -NL : F •k = (1-α) I -αD -1 2 W D -1 2 -1 Y •k , σ = 0 -PR : F •k = (1-α) I -αW D -1 -1 Y •k .
From above formulations, classification function F is a closed form solution based on the theory of random walks on graphs, which in turn provides connection to the probabilistic interpretation of G-SSL. Parameter α controls the strength of the ground truth label matrix Y in the generalized optimization framework.

Fractional graph-based semi-supervised learning To improve classification performance (in particular, fuzzy graphs and unbalanced labeled data) of G-SSL, fractional graph-based semi-supervised learning [START_REF] De Nigris | Fractional graph-based semi-supervised learning[END_REF] embeds Lévy Flights into random walks on graphs by constructing from powers of the Laplacian matrix, i.e., the L γ operator. This operation can be used to generate different transition probabilities (i.e., corresponding to stochastic adjacency matrix) based on different γ values. Intuitively, embedding Lévy Flights into random walks allows for better capturing mixing properties (i.e., dependence) in the data. Based on a fractional Laplacian matrix, 0 < γ ≤ 1, the anomalous (fractional) diffusion processes on networks can be constructed from the spectra data and eigenvectors of the Laplacian matrix. The fractional powers of L allows Lévy random walks with long-range navigation on a network. For example, the long-range transitions on a network can directly move node u and node v with the transition probability m (γ) u→v through a random walker, where m (γ) u→v is an element in the fractional transition matrix M (γ) . Transition probability m (γ) u→v between any two nodes whose geodesic distance is not infinite can be summarized as follow:

m (γ) u→v = δ uv -(L γ ) uv /k (γ) u , (3)
where δ uv is the Kronecker delta, k

u denotes the fractional degree of the node u and k (γ) u ≡ (L γ ) uu . Eq. ( 3) provides transition probabilities for the Lévy Flights. Unlike the standard random walk, the Lévy Flights can jump immediately over several hops in a graph. This feature enables Lévy Flights to be a very effective graph exploratory process. Lemma 2 makes this statement formal. Proof of Lemma 2 is in Appendix VIII. There is a price to pay for this: the typically sparse transition probability matrix becomes non-sparse. We can mitigate non-sparsity by taking a reasonable number of principal singular eigenvectors or limiting the number of terms in the Taylor expansion. Through replacing the L operator with L γ = U Λ γ U , the new optimization formulation S * (F ) leaves us with the following expression:

S * (F ) = min F 2F T •k D σ-1 γ L γ D σ-1 γ F •k (4) + µ(F •k -Y •k ) T D 2σ-1 γ (F •k -Y •k ) ,
where

(D γ ) ii = (L γ ) ii .
Let 0 < γ ≤ 1, then the closed form solution for (4) can be obtain as follows:

F •k = (1 -α) I -αD -σ γ W γ D σ-1 γ -1 Y •k ,
for k = 1,...,K. Therefore, we can conclude three particular fractional semi-supervised learning methods like G-SSL:

σ = 1 -FSL : F •k = (1-α) I -αD -1 γ W γ -1 Y •k , σ = 1 2 -FNL : F •k = (1-α) I -αD -1 2 γ W γ D -1 2 γ -1 Y •k , σ = 0 -FPR : F •k = (1-α) I -αW γ D -1 γ -1 Y •k .

B. Proposed Lévy Flights Graph Convolutional Network for semi-supervised node classification

Although both G-SSL and fractional G-SSL achieve comparable and consistent (low variance) performance on some datasets, e.g., Les Miserables, Wikipedia-math, and MNIST, these approaches consider only the given adjacency matrix W and the label matrix Y , without using the feature matrix X. This limitation is crucial, especially when dealing with datasets that not only exhibit a sophisticated topological graph structure but also provide node feature information, such as citation, biological, financial, and power grid networks. To address this limitation, there have been recently proposed many graph-based neural networks methods, e.g., graph convolutional networks (GCN), which use the feature matrix X instead of the label matrix Y and encode the graph structure by using neural network framework. Such graph-based neural networks have been shown to achieve impressive gains in semi-supervised learning performance on graphs. Next, we turn to discussing on how the idea of Lévy Flights can be incorporated to GCN, leading to the new Lévy Flights Graph Convolutional Network (LFGCN) for semi-supervised node classification.

Lévy Flights Graph Convolutional Network (LFGCN) The key idea behind our proposed method is Fractional Generalized Sigma-based (FGS) filter

g F GS (α,σ,γ) = 1-α I -αD -σ γ W γ D σ-1 γ = 1-α I -α L .
To avoid the inverse computations, we insert the Taylor series expansion into the FGS filter, resulting in:

g F GS (α,σ,γ) = (1-α) ∞ i=0 α L i , 0 < α,σ,γ ≤ 1. (5)
Empirically, it shows that i = 4α is enough to get a good approximation. We then obtain the general classification function by multiplying (5) by the feature matrix X:

X = g F GS (α,σ,γ)X (6) = (1-α) X the 1st item + α LX the 2nd item + α 2 L2 X the 3rd item +••• , = (1-α)(X ) i where (X ) i = X +α L(X ) i-1 , (X ) 0 = X, i ∈ Z i≥0 .
Convolutional layer During LFGCN training, the convolutional model needs to train parameters (W,b) of the graph filter, where the trainable graph filter scan the given input feature matrix into a series of feature maps with neurons. Thereby, we provide an implementation of (6) as a FGS convolutional layer:

H (t+1) = σ (1-α) ∞ i=0 α L i H (t) W (t) , (7)
where H (t+1) is the hidden layer output matrix of activations in the t-th layer and H (0) = X, σ(•) is the adopted activation function, and W t is the trainable weight in the t-th layer. Furthermore, we bring the concept of the parallel system (PS) from the reliability theory to improve the consistency of our proposed method. A parallel system is a configuration such that the entire system functions as long as not all involved components in the system fail. Hence, the parallel system structure is more robust against noisy inputs, compared to a single system structure.

Lemma 3. Let XF GS be the output matrix P 1 from a pooling layer. Let U = {1,2,...,N } be a finite population such that each unit i,i ∈ U is associated with an output matrix X (i)

F GS , i = 1,...,N . Then Var( XF GS ) = (1-n/N )S 2 /n, n < N,n ∈ Z >0 , where S 2 = N i=1 X (i) F GS -XU F GS 2 /(N -1).
Suppose there are n components in a parallel system, with the probability of non-failure P (i) R (where i = 1,••• ,n) in a parallel system, then the reliability of this parallel system P P S R can be obtained with the following expression:

P P S R = 1- n i=1 (1-P (i) R ).
Proof of Lemma 3 is in Appendix IX. According to Lemma 3, the introduced concept of a parallel system allows for enhancing stability and reducing estimation variance up to order of n (i.e., Var( XF GS ) = O(S 2 /n)). In this way, we establish both theoretical and practical guarantees for our proposed model to reach stable over a large set of hyperparameters, small datasets, and noisy labels based on this parallel implementation.

Pooling layer When implementing the form of pooling operation to aggregate information from the outputs of parallel FGS convolutional layer, instead of using some popular pooling functions such as max and average pooling, we apply the state-of-the-art pooling operation -gated max-average pooling [START_REF] Lee | Generalizing pooling functions in convolutional neural networks: Mixed, gated, and tree[END_REF] to capture the local and global information from all the nodes and graph structure. The rationale behind the gated max-average pooling, is that it considers "responsive" strategy (i.e., improving translation invariance and scale

f gated (X F GS ) = σ W X F GS f max (X F GS ) + 1-σ W X F GS f avg (X F GS ),
where W is the trainable weight matrix, X F GS is the output matrix from the parallel FGS convolutional layer after concatenation operation.

Residual building block Inspired by the seminal works of [START_REF] Hamilton | Inductive representation learning on large graphs[END_REF][START_REF] Liu | Geniepath: Graph neural networks with adaptive receptive paths[END_REF] that implemented residual learning in a graph convolutional network, we apply a residual block (RB) by adding the skip connection after the pooling layer. One of the advantages of the residual learning is the identity mapping which provides a direct path for propagating information. When using the residual building block, we adopt a similar scheme as [START_REF] He | Deep residual learning for image recognition[END_REF] to deal with the output of the pooling layer. Let H(x) be an underlying mapping and we cast it as H(x) = F(x)+x, where F(x) is the residual mapping, defined by H(x)-x. That is, optimizing the residual mapping F(x) is easier than optimizing the direct mapping H(x) and helps to avoid the gradient vanishing problem during training. We use an exponential linear unit (ELU) in direct mapping and place a rectified linear unit (ReLU) after addition in our model. P-DropEdge Motivated by the recent idea of message passing inference [i.e., DropEdge of 10], we develop a new preferential DropEdge approach called the P-DropEdge which is based on censoring higher edge betweenness order statistics. In particular, most recently [START_REF] Rong | The truly deep graph convolutional networks for node classification[END_REF] propose a flexible approach, the DropEdge algorithm which by uniformly randomly removing a certain proportion of edges from the input graph at each training epoch, allows to better prevent against over-fitting and to reduce the effect of over-smoothing. The rationale behind DropEdge on introducing more randomness and deformation into the data is intrinsically linked and complementary to the Dropout ideas of [START_REF] Hinton | Improving neural networks by preventing co-adaptation of feature detectors[END_REF]. Our approach further advances DropEdge by targeting and randomly removing edges proportionally to their betweenness centrality, i.e., preferential edge dropout of higher edge betweenness order statistics. That is, first, our idea is based on the Girvan-Newman argument of focusing on edges which tend to play a higher role in the underlying network topology [START_REF] Girvan | Community structure in social and biological networks[END_REF]. Second, dropout of higher edge betweenness order statistics may be viewed as a variant of recently proposed non-uniform censoring schemes for generalized order statistics in reliability theory which are shown to deliver more robust parameter estimates in heterogeneous probability distributions [START_REF] Balakrishnan | Progressive censoring from heterogeneous distributions with applications to robustness[END_REF]. Definition 1.. (Edge Order Statistics) Given a input graph G = {V,E,W }, the betweenness centrality for the edge e ∈ E is defined as C Be (e) = u =v∈V σ uv (e)/σ uv , where σ uv the number of shortest paths connecting u to v, and σ uv (e) the number of shortest paths connecting u to v passing through the edge e. We then arrange edges in ascending order of their betweenness {C Be (e) i }, i = 1,2,...,|E| as C Be (e) (1) ≤ C Be (e) (2) ≤ ••• ≤ C Be (e) (|E|) . Here C Be (e) (i) is said to be the ith-order edge betweenness score, or the ith-edge betweenness order statistic.

Note that the Girvan-Newman algorithm on edge betweenness infers the edges connecting communities, that is, the edges exhibiting a more profound role in the network organization. As a result, P-DropEdge offers multi-fold benefits: (i) it constrains direction of a random walk and acts as a "self-avoiding" random walk, e.g., reduces the chance of moving back to the already visited graph structure; (ii) increases variability among randomly deformed copies of the original graph. That is, let us consider, e.g., an international political network. Randomly removing connections among Mr. and Mrs. Smith or even US Senators from Texas and California will tend to deliver a more similar resulting graph structure than randomly removing collaboration links between Trump, Macron, Putin and Johnson. . Finally, we replace the fractional Laplacian L in [START_REF] Levie | Cayleynets: Graph convolutional neural networks with complex rational spectral filters[END_REF] with LpP-D.E. for propagation and training. In validation and testing steps, P-DropEdge is not utilized.

Algorithm 1 P-DropEdge Algorithm

Advantages of LFGCN vs. Higher-order methods Recently there has been a spike of interests to higher-order methods, that is, algorithms based on the graph convolutional layer with higher-order information in graphs, such as APPNP [START_REF] Klicpera | Predict then propagate: Graph neural networks meet personalized pagerank[END_REF], VPN [START_REF] Jin | Power up! robust graph convolutional network based on graph powering[END_REF], and MixHop [START_REF] Abu-El-Haija | Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing[END_REF]. In contrast to such higher-order graph architectures, LFGCN offers multi-fold benefits: (i) Due to a fractal character, LF integrates local graph exploration with long-range excursions, which reduces oversampling comparing to standard random walks and allows for more efficient graph exploration; (ii) since high-order schemes [START_REF] Jin | Power up! robust graph convolutional network based on graph powering[END_REF][START_REF] Abu-El-Haija | Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing[END_REF] are based on integer powers of Laplacian, when exploring 2-hops, 3-hops,..., k-hops, standard random walks employed in these higher-order methods can only describe larger scale graph structures, often resulting in very dense adjacency matrices and higher computation costs; (iii) Lévy Flights average return probability is lower than average return probability of a normal random walk, implying more efficient graph exploration; (iv) Lévy Flights reinforces separability of clusters, enhances performance for unbalanced data, and is known to yield better search results in directional data. Clearly, these advantages are essential for learning graphs with higher heterogeneity, and for more homogeneous and balanced graphs, methods based on standard random walks may be a competitive alternative.

IV. EXPERIMENTAL SETTINGS

Directed and Undirected Datasets Joining the previous works practice, we use three undirected citation networks benchmark datasets for semi-supervised learning evaluation, including Cora-ML (this Cora dataset consists of Machine Learning papers), CiteSeer and PubMed. We also evaluate our method on four directed networks -Cora, IEEE 118-bus system (IEEE bus), Texas 2000-bus system (TX bus), and South Carolina 500-bus system (SC bus). The dataset statistics are summarized in Table V (in Appendix X). We provide the more details about datasets description on Github in the Appendix X.

Baseline Methods On undirected networks, we compare LFGCN with the following state-of-the-art semi-supervised classification approaches which include (i) using the label matrix as input: label propagation (LP) [START_REF] Zhu | Learning from labeled and unlabeled data with label propagation[END_REF]; (ii) using the feature matrix as input: DeepWalk (DW) [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF], graph attention networks (GAT), GNN with ChebNet polynomials filter (Cheb-Net), GCN, GNNs with convolutional ARMA filters (ARMA), Graph Markov Neural Networks (GMNN) [START_REF] Qu | Gmnn: Graph markov neural networks[END_REF], Large-Scale Learnable Graph Convolutional Networks (LGCNs) [START_REF] Gao | Large-scale learnable graph convolutional networks[END_REF], Shortest Path Graph Attention Network (SPAGAN) [START_REF] Yang | Spagan: shortest path graph attention network[END_REF], APPNP, VPN, and MixHop. In addition, on undirected graphs, we use MotifNet, ChebNet, GCN, ARMA, GMNN, LGCNs, SPAGAN, APPNP, VPN, and MixHop as the benchmarks.

Training Settings Training task is done by using Adam optimizer with learning rate lr 1 = 0.01 for undirected networks and lr 2 = {0.1;0.001} for directed networks. To prevent our approach from over-fitting, we consider both adding dropout layer before two graph convolutional layers and kernel regularizers ( 2 ) in each layer. For undirected and directed networks:

we follow the same experimental setup used in the baselines experiments to set the parameters of baselines. Parameters p P-D.E. and τ largely depend on the distributional properties of a network and can be estimated, e.g., via cross-validation. As a rule of thumb, we recommend p P-D.E. and τ of 5% and 6%, respectively, in larger networks of more than 2,000 nodes, and p P-D.E. and τ of 1% and 2%, respectively, in smaller network of less than 1,000 nodes. The best hyperparameter configurations of LFGCN for each dataset by using standard grid search mechanism are available at Github link in Appendix X.

V. RESULTS 1. Performance analysis Tables I and II report the average accuracy delivered by LFGCN and competing methods for undirected and directed networks, respectively. The best performance for each dataset is marked in bold. We find that LFGCN outperforms all competing approaches in all datasets, except for PubMed (LFGCN delivers the second best accuracy result). The improvement gain of LFGCN over the next most accurate method ranges from 0.29% (for CiteSeer over GMNN) to 4.27% (for directed IEEE 118-Bus over GMNN). Remarkably, methods that are applicable both to undirected and directed networks (i.e., [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF][START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF][START_REF] Bianchi | Graph neural networks with convolutional arma filters[END_REF][START_REF] Qu | Gmnn: Graph markov neural networks[END_REF][START_REF] Klicpera | Predict then propagate: Graph neural networks meet personalized pagerank[END_REF][START_REF] Jin | Power up! robust graph convolutional network based on graph powering[END_REF][START_REF] Abu-El-Haija | Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing[END_REF][START_REF] Gao | Large-scale learnable graph convolutional networks[END_REF][START_REF] Yang | Spagan: shortest path graph attention network[END_REF]) tend to deliver noticeably lower accuracy results for a directed networks (especially on weighted-directed networks), while the new LFGCN method yields a more stable performance across both directed and undirected networks. In turn, PubMed (unweighted-undirected), GMNN outperforms LFGCN up to 2.63%. Based on the obtain results, the new LFGCN approach tends to be the most competitive and, hence, preferred node classification method for sparser networks with higher label rates. Furthermore, the IEEE 118-Bus dataset is the smallest among the considered data, and we might expect to observe lower accuracy results for this dataset due to a limited training set. However, the accuracy yielded by LFGCN is among the highest ones across all datasets. For PubMed, it has the lightest tails for the degree distribution and a weak structural info (i.e., with very few links per node on average), thus LFGCN is not the best exploration choice.

We provide the training time per epoch on all datasets in the Appendix X (see Tables VI VII and VIII).

2. Ablation study by removing individual components in LFGCN To discover the vital components in the success of our LFGCN, we investigate the contributions of individual components proposed in Section III-B to the performance of LFGCN. We conduct experiments by removing individual component separately (in the spirit of leave-one-out operation) from our LFGCN architecture, leading to a network without P-DropEdge, parallel structure, residual block, or gated max-average pooling.

Table III provides the comparison results between LFGCN without P-DropEdge, parallel structure, residual block, or gated maxaverage pooling. The results show that LFGCN consistently outperforms the reduced LFGCN baselines by a significant margin, reaching around 0.24% to 2.91% relative improvement on Cora-ML and IEEE 118-bus system. These results demonstrate contributions of all components to performance improvement.

3. P-DropEdge vs. DropEdge We now evaluate our P-DropEdge and regular DropEdge of [START_REF] Rong | The truly deep graph convolutional networks for node classification[END_REF] based on the LFGCN and GMNN (i.e., the best performing baseline).

Table I: Comparison of average accuracy (%) and standard deviation (%) in () of semi-supervised classification approaches for undirected networks.

Method

Cora-ML CiteSeer PubMed LP [START_REF] Zhu | Semisupervised learning using gaussian fields and harmonic functions[END_REF] 68.70 46.32 65.92 DW [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF] 67.20 43.27 65.33 ChebNet [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF] 81.45 70.23 78.40 GCN [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF] 81.50 71.11 79.00 ARMA [START_REF] Bianchi | Graph neural networks with convolutional arma filters[END_REF] 82.80 (0.63) 72.30 (0.44) 78.80 (0.30) GAT [START_REF] Veličković | Graph attention networks[END_REF] 83.11 (0.70) 70.85 (0.70) 78.56 (0.31) GMNN [START_REF] Qu | Gmnn: Graph markov neural networks[END_REF] 83.72 (0.90) 73.10 (0.79) 81.80 (0.53) LGCNs [START_REF] Gao | Large-scale learnable graph convolutional networks[END_REF] 83. [START_REF] Perozzi | Deepwalk: Online learning of social representations[END_REF] Carolina 500-bus system. We find that while a sufficiently sampling-based edge-removing is helpful for performance enhancement, regular randomly removing edges do not always improve performance. Note that this finding is in contrast to the regular DropEdge where both LFGCN and baseline equipped with P-DropEdge achieve consistently better performance than others. These findings prove the effectiveness of employing preferential approach of P-DropEdge before the learning task. 4. Evaluation of LFGCN-specific parameters During grid search over three parameters (i.e., α, σ, and γ), we find that: (i) the regularization parameter α which used to specify the relative importance of a graph in clustering strongly relates to the probability of initial conditions for random walks when the self-refreshing process works, and it strongly influences the network's generalization ability and node classification performance for all datasets; (ii) the free unifying parameter σ provides enough flexibility to construct a canonical formulation of different graph-based semi-supervised methods -Table I and Table II indicate that the optimal value of σ depends on both the types of networks (undirected and directed) and label rate not on the size of network; (iii) the fractional power parameter γ substantially impacts the accuracy of node classification for the small datasets (see e.g., Figure 2), however, no similarly strong influence is found in the larger datasets.

Hyperparameter sensitivity

In the sensitivity analysis setting, we have the ability to analyze the sensitivity of the node classification accuracy to variation from three LFGCNspecific parameters -α ∈ {0.1,••• ,1}, σ ∈ {0,0.1,••• ,1}, and γ ∈ {0.001,0.01,0.1,1}. In this case, we only show the results from sensitively analysis for LFGCN model on IEEE 118-bus dataset. First, we perform the parameter learning experiments on four scenarios with a fixed parameter γ. Figure 2 shows that the accuracy substantially decreases when α is larger than 0.8, especially in γ equals to 0.001 and 0.01 (see Figure 2(a), 2(b)). Setting γ = {0.1,1}, we observe that the classification accuracy nearly monotonic decreases while increasing α. Additionally, LFGCN generally gives consistent and higher accuracy for γ = {0.001,0.01} when the α parameter is within the range of {0.1, 0.2, 0.3, 0.4}. We then explore the variation of accuracy based on tuning parameter γ within the range of [0.001,0.002,•••,0.01] (setting σ ∈ {0,0.1,•••,1} at the same time), however, it is hard to obtain the optimal (σ, γ) combination through gathering finite experimental results (100 runs) since some of the results are very close. Therefore, we run the following experiments to demonstrate the impact evaluation of γ: Figure 3 shows that there exists a more profound difference between the shapes of approximate Gaussian distributions by fixing the parameter σ than fixing the parameter γ. These findings imply that σ tends to be a more important factor in the LFGCN approach for small datasets. Fig. 3: Generalized Gaussian density of accuracy of LFGCN (two blue dashed lines represent lower and upper bounds, respectively): (a) the red filled curve is the PR-based method (σ = 0), blue filled curve is the NL-based method (σ = 0.5), and green filled curve is the SL-based method (σ = 1). (b) the red, blue, green filled curves represent scenarios with fractional parameters γ of 0.001, 0.005, and 0.010, respectively.

VI. CONCLUSION

We have proposed a new Lévy Flights Graph Convolutional Network (LFGCN) method for semi-supervised learning on graphs that enables to better capture the intrinsic local graph topology. In addition, to further mitigate over-fitting and over-smoothing, we have proposed a new preferential P-DropEdge algorithm, based on censoring higher edge betweenness order statistics. We have investigated theoretical properties of LFGCN and have validated utility of individual components of the LFGCN architecture.

Our numerical studies have indicated that the new LFGCN method tends to outperform all competing deep learning approaches on both unweighted-directed and unweightedundirected graphs in all considered datasets, except of PubMed. The gain in learning accuracy of LFGCN over the next best competitor ranges from 0.29% to 4.27%, and the highest gain has been achieved for the IEEE 118-Bus dataset which is the smallest among the considered datasets. Furthermore, in contrast to the competing approaches, LFGCN tends to deliver a more stable performance across directed and undirected networks regardless of the label rate.

In the future we plan to advance the proposed LFGCN technique to learning on multilayer networks, explore utility of P-DropEdge combined with other order statistics on graphs, and enhance graph learning process with topological information on the underlying deep neural network.

Lemma 2 .

 2 The Lévy flight defined by the normalized Laplacian has a shorter relaxation time (measure of the transience) in comparison with the original random walk.

Fig. 1 :

 1 Fig. 1: Illustration Lévy Flights Graph Convolutional Network model. The input is the feature matrix X and the graph within dotted circle represents embedding Lévy Flights into random walks on graph (where L γ is the Laplacian matrix L to a power γ). LFGCN architecture consists of three main components: (i) FGS convolutional layer with parallel structure; (ii) gated max-average pooling layer; (iii) activation block for residual learning. invariance via considering input in each gating mask) based on the mixed max-average pooling equation. That is,

Input:

  Data adjacency matrix W , Parameter p P-D.E. , τ for i = 1 to |E| do calculate C Be (e) i for the edge e i end for Find order statistics of {C Be (e) i }, i = 1,2,...,E C Be (e) (1) ≤ C Be (e) (2) ≤ ••• ≤ C Be (e) (|E|) Draw edges which correspond to the top order statistics C Be (e) ((1-τ )|E|) ≤ ••• ≤ C Be (e) (|E|) Assign weights to the selected edges in 1st-round as ψ (j) = C Be (e) (j) |E| j=(1-τ )|E| C Be (e) (j) , j = (1-τ )|E|,...,|E|, ψ = {ψ ((1-τ )|E|) ,•••,ψ (|E|) } Weighted sampling without replacement randsample((1-τ )|E| : |E|,p P-D.E. ×τ ×|E|,ψ), obtain sample s with size p P-D.E. ×τ ×|E| Output new adjacency matrix Wp P-D.E. = W -W C Be (e)∈s P-DropEdge method is presented in Algorithm 1. Given a resulting adjacency matrix W pP-D.E. upon P-DropEdge application, a new fractional Laplacian takes the form LpP-D.E. = D -σ γp P-D.E. W γp P-D.E. D σ-1 γp P-D.E.

• Step 1 :

 1 Set γ ∈ {0.001,0.002,•••,0.1}.• Step 2: For each fixed γ, we run our proposed model 100 times separately for σ from 0 to 1 by 0.01. We obtain 100 average accuracies for each γ:{Acc σ=0 ,Acc σ=0.01 ,•••,Acc σ=1 } [i] , 1 ≤ i ≤ 10. • Step 3: Fit the Gaussian distribution to {Acc σ=0 ,Acc σ=0.01 ,•••,Acc σ=1 }[i] (see Fig.3(b)). Similar to γ, we fit the Gaussian distribution to {Acc γ=0.001 , Acc γ=0.002 , ••• , Acc γ=0.01 }[j] by fixing σ, where j = 1,•••,11 (see Figure3(a)).

Fig. 2 :

 2 Fig. 2: Accuracy of LFGCN for PR, NL, and SL as a function of α and fractional power γ = {0.001 (a), 0.01 (b), 0.1 (c), 1.0 (d)}.

Table II :

 II Comparison of average accuracy (%) and standard deviation (%) in () of semi-supervised classification approaches for directed networks.

	Method	Cora	IEEE Bus	TX Bus	SC Bus
	MotifNet [25]	60.00	65.75	82.00	95.18
	ChebNet [5]	58.93	60.00	80.04	94.13
	GCN [6]	57.75	52.86	73.36	90.33
	ARMA [8]	58.99 (0.52)	70.55 (2.23)	81.20 (0.23)	94.33 (0.47)
	GMNN [12]	61.20 (0.50)	78.88 (2.50)	86.21 (0.29)	96.57 (0.52)
	LGCNs [36]	60.72 (0.43)	71.43 (2.20)	85.57 (0.25)	95.14 (0.45)
	SPAGAN [37]	61.00 (0.45)	78.55 (2.25)	86.00 (0.26)	96.19 (0.40)
	APPNP [22]	61.00 (0.44)	82.05 (2.24)	86.77 (0.30)	96.11 (0.45)
	VPN [23]	60.53 (0.43)	82.19 (2.20)	86.87 (0.33)	96.23 (0.50)
	MixHop [24]	60.33 (0.55)	80.05 (2.50)	86.10 (0.25)	95.94 (0.40)
	LFGCN w/o pP-D.E.	60.70 (0.47)	82.20 (2.30)	87.74 (0.30)	97.61 (0.47)
	LFGCN	61.35 (0.45)	82.40 (2.24)	88.23 (0.26)	97.85 (0.47)

  Table IV presents comparison between LFGCN and GMNN with regular DropEdge and P-DropEdge on CiteSeer and South

Table III :

 III Comparison of the LFGCN with/without (1) P-DropEdge (p P-D.E. ), (2) Parallel Structure (PS), (3) Residual Block (RB), and (4) gated max-average pooling (Gated Max-Avg) in terms of node classification accuracy (%) on undirected Cora-ML and directed IEEE118 bus system. Numbers in () are relative gains in (%) between the best result delivered by the LFGCN and reduced LFGCN.

		Undirected	Directed
	Method	Cora-ML	IEEE Bus
	LFGCN w/o p G-N.	84.35 (0.33)	82.20 (0.24)
	LFGCN w/o PS	84.31 (0.38)	80.71 (2.09)
	LFGCN w/o RB	83.31 (1.58)	80.07 (2.91)
	LFGCN w/o Gated Max-Avg 83.66 (1.16)	81.12 (1.58)
	LFGCN	84.63	82.40

Table IV :

 IV Comparison of GMNN and LFGCN with regular DropEdge (p) and P-DropEdge (p P-D.E. ) in terms of node classification accuracy (%) on undirected Citeseer and directed South Carolina bus system. The numbers in () denote the optimal edge removal rate for the models with DropEdge and P-DropEdge.

		Undirected	Directed
	Method	CiteSeer	SC Bus
	GMNN with p	73.10 (5%)	96.57 (1%)
	GMNN with p P-D.E.	73.20 (5%)	96.89 (1%)
	LFGCN with p	72.05 (5%)	97.58 (1%)
	LFGCN with p P-D.E.	73.31 (5%)	97.85 (1%)

APPENDIX VII. PROOF OF LEMMA 1

Proof. The objective function of the generalized semi-supervised learning framework (i.e., Lemma 1) can be rewritten in the following matrix form:

T D 2σ-1 = 0. Multiplying the above expression from the right hand side by

VIII. PROOF OF LEMMA 2 Proof. Relaxation time of a Markov process is given by the reciprocal of the spectral gap min{λ 2 , 2 -λ n }, where 0 = λ 1 ≤ λ 2 ≤ ... ≤ λ n are eigenvalues of the normalized Laplacian. From the singular value decomposition L γ = U Λ γ U and monotonicity of the power function, we conclude that λ γ 2 and λ γ n are the smallest and largest eigenvalues of the Lévy flight, respectively. Since for 0 < γ < 1, x γ > x when 0 < x < 1 and x γ < x when 1 < x < 2, the spectral gap of the Lévy flight increases with respect to the original random walk. Consequently, the relaxation time of the Lévy flight is less than the relaxation time of the original random walk.

IX. PROOF OF LEMMA 3 Proof. The parallel structure [START_REF] Henley | Reliability engineering and risk assessment[END_REF] is constructed in a similar spirit as bagging of features in random forest and other ensemble learning methods. The key rationale behind the parallel structure is to reduce variance and increase stability. Let us first consider the first equation in Lemma 2. Suppose that Υ is a random sample drawn without replacement from a finite population U = {1,2,...,N } according to a sampling design p(•).

F GS , i.e. the i-th output matrix from FGS convolution for new feature matrix X i . Probability of choosing sample υ is P r(Υ = υ) = p(Υ) > 0 for all υ ∈ U and υ = ∅. Let Z be the indicator variable such that Z i = 1 if X i is in the sample, and 0 otherwise. Hence, probability that the unit i,i = 1,...,N is selected, is given by π i = E(Z i ), and probability that units i and j, i,j = 1,...,N are selected simultaneously is π ij = E(Z i Z j ); π i and π ij are called first order inclusion probability and second order inclusion probability, respectively. Since in the current paper, we consider a simple random sampling design of n units X (i)

F GS }, we find that

where XF GS is be the output matrix P 1 from a pooling layer (see Residual Blocks in main text Figure 1), which implies that XF GS is an unbiased estimator of population mean XU F GS . In turn,

Hence, the proposed PS structure decreases an original estimation variance S by order of n. Note that we can consider other sampling designs p(•), including, for example, weighted sampling and p-extended simple random sampling with replacement [see discussion by 40, 41, 42, and references therein].

The stability result of the parallel structure [START_REF] Nowak | Reliability of structures[END_REF] follows from verbatim application of the probability bound on the intersection of independent events.

X. MORE DETAILS ON EXPERIMENTS

The statistics of data we used in the experimental section are summarized in Table V. For undirected networks and Cora, we trained and tested our model on the same dataset splits as in [START_REF] Kipf | Semi-supervised classification with graph convolutional networks[END_REF]; and we use a 10%/20%/70% split into training, validation, and test sets for power grid networks. Note that while calculating edge betweenness may be time consuming, it's performed offline. Different from DropEdge, P-DropEdge is an offline method based on prior edge info and such prior info is not limited to edge betweenness. Instead, we can use, e.g. edge criticality based on percolation theory, k-path edge centrality with time complexity O(k|E|), and centrality based on the edge impact on giant comp -scores particularly important in weighted graphs, e.g power and transportation systems. P-DropEdge can bring new insights on how targeted perturbation of graph topology can assist addressing GCN oversmoothing and GCN sensitivity to attacks.


Emilie Leblong

Bastien Fraudet

Louise Devigne

Marie Babel

François Pasteau

Nicolas Benoit

Philippe Gallien

Evaluation on standardised circuits of the interest of a robotic module for assisting the driver of an electric wheelchair: pilot, prospective, controlled, randomised study

• Most people with disabilities require assistance and often use a technical mobility aid.

• Prevalence of people using wheelchairs = increase with an estimate ranging from 60 to 200 per 10,000 inhabitants (Vignier 2008).

• 10% of wheelchair users use electric models (Kaye 2002;Vignier 2008) • 25% of accidents with Power Wheelchair (PWC) (Kirby 1995).

• 100 000 accidents involving wheelchair users in the United States in 2006,

• 54.7% of subjects reported having had at least 1 accident in the last 3 years (Chen 2011).

Contexte

• Statistically significant reduction in the number of collisions on the most complex circuit (13 versus 46)

• Significant slowdown due to the activation of the driver assistance module but a real increase of safety.

 Efficiency of the PWC driver assistance module in terms of safety without reducing travel speed in a population of people with disabilities who are usual wheelchair drivers.

  Future trials : tests on the target population in failure or driving difficulties Bibliography DEVIGNE L, NARAYANAN V, PASTEAU F, et al. Low complex sensor-based shared control for power wheelchair navigation. In : Intelligent Robots and Systems (IROS), 2016 IEEE/RSJ International Conference on. IEEE, 2016. p. 5434-5439. DEVIGNE L, PASTEAU F, LE BORGNE N, BABEL M, CARLSON T, GALLIEN P. Assisting power wheelchair driving on a sidewalk: A proof of concept. Modelling, Measurement and Control C, 79(4):185-189, RAGOT N, CARON G et al. Coalas: A eu multidisciplinary research project for assistive robotics neuro-rehabilitation. In : IEEE/RSJ IROS Workshop on Rehabilitation and Assistive Robotics: Bridging the Gap Between Clinicians and Roboticists, Chicago, USA. 2014. Emilie Leblong* (1), Bastien Fraudet (1,2), Louise Devigne (3), Marie Babel (3), François Pasteau (3), Benoit Nicolas (1), Philippe Gallien (1) 1) Pôle Saint-Hélier (Rennes) 2) Living Lab ISAR, 54 rue St Hélier, 35043 Rennes Cedex 3) INSA Rennes, Inria, Irisa-UMR6074, France.


Mathieu Seurin
email: mathieu.seurin@inria.fr

Philippe Preux
email: philippe.preux@inria.fr

Olivier Pietquin
email: pietquin@google.com

I'm Sorry Dave, I'm Afraid I Can't Do That Deep Q-Learning from Forbidden Actions

Keywords: Deep Reinforcement Learning, Safety, constraints, Q-Learning

The use of Reinforcement Learning (RL) is still restricted to simulation or to enhance human-operated systems through recommendations. Real-world environments (e.g. industrial robots or power grids) are generally designed with safety constraints in mind implemented in the shape of valid actions masks or contingency controllers. For example, the range of motion and the angles of the motors of a robot can be limited to physical boundaries. Violating constraints thus results in rejected actions or entering in a safe mode driven by an external controller, making RL agents incapable of learning from their mistakes. In this paper, we propose a simple modification of a state-of-theart deep RL algorithm (DQN), enabling learning from forbidden actions. To do so, the standard Q-learning update is enhanced with an extra safety loss inspired by structured classification. We empirically show that it reduces the number of hit constraints during the learning phase and accelerates convergence to nearoptimal policies compared to using standard DQN. Experiments are done on a Visual Grid World Environment and the TextWorld domain.

I. INTRODUCTION

Reinforcement Learning (RL) [START_REF] Sutton | Reinforcement learning: An introduction[END_REF] is the main machine learning answer to address sequential decision-making problems under uncertainty. Its genericity allows application to a variety of domains such as Robotics [START_REF] Gu | Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates[END_REF][START_REF] Levine | Endto-end training of deep visuomotor policies[END_REF], Resource Management [START_REF] Mao | Resource management with deep reinforcement learning[END_REF], Chemical reaction [START_REF] Zhou | Optimizing chemical reactions with deep reinforcement learning[END_REF]), Traffic-light Management (El-Tantawy et al., 2013), Spoken Dialogue Systems [START_REF] Lemon | Data-driven methods for adaptive spoken dialogue systems: Computational learning for conversational interfaces[END_REF] and sparked interest in other industrial applications. Bringing reinforcement learning to critical systems such as Surgery [START_REF] Hashimoto | Artificial intelligence in surgery: promises and perils[END_REF], Dam Management [START_REF] Wang | Multi-agent dam management model based on improved reinforcement learning technology[END_REF] or Autonomous Driving [START_REF] Leurent | Social attention for autonomous decision-making in dense traffic[END_REF][START_REF] Sallab | Deep reinforcement learning framework for autonomous driving[END_REF] remains one of the most interesting open challenges in machine learning. Unexpected behavior, inability to handle uncertainty and low sampling efficiency are the Achilles heels of real-world RL [START_REF] Dulac-Arnold | Challenges of real-world reinforcement learning[END_REF].

The major issue is that designing RL agents able to measure uncertainty about their internal estimates (e.g. their state, the outcome of their actions) is difficult [START_REF] Geist | Managing uncertainty within the KTD framework[END_REF] and especially when associated with recent Deep Learning methods [START_REF] O'donoghue | The uncertainty bellman equation and exploration[END_REF]. Even if available, using a measure of uncertainty for safety is not straightforward either [START_REF] Bellemare | A distributional perspective on reinforcement learning[END_REF][START_REF] Daubigney | Uncertainty management for on-line optimisation of a pomdp-based large-scale spoken dialogue system[END_REF]. Uncertainty is especially harmful when agents are meant to control a physical system, where a wrong action can lead to catastrophic consequences (e.g. damaging material or endangering people).

Fortunately, many real-world systems are equipped with contingency measures, in the form of forbidden actions or external controller taking over when the system is misbehaving. For example, over-temperature monitoring regulates servomotors present in robots, preventing the motors from reaching their heat limit. Cleaning robots also automatically u-turn in the presence of an obstacle, preventing any damage to the machine and its environment.

Beyond critical systems, many areas could benefit from forbidden actions. In Natural Language Generation [START_REF] Reiter | Building applied natural language generation systems[END_REF] or Dialogue systems [START_REF] Chandramohan | Optimizing spoken dialogue management with fitted value iteration[END_REF]; [START_REF] Chen | A survey on dialogue systems: Recent advances and new frontiers[END_REF], syntax parser or auto-correct mechanism can act as an external rejection signal. Indicating which word does not fit a generated sentence or pointing out grammar mistakes could improve language generation by greatly reducing word's space, leveraging language learning and generation.

These examples show a potential misalignment between the standard RL frameworks and the potential real-world applications. Of course, designing constraints to avoid critical situations requires expert knowledge about the system to be controlled. But it is often the case that environments already implement such contingency measures (obstacle avoidance, circuit breaker, etc.).

In this paper, we consider a simple type of external constraints, prevalent in many real-world problems: when the agent is about to perform a hazardous action, the system rejects it and thus prevents the agent from doing so. The agent then follows the natural dynamics of the environment [START_REF] Alshiekh | Safe reinforcement learning via shielding[END_REF]. We aim at building an algorithm that learns from these rejected actions.

In the general Markov Decision Process (MDP) framework [START_REF] Puterman | Markov Decision Processes[END_REF], a rejected action, from the agent's point of view, would be seen as a transition to the same state. Everything happens like if the action had no effect. This misrepresents the potential harmfulness of the action and prevents the agent from learning anything useful from the rejected action (See subsection III-A for a detailed explanation). We want a modelfree reinforcement learning to benefit from those constraints so as to learn faster to avoid hazardous states and alleviate exploration problems.

In the coming sections, after introducing the RL paradigm, we propose a constrained version of Deep Q-learning (DQN) [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] by adding a classification loss that maintains Q-values of forbidden actions below valid ones. We then validate our method empirically, showing that vanilla DQN struggles at solving tasks with rejected actions while our algorithm reduces the number of calls to forbidden actions. It accelerates convergence to near-optimal policies compared to standard DQN. Experiments are conducted on two tasks: A maze navigation using visual features and a text-based game.

II. CONTEXT: REINFORCEMENT LEARNING

In the reinforcement learning (RL) paradigm [START_REF] Sutton | Reinforcement learning: An introduction[END_REF], an agent learns to interact with its environment so as to maximize a cumulative function of rewards. The environment to be controlled is modeled as a Markov Decision Process (MDP) that is a tuple {S, A, P, R, γ} which elements are defined as follows. At each time step t, the agent is in a state s t ∈ S, where it selects an action a t ∈ A according to its policy π : S → A. It moves to state s t+1 according to a transition kernel P and receives a reward r t = r(s t , a t ) drawn from the environment's reward function R : S × A → R. The quality of the policy is assessed by the Q-function defined by a), from which the optimal policy π * is derived.

Q π (s, a) = E π t γ t r(s t , a t )|s 0 = s, a 0 = a for all (s, a) where γ ∈ [0, 1] is the discount factor. The optimal Q-value is defined as Q * (s, a) = max π Q π (s,
π * (s) ∈ arg max a Q * (s, a)
We here use the Deep Q-learning (DQN) algorithm [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] to approximate the optimal Q-function with neural networks and perform off-policy updates by sampling transitions (s t , a t , r t , s t+1 ) from a replay buffer [START_REF] Lin | Self-improving reactive agents based on reinforcement learning, planning and teaching[END_REF].

III. METHOD A. Feedback Signal and MDP-F

In this section, we present a way to integrate forbidden actions into the MDP framework. We augment the MDP model with a Feedback Signal [START_REF] Alshiekh | Safe reinforcement learning via shielding[END_REF], a Boolean indicating whether an action was accepted by the environment or rejected. A MDP-F is then defined as a tuple < S, A, P, R, γ, F > where F is a function mapping a state s t and action a t to a binary value.

F : S × A → (0, 1)
with 0 meaning the action is valid and 1 meaning unsafe/rejected action.

Vanilla Q-learning struggles to differentiate between actions flagged as forbidden and valid ones. Consider the following example: an agent in a state s takes action a flagged as forbidden (F(a, s) = f = 1). When applying the Q-learning update (Q(s, a f eed ) = r(s, a f eed ) + γmaxQ(s , a )), since the action was rejected, r(s, a) = 0 and s = s . Thus the update becomes Q(s, a f eed ) = γmaxQ(s, a ). In current Deep Reinforcement Learning setup γ is usually set between 0.99 [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] and 0.999 [START_REF] Pohlen | Observe and look further: Achieving consistent performance on atari[END_REF]. DQN-like algorithm will require lots of transitions to make the Q-function of forbidden actions smaller, thus loosing time to explore and collect useful samples. We emphasize that an invalid action indicates an action that could be harmful, so rapidly identifying and avoiding those potentially dangerous situations is crucial.

B. Frontier loss

We take inspiration from the learning from demonstrations paradigm where one wants to use expert demonstrations to induce the usage of preferred actions in RL agents.

a) Expert loss and Imitation learning: In Imitation learning, few expert demonstrations are available and extracting as much information from those is essential. For example [START_REF] Hester | Deep Q-learning from demonstrations[END_REF][START_REF] Piot | Boosted Bellman residual minimization handling expert demonstrations[END_REF] slightly modify the Q-learning update to nudge expert actions-value above other actions. This is done by adding a secondary loss inspired by structured classification:

Minimize J E (Q) = max a∈A [Q(s, a) + l(a E , a)] -Q(s, a E )
where a E is the action of the expert, l(a E , a) = 0 when a E = a and m otherwise. This nudges the Q-value of actions taken by the expert above the Q-value of other actions by at most a certain margin m.

Similarly, we want to derive a loss that penalizes the Qfunction when a forbidden action's value excesses the value of a valid one.

b) Frontier loss: The optimal policy π * (derived from Q * ) will never take a forbidden action as it keeps the agent in the same state. Based on this assumption we can derive the following rule: for every state encountered during training, the Q-values of all forbidden actions should be below the one of each valid actions, within a certain margin m. This defines a new loss we want to minimize that we call frontier loss J F :

J F (Q) = Q(s, a -) -min a∈Vs [Q(s, a) -m] (1)
where

V s = A(s) ∩ {a s.t. F(s, a) = 0} and a -∈ A(s) ∩ {a s.t. F(s, a) = 1}
The margin m is an hyper-parameter that depends mostly on the Q-values magnitude. In our experiments, since the rewards are bounded between 0 and 1, the margin is small (m = 0.1). c) Frontier loss and classification: The main problem regarding this objective function is the need to know which actions are valid for every state. In most tasks, it's unlikely that the agent visits a specific state more than once (e.g. visual domains). Thus, function approximation is required to estimate which actions are valid in a given state. To achieve this, we train a neural network to predict, for each state, which action will be valid. Along agent's trajectories, for every action taken, we store the corresponding feedback, creating a dataset of (s, a, f ). The network, taking the state as input, predicts a binary value for every action (0 for valid, 1 for invalid). For each state in our transition dataset, since most of the time only one action is labelled, we need to adapt the training regime. We can achieve this by masking the gradients from untaken action, only backpropagating for the action the policy π took.

The training procedure is illustrated on Figure 2.

To consider an action as valid and to avoid early misclassifications, we put a threshold after the sigmoid function. The action is considered to be valid if its activation is above the threshold.

d) DQN-F: We construct a new algorithm, DQN-F, that simply combines the frontier loss and Deep Q-learning. We build a composite loss by using weighting factors λ DQN and λ F to balance the DQN and the frontier losses. For all the experiments described below, we use λ DQN = 1 and λ F = 0.5. Not much tweaking is required regarding these hyper-parameter.

J(Q) = λ DQN J DQN (Q) + λ F J F (Q)

IV. EXPERIMENTS

We assess our method on two different tasks: a toy problem (MiniGrid) and a text-based game (TextWorld).

A. MiniGrid Enviroment

The first environment is a simple visual gridworld presented in [START_REF] Chevalier-Boisvert | BabyAI: First steps towards grounded language learning with a human in the loop[END_REF]. The goal is to reach the green zone starting from a random point. Since we want to study how the agent can integrate feedback about action's validity, we increase the action space size. To do so, we create k different room types where the color of the background indicates which set of actions is valid. The primary action space is composed of 3 actions (Turning Left, Turning Right, Going Forward) for navigation, but each action is duplicated k times. The action space size becomes 3 × k but only 3 are valid in a given room. For example, in the red room, only actions 11, 12, 13 are valid, and all the others are returning a not valid feedback. In our setup, we use k = 5 making a total of 15 actions.

The state space is an embedding of the agent's point of view represented as different features maps allowing the use of convolution layers (more details in [START_REF] Chevalier-Boisvert | BabyAI: First steps towards grounded language learning with a human in the loop[END_REF]). Since the environment is partially observable, we stack the last three frames as in [START_REF] Mnih | Human-level control through deep reinforcement learning[END_REF] but we do not use frame-skipping. An episode ends when the agent reaches the green zone or after 200 environment steps as illustrated on Figure 3.

B. TextWorld Environment

TextWorld [START_REF] Côté | Textworld: A learning environment for text-based games[END_REF] is a text-based game where the agent interacts with the environment using short sentences. We generated a game composed of 3 rooms, 7 objects, and quest length of size 4. An example is shown on Figure 4. In this context, we modified the environment to fit our needs. The action space is composed of all <action> <object> pairs, creating a total of 46 actions. Most of the actions created will be rejected by the simulator since they will not fit the situation the agent is facing. For example, the action "take sword" will be rejected if no sword is available. An illustration of the game can be found Figure 4.

C. Model and architecture

During all experiments, we use Double Deep Q-Network (DQN) [START_REF] Hasselt | Deep reinforcement learning with double q-learning[END_REF] with uniform Experience Replay and -greedy exploration. In the Minigrid environment, we use a Convolution Neural Network [START_REF] Lecun | Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks[END_REF] with a fully-connected layer on top. In TextWorld, inventory, observation, and room descriptions are each encoded by an LSTM [START_REF] Hochreiter | Long short-term memory[END_REF] processed by a fully-connected layer on top.

The classification network matches exactly the architecture used by DQN, i.e. ConvNet for Minigrid and LSTM's for TextWorld, the only difference resides in training (explained Figure 2) V. RESULTS

In Figure 5, Figure 6, Figure 7, Figure 8, we compare DQN and DQN-F. In the Minigrid domain, DQN struggles to find the optimal policy and reaches only 20% of the time the exit. Most of the time, DQN is able to solve one room but fails to find the set of actions for each room, performing forbidden actions over and over. On the contrary, the frontier loss is guiding DQN-F, reducing the number of negative feedback signals from the environment, and helping to find the optimal policy. Those results are echoed in the TextWorld experiment. DQN solves the game half of the time, and the other half does not encounter the reward and as a result, can not solve the game. This could be mitigated by having a better exploration strategy, but it shows that shaping Q-values with the frontier loss is enough to reduce the sample complexity and guide exploration. We want to emphasize that in early stages of the training, the classification network performs poorly due to low quantity of samples but it does not hurt the performances of DQN-F, it's able to quickly learn to avoid forbidden actions. Visualization of Q-values at different stages of training can be found on Figure 9, Figure 10. They clearly illustrate the benefits of using the frontier loss in those setups. Even in the early training stage, the separation between valid actions and invalid is clear, alleviating the difficulty of finding the optimal policy. Where as DQN Q-values are really hard to distinguish from each other.

VI. RELATED WORKS

a) Action Elimination: Closely related to our work is the notion of action elimination which was introduced in (Even- [START_REF] Even-Dar | Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems[END_REF]. The main idea developed in that work, applied to Multi-Arm Bandits [START_REF] Lai | Asymptotically efficient adaptive allocation rules[END_REF][START_REF] Lattimore | Bandit algorithms[END_REF][START_REF] Robbins | Some aspects of the sequential design of experiments[END_REF] is to get rid of a sub-optimal action as soon as the value of this action is out of some confidence interval.

A similar idea was applied in Deep Reinforcement Learning by [START_REF] Zahavy | Learn what not to learn: Action elimination with deep reinforcement learning[END_REF]. This article shares similarities with ours as the authors are trying to eliminate actions based on a signal given by the environment, indicating if the action is valid or not. They are using a contextual bandit to assess the elimination signal's certainty, and remove actions from the action set A when the confidence is above a certain threshold. The main difference is in the way the elimination signal acts on Q-learning. In their case, the elimination signal doesn't change Q-values but modifies the action set directly. They need extra care because removing a valid action can irreversibly damage the policy where as in our case, we only nudge values. [START_REF] Alshiekh | Safe reinforcement learning via shielding[END_REF] define the term shielding similar to our notion of feedback. The simulator rejects potentially harmful actions. To learn from this process, the agent outputs a set of actions, ordered by preferences, and the simulator picks the best-allowed action.

b) Learning when the environment takes over: Orseau and Armstrong (2016) design agent to not take into account feedback from the environment. For example, for an agent operating in real-time, it may be necessary for a human operator to prevent executing a harmful sequence and lead the agent into a safer situation. However, if the learning agent expects to receive rewards from this sequence, it may learn in the long run to avoid such interruptions, for example, by disabling the off-button. Under this setup, they showed that Q-learning could be interrupted safely, supporting our hypothesis that Q-learning is not integrating the feedback signal. et al., 2012) rendering problems with large action sets tractable. (He et al., 2016a,b) are dealing with variable action space, meaning that at every time step, the action set size is different. To cope with this challenge, they compute a state embedding and action embedding for every action available then perform a dot product between the two. This allows them to deal with variable sized action set.

VII. CONCLUSION

Critical real-world systems are constrained by safety measures that prevent hazardous action. We hypothesize that Qlearning, a model-free reinforcement learning method struggles with those constraints. In this paper, we proposed a frontier loss, combined with a classification network, to help DQN. This algorithm nudges rejected actions Q-values below Qvalues of valid actions. We showed empirically that the frontier loss reduces the number of calls to rejected actions and guides early exploration, helping Deep Q-learning achieving higher performances. We demonstrate its effectiveness on two benchmarks, a visual grid world and a TextWorld domain.

a) Limitations and Future Work: At the moment, applying the frontier to continuous action space is non-trivial but it would be a key to use this type of algorithm in robotics and more realistic settings. Another future improvement would be to combine the loss with action's embedding could allow generalization to unseen actions. For example, learning that "Take sword" is rejected "Grab sword" shouldn't be considered by the algorithm.

Figure 2 .

 2 Figure 1. Illustration of frontier loss.

Algorithm 1 :Figure 3 .

 13 Figure 3. An instance of the MiniGrid problem. The state is a partial view of the maze (point of view of the agent) to avoid problem regarding partial observability, we stacked the last 3 frames.

Figure 4 .

 4 Figure 4. An example of interaction in TextWorld. The agent has access to: what happened after its latest action ("You open the door, it's very dark in here, [...]"), a room description ("Attic, an empty room, maybe you should head back. You can go North, East") and its inventory content ("Keycard, Mask").

Figure 5 .

 5 Figure 5. Minigrid results: Number of times a forbidden action is taken. DQN-F (yellow) DQN (blue). Results are averaged over five random seeds. The shaded area represents one standard deviation.

Figure 6 .

 6 Figure 6. Minigrid results: Percentage of success over time. DQN-F (yellow) DQN (blue). Results are averaged over 5 random seeds. The shaded area represents one standard deviation.

Figure 7 .

 7 Figure 7. Textworld results: Number of invalid action taken by the agent. DQN-F (yellow) DQN (blue). Results are averaged over nine random seeds. The shaded area represents one standard deviation.

Figure 8 .

 8 Figure 8. Textworld results: Percentage of success over time. DQN-F (yellow) DQN (blue). Results are averaged over 9 random seeds. The shaded area represents one standard deviation.

Figure 9 .

 9 Figure 9. Q-values, after 150 episodes of training (30 000) env steps) for certain state. Left: DQN; Right: DQN with frontier loss. We can clearly see how the frontier-loss shapes Q-values, clearly separating forbidden action from good ones. This cherry-picked example illustrates well how the Q-distribution is modified, even at that early training stage.

  c) Reward Shaping: Lipton et al. (2016) introduced the notion of Intrinsic Fear (IF) to deal with dangerous states. Deep agents tend to periodically revisit these states upon forgetting their existence under a new policy. IF is shaping the reward to guard agents against periodic catastrophes. To achieve that they train a model to predict the probability of imminent dangerous state and it penalizes the true reward function R with an intrinsic reward F d) Large Discrete Action Space: A benefit of our method is to simplify policy space search when using bigger action space. Dealing with large discrete action space in Deep Reinforcement Learning was studied by Dulac-Arnold et al. (2015) where they use an action embedding in continuous space and map it to a discrete action. Recent methods build upon this by also learning the action embedding instead of using a precomputed one Adolphs and Hofmann (2019); Chandak et al. (2019); Chen et al. (2019); Tennenholtz and Mannor (2019) Another body of literature explores how to reduce combinatorial action space by using an encoding dictionary (Dulac-Arnold

Figure 10 .

 10 Figure 10. Q-values, after 100 000 training steps Left: DQN; Right: DQN-F . Even after 100 000 network updates, DQN still struggles to differentiate good action from bad ones. This cherry-picked example illustrates well how the Q-distribution is modified and how Q-values are kept separated even later during training.

Acknowledgments: The authors would like to acknowledge the stimulating research environment of the SequeL INRIA Project-Team. Special thanks to Florian Strub and Edouard Leurent for fruitful discussions. We acknowledge the following agencies for research funding and computing support: Project BabyRobot (H2020-ICT-24-2015, grant agreement no.687831), and CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020.

APPENDIX