Pasar al contenido principal

REWIRING DE GRAFOS UNIFICADO Y ESCALABLE PARA GRANDES REDES

PID2022-142516OB-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Año convocatoria 2022
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSIDAD DE ALICANTE

Resultados relacionados

Resultados totales (Incluyendo duplicados): 9
Encontrada(s) 1 página(s)

RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Edge-Centric Embeddings of Digraphs: Properties and Stability Under Sparsification

  • Begga, Ahmed
  • Escolano, Francisco
  • Lozano, Miguel Angel
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
In this paper, we define and characterize the embedding of edges and higher-order entities in directed graphs (digraphs) and relate these embeddings to those of nodes. Our edge-centric approach consists of the following: (a) Embedding line digraphs (or their iterated versions); (b) Exploiting the rank properties of these embeddings to show that edge/path similarity can be posed as a linear combination of node similarities; (c) Solving scalability issues through digraph sparsification; (d) Evaluating the performance of these embeddings for classification and clustering. We commence by identifying the motive behind the need for edge-centric approaches. Then we proceed to introduce all the elements of the approach, and finally, we validate it. Our edge-centric embedding entails a top-down mining of links, instead of inferring them from the similarities of node embeddings. This analysis is key to discovering inter-subgraph links that hold the whole graph connected, i.e., central edges. Using directed graphs (digraphs) allows us to cluster edge-like hubs and authorities. In addition, since directed edges inherit their labels from destination (origin) nodes, their embedding provides a proxy representation for node classification and clustering as well. This representation is obtained by embedding the line digraph of the original one. The line digraph provides nice formal properties with respect to the original graph; in particular, it produces more entropic latent spaces. With these properties at hand, we can relate edge embeddings to node embeddings. The main contribution of this paper is to set and prove the linearity theorem, which poses each element of the transition matrix for an edge embedding as a linear combination of the elements of the transition matrix for the node embedding. As a result, the rank preservation property explains why embedding the line digraph and using the labels of the destination nodes provides better classification and clustering performances than embedding the nodes of the original graph. In other words, we do not only facilitate edge mining but enforce node classification and clustering. However, computing the line digraph is challenging, and a sparsification strategy is implemented for the sake of scalability. Our experimental results show that the line digraph representation of the sparsified input graph is quite stable as we increase the sparsification level, and also that it outperforms the original (node-centric) representation. For the sake of simplicity, our theorem relies on node2vec-like (factorization) embeddings. However, we also include several experiments showing how line digraphs may improve the performance of Graph Neural Networks (GNNs), also following the principle of maximum entropy.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Empirical Eigenfunctions for Graph Neural Networks

  • Begga, Ahmed
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Eigenvector Distance-Modulated Graph Neural Network: Spectral Weighting for Enhanced Node Classification

  • Begga, Ahmed
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
Graph Neural Networks (GNNs) face significant challenges in node classification across diverse graph structures. Traditional message passing mechanisms often fail to adaptively weight node relationships, thereby limiting performance in both homophilic and heterophilic graph settings. We propose the Eigenvector Distance-Modulated Graph Neural Network (EDM-GNN), which enhances message passing by incorporating spectral information from the graph’s eigenvectors. Our method introduces a novel weighting scheme that modulates information flow based on a combined similarity measure. This measure balances feature-based similarity with structural similarity derived from eigenvector distances. This approach creates a more discriminative aggregation process that adapts to the underlying graph topology. It does not require prior knowledge of homophily characteristics. We implement a hierarchical neighborhood aggregation framework that utilizes these spectral weights across multiple powers of the adjacency matrix. Experimental results on benchmark datasets demonstrate that EDM-GNN achieves competitive performance with state-of-the-art methods across both homophilic and heterophilic settings. Our approach provides a unified solution for node classification problems with strong theoretical foundations in spectral graph theory and significant empirical improvements in classification accuracy.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Syntax Savants-UA at IberLEF 2024: Leveraging FLAN-T5-XXL for Automatic 5W1H Identification in Texts

  • Grande Ruiz, Eduardo
  • Begga, Ahmed
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
  • Grande Ruiz, Eduardo|||/items/d0bc54e8-b11a-41c0-9f6b-3889b4ed8179
The 5W1H technique involves formulating six questions to briefly capture the basic information of a news text: What, When, Where, Who, Why, and How. This method enables an easy understanding of the news. This work, part of the FLARES competition at the Iberian Languages Evaluation Forum 2024, presents a Natural Language Processing (NLP) model, specifically FLAN-T5-XXL, designed to automatically extract 5W1H elements with an F1-score of 0.543. Our methodology includes creating task-specific templates and prompts and then fine-tuning the FLAN-T5-XXL model using annotated Spanish news articles provided by the competition organizers. We leverage Low-Rank Adaptation (LoRA) for efficient fine-tuning and conduct comprehensive hyperparameter optimization to enhance model performance and output generation. The evaluation demonstrates that FLAN-T5-XXL significantly outperforms other models. This study underscores the potential of Generative NLP models in automating information extraction from news texts.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Node classification in the heterophilic regime via diffusion-jump GNNs

  • Begga, Ahmed
  • Escolano, Francisco
  • Lozano, Miguel Angel
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Learnable Diffusion Distances for Link Prediction

  • Begga, Ahmed
  • Lozano, Miguel Angel
  • Escolano, Francisco
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
In this paper, we address the problem of link prediction (LP) in Graph Neural Networks (GNNs) by learning approximated diffusion distances. Since diffusion distances have a spectral interpretation, we learn the smallest eigenvectors of the normalized Laplacian using the training edges. The resulting ‘‘empirical eigenfunctions’’ are reactive both to the Dirichlet loss that finds the eigenvectors and to the prediction loss. This allows us to chase the spectrum of the network in addition to provide competitive results in many LP benchmarks without precomputing subgraphs or subgraphs sketches (e.g. SEAL, WalkPooling, ELPH/BUDDY). In addition, we provide a scalable approach for large graphs, where we do not rely on the matrix of diffusion distances.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Deep positional encoders for graph classification

  • Begga, Ahmed
  • Lozano, Miguel Angel
  • Escolano, Francisco
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

AG-GNN: Adaptive gating mechanism for robust node classification in graph neural networks

  • Begga, Ahmed
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Preserving node representation diversity in deep graph neural networks through Rényi entropy regularization

  • Begga, Ahmed
  • Escolano, Francisco
  • Lozano, Miguel Angel
  • Begga, Ahmed|||/items/4c7ecb8a-642d-4bfd-9eba-f52338bc14b6
  • Escolano, Francisco|||/items/d76f9381-7cca-497e-a9ab-e352c47660c6
  • Lozano, Miguel Angel|||/items/413f111d-7a63-43f2-bb70-6421affe1647
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.