In this paper, we introduce Edges , a novel deep architecture that aims at predicting the Graph Edit Distance (GED). Edges reformulates the quadratic assignment problem (QAP) associated to the GED problem as an edge prediction task within a GED instance graph constructed from the input graph pair. It uses a 3-Weisfeiler-Lehman expressive GNN, enabling to embed structural information at the edge level on this GED instance graph . It bypasses the need for costly matching solvers by directly predicting a soft assignment matrix through an end-to-end architecture. Extensive experiments on benchmark datasets demonstrate that the method enhances prediction accuracy through structural awareness while maintaining computational efficiency.

Since the advent of Graph Neural Networks (GNNs), many works have computed distances between graphs by embedding them in vector spaces using Message Passing GNNs (MPNNs).However, MPNNs are known for their lack of expressiveness as they are bounded by the firstorder Weisfeiler-Lehman test.In this paper, we use higher-order GNNs to tackle the metric learning problem and show on benchmark datasets how they can improve performance by using a node-level strategy and the Wasserstein distance. IntroductionA key challenge in modeling structured information with graphs lies in computing the distances between them.The Graph Edit Distance(GED)[4] is a state-ofthe-art method for this purpose; however, it suffers from NP-hard complexity.Recently, several architectures have been proposed to address this limitation [9,7,8,11,12] in a learning framework.These architectures generally consist of two main components.The first is an embedding block that uses siamese Graph Neural Networks(GNNs) to embed graphs either at the graph level or at the node level.The second component is a metric block that takes the embeddings generated by the first block as input and computes the distance between graphs, taking into account the embedding level.The rationale behind these architectures is that the embedding block learns an optimal representation to facilitate the computations in the metric block.To the best of our knowledge, existing embedding blocks in the literature rely on simple yet effective Message Passing Neural Networks(MPNNs), such as GCN [3] or GIN [2].Consequently, they suffer from the well-known limitations of MPNNs, including over-smoothing, over-squashing, and limited expressive power.This last limitation is particularly significant for metric learning, as it affects the ability to generate distinct embeddings for different graphs.Yet, GCN and GIN models have been shown to be at most equivalent to the firstorder Weisfeiler-Lehman(WL) test in the WL hierarchy [1].Recently, more expressive GNNs such as PPGN [5] and G 2 N 2 [6] have been introduced in the literature, achieving a 3-WL expressivity level.To attain this level of expressivity, these architectures naturally incorporate edge embeddings, adding valuable information to the traditional node-and graph-level representations.These recent developments raise two research questions: how can 3-WL GNNs be integrated into a metric learning framework, and do they enable improved performance?283

This paper presents Grammar Reinforcement Learning (GRL), a reinforcement learning algorithm that uses Monte Carlo Tree Search (MCTS) and a transformer architecture that models a Pushdown Automaton (PDA) within a context-free grammar (CFG) framework. Taking as use case the problem of efficiently counting paths and cycles in graphs, a key challenge in network analysis, computer science, biology, and social sciences, GRL discovers new matrix-based formulas for path/cycle counting that improve computational efficiency by factors of two to six w.r.t state-of-the-art approaches. Our contributions include: (i) a framework for generating transformers that operate within a CFG, (ii) the development of GRL for optimizing formulas within grammatical structures, and (iii) the discovery of novel formulas for graph substructure counting, leading to significant computational improvements.

Universal Domain Adaptation (UniDA) aims to transfer knowledge from a labeled source domain to an unlabeled target domain, even when their classes are not fully shared. Few dedicated UniDA methods exist for Time Series (TS), which remains a challenging case. In general, UniDA approaches align common class samples and detect unknown target samples from emerging classes. Such detection often results from thresholding a discriminability metric. The threshold value is typically either a fine-tuned hyperparameter or a fixed value, which limits the ability of the model to adapt to new data. Furthermore, discriminability metrics exhibit overconfidence for unknown samples, leading to misclassifications. This paper introduces UniJDOT, an optimal-transport-based method that accounts for the unknown target samples in the transport cost. Our method also proposes a joint decision space to improve the discriminability of the detection module. In addition, we use an auto-thresholding algorithm to reduce the dependence on fixed or fine-tuned thresholds. Finally, we rely on a Fourier transform-based layer inspired by the Fourier Neural Operator for better TS representation. Experiments on TS benchmarks demonstrate the discriminability, robustness, and state-of-the-art performance of UniJDOT.

ABSTRACT This paper presents a novel approach to pollution assessment by investigating support vector machines (SVM) with an uncertainty option to overcome the limitations of traditional kriging. While kriging is a major tool for geostatistical modelling, allowing to estimate the distribution of contaminants in a region from a small set of samples, it does not allow to extract also the uncertainty map. An uncertainty map is of great interest, as it allows to identify regions of high uncertainty where one should sample in order to reduce high level of uncertainties. In this paper, we propose two variants of the SVM with an uncertainty option, each using a different hinge loss to improve the accuracy and efficiency. These losses allow to estimate different levels of contaminations, as well as uncertainty, such as the three levels: positive, uncertain and negative, namely for pollution estimation: high‐pollution, uncertain and low‐pollution. In addition to the exploration of SVM variants, we propose an innovative active sample selection strategy based on the uncertainty criterion. This strategy is designed to systematically reduce uncertainties in pollution assessment, thus providing adaptability to dynamic environmental changes. An incremental SVM with an uncertainty option is introduced to further optimise the sample selection process. Furthermore, the decision‐making process is refined through the introduction of a novel three‐hinge loss. The corresponding optimization problem and its resolution allow for a more nuanced contamination assessment with multiple levels of estimation, providing a valuable tool for characterising contamination levels with increased granularity. Extensive experiments on synthetic and real data validate the proposed methodology. Synthetic data simulations assess the quality of the approach, while real data from a two‐dimensional porosity measurement demonstrate practical applicability. This research contributes to the advancement of pollution assessment methodologies, providing an adaptable solution for environmental monitoring.

Contrastive learning has demonstrated great effectiveness in representation learning especially for image classification tasks. However, there is still a shortage in the studies targeting regression tasks, and more specifically applications on hyperspectral data. In this paper, we propose a contrastive learning framework for the regression tasks for hyperspectral data. To this end, we provide a collection of transformations relevant for augmenting hyperspectral data, and investigate contrastive learning for regression. Experiments on synthetic and real hyperspectral datasets show that the proposed framework and transformations significantly improve the performance of regression models, achieving better scores than other state-of-the-art transformations.

This paper introduces a framework for formally establishing a connection between a portion of an algebraic language and a Graph Neural Network (GNN). The framework leverages Context-Free Grammars (CFG) to organize algebraic operations into generative rules that can be translated into a GNN layer model. As CFGs derived directly from a language tend to contain redundancies in their rules and variables, we present a grammar reduction scheme. By applying this strategy, we define a CFG that conforms to the third-order Weisfeiler-Lehman (3-WL) test using the matricial language MATLANG. From this 3-WL CFG, we derive a GNN model, named G$^2$N$^2$, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficiency of G$^2$N$^2$ compared to other 3-WL GNNs across numerous downstream tasks. Specifically, one experiment highlights the benefits of grammar reduction within our framework.

We propose a novel approach for comparing distributions whose supports do not necessarily lie on the same metric space. Unlike Gromov-Wasserstein (GW) distance which compares pairwise distances of elements from each distribution, we consider a method allowing to embed the metric measure spaces in a common Euclidean space and compute an optimal transport (OT) on the embedded distributions. This leads to what we call a sub-embedding robust Wasserstein (SERW) distance. Under some conditions, SERW is a distance that considers an OT distance of the (low-distorted) embedded distributions using a common metric. In addition to this novel proposal that generalizes several recent OT works, our contributions stand on several theoretical analyses: (i) we characterize the embedding spaces to define SERW distance for distribution alignment; (ii) we prove that SERW mimics almost the same properties of GW distance, and we give a cost relation between GW and SERW. The paper also provides some numerical illustrations of how SERW behaves on matching problems.

We introduce in this paper a novel strategy for efficiently approximating the Sinkhorn distance between two discrete measures. After identifying neglectable components of the dual solution of the regularized Sinkhorn problem, we propose to screen those components by directly setting them at that value before entering the Sinkhorn problem. This allows us to solve a smaller Sinkhorn problem while ensuring approximation with provable guarantees. More formally, the approach is based on a new formulation of dual of Sinkhorn divergence problem and on the KKT optimality conditions of this problem, which enable identification of dual components to be screened. This new analysis leads to the Screenkhorn algorithm. We illustrate the efficiency of Screenkhorn on complex tasks such as dimensionality reduction and domain adaptation involving regularized optimal transport.

This paper introduces a new approach for the scalable Tucker decomposition problem. Given a tensor X , the method proposed allows to infer the latent factors by processing one subtensor drawn from X at a time. The key principle of our approach is based on the recursive computations of gradient and on cyclic update of factors involving only one single step of gradient descent. We further improve the computational efficiency of this algorithm by proposing an inexact gradient version. These two algorithms are backed with theoretical guarantees of convergence and convergence rate under mild conditions. The scalabilty of the proposed approaches which can be easily extended to handle some common constraints encountered in tensor decomposition (e.g non-negativity), is proven via numerical experiments on both synthetic and real data sets.

Principal Component Analysis (PCA) is a canonical and well-studied tool for dimensionality reduction. However, when few data are available, the poor quality of the covariance estimator at its core may compromise its performance. We leverage this issue by casting the PCA into a multitask framework, and doing so, we show how to solve simultaneously several related PCA problems. Hence, we propose a novel formulation of the PCA problem relying on a novel regularization. This regularization is based on a distance between subspaces, and the whole problem is solved as an optimization problem over a Riemannian manifold. We experimentally demonstrate the usefulness of our approach as pre-processing for EEG signals.

We propose a brain tumor segmentation method from multi-spectral MRI images. First, a large set of features based on wavelet coefficients, is computed on all types of images for a small number of voxels, allowing us to build a training feature base which is not homogeneous due to different types of image. The segmentation task is then viewed as a learning problem where only the most significant features from the feature base should be selected and then a classifier can be used. The new idea is to use Multiple Kernel Learning (MKL) by associating one or more kernels to each feature in order to solve jointly the two problems: selection of the features and their corresponding kernels and training of the classifier. All types of images are then segmented using the trained classifier on the selected features. Our algorithm was tested on the real data provided by the challenge of Brats 2012 and was compared to the resulting top methods. The results show good performance of our method.

This paper addresses the problem of principal subspace tracking in presence of a colored noise. We propose to extend the YAST algorithm to handle such a case. We also propose a Riemannian framework that could benefit to other classical trackers. Finally, as a proof of concept, our method is compared to the only oblique tracker of the literature on a toy dataset.