Generalizing CNNs to graphs with learnable neighborhood quantization
Authors: Isaac Osafo Nkansah
Neil Gallagher
Ruchi Sandilya
Conor Liston
Logan Grosenick
Venue: NeurIPS 2024 poster (2024)
Keywords: graph convolutional networks
graph neural networks
quantization
Primary area: graph_neural_networks
TL;DR: We present a novel GCN framework that properly generalizes CNNs to graph structured data.

Abstract: Convolutional neural networks (CNNs) have led to a revolution in analyzing array data. However, many important sources of data, such as biological and social networks, are naturally structured as graphs rather than arrays, making the design of graph neural network (GNN) architectures that retain the strengths of CNNs an active and exciting area of research. Here, we introduce Quantized Graph Convolution Networks (QGCNs), the first framework for GNNs that formally and directly extends CNNs to graphs. QGCNs do this by decomposing the convolution operation into non-overlapping sub-kernels, allowing them to fit graph data while reducing to a 2D CNN layer on array data. We generalize this approach to graphs of arbitrary size and dimension by approaching sub-kernel assignment as a learnable multinomial assignment problem. Integrating this approach into a residual network architecture, we demonstrate performance that matches or exceeds other state-of-the-art GNNs on benchmark graph datasets and for predicting properties of nonlinear dynamics on a new finite element graph dataset. In summary, QGCNs are a novel GNN framework that generalizes CNNs and their strengths to graph data, allowing for more accurate and expressive models.

Generalizing CNNs to Graphs with Learnable Neighborhood Quantization
Isaac Osafo Nkansah
Neil Gallagher' Logan Grosenick!* Department of Psychiatry and BMRI, Weill Cornell Medicine, Cornell University, New York, NY, USA
Ruchi Sandilya'
Conor Liston'
Abstract
Convolutional neural networks (CNNs) have led to revolution in analyzing array data. However, many important sources of data, such as biological and social networks, are naturally structured as graphs rather than arrays, making the design graph neural network (GNN) architectures that retain the strengths of CNNs an active and exciting area of research. Here, we introduce Quantized Graph Convolution Networks (QGCNs), the first framework for GNNs that formally and directly extends CNNs to graphs. QGCNs do this by decomposing the convolution operation into non-overlapping sub-kernels, allowing them to fit graph data while reducing to 2D CNN layer array data. We generalize this approach to graphs of arbitrary size and dimension by approaching sub-kernel assignment as learnable multinomial assignment problem. Integrating this approach into residual network architecture, we demonstrate performance that matches or exceeds other state- of-the-art art GNNs benchmark graph datasets and for predicting properties of nonlinear dynamics on new finite element graph dataset. In summary, QGCNs are novel GNN framework that generalizes CNNs and their strengths to graph data, allowing for more accurate and expressive models.
1 Introduction
Many important real-world scenarios involve data structured graphs. For example, neural networks (both biological and artificial) are typically represented as directed graphs where individual neurons propagate information to other neurons along edges. Digital networks (e.g. social networks, the internet) are graphs made up of links between digital objects, and chemical structures can be modeled graphs made up of bonds between atoms. It can be challenging data, creating a barrier to studying these problems. Indeed, this work was motivated by our own experiments modeling brain networks from neural data, where have found that existing methods are often not expressive enough to effectively capture the types of phenomena we are interested in.
accurately model such graph
In recent years, the prevailing approach for learning from graph data has shifted towards methods inspired by convolutional neural networks (CNNs) 220 21 8 [7 25 4|5 [5]. The focus on extending the convolutional layer of CNNs to graph data is motivated by the strong and successful inductive bias of CNNs, which use trainable filters that efficiently model local structure in array-structured data (e.g., images). CNNs have been effectively employed in numerous domains, including natural language processing (66 43 and image recognition [ Because graph data often exhibit strong patterns of local correlation like those in language and image data, it is reasonable expect they might similarly benefit from shared local filters.
To whom correspondence should be addressed: log4002 @ mod.cconell.cduu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Early work extending CNNs to graphs focused on spectral methods [6 which can suffer from high runtime and memory complexity [40]. In contrast, spatial methods aim to generalize the convolution operation explicitly from array data graph data. Recent spatial GNN methods approach this problem by either adapting the convolution operation to graphs [ I 27 28 or by adapting graphs to fit the
CNN convolutional operation [00]. Existing spatial methods, however, do not truly generalize the CNN convolution layer.
Spatial Graph Convolutional Networks (SGCNs) [S). for example, claim to generalize CNNs to graph data as during inference on array data an SGCN will have spatial filters that resemble those of a CNN. But an SGCN will not reduce to an equivalent CNN when trained on array data, and thus not a proper generalization. This relates to a central challenge of extending convolutions to graph-structured data: in CNNs, local neighborhoods have fixed sizes and fixed ordering of the nodes within the neighborhood, a convenience that does not hold true for more general graphs. We believe that bridging the gap between CNNs and GCNs and properly generalizing the powerful local inductive bias of CNNs to GNNs will lead to improved learning for many types of graph data.
To this end, we introduce the Quantized Graph Convolution Layer (QGCL), which adds to the spatial graph neural network literature proper generalization of the CNN convolution layer to graphs. We do this by first "quantizing" the convolution operation for CNNs into an equívalent set of non-overlapping sub-kernels applied to local geometry, Second, we describe a specific set of sub-kernels for graphs that are equivalent to 2D convolutional kernel based on a satisficing mapping, which relies on relative angular displacements of nodes to quantize graph neighborhoods into sub-kernels. To generalize the QGCI. to arbitrary graphs, we extend it to be able to learn neighborhood quantizations from data, using a network we term QuantNet. Furthermore, we design a residual network around the QGCL architecture, which we term Quantized Graph Residual Layer (QGRL), to make the layer more robust to model depth effects like vanishing gradients. As we were initially inspired by the regularity of widely-used finite element method (FEM) graphs, we provide a new benchmark data set for FEM (based on Navier-Stokes fluid flow on an adaptive mesh graph) and demonstrate that a QGRL-based architecture (called Quantized Graph Residual Network or QGRN) is highly competitive on such data. Next, we show that QGRNs enable competitive performance across nineteen inductive learning graph datasets. Finally, demonstrate that incorporating QGRLs leads to superior performance in supervised autoencoder model applied to public EEG recordings and emotional states dataset [18]
In summary, our main contributions are:
1. Introducing the Quantized Graph Convolutional Network (QGCN) framework, which gener- alizes CNNs to graphs.
2. Empirical and formal validation that a QGCN using the satisficing mapping sub-kernels reduces to 2D CNN on image graphs.
3. An end-to-end learnable quantization network (QuantNet) that extends QGCNs to arbitrary graphs.
4. A residual network inspired architecture, Quantized Graph Residual Networks (QGRNs). that further improves QGCN performance.
5. Benchmarking of QGRNs on a new Navier-Stokes FEM dataset and 19 other public bench- mark graph datasets for graph classification and node classification.
6. Showing QGRLs improve joint modeling of emotional states and EEG data in supervised autoencoder architecture.
2 Relevant work
GCNs Although inspired by spectral theory, Graph Convolutional Networks (GCNs) [7] are practi- cally understood as a spatial GNN method they aggregate node features within local neighborhoods (normalizing by the node degree of the central/target node) and then transform the resulting aggre- gated features into new features for the central/target nodes. Because all neighboring node features are scaled by fixed weights and then aggregated in the input features space, this method's number of trainable free parameters differs from CNNs (failing to generalize the CNN convolution layer). In contrast, CNNs learn embeddings of each node feature separately and the ability of each node's features to embed in different point the output feature space independently makes CNNs more flexible than GCNs.

---

SGCNs Spatial Graph Convolutional Networks (SGCNs) [S] recent novel CNN-inspired GCN architecture, improve on GCNs by using graph node positional descriptors to rank nodes within their neighborhoods. They extend GCNs by using ML.ss that project the relative spatial/positional descriptors of nodes into output feature space. Though the authors claim that SGCNs are equivalent to CNNs for inference, SGCNs and CNNs exhibit different inductive bias during training. There is additional difficulty in matching CNN and SGCN model parameters and determining how scaling different parts of SGCN architecture translates into equivalent CNN adaptions. A strength of SGCNs is that they can consume pseudo-positiona descriptors, making them more general than GCNs.
KerGNNs Kernel GNNs [9] define kernels as sub -ab-graahs with trainable adjacency matrices and node features. The trainable node features for sub- sub-graphs parallel CNN kernel weights, and the learned adjacency matrices allow for different topologies of sub-graph kernels to be learned. In CNNs, the adjaceney matrix of the convolving kernel is fixed, hence kerGNNS generalize the CNN convolution operation well in this sense. However, the size of the direct product graph (which captures the relationship between local sub-graph patches and the convolving sub-graph kernel) grows quadratically with the sizes of the local neighborhood and the convolving sub-graph kernel. For graphs with large local neighborhoods, the computation of the adjacency matrix of the direct product graph per local neighborhood (effectively cubic runtime complexity across the data) becomes very expensive. Further the authors suggest the use of additional trainable weights for the base random walk kernels, causing further divergence with regular CNN convolution layer.
LGCLS Inspired by (27], the Learnable Graph Convolutional Layer [T] approach is unlike the aforementioned methods, instead adapting graph data into a form that regular CNN convolution operator can use. It does this by applying max pooling on the feature vectors of the local graph neighborhoods. This does not generalize the CNN convolution operation (which uses all the features within the local neighborhood and not a sub-sampled set), Further, max pooling sub-sampling constrains the model to ascribe more importance to large features; a constraint absent in CNNs.
GATs GATs extend the power of transformers and attention networks to graphs and have been shown to be highly performant on graph data [38] 39 2 36). In current GATs, every node attends to its neighbors either in static or dynamic fashion. The attention mechanism effectively yields edge-aware feature scalars from source nodes whose messages must be aggregated for the target node. This is akin to CNNs applying different kernel weights to different node features in local image graph neighborhoods.
DeeperGCNs Early works [22 adapted residual connections, inspired by ResNets 112. deep graph
networks to deal with the problem of vanishing gradients and over-smoothing [24]. A more recent innovation in this space, GENConv [23] builds on these residual connections (first demonstrating how powerful these connections alone are for deep networks) and innovates generalized messaging passing aggregators, learnable message normalization layers etc. to compete with performance on standard graph dataset benchmarks. Other works such as DropEdge (31), which propose randomly removing graph edges, and PairNorm 44 which develops a normalization layer to tackle the problems aforementioned, are also noteworthy.
3 Proposed methodology
3.1 Extending CNNS to graphs
Quantized Graph Convolution Networks (QGCNs) are an extension of CNNs to graph data. We begin with a formal description of the convolutional layer, which is the core component of CNNs, in order to motivate the Quantized Graph Convolution Layer (QGCL). For simplicity, we focus on the convolutional layer in two dimensions with a stride size of one operating on E RC'x where G is structured in way such that proximity and adjacency in the space composed of the first two dimensions has meaning, but that the ordering of those 2D planes along the third dimension is arbitrary. As an example, 2D image data with multiple color channels exhibits this structure. In this case, a convolutional layer will generate an output feature map O E RxF
J-1K-1 ΣΣ
0 O =
W j.kk M.k.e.GGee.Hte Gjtckkdd + b,
(1)
5-0 0=
3

---

where W E R and b E R are the weights and bias terms of the convolutional kernel, respectively. To produce a map that the same size as the original input, rero-padding can be added along the edges of G before applying the convolutional layer to result in Oc,d; being defined for e E [0, C" 11, E [0, 1|.
We can refactor the kernel parameters in Eq. to have single index h iterating over the 2D space traversed by j and above:
JK-1
K
b JK
O Oc.d,:
Σ A=
W
[(= Gj+ck+d; (M=jjkt)Gjtkkdd,
B
Bi:
vh, (2)
3=0 K=
where W W.K+ corresponds to W J. in Eq. 1 The indicator function 1 ((= has the effect of creating mask over a single element in the 2D space defined by and k. with one-to-one correspondence between each element and each value of h. Thus the convolutional layer can be decomposed into a set of sub-kemels (i.c., weight matrices Wn... and bias vectors Br..)) along with a corresponding set of masks on the input space. This formulation of the convolutional layer allows for interesting possibilities by designing a different set of mask functions; for example, one could produce well-defined output O with the same dimensions G without the need for zero-padding.
In the 2 the masks implicitly compare the location of elements in G to the relative position the current output within the larger output tensor O. We generalize the ideas above to graphs by allowing for masks that operate on node pairs, rather than comparing pairs of elements tensor data. When generalizing the convolution to graph input, we want the output to be a graph as well. Here, we limit ourselves to outputting graphs with identical structure to the input and only considering the local neighborhood of a node when calculating the features of the corresponding output node. We formally define output of the quantized graph convolution layer as follows:
H-1
(vv)
W W
(((e.))em,)aa')) + B e'EN(O)
Σ
where (vv) E R provides the feature vector of the output node at the same relative location as input node v, (N)) is the set of nodes in the local neighborhood around v, MA, is the set of node pairs selected by the mask corresponding W R. and a(v) E RFF' retrieves the feature vector of node v. In the context of QGCNs, we refer to each Wn.:: as a sub-kernel. It the process of using binary masks of fixed cardinality to quantize the space of potential nodes in a local neighborhood that gives quantized graph convolution networks their name. This framework sufficient to include most practical use cases of the convolutional layer. For example, convolutional kernels with any dimension larger than three can be represented by considering tensor elements to be connected in the graph representation if the kemnel would apply to one node while the kernel is positioned with the other node at its 'center'. Two noteworthy exceptions that do not fit in the QGCN framework are stride sizes larger than one or convolutional kernels with odd dimensions (to be explored in future work).
3.2 A satisficing mapping generalizes local convolutional kernel masks
In this section, we show how the sub-kernel masks (Md,) associated with convolutional kernels can be extended to the case of graphs with (yseudo-)positions information. The masks associated with CNN convolutions are functions of the relative position of tensor elements (nodes) to the position of the current element in the output tensor (see Eq. ( We refer to these as the natural convolutional masks (see Fig. [ For graphs with positional information, it is possible to formalize a method for choosing a set of sub-kerne masks that would produce standard convolutional layer masks when applied to tensor data that has been converted to graph form. For simplicity we consider the case of a convolution in two dimensions where data is converted to 2D positional graph by assuming that edges exist only between adjacent elements (nodes) and extend this case to handle all 2D positional graphs. Note that in the absence of positional information, any other information associated with nodes that can be embedded into a 2D space can be treated as pseudo-posiin positional information to enable this more general approach.
As seen in Eq. each mask is defined by the indicator function ((k=)K+)) which selects a single element. When dealing with tensor data, the relative position of the elements selected by these masks

---

Navier Stokes FEM mesh graph
Simple 4x4 image
(c) Sample Neighbarhood from
Semple Inner tocal neighborhood from
(e) Another inner local neighborhoodd from
-il
Di-1l
(leer)
grany
w
(e)
Centrol mode
D.
par))
lanet)
Darg
(1) No iighorhooodin in (e) with netural filter
ibrghiborhood in with quantizing filter superposed
(h) Neighborhood in (e) with quantizing filter
mask superoosed
superposed
Figure 1: Contrasting the assignment of kernel weights to local neighborhood nodes for traditional CNN convolution kernels and the satisficing mapping sub-kernels of QGCL layer. Traditional CNN convolution kernel is depicted with its natural kernel weights masks while QGCL sub-kernels are shown with their corresponding quantizing kernel masks on graph neighborhoods. Note that the angular quantization bins have inclusive angular lower bounds and exclusive angular upper bounds, such that nodes falling the edges mapped unique sub-kernels (e.g., g., the node in (h.) on the e35e maps to the green mask sub-kernel.
remains fixed as the convolutional kernel moves to different output positions. In contrast, we cannot assume that the nodes in local neighborhood will always be located in the same relative positions for all local neighborhoods within a graph. Because we desire a set of masks that is applicable to all 2D positional graphs, our masks must define way potentially map all of 2D space to set of sub- kub-kernels. One simple option is dividing 2D space into regularly spaced aonrllellgppnng segments defined by angular position relative to the center node of the local neighborhood that the map being applied to. Then the center- neighbr node pair (v, v') is part of the ht sub-kernel mask (M,) when
Ml. (0,,0)]
2n H -
h
Φ ((,,0'))
h H
h [1, H 1],
Py((') (v) (x()") Pa (v)
0(v,0') tan-1
(0,,
where 0 is the angle of the neighbor node relative to the center node, Pa. and Py return the x and coordinates node, respectively, and is the total number of sub-kernels. The 0th sub-kernel is applied only the node pair (v, v) made up of the center node and itself. The offset angle is an optional hyperparameter that can be used to select the starting point from which the space is divided. To select H. choose the smallest number that results in all nodes within local neighborhood being assigned to different sub-kernel, which we refer to as satisficing mapping. It is easy to see that separating the local elements of tensor data based on this method produces the same assignments as the natural convolutional kernel masks (Fig. ff). Algorithm 2 in Appendix outliiees an efficient process for determining the value of that satisfies this condition. If the sub-kernel masks are chosen in this way and, importantly, the bias values for each sub-kernel are tied to the same value (i.e. b Br.; JK: Yh), then we arrive at a set of quantized graph convolution sub-kernels that will behave standard 2D convolutional layer on equivalent tensor data
on 2D positional graph data identically (see Appendix C for proof and below for empirical validation).
5

---

With this satisficing mapping approach, the process of assigning nodes in every local neighborhood to sub-kernels (see Algorithm | in Appendix DD incurs computational cost of ((VV in each forward pass. In the case of homogeneous graph meshes, choosing to cache the satisficing mapping incurs at worst (((V)²) space complexity. Using Algorithm 2 for determining the minimum number of subkernels for the convolution such that satisficing mapping is honored adds constant cost on top of Algorithm [ We note that this is only one of many possible ways in which the natural convolutional mask and sub-kernels described in Eq. 2 can be extended to positional graph data.
3.3 Learning neighborhood quantization
Next, we introduce a method for generating masks that assign nodes to sub-kernels in arbitrary dimensions and regardless of whether positional information is present. Specifically, we frame quantization as a learnable multinomial classification problem where for a learnable model assigns a sub-kernel to each center-neighbor node pair in a local neighborhood. This approach was inspired by the idea of dilated convolutions in CNNs, akin to learning the spacings the kernel elements during CNN convolution [1]. To learn the quantization, we introduce QuantNet, an MLP that projects node features or Jpositioa descriptors into a higher dimensional space where we difference the target and source features and then project this difference to a vector representing assignment weights for each sub-kernel (see Fig. 2]. The mask M,, associated with sub-kernel h contains the ordered node pair (v, o²) when QuantNet Q assigns the node pair to h:
MA = (,,,, -lnnee.wee) Q(u, r/) = argmax argmax(sftmaxx(25006rr)) U1 Ui(+':n):)))
where U1 is a high dimensional MLP projector with parameters 1j for the input features (spatial descriptors, node features, etc.), U2 is a low dimensional projector with parameters & for the difference in high dimensional features projected by U1. is a node V (the node set of the input graph), and ((v) denotes the local neighborhood node set of c. Note argmax in Eq. i symbolic; it represents any differentiable function that outputs discrete categorical samples, for example, a custom argmax implemented with a straight-through gradient estimator or Gumbel-Softmax with hard sampling (our implementation uses Gumbel-Softmax with hard sampling) [33. The QuantNet network architecture is shown in Fig. 2 Finally, reiterate that because QuantNer can use any vector in place of positional information, QGCL becomes extensible to graphs without explicit positional information.
3.4 Integrating QGCNs with a residual architecture
A common and successful approach used to address vanishing gradients and over-smoothing in GNNs is residual learning, inspired by the success of ResNets for CNNs [1). We adapt this framework
Suight socm
Vociible Dapa)
MU.4
Itipler socket)
mubhic Ne117
Text Cruph
Joancs rodes
Figure 2: QuantNet and Quantized Graph Residual Layer (QGRL). [Left] learnable network for dynamic quantization of nodes to subkernels in different local neighborhoods. The message passing framework PyTorch provides the source and target nodes across all edges so QGCL doesn') 't have any computation overheads in defining the input tensors fed into QuantNet. The output of QuantNet the satisficing mapping used to filter the receptive fields of the QGCL subkernels. [Right] An architectural retrofit of QGCL, incorporating 2 residual blocks: (1) outer residual block for the QGCL and (2) an inner residual block for learning features from input graph messages. The network combines all features dynamically via MIP-III to prepare the final node messages for the layer.

---

Table 1: Standard image datasets. CNN and QGCN model accuracies (mean + S.D.).
Dataset
Test Accuracy
CNN
QGCN
MNIST
98.92 0.10
98.98 = 0.04
PashionMNIST
92.56 + 0.18
92.39 = 0.13
CIFAR-10
80.21 0.29
79.59 = 0.35
Table 2: Custom Graph Datasets.
QGRN and SGCN Performance Comparison
Dataset
Parameters (k)
FLOPs (M)
Test Accuracy (%)
QGRN SGCN
QGRN
SGCN
QGRN
SGCN
-S--anary
58.67
57.37
535.17
800.32
99.67 + 00.23
99.67 = 00.23
NS-Denary-1 1
58.67
57.37
535.17
800.32
+7.47=0.000
94.23 01.32
NS- NS-Denary-2
58.67
57.37
535.17
800.32
95.13 05.21
AIDS
59.43
57.61
9.30
13.03
99.50 + 00.14
99.25 + 01.07
Letter (high)
56.33
49.72
0.77
0.98
94.10 + 00.81
93.21 + 00.79
Letter (low)
53.14
49.72
0.74
0.95
99.81 + 00.23
99.62 + 00.14
Letter (med)
53.14
49.72
0.74
0.95
97.14 + 00.71
95.24 + 00.79
to QGCNs, arriving at the architecture shown the right panel of Fig. 2 which we call Quantized Graph Residual Luyer (QGRL). Notice that QGRL subsumes and generalizes QGCL.
4 Experiments
4.1 Empirical validation of equivalence with CNNs on 2D images
First, we confirmed that the QGCL performs similarly the CNN convolutional layer when applied to image data. We considered three standard 2D image datasets that vary in complexity: MNIST (21]
Fashion-MNIST 41, and CIFARIO 10 19). MNIST contains gray-scaled images of handwritten digits of shape 28x28x1, FaShionMNIST contains fashion images of shape 28x28x1, and CIFARIO consists of color images of shape 32x32x3 from 10 categories. Figure
Appendix E shows the different CNN models trained for the different standardized datasets. We created 3-layer CNN and its equivalent QGCN model for the MNIST dataset, 6-layer network models for Fashion- MNIST, and 9-layer network models for CIFAR10 10. The equivalent QGCN models have the same architecture as the CNN models, except that QGCN uses QGCL layers internally in place of traditional convolutional layers. All models were trained 5 times on each dataset, with different random parameter initializations and random ordering of the training data for each run, using cross-entropy loss and the Adam optimizer [16] with a learning rate of 0.01 for 200 epochs. In order to establish equivalence between CNN and QGCN while avoiding full-dataset ceiling effects we separately trained models fit at three different sample sizes (yielding different variina trade-off's by varying the dataset train-test splits (see Appendix F).
Table D shows how QGCN performs almost identically to CNN across the different standard image datasets. [taandix[F[taaleeB shows the expanded version [ showing different train-test splits, devised to explore bias variance trade-offs. Additionally, Appendix G shows training loss and train/test set accuracy profiles over wide range of learning rates for both CNN and its parameter- matched equivalent QGCN (not QGRN) to show how model behaviors are very similar even in different bias-variance trade-off regimes. These results confirm how both models follow exceedingly similar loss trajectories during training and have the same accuracy profiles, empirically supporting our formal proof of CNN and QGCN equivalence on image data.
4.2 Graph Classification: Datasets with Positional Descriptors
Next, we compared QGRN to SGCN graph datasets that have positional descriptors. including novel FEM fixed-mesh graph dataset. The graph benchmark datasets: AIDS, Letters (high/low/med) post-processed to extract out their positional node descriptors into separate positional attributes

---

Table 3: Graph kernels benchmark datasets Test Accuracy (%) across different GCNs
Models
AIDS
Frankenstein
Mutag
Proteins
QGRN
99.50 = 0.10
75.58 + 0,40
99.99 = 00.26
80.20 + 00.14
GCNConv
90.92 = 0.38
60.27 + 0.06
92.68 + 02.29
71.95 00.57
ChebConv
93.42 = 0.14
62.56
0.28
91.87 + 01.41
75.58 + 01.51
GraphConv
94.25 + 0.16
65.89
95.12 00.48
74.59 00.57
SGConv
91.92 = 0.14
60.23
92.68 00.49
=
72.94 00.57
GENConv
99.17 + 0.14
0.42
98.37 01.41
79.87 :: 00.57
GeneralConv
94.33 + 0.14
65.67
92.68 + 00.45
74.59 + 00.57
GATv2Conv
98.58 + 0.38
63.71 0.29
+ + 01.41
80.20 + 00.99
TransformerConv
99.25 0.14
6
92.68 = 02.29
79.21 00.67
that QGRN and SGCN use. This was show that QGRN is able to use positional descriptors when they exist and is able to perform competitively with models such as SGCN designed specifically to positional descriptors. Table Table provides test set accuracy, as well model size and computational complexity for each model on each positional graph dataset. We highlight that QGRN performs equal to or better than SGCN on all positional graph datasets tested.
4.2.1 Custom FEM Dataset
We compare QGRNs and matched SGCNs on our new simulated Navier-Stokes non-linear dynamics benchmark datasets for binary and denary classification. We simulated the "flow past a cylinder" problem on an adaptive mesh with the underlying two-dimensional flow geometry depicted in Appendix [H] Fig. p. For binary classification, we separated laminar and turbulent flows based on distinct Reynold's 's number (Re) values while for denary classification we used evenly spaced Re values. We created three datasets: Navier-Stokes- Binnar (NS- (NS-Binary) for easier binary classification and Savier-Stokes Stokes-Denary-1 (NS-Denary-D) and Navier-Stokes- Ste---ttteee---r--2222 (NS- (NS-Denary-2) for more challenging denary classification, with NS-Denary-2 being most challenging (most closely spaced Re values; see Appendix HH.. QGRNs matched SGCN performance on the binary task and outperformed SGCNs on the more challenging denary tasks.
4.3 Graph Classification: Generic Graph Datasets
Finally, we compared QGRNs to matched (in model parameter count) GNN models using inductive learning datasets from Benchmark Data Sets for Graph Kernels [14], namely: AIDS, COIL-DEL, Frankenstein, Enzymes, Letter (low/med/high), Mutagenicity, Proteins, Proteins-Full, Mutag and Synthie. See Appendix [ for a description of each dataset. We trained on a number of novel GNN architectures including Transformer networks (GAT, TransfommerConv), showing how QGRN maintains superior performance over its competitors on many of the benchmark datasets (which lack positional descriptors). We size all models relative to QGRN to have matched number of parameters for fair comparison. Given the simplicity of some of the models, this effort of establishing equivalence yields slightly different architectures, however, all architectures depth. More details are provided the dataset configuration section of the provided code. All models trained with the Adam optimizer using cross-entropy loss for 500 epochs at 4 different learning rates 10.1, 1, 0.01, 0.001, 0.0001). Appendix subsection K shows how QGCN wall clock time varies compared other GNN methods with matching parameter sizes. Each is repeated 3 times and we report the best accuracy for each model across these learning rates.
constrained have the same
Tables 3 and 12 showcase QGRN matching and outperforming all GNN methods across diverse sampling of inductive graph learning problems. All datasets appearing in these tables either do not have positional descriptors have their positional attributes collapsed into the individual node features. We do this because many of the generalized GNNs in the literature such as ChebConv, GCNConv, GraphConv etc. are not able to handle positional descriptors separate attributes from node features. the tables, we see clearly how QGRN matches or outperforms all models on all benchmark graph classification tasks.
Finally, there are additional experiments we carried out such as how QGRN fares deeper networks (see Appendix O). how different quantizations impact model performance (see Appendix P. how
8

---

Table 4: Graph kernels benchmark datasets H. Test Aceuracy (%) across different GCNs
Models
Synthie
Letters (high)
Enzymes
Coil-Del
QGRN
99.99 = 0.23
94.10 = 0,81
72.50 = 00.96
94.14 = 00.78
GCNConv
80.89 = 0.70
40.76 0.29
43.61 = 00.48
20.42 = 00.39
ChebConv
55.56 0.40
48.06 = 01.74
27.86 = 00.29
GraphConv
89.43 + 0.70
0.22
46.94 00.48
26.91 = 00.30
SGConv
80.08 = 0.41
0.14
44.44 01.27
20.81 = 00.44
GENConv
92.28 + 0.86
0.8
67.22 + 02.93
81.91 = 00.86
GeneralConv
91.46 + 0.22
0.11
48.61 = 00.48
28.33 00.60
GATv2Conv
92.68 + 0.11
10.83
53.89 + 03.16
65.48 - 01.82
TransformerConv
92.68 + 0.11
$5.52
54.17 01.34
62.71 00.76
Table 5: Node Classification Datasets. Test Accuracy (%) across different GNNs
Models
Homophilic Cora
Heterophilic
Computers
PubMed
Chameleon
Squirrel
QGRN
90.02 + 0.02
89.02
0.14
89.11 + 0.15
74.15 + 0.37
56.17 0.45
GraphConv
87.96 + 0.16
87.15 0.44
88.39 + 0.07
72.77 0.32
64.25 + 0.09
GENConv
91.66 = 0.05
86.31 0.36
71.56 0.67
58.00 = 0.18
GeneralConv
89.29 = 0.02
87.64
78.11
66.80 = 0.08
EGConv
91.50 = 0.06
0.30
88.38 = 0.08
63.54 0.07
48.44 0.41
to determine the number of quantization bins for a given dataset (see Appendix Q and finally comparison of QGRN with leaderboard performances from papers with code (see Appendix M)).
4.4 Node Classification
Next, we evaluated the performance of QGRNs on various node classification tasks. We tested on multiple types of node classification datasets, including citation networks (like Cora, PubMed), Wikipedia hyperlinks networks (like such the Chameleon dataset) and product relations networks We highlight that the datasets used in this exploration exhibit different degrees of homophily and heterophily properties. The Chameleon and Squirrel datasets exhibit strong heterophily while all the others exhibit stronger homophily. We chose single architecture that proved reasonably performant across all the models we compared against (see Figure 5) in Appendix E). We include another novel GNN, EGConv [37] to highlight the competitiveness
(such as Amazon Computers) [33 35 42)
our method recent methods. We trained all models across a range of learning rates (0.1, 1, 0.05, 0.01, 0.005, 0.001) for 2000 epochs and mimicked early stopping by caching the model state that produced the largest validation set accuracy. Given the now apparent fact that Message Passing Neural Networks generally struggle with heterophilic datasets, we designed the generic architecture with edge directionality awareness, as inspired by authors Rossi et.
We see in Table T Tables and and 19 in Appendix L that QGRNs performed competitively across the homophilic datasets and appreciably well on the two heterophilic datasets. On the Chameleon heterophilic dataset QGRN performs moderately well, outperforming all comparison models except GeneralConv. The Squirrel dataset, which is the most heterophilic those we tested, proved more challenging for our QGRN models. Overall, QGRNs perform reasonably well on node classification tasks, especially in cases where the dataset exhibits homophilic properties.
4.5 Supervised Autoencoder Model of Emotional States in EEG data
major motivation behind these models was the need for more expressive ways model graphical data with positional information captured from complex geometrical surfaces. As demonstration of the practical value of QGRNs beyond standardized benchmark datasets, we developed a supervised autoencoder (SAE) to model brain networks related to valence in the publicly available DEAP dataset [8]] The last 42 of each recording the DEAP EEG dataset were divided into sliding windows of 3 s with 50% overlap, then were z-scored and spectral power calculated in four

---

Table 6: EEG SAE test set performance. All values are presented as the SeM over all subjects.
Models
QGRN
SGCN
MSE loss (Generative)
1787.33 = 315.51
2169.38 = 317.80
CE loss (Supervised) AUC
0.65 + 0.01
0.66 = 0.01
0.59 + 0.01
0.56 = 0.01
frequency bands (4-8 Hz, 8-12 Hz, 12-30 Hz, and 30-44 Hz) for each of the 32 electrodes. Power features were used as node attributes in a fully-connected graph containing all electrodes. We trained a separate model for each subject, dividing the data for each subject according to 64%/16%//00% train/validationnnest split. The generative objective for the autoencoder was mean-squared error (MSE) and the supervised objective was cross-entropy (CF) for classifying whether subjects self-rated their emotional state as positive valence (2 5) or negative valence (< 5) on a 9-point scale. Models were pre-trained for 1000 epochs on just the generative objective, then for another 100 epochs with one of 3 values of weight (100, 1000, or 10000) on the classification objective. Validation sets were used to select the weight and number of training epochs with highest area under the receiver operating curve (AUC). As shown in 6, we found that using QGRN layers in the same autoencoder architecture compared to SGCN layers resulted in better generative and supervised loss values on the held out test sets. In addition, the DGRN-baseer model resulted in appreciably better classification performance (measured by AUC) for this difficult classification problem.
5 Discussion
This work introduces Quantized Graph Convolution Networks (QGCNs), flexible framework for designing graph neural networks that extends the benefits of CNNs' strong local inductive bias to graphs. QGCNs "quantize" the space of possible neighbor nodes in a local neighborhood into fixed set of sub-kerness We show, both theoretically and empirically, that QGCNs are a generalization of CNNs to graphs with positional information. We extend QGCNs to arbitrary graphs by introducing the QuantNet method for learning sub-kernel assignment in a QGCN. We then show that embedding QGCL within a residual network architecture gives state-of-tt state-of-the-art results on suite of benchmark graph and node classification tasks, in addition to a novel Bavier-Stokes FEM dynamics classification dataset. Finally, we demonstrate that QGCLs improve the performance of supervised autoencoder to jointly model EEG data and emotional state.
One significant limitation of the current work is that the implementation of the QGCL is not yet efficient as demonstrated in the comparison of wall clock runtime with other models in Appendix K Future work will look into parallelized subkernel operations to demonstrate wall clock runtime competitive with similar models in the literature. QGCNs also do not generalize all CNNs, as cannot represent convolutional layers with and-numeered kernel sizes (i.e. no 'center' element) or stride sizes other than one. Finally, the use of the QGCL layer in more complex architectures such as U-Nets could be explored in future work, alongside examining the performance of this model on more inductive and transductive tasks to assess its strength in various learning scenarios.
We have shown that QGCNs are a true generalization of CNNs and therefore are capable of maintain- ing the same powerful inductive bias that has led to such great success in the application of CNNs. In our experience, QGCNs are more expressive and efficient at learning complex local patterns of correlation in graph data than competing methods, and we expect that QGCNs can be successfully applied in many domains where graph data are prevalent. We expect that future research into dif- ferent masking functions for QGCN sub-kernels (in addition the angular satisficing mapping and QuantNet masking functions we outline here) will further extend the potential usefulness of QGCNs.
Acknowledgments and Disclosure of Funding
NG is supported by the NIH CTSA TL1 training program via NIH/NCATS Grant #2TLITR2386. LG is supported by NIH 20IMH131534 R01MHI 18388, New Venture Fund 202423, a Whitehall Foundation grant (WF 2021-08-089, a Cornell Center for Pandemic Prevention Research seed grant, and an A2 Collective pilot grant (PennAlTech, NIA)
10

---

References
[1] J. Atwood and D. Towsley. Diffusion-comvoluttinnl neural networks. In D. Lee, M. Sugiyama. U. Luxburg. Guyon, and Garnett, editors, Advances Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
[2] S. Brody, U. Alon, and Yahav. How attentive are graph attention networks?, 2022.
[3] Bruna, W. Zaremba, A. Szlam, and LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 1312.6203, 2013.
[4] Chen, Ma, and C. Xiao. Fastgen: Fast learning with graph convolutional networks importance sampling, 2018.
[5] T. Danel, P. Spurek. J. Tabor, M. Smieja, L. Struski, A. Slowik, and L. Maziarka. Spatial graph convolutional networks. In International Conference Neural Information Processing, pages
Springer. 2020.
[6] M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advonces in neural information processing systems, 29, 2016.
[7] J. Deng, W. Dong, Socher. L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: large-scale hierarchical image database. 2009 IEEE Conference on Computer Vision and Patter Recognition, pages 248-255, 2009.
[8] D. Duvenaud, D. Maclaurin, J. Iparraguirre, Bombarell, T. Hirzel, A. Aspuru-Guzik, Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
Adams.
[9] A. Feng, C. You, S. Wang, and L. Tassiulas. Kergnns: Interpretable graph neural networks with graph kernels. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 6614-664666 46622, 2022.
[10] H. Gao, Z. Wang, and Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD international conference knowledge discovery & data mining, pages 1424, 2018
[11] Hamilton, Ying. and J. Leskovee. Inductive representation learning on large graphs. Guyon, Luxburg. S. Bengio, Wallach, R. Fergus, Vishwanathan, and Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[12] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition, 2015.
[13] E. Jang, S. Gu, and B. Poole. Categorical Reparameterization with Gumbel-SSftmax, Aug. 2017. arXiv:1611.011 144 [cs, stat].
[14] K. Kersting, N. M. Kriege, C. Morris, Mutzel, and M. Neumann. Benchmark data sets for graph kernels, 2016.
[15] I. Khalfaoui-Hassani, T. Pellegrini, and T. Masquelier. Dilated convolution with learnable spacings, 2023.
[16] D. P. Kingma. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
[17] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arviv: (eee::699.00000 020900297,,2116
[18] S. Koelstra, C. Muhl, M. Soleymani, J.-S. Lee, A. Yazdani, T. Ebrahimi, T. Pun, A. Nijholt, and Patras. Deap: A database for emotion analysis; using physiological signals. IEEE transactions on affective computing, 3(1):18-31, 201
[19] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[20] Y. LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard, W. Hubbard, and L. D. Jackel. Backpropa- gation applied to handwritten zip code recognition. Neural Computation, 1:541-551, 1989.
[21] Y. Lecun, I.. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEF, 86(11):222 1)2278-2234, 1998.
[22] G. Li, M. Müller, A. Thabet, and B. Ghanem. Deepgens: Can gens go as deep cnns?, 2019.
[23] G. Li, C. Xiong, A. Thabet, and B. Ghanem. Deepergen: All you need train deeper gens, 2020.

---

[24] Q. Li, Z. Han, and X.-M. Wu. Deeper insights into graph convolutional networks for semi-supervised learning, 2018.
[25] R. Li, S. Wang, F. Zhu, and J. Huang. Adaptive graph convolutional neural networks, 2018.
[26] M. M. Lopez and J. Kalita. Deep learning applied to nlp, 2017.
[27] Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. Interna- tional conference on machine learning, pages 2014-2023. PMIR, 2016.
[28] G. Nikolentzos, Meladianos, A. J.PP. Tixier, K. Skianis, and M. Vazirgiannis, Keree graph convolutional neural networks, In Artificial Neural Networks and Machine Learning-ICANN 2018: 27th International Conference Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27, pages 22-32. Springer, 2018.
[29] C. Norberg. Flow around a circular cylinder: aspects of fluctuating lift. Journal of fluids and structures, 156-44):45--669 2001. 2000.
[30] K. Riesen and H. Bunke. lam graph datahase repository for graph hased pattern recognition and machine learning. In N. da Vitoria Lobo, T. Kasparis, F. J. Kwok, M. Georgiopoulos, G. C. Anagnostopoulos, and Loog, editors, Structural, Syntactic, and Statistical Puttern Recognition, pages 287-297, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[31] Y. Rong, W. Huang, Xu, J. Huang. Dropedge: Towards deep graph convolutional networks on node classification, 2020.
[32] E. Rossi, B. Charpentier, F. Giovanni, Frasca, Günnemann, and M. Bronstein. Edge directionality improves learning on heterophilic graphs, 2023.
[33] B. Rozemberezki, C. Allen, and R. Sarkar. Multi-scale attrihuted node emhedding, 2021.
[34] Schäfer, Turck, F. Durst, E. Krause, and R. Rannacher. Benchmark computations of laminar flow around cylinder. Springer, 1996.
[35] O. Shehur, M. Mumme, A. Bojehevski, and S. Günnemann. Pitfalls of graph neural network evaluation, 2019.
[36] Y. Shi, Huang, W. Wang, H. Zhong, Feng, and Y. Sun. Masked label prediction: Unified massage passing model for semi-supervised classification, 2020.
[37] S. A. Tailor, L. Opolka, Liò, and N. D. Lane. Do need anisotropic graph neural networks?, 2022.
[38] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Lio. Y. Bengio, al. Graph attention networks. stat, 1050(20):10 485500 2017.
[39] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks, 2018.
[40] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu. A comprehensive survey graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4 24, 2021.
[41] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 077771770..0747, 2017.
[42] Z. Yang, W. W. Cohen, and R. Salakhutdinov. Revisiting sumi-super learning with graph embeddings. 2016.
[43] W. Yin, K. Kann, M. Yu, and H. Schütze. Comparative study of cnn and mn for natural language processing. 2017.
[44] L.. Zhao and L. Akoglu. Paimorm: Tackling oversmoothing in gnns, 2020.
12

---

A
Code
Please find the code-base for the paper here: http:://ggttb..ccc//roooolllaaaa QuantNets
B Nomenclature disambiguation
The table meant to assist with disambiguating different layer, network and model names introduced this paper.
Table Glossary. Terms used in this paper and quick reference meaning
Name
Expanded
Comment
QGCL
Quantized Graph Convolution Layer
CNN-equivalent convolutional lay- er that can be applied to graphs with (pseudo--possitional information
QGCN
Quantized Graph Convolution Network
A network model that subsumes the QGCLs
QuantNet Quantizing Network
A learnable network for assigning nodes in local neighborhoods to QGCL sub-kernels
QGRL
Quantized Graph Residual Layer
QGCL retrofitted with residual net- work architecture
QGRN
Quantized Graph Residual Network
A network model that subsumes QGRLs
C
The satisficing mapping QGCL for 2D positional graphs extends the 2D local convolutional layer
In this section we formally prove that the satisficing mapping QGCL described in Section 3.2 is identical to the convolutional kernel on the local neighborhood of array elements (i.e. kernel) as described in Section 3.1
Theorem 1. The satisficing mapping QGCL is identical 3 x 3 convolutional layer when applied to 2D array data converted to a 2D positional graph by forming edges between adjacent elements (i.e. nodes).
Proof. We have already defined the output of the satisficing mapping QGCL 3 and (3.2): ; and we have shown that the output of standard convolutional layer is given by (2) in Section 3.1 Here, it is sufficient to show that these two are equivalent when using 2D array data that represented as a positional graph.
13

---

Whin
Σ s(le)))
Bi.
(6)
h=0
w'E((w)
2
Wh.:
(h=3)+ a (((ttakta))
+ Br:
(7)
h=0
== k=0
2
Wh Wha:
(h=3j++)) G jtcktdd
+ B
(8)
h
J=0 km
2
2
b
What
11=33+ +)) Gjtcktd;
+
(9)
9
k=
c,d,;
(10)
The proof begins by restating the definition of the QGCL in (6). As described in Section 3.2 the
sub-kernel masks are chosen such that within each local neighborhood N(v)) each mask M, is selective of single neighbor node v'. Thus we can iterate over each sub-kernel and mask by iterating over the rows and columns of the equivalent convolutional kernel, giving (7). We use '/ to represent
the node associated with the array data Go,b.s. which gives (8) Section 3.2 we define the bias
b vectors associated with each sub-kernel BA JK vh, giving This is equivalent to the form given (2) in Section 3.1 completing our proof.
This equivalence indicates that both types of convolutional models will produce identical output vectors during inference when given the same parameters (W, b) and input data (G). This also means that gradients with respect to the parameters will be identical for the purposes of backpropagation, because f(z) = g(z) implies 0f da 8x 82
D Quantizing local neighborhoods with satisficing mapping
Algorithm Quantization algorithm: pseudo-code
Input: G = (V, E, P) and S, where V is the node of G. E is the adjacency matrix of G, P is the positional descriptors for all nodes in V and S is the list of subkernels
and their angular centroids or quantization ranges.
Helper Functions:
exnb extracts local graph neighborhoods crad computes relative angular distances
gski gets subkerel (by index) node maps to M + {}
for E V do
N, + exnb(G, a)
for b E No do r + crad(a, b) i_index: + r))
M.add( (b, k)
return M
14

---

Algorithm shows in pseudo-code the operation to be done deterministically in each forward pass iteration of the QGCL model with satisficing mapping kernels. Notice that we have (()]V where [V| is the cardinality of the node set of the graph and k is the constant overhead of computation in each neighborhood map nodes to specific kernels: this is the complexity of the function named gski. For homogeneous graphs with fixed graph meshes, this computation could be cached, adding memory/space cost (()) exemplified in the strongly connected graph scenario.
D.1 Determining the minimum number of sub-kernels per QGCL layer
Algorithm 2 QGCL minimum sub-kernel number
Input: G= (V, E, P) and ub, where V is the node set of G, E is the adjacency matrix of G, P is the positional descriptors for all nodes in V and uh the upper-bound on number of sub- kernels in the QGCL layer.
Helper Functions:
mnd extracts graph's max node degree ernb - extracts local graph neighborhoods absk assigns angular bins to sub-k tub-kennlls crad computes relative angular distances ansk assigns neighborhood nodes sub-kernels
inai determines if neighborhood assignment is injective
M mG)(G)
if M 2 ub then return ub
else
N - exnb(E)
for i M until ub do
ke
k number of sub-kernels
9 + 360
b absk(k:g) g)
for n E N do
a crad(n)
is injective <- (ans(an,, b))
not is injective then break
is injective then return k
return ub
We introduce Algorithm 2 to establish the minimum number of sub-kernels necessary to ensure satisficing mapping across any arbitrary static graph dataset. This algorithm runs once during the first training epoch to initialize the minimum number of sub-kernels necessary for the particular dataset. This cost occurs just once for the very first batch of training data; afterwards the mapping of sub-kernels to local neighborhood nodes can be cached so that subsequent batches and nodes can reuse it. The runtime complexity of the algorithm is O(IV12) where [V] represents the cardinality of the graph node set. This worst-case asymptotic complexity is observed in strongly connected graphs. The quadratic dependency on [V] arises from the inner for loop, which iterates through each node within the graph (resulting in an O(VV) operation) and computes relative angular displacements for each local neighborhood (another O(VV) worst-case-complextty operation the case of strongly connected graphs) to assign nodes to their respective sub-kernels. Caching incurs (2(V(2) space cost the case of strongly connected graphs where the same node every neighborhood maps to different subkernel.
15

---

(0) Convolution
karnet with relative
Sample
coordinates
neighborhood with
weights
relattve spattal
coordinates nodes
(b) Visualizing different stages in convolution
operation between kernel and
Kernel weights
Receptive Fields of weights
1D convolution with weights
Partial Outputs
(d) Rethinking CNN convolutions linear combination 1D convolutions
Figure 3: Visualization of natural ranking of nodes within local neighborhoods of image graph data via relative positional descriptors, which imposes natural relative positional descriptor label on the convolving sub-kernels.
E
Model Architectures
4K
MNIST CNN architocturc
(b) FashionMNIST CNN architecture
7x
(c) CIFAR10 CNN architecture
Figure 4: CNN models trained for different standardized datasets: MNIST, FashionMNIST and CIFARIO. QGCN and SGCN architectures were exactly the same as the CNN architectures except with the convolutional layers replaced with QGCL and SGCN layers.
16

---

Com-Rolo
Core Con-Batttieerm-lee Reto
Node Classification Task Architecture
Figure 5: Neural GNN Architecture for Node Classification Task. All GNNs we tested had the same architecture as depicted. The generic architecture has blocks, the first is a convolutional layer followed by batch normalization and then ReLU activation function. The second block in the architecture sums up features from three identical blocks, each of which is a convolutional layer followed by ReLU activation function. For any given GNN, it's message passing layer was substituted into the convolutional layer, depicted the figure, to derive the overarching architecture. In doing so, guaranteed iso-architecture comparison.
F Standard Datasets: Full Results
We trained CNN and QGCN models sub-sampled splits of the standard image datasets described in the main paper. The splits chosen were: (train, test) = (100, 20), (1000, 200) and (10000, 1000), with equal sampling across categories. These sub-sampled versions of the data allowed greater variance in model performance, facilitating clearer comparisons across methods. Here, we compared training loss, and train/test accuracies across various learning rates for both CNN and QGCN. We train all models three times on different splits of the datasets.
Table provides results collated across various train-test splits, in effort to capture model performance different birs-variance regimes.
G Learning Rate Charts
Figure 6: MNIST dataset results Figure for 100:20 dataset split
17

---

Table 8: Standard Datasets. CNN and QGCN model accuracies (mean = S.D.) standard datasets
Dataset
Train:
Test Accuracy
CNN
QGCN
MNIST
100:20
76.67 + 5.77
74.33 6.56
1000:200
95.50 + 0.71
97.50
10000: 1000
97.91 + 1.02
97.57
10000:10000
98.92 0.10
98.98
Fashion-
100:20
72.67 + 2.31
MNIST
1000:200
84.67 0.03
63.67
10000: 1 1000
90.13 + 0.03
90.23 + 0.26
60000:10000
92.56 0.18
92.39
CIFAR-10 10
100:20
23.67 2.52
24.33
1000:200
49.33 0.08
47.67 #
10000:1000
68.08 0.45
66.95 1.07
50000:10000
80.21 0.29
79.59 0.35
Mockl them Lac aptino Loane Pate
Mordd Thal decome fulz
Figure MNIST dataset results Figure for 1000:200 dataset split
Model Train Loss against Learning Rate
Model Test Accuracies against Learning Rate 1.
0.00001
0000001
Ratz
Figure 8: MNIST dataset results Figure for 10000:1000 dataset split
Loarning
Aoc.rooocyyyyoo Leornnng
3.0000
Figure Fashion-MNIST dataset results Figure for 100:20 dataset split
18

---

Model Train Leaming
Model Ascuaay Learning
Midde Trd Arruney trorning Part
Figure 10: MushiOn-MNIST dataset results Figure for 1000:200 dataset split
Model Train Loss Learning Rate
Model Test Accuracy Learning Rate
20
ONN Q00P
Figure 11: Fashion-MNIST dataset results Figure for 10000:1000 dataset split
L0O0C
Figure 12: CIFAR-10 dataset results Figure for 100:20 dataset split
Train
Model Acouncy Leaming
Model Text Latarinnn
Figure 13: CIFAR-10 dataset results Figure for 1000:200 dataset split
19

---

Model Train Loss vs Learning Rate
Madel Test Accuracy vs Learning Rote
CMH
43
40-
0.5
0.00211
13
011
100
0,011
0985
29801
000XL
Searing
Leaning
Figure 14: CIFAR- 10 dataset results Figure for 10000:1000 dataset split
H
Custom FEM Dataset
1,40
1.50
1.50
2,30
(b) Color map visualization vortex shedding behavior for Re=120 (on an adaptive mesh with 1446 nodes and 2897 elements)
(a) Underlying 2D geometry and boundary conditions
Figure 15: Underlying geometry and the flow around circular cylinder.
We introduce several simulated Navier-Stokes non-linear dynamics benchmark datasets for both binary and denary classification tasks on FEM graphs. We simulated the "flow past cylinder" problem on an adaptive mesh with the underlying two-dimensional flow geometry depicted in Figure 15p. We assumed fluid density of p 1.0 and dynamics governed by the time-dependent Navier-Stokes Equation:
- v + uAu Vp= = V, u=
(11)
Here, represents velocity and represents pressure. We adopted kinematic velocity of 0.001. For the lower and upper walls, as well as the boundary of the cylinder, no-slip boundary conditions were imposed. On the left edge, preseribed parabolic inflow profile u(0. y)
(W0((0.41-)).0) with maximum velocity U = Softe Here, Re and D denote the Reynolds number 0.412 and the diameter of the cylinder, respectivcly. On the right edge, do-nothing boundary conditions define the outflow u pm = 0 with denoting the outer normal vector. We employed FEniCS library for solving the governing Navier-Stokes equations, using the adaptively refined mesh as shown in Figure [pp for the spatial discretization in the finite element implementation. We conducted simulations produce dataset of flow velocities, covering a range of Reynolds numbers spanning flow exhibits a stationary behavior. However,
2D
values 20 to 120. At lower Reynolds numbers, as the Reynolds number increases, fascinating phenomenon known Karman vortex shedding emerges. This phenomenon results in the flow adopting a time-periodic behavior, characterized by vortex shedding occurring behind the cylinder (29) 34)). It's important to note that in simulations, the primary flow direction is horizontal, emphasizing the significance the x-component of velocity.
We generated the graph dataset representing fluid velocity components in standard PyTorch Geo- metric format. We explored two inductive learning tasks with the graph dataset: binary and denary classifications. For binary, we separated laminar and turbulent flows based on distinct Re values, while for denary classification, we used evenly spaced Re values across a range. We created three datasets, as illustrated in T Navier-Stokes-Bing Binary (NS-Binary) for binary classification and Navier-Stokes- - (NS-Denary-I) and Wavier-Stokes- 2enkes--enary-2 (NS-Denary-2) for denary classification, with NS-Denary-2 being more challenging. Training data for each Re value is from the
20

---

initial time period, and test data is from later time steps in the simulation, so models predict classes for future time points they have not seen.
Table The table captures the different Re ranges we considered for the different custom datasets and the step sizes. Notice in the binary case that Re 20-40 are grouped in laminar class and 100-120 into the turbulent flow class.
Dataset
Re range
Re step-size
NS- NS- IS--Binrr
20-40. 100-120
5
NS- NS-Denary-1
30-120
10
NS- NS-Deny
20-40, 100-120
5
Table 10: Shown in the table are different custom dataset splits have provided as part of this paper. The third column captures the training time period per Re from which train data were aggregated from the FEM time series solutions
Dataset
Train:Test
Train Time (s)
NS-Binary
100:20
0- 0.005
NS- IS-Binary
1000:200
0-0,5
NS- AS--Biarr
10000:
0-
NS-Binary
20000:5000
0-
NS- Denary-1
100:20
0.0.00
NS-Denary-
1000:200
0.0.
NS-Denary-
10000: 1000
0-5.5
NS-Denary-1
20000:2000
0-0.0
NS-Denary-2
100:20
0.0.0
NS-Denary-2
1000:200
0.0.55
NS-Denary-2
10000: 1000
0.
NS- Denarryy2
20000:2000
0 1.0
21

---

I Benchmark Datasets for Graph Kernels
The diverse set of Benchmark Data Sets for Graph Kernels we used for validating QGRN and other GNN methods are as introduced below:
AIDS. 2000 sample binary classification dataset of molecular compounds with classes active and inactive, representing activity against HIV.
COIL-DEL. 3900 sample graph dataset extracted from images of 100 different objects taken at different poses (with pose interval degrees)
Enzymes. 600 sample size enzymes dataset with 6 classes (each of which represents one of the 6 EC top-level classes) from the BRENDA enzyme database.
Letter (low/med/high). 2250 sample datasets of graphs representing distorted letter drawing with 15 classes, each corresponding to different Roman alphabet letter. low, med and high represent different degrees of distortions applied to the hand-drawn letter graphs.
Mutagenicity. 4337 sample binary classification dataset of chemical compounds with classes mutagen and non-mutagen.
Proteins and Proteins-Fult 1113 sample size binary classification datasets for classifying protein graphs into enzymes or non-enzymes.
Proteins-Fued Full differs in that it has many more node features: Proteins=3 and Proteins-Futde Fuleln1
Frankenstein. A 4337 sample binary mutagenicity classification dataset modified from the BURSI dataset with classes, mutagen and non-mutagen. This dataset has continuous node features with very high dimensionality: 781 features per node.
Mutag. 188 sample binary classification dataset of chemical compounds and their mutagenic effect on bacterium
Synthie. A 400 sample Erdös Erdös-Rényi Rényi synthetic graphs dataset with classes generated with prob- abilistic models. Figure 16 shows the distribution of the dataset samples across their different classes.
Distribution of Classes across Renchmark Graph Datasets- A
Distribttion of Classes ecross Benchmark Graph Datenets -
4000
590
600
(ew/nedhhgg))
2030
Figure 16: Distribution of samples by classes across all datasets used in this paper. We exclude COIL-DEL because has 100 classes each with 39 samples and hence would render the plot illegible.
J Graph kernels benchmark datasets: additional results
Tables II and 12 contain additional results worth highlighting.
22

---

Table 11: Standard datasets. CNN and QGCN model accuracies standard datasets
Dataset
Train:Test
Train Accuracy
Test Accuracy
CNN
QGCN
CNN QGCN
MNIST
100:20
95.33 + 0.05
92.67 = 2.31
76.67
74.33 6.56
1000:200
99.67 + 0.02
99.67 0.02
95.50 0.71
97.50
10000: 1000
97.91
97.57
60000:10000
98.92
98.98
Fashion-
100:20
99.67 + 0.58
98.33 = 1.15
2.33
72.67 + 2.31
MNIST
1000:200
99.50 + 0.71
97.05 = 0.71
84.67
83.67 0.11
10000: 1000
0.00
90.23 + 0.26
60000:
9
92.39
CIFAR-10 10
100:20
96.67 + 4.93 99.33 + 0.33
99.33 = 0.58
23.67
24.33 2.31
1000:200
95.33 = 0.71
19.33
47.67 0.20
10000: 1000
68.08 + 0.45
66.95 + 1.07
50000:10000
80.21 0.29
79.59 0.35
Table 12: Graph kernels benchmark datasets I11. Test Accuracy (%) across different GCNs
Models
Mutagenicity
Proteins-Fad
Letters (low)
Letters (med)
QGRN
83.80 + 00.33
87.13 + 00.55
99.81 + 00.11
96.76 + 00.63
GCNConv
60.60 + 00.19
85.15 + 00.86
64.95 + 00.22
41.52 01.39
ChebConv
68.66 + 00.17
85.15 00.99
73.27 00.22
63.18 + 00.40
GraphConv
68.66 00.17
$5.48+00.33
74.29 00.19
64.25 00.90
SGConv
60.60 = 00.11
84.16
65.21 00.11
42.10 = 00.57
GENConv
81.10 00.34
#5.48200.33
99.11 00.11
90.92 00.67
GeneralConv
68.81 + 00.11
85.48 + 00.57
74.29 00.19
64.19 = 00.50
GATv2Conv
80.02 00.33
84.16
96.70 00.55
85.84 00.98
TransformerConv
78.36 + 00.34
85.15 + 00.72
98.09 + 00.11
90.10 = 00.50
K
Graph kernels benchmark datasets: model parameters and wall clocks
Table 13: Graph kernels benchmark datasets J. Model sizes (number of parameters)
Models
AIDS
Frankenstein
Mutag
Mutagenicity
Proteins
Proteins-Full
QGRN
64.86
1409.33
57.15
63.69
63.97
73.61
GCNComv
63.36
1437.89
57.54
62.59
62.79
68.16
ChebConv
64.13
1400.48
56.45
65,67
65.95
74.02
GraphCony
67.71
1447.30
56.45
66.69
66.95
74.11
SGConv
63.36
1408.83
57.54
62.59
62.79
72.61
GENConv
71.62
1399.17
60.80
60.80
60.99
74.82
GeneralConv
60.10
1393.67
59.33
59.33
59.52
77.51
GATv2Conv
64.13
1391.62
63.36
63.36
63.55
68.93
TranformerConv
64.90
1307.91
63.36
63.36
63.75
74.50
23

---

Table 14: Graph kermels benchmark datasets I. Model sizes (number of parameters)
Models
Synthie
Letters (h)
Letters ())
Letters (m)
Enzymes
Coil-Del
QGRN
68.19 19
61.51
58.21
58.21
69.71
70.34
GCNConv
65.54
60.21
60.21
60.21
66.57
61.09
ChebConv
69.96
59.15
59.15
59.15
71.81
75.56
GraphCony
70.53
59.15
59.15
59.15
71.81
75.56
SGConv
70.72
60.21
60.21
60.21
71.88
75.43
GENConv
73.28
62.67
62.67
62.67
74.18
73.64
GeneralConv
67.52
62.86
62.86
62.86
68.93
65.83
GATv2Conv
66.18
52.18
52.18
52.18
67.08
69.92
TranformerConv
68.87
53.88
52.88
52.88
70.50
70.12
Table 15: Graph kernels benchmurk datasets I. Google TPU Inference latency. Wall clock (in ms)
Models
AIDS
Frankenstein
Mutag
Proteins
QGRN
12.38 + 0.38
17.50 1.02
14.74 = 0.42
15.69 + 2.28
GCNConv
2.39 0.04
3.04 + 0.32
3.82 = 0.63
2.42 1 0.14
ChebConv
5.65 + 0.24
5.53 + 0.37
3.61 = 0.20
6.25 0.43
GraphConv
1.25 0.05
1.81
1.16 0.04
1.60
SGConv
4.20 0.09
0.83
4.10 0.26
4.37 0.44
GENConv
1.58
1.19
1.49
1.57
GeneralConv
1.67 #.06
0.227
1.36
1.54
GATv2Comv
3.33 - 0.27
4.11
3.34
3.56 0.33
TransformerConv
3.50 + 0.24
4.06 0.34
3.27 107=0 0.13
4.09 + 0.44
Table 16: Graph kernels benchmark datasets 1I. Google TPU Inference latency. Wall clock (in ms)
Models
Synthie
Letters (high)
Enzymes
Coil-Del
QGRN
13.46 + 1.65
10.83 + 0.20
13.46 + 2.34
13.68 + 0.99
GCNConv
2.45 + 0.14
2.26 + 0.06
2.33 0.06
2.37 + 2.37
ChebConv
6.12 1 1.80
3.88 0.28
4.99 1.33
3.65 + 0.08
GraphConv
1.00
1.06
1.47
1.26 0.14
SGConv
0.19
4.13
4.32 0.23
4.70
GENConv
0.18
1.54
0.007
1.51
GeneralConv
1.47
1.09
1.12
1.45 - 0.08
GATv2Conv
3.37 + 0.31
4.29
3.29
3.31 + 0.08
TransformerCony
3.50
4.63 1.11
3.56 0.23
3.78 + 0.17
Table 17: Graph kernels benchmark datasets III. Google TPU Inference latency. Wall clock (in ms)
Models
Mutagenicity
Proteins-Full
Letters (low)
Letters (med)
QGRN
24.88 + 9.04
15.73 1.07
14.12 + 2.53
10.45 = 0.53
GCNConV
3.07 + 0.32
2.48 0.11
3.50 0.75
2.40 0.13
ChebConv
4.81 + 0.21
6.26 = 0.56
3.70 + 0.16
3.73 +.26
GraphCony
1.27 0.02
1.62 0.04
2.10
1.22
SGConv
4.84
5.57 1.22
4.12
4.03
GENConv
1.50 0.03
1.62=0.12
1.42
1.55
GeneralConv
1.58 0.08
1.56 0.18
1.42 0.05
1.55 1.15
GATv2Conv
4.06 + 0.97
3.35
3.18
TransformerConv
4.12 1.09
3.89 0.16
3.34 0.27
3.16

---

L Graph Datasets: Node Classification
Tables 18 and 19 representing homophilic and heterophilic dataset results respectively, provide the full set of datasets, against which we benchmarked, for node classification tasks.
Table 18: Homophilic node classification datasets. Test Accuracy (%) across different GCNs
Models
Photo
Computers
Cora
PubMed
CiteSeer
QGRN
95.34 + 0.10
90.02 + 0.02
89.02 + 0.14
89.11 + 0.15
79.09 + 0.27
GraphConv
94.44 0.04
$7.96 0.16
87.15 0.44
88.39 + 0.07
76.69 + 0.07
GENConv
95.25 = 0.04
91.66 0.05
86.31 + 0.36
87.73 0.19
75.37 0.34
GeneralConv
94.13 = 0.14
19.29
87.64 0.04
88.97
75.53 0.10
EGConv
96.19 + 0.05
91.50 + 0.06
88.34 + 0.30
88.38 + 0.08
76.34 0.21
Table 19: Heterophilic node classification datasets. Test Accuracy (%) across different GCNs
Models
Chameleon
Squirrel
QGRN
74.15 0.37
56.17 + 0.45
GraphConv
72.77 + 0.32
64.25 + 0.09
GENConv
71.56 + 0.67
58.00 0.18
GeneralConv
78.11 + 0.29
66.80 + 0.08
EGConv
63.54 + 0.07
48.44 0.41
M Leader Board Comparison with QGRNs
Our search for state of the art performance was limited to Papers with Code, which has only subset of the datasets we trained on. This, we believe, is indicative of the fact that in literature, a subset of these benchmarks inductive classification tasks. After searching thoroughly through Papers with Code, we found what believe to be the full subset of data sets with comparable SOTA results below:
chosen for different types of downstream tasks. Our method mostly focused
Table 20: Leader-board (Papers with Code). Comparison QGRN performance to leading models Dataset
Average Test Accuracy (%) Leading Model Name
QGRN
Leading Model
AIDS
99.50
97.30
k-NN classifier: IAM Repository
MUTAG
100.00
100.00
Evolution of Graph Classifiers
Mutagenicity
83.80
83.00
Tree-G
Proteins
80.20
84.91
HGP-SL
Enzymes
72.50
78.39
DSGCN-allfeat-2000
Frankenstein
75.58
78.90
GWL WL (Graph Invariant Kernels)
N IAM Graph Database Comparison with QGRNs
The conference paper. "IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning" ((30), provides k-NN classifier-based results that the authors intended as "a first reference system compare other algorithms with". Clearly these do not represent SOTA results, but we include them as another baseline comparison available for the data sets considered in our paper:
25

---

Table 21: IAM Graph Database Repository. Comparison of QGRN performance k-NN classifier
Dataset
Average Test Accuracy (%)
QGRN
k-NN
Letters (low)
99.81
99.60
Letters (medium)
96.76
94.00
Letters (high)
94.10
90.00
Coil-Del
94.14
93.30
AIDS
99.50
97.30
Mutagenicity
83.80
71.50
Proteins
80.20
65.50
Training Deeper QGRNs
present some preliminary results on training deeper QGRNs, in an effort to understand the model's ability to overcome GCNs inability to go deep. In this exploration, trained different depths of the same QGRN model each on 2 different datasets. These datasets roughly capture the extremes of dataset difficulty in the paper. We trained on the AIDS dataset: small binary classification 1600:400 train:test split dataset, and the Letters (high) dataset: more complex dataset with 15 classes and train:test 1725:525 split. We trained these models with ADAM optimizer and cross entropy loss, under the same conditions as used elsewhere in the paper (see Sec. 4.3
Table 22: Deeper QGCN and QGRN networks. Sample results illustrating impact of deeper network model performance
Dataset
Model Depth
Model Size (K)
Mean Test Accuracy (%
QGCN
QGRN
QGCN
QGRN
AIDS
30.91
59.43
99.25
99.50
59.62
101.26
99.25
99.25
88.32
143.09
99.25
99.25
12
117.03
184.92
99.25
99,00
18
174.43
268.58
99.25
99,00
Letters (high)
30.90
56.33
92.95
94.10
59.60
95.07
91.24
93.33
88.30
133.81
89.57
91.19
12
117.01
172.55
90.23
91.24
174.42
250.05
87.24
90.86
Discussion: From the results compiled in ta do that as the depth of the network increases there is modest reduction overall model performance. The results also reveal that the extent of model performance regression depends the complexity of the dataset. The AIDS dataset is less sensitive to model depth: scaling the model depth by 6x (from 3 to 18) results in just a 0.5% loss in mean test accuracy. Letters (high), on the other hand, more performance loss the same 6x depth, i.e., 5% loss in performance. Though part of the regression could be attributed to insufficient number of epochs for the deeper networks, but speculate that it is largely due our residual network retrofit in our QGRN layer not being sufficient to mitigate the effects of depth (e.g., the vanishing gradient problem). There several exciting findings the literature that have suggested methods such as customized aggregators instead of standard addition and softmax aggregation in the message passing network (layer level innovations). Others approach this problem architecturally, e.g., borrowing from successful architectures such as ResNets (as we did), using skip connections, pooling and sampling layers, drop-out inspired methods, and so on. We highlight that our paper's focus is primarily extending CNN's convolution operation to arbitrary graphs, which we demonstrate the case through our equivalence analysis. this context, we highlight that deep vanilla CNNs also face this same challenge of being difficult to train. In the world of CNNs, this problem is combated via architectural innovations such as batch normalization, use of better activations like ReLU, skip connections etc. In this light, layer-level innovation with quantizable neighborhoods (replicating
26

---

CNN-like convolution) also stands to benefit from such architectural designs that allow for robust and deeper network architectures, which we leave future work.
P Performance impact of quantization
Here, explore pilot comparison of satisficing (angular) mapping and QuantNet to understand how quantizing the neighborhoods uniformly vs learning the quantization affects model performance. We able compile together some sample results that provide some insight into this, which share in Table 23 In Table 24] we considered the impact of using pseudo-positional descriptors (here, the entire node attributes) opposed explicit spatial descriptors positional descriptors.
Table 23: Deeper satisficing mapping (SM) and QuantNet networks. Sample results illustrating impact deeper network on model performance
Dataset
Model Depth
Model Size (K)
Mean Test Accuracy (%)
SM
QuantNet
SM
QuantNet
AIDS
3
30.91
59.43
99.25
99.50
6
59.62
101.26
99.25
99.25
9
88.32
143.09
99.25
99.25
12
117.03
184.92
99.25
99.00
18
174.43
268.58
99.25
99.00
Letters (high)
3
30.90
56.33
92.95
94.10
6
59.60
95.07
91.24
93.33
9
88.30
133.81
89.57
91.19
12
117.01
172.55
90.23
91.24
18
174.42
250.05
87.24
90.86
Table 24: 3-layer QGRN model analysis. Sample results for QGRN model trained with and without positional descriptors.
Dataset
Average Test Accuracy
With Positional Descriptors
Without Positional Descriptors
AIDS
99.50
99.50
Coil-Del
94.57
94. 14
Letters (high)
94.10
94.10
Letters (med)
97.14
96.76
Letters (low) 100.00
99.81
Discussion: In Table we examined 2 different datasets representing the extremes of classification difficulty: AIDS binary classification task with 2000 samples) and Letters-high (a dataset with 15 classes and 2250 total samples). We notice from Table 5 that in the easier inductive task, both uniform and learned quantization methods yield similar performance. Learned quantization outperforms uniform quantization in the harder learning task, Letters (high), where the ability to learn which bins activation input elements should be clustered, becomes beneficial. We also observe that the relative model performance improvement of 1-2% persists between the satisficing (angular) mapping and QuantNet, even with increasing model depth, adding more validation quantization learning as a useful property. In Table 24] we focused only on QuantNet-based QGRN and trained the model on sampling of datasets which had positional attributes. We prepared from the same datasets, variants with positional attributes and variants without positional attributes for the quantization learning. Intuitively, we'd we'd expect that with quantization learning from explicit positional descriptors, binning should be close to optimal, thereby leading to optimal model performance. This is what the experimental results show. Without explicit positional descriptors (here QGRN uses the entire node attributes, of which explicit positional attributes are inclusive), the model achieves near-optimal test accuracies. interesting to point out that the model performance of the variants without positional descriptors is upper bounded by the model performance variants with positional descriptors.
27

---

Empirically determining quantization bins
The number of bins set by choosing the number of subkernels, which user defined and hence a hyper-paramen of our model. As such, the number of bins can be tuned via any typer-parameter optimization method, such as Grid search, Bayesian search etc. For image datasets, this choice is immediately obvious: the number of bins must be the total number of neighboring nodes in any given neighborhood (8 neighbors algorithm (an algorithm pseudo-code, Algorithm D.I to determine satisficing mapping across all neighborhoods. For QGRN with learnable quantization, the number bins is hyper-parameter, We present a sample Table 25
central node). For the uniform quantization case, we developed an
search for select graph datasets from the TUDatasets benchmark in
Table 25: Number of bins hyper-parameter search. Hyper-parameter search of optimal number of bins/subkernels for QGRN
Dataset
Average
Test Accuracy (%)
Bins=2
Bins=3
Bins=5
Bins=7
Bins=9
AIDS
99.25
99.25
98.75
99.50
99,25
Enzymes
70.83
71.67
69.17
72.50
68.89
Coil-Del
91.26
92.39
92.39
94.14
90.54
Letters (high)
93.91
93.71
93.71
94.67
93.71
Proteins
73.27
76.24
73.27
80.20
73.27
Discussion: Notice the classification test accuracy variations as we sweep the number of bins/subkernels. The trend is non-linear, mostly peaking between 3 7 bins/subkernels. This partly explained by the fact that most datasets here have an average neighborhood size of 5 which provides reasonable partitioning size for all neighborhoods; the analogy here is CNN's bin size of 9, which a consequence of full regular neighborhoods having a size of 9 pixels. As the number of subkemnlss grow, each subkernel sees a smaller subset of the training data; additionally, bin data size distribution imbalance results in uneven training of the corresponding bin subkernels, which results in regression of the overall model's performance. A pathological here would be defining an arbitrarily large number of bins (far greater than the dataset's average neighborhood size), leading
worth mentioning
very little training of subkernels: the weights that see any node features are bound to overfit on the small set of node features they see while those not seeing any node features will never get to train. During test time, this blend of over-fitted and under-fitted subkernel weights will result in large regression in the overall model's performance. On the other extreme, with single learnable subkernel, all types of nodes which ideally may belong to different bins are collapsed into the same bin, making it hard for the single subkernel to learn common messages across the entire node of the graph for message passing. This an example underfitting (high bias) scenario. The optimal bin size is intuitively expected to be around the average neighborhood size of the given dataset, which what we see in the experimental results summarized in Table 25
R Compute resources for experiments
All experimental results provided in this paper were the results of runs on Google Colab premium offering of GPUs and TPUs. As much as specific details on these systems are publicly available, we have tabulated them below. The two main accelerator options used were the A100 GPUs and TPUs. In table 266 we outline some of the system specifications. It is worth noting that the set of datasets we explored in the TUDataset benchmark were all moderately sized, hence Google Colab's Pro+ offering was more than sufficient for us. This was also the case for results collated on the standard dataset splits and our own custom Navier-Stokes FEW dataset. Not included in the table is Tesla V100, which at the time of finalizing this paper, Colab had deprecated support for it.
S Addressing Latency Concerns
Regarding model training and inference speed, there much room for future work to develop new algorithms for choosing subkernel masks that are faster than those introduce here. We see the
28

---

Table 26:
Compute Resources. Google Colab Pro+ offering
System
System RAM (GB)
GPU RAM (GB)
Disk Space (GB)
Nvidia A100
83.5
40.0
201.2
Google T4 GPU
51.0
15.0
201.2
Google L4 GPU
62.8
22.5
201.2
Google TPU
334.6
NA
225.3
primary contribution of this paper as the introduction of the quantized convolutions theoretical framework, which we demonstrated with 2 options for subkernel selection:
2D angular-quannizztion (satisficing mapping).
2. Flexible caamable-quantization (QuantNet).
There are many possible algorithms for choosing sub-kernel masks within this framework, and suspect that future research into this area could be very fruitful. For example, some practical ways satisficing mapping & QuantNet might be sped up include:
1. Separating out tensor operations in the message preparation, propagation and update stages of the message- passiin neural networks (MPNN) and leveraging the operator fusion capability of Torch JIT Script to optimize these operation sets.
2. Parallelizing the execution of the sub-kernel convolutions, with dedicated low level CUDA kernels, instead of using grouped convolutions (as we do in our current implementation).
3. Using depth-wise separable convolutions: this will reduce the model complexity (in terms of number of parameters, hence resulting in a proportional reduction in model runtime com- plexity. Depth- Depth-wise wise separable convolutions trade off model flexibility for model size. This means this optimization would need be carried out carefully to ensure that QGCN/QGRN doesn't I regress significantly in performance. It is worth noting that CNNs also have been sped up in this way for edge platforms.
The above listed are by no means exhaustive but we believe these will be good starting points for optimizing QGCN/QGRN to make them competitive with existing highly optimized MPNNs in the literature. We do hope that further research into QGCN/QGRNs will allow them to eventually be useful for numerous applications (as happened historically for CNNs over time).
T Impact statement
As the paper's primary innovation is a learning model that be trained to perform different tasks on graphs, it by itself doesn't it pose any obvious risks. The potential for negative societal impact depends the dataset and downstream learning tasks user of this model designs for. We strongly recommend for such a model to be used in compliance with all ethical standards appropriate to the domain in which it targeted be deployed. We accentuate the need to ensure that datasets on which this model is trained reflect not only the status quo but take into account broader social, political, cconomical and religious contexts that they mitigate potential harms from any potential bias or misuse of the model's 's learning abilities.
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Clain 1: QGCNs contain CNN-equivalent convolution layer, termed QGCL, as a subset. We show this in Section 3.1 Claim 2: QGCNs using the the satisficing mapping strategy are empirically and formally equivalent to 2D CNNs applied to image data. We introduce the satisficing mapping as a masking approach that matches the natural convolutional masks in Section 3.2 we show that performance is empirically equivalent between QGCNs and CNNs in Table Figures 6
7
8
9
TO 12
14 Claim
We present an end-to-ent learnable quantization network that extends QGCNs Ns arbitrary graphs. See Section 3.3] Claim 4: A residual network inspired architecture (QGRNs) that further improve QGCN performance. See Section 3.4 Claim 5: Benchnarking of QGRNs on a novel Kavier-Stoke. FEM dataset and 19 other public benchmark graph datasets. See Section 4 Claim 6: Showing QGRLs improve joint modeling of emotional states and EEG
data in a supervised autoencoder architecture. See Section 4.3
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitation are mentioned briefly throughout the paper and discussed in detail in Section 5
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: See Sections 3.J 3.2 and
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide all code and data necessary to reproduce every experimental result that we describe in this paper.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We provide all experimental code and data.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide sufficient details to make sense of the results in the core paper. Full details are provided in the available code.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
30

---

Answer: [Yes]
We report for all relevant results (both in the main paper and the appendix) the and standard deviations, wherever applicable. The error bars shown the learning rate plots in Figures
Justification:
I0 and 12 are all also standard deviation.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experimental results reported were generated Google Colab's offering of GPUs and TPUs. As much as specific details on these systems are publicly available, we have included them in the paper, here in Appendix section R
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: To the best of our knowledge, this paper fully conforms with the Code of Ethics.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We address impacts in Section
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We do believe this paper poses any such risks.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All datasets, other than our custom datasets, have been cited properly. The various GNN models we compared our QGRN models have also all been cited properly, including SGCN (which was cloned from the original paper's s GitHub repository). For SGCN, the cloned repository includes the copyright and permission notices, as defined within the MIT License. Other than these datasets and models, no other assets were used in the project.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: New assets (code, datasets: Navier Stokes FEM datasets) are well documented. Appendix section bection|H]detailyy how the FEM dataset was constructed. Additionally, the GitHub repository contains relevant links for where to download the datasets. All the datasets used in this paper were packaged into common dictionary object that our experimentation infrastructure could use. The details are all provided in the README page of the GitHub repository.
31

---

14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper did not involve crowdsourcing or research with human subjects. 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper did not involve crowdsourcing or research with human subjects.
32


Reviews:
[{"review_id": "pBS9KnjUEq", "reviewer": "Reviewer_5Ti4", "summary": "In this paper, the authors propose Quantized Graph Convolution Networks (QGCN), a GCN framework that directly extends CNNs by decomposing convolution operations into non-overlapping sub-kernels. This paper demonstrate that QGCN is essentially the same as a 2D CNN layer in dealing with pixel local neighbourhoods, and generalize the approach to graphs of arbitrary dimensions. After integrating the algorithm into a residual network architecture, the algorithm demonstrates performance that matches or outperforms other state-of-the-art GCNs on several benchmark datasets.", "questions": "1. For hyperparameter $\\phi$, can the authors give the results of its sensitivity analysis?", "limitations": "The authors adequately addressed the limitations of thier work.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. This article completely extends CNNs to GNNs, and it is an important task to build better architectures for processing graph data.\n2. The QGCN algorithm proposed in the article achieves quite excellent results on Benchmark datasets for graph kernels.\n3. This paper proposes a simple but effective method that computes the difference between the target and source features, and then project that difference onto a vector representing the assignment weights of each subkernel. This approach is somewhat enlightening.", "weaknesses": "1. The authors experiment only on Benchmark datasets for graph kernels. Node classification and edge classification tasks are also very important graph tasks, but there is no mention of related experiments in this paper.\n2. The baselines that the authors compare are a little old-fashioned, such as GAT, which was proposed in 2017, and there is a lack of comparison with the most novel approaches.\n3. The heavy computational burden of GNN hinders its practical application, however, the Inference latency of QGRN is about 6 times higher than that of GCN, which raises concerns about the application of QGRN in the real world.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Responses to listed weaknesses (*W*) and question (*Q*):\n\n*W1*. Excellent point. To address other important graph tasks, in addition to adding the SVAE example above we now run several node classification tasks on multiple types of datasets, mostly citation networks (like Cora, PubMed), Wikipedia hyperlinks networks (like such as the Chameleon dataset) and product relations networks (such as with the Amazon Photos, Computers etc.). We highlight that the datasets used in this exploration exhibit different degrees of homophily and heterophily properties. Chameleon and Squirrel datasets exhibit strong heterophily while all the others exhibit stronger homophily. Given the brief time to investigate this, we have only pursued **limited architectural exploration** and here chose a single architecture that proved reasonably performant across all the models we compared against. The final architecture had the structure below: \n\n**Conv**>**BatchNorm**>**Relu** > **sum**( 3x(**Conv**>**Relu**) ).\n\nThe convolution (also referred to here as ‘conv’) layers are where the different graph convolutional layers like QGRL, GenConv, EGConv etc. plug into. This network has 2 layers, the first is a convolution layer followed by batch normalization and then a ReLU activation layer. The second layer in the architecture sums up features from three identical blocks, each of which is a convolution layer followed by a ReLU activation layer. We trained all models across a range of learning rates (0.1, 0.05, 0.01, 0.005, 0.001) for about 2000 epochs and mimicked early stopping by caching the model state that produced the largest validation set accuracy. Given the now apparent fact that MPNNs (Message Passing Neural Networks) generally struggle with heterophily datasets, we designed the generic architecture with edge directionality awareness, as inspired by the paper “Edge Directionality improves Learning on Heterophilic Graphs” by Rossi et. al. Empirically, we noticed that most of the performance improvement came from training on the reversed edge index tensor, which is equivalent to training on the original graph dataset, except with reversed edge directions. This is intuitive as a commonality across these datasets is the fact that a small number of nodes have high degrees and hence reversing edge directionality allows nodes with fewer edges to learn better from the representations of the few popular nodes. We note that QGRN performs competitively on the homophilic datasets. On the heterophilic datasets, except for Squirrel (the most heterophilic, where we suspect further fine tuning can help us bridge the performance gap), QGRN performs moderately well. Thus, beyond the strong results presented in our main paper, our method also shows potential for node/edge classification in both homophilic and heterophilic graphs.\n\nTable 1. Node Classification: Comparing QGRN to other recent models.\n| | Photo | Computers | Cora | PubMed | CiteSeer | Chameleon |  Squirrel | \n|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n| QGRN | 95.34 ± 0.10 | 90.36 ± 0.02 | **89.02 ± 0.14** | **89.11 ± 0.15** | **79.09 ± 0.27** | 74.15 ± 0.37 | 56.17 ± 0.45 |\n | GraphConv |  94.44 ± 0.04 |  87.96 ± 0.16 | 87.15 ± 0.44 | 88.39 ± 0.07 | 76.69 ± 0.07 | 72.77 ± 0.32 | 64.25 ± 0.09 |  \n| GenConv |  95.25 ± 0.04 |   **91.66 ± 0.05** | 86.31 ± 0.36 | 87.73 ± 0.19 | 75.37 ± 0.34 | 71.56 ± 0.67 |  58.00 ± 0.18 |  \n| GeneralConv |  94.13 ± 0.14 | 89.29 ± 0.02 | 87.64 ± 0.04 | 88.97 ± 0.09 | 75.53 ± 0.10 | **78.11 ± 0.29** | **66.80 ± 0.08** | \n| EGConv|  **96.19 ± 0.05** | 91.50 ± 0.06 | 88.34 ± 0.30 |  88.38 ± 0.08 | 76.34 ± 0.21 |  63.54 ± 0.07 | 48.44 ± 0.41 |\n\n\n*W2.* Thank you for highlighting this. We did consider a variety of models in our work. Please note that for GAT, we actually compared against the improved GAT model, released in 2021, not the 2017 version. Additionally, we considered other transformer-based models like TransformerConv. Newer models like GNNDLD, reported to be beating SOTA on many node classification tasks (on Papers with Code), don't have publicly available codebases yet, hence the absence of any comparison with them. Please find the table below outlining the various models we compared against and the year these models were publicly released:\n\n| *Model* | GCNConv | ChebConv | GraphConv | SGCN | SGConv | GenConv | GeneralConv | TransformerConv | GATv2Conv | EGConv |\n|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|-----------|\n| *Year* |  2016 | 2016 | 2018 | 2019 | 2019 | 2020 | 2020 | 2020 | 2021 | 2022\n\n\n*W3.* Please see our response in the general rebuttal section.\n\n*Q1.* We fully expect that the impact of 𝜙 will be negligible in the vast majority of datasets, and primarily include it in the description of the model to make for easier visual interpretation of which nodes get assigned to which sub kernels when a large portion of nodes occur at an angle of 0 (such as in the case of graphs constructed from local neighborhoods in 2D image data). There will be a few cases in which the choice of 𝜙 might influence performance, such as when the majority of edges in a dataset are clustered around a specific angle. However, we do not readily have access to any such datasets to provide a meaningful sensitivity analysis of 𝜙. A more sensitive related parameter is the number of subkernels *k*. The paper already carries out a sensitivity analysis (outlined in-depth in the appendix) on, e.g., how the number of subkernels influence model performance, how the type of quantization (here, QGCN vs QGRN) impacts model performance etc. We will highlight these sensitivity analyses more explicitly in our revision of the paper as we agree such analyses are important.\n\nWe hope we have adequately addressed the reviewer's concerns and that they will consider increasing their score accordingly. Thank you for your time.", "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": "", "extra_scores": {}}, {"review_id": "yBxH3t2kf4", "reviewer": "Reviewer_rsM6", "summary": "In this paper, the authors present a novel Quantized Graph Convolution Layer (QGCL) that extends the benefits of CNNs’ strong local inductive bias to graphs. The authors have shown that embedding a QGCL within a residual network architecture give state-of-the-art results on benchmark graph datasets.", "questions": "1. Is the efficiency of QGCN related to the average degree of nodes in the graph?\n2. How does QGCN’s training time compare to baseline methods?", "limitations": "None", "rating": 6, "confidence": 1, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The presentation of the paper is clear and easy to follow.\n2. Extending the benefits of CNNs’strong local inductive bias to graphs is interesting and instructive, which has the potential to advance the understanding and analysis of Graph Neural Networks.\n3. The method is effective in comparison to baseline methods.", "weaknesses": "1. Implementation of QGCN is not yet efficient as demonstrated in the comparison of inference time with other baselines.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Responses to listed weaknesses (*W*) and question (*Q*):\n\n*W1.* Thank you for highlighting this. We kindly refer to the related response given in the general rebuttal section, as this was a repeated concern for most reviewers. Thank you.\n\n*Q1.* Runtime efficiency is indeed determined partly by the average node degree of the input graphs. The primary factor that determines the runtime efficiency is the number of sub-kernels initialized in a QGRL for its convolution. This is because our current implementation of QGRL convolution effectively serializes the individual sub-kernel convolutions, thereby forcing the runtime to roughly scale linearly with the number of subkernels used. Some secondary factors determining runtime efficiency would be the average degree of nodes in the graph, input graph node feature size, the dimension of positional descriptors, which will all collectively contribute to the model's size. On model efficiency, a variety of factors work together to influence this. The paper already carries out different sensitivity analysis (outlined in-depth in the appendix) on, e.g., how the number of subkernels influence model performance, how the type of quantization (here, QGCN vs QGRN) impacts model performance etc. We will expand and highlight these results more prominently in the revision.\n\n*Q2.* Currently, QGCN’s training time is comparable to CNN, where the local neighborhoods are regular, i.e., positional topologies are the same across all graphs. This is already highlighted in the paper (and we plan to emphasize it better in our revision). Our approach here caches the quantized sub-kernel masks, i.e., the satisficing mapping of nodes to sub-kernels, once it is computed so that subsequent epochs do not have to recompute the same mapping. We note that caching, as a runtime optimization strategy, isn’t novel to our method; some popular GNNs use this approach, e.g., GCN, which caches its renormalization matrix. For QGRN, our current implementation is not optimal due to the serialization of sub-kernel convolutions (note this is not required but rather a product of our code not yet being fully optimized). As such, QGRN runs slower by roughly a factor of *k* (where *k* = number of sub-kernels used in the network’s convolution) compared to other models (particularly with respect to GCN or GAT, for example). This is also mentioned in the paper, but we shall emphasize it more so that it is apparent.\n\nWe hope that this response (along with the general response above) was informative and addressed your concern about efficiency. We thank you for your time.", "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": "", "extra_scores": {}}, {"review_id": "kjQ9CQALxU", "reviewer": "Reviewer_1wWD", "summary": "The authors find a new a way to generalize CNN from Euclidean space to graph data. The proposed method has good analogy with CNN's computing pattern, and can be applied to data with/without positional descriptors.\nOn dataset with positional descriptors, the proposed method is equivalent to SGCN. On dataset without positional descriptors, the proposed method matchs or outperforms all GNN methods across adiverse graph learning problems.", "questions": "1. Why the leading accuracy of AIDS dataset in Table 17 is lower than the baselines' accuracy in table 3?\n\n2. Please add a bracket to eq. (2) to clarify the order of operations.\n$$\nO_{c,d,:} = \\sum_{h=0}^{JK-1} \\color{red}\\left[\\color{black} \\left(W\\sum\\sum ...\\right) + B \\color{red}\\right]\\color{black}\n$$", "limitations": "the authors have adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "All designs of the proposed method are derived from authors' insights into CNNs and are thus well motivated. The proposed method has a better analogy with CNNs than existing GNNs in terms of spatial computing pattern, and also has a stronger expressive power.\n\nExperiments are comprehensive and convincing. The proposed method is compared with a wide range of baselines on multiple datasets. \n\nThe manuscript is well-written and easy to follow. I can go through the paper without any confusion.", "weaknesses": "My major concern is how is the proposed method's performance compared with the state-of-the-art results of each dataset. Are the sota baselines included in table 3 and table 4? Table 17 shows some sota baseline's results, but only covers a limited number of datasets. \n\nA minor concern is that forward/backward speed of the proposed method may be slow, but this has been discussed by the authors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Responses to listed weaknesses (*W*) and question (*Q*):\n\n*W1.* Tables 3 and 4 in the paper record the performance of QGRN as compared to similar sized models in the GNN literature. A singular simple architecture subsuming these layers were trained across different hyperparameter ranges, as documented in the paper and codebase, and the best performance on the benchmark was reported for each model. In regards to Table 17, our search for state of the art performance on this benchmark was limited to Papers with Code, which has only a subset of the datasets we trained on. This, we believe, is indicative of the fact that in literature, a subset of these benchmarks are chosen for different types of downstream tasks. Our method mostly focused on inductive classification tasks. After searching thoroughly through Papers with Code, we found what we believe to be the full subset of data sets with comparable SOTA results below:\n\n| Dataset | QGRN Avg. Test Acc. (%) | SOTA Avg. Test Acc. (%) | Leading Model Name | \n|-----------|-----------|-----------|-----------|\n| Aids |  **99.50**  |  97.30  | k-NN classifier: IAM Graph Database Repository (2008)   | \n| Mutag |  **100.00** | **100.00** | Evolution of Graph Classifiers | \n|  Mutagenicity |  **83.80** | 83.00 | Tree-G | \n|  Proteins | 80.20 | **84.91** | HGP-SL | \n| Enzymes | 72.50 | **78.39** | DSGCN-allfeat-2020 |\n|  Frankenstein | 75.58 | **78.90** | GWL_WL (Graph Invariant Kernels) |\n\nIn addition, the conference paper “IAM Graph Database Repository for Graph Based Pattern Recognition and Machine Learning”, published in 2008 (also cited in our paper) provides some k-NN classifier-based results that the authors intended as “a first reference system to compare other algorithms with”. Clearly these **do not** represent SOTA results, but we include them as another baseline comparison available for the data sets considered in the table below:\n\n| Dataset | QGRN Avg. Test Acc. (%) | kNN Avg. Test Acc. (%) |\n|-----------|-----------|-----------|\n| Letters (low) | **99.81**| 99.60 |\n| Letters (medium) | **96.76**| 94.00 |\n| Letters (high) | **94.10** | 90.00 |\n| Coil-Del | **94.14** | 93.30 |\n| AIDS | **99.50** | 97.30 |\n| Mutagenicity |  **83.80** |  71.50 |\n| Proteins |  **80.20** | 65.50 | \n\n*W2.* Thank you for pointing this out. We agree and add further response on this topic in the general rebuttals section above.\n\n*Q1.* Thank you for highlighting this. We noticed this was odd, especially given that the k-NN classifier approach from 2008 was beating a novel approach from 2017. After examining DGCNN’s manuscript, we found that though the reported number is classification accuracy, it was for a different dataset (coincidentally bearing the same name as TUDatasets AIDs on Papers with Code). DGCNN’s AIDs dataset is a 3-class classification dataset, while TUDatasets' AIDs is a binary classification dataset. Thank you for helping us catch this. On Papers with Code, we found that there was a placeholder leaderboard for the AIDS dataset we trained on (named “AIDS Antiviral Screen”), with no benchmarks or papers submitted for it. In the absence of any submissions, we have reported the k-NN classifier accuracy as the best to date that we know of, but would consider removing the row from Table 17 at the reviewer's request.\n\n*Q2.* Concern is duly noted. We have identified some clarity concerns and plan to thoroughly clean notations up in order to improve readability and digestibility of the paper’s contents.\n\nWe hope we have adequately addressed the reviewer's concerns and thank the reviewer for their time.", "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": "", "extra_scores": {}}, {"review_id": "zCuBSVYc2Z", "reviewer": "Reviewer_XG75", "summary": "In this paper, the authors introduce a Quantized Graph Convolution Network (QGCNs), which directly extends CNN on GCN by decomposing the convolution operation into non-overlapping sub-kernels. It shows that a QGCN is identical to a 2D CNN layer on a local neighborhood of pixels. Then, they generalize this approach to graphs of arbitrary dimension by approaching sub-kernel assignment as a learnable multinomial assignment problem. Meanwhile, they also integrate the network with a residual operation and achieve better performance than the current GCN models.", "questions": "1) In my opinion, GCN has achieved excellent performance on graph datasets. Why do you integrate the convolution kernel into the GCN network to handle the graph data?\n2) Why conduct the experiments on image datasets like MNIST, Fashion-MNIST or CIFAR-10? Does it verify that QGCN and 2D CNN have the same performance? In my view, it should be conducted on graph scenarios.\n3) I suggest that the author could describe the downstream task of the proposed model in detail.\n4) In line 150, the authors state that they want the output to be a graph as well. However, for most GCN-based models, the output is always the representation of the node or edge. Hence, why does the proposed graph layer output a graph?\n5) In Section 3.2, I am curious about how to handle the scenario that more than 2 neighbors fall in the same bound.\n6) As shown in Line 199, the complexity of the proposed satisficing mapping is $O(|V|^2)$. Is there a strategy to reduce the complexity?\n7) The authors should describe more experiment settings like learning rate, network layers, and so on.\n8) The manuscript lacks some reference to the baseline model in the experiment and some notations lack definitions.", "limitations": "It is an interesting idea that extend CNN into GNN and handle the graph datasets. The authors could describe the motivation in more detail and clearly, which makes the manuscript more convincing. Meanwhile, although the authors first quantizing the convolution kernel into an equivalent set of non-overlapping sub-kernels applied to graph geometry, the complexity is too high such as $O(|V|^2)$. Besides, The authors should adjust the experiment section and add more descriptions about the experiment setting.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Compared with other CNN-based models extending on graph datasets, the authors first quantizing the convolution kernel into an equivalent set of non-overlapping sub-kernels applied to graph geometry. In my opinion, the novelty of this manuscript is relatively novel. Besides, the presentation of this paper sounds relatively clear and logical.", "weaknesses": "1) The motivation seems unclear. As shown in the abstract and introduction, the authors attempt to extend CNN on graph datasets. However, in my view, GCNs have achieved excellent performance on graph tasks. Why do the authors integrate the convolution kernel into the GCN network?\n2) The downstream task of the proposed network is ambiguous. Does it solve the image classification or graph-related tasks? The authors conduct them both in the experiment section.\n3) The manuscript lacks some reference to the baseline model in the experiment and some notations lack definitions.\n4) The experiment settings are not detailed enough to reproduce the experiment results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Responses to listed weaknesses (*W*) and question (*Q*):\n\n*W1* and *Q1*. We agree that we have done an inadequate job at explaining our motivation for this work in the introduction. We will update the introduction and related work sections to clarify our motivation and why we desired to improve on existing models. In brief, our original motivation was to create a model that did a better job taking advantage of positional information in graphs by generalizing CNNs (for example, doing better than SGCNs) by handling positional information in a more flexible way. In pursuing this line of research, we further discovered that our method also substantially outperformed GCNs on the graph benchmark datasets that we report in the manuscript. \n\n*Q2*. We agree that we should have been more clear about why we are sometimes considering image data when our main practical application target is graph data. In brief, there are two main threads in the results section: **a.** empirical validation of theory: the results reported in table 1 were meant to demonstrate that a 2D-CNN on image data and a QGCN using satisficing mapping on graphs generated by connecting local pixels result in equivalent classification performance. These results are meant to empirically back up our theoretical results that show QGCNs reduce to 2D-CNNs on image data (i.e., to demonstrate that QGCNs properly generalized CNNs by reducing to CNNs on image data); **b.** performance on graph data: the remaining tables show QGCN and our extensions of it are highly performant against SGCN on spatial graph data (Table 2; also including graph based representations of image data as benchmarks as in prior work) and against other state-of-the-art GNNs and graph data benchmarks (Tables 3 and 4). We think that (a) is interesting theoretically and (b) is of practical interest for graph data. We will make this distinction much more clear in our revision of the manuscript.\n\n*W2* and *Q3*. Thank you for the feedback, we will update section 4 and the appendices in detail to more clearly describe the downstream tasks for each of our experiments. We will highlight that all tasks currently described in section 4 are framed as graph classification tasks when using QGCN, where images are transformed into graphs by connecting adjacent pixels. CNNs are applied directly to image data. Again, the image tasks are included to address point **a.** above.\n\n*W3*. We will carefully clarify in detail references to baseline models in our experiments ensure all notations have clear definitions. \n\n*W4*. We will add code to reproduce all experiments including our Navier-Stokes dataset exactly with seeds set for exact reproducibility.  \n\n*Q4*. The reviewer is correct that the output of Eqn. (3) is a node representation. We will clarify our language on line 150 to point out that after each layer, the node representations are embedded in a graph with the same edge structure as the input graph.\n\n*Q5*. In section 3.2, the satisficing mapping is actually defined such that no 2 neighbors will ever fall within the same bound (see lines 190-191).\n\n*Q6*. Yes! In the case when all neighborhoods have the same positional structure, the satisficing mapping only needs to be calculated once and can then be cached, resulting in a substantial speedup (comparable to CNN).\n\n*Q7. / Q8.* Thank you for pointing this out. We will update the manuscript to clarify experimental settings, references, and notation. If you have any suggestions for specific edits we could make, we will be happy to incorporate them!\n\nWe hope this response was thorough enough to address the concerns you have raised. Thank you again for your time to review this manuscript.", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank the reviewers for dedicating their time and providing high quality feedback on our manuscript.

One concern noted in various ways by the reviewers was that the computational overhead of QGCNs and QGRNs is high. We agree that this is a limitation of our approach as currently implemented. This primarily limits these models in applications that require very low latency and high throughput. Importantly, there are many applications in need of expressive graphical models such as ours where such speed concerns are not significant. 

As one example, a primary motivation behind these models was the need for more expressive ways to model brain networks from EEG data in a way that takes spatial information into account. We plan to publish a clinically-focused manuscript that uses these models for psychiatric clinical trial research in the near future at a clinical-neuroscience-focused venue. We have put together a quick demonstration for the reviewers using the publicly available [DEAP dataset](http://www.eecs.qmul.ac.uk/mmv/datasets/deap/), where we compare the performance of a supervised autoencoder using either QGRN layers or SGCN layers to construct the encoder and decoder. Methods and results for that experiment are reported below and will be added to the revised manuscript’s supplement (with code for reproducibility). We note that the inference time of GNNs, our model inclusive, is inconsequential in a clinical setting, even for real-time feedback applications where a new window of EEG is processed every few seconds.

The FEM example in the manuscript is another application where throughput time is not significant, as the tens of milliseconds required for inference are virtually instantaneous compared to the hours to days required for a full FEM simulation with a physical model. We will edit the paper to more clearly point out the FEM application and other applications that can currently benefit from QGCNs. Training times may still be significant for some of these applications, but we are unaware of any other models that can achieve the desired level of performance on the types of datasets we are interested in.

Another point regarding model speed is that there is much room for future work to develop new algorithms for choosing subkernel masks that are faster than those we introduce here. We see the primary contribution of this paper as the introduction of the quantized convolutions theoretical framework, which we demonstrated with 2 options for subkernel selection: 
- 2D angular-quantization (satisficing mapping, QGCN)
- flexible learnable-quantization (QuantNet, QGRN)

There are many possible algorithms for choosing sub-kernel masks within this framework, and we suspect that future research into this area could be very fruitful. For example, some practical ways satisficing mapping & QuantNet might be sped up include:
* Separating out tensor operations in the message preparation, propagation and update stages of the MPNN and leveraging the operator fusion capability of Torch JIT Script to optimize these operation sets.
* Parallelizing the execution of the sub-kernel convolutions, with dedicated low level cuda kernels, instead of using grouped convolutions (as we do in our current implementation).
* Using depth-wise separable convolutions: this will reduce the model complexity (in terms of number of parameters, hence resulting in a proportional reduction in model runtime complexity. Depth-wise separable convolutions trade off model flexibility for model size. This means this optimization would need to be carried out carefully to ensure that QGCN/QGRN doesn’t regress significantly in performance. It is worth noting that CNNs also have been sped up in this way for edge platforms.

The above listed are by no means exhaustive but we believe these will be good starting points for optimizing QGCN/QGRN to make them competitive with existing highly optimized MPNNs in the literature. We do hope that further research into QGCN/QGRNs will allow them to eventually be useful for numerous applications (as happened historically for CNNs over time).

Other concerns involved benchmarking our methods for node/edge classification and clarifying comparisons against SOTA results. We directly address these by including new results and tables in the responses to reviewers 5Ti4 and 1wWD below.

### EEG Supervised Autoencoder Example

The last 42 s of each recording in the DEAP EEG dataset were divided into sliding windows of 3 s with 50% overlap, then were *z*-scored and spectral power was calculated in four frequency bands for each of the 32 electrodes. Power features were used as node attributes in a fully-connected graph containing all 32 electrodes. We trained a separate model for each subject (64%/16%/20%: training/val/test splits). The generative objective was MSE and the supervised objective was cross-entropy loss for classifying whether subjects self-rated their emotional state as positive valence or negative valence. Models were pre-trained for 1000 epochs on just the generative objective, then for another 100 epochs with one of 3 values of weight on the classification objective [100, 1000, 10000]. Validation sets were used to select the weight and number of training epochs with highest area under the receiver operating curve (AUC). 

We found that using QGRN layers in the same autoencoder architecture compared to SGCN layers resulted in better generative and supervised loss values on the held out test sets. In addition, the QGRN-based model resulted in significantly better classification performance for this difficult classification problem (as measured by AUC). The mean +/- SEM over all subject test sets are reported in the following table:

| | QGRN | SGCN |
|-----------|-----------|-----------|
| MSE loss (Generative) |**1787.33 ± 315.51** | 2169.38 ± 317.80 |
| Cross-entropy loss (Supervised) | **0.6500 ± 0.0088** | 0.6591 ± 0.0091 |
| AUC |  **0.593 ± 0.014**  |  0.562 ± 0.011 |

Meta-review: All four reviewer expressed enthusiastic support to this work, and an accept is recommended.
Decision: Accept (poster)