The evolution of representation learning depends not just on building more expressive models, but on aligning their design with the often messy, irregular realities of real-world data. This dissertation investigates the representational capacity of Graph Neural Networks (GNNs) through a critical and empirically grounded lens, challenging the notion that deeper or more complex models are inherently better. Instead, it advocates for a task-aware, data-sensitive approach to GNN design—one that prioritizes clarity over complexity, and rigor over trend. Positioned at the intersection of geometric learning and deep learning, this work makes the case for rethinking how GNN architectures are developed and evaluated. It begins with a thorough literature review that critically examines the theoretical foundations of graph representation learning—particularly the implications of the curse of dimensionality, the role of geometric inductive biases, and the entanglement of learning challenges, topology and features. This theoretical analysis sets the stage for identifying what is essential for GNNs to learn effectively and how these principles should inform model design. The dissertation then transitions to a careful empirical diagnosis of the challenges posed by graphs: from their non-Euclidean structure to the wide variability of their feature content. Drawing on synthetic and real-world experiments, it demonstrates that the relative importance of structural and feature signals varies substantially across tasks—often in ways that contradict prevailing architectural assumptions. These insights expose the absence of a one-size-fits-all solution and advocate for principled, task-aware approaches to GNN development. As such, a key contribution of this work is a principled methodology to disentangle structure and feature effects, enabling a clearer view of how GNNs actually learn. This leads to the identification of performance “sweet spots”—where graph convolutional networks excel under specific feature-structure alignments—, enabling the formulation of empirically grounded guidelines for matching GNN architectures to task and data characteristics. These insights challenge the common assumption that more complex architectures inherently lead to better performance, instead reframing the discussion around task-specific requirements. Building on this task-sensitive perspective, we turn to one of the most debated dimensions of GNN design: depth. While depth is traditionally associated with increased capacity in neural networks, our findings suggest that this intuition does not necessarily hold for GNNs. Our analyses show that GNNs often plateau or collapse as depth increases, with layers becoming noisy or redundant. Besides creating evident computational inefficiencies, this effect can also result in behavior resembling that of a Multilayer Perceptron (MLP), in which the usage of structure is ultimately obliterated. These findings stem from the introduction of a novel evaluation protocol that reveals these failure modes in both synthetic and real-world settings. This contribution underscores the importance of embracing controlled shallowness and reinforces the broader argument of the dissertation: GNN effectiveness is highly context-dependent, and architectural decisions must be grounded in the specific characteristics of the task and data. Ultimately, this dissertation pushes for a shift in how GNNs are understood and applied. It moves the field toward a more grounded, problem-driven mindset—where the goal is not simply to build bigger and more complex models, but to build the right ones. The resulting insights not only clarify when and why GNNs work, but also offer a practical path forward for researchers and practitioners seeking models that are better aligned with task requirements and more robust in real-world settings.
Sousa Gomes, D 2025, 'Enhancing representation learning with graph neural networks by understanding their benefits and limitations', Vrije Universiteit Brussel.
Sousa Gomes, D. (2025). Enhancing representation learning with graph neural networks by understanding their benefits and limitations. [PhD Thesis, Vrije Universiteit Brussel].
@phdthesis{77165ec69b064ad19d2bad32fe59d6aa,
title = "Enhancing representation learning with graph neural networks by understanding their benefits and limitations",
abstract = "The evolution of representation learning depends not just on building more expressive models, but on aligning their design with the often messy, irregular realities of real-world data. This dissertation investigates the representational capacity of Graph Neural Networks (GNNs) through a critical and empirically grounded lens, challenging the notion that deeper or more complex models are inherently better. Instead, it advocates for a task-aware, data-sensitive approach to GNN design—one that prioritizes clarity over complexity, and rigor over trend. Positioned at the intersection of geometric learning and deep learning, this work makes the case for rethinking how GNN architectures are developed and evaluated. It begins with a thorough literature review that critically examines the theoretical foundations of graph representation learning—particularly the implications of the curse of dimensionality, the role of geometric inductive biases, and the entanglement of learning challenges, topology and features. This theoretical analysis sets the stage for identifying what is essential for GNNs to learn effectively and how these principles should inform model design. The dissertation then transitions to a careful empirical diagnosis of the challenges posed by graphs: from their non-Euclidean structure to the wide variability of their feature content. Drawing on synthetic and real-world experiments, it demonstrates that the relative importance of structural and feature signals varies substantially across tasks—often in ways that contradict prevailing architectural assumptions. These insights expose the absence of a one-size-fits-all solution and advocate for principled, task-aware approaches to GNN development. As such, a key contribution of this work is a principled methodology to disentangle structure and feature effects, enabling a clearer view of how GNNs actually learn. This leads to the identification of performance “sweet spots”—where graph convolutional networks excel under specific feature-structure alignments—, enabling the formulation of empirically grounded guidelines for matching GNN architectures to task and data characteristics. These insights challenge the common assumption that more complex architectures inherently lead to better performance, instead reframing the discussion around task-specific requirements. Building on this task-sensitive perspective, we turn to one of the most debated dimensions of GNN design: depth. While depth is traditionally associated with increased capacity in neural networks, our findings suggest that this intuition does not necessarily hold for GNNs. Our analyses show that GNNs often plateau or collapse as depth increases, with layers becoming noisy or redundant. Besides creating evident computational inefficiencies, this effect can also result in behavior resembling that of a Multilayer Perceptron (MLP), in which the usage of structure is ultimately obliterated. These findings stem from the introduction of a novel evaluation protocol that reveals these failure modes in both synthetic and real-world settings. This contribution underscores the importance of embracing controlled shallowness and reinforces the broader argument of the dissertation: GNN effectiveness is highly context-dependent, and architectural decisions must be grounded in the specific characteristics of the task and data. Ultimately, this dissertation pushes for a shift in how GNNs are understood and applied. It moves the field toward a more grounded, problem-driven mindset—where the goal is not simply to build bigger and more complex models, but to build the right ones. The resulting insights not only clarify when and why GNNs work, but also offer a practical path forward for researchers and practitioners seeking models that are better aligned with task requirements and more robust in real-world settings.",
author = "\{Sousa Gomes\}, Diana",
year = "2025",
language = "English",
school = "Vrije Universiteit Brussel",
}