Generalizing CNNs to graphs with learnable neighborhood quantization

Authors: isaac osafo nkansah
neil  gallagher
ruchi  sandilya
conor  liston
logan  grosenick
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:28:47

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.

Main paper: 
 introduction: 
 Many important real-world scenarios involve data structured as 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 as graphs made up of bonds between atoms. It can be challenging to accurately model such graph data, creating a barrier to studying these problems. Indeed, this work was motivated by our own experiments in modeling brain networks from neural data, where we have found that existing methods are often not expressive enough to effectively capture the types of phenomena we are interested in.In recent years, the prevailing approach for learning from graph data has shifted towards methods inspired by convolutional neural networks (CNNs) [20, 21, 8, 17, 25, 4, 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 [26, 43] and image recognition [7] . Because graph data often exhibit strong patterns of local correlation like those seen in language and image data, it is reasonable to expect they might similarly benefit from shared local filters.Early work extending CNNs to graphs focused on spectral methods [6, 3] , which can suffer from high runtime and memory complexity [40] . In contrast, spatial methods aim to generalize the convolution operation explicitly from array data to graph data. Recent spatial GNN methods approach this problem by either adapting the convolution operation to graphs [11, 1, 27, 28] or by adapting graphs to fit the CNN convolutional operation [10] . Existing spatial methods, however, do not truly generalize the CNN convolution layer. Spatial Graph Convolutional Networks (SGCNs) [5] , 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 is 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 a proper generalization of the CNN convolution layer to graphs. We do this by first "quantizing" the convolution operation for CNNs into an equivalent 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 a 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 QGCL 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, we demonstrate that incorporating QGRLs leads to superior performance in a supervised autoencoder model applied to a public EEG recordings and emotional states dataset [18] .In summary, our main contributions are:1. Introducing the Quantized Graph Convolutional Network (QGCN) framework, which generalizes CNNs to graphs. 2. Empirical and formal validation that a QGCN using the satisficing mapping sub-kernels reduces to a 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 benchmark graph datasets for graph classification and node classification. 6. Showing QGRLs improve joint modeling of emotional states and EEG data in a supervised autoencoder architecture. 
relevant work: 
 GCNs Although inspired by spectral theory, Graph Convolutional Networks (GCNs) [17] are practically understood as a spatial GNN method as they aggregate node features within local neighborhoods (normalizing by the node degree of the central/target node) and then transform the resulting aggregated 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 a different point in the output feature space independently makes CNNs more flexible than GCNs.SGCNs Spatial Graph Convolutional Networks (SGCNs) [5] , a 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 MLPs 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 a 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-positional descriptors, making them more general than GCNs.KerGNNs Kernel GNNs [9] define kernels as sub-graphs with trainable adjacency matrices and node features. The trainable node features for 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 adjacency 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 a 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 [10] approach is unlike the aforementioned methods, instead adapting graph data into a form that a 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 a 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.Early works [22] adapted residual connections, inspired by ResNets [12] , to 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 state-of-the-art 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 methodologyThere 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:1. Separating out tensor operations in the message preparation, propagation and update stages of the message-passing 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 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).As the paper's primary innovation is a learning model that can be trained to perform different tasks on graphs, it by itself doesn't pose any obvious risks. The potential for negative societal impact depends on the dataset and downstream learning tasks a 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 is targeted to 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, economical and religious contexts so that they mitigate potential harms from any potential bias or misuse of the model's learning abilities. 
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 G ∈ R C ′ ×D ′ ×F ′ , where G is structured in a 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 ∈ R C×D×F :EQUATIONwhere W ∈ R J×K×F ×F ′ and b ∈ R F are the weights and bias terms of the convolutional kernel, respectively. To produce a map that is the same size as the original input, zero-padding can be added along the edges of G before applying the convolutional layer to result in O c,d,: being defined forc ∈ [0, C ′ -1], d ∈ [0, D ′ -1].We can refactor the kernel parameters in Eq. 1 to have a single index h iterating over the 2D space traversed by j and k above:EQUATIONwhere ŴjK+k,:,: corresponds to W j,k,:,: in Eq. 1. The indicator function 1 (h=jK+k) has the effect of creating a mask over a single element in the 2D space defined by j and k, with a one-to-one correspondence between each element and each value of h. Thus the convolutional layer can be decomposed into a set of sub-kernels (i.e., weight matrices Ŵh,:,: and bias vectors Bh,: ) 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 a well-defined output O with the same dimensions as G without the need for zero-padding.In the Eq.2, the masks implicitly compare the location of elements in G to the relative position of 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 in 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:EQUATIONwhere o(v) ∈ R F provides the feature vector of the output node at the same relative location as input node v, N (v) is the set of nodes in the local neighborhood around v, M h is the set of node pairs selected by the mask corresponding to Ŵh,:,: , and a(v) ∈ R F ′ retrieves the feature vector of node v. In the context of QGCNs, we refer to each Ŵh,:,: as a sub-kernel. It is 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 is 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 kernel 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).In this section, we show how the sub-kernel masks (M h ) associated with convolutional kernels can be extended to the case of graphs with (pseudo-)positional 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. 2). We refer to these as the natural convolutional masks (see Fig. 1 f ). For graphs with positional information, it is possible to formalize a method for choosing a set of sub-kernel 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 a 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-positional information to enable this more general approach.As seen in Eq. 2, each mask is defined by the indicator function 1 (h=jK+k) , which selects a single element. When dealing with tensor data, the relative position of the elements selected by these masks Figure 1 : Contrasting the assignment of kernel weights to local neighborhood nodes for traditional CNN convolution kernels and the satisficing mapping sub-kernels of a 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 on the edges are mapped to unique sub-kernels (e.g., the node in (h.) on the 135°edge 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 a 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 a way to potentially map all of 2D space to a set of sub-kernels. One simple option is dividing 2D space into regularly spaced non-overlapping segments defined by angular position relative to the center node of the local neighborhood that the map is being applied to. Then the center-neighbor node pair (v, v ′ ) is part of the h th sub-kernel mask (M h ) whenEQUATIONwhere θ is the angle of the neighbor node relative to the center node, p x and p y return the x and y coordinates of a node, respectively, and H is the total number of sub-kernels. The 0 th sub-kernel is applied only to 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, we choose the smallest number that results in all nodes within a local neighborhood being assigned to a different sub-kernel, which we refer to as a 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. 1 f ). Algorithm 2 in Appendix D outlines an efficient process for determining the value of H 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. Bh,: = b JK , ∀h), then we arrive at a set of quantized graph convolution sub-kernels that will behave on 2D positional graph data identically to a standard 2D convolutional layer on equivalent tensor data (see Appendix C for proof and below for empirical validation).With this satisficing mapping approach, the process of assigning nodes in every local neighborhood to sub-kernels (see Algorithm 1 in Appendix D) incurs a computational cost of O(|V | 2 ) in each forward pass. In the case of homogeneous graph meshes, choosing to cache the satisficing mapping incurs at worst O(|V | 2 ) space complexity. Using Algorithm 2 for determining the minimum number of subkernels for the convolution such that a satisficing mapping is honored adds a constant cost on top of Algorithm 1. 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.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 of the kernel elements during CNN convolution [15] . To learn the quantization, we introduce QuantNet, an MLP that projects node features or (pseudo-)positional 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 h associated with sub-kernel h contains the ordered node pair (v, v ′ ) when QuantNet Q assigns the node pair to h:EQUATIONwhere U 1 is a high dimensional MLP projector with parameters η for the input features (spatial descriptors, node features, etc.), U 2 is a low dimensional projector with parameters θ for the difference in high dimensional features projected by U 1 , v is a node in V (the node set of the input graph), and N (v) denotes the local neighborhood node set of v. Note argmax in Eq. 5 is 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) [13] . The QuantNet network architecture is shown in Fig. 2 . Finally, we reiterate that because QuantNet can use any vector in place of positional information, QGCL becomes extensible to graphs without explicit positional information.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 [12] . We adapt this framework  
empirical validation of equivalence with cnns on 2d images: 
 First, we confirmed that the QGCL performs similarly to 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 CIFAR10 [19] . MNIST contains gray-scaled images of handwritten digits of shape 28x28x1, FashionMNIST contains fashion images of shape 28x28x1, and CIFAR10 consists of color images of shape 32x32x3 from 10 categories. Figure 4 in Appendix E shows the different CNN models trained for the different standardized datasets. We created a 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. 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 bias-variance trade-offs) by varying the dataset train-test splits (see Appendix F). that QGRN and SGCN use. This was to 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 use positional descriptors. Table 2 provides test set accuracy, as well as 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 we tested.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. 15a . For binary classification, we separated laminar and turbulent flows based on distinct Reynold's number (Re) values while for denary classification we used evenly spaced Re values. We created three datasets: Navier-Stokes-Binary (NS-Binary) for easier binary classification and Navier-Stokes-Denary-1 (NS-Denary-1) and Navier-Stokes-Denary-2 (NS-Denary-2) for more challenging denary classification, with NS-Denary-2 being most challenging (most closely spaced Re values; see Appendix H). QGRNs matched SGCN performance on the binary task and outperformed SGCNs on the more challenging denary tasks.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 I for a description of each dataset. We trained on a number of novel GNN architectures including Transformer networks (GAT, TransformerConv), 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 a 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 are constrained to have the same depth. More details are provided in the dataset configuration section of the provided code. All models were trained with the Adam optimizer using cross-entropy loss for 500 epochs at 4 different learning rates (0.1, 0.01, 0.001, 0.0001). Appendix subsection K shows how QGCN wall clock time varies compared to other GNN methods with matching parameter sizes. Each run is repeated 3 times and we report the best accuracy for each model across these learning rates. Tables 3, 4 and 12 showcase QGRN matching and outperforming all GNN methods across a diverse sampling of inductive graph learning problems. All datasets appearing in these tables either do not have positional descriptors or 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 as separate attributes from node features. In 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 in deeper networks (see Appendix O), how different quantizations impact model performance (see Appendix P), how 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 as the Chameleon dataset) and product relations networks (such as Amazon Computers) [33, 35, 42] . 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 a 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 of our method to recent methods. We trained all models across a range of learning rates (0.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. al. [32] .We see in Table 5 and Tables 18 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 of 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.A major motivation behind these models was the need for more expressive ways to model graphical data with positional information captured from complex geometrical surfaces. As a 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 [18] . 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  
discussion: 
 This work introduces Quantized Graph Convolution Networks (QGCNs), a 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 a fixed set of sub-kernels. 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 a QGCL within a residual network architecture gives state-of-the-art results on a suite of benchmark graph and node classification tasks, in addition to a novel Navier-Stokes FEM dynamics classification dataset. Finally, we demonstrate that QGCLs improve the performance of a 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 it cannot represent convolutional layers with odd-numbered 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 maintaining 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 different masking functions for QGCN sub-kernels (in addition to the angular satisficing mapping and QuantNet masking functions we outline here) will further extend the potential usefulness of QGCNs.Please find the code-base for the paper here: https://github.com/Grosenick-Lab-Cornell/ QuantNetsThe table 7 is meant to assist with disambiguating different layer, network and model names introduced in this paper. In this section we formally prove that the satisficing mapping QGCL described in Section 3.2 is identical to the 2D convolutional kernel on the local neighborhood of array elements (i.e. 3 × 3 kernel) as described in Section 3.1.Theorem 1. The satisficing mapping QGCL is identical to a 3 × 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 in (3) and (3.2); and we have shown that the output of a 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 is represented as a 2D positional graph.EQUATION= 8 h=0   Ŵh,:,: EQUATION= O c,d,: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 h is selective of a 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 v ′ a,b to represent the node associated with the array data G a,b,: , which gives (8) . In Section 3.2, we define the bias vectors associated with each sub-kernel Bh,: = b JK , ∀h, giving (9) . This is equivalent to the form given in (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 ( Ŵ, 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 (x) = g(x) implies ∂f ∂x = ∂g ∂x .Algorithm 1 Quantization algorithm: pseudo-codeInput: G = (V, E, P ) and S, 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 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 subkernel (by index) a node maps toM ← {} for a ∈ V do N a ← exnb(G, a) for b ∈ N a do r ← crad(a, b) k_index ← gski(S, r) M .add( {b, k} ) return MAlgorithm 1 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 O(k|V | 2 ), where |V | is the cardinality of the node set of the graph and k is the constant overhead of computation in each neighborhood to 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 a memory/space cost of O(|V | 2 ), 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 ub is the upper-bound on number of subkernels in the QGCL layer. Helper Functions: mnd -extracts graph's max node degree exnb -extracts local graph neighborhoods absk -assigns angular bins to sub-kernels crad -computes relative angular distances ansk -assigns neighborhood nodes to sub-kernels inai -determines if neighborhood assignment is injectiveM ← mnd(G) if M ≥ ub then return ub else N ← exnb(E) for i = M until ub do k ← i ▷ k -number of sub-kernels q ← 360 k b ← absk(k, q) for n ∈ N do a ← crad(n) is_injective ← inai(ansk(a, b)) if not is_injective then break if is_injective then return k return ubWe 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(|V | 2 ), 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(|V |) operation) and computes relative angular displacements for each local neighborhood (another O(|V |) worst-case-complexity operation in the case of strongly connected graphs) to assign nodes to their respective sub-kernels. Caching incurs O(|V | 2 ) space cost in the case of strongly connected graphs where the same node in every neighborhood maps to a different subkernel. The generic architecture has 2 blocks, the first is a convolutional layer followed by batch normalization and then a 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 a ReLU activation function. For any given GNN, it's message passing layer was substituted into the convolutional layer, depicted in the figure, to derive the overarching architecture. In doing so, we guaranteed an iso-architecture comparison.We trained CNN and QGCN models on 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 a 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. 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 a cylinder" problem on an adaptive mesh with the underlying two-dimensional flow geometry depicted in Figure 15a . We assumed a fluid density of ρ = 1.0 and dynamics governed by the time-dependent Navier-Stokes Equation:EQUATIONHere, u represents velocity and p represents pressure. We adopted a kinematic velocity of v = 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, we prescribed a parabolic inflow profile as u(0, y) = 4U y(0.41-y) 0.41 2, 0 with a maximum velocity U = 3vRe 2D . Here, Re and D denote the Reynolds number and the diameter of the cylinder, respectively. On the right edge, do-nothing boundary conditions define the outflow v δu δn -pn = 0 with n 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 1b . for the spatial discretization in the finite element implementation. We conducted simulations to produce a dataset of flow velocities, covering a range of Reynolds numbers spanning values 20 to 120. At lower Reynolds numbers, the flow exhibits a stationary behavior. However, as the Reynolds number increases, a fascinating phenomenon known as 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 our simulations, the primary flow direction is horizontal, emphasizing the significance of the x-component of velocity.We generated the graph dataset representing fluid velocity components in a standard PyTorch Geometric 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 Table 9 : Navier-Stokes-Binary (NS-Binary) for binary classification and Navier-Stokes-Denary-1 (NS-Denary-1) and Navier-Stokes-Denary-2 (NS-Denary-2) for denary classification, with NS-Denary-2 being more challenging. Training data for each Re value is from the 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. 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. Our search for state of the art performance 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: 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 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 our paper: Discussion: From the results compiled in table 22 , we do see that as the depth of the network increases there is a modest reduction in overall model performance. The results also reveal that the extent of model performance regression depends on 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, sees more performance loss at 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 we speculate that it is largely due to our residual network retrofit in our QGRN layer not being sufficient to mitigate the effects of depth (e.g., the vanishing gradient problem). There are several exciting findings in 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 is the case through our equivalence analysis. In 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, our layer-level innovation with quantizable neighborhoods (replicating CNN-like convolution) also stands to benefit from such architectural designs that allow for robust and deeper network architectures, which we leave to future work.Here, we explore a pilot comparison of satisficing (angular) mapping and QuantNet to understand how quantizing the neighborhoods uniformly vs learning the quantization affects model performance.We were able to compile together some sample results that provide some insight into this, which we share in Table 23 . In Table 24 , we considered the impact of using pseudo-positional descriptors (here, the entire node attributes) as opposed to explicit spatial descriptors as positional descriptors. 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 to quantization learning as a useful property. In Table 24 , we focused only on QuantNet-based QGRN and trained the model on a 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 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. It is interesting to point out that the model performance of the variants without positional descriptors is upper bounded by the model performance on variants with positional descriptors.The number of bins is set by choosing the number of subkernels, which is user defined and hence a hyper-parameter of our model. As such, the number of bins can be tuned via any hyper-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 + 1 central node). For the uniform quantization case, we developed an algorithm (an algorithm pseudo-code, Algorithm D.1) to determine satisficing mapping across all neighborhoods. For QGRN with learnable quantization, the number of bins is a hyper-parameter. We present a sample hyper-parameter search for select graph datasets from the TUDatasets benchmark in Table 25 . 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 is partly explained by the fact that most datasets here have an average neighborhood size of 5 -7, which provides a reasonable partitioning size for all neighborhoods; the analogy here is CNN's bin size of 9, which is a consequence of full regular neighborhoods having a size of 9 pixels. As the number of subkernels 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 case worth mentioning here would be defining an arbitrarily large number of bins (far greater than the dataset's average neighborhood size), leading no or 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 a 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 set of the graph for message passing. This is an example of underfitting (high bias) scenario. The optimal bin size is intuitively expected to be around the average neighborhood size of the given dataset, which is what we see in the experimental results summarized in Table 25 .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 we used were the A100 GPUs and TPUs. In table 26, 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.Regarding model training and inference speed, 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:1. 2D angular-quantization (satisficing mapping). 
 
 Appendix:  


Decision: All four reviewer expressed enthusiastic support to this work, and an accept is recommended.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: questions: 1. For hyperparameter $\phi$, can the authors give the results of its sensitivity analysis?
limitations: limitations: The authors adequately addressed the limitations of thier work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. Implementation of QGCN is not yet efficient as demonstrated in the comparison of inference time with other baselines.
questions: questions: 1. Is the efficiency of QGCN related to the average degree of nodes in the graph?
2. How does QGCN’s training time compare to baseline methods?
limitations: limitations: None
paper_summary: paper_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.
On 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.
strength_weakness: strength_weakness: 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. 

A minor concern is that forward/backward speed of the proposed method may be slow, but this has been discussed by the authors.
questions: questions: 1. Why the leading accuracy of AIDS dataset in Table 17 is lower than the baselines' accuracy in table 3?

2. Please add a bracket to eq. (2) to clarify the order of operations.
$$
O_{c,d,:} = \sum_{h=0}^{JK-1} \color{red}\left[\color{black} \left(W\sum\sum ...\right) + B \color{red}\right]\color{black}
$$
limitations: limitations: the authors have adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2) 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.
3) The manuscript lacks some reference to the baseline model in the experiment and some notations lack definitions.
4) The experiment settings are not detailed enough to reproduce the experiment results.
questions: 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?
2) 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.
3) I suggest that the author could describe the downstream task of the proposed model in detail.
4) 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?
5) In Section 3.2, I am curious about how to handle the scenario that more than 2 neighbors fall in the same bound.
6) As shown in Line 199, the complexity of the proposed satisficing mapping is $O(|V|^2)$. Is there a strategy to reduce the complexity?
7) The authors should describe more experiment settings like learning rate, network layers, and so on.
8) The manuscript lacks some reference to the baseline model in the experiment and some notations lack definitions.
limitations: 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.

Comments: title: Thanks for you reply. I will keep my score.
I thank authors for comments. Will keep my score.
comment: It seems that there is still a gap between your method and SOTA, but considering the clear motivation behind, I will keep my score.
I would like to thank the authors for addressing my concern, no further questions from my side, I'll increase my score of to 5.
Thank you for taking the time to address my concerns. After reading the other reviews and answers I maintain my review score.
Thank you for engaging with our rebuttal. 

On your concern with *'the accuracy of GraphConv & GenConv on the Cora, Citeseer and Pubmed datasets is higher than my usual experience'*,  we'd like to affirm that it was indeed similar observations we made when we trained various GNNs like GraphConv and GenConv, without edge-directionality awareness. Dir-GNN (published in 2023) highlights the benefits of edge-directionality awareness on model performance. Dir-GNN is not a GNN but instead a wrapper around GNNs, non-invasively introducing edge-directionality awareness into the models being wrapped. Once we replicated this in our architecture, we saw that GNNs like GraphConv, GenConv, EGConv etc., and our own model, began to see a drastic improvement in model performance. We hope this clarifies the reviewer's doubts. 

Thank you for being open to improving your scores.
Thanks to the authors for your patient reply. I recognize the potential of GRCN in the field where throughput time is not significant. Besides, the experimental results presented in Table 1 show that GRCN is very effective in node classification, especially for datasets such as Cora, Citeseer, Pubmed. However, I have to point out that the accuracy of GraphConv & GenConv on the Cora, Citeseer and Pubmed datasets is higher than my usual experience.  
In general, the author's reply eliminated part of my concern. I am open to improve my score.