Resumen de Empirical Eigenfunctions for Graph Neural Networks
Neural networks have emerged as a powerful tool for solving a wide range of problems in areas such as computer vision, natural language processing, and machine learning. However, most traditional neural network architectures are designed to handle vectorized data like images and sequences, limiting their applicability to more complex, non-Euclidean data structures such as graphs. This limitation has become increasingly relevant as many real-world problems naturally manifest as graph-structured data. Graphs provide a natural framework for modeling intricate relationships between entities, making them essential for applications like social networks, recommendation systems, molecular structure analysis, and bioinformatics. Despite their flexibility, the non-vectorial nature of graphs introduces several unique challenges in machine learning, including the difficulty of capturing both local and global structures simultaneously, the inherent sparsity of connections, the presence of heterogeneous node and edge features, and the computational complexity of graph algorithms. These challenges have motivated the development of specialized architectures capable of processing graph-structured data effectively. Graph Neural Networks (GNNs) have emerged as a promising solution, enabling the learning of vector representations for nodes and edges directly from graph data. In particular, these architectures have achieved remarkable success in various tasks, from node classification to graph generation. Despite their success, GNNs still face significant challenges that limit their practical applicability: over-smoothing, where node features become indistinguishable after multiple layers; the vanishing of informative features during message passing; over-squashing, which occurs when exponentially growing information is forced through fixed-size vectors; difficulties in generalizing across different graph types; and under-reaching, where the model fails to capture long-range dependencies effectively. This doctoral thesis presents a novel approach that leverages Spectral Graph Theory (SGT) to address these issues by approximating eigenvectors of the graph Laplacian, which constitutes a core contribution of this work. A distinctive feature of our approach is that the learned eigenvectors are reactive to the downstream task, such as node classification, graph classification and link prediction. This is why we call our approach: Empirical Eigenvectors. Unlike traditional GNN approaches that rely primarily on spatial operations, this method builds upon the precise approximation of these eigenvectors, allowing for a more robust and expressive representation of graph data. Thus, this spectral-based framework enables us to address the over-smoothing problem by maintaining distinct frequency components of the graph signal and enhancing the model’s ability to capture both local and global structures in complex graph topologies through adaptive spectral filtering. Moreover, the approach is extended beyond node classification to graph classification and link prediction tasks, demonstrating its versatility across different graph learning paradigms. By leveraging the spectral properties of graphs, this method significantly improves performance across these applications, achieving state-of-the-art results on multiple benchmark datasets. The approximation of eigenvectors enables the preservation of the rich structural information embedded in graphs while maintaining computational efficiency. This leads to competitive results in a wide range of graph-based learning tasks. The extensive experimental results demonstrate that this eigenvector-based framework is not only a versatile and powerful tool for tackling the inherent challenges of learning on graphs, but also establishes new benchmarks in terms of accuracy, scalability, and robustness. Furthermore, theoretical guarantees are provided for the expressiveness of the method along with an analysis of its computational complexity, demonstrating an optimal trade-off between representational power and computational efficiency. This thesis opens new avenues for research in spectral graph neural networks and provides a solid foundation for future developments in the field of geometric deep learning.
