# ADMP-GNN: Adaptive Depth Message Passing GNN

Yassine Abbahaddou

LIX, Ecole Polytechnique, IP Paris

Palaiseau, France

yassine.abbahaddou@polytechnique.edu

Johannes F. Lutzeyer

LIX, Ecole Polytechnique, IP Paris

Palaiseau, France

johannes.lutzeyer@polytechnique.edu

Fragkiskos D. Malliaros

Université Paris-Saclay, CentraleSupélec, Inria

Gif-sur-Yvette, France

fragkiskos.malliaros@centralesupelec.fr

Michalis Vazirgiannis

LIX, Ecole Polytechnique, IP Paris

Palaiseau, France

mvazirg@lix.polytechnique.fr

## Abstract

Graph Neural Networks (GNNs) have proven to be highly effective in various graph learning tasks. A key characteristic of GNNs is their use of a fixed number of message-passing steps for all nodes in the graph, regardless of each node's diverse computational needs and characteristics. Through empirical real-world data analysis, we demonstrate that the optimal number of message-passing layers varies for nodes with different characteristics. This finding is further supported by experiments conducted on synthetic datasets. To address this, we propose *Adaptive Depth Message Passing GNN (ADMP-GNN)*, a novel framework that dynamically adjusts the number of message passing layers for each node, resulting in improved performance. This approach applies to any model that follows the message passing scheme. We evaluate ADMP-GNN on the node classification task and observe performance improvements over baseline GNN models. Our code is publicly available at: https://github.com/abbahaddou/ADMP-GNN.

## CCS Concepts

* **Computing methodologies → Machine learning;**
* **Theory of computation → Randomness, geometry and discrete structures.**

## Keywords

Graph Neural Networks, Adaptive Neural Networks

## ACM Reference Format:

Yassine Abbahaddou, Fragkiskos D. Malliaros, Johannes F. Lutzeyer, and Michalis Vazirgiannis. 2025. ADMP-GNN: Adaptive Depth Message Passing GNN. In *Proceedings of the 34th ACM International Conference on Information and Knowledge Management (CIKM '25)*, November 10–14, 2025, *Seoul, Republic of Korea*. ACM, New York, NY, USA, 10 pages. https://doi.org/10.1145/3746252.3761009

## 1 Introduction

A plethora of structured data comes in the form of graphs [3, 5, 31]. This has driven the need to develop neural network models, known as Graph Neural Networks (GNNs), that can effectively process and analyze graph-structured data. GNNs have garnered significant attention for their ability to learn complex node and graph representations, achieving remarkable success in several practical applications [6, 9, 10, 32, 33]. Many of these models are instances of Message Passing Neural Networks (MPNNs) [16, 24, 42]. A common characteristic of GNNs is that they typically employ a fixed number of message passing steps for all nodes, determined by the number of layers in the GNN [16]. This static framework raises an intriguing question: *Should the number of message passing steps be adapted individually for each node to better capture their unique characteristics and computational needs?*

Determining the optimal number of message passing layers for each node in a GNN presents a significant challenge due to the intricate and diverse nature of graph structures, node features, and learning tasks. While deeper GNNs can capture long-range dependencies [28], they can also encounter issues like oversmoothing, where nodes become indistinguishably similar [17, 29]. In dense graphs, where information can propagate quickly, even shallow GNNs can effectively capture local information [45]. Conversely, sparse graphs may require additional layers to facilitate effective information sharing [46, 47]. This underscores the importance of selecting the appropriate number of layers for a GNN to capture the necessary graph information effectively. An even more compelling idea is to adjust the GNN depth for each node based on its local structural properties. This adaptive approach could be especially beneficial for graphs with varied local structures, ensuring that each node is processed according to its unique requirements.

This need for per-node customization naturally aligns with the concept of *Dynamic Neural Networks*, also referred to as *Adaptive Neural Networks* [2]. Dynamic Neural Networks represent a class of models that can adjust their architecture or parameters depending on the input. Dynamic Neural Networks have gained significant popularity, especially in the field of computer vision. Examples of adaptation include varying the number of layers and implementing skip connections [20, 25, 35]. Beyond computer vision, other types of adaptive neural networks have been explored in various domains. In natural language processing, adaptive computation time models allow recurrent neural networks (RNNs) to determine the required number of recurrent steps dynamically based on the complexity

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.

CIKM '25, *Seoul, Republic of Korea*

© 2025 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 979-8-4007-2040-6/2025/11
https://doi.org/10.1145/3746252.3761009
of the input sequence [18]. However, applying these adaptations to graph learning tasks presents unique challenges. Unlike the structured and homogeneous data often encountered in computer vision, graph data involves overcoming nuisances related to the inherent complex structure of graphs. Graphs may have varying node degrees, non-uniform connectivity, and feature Heterogeneity. While some dynamic approaches may extend effectively to graph classification tasks, applying these methods to node classification presents additional complexities. In node classification, each input sample (node) is part of a larger interconnected system where information propagates through edges, i.e., the prediction for one node often depends on the features of the other nodes and the structure of the graph. As a result, specific techniques are needed to account for the dependencies and relational information encoded in the graph structure.

In this work, we focus on the task of node classification by proposing ADMP-GNN, a novel approach that dynamically adapts the number of layers for each node within a GNN. Our main contributions are as follows:

*   **Node-specific depth analysis in GNNs.** We demonstrate through empirical analysis that different nodes within the same graph may require varying numbers of message passing steps to accurately predict their labels. This finding underscores the importance of node-specific depth in GNNs.

*   **Adaptive message passing layer integration.** We present ADMP-GNN, a novel approach that enables any GNN to make predictions for each node at every layer. Training the GNN to predict labels across all layers is a multi-task setting, which often suffers from gradient conflicts, leading to suboptimal performance. To address this, we propose a sequential training methodology where layers are progressively trained, and their gradients are subsequently frozen, thereby mitigating conflicts and improving overall performance.

*   **Adaptive layer policy learning for node classification.** We introduce a heuristic method to learn a layer selection policy using a set of validation nodes. This policy is then applied to select the optimal layer for predicting the labels of test nodes, ensuring that each node exits the GNN at the most appropriate layer for its specific classification task.

*   **Model-agnostic flexibility.** Our approach is model-agnostic and can be integrated with any GNN architecture that employs a message passing scheme. This flexibility enhances the GNN's performance on node classification tasks, providing a significant improvement over traditional fixed-layer approaches.

## 2 Related Work

In this section, we review key developments in GNNs and dynamical neural networks, which form the foundation of our work.

### 2.1 Graph Neural Networks

Graphs, denoted as $G = (\mathcal{V}, \mathcal{E}, X)$, are mathematical structures used to represent pairwise relationships. Here, $\mathcal{V}$ is the set of nodes, $\mathcal{E}$ is the set of edges, and $X = \{x_u : u \in \mathcal{V}\}$ represents the node features, where each $x_u \in \mathbb{R}^d$ corresponds to a $d$-dimensional feature vector associated with node $u$. GNNs are a class of deep

learning methods specifically designed to operate on such graph-structured data. As with most neural networks, GNNs are formed by stacking many layers. Each layer, $\ell$, is responsible for updating the node representations $\{h_u^{(\ell)} : u \in \mathcal{V}\}_{0 \le \ell \le L}$, relying on the graph structure and the output from the previous layer, $\{h_u^{(\ell-1)} : u \in \mathcal{V}\}$. Conventionally, the features of the nodes are used as input of the first layer, i.e., $h_u^{(0)} = x_u \in \mathbb{R}^d$ for all $u \in \mathcal{V}$. A basic GNN layer is based on the message passing mechanism and consists of two components: (i) Aggregate Layer $\psi$ that applies for each node $v$, a permutation invariant function to its neighbors, denoted by $\mathcal{N}(v)$ to generate the aggregated node feature; (ii) Update Layer $\phi$ that combines the aggregated node feature $m_v^{(\ell)}$ with the previous hidden vector $h_v^{(\ell-1)}$, and generate a new representation $h_v^{(\ell)}$ of the same node $v$,

$$m_v^{(\ell)} = \psi^{(\ell)}(\{h_u^{(\ell-1)} : u \in \mathcal{N}(v)\}), \\ h_v^{(\ell)} = \phi^{(\ell)}(h_v^{(\ell-1)}, m_v^{(\ell)}).$$

Depending on the task, an additional readout or pooling function can be added after the last layer to aggregate the representation of nodes, as follows, $h_G = \text{ReadOut}(\{h_u^{(L)} : u \in \mathcal{V}\})$. Examples of the most popular GNN models include the Graph Convolutional Network (GCN) [24] and Graph Isomorphism Network (GIN) [42], which apply a weighted sum and sum operator in their aggregate layer, respectively.

### 2.2 Dynamical Neural Networks

Dynamic neural networks are gaining significance in the field of deep learning. Unlike static models with fixed computational graphs and parameters during inference, dynamic networks adapt their structures or parameters based on varying inputs. This dynamic flexibility gives models significant benefits, such as improved accuracy, enhanced computational efficiency, and superior adaptability [41, 48]. A popular type of dynamic neural networks includes those that dynamically adjust network depth based on each input. For instance, in natural language processing, some adaptive large language models employ adaptive depth to optimize both inference speed and computational memory usage of the Transformer architecture [11, 36, 40]. In the field of computer vision, there are studies that dynamically generate filters conditioned on each input, enhancing flexibility without significantly increasing the number of model parameters [22].

In Graph Machine Learning, dynamic adaptations have been proposed for GNN message passing. These methods include dynamically determining which neighbors to consider at each layer, enabling more flexible and adaptive message passing [15], or allowing nodes to react to individual messages at varying times rather than processing aggregated neighborhood information synchronously [14]. Another line of work focuses on adapting normalization layers for each node to enhance expressive power, generating representations that reflect local neighborhood structures [12]. Additionally, other related approaches use residual connections to mitigate issues like oversmoothing [7, 13]. To the best of our knowledge, in the field of GNNs, there has been no prior work proposing adaptive depth for each node. However, several studies have focused on combining
<figure><img src="image_1.png" /><figcaption>Figure 1: Effect of GCN's depth on sparse and dense subgraphs. The figure shows the performance of GCNs when varying layer depths, and comparing its effectiveness on both sparse and dense subgraphs.</figcaption></figure>

all GNN layers. These works typically aim to adapt GNN architectures for heterophilic graphs [8] and leverage information from higher-order neighbors [43]. While combining GNN layers can be viewed as a form of depth-adaptive strategy, where the final node representation is guided by the optimal intermediate hidden states, this approach remains static because the same inference policy is applied uniformly across all nodes and learned layer aggregators stay fixed after training.

## 3 Adaptive Depth Message Passing GNN

In this section, we first present an empirical analysis highlighting the necessity for node-specific depth in GNNs. Then, we introduce our ADMP-GNN. Our study includes experiments on both synthetic and real-world datasets to illustrate the importance and potential benefits of this methodology.

### 3.1 Depth Analysis on Synthetic Graphs

This analysis aims to highlight the importance of employing a varying number of message passing steps based on the specific characteristics of individual nodes. As outlined in the introduction, this approach is particularly relevant for graphs where nodes exhibit diverse properties, such as varying local structures. In this experiment, we investigate the effect of the number of message-passing layers on nodes with varied levels of local neighborhood sparsity. To achieve this, we construct a graph by merging two subgraphs extracted from real-world datasets, namely Computers and Photo [38]. Both subgraphs contain the same number of nodes, exhibit nearly identical homophily, and have equally distributed node labels. The main difference between these subgraphs lies in their structure, as one subgraph is sparse while the other is dense. Consequently, nodes within each subgraph share comparable structural characteristics. Details on the construction of these synthetic

datasets and visualizations of their adjacency matrices are provided in Appendix A.

We have trained $L + 1$ different GCN models, with a varying number of layers $\ell \in \{0, \dots, L\}$, where $L$ represents the maximum depth, set to $L = 10$. Each GCN was trained on the entire synthetic graph, composed of both sparse and dense subgraphs, but the performance was evaluated separately on the individual subgraphs. This allows us to assess the impact of GNN depth on different types of local subgraph structures. The results, presented in Fig. 1, reveal notable differences in behavior between the subgraph types. As observed, in dense subgraphs, the test accuracy decreases at a faster rate, while in sparse subgraphs, the drop in accuracy occurs later, typically around layers 2 or 3. Moreover, the optimal number of layers differs between sparse and dense subgraphs. For instance, in the Computers dataset, the highest accuracy is achieved at layer 2 for the sparse subgraph, while for the dense subgraph, the optimal performance is reached at layer 0. Additionally, in the Photo dataset, we observe a distinct behavior starting from layer 6, where the impact of GNN depth diverges between sparse and dense subgraphs. This highlights the need to adapt the number of layers per node based on its characteristics.

### 3.2 Adaptive Message Passing Layer Integration

Building on the insights from the previous analysis, it is essential to develop a framework that can efficiently adjust the GNN depth. For a maximum GNN depth $L$, a traditional approach would involve training $L + 1$ different GNNs, each with a distinct number of layers $\ell$, where $\ell$ ranges from 0 and $L$. Subsequently, a policy must be established to determine the optimal GNN with the appropriate number of layers for each individual node. However, training $L + 1$ GNNs separately can be computationally expensive. A more efficient approach involves designing a single GNN with $L + 1$ layers that provide predictions at each intermediate layer. To ensure equivalence to the previous approach, i.e., training $L + 1$ GNNs separately, the computational graph for predictions at layer $\ell$ must match that of a standard GNN with $\ell$ layers, and the classification performance at layer $\ell$ should yield results comparable to those of a conventional GNN with $\ell$ layers.

To address these challenges, we introduce ADMP-GNN, an adaptation of a Message Passing Neural Network with a maximum depth of $L$ layers. The goal is to ensure that the computational graph and the performance of ADMP-GNN at a certain layer match that of traditional GNNs when trained and tested on the same number of layers. To achieve this, we incorporate an additional Update function, denoted as $\phi_{\text{Ex}}^{(\ell)}$ (Ex stands for 'Exit'), to directly predict node labels at a given layer $\ell$, i.e., $p^{(\ell)}$. The function $\phi_{\text{Ex}}^{(\ell)}$ is defined as follows,

$$p_{v}^{(\ell)} = \phi_{\text{Ex}}^{(\ell)} (h_{v}^{(\ell-1)}, m_{v}^{(\ell)}) = \text{Softmax} (\tilde{W}^{(\ell)} m_{v}^{(\ell)})$$

where $\tilde{W}^{(\ell)} \in \mathbb{R}^{d^{(\ell)} \times c}$ is a learnable weight matrix, $d^{(\ell)}$ is the dimension of the hidden representation at the $\ell$-th layer, and $c$ is the number of classes. To obtain predictions at a deeper layer $\ell' \ge \ell$, we continue the message passing using another Update function
<figure><img src="image_2.png" /><figcaption>Figure 2: Illustration of ADMP-GNN, when the maximum GNN depth is $L = 3$.</figcaption></figure>

$\phi_{\text{Ct}}^{(\ell)}$ (Ct stands for 'Continuation'),

$$ 
\begin{aligned}
p_v^{(\ell)} &= \phi_{\text{Ex}}^{(\ell)} (h_v^{(\ell-1)}, m_v^{(\ell)}), \\
h_v^{(\ell+1)} &= \phi_{\text{Ct}}^{(\ell)} (h_v^{(\ell-1)}, m_v^{(\ell)}).
\end{aligned}
$$

For $\ell = 0$, we directly use the Exit Update function on the node features, i.e., $m_v^{(0)} = x_v$,

$$ \forall v \in \mathcal{V}, \quad p_v^{(0)} = \phi_{\text{Ex}}^{(0)}(m_v^{(0)}) = \text{Softmax}(\tilde{W}^{(0)} x_v). $$

In Fig. 2, we illustrate the architecture of the proposed ADMP-GNN.

## 3.3 Training Scheme of ADMP-GNN

Our next objective is to train ADMP-GNN to predict node labels across all layers $\ell \in \{0, \dots, L\}$ simultaneously. For each layer $\ell$, let $\theta_{\ell}$ denote the weights of the function $\psi^{(\ell)} \circ \phi_{\text{Ct}}^{(\ell)}(\cdot)$. Two distinct strategies for training ADMP-GNN are explored:

1. **Aggregate Loss Minimization (ALM).** This straightforward approach minimizes the aggregate loss over all layers. The total loss is formulated as,

$$ \mathcal{L}_{\text{ALM}} := \arg \min_{\theta} \mathbb{E}_{v \in \mathcal{V}} [S_L(v)] \quad (1) $$

$$ = \arg \min_{\theta_0, \dots, \theta_L} \mathbb{E}_{v \in \mathcal{V}} \left[ \sum_{\ell=0}^{L} \mathcal{L} \left( p_v^{(\ell)}(m_v^{(0)}, \theta_0, \dots, \theta_\ell), y_v \right) \right], $$

where $p_v^{(\ell)}(m_v^{(0)}, \theta_0, \dots, \theta_\ell) = \phi_{\text{Ex}}^{(\ell)}(m_v^{(\ell)})$ is the prediction for node $v$ at layer $\ell$, and $\mathcal{L}$ is the Cross Entropy Loss. This approach may encounter gradient conflicts, particularly for early layers involved in both computation and back-propagation across upper layers.

2. **Sequential Training (ST).** We have studied an alternative training setup where we progressively train one GNN layer at a time, subsequently freezing each layer after training. More formally, the problem in (1) can be tackled using dynamic programming as follows,

$$ \forall v \in \mathcal{V}, S_{\ell+1}(v) = \mathcal{L} \left( p_v^{(\ell)}(m_v^{(0)}, \theta_0^*, \dots, \theta_\ell^*, \theta_{\ell+1}), y_v \right) + S_\ell(v) $$

$$ \theta_{\ell}^{*} = \arg \min_{\theta_{\ell}} \mathbb{E}_{v \in V} [S_{\ell}(v)], $$

where $\forall v \in \mathcal{V}, S_0(v) = \mathcal{L}(\phi_{\text{Ex}}^{(0)}, y_v)$. For each intermediate layer $\ell < L$, by training this layer on the node classification task, we

**Algorithm 1: Sequential Training for ADMP-GNN**

**Inputs:** Graph $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathcal{X})$, number of layers $L$, node classification loss function $\mathcal{L}$,

**foreach** $t \in \{0, \dots, L\}$ **do**

if $t=0$ **then**

1. Set $\tilde{h}_v^{(0)} \leftarrow m_v^{(0)} = x_v$ for all $v \in \mathcal{V}$.

2. Compute predictions at layer $\ell = 0$, i.e.,

$$ \forall v \in \mathcal{V}, \quad p_v^{(0)} = \phi_{\text{Ex}}^{(0)}(\tilde{h}_v^{(0)}). $$

3. Train the weights of $\phi_{\text{Ex}}^{(0)}$ to minimize $\mathcal{L}(p_v^{(0)})$.

4. Freeze the gradients of $\phi_{\text{Ex}}^{(0)}$.

else

1. Use the $\phi_{\text{Ct}}^{(t-1)}$ to update node representations

$$ \forall v \in \mathcal{V}, \quad \tilde{h}_v^{(t-1)} = \phi_{\text{Ct}}^{(t-1)}(\tilde{h}_v^{(t-1)}). $$

2. Aggregate the information for neighbor nodes

$$ \forall v \in \mathcal{V}, \quad m_v^{(t)} = \psi^{(t)}(\{\tilde{h}_u^{(t-1)} : u \in \mathcal{N}(v)\}). $$

3. Compute predictions at layer $\ell = t$, i.e.,

$$ \forall v \in \mathcal{V}, \quad p_v^{(t)} = \phi_{\text{Ct}}^{(t-1)}(\tilde{h}_v^{(t-1)}, m_v^{(t)}). $$

4. Train $\phi_{\text{Ct}}^{(t-1)}$, $\psi^{(t)}$, and $\phi_{\text{Ex}}^{(t)}$ to minimize $\mathcal{L}(p_v^{(t)})$.

5. Freeze the gradients of $\phi_{\text{Ct}}^{(t-1)}$, $\psi^{(t)}$, and $\phi_{\text{Ex}}^{(t)}$.

end **foreach**

obtain high-quality node representations $\{\tilde{h}_v^{(\ell)} : v \in \mathcal{V}\}$. These representations are directly employed for predictions and serve as a robust foundation for the label predictions of the subsequent layer $\ell+1$. Algorithm 1 offers a summary of the approach.

**Comparison of ADMP-GNN Training Paradigms.** To identify the optimal multi-task training configuration, we evaluate how much of a performance drop we incur at each layer compared to the single-task setting in GNNs. The comparative analysis of the three strategies for both GCN is detailed in Tables 1. Our findings indicate that ADMP-GNN ST outperforms ADMP-GNN ALM. Notably, the performance of ADMP-GNN ST is comparable to, or even exceeds, that of GNN when trained under the single-task setting. Furthermore, ADMP-GNN ST exhibits a smaller standard deviation, suggesting more consistent performance. These results underscore the effectiveness of the ST setting in addressing gradient conflicts inherent in aggregate loss minimization (ALM). Furthermore, ADMP-GNN ST effectively mimics the results of training $L+1$ separate GNNs,
each with a different number of layers, while requiring only a single unified model. The next step, outlined in Section 3.5, is to learn a policy that selects the optimal prediction layer for each node, completing the framework of ADMP-GNN.

*Time Complexity.* The training setup ST, where we sequentially train the deep ADMP-GNN, incurs relatively higher time costs due to the need for $L + 1$ training iterations. However, in each iteration, backpropagation is performed on a limited number of parameters, approximately equivalent to those in a single message passing layer. Consequently, only a small number of epochs are required for each training iteration. We report the training time of each approach in Table 5 in Appendix B.

## 3.4 Empirical Insights into Node Specific Depth

We define *Oracle Accuracy* as the maximum achievable test accuracy under an optimal policy for selecting layers. This is formally expressed as,

$$ \mathcal{A}_{\text{oracle}} = \frac{1}{|\mathcal{V}_{\text{test}}|} \sum_{v \in \mathcal{V}_{\text{test}}} 1(y_v \in \{\hat{y}_v^{(\ell)} : \ell = 0, \dots, L\}), $$

where $\mathcal{V}_{\text{test}}$ is the set of test nodes, $\{\hat{y}_v^{(\ell)} : \ell = 0, \dots, L\}$ represents the predictions for node $v$ at each layer, and $1(\cdot)$ is the indicator function. Specifically, $\mathcal{A}_{\text{oracle}}$ corresponds to the accuracy obtained if, for each test node, we could perfectly choose the layer that provides the correct prediction. Assuming such an optimal selection for each node, it represents the upper bound of accuracy achievable when employing adaptive strategies to determine the best layer for each node.

Based on the findings presented in Table 2 for GCN, it is clear that $\mathcal{A}_{\text{oracle}}$ outperforms the highest accuracies achieved by both GCN and ADMP-GCN ALM. This empirical evidence strongly indicates that adopting a distinct exit layer for each node is highly beneficial in an optimal configuration.

## 3.5 Generalization to Test Nodes

In this section, we introduce a heuristic approach to predict the optimal exit layer for test nodes based on the assumption that nodes exhibiting structural similarity should share the same exit layer. The notion of structural similarity can be assessed using various metrics. In our work, we define the structural similarity based on node centrality metrics, i.e., nodes are considered structurally similar if they exhibit closely aligned centrality values within the graph. We measured node centralities using both local metrics like degree and global metrics such as k-core [30], PageRank scores [4], and Walk Count, which are detailed below.

**k-core.** The k-core decomposition of a graph is a method that involves systematically pruning nodes. In each iteration, a subgraph $G_k \subset G$ is constructed by removing all vertices whose degree is less than k. The core number of a vertex u, denoted as core(u), represents the largest value of k for which i is included in the k-core. Formally, this is expressed as core(i) = max${k : i \in G_k}$.
Nodes with higher core numbers are typically found in denser subgraphs, reflecting strong interconnections with their neighbors and indicating a higher level of centrality.

**PageRank.** A node's PageRank score represents the probability of a random walk visiting that node, making it a fundamental metric for measuring node importance in social network analysis and the web [4].

**Walk Count.** The Walk Count centrality quantifies the importance of a node based on the number of walks of a given length $\ell$ starting from that node. This measure captures higher-order connectivity patterns within the graph, going beyond direct neighbors to account for paths that traverse intermediate nodes. In this work, we consider the Walk Count centrality for $\ell = 2$, as it effectively captures higher-order structures and provides valuable insights into the organization of complex systems [1].

Using this assumption, we employ node clustering to partition the node set into C clusters, denoted by $\mathcal{P} = \cup_{1 \le l \le c \le C} \mathcal{P}_l$. Each cluster $c \in \{1, \dots, C\}$ is assigned a common exit layer $\ell_c \in \{0, \dots, L\}$, determined using nodes excluded from the test set. Validation nodes are utilized for this purpose. (i) Centrality scores are computed for all nodes, considering metrics. (ii) Nodes are ranked based on their centrality scores. (iii) These centrality scores are discretized into C equal-sized buckets to facilitate the clustering process. (iv) The optimal exit layer for each cluster is determined by evaluating the classification accuracy on validation nodes within that cluster, i.e.,

$$ \forall c \in \{1, \dots, C\}, \quad \ell_c = \arg \max_{\ell \in \{0, \dots, L\}} \text{Acc} \{p_v^{(\ell)} \in \mathcal{V}_{\text{val}} \cap \mathcal{P}_c\}. $$

**Ablation Study.** The choice of using validation nodes rather than training nodes for learning the layer selection policy stems for the high prediction accuracy on training nodes across all layers. This high accuracy leads to a significant distribution shift between the predictions for train nodes and those for test nodes. Conversely, validation nodes, which were not utilized during the training of the ADMP-GNN, present a more suitable option for learning the policy due to their unbiased predictions. For the choice of the cluster-based layer selection policy, we could use a variety of deep learning mechanisms to predict the best exit layer for each node. This included generalizing the policy by training neural networks to identify layers that accurately predict node outcomes or by framing the problem as an optimal stopping problem following the framework of [21]. However, these approaches require learning the policy on a set of nodes larger than the test set, which is impractical for node classification tasks where the training and validation node sets available for policy learning are typically smaller than the test set.

# 4 Experimental Evaluation

## 4.1 Experimental Setup

**Datasets.** We use thirteen widely used datasets in the GNN literature. We particularly used the citation networks Cora, CiteSeer, and PubMed [37], the co-authorship networks CS [38], the citation network between Computer Science arXiv papers Ogbn-arxiv [19], the Amazon Computers and Amazon Photo networks [38], the non-homophilous dataset genius [26], and the disassortative datasets Chameleon, Squirrel [34], and Cornell, Texas, Wisconsin from the WebKB dataset [27]. More details and statistics about the used datasets can be found in Appendix C. For the Cora, CiteSeer, and Pubmed datasets, we used the provided train/validation/test
<table><caption>Table 1: Comparison of ADMP-GCN training paradigms ALM and ST. These paradigms are also compared to the single-task training setting to evaluate which approach most closely mimics the classical GCN under single-task training. The best multi-task results for each dataset are bolded.</caption><thead><tr><th># Layers</th><th>Training Paradigm</th><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genius</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td rowspan="2">①</td><td>Single-task</td><td>GCN</td><td>56.38±0.04</td><td>57.18±0.12</td><td>88.04±0.49</td><td>72.50±0.09</td><td>80.82±1.00</td><td>48.88±0.06</td></tr><tr><td>Multi-task</td><td>ADMP-GCN (ALM)<br>ADMP-GCN (ST)</td><td><b>56.96±0.20</b><br>56.38±0.06</td><td><b>58.44±0.21</b><br>57.17±0.09</td><td>87.06±1.06<br>87.27±1.29</td><td>72.11±0.18<br>72.48±0.14</td><td>80.03±0.37<br>80.17±0.79</td><td>36.50±0.12<br><b>48.86±0.03</b></td></tr><tr><td rowspan="2">②</td><td>Single-task</td><td>GCN</td><td>76.90±0.14</td><td>69.68±0.06</td><td>91.74±0.80</td><td>76.63±0.13</td><td>80.23±0.37</td><td>55.21±0.50</td></tr><tr><td>Multi-task</td><td>ADMP-GCN (ALM)<br>ADMP-GCN (ST)</td><td><b>75.67±0.18</b><br><b>76.90±0.00</b></td><td><b>70.12±0.04</b><br>69.70±0.00</td><td>90.55±0.74<br><b>90.89±0.81</b></td><td>73.74±0.16<br><b>76.60±0.00</b></td><td><b>80.13±0.29</b><br>79.93±0.00</td><td>39.54±1.44<br><b>55.15±0.00</b></td></tr><tr><td rowspan="2">③</td><td>Single-task</td><td>GCN</td><td>79.14±1.58</td><td>66.33±1.35</td><td>89.80±0.87</td><td>78.50±0.68</td><td>80.00±0.04</td><td>67.33±0.55</td></tr><tr><td>Multi-task</td><td>ADMP-GCN (ALM)<br>ADMP-GCN (ST)</td><td><b>68.64±5.14</b><br><b>80.21±0.52</b></td><td><b>51.30±6.74</b><br><b>70.08±0.90</b></td><td>47.82±12.98<br><b>89.83±1.02</b></td><td>74.17±1.98<br><b>78.25±0.51</b></td><td><b>80.04±0.10</b><br>79.93±0.00</td><td>56.22±0.50<br><b>68.31±0.48</b></td></tr><tr><td rowspan="2">④</td><td>Single-task</td><td>GCN</td><td>75.96±1.93</td><td>60.33±2.38</td><td>78.90±22.33</td><td>76.59±0.98</td><td>80.01±0.04</td><td>65.49±0.99</td></tr><tr><td>Multi-task</td><td>ADMP-GCN (ALM)<br>ADMP-GCN (ST)</td><td><b>67.88±6.05</b><br><b>81.05±0.49</b></td><td><b>49.29±7.87</b><br><b>67.99±0.74</b></td><td>52.76±11.79<br><b>88.86±0.70</b></td><td>73.40±1.95<br><b>75.27±1.02</b></td><td><b>80.04±0.10</b><br>79.93±0.00</td><td>56.43±0.31<br><b>69.29±0.74</b></td></tr><tr><td rowspan="2">⑤</td><td>Single-task</td><td>GCN</td><td>70.09±4.01</td><td>57.40±3.43</td><td>77.96±15.24</td><td>74.32±3.66</td><td>80.01±0.04</td><td>63.04±1.33</td></tr><tr><td>Multi-task</td><td>ADMP-GCN (ALM)<br>ADMP-GCN (ST)</td><td><b>67.68±7.04</b><br><b>81.22±0.36</b></td><td><b>50.14±7.65</b><br><b>67.42±0.75</b></td><td>54.53±10.61<br><b>86.65±1.52</b></td><td>73.27±1.51<br><b>75.08±0.94</b></td><td><b>80.04±0.10</b><br>79.93±0.00</td><td>56.66±0.31<br><b>68.92±1.00</b></td></tr></tbody></table>

<table><caption>Table 2: Comparison of highest accuracy (± standard deviation) for GCN and ADMP-GCN ST, with the layer achieving the best accuracy indicated in brackets. The final row shows the Oracle Accuracy for ADMP-GCN ST. Best results for each dataset are bolded.</caption><thead><tr><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genius</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td>GCN</td><td>81.06±0.50 [2]</td><td>71.05±0.48 [2]</td><td>91.67±0.94 [2]</td><td>79.46±0.31 [2]</td><td>80.82±1.00 [0]</td><td>67.33±0.55 [3]</td></tr><tr><td>ADMP-GCN (ST)</td><td>81.22±0.36 [5]</td><td>71.33±0.40 [2]</td><td>91.49±0.66 [2]</td><td>79.02±0.21 [2]</td><td>80.17±0.79 [0]</td><td>69.29±0.74 [4]</td></tr><tr><td>ADMP-GCN (ST) - Oracle</td><td><b>89.43±0.19</b></td><td><b>81.96±0.49</b></td><td><b>97.24±0.52</b></td><td><b>90.13±0.36</b></td><td><b>85.97±7.59</b></td><td>79.64±0.27</td></tr></tbody></table>

<table><caption>Table 3: Classification accuracy (± standard deviation) on different node classification datasets for the baselines based on the GCN backbone. The higher the accuracy (in %), the better the model. Highlighted are the first, second best results. OOM means Out of memory.</caption><thead><tr><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genius</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td>JKNET-CAT</td><td>79.52±1.16 [2]</td><td>69.69±0.05 [1]</td><td>91.23±1.26 [1]</td><td>77.63±0.59 [2]</td><td><b>81.46±0.10</b> [2]</td><td>68.54±0.57 [5]</td></tr><tr><td>JKNET-MAX</td><td>75.67±0.18 [1]</td><td>70.12±0.04 [1]</td><td>90.55±0.74 [1]</td><td>75.10±2.41 [2]</td><td>80.13±0.29 [1]</td><td>56.66±0.31 [5]</td></tr><tr><td>JKNET-LSTM</td><td>78.95±0.62 [0]</td><td>65.83±1.27 [0]</td><td>90.17±1.41 [2]</td><td>77.73±0.67 [0]</td><td>OOM</td><td>OOM</td></tr><tr><td>Residuals - GCNII</td><td>76.84±0.20 [1]</td><td>69.72±0.06 [1]</td><td>90.84±1.35 [1]</td><td>77.82±0.44 [2]</td><td>81.36±1.13 [2]</td><td>61.48±3.10 [4]</td></tr><tr><td>AdaGCN</td><td>75.08±0.27 [1]</td><td>69.58±0.19 [1]</td><td>89.62±0.51 [0]</td><td>76.40±0.12 [5]</td><td>79.85±0.00 [0]</td><td>22.06±1.67 [5]</td></tr><tr><td>GPR-GNN</td><td>79.91±0.43 [2]</td><td>69.21±0.81 [2]</td><td>91.42±1.12 [2]</td><td>79.00±0.39 [2]</td><td>81.04±0.41 [2]</td><td>68.03±0.23 [3]</td></tr><tr><td>GCN</td><td>80.78±0.72 [2]</td><td>71.25±0.72 [2]</td><td><b>92.20±0.00</b> [1]</td><td><b>79.32±0.41</b> [2]</td><td>80.76±1.05 [0]</td><td>64.37±0.43 [2]</td></tr><tr><td>ADMP-GCN</td><td><b>81.22±0.36</b> [5]</td><td><b>71.33±0.40</b> [2]</td><td>91.49±0.66 [2]</td><td><b>79.02±0.21</b> [2]</td><td>80.17±0.79 [0]</td><td>69.29±0.74 [4]</td></tr><tr><td>ADMP-GCN w/ Degree</td><td>81.03±0.53</td><td>71.10±0.50</td><td>91.26±0.59</td><td>78.71±0.39</td><td>80.73±1.00</td><td>69.59±0.28</td></tr><tr><td>ADMP-GCN w/ k-core</td><td><b>81.19±0.40</b></td><td><b>71.27±0.53</b></td><td>91.29±0.68</td><td>78.73±0.41</td><td>80.73±1.00</td><td>69.55±0.33</td></tr><tr><td>ADMP-GCN w/ Walk Count</td><td>81.14±0.41</td><td>71.14±0.50</td><td>91.19±0.64</td><td>78.64±0.60</td><td>80.68±0.97</td><td>69.55±0.34</td></tr><tr><td>ADMP-GCN w/ PageRank</td><td>81.05±0.46</td><td>71.00±0.29</td><td>91.09±0.99</td><td>78.69±0.56</td><td>81.12±1.41</td><td><b>69.60±0.29</b></td></tr></tbody></table>

splits. For the remaining datasets, we followed the framework in [27, 34].

Baselines. We compare our approach with architectures that combine all the hidden representations of nodes to form a final

node representation used for prediction. For each baseline model, we vary the number of layers from 0 to 5, and we report in Table 3 the performance of the best number of layers with respect
<table><caption>**Table 4: Classification accuracy (± standard deviation) on different node classification datasets for the baselines based on the GIN backbone. The higher the accuracy (in %), the better the model. Highlighted are the first, second best results. OOM means Out of memory.**</caption><thead><tr><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genuis</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td>JKNET-CAT</td><td>77.94±0.67 [2]</td><td>64.82±0.04 [1]</td><td>89.26±1.18 [1]</td><td>75.89±2.50 [2]</td><td>OOM</td><td>60.23±0.37 [1]</td></tr><tr><td>JKNET-MAX</td><td>77.47±0.81 [1]</td><td>64.96±2.08 [2]</td><td>87.40±2.11 [0]</td><td>76.21±1.73 [0]</td><td>OOM</td><td>51.84±4.01 [0]</td></tr><tr><td>JKNET-LSTM</td><td>77.39±1.39 [2]</td><td>64.52±2.02 [1]</td><td>87.27±3.66 [3]</td><td>75.90±1.63 [0]</td><td>OOM</td><td>OOM</td></tr><tr><td>GPR-GIN</td><td>76.83±1.22 [2]</td><td>66.43±1.15 [2]</td><td>88.15±1.53 [5]</td><td>77.27±0.87 [2]</td><td>80.82±0.42 [3]</td><td>63.05±0.44 [2]</td></tr><tr><td>GIN</td><td>77.73±0.99 [2]</td><td>65.23±1.45 [2]</td><td>90.29±0.99 [1]</td><td>76.05±1.14 [2]</td><td>80.78±1.03 [0]</td><td>60.70±0.15 [1]</td></tr><tr><td>ADMP-GIN</td><td>78.07±0.68 [2]</td><td>65.41±1.91 [2]</td><td>90.82±1.15 [1]</td><td>76.46±1.04 [4]</td><td>80.47±0.91 [0]</td><td>60.85±0.01 [1]</td></tr><tr><td>ADMP-GIN w/ Degree</td><td>78.12±0.70</td><td>66.82±0.89</td><td>90.70±0.79</td><td>76.07±1.27</td><td>81.68±0.70</td><td>60.85±0.01</td></tr><tr><td>ADMP-GIN w/ k-core</td><td>78.10±0.64</td><td>66.36±1.03</td><td>90.85±0.93</td><td>75.93±1.13</td><td>81.48±0.64</td><td>60.85±0.01</td></tr><tr><td>ADMP-GIN w/ Walk Count</td><td>78.19±0.68</td><td>65.79±0.81</td><td>90.77±0.91</td><td>76.72±0.76</td><td>81.21±0.58</td><td>60.85±0.01</td></tr><tr><td>ADMP-GIN w/ PageRank</td><td>77.78±0.83</td><td>67.08±0.51</td><td>90.72±0.91</td><td>76.63±0.87</td><td>81.89±1.04</td><td>60.85±0.01</td></tr></tbody></table>

to the test set. (i) This includes *Jumping knowledge*, which combines the nodes representation of all layers using an aggregation layer, e.g., MaxPooling (JKMaxPool), Concatenation (JK-Concat), or LSTM-attention (JK-LSTM) [44]. (ii) Residuals-GCNII uses an initial residual connection and an identity mapping for each layer. The initial residual connection ensures that the final representation of each node retains at least a fraction of $\alpha$ from the input layer [7]. (iii) GPR-GCN combines adaptive generalized PageRank (GPR) scheme with GNNs [8]. (iv) Ada-GCN, which proposes an RNN-like deep GNN architecture by incorporating AdaBoost to combine the layers [39]. In contrast to the baselines, which aggregate the layers and determine the best performance by performing a grid search over the number of layers $L$, we fix the maximum number of layers to $L = 5$ for ADMP-GNN. This comparison gives a strong advantage to the baselines, as their results are optimized for each dataset, while ADMP-GNN's performance is evaluated under a fixed and consistent setup.

*Implementation Details.* We train all the models using the Adam optimizer [23] and the same hyperparameters. The GNN hyperparameters in each dataset were performed using a Grid search on the classical GCN; we detail the values of these hyperparameters in Table 7 of Appendix D. To account for the impact of random initialization, each experiment was repeated 10 times, and the mean and standard deviation of the results were reported. The experiments have been run on both an NVIDIA A100 GPU.

## 4.2 Experimental Results

Through extensive experiments on multiple datasets, we can better understand the scenarios in which ADMP-GNN proves to be effective. As observed in Tables 3, 4, a comparison between ADMP-GCN and ADMP-GIN against their respective baselines, GCN and GIN, demonstrates consistently higher accuracy for most datasets. Regarding the centrality-based layer selection policy, it becomes clear that this policy is particularly efficient when graphs exhibit a wide range of local density and centrality among nodes. Most importantly, no impactful drop in accuracy was observed with ADMP-GNN. It is important to note that the suitability of a given centrality metric can vary significantly across datasets. For instance, while PageRank is widely used, its distribution often forms a peak near

zero due to the normalization constraint where the sum of PageRank scores across nodes equals 1, making it challenging to form meaningful clusters. In contrast, other centrality metrics like k-core and Walk Count are more adaptable in datasets where clear clustering patterns emerge. For example, in datasets like Cora, Ogbn, and Photo, the k-core centrality effectively highlights clusters, enabling an adaptive depth policy. For datasets like Texas and Wisconsin, Walk Count effectively captures the structural diversity necessary for cluster-based layer selection policy. These observations emphasize the importance of selecting appropriate centrality metrics tailored to the specific properties of a dataset to maximize the effectiveness of ADMP-GNN.

## 5 Conclusion

In this work, we propose ADMP-GNN, a novel adoption of message passing neural networks that enables to make predictions for each node at every layer. Additionally, we propose a sequential training approach designed to achieve performance comparable to training multiple GNNs independently in a single-task setting. Our empirical analysis highlights the importance of node-specific depth in GNNs to effectively capture the unique characteristics and computational requirements of each node. Determining the optimal number of message-passing layers for each node is a challenging task, influenced by factors such as the complexity and connectivity of graph structures and the variability introduced by node features. Through our experiments, we identified that node centrality can serve as a useful indicator for determining the optimal layer for each node. To this end, we heuristically learn a layer selection policy using a set of validation nodes, which is then generalized to test nodes. Extensive experiments across multiple datasets, particularly those characterized by a diversity in local structural properties, demonstrate that ADMP-GNN significantly enhances the prediction accuracy of GNNs, offering an effective solution to address the challenges of layer selection and node-specific learning.

## Acknowledgment

F.M. acknowledges the support of the Innov4-ePiK project managed by the French National Research Agency under the 4th PIA, integrated into France2030 (ANR-23-RHUS-0002). Y.A. and M.V. are supported by the French National Research Agency (ANR)
via the AML-HELAS (ANR-19-CHIA-0020) project. Y.A. and J.L. are supported by the French National Research Agency (ANR) via the “GraspGNNs” JCJC grant (ANR-24-CE23-3888). This work was granted access to the HPC resources of IDRIS under the allocation “2024-AD010613410R2” made by GENCI.

## A Node-Specific Depth Analysis in Graph Neural Networks

We generate synthetic graphs of size $N = 5,000$. We select nodes belonging to sparse or dense regions in the original graph based on their core number. We consider only nodes with labels that are sufficiently present in both dense and sparse region. Last, we randomly select nodes, all by keeping the label distribution similar in both sparse and dense subgraphs. Yellow points indicate edges, while purple points represent non-edges. Notably, there are variations in edge density across different blocks: the first block is characterized by extreme sparsity, whereas the second block exhibits a much denser structure.

<figure><img src="image_3.png" /><figcaption>Figure 3: The adjacency matrix of the synthetic graphs extracted from the real graphs Computers and Photo.</figcaption></figure>

## B Time Complexity

Understanding the time complexity of the ADMP-GCN model is crucial for evaluating its practical efficiency and scalability. Table 5 reports the average training time, measured in seconds, for two distinct settings: ALM and ST.

<table><caption>Table 5: The average time needed for each training setting for different datasets.</caption><thead><tr><th>Model</th><th>Cora</th><th>squirel</th><th>chamelon</th><th>Computers</th><th>Photo</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td>ADMP-GCN ALM</td><td>14</td><td>36</td><td>15</td><td>51</td><td>26</td><td>266</td></tr><tr><td>ADMP-GCN ST</td><td>32</td><td>88</td><td>40</td><td>175</td><td>87</td><td>882</td></tr></tbody></table>

## C Dataset Statistics

Characteristics and information about the datasets utilized in the node classification part of the study are presented in Table 6, which provides statistics about each dataset, and highlights the variety in their features, size, and edge homophily,

<table><caption>Table 6: Statistics of the node classification datasets used in our experiments.</caption><thead><tr><th>Dataset</th><th>#Features</th><th>#Nodes</th><th>#Edges</th><th>#Classes</th><th>Edge Homophily</th></tr></thead><tbody><tr><td>Cora</td><td>1,433</td><td>2,708</td><td>5,208</td><td>7</td><td>0.809</td></tr><tr><td>CiteSeer</td><td>3,703</td><td>3,327</td><td>4,552</td><td>6</td><td>0.735</td></tr><tr><td>PubMed</td><td>500</td><td>19,717</td><td>44,338</td><td>3</td><td>0.802</td></tr><tr><td>CS</td><td>6,805</td><td>18,333</td><td>81,894</td><td>15</td><td>0.808</td></tr><tr><td>Genuis</td><td>12</td><td>421,961</td><td>984,979</td><td>5</td><td>0.618</td></tr><tr><td>Ogbn-arxiv</td><td>128</td><td>169,343</td><td>2,315,598</td><td>40</td><td>0.654</td></tr></tbody></table>

## D Hyperparameter Configurations

For a more balanced comparison, however, we use the same training procedure for all the models. The hyperparameters in each dataset where optimized using a grid search on the classical GCN over the following search space:

* Hidden size: [16, 32, 64, 128, 256, 512],

* Learning rate: [0.1, 0.01, 0.001],

* Dropout probability: [16, 32, 64, 128, 256, 512].

The number of layers was fixed to 2. The optimal hyperparameters can be found in Table 7.

<table><caption>Table 7: Hyperparameters used in our experiments.</caption><thead><tr><th>Dataset</th><th>Hidden Size</th><th>Learning Rate</th><th>Dropout Probability</th></tr></thead><tbody><tr><td>Cora</td><td>64</td><td>0.01</td><td>0.8</td></tr><tr><td>CiteSeer</td><td>64</td><td>0.01</td><td>0.4</td></tr><tr><td>PubMed</td><td>64</td><td>0.01</td><td>0.2</td></tr><tr><td>CS</td><td>512</td><td>0.01</td><td>0.4</td></tr><tr><td>Genuis</td><td>512</td><td>0.01</td><td>0.2</td></tr><tr><td>Ogbn-Arxiv</td><td>512</td><td>0.01</td><td>0.5</td></tr></tbody></table>

## E Supplementary Results of ADMP-GIN

We replicate the experiments from the main papers described in Section 3, using the GIN backbone. The results for ADMP-GIN are presented in Tables 8 and 9.

## F GenAI Usage Disclosure

No generative AI tools were used in the preparation of this research, including in the code, data, analysis, or writing of this paper.

## References

[1] Austin R Benson, David F Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. *Science* 353, 6295 (2016), 163–166.

[2] Tolga Bolukbasi, Joseph Wang, Ofer Dekel, and Venkatesh Saligrama. 2017. Adaptive neural networks for efficient inference. In *International Conference on Machine Learning*. PMLR, 527–536.

[3] Stefan Bornholdt and Heinz Georg Schuster. 2001. Handbook of graphs and networks. *From Genome to the Internet, Willey-VCH (2003 Weinheim)* (2001).

[4] Sergey Brin and Lawrence Page. 1998. The anatomy of a large-scale hypertextual web search engine. *Computer networks and ISDN systems* 30, 1-7 (1998), 107–117.

[5] Defu Cao, Yujing Wang, Juanyong Duan, Ce Zhang, Xia Zhu, Congrui Huang, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, et al. 2020. Spectral temporal graph neural network for multivariate time-series forecasting. *Advances in neural information processing systems* 33 (2020), 17766–17778.

[6] Jhon A. Castro-Correa, Jhony H. Giraldo, Mohsen Badiey, and Fragkiskos D. Malliaros. 2024. Gegenbauer Graph Neural Networks for Time-Varying Signal
<table><caption>Table 8: Comparison of ADMP-GIN training paradigms ALM and ST. These paradigms are also compared to the single-task training setting to evaluate which approach most closely mimics the classical GIN under single-task training. The best multi-task results for each dataset are bolded.</caption><thead><tr><th># Layers</th><th>Training Paradigm</th><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genius</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td rowspan="2">0</td><td>Single-task</td><td>GIN</td><td>56.40±0.06</td><td>57.14±0.09</td><td>87.17±1.41</td><td>72.49±0.08</td><td>80.78±1.03</td><td>48.87±0.04</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td><b>58.00±0.00</b><br>56.38±0.04</td><td><b>61.50±0.00</b><br>57.17±0.08</td><td>86.36±0.78<br><b>87.41±0.95</b></td><td><b>73.20±0.00</b><br>72.47±0.14</td><td>79.95±0.10<br><b>80.47±0.91</b></td><td>36.49±0.19<br><b>48.87±0.04</b></td></tr><tr><td rowspan="2">1</td><td>Single-task</td><td>GIN</td><td>75.17±0.09</td><td>64.79±0.03</td><td>90.29±0.99</td><td>74.97±0.11</td><td>78.42±4.95</td><td>60.90±0.15</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td>74.50±0.00<br><b>75.07±0.06</b></td><td><b>66.50±0.00</b><br>64.80±0.00</td><td>88.66±1.18<br><b>90.82±1.15</b></td><td><b>75.40±0.00</b><br>75.00±0.00</td><td>72.07±17.44<br><b>77.01±12.06</b></td><td>59.43±0.73<br><b>60.85±0.01</b></td></tr><tr><td rowspan="2">2</td><td>Single-task</td><td>GIN</td><td>77.73±0.99</td><td>65.23±1.45</td><td>87.93±0.71</td><td>76.05±1.14</td><td>78.89±0.48</td><td>16.23±9.60</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td>63.53±4.80<br><b>78.07±0.68</b></td><td>60.68±2.09<br><b>65.41±1.91</b></td><td>12.90±8.05<br><b>87.47±2.18</b></td><td>72.20±4.11<br><b>76.04±0.88</b></td><td>79.60±0.51<br>72.99±13.48</td><td><b>47.63±3.20</b><br>10.13±8.00</td></tr><tr><td rowspan="2">3</td><td>Single-task</td><td>GIN</td><td>74.40±1.14</td><td>60.81±2.20</td><td>82.13±2.24</td><td>74.97±1.69</td><td>52.22±28.47</td><td>6.00±0.17</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td>66.99±2.85<br><b>76.28±1.11</b></td><td>59.57±2.57<br><b>65.13±1.00</b></td><td>17.69±12.02<br><b>83.60±3.72</b></td><td>74.15±2.00<br><b>76.21±1.75</b></td><td>68.00±23.98<br><b>80.04±0.09</b></td><td><b>27.51±16.25</b><br>13.74±9.66</td></tr><tr><td rowspan="2">4</td><td>Single-task</td><td>GIN</td><td>67.68±4.07</td><td>57.54±2.92</td><td>47.37±17.10</td><td>73.62±1.63</td><td>80.05±0.10</td><td>6.07±0.21</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td>68.78±4.30<br><b>74.94±1.58</b></td><td>60.12±2.36<br><b>65.21±1.54</b></td><td>21.07±14.15<br><b>81.33±2.15</b></td><td><b>74.20±2.57</b><br><b>76.46±1.04</b></td><td>79.36±1.18<br><b>80.04±0.09</b></td><td>15.23±11.85<br><b>16.02±10.78</b></td></tr><tr><td rowspan="2">5</td><td>Single-task</td><td>GIN</td><td>32.48±0.47</td><td>54.76±2.32</td><td>18.56±11.32</td><td>67.98±5.80</td><td>80.05±0.10</td><td>6.19±0.39</td></tr><tr><td>Multi-task</td><td>ADMP-GIN (ALM)<br>ADMP-GIN (ST)</td><td>67.46±4.34<br><b>71.34±2.09</b></td><td>59.74±1.95<br><b>63.89±1.39</b></td><td>29.16±13.84<br><b>79.10±1.84</b></td><td>73.94±2.42<br><b>75.75±1.09</b></td><td>79.99±0.10<br>79.57±1.40</td><td>14.61±12.11<br><b>15.72±12.13</b></td></tr></tbody></table>

<table><caption>Table 9: Comparison of highest accuracy (± standard deviation) for GIN and ADMP-GIN ST, with the layer achieving the best accuracy indicated in brackets. The final row shows the Oracle Accuracy for ADMP-GIN ST. Best results for each dataset are bolded.</caption><thead><tr><th>Model</th><th>Cora</th><th>CiteSeer</th><th>CS</th><th>PubMed</th><th>Genius</th><th>Ogbn-arxiv</th></tr></thead><tbody><tr><td>GIN</td><td>77.73±0.99 [2]</td><td>65.23±1.45 [2]</td><td>90.29±0.99 [1]</td><td>76.05±1.14 [2]</td><td>80.78±1.03 [0]</td><td>60.90±0.15 [1]</td></tr><tr><td>ADMP-GIN (ST)</td><td>78.07±0.68 [2]</td><td>65.41±1.91 [2]</td><td>90.82±1.15 [1]</td><td>76.46±1.04 [4]</td><td>80.47±0.91 [0]</td><td>60.85±0.01 [1]</td></tr><tr><td>ADMP-GIN ST - Oracle</td><td><b>90.76±0.27</b></td><td><b>81.87±0.63</b></td><td><b>97.64±0.18</b></td><td><b>92.73±0.54</b></td><td><b>92.07±6.13</b></td><td><b>71.23±2.69</b></td></tr></tbody></table>

Reconstruction. *IEEE Transactions on Neural Networks and Learning Systems* 35, 9 (2024), 11734–11745.

[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. 2020. Simple and deep graph convolutional networks. In *International conference on machine learning*. PMLR, 1725–1735.

[8] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2020. Adaptive universal generalized pagerank graph neural network. *arXiv preprint arXiv:2006.07988* (2020).

[9] Gabriele Corso, Bowen Jing, Regina Barzilay, Tommi Jaakkola, et al. 2023. Diff-Dock: Diffusion Steps, Twists, and Turns for Molecular Docking. In *International Conference on Learning Representations (ICLR 2023)*.

[10] Alexandre Duval, Victor Schmidt, Alex Hernández-García, Santiago Miret, Fragkiskos D. Malliaros, Yoshua Bengio, and David Rolnick. 2023. FAENet: Frame Averaging Equivariant GNN for Materials Modeling. In *Proceedings of the 40th International Conference on Machine Learning*. PMLR, 9013–9033.

[11] Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. 2020. Depth-Adaptive Transformer. In *International Conference on Learning Representations*. https://openreview.net/forum?id=SJg7KhVKPH

[12] Moshe Eliasof, Beatrice Bevilacqua, Carola-Bibiane Schönlieb, and Haggai Maron. 2024. GRANOLA: Adaptive Normalization for Graph Neural Networks. *arXiv preprint arXiv:2404.13344* (2024).

[13] Federico Errica, Henrik Christiansen, Viktor Zaverik, Takashi Maruyama, Math- ias Niepert, and Francesco Alesiani. 2023. Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching. *arXiv preprint arXiv:2312.16560* (2023).

[14] Lukas Faber and Roger Wattenhofer. 2024. GwAC: GNNs with Asynchronous Communication. In *Learning on Graphs Conference*. PMLR, 8–1.

[15] Ben Finkelshtein, Xingyue Huang, Michael M. Bronstein, and Ismail Ilkan Ceylan. 2024. Cooperative Graph Neural Networks. https://openreview.net/forum?id=T0FuEDnODP

[16] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. 2017. Neural message passing for quantum chemistry. In *International conference on machine learning*. PMLR, 1263–1272.

[17] Jhony H. Giraldo, Konstantinos Skianis, Thierry Bouwmans, and Fragkiskos D. Malliaros. 2023. On the Trade-off between Over-smoothing and Over-squashing in Deep Graph Neural Networks. In *Proceedings of the 32nd ACM International Conference on Information and Knowledge Management (CIKM '23)*. 566–576.

[18] Alex Graves. 2016. Adaptive computation time for recurrent neural networks. *arXiv preprint arXiv:1603.08983* (2016).

[19] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. *Advances in neural information processing systems* 33 (2020), 22118–22133.

[20] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q Weinberger. 2016. Deep networks with stochastic depth. In *Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part IV 14*. Springer, 646–661.

[21] Côme Huré, Huyën Pham, Achref Bachouch, and Nicolas Langrené. 2021. Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis. *SIAM J. Numer. Anal.* 59, 1 (2021), 525–557.

[22] Xu Jia, Bert De Brabandere, Tinne Tuytelaars, and Luc V Gool. 2016. Dynamic filter networks. *Advances in neural information processing systems* 29 (2016).

[23] Diederik P. Kingma and Jimmy Ba. 2014. Adam: A Method for Stochastic Optimization. doi:10.48550/ARXIV.1412.6980

[24] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In *ICLR*.

[25] Hao Li, Asim Kadav, Igor Durdanovic, Hanan Samet, and Hans Peter Graf. 2017. Pruning Filters for Efficient ConvNets. In *International Conference on Learning Representations*. https://openreview.net/forum?id=rJqFGTslg
[26] Derek Lim and Austin R Benson. 2021. Expertise and dynamics within crowdsourced musical knowledge curation: A case study of the genius platform. In *Proceedings of the International AAAI Conference on Web and Social Media*, Vol. 15. 373–384.

[27] Derek Lim, Felix Matthew Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Prasad Bhalerao, and Ser-Nam Lim. 2021. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. In *Advances in Neural Information Processing Systems*, A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (Eds.).

[28] Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and Xiaokui Xiao. 2021. Eignn: Efficient infinite-depth graph neural networks. *Advances in Neural Information Processing Systems* 34 (2021), 18762–18773.

[29] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. 2022. Revisiting heterophily for graph neural networks. *Advances in neural information processing systems* 35 (2022), 1362–1375.

[30] Fragkiskos D. Malliaros, Christos Giatsidis, Apostolos N. Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: theory, algorithms and applications. *VLDB J.* 29, 1 (2020), 61–92.

[31] Fragkiskos D. Malliaros and Michalis Vazirgiannis. 2013. Clustering and community detection in directed networks: A survey. *Physics Reports* 533, 4 (2013), 95–142. Clustering and Community Detection in Directed Networks: A Survey.

[32] George Panagopoulos, Nikolaos Tziortziotis, Michalis Vazirgiannis, and Fragkiskos Malliaros. 2024. Maximizing Influence with Graph Neural Networks. In *Proceedings of the 2023 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining*, 237–244.

[33] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. 2022. Recipe for a general, powerful, scalable graph transformer. *Advances in Neural Information Processing Systems* 35 (2022), 14501–14515.

[34] Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2021. Multi-scale attributed node embedding. *Journal of Complex Networks* 9, 2 (2021), cnab014.

[35] Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. 2017. Dynamic routing between capsules. *Advances in neural information processing systems* 30 (2017).

[36] Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q. Tran, Yi Tay, and Donald Metzler. 2022. Confident Adaptive Language Modeling. In *Advances in Neural Information Processing Systems*, Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (Eds.). https://openreview.net/forum?id=uLYc4L3C81A

[37] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective Classification in Network Data. *AI Magazine*

29, 3 (Sep. 2008), 93. doi:10.1609/aimag.v29i3.2157

[38] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. doi:10.48550/ARXIV.1811.05868

[39] Ke Sun, Zhanxing Zhu, and Zhouchen Lin. 2021. Ada[GCN]: Adaboosting Graph Convolutional Networks into Deep Models. In *International Conference on Learning Representations*. https://openreview.net/forum?id=QkRbdiiEjM

[40] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention Is All You Need. CoRR abs/1706.03762 (2017). arXiv:1706.03762 http://arxiv.org/abs/1706.03762

[41] Yulin Wang, Kangchen Lv, Rui Huang, Shiji Song, Le Yang, and Gao Huang. 2020. Glance and Focus: a Dynamic Approach to Reducing Spatial Redundancy in Image Classification. CoRR abs/2010.05300 (2020). arXiv:2010.05300 https://arxiv.org/abs/2010.05300

[42] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In *7th International Conference on Learning Representations*.

[43] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation Learning on Graphs with Jumping Knowledge Networks. CoRR abs/1806.03536 (2018). arXiv:1806.03536 http://arxiv.org/abs/1806.03536

[44] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation Learning on Graphs with Jumping Knowledge Networks. In *Proceedings of the 35th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 80)*, Jennifer Dy and Andreas Krause (Eds.). PMLR, 5453–5462. https://proceedings.mlr.press/v80/xu18c.html

[45] Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Rajgopal Kannan, Viktor Prasanna, Long Jin, Andrey Malevich, and Ren Chen. 2020. Deep graph neural networks with shallow subgraph samplers. (2020).

[46] Wentao Zhang, Zeang Sheng, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. 2021. Evaluating deep graph neural networks. arXiv preprint arXiv:2108.00955 (2021).

[47] Lingxiao Zhao and Leman Akoglu. 2020. PairNorm: Tackling Oversmoothing in GNNs. In *International Conference on Learning Representations*.

[48] Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian J. McAuley, Ke Xu, and Furu Wei. 2020. BERT Loses Patience: Fast and Robust Inference with Early Exit. CoRR abs/2006.04152 (2020). arXiv:2006.04152 https://arxiv.org/abs/2006.04152