Graph neural networks (GNNs) are designed to learn functions on graphs. Models based on message passing, one of the main architectures, have a strong theoretical limit: they are not able to distinguish two graphs that are not distinguishable by the Weisfeiler-Leman test and they fail to represent certain substructures. This thesis investigates a transformation understudied for graph learning, called the super line graph from line graph theory, that allows the creation of a new graph from a given one. The study focuses primarily on the super line graph of index two, L_2(G), whose vertices correspond to unordered pairs of edges of the original graph, with the final aim of building the theoretical ground to construct a higher-order graph neural network. We derive a bound for the dimension of the super line graph, we construct an output-sensitive algorithm and we characterize the degree distribution of L_2(G) for regular graphs through counts of induced subgraphs, showing that the degree distribution can distinguish graph pairs that are not separated by three-dimensional Weisfeiler-Leman. We introduce some graph invariants that combine Weisfeiler-Leman and the super line graph, giving us strictly more expressive power than both. Neural architectures inspiredby these invariants also improve the results of the standard baseline GCN on several synthetic subgraph-counting tasks. However, they do not outperform the baseline on the considered real-world benchmarks.These findings establish super line graphs as expressive higher-order representations with theoretical guarantees.
Graph neural networks (GNNs) are designed to learn functions on graphs. Models based on message passing, one of the main architectures, have a strong theoretical limit: they are not able to distinguish two graphs that are not distinguishable by the Weisfeiler-Leman test and they fail to represent certain substructures. This thesis investigates a transformation understudied for graph learning, called the super line graph from line graph theory, that allows the creation of a new graph from a given one. The study focuses primarily on the super line graph of index two, L_2(G), whose vertices correspond to unordered pairs of edges of the original graph, with the final aim of building the theoretical ground to construct a higher-order graph neural network. We derive a bound for the dimension of the super line graph, we construct an output-sensitive algorithm and we characterize the degree distribution of L_2(G) for regular graphs through counts of induced subgraphs, showing that the degree distribution can distinguish graph pairs that are not separated by three-dimensional Weisfeiler-Leman. We introduce some graph invariants that combine Weisfeiler-Leman and the super line graph, giving us strictly more expressive power than both. Neural architectures inspiredby these invariants also improve the results of the standard baseline GCN on several synthetic subgraph-counting tasks. However, they do not outperform the baseline on the considered real-world benchmarks.These findings establish super line graphs as expressive higher-order representations with theoretical guarantees.
Expressive graph neural networks via super line graph transformation
CRUCIOLI, GIULIANO
2025/2026
Abstract
Graph neural networks (GNNs) are designed to learn functions on graphs. Models based on message passing, one of the main architectures, have a strong theoretical limit: they are not able to distinguish two graphs that are not distinguishable by the Weisfeiler-Leman test and they fail to represent certain substructures. This thesis investigates a transformation understudied for graph learning, called the super line graph from line graph theory, that allows the creation of a new graph from a given one. The study focuses primarily on the super line graph of index two, L_2(G), whose vertices correspond to unordered pairs of edges of the original graph, with the final aim of building the theoretical ground to construct a higher-order graph neural network. We derive a bound for the dimension of the super line graph, we construct an output-sensitive algorithm and we characterize the degree distribution of L_2(G) for regular graphs through counts of induced subgraphs, showing that the degree distribution can distinguish graph pairs that are not separated by three-dimensional Weisfeiler-Leman. We introduce some graph invariants that combine Weisfeiler-Leman and the super line graph, giving us strictly more expressive power than both. Neural architectures inspiredby these invariants also improve the results of the standard baseline GCN on several synthetic subgraph-counting tasks. However, they do not outperform the baseline on the considered real-world benchmarks.These findings establish super line graphs as expressive higher-order representations with theoretical guarantees.| File | Dimensione | Formato | |
|---|---|---|---|
|
Thesis_Crucioli.pdf
accesso aperto
Dimensione
3.91 MB
Formato
Adobe PDF
|
3.91 MB | Adobe PDF | Visualizza/Apri |
The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License
https://hdl.handle.net/20.500.12608/115830