Linear Sum Assignment Problem (LSAP) consists in mapping two sets of points of equal sizes according to a matrix encoding the cost of mapping each pair of points. The Linear Sum Assignment Problem with Edition (LSAPE) extends this problem by allowing the mapping of sets of different sizes and adding the possibility to reject some matchings. This problem is set up by a rectangular cost matrix whose last column and last line encode the costs of rejecting the match of an element of respectively the first and the second sets. LSAPE has been the workhorse of many fundamental graph problems such as graph edit distance, median graph computation or sub graph matching. LSAP may be solved using the Hungarian algorithm while an equivalent efficient discrete algorithm has been designed for LSAPE. However, while the Sinkhorn algorithm constitutes a continuous solver for LSAP, no such algorithm yet exists for LSAPE. This lack of solvers forbids the integration of LSAPE in Neural networks requiring continuous operations from the input to the final loss. This paper aims at providing such a solver, hence paving the way to an integration of LSAPE solvers in Neural Networks.

Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in $\mathcal{O}(n^3)$ with memory usage in $\mathcal{O}(n^2)$, consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks.

In this paper, we present GMG-BCU — a local search algorithm based on block coordinate update for estimating a generalized median graph for a given collection of labeled or unlabeled input graphs. Unlike all competitors, GMG-BCU is designed for both discrete and continuous label spaces and can be configured to run in linear time w. r. t. the size of the graph collection whenever median node and edge labels are computable in linear time. These properties make GMG-BCU usable for applications such as differential microbiome data analysis, graph classification, clustering, and indexing. We also prove theoretical properties of generalized median graphs, namely, that they exist under reasonable assumptions which are met in almost all application scenarios, that they are in general non-unique, that they are NP-hard to compute and APX-hard to approximate, and that no polynomial α-approximation exists for any α unless the graph isomorphism problem is in P. Extensive experiments on six different datasets show that our heuristic GMG-BCU always outperforms the state of the art in terms of runtime or quality (on most datasets, both w. r. t. runtime and quality), that it is the only available heuristic which can cope with collections containing several thousands of graphs, and that it shows very promising potential when used for the aforementioned applications. GMG-BCU is freely available on GitHub: https://github.com/dbblumenthal/gedlib/.

Solving or approximating the linear sum assignment problem (LSAP) is an important step of several constructive and local search strategies developed to approximate the graph edit distance (GED) of two attributed graphs, or more generally the solution to quadratic assignment problems. Constructive strategies find a first estimation of the GED by solving an LSAP. This estimation is then refined by a local search strategy. While these search strategies depend strongly on the initial assignment, several solutions to the linear problem usually exist. They are not taken into account to get better estimations. All the estimations of the GED based on an LSAP select randomly one solution. This paper explores the insights provided by the use of several solutions to an LSAP, refined in parallel by a local search strategy based on the relaxation of the search space, and conditional gradient descent. Other generators of initial assignments are also considered, approximate solutions to an LSAP and random assignments. Experimental evaluations on several datasets show that the proposed estimation is comparable to more global search strategies in a reduced computational time.

The graph edit distance (GED) measures the amount of distortion needed to transform a graph into another graph. Such a distance, developed in the context of error-tolerant graph matching, is one of the most flexible tool used in structural pattern recognition. However, the computation of the exact GED is NP-complete. Hence several suboptimal solutions, such as the ones based on bipartite assignments with edition, have been proposed. In this paper we propose a binary quadratic programming problem whose global minimum corresponds to the exact GED. This problem is interpreted as a quadratic assignment problem (QAP) where some constraints have been relaxed. This allows to adapt the integer projected fixed point algorithm, initially designed for the QAP, to efficiently compute an approximate GED by finding an interesting local minimum. Experiments show that our method remains quite close to the exact GED for datasets composed of small graphs, while keeping low execution times on datasets composed of larger graphs.

In this paper we propose an improvement of a human action recognition method that uses a string-based representation and a string edit distance to compare the observed action with reference actions in the training set. In particular, the original improvement is based on a specific formulation of the string edit distance that is more suited to take into account the problems related to noise and to different execution speeds that are observed in an action recognition system. The experimentation has been carried out on two widely adopted datasets, namely the MIVIA and the MHAD datasets, and the obtained results, compared with both the original method and other state of the art approaches, confirm the significance of the proposed improvement and the effectiveness of the method.

Chemo informatics aims to predict molecular properties using informational methods. Computer science's research fields concerned by this domain are machine learning and graph theory. An interesting approach consists in using graph kernels which allow to combine graph theory and machine learning frameworks. Graph kernels allow to define a similarity measure between molecular graphs corresponding to a scalar product in some Hilbert space. Most of existing graph kernels proposed in chemo informatics do not allow to explicitly encode cyclic information, hence limiting the efficiency of these approaches. In this paper, we propose to define a cyclic representation encoding the relative positioning of substituents around a cycle. We also propose a graph kernel taking into account this information. This contribution has been tested on three classification problems proposed in chemo informatics.