2.1 Locally irregular edge-colouring

Graphs considered in this study are simple and finite unless stated otherwise. A graph $G$ with vertex (or node) set $V$ and edge set $E$ is said to be locally irregular if for every edge $e \in E$ , the end vertices of $e$ have distinct degrees. A $k$ -locally irregular edge decomposition of $G$ is analogous to colouring the edges of $G$ with $k$ colours such that each colour induces a locally irregular subgraph [Reference Baudon, Bensmail, Przybyło and Woźniak6]. This is also known as $k$ -locally irregular edge-colouring ( $k$ -liec). The smallest such $k$ for which $G$ admits a $k$ -liec is called the locally irregular chromatic index, denoted $\chi _{\mathrm {irr}}'(G)$ . If $G$ admits a locally irregular edge-colouring, we say that $G$ is decomposable and $\chi _{\mathrm {irr}}'(G)$ is finite. Otherwise, $G$ is exceptional and $\chi _{\mathrm { irr}}'(G) = \infty $ (notation and definitions used in [Reference Bensmail, Merker and Thomassen8]).

The local irregularity conjecture was first conjectured in 2015 by Baudon et al. [Reference Baudon, Bensmail, Przybyło and Woźniak6]. It was first believed that every decomposable graph required at most 3 colours for a locally irregular edge-colouring. However in 2021, a counter-example to the original conjecture was found (see Figure 1). Then, it was further proved that the bow-tie graph, $B$ , is the only counter-example to the original conjecture among all cactus graphs [Reference Sedlar and Škrekovski62]. This has lead to the weaker version of the conjecture (Conjecture 1), where it is currently believed that except for $B$ , every decomposable graph required at most 3 colours for a locally irregular edge-colouring.

Figure 1

The bow-tie graph, $B$ , and its 4-liec [Reference Sedlar and Škrekovski61].

Here, we will deal with a simpler problem under the umbrella of locally irregular edge-colouring, where given a graph $G$ , one aims to classify it as either decomposable or exceptional. The study of locally irregular edge-colouring has traditionally relied on rigorous mathematical proofs, with little to no exploration of machine learning approaches. As a result, the effectiveness of such methods in addressing these problems remains largely unknown.

Theorem 1 lays the foundation to our work, where the complete set of exceptional graphs is characterized. A cactus graph is a graph where any two cycles in the graph shares at most one common vertex. For a node $v$ , we let $\mathcal {N}(v)$ denote the set of all vertices that are adjacent to $v$ . By identifying two vertices $v_1$ and $v_2$ , we mean the operation that produces a graph in which these two nodes are replaced with a single vertex $v$ such that $v$ is adjacent to all the vertices in $\mathcal {N}(v_1) \cup \mathcal {N}(v_2)$ . The special family of cactus graphs, $\mathfrak {T}$ , can be defined inductively as follows [Reference Baudon, Bensmail, Przybyło and Woźniak6]:

• • the triangle, $K_3$ is in $\mathfrak {T}$ ;

• • every other graph of this family may be constructed by taking an auxiliary graph $F$ which might either be a path of even length or a path of odd length with a triangle glued to one of its ends, then choosing a graph $G \in \mathfrak {T}$ containing a triangle with at least one vertex, say $v$ , of degree two in $G$ , and finally identifying $v$ with a vertex of degree one of $F$ .

We denote by $\mathfrak {T}'$ (notation introduced in [Reference Sedlar and Škrekovski62]) the union of odd-length paths, odd-length cycles and the family $\mathfrak {T}$ . Notably, all graphs in $\mathfrak {T}'$ are cactus graphs with an odd number of edges. Therefore, cactus graphs represent a significant class in the study of locally irregular edge-colourings, as every known exceptional graph belongs to this category.

2.2 Graph neural networks

Graphs are inherently non-Euclidean structures [Reference Asif4] and lack a fixed topology, which poses challenges for their direct integration into traditional machine learning models. Consequently, it is necessary to employ appropriate techniques that can transform graph data into fixed-size representations, enabling their use within standard machine learning pipelines.

GNNs are a class of neural architectures designed to learn from graph-structured data. Given a graph $G = (V, E)$ , where each node $v \in V$ is associated with a feature vector $\mathbf {x}_v \in \mathbb {R}^d$ , the objective of a GNN is to learn expressive representations that capture both local and global structural information. These representations may correspond to node embeddings $\mathbf {h}_v \in \mathbb {R}^{d_v}$ , edge embeddings $\mathbf {h}_{uv} \in \mathbb {R}^{d_e}$ or a graph-level embedding $\mathbf {h}_{G} \in \mathbb {R}^{d_G}$ , which can then be used for downstream tasks such as node classification, link prediction or graph classification.

Most GNN models fall under the MPNN framework [Reference Gilmer, Schoenholz, Riley, Vinyals and Dahl23], where node representations are iteratively updated by exchanging information with neighbouring nodes. The message passing process is initialized with the input node features: $\{\mathbf {h}_v ^{(0)} = \mathbf {x}_v \mid v \in V \}$ and a fixed number of layers $L$ . At each message passing layer $l = 1,2,\ldots ,L$ , the embedding $\mathbf {h}_v^{(l)}$ of each node $v \in V$ is generally obtained through the following steps [Reference Wu, Sun, Zhang, Xie and Cui71]:

1. (1) message aggregation from the local neighbourhood,

   $$ \begin{align*} \mathbf{m}_v ^{(l)} = \mathrm{AGGREGATE}^{(l)}(\{\mathbf{h}_u^{(l-1)} \,\vert\, u \in \mathcal{N}(v) \}); \end{align*} $$

2. (2) update of the node embedding using the previous embedding and the aggregated message,

   $$ \begin{align*} \mathbf{h}_v ^{(l)} = \mathrm{UPDATE}^{(l)}(\mathbf{h}_v^{(l-1)}, \mathbf{m}_v^{(l)}). \end{align*} $$

Here, AGGREGATE and UPDATE are differentiable and often parametrized functions, enabling end-to-end learning through back-propagation. The AGGREGATE function is required to be permutation-invariant with respect to the unordered set of neighbours $\mathcal {N}(v)$ , where typical choices include sum, mean or max pooling. Figure 2 illustrates a single message passing layer for a node, with all nodes updated in parallel using shared AGGREGATE and UPDATE functions.

Figure 2

Illustration of node feature updates in layer $l$ of a GNN for a single node.

After $L$ layers of message passing, the final node embeddings $\mathbf {h}_v ^ {(L)}$ can be used for downstream prediction tasks. For node classification, each $\mathbf {h}_v ^ {(L)}$ is passed to a classifier (for example, a multilayer perceptron) with loss back-propagated to update both classifier and GNN parameters. For graph-level tasks, a differentiable, permutation invariant READOUT function aggregates information across all node embeddings to produce a graph-level representation:

$$ \begin{align*} \mathbf{h}_G = \mathrm{READOUT}(\{ \mathbf{h}_v^{(L)} \,\vert\, v \in V \}). \end{align*} $$

This representation is then passed to a classifier and training proceeds similarly. Through iterative message passing, the node embeddings $\mathbf {h}_v^{(l)}$ encode information from the $l$ -hop neighbourhood of node $v$ (all nodes within a distance of at most $l$ ), capturing progressively larger structural contexts. In practice, the number of layers $L$ is kept relatively small, as deeper GNNs are prone to oversmoothing [Reference Wu, Chen, Wang and Jadbabaie72], where node embeddings become increasingly similar and lose their discriminative capacity. Most GNN architectures follow a common message passing framework, and differ primarily in the specific design of the AGGREGATE and UPDATE functions.

Although there are other methods to automatically obtain node embeddings for graphs such as Deepwalk [Reference Perozzi, Al-Rfou and Skiena55] and node2vec [Reference Grover and Leskovec25], the versatility of GNNs make it the more popular choice among these algorithms.

2.3 Problem statement

Given a graph $G$ , the task is to classify it as either decomposable or exceptional. By Theorem 1, a graph is exceptional if and only if $G \in \mathfrak {T}'$ . Consequently, the classification problem reduces to determining whether $G \in \mathfrak {T}'$ or $G \notin \mathfrak {T}'$ .

In this work, we address this problem through a data-driven approach by leveraging GNNs. Specifically, we investigate the effectiveness of various GNN architectures in learning to distinguish between decomposable and exceptional graphs. The goal is to evaluate and compare the performance of these models in accurately predicting membership in the set $\mathfrak {T}'$ .

3.1 Dataset

To the best of our knowledge, no publicly available dataset exists for learning-based approaches to locally irregular edge-colouring. To address this gap, we introduce a datasetFootnote ¹ of 3120 graphs derived from the structural characterization of exceptional graphs presented in Theorem 1 [Reference Baudon, Bensmail, Przybyło and Woźniak6]. The dataset is explicitly divided into an in-distribution subset used for training and validation, and an OOD subset used exclusively for robustness and generalization evaluation. In total, the dataset contains 2600 in-distribution instances (Section 3.1.1) and 520 OOD instances (Section 3.1.2).

From [Reference Baudon, Bensmail, Przybyło and Woźniak6], all exceptional graphs are known to be odd-sized cactus graphs with maximum degree at most three. Consequently, any graph violating these conditions is trivially decomposable. To avoid this degeneracy and ensure a nontrivial classification task, all graphs in our dataset (both exceptional and decomposable) are restricted to connected cactus graphs with maximum degree three.

We do not enforce the odd-size constraint, as doing so would overly restrict the diversity of instances and limit the applicability of the dataset. Basic statistics of the resulting dataset are summarized in Table 1.

3.1.1 In-distribution dataset

The in-distribution dataset consists of 1300 exceptional graphs and 1300 decomposable graphs, for a total of 2600 instances.

A tadpole $T_{m,n}$ is the graph obtained by concatenating a cycle with $m$ vertices, $C_m$ , and a path with $n+1$ vertices, $P_{n+1}$ , with an edge from any vertex of $C_m$ to a pendant (vertex of degree one) of $P_n$ for $m \geq 3$ and $n\geq 1$ . Let $\mathcal {P}$ and $\mathcal {T}$ denote the full sets of path and tadpole graphs, respectively. Also, let $\mathcal {P}_{\mathrm {even}}$ denote the set of even-length paths (even size), and $\mathcal {T}_{3, \mathrm { odd}}$ the set of tadpole graphs with $m = 3$ and odd $n$ .

Among the exceptional graphs, 300 instances consist of:

• • 100 odd-length paths;

• • 100 odd-length cycles;

• • 100 tadpole graphs with $m = 3$ and even $n$ .

The remaining 1000 exceptional graphs are hand-crafted following the inductive construction of the class $\mathfrak {T}$ in Theorem 1 (excluding tadpole graphs). Specifically, each graph is constructed by identifying a degree-two vertex belonging to a triangle in a base graph from $\mathfrak {T}$ with a pendent vertex of degree one in a graph drawn from $\mathcal {P}_{\mathrm {even}} \cup \mathcal {T}_{3, \mathrm {odd}}$ .

Table 1

Statistics for in-distribution and OOD datasets.

Table 1 Long description

The table consists of three columns: Measure, In-distribution dataset, and Out-of-distribution dataset.

* Number of graphs: 2600 for in-distribution and 520 for out-of-distribution.

* Average order: 47.41 for in-distribution and 66.03 for out-of-distribution.

* Average size: 49.70 for in-distribution and 82.18 for out-of-distribution.

* Average degree: 2.17 for in-distribution and 2.52 for out-of-distribution.

* Min cycles: 1 for in-distribution and 15 for out-of-distribution.

* Max cycles: 10 for in-distribution and 20 for out-of-distribution.

The decomposable subset is constructed analogously. It includes:

• • 100 even-length paths;

• • 100 even-length cycles;

• • 100 tadpole graphs with $m = 3$ and odd $n$ ,

with the remaining 1000 instances generated via a similar inductive procedure. To ensure decomposability, pendant vertices from at least one graph in $\mathcal {P} \setminus \mathcal {P}_{\mathrm {even}}$ or ${\mathcal {T} \setminus \mathcal {T}_{3, \mathrm {odd}}}$ are identified with a vertex of degree two in the base graph. This ensures that the resulting graph is still a cactus graph with maximum degree of three, but no longer satisfies the exceptional structural constraints of $\mathfrak {T}$ and is thus decomposable.

In addition, we include some adversarial decomposable instances obtained by deleting one or more edges from exceptional graphs while maintaining connectivity and decomposability. All graphs in the in-distribution dataset contain at least one cycle and at most ten cycles.

3.2 Experimental setup

To ensure a controlled and reproducible comparison of GNN architectures, we design our experiments to isolate the impact of aggregation and update mechanisms, while minimizing variance from data splits and optimization effects.

3.2.2 Shared model architecture

To isolate architectural effects, we adopt a shared backbone architecture across all GNN variants. The only components that differ between models are the message aggregation and update functions specific to each architecture. Each input graph $G_i = (V_i, E_i)$ is defined by its node set $V_i$ and edge set $E_i$ , node features $\{\mathbf {x}_v \mid v \in V_i\}$ and a one-hot encoded class label $\mathbf {y}_i \in \{0,1\}^2$ .

Node features are passed through $L = 3$ message-passing layers to produce embeddings $\mathbf {h}_v^{(L)}$ . A relatively low number of layers is chosen to avoid over-smoothing, which was shown to be prevalent in GNNs [Reference Wu, Chen, Wang and Jadbabaie72]. Hidden layers use a dimensionality of 64 and the final node embeddings are projected to 16 dimensions. This choice reflects common practice in the GNN literature, where hidden dimensions typically range from 16 to 256 [Reference Hamilton, Ying and Leskovec27, Reference Hu, Fey, Zitnik, Dong, Ren, Liu, Catasta and Leskovec30, Reference Kipf and Welling38]. The message-passing process is as follows:

$$ \begin{align*} \mathbf{h}_v^{(0)} \rightarrow \mathbf{h}_v^{(1)} \rightarrow \mathbf{h}_v^{(2)} \rightarrow \mathbf{h}_v^{(3)} \end{align*} $$

with initial embeddings $\mathbf {h}_v^{(0)} = \mathbf {x}_v$ . A LeakyReLU [Reference Maas, Hannun and Ng50] nonlinearity is applied after the first two layers:

$$ \begin{align*} \mathbf{h}_v^{(l)} \leftarrow \mathrm{LeakyReLU}(\mathbf{h}_v^{(l)}), \end{align*} $$

where $\mathrm {LeakyReLU}(z) = \max (\alpha z, z)$ , $\alpha = 0.2$ . We also apply graph-wide normalization with GraphNorm as proposed by Cai et al. [Reference Cai, Luo, Xu, He, Liu and Wang14]. The normalization is defined as

$$ \begin{align*} \mathbf{h}_{\mathrm{norm}} = \dfrac{\mathbf{h} - \alpha \cdot \mathbb{E}[\mathbf{h}]}{\sqrt{\mathrm{Var}[\alpha \cdot \mathbb{E}[\mathbf{h}]] + \epsilon}} \cdot \gamma + \beta , \end{align*} $$

where $\alpha , \beta $ and $\gamma $ are learnable parameters, and $\epsilon $ is a small constant to prevent division by 0. Normalization is applied after each GNN layer prior to the nonlinearity (when applicable). This is done such that the node embeddings have an appropriate (learnable) distribution that is conducive to learning. GraphNorm has been shown to improve training stability, accelerate convergence and help with generalization in graph learning tasks [Reference Cai, Luo, Xu, He, Liu and Wang14].

3.3 Graph-level representation

After the final message-passing layer, node embeddings are aggregated using global sum pooling to form a graph-level representation

$$ \begin{align*} \mathbf{h}_{G_i} = \sum_{v \in V^{(i)}} \mathbf{h}_v^{(L)}. \end{align*} $$

The resulting graph embedding is passed through a multilayer perceptron (MLP) with a single hidden layer and a softmax output, producing predicted class probabilities $\boldsymbol {\hat {y}}^{(i)} \in [0, 1]^2$ . Models are trained using the binary cross-entropy loss:

$$ \begin{align*} \mathcal{L}(\mathbf{y}_{i}, \boldsymbol{\hat{y}}_{i}) = - \sum_{c = 1}^2 y_{i,c} \log (\hat{y}_{i,c}), \end{align*} $$

and optimized using the Adam optimizer [Reference Kingma37]. An overview of the shared architecture is shown in Figure 3.

Figure 3

Illustration of the forward pass shared by the GNN models.

3.4 Aggregation

In this section, we present the aggregation schemes considered in this study. While not exhaustive, the selected architectures GCN [Reference Kipf and Welling38], GraphSAGE [Reference Hamilton, Ying and Leskovec27], GAT [Reference Veličkovi’c, Cucurull, Casanova, Romero, Lio and Bengio66] and GIN [Reference Xu, Hu, Leskovec and Jegelka75] represent some of the most widely adopted message passing neural network (MPNN) frameworks in recent years, due to their effectiveness across a range of graph learning tasks [Reference Hajibabaee, Malekzadeh, Heidari, Zad, Uzuner and Jones26, Reference Liang, Qian, Yu, Griffith and Golmie45, Reference Liu, Ong and Chen47, Reference Liu and Wang48, Reference Vrahatis, Lazaros and Kotsiantis67, Reference Zhang, Tong, Xu and Maciejewski77, Reference Zhang, Zhang and Wu78]. Table 2 summarizes the node-wise update formulation for each layer for some GNN models. These aggregation layers are implemented using PytorchGeometric (PyG) [Reference Fey and Lenssen18, Reference Fey19].

Table 2

Summary of models considered in this study and their node-wise update formulations for each layer.

Table 2 Long description

The table consists of three columns: Model, Node-wise update for layer l, and Description.

* G C N: h sub v super (l) = Theta super (l) transpose summation over u in N(v) union {v} of (e sub v,u / sqrt(d-hat sub u d-hat sub v)) h sub u super (l-1). Described as a graph convolutional network with symmetric normalization.

* GraphSAGE-mean: h sub v super (l) = Theta sub 1 super (l) h sub v super (l-1) + Theta sub 2 super (l) dot mean({h sub u super (l-1) : u in N(v)}). Aggregates neighbor features using elementwise mean.

* GraphSAGE-lstm: (c sub v,t super (l), s sub v,t super (l)) = L S T M Cell(h sub u sub t super (l-1), (c sub v,t-1 super (l), s sub v,t-1 super (l))). Aggregates neighbors sequentially using an L S T M.

* GraphSAGE-lstm (shuffled): h sub v super (l) = Theta sub 1 super (l) h sub v super (l-1) + Theta sub 2 super (l) s sub v, |N(v)| super (l). Same as above but with random shuffling.

* GraphSAGE-max: h sub v super (l) = Theta sub 1 super (l) h sub v super (l-1) + Theta sub 2 super (l) dot max({ReLU(Theta sub 3 super (l) h sub u super (l-1) + b) : u in N(v)}). Aggregates using elementwise maximum.

* G A T-1 head: alpha sub v,u super (l) = exp(LeakyReLU(a super (l) transpose [Theta super (l) h sub v super (l-1) || Theta super (l) h sub u super (l-1)])) all over summation over w in N(v) of the same exp term. A graph attention network with one head.

* G A T-2 heads: h sub v super (l) = summation over u in N(v) of alpha sub vu super (l) Theta super (l) h sub u super (l-1). Uses two concatenated attention heads.

* G A T-4 heads: Formulation omitted. Uses four concatenated attention heads.

* G I N: h sub v super (l) = M L P sub Theta super (l) ((1 + epsilon super (l)) dot h sub v super (l-1) + summation over u in N(v) of h sub u super (l-1)). A graph isomorphism network using an M L P for updates.

4.1 Learning dynamics

Figures 4 and 5 illustrate the learning dynamics of the corresponding GNN architectures over 500 training epochs under two initialization regimes, which are constant node features and one-hot-degree as initial node features. By holding the training protocol fixed while varying only the initial node information, these experiments isolate how architectural inductive bias interacts with minimal node-level signals to enable stable learning and generalization. Training times are comparable across architectures (approximately 350 seconds on average), with the exception of the shuffled GraphSAGE-lstm variant (approximately 900 seconds), where the additional cost arises from per-iteration node-index shuffling.

Figure 4

Accuracy learning curves (mean $\pm $ std across five folds) for training, validation and OOD splits using constant node features.

Figure 5

Accuracy learning curves (mean $\pm $ std across five folds) for training, validation and OOD splits using one-hot-degree node features.

Under constant initialization (Figure 4), most architectures achieve high training accuracy but fail to generalize, collapsing to near-random performance on both validation and OOD splits. This behaviour indicates that message passing alone is frequently insufficient to recover the structural signal required by the task of distinguishing decomposable and exceptional graphs. Only GCN, GIN and the lstm-based GraphSAGE variants achieve nontrivial validation accuracy, stabilizing above 80% on average across five folds. These models share stronger aggregation or update mechanisms either near injective aggregation [Reference Xu, Hu, Leskovec and Jegelka75] or sequential neighbourhood integration, suggesting that increased architectural expressivity partially compensates for the absence of explicit node features. Nevertheless, even these architectures exhibit pronounced degradation on OOD graphs, revealing a limitation in extrapolating learned representations to graphs with substantially larger size or higher-order structure.

Introducing one-hot-degree as initial node features (Figure 5) fundamentally alters the learning behaviour. Architectures that previously failed to generalize, such as SAGE-mean, SAGE-max and all GAT variants, now converge reliably, exhibit reduced variance across folds, and achieve consistently higher validation and OOD accuracy. Across models, training and validation accuracy typically stabilize within the first 100 epochs, while OOD performance continues to improve thereafter, indicating that even with minimal local structural information, it is possible to achieve stable representation learning and extrapolation. These results suggest that degree features can help break representational symmetry and allow message passing to exploit local structural cues more effectively.

We further quantify these effects in Table 3 and analyse the corresponding embedding spaces in Section 4.3 to explain the observed differences in generalization behaviour.

Table 3

Average validation and OOD accuracy of various aggregation schemes ( $\pm $ std) and corresponding differences between validation and OOD accuracy ( $\Delta $ Gap) for 500 epochs.

Table 3 Long description

The table is structured with a primary header row for Initial node features, split into Constant and One-hot-degree. Each category contains three sub-columns: Val Acc, O O D Acc, and Delta Gap.

* G C N: Constant features show Val Acc 0.814 plus or minus 0.015, O O D Acc 0.627 plus or minus 0.056, and Delta Gap tilde 0.187. One-hot-degree features show Val Acc 0.829 plus or minus 0.011, O O D Acc 0.627 plus or minus 0.019, and Delta Gap tilde 0.202.

* Graph S A G E-mean: Constant features show Val Acc 0.513 and O O D Acc 0.510. One-hot-degree features show Val Acc 0.837 and O O D Acc 0.662.

* Graph S A G E-l s t m: Constant features show Val Acc 0.866 plus or minus 0.010 and O O D Acc 0.589. One-hot-degree features show Val Acc 0.872 plus or minus 0.012 and O O D Acc 0.628.

* Graph S A G E-l s t m (shuffled): Constant features show Val Acc 0.843 and O O D Acc 0.553. One-hot-degree features show Val Acc 0.862 and O O D Acc 0.700 plus or minus 0.078.

* Graph S A G E-max: Constant features show Val Acc 0.519 and O O D Acc 0.513. One-hot-degree features show Val Acc 0.850 and O O D Acc 0.585.

* G A T-1 head: Constant features show Val Acc 0.542 and O O D Acc 0.510. One-hot-degree features show Val Acc 0.734 and O O D Acc 0.691 with a Delta Gap of tilde 0.043.

* G A T-2 heads: Constant features show Val Acc 0.533 and O O D Acc 0.511. One-hot-degree features show Val Acc 0.798 and O O D Acc 0.609.

* G A T-4 heads: Constant features show Val Acc 0.543 and O O D Acc 0.530. One-hot-degree features show Val Acc 0.831 and O O D Acc 0.619.

* G I N: Constant features show Val Acc 0.817 and O O D Acc 0.535. One-hot-degree features show Val Acc 0.856 and O O D Acc 0.657.

4.2 Comparative performance and OOD generalization

Table 3 reports the best average validation and OOD accuracies across five folds for each architecture after 500 training epochs. We observe several trends, which are as follows.

• • Incorporating one-hot-degree features improves validation accuracy and substantially reduces performance variance across folds for nearly all architectures. In addition, the gap between in-distribution and OOD accuracy is reduced, indicating improved robustness under distribution shift.

• • The GraphSAGE-lstm variants achieve the highest validation accuracy overall, followed closely by GIN. Notably, the unshuffled GraphSAGE-lstm outperforms its shuffled counterpart on validation data, but this comes at the cost of reduced OOD performance. Because the dataset is constructed with an arbitrary but fixed node ordering, this behaviour suggests that the unshuffled model may exploit order-dependent patterns that do not generalize. Shuffling node indices act as a regularizer, reducing validation accuracy while improving OOD robustness.

• • GAT architectures exhibit lower validation accuracy than the top-performing models even with degree features, but their OOD performance is comparatively strong, where it is surpassed only by the shuffled GraphSAGE-lstm. We observe that increasing the number of attention heads in GAT consistently improves training and validation accuracy, but worsens OOD performance. This is highly suggestive that higher-capacity attention mechanisms more readily overfit to an in-distribution structure.

• • GIN performs strongly on training and validation data, consistent with its known theoretical expressivity equivalent to the Weisfeiler–Lehman test [Reference Xu, Hu, Leskovec and Jegelka75]. With the task of classifying decomposable and exceptional graphs being equivalent to determining isomorphism to a graph in $\mathfrak {T}'$ , it is no surprise that GINs performed well in this setting. However, as with most architectures considered, GIN performance degrades on OOD graphs, suggesting that expressive aggregation alone may overfit and does not guarantee robustness to changes in graph size or structural complexity.

Taken together, these results demonstrate that while expressive aggregation can partially compensate for limited node features, its effectiveness is highly architecture dependent and fragile under distribution shift. For the task of classifying decomposable and exceptional graphs, only a small subset of architectures sustains meaningful generalization without explicit node information. With appropriate aggregation mechanisms and minimal structural node features, we show that GNNs can achieve high in-distribution accuracy and limited but nontrivial generalization to unseen graph distributions.

Detailed confusion matrices for the validation and OOD splits are reported in Figures A1 and A2, respectively, in Appendix A. On the validation set, predictions are generally well balanced across all architectures, with no strong bias towards either class. In contrast, evaluation on the OOD split reveals a consistent shift across most models towards increased false positives such that exceptional graphs are increasingly misclassified as decomposable.

Inspection of the graph distributions suggests that this behaviour is driven by a distributional bias. In the in-distribution training set, decomposable graphs tend to have larger order and size on average than exceptional graphs. As a result, models appear to rely on coarse graph-scale statistics, leading to an over-prediction of the decomposable class when confronted with larger or structurally more complex OOD graphs. Notably, the single-head GAT is the only architecture that does not exhibit this bias to the same extent, maintaining a more balanced error profile under distribution shift. This observation further supports the conclusion that single-head attention in GAT encourages the learning of more generalizable structural cues rather than over-reliance on size-related artefacts, despite their lower performance on the training and validation set.

4.3 Embedding analysis

It has been shown that the performance of many message passing GNNs degrades in the absence of node features [Reference Cai and Wang13, Reference Errica, Podda, Bacciu and Micheli17]; however, little work has been done to show why that is the case. In our results, we show that this is not the case in general and it is possible for some GNNs to learn meaningful representations related to graph structure despite the lack of initial node features.

We observe that both mean and max aggregation fail when all vertices share identical initial embeddings. Our experiments further reveal that GATs, despite having a more complex aggregation scheme exhibit the same limitations, as evidenced by their degraded performance under constant node features. This behaviour can be explained by examining the GAT aggregation rule, as shown as follows:

$$ \begin{align*} \alpha_{v,u}^{(l)} &= \dfrac{\exp\, \big(\mathrm{LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}_v^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}_u^{(l-1)}\big]\big)\big)}{\sum_{w \in \mathcal{N}(v) \cup \{v\}}\exp\, \big(\mathrm{ LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}_v^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}_w^{(l-1)}\big]\big)\big)}, \\[4pt]\mathbf{h}_v^{(l)} &= \sum_{u \in \mathcal{N}(v) \cup \{v\}} \alpha_{vu}^{(l)} \boldsymbol{\Theta}^{(l)} \mathbf{h}_u^{(l-1)}. \end{align*} $$

Suppose $\mathbf {h}_v^{(l-1)} = \mathbf {h}_u^{(l-1)} = \mathbf {h}^{(l-1)}$ for all $v,u \in V(G)$ , then

$$ \begin{align*} \alpha_{v,u}^{(l)} &= \dfrac{\exp\, \big(\mathrm{LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}_v^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}_u^{(l-1)}\big]\big)\big)}{\sum_{w \in \mathcal{N}(v) \cup \{v\}}\exp\, \big(\mathrm{ LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}_v^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}_w^{(l-1)}\big]\big)\big)} \\ &= \dfrac{\exp\, \big(\mathrm{LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}^{(l-1)}\big]\big)\big)}{\sum_{w \in \mathcal{N}(v) \cup \{v\}}\exp\, \big(\mathrm{ LeakyReLU}\big(\mathbf{a}^{(l)^{\top}}\big[\boldsymbol{\Theta}^{(l)}\mathbf{h}^{(l-1)}\Vert \boldsymbol{\Theta}^{(l)}\mathbf{h}^{(l-1)} \big]\big)\big)} \\ &= \dfrac{1}{\mathrm{deg}(v) + 1}. \end{align*} $$

Following this,

$$ \begin{align*} \mathbf{h}_v^{(l)} &= \sum_{u \in \mathcal{N}(v) \cup \{v\}} \alpha_{vu}^{(l)} \boldsymbol{\Theta}^{(l)} \mathbf{h}_u^{(l-1)} \\&= \sum_{u \in \mathcal{N}(v) \cup \{v\}} \dfrac{1}{\mathrm{deg}(v) + 1} \boldsymbol{\Theta}^{(l)} \mathbf{h}^{(l-1)} \\&= \dfrac{\boldsymbol{\Theta}^{(l)}}{\mathrm{deg}(v) + 1} \sum_{u \in \mathcal{N}(v) \cup \{v\}} \mathbf{h}^{(l-1)}\\&= \dfrac{\boldsymbol{\Theta}^{(l)}}{\mathrm{deg}(v) + 1} \cdot (\mathrm{deg}(v) + 1) \mathbf{h}^{(l-1)} \\[3pt] &= \boldsymbol{\Theta}^{(l)} \mathbf{h}^{(l-1)}. \end{align*} $$

This implies that under uniform initial embeddings, GAT layers reduce to a linear transformation applied identically to each node. This results in a complete loss of structural information. Due to the fact that each subsequent layer propagates identical representations, increasing network depth does not resolve the degeneracy. The same phenomenon also occurs in the improved GAT variant proposed in [Reference Brody, Alon and Yahav12], which relocates the attention vector outside the nonlinearity but does not address collapse under uniform features. Analogous derivations apply to GraphSAGE with mean and max aggregation as examples shown in [Reference Xu, Hu, Leskovec and Jegelka75]. As a consequence, when node features are identical or nearly identical, GATs and similar architectures struggle to distinguish graph structure.

The empirical evidence in Table 4 demonstrates that including degree as a node feature allows GraphSAGE-mean, GraphSAGE-max and GAT to generate embeddings with substantially higher effective dimensionality after message passing. Conversely, using constant node features results in embeddings that are effectively linear. In contrast, aggregation schemes like GCN and GIN do not suffer from this to the same extent, as their aggregation schemes have partially recover structural information such as node degree (for example, the $\sqrt {\hat {d}_u \cdot \hat {d}_v}$ normalization term in GCN and the summation over neighbouring embeddings in GIN and GraphSAGE-lstm; see Table 2). Consequently, the performance of GCN, GIN and GraphSAGE-lstm with constant node features remains relatively close to the case where degree information is included explicitly, though explicit degree features still yield a modest improvement.

Table 4

Number of principal components for $>$ 99% cumulative explained variance for each model, trained on constant initialized node embeddings and one-hot-degree initialized node embeddings.

Table 4 Long description

The table consists of three columns: Model, Constant initialization, and One-hot-degree initialization.

* G C N: 6 for Constant, 6 for One-hot-degree.

* Graph S A G E-mean: 1 for Constant, 6 for One-hot-degree.

* Graph S A G E-max: 1 for Constant, 7 for One-hot-degree.

* Graph S A G E-l s t m: 8 for Constant, 7 for One-hot-degree.

* Graph S A G E-l s t m-shuffled: 7 for Constant, 7 for One-hot-degree.

* G A T-1 H: 1 for Constant, 5 for One-hot-degree.

* G A T-2 H: 1 for Constant, 6 for One-hot-degree.

* G A T-4 H: 1 for Constant, 7 for One-hot-degree.

* G I N: 6 for Constant, 8 for One-hot-degree.

The highest value for Constant initialization is 8 (Graph S A G E-l s t m) and the highest for One-hot-degree is 8 (G I N).

4.3.2 Misclassified graphs

By extracting the learned graph embeddings and inspecting the misclassified instances, we observe that most in-distribution misclassifications cluster within localized regions of the embedding space rather than being uniformly dispersed (see Figure 6). These regions are dominated by simple graphs such as path, cycle and tadpole graphs, indicating that these structures induce systematic ambiguity for the models. Further inspection of the predicted class probabilities reveals that, for these graph families, the models typically assign near-uniform probabilities (approximately 50–50) across classes. This suggests that the learned representations capture insufficient discriminative signals for these motifs, rather than exhibiting a strong but incorrect bias towards a particular class. In other words, the models appear uncertain rather than confidently wrong, pointing to an inherent representational limitation when distinguishing these structurally simple yet ambiguous graphs.

Figure 6

Missclassified graphs for GIN and GraphSAGE-lstm for the validation set (fold two). The cluster of missclassified graphs (in red) consists of paths, cycles and tadpole graphs. Similar clusters exist for the embeddings generated by other aggregation schemes.

Excluding these simple graphs, the remaining misclassified graphs do not exhibit a consistent structural pattern and are scattered uniformly throughout the dataset. In these cases, however, the top-performing models tend to be confidently incorrect, often assigning high probability to the wrong class. Notably, despite these errors, the overall prediction distribution on the validation set remains balanced, with no systematic preference for either class. This indicates that misclassifications are not driven by class imbalance or global bias.

The OOD set does not contain path, cycle or tadpole graphs. Nevertheless, we expect similar outcomes as in the in-distribution set to persist for these graphs. For OOD graphs, we observe that models frequently misclassify graphs with high confidence, predominantly prediction on the decomposable class. We attribute this behaviour to a distributional shift in graph size and order, where decomposable graphs in the training sets tend to have higher average size, causing the models to rely on size-correlated features that do not generalize to the OOD dataset. While this effect is present across architectures, it is less pronounced in GAT-based models than other well-performing models in the validation such as GIN and GraphSAGE-lstm variants. We suspect that it is due to the lower intrinsic dimensionality of the embeddings generated. This allows the embeddings to be more generalizable to unseen distributions instead of overfitting.

Figure 7 visualizes OOD embeddings using t-SNE [Reference van der Maaten and Hinton65] for both GAT and GIN. The embeddings produced by GAT-1H exhibit less polarized decision regions, resulting in less one-sided predictions. However, increasing the number of attention heads increases the tendency to predict decomposable graphs, suggesting that additional heads may encourage overfitting to in-distribution structural statistics rather than improving robustness to distributional shift. This behaviour aligns with our PCA analysis, which shows that embeddings produced by GIN and GraphSAGE-lstm exhibit substantially higher intrinsic dimensionality. This implies that increased model capacity that captures in-distribution variability is at the expense of generalization to OOD graph structures.

Figure 7

Comparison of true and predicted labels for GAT-1H and GIN, with normalization and one-hot encoded degree as initial features for the OOD set (fold two). We observe that for aggregation schemes other than GAT-1H, the predictions tend to bias towards decomposable graphs heavily.

4.4 Long-term behaviour of the models

We ran extended training (2500 epochs) for the top-performing architectures on the validation set, which are GIN and the GraphSAGE-lstm variants. Figure 8 shows the training, validation and OOD accuracies over the full 2500 epochs (mean $\pm $ std across five folds).

Figure 8

Accuracy learning curves (mean $\pm $ std across five folds) for training, validation and OOD splits using constant node features.

First, training and validation accuracies stabilize near approximately 85% well before 2500 epochs, while OOD accuracy continues to improve after epoch 500. This divergence indicates that prolonged training can yield representations that generalize better to OOD instances even after the conventional train/validation signals appear to have converged. Second, the different architectures exhibit distinct reliability across folds, where the shuffled GraphSAGE-lstm variant produces the most stable OOD performance (small variance between folds), whereas GIN shows substantially greater variability, where some folds reach OOD performance comparable to training and validation, while others stop improving at approximately 60% accuracy.

We inspected the fold contents to identify obvious distributional causes (for example, different counts of paths, cycles or tadpole graphs across folds), but found no meaningful differences in these distributions. Thus, the observed GIN sensitivity appears not to be explained by a sampling imbalance. Possible contributors include stochastic optimization effects (initialization and SGD noise), model inductive bias and capacity, or differing reliance on size-correlated features that fail to generalize to the OOD set. Resolving these possibilities is left to future work.

Taken together, these results provide evidence that: (1) extended training can improve OOD generalization for some architectures; and (2) model choice and architecture-specific behaviour (here, the stability advantage of shuffled GraphSAGE-lstm versus the fold sensitivity of GIN) materially affect OOD robustness. We therefore recommend that experimental evaluations of OOD generalization report OOD metrics across extended training runs and across multiple folds and/or seeds rather than relying on the epoch at which training and validation appears to converge.

5.1 Computational budget

Owing to limited compute resources, the extended 2500-epoch experiments were performed on the two top validation models (GIN and GraphSAGE-lstm variants) rather than across all nine architectures. This choice was made deliberately to: (1) exercise the highest-capacity, best-performing architectures; and (2) evaluate whether extended training yields consistent OOD gains for the most promising models. We acknowledge this selection is not exhaustive. Future work should expand long-run experiments to additional architectures as compute allows.

5.2 Dataset scale and design

Our dataset (training and validation set of 2600 graphs and OOD set of 520 graphs) is primarily hand-crafted to ensure coverage of the structural motifs relevant to the locally irregular edge-colouring decision problem. This domain-specific construction trades scale for careful control over specific graph patterns and adversarial instances. This may limit how broadly the quantitative results generalize to naturally occurring graphs. We therefore present our empirical findings as targeted evidence about GNN behaviour on this problem family rather than as universal claims about all graph-classification tasks.

5.3 Limited hyper-parameter exploration

Network training was performed for five folds and we report mean $\pm $ std and we did not perform exhaustive hyper-parameter sweeps or change random seeds. The fold-to-fold variability observed for GIN suggests that additional seeds, systematic hyper-parameter searches and a larger number of folds would be valuable to fully characterize architecture-level sensitivity. We therefore treat the long-run experiments as evidence of promising behaviour, not definitive proof that extended training universally improves OOD generalization.

5.4 Scope of aggregation schemes

We focused on widely used aggregation schemes (GCN, GraphSAGE, GAT and GIN) as representative baselines, supported by their prevalence in the literature and in common frameworks. This is evidenced by the foundational papers for these models being among the most cited in graph learning [Reference Hamilton, Ying and Leskovec27, Reference Kipf and Welling38, Reference Veličkovi’c, Cucurull, Casanova, Romero, Lio and Bengio66, Reference Xu, Hu, Leskovec and Jegelka75]. Overall, surveys and benchmarks regularly list these models as prototypical GNN architectures [Reference Hu, Fey, Zitnik, Dong, Ren, Liu, Catasta and Leskovec30, Reference Morris, Kriege, Bause, Kersting, Mutzel and Neumann53]. However, other alternative aggregation and readout strategies exist and may be better tailored to the locally irregular edge-colouring problem. Future work should explore broader families of GNNs and non-GNN baselines (graph kernels, classical combinatorial methods) to better delineate where GNNs succeed and fail on this task.