Do We Need Anisotropic Graph Neural Networks?
Authors: Shyam A. Tailor
Felix Opolka
Pietro Lio
Nicholas Donald Lane
Venue: ICLR 2022 Poster (2022)
Keywords: graph neural networks
efficiency
latency reduction
memory reduction
architecture design
benchmarking
hardware-aware

Abstract: Common wisdom in the graph neural network (GNN) community dictates that anisotropic models---in which messages sent between nodes are a function of both the source and target node---are required to achieve state-of-the-art performance. Benchmarks to date have demonstrated that these models perform better than comparable isotropic models---where messages are a function of the source node only. In this work we provide empirical evidence challenging this narrative: we propose an isotropic GNN, which we call Efficient Graph Convolution (EGC), that consistently outperforms comparable anisotropic models, including the popular GAT or PNA architectures by using spatially-varying adaptive filters. In addition to raising important questions for the GNN community, our work has significant real-world implications for efficiency. EGC achieves higher model accuracy, with lower memory consumption and latency, along with characteristics suited to accelerator implementation, while being a drop-in replacement for existing architectures. As an isotropic model, it requires memory proportional to the number of vertices in the graph ($\mathcal{O}(V)$); in contrast, anisotropic models require memory proportional to the number of edges ($\mathcal{O}(E)$). We demonstrate that EGC outperforms existing approaches across 6 large and diverse benchmark datasets, and conclude by discussing questions that our work raise for the community going forward. Code and pretrained models for our experiments are provided at https://github.com/shyam196/egc.

Published as a conference paper at ICLR 2022
Do WE NEED ANISOTROPIC GRAPH NEURAL NETWORKS?
Shyam A. Tailor
Felix L. Opolka 1.2
Pietro Liô"
Nicholas D. Lane
Department of Computer Science and Technology, University of Cambridge
2 Invenia Labs, Cambridge, UK
3 Samsung AI Center, Cambridge, UK
ABSTRACT
Common wisdom in the graph neural network (GNN) community dictates that anisotropic models-in which messages sent between nodes are a function of both the source and target node-are required to achieve state-of-the-art perfor- mance. Benchmarks to date have demonstrated that these models perform better than comparable isotropic models where messages are a function of the source node only. In this work we provide empirical evidence challenging this narra- tive: we propose an isotropic GNN, which we call Efficient Graph Convolution (EGC), that consistently outperforms comparable anisotropic models, including the popular GAT or PNA architectures by using spatially-varying adaptive filters. In addition to raising important questions for the GNN community, our work has significant real-world implications for efficiency. EGC achieves higher model ac- curacy, with lower memory consumption and latency, along with characteristics suited to accelerator implementation, while being a drop-in replacement for exist- ing architectures. As an isotropic model, requires memory proportional to the number of vertices in the graph (O(V)); in contrast, anisotropic models require memory proportional to the number of edges (O(E)). We demonstrate that EGC outperforms existing approaches across large and diverse benchmark datasets, and conclude by discussing questions that our work raise for the community go- ing forward. Code and pretrained models for experiments are provided
https:/ https://github..om gwthtg..hhhho.. com
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as an effective way to build models over arbitrarily structured data. For example, they have successfully been applied to computer vision tasks: GNNs can deliver high performance on point cloud data (Qi et al., 2017) and for feature matching across images (Sarlin et al.] 2020). Recent work has also shown that they can be applied to physical simulations (Praff et al. 2020, Sanchez-Gonzalee et al. 2020). Code analysis is another application domain where GNNs have found success (Guo et al. 2020 Allamanis et al. 2017).
In recent years, the research community has devoted significant attention to building more expres- sive, and better performing, models process graphs. Efforts to benchmark GNN models, such as Open Graph Benchmark (Hu et al. 2020), or the work by Dwivedi et al. (2020). have attempted to more rigorously quantify the relative performance of different proposed architectures. One common conclusion-explicae stated by Dwivedi et al. (2020) that anisotropi models, in which mes- sages sent between nodes are function of both the source and target node, the best performing models. By comparison, isotropic models, where messages are a function of the source node only, achieve lower accuracy, even if they have efficiency benefits over comparable anisotropic models. Intuitively, this conclusion is satisfying: anisotropic models are inherently more expressive, hence we would expect them to perform better most situations. Our work provides surprising chal- lenge to this wisdom by providing an isotropic model, called Efficient Graph Convolution (EGC),
"Corresponding author. Contact at sat 620 ac. uk Definition from Dwivedi al. 2020). Equal attentional & message passing from Bronstein et al.
2021

---

Published as a conference paper at ICLR 2022
Anisotropic
Isotropic
f(x, m)
f(x,b) b)
S(a)
S(b)
X
X
f cx)
f(x, di
f(c)
f(d)
Messages are functions source and target nodes and honce must he materialized
Messages functions source only: propagation be implemented using matrix multiplication-sny appronches
Figure 1: Many GNN architectures (e.g. GAT (Veličković et al. 2018 PNA (Corso et al. 2020 incorporate sophisticated message functions to improve accuracy (left). This problematic as we must materialize messages, leading to (EE) memory consumption and OPs to calculate messages; these dataflow patterns are also difficult to optimize for at the hardware level. This work demon- strates that (right) and improve performance over existing GNNs.
simple message functions, requiring only OVV) memory consumption
that outperforms comparable anisotropic approaches, including the popular GAT (Veličković al. 2018) and PNA (Corso et al. 2020) architectures.
In addition to providing surprising empirical result for the community, work has significant practical implications for efficiency, as shown in Figure As EGC is an isotropic model achieving high accuracy,
take advantage of the efficiency benefits offered by isotropic models without having to compromise on model accuracy. We have seen memory consumption and latency for state-of-the-art GNN architectures increase OEE) in recent years, due to state-of-the-art models incorporating anisotropic mechanisms to boost accuracy. EGC reduces the complexity to O(V), delivering substantial real-world benefits, albeit with the precise benefit being dependent on the topology of the graphs the model is applied to. The reader should note that our approach can also be combined with other approaches for improving the efficiency of GNNs. For example, common hardware-softwarr co-design techniques include quantization and pruning (Sze et al. (2020) could be combined with this work, which proposes an orthogonal approach of improving model efficiency by improving the underlying architecture design. We also note that our approach can be combined with graph sampling techniques (Zeng et al. 2019 Hamilton et al., 2017 Chen et al. 2018a) to improve scalability further when training graphs with millions, billions, of nodes.
Contributions (1) We propose new GNN architecture, Efficient Graph Convolution (EGC), and provide both spatial and spectral interpretations for it. (2) We provide rigorous evaluation of our architecture across 6 large graph datasets covering both transductive and inductive use-cases, and demonstrate that EGC consistently achieves better results than strong baselines.
(3) We pro- vide several ablation studies to motivate the selection of the hyperparameters in our model. (4) We demonstrate that our model simultaneously achieves better parameter efficiency, latency and mem- ory consumption than competing approaches. Code and pre-trained models for our experiments (including baselines) can be found at hhtps: github.tbbb.... com/ shyaml 96 /6// At time of publication, EGC has also been upstreamed to Torch Geometric (Fey & Lenssen 2019).
2 BACKGROUND
2.1 BARDWARR--SOFTWAR CO-DESIGN FOR DEEP LEARNING
Several of the popular approaches for co-design have already been described in the introduction: quantization, pruning, and careful architecture design are all common for CNNs and Transform- ers (Vaswani et al.) 2017) 7). In addition to enabling better performance to be obtained from general purpose processors such as CPUs and GPUs, these techniques are also essential for maximizing the return from specialized accelerators: while it may be possible to improve performance over time due to improvements in CMOS technology. further improvements plateau without innovation the algorithmic level (Fuchs & Wentzlaff 2011).. As neural network architecture designers, we cannot simply rely improvements in hardware make our proposals viable for real-world deployment.
2

---

Published as a conference paper at ICLR 2022
2.2 GRAPH NEURAL NETWORKS
Many GNN architectures can be viewed as a generalization of CNN architectures to the irregular domain: as in CNNs, representations at each node are built based on the local neighborhood using parameters that are shared across the graph. GNNs differ as we cannot make assumptions about the the size of the neighborhood, the ordering. One common framework used to define GNNs is the message passing neural network (MPNN) paradigm (Gilmer et al.) (017). A graph G = (V. has node features X RN adjacency matrix A R and optionally D-dimensional edge features E E E We define a function & that calculates messages from node u to node v, a differentiable and permutation-invarian aggregator O, and an update function 7 calculate representations at layer + 1:
(JEN()) (o()) (6) h,?) )l, Propagation rules for baseline architecture are provided in [ with further details supplied in Tables5jin the Appendix.
h = 7(2 (1)
Relative Expressivity of GNNs Common wisdom in the research community states that isotropic GNNs are less expressive than anisotropic GNNs; empirically this is well supported by benchmarks. Brody et al. (2022) prove that GAT' models can be strictly more expressive than isotropic models. Bronstein et al. (202T) ) also discuss the relative expressivity of different classes of GNN layer, and argue that convolutional (also known as isotropic) models are well suited to problems leveraging homophily] in the input graph. They further argue that attentional, or full message passing, models are suited to handling heterophilous problems, but they acknowledge the resource consumption and trainability of these architectures may be rooibitive--sspccillly in the case of full message passing.
Scaling and Deploying GNNs While GNNs have seen success across range of domains, there remain challenges associated with scaling and deploying them. Graph sampling is one approach to scaling training for large graphs models which will not fit in memory. Rather than training over the full graph, each iteration is run over a sampled sub- graph; approaches vary in whether they sample node-wise wise (Hamilton et al. 2017)) layer-wise (Chen et al. (201 Sal Huang et al. 2018), or sub- graphs (Zeng et al. 2019:CChing et al. 2019). Alternatively systems for distributed GNN training have been proposed (Jia al. (020) to scale training beyond the limits of single accelerator. Some works have proposed architectures that are designed to accommodate scaling: graph-augmented MLPs, such SIGN (Rossi et al. 2020), explicitly designed
shallow architecture, as all the graph operations are done as a pre-processing step. Other work includes applying neural archi- tecture search (NAS) to arrange existing GNN layers (Zhao et al.. 2020)), or building quantization techniques for GNNs (Tailor et al. (021)) Finally, a recent work has shown that using memory- efficient reversible residuals (Gomez et al.
2017) for GNNs (Li et al. 2021) enables us to train far deeper and larger GNN models than before, thereby progressing the state-of sfate-of-the the-arrt accuracy.
Why Are Existing Approaches Not Sufficient? is worth noting that many of these approaches have significant limitations that we aim to address with our work. Sampling methods are often ineffective when applied to many problems which involve model generalization to unseen graphs common use-case for GNNs. We evaluated a variety of sampling approaches and observed that even modest sampling levels, which provide little benefit to memory or latency, cause model performance to decline noticeably. In addition, these methods do not accelerate the underlying GNN, hence they may not provide any overall benefit to inference latency. There is also no evidence that we are aware of that graph-augmented MLPs perform adequately when generalizing to unseen graphs; indeed, they are known to be theoretically less expressive than standard GNNs (Chen et al. 2021). We also investigated this setup, and found that these approaches do not offer competitive accuracy with state-of-thc-at approaches. Experiment details and results, along with further discussion of the limitations of existing work, is provided in Appendix B
In summary, our work on efficient GNN architecture design is of interest to the community for two reasons: firstly, it raises questions about common assumptions, and how we design and evaluate GNN models; secondly, our work may enable us to scale our models further, potentially yielding improvements in accuracy. In addition, for tasks where we need to generalize to unseen graphs, such as code analysis or point cloud processing, we reduce memory consumption and latency, thereby enabling us to deploy our models to more resource-constrained devices than before. We note that efficient architecture design can be usefully combined with other approaches including sampling, quantization, and pruning, where appropriate.
Homophily means that if nodes are connected, then they have high similarity
3

---

Published as a conference paper at ICLR 2022
wf
xx 9
2
Run scparate graph filters parameterised by O₁ over graph
Apply per-node weightings w(( each basis filter
Figure 2: Visual representation of our EGC-S layer. In this visualization have basis filters (i.c. B = 3), which are combined using per-node weightings w. This simplified figure does not show the usage of heads, multiple aggregators, used by EGC-M.
3 OUR ARCHITECTURE: EFFICIENT GRAPH CONVOLUTION (EGC)
In this section describe approach, and delay theoretical analysis to the next section. We present two versions: EGC-S(ingle), using a single aggregator, and EGC-M(ulti) which generalizes approach by incorporating multiple aggregators. Our approach is visualized in Figure
3.1 ARCHITECTURE DESCRIPTION
For layer with in-dimension of and out-dimension of we use B basis weights O₁ E F'x We compute the output for node i by calculating combination weighting coefficients w(i) RB per node, and weighting the results of each aggregation using the different basis weights O₁ The output for node is computed in three steps. First, we perform the aggregation with each set of basis weights 9 Second, we compute the weighting coefficients w( +x + R for each node where & E BxF and b E B are weight and bias parameters for calculating the combination weighting coefficients. Third, the layer output for node i is the weighted combination of aggregation outputs:
(
( W
Σ
alx,)))xx0)
JEN())
where (ii,j) is some function of nodes and j. and N(i)) denotes the in-neighbours of i. A popular method pioneered by GAT (Veličković et al. (2018) to boost representational power is to represent a using a learned function of the two nodes' representations. While this enables anisotropic treatment of neighbors, and can boost performance, it necessarily results in memory consumption of (E)) due to messages needing to be explicitly materialized, and complicates hardware implementation for accelerators. If we choose representation for a that is not function of the node representations such aii,j)
to recover the add aggregator used by GIN (Xu al., 2019). ati,
1/ / (ied (j) recover symmetric normalization used by GCN (Kipf & Welling 2017
then we can implement our message propagation phase using sparse matrix muluplication (SpMM), and avoid explicitly materializing each message, even for the backwards pass. In this work, we assume cx(i.) j) to be symmetric normalization as used by GCN unless otherwise stated; we use this normalization as is known to offer strong results across variety of tasks; more formal justification provided in section 4.2
Adding Heads as a Regularizer We can extend our layer through the addition heads, as used in architectures such GAT or Transformers (Vaswani al. (017). These heads share the basis weights, but apply different weighting coefficients per head. We find that adding this degree of freedom aids regularization when the number of heads (H) is larger than B, bases discouraged from specializing (see section without requiring the integration additional loss terms into the optimization hence requiring changes to code for downstream users. To normalize the output
4

---

Published as a conference paper at ICLR 2022
dimension, change the basis weight matrices dimensions to F operator, and making the use of symmetric normalization explicit, we obtain the EGC-S layer:
1f x F. Using || as the concatenation
Σ R.b
O5x
(EN( deg(i)deg(j)
EGC works by combining basis matrices. This idea was proposed in R-GCN (Schlichtkrull et al, 2018) to handle multiple edge types; Xu et al. (2021) can be viewed as generalization of this approach to point cloud analysis. In this work we are solving a different problem to these works: we interested in designing efficient architectures, rather than ways to handle edge information.
3.2 BOOSTING REPRESENTATIONAL CAPACITY
Recent work by Corso et al. (2020) has shown that using only a single aggregator is sub-optimal: instead, it is better to combine several different aggregators. In Equation (2) we defined our layer to use only symmetric normalization. To improve performance, we propose applying different aggre- gators to the representations calculated by @xx(1) The choice of aggregators could include different unweighted addition, opposed symmetric nor-
variants of summation aggregators e.g. malization that was proposed in the previous section. Alternatively, we can use aggregators such as stddev, min max which are not based on summation. is also possible gators proposed by Beaini et al. (2021). however this enhancement is orthogonal to this work. If we have a of aggregators A, we can extend Equation
directional aggre-
(2) obtain our EGC-M layer:
(
11 4=1 DEA b=1
(E) R.
(EN())
where an aggregator. With this formulation, are reusing the same messages we have calcu- lated as before- but we are applying several aggregation functions to them at the same time.
Aggregator Fusion It would appear that adding more aggregators would cause latency and mem- ory consumption to grow linearly. However, this is not true in practice. Firstly, since sparse op- erations are typically memory bound in practice, we can apply extra aggregators data that has already arrived from memory with little latency penalty. EGC can also efficiently inline the node- wise weighting operation inference time, thereby resulting in relatively little memory consump- tion overhead. The equivalent optimization is more difficult to apply successfully to PNA due to the larger number of operations per-node that must be performed during aggregation, caused by scaling functions being applied each aggregation, before all results concatenated and a transformation applicd. More details, including profiling and latency measurements, can be found Appendix D
INTERPRETATION AND BENEFITS
This section will explain our design choices, and why they are better suited the hardware. We emphasize that our approach does not directly correspond to attention.
4.1 SPATIAL INTERPRETATION NODE- WISE WRIGHT MATRICES
In our approach, each node effectively has its own weight matrix. We can derive this by re- arranging eq. (2) by factorizing the O, terms out of inner sum:
JENTOUL V deg(i))))g()) (
Σ
Varying per Node
Computable via SpMM
In contrast, GAT shares weights, and pushes complexity into the message calculation phase by calculating per-message weightings. MPNN (Gilmer et al. (017)) and PNA (Corso al. 2020)
further increase complexity by explicitly calculating each message resulting in substantial latency
overhead due to the number of dense operations increasing by roughly [ Specifically, have:
[
5

---

Published as a conference paper at ICLR 2022
H
Σ (EN())
(0) MPNA
U(x
(8)
M(x ()
Y GAT
je.(())
Explacit Message Calculation
Shared Weights
Calculated Message Weighting
From an efficiency perspective we observe that our approach of using SpMM has better character- istics due to it requiring only ((V) memory consumption-no messages must be explicitly mate- rialized to use SpMM. We note that although it is possible to propagate messages for GAT with SpMM, there no way to avoid storing the weightings during training they are needed for back- propagation, resulting in (EE) memory consumption. We also note that fusing the message and aggregation steps for certain architectures may be possible at inference time, but this is difficult pattern for hardware accelerators to optimize for.
Relation To Attention Our method is not directly related to attention, which relies upon pairwise similarity mechanisms, and hence results in (EE) cost when using the common formulations. Alternatives to attention- based Transformers proposed by Wu al. (20T9a) are closer analogue to technique, but rely upon explicit prediction of the per- tir-tiiestep weight matrix. This approach is not viable for graphs, as the neighborhood size is not constant.
4.2 SPECTRAL INTERPRETATIONS LOCALISED SPECTRAL FILTERING
We can also interpret our EGC-S layer through the lens of graph signal processing (Sandryhaila & Moura 2013). Many modern graph neural networks build on the observation that the convolution operation for the Euclidean domain when generalised to the graph domain has strong inductive biases: it respects the structure of the domain and preserves the locality of features by being an operation localised in space. Our method can be viewed as a method of building adaptive filters for the graph domain. Adaptive filters are common approach when signal or noise characteristies vary with time or space; for example, they are commonly applied in adaptive noise cancellation. Our approach can be viewed constructing adaptive filters by linearly combining learnable filter banks with spatially varying coefficients.
The graph convolution operation typically defined on the spectral domain as filtering the input signal x E I2 on a graph with N nodes with filter go parameterized by 0. This requires translating between the spectral and spatial domain using the Fourier transform. As on the Euclidean domain, the Fourier fransform on the graph-domain is defined as the basis decomposition with the orthogonal eigenbasis of the Laplace operator, which for a graph with adjacency matrix E N is defined
as L D A, where D is the diagonal degree matrix with Dj = Σ Aij- The Fourier transform of signal
R then is F(x) U where L UAUT, with orthogonal eigenvector matrix U R x N and diagonal eigenvalue-matee matrix A E N-N The result of a signal x filtered by ge is where the second equality holds if the Taylor expansion of go exists.
y go [L)x x UAo(AAU
Our approach corresponds to learning multiple filters and computing a linear combination of the resulting filters with weights depending on the attributes of each node locally. The model therefore allows applying multiple filters for each node, enabling us to obtain a spatially-varying frequency response, while staying far below OEE) in computational complexity. Using linear combination of filters, the filtered signal becomes y = Em Wi @ ge. (L)x, where wa E RV are the weights of filter à for each of the N nodes in the graph. If parameterize polynomials as used by Kipf & Welling (017)) our final expression for the filtered signal becomes Y = E Wo C (D AAD x)x0, where Á = A + Iy is the adjacency matrix with added self-loops and D is the diagonal degree matrix of Á as defined earlier. This justifies the symmetric normalization aggregator we chose in Equation (2).
filter using first-order Chebyshev
Cheng et al. (202 proposed approach for localized filtering. However, their approach does not generalize to unseen topologies or scale to large graphs as it requires learning the coefficients of several filter matrices S₁. of size N N. Our approach does not suffer from these constraints.

---

Published as a conference paper at ICLR 2022
ZINC (MAR
CIFAR
MAHHV (ROC-AEC
CF
(Ac..
Architecture
Propegation
Memory
Graph. Clucrtction
Greph Clocticator
Nod:
Regrastion
Coodiicano
Chasticato
GCN
yd EE
((V)
0.499 - 0.006
55.71 + 0:38
76.14 1.29
0,1480 + 0.0018
71.92 0.21
GIN
foll +oje
((V)
0.387
0.015
55.26
1.53
76112 + 1.35
0,1481 + 0,0027
67.33 + 1.47
GraphSAGE
311 8,x"
①. e,x0
O(V)
0.468
0.1453 0,0028
71.73 0.26
GAT'
((8)
0.75
0.007
64,22 + 0.46
77.17 + 1.37
0.1513 + 0,0011
+71.81 0.233
GATV2
0.447
0.015
67.48 0.53
77.15 4: 1.55
0,1537 4: 0.0022
=71.87 1:43
MPNN-Sum
y10 Gipel E, M(xl") win))
((RR
0.381
75.19
3.57
0.1430
-66.11
MPNN-Max
y69
0(8)
0.468
0.002
69.70
0.55
77.07 + 1.37
0,1552 + 0,0022
*71.02 #:221
PNA
O(E)
0.320
0.032
70.21
1: 0.15
79.05 1: 1.32
= -0.1570 +: 0.0032
+ =71.21 4: 0.30
BGC& (churs)
Eiuasion 7
(1V)
0. 364
0.020
66.92
0.37
77.44 + 1.08
0.1528 0,0025
72.21 + 0.17
RGCM (CAar))
Squano
0(V)
0.281
0.007
71,03
0.42
78.18 + 1.53
0.1595
0,0019
71.96 + 0.225
Table I: Results (mean + standard deviation) for purameter-normalizze models run on datasets. Details of the specific aggregators chosen per dataset and further experimental details can be found in the supplementary material. Results marked with * ran out of memory on 1IGB 1080Ti and 2080Ti GPUs EGC obtains best performance on 4 of the tasks, with consistently wide margins.
5 EVALUATION
5.1 PROTOCOL
We primarily evaluate our approach on datasets taken from recent works on GNN henchmarking. We use ZINC and CIFAR-10 Superpixels from Dwivedi et al. (2020) and Arxiv, MolHIV and Code from Open Graph Benchmark (Hu et al.] 2020). These datasets cover a wide range of domains, cover both transductive and inductive tasks, and are larger than datasets which are typically used in
GNN works. We use evaluation metrics and splits specified by these papers. Baseline architectures
chosen reflect popular cineral-purposs choices (Kipf & Welling 2017 Xu et al., 2019: Hamilton
cet al.
2017 Veličković et al. 20188) Gilmer et al. 2017), along with the state-of-the-ar PNA (Corso
al.
2020 and GATv2 (Brody al.] (022) architectures.
In order to provide a fair comparison we standardize all parameter counts, architectures and opti- mizers in our experiments. All experiments were run using Adam (Kingma & Ba 2014). Further details on how we ensured a fair evaluation can be found in the appendix.
We do not use edge features in our experiments as for most baseline architectures there exist no standard method to incorporate them. We do not use sampling, which, as explained in Section 2.2 ineffective for 4 datasets; for the remaining dataset, Arxiv, we believe it is not in the scientific interest to introduce an additional variable. This also applies to GraphS where we do not use the commonly applied neighborhood sampling. All experiments were run 10 times.
5.2
MAIN RESULTS
Our results across the tasks are shown in Table [ We draw attention the following observations:
EGC-S is competitive with anisotropic approaches. We outperform GAT(y1) and MPNN-Sum on all benchmarks, despite our resource efficiency. The clearest exception is MPNN-Max on CIFAR & Code, where the max aggregator provides a stronger inductive bias. We observe that GATv2 improves upon GAT, but does not clearly outperform EGC.
* EGC-M outperforms PNA. The addition of multiple aggregator functions improves per- formance of EGC to beyond that obtained by PNA. We hypothesize that our improved performance over PNA is related to PNA's 'ss reliance on multiple degree-scaling transforms. While this approach can boost the representational power of the architecture, we believe that it can result in tendency to overfit to the training set.
EGC performs strongly without running out of memory. We observe that EGC is one of only three architectures that did not exhaust the VRAM of the popular Nvidia 1080/2080Ti GPUs, with 1IGB VRAM, when applied to Arxiv: we had to use an RTX 8000 GPU with 48GB VRAM to run these experiments. PNA, our closest competing technique accuracy- wise, exhausted memory on the Code benchmark as well. Detailed memory consumption figures provided in Table 4
7

---

Published as a conference paper at ICLR 2022
0.400
0.46
Bassss
Heden
20:011
2- 025
Hibour:
422023
Hibben:
22.0%
H123a
21.015
Mean Absolute Enro (M (MAEE)
2:0:22
020
52.014
0.2
20.04
18cdkr:
19200::
raSSer:
1168811
Besos
0.390
-0.023
+22011
22,000
21.016
0.40
180DeM:
Hladbe:
11555
20:020
024
2-2022
2-2.22
20,022
Iiddan:
11:00:1:3
P920ur:
HIADUT:
Meddum:
0.300
Fidder:
20011
11:dem::3 32
011
cdlee
2-2 029
1icole::
2-0 022
18:
+1.027
0.34
16
Heads
Heads
(a) Constant parameter count (100k)
(b) Constant hidden dimension (128)
Figure 3: Study over the number of heads (H) and bases (B). Study run on ZINC dataset with EGC-S. Metric is MAE (mean + standard deviation): lower is better. We study keeping the total parameter count constant, and fixing the hidden dimension. Each experiment was tuned individually. Setting B H does not necessarily improve performance due the risk of overfitting, and forces the usage of smaller hidden dimension to retain a constant parameter count.
Overall, EGC obtains the best performance on 4 out of the main datasets; on the remaining dataset (MolHIV), EGC is the second best architecture. This represents significant achievement: our architecture demonstrates that we do not need to choose between efficiency and accuracy.
5.3 ADDITIONAL STUDIES
How Should Heads and Bases be Chosen? To understand the trade-off between the number of heads (H) and bases (B), we ran an ablation study on ZINC using EGC-S; this in shown in Figure
The relationship between these parameters non-trivial. There are several aspects consider: (1) increasing H and B means that we spend more of our parameter budget to create the combinations, which reduces hidden dimension as shown in Figure 3 This exacerbated if we use multiple aggregators: our combination dimension must be H B A.. (2) Increasing B means we must reduce the hidden size substantially, since it corresponds to adding more weights of size F' F. (3) Increasing H allows us to increase hidden size, since each basis weight becomes smaller. We see in Figure 3 that increasing B beyond H does not yield significant performance improvements: we conjecture that bases begin specializing for individual heads; by sharing, there is a regularizing effect, like observed in Schlichtkrull al. (2018). This regularization stabilizes the optimization and we observe lower trial variance for smaller B.
We advise B H or B H. We find H = 8 be effective with EGC-S; for EGC-M, where more parameters are spent on combination weights, we advise setting // = 4. This convention is applied consistently for Table [ full details are supplied the appendix and code.
Should The Combination Weightings (w) Be Activated?
Activation
EGC-S
EGC-M
Any activation function will shrink the space the per-node weights (0) can lie in, hence we would expect it to harm perfor- mance; this is verified in Table 2 Activating may improve training stability, but we did not observe to be an issue in our experiments. Another issue is that different aggregators re- sult in outputs with different means and vari- ances (Tailor et al. 2021), hence they need to be scaled by different factors to be combined.
Identity
0.364 + 0.020
0.281 + 0.007
Hardtanh Sigmoid Softmax
0.435 + 0.010
0.293 + 0.013
0.366 + 0.008
0.303 + 0.016
0.404 + 0.010
0.307 + 0.013
Table Activating the combination weightings w harms performance. Run on ZINC; lower is better.
Applying EGC to Large-Scale Heterogeneous Graphs We evaluated EGC on the heteroge- neous OGB-MAG dataset, containing 2M nodes and 21M edges. On homogeneous version of the graph, we exceed the baselines' performance by 1.5-2%; we experiment with both symmetric nor- malization (EGC-S) and the mean aggregators demonstrate that the mechanism utilized by EGC
8

---

Published as a conference paper at ICLR 2022
is effective, regardless of which aggregator provides the stronger inductive bias for the dataset. Our architecture can be expanded to handle different edge types, yielding the R-EGC architecture which improves performance over R-GCN by 0.9%. We expect that accuracy can be further improved by using sampling techniques to regularize the optimization, or using pretrained embeddings; however, adding these techniques makes comparing the results more difficult as it is known that sampling techniques can affect each architecture's 's performance differently (Liu et al. 2020
5.4 MEMORY AND LATENCY BENCHMARKS
We now assess our model's resource efficiency. For CPU measurements used an Intel Xeon Gold 5218 and for GPU we used an Nvidia RTX 8000.
Method
Test Accuracy % t
MLP
26.92 + 0.26
GCN
30.43 + 0,25
Aggregator Fusion We evaluated aggregator fu- sion across several topologies on both CPU and GPU. For space reasons, we leave full details to Appendix In summary, we observe that using 3 aggregators standard SpMM incurs addi- tional overhead of only 14% enabling us to im- prove model performance without excessive com- putational overheads at inference time.
GraphSAGE-MMan
31.53 + 0.15
EGC-S
32.13 + 0.73
EGC (+ Mean)
33.22 0.50
R-GCN (Full Batch)
46.29 + 0.45
R-EGC (Full Batch)
47.21 + 0.40
Table 3: EGC can be applied applied to large scale heterogeneous graphs, outperforming R- GCN by 0.9%.
End-to-End Latency We provide latency and memory statistics for parameter-normalizze mod- els in Table 4 We draw attention to how slow and memory-intensive the (FF) models are for training and inference. The reader should note that the inference latency and memory consump- tion for MPNN and PÑA rises by 6-7x rela- [E] tive to EGC, corresponding to the large [V ra- tio for Arxiv. EGC-M offers substantially lower latency and memory consumption than its near- est competitor, PNA, however the precise bene- fit will be dataset-dependent. Extended results can be found in Appendix E., including results for accuracy-normale models on Arxiv, which fur- ther demonstrate EGC's resource efficiency.
Training Memory (MB)
GPU Training Latency (m))
GPU Latency (ms)
GEN
1906
1593 46
38.2 0.1
GIN
1756
155 : 3.9
35.2 0.1
GragSAGG
1352
113.9 + 5.4
25,1 0.4
GAT
10841
324.3 L.2
129.2 0.3
GATv2
14134
341
MPNN
MPNN-Mux
14623
797.8
258.2
PNA
14533
892.7 1.1
305.7 1: 0.5
RGC-S
2430
177.7
222
0.13+001
EGC-M
4068
220.9
0.6
4..2+00.3
Table 4: Memory and latency statistics for parameter-normalized models (used in ta- ble D on Arxiv. Note that EGC-M memory consumption and latency can be reduced with aggregator fusion at inference time.
DISCUSSION AND CONCLUSION
How Surprising Are Our Results? We observed that it was possible design isotropic GNN that is competitive with state-of-the-art anisotropic GNN models on 6 benchmarks. This result con- tradicts common wisdom in the GNN community. However, our results may be viewed as part of a pattern visible across the ML community: both the NLP and computer vision communities have seen works indicating that amisotropy offered by Transformers may not be necessary (Tay et al.) 2021 Liu et al. 2022), consistent with our observations. It is worth asking why we observe our re- sults, given that they contradict properties that have been theoretically proven. We believe that there are a variety of reasons, but the most important is that most real world datasets do not require the theoretical power these more expressive models provide to achieve good results. In particular, many real world datasets are homophilous: therefore simplistic approaches, such as EGC, can achieve high performance. This implies that the community should consider adding more difficult datasets to standard benchmarks, such those presented in Lim et al. (2021) and Veličković et al. (2021).
Our proposed layer, EGC, can be used as a drop-in replacement for existing GNN layers, and achieves better results across 6 benchmark datasets compared strong baselines, with substantially lower resource consumption. Our work raises important questions for the research community. while offering significant practical benefits with regard to resource consumption. We believe the next step for our work is incorporation of edge features e.g. through line graphs (Chen et al. 2020b) or topological message passing (Bodnar et 202T)
9

---

wtw.ii/wwnee//ooummdd-iii.t Published as a conference paper at ICLR 2022
ACKNOWLEDGEMENTS
This work was supported by the UK's Engineering and Physical Sciences Research Council (EP- SRC) with grant WISS001530/ (the MOA project) and the European Research Council (ERC) via the REDIAL project (Grant Agreement ID: 805194). FLO acknowledges funding from the Huawei Studentship the Department of Computer Science and Technology of the University of Cambridge.
The authors would like to thank Ben Day, Javier Gemandez-Marquee Chaitanya Joshi, Titouan Parcollet, Petar Veličković, and the anonymous reviewers who have provided comments on earlier versions of this work.
ETHICS STATEMENT
The method described in this paper is generic enough that it can be applied to any problem GNNs are applied to. The ethical concerns associated with this work are related to enabling more efficient training and deployment of GNNs. This may be positive (drug discovery) negative (surveillance), but these concerns are inherent to any work investigating efficiency for machine learning systems.
REPRODUCIBILITY STATEMENT
We have supplied the code required to regenerate our results, along with the hyperparameters quired. In addition, we supply pre-trained models. Resources associated with this paper can be found at httttttss//gtthhbee com shyaml 96/egc
REFERENCES
Miltiadis Allamanis, Mare Brockschmidt, and Mahmoud Khademi. Learning represent programs with graphs. arXiv preprint arXiv: 2017.
Gene M Amdahl. Validity of the single processor approach achieving large scale computing capabilities. In Proceedings of the April 18-20, 1967, spring joint computer conference, pp. 483 485, 1967.
Dominique Beaini, Saro Passaro, Vincent Létourneau, William L. Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks, 2021.
Cristian Bodnar, Fabrizio Frasca, Yu Guang Wang, Nina Otter, Guido Montúfar, Pietro Liò, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks, 2021.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive graph attention networks? In Interna- lional Conference on Learning Representations, 2022. URL https::/ htt.tirreiieeeeeeeeeeeeee Forump1G=F72xiimxx7]]
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković, Geometric deep learning: Grids, groups, graphs, geodesics, and gauges, 2021.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 1801. 2018a.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented [mlp]s. In International Conference Learning Representations, 2021. URL https://
Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Meghan Cowan, Haichen Shen, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Tym: An automated end-to-end optimizing compiler for deep learning. In Proceedings of the 13th USENIX Conference on Operating Systems Design and Implementation, OSDI' 18, pp. 579-594, USA, 2018b. USENIX Association. ISBN 978 177199977747.
10

---

Published as a conference paper at ICLR 2022
Xiaobing Chen, Yuke Wang, Xinfeng Xie, Xing Hu, Abanti Basak, Ling Liang. Mingyu Yan, Lei Deng, Yufei Ding, Zidong Du, Yunji Chen, and Yuan Xie. Rubik: A Hierarchical Architecture for Efficient Graph Learning. arXiv:2009.1244 [es], September 2020a. URL http://arxi>: arXiv: 12495.
hrg/abs/2009. 12495
Zhengdao Chen, Xiang Li, and Joan Bruna. Supervised community detection with line graph neural networks, 2020b.
Xiuyuan Cheng, Zichen Miao, and Qiang Qiu. Graph convolution with low-rank learnable local filters. In International Conference on Learning Representations, 2021.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh, Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Intel Corporation. Intel@ 64 and ia-32 architectures optimization reference manual.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal Neighbourhood Aggregation for Graph Nets. arXiv:2004.055 05 [es, stat], June 2020. URL arXiv: 0004005718.
http://arxixy www.orggabao. abs abs//004 05718
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. 1:Xiv:2003.0096 [cs, stat), July 2020. URL http:
00982
arXiv: 2003.00982.
Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with Py PyTch Geometric, 5 2019. URL https: http:/ttt:://tttb.coo/////// http://hhhh...coo//o//e/eettorro Seaerrcchh_mmttrriieee
Adi Fuchs and David Wentzlaff. The accelerator wall: Limits of chip specialization. In 2019 IEEE International Symposium High Performance Computer Architecture (IPPAA), pp. 1-14. IEEE, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pp- 1263-1272 PMLR, 2017.
Aidan N. Gomez, Mengye Ren, Raquel Urtasun, and Roger B. Grosse. The reversible residual network: Backpropagation without storing activations, 2017.
Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang. Shujie Liu, Long Zhou, Nan Duan, Jian Yin, Daxin Jiang, et al. Graphcodebert: Pre-training code representations with data flow. arXiv preprint 20xx:2009008666, 2020.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint arXiv: 1706.0//00602216 2017.
Weihua Hu, Mathias Fey, Marinka Zimik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00m 00667,, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. arXiv preprint arXiv: 1809vv1009.00 1809.08094.544 2018.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, seala- bility, and performance of graph neural networks with roc. Proceedings of Machine Learning and Systems, 2: 1878 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.660 69800 2014.
Thomas N. Kipf and Max Welling. Supervisee Classification with Graph Convolutional Net- works. In International Conference on Learning Representations, 2017.

---

Published as a conference paper at ICLR 2022
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers, 2021.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs, 2021.
Zhuang Liu, Hanzi Mao, Chao-Yure Yuan Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s, 2022.
Ziqi Liu, Zhengwei Wu, Zhiqiang Zhang, Jun Zhou, Shuang Yang, Le Song, and Yuan Qi. Bandit samplers for training graph neural networks, 2020.
Tobias Pfaff, Meire Fortunato, Alvaro Sanchez-Gonzales and Peter W Battaglia. Learning mesh- based simulation with graph networks. arXiv preprint arXiv:2010.03409, 2020.
Charles R Qi, Li Yi, Hao Su, and Leonidas J Guibas. Pointnet++: Deep hierarchical feature learning on point sets in a metric space. arXiv preprint arXiv:1706. 02-13,02223,.. 2017.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification, 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Fed- erico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. 198, 2020.
Alvaro Sanchez-Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Pe- ter W Battaglia. Learning to simulate complex physics with graph networks. arXiv preprint arXiv:2002.094000 2020.
Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs. IEEE transactions on signal processing, 61(7):1644-1656 2013.
Paul-Edouard Sarlin, Daniel DeTone, Tomasz Malisiewicz, and Andrew Rabinovich. Superglue: Learning feature matching with graph neural networks. In Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pp. 4938-4947, 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S Emer. Efficient processing of deep neural networks. Synthesis Lectures on Computer Architecture, 15(2):13341, 2020.
Shyam A. Tailor, Javier Hemandez-Marques, and Nicholas D. Lane. Degree-Quael Quantization- Aware Training for Graph Neural Networks. In International Conference on Learning Represen- tations, 2021.
Yi Tay, Mostafa Dehghani, Jai Gupta, Dara Bahri, Vamsi Aribandi, Zhen Qin, and Donald Metzler. Are pre-trained convolutions better than pre-trained transformers?, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In I. Guyon, U. V. Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neu- ral Information Processing Systems 30, pp. 5998 6008. Curran Associates, Inc., 2017. URL http::/
http:////pppe////atteetertrr-ese -luu-lll---eedd pdd
Petar Veličković, Adrià Puigdomênech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The clrs algorithmic reasoning bench- mark. 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
12

---

Published as a conference paper at ICLR 2022
Felix Wu, Angela Fan, Alexei Baevski, Yann N. Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions, 2019a.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr. au2, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks, 2019b.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How Powerful are Graph Neural Networks? arXiv:/810.0088: [cs, stat], February 2019. URL http:://axx....rrrr.. abs/ 1810. 00826 arXiv: 1810.00826.
Mutian Xu, Runyu Ding, Hengshuang Zhao, and Xiaojuan Qi. Paconv: Position adaptive convolu- tion with dynamic kernel assembling point clouds, 2021.
Mingyu Yan, Lei Deng, Xing Hu, Ling Liang, Yujing Feng, Xiaochun Ye, Zhimin Zhang, Dongrui Fan, and Yuan Xie. HyGCN: A GCN Accelerator with Hybrid Architecture. In 2020 IEEE Inter- national Symposium on High Performance Computer Architecture (HPCA), pp. 15-29, February 2020. doi: 10. WW09///CA445542200000000
ISSN: 2378-203X.
Carl Yang, Aydin Buluc, and John D. Owens. Design principles for sparse matrix multiplication on the gpu, 2018.
Haoran You, Tong Geng, Yongan Zhang. Ang Li, and Yingyan Lin. Gcod: Graph convolutional net- work acceleration via dedicated algorithm and accelerator co-design. In 28th IEEE International Symposium on Hlgh-Perffrmance Computer Architecture (HPCA 2022), 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. arXiv preprint (rXXv:1907.049311 2019.
Yongan Zhang, Haoran You, Yonggan Fu, Tong Geng, Ang Li, and Yingyan Lin. G-cos: Gnn- accelerator co-search towards both better accuracy and efficiency, 2021.
Yiren Zhao, Duo Wang, Xitong Gao, Robert Mullins, Pietro Lio, and Mateja Jamnik. Probabilistic dual network architecture search on graphs. arXiv preprint arXiv:2003.09667, 2020.
13

---

Published as a conference paper at ICLR 2022
Method
Propagation Rule
Memory
Notes
GCN Kipf &
2 Vanrsaaas) x
O(V)
Formally defined for undirected graphs with self-loops; moti- vated by graph signal processing.
Welling
GIN Xu al.
fel [1 e) > Seenm x!
O(V)
leurnalle function, typically parameterized MLP linear layer. may be lixed or leamne.
2019
GraphSAGE [amil
y Oxx!! ① Dearc 02x()
O(V)
i typically parameterized as mean or max.
Ion al. 2017
GAT VeliSkovi
ym ex(( (1) + Σ DyeNty (.y(x
O(E)
Attention
coefficients calculated using: ReLl "[ay" ex(")))
2018
Exeroouga exd (LoskyRe21 [ext0 (e detine multiplo attention heads and concatenate.
Common
GATv2 Brody al. 2022
yd ex.") ExEN(o and ex
O(E)
Similar to
GAT, but improve expressivity
with atlention 013
calcula-
tion
redelined
to
cap(a Lesky (9ix, 1x11))
Exescouti oxple Les MNl)]
MPNN Gilmer
yd Uxx! JENCO M x ee)))
O(E)
U. U.M typically defined as lincar layers acting concatenated features; @ may be any valid aggregator, typically sum or max.
ST al.. 2017
PNA
Corso
y U JeN( (xx
( x eg))
O(E)
Similar to MPNN, but with + defined to use 4 aegregatons (mcan, standard deviation, max, min) scaled by different functions of made degree, resulting in 12 different aggregations by default.
M 2020
Table 5: Propagation rules for general-purpose GNN architectures we compare against in this work; rules are provided using node-wise formulations. We evaluate against popular architectures, and recent proposal that has achieved state-of-the-an performance, PNA.
A FURTHER EXPERIMENT DETAILS
A.1 ENSURING FAIRNESS
We expand on our experimental protocol, with particular focus on describing measures that we took to ensure that the results we report are not unfairly biased towards EGC.
For EGC-S, we use H 8 and B 4, implied by our ablation for all experiments, with the single exception of OGB-Code, where we use H = B = 8. The benefit of using a smaller set of bases is that we can increase the hidden dimension, but this is not viable in this case since most of the 1 1M parameters in the model correspond to the token read-out layers, which quickly increases as the model hidden dimension grows. As shown by section [.3] if we cannot increase the hidden dimension, it is better to increase the bases. This is the only exception we make.
For EGC-M, we use H = B for all experiments. The main challenge aggregator selection, and this remains major challenge for our work. We were unable to find satisfactory technique for automated discovery of aggregator choices, hence we rely on heuristics to find them. We restrict ourselves to use 3 aggregators for each model (yielding 35 possible choices). In order to determine the aggregators, we use two heuristics: (1) aggregators should be "diverse" and (2) aggregators should be chosen based on inductive bias for task. Using these two rules, we try up to 3 possible choices of aggregators; all choices considered are shown in Table We note that while some choices do improve performance, our conclusions are not invalidated; also worth noting that is likely that better aggregator choices can be found.
A.2 CLUSTER DETAILS
Most of our experiments were run on several machines in our SLURM cluster using Intel CPUs and NVIDIA GPUs. Each machine was running Ubuntu 18.04. The GPU models in cluster were RTX 2080Ti and GTX 1080Ti. High-memory experiments were run on V100s in our cluster and an RTX 8000 virtual machine had access to.
14

---

Published as a conference paper at ICLR 2022
Dataset
Add
Mean
Symmetric Normalization
Max
Min
Std
Var
Result
Zinc
0.281 + 0.007
Zinc
0.284 1 0.045
CIFAR
71.03 + 0.42
CIFAR
70.05 + 1.14
MolHIV
78.19 + 1.54
MolHIV
77,40 + 1.02
MolHIV
77.98 + 1.65
Arxiv
/
71.96 + 0.23
Arxiv
70.59 + 0.67
Arxiv
70.38 + 0.76
Code-V2
0.1595 + 0.0019
Code-V V2
0.1572 = 0.0029
Code- V2
0.1578 = 0.0021
Table 6: Possible aggregators tried for EGC-M. Up to 3 combinations (from a possible 35) were tried, limited ourselves to always using 3 aggregators. Our conclusions do not change, and it likely that better results can be found with more optimal aggregator choices.
Model
ZINC (MAE !)
CIFAR (Acc. t)
MolHIV (ROC-AUC
Code- V2 (F1 ?)
GA-MLP
0.510 0.037
58.13 + 0.65
75.50 + 1.32
0.1485 + 0.0027
GCN
0.459 = 0.006
55.71 + 0.38
76.14 + 1.29
0.1480 + 0.0018
EGC-S
0.364 0.020
66.92 0.37
77.44 + 1.08
0.1528 0.0025
Table 7: Results of applying graph-augmented MLPs (GA-MLPs) to tasks requiring generalization to unseen graphs. We see that the performance is broadly similar to the corresponding GCN model- and far weaker than EGC-S, which uses the same aggregator. We also considered using the add aggregation on ZINC, and achieved 0.444 + 0.019. By comparison, the equivalent GIN model (which uses the add aggregation) achieved 0.387 + 0.015.
B LIMITATIONS OF EXISTING APPROACHES
As explained in the related work, existing approaches improving GNN efficiency have severe limitations. this section we elaborate upon them, and provide experimental evidence where nec- essary.
We first examine graph-augmented MLPs (GA-MI.Ps) to our knowledge there are few experimental results assessing the performance of these models when they applied to problems requiring generalization to unseen graphs. In the literature they are generally applied to large scale node classification benchmarks, such those found in the OGB benchmark suite (Wu et al.] [209bb] Rossi et al., 2020). It is known that these models are theoretically less expressive than standard GNNs, however their performance when applied node classification datasets has been acceptable.
We consider models of the form:
i s*xW)) k=
Y = Readout (M.P
(5)
We use up to the 4th power of the diffusion operator to emulate the depth of the corresponding GNNs, which all use 4 layers. We set S to use symmetric normalization, used by GCN and EGC- S; we also consider setting S to the adjacency matrix on ZINC, to emulate the operations used by GIN. The results are provided in Table 7 We see that the GA-MLP models offer similar (but often worse) performance than the corresponding GNN baselines. The models are not competitive with approaches such as GAT MPNN, and is outperformed by wide margin by EGC-S. Achieving
15

---

Published as a conference paper at ICLR 2022
Experiment
ZINC (MAE L)
CIFAR (Acc. 1)
MolitIV (ROC-AUC1)
Code- (F1 f)
EGC-S
0.364 0.020
66.92 0.37
77.44 + 1.08
0.1528 + 0.0025
EGC-S DropEdge (p 0.1)
0,468 0.007
66.37 1 0.28
77.41 1 1.32
0.1553 1 0.0021
EGC-S DropFdge (p 0.5)
0.629 0.023
64,60 + 0.58
75.33 + 0.82
0.1527 + 0.0019
EGC-S
GraphSAINT Node
0.631 0.012
61.37 0.75
73.65 # 1.41
0.1461 = 0.0027
Sampler (p 0.1)
Table 8: Results of applying sampling approaches EGC-S. We do not enable sampling test time-hence these approaches do not offer any test time reductions to computation. Sampling, in principle, is applicable any underlying GNN: our conclusions will transfer other underlying GNNs. We see that DropEdge (Rong et al., 2020) with a low drop probability (p = 0.1) can aid model performance; however, setting p this low does not significantly reduce memory consumption or computation. Increasing to 0,5 does reduce resource consumption noticeably, but results in noticeable degradation to model performance.
state-of-the-art performance with GA-MLPs does not appear to be possible, at least with our current understanding of these models.
We now proceed investigate sampling, in which each training step does not run over the entire graph, but over some sampled subgraph. These methods have seen great popularity when applied to tasks such as node classification, and they are able deliver sampling ratios in excess of 20x, hence yielding noticeable improvements to memory consumption (the primary limitation with large scale training). However, we note that the benefit of these methods has not been examined carefully for many graph topologies; while they have been shown to be effective for many "small-world" graph topologies-we wwhch arise in many graphs it is not the case that all graphs fall into this category. For example, molecule graphs would not fit this category.
We first assess the sampling strategy from GraphSAINT Zeng et al. 2019) by applying it to EGC-S models. For our experiments, we use the node-centric sampler. The results are presented in Table we disable sampling at test time. Even with a relatively low dropping probability of 10% (i.e. 90% of nodes are retained), the model performance degradation is severe. We note that the computational savings achieved are modest when using this drop probablility. We also observed similar results when using the edge-centric sampler from GraphSAINT.
We also attempted a different approach for sampling proposed by DropEdge (Rong et al.] 2020 as before, we apply it to EGC-S models. In this simple scheme, elements of the adjacency matrix are dropped; this scheme was shown to be effective for training deep graph networks, but it is also useful for reducing the computational footprint of models, since it effectively reduces the number of messages that have to be computed. We also provide results in Table The results are significantly better than we observe when using GraphSAINT's sampling strategies: at 10% drop probabilities we even see an improvement in some cases, due to the regularization effect. However, once we increase the drop probability to levels where we would observe a noticeable reduction in compu- tational demand, we observe that model performance declines. In summary, while DropEdge is more effective strategy for sampling on many inductive tasks, is not beneficial as a method to reduce the computational burden.
Finally, we discuss the limitations of other approaches proposed in the literature. Quantization is an approach that is typically applied at inference time; mixed-precisioe approaches can be applied at training time, however care must be taken for GNNs to avoid biasing the gradients (Tailor et al.) 2021]. Additionally, while neural architecture search (NAS) may be useful to find memory-efficient models if the search objective is set appropriately, they suffer from some cunitations-primann search time and memory consumption. Finally, approaches such reversible residuals (Li et al. 2021) are useful to architecture design, they do not tackle issues such as high peak memory usage induced by the message passing step.
C APPROACHES FOR HARDWARE ACCELERATION OF GNNS
The reader should note that most existing work for GNN hardware acceleration focuses on support- ing only subset of GNNs: specifically, they tend to only support models that be implemented
16

---

Published as a conference paper at ICLR 2022
using SpMM. Approaches in the literature falling into this area include Chen et al. (2020a). Yan
et al. (2020) You et al. (202I) and Zhang et al. (202I). is possible to add greater flexibility to the accelerator support more expressive message passing schemes, however this necessarily im- plies greater complexity. As Amdahl's law (Amdahl, 1967) implies, increasing flexibility is likely
reduce peak performance, while increasing silicon area requirements. Therefore, aiming for the simplest primitive (as we do with EGC) is the most sensible approach to obtain hardware accelera- tion.
D AGGREGATOR FUSION
Algorithm 1 Aggregator Fusion with aggregators A. This method is modification of the Com- pressed Sparse Row (CSR) SpMM algorithm, where we maximize re-use of matrix B. Maximizing re-use enables to obtain significantly better accuracy with minimal impact memory and la- tency. For simplicity, pseudocode assumes H = B = This version demonstrates how we can remove memory overheads at inference time.
Input: CSR A E IRN Dense B E RNxF, Combination weightings w E E X
Output: Dense C E RN for i = 0 to A.row.s
1 do
for jj- = Awwoww pointer(ij to A.row coooteoittrr(i// + do
j == A. Accoumm_indexxppe
Init temp arrays of length F per aggregator
0:j A. values]jj]]
{ (May be faster to interleave these calls:}
for ② A do
process_ron soo & (a:j. B(t,:] t)mp
end for
end for
[Can be generalized to H, B > 1:} = E w/i. + temp a
end for
The naive approach of performing each aggregation sequentially would cause a linear increase in latency with respect to [A). However, key observation to note is that we are memory-bound: the bottleneck with sparse operations is waiting for the data to arrive from memory. This observation applies to both GPUs and CPUs, and justified through profiling. Using profiler on a GTX 1080Ti we observed that SpMM using the Reddit graph Hamilton et al. (2017) with feature sizes of 256 achieved just 1.2% of the GPU's peak FLOPS, with 88.5% of stalls being caused by unmet memory dependencies. The fastest processing order performs as much work as possible with data that has already been fetched from memory. rather than fetching it multiple times. This concept is illustrated in Algorithm in the appendix. We can perform all aggregations as a lightweight modification to the standard compressed sparse row (CSR) SpMM algorithm.
The second observation we make is that storing the results of all aggregations is unnecessary at in- ference time. Note that the CSR SpMM algorithm processes each row in the output matrix sequen- tially: rather than storing the aggregations for every row, instead we should store only the weighted results. This approach not only reduces memory consumption, but also latency as we improve the effectiveness of our cache and reduce memory system contention. In practice, this optimization is especially important when performing inference on topologies which have more frequent periods where the processing has become compute-bound, since we reduce contention between load and store units Corpprratin This also demonstrated in Algorithm
We evaluated aggregator fusion across four different topologies, on both CPU and GPU; our results can be found in Table / We assumed all operations are 32-bit floating point, and that we were using three aggregators: summation-based max, and min; these aggregators match those used for EGC-M Code. Our benchmarks were conducted on a batch of 10k graphs from the ZINC and Code datasets, Arxiv, and the popular Reddit dataset (Hamilton al. 2017). which is one of the largest graph datasets commonly evaluated on in the GNN literature. Our SpMM implementation on GPU based on Yang et al. (2018). Code for the kemels provided in our repo
17

---

Published as a conference paper at ICLR 2022
(Xeon
8000)
Method
Reddit/s
Code/s
Ardi/
Reddit uss
Weight
0.00
= 0.040
0,055
0.01
2.36
1.74
CSR SpMMM
1.943
0.760
0.066
186.44
19.88
5.56
Naive Fusion
88.25 0.20
8.680
#: 0.084
2A31 0.016
1.4824
0.000
595.
0.23
112.52 4: 0.22
23.83
=: 0006
19:09 2: 0,05
Faster Ordering
40.05 = 0.10
4,592
J: 0,054
13303
0.037
0.772
0,008
214.00 0.10
29.38 0.32
7,63 0.00
4.78 = 0.00
Store Weighted Result Cnuly
38.63 0.22
1,752 + 0.018
0.922 = 0.026
0.278 0.003
208.23 + 0.13
26.64 0.00
6.75 + 0.08
4.38 0.02
Table 9: Inference latency (mean and standard deviation) for CSR SpMM, used by GCN/GIN, and aggregator fusion. Assuming a feature dimension of 256 and H = B = per Algorithm T We observe that aggregator fusion results in an increase of 34% in the worse case; in contrast, the naive implementation has worst case increase of 466%. Also included are timings for dense multiplication with square weight matrix; we observe that sparse operations dominate latency measurements.
Model
Train Epoch Time (s)
Test Epoch Time (s)
Peak Train Memory (MB)
GCN
144.7 + 0.5
6.3 = 0.3
1337
GIN
134.5 + 0.1
5.7 + 0.3
1331
GraphSAGE
140.3 + 0.3
5.6 + 0.3
1226
GAT
176.0 0.7
6.3 + 0.3
2885
MPNN-Sum
305.3 + 2.7
6.8 + 0.3
3448
MPNN-Max
319.0 1.3
7.6 0.4
3901
PNA
575.4 + 2.3
12.0
9399
EGC-S
166.4 + 2.7
6.2 + 0.3
1 1842
EGC-M
225.7 + 0.6
7.9 0.3
3470
Table 10: Latency and memory results for parameter-normmllizee models on OGB Code-V2 V2. Despite [E] having a lower |V ratio of 2.75 relative to Arxiv (13.67), we see that the trends we observed for Arxiv broadly remain. It is worth noting again that EGC-M is far more efficient both latency and memory-wise than PNA.
As expected, our technique optimizing for input re-use achieves significantly lower inference latency than the naive approach to applying multiple aggregators. While the naive approach results in mean increase in latency of 331% %, our approach incurs a mean increase only 14% relative to ordinary SpMM, used by GCN and GIN. The increase is topology dependent, with larger increases in latency being observed for topologies which are less memory-bound. We also provide timings for dense matrix multiplication (i.e. X to justify our focus optimizing sparse operations in this work: CSR SpMM operation is 4.7 x slower (geomean) than the corresponding weight multiplication. We believe further optimizations of the operations used by architecture are achievable through the use of auto-tuning frameworks e.g. TVM (Chen et al.) (0188)), but this lies beyond the scope of this work.
E LATENCY AND MEMORY CONSUMPTION ON OTHER DATASETS
In the evaluation, we assessed the memory consumption and latency for the parameter-normaaized models on Arxiv. In this section, consider similar exercise for OGB Code models. The results are provided in Table 10 Our conclusions remain broadly similar, with EGC-M offering clear improvements to memory consumption, latency, and parameter efficiency relative to PNA. EGC-S superior to GAT, with similar inference latency, better model performance, and noticeably lower memory consumption. We train models using batch size 128; the reader should note that the memory consumption figures vary between runs (even for the same model), since graphs vary in the number nodes and edges.
So far have not demonstrated that our approach is more efficient than the baselines Arxiv, which is the only dataset where EGC-M and PNA are not the best performing. To demonstrate that more efficient must show that we achieve lower memory consumption and latency for a given accuracy-level-iae we must consider models that are recuracy-normalio We evaluate increasing the parameter count for baseline models until they achieve the accuracy as EGC-S;
18

---

Published as a conference paper at ICLR 2022
Accuracy-Normalized
Parameters
GPU Training Latency (ms)
GPU Inference Latency (ms)
Peak Memory (MB)
Model
GCN
184k
208.6 = 2.2
44,9 + 0.4
2549
GIN
FAIL
FAIL 335.8 + 2.4
FAIL
FAIL
GraphSAGE
593k
60.2 + 0.2
3208
EGC-S
100k
177.7 + 2.2
37.3 + 0.1
2430
Table 11: Latency and memory statistics for accuracy- models Arxiv. To achieve the same accuracy as EGC-S, we must boost the size of the baseline models. We observe that EGC-S offers noticeable reductions to both memory consumption and latency for given accuracy level.
we also gave these models an extra advantage over our method by increasing the hyperparameter search budget. The results are shown Table [I]] where observe that EGC-S is more efficient once we are comparing models achieving the same accuracy.
The reader should note that GAT (but not GATv2) can be implemented to reduce memory consump- tion by noting that the left and right halves of the attention vector can be computed separately. and added together as appropriate. We use an optimized implementation of GAT' for our experiments (from Py PoTcch Geometric); refer the reader to the implementation for further details.
F GENERALIZING TO HETEROGENEOUS GRAPHS
Our R-EGC model is similar to the bascline R-GCN model included in the OGB repository. The OGB model deviates from the standard definition of R-GCN (Schlichtkrull et al. 2018) since it han- dles different node types, not just edge types. The baseline model has weights generate messages for each relation-type and a weight matrix to update each individual node type. This corresponds to:
yO 0xx
Σ
θ,x JEA.(0)
Σ
(W-(1]
where 17 corresponds to the node type of node i, and R. represents the set of relation types. Note that the mean aggregator used.
We deviate from the baseline by using single set of basis weights. Instead, we use different weighting calculation layers (w(*) 4x + b) per node and relation type.
B Σ
Σ PER
Σ b=1
Σ
(i)
r.h.b
A=1 b=1
h=
JEN(()
19


Reviews:
[{"review_id": "vJemh6hgjy6", "reviewer": "Reviewer_Cq1y", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper is a mixed bag. On one hand, I appreciate the authors' vision: take some things we've learned about GNNs (heads, aggregators), revisit first principles (isotropic GNNs), try to come up with something new that blends them. In addition, I appreciate their take on computational efficiency: they correctly seize upon the notion that a well-understood algorithmic kernel can have meaningful computational impact, and they build on its advantages (e.g., section 3.2-aggregator fusion). On the other hand, many of the conclusions leave something to be desired. The analyses and descriptions sometimes gloss over important factors, and I wish the results delivered a stronger takeaway to match the ambition. For all the talk about computation and memory efficiency, the actual numbers are not all that substantial.\n\nStrengths:\n\n- The authors' direct challenge to accepted folk knowledge about anisotropic GNNs is healthy and welcome. As models evolve over time, it is important for the community to revisit fundamental positions on model components. The paper opens a lot of areas for other researchers to build off it, which I see as a major strength.\n- The proposed model is clearly explained and fairly easy to follow. The intrepretations are useful and provide good intuition for how to place their proposed model in the context of other current work.\n- The appendices actually provide a lot of useful content, sometimes more than the paper itself. The rationale in appendix C, for instance, was far clearer than the paper's 'aggregator fusion' section in 3.2 (even without the algorithm).\n\nWeaknesses:\n\n- Some of the evaluation results are weak. The accuracy-normalized results in seem to demonstrate that EGC-S  is not all that much faster or smaller than GCN. It also seems to indicate that parameter-normalized results do not correlate particularly well with memory footprint across models, which weakens the argument for O(V) vs. O(E).\n- Despite a nominally primary argument of the paper being about memory efficiency and computational performance, very little quantitative results support that argument. I agree that there is definitely a lot of potential for this approach to be efficient, but I wish the paper had strong support for it.\n\n- The authors fail to disambiguate different types of memory effects. For instance, while high-watermark memory footprint (which is mostly what is measured in their experiments) is important, they overlook the effects of parallelism. This leads them, amongst other things, to dismiss sampling methods almost out of hand. The memory behavior of sampled methods is vastly different than non-sampled GNNs when dealing with distributed execution or on graphs that are substantially larger than single-device memory capacity.  Or the focus on O(V)/O(E), which glosses over the fact the average degree is small (between 2 and 13 on their chosen OGB datasets) and ignores other 'constants' on the same order. This is technically correct but misleading. None of these invalidate the authors' methods, but it's somewhat disingenuous.\n\nAlso, it very much felt like parts of the paper were aimed at different goals. The intro and background lean heavily into hardware efficiency, while other parts of the paper (S3 outside of the last paragraph; S5.1-5.3) seem to ignore it.", "summary_of_the_paper": "The authors propose a different formulation for a graph neural network, focused on achieving accuracy equal to anisotropic GNNs without anisotropic mechanisms.", "summary_of_the_review": "The authors take a different tact with their proposed GNN, which is welcome. They explain it clearly, and the paper's writing and organization are solid. The results support their claim that they can achieve competitive accuracy, but the quantitative computation and memory results are somewhat underwhelming. In my view, the contribution of this paper is its approach and challenge to convention, which feels good enough to publish, even if it left me wanting more substantive.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YvI9rdVPbC-", "reviewer": "Reviewer_SZEe", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "### Strengths:\n1. This paper applied the idea of \"basis weights\" and thus effectively uses different weight matrices for different nodes.\n2. This paper has provided a long section to help interpret the proposed architecture and compared it with GCN, GAT, and PNA.\n\n### Questions:\n1. Since it is noted that different aggregators might result in outputs with different means and variances, for the experiments in Table 1, did you normalize the combination weights $w$ or the different aggregated outputs?\n2. I am curious how you implemented the \"weighting of bases\" per node, i.e., multiplication between the combination weighting coefficients $w$ (different for different nodes) and the aggregated outputs corresponding to different basis weight matrices? Is this step before or after the aggregation? Although the theoretical complexity of this step is $O(V)$, I think the choice of actual implementation might significantly affect the practical time efficiency.\n\n### Weaknesses:\n1. The major weakness of this paper, in my opinion, is that this paper seems to have misunderstood the real bottleneck to scale-up GNNs, and the proposed architecture may not be suitable for large graphs (i.e., size over a million).\n   - The paper has compared with many existing approaches to solve the scalability issues of GNNs on large graphs. However, this paper did not tackle this problem. Firstly, the theoretical complexities of the proposed architecture are still $O(V)$. Thus on a graph with more than a million nodes (which happens in some node classification or link prediction benchmarks), the memory consumption is still too large for conventional GPUs. Secondly, the main experiments (Table 1) are conducted on four graph regression/classification benchmarks and only one node classification benchmark. However, the graphs in the four graph-level benchmarks are small. The experimental exploration and evidence on large graphs are insufficient.\n   - For graph sampling approaches, the paper claimed that `We evaluated a variety of sampling approaches and observed that even modest sampling levels, which provide little benefit to memory or latency, cause model performance to decline noticeably.` The corresponding experimental results are shown in Table 8 in the appendix. However, all four benchmarks used in Table 8 are graph-level tasks (graph regression or classification), where the sizes of input graphs are small. For example, ZINC and MolHIV are molecule graphs, and CIFAR consists of super-pixel sampled graphs whose sizes are at most 150 (Dwivedi et al., 2020). Applying sampling strategies to these small input graphs is not reasonable, and it is not strange to observe significant performance degradation. Actually, the performance of some sampling algorithms on relatively large graphs for node classification is strong, e.g., GraphSAINT (SAGE aggregator) can outperform the \"Full-batch\" GraphSAGE on *ogbn-products* (see [leaderboard](https://ogb.stanford.edu/docs/leader_nodeprop/)). The quoted sentence above is not appropriate.\n   - To sum up, I think the architecture proposed in the paper does not solve the scalability problem on large graphs. Thus the authors should make this point clearer in the related work and experiment sections.\n2. Another potential problem, in my opinion, is the spectral interpretation in Section 4.2. The paper claims that `Our approach corresponds to learning multiple filters and computing a linear combination of the resulting filters with weights depending on the attributes of each node locally.` The paper compared two formulas: (1) the ideal linear combination of filters: $y=\\sum_{b=1}^Bw_b\\odot g_{\\theta_b}(\\mathbf{L})\\mathbf{X}$; and (2) the filtering of proposed model (correspond to EGC-S, Eq.(2)) $y=\\sum_{b=1}^Bw_b\\odot (\\tilde{D}^{-\\frac12}\\tilde{A}\\tilde{D}^{-\\frac12})\\mathbf{X}\\Theta_b$.  However, I think the latter formula is not a combination of multiple filters. There is only one filter $(\\tilde{D}^{-\\frac12}\\tilde{A}\\tilde{D}^{-\\frac12})$ (which is left multiplied to $\\mathbf{X}$) and the weight matrix $\\Theta_b$ right multiplied to $\\mathbf{X}$ should not change the relative magnitude of signals of different frequencies. It is not the same if changing $g(\\mathbf{L})$ in the former formula, where the matrix left multiplied to $\\mathbf{X}$ changes.", "summary_of_the_paper": "This paper claimed they designed a new GNN architecture that achieves state-of-the-art performance with lower memory consumption and latency. More specifically, the proposed model uses memory proportional to the number of vertices in the graph $O(V)$, in contrast to competing methods which require memory proportional to the number of edges $O(E)$. The paper claimed that the new architecture enabled each vertex to have its own weight matrix, thus following a novel adaptive filtering approach. The experiments found that the proposed efficient model could achieve higher accuracy than competing approaches across six large and varied datasets against strong baselines. Moreover, the experiments demonstrated that the proposed method achieves lower latency and memory consumption for the same accuracy compared to competing approaches.", "summary_of_the_review": "This paper proposed a novel architecture to linearly combine the aggregated outputs using different weight matrices for each node. The model is memory efficient since the memory consumption is $O(V)$ instead of $O(E)$. However, the proposed method did not solve the scalability problem of GNNs when applied to considerably large graphs. And it is unclear when the provided memory efficiency is necessary, and thus the proposed method is the first choice. In terms of performance, the improvements compared with PNA are also not very convincing. The significance of this paper might be limited if the efficiency/performance improvements are marginal. I would encourage the author to explore the theoretical understanding of the proposed architecture further. Currently, section 4 is well-written, but the conclusions are limited and may have some flaws. In general, I could not recommend the current manuscript for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UUWbk8VqUEH", "reviewer": "Reviewer_gVtv", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n- The paper conducts a thorough analysis and comparison of alternative approaches and describes how some of the motivations behind the alternatives can be gained without the memory costs.\n- The paper conducts a thorough analysis on latency, which I appreciate.\n- I like that the authors consider hardware - in many cases, more efficient algorithms in FLOP terms are less efficient because they are not parallelisable. This is an important point and I encourage work in the GNN literature that addresses this.\n- The results are better than the baselines, which are over a number of different graph networks. I think the model description is quite general.\n\nWeaknesses:\n- To state the obvious, such a network is only really applicable to data where you do not need to consider edge features explicitly. While this is fine in principle, the paper doesn't really make this distinction and so the claim is probably broader than the evidence supports.\n- The text seems to imply that the computational efficiencies derive from the use of sparse matrix multiplies. But, many new accelerators do not support sparse matmuls well at all, instead are very strong on dense compute. This distinction should be clearer in the text - this is a *GPU* optimised GNN, not an accelerator optimised GNN (perhaps a more parallel GNN would count for something more general purpose).\n- I do not think these results are state of the art - simply that they are better than the baselines reported. Please remove the phrase state of the art.\n- Whilst I understand that this method is different from the literature, it is *very* related to concepts such as attention. Thus, I think the impact may be limited.\n\nSome nits: It would be nice to have more detail on the OGB and Zinc results - perhaps explain why this model does not perform as well as MolHIV.\n\n\n\n", "summary_of_the_paper": "This paper introduces Adaptive Filters that enable some of the benefits of Message Passing architectures, but while maintaining a memory consumption that scales with the number of nodes.\n\nThe authors claim that this architecture is not only better performing, and use less memory, but more efficient for GPUs through the use of sparse matrix multiplication.\n\nThe idea of the model is that you have a number of filters (MLPs or linear layers) applied to each sending node latent, a \"filter\". These are then weighted and summed by a weighting vector calculated as a function of the receiving node. Since there are no functions that take as input both sending, receiving or edge inputs, the memory will scale with the number of nodes. You, in essence, get an efficient pseudo-attention mechanism. \n", "summary_of_the_review": "I think this is a thorough piece of work, but I am concerned that the impact is limited for the following reasons:\n- I am not convinced that the results presented reflect the current state of of O(V) scaling GNNs. You cite \"Training graph neural networks with 1000 layers\" which I believe scales O(V), and I think achieves better results on OGBN-ARXIV. \n- The ideas seem very related to existing work. This isn't to suggest that the ideas are identical, more that the contribution appears to be incremental.\n\nThat being said, I think the analysis is beneficial to the community so give it a weak accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Nz76cHjmrP7", "reviewer": "Reviewer_x8K1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "I am convinced by the introduction part. The hardware efficiency and memory cost are arguably two bottlenecks in the GCN inference and training and they are often correlated.\n\nStrengths:\n\n* The recap of algorithm-hardware co-design is clean and to the point and should promote the understanding of hardware acceleration for the GCN community, potential reference also includes GCoD (HPCA'22) and G-CoS (ICCAD'21).\n\n* The comparison table give the readers high-level information about the propagation differences among various GCN methods and their corresponding memory requirements.\n\n* The adaptive filter is a kind of meta-learning approach that allows different basis filters to explore different latent spaces and finally weighted summed. I suppose the experiments are a fair comparison with a similar number of parameters as Fig. 3 shows.\n\n* A clean codebase is provided.\n\nQuestions:\n\n* I have one question about the sampling-based methods. As Table 2 shows, GraphsSAGE achieves the lowest GPU training and inference latency and also the least peak training memory, which seems to contradict the argument in Sec. 2 that sampling-based methods are often ineffective. In addition, why the inference time of GraphSAGE is also lower than GCN since we will not sample the subgraphs during inference? I am also wondering whether EGC can also be implemented in a sampling-based way?\n\n* Could you elaborate more about the potential impact on the GCN hardware acceleration? Will EGC-S or EGC-M propose unique challenges/opportunities that commercial devices (CPU or GPU) cannot efficiently handle while needing further customized hardware architecture for leveraging their full potential?", "summary_of_the_paper": "This paper investigates whether incorporating anisotropy (treating neighbors differently using latent functions and thus resulting in $\\mathcal{O}(E)$ memory cost) is necessary for boosting GCN's accuracy. They argue that the proposed EGC with $\\mathcal{O}(V)$ memory requirement can achieve higher accuracy than prior anisotropy-based works (e.g., GAT) using adaptive filters and thus achieve (1) better accuracy than vanilla GCN; (2) and less memory cost and latency than anisotropy-based methods.", "summary_of_the_review": "I think the introduction and related works description clearly recap the background of both GCN algorithm and potential algorithm-accelerator co-design, and also the current dilemma in the GCN community, that is, the more accurate but less time/memory efficient anisotropy approaches VS. less accurate but more time/memory efficient vanilla GCN approaches. The proposed EGC can alleviate such a dilemma by achieving both higher accuracy and efficiency.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The manuscript develops a new and simple graph neural network architecture. The proposal make use of only O(V) (number of vertices) rather than O(E) (number of edges, meaning that it may be useful for scaling to larger problems. The didactic figures are especially clear, and as is shown in Fig 1 the proposed architecture passes messages based only on the source vertex rather than based on source and target. This challenges common ideas in the field that passed messages ought to reflect a function of both source and target. In spite of this introduced simplification, the architecture performed better than or as well as a set of strong baselines on a set of 6 datasets. The manuscript also examines latency and memory consumption, showing that the methods comes out favourably in this regard.
One of the reviewers worries that the paper does not directly provide a solution to scaling network training to very large graphs; they note that several of the datasets that are examined do not contain large graphs. This is true, but the paper does not overclaim in this regard, and I agree with the majority of reviewers that the manuscript is worth publishing on the basis of having developed a well-performing approach that challenges the accepted assumptions in the field. While it may not be a direct solution, the counterintuitive results may help point the direction toward development of simple, effective approaches that do scale up.
Decision: Accept (Poster)