Publications

2022

• LP-ROBIN: Link prediction in dynamic networks exploiting incremental node embedding
  
  • Barracchia Emanuele Pio
  • Pio Gianvito
  • Bifet Albert
  • Gomes Heitor Murilo
  • Pfahringer Bernhard
  • Ceci Michelangelo
  Information Sciences, Elsevier, 2022, 606, pp.702--721. In many real-world domains, data can naturally be represented as networks. This is the case of social networks, bibliographic networks, sensor networks and biological networks. Some dynamism often characterizes these networks as their structure (i.e., nodes and edges) continually evolves. Considering this dynamism is essential for analyzing these networks accurately. In this work, we propose LP-ROBIN, a novel method that exploits incremental embedding to capture the dynamism of the network structure and predicts new links, which can be used to suggest friends in social networks, or interactions in biological networks, just to cite some. Differently from the state-of-the-art methods, LP-ROBIN can work with mutable sets of nodes, i.e., new nodes may appear over time without being known in advance. After the arrival of new data, LP-ROBIN does not need to retrain the model from scratch, but learns the embeddings of the new nodes and links, and updates the latent representations of old ones, to reflect changes in the network structure for link prediction purposes. The experimental results show that LP-ROBIN achieves better performances, in terms of AUC and F1-score, and competitive running times with respect to baselines, static node embedding approaches and state-of-the-art methods which use dynamic node embedding. (10.1016/J.INS.2022.05.079)
  DOI : 10.1016/J.INS.2022.05.079
• How Cognitive Biases Affect XAI-assisted Decision-making: A Systematic Review
  
  • Bertrand Astrid
  • Belloum Rafik
  • Eagan James
  • Maxwell Winston
  , 2022. The field of eXplainable Artificial Intelligence (XAI) aims to bring transparency to complex AI systems. Although it is usually considered an essentially technical field, effort has been made recently to better understand users' human explanation methods and cognitive constraints. Despite these advances, the community lacks a general vision of what and how cognitive biases affect explainability systems. To address this gap, we present a heuristic map which matches human cognitive biases with explainability techniques from the XAI literature, structured around XAI-aided decision-making. We identify four main ways cognitive biases affect or are affected by XAI systems: 1) cognitive biases affect how XAI methods are designed, 2) they can distort how XAI techniques are evaluated in user studies, 3) some cognitive biases can be successfully mitigated by XAI techniques, and, on the contrary, 4) some cognitive biases can be exacerbated by XAI techniques. We construct this heuristic map through the systematic review of 37 papers-drawn from a corpus of 285-that reveal cognitive biases in XAI systems, including the explainability method and the user and task types in which they arise. We use the findings from our review to structure directions for future XAI systems to better align with people's cognitive processes. (10.1145/3514094.3534164)
  DOI : 10.1145/3514094.3534164
• Bayesian Information Gain to Design Interaction
  
  • Liu Wanyu
  • Rioul Olivier
  • Beaudouin-Lafon Michel
  , 2022. This chapter discusses a perspective on designing interaction by quantifying information that reduces the computer's uncertainty about the user's goal. We begin with how to quantify uncertainty and information using Shannon's information-theoretic terms and how to optimize decisions under uncertainty using an expected utility function with Bayesian Experimental Design. We then describe the BIG framework-Bayesian Information Gain-where the computer "runs experiments" on the user by sending feedback that maximizes the expected gain of information by the computer, and uses the users' subsequent input to update its knowledge as interaction progresses. We demonstrate a BIG application to multiscale navigation, discuss some limitations of the BIG framework and conclude with future possibilities.
• Choosing Among Notions of Multivariate Depth Statistics
  
  • Mosler Karl
  • Mozharovskyi Pavlo
  Statistical Science, Institute of Mathematical Statistics (IMS), 2022, 37 (3). (10.1214/21-STS827)
  DOI : 10.1214/21-STS827
• SASIMI: Evaluation Board for EM Information Leakage from Large Scale Cryptographic Circuits
  
  • Fujimoto Daisuke
  • Kim Youngwoo
  • Hayashi Yuichi
  • Homma Naofumi
  • Hashimoto Masanori
  • Sato Takashi
  • Danger Jean-Luc
  , 2022, pp.299-302. In this paper, we propose a common evaluation board(Side-channel Attack Standard IMplementation and eval-uatIon board: SASIMI) for the threat of acquiring information leaked from electromagnetic(EM) noise generated by devices. To prevent this threat, it is necessary to implement circuits that do not leak secret information, like a secret key, via EM side-channel, and conduct actual measurement and evaluation environment, which makes it difficult for a third party to reproduce the results. However, since captured EM activity is affected by the surrounding EM noise, the evaluation results may vary depending on the evaluation environment. The proposed evaluation board can implement various cryp-tographic circuits. The IC must be capable of reconfiguring logic and implementing large-scale cryptographic blocks such as post quantum cryptography. To reduce the influence of environmental EM noise, an independent power supply network and measurement port are provided for the IC to be evaluated thus improving the measurement reproducibility. In order to evaluate the performance of the SASIMI board, this paper proposes an index to evaluate the strength of the information of the secret key contained in the power supply noise. This index is to find the value of the resistance to be inserted into the power supply network of the prototype board. Measurement results show that the simple amplitude value of EM noise and the intensity of information leakage do not necessarily coincide (10.1109/EMCSI39492.2022.9889445)
  DOI : 10.1109/EMCSI39492.2022.9889445
• Side-Channel Expectation-Maximization Attacks
  
  • Béguinot Julien
  • Cheng Wei
  • Guilley Sylvain
  • Rioul Olivier
  IACR Transactions on Cryptographic Hardware and Embedded Systems, IACR, 2022, 2022 (4), pp.774-799. Block ciphers are protected against side-channel attacks by masking. On one hand, when the leakage model is unknown, second-order correlation attacks are typically used. On the other hand, when the leakage model can be profiled, template attacks are prescribed. But what if the profiled model does not exactly match that of the attacked device? One solution consists in regressing on-the-fly the scaling parameters from the model. In this paper, we leverage an Expectation-Maximization (EM) algorithm to implement such an attack. The resulting unprofiled EM attack, termed U-EM, is shown to be both efficient (in terms of number of traces) and effective (computationally speaking). Based on synthetic and real traces, we introduce variants of our U-EM attack to optimize its performance, depending on trade-offs between model complexity and epistemic noise. We show that the approach is flexible, in that it can easily be adapted to refinements such as different points of interest and number of parameters in the leakage model. (10.46586/tches.v2022.i4.774-799)
  DOI : 10.46586/tches.v2022.i4.774-799
• Non-asymptotic bounds of point-to-point communication with or without perfect feedback using alpha-information theory
  
  • Rioul Olivier
  • Nguyen Hang
  , 2022. Some results of alpha-information theory are pre- sented in order to derive simple non-asymptotic lower bounds on the probability of error for any binary block code used on symmetric channels with or without feedback. In particular, we obtain lower bounds on the signal-to-noise ratio for given code parameters and probability of error. (10.1109/ICCE55644.2022.9852067)
  DOI : 10.1109/ICCE55644.2022.9852067
• Mitigating Gender Bias in Face Recognition Using the von Mises-Fisher Mixture Model
  
  • Clémençon Stéphan
  • Conti Jean-Rémy
  • Noiry Nathan
  • Despiegel Vincent
  • Gentric Stéphane
  , 2022, PMLR 162:4344-4369. In spite of the high performance and reliability of deep learning algorithms in a wide range of everyday applications, many investigations tend to show that a lot of models exhibit biases, discriminating against specific subgroups of the population (e.g. gender, ethnicity). This urges the practitioner to develop fair systems with a uniform/comparable performance across sensitive groups. In this work, we investigate the gender bias of deep Face Recognition networks. In order to measure this bias, we introduce two new metrics, BFAR and BFRR, that better reflect the inherent deployment needs of Face Recognition systems. Motivated by geometric considerations, we mitigate gender bias through a new post-processing methodology which transforms the deep embeddings of a pre-trained model to give more representation power to discriminated subgroups. It consists in training a shallow neural network by minimizing a Fair von Mises-Fisher loss whose hyperparameters account for the intraclass variance of each gender. Interestingly, we empirically observe that these hyperparameters are correlated with our fairness metrics. In fact, extensive numerical experiments on a variety of datasets show that a careful selection significantly reduces gender bias.
• Self-supervised training strategies for SAR image despeckling with deep neural networks
  
  • Dalsasso Emanuele
  • Denis Loïc
  • Muzeau Max
  • Tupin Florence
  , 2022. Images acquired by Synthetic Aperture Radar (SAR) are affected by speckle, making their interpretation difficult. Most recently, the rise of deep learning algorithms has led to groundbreaking results. The training of a neural network typically requires matched pairs of speckled / speckle-free images. To account for the speckle present in actual images and simplify the generation of training sets, self-supervision approaches directly train the network on speckled SAR data. Self-supervision exploits a form of diversity, either temporal, spatial, or based on the real/imaginary parts. We compare the requirements in terms of data preprocessing and the performance of three self-supervised strategies.
• Brief Announcement: How to Tame Multiple Spending in Decentralized Cryptocurrencies
  
  • Bezerra João Paulo
  • Kuznetsov Petr
  , 2022, pp.427-429. The last decade has seen a variety of Asset-Transfer systems designed for decentralized environments. To address the problem of double-spending, these systems inherently make strong model assumptions and spend a lot of resources. In this paper, we take a non-orthodox approach to the double-spending problem that might suit better realistic environments in which these systems are to be deployed. We consider the decentralized trust setting, where each user may independently choose who to trust by forming its local quorums. In this setting, we define k-Spending Asset Transfer, a relaxed version of asset transfer which bounds the number of times the same asset can be spent. We establish a precise relationship between the decentralized trust assumptions and k, the optimal spending number of the system. (10.1145/3519270.3538465)
  DOI : 10.1145/3519270.3538465
• Brief Announcement
  
  • Freitas Luciano
  • Kuznetsov Petr
  • Tonkikh Andrei
  , 2022, pp.103-105. A major part of the results of this brief announcement is presented in detail in the technical report [8]. (10.1145/3519270.3538461)
  DOI : 10.1145/3519270.3538461
• Procédé d'appairage
  
  • Khalfaoui Sameh
  • Villard Arthur
  • MA Jingxuan
  • Leneutre Jean
  , 2022.
• Characterization of Optical Chaos in Mid-Infrared Interband Cascade Lasers: Towards High-Speed Free-Space Applications
  
  • Spitz O.
  • Zhao Shihao
  • Díaz-Thomas D.
  • Cerutti L.
  • Baranov A.
  • Rontani D.
  • Grillot Frédéric
  , 2022, pp.NpW2F.2. We analyze the dynamics features of 4.1 µ m optical chaos generated experimentally bya Fabry-Perot interband cascade laser. The numerical simulations we perform with the Lang-Kobayashi model are in good agreement with the experimental findings. (10.1364/NP.2022.NpW2F.2)
  DOI : 10.1364/NP.2022.NpW2F.2
• Data depth: computation, applications, and beyond
  
  • Mozharovskyi Pavlo
  , 2022.
• Quantum computation capability verification protocol for NISQ devices with dihedral coset problem
  
  • Lin Ruge
  • Wen Weiqiang
  Physical Review A, American Physical Society, 2022, 106 (1), pp.012430. In this article, we propose an interactive protocol for one party (the verifier) holding a quantum computer to verify the quantum computation power of another party's (the prover) device via a one-way quantum channel. This protocol is referred to as the dihedral coset problem (DCP) challenge. The verifier needs to prepare quantum states encoding secrets (DCP samples) and send them to the prover. The prover is then tasked with recovering those secrets with a certain accuracy. Numerical simulation demonstrates that this accuracy is sensitive to errors in quantum hardware. Additionally, the DCP challenge serves as a benchmarking protocol for locally fully connected quantum architecture and aims to be performed on current and near-future quantum resources. We conduct a 4-qubit experiment on one of the IBM Q devices. (10.1103/PhysRevA.106.012430)
  DOI : 10.1103/PhysRevA.106.012430
• Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
  
  • Bordage Sarah
  • Lhotel Mathieu
  • Nardi Jade
  • Randriam Hugues
  , 2022, pp.30:1--30:45. In this work, we initiate the study of proximity testing to Algebraic Geometry (AG) codes. An AG code C = C(X , P, D) is a vector space associated to evaluations on P of functions in the Riemann-Roch space L X (D). The problem of testing proximity to an error-correcting code C consists in distinguishing between the case where an input word, given as an oracle, belongs to C and the one where it is far from every codeword of C. AG codes are good candidates to construct short proof systems, but there exists no efficient proximity tests for them. We aim to fill this gap. We construct an Interactive Oracle Proof of Proximity (IOPP) for some families of AG codes by generalizing an IOPP for Reed-Solomon codes, known as the FRI protocol [BBHR18a]. We identify suitable requirements for designing efficient IOPP systems for AG codes. Our approach relies on a neat decomposition of the Riemann-Roch space of any invariant divisor under a group action on a curve into several explicit Riemann-Roch spaces on the quotient curve. We thus provide a framework in which a proximity test to C can be reduced to one to a simpler code C. Iterating this process thoroughly, we end up with a membership test to a code with significantly smaller length. As concrete instantiations, we study AG codes on Kummer curves and curves in the Hermitian tower. The latter can be defined over polylogarithmic-size alphabet. We specialize the generic AG-IOPP construction to reach linear prover running time and logarithmic verification on Kummer curves, and quasilinear prover time with polylogarithmic verification on the Hermitian tower. (10.4230/LIPIcs.CCC.2022.30)
  DOI : 10.4230/LIPIcs.CCC.2022.30
• Online Hyperparameter Optimization for Streaming Neural Networks
  
  • Gunasekara Nuwan
  • Gomes Heitor Murilo
  • Pfahringer Bernhard
  • Bifet Albert
  , 2022, pp.1--9. Neural networks have enjoyed tremendous success in many areas over the last decade. They are also receiving more and more attention in learning from data streams, which is inherently incremental. An incremental setting poses challenges for hyperparameter optimization, which is essential to obtain satisfactory network performance. To overcome this challenge, we introduce Continuously Adaptive Neural networks for Data streams (CAND). For every prediction, CAND chooses the current best network from a pool of candidates by continuously monitoring the performance of all candidate networks. The candidates are trained using different optimizers and hyperparameters. An experimental comparison against three state-of-the-art stream learning methods, over 17 benchmark streaming datasets con-firms the competitive performance of CAND, especially on high-dimensional data. We also investigate two orthogonal heuristics for accelerating Cand,which trade-off small amounts of accuracy for significant run-time gains. We observe that training on small mini-batches yields similar accuracy to single-instance fully incremental training, even on evolving data streams. (10.1109/IJCNN55064.2022.9891953)
  DOI : 10.1109/IJCNN55064.2022.9891953
• What is randomness? The interplay between alpha-entropies, total variation and guessing
  
  • Rioul Olivier
  , 2022, 5 (30), pp.30. In many areas of computer science, it is of primary importance to assess the randomness of a certain variable X. Many different criteria can be used to evaluate randomness, possibly after observing some disclosed data. A “sufficiently random” X is often described as “entropic”. Indeed, Shannon’s entropy is known to provide a resistance criterion against modeling attacks. More generally one may consider the Rényi α-entropy where Shannon’s entropy, collision entropy and min-entropy are recovered as particular cases α = 1, 2 and +∞, respectively. Guess work or guessing entropy is also of great interest in relation to α-entropy. On the other hand, many applications rely instead on the “statistical distance”, a.k.a. total variation distance to the uniform distribution. This criterion is particularly important because a very small distance ensures that no statistical test can effectively distinguish between the actual distribution and the uniform distribution. We establish optimal lower and upper bounds between α-entropy, guessing entropy on one hand, and error probability and total variation distance to the uniform on the other. In this context, it turns out that the best known “Pinsker inequality” and recent “reverse Pinsker inequalities” are not necessarily optimal. We recover or improve previous Fano-type and Pinsker-type inequalities used for several applications. (10.3390/psf2022005030)
  DOI : 10.3390/psf2022005030
• Adaptive Model Compression of Ensembles for Evolving Data Streams Forecasting
  
  • Boulegane Dihia
  • Cerquiera Vitor
  • Bifet Albert
  , 2022, pp.1--8. Ensemble methods combining several models have shown superior predictive performance in data streams forecasting compared to individual models. Besides, they can cope with evolving data streams and concept drift as they allow adaptation. However, ensembles are renowned for their complexity and computational costs which makes them unsuitable in cases where both resources and time are limited such as IoT applications. In this paper, we propose to use model compression in the streaming setting in order to overcome the aforementioned drawbacks. We show that compressing a highly performing dynamic ensemble into an individual model leads to better predictive performance when compared to an individual learner while significantly reducing computational costs. We conduct an extensive experimental study on both real and synthetic time series to measure the impact of compression on both predictive performance and computational cost. (10.1109/IJCNN55064.2022.9892811)
  DOI : 10.1109/IJCNN55064.2022.9892811
• Functional Output Regression with Infimal Convolution: Exploring the Huber and -insensitive Losses
  
  • Lambert Alex
  • Bouche Dimitri
  • Szabo Zoltan
  • d'Alché-Buc Florence
  , 2022, 162. The focus of the paper is functional output regression (FOR) with convoluted losses. While most existing work consider the square loss setting, we leverage extensions of the Huber and the-insensitive loss (induced by infimal convolution) and propose a flexible framework capable of handling various forms of outliers and sparsity in the FOR family. We derive computationally tractable algorithms relying on duality to tackle the resulting tasks in the context of vector-valued reproducing kernel Hilbert spaces. The efficiency of the approach is demonstrated and contrasted with the classical squared loss setting on both synthetic and real-world benchmarks.
• Learning to Predict Graphs with Fused Gromov-Wasserstein Barycenters
  
  • Brogat-Motte Luc
  • Flamary Rémi
  • Brouard Celine
  • Rousu Juho
  • d'Alché-Buc Florence
  , 2022, 162. This paper introduces a novel and generic framework to solve the flagship task of supervised labeled graph prediction by leveraging Optimal Transport tools. We formulate the problem as regression with the Fused Gromov-Wasserstein (FGW) loss and propose a predictive model relying on a FGW barycenter whose weights depend on inputs. First we introduce a non-parametric estimator based on kernel ridge regression for which theoretical results such as consistency and excess risk bound are proved. Next we propose an interpretable parametric model where the barycenter weights are modeled with a neural network and the graphs on which the FGW barycenter is calculated are additionally learned. Numerical experiments show the strength of the method and its ability to interpolate in the labeled graph space on simulated data and on a difficult metabolic identification problem where it can reach very good performance with very little engineering.
• Towards the Combination of Model Checking and Runtime Verification on Multi-agent Systems
  
  • Ferrando Angelo
  • Malvone Vadim
  , 2022.
• Sketched Newton--Raphson
  
  • Yuan Rui
  • Lazaric Alessandro
  • Gower Robert M
  SIAM Journal on Optimization, Society for Industrial and Applied Mathematics, 2022, 32 (3), pp.1555 - 1583. We propose a new globally convergent stochastic second-order method. Our starting point is the development of a new sketched Newton-Raphson (SNR) method for solving large scale nonlinear equations of the form F (x) = 0 with F : R p → R m. We then show how to design several stochastic second-order optimization methods by rewriting the optimization problem of interest as a system of nonlinear equations and applying SNR. For instance, by applying SNR to find a stationary point of a generalized linear model, we derive completely new and scalable stochastic second-order methods. We show that the resulting method is very competitive as compared to state-of-the-art variance reduced methods. Furthermore, using a variable splitting trick, we also show that the stochastic Newton method (SNM) is a special case of SNR and use this connection to establish the first global convergence theory of SNM. We establish the global convergence of SNR by showing that it is a variant of the online stochastic gradient descent (SGD) method, and then leveraging proof techniques of SGD. As a special case, our theory also provides a new global convergence theory for the original Newton-Raphson method under strictly weaker assumptions as compared to the classic monotone convergence theory. (10.1137/21m139788x)
  DOI : 10.1137/21m139788x
• The devil hides in the model: Reviewing Blockchain and BFT protocols
  
  • Durand Antoine
  • Memmi Gérard
  , 2022. Recent advances in blockchains and Byzantine Fault Tolerant protocols have been numerous and varied in nature. However, making a fair and consistent comparison of existing protocols is a difficult task that must begin right at the execution model. In this work, we undergo a review of several prominent blockchain protocols including their models, i.e., network synchrony, cryptographic assumptions, corruption, as well as latency and communication cost figures. This review illustrates the issues that can arise due to the lack of standardization on blockchain terminology. For example, we show that in two prominent blockchain protocols, seemingly minor technical details in the formulation leads to the execution model being strictly different from the intended one.
• Interband cascade technology for next-generation mid-IR communication and quantum applications
  
  • Spitz Olivier
  • Zhao Shiyuan
  • Didier Pierre
  • Diaz-Thomas Daniel Andres
  • Cerutti Laurent
  • Baranov Alexei
  • Knotig Hedwig
  • Weih Robert
  • Koth Johannes
  • Schwarz Benedikt
  • Grillot Frederic
  , 2022, pp.1-2. To achieve mid-infrared wavelength operation with semiconductor technology, efforts were mainly focused on in-tersubband devices requiring high voltage and current. In this work, we show our latest progress with energy -efficient interband emitters and receivers, paving the way towards application like free-space communication and squeezed light. (10.1109/SUM53465.2022.9858128)
  DOI : 10.1109/SUM53465.2022.9858128