Graph Neural Networks (GNNs) have revolutionized node classification tasks by leveraging graph structure and node features through message-passing schemes. However, GNNs frequently suffer from over-smoothing as the number of layers increases, causing node representations to collapse and lose discriminative power. In this paper, we propose AG-GNN, a novel architecture that addresses these challenges through a simple yet effective adaptive gating mechanism. This mechanism acts as a smart switch that dynamically controls how much information flows from the graph structure versus the node features at each layer. Our model’s dual-pathway design enables it to excel in both homophilic graphs (where connected nodes tend to share the same class) and heterophilic graphs (where connected nodes often belong to different classes). Extensive experiments demonstrate that AG-GNN consistently outperforms state-of-the-art methods, achieving up to 2.16 % improvement on heterophilic datasets like Cornell and 5.86 % improvement on large-scale networks like Penn94. Importantly, our approach maintains strong performance even with very deep architectures (up to 64 layers), demonstrating remarkable resistance to over-smoothing where traditional GNNs fail. AG-GNN scales efficiently to graphs with millions of nodes while maintaining computational tractability where several baseline models experience out-of-memory errors. • Our model dynamically balances node features and graph structure through an adaptive gating mechanism. • A novel multi-pathway architecture automatically handles both homophilic and heterophilic graphs. • The proposed model maintains stable performance across network depths without over-smoothing. • Extensive experiments on 15 datasets demonstrate superior performance and scalability. • The model effectively scales to graphs with millions of nodes where baseline models fail.

Abstract Graph Neural Networks have demonstrated remarkable performance across diverse domains, yet they face significant limitations in deeper architectures due to oversmoothing—the phenomenon where node representations become increasingly indistinguishable through successive message-passing operations. We propose a novel information-theoretic approach that addresses this fundamental challenge through Rényi entropy optimization. Our method quantifies and maximizes the diversity of node representations across network layers using kernel density estimation with Gaussian kernels. By formulating a graph-structured entropy regularization term that respects the underlying topology, we encourage networks to maintain discriminative features while preserving essential structural information. This approach integrates seamlessly with existing GNN architectures, requiring minimal modifications to the training procedure. Extensive experiments on ten benchmark datasets demonstrate that our Rényi entropy regularization consistently improves performance across multiple GNN variants, with average gains of 1.89% and particularly significant improvements on heterophilic graphs exceeding 2.5%. Our depth analysis shows that the method extends viable network depth from 2–3 layers to 8–10 layers, effectively countering the homogenization tendency of deep GNNs and establishing a principled foundation for more expressive graph neural networks.

Structural Pattern Recognition (SPR) includes the study of graphs as encoders of non-sequential and permutation-invariant patterns. In this regard, Graph Neural Networks (GNNs) are paving the way towards “inductive SPR” where classical structural problems such as graph classification can be approached through learnable priors. However, since graphs do not have a canonical order, existing GNNs struggle to learn the structural role of each node in the graph, which becomes key in graph classification. In this paper, we address this problem by making Spectral Graph Theory “inductive”, i.e. by learning the eigenvectors of the graph Laplacian, and then using them as positional encoders (PEs). Our experiments show that we improve significantly the SOTA of GNN-based graph classification.

In the ideal (homophilic) regime of vanilla GNNs, nodes belonging to the same community have the same label: most of the nodes are harmonic (their unknown labels result from averaging those of their neighbors given some labeled nodes). In other words, heterophily (when neighboring nodes have different labels) can be seen as a “loss of harmonicity”. In this paper, we define “structural heterophily” in terms of the ratio between the harmonicity of the network (Laplacian Dirichlet energy) and the harmonicity of its homophilic version (the so-called “ground” energy). This new measure inspires a novel GNN model (Diffusion-Jump GNN) that bypasses structural heterophily by “jumping” through the network in order to relate distant homologs. However, instead of using hops as standard High-Order (HO) GNNs (MixHop) do, our jumps are rooted in a structural well-known metric: the diffusion distance. Computing the “diffusion matrix” (DM) is the core of this method. Our main contribution is that we learn both the diffusion distances and the “structural filters” derived from them. Since diffusion distances have a spectral interpretation, we learn orthogonal approximations of the Laplacian eigenvectors while the prediction loss is minimized. This leads to an interplay between a Dirichlet loss, which captures low-frequency content, and a prediction loss which refines that content leading to empirical eigenfunctions. Finally, our experimental results show that we are very competitive with the State-Of-the-Art (SOTA) both in homophilic and heterophilic datasets, even in large graphs. • Structural Heterophily . We define heterophily in graphs as the loss of harmonicity of the labeling. • Diffusion-Jump GNNs . High-Order GNNs where the distances between the nodes rely on diffusion distances (leading to “jumps”) instead of hops. • Learnable Structural Filters . Jumps result from slicing the matrix of diffusion distances (diffusion matrix DM). Such slicing is fully learnable. • Empirical Eigenfunctions . Instead of computing the eigenvectors, we learn them in order to provide a spectral approximation of diffusion distances.

We describe the deep learning-based COVID-19 cases predictor and the Pareto-optimal Non-Pharmaceutical Intervention (NPI) prescriptor developed by the winning team of the 500k XPRIZE Pandemic Response Challenge. The competition aimed at developing data-driven AI models to predict COVID-19 infection rates and to prescribe NPI Plans that governments, business leaders and organizations could implement to minimize harm when reopening their economies. In addition to the validation performed by XPRIZE with real data, our models were validated in a real-world scenario thanks to an ongoing collaboration with the Valencian Government in Spain. Our experience contributes to a necessary transition to more evidence-driven policy-making during a pandemic.

Augmented Reality or AR filters on selfies have become very popular on social media platforms for a variety of applications, including marketing, entertainment and aesthetics. Given the wide adoption of AR face filters and the importance of faces in our social structures and relations, there is increased interest by the scientific community to analyze the impact of such filters from a psychological, artistic and sociological perspective. However, there are few quantitative analyses in this area mainly due to a lack of publicly available datasets of facial images with applied AR filters. The proprietary, close nature of most social media platforms does not allow users, scientists and practitioners to access the code and the details of the available AR face filters. Scraping faces from these platforms to collect data is ethically unacceptable and should, therefore, be avoided in research. In this paper, we present OpenFilter, a flexible framework to apply AR filters available in social media platforms on existing large collections of human faces. Moreover, we share FairBeauty and B-LFW, two beautified versions of the publicly available FairFace and LFW datasets and we outline insights derived from the analysis of these beautified datasets.

In this paper, we propose to embed edges instead of nodes using state-of-the-art neural/factorization methods (DeepWalk, node2vec, NetMF). These methods produce latent representations based on co-ocurrence statistics by simulating fixed-length random walks and then taking bags-of-vectors as the input to the Skip Gram Learning with Negative Sampling (SGNS). We commence by expressing commute times embedding as matrix factorization, and thus relating this embedding to those of DeepWalk and node2vec. Recent results showing formal links between all these methods via the spectrum of graph Laplacian, are then extended to understand the results obtained by SGNS when we embed edges instead of nodes. Since embedding edges is equivalent to embedding nodes in the line graph, we proceed to combine both existing formal characterizations of the line graphs and empirical evidence in order to explain why this embedding dramatically outperforms its nodal counterpart in multi-label classification tasks.

In this paper we study the poorly investigated problem of learning Random Forests for distance-based Random Forest clustering. We studied both classic schemes as well as alternative approaches, novel in this context. In particular, we investigated the suitability of Gaussian Density Forests, Random Forests specifically designed for density estimation. Further, we introduce a novel variant of Random Forest, based on an effective non parametric by-pass estimator of the Rényi entropy, which can be useful when the parametric assumption is too strict. An empirical evaluation involving different datasets and different RF-clustering strategies confirms that the learning step is crucial for RF-clustering. We also present a set of practical guidelines useful to determine the most suitable variant of RF-clustering according to the problem under examination.

In this paper, we propose net4Lap, a novel architecture for Laplacian-based ranking. The two main ingredients of the approach are: a) pre-processing graphs with neural embed-dings before performing Laplacian ranking, and b) introducing a global measure of centrality to modulate the diffusion process. We explicitly formulate ranking as an optimization problem where regularization is emphasized. This formulation is a theoretical tool to validate our approach. Finally, our experiments show that the proposed architecture significantly outperforms state-of-the-art rankers and it is also a proper tool for re-ranking.

In this paper, we propose the concept of graph rewiring and we show how to exploit it in an un-supervised setting so that commute times can be better estimated by state-of-the-art methods. Our experiments show a significant improvement with respect to unsupervised graph rewiring.

In this paper we decouple the problem of measuring graph similarity into two sequential steps. The first step is the linearization of the quadratic assignment problem (QAP) in a low-dimensional space, given by the embedding trick. The second step is the evaluation of an information-theoretic distributional measure, which relies on deformable manifold alignment. The proposed measure is a normalized conditional entropy, which induces a positive definite kernel when symmetrized. We use bypass entropy estimation methods to compute an approximation of the normalized conditional entropy. Our approach, which is purely topological (i.e., it does not rely on node or edge attributes although it can potentially accommodate them as additional sources of information) is competitive with state-of-the-art graph matching algorithms as sources of correspondence-based graph similarity, but its complexity is linear instead of cubic (although the complexity of the similarity measure is quadratic). We also determine that the best embedding strategy for graph similarity is provided by commute time embedding, and we conjecture that this is related to its inversibility property, since the inverse of the embeddings obtained using our method can be used as a generative sampler of graph structure.

Bai and Hancock recently proposed a novel edge-based matching kernel for graphs [1], by aligning depth-based representations. Unfortunately, one drawback arising in their kernel is the computational inefficiency for large graphs. This follows the fact that their kernel is essentially defined on directed line graphs. Moreover, the computational complexity of the kernel is cubic in the vertex number of the line graph. Since the directed line graph is a dual representation and each vertex represents a directed arc residing on the edge of the original graph. For a graph having n vertices, there may be at most n(n − 1) directed arcs residing on the edges and thus at most n(n − 1) vertices in the directed line graph. As a result, computing the kernel through the line graphs may require time complexity O(n6) for the worst case, making the kernel unapplicable for graphs having hundreds of vertices. The aim of this paper is to overcome this inefficiency, by proposing a new edge-based matching kernel. In order to cope with large graph structures, we propose to construct a sparser version of the original graph using the simplification method introduced in [2]. More specifically, we compute the minimum spanning tree over the commute time matrix of a graph. This spanning tree representation minimizes the number of edges of the original graph while preserving most of its structural information. With this simplification method to hand, the new edge-based matching kernel between two graphs is then computed on the directed line graphs transformed from their respective minimum spanning trees. We show that this strategy significantly reduces the computational complexity to O(n3). We evaluate the performance of the proposed kernels on several standard graph datasets. The experimental results demonstrate the effectiveness and efficiency.

In this paper, we present a novel approach for aerial obstacle detection (e.g., branches or awnings) using a 3-D smartphone in the context of the visually impaired (VI) people assistance. This kind of obstacles are especially challenging because they cannot be detected by the walking stick or the guide dog.The algorithm captures the 3-D data of the scene through stereo vision. To our knowledge, this is the first work that presents a technology able to obtain real 3-D measures with smartphones in real time. The orientation sensors of the device (magnetometer and accelerometer) are used to approximate the walking direction of the user, in order to look for the obstacles only in such a direction. The obtained 3-D data are compressed and then linearized for detecting the potential obstacles. Potential obstacles are tracked in order to accumulate enough evidence to alert the user only when a real obstacle is found.In the experimental section, we show the results of the algorithm in several situations using real data and helped by VI users.

In this paper, we aim to characterize hyper graphs in terms of structural complexities. To measure the complexity of a hyper graph in a straightforward way, we transform a hyper graph into a line graph which accurately reflects the multiple relationships exhibited by the hyper graph. To locate the dominant substructure within a line graph, we identify a centroid vertex by computing the minimum variance of its shortest path lengths. A family of directed centroid expansion sub graphs of the line graph is then derived from the centroid vertex. We compute the directed depth-based complexity trace of a hyper graph by measuring directed entropies on its directed sub graphs. The novel hyper graph complexity trace provides a flexible framework that can be applied to both hyper graphs and graphs. Experiments on standard (hyper)graph datasets demonstrate the effectiveness and efficiency of the new complexity trace.

The estimation of mutual information between graphs has been an elusive problem until the formulation of graph matching in terms of manifold alignment. Then, graphs are mapped to multi-dimensional sets of points through structural preserving embeddings. Point-wise alignment algorithms can be exploited in this context to re-cast graph matching in terms of point matching. Unfortunately, the potentially high dimensionality of the point-sets points encompass the development of mutual information means that bypass entropy estimation. These methods must be deployed to render the estimation of mutual information computationally tractable. In this paper the novel contribution is to show how manifold alignment can be combined with copula-based entropy estimators to efficiently estimate the mutual information between graphs. We compare the empirical copula with an Archimedean copula (the independent one) in terms of retrieval/recall after graph comparison. Our experiments show that mutual information built in both choices improves significantly state-of-the art divergences.

Variational approaches to density estimation and pattern recognition using Gaussian mixture models can be used to learn the model and optimize its complexity simultaneously. In this brief, we develop an incremental entropy-based variational learning scheme that does not require any kind of initialization. The key element of the proposal is to exploit the incremental learning approach to perform model selection through efficient iteration over the variational Bayes optimization step in a way that the number of splits is minimized. The method starts with just one component and adds new components iteratively by splitting the worst fitted kernel in terms of evaluating its entropy. Our experimental results, on synthetic and real data sets show the effectiveness of the approach outperforming other state-of-the-art incremental component learners.

In this paper we cast the problem of graph matching as one of non-rigid manifold alignment. The low dimensional manifolds are from the commute time embedding and are matched though coherent point drift. Although there have been a number of attempts to realise graph matching in this way, in this paper we propose a novel information-theoretic measure of alignment, the so-called symmetrized normalized-entropy-square variation. We successfully test this dissimilarity measure between manifolds on a a challenging database. The measure is estimated by means of the bypass Leonenko entropy functional. In addition we prove that the proposed measure induces a positive definite kernel between the probability density functions associated with the manifolds and hence between graphs after deformation. In our experiments we find that the optimal embedding is associated to the commute time distance and we also find that our approach, which is purely topological, outperforms several state-of-the-art graph-based algorithms for point matching.

In this work we evaluate purely structural graph measures for 3D objects classification. We extract spectral features from different Reeb graph representations. Information-theoretic feature selection gives an insight on which are the most relevant features.

In this paper we establish a formal link between network complexity in terms of Birkhoff-von Newmann decompositions and heat flow complexity (in terms of quantifying the heat flowing through the network at a given inverse temperature). Furthermore, we also define heat flow complexity in terms of thermodynamic depth, which results in a novel approach for characterizing networks and quantify their complexity. In our experiments we characterize several protein-protein interaction (PPI) networks and then highlight their evolutive differences.

In this paper we survey two multi-dimensional Scale Saliency approaches based on graphs and the k-d partition algorithm. In the latter case we introduce a new divergence metric and we show experimentally its suitability. We also show an application of multi-dimensional Scale Saliency to texture discrimination. We demonstrate that the use of multi-dimensional data can improve the performance of texture retrieval based on feature extraction.

In this paper, we address the problem of estimating the parameters of Gaussian mixture models. Although the expectation-maximization (EM) algorithm yields the maximum-likelihood (ML) solution, its sensitivity to the selection of the starting parameters is well-known and it may converge to the boundary of the parameter space. Furthermore, the resulting mixture depends on the number of selected components, but the optimal number of kernels may be unknown beforehand. We introduce the use of the entropy of the probability density function (pdf) associated to each kernel to measure the quality of a given mixture model with a fixed number of kernels. We propose two methods to approximate the entropy of each kernel and a modification of the classical EM algorithm in order to find the optimum number of components of the mixture. Moreover, we use two stopping criteria: a novel global mixture entropy-based criterion called Gaussianity deficiency (GD) and a minimum description length (MDL) principle-based one. Our algorithm, called entropy-based EM (EBEM), starts with a unique kernel and performs only splitting by selecting the worst kernel attending to GD. We have successfully tested it in probability density estimation, pattern classification, and color image segmentation. Experimental results improve the ones of other state-of-the-art model order selection methods.

In this paper we use doubly stochastic matrices to establish a link between Birkhoff polytopes and heat kernels on graphs. Based on this analysis we construct a multi-dimensional graph complexity measure characterized by the sequence of entropies associated to the Birkhoff-von Neumann decompositions (structural snapshots) of kernels with variable beta (range interaction factors). This construction is motivated by analogies with solving of traffic and transportation problems. We test the permutation invariance of the measure and demonstrate its application to graph embedding.

In this paper, we present a novel coarse-to-fine visual localization approach: contextual visual localization. This approach relies on three elements: (i) a minimal-complexity classifier for performing fast coarse localization (submap classification); (ii) an optimized saliency detector which exploits the visual statistics of the submap; and (iii) a fast view-matching algorithm which filters initial matchings with a structural criterion. The latter algorithm yields fine localization. Our experiments show that these elements have been successfully integrated for solving the global localization problem. Context, that is, the awareness of being in a particular submap, is defined by a supervised classifier tuned for a minimal set of features. Visual context is exploited both for tuning (optimizing) the saliency detection process, and to select potential matching views in the visual database, close enough to the query view.

In this paper, we present a novel approach to computing ceiling mosaics based on Information Theory. The only sensor of the robot is a digital camera oriented to the ceiling of the map, which is used to approximate the Simultaneous Localization and Mapping (SLAM) problem. We have divided the algorithm into two steps: (i) action estimation, which approximates the actions of the robot maximizing the Mutual Information between consecutive views; and (ii) global rectification, which rectifies the drift of the global trajectory minimizing the entropy of the map. Moreover, a fisheye lens is used to recover enough information from ceilings, reducing their inherent ambiguity. Such lenses produce a semi-spherical aberration in the images, that must be rectified using some information about calibration. In order to do so, we propose a novel technique for image rectification, also based on Information Theory. Finally, we present some experimental results using real data, that prove the robustness of the method.

The aquatic realm is ideal for testing autonomous robotic technology. The challenges presented in this environment are numerous due to the highly dynamic nature of the medium. Applications for underwater robotics include the autonomous inspection of coral reef, ships, pipelines, and other environmental assessment programs. In this paper we present current results in using 6DOF entropy minimization SLAM (simultaneous localization and mapping) for creating dense 3D visual maps of underwater environments that are suitable for such applications. The proposed SLAM algorithm exploits dense information coming from a stereo system, and performs robust egomotion estimation and global-rectification following an optimization approach

In this paper, we propose and validate an entropy minimization algorithm for solving the SLAM problem in the 6DOF case with semi-sparse (stereo) data. The proposed SLAM solution relies on both an efficient and robust strategy for egomotion estimation and an effective global rectification strategy. Our global rectification method is scalable because it relies on dynamically compressing actions, in order to reduce the number of variables to optimize, and thus on integrating/fusing observations. We have implemented a wearable stereo device that runs the SLAM algorithm in real time and we have tested such implementation both in indoor and outdoor scenarios. Our experiments show that action compression is a critical element for yielding acceptable and efficient solutions to the global optimization problem in the 6DOF case

In this paper we present an information-based approach to solve the SLAM problem using stereo vision. This approach results for an improvement, in terms of both efficiency and robustness, of our early multi-view ICP randomized algorithm. Instead of minimizing an ICP-based cost, we propose the minimization of the entropy of the 2D distribution induced by the projection of the 3D point cloud. In addition we embed both the egomotion/action estimation algorithm which precedes global rectification and the new global rectification algorithm in an autonomous exploration schema. We assume plane-parallel environments and, for the sake of efficiency, we also assume a flat floor and a fixed stereo camera mounted on the robot. We show successful experiments both under tele-operating the robot and under autonomous navigation.

In this paper we propose a method for extracting the planes from a 3D dense map. Three-dimensional data is acquired using active stereo in order to fill texture gaps which are typical in indoor environments. Then, a randomized SLAM algorithm recently proposed by the authors is applied to compute the 3D map by teleoperating a mobile robot. A 3D mesh generation algorithm specially designed to triangulate not solids but open objects, is the basis for computing the main planes in the map after clustering the normals of the vertices in the mesh. Finally, we present our experimental results in indoor environments.

We present a stereo-based approach for building 3D maps. First, the best local alignment between successive point clouds is computed by a fast ego-motion/action-estimation algorithm which relies on an incremental matches filtering process followed by energy minimization. Then, a quasi-random updating algorithm, a kind of multi-view ICP, minimizes the global inconsistency of the map. Such an inconsistency is defined in terms of the sum of local inconsistencies and an additional entropy-based regularization term which is effective in plane-parallel environments. For the sake of efficiency, we assume a flat floor and a fixed stereo camera mounted on the robot. We have successfully tested the approach by performing several indoor mapping experiments.

We propose two Bayesian methods for junction classification which evolve from the Kona method: a region-based method and an edge-based method. Our region-based method computes a one-dimensional (1-D) profile where wedges are mapped to intervals with homogeneous intensity. These intervals are found through a growing-and-merging algorithm driven by a greedy rule. On the other hand, our edge-based method computes a different profile which maps wedge limits to peaks of contrast, and these peaks are found through thresholding followed by nonmaximum suppression. Experimental results show that both methods are more robust and efficient than the Kona method, and also that the edge-based method outperforms the region-based one.