Caio F. Deberaldini Netto

Caio F. Deberaldini Netto, Zhiyang Wang, Luana Ruiz

Graph Neural Networks (GNNs) have gained popularity in various learning tasks, with successful applications in fields like molecular biology, transportation systems, and electrical grids. These fields naturally use graph data, benefiting from GNNs' message-passing framework. However, the potential of GNNs in more general data representations, especially in the image domain, remains underexplored. Leveraging the manifold hypothesis, which posits that high-dimensional data lies in a low-dimensional manifold, we explore GNNs' potential in this context. We construct an image manifold using variational autoencoders, then sample the manifold to generate graphs where each node is an image. This approach reduces data dimensionality while preserving geometric information. We then train a GNN to predict node labels corresponding to the image labels in the classification task, and leverage convergence of GNNs to manifold neural networks to analyze GNN generalization. Experiments on MNIST and CIFAR10 datasets demonstrate that GNNs generalize effectively to unseen graphs, achieving competitive accuracy in classification tasks.

Martin Carrasco, Caio F. Deberaldini Netto, Vahan A. Martirosyan et al.

The expressive power of graph neural networks (GNNs) is typically understood through their correspondence with graph isomorphism tests such as the Weisfeiler-Leman (WL) hierarchy. While more expressive GNNs can distinguish a richer set of graphs, they are also observed to suffer from higher generalization error. This work provides a theoretical explanation for this trade-off by linking expressivity and generalization through the lens of coloring algorithms. Specifically, we show that the number of equivalence classes induced by WL colorings directly bounds the GNNs Rademacher complexity -- a key data-dependent measure of generalization. Our analysis reveals that greater expressivity leads to higher complexity and thus weaker generalization guarantees. Furthermore, we prove that the Rademacher complexity is stable under perturbations in the color counts across different samples, ensuring robustness to sampling variability across datasets. Importantly, our framework is not restricted to message-passing GNNs or 1-WL, but extends to arbitrary GNN architectures and expressivity measures that partition graphs into equivalence classes. These results unify the study of expressivity and generalization in GNNs, providing a principled understanding of why increasing expressive power often comes at the cost of generalization.

Caio F. Deberaldini Netto, Zhiyang Wang, Luana Ruiz

We propose a graph semi-supervised learning framework for classification tasks on data manifolds. Motivated by the manifold hypothesis, we model data as points sampled from a low-dimensional manifold $\mathcal{M} \subset \mathbb{R}^F$. The manifold is approximated in an unsupervised manner using a variational autoencoder (VAE), where the trained encoder maps data to embeddings that represent their coordinates in $\mathbb{R}^F$. A geometric graph is constructed with Gaussian-weighted edges inversely proportional to distances in the embedding space, transforming the point classification problem into a semi-supervised node classification task on the graph. This task is solved using a graph neural network (GNN). Our main contribution is a theoretical analysis of the statistical generalization properties of this data-to-manifold-to-graph pipeline. We show that, under uniform sampling from $\mathcal{M}$, the generalization gap of the semi-supervised task diminishes with increasing graph size, up to the GNN training error. Leveraging a training procedure which resamples a slightly larger graph at regular intervals during training, we then show that the generalization gap can be reduced even further, vanishing asymptotically. Finally, we validate our findings with numerical experiments on image classification benchmarks, demonstrating the empirical effectiveness of our approach.