Adaptive Diffusion in Graph Neural Networks
Authors: Jialin Zhao
Yuxiao Dong
Ming Ding
Evgeny Kharlamov
Jie Tang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Convolutional Network

Abstract: The success of graph neural networks (GNNs) largely relies on the process of aggregating information from neighbors defined by the input graph structures. Notably, message passing based GNNs, e.g., graph convolutional networks, leverage the immediate neighbors of each node during the aggregation process, and recently, graph diffusion convolution (GDC) is proposed to expand the propagation neighborhood by leveraging generalized graph diffusion. However, the neighborhood size in GDC is manually tuned for each graph by conducting grid search over the validation set, making its generalization practically limited. To address this issue, we propose the adaptive diffusion convolution (ADC) strategy to automatically learn the optimal neighborhood size from the data. Furthermore, we break the conventional assumption that all GNN layers and feature channels (dimensions) should use the same neighborhood for propagation. We design strategies to enable ADC to learn a dedicated propagation neighborhood for each GNN layer and each feature channel, making the GNN architecture fully coupled with graph structures---the unique property that differs GNNs from traditional neural networks. By directly plugging ADC into existing GNNs, we observe consistent and significant outperformance over both GDC and their vanilla versions across various datasets, demonstrating the improved model capacity brought by automatically learning unique neighborhood size per layer and per channel in GNNs. 

Adaptive Diffusion in Graph Neural Networks
Jialin Zhao Tsinghua University =j119977660@@maii..com com
Yuxiao Dong" Microsoft Research eri crriddgyy@@@mil.ccmm com
Ming Ding Tsinghua University
Evgeny Kharlamov Bosch Center for Artificial Intelligence Evgeny Kharlamov@de bosch com
dm18@mails. ttt.mmmml..sssnnuaaa..aaa. edu.
Jie Tangi Tsinghua University
j jietang@tsinghua edu. cn
Abstract
The success graph neural networks (GNNs) largely relies on the process aggregating information from neighbors defined by the input graph structures. No- tably, message passing based GNNs, e.g., graph convolutional networks, leverage the immediate neighbors of each node during the aggregation process, and recently, graph diffusion convolution (GDC) is proposed to expand the propagation neigh- borhood by leveraging generalized graph diffusion. However, the neighborhood size in GDC is manually tuned for each graph by conducting grid search over the validation set, making its generalization practically limited. To address this issue, we propose the adaptive diffusion convolution stratetr strategy to automatically learn the optimal neighborhood size from the data. Furthermore, we break the conventional assumption that all GNN layers and feature channels (dimensions) should use the same neighborhood size for propagation. We design strategies enable ADC to learn dedicated propagation neighborhood for each GNN layer and each feature channel, making the GNN architecture fully coupled with graph structures-tte the unique property that differs GNNs from traditional neural networks. By directly plugging ADC into existing GNNs, we observe consistent and sig- nificant outperformance over both GDC and their vanilla versions across various datasets, demonstrating the improved model capacity brought by automatically learning unique neighborhood size per layer and per channel in GNNs.
Introduction
Graph neural networks (GNNs) are type neural networks that can be directly coupled with graph-structured data 330 41 Specifically, graph convolution networks [22 [9] (GCNs) generalize the convolution operation to local graph structures, offering attractive performance for various graph The graph convolution operation is designed to aggregate information from immediate neighboring nodes into the central node, which is also referred to as message passing [14). To propagate information between nodes that further away, multiple neural layers can be stacked
mining tasks 15
32 37).
Now at Meta Al and work done when at Microsoft.
Jie Tang is corresponding author. "Code is available at htttttss://itiiii //tttthb/btbbb/// com/ aalaaaabbdbff/ /ADC
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to go beyond the immediate hop of neighbors. To directly collect high-order information, spectral based GNNs leverage graph spectral properties to collect signals from global neighbors 66 12 17].
Though generating promising results, both strategies are limited to a pre-determined and fixed neighborhood for passing and receiving messages. Essentially, these methods have implicit assumption that all graph datasets share the same size of receptive field during the message passing process. To break this, graph diffusion convolution (GDC) [21 was recently proposed to extend the discrete message passing process in GCN to a diffusion process, enabling it to aggregate information from larger neighborhood. For each input graph, GDC hand-tunes the best neighborhood size for feature aggregation by grid-searching the parameters on the validation set, making its practical application limited and sensitive.
To eliminate the manual search process of the optimal propagation neighhorhood in GDC, we propose the adaptive diffusion convolution (ADC) strategy that supports learning the optimal neighborhood from the data automatically. ADC achieves this by formalizing the task as a bilevel optimization problem [II] enabling the customized learning of one optimal propagation neighborhood size for each dataset. In other words, all GNN layers and feature channels (dimensions) share the same neighborhood size during message passing on each graph.
To further this direction, we also enable ADC to automatically learn a customized neighborhood size for each GNN layer and each feature channel from data. By learning unique propagation neighborhood for each layer, ADC can empower GNNs to capture neighbors' information from diverse graph structures, which is fully dependent the data and downstream learning objective. Similarly, by learning distinct nei neighborhood size for each feature channel, GNNs are then capable of selectively modeling each neighbor's multiple feature signals. Altogether, ADC makes GNNs fully coupled with the graph structures and all feature channels.
By design, iDC general plugin that can be directly applied to existing GNN models. By plugging it on several GNNs, we show that the upgraded GNNs can offer significant performance advances over their vanilla versions across wide range of datasets. Furthermore, experimental results also show that by learning the propagation neighborhood size automatically. ADC can consistently outperform GDC, which customizes this for each dataset by grid search. Finally, we demonstrate that GNNs' model capacity can benefit from the better coupling between the its architecture, graph structures, and feature channels, that is, by learning dedicated neighborhood size for each GNN layer and feature channel.
2 Neighborhood Radius in GNNs
We focus on the problem of semi-supervised node classification. The input includes an undirected network G = (V, E), where the node set V contains of n nodes {v) J J and E is the edge set, and A pmxx is the symmetric adjacency matrix of graph G. Given the input feature matrix X and a subset of node label Y, the task is to predict the labels of remaining nodes.
2.1 Neighborhood Radius in Message Passing Networks
The convolution operation graphs can be described as the process of neighborhood feature aggregation or message passing [4] The message passing graph convolutional networks can be simply defined as:
H (00) (H()))), G)
(1)
where (4) denotes the hidden feature of layer with H = X and X the input feature, (p))
denotes feature transformation and 7(-) denotes feature propagation. Take GCN [19 for example. The
feature transformation and feature propagation functions correspond to pp (H) HW, > (H, G)
D 1 ÄD à A, respectively, in which D is the diagonal degree matrix with D E, Ag. and A denotes hidden feature after transformation. Note that GCN uses the adjacency matrix A with self loop, so it actually uses À I I A. To simplify the notations, we use T to denote D 3 AD 4.
Straightforwardly, the feature transformation function yp(-) describes how features transform inside each node and the feature propagation function 7(-) describes how features propagate between nodes. Essentially, how good GNN model can utilize graph structures heavily depends on the design of the feature propagation function.

---

Neighborhood radius r. Most graph- based models can be represented as G) () HT. where f(T) is a matrix that can be generated by T. So f(T) can be represented as f(T) En= 0g TT. To quantify how far each node could aggregate features from, define the neighbor-
hood radius of node as r:
Σx= k= O2
Ex= 0z
Here, O2 denotes the influence from k-step-away nodes. For large r, this means the model puts more emphasis on long distance nodes, i.e., global information. For a small r, this means the model amplifies local information.
Neighborhood radius r in GCN. For GCN, the neighborhood radius = 1, which is just range of nodes directly connected to it. To collect information beyond direct connections, it is required to stack multiple GCN layers to reach high-order neighborhoods.
Neighborhood radius r in multi-hop models. There are attempts to improve GCN's feature propagation function from first-hop neighborhood to multi-hop neighborhood, such as MixHop (2) JKNet [38], and SGC [35]. For example, SGC [35) uses feature propagation function 7(H, G) = T H. where T = AD- $ In other words, the neighborhood radius = K for SGC, which is the range of neighborhoods collect information from each GNN layer. However, for all multi-hop models, the discrete nature of hop numbers makes non-differentiable.
2.2 Neighborhood Radius in Graph Diffusion Convolution
Recently, a line of work has been focused generalizing feature propagation from discrete hops to continuous graph diffusion [2] 40). Notably, graph diffusion convolution (GDC) addresses this
by the following propagation setup 21
1 - T
- 0g
k=
where & is summed from to infinity, making each node aggregate information from the whole graph.
In Eq 3, the weight coefficients should satisfy Ek=o 0₂ = such that the signal strength is not amplinied nor reduced through the propagation. The two commonly sets of weight coefficients
21 36 40)
are generated from personalized PageRank (0, = a(1 - a)*) [7 and the heat kernel
(0,-
22
respectively. In this work, focus heat kernel.
Heat kernel. Heat kernel incorporates prior knowledge into the GNN model, which means the feature propagation between nodes follows Newton's 's law of cooling [34] i.e. the feature propagation speed between two nodes is proportional to the difference between their features. Formally, this prior knowledge can be described as:
dx, = Σ At)(x((t) -xy(t)
(4)
dt
JEN())
where (1) denotes the neighborhood of node i, (t) represents the feature of node i after diffusion time t. This differential equation can be solved as:
X(1) ())
where X(t) means the feature matrix after diffusion time t and H, - (I-T)* is the heat kernel.
Neighborhood radius Tn in diffusion models. According to the definition of neighborhood radius Eq. the heat kernel version of the GDC has neighborhood radius Th
Th Ek=0 Oak
Σ
t* k1
6
k
C
(c't) e-
=
(6)
Ex On Ex K
e-
c
2 Æ
This suggests that the neighborhood radius for the heat kernel based GDC, that is, becomes a perfect continuous substitute for the hop number in multi-hop models.
3

---

0.4
3.5
4.0
Benti on bnthaee
0.90
0.85
0.80
3.0
0.80
Lost aecurary
2.5
train less
875
2.0
0.70
bamts crahiion
0.60
0.60
100
200
400
S00
100
20c
400
S00
0.55
100
23c
300
400
São
0.55
100
230
450
Soc
epochs
epochs
epachs
epachs
Figure I: Comparison among fixing i (red), training & on train set (blue), training t on validation set (green), and training separately for each feature channel on validation set (black). The results are reported by using the Heat Kernel version of GCN the Cora dataset. Training validation set can prevent overfitting.
3 Adaptive Diffusion Convolution
Recall that the heat kernel version of graph diffusion convolution (GDC) has the following feature propagation function
(0) (f, G) =
T
where the Laplacian matrix I T. For each graph dataset, requires the manual grid search step to determine the neighborhood radius related parameter t. Moreover, t is fixed for all feature channels and propagation layers in each dataset. In this work, we explore how adaptively learn the neighborhood radius from data for each graph and further examine the potential to generalize it for different feature channels and GNN layers.
3.1 Training Neighborhood Radius
Diffusion convolution enables us to replace GNNs' discrete feature propagation function with the continuous heat kernel. Instead of hand-tuning t, we can calculate the gradient of and update to converge to an optimal neighborhood, which is the same to learning other weight and bias parameters in the model.
Figure [ shows the training process of learning t. With more epochs, both / and training loss decrease when learning on the training set (blue). Meanwhile, the validation and test accuracies drop dramatically as tends to zero (more epochs)-rrpreeeettiie
each node could only use its own features to predict the label. That is, learning / directly the training set causes overfitting. This phenomenon has also been observed in GDC (21). The authors found that strong regularization on the difference of 0x+1 - 02 could help overcome the overfitting issue. However, that would require hand-tuning the regularization factor for every dataset, which is similar to hand-tuning t itself, e.g.. by grid search, further limiting the generalization of the model.
To address this issue, we propose method of training t by using the gradient of the model on the validation The goal for the model is to find t* that minimizes the validation loss Ceat(t, w*), where w denotes all the other trainable parameters in the feature transformation function and w" denotes the of parameters that minimize the training loss Lerain (1,, w). This strategy can be formalized as bilevel optimization problem
arg min (tai (t))
(8)
arg min Ltrain (1,
w
By doing so, every time we update t, we need to make w converge to the optimal value, which too expensive to train. An approximation method is to update t every time we update w, that is,
w (c+1) w(()
a1 T Lirain (t(c) w())
(10)

---

((e-1) =(()) 02 Vi (tle), (10t,,w(et) wl(++1)
(11)
where denotes the number of training epochs, a and a2 denote the learning rate on the training and validation sets, respectively. The similar idea has been proposed in the gradient-based hyperparameter tuning [24] and neural architecture search 23 Figure [ shows that using this method (green lines)
helps avoid overfitting and thus offers better generalization, as there is no sign of test accuracy drop. Meanwhile, does not diminish to zero, indicating the meaningful learning of this parameter- neighborhood radius.
3.2 Training Neighborhood Radius for Each Layer and Channel
Conventional GNNs use the pre- determined neighborhood radius for feature propagation. GDC proposes to use different neighborhood radius t for different datasets by hand-tuning the values. The above method furthers this direction by automatically learn- ing the radius from the given graph. This implies that one / for one dataset, that is, the same t for all GNN layers and all feature channels (dimensions).
(
fla
3
A
PHiL -0
1
8
Figure Illustration of the Adaptive Diffusion Convolu- tion (ADC). For the hidden feature H. of feature channel in layer 1, we train separate feature propagation function 70) (Ar G); with unique neighborhood radius (00) When t is large (e.g.. f=3), the contributions from close (c.g.. in I-hop) and distant neighbors (e.g., in 3-hop) have little dif- ference (shown as the relatively similar color shading across different hops). When f is small (e.g., t=1), the contributions from close neighbors are much more significant than from distant neighbors (shown as dark color concentrated around center).
Adaptive diffusion convolution (ADC). The natural question arises here is whether we can have a unique t for each layer and channel, making them adaptive for the final learning objective. The obstacle that prevents previous models from achieving this lies in the infeasible challenge of hand-tuning or grid-searching the propagation function separately for each feature channel and GNN layer, given that as the number of parameters increases, the time complexity increases exponentially. However, the aforementioned strategy for updating t during the training of the model empowers us to adaptively learn specific ł for all layers and all feature channels.
Straightforwardly, have the adaptive diffusion convolution (ADC) by extending the feature (1)
propagation function in Eq. for each layer and channel, that is, from t to t
((,AG) G)
T
(12)
k!
k=
where (!)) denotes the neighborhood radius t for the (-th layer and i-th channel, Å. represents the i-th column of the hidden feature H. i.e., the feature channel and 7 (1) denotes the feature propagation function on the 1-th layer and i-th channel. This feature propagation function enables the GNN to train separate t for each feature channel and layer, which is illustrative in Figure 2 In addition, Figure [ (black lines) also shows that there is no overfitting caused by the increase of the number of pyperparameters (t).
Generalized adaptive diffusion convolution (GADC). By now, we introduce the adaptive diffusion convolution based on heat kernel. Without loss of generality, we can have ADC extended generalized ADC (GADC), that is, not limiting the weight coefficients 0g as heat kernel. Therefore, we have the feature propagation of GADC
20
(0HHH)) G), = Σe T
(13)
k=U
5

---

Table 1: Dataset Statistics 29
CORA
CiteSeer
PubMed
Coauthor CS
Amazon Computers
Amazon Photo
MNodes
2485
19717
18333
#Edges
5069
3668
44324
81894
245778
119043
#Classes
7
6
3
15
10
8
#Training- -oiiin
140
120
60
300
2001
160
#Validation Nodes
1440
4700
1300
1340
#Test-Nodes
985
610
18217
13333
11881
5987
CORA
CITESEER
PUBMED
85
75
83
83
74
82
None
None
None
GDC
ADC
72
ADC
78
ADC
GADC
GADC
GADC
80
GCN
ARMA
JKNet
71
GCN
ARMA
JKNet
GCN
ARMA
JKNet
COAUTHOR
AMZ COMP
AMZ PHOTO
92.5
86
85.5
85.0
91
None
84.5
None
None
91.0
GDC
04.0
GDC
ACC
GDC
GADC
GADC
GADC
GCN
ARMA
JKNet
GCN
ARMA
JKNet
GCN
ARMA
JKNet
Figure 3: Semi-supervised node classification accuracy, original model improved with GDC
our trainable heat kernel. Our improvement surplus GDC in most datasets and models.
where 0(4) denotes the weight coefficient for k-hop neighbors I-th layer and i-th channel. We restrict
= during training.
Implementation Details. we operate differently on each channel, whether we propagate before or after the feature transformation function actually matters. Empirically, we find that propagating on the input channels generates better results than propagating on the output channels (Cf. Figure for details). Therefore, we swap the propagation and transformation steps in the original message passing networks from Eq. to:
H (0) (0 (H G))
(14)
Additionally, calculating e Lt directly is infeasible for large graphs. Practically, we need to use the top-K K truncation approximate the heat kernel, making ADC (Eq. [2] and GADC (Eq respectively updated as:
(1 Ze-t k=
1 (HH
HH (HH
Σ TH
(15)
Similar to GDC, ADC and GADC are flexible components that can directly plugged into existing GNN models, enabling them adaptively learn the neighborhood radius for feature aggregation.

---

4 Experiments
4.1 Experimental setup
We follow the standard procedure to conduct experiments and report results. Same GDC, each result is averaged across 100 random data splits and initializations. All baseline GNNs use the same hyperparameters as GDC's baseline model. We only compare with the heat kernel version of GDC. We set the learning rate of t equals to the learning rate of other parameters, which is 0.01. All results calculated averages with 95% confidence via bootstrapping.
The prediction task is focused on semi- supervieee node classification. We use including CORA, CiteSeer (28), PubMed (25]. Coauthor CS, Amazon Computers and Amazon Photo 29 Statistics of datasets are listed in T Same as GDC, we only use their largest connected components. The data is split to development and test set. Development set contains 15000 nodes except Coauthor CS that contains 5000 nodes. The development set is split to a training set containing 20 nodes for each class and validation set with remaining nodes.
datasets
We implement ADC and GADC on three models: GCN [9], JKNet 38 and ARMA [5]. We only replace original model's ss feature propagation function with ADC or GADC and preserve feature transformation function. The expansion step (K in [5) is set to 10. We use early stopping with patience of 100 epochs. Different from GDC, we don't 't use GAT [32] or GIN (37], because GAT uses learned attention matrix instead of adjacency matrix and GDC's experiments show that GIN performs much worse than other models.
4.2 Results
Figure 3 reports the main results when applying GDC and the proposed ADC on GCN, ARMA, and JKNet. It shows that ADC significantly improves base GNNs and outperforms GDC on most cases. Compared to GADC, which has x more hyperparameters than ADC, ADC can match and achieve comparable even better results.
In addition, we observe that the runs with low stopping epochs (less than 300) often perform worse than those with more stopping epochs. Forcing early stopping inactive in low epochs could help increase the performance by a little. This suggests that the neighborhood radius may need more training epochs, however, this contradicts with the early stopping strategy, which means high stopping epochs may cause w to overfitting. To make a straightforward and fair comparison, we do not use this training trick in our experiments.
Ablation study. The ablation studies on different diffusion setting are summarized Figure GDC can be seen as fixing /. heat kernel with sparsification. The results suggest that GDC's performance is partly due to its sparsification on propagation matrix, because we remove sparsification, training t for each feature channel and layer always performs better than fixing t to its initialization value. Figure 4 also shows that by comparing the improvements brought by training t at different levels, training& t for each channel and layer contributes the most to the performance improvements on the node classification task.
The influence of rate between training and validation set. Because ADC trains large number of hyperparameters on validation set, this may cause concerns about whether the improvement is due to overuse of the validation set. To verify that, do the same experiment of Figure 3 on different rates between training and validation sets, with same settings. We fix the total number of nodes of the development set and change the number of nodes per class in training set. As stated before, the development set contains 1500 nodes except Coauthor CS which has 5000 nodes. Results in Figure 5 show that ADC constantly performs better than GDC and the original base GNN model (GCN) in most cases. This demonstrates that the advantage of ADC does not come from training more parameters on large validation set.
The influence of expansion step. Do the long-distance neighbor nodes really help? K in Eq. 15 denotes the expansion step or truncation step of Taylor expansion. By changing K, we could examine whether neighbors further than K step away really matter. Figure shows that increasing the step of Taylor expansion (K) often helps to increase accuracy. Nodes further than ten step away don't 't carry valuable information.
7

---

CORA
CITESEER
PUBMED
84.5
74.50
1%
84.0
74.25
82
Accura
883.0
83.5
74.00
73.75
81
73.50
80
82.5
82.0
GCN
73.25
73.00
GCN
79
81.5
ARMA
72.75
ARMA
78
ARMA
81.0
JKNet
72.50
Koiet
77
JKNet
(a)
(b)
(c)
(d)
aa)
(b)
(c)
(d)
(a)
(b)
(c)
(d)
COAUTHOR CS
AMZ COMP
AMZ PHOTO
93.0
86.0
93.2
92.5
85.5
93.0
Accuracy
.9.00
85.0
84.5
92.6
92.8
91.5
84.0
92.4
91.0
GCN
83.5
GCN
92.2
GEN
90.5
83.0
92.0
90.0
JKNet
82.5
JKNet
91.8
KNNet
(a)
(b) (c)
(d)
(a)
(b) (c)
(d)
(a)
(b)
(c)
(d)
Figure 4: (a) Fixing to the initialization value. (b) Training one t for all layers. (c) Training one t for each layer. (d) Training a unique for each feature channel and layer. (a) can be seen as GDC without sparsification. Results show that after removing sparsification in GDC, training from data always helps improve performance.
CORA
CITESEER
PUBMED COAUTHOR CS
AMZ COMP
AMZ PHOTO
03:
RA.0
73
76
83
21
30
20
40
10
120
50
25
30
80
123
10
20
1O
120 TE0
1V
20
45 nitanee
10
20 45
10
120
20 43
05 150
In 17
In tran
15 ORT
Figure 5: Influence of the number of training nodes. X-axis denotes the number of nodes per class in training set. We fix the total number of development set (train + valid) to be the same. ADC constantly performs better than GDC and the original model (GCN) in most cases. This indicates that the advantage of ADC is not due to training more parameters on large validation set.
CORA
CITESEER
PUBMED
COAUTHOR CS
AMZ COMP
AMZ PHOTO
03.0
53
52.6
$4.5
32.
53.5
10
28
20
Figure 6: Influence of the number of Taylor expansion steps on the trainable heat kernel in ADC. Increasing step number helps increase the accuracy in most cases.

---

The influence of propagation before or after transfor- mation. As we discuss in [q different from GCN, propagation before or after transformation does matter in our model, because this means learning unique for each input feature channel or each output feature channel. Figure[]showe that propagation before transformation per- forms better than propagation after transformation. This is probably because input feature's ' channel carries more diverse information.
in channel
out channel
Accuracy (%)
85
80
ConuthorAMECa
5 Related Work
Figure 7: Comparing propagating before or after feature transformation function on ADC GCN, which means learn separate propagation for each input or output feature channel. Result shows that learning separate t on input channels performs better.
Bruna et al. 6 first propose spectral graph convolu- tional network, using back propagation to learn the kernel filter. Later, ChebyNet [12 is proposed to leverage Cheby- shev expansion to avoid the Laplacian eigendecomposi- tion, which has high computational complexity. The graph convolutional network (GCN) [9 go one step further by
simplifying the kernel filter to the first-order of Cheby-
shev expansion. The graph attention networks (GAT) [32] utilize self-attention layers to learn the importance of dif-
ferent nodes in neighborhood. GraphSAGE [15) generalizes graph convolution from transductive
tasks to inductive tasks. Different types of feature propagation model have been proposed and used in
practice [20 1 33 16.
In Chung et al.'s book [10), the properties of heat kernel in graph have been discussed thoroughly. David et al. 31] generalize windowed Fourier graph with heat kernel. After GCN emerged, some graph convolution models integrating heat kernel have been proposed. GraphHeat (36 leverages heat kernel to enforce smoothness the signal variation on graph, which acts as a low-pass filter. GDC 21 utilizes heat kernel as special case of graph diffusion. In ProNE [39. Chebyshev expansion is proposed to approximate heat kernel.
Using learned coefficients of k-hops neighbors instead of hand-tuned has already been discussed in some other graph learning tasks. AdaDIF 4 proposes a class-specific adaptive diffusion method on label propagation. AGF [8] also in label propagation, uses adaptive graph filters to form global decision by combining decisions from multiple graph filters. In node embedding tasks, an attention-based model (I] proposes to learn the length of random walk via backpropagation. PERDIF 26 learns personalized diffusion over item models for top-n recommendation. AptRank [18] utilizes an adaptive diffusion method for protein function prediction. A recent work, GPR-GNNN [.. utilizes adaptive generalized PageRank, but focusing on handle heterophily and over-smoothing.
None of the previous methods calculates gradients validation set to prevent overfitting or treat each feature channel and layer separately.
Conclusion and Discussion
In this work, propose to learn the neighborhood radius for the feature aggregation process in GNNs. Traditionally, the neighborhood radius is either pre-determined, e.g., GCN, or hand-tuned, e.g.. GDC. To make it practically applicable to real-world problem settings, we present a general GNN plugin ADC that can automatically learn the neighborhood radius for each GNN layer and each feature channel. Similar to GDC, ADC is able enhance any graph-based model, particularly GNNs. By directly plugging ADC into existing GNNs, the experiments and ablation studies show that learning unique neighborhood radius for each feature channel in each GNN layer consistently and significantly improves the performance for downstream graph mining tasks.
Notwithstanding the promising results, future works might lie in improving the training procedure, as we notice that the neighborhood radius sometimes requires more epochs to train than other parameters. One possible direction is study how automatically balance this with early stopping strategy.
In terms of societal impacts, the proposed technique ADC shares the same promises and potential issues with the general GNN research. Graphs are naturally used for abstracting and modeling

---

relational and structured data, such as social networks, and graph neural networks, as a powerful tool for modeling graphs, may suffer from the privacy issues faced by the original social platforms or graph datasets. However, in general, we do not see ethical concerns or potential harms of the proposed technique.
For reproducibility, both the code and datasets (publicly available) used for experiments are included in the supplementary document.
References
[1] Sami Abu-EI-Haija, Bryan Perozzi, Rami AI-Rfou, and Alex Alemi. Watch your step: Learning node embeddings via graph attention. arXiv preprint arXiv: 2017.
[2] Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan, Mixhop: Higher-order graph convolution architectures via sparsified neighborhood mixing, In International Conference on Machine Learning (ICML), 2019.
[3] G Anandalingam and Terry I. Friesz. Hierarchical optimization: An introduction. Annals of Operations Research, 34(1):1-11, 1992.
[4] Dimitris Berberidis, Athanasios N Nikolakopoulos, and Georgios Giannakis. Adaptive diffu- sions for scalable learning over graphs. IEEE Transactions on Signal Processing, 67(5):1307- 1321, 2018.
[5] Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. arXiv preprint wIXIv:1901.01333 2019.
[6] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations (ICLR2014), CBLS, April 2014, 2014.
[7] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pages 1725-1735. PMLR, 2020.
[8] Siheng Chen, Aliaksei Sandryhaila, José MF Moura, and Jelena Kovačević. Adaptive graph filtering: Multiresolution classification graphs. In 2013 IEEE Global Conference Signal and Information Processing, pages 427-430. IEEE, 2013.
[9] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
[10] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
[11] Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-256, 2007.
[12] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 3854-3852, 2016.
[13] Wenzheng Feng Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22092-22103, Curran Associates. Inc., 2020.
[14] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.
10

---

[15] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large 2017.
graphs. arXiv preprint
[16] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pages 41264 PMLR, 2020.
[17] Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint arXiv: /.tiv:55060000 05 163,, 2015.
[18] Biaobin Jiang. Kyle Kloster, David Gleich, and Michael Gribskov. Aptrank: an adap- tive pagerank model for protein function prediction on bi-relational graphs. Bioinformatics, 33(12):182--1836 2017.
[19] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[20] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
[21] Johannes Klicpera, Stefan WeiB enberger, and Stephan Günnemann. Diffusion improves graph learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[22] Risi Imre Kondor and John Lafferty. Diffusion kernels on graphs and other discrete structures. In Proceedings of the 19th international conference on machine learning, volume 2002, pages 315-322, 2002.
[23] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprini arXiv:/806.0000 1806.09055 2018
[24] Jelena Luketina, Mathias Berglund, Klaus Greff, and Tapani Raiko. Scalable gradient- based tuning of continuous regularization hyperparameters. In International conference on machine learning, pages 2952-2960. PMLR, 2016.
[25] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, 2012.
[26] Athanasios Nikolakopoulos, Dimitris Berberidis, George Karypis, and Georgios Giannakis. Personalized diffusions for top-n recommendation. In Proceedings of the 13th ACM Conference on Recommender Systems, pages 260-268, 2019.
[27] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
[28] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008
[29] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 18/10588 2018.
[30] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[31] David I Shuman, Benjamin Ricaud, and Pierre Vandergheynst. Vertex-frequunccy analysis on graphs. Applied and Computational Harmonic Analysis, 40(2):260-291, 2016.
[32] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference Learning Representations, 2018. accepted as poster.
[33] Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In ICLR (Poster), 2019.

---

[34] Widder and David Vernon. The heat equation, volume 67. Academic Press, 1976.
[35] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In Proceedings of 36th International Conference on Machine Learning, pages 6861-6871, PMLR, 2019.
[36] Bingbing Xu, Huawei Shen, Qi Cao, Keting Cen, and Xueqi Cheng. Graph convolutional networks using heat kernel for cumi-uuperiieed learning. arXiv preprint arXiv:2007. 2020.
[37] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
[38] 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, pages 5453-5462. PMLR, 2018.
[39] Jie Zhang, Yuxiao Dong, Yan Wang, Jie Tang, and Ming Ding. Prone: Fast and scalable network representation learning. In IJCAI, volume 19, pages 4278-4284, 2019.
[40] Jialin Zhao, Yuxiao Dong, Jie Tang, Ming Ding, and Kuansan Wang. Generalizing graph convolutional networks via heat kernel, 2021.
[41] Xiaojin Jerry Zhu. Semi-supere learning literature survey. 2005.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In the first part of section 4.2 we discuss our training procedure still has a lot to improve and when will have poor performance.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We discuss in conclusion section.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] The only assumption we make is that by using heat kernel, we assume the feature propagation on graphs follow Newton's law of cooling, See equation 4
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We include all the codes needed for reproduction in supplemental material. The hyperparameters are listed in appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See [.ction[4.]]aa and appendix.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Our figure 3 contains error bars. Results in tabular form are presented in appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See appendix.
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
12

---

(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] They are all public datasets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "OINyTZNOuk", "reviewer": "Reviewer_JPvA", "summary": "This paper extends from graph diffusion convolution (GDC) that used hand-tuned neighborhood size for feature aggregation to adaptively learning the size. ADC can automatically learn the neighborhood radius for each GNN layer and\neach feature dimension and acts as a plugin to any GNN model. Experimental results and ablation studies show\nthat learning a unique neighborhood radius for each feature channel in each GNN layer consistently\nand improves the performance of downstream graph mining tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Pros:\n1. Improve from GDC that is manually tuned size for each graph by conducting grid search over the validation set, the paper proposes the adaptive diffusion convolution (ADC) to automatically learn the optimal neighborhood size from the data.\n2. ADC chooses different neighborhood sizes for each GNN layer and feature channel.\n\nCons:\n1. GDC applies diffusion on the original adjacent matrix to get a dense graph, and then sparsify the dense graph to get a sparse graph (Only one pass graph diffusion); while ADC extends such idea to each GNN layer over adjacent matrix. Therefore, the proposed method also has high computation complexity comparing to GDC. This is not mentioned in the paper.\n2. The experimental setup does not follow standard splitting for semi-supervised node classification. Therefore it is difficult to compare the results in the paper to other recent STOA on the semi-supervised node classification (for example, \"Direct Multi-hop Attention based Graph Neural Network\", https://arxiv.org/pdf/2009.14332.pdf)\n3. From the experimental results, the improvement seems not convincing and the reported accuracy improvement is GNN- and data-dependent: the original ARMA and JKNet are generally better than GCN on Cora, Citeseer. However, Fig. 3 did not show the benefit of JKNet (ARMA) vs GCN on Cora, Citeseer.  In fig. 3, the proposed method + ARMA (JKNet) is worse than (proposed method + GCN).  In comparison, GDC + ARMA (JKNet) is usually still better than GDC + GCN. Meanwhile, the proposed method + ARMA is also worse than the performance on COAUTHOR CS and AMZ COMP --- there are no explanations for these inconsistent results.\n4. The performance numbers for ADC/GADC are not consistent, on some datasets, ADC is better, some GADC is better. Any explanation?\n5. On page 5, feature transformation and propagation are swapped because \"Empirically, we find that propagating on the input channels generates better results than propagating on the output channels\". This conclusion might be data-dependent or GNN model-dependent: In figure 6,  the experiments were conducted using GCN. Is the same conclusion achieved on JKNet and ARMA models?\n\n** I have read the responses from the authors and adjusted the score based on their answers to my questions. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "IjpnWWbacti", "reviewer": "Reviewer_R6WW", "summary": "This paper introduces adaptive graph diffusion convolution (ADC), a new module that adaptively and automatically determines the neighborhood size for the better feature aggregation of existing GNN frameworks. It extends the graph diffusion convolution (GDC) one step further to make the selection of neighborhood radius learnable. Generally speaking, it is an interesting idea to directly learn different neighborhood radius in different layers. This paper is well-written and easy to follow, and related works are covered comprehensively. Authors further conduct (limited) experiments comparing with selected baselines in node classification tasks, various analysis, and ablation studies demonstrate the strength of this proposed module.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "My main concerns of this work lie in two aspects. First, the technical novelty is rather limited since the backbone of the model basically follows its predecessor – GDC, including the design graph diffusion, the concept of neighborhood radius, and the heat kernel. It seems like the contribution of this work is merely the proposal of an adaptive version of choosing the neighborhood radius. Second, the authors claim that ADC can be utilized as a plug-in for all GNN layers. However, based on the design of ADC, it leverages the weighted self-multiplication of the Laplacian matrix to achieve the idea of graph diffusion, which makes it hard to apply in non-Laplacian matrix-based GNNs (e.g., GAT and GTN) (as also mentioned by authors in Section 4.1).\n\nThere are some additional comments:\n1.\tEq. (6) confuses me. It is not obvious how t equals the neighborhood radius for the heat kernel-based GDC. I double-checked the GDC paper and found no evidence of such a claim. Either a detailed explanation or a reference can be provided here.\n2.\tSince one of the claims in this work is the development of a novel GNN plug-in, it is not adequate of using only one task to demonstrate its ability. Other than node classification, experiments on different tasks (node clustering, link prediction) are expected.\n3.\tAs mentioned in Related Work, the graph diffusion convolution shares lots of commonalities with the conventional graph diffusion method on label propagation. Authors should also consider them [4], [8], [9] or demonstrate how they cannot be compared in this task.\n4.\tLegends in Fig. 5 are not consistent with the context.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no obvious negative societal impact found.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "Ggg7Zby0Ge5", "reviewer": "Reviewer_is4Q", "summary": "This paper proposes an adaptive diffusion convolution strategy that can automatically learn the optimal radius of message passing in graph neural networks and addresses the issue of selecting the optimal radius by hand-tuning. Additionally, this mechanism can serve as a plugin for graph neural networks and improve the model capacity and performance. Eventually, the paper validates this claim on the task of semi-supervised node classification.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "1.\tA novel mechanism to optimally select the neighborhood radius when performing graph diffusion convolution. The paper formulates choosing the radius as a bi-level optimization problem, and the optimization of the radius is performed on the validation set.\n2.\tIt breaks the convention that graph convolution should be based on neighborhood and extends to freely learn an optimal radius for each layer and each feature channel.\n3.\tThorough experiments are done to compare with the baseline GDC and explore the relationship between different radius updating mechanisms. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1.\tThere are two methods proposed in the paper, which are ADC and GDC. In the experimental session, comparisons are performed between them. Even though ADC is better than GDC in many cases, there are still some cases where GDC can excel. It would be great if the authors can offer some recommendations for these two methods.  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "50v7Wz9qvtt", "reviewer": "Reviewer_uhXN", "summary": "This paper proposes a strategy for adaptive diffusion convolution (ADC and GADC) that automatically learns the optimal neighborhood aggregation size, and it allows for learning a dedication propagate neighborhood for each GNN layer and each feature channel. They perform ablation studies and compares their method to related work on well-known benchmarks. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Originality: The ability to flexibly learn the neighborhood size is original and significant. This is an important contribution and plays very well into previous work as a natural and helpful extension. \n\nQuality: The paper shows high quality through-out, it’s well done and the experiments are useful and convincing. I would appreciate some kind of visualization of the learned diffusion, that would be interesting. Also, it would be nice to see this on other benchmarks dealing with graph classification and edge classification. \n\nClarity: Clear writing and structure. The flow is nice and the material easy to digest.\n\nSignificance: I like this work and think it’s a significant contribution. There is however a lot of related work that is dealing with similar problems and I don’t know if there is something that they’ve missed citing and that’s very similar. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "They address it adequately.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method called adaptive graph diffusion convolution (ADC), which can adaptively decide the neighborhood size for each layer and feature channel. The proposed method can be plugged in to any GNN frameworks. The experimental studies have demonstrated the superiority of the proposed module. The reviewers were split in the beginning, with concerns about novelty etc. After receiving a strong rebuttal from authors, including additional experiments, two reviewers have raised their scores to reflect their satisfaction to the rebuttal. In the end, the reviewers have reached consensus to accept this paper.
Decision: Accept (Poster)