Publications

2023

• Localization in 1D non-parametric latent space models from pairwise affinities
  
  • Giraud Christophe
  • Issartel Yann
  • Verzelen Nicolas
  Electronic Journal of Statistics, Shaker Heights, OH : Institute of Mathematical Statistics, 2023, 17 (1), pp.1587-1662. We consider the problem of estimating latent positions in a one-dimensional torus from pairwise affinities. The observed affinity between a pair of items is modeled as a noisy observation of a function f (x*i , x*j) of the latent positions x*i, x*j of the two items on the torus. The affinity func-tion f is unknown, and it is only assumed to fulfill some shape constraints ensuring that f(x, y) is large when the distance between x and y is small, and vice-versa. This non-parametric modeling offers a good flexibility to fit data. We introduce an estimation procedure that provably localizes all the latent positions with a maximum error of the order of log(n)/n, with high-probability. This rate is proven to be minimax optimal. A computa-tionally efficient variant of the procedure is also analyzed under some more restrictive assumptions. Our general results can be instantiated to the prob-lem of statistical seriation, leading to new bounds for the maximum error in the ordering. (10.1214/23-ejs2134)
  DOI : 10.1214/23-ejs2134
• Next generation of Bluetooth and Wi-Fi networks
  
  • Lim Keun-Woo
  , 2023.
• PROCÉDÉ D'ÉVALUATION DE L'ÉTAT RELATIF D'UN MOTEUR D'AÉRONEF
  
  • Pineau Edouard
  • Razakarivony Sébastien
  • Bonald Thomas
  , 2023.
• Nonatomic Non-Cooperative Neighbourhood Balancing Games
  
  • Auger David
  • Cohen Johanne
  • Lobstein Antoine
  , 2023. We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs. (10.48550/arXiv.2303.08507)
  DOI : 10.48550/arXiv.2303.08507
• DNA code from cyclic and skew cyclic codes over F 4 [v]/⟨v 3 ⟩
  
  • Prakash Om
  • Singh Ashutosh
  • Verma Ram Krishna
  • Solé Patrick
  • Cheng Wei
  Entropy, MDPI, 2023. The main motivation of this work is to study and obtain some reversible and DNA codes of length n with better parameters. Here, we first investigate the structure of cyclic and skew cyclic codes over the chain ring R : = F 4 [ v ] / ⟨ v 3 ⟩ . We show an association between the codons and the elements of R using a Gray map. Under this Gray map, we study reversible and DNA codes of length n. Finally, several new DNA codes are obtained that have improved parameters than previously known codes. We also determine the Hamming and the Edit distances of these codes. (10.3390/e25020239)
  DOI : 10.3390/e25020239
• Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient
  
  • Fercoq Olivier
  Open Journal of Mathematical Optimization, Centre Mersenne, 2023, 4, pp.1-34. We study the linear convergence of the primal-dual hybrid gradient method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems. Equipped with this tool, we manage to prove tighter convergence rates. Then, we show that averaging and restarting the primal-dual hybrid gradient allows us to leverage better the regularity constant. Numerical experiments on linear and quadratic programs, ridge regression and image denoising illustrate the findings of the paper. (10.5802/ojmo.26)
  DOI : 10.5802/ojmo.26
• ADT: AI-Driven network Telemetry processing on routers
  
  • Foroughi Parisa
  • Brockners Frank
  • Rougier Jean-Louis
  Computer Networks, Elsevier, 2023, 220, pp.109474-1:109474-17. Network monitoring is a pivotal part of network management and operations. It is responsible for monitoring the behavior of the network to assure its functionality within expectation and to guarantee a smooth-running environment for enabling of various services. Therefore, operators are interested in gaining a comprehensive assessment of their network elements and tracking operational changes to facilitate timely correction of any deviation. Commonly, this assessment is achieved by performing regular manual checks of different operational counters and defining expert rules from known root causes. The common approach requires the maintenance of a regularly updated set of rules and only goes as far as the operator's pre-gained knowledge of the system. With the growing complexity of the networks as well as the availability of more data, a more efficient monitoring approach is necessary to address the emerging network monitoring requirements. In this paper, a novel unsupervised approach is proposed that is capable of exploring a broader set of counters (not limited to the handpicked Key Performance Indicators (KPIs)). The goal is to leverage the dependencies between the counters in order to discover complex state changes that might have otherwise slipped the operator's view. This paper proposes ADT, an AI-driven telemetry processing solution that facilitates monitoring of a larger set of counters. The Detector block of ADT is known as DESTIN, a multivariate unsupervised change detection for high dimensional time-series data of originally low effective dimension, which provides near real-time state assessment of network devices. The efficiency of the proposed approach is demonstrated and compared with well-known methodologies on an experimental test-bed. The method's performance is also explored extensively considering different criteria such as traffic type, device and the type of events to identify its potentials and limitations. The datasets used for the evaluation are made publicly available. (10.1016/j.comnet.2022.109474)
  DOI : 10.1016/j.comnet.2022.109474
• Solving stochastic weak Minty variational inequalities without increasing batch size
  
  • Pethick Thomas
  • Fercoq Olivier
  • Latafat Puya
  • Patrinos Panagiotis
  • Cevher Volkan
  , 2023. This paper introduces a family of stochastic extragradient-type algorithms for a class of nonconvex-nonconcave problems characterized by the weak Minty variational inequality (MVI). Unlike existing results on extragradient methods in the monotone setting, employing diminishing stepsizes is no longer possible in the weak MVI setting. This has led to approaches such as increasing batch sizes per iteration which can however be prohibitively expensive. In contrast, our proposed methods involves two stepsizes and only requires one additional oracle evaluation per iteration. We show that it is possible to keep one fixed stepsize while it is only the second stepsize that is taken to be diminishing, making it interesting even in the monotone setting. Almost sure convergence is established and we provide a unified analysis for this family of schemes which contains a nonlinear generalization of the celebrated primal dual hybrid gradient algorithm.
• A Consistent Diffusion-Based Algorithm for Semi-Supervised Graph Learning
  
  • Bonald Thomas
  • de Lara Nathan
  , 2023. The task of semi-supervised classification aims at assigning labels to all nodes of a graph based on the labels known for a few nodes, called the seeds. One of the most popular algorithms relies on the principle of heat diffusion, where the labels of the seeds are spread by thermoconductance and the temperature of each node at equilibrium is used as a score function for each label. In this paper, we prove that this algorithm is not consistent unless the temperatures of the nodes at equilibrium are centered before scoring. This crucial step does not only make the algorithm provably consistent on a block model but brings significant performance gains on real graphs.
• Dynamic Autoencoders Against Adversarial Attacks
  
  • Chabanne Hervé
  • Despiegel Vincent
  • Gentric Stéphane
  • Guiga Linda
  Procedia Computer Science, Elsevier, 2023, 220, pp.782-787. Neural Networks are the target of numerous adversarial attacks. In those, the adversary perturbs a model's input with a noise that is small, but large enough to fool the model. In this article, we propose to dynamically add autoencoders from a pretrained set to a base model as a countermeasure to such attacks. This doing, we modify the underlying labels regions of the model to be protected, letting the adversary unable to craft relevant adversarial perturbations. Our experiments confirm the efficiency of our protection when the pretrained set has enough elements. (10.1016/j.procs.2023.03.104)
  DOI : 10.1016/j.procs.2023.03.104
• Proceedings of The Semantic Web: ESWC 2023 Satellite Events
  
  • Pesquita Catia
  • Skaf-Molli Hala
  • Efthymiou Vasilis
  • Kirrane Sabrina
  • Ngonga Axel
  • Collarana Diego
  • Cerqueira Renato
  • Alam Mehwish
  • Trojahn Cassia
  • Hertling Sven
  , 2023, 13998. (10.1007/978-3-031-43458-7)
  DOI : 10.1007/978-3-031-43458-7
• Online Matching in Geometric Random Graphs
  
  • Sentenac Flore
  • Noiry Nathan
  • Lerasle Matthieu
  • Ménard Laurent
  • Perchet Vianney
  , 2023. We investigate online maximum cardinality matching, a central problem in ad allocation. In this problem, users are revealed sequentially, and each new user can be paired with any previously unmatched campaign that it is compatible with. Despite the limited theoretical guarantees, the greedy algorithm, which matches incoming users with any available campaign, exhibits outstanding performance in practice. Some theoretical support for this practical success has been established in specific classes of graphs, where the connections between different vertices lack strong correlations-an assumption not always valid in real-world situations. To bridge this gap, we focus on the following model: both users and campaigns are represented as points uniformly distributed in the interval [0, 1], and a user is eligible to be paired with a campaign if they are "similar enough," meaning the distance between their respective points is less than c/N , where c > 0 is a model parameter. As a benchmark, we determine the size of the optimal offline matching in these bipartite random geometric graphs. We achieve this by introducing an algorithm that constructs the optimal matching and analyzing it. We then turn to the online setting and investigate the number of matches made by the online algorithm CLOSEST, which pairs incoming points with their nearest available neighbors in a greedy manner. We demonstrate that the algorithm's performance can be compared to its fluid limit, which is completely characterized as the solution to a specific partial differential equation (PDE). From this PDE solution, we can compute the competitive ratio of CLOSEST, and our computations reveal that it remains significantly better than its worst-case guarantee. This model turns out to be closely related to the online minimum cost matching problem, and we can extend the results obtained here to refine certain findings in that area of research. Specifically, we determine the exact asymptotic cost of CLOSEST in the ϵ-excess regime, providing a more accurate estimate than the previously known loose upper bound.
• Manifold Learning via Linear Tangent Space Alignment (LTSA) for Accelerated Dynamic MRI With Sparse Sampling
  
  • Djebra Yanis
  • Marin Thibault
  • Han Paul K
  • Bloch Isabelle
  • Fakhri Georges El
  • Ma Chao
  IEEE Transactions on Medical Imaging, Institute of Electrical and Electronics Engineers, 2023, 42 (1), pp.158-169. The spatial resolution and temporal framerate of dynamic magnetic resonance imaging (MRI) can be improved by reconstructing images from sparsely sampled k-space data with mathematical modeling of the underlying spatiotemporal signals. These models include sparsity models, linear subspace models, and non-linear manifold models. This work presents a novel linear tangent space alignment (LTSA) model-based framework that exploits the intrinsic low-dimensional manifold structure of dynamic images for accelerated dynamic MRI. The performance of the proposed method was evaluated and compared to stateof-the-art methods using numerical simulation studies as well as 2D and 3D in vivo cardiac imaging experiments. The proposed method achieved the best performance in image reconstruction among all the compared methods. The proposed method could prove useful for accelerating many MRI applications, including dynamic MRI, multi-parametric MRI, and MR spectroscopic imaging. (10.1109/TMI.2022.3207774)
  DOI : 10.1109/TMI.2022.3207774
• Some Complexity Considerations on the Uniqueness of Graph Colouring
  
  • Hudry Olivier
  • Lobstein Antoine
  WSEAS Transactions on Mathematics, World Scientific and Engineering Academy and Society (WSEAS), 2023, 22, pp.art. #54, 483-493. For some well-known NP-complete problems, linked to the satisfiability of Boolean formulas and the colourability of a graph, we study the variation which consists in asking about the uniqueness of a solution.In particular, we show that five decision problems, Unique Satisfiability (U-SAT), Unique k-Satisfiability (U-k-SAT), k ≥ 3, Unique One-in-Three Satisfiability (U-1-3-SAT), Unique k-Colouring (U-k-COL), k ≥ 3, and Unique Colouring (U-COL), have equivalent complexities, up to polynomials —when dealing with colourings, we forbid permutations ofcolours. As a consequence, all are NP-hard and belong to the class DP. We also consider the problems U-2-SAT, U-2-COL and Unique Optimal Colouring (U-OCOL). (10.37394/23206.2023.22.54)
  DOI : 10.37394/23206.2023.22.54
• Towards a Development Process for Multi-CPU Distributed Synchronous Software Applications
  
  • Lubat Eric
  • Jenn Eric
  • Blouin Dominique
  • Kaufmann Marc
  Psychology in Spain, Colegio Oficial de Psicólogos, 2023, pp.549-558. (10.1109/MODELS-C59198.2023.00092)
  DOI : 10.1109/MODELS-C59198.2023.00092
• Improving Causal Learning Scalability and Performance using Aggregates and Interventions
  
  • Fadiga Kanvaly
  • Houzé Etienne
  • Diaconescu Ada
  • Dessalles Jean-Louis
  ACM Transactions on Autonomous and Adaptive Systems, Association for Computing Machinery (ACM), 2023. Smart homes are Cyber-Physical Systems (CPS) where multiple devices and controllers cooperate to achieve high-level goals. Causal knowledge on relations between system entities is essential for enabling system self-adaption to dynamic changes. As house configurations are diverse, this knowledge is difficult to obtain. In previous work, we proposed to generate Causal Bayesian Networks (CBN) as follows. Starting with considering all possible relations, we progressively discarded non-correlated variables. Next, we identified causal relations from the remaining correlations by employing “ do-operations ”. The obtained CBN could then be employed for causal inference. The main challenges of this approach included: “non-doable variables” and limited scalability. To address these issues, we propose three extensions: i) early pruning weakly correlated relations to reduce the number of required do-operations; ii) introducing aggregate variables that summarize relations between weakly-coupled sub-systems; iii) applying the method a second time to perform indirect do interventions and handle non-doable relations. We illustrate and evaluate the efficiency of these contributions via examples from the smart home and power grid domain. Our proposal leads to a decrease in the number of operations required to learn the CBN and in an increased accuracy of the learned CBN, paving the way towards applications in large CPS. (10.1145/3607872)
  DOI : 10.1145/3607872
• Affine invariant integrated rank-weighted statistical depth: properties and finite sample analysis
  
  • Clémençon Stephan
  • Mozharovskyi Pavlo
  • Staerman Guillaume
  Electronic Journal of Statistics, Shaker Heights, OH : Institute of Mathematical Statistics, 2023, 17 (2), pp.3854 - 3892. Because it determines a center-outward ordering of observations in Rd with d≥2, the concept of statistical depth permits to define quantiles and ranks for multivariate data and use them for various statistical tasks (e.g. inference, hypothesis testing). Whereas many depth functions have been proposed ad-hoc in the literature since the seminal contribution of [50], not all of them possess the properties desirable to emulate the notion of quantile function for univariate probability distributions. In this paper, we propose an extension of the integrated rank-weighted statistical depth (IRW depth in abbreviated form) originally introduced in [40], modified in order to satisfy the property of affine invariance, fulfilling thus all the four key axioms listed in the nomenclature elaborated by [59]. The variant we propose, referred to as the affine invariant IRW depth (AI-IRW in short), involves the precision matrix of the (supposedly square integrable) d-dimensional random vector X under study, in order to take into account the directions along which X is most variable to assign a depth value to any point x∈Rd. The accuracy of the sampling version of the AI-IRW depth is investigated from a non-asymptotic perspective. Namely, a concentration result for the statistical counterpart of the AI-IRW depth is proved. Beyond the theoretical analysis carried out, applications to anomaly detection are considered and numerical results are displayed, providing strong empirical evidence of the relevance of the depth function we propose here. (10.1214/23-EJS2189)
  DOI : 10.1214/23-EJS2189
• Zero-shot spatial layout conditioning for text-to-image diffusion models
  
  • Couairon Guillaume
  • Careil Marlène
  • Cord Matthieu
  • Lathuilière Stéphane
  • Verbeek Jakob
  , 2023. Large-scale text-to-image diffusion models have significantly improved the state of the art in generative image modelling and allow for an intuitive and powerful user interface to drive the image generation process. Expressing spatial constraints, e.g. to position specific objects in particular locations, is cumbersome using text; and current text-based image generation models are not able to accurately follow such instructions. In this paper we consider image generation from text associated with segments on the image canvas, which combines an intuitive natural language interface with precise spatial control over the generated content. We propose ZestGuide, a zero-shot segmentation guidance approach that can be plugged into pre-trained text-to-image diffusion models, and does not require any additional training. It leverages implicit segmentation maps that can be extracted from cross-attention layers, and uses them to align the generation with input masks. Our experimental results combine high image quality with accurate alignment of generated content with input segmentations, and improve over prior work both quantitatively and qualitatively, including methods that require training on images with corresponding segmentations. Compared to Paint with Words, the previous state-of-the art in image generation with zero-shot segmentation conditioning, we improve by 5 to 10 mIoU points on the COCO dataset with similar FID scores.
• Test your samples jointly: Pseudo-reference for image quality evaluation
  
  • Tworski Marcelin
  • Lathuilière Stéphane
  , 2023. In this paper, we address the well-known image quality assessment problem but in contrast from existing approaches that predict image quality independently for every images, we propose to jointly model different images depicting the same content to improve the precision of quality estimation. This proposal is motivated by the idea that multiple distorted images can provide information to disambiguate image features related to content and quality. To this aim, we combine the feature representations from the different images to estimate a pseudo-reference that we use to enhance score prediction. Our experiments show that at test-time, our method successfully combines the features from multiple images depicting the same new content, improving estimation quality.
• Few-shot Semantic Image Synthesis with Class Affinity Transfer
  
  • Careil Marlène
  • Verbeek Jakob
  • Lathuilière Stéphane
  , 2023. Semantic image synthesis aims to generate photo realistic images given a semantic segmentation map. Despite much recent progress, training them still requires large datasets of images annotated with per-pixel label maps that are extremely tedious to obtain. To alleviate the high annotation cost, we propose a transfer method that leverages a model trained on a large source dataset to improve the learning ability on small target datasets via estimated pairwise relations between source and target classes. The class affinity matrix is introduced as a first layer to the source model to make it compatible with the target label maps, and the source model is then further finetuned for the target domain. To estimate the class affinities we consider different approaches to leverage prior knowledge: semantic segmentation on the source domain, textual label embeddings, and self-supervised vision features. We apply our approach to GAN-based and diffusion-based architectures for semantic synthesis. Our experiments show that the different ways to estimate class affinity can be effectively combined, and that our approach significantly improves over existing state-of-the-art transfer approaches for generative image models.
• Visualization Empowerment: How to Teach and Learn Data Visualization
  
  • Bach Benjamin
  • Carpendale Sheelagh
  • Hinrichs Uta
  • Huron Samuel
  , 2023, pp.10.4230/DagRep.12.6.83. Data visualization is becoming an important asset for a data-literate, informed, and critical society. Despite the variety of existing resources to teach theories and practical skills in this domain, little is known about 1) how learning processes in the context of visualization unfold and 2) best practices for engaging and teaching data visualization to diverse audiences and in different contexts. This Dagstuhl Seminar invited practitioners, researchers, and teachers from the areas of visualization, design, education and cognitive psychology to explore these questions from multiple perspectives. Through a range of practical activities, talks, and discussions, we have begun characterizing and classifying teaching methodologies. We have redacted a pedagogical manifesto, and started formalizing the concept of improvisation with visualization in the context of teaching and learning. We have also interrogated creativity as an important aspect of visualization teaching and learning and explored links between data physicalization and visualization teaching activities. Across these different themes, we have begun to map out the challenges of visualization teaching and learning and the opportunities for research and practice in this area. (10.4230/DagRep.12.6.83)
  DOI : 10.4230/DagRep.12.6.83
• Parallelizable Synthesis of Arbitrary Single-Qubit Gates with Linear Optics and Time-Frequency Encoding
  
  • Henry Antoine
  • Raghunathan Ravi
  • Ricard Guillaume
  • Lefaucher Baptiste
  • Miatto Filippo
  • Belabas Nadia
  • Zaquine Isabelle
  • Alléaume Romain
  Physical Review A, American Physical Society, 2023, 107, pp.062610. We propose novel methods for the exact synthesis of single-qubit unitaries with high success probability and gate fidelity, considering both time-bin and frequency-bin encodings. The proposed schemes are experimentally implementable with a spectral linear-optical quantum computation (S-LOQC) platform, composed of electro-optic phase modulators and phase-only programmable filters (pulse shapers). We assess the performances in terms of fidelity and probability of the two simplest 3-components configurations for arbitrary gate generation in both encodings and give an exact analytical solution for the synthesis of an arbitrary single-qubit unitary in the time-bin encoding, using a single-tone Radio Frequency (RF) driving of the EOMs. We further investigate the parallelization of arbitrary single-qubit gates over multiple qubits with a compact experimental setup, both for spectral and temporal encodings. We systematically evaluate and discuss the impact of the RF bandwidththat conditions the number of tones driving the modulators-and of the choice of encoding for different targeted gates. We moreover quantify the number of high fidelity Hadamard gates that can be synthesized in parallel, with minimal and increasing resources in terms of driving RF tones in a realistic system. Our analysis positions spectral S-LOQC as a promising platform to conduct massively parallel single qubit operations, with potential applications to quantum metrology and quantum tomography. (10.1103/PhysRevA.107.062610)
  DOI : 10.1103/PhysRevA.107.062610
• Provably Efficient Learning of Phases of Matter via Dissipative Evolutions
  
  • Onorati Emilio
  • Rouzé Cambyse
  • Watson James
  • Stilck França Daniel
  , 2023. The combination of quantum many-body and machine learning techniques has recently proved to be a fertile ground for new developments in quantum computing. Several works have shown that it is possible to classically efficiently predict the expectation values of local observables on all states within a phase of matter using a machine learning algorithm after learning from data obtained from other states in the same phase. However, existing results are restricted to phases of matter such as ground states of gapped Hamiltonians and Gibbs states that exhibit exponential decay of correlations. In this work, we drop this requirement and show how it is possible to learn local expectation values for all states in a phase, where we adopt the Lindbladian phase definition by Coser \& Pérez-García [Coser \& Pérez-García, Quantum 3, 174 (2019)], which defines states to be in the same phase if we can drive one to other rapidly with a local Lindbladian. This definition encompasses the better-known Hamiltonian definition of phase of matter for gapped ground state phases, and further applies to any family of states connected by short unitary circuits, as well as non-equilibrium phases of matter, and those stable under external dissipative interactions. Under this definition, we show that $N = O(\log(n/δ)2^{polylog(1/ε)})$ samples suffice to learn local expectation values within a phase for a system with $n$ qubits, to error $ε$ with failure probability $δ$. This sample complexity is comparable to previous results on learning gapped and thermal phases, and it encompasses previous results of this nature in a unified way. Furthermore, we also show that we can learn families of states which go beyond the Lindbladian definition of phase, and we derive bounds on the sample complexity which are dependent on the mixing time between states under a Lindbladian evolution. (10.48550/arXiv.2311.07506)
  DOI : 10.48550/arXiv.2311.07506
• Pseudo-Bayesian Approach for Robust Mode Detection and Extraction Based on the STFT
  
  • Legros Quentin
  • Fourer Dominique
  Sensors, MDPI, 2023, 23 (1), pp.85. This paper addresses the problem of disentangling nonoverlapping multicomponent signals from their observation being possibly contaminated by external additive noise. We aim to extract and to retrieve the elementary components (also called modes) present in an observed nonstationary mixture signal. To this end, we propose a new pseudo-Bayesian algorithm to perform the estimation of the instantaneous frequency of the signal modes from their time-frequency representation. In a second time, a detection algorithm is developed to restrict the time region where each signal component behaves, to enhance quality of the reconstructed signal. We finally deal with the presence of noise in the vicinity of the estimated instantaneous frequency by introducing a new reconstruction approach relying on nonbinary band-pass synthesis filters. We validate our methods by comparing their reconstruction performance to state-of-the-art approaches through several experiments involving both synthetic and real-world data under different experimental conditions. (10.3390/s23010085)
  DOI : 10.3390/s23010085
• Sparse Graph Neural Networks with Scikit-network
  
  • Bonald Thomas
  • Delarue Simon
  , 2023. In recent years, Graph Neural Networks (GNNs) have undergone rapid development and have become an essential tool for building representations of complex relational data. Large real-world graphs, characterised by sparsity in relations and features, necessitate dedicated tools that existing dense tensor-centred approaches cannot easily provide. To address this need, we introduce a GNNs module in Scikit-network, a Python package for graph analysis, leveraging sparse matrices for both graph structures and features. Our contribution enhances GNNs efficiency without requiring access to significant computational resources, unifies graph analysis algorithms and GNNs in the same framework, and prioritises user-friendliness.