Bayesian Neighborhood Adaptation for Graph Neural Networks
Authors: Paribesh Regmi
Rui Li
Kishan K C
Venue: Accepted by TMLR ()

Abstract: The neighborhood scope (i.e., number of hops) where graph neural networks (GNNs) aggregate information to characterize a node's statistical property is critical to GNNs' performance. Two-stage approaches, training and validating GNNs for every pre-specified neighborhood scope to search for the best setting, is a time-consuming task and tends to be biased due to the search space design. How to adaptively determine proper neighborhood scopes for the aggregation process for both homophilic and heterophilic graphs remains largely unexplored. We thus propose to model the GNNs' message-passing behavior on a graph as a stochastic process by treating the number of hops as a beta process. This Bayesian framework allows us to infer the most plausible neighborhood scope for message aggregation simultaneously with the optimization of GNN parameters. Our theoretical analysis shows that the scope inference improves the expressivity of a GNN. Experiments on benchmark homophilic and heterophilic datasets show that the proposed method is compatible with state-of-the-art GNN variants, achieving competitive or superior performance on the node classification task, and providing well-calibrated predictions.

Published in Transactions on Machine Learning Research (07/2025)
Bayesian Neighborhood Adaptation for Graph Neural Net- works
Paribesh Regmi
pr8537@rit.ed edu
Golisano College of Computing and Information Science Rochester Institute of Technology
Rui Li
rikis Srit. edu
Golisano College of Compuling and Information Science Rochester Institute of Technology
Kishan KC
dkshan@umazon.
Amazon.com com, Inc.
Reviewed on OpenReview: https: // openreview. net/ forum? id= 2zEemRi b3a
Abstract
The neighborhood scope (i.e., number hops) where graph neural networks (GNNs) ag- gregate information to characterize a node's statistical property is critical to GNNs' perfor- mance. Two-stage approaches, training and validating GNNs for every pre-specified neigh- borhood scope to search for the best setting, time-consuming task and tends to be biased due to the search space design. How to adaptively determine proper neighborhood scopes for the aggregation process for both homophilic and heterophilic graphs remains largely unexplored. We thus propose to model the GNNs message passing behavior on a graph as a stochastic process by treating the number of hops as a beta process. This Bayesian framework allows us to infer the most plausible neighborhood scope for message aggregation simultaneously with the optimization of GNN parameters. Our theoretical analysis shows that the scope inference improves the expressivity of GNN, Experiments on benchmark homophilic and heterophilic datascts show that the proposed method is compatible with state-of-the-arl GNN variants, achieving competitive superior performance on the node classification task, and providing well-calibrated predictions.
message-pasingg
1 Introduction
Graph neural networks (GNNs) (Kipf & Welling 2016 and its variants have shown success modeling graph-structured data arising in various fields, such as computational biology (Huang al. 2020 Kishan et al. 2021), social information analysis (Li & Goldwasser 2019 Qiu et al. 2018), recommender systems (Ying et al. 2018), etc. Due to the locality assumption, multiple GNN layers needed be stacked up in the network structures in order to expand the neighborhood scope for message aggregation. Substantial rescarch efforts focus on enhancing the aggregation schemes for homophilic and heterophilic graphs, resulting in GNN
variants showing significant performance improvements [Xu et al. 2018 Veličković et al.) 2017 Rong et al.
2020 Chen et al.) 2020 Chien et al. 2021 Luan et al.) 2022 Zeng et al. 2021). Although the neighborhood
scope where GNNs aggregate information is also vital to their performance, the state-of-ther the-art GNN variants still rely on traditional two-stage approaches scarch for the best sctting. Since these empirical approaches involve training and validating GNN models for each single candidate configuration of neighborhood scope, it is daunting task and tend to be biased. Moreover, since the validation error is noisy quantity, it is necessary to devote large quantities of data to the validation set to obtain a reasonable signal-to-noie noise ratio,
* *Corresponding author

---

Published in Transactions on Machine Learning Research (07 (225)
Feature Sampling
1
T
Number of hops
Illustration of our proposed neighborhood adaptation strategy. Left: The feature of a given node (black-colored) is generated by aggregating messages from neighbors located multiple hops away. The direction of message passing indicated by arrows. The nodes each hop are assigned a contribution probability (m)) indicating their contribution in aggregation (color-coded). Right: Visualizing stick-breaking construction of a beta process. The sticks top random draws from beta process, representing the probabilities over the number of hops. The bottom shows the conjugate Bernoulli process over node feature dimensions. Filled circles (bluc) indicate a random draw of confirming the sclection of a particular feature.
Figure 1:
Recent research efforts mainly focus on designing aggregation schemes for effective message passing to improve GNNs performance. Regularization--asse
methods (Rong et al. 2020 Hasanzadeh et al. 2020), introduce
regularization techniques that randomly drop edges neural connections between layers during training.
Connection- based methods (Xu et al.) 2018 Chen et al. 2020) incorporate additional residual connections
between GNN layers. Another group of methods MAbu-FI-Haijj et al.) 2019 Wu et al. 2019 aggregate messages from multiple hops in a single neural layer by using higher powers of the adjacency matrix. GAT (Velččković et al. 2017) enables the prioritization of specific nodes during message aggregation in a pre- specified neighborhood scope. The performance of some approaches rely on an implicit assumption of graph homophily (McPherson et al. 2001] (L.e,, nodes belonging to the same class tend to form edges) and they may not perform well on heterophilic graphs (i.e., nodes with distinct features are more likely connected) ZZuu
et al. 2020 Liu et al.) 2021). Aggregation schemns (Chien et al., 2021 Luan et al. 2022 Zhu et al. 2020
tailored for heterophilic settings allow GNN variants to achieve state-of the-art performance. Besides effective aggregation schomes, proper neighborhood scopes for message passing is also critical for GNNs' superior performance (Huang el al., 2020: Abu-FElHaaja el al.) 2019: Perozzi el. al. 2014).. Small neighborhood scopes limit GNNs at capturing long-range information in the graph, whereas overly large neighborhood scopes tend to degrade model expressivity and incur expensive computation. It remains open question how to automatically determine proper neighborhood scope for both homophilic and heterophilic graphs without numerous rounds of training and validating different GNN candidate structures.
To address this challenge, we propose neighborhood scope adaptation strategy based on non-parametric Bayesian inference. This general framework allows us to infer the most plausible neighborhood scope for message aggregation simultancously with learning node representations. Specifically, we model the expansion of the neighborhood as stochastic process by defining a beta process prior over the number of hops. The beta process induces a probability for the neighboring nodes in each hop to quantify their contribution to the aggregation. Based on the hop-wise probabilities, by masking them with binary vector generated from conjugate Bernoulli process. Such strategy further prioritizes the nodes' contribution within the neighborhood scope, leading to customized message aggregation. To assess the effectiveness of our proposed framework, we showcase its versatility on state-of of art GCN variants and demonstrate its ability to boost their performance on both homophilic and heterophilic datascts. We also provide theoretical and empirical analysis of its ability to improve expressivity in deep network structures. Moreover, our framework leads to well-calibrated predictions via reliable uncertainty
randomly sample fraction of the node features
2

---

Published in Transactions on Machine Learning Research (07/)025)
estimation. We also demonstrate that our method can successfully infer the L3 path (ováács et al. 2019 of real-world biomolecular network.
Our contributions are as follows: i) We propose a general Bayesian inference strategy that automatically determines neighborhood scopes for message passing. ii) We introduce an efficient stochastic variational ap- proximation to simultaneously infer neighborhood scopes and learn node representations. iii) Our theoretical and empirical analyses show that our framework can enhance GNNs' expressivity. iv) We demonstrate the adaptive neighborhood scope inference boosts statc-of-the-art GNN performance on node classification task for both homophilic and heterophilic graphs.
2 Preliminaries and Related Works
We denote a graph with 9 with vertices (nodes), edges, and node features denoted by (),, The adjacency matrix with added self-connectonns is denoted by A E R|V| and À is it's normalized form. H denotes the d hidden layer in a neural network (Ho = X), with Wz being its parameters. GCN (Kipf & Welling 2016) proposed a neural network with graph convoluutn layers. GNN with a single hidden layer is represented as:
Y= A (AX..)
where a is the activation function. Multiplication by adjacency matrix À denotes message aggregation from the immediate neighborhood. Equ. (1] highlights that stacking multiple layers in GNN model involves repeated multiplication with A, expanding the neighborhood scope with each additional layer. Therefore, specifying the number of layers implicitly assumes the locality i.c. it incorporates hhp neighbors for message aggregation when the network consists of I layers. Subsequent research has aimed to improve upon this basic aggregation scheme, as outlined below.
2.1 Message Aggregation Schemes
Dropedge [Rog et al., 2020 proposes to randomly drop a fraction of the edges and train GNNs with the resulting sparse graph to reduce noise in the graph structure. Residual connections between layers are employed to enhance GNN models' performance while preserving locality. JKNet (Xu et al. 2018) aggregates the information from all hidden layers before feeding it into the output layer. Such aggregation helps maintain the local information of each layer when propagating towards the output layer. PPNP (Gasteiger el al.,
2019)
proposes a message aggregation scheme based on the personalized PageRank algorithm (Page et al. 1998)
allowing messago passing from larger neighborhood. GCNII (Chen et al. 2020) extends GCNs with an initial residual connection and identity mapping, resulting in stable and better performance with deeper structures. In addition, utilizing higher powers of the adjacency matrix for aggregation from broader neighborhoods is also an effective strategy. The GNN variant proposed in (Wu et al. 2019) widens the scope from immediate neighbors the ones lying multiple hops away in a single layer and effectively expand the neighborhood scope for aggregation. Mixhop, (Abu-al-Haija et al. 2019), employs multiple heads in a single layer to aggregate and combine messages from neighbors lying at higher hops. Co-GNN Finkelshtein et al. (2024) proposes a flexible message passing approach where each nodes can determine how the message is propagated to and from its neighbors. At each layer, the message passing behavior of each nodes can change, which results in dynamic, task-aware computational graph that is different at each layer. D2GCN Duan et al. (2022) incorporates a subset of non-neighboring nodes as negative samples during message passing and learns the central node's representation to deviate away from the nodes. The extends the message passing scheme to non-neighboring nodes well. LDGCN Duan et al. (024) proposes diverse negative sampling that improves on D2GCN by reducing the redundancy of negative samples at cach layer, which is also shown to improve the expressivily of GCNs. All these methods lack an automatic mechanism to determine the appropriate neighborhood scope from the imput graph. Attention- based methods like GAT (Veličković et al. 2017) learn odgo-specific attention weights to prioritize certain neighbors during message aggregation. However, this prioritization limited to a fixed neighborhood scope determined by the number of layers. Reinforcement learning approaches such Policy-GNN Lai et al. (2020) adaptively select the number of hops for each
3

---

Published in Transactions on Machine Learning Research (07/2025)
node using deep Q-network, but this requires training an additional network. Furthermore, the maximum aggregation range (K) must still be predefined, and the adaptivity is confined within this range. In contrast, our method requires no auxiliary network and imposes no fixed upper limit on the neighborhood scope, allowing information to propagate thcoretically up to an infinite range.
2.2
Aggregation Schemes for Heterophilic Graphs
Some aggregation approaches assume graph homophily and perform poorly on heterophilic graphs Pei el al. 2020 Bojchevski et al. 2020 2019). Since the connected nodes often exhibit siguificantly different properties in heterophilic graphs, a new design of effective message aggregation becomes necessary (Jia & Benson 2020). To address this challenge, H₂GCN (Zhu et al. 2020) proposes ego embedding and higher order neighborhood aggregation, allowing for significant performance improvements on heterophílic graphs. GPR- GNN (Chien et al. ) associates message aggregation in each step with a learnable weight, allowing it to adapt to the homophily or heterophily structure of the input graph. ACM-GCN (Luan et al. 2022) proposes adaptive channel mixing and achieves slate-of-the-art results on benchmark heterophilic datasets. However, all these methods rely on pre-specified neighborhood scope prior to training (the number of propagation steps in H₂GCN and GPR-GNN or the number of graph convolutional layers in ACM-GCN) the input graph. Moreover, while all the mentioned methods are
2.3 Bayesian Methods for GNNs
Bayesian approaches have been applied to graph modeling, offering key advantages such as strong per- formance with limited labeled data, robustness to adversarial perturbations, and reliable uncertainty cal- ibration. These are helpful in scenarios such safety-critica systems, few-shot learning, and adversarial settings, where improved robustness and reliable uncertainty estimation can lead to more reliable and cau- tious decision-making. A set of Bayesian approaches define a prior over the properties of the input graph, such as node features, structure, and labels, and perform joint inference to predict the labels of missing nodes in an unsupervised setting. Bayesian-GGNN alization from a parametric family of random graphs and performs inference of the joint posterior of the random graph parameters and the node labels. G (Ma et al. 2019) defines a random graph model where the distribution of random graphs also depends the node features and labels, capturing their interactions for more ficxible modeling, and infers missing labels in a semi-supervised learning setting. VGCN (Elinas) et al. 2020) defines a probability distribution over the adjacency matrix to capture the topological structures of input graphs, enhancing model performance under adversarial perturbations of the input graph structure. Another approach, BBGDC (Hasanzadeh et al.] 2020), which models both graph properties (edges) and GCN properties (convolutional channels) using a Bernoulli process. Both DropEdge and dropout (Srivas- fava et al.) 2014 can be viewed as special cases of BBGDC. All these methods suffer from the limitation of relying on GCN with predefined neighborhood scope. Our method differs fundamentally from these approaches. While they define priors and conduct inference over the properlies of input graphs, such features, structure, and labels, we propose a general neighborhood scope inference strategy by defining a prior over neighborhood hops as and automatically inforring the neighborhood scope simultancously with learning network parameters. Furthermore, the priors used in these approaches to model graph properties are not suitable for modeling the neighborhood scope of a GCN. This calls for a novel treatment of the scope, which we achieve through a stick- brekkin construction of the beta process.
(Zhang et al. 2019) considers the input graph as a specific re-
3 Bayesian Neighborhood Adaptation for GNNs
Given the importance of determining appropriate neighborhood scope for message aggregation, we proposc a framework in which the model jointly learns the relevant neighborhood scope with the node representations. Specifically, we aim to learn discrete hop-level values that quantify the influence of neighbors at varying distances from a central node. Morcover, motivated by the robustness and reliable uncertainty calibration offered by Bayesian methods in graph learning (Elinas et al., 2020 Zhang et al. 2019 Hasanzadeh et al., 2020) (as discussed in Section 2.3h. we adopt Bayesian approach to infer the number of hops used for
4

---

Published in Transactions on Machine Learning Research (07/2025)
message aggregation. In the following sections, we discuss the construction of the prior, define the likelihood model, and the posterior inference of our proposed Bayesian neighborhood adaptation framework.
3.1 Beta Process Prior over Infinite Neighborhood Scopes
We model the number of hops for message aggregation as a beta process (Paisley et al. 2010 Broderick ct al., 2012). Beta process is a completely random measure defined over discrete indices that assigns each hop a contribution probability independently ranging from 0 1. Unlike other stochastie processes such the Dirichlet or Pitman- Yor processes, which constrain probabilities to sum to one, the Beta process provides greater flexibility, making it a natural prior for our purpose. Specifically, we utilize stick-breaking construction of the beta process as follows:
U5: in Beta(a, (3)
(2)
where ii are sequentially drawn from a beta distribution. Additionally, x denotes the contribution probabil- ity assigned to neighbors at the I-th hop level. Theoretically, the process assigns a probability to neighbors at infinite hop levels, potentially enabling message aggregation from an infinite scope, as demonstrated Figure [ π can be interpreted as the contribution of nodes lying at the 1-th hop during message aggregation. To sample features from nodes the I-th hop, we introduce Bernoulli variable zot Bernoulli (m). Thus, if Sot 1, it indicates that the o-th feature of node at the I-hop level will be included for message aggre- gation. This mechanism selectively retains features from each hop based on mi, allowing hops with higher contribution probabilities to have a stronger influence during aggregation, while those with lower probabili- ties contribute less, reflecting their weaker presence. We thus perform joint inference over the contribution probabilities of hops with a beta process and feature sampling using its conjugate Bernoulli process (KC Thapa & Li 2024 by formulating the prior over Z as:
ct al. 2021 Regmi & Li 2023
p(Z, vl,, 9)p(Z)) = Beta( in a. B) II [ernouli(zaa] (T))
(3)
where and 3 are hyperparameters. Specifically, large and small 3 encourage aggregation from broader neighborhood. Given the prior, next, we define a likelihood model.
3.2 GNN models as a Likelihood
As a likelihood model, we use a GNN backbone, in which we incorporate the feature sampling mechanism. Specifically, since GNNs aggregate messages from 1-th hop neighbors at the I-th layer, we sample features of node the (-th hop level by multiplying the output from the (-th layer with the binary mask z₁. Following this framework, GNN layer is specified as:
H; = (AH, Wi) X 2i + H 1 (1,
(4)
where W, E gxx denotes the weight matrix of layer I, is the dimensionality of the feature vector (i.e. the number of neurons in hidden layer), and o is the activation function. The output of layer is multiplied element-wisely by a binary vector z; where its element Fn E 10, The residual connections feed the outputs from the last activated GNN layer to the output layer. What's more, they also improve GNNs' performance with deep structures Kipf & Welling 2016).
Let = (X, YJ where Y = {vv} denoting the node labels a graph & with feature matrix X. For the node classification task, we express the likelihood as:
M
PD
II
plun {w), Y= f(H))
(5)
5

---

Published in Transactions on Machine Learning Research (07 (07/2025)
where f()) denotes the output layer with softmax activation and Y = {8n} is the estimated outputs. Z is binary matrix whose 1-th column is 2t, W denotes the set of weight matrices, and H,, is the output from the last activated layer. The marginal likelihood obtained by marginalizing out Z in the product of Equ. (3)
and Equ. 5 is:
p(D W. a, PPII W. uI,,
Given the likelihood and prior, we want to infer the posterior of 2, v. However, due to the non-linearity of GNN the likelihood P W) and - 0o (Eqn. (3), exact computation of the marginal likelihood in Eqn. (6, and thus the posterior is intractable. Therefore, we resort to variational inference to learn an approximate distribution.
3.3 Efficient Variational Approximation
We propose adapt stochastic variational inference (Hoffman al. 2013 Hoffman & Blei
2015
approximate the marginal likelihood. We define variational distribution as follows:
O
-
II Beta(u bi) II ConBer(zalmi)
(7)
where, T is truncation level that denotes the maximum number of layers for the variational distribution, ConBer(=ad mi denotes concrete Bernoulli distribution (Maddison et al. 2016 Jang et al.) 2016). The concrete Bernoulli presents a continuous relaxation of the binary variables generated from the Bernoulli process. This relaxation allows optimization through gradient descent, which was not possible with the binary variables The neighborhood scope is defined as the index of the deepest activated layer ie. layer with least one activated neuron. Formally, the neighborhood scope mns is the maximum value of such that Ee Pnl 0.
The lower bound for the log marginal likelihood in Eqn. 6 (ELBO) is: logp(D|W, G, a, B) 2 (, p w) -
(8)
Equ. is the optimization objective for our proposed framework. The first term in the right-hand side fits the model to the data and the rest two terms regularization derived from the prior. The expectation is estimated with Monte Carlo sampling. The algorithm and diagram of our method are provided in Appendix
D and respectively.
4 Expressivity Analysis
For case of notation, we use N to denote the number of nodes the graph (N M)). For a symmetric adjacency matrix A, the eigenvectors are perpendicular. Lel A AN are the eigenvalues of A sorted in ascending order, and let the multiplicity of largest eigenvalue dy is M ie A1 ....AN-M <NNM441 = AN. We also assume that the adjacency matrix is normalized and possesses positive cigenvalues, with the maximum eigenvalue capped at 1.
Let, {Em)m=A (em))=N--+LL.... MN = 1, and (em)m=I....N..)
the orthonormal basis the subspace U corresponding to the eigenvalues the orthonormal basis for U+ Consequently, H E Nxo
(AmIn=- Nolmm=N-M+H,... MM+1...... can be expressed as H = Σ Cm & Wm where E T
Theorem OOoo & Suzuki, 2019) Let (H) denote the perpendicular distance between the representa- tions and the subspace U, then the output representations from I layer (H2) in a GCN exponentially converges to the subspuce U.
(M S A dM(H) = min
- PI|
(9)
PEU
==
me(....,N.... M) Am
Details the Bernoulli distribution is provided in Appendix

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Epoch: 10
Epoch: 50
Epoch: 100
Epoch: 300
1
1
Number hops
Number of hops
Number of hops
Number of hops
Figure 3: Evolution of neighborhood scope and contribution probabilities over the number of epochs for the Pubmed dataset when trained with our method. The contribution probabilities and hence the neighbor- hood scope increases as the training progresses and settles to an optimal value.
The convergence of H2 to lower dimensional subspace in Theorem 1 shows that the expressivity of a GCN exponentially decrcases with an increase in the number of layers. This leads to information loss since nodes that lie within the same connected component lend to share identical features, making them indistinguishable.
In our analysis, we measure the convergence in terms of the angular region (0) spanned by H around U shown in Figure 2 A low value of 0 is indicative of feature vector collapsing onto the lower-dimensional subspace U, resulting in decreased expressivity. Conversely, a high value of 0 indicates that the feature representations span a broader angular region around U. The findings in (Kipf & Welling 2016) indicate that incorporating residual connections in a GCN (ResGCN) yiclds improved performance with deoper structure compared to a vanilla GCN. We will theoretically analyze ResGCN and show that the addition of residual connection widens the angular region Moreover, we observe that even in ResGCN, the region becomes more confined the number of layers increases. Our proposed framework addresses this issue and maintains wider region even with deeper layers by automatically inferring the relevant neighborhood scope. If 02 is the angle spanned by Hg with the subspace U,
U
dy (HL)
tan 0₂
P arg min
H
-P|,
dd((H)
0
PL
PEU
(10)
0 (Rua
dm (HL)
0r tan
0
Pr
U
(11)
A network with residual connections between each layer (ResGCN) represented as:
Figure 2: (left) Illustaaioon of the convergence fea- lure vector H in the subspace U. and d (H) are the projection and the perpendicular distance of H from the subspace respectively. 0 is the size of the angular region spanned by H around U. (right) Visualization of the angular regions spanned by vanilla GCN (grey), ResGON (blue), and BNA-GCN (purple) around the subspace U (denoted by the dark line).
H (ess) (REH) + H (Res)
(12)
Lemma 1 If (es)) is the angle spanned by H; (Res)
with the subspace U, then ((Res) 2 0r
Corollary 1 The angular region narrows down with increase in layers La (Res)
0f (Ree)
Proofs of the Lemma 1 and Corollary are provided in Appendix B and B.1 respectively. The lemma suggests that ResGON has better expressivity than a vanilla GCN with representations covering a wider angular region. However, Corollary suggests that with the increase in layers in ResGCN, the features H (Res) increasingly collapse into the subspace U.
Next, analyze the impact of the application of our neighborhood inference framework in GCN.

---

Published in Transactions on Machine Learning Research (07 (225))
Table Node classification performance of the GNN variants on homophilic (Cora, Citeseer, Pubmed) and heterophilic (Chamelcon, Cornell, Texas, Wisconsin) graphs. The reported metric is averaged accuracy with + one standard deviation. The best result for each graph is highlighted in bold, while the second-best result is underlined. (OOM indicates Out Of Memory)
Baselines
Citessor
Pubmed
Chameloon
Cornell
Wisconsin
GCN
85.35
77.37
77.30:10.20
55.84.16.00
80.82.13.60
73.11:122.46
60.38.113.88
ReaGCN
86.15=0.15
78.15#0.30
77. 66:00.81
66.01422.08
80.82::3 60
80.82=3.60
62. 02.75:66.66
BBGDC
86.80=0.10
77.2540.32
OOM
55.7111.86
79.3415.500
d:
Ours+ ResGCN
86.83=0.13
77.90-10.37
78.20:10.29
64.25-12.30
80.82:1:3.00
78.20=4.15
66.13:15.35
JKNet
86.20=0.10
07.6820.35
07.25:00.23
52.43:22.84
74.43:18.38
70.00=5.49
62 13:16.200
JKKet
86.40
78.20.10.65
0..1
63.85122.04
77.70.14.10
78.52.16.24
67.38.14.82
GAT
86.43=0.40
77.76#0.21
76.78=0.63
63.9020.
76.00==1.01
78,87=0.86
71:01=41.66
Ours+-GAT
86.70=0.40
0..32-00.3
77.4710.19
65.32412.61
79. 3..13433336
75.08:17.10
73. 73.121:3.41
GONI
87.53+0.30
07.6310.21
79.9610.17
58.9742.76
87. 70:15
76.07=5.35
80.35 30.37:55.86
Oues++GCNII
87.26:0025
78.36:10.c0 0.66
78.6 0.0600
57 57.44413335
87.87
2.54
90.75-13.12
GPR-GCN
67. 40
91. 3633600000 70
92.92=0.61
93 73.7722..7
4CM-GCN
85.63-0.13
0..20:10.29
75.73110.40
74.62= 1.79
92.46:12.34
91.80=4.21
94.87+12.20
+CC
84.76=0.76
0..3310.33
74.33:00.82
74.38:11..9
93.61:2.13
94.10:13.55
95.7511..9
Theorem With the application of the Bayesian Neighborhood Adaplation (BNA) framework, if (BBN)) is the angle spanmed with the subspace U, then 0f ((BNA) A) 2 0 [esss) Oz.
Corollary 2 Beyond a certain number of layers g the angular region 0 (BNA) remains constant even with further increase in the number of layers: ((BNA) o(BNA) for L nns
Proofs of Theorem and Corollary 2 are provided in Appendix aadd C.. respectively. The theorem suggests that the application of the BNA framework further enhances the expressivity of ResGCNs. Importantly, Corollary 2 suggests that by inferring the appropriate neighborhood for message aggregation, the BNA framework avoids feature collapse and prevents information loss in deep GCN. These analysos are illustrated in Figure 2 and empirically validated in Figure
5 Experiments
We present series of experiments to assess the effectiveness of the proposed neighborhood scope inference framework. In section 5.1 we demonstrate the neighborhood scope inference mechanism by showing how the scope of a GNN expands during training. In section 5.2 we then compare the performance of GNN baselines with and without the application of our framework. In section 5.3 we empirically validate the expressivity analysis from section by visualizing the learned node representations GCN and our method. In section 5.4 we assess the effect of our framework on uncertainty calibration by analyzing the uncertainty estimates. We then conduct an ablation study in section 5.5 to assess the contribution of each component. In Section 5.6 evaluate the scalability of our framework to large graph datasets. Section |5.7 provides both theoretical and empirical analysis of the time and space complexity of our method. Lastly, in section 5.8 we present case study on real-world molecular graph dataset to validate the neighborhood scope inference capability of our approach.
5.1 Neighborhood Scope Adaptation
Figure 3 demonstrates the mechanism of neighborhood scope adaptation during training over 300 epochs for the Pubmed dataset. The truncation was set to T 10. During initial phase, the scope is limited to 4 hops, with comparatively less contribution from each hop. As the training progresses, our framework allows the contribution probabilities and hence the neighborhood scope to adapt the input. At 300 epoch, the expansion converges to 6 hops and the contribution probabilities become stable training.
8

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Cora
Citeseer
Texas
80
03
Accuracy (%)
80
80-
Accuracy
Accuracy
NesCCh
55
ReeGCN
ResGCN
DAT
GAT
50
GAT
ACM-GGNN-
ACW-SON-
ACM GON+
Qurt ResSCN
OuSSRRsSGN
OUIS-GAT
Ours GAT
30
Ours GAT
OUIS-ACM GON+
Ours GCN+
65
2
2
2
35
2
L/T
L/T
Figure 4: The impact of increasing the depths (L/T) of GNN variants with and without our framework on their expressivily. Although the depth increase degrades the performance of vanilla ResGCN, GAT, and ACM-GCN, the application of our framework stabilizes their performance for deep network structures.
Cora
Wisconsin
L/T= =4
LTT = 64
L/T=4
L/T = 32
ResGCN
ResGCN
Ours + ResGON
Ours + ResGON
Figure 5: TSNE visualization of the learned node representations by ResGCN with and without our frame- work for shallow (7. = T 4) and deep (T. = = 32/64) structure. The representations of ResGCN converge in narrow, curve-shaped regions for deep structures. This indicates that the representations converge a narrow subspace, which is consistent with Corollary [ Applying framework (bottom row) addresses this issue, resulting in spread-oul representations with deeper network structure. This suggests that the application of our framework enhances the expressivity.
5.2 Performance Comparison on GNN Variants
We evaluate the performance of GNN variants integrated with our framework to determine the optimal neigh- borhood scopes for the task on the homophilic (Cora, Citeseer, Pubmed) (Sen et al. 2008)) and heterophilic (Chameleon, Cornell, Texas, Wisconsin) Pei et al.) 2020 graphs by comparing with the variants.
For homophilic graphs, perform both full-supervised (Cileseer, Cora) and semi-supervised (Pubmed) node classification in Table We integrate our inference framework with vanilla GCN, ResGCN (Kipf & Welling
2016) (GCN with residual skip connections), GAT /Veličković et al.) 2017), JKNet (Xu et al. 2018), GCNIL CCen et al. 2020), and ACM-GCN+ Luan et al., 2022) Additional basclines we use are GPR-GNN Chien al. 2021), and bayesian GCN variant BBGDC (Hasanzadeh et al. 2020). The implementation details are provided in appendix G Table shows that the GNN variants with our framework achieve the best performance on four graph datasets and the second best the remaining three datasets. The results suggest that by jointly inferring neighborhood scope and learning GNN parameters, boost the overall performance of the GNN models.
Integration details provided Appendix F
9

---

Published in Transactions on Machine Learning Research (07 2025))
Table 2: Uncertainty calibration comparison between baseline GNN models, an ensemble of the baseline models, and applying our framework in the bascline modcls. The reported metric is the expected calibration error (ECE 4). The best result is bolded.
Baselines
Cora
Citeseer
Pubmed
Chameleon
Cornell
Texas
Wisconsin
GCN
0.14110.03
0.27:10.03
0.17::0.02
0.11100.03
0.46:10.06
0.49-10.09
0.30:10.11 13
GCN Ensemble
0.02 + 0.01
0.21#0.02
0.04+0.01
0.0420.01
0.51=0.02
0.67#0.02
0.25+ 03
Our3+GNN
0.01+:0.02
0.1240.05
0.08+:0.03
0.05+0.01
0.18+0.05
0.15+0.03
0.13+0005
GCNTT
0.32::0.01
0.39:5.02
0.0440.01
0.0640.01
0.36:0.03
0.1300.03
0.1000.05
GCNII Ensemble
0.32:4:.01
0,3940.01
0.04+0.01
0.03+0.01
0.31+0.01
0.20=0001
0.21+0.02
ACM-GCN+
0.194:0.04
0.2740.03
0.15:0.033
0.0420.01
0.13+00.03
0.09#0.02
0.09
ACM-GCN+ Ensemble
0.17+0000
0,28:0.01
0.16+0.01
0.05+0.01
0.12:0002
0.11#0.03
0.12+ 02
Our++ACM-GGNN
0.091:0.03
0.13+0.02
0.14+0.01
0.0410.01
0.10:0.05
0.07:0.01
0.06:10.01
5.3 Expressivity with Deep GNN Structures
We evaluate the effects of our inference framework the expressivity of GNN variants with increasingly deep structures. We apply dropout regularization to the GNN variants in this analysis. The performance over varying numbers of GNN layers is shown in Figure The results show that the overall performance of ResGCN, GAT, and ACM-GCN+ across the datasets suffer a decline when the network depth L becomes large. However, combining our framework with these GNN models to adapt the neighborhood scopes for the node feature learning, we mitigate the problem as indicated by the solid flat curves, showing the robustness of the performance over the increasing truncation level T.
In Figure 5 assess expressivity by visualizing the node representations learned by ResGCN with and without our framework. The t-SNE embeddings of the representations obtained from the last layer of a shallow network (L = 4) and deep network (L 32/64) are shown for the Cora and Wisconsin datasets The representations generated by ResGCN with shallow networks are well-separated into clusters and are spread-out in the latent feature space. However, For deep ResGCN, the cluster separation becomes less distinct, and the representations collapse into a curved-shaped region. This consistent with Corollary
The application of our framework (bottom row) results in comparatively spread-out representations for shallow structure (T/L- 4), which is in accordance with Theorem 2 However, the representations remain spread-out even for deep structures, indicating improved expressivity suggested by Corollary 2 This can be attributed to the property of our framework that decouples the neighborhood scope from the truncation level (i.e., a pre-specified network depth) and allows the ResGCN network depth to adapt as it learns node representations.
5.4 Uncertainty Quantification
We assess the uncertainty estimates of GNN variants, their combinations with our framework, and GNN deep assembles. The baselines include the vanilla GCN and the two best performers from Table ! namely GCNIT and ACM-GCN+. The ensemble of the baseline models consists of 10 models trained with differ- ent initializations. The metric for assessing uncertainty expected calibration error (ECE) (Guo et al., 2017 [ Table 2 shows that. compared to the baseline GNN models, integrating our framework improves their uncertainty quantification both homophilic and heterophilic datasets in most cases. By quantifying the uncertainty of adaptive neighborhood scopes in training via Bayesian inference, our approach enhances uncertainty calibration in four cases and delivers comparable results in the remaining three, compared to the GNN deep ensemble.
5.5 Ablation Study
We analyze the contribution of different modeling components of our framework on GCNs. ResGCN is the GCN with residual connections between successive layers. The results in Table B show that residual connce- tions is an effective technique, and with dropout regularization (do) for feature sampling ResGCN improve
More detailed expressivity assessments along with overfitting analysis are Appendix Analysis using PAuSPU metric Appendix
respectively.
10

---

Published in Transactions on Machine Learning Research (07 (07))
Table 3: Ablation study of our online inference framework for neighborhood scope adaptation.
Dataset
Cora
Citeseer
Pubmed
GCN
85.00:10.10 10
77.23=0.17
77. 77.00+0.50
ResGCN
86. 06.16
77.26=0.10
76.66++0.33
ResGCN+do
86.15+0.15
78.15=t0.30
77.66+0.84
GCN
86.83 0.13
77.90-0.37
78.20 0.29
the GCN's performance and achieve the best on Citeseer. Furthermore, by adapting the neighborhood scope with beta process, our framework achieves the overall best performance.
Table 4: Performance of baselines and our method large graph datasets. The metric reported are percentage accuracy for Flickr & ogb-arxiv, and AU-ROC for ogb-proteins. The best result is highlighted in bold and the second-best. is underlined. The last column shows the GPU memory usage for one epoch (in Gigabytes) while training the baselines and our method (S 3) on the ogb-protein dataset.
Datasel GCN
Flickr
ogb-arxiv
ogb-proteins
Memory (ogb-proteins)
11.44
71.744:0.29
0.7251+:0.0022
9.19
ResGCN
51.38:10.11
02.8610.116
0.7343=10.011
9.88
Ours ResGCN
51.73++0.21
72.79+0030
0.7572=00.004
10.06
JKNet
52.56=0.12
72.19:0.21
0.6966::000022
10.14
Ours + JKNet
52.2410.28
72.8840.09
0.7330=10.006$
10.41
GCNII
51.5310.16
72.7410.16
0.741410.0070
9.91
Ours + GCNII
51.48:0.11
73.06=0.40
0.7513=0.0054
10.07
5.6 Performance on Large Datasets
We evaluate baselines and our method on three large datasets: Flickr, ogb-arxiv on multi-class classifica- tion, and ogb-proteins on binary classification. The reported metrics are percentage accuracy for multi- class classífication and AU-ROC for binary classifi- cation settings. Table g demonstrates that applying our framework to the baselines results in compara- ble or significantly better performance, showing that the performance of our framework scales effectively to large datasets.
A
L3 path
X
B
likely
interaction
5.7 Training
Time and Space Complexity Evaluation
For a constant maximum layer width, the time com- plexity of training a GNN model with depth is O, = (LL [V]. Let S denote the number of Monte Carlo samples, our method is linearly scal- able as SO,, The space complexity of training the GNN model is C(D)22 + L(V)). For our method, the space complexity is 0 + SL/V)-
Figure 6: simplified illustration a Protein-Protein Interaction (PPI) network. Kovács et al.] (2019) pro- vide evidence that proteins that are connected by mul- tiple L3 paths (i.e. 3-hope apart) & Y in the día- gram) more likely to interact than others, high- lighting the importance of aggregating messages from three-hop neighbors when learning node representa- tions.
We report the training times of the GNN variants combining with our framework in Table 5 For the inference neighborhood scopes, the number of samples of Z is set to S 5. The results align with
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
complexity analysis, showing that the training time of our method scales linearly with the number of samples. The convergence of our method with respect to the varying number of samples S is discussed in Appendix D which also provides an overview of the trade-off between the increased complexity of our method (brought by a higher value of 5) and the performance. Compared to the basclincs, although our method takes extra time for the joint inference training to infer the best settings of neighborhood scopes, this is justified by the overall performance improvement over the basclines, improved expressivity of baseline GNN, improved uncertainty calibration, and mitigation of overfitting in the baselines (Appendix H
In the last column of Table | report the GPU memory usage when training the baseline models with and without our framework on the ogb-proteins dataset. The results demonstrate that integrating our framework introduces no significant increase in memory usage. This aligns with our complexity analysis, which shows that for larger graphs (i.e., large [V]), the first term in the space complexity O(IV2 + SL(VI) dominates, while the second term contributes minimally to the overall memory load. Since the first term is the same for both the basclines and our approach, memory consumption remains effectively unchanged.
Table 5: Training times (in seconds) of GNN variants with and without our framework for 100 epochs. The number of samples for our method is set to S = 5.
Dataset
Cora
Citeseer
Flickr
ogb-arxiv
ResGCN
0.35
0.37
2.30
5.60
Ours + GCN
1.14
1.30
10.12
29.20
GCNII
0.60
0.62
2.84
6.65
Ours + GCNIT
1.21
1.18
11.64
31.60
5.8 Neighborhood Scope Adaptation on Biomolecular Network
As a case study, we evaluate our model on real-world biomolccular graph dataset. Specifically, we apply it to the link prediction lask in the Protein-Protein Interaction (PPI) dataset. In this graph, nodes represent pro- tein molecules, and edges denote interactions between them. Kovács et al. (019) provide evidence that pro- teins that are three hops spart (i.e. that are connected by L3 paths) are likely to interact as shown Figure
This suggests that, in PPI graphs, aggregating mes- sages from 3-hop neighbors is essential for effective reprosentation lcarning. To validate the neighbor- hood scope inference capability of our method in this domain-specific setting, we assess whether it aligns with the findings of Kovács et al. (2019). Specifi- cally, we evaluate whether our Tramework can infer a neighborhood scope that enables message passing between nodes 3 hops apart.
L3 scope
0.7
0.5
0.3
02-
Given an interaction graph with fraction of miss- ing positive interactions, the goal is to predict these missing links. For experimental evaluation, we ran- domly split the interactions into training (70%), val- idation (10%), and testing (20%) sets. Since the dataset contains only positive interactions, we gen- erate negative samples by randomly selecting node pairs that lack observed edge, assuming these represent non-interacting proteins.
0.0
Figure 7: Contribution probabilities learned by our method for the PPI network. The shaded region (L.3 scope) corresponds to the neighborhood scope encom- passing L3 neighbors. The activation probabilities drop below 0.1 from the fourth hop, showing that the effective neighborhood scope in 3 hops. The neighbor- hood scope inferred from our method aligns with the findings in Kovács et. al.) (2019), which suggests that proteins lying 3-hops away are likely to interact.
We train a (GNN) to learn node representations and an interaction between the nodes are presented basod on the similarity of representations. The AU- ROC and AUPRC scores for ResGCN and Ours + ResGCN the link prediction task (0.907 +
12

---

Published in Transactions on Machine Learning Research (07 (075)
0.006, 0.894 0.002) and (0.918 = 0.002, 0.907 = 0.003), respectively. The learned contribution probabili- ties are visualized in Figure i The contribution probabilities drop below 0.1 starting from the fourth hop, indicating that effective message aggregation occurs from nodes within the 3-hop range. This suggests that the inferred neighborhood scope allows the interaction with the neighbors 3-hops away, aligning with the findings in Kováes et al. 2019h.
6 Discussion and Conclusion
We propose general automatic neighborhood scope adaption method compatible with various GNN models and boosting the overall performance and uncertainty estimation. We show that the application of our framework improves the expressivity with deep network structures. Furthermore, we demonstrated the neighborhood scope inference capability of our method on a real-world PPI network. Our future work entails adopting our neighborhood adaptation strategy for more complex GNN architectures, such as graph transformer networks (Yun et al., 2019). Another future direction relaxing the finite truncation constraint in the variational distributions by incorporating the Russian roulette method [uu et al. 2019
Broader Impact Statement
This work advances Graph Neural Networks, a machine learning model. All datasets used in the paper are publicly available and the experiments do not involve human subjects. The work has no specific societal impact beyond the ones that come with developing a machine learning model.
Acknowledgement
This work is supported by the National Science Foundation under NSF Award No. 2045804 and the National Institute of General Medical Sciences of the National Institutes of Health under Award No. R35GM156633, We acknowledge Research Computing at the Rochester Institute of Technology (RC) for providing compu- tational resources.
References
ShadowwKHppammler.. https://docs..dl.. agl
Research computing at rochester institute of technology. httpps//bbb.or////37778////56-
Sami Abu-El-Haijpa Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun- yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), pp. 21 29. PMLR, 2019.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Martin Blais, Amol Kapoor, Michal Lukasik, and Stophan Günnemann. Is pagerank all you neod for scalable graph neural networks. In ACM KDD, MLG Workshop, 2019.
Aleksandar Bojehevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózem- berczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Dala Mining, pp. 2464 2473, 2020.
Tamara Broderick, Michael Jordan, and Jim Pitman. Beta processes, stick-breaking and power laws. Boyesian Analysis, 7(2):439 476, Jun 2012. ISSN 1936-0975. doi: 10.1214/12 ba715. URL http://dx. doi. orooorg/1111 10. 12-111
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning (ICML,), pp. 1725-1733 PMLR, 2020.
13

---

Published in Transactions on Machine Learning Research (07/2025)
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL https:
//openreview.net// wwt..e//oorummmddoooflllll..
Wei Duan, Junyu Xuan, Maoying Qiao, and Jie Lu. Learning from the dark: boosting graph convolu- tional neural networks with diverse negative samples. In Proceedings of the AAAI conference on artificial intelligence, 2022.
Wei Duan, Jie Lu, Yu Guang Wang, and Junyu Xuan. Layer-diverse negative sampling for graph neural networks. Transactions on Machine Learning Research, 2024.
Pantelis Elinas, Edwin V Bonilla, and Louis Tiao. Variational inference for graph convolutional networks in the absence of graph data and adversarial settings. In Advances in neural information processing systems, volume 33, pp. 18648-18660, 2020.
Ben Finkelshtein, Xingyue Huang, Michael M. Bronstein, and Ismail Ilkan Ceylan. Cooperative graph neural networks. In Proceedings of the 41st International Conference on Machine Learning, 2024.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph
neural networks meet personalized pagerank. In International Conference Learning Representations, 2019.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pp. 1321-1330. PMLR, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. In International Conference on Machine Learning (ICML), pp. 4094-4104. PMLR, 2020.
Matthew Hoffman and David Blei. Stochastic structured variational inference. In Proc. of the Artificial Intelligence and Slatistics (AISTATS), pp. 361-369, 2015.
Matthew D Hoffman, David M Blei, Chong Wang, and John Paisley. Stochastic variational inference. The Journal of Machine Learning Research, 14(1):1303-1344 2013.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datascts for machine learning on graphs. arXiv preprint arXiv:2005.0063 2020.
Kexin Huang, Cao Xiao, Lueas M Glass, Marinka Zitnik, and Jimeng Sun. Skipgnn: predicting molecular interactions with skip-graph networks. Scientific Reports, 10(1):1-16, 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint 3xXiv:1611.01144 2016.
Junteng Jia and Austion Benson. Residual correlation graph neural net work regression. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 588 598, 2020.
Kishan KC, Rui Li, and Mohammad Mahdi Gilany. Joint inference for neural network depth and dropout regularization. In Advances in Nearal Information Processing Systems (NeurIPS), 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint ar arXiv:1600 609.00997, 2016.
KC Kishan, Rui Li, Feng Cui, and Anne Haake. Predicting biomedical interactions with higher-order graph convolutional networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(2):676 (77766777777777 2021.
14

---

Published in Transactions on Machine Learning Research (07 (07/2025)
István A Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dac- Kyum Kim, Nishka Kishore, Tong Hao, et al. Network-based prediction of protein interactions. Nature communications, 10(1):1240, 2019.
Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-gun: Aggregation optimization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 461-471. ACM, 2020. doi: 111144/3394486.4400 URL https:
7/arxiv. org/ abtaa/aas///...//////////////e.a 200020006..11777
Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In Proceedings of the 57th Annual Meeling of the Associalion for Computational Linguistics (ACL), pp. 2594-2000 2604, 2019.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. TEEE transactions on pattern analysis and machine intelligence, 44(12):10270 10276, 2021.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao- Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In Advances in neural in information processing systems, volume 35, pp. 1362 1375, 2022.
Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph-based semi- supervised learning. In Adcances in Neural Information Processing Systems, volume 32, 2019.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The conerete distribution: A continuous relaxation of discrete random variables. arXiv preprint or Xrxi::161 10x:1611.00711 2016.
Miller McPherson, Lynn Smith- Lovin, and James M Cook. Birds of feather: Homophily in social networks.
Annual review of sociology, 27(1):415-444, 2001.
Jishnu Mukhoti and Yarin Gal. Evaluating Bayesian deep learning methods for semantic segmentation. arXiv preprint ar 1811. 12709, 2018.
Kenta Oono and Taiji Suzuki. On asymptotic behaviors of graph cmns from dynamical systems perspective. arXiv preprint XrXiv: 10947, 2019.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. 1998.
John Paisley, Aimee Zaas, Christopher W. Woods, Geoffrey S. Ginsburg, and Lawrence Carin. A stick- breaking construction of the beta process. In Proceedings of the 27th International Conference Machine Learning (ICML), pp. 2902-2911. JMLR. org, 2010.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gon: Geometric graph convolutional networks. arXiv preprint arXiv:2002.052: 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 701-710, 2014.
Jiezhong Qiu, Jian Tang, Hao Ma, Yuxiao Dong, Kuansan Wang, and Jie Tang, Deepinf: Social influence prediction with deep learning. In Proceedings of the 24th ACM SIGKDD international conference. knowledge discovery & data mining, pp. 2110 2119, 2018.
Paribesh Regmi and Rui Li. Adavac: Bayesian structural adaptation for variational autoencoders. In Advances in Neural Information Processing Systems, volume 36, 2023.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks node classification. In International Conference on Learning Representations (ICLR), 2020.
15

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collec- tive classification in network data. AT magazine, 29(3):93 -3.999,,-00 2008.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky; Lyya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15 (1):1929-1958, 2014.
Jeevan Thapa and Rui Li. Bayesian adaptation of network depth and width for continual learning. In Forty-first International Conference on Machine Learning, 2024.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph allention networks. arXiv preprint arXiv:1710. 10903, 2017.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning (ICML), pp. 6861-6871. PMLR, 2019.
Kai Xu, Akash Srivastava, and Charles Sutton. Variational Russian roulette for deep Bayesian nonparamet- rics. In International Conference Machine Learning (ICML), pp. 6963-6972. PMLR, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp.
PMLR, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICML), pp. 40 48. PMLR, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Scongjun Yun, Minbyul Jeong, Rachyun Kim, Jacwoo Kang, and Hyunwoo J Kim. Graph trans- former networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: http::://proceediig neurips. nwwrips.cccpaperr... filess/paerr2219/fiile Paper. Paperodd..ppppp..........
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference Learning Representation (ICLR), 2020.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In Advances in Neural Information Processing Systems (NewrIPS), 2021.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 5829-5836, 5836, 2019.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. Advances neural information processing systems, 33:7793 7804, 2020.
16

---

Published in Transactions on Machine Learning Research (07/202) 2025)
A Appendix
B Proof of Lemma 1
Restating the notations and assumptions the main text, for ease of notation we use N to denote the number nodes in the graph (N = [V). For a symmetric adjacency matrix A, the eigenvectors are perpendicular. Let AI...., AN are the cigenvalues of A sorted in ascending order, and let the multiplicity of largest eigenvalue Ax is M ie À <.... AN-M AN-M+1
Av- We also assume that the adjacency matrix is normalized and possesses positive eigenvalues, with the maximum eigenvalue capped at 1.
Let, Momlm=N-M+1... be the orthonormal basis of the subspace U corresponding the the eigenvalues Ammm=N-M+1.... = 1, and (em (em)m=i....NM. be the orthonormal basis for U-. Consequently, H E RRX be expressed as H Em= Cm @ Wm where Wm E R
The difference between normal multi-layer perception (MLP) layer and GCN layer lies in the multiplication of the layer output with adjacency matrix A. And this repeated multiplication with A at every layer is the cause of the collapse of node features into a subspace (Oono & Suzuki 2019). To analyze how this repeated multiplication affects a GCN with residual connections, in our analysis we simplify a GCN layer to multiplication of features with the adjacency matrix A.
If 0 is the angle made by Hr with subspace U,
tan 0 dm (H,)
(13)
P
0 tan -2 (H)
(14)
P
For ResGCN, a layer is defined as:
H [Rex) ((H (Rea) + H (Res)
H((ess
Representing a layer by its adjacency matrix,
H (Rss)
(Ress)
AH (Res) H
H Res) (A I)H Ras)
2-1
Solving this recurrence, we get:
H Res) (A I H (es)
(15)
Expanding Equ.
15 in terms of {wm}, we get:
H
Ree) Σ
Cm & (Am + 1) um
m=l
(16)
17

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
The distance from the subspace U is:
N-M
l1(Am + wmll
m=1
Σ
[I(1 + Am
(
m=1
N-M
1 )2h (Am) wmll
Σ (1+
(17)
Am
1 - 2. Then,
Since, 0 < Am < (1+
Am
(m(H! 22 (H())
dm(H) 2 dm (Hz)
(18)
Similarly,
N 2 = Σ
11(Am + 1) 11?
m= N M+1
Since, Am 1 for N - M+ m S N,
N Σ
P (p
|12 12 11
m= M+1
22L
Σ
||mml'
m=N M+1
= -2 PL
P Ros)
1 Pr.
(19)
The angular region spanned is:
d (M (Rea)
tan (
Ros)
|P/ (R(ee))
2 (HL)
tan (Res)
>
2 Pal
tan (Rea)
> tan 02
(Rees) > 0z.
(20)
18

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
B.1
Corollary 1
From equation (5)
N-M
LM (REs)) =
1 2 (2(m(((m)) "2
(1
Am
m=1
N-M M
Σ
(1+ (2m) ( wm 12
Am
m=1
E (1
+ 1
) +
1 _ 11( ( wmll
Amm
Am
Σ
(mm +1)2(1
_ )2(2- (Amm) )-- wmll 1?
1
Am
N-M
1 1 )2(1-11) (m wmll? [Since, Am S -1]
Σ 21 +
Am
m=1
2 d (H
(R(a))
dm(H (Res) < 2 d (H R
(21)
The angular region spanned for layers is:
dm (H) L Rea))
tan (
P Ros))
2 dd (H Res)
tan (Rea) Rea)
2
d, (H (Res)
tan 0 Res))
(Rea)
v 24-1 PP
1-
[Sinc, |Pz-1| = PAl
tan 0 (Ree)) < tan 0f f--1
(Res)
< 0 Res))
h-1
(22)
C Proof of Theorem 2
First, prove simple relation. For 0 < À 5
Am +1 T+1
X+1
2
2(A +1) - (A 1)(T +1)
2(A 1)
(1 (1~A)(1- T)
2(A+11 1)
2 0
An +1 1+1
A +1 2
(23)
A layer in BNA-GCN represented
H (BNA) = ((((BN)) (BNA))
@ 2Z + H (BNA)
(24)
19

---

Published in Transactions on Machine Learning Research (07 (07/2025)
Since Z is random variable, we calculate the expectation as:
E E (BNA) = -(HHL @ E[zz] + (BNA) L-1 -((HL (N) TT + H (BNN))
Representing layer by the adjacency matrix, (dropping the expectation notation for convenience).
H (BNA)
AH
L-1 8TL +
(N
H L-1
BNA)
(ATT +1HH (BNA) (PNA)
Solving this recurrence, we get:
(BNA)
II (Am + (BNA) (BNA)
H
1=1
Expanding in terms of Wm, we get:
N-M L Σ
BNA)
II
(mm Ty + 1)wm
m=1
The distance from subspace U is:
I.
d (H
(BNA))
Σ
PmmTI 1)wn 112
E
Σ
(DmiT ग. + 1)
||wmll
Amar + 1
Σ
11(Am +1) wmml?
Xm +
L
NM-
+
11(mm 1) 112
[From Eqn. 23
2
L
1=
(M
+ 1)2
dz (Ress))
22L.
dn(H((NA))
11
(
+ 1).
d (H (Heal)
(25)
24
20

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
Similarly,
N
P L
(2
(A T 1)mm 11
N- M+1
Since, Am
for M M+1smsi
N
L
Σ
II
[ + 1)wml 11
m. N M+1
[ml
N
[ + 1)²
Σ
|wmll 1|
1=1
m=N M+11
(m
+ 1)2
N
Σ
2 2 |
22L
N M+1
L
1= (TI + 1)2
P Ras
221.
PPL (BBBN))
|=1 (TT) + 1)
(26)
24
L
The angular region spanned is:
tan ((BN)) (M(
P(BNA)]
Substituting the values from Equ.
25 and
26 and simplifying
tan (BNA) 2 dm ( (Rea)
tan ((BNA)) > tan ofites)
0 (BNNA) > (ees)
(27)
C.1 Corollary 2
By the definition of 1ss =0 for 1> gss From Eqn. 24
we have:
H
(BNA) { (NA))
8 Zr. + H (BNA)
I.
L-1
For I -= pm + 1,
(BNA)
= J(H(
(BNA)) 3 2(n2 + BNN)
|a+11
(BNA) (BNA)
gax+1
Generalizing the relation:
H (BNA)
(NA)) for 1 > pn H in
Therefore,
0f (BNN)) (BNA) for > ma
21

---

Published in Transactions on Machine Learning Research (07 (07/2025)
D Algorithmic Description
The algorithm of our proposed framework is in Algorithm !
Algorithm 1 Training of our proposed method
Input Graph G, D,S, prior parameters a, S. Initialize Variational parameters {a,, be]
1: Draw 5 samples network structures (2.)-=1 from g(Z, v)
2: for s I,..,, do
3: Compute the neighborhood scope !ns from Z. (see section 3.3).
Compute log ZZ. W. with (ns GNN layers using equation
end for
Compute ELBO using equation
Update {ue, be -andddadd [W] using backpropagation.
E Structural Diagram of the Proposed Framework
L - 00
Z1
Z1
h
GC layer
H
H
GC layer
H
H
hj
g
Figure 8: The block diagram of our proposed model with potentially infinite number of hidden layers in the GCN corresponds to potentially infinite scope for message aggregation. In practice, sufficiently large number of hidden layers is set. The input to the network is graph G with edges & between entities V and feature matrix H. The gray-colored circles are the nodes with known labels and blank circles are the nodes with unknown labels. The feature output from a GC layer is sampled using the binary vector z₁. The model also has residual skip connection between the layers.
F Integrating the Framework With the GCN Variants
To integrate our inference framework vanilla GCN, we multiply the layer output with binary vector z and add a skip connection between the layers:
H; (HH Wi)
2 H 1 (1,2,...0))
(28)
The difference between GCN and GAT lies in the calculation of the atlention coefficient. for message aggre- gation. However, since they share similar network structure, integrating our framework in GAT is straight- forward and is similar GCN. Similarly JKNet and GCN also share similar network structure and hence our framework is integrated in the same way. The aggregation layer in JKNet is kept unchanged while integrating framework.
22

---

Published in Transactions on Machine Learning Research (07/2025)
GCNII had two additional components in the network, the initial residual connection and identity mapping. A GCNIT layer is defined as:
H =o ((1 ((1- AH aH,) ((L (11 +
(29)
where,
3 llggg((//+
We have couple of options to integrate our framework with GCNIL. The first is just incorporating an initial residual connection as follows (used for homophilic datasets):
H (((1- + H, Wi
ZJ
H
(30)
Sccondly, we can also incorporate the identity mapping module as follows (used for heterophilic datascts):
H: -0 (a) az -1- X
Z
(31)
where dg is the teleport probability similar to GCNII, a subsrcript t is introduced to differentiate from the prior parameter a.
G Implementation Details
G.1 Datasets
We use the publicly available datasets for experimentation which includes the three homophilic citation graphs:
Citeseer, Cora Pubmed and four heterophilic graphs: Chameleon, Cornell, Texas, and Wisconsin. The dataset details are in Table The experiments are carried out on NVIDIA A100-PCIE-40GB and NVIDIA RTX A5000 GPUs.
Table 6: Datasel details
Dataset
# #odes
# #Edges
# #Classes
# Features
Cora
2708
5429
7
1433
Citeseer
3327
4732
6
3703
Pubmed
19717
44338
3
500
Chameleon
2277
36101
4
2325
Cornell
183
295
5
1703
Texas
183
309
5
1703
Wisconsin
251
499
5
1703
Flickr
89250
899756
7
500
ogb-arxiv
169343
1166243
40
128
ogb-proteins
132534
39561252
112
G.2 Hyperparameter Details for Table 1
G.2.1 Homophilic Graphs (Citeseer, Cora, Pubmed)
We used the standard fixed split for the homophilic graphs as introduced in (Yang et al. 2016 The general setup for the experiments (unless mentioned otherwise) including the width of hidden layers (O), learning rate (Ir), and activation function (act) are detailed in Table 7 The value dropout and learn- ing rate set as suggested in Kiip & Welling 2016). The hyperparameter search for the layers is done in the range [2, 4, 6, 10). We applied dropedge for the homophilic graphs on the baselines and our method and tuned the dropedge rate over (5,, 10%, 20%, 30%). For JKNet, PoxP is used
23

---

Published in Transactions on Machine Learning Research (07 (025)
aggregator function. In the case of GAT, faced out-of-memory (0OM) error during model train- ing when using the complete graph in single batch. To address this issue, we employed the ShaD- oowoSmllmpeer (Dgl) as per (Zeng et al.) 2021), enabling mini-batch training. Each mini-batch was configured with a batch size of 32, and we sampled a maximum 10 neighbors within a range of two hops.
We report the mean and variance of the curacy metric over 4 random trials. In ad- dition to the general configuraiion, Table g presents the specific hyperparamcter settings. For GCNII and ACM-GCN+, the hyperpa- rameters were configured following the rec- ommendations the original implementa- tion. our framework, we fine-tuned the prior parameters and within the ranges [2, 5, 10, 15] and [2, 4, 6], respectively.
Table 7: General hyperparameter sctup for bascline methods and our method for Table [
General hyperparameter setup
128
epochs
500
patience
100
Ir dropout
1e-2
0.5
act
ReLU
optimizer
Adam
Table 8: Implementation details of basclines and our method for the homophilic datasets (de and do the dropedge and dropout rates respectively).
Datasct
Methods
Hyperparamcter details
GCN
de = 0.3
ResGCN
de = 0.3
GAT
de 0.3
JKNet
de 0.1
GCNIT
de 0.05,
0.1, À 0.5
Cora
ACM-GCN+
de 0.2, do = 0.7
Ours ResGCN
de = 0.1, = =5,, = =5,3= =2
Ours+GAT
de = 0.0, S =,,0= =5,8=2
OJrNttJKNet
de = 0.2, = =5,a = =5,
Ours+GCNII
de 0.0, 5,a 5, 2, 0.1
Ours + ACM-GCN+
de 0.2, 10, 8 2,
GCN
de 0.2 de 0.2
ResGCN
GAT
de 0.1
JKNet
de 0.2
GCNII
de 0.1, ( 0.1, = 0.6
Citeseer
ACM-GCN+
de = 0.2, do 0.2
Ours RReGGCN
de = 0.2, = -5,a 5, =2
Ours+GAV
de 0.0, 5, 5,8=1
Ours+JKKNG
de 0.1, 5,a
=5,8- 2
Our++GNNII
de 0.0, 5,
2, 2, 0.1
Ours + ACM-GCN+
de 0.2,
10, = 22
GCN
de = 0.3
ResGCN
de = 0.3
GAT
de = 0.05
JKNet
de = 0.05
GCNIT
de 0.1, a 0.1, X
Pubmed
ACM-GCN+
de 0.2, do 0.3
+ResGCN
de 0.1, 5,
5,, 3,
Ours+ GAT
de 0.0, 5,a =5,3 =
OKrs-tJKNet
de 0.1, = 5,a 2,
Ours+GCNII
de 0.0, S 5,a 5, = 2, 0.1
Ours + ACM-GCN+
de 0.2, a = 10, 3 2,
24

---

Published in Transactions on Machine Learning Research (07 (02))
G.2.2 Heterophilic Graphs (Chameleon, Cornell, Texas, Wisconsin)
For heterophilic datasets, we adopt the 3:1:1 split for the train, validation and test sets respectively in (Luan ct al., 2022). The basclines except GPR-GCN were implemented following the hyperparameter settings in (Luan et al. 2022). For GPR-GCN, the we adopled the results reported in (Luan et al. 2022)
The hyperparameters setup when integrating our framework with the baselines detailed in Table 9
Table 9: Implementation details of baselines and method for the heterophilic datasets (wd is the weight decay rate).
Dataset
Methods
Hyperparameter details
Ir = und 0=000000100000000000-0--00055550 b = 0.01, wd -00
Chameleon
Our++JKNet
Our=+GNNI
( 0.01, wd 5 10 -0
0.5, 15,3
Ours
Ir 0.01, wd = 10 -00
ACM-GCN+
I 0.004, wd 10 10 -=
RcsCNR
I = 0.1, wd = 5 100"000-66.--2------55
Cornell
OurttJJKNet
0.1, wd
3, -,0
Our=+GCNTI
Ir 0.1, wd 10 -0=6,,==45==100==0030 0.5, = 10, =2
Ours+GAT
= 0.1, wd = 2,
OUs+ACM-GGON+
i 0.01, wd -00,0000-1111..-..00
Ours+ResGCCN
I = 0.1, wd = = = =
Texas
Our++JKNet
/r 0.1, wd 1003000==
= =
Our-+GCNII
Jr = 0.1, wd = = -45.==4,5=10,pm
=05, 0.5, a= 10, =2
Ours+GAT
fr 0.1, wd
10,8
Ours +CM-GCN+
Ir = 0.05, wd -.0. 5,3
ResSN
= 0.1, -00
Wisconsin
JKNet
J 0.1, wd =
Ours+GCNII
Ir 0.01, wd 10 -00. -,-66,,7,,55110,0 05, 0.5, a = 1
Ours+GAT
l 0.1, wd 100330=333
10,3
Ours+ ACM-GCN
f 0.05, wd = 10 0= = 64.T 1,5 1,0 5.3=2
G.2.3 Hyperparameter Details for Table 4
In Table 4, evaluate the models three large graphs: Flickr (Zeg al. 2020 ogb-arxiv & ogb- proteins (Hu et al. (020).. We follow original train/validation/teen split as described in the original papers. The general settings are as described in Table 7 Additional hyperparamcter details are provided in Table 10 For the ogb-arxiv dataset, empirically we found that replacing the masking of node features with Z by multiplying the batch-normalized features with the activation probabilities of each layer ny results in better performance.
Table 10:
Implementation details for the large graph datasets.
Dataset
Methods
Hyperparameter details
Ours+ResGCCN
S = 5,
Flickr
JKrs+JKNet
S= 5,8=2
Our++GNNII
S= 5, 5, 2, at = 0.1
OesS
== 25,3=
ogb-arxiv
Net
S 5=3,00 20, ß 2
Ours+GNNII
S 5, = 25, β = 2, 0: = 0.5
OurS+
25, =
ogb-proteins
Ours
S = 3, 25, =
GUNTT
S 3, a 25, 8 2, 01 0.1
25

---

Published in Transactions on Machine Learning Research (07 (07/2025)
H Overfitting Analysis
We analyze overfitting in the GCN variants with and without our framework in Figure 9 The results suggest that the variants ResGCN, JKNet, and GAT trained with dropout suffer from overfitting problems as indicated by the increasing value of their validation loss at higher number epochs. The issue is alleviated by integrating these variants with our framework. GCNIT already robust to the overfitting problem. Application of our framework in GCNII does not have any significant effect on the validation loss.
Cora
Citeseer
Pubmed
desGCNedo
3.0
ResGCN+DD
ResāChido
Validation Loss
2.0
Validation Loss
2.5
JCNete DQ
CAT-DDO
Validation Loss
25
JKNet=do
GCNil+do
SCNIL=3D
GCHIl-do
2.0
Purs-RRsSCY
20
RusGRR
Ours-JChet
Durs-JjOlet
Durs-jKKNet
Qurs-EAT
Durs+GRT
15
Oursi
Durn COEM
1.0
10
0.5
0.5
100
150
200
250
300
350
400
50
100
150
200 Epochs
250
300
Epochs
Epochs
Figure 9: Validation loss for different GCN variants with and without the application of our framework.
Uncertainty Analysis
Cora
Citeseer
Pubmed
0.8
0.7
0.6
0.5
0.4
0.2
GCMI
0.2
AOM-DCM
GCMI
A29-2011
0.1
02
SureION
0.0
0.5
1.5
0.0
0.0
0.5
1.0
1.5
0.0
0.5
1.0
1.5
Uncertainty Threshold
Uncertainty Threshold
Uncertainty Threshold
Chameleon
Coreell
Texas
Wisconsin
Goe
GOB
0.6
RU
0.6
0.6
PA VS
0.4
0.4
0.4
0.2
0.2
0.2
0.0
0.0
08
Uncertainty Threshold
Uncertainty
Uncertainty Threshold
Uncertainty Threshold
Figure 10: Evaluating the uncertainty estimation of models, The reported metric PAusPU (higher values are preferable) plotted against increasing uncertainty thresholds.
In the main lext, we evaluated uncertainty calibration of models using the ECE metrie. For this study, we performed semi-supervised learning on the homophilic datasets and full supervised learning on the het- crophilic datasets. The dataset splits are as defined in sections 6.2.1 and 6.2.2. Here, we first detail the ECE metric and then extend this study by evaluating uncertainty calibration using the PAusPU metric (Mukhoti & Gal 2018 Hasanzadeh et al. 2020
26

---

Published in Transactions on Machine Learning Research (07 (025)
1.1 Expected Calibration Error (ECE)
Expected Calibration Error (Guo al. 2017) approximates the difference between predictive confidence and empirical accuracy. First, the predicted confidence is partitioned into I cqually-spaced bins (f, max Ds is the softmax oulput). Then ECE is the weighted average of miscalibration in each bin.
Bil |acc(B)) conf( B,)
ECE
(32)
with the number of samples N, accuracy of the bin B;
acc(B.)
Σ
1ly argmaa (ú:
|B
ieB;
and confidence of the bin B,
conf(B,) |
fs
iEB,
1.2 Assessing Uncertainty Calibration using the PAvsPU metric
To quantify uncertainty, we calculate the entropy of the output softmax distribution. For calculating the metric, we first an uncertainty threshold. Predictions with uncertainty values below the threshold are classified as cerlain predictions, while those with uncertainty values above the threshold are classified uncertain predictions. The count of accurate and certain predictions made by the model for given dataset is denoted as Rac- Similarly, the count of inaccurate and uncertain predictions are denoted as nuu- Finally, the metric PAusPU (Mukhoti & Gal 2018 Hasanzadeh et al. 2020) is defined as:
PAusPU = (Nac + maw)/(non + Max + Nie + Tlu))
(33)
where Naw the count of accurate and uncertain predictions and nie the count of inaccurate and certain predictions. The PAusPU metric assumes that the model has reliably estimated uncertainty when the predictions are accurate and certain as well as inaccurate and uncertain. It measures the proportion of predictions with reliable uncertainty estimation. Higher values of the metric indicates reliable uncertainty estimation.
Figure 10 shows that our method combined with GCN and ACM-GCN+ outperform other baselines in most cases.
J Concrete Bernoulli Distribution
The probability density function of a Concrete Bernoulli Distribution is:
ConBer(zod(at) = Te(2ot) T (1 Tt)) - 2ot) " (Zat)
(34)
TT) Fxt) =xt) -232
where 7 controls the distribution smoothness. We thus generate the VAE architecture samples Z, by first sampling from a logistic distribution, and then putting the samples through logistic function:
Zot I expeexxp-T11 (log log(1 me) + +))
(35)
where, c ~ Logistic(O,,
27

---

Published in Transactions on Machine Learning Research (07 (0/5))2))
=
L/T 4
L/T = 32
L/T = 64
GCN
ResGCN
OurS+ResGON
Figure 11: TSNE visualization of the learned node represenlations by GCN, ResGCN and our framework for shallow (L T {2,4)) 43) and deep (I. = T (32, 64)) structures on the Cora dataset. As observed in the top (GCN) and middle (ResGCN) rows, the representations converge in narrow curve-shaped regions for deep structures compared to spread-out representations in shallow structures. This indicates that the representations ions from GCN and ResGCN converge to a narrow subspace with deep networks. Applying our framework (bottom row) addresses this issue, resulting in spread-out representations with deeper structures. This suggests that the ion of our framework enhances the expressivily of GCNs.
K
Expressivity Analysis with Deep Network Structures
In Figure I we visualize the impact of ove-ssmoothing by plotting node representations learned by GCN, ResGCN, and our method. The t-SNE embeddings of the representations obtained from the last layer of shallow GCN networks (L (2, 4}) and deep GCN networks (L (32, 64)) are shown. With vanilla GCN, the representations are organized in clusters and spread out in space for shallow networks. However, for deep networks, the representations lose their organization and collapse to a curved-shaped region. In ResGCNs, the cluster organization is maintained deep structures, however the separation between clusters becomes less distinct. Also, the representations lie close together within a constricted curved-shaped region compared that with shallow structures. This is in accordance with Lemma and Corollary 1. The application of our framework (bottom row) results in comparatively spread-oul representations at the shallow structure (T/L- 4), which is in accordance with Theorem 2. Furthermore, the representations remain spread-on out even at deep structures, indicating improved expressivity as stated in Corollary 1. This demonstrates the effectiveness of our framework in enhancing the expressivity of GCNs.
L Effect of the Number of Monte Carlo Samples $
We investigate how the number of Monte Carlo samples S used to estimate the ELBO in Equation equation g affects the performance of our method. The results are reported in Table II We find that a higher number of samples i.c. S {3, 5, 10) performs significantly better compared to (1,2). The best performance
is achieved with 5
As further shown in the hyperparameter details in sections G.2 and G.2 S 5 consistently yields the best results in nearly all cases, although few instances perform best with S = 3
28

---

Published in Transactions on Machine Learning Research (07/2025)
= 10. Based these findings, recommend searching for the hyperparameter S in range centered around 5 when applying our method.
Table 11:
Node classification performance of our method on the Cora and Citeseer datasets for different
settings of the number of Monte Carlo samples S.
5
Cora
Citeseer
1
81.76::0.48
74.05=0.20
2
82.31+0.17
74.20=0.445
3
86.43-40.24
76.06:10.33
5
86.83:10.13
77.90=1.37
10
76.70:00.6
76.95-10.25
M Performance with Different Settings of a and 3
We evaluate the effect of the hyperparameters a and 3 on the performance of our method, and the results are reported Table 12 For small-scale datasets (Cora, Citeseer), the setting 5, 3= yields the best results, while for larger datasets (e-g-, ogb-arxiv), prior with 25, = 2 is optimal. As shown in the hyperparameter details in sections G.2 and C this pattern holds consistently: smaller datasets in Table [
favor 5, 3 = 2, whereas larger dalasets like ogb-arxiv and ogb-proteins perform best with E (20, 25} and 3 = 2. These findings suggest that the recommended search range for and & should be set according to the dataset size.
Table 12: Node classification performance of our method on the Cora, Citeseer, and ogb-arxiv dalasets for different settings of the hyperparameters (a, 3).
(a, B)
Cora
Citescer
ogb-arxiv
(2, 5)
80.1610.53
70.63:0.93
64.25:1..93
(2, 2)
86.4010.51
75.50
67.60+10.45
(5, 2)
86.8320.13
77.90
70.08=0.16
(10, 2)
85.85+00115
76.36+00.38
70.68+0.144
(20,2)
01.21
(25,2)
72.39
N Performance on Link Prediction Task
We further validate the performance of our framework in link prediction task by comparing it with Res- GCN on the biomedical datasets. The datasets we are (a) BioSNAP-DTI. Drug Target Interaction network with 15,139 drug-targel interactions between 5,018 drugs and 2,325 proteins, (b) BioSNAP-DDE: Drug-Drug Interactions with 48,514 drug-drug interactions between 1,514 drugs extracted from drug la- bels and biomedical literature, (c) HuRI-PPI: HI-III human PPI network contains 5,604 proteins and 23,322 interactions generated by multiple orthogonal high-throughpun yeast two-hybrid screens. and (d) NEG-GNET- gene-disease network with 81,746 interactions between 9,413 genes and 10,370 diseases curated from GWAS studies, animal models, and scientific literature. For all interaction datasets, we repre- sent the interactions as binary adjacency matrix A with 0 representing the absence of an interaction and 1 representing the presence of interaction between two entities in network. We perform random split of interactions within biological network, partitioning them into train seain/validatio//eee of 7: 1: 2. For each set, we acquire pairs of nodes that exhibit interactions between them (positive pairs) from the adjacency matrix A. In order to form a balanced dataset, we randomly select an equal number of node pairs with no interactions (negative pairs). The results in Table 13 show that applying our framework improves the link prediction performance on both the AUROC and AUPRC metric.
sets following ratio
29

---

Published in Transactions on Machine Learning Research (07/2025)
Table 13: Average AUPRC and AUROC for GCN and Ours on biomedical interaction prediction
Dataset
Method
AUPRC
AUROC
DTI
ResGCN
0.896 = 0.006
0.914 0.005
Ours+ResGCN
0.925 + 0.002
0.933 0.002
DDI
ResGCN
0.961 + 0.005
0.962 + 0.004
OerS+ResGCNN
0.983 = 0.002
0.982
0.003
PPI
ResGCN
0.894 = 0.002
0.907 0.006
Ours+ReGGCN
0.907 + 0.003
0.918 + 0.002
GDI
ResGON
0.909 + 0.002
0.906 + 0.002
ResS+
0.933 + 0.001
0.945 0.001
30


Reviews:
[{"review_id": "I0hP81UkMl", "reviewer": "Reviewer_ajXi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n- The paper is generally well-presented and easy to follow.\n- The central ideas of this paper are relatively straightforward and novel.\n- All theoretical results are well-argued with relatively straighforward proofs.\n- BNA is very effective at mitigating the \"oversmoothing\" problem of deep message-passing networks.\n\n**Weaknesses**\n\n- The intuition behind why the Beta distribution is used to model layer contributions is underexplained. Motivation for the proposed approach is insufficient.\n- The performance benefits conferred by BNA are inconsistent for certain combinations of datasets and models both for node classification and uncertainty calibration.\n- There is no discussion of the impact of the Bernoulli process over node features on performance. It would be interesting to see how each probabilistic component of BNA contributes to performance.\n- Graph rewiring methods like DropEdge are mentioned in related work, and it's revealed in the appendix that it was used by default in the homophilic datasets, but this is not made explicit in the main text. This raises concerns that BNA relies on competing regularization techniques to acheive good performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Apologies for the late review.\n\nThis paper offers Bayesian Neighborhood Adaptation (BNA) for adaptively determining the receptive field for residual GCNs. Layer contributions are modeled as a beta process, and node features are masked according to a Bernoulli prior trained via variational inference. Compared to other methods that rely on empirical heuristics, BNA offers an approach to learn optimal layer and feature contributions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dLBkJd5dsx", "reviewer": "Reviewer_wY2f", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe proposed BNA is novel. Different from fixed-depth message passing, BNA-GNN can dynamically learn the size of the receptive field by being jointly trained.\n\nWeakness:\n\n1. The reasons/intuitions for applying the Bernoulli process at the feature level are underexplained. A clearer motivation would help readers understand the design choices.\n\n2. The hyperparameter sensitivity of the proposed methods to the choice of $\\alpha$ and $\\beta$ is not discussed. Since both parameters control the final size of the receptive field, it would be helpful to discuss how $\\alpha,\\beta$ were set in experiments, like were they fixed across all runs or treated as tunable parameters.\n\n3. For the link prediction task, the authors can further validate BNA's improvement over GNNs on PPI datasets like OGBL-PPA[1]. This dataset is much larger and denser compared to other benchmarks, which can further examine the efficiency and effectiveness of the proposed method.\n\n[1] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a Bayesian Neighborhood Adaptation (BNA) framework for GNNs that dynamically determines the neighborhood size during training, rather than relying on a fixed hop count or exhaustive hyperparameter search. The core idea is to treat the neighborhood expansion as a stochastic process: a beta process prior is placed over an infinite sequence of possible hop counts. Besides, a conjugate Bernoulli process is used to sample feature-wise masks for each hop, determining which dimensions of the node features from that hop are included in aggregation. The authors claim this approach automatically adapts the neighborhood scope for message passing while jointly learning the GNN parameters.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EppibLmXrR", "reviewer": "Reviewer_QL3K", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n1. The proposed method is theoretically supported.\n\n2. Figure 4 experimental results on network expressivity are interesting and convincing\n- It seems like a clear demonstration of when the proposed adaptation method is useful (prevent performance collapsing with deep GNN structures). I suggest the authors to analyze deeper into this specific case.\n\n### Weaknesses\n\n1. Lack of intuition\n- It does not seem like the authors explained their specific choice of stochastic process. Why beta distribution? The choice of beta distribution reminds me of the Mixup augmentation. Given the ablation experiments when comparing against dropout regularization, the authors should explain how much of the proposed adaptation trick is contributing to the final performance by adding more nuanced/advanced regularization; and how much is contributed by actually treating the message passing behaviour as stochastic process.\n\n2. Experimental performance seems weak.\n- Performance improvement introduced from the proposed method seems marginal.\n\n3. Uncertainty quantification results lack explanations.\n- The authors argue that the proposed approach enhances uncertainty calibration, giving comparable results to GNN deep ensemble methods. However, this conclusion seems to contradict with Table 1 results, where the standard deviation shown by the proposed method in Table 1 are decently high when comparing against other methods.\n\n4. Biomolecular network results in section 5.8 are confusing\n- It is unclear how the results support the conclusion that “proteins that are three hops apart are likely to interact”. If that is the case, should not Figure 7 show a jump on the three hop position?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduced a stochastic process into the message passing process of GNNs by treating the number of hops as a beta process, which allows one to infer the neighborhood scope of the graph while learning their representations. The paper formulated this process and provided theoretical justification for the design, showing that the introduced stochastic process can make GNNs more expressive. The authors later conducted experimental validation of the model, which includes (1) experimental demonstration of the mechanism of the proposed neighborhood adaptation method and its expressiveness; (2) experimental performance by adding the neighborhood adaptation method as a plug in components on top of existing architectures; (3) ablations and complexity analysis; (4) a case study on biomolecular graph and the interpretability results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The authors should provide additional explanations on section 5.4 (Uncertainty quantification), showing why and how the proposed method is better than other methods, outside of only numerical results.\n2. The authors should provide additional explanations on section 5.8, detailing why the results show that “proteins that are three hops apart are likely to interact”.\n3. Ideally, if the authors can quantify or provide theoretical justification of the adaptation method by formulating the role of this neighborhood adaptation method in the regularization process, the theoretical results could be a lot stronger.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BCwCDLDPKX", "reviewer": "Reviewer_3vY9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. Timely focus on a known issue: The paper addresses the critical issue of choosing the proper neighborhood scope in GNNs, which impacts both performance and computational cost.\n\n2. Comprehensive experiments: The authors evaluate their method across a wide range of GNN backbones and datasets, and include expressivity analysis, uncertainty calibration, scalability, and biomolecular graph case studies.\n\n3. Theoretical contribution: The paper includes non-trivial expressivity analysis, extending previous work (e.g., Oono & Suzuki, 2019) and showing how the proposed method avoids feature collapse.\n\n4. Framework generality: The method is applicable to multiple backbone models, such as GCN, ResGCN, GCNII, and GAT.\n\n**Weaknesses and Concerns**\n1. **Motivation and Conceptual Framing**\n- **Unconvincing motivation for using Bayesian inference.** The paper proposes a Bayesian approach to infer neighborhood scope, but it does \n not clearly justify:\n  - Why Bayesian modelling is particularly suited to this task over other variational or heuristic adaptive methods.\n  - What fundamental advantagedo  Beta-Bernoulli processes offer in this context over simpler stochastic modeling techniques.\n\n- **Weak taxonomy of related work.** The literature review in Section 2.3 on Bayesian GNNs lacks a clear categorisation or comparison. The paper loosely groups prior work but does not articulate:\n  - Why existing Bayesian GNN methods (e.g., Bayesian-GCNN, G3NN) are inadequate for adaptive neighborhood inference.\n  - How this work extends or deviates from existing Bayesian inference practices in GNNs.\n\n2. **Organization and Writing.**\n- Disjointed Section 3. The subsections of Section 3 (Bayesian modeling, likelihood, inference) read as disconnected modules. The logical flow should be improved by:\n  - Starting with an intuitive explanation and motivating example.\n  - Explicitly connecting each subsection and clearly stating design decisions (e.g., why using Concrete Bernoulli).\n  - Summarizing the full generative process more clearly.\n\n- Unstructured Section 5. The experimental section covers many topics (expressivity, calibration, scalability, ablation, PPI case study), but lacks a clear mapping between objectives and subsections. The introduction of Section 5 should explicitly outline each experimental goal and assign each to a numbered subsection.\n\n- Appendix and Main Text Disconnect. Several critical derivations and definitions (e.g., inference procedure, model integration details) are deferred to the appendix without adequate referencing or notation consistency. The authors should:\n  - Clearly reference which parts of the appendix relate to specific claims in the main text.\n  - Use consistent notation across the main paper and appendix (e.g., θ, 𝜋_𝑙, 𝑍).\n\n3 **Methodological and Writing Issues**\n- Model complexity vs. gain trade-off is not clearly discussed. The Bayesian modelling and variational inference introduce computational overhead. While training time is reported, the paper lacks:\n  - Discussion of when this overhead is justified.\n  - Analysis of convergence behaviour and sample efficiency.\n\n- Writing requires polishing. There are frequent grammar and syntax issues (e.g., \"a daunting and time-consuming task and tend to be biased\", \"feature expression in a greater number of dimensions\"), which occasionally obscure the technical clarity. The writing should be revised for conciseness and precision.\n\n- Missing discussion on the broader impacts of Bayesian inference. The paper could benefit from a short discussion about when and why uncertainty-aware neighbourhood inference (vs. fixed-depth or deterministic schemes) is especially valuable—e.g., in safety-critical systems, few-shot learning, or adversarial robustness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a Bayesian Neighborhood Adaptation (BNA) framework that automatically infers the appropriate neighborhood scope (i.e., number of hops) in Graph Neural Networks (GNNs) using a nonparametric Bayesian prior (Beta-Bernoulli process). By modeling hop-level contribution probabilities and sampling node features with a binary mask, the method adaptively controls the message passing range during training.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Improve motivation by clearly articulating the rationale for using Bayesian inference over other methods and explicitly comparing with alternative approaches (e.g., attention-based dynamic scope, reinforcement learning).\n\n2. Reorganize Section 3 to build narrative coherence between model formulation, inference strategy, and integration into GNNs.\n\n3. At the beginning of Section 5, introduce a roadmap with subsections for each experiment to improve clarity.\n\n4. Establish stronger connectivity between main paper and appendix, with better notation alignment and referencing.\n\n5. Provide more nuanced insights into when the increased complexity of this method is justified, especially compared to lightweight methods like GPR-GCN or MixHop.\n\n6. Incorporate recent GCN advancements in related work\nThe current categorization of connection-based methods and GCN improvements is incomplete. \n- In particular, the authors should discuss:\n  - Cooperative Graph Neural Networks (ICML 2024), which introduce task-aware cooperative message passing strategies and dynamic connection weighting.\n  - Learning from the Dark: boosting graph convolutional neural networks with diverse negative samples. (AAAI 2022), which enhances GCNs by learning from diverse and informative negative samples.\n  - Layer-Diverse Negative Sampling (TMLR 2024), which improves expressivity and depth robustness by diversifying supervision across GNN layers.\n\n7. Thoroughly revise the manuscript for grammatical clarity, sentence structure, and typographic consistency, such as under Eq. (4):  \"O\" is the is the dimensionality of the feature vector. \"O\" should be \"W_l\"?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)