Processing and Learning over Irregular Domains: Multidimensional Signals Defined over Multiple Graphs

Abstract

Graphs provide a powerful mathematical framework for representing complex systems characterized by entities and their pairwise relationships, with applications ranging across diverse scientific and engineering disciplines. While traditional graph signal processing and Graph Neural Networks (GNNs) have achieved remarkable success, they predominantly focus on signals and learning tasks defined over single, often static and homogeneous, graph structures. However, many real-world phenomena exhibit a richness and complexity that cannot be adequately captured by a unique graph. This dissertation addresses this limitation by exploring the paradigm of multidimensional signals defined over multiple graphs, aiming to develop novel methodologies for both generating meaningful ensembles of graphs and designing advanced GNN architectures that effectively leverage these richer structural representations. The research presented herein confronts several key challenges inherent in multi-graph scenarios. These include the generation of realistic, diverse, and controlled graph structures that can serve as inputs for learning systems; the difficulty of bridging structural and semantic gaps when processing, relating, or transferring information between graphs that differ significantly in node sets, edge structures, or resolutions; and the need to enhance GNN expressivity and adaptability to effectively utilize information from multiple complex graphs, especially in scenarios involving non-aligned nodes, settings with incomplete node features or challenging data characteristics like heterophily. To address these challenges, this dissertation makes four primary contributions, each corresponding to one or more peer-reviewed publications. The first set of contributions focuses on advancing graph generative modeling. Recognizing the need for generating graphs that not only mimic observed data but also adhere to specific structural requirements, we introduce Graph Guided Diffusion (GGDiff). This novel framework unifies multiple guidance strategies for conditional graph generation using diffusion models, interpreting the process as a stochastic control problem. GGDiff enables zero-shot guidance of pre-trained diffusion models under both differentiable and non-differentiable reward functions, facilitating the generation of graphs constrained by desired properties, such as motif counts or fairness metrics. This work significantly expands the toolkit available for creating graph data, enabling the utilization of the generated graphs for downstream tasks. Complementing this graph generation setting, we explore graph generation through the lens of graphons, which are limit objects for dense graph sequences. We propose a scalable graphon estimation method that directly recovers the graphon via moment matching using implicit neural representations. This approach bypasses the complexities of latent variable modeling and costly metric optimizations, offering theoretical guarantees on estimation accuracy. We also introduce MomentMixup, a data augmentation technique in the moment space to enhance graph-based learning tasks. These two generative methodologies provide powerful tools for creating diverse and principled graph structures, laying the groundwork for more sophisticated multi-graph learning. The second set of contributions delves into novel GNN architectures designed to operate effectively in multi-graph and complex single-graph settings. We first propose a flexible GNN architecture to handle tasks where input and output signals are defined on two entirely different graphs, which may possess distinct node sets and topologies. This Input-Output GNN (IO-GNN) framework features a three-block design (an input GNN, a latent space transformation, and an output GNN) allowing for effective signal mapping and representation learning across disparate graph domains. The framework also accomodates a self-supervised learning approach, inspired by canonical correlation analysis, demonstrating the utility of leveraging information from multiple graph structures to learn informative latent representations. Finally, we address the issue of GNN performance degradation on heterophilic graphs, where connected nodes often have different labels. We introduce Structure-Guided GNN (SG-GNN), an architecture that leverages structural attributes (such as role-based or global properties) to construct alternative graph views. These structural graphs are designed to exhibit higher homophily, and SG-GNN adaptively learns to weigh the contributions from the original graph and these new views. This approach significantly improves performance on heterophilic benchmarks by providing GNNs with more relevant neighbor information, and highlights the benefit of considering multiple graph perspectives even for tasks initially proposed to operate on a single primary graph. Complementing this focus on leveraging existing structure for better learning, we also demonstrate that similar structural attributes can be used in scenarios with missing data, successfully being used to interpolate entirely unavailable node features by identifying local structural similarities. Taken collectively, the contributions of this dissertation establish a comprehensive suite of tools and methodologies for the generation of, and learning over, multiple and complex graph structures. By developing principled graph generative models and innovative GNN architectures, this work pushes the boundaries of how we can process and understand multidimensional signals defined over multiple graphs. The findings demonstrate the significant potential of moving beyond single-graph paradigms, opening new avenues for tackling complex real-world problems where data is inherently structured through multiple, interacting underlying structures. In summary, this research provides both theoretical insights and practical algorithms that contribute to the broader advancement of machine learning on graphs.