MOTIVATION: Graphs have been demonstrated to have an impressive ability to keep the structural and semantic properties of chemical compounds and are therefore widely used in molecular modeling. Moreover, Graph Neural Networks (GNNs) and Large Language Models (LLMs) have achieved outstanding results in predicting molecular properties and generating textual descriptions given graphs or texts, respectively. Recently, some mathematical models have been presented for molecular science applications, which combine the GNNs ability to capture the structural and semantic information and the generative ability of LLMs. However, these models are dispersed across the literature and vary in architecture, input-output design, and application scope, making it difficult to systematically compare them or to identify suitable approaches for specific research objectives. RESULTS: This paper classifies recent GNN-LLM models and summarizes them with the aim of providing guidance for research involving their use or the development of new models. We present tables that depict the properties and parameters of the models, as well as their associated chemical computational applications. In addition, a new model classification is presented to help researchers define the models they use or future ones. Finally, we quantitatively compare these models based on their reported experimental results.

Abstract In some machine learning applications, graphs tend to be composed of a large number of tiny almost constant sub-structures. The current embedding methods are not prepared for this type of graphs and thus, their representational power tends to be very low. Our aim is to define a new graph embedding that considers this specific type of graphs. We present GraphFingerprint, which is a new embedding method that specifically considers the fact that graphs are composed of millions of almost constant sub-structures. The three-dimensional characterisation of a chemical metal-oxide nanocompound easily fits in these types of graphs, which nodes are atoms and edges are their bonds. Our graph embedding method has been used to predict the toxicity of these nanocompounds, achieving a high accuracy compared to other embedding methods. The representational power of the current embedding methods do not properly satisfy the requirements of some machine learning applications based on graphs, for this reason, a new embedding method has been defined and heuristically demonstrated that achieves good accuracy.

Agglomerative hierarchical clustering has become a common tool for the analysis and visualization of data, thus being present in a large amount of scientific research and predating all areas of bioinformatics and computational biology. In this work, we focus on a critical problem, the nonuniqueness of the clustering when there are tied distances, for which several solutions exist but are not implemented in most hierarchical clustering packages. We analyze the magnitude of this problem in one particular setting: the clustering of microsatellite markers using the Unweighted Pair-Group Method with Arithmetic Mean. To do so, we have calculated the fraction of publications at the Scopus database in which more than one hierarchical clustering is possible, showing that about 46% of the articles are affected. Additionally, to show the problem from a practical point of view, we selected two opposite examples of articles that have multiple solutions: one with two possible dendrograms, and the other with more than 2.5 million different possible hierarchical clusterings.

Attributed graphs are structures that are useful to represent objects through the information of their local parts and their relations. Each characteristic in the local parts is represented by different attributes on the nodes. In this context, the comparison between structured objects is performed through a distance between attributed graphs. If we want to correctly tune the distance and the node correspondence between graphs, we have to add some weights on the node attributes to gauge the importance of each local characteristic. In this paper, we present a method to learn the weights on each node attribute. It is based on building an embedded space and imposing the weights we want to learn to be the constants of the hyperplane deduced by a linear regression applied on a cloud of points. These points represent the node-to-node mappings.

Differential models for the simulation of the muscle mechanics are based on iteratively updating a mesh grid and deducing its new state through a finite element model. Models usually assume that the mesh grid is almost regular, and this makes a degradation of the simulation accuracy in long simulation sequences, since the mesh tends to be less regular when the number of iterations increases. We present a model that has the aim of reducing this accuracy degradation. It is based on recomputing the mesh grid returned by the model in each iteration through the concept of graph matching. The new model is currently in use to analyse the dynamics of the human heart when some pressure is applied to it. The final goal of the project (which is not shown in this paper) is to deduce the optimal position and strength pressure applied to the heart that increases the chance of reviving it with the minimum tissue damage. Experimental validation shows that our model returns a higher accuracy of the muscle position through some iterations than classical differential models with an insignificant increase of runtime. Thus, it is worth recomputing the mesh grid since the simulation accuracy drastically increases at the expense of a low runtime increase.

Error-tolerant graph matching has been demonstrated to be an NP-problem, for this reason, several suboptimal algorithms have been presented with the aim of making the runtime acceptable in some applications. These algorithms have been tested with relative small graphs due to the computation of the true distance for comparison purposes is too costly. We present a method to generate graphs together with an upper and lower bound distance with linear computational cost. Through this method, we can test the behaviour of the known or new sub-optimal error-tolerant graph matching algorithms against a lower and an upper bound graph edit distance on large graphs, even though we do not have the true distance. The computational cost to generate a pair of graphs together with their upper and lower bounds is linear with regard to the number of nodes. The practical experimentation shows that the runtime to generate a pair of graphs is negligible with regard to the runtime to match them.

This paper presents a methodology for generating pairs of attributed graphs with a lower and upper- bounded graph edit distance (GED). It is independent of the type of attributes on nodes and edges. The algorithm is composed of three steps: randomly generating a graph, generating another graph as a sub-graph of the first, and adding structural and semantic noise to both. These graphs, together with their bounded distances, can be used to manufacture synthetic databases of large graphs. The exact GED between large graphs cannot be obtained for runtime reasons since it has to be computed through an optimal algorithm with an exponential computational cost. Through this database, we can test the behavior of the known or new sub-optimal error-tolerant graph-matching algorithms against a lower and an upper bound GED on large graphs, even though we do not have the true distance. It is not clear how the error induced by the use of sub-optimal algorithms grows with problem size. Thus, with this methodology, we can generate graph databases and analyze if the current assumption that we can extrapolate algorithms’ behavior from matching small graphs to large graphs is correct or not. We also show that with some restrictions, the methodology returns the optimal GED in a quadratic time and that it can also be used to generate graph databases to test exact sub-graph isomorphism algorithms.

Given a fleet of robots, automatic estimation of the relative poses between them could be inaccurate in specific environments. We propose a framework composed by the fleet of robots with embedded stereoscopic cameras providing 2D and 3D images of the scene, a human coordinator and a Human-Machine Interface. We suppose auto localising each robot through GPS or landmarks is not possible. 3D-images are used to automatically align them and deduce the relative position between robots. 2Dimages are used to reduce the alignment error in an interactive manner. A human visualises both 2D-images and the current automatic alignment, and imposes a new alignment through the Human-Machine Interface. Since the information is shared through the whole fleet, robots can deduce the position of other ones that do not visualise the same scene. Practical evaluation shows that in situations where there is a large difference between images, the interactive processes are crucial to achieve an acceptable result.

There has been an increase of video surveillance systems in operation in public areas. The classical systems simply send the images to monitors. Nevertheless, there is a demand on giving more intelligence on these systems and asking them to automatically track objects or recognise people. One of the basic low-level tasks that these systems have to face with is the accurate deduction of the cameras' poses. We present a method that deducts these poses in an interactive way when the automatic method fails or generates a large error. The user is asked for mapping some points between the images from these cameras when the alignment between them fails in a completely automatic way. Experimental validation has demonstrated that with really few interactions, the reduction of the pose error is considerable.

In pattern recognition, it is usual to compare structured objects through attributed graphs in which nodes represent local parts and edges relations between them. Thus, each characteristic in the local parts is represented by different attributes on the nodes or edges. In this framework, the comparison between structured objects is performed through a distance between attributed graphs. If we want to correctly tune the distance and node correspondence between graphs, we need to add some weights on the node and edge attributes to gauge the importance of each local characteristic while defining the distance measure between graphs. In this paper, we present a method to learn the weights of each node and edge attribute such that the distance between the ground truth correspondence between graphs and the automatically obtained correspondence is minimized.

Bipartite (BP) has been seen to be a fast and accurate suboptimal algorithm to solve the Error-Tolerant Graph Matching problem. Recently, Fast Bipartite (FBP) has been presented that obtains the same distance value and node labelings but in a reduced time. Both algorithms approximate the quadratic problem in a linear problem and they do it through a specific cost matrix. FBP imposes the Edit costs to be defined such as the Edit distance is a distance function. Originally, the Hungarian method was used but it has been seen the Jonker–Volgenant linear solver obtains similar results than the Hungarian method but with an important run time reduction. Nevertheless, this second solver has some convergence problems on some specific cost matrices. The aim of this paper is to define a new cost matrix such that the Jonker–Volgenant solver converges and the matching algorithm obtains the same distance value than the BP algorithm.

On the one hand, it is usual that the current image registration techniques fail when images at hand have large differences due to dissimilarities on the point of views, occlusions, shadows and so on. On the other hand, humans are very good at finding correlations between salient points of images. We propose a method that acts when the automatic method fails, in this case, a human interacts on the computer vision system to help it to find a preliminary mapping between some salient points. Our method solves the alignment problem between two images in which a human (or oracle) imposes a partial correspondence between salient points extracted from the images through a Human-Machine Interface and the Interactive Alignment Estimation Method computes a new image alignment.

In pattern recognition applications, with the aim of increasing efficiency, it is useful to represent the elements by attributed graphs (which consider their structural properties). Under this structural representation of the elements some graph matching problems need a common labeling between the vertices of a set of graphs. Computing this common labeling is a NP-Complete problem. Nevertheless, some methodologies have been presented which obtain a sub-optimal solution in polynomial time. The drawback of these methods is that they rely on pairwise labeling computations, causing the methodologies not to consider the global information during the entire process. To solve this problem, we present a methodology which generates the common labeling by matching all graph nodes to a virtual node set. The method has been tested using three independent datasets, one synthetic and two real. Experimental results show that the presented method obtains better performance than the most popular common labeling algorithm with the same computational cost.

We model the edit distance as a function in a labeling space. A labeling space is an Euclidean space where coordinates are the edit costs. Through this model, we define a class of cost. A class of cost is a region in the labeling space that all the edit costs have the same optimal labeling. Moreover, we characterize the distance value through the labeling space. This new point of view of the edit distance gives us the opportunity of defining some interesting properties that are useful for a better understanding of the edit distance. Finally, we show the usefulness of these properties through some applications.

Local invariant feature extraction methods are widely used for image-features matching. There exist a number of approaches aimed at the refinement of the matches between image-features. It is a common strategy among these approaches to use geometrical criteria to reject a subset of outliers. One limitation of the outlier rejection design is that it is unable to add new useful matches. We present a new model that integrates the local information of the SIFT descriptors along with global geometrical information to estimate a new robust set of feature-matches. Our approach encodes the geometrical information by means of graph structures while posing the estimation of the feature-matches as a graph matching problem. Some comparative experimental results are presented.

Graphs are powerful data structures that have many attractive properties for object representation. However, some basic operations are difficult to define and implement, for instance, how to obtain a representative of a set of graphs. The median graph has been defined for that purpose, but existing algorithms are computationally complex and have a very limited applicability. In this paper we propose a new approach for the computation of the median graph based on graph embedding in vector spaces. Experiments on a real database containing large graphs show that we succeed to compute good approximations of the median graph. We have also applied the median graph to perform some basic classification tasks achieving reasonable good results.

Structural graph matching methods often fail when trying to match graphs which are small and present low structural constraints. An extra source of information is needed in order to eliminate the ambiguities produced by the lack of structural information. In this paper we introduce positional information into the cliques model in order to enhance the matching criterion. Procrustes methods provide a proper framework to do statistics with coordinate positions. Results show that our model significantly improves the matching capability in graphs generated from shapes (handwritten capital letters).

We present an efficient algorithm for computing a sub-optimal Earth Movers' Distance (EMD) between multidimensional histograms called EMD- g f, which is not limited to any type of measurement. Some algorithms that find a cross-bin distance between histograms have been proposed in the literature. Nevertheless, most of this research has been applied on 1D-histograms or on nD-histograms but with limited types of measurements. The EMD is a cross-bin distance between nD-histograms with any ground distance. Experimental validation shows that it obtains good retrieval results although the main drawback of this method is its cubic computational cost, O(z3), z being the total number of bins. The worst-case complexity of EMD- g f is O(z2), although the obtained average computational cost in the experiments is near O(m2), where m represents the number of bins per dimension, which is clearly lower than the computational cost of the EMD algorithm. Moreover, the experiments using real data show similar retrieval results.

This paper presents a new method for object tracking in video sequences that is especially suitable in very noisy environments. In such situations, segmented images from one frame to the next one are usually so different that it is very hard or even impossible to match the corresponding regions or contours of both images. With the aim of tracking objects in these situations, our approach has two main characteristics. On one hand, we assume that the tracking approaches based on contours cannot be applied, and therefore, our system uses object recognition results computed from regions (specifically, colour spots from segmented images). On the other hand, we discard to match the spots of consecutive segmented images and, consequently, the methods that represent the objects by structures such as graphs or skeletons, since the structures obtained may be too different in consecutive frames. Thus, we represent the location of tracked objects through images of probabilities that are updated dynamically using both recognition and tracking results in previous steps. From these probabilities and a simple prediction of the apparent motion of the object in the image, a binary decision can be made for each pixel and abject.

The aim of this article is to present a random graph representation, that is based on second-order relations between graph elements, for modeling sets of attributed graphs (AGs). We refer to these models as Second-Order Random Graphs (SORGs). The basic feature of SORGs is that they include both marginal probability functions of graph elements and second-order joint probability functions. This allows a more precise description of both the structural and semantic information contents in a set of AGs and, consequently, an expected improvement in graph matching and object recognition. The article presents a probabilistic formulation of SORGs that includes as particular cases the two previously proposed approaches based on random graphs, namely the First-Order Random Graphs (FORGs) and the Function-Described Graphs (FDGs). We then propose a distance measure derived from the probability of instantiating a SORG into an AG and an incremental procedure to synthesize SORGs from sequences of AGs. Finally, SORGs are shown to improve the performance of FORGs, FDGs and direct AG-to-AG matching in three experimental recognition tasks: one in which AGs are randomly generated and the other two in which AGs represent multiple views of 3D objects (either synthetic or real) that have been extracted from color images. In the last case, object learning is achieved through the synthesis of SORG models.

The aim of this article is to describe and compare the methods based on random graphs (RGs) which are applied to learn and recognize 3D objects represented by multiple views. These methods are based on modelling the objects by means of probabilistic structures that keep 1/sup st/ and 2/sup nd/-order probabilities. That is, multiple views of a 3D object are represented by few RGs. The most important probabilistic structures presented in the literature are first-order random graphs (FORGs), function-described graphs (FDGs) and second-order random graphs(SORGs). In the learning process, each one of the 3D-object views are represented by an attribute graph (AC), and a group of AGs are synthesized in a RG. In the recognizing process, the view of the object is represented by an AG and then it is compared with the RG that model each one of the 3D-object prototypes. In this paper, it is explained the modelling of the 3D-objects and the methods of learning and recognition based on FORGs, FDGs and SORGs. We show some results of the methods for real 3D objects.

Function-Described Graphs (FDGs) have been introduced by the authors as a representation of an ensemble of Attributed Graphs (AGs) for structural pattern recognition alternative to first-order random graphs. Both optimal and approximate algorithms for error-tolerant graph matching, which use a distance measure between AGs and FDGs, have been reported elsewhere. In this paper, both the supervised and the unsupervised synthesis of FDGs from a set of graphs is addressed. First, two procedures are described to synthesize an FDG from a set of commonly labeled AGs or FDGs, respectively. Then, the unsupervised synthesis of FDGs is studied in he context of clustering a set of AGs and obtaining an FDG model for each cluster. Two algorithms based on incremental and hierarchical clustering, respectively, are proposed, which are parameterized by a graph matching method. Some experimental results both on synthetic data and a real 3D-object recognition application show that the proposed algorithms are effective for clustering a set of AGs and synthesizing the FDGs that describe the classes. Moreover, the synthesized FDGs are shown to be useful for pattern recognition thanks to the distance measure and matching algorithm previously reported.

Function-described graphs (FDGs) have been introduced by the authors as a representation of an ensemble of attributed graphs (AGs) for structural pattern recognition as an alternative to first-order random graphs. The unsupervised synthesis of FDGs is studied in the context of clustering a set of AGs and obtaining an FDG model for each cluster. Two algorithms based on incremental and hierarchical clustering, respectively, are proposed, which are parameterized by a graph matching method. Results on 3D object recognition show that these algorithms are effective for clustering a set of AGs and synthesising the FDGs that describe the classes.

Function-described graphs (FDG) have been introduced by the authors as a representation of an ensemble of attributed graphs (AG) for structural pattern recognition alternative to first-order random graphs. In previous works, algorithms for the synthesis of FDG and a branch-and-bound algorithm for error-tolerant graph matching, which computes a distance measure between AG and FDG, have been reported. Since the worst-case complexity of that matching algorithm is exponential in the number of nodes, an approximate algorithm to compute a suboptimal measure is proposed in this paper. Results in 3D-object recognition show that, although the computational time is reduced, there is only a slight decrease of effectiveness while classifying an AG against a set of FDG.