{'fraction_non_alphanumeric': 0.0366226870148558, 'fraction_numerical': 0.008856731724123953, 'mean_word_length': 4.611509155009667, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks

Graph convolutional networks (GCNs) have shown promising results in processing graph data by extracting structure-aware features. This gave rise to extensive work in geometric deep learning, focusing on designing network architectures that ensure neuron activations conform to regularity patterns within the input graph. However, in most cases the graph structure is only accounted for by considering the similarity of activations between adjacent nodes, which limits the capabilities of such methods to discriminate between nodes in a graph. Here, we propose to augment conventional GCNs with geometric scattering transforms and residual convolutions. The former enables band-pass filtering of graph signals, thus alleviating the so-called oversmoothing often encountered in GCNs, while the latter is introduced to clear the resulting features of high-frequency noise. We establish the advantages of the presented Scattering GCN with both theoretical results establishing the complementary benefits of scattering and GCN features, as well as experimental results showing the benefits of our method compared to leading graph neural networks for semi-supervised node classification, including the recently proposed GAT network that typically alleviates oversmoothing using graph attention mechanisms.


Introduction
Deep learning approaches are at the forefront of modern machine learning. While they are effective in a multitude of applications, their most impressive results are typically achieved when processing data with inherent structure that can be used to inform the network architecture or the neuron connectivity design. For example, image processing tasks gave rise to convolutional neural networks that rely on spatial organization of pixels, while time series analysis gave rise to recurrent neural networks that leverage temporal organization in their information processing via feedback loops and memory mechanisms. The success of neural networks in such applications, traditionally associated with signal processing, has motivated the emergence of geometric deep learning, with the goal of generalizing the design of structure-aware network architectures from Euclidean spatiotemporal structures to a wide range of non-Euclidean geometries that often underlie modern data.
Geometric deep learning approaches typically use graphs as a model for data geometries, either by constructing them from input data (e.g., via similarity kernels) or directly given as quantified interactions between data points [1]. Using such models, recent works have shown that graph neural networks (GNNs) perform well in multiple application fields, including biology, chemistry and social networks [2][3][4]. It should be noted that most GNNs consider each graph together with given node features, as a generalization of images or audio signals, and thus aim to compute whole-graph representations. These in turn, can be applied to graph classification, for example when each graph represents the molecular structure of proteins or enzymes classified by their chemical properties [5][6][7].
On the other hand, methods such as graph convolutional networks (GCNs) presented by [4] consider node-level tasks and in particular node classification. As explained in [4], such tasks are often considered in the context of semi-supervised learning, as typically only a small portion of nodes of the graph possesses labels. In these settings, the entire dataset is considered as one graph and the network is tasked with learning node representations that infer information from node features as well as the graph structure. However, most state-of-the-art approaches for incorporating graph structure information in neural network operations aim to enforce similarity between representations of adjacent (or neighboring) nodes, which essentially implements local smoothing of neuron activations over the graph [8]. While such smoothing operations may be sufficiently effective in whole-graph settings, they often cause degradation of results in node processing tasks due to oversmoothing [8,9], as nodes become indistinguishable with deeper and increasingly complex network architectures. Graph attention networks [10] have shown promising results in overcoming such limitations by introducing adaptive weights for graph smoothing via message passing operations, using attention mechanisms computed from node features and masked by graph edges. However, these networks still essentially rely on enforcing similarity (albeit adaptive) between neighboring nodes, while also requiring more intricate training as their attention mechanism requires gradient computations driven not only by graph nodes, but also by graph edges. We refer the reader to the supplement for further discussion of related work and recent advances in node processing with GNNs.
In this paper, we propose a new approach for node-level processing in GNNs by introducing neural pathways that encode higher-order forms of regularity in graphs. Our construction is inspired by recently proposed geometric scattering networks [11][12][13], which have proven effective for wholegraph representation and classification. These networks generalize the Euclidean scattering transform, which was originally presented by [14] as a mathematical model for convolutional neural networks. In graph settings, the scattering construction leverages deep cascades of graph wavelets [15,16] and pointwise nonlinearities to capture multiple modes of variation from node features or labels. Using the terminology of graph signal processing, these can be considered as generalized band-pass filtering operations, while GCNs (and many other GNNs) can be considered as relying on low-pass filters only. Our approach combines together the merits of GCNs on node-level tasks with those of scattering networks known from whole-graph tasks, by enabling learned node-level features to encode geometric information beyond smoothed activation signals, thus alleviating oversmoothing concerns often raised in GCN approaches. We discuss the benefits of our approach and demonstrate its advantages over GCNs and other popular graph processing approaches for semi-supervised node classification, including significant improvements on the DBLP graph dataset from [17].
Notations: We denote matrices and vectors with bold letters with uppercase letters representing matrices and lowercase letters representing vectors. In particular, I n ∈ R n×n is used for the identity matrix and 1 n ∈ R n denotes the vector with ones in every component. We write ., . for the standard scalar product in R n . We will interchangeably consider functions of graph nodes as vectors indexed by the nodes, implicitly assuming a correspondence between a node and a specific index. This carries over to matrices, where we relate nodes to column or row indices. We further use the abbreviation

Graph Signal Processing
Let G = (V, E, w) be a weighted graph with V := {v 1 , . . . , v n } the set of nodes, E ⊂ {{v i , v j } ∈ V × V, i = j} the set of (undirected) edges and w : E → (0, ∞) assigning (positive) edge weights to the graph edges. We note that w can equivalently be considered as a function of V × V , where we set the weights of non-adjacent node pairs to zero. We define a graph signal as a function x : V → R on the nodes of G and aggregate them in a signal vector x ∈ R n with the i th entry being x(v i ).
We define the (combinatorial) graph Laplacian matrix L := D − W , where W ∈ R n×n is the weighted adjacency matrix of the graph G given by being the degree of the node v i . In practice, we work with the (symmetric) normalized Laplacian matrix L := D −1/2 LD −1/2 = I n −D −1/2 W D −1/2 . It can be verified that L is symmetric and positive semi-definite and can thus be orthogonally diagonalized as . . , λ n ) is a diagonal matrix with the eigenvalues on the main diagonal and Q is an orthogonal matrix containing the corresponding normalized eigenvectors q 1 , . . . , q n ∈ R n as its columns.
A detailed study (see, e.g., [18]) of the eigenvalues reveals that 0 = λ 1 λ 2 · · · λ n 2. We can interpret the λ i , i ∈ [n] as the frequency magnitudes and the q i as the corresponding Fourier modes. We accordingly define the Fourier transform of a signal vector x ∈ R n byx[i] = x, q i for i ∈ [n]. The corresponding inverse Fourier transform is given by x = n i=1x [i]q i . Note that this can be written compactly asx = Q T x and x = Qx. Finally, we introduce the concept of graph convolutions. We define a filter g : V → R defined on the set of nodes and want to convolve the corresponding filter vector g ∈ R n with a signal vector x ∈ R n , i.e. g x. To explicitly compute this convolution, we recall that in the Euclidean setting, the convolution of two signals equals the product of their corresponding frequencies. This property generalizes to graphs [19] in the sense that . Applying the inverse Fourier transform yields where G := diag(ĝ) = diag(ĝ [1], . . . ,ĝ[n]). Hence, convolutional graph filters can be parameterized by considering the Fourier coefficients in G.
Furthermore, it can be verified [20] that when these coefficients are defined as polynomialsĝ[i] := k γ k λ k i for i ∈ N of the Laplacian eigenvalues in Λ (i.e. G = k γ k Λ k ), the resulting filter convolution are localized in space and can be written in terms of L as g x = k γ k L k x without requiring spectral decomposition of the normalized Laplacian. This motivates the standard practice [4,[20][21][22] of using filters that have polynomial forms, which we follow here as well.
For completeness, we note there exist alternative frameworks that generalize signal processing notions to graph domains, such as [23], which emphasizes the construction of complex filters that requires a notion of signal phase on graphs. However, extensive study of such alternatives is out of scope for the current work, which thus relies on the well-established (see, e.g., [24]) framework described here.

Graph Convolutional Network
Graph convolutional networks (GCNs), introduced in [4], consider semi-supervised settings where only a small potion of the nodes is labeled. They leverage intrinsic geometric information encoded in the adjacency matrix W together with node labels by constructing a convolutional filter parametrized byĝ[i] := θ(2 − λ i ), where the choice of a single learnable parameter is made to avoid overfitting. This parametrization yields a convolutional filtering operation given by The matrix I n +D −1/2 W D −1/2 has eigenvalues in [0, 2]. This could lead to vanishing or exploding gradients. This issue is addressed by the following renormalization trick [4]: . This operation replaces the features of the nodes by a weighted average of itself and its neighbors. Note that the repeated execution of graph convolutions will enforce similarity throughout higher-order neighborhoods with order equal to the number of stacked layers. Setting A :=D −1/2WD−1/2 , the complete layer-wise propagation rule takes the form h j = σ where indicates the layer with N neurons, h j ∈ R n the activation vector of the j th neuron, θ ij the learned parameter of the convolution with the i th incoming activation vector from the preceding layer and σ(.) an element-wise applied activation function. Written in matrix notation, this gives where Θ ∈ R N −1 ×N is the weight-matrix of the th layer and H ∈ R n×N contains the activations outputted by the th layer.
We remark that the above explained GCN model can be interpreted as a low-pass operation. For the sake of simplicity, let us consider the convolutional operation (Eq. 1) before the reparametrization trick. If we observe the convolution operation as the summation g θ x = n i=1 γ ix [i]q i , we clearly see that higher weights γ i = θ(2 − λ i ) are put on the low-frequency harmonics, while high-frequency harmonics are progressively less involved as 0 = λ 1 λ 2 · · · λ n 2. This indicates that the model can only access a diminishing portion of the original information contained in the input signal the more graph convolutions are stacked. This observation is in line with the well-known oversmoothing problem [8] related to GCN models. The repeated application of graph convolutions will successively smooth the signals of the graph such that nodes cannot be distinguished anymore.

Geometric Scattering
In this section, we recall the construction of geometric scattering on graphs. This construction is based on the lazy random walk matrix which is closely related to the graph random walk defined as a Markov process with transition matrix R := W D −1 . The matrix P however allows self loops while normalizing by a factor of two in order to retain a Markov process. Therefore, considering a distribution µ 0 ∈ R n of the initial position of the lazy random walk, its positional distribution after t steps is encoded by µ t = P t µ 0 .
As discussed in [12], the propagation of a graph signal vector x ∈ R n by x t = P t x performs a lowpass operation that preserves the zero-frequencies of the signal while suppressing high frequencies.
In geometric scattering, this low-pass information is augmented by introducing the wavelet matrices Ψ k ∈ R n×n of scale 2 k , k ∈ N 0 , This leverages the fact that high frequencies can be recovered with multiscale wavelet transforms, e.g., by decomposing nonzero frequencies into dyadic frequency bands. The operation (Ψ k x)[v i ] collects signals from a neighborhood of order 2 k , but extracts multiscale differences rather than averaging over them. The wavelets in Eq. 3 can be organized in a filter bank {Ψ k , Φ K } 0≤k≤K , where Φ K := P 2 K is a pure low-pass filter. The telescoping sum of the matrices in this filter bank constitutes the identity matrix, thus enabling to reconstruct processed signals from their filter responses. Further studies of this construction and its properties (e.g., energy preservation) appear in [25] and related work.
Geometric scattering was originally introduced in the context of whole-graph classification and consisted of aggregating scattering features. These are stacked wavelet transforms (see Fig. 1) parameterized via tuples p := (k 1 , . . . , k m ) ∈ ∪ m∈N N m 0 containing the bandwidth scale parameters, which are separated by element-wise absolute value nonlinearities 2 according to where m corresponds to the length of the tuple p. The scattering features are aggregated over the whole graph by taking q th -order moments over the set of nodes, As our work is devoted to the study of node-based classification, we reinvent this approach in a new context, keeping the scattering transforms U p on a node-level by dismissing the aggregation step in Eq. 5. For each tuple p, we define the following scattering propagation rule, which mirrors the GCN rule but replaces the low-pass filter by a geometric scattering operation resulting in We note that in practice, we only choose a subset of tuples, which is chosen as part of the network design explained in the following section. Figure 1: Illustration of geom. scattering at the node level (U (x) = {U p x : p ∈ N m 0 , m = 0, 1, 2}) and at the graph level (S(x) = {S p,q x : q ∈ N, p ∈ N m 0 , m = 0, 1, 2}), extracted according to the wavelet cascade in Eqs. 3-5. While m ≤ 2 orders are illustrated here, more can be used in general.

Combining GCN and Scattering Models
To combine the benefits of GCN models and geometric scattering adapted to the node level, we now propose a hybrid network architecture as shown in Fig. 2. It combines low-pass operations based on GCN models with band-pass operations based on geometric scattering. To define the layer-wise propagation rule, we introduce Note that every GCN filter uses a different propagation matrix A k and therefore aggregates information from k-step neighborhoods. Similarly, we proceed with H sct,k according to Eq. 6 and calculate where p k ∈ m∈N N m 0 , k = 1, . . . , C sct enables scatterings of different orders and scales. Finally, the GCN components and scattering components get concatenated to The learned parameters are the weight matrices Θ gcn,k , Θ sct,k ∈ R N −1 ×N coming from the convolutional and scattering layers. These are complemented by vectors of the biases b gcn,k , b sct,k ∈ R N , which are transposed and vertically concatenated n times to the matrices B gcn,k , B sct,k ∈ R n×N . To simplify notation, we assume here that all channels use the same number of neurons (N ). Waiving this assumption would slightly complicate the notation but works perfectly fine in practice.
In this work, for simplicity, and because it is sufficient to establish our claim, we limit our architecture to three GCN channels and two scattering channels as illustrated in Fig. 2 (b). Inspired by the aggregation step in classical geometric scattering, we use σ(.) := | . | q as our nonlinearity. However, unlike the powers in Eq. 5, the q th power is applied at the node-level here instead of being aggregated as moments over the entire graph, thus retaining the distinction between node-wise activations.
We set the input of the first layer H 0 to have the original node features as the graph signal. Each subchannel (GCN or scattering) transforms the original feature space to a new hidden space with the dimension determined by the number of neurons encoded in the columns of the corresponding submatrix of H . These transformations are learned by the network via the weights and biases.
Larger matrices H (i.e., more columns as the number of nodes in the graph is fixed) indicate that the weight matrices have more parameters to learn. Thus, the information in these channels can be propagated well and will be sufficiently represented.
In general, the width of a channel is relevant for the importance of the captured regularities. A wider channel suggests that these frequency components are more critical and need to be sufficiently learned. Reducing the width of the channel suppresses the magnitude of information that can be learned from a particular frequency window. For more details and analysis of specific design choices in our architecture we refer the reader to the ablation study provided in the supplement.

Graph Residual Convolution
Using the combination of GCN and scattering architectures, we collect multiscale information at the node level. This information is aggregated from different localized neighborhoods, which may exhibit vastly different frequency spectra. This comes for example from varying label rates in different graph substructures. In particular, very sparse graph sections can cause problems when the scattering features actually learn the difference between labeled and unlabeled nodes, creating high-frequency noise. In the classical geometric scattering used for whole-graph representation, geometric moments were used to aggregate the node-based information, serving at the same time as a low-pass filter. As we want to keep the information localized on the node level, we choose a different approach inspired by skip connections in residual neural networks [26]. Conceptually, this low-pass filter, which we call graph residual convolution, reduces the captured frequency spectrum up to a cutoff frequency as depicted in Fig. 2 (e).
The graph residual convolution matrix, governed by the hyperparameter α, is given by A res (α) = 1 α+1 (I n + αW D −1 ) and we apply it after the hybrid layer of GCN and scattering filters. For α = 0 we get the identity (no cutoff), while α → ∞ results in R = W D −1 . This can be interpreted as an interpolation between the completely lazy (i.e., stationary) random walk and the non-resting (i.e., with no self-loops) random walk R. We apply the graph residual layer on the output H of the Scattering GCN layer (Eq. 7). The update rule for this step, illustrated in Fig. 2 (c), is then expressed by are learned biases (similar to the notations used previously), and N is the number of features of the concatenated layer H . If H +1 is the final layer, we choose N +1 equal to the number of classes.

Additional Information Introduced by Node-level Scattering Features
Before empirically verifying the viability of the proposed architecture in node classification tasks, we first discuss and demonstrate the additional information provided by scattering channels beyond that provided by traditional GCN channels. We first consider information carried by node features, treated as graph signals, and in particular their regularity over the graph. As discussed in Sec. 3, such regularity is traditionally considered only via smoothness of signals over the graph, as only low frequencies are retained by (local) smoothing operations. Band-pass filtering, on the other hand, can retain other forms of regularity such as periodic or harmonic patterns. The following lemma demonstrates this difference between GCN and scattering channels. Lemma 1. Consider a cyclic graph on 2n nodes, n ∈ N, and let x ∈ R 2n be a 2-periodic signal on it (i.e., x 2 −1 = a and x 2 = b, for ∈ [n] for some a = b ∈ R). Then, for any θ ∈ R, the GCN filtering g θ x from Eq. 1 yields a constant signal, while the scattering filter Ψ 0 x from Eq. 3 still produces a 2-periodic signal. Further, this result extends to any finite linear cascade of such filters (i.e., g θ · · · g θ x or Ψ 0 · · · Ψ 0 x with k ∈ N filter applications in each).
While this is only a simple example, it already indicates a fundamental difference between the regularity patterns considered in graph convolutions compared to our approach. Indeed, it implies that if a smoothing convolutional filter encounters alternating signals on isolated cyclic substructures within a graph, their node features become indistinguishable, while scattering channels (with appropriate scales, weights and bias terms) will be able to make this distinction. Moreover, this difference can be generalized further beyond cyclic structures to consider features encoding two-coloring information on constant-degree bipartite graphs, as shown in the following lemma. We refer the reader to the supplement for a proof of this lemma, which also covers the previous one as a particular case, as well as numerical examples illustrating the results in these two lemmas. Lemma 2. Consider a bipartite graph on n ∈ N nodes with constant node degree β. Let x ∈ R n be a 2-coloring signal (i.e., with one part assigned constant a and the other b, for some a = b ∈ R). Then, for any θ ∈ R, the GCN filtering g θ x from Eq. 1 yields a constant signal, while the scattering filter Ψ 0 x from Eq. 3 still produces a (non-constant) 2-coloring of the graph. Further, this result extends to any finite linear cascade of such filters (i.e., g θ · · · g θ x or Ψ 0 · · · Ψ 0 x with k ∈ N filter applications in each).
Beyond the information encoded in node features, graph wavelets encode geometric information even when it is not carried by input signals. Such a property has already been established, e.g., in the context of community detection, where white noise signals can be used in conjunction with graph wavelets to cluster nodes and reveal faithful community structures [27]. To demonstrate a similar property in the context of GCN and scattering channels, we give an example of a simple graph structure with two cyclic substructures of different sizes (or cycle lengths) that are connected by one bottleneck edge. In this case, it can be verified that even with constant input signals, some geometric information is encoded by its convolution with graph filters as illustrated in Fig. 3 (we refer the reader to the supplement for exact calculation of filter responses). However, as demonstrated in this case, while the information provided by the GCN filter responses g θ x from Eq. 1 is not constant, it does not distinguish between the two cyclic structures (and a similar pattern can be verified for Ax).
Formally, each node u in one cycle is shown to have at least one node v in the other with the same filter response (i.e., g θ x(u) = g θ x(v)). In contrast, the information extracted by the wavelet filter response Ψ 3 x (used in geometric scattering) distinguishes between cycles and would allow for their separation. We note that this property generalizes to other cycle lengths as discussed in the supplement, but leave more extensive study of geometric information encoding in graph wavelets to future work.  Color coding differs slightly between plots, but is consistent within each plot, indicating nodes with numerically indistinguishable response values.

Empirical Results
To evaluate our Scattering GCN approach, we compare it to several established methods for semisupervised node classification, including the original GCN [4], which is known to be subject to the oversmoothing problem, as discussed in [8], and Sec. 1 and 3 here. Further, we compare our approach with two recent methods that address the oversmoothing problem. The approach in [8] directly addresses oversmoothing in GCNs by using partially absorbing random walks [28] to mitigate rapid mixing of node features in highly connected graph regions. The graph attention network (GAT) [10] indirectly addresses oversmoothing by training adaptive node-wise weighting of the smoothing operation via an attention mechanism. Furthermore, we also include two alternatives to GCN networks based on Chebyshev polynomial filters [20] and belief propagation of label information [29] computed via Gaussian random fields. Finally, we include two baseline approaches to verify the contribution of our hybrid approach compared to compared to the classifier from [13] that is solely based on handcrafted graph-scattering features, and compared to SVM classifier acting directly on node features without considering graph edges, which does not incorporate any geometric information.
The methods from [4,8,10,20,29] were all executed using the original implementations accompanying their publications. These are tuned and evaluated using the standard splits provided for the benchmark datasets for fair comparison. We ensure that the reported classification accuracies agree with previously published results when available. The tuning of our method (including hyperparameters and composition of GCN and scattering channels) on each dataset was done via grid search (over a fixed set of choices for all datasets) using the same cross validation setup used to tune competing methods. For further details, we refer the reader to the supplement, which contains an ablation study evaluating the importance of each component in our proposed architecture. Our comparisons are based on four popular graph datasets with varying sizes and connectivity structures summarized in Tab. 1 (see, e.g., [30] for Citeseer, Cora, and Pubmed, and [17] for DBLP). We order the datasets by increasing connectivity structure, reflected by their node degrees and edges-to-nodes ratios. As discussed in [8], increased connectivity leads to faster mixing of node features in GCN, exacerbating the oversmoothing problem (as nodes quickly become indistinguishable) and degrading classification performance. Therefore, we expect the impact of scattering channels and the relative improvement achieved by Scattering GCN to correspond to the increasing connectivity order of datasets in Tab. 1, which is maintained for our reported results in Tab. 2 and Fig. 4. We first consider test classification accuracy reported in Tab. 2, which shows that our approach outperforms other methods on three out of the four considered datasets. On the remaining one (namely Citeseer) we are only outperformed by GAT. However, we note that this dataset has the weakest connectivity structure (see Tab. 1) and the most informative node features (e.g., achieving 61.1% accuracy via linear SVM without considering any graph information). In contrast, on DBLP, which has the richest connectivity structure and least informative features (only 48.2% SVM accuracy), we significantly outperform GAT (over 15% improvement), which itself significantly outperforms all other methods (by 6.8% or more) except for the graph scattering baseline from [13].
Next, we consider the impact of training size on classification performance as we are interested in semi-supervised settings where only a small portion of nodes in the graph are labelled. Fig. 4 (top) presents the classification accuracy (on validation set) for the training size reduced to 20%, 40%, 60%, 80% and 100% of the original training size available for each dataset. These results indicate that Scattering GCN generally exhibits greater stability to sparse training conditions compared to other methods. Importantly, we note that on Citeseer, while GAT outperforms our method for the original training size, its performance degrades rapidly when training size is reduced below 60% of the original one, at which point Scattering GCN outperforms all other methods. We also note that on Pubmed, even a small decrease in training size (e.g., 80% of original) creates a significant performance gap between Scattering GCN and GAT, which we believe is due to node features being less independently informative in this case (see baseline in Tab. 2) compared to Citeseer and Cora.
Finally, in Fig. 4 (bottom), we consider the evolution of (validation) classification error during the training process. Overall, our results indicate that the training of Scattering GCN reaches low validation errors significantly faster than Partially Absorbing and GAT 3 , which are the two other leading methods (in terms of final test accuracy in Tab. 2). On Pubmed, which is the largest dataset considered here (by number of nodes), our error decays at a similar rate to that of GCN, showing a notable gap over all other methods. On DBLP, which has a similar number of nodes but significantly more edges, Scattering GCN takes longer to converge (compared to GCN), but as discussed before, it also demonstrates a significant (double-digit) performance lead compared to all other methods.

Conclusion
Our study of semi-supervised node-level classification tasks for graphs presents a new approach to address some of the main concerns and limitations of GCN models. We discuss and consider richer notions of regularity on graphs to expand the GCN approach, which solely relies on enforcing smoothness over graph neighborhoods. This is achieved by incorporating multiple frequency bands of graph signals, which are typically not leveraged in traditional GCN models. Our construction is inspired by geometric scattering, which has mainly been used for whole-graph classification so far. Our results demonstrate several benefits of incorporating the elements presented here (i.e., scattering channels and residual convolutions) into GCN architectures. Furthermore, we expect the incorporation of these elements together in more intricate architectures to provide new capabilities of pattern recognition and local information extraction in graphs. For example, attention mechanisms could be used to adaptively tune scattering configurations at the resolution of each node, rather than the global graph level used here. We leave the exploration of such research avenues for future work.

Broader Impact
Node classification in graphs is an important task that gains increasing interest nowadays in multiple fields looking into network analysis applications. For example, they are of interest in social studies, where a natural application is the study of social networks and other interaction graphs. Other popular application fields include biochemistry and epidemiology. However, this work is computational in nature and addresses the foundations of graph processing and geometric deep learning. As such, by itself, it is not expected to raise ethical concerns nor to have adverse effects on society.  Proof of Lemma 1. Note that G 2n cyc is a bipartite graph with constant node degree β = 2. Therefore, the proof of Lemma 1 can be seen as special case of Lemma 2, which is proved below.

Supplement
Proof of Lemma 2. We first notice that if g 1 2 x is constant, then g θ x = 2θ(g 1 2 x) is constant for any θ. Furthermore, for the considered class of graphs, D = β I n with β > 0, implying that D −1 = 1 β I n and D −1/2 = 1 √ β I n . Therefore, as a direct result of Eq. 1 in the main paper, it holds that Similarly, it is easily verified that any k ∈ N applications of the convolution with g θ (for any θ ∈ R) can be written as 2 k θ k P k x. Furthermore, since P is column-stochastic and (here) symmetric (thus also row-stochastic), we have P c = c for any constant signal c = c1 2n . Thus, it is sufficient to show that P x is a constant signal to verify the first claim of the lemma.
We consider G n bi,β = (V, E). For any node v ∈ V , according to Eq. 8, we can write where we denote by N (v) the neighborhood of the node v and set N (v)). This implies that We now consider a 2-coloring signal x ∈ R n . W.l.o.g., let thus verifying the first claim of the lemma as the choice of v was arbitrary. Finally, it is now straightforward to verify the second claim as well, since the operation Ψ 0 x = (I n −P )x = x − a+b 2 1 n retains a 2-coloring signal (the original colors are shifted by a constant: − a+b 2 ).

B Geometric Information Encoded by Graph Wavelets (supp. info. Sec. 7)
Let G ≥ cyc := {G k cyc : k ≥ }, 3 ≤ ∈ N, be the class of unweighted cyclic graphs of length greater than or equal to . Furthermore, let G be the class of graphs constructed by taking n ≥ 2 cyclic graphs G 1 , . . . , G n , arranging them in the order of the indexes, and connecting subsequent cycles with bottleneck edges as described in the following.
1. We take G 1 , G n ∈ G ≥4 cyc and G 2 , . . . , G n−1 ∈ G ≥ cyc . 2. The (sub)graph G i , 1 ≤ i ≤ n − 1, is connected by exactly one bottleneck edge to G i+1 . 3. No edge is connecting (sub)graphs G i and G j if |i − j| ≥ 2. 4. For each G i , 2 ≤ i ≤ n − 1, there are exactly two nodes in G i with bottleneck edges coming out of them, and these nodes are the farthest from each other in the cycle 4 (in shortest-path distance).
This construction essentially generalizes the graph demonstrated in Fig. 3 of the main paper (see Sec. 7). The following lemma shows that on such graphs, the filter responses of g θ for a constant signal will encode some geometric information, but will not distinguish between the cycles in the graph. Note that this result can also be generalized further to a chain that is closed by connecting G n and G 1 with a bottleneck edge if we further assume that G 1 , G n ∈ G ≥7 cyc . Lemma 3. Let G = (V, E) a graph of the class G 7 . We consider a constant signal c = c1 |V | , for some c ∈ R. Then, for all nodes v ∈ V and for any θ ∈ R, the filter response (g θ c) [v] shares its value with at least one node of each other cyclic substructure.
Proof. First, note that V contains only the following two kinds of nodes. We refer to a node of degree 3 (those contained in a bottleneck edge) as a hub, while using the term pass for all other nodes (those of degree 2). Furthermore, due to the minimal cycle length, and the shortest-path distance requirement between hub nodes in the same cycle, only three types of neighborhoods can be encountered. Indeed, it is easy to see that each hub node has one hub neighbor and two pass neighbors, while pass nodes can either have two pass neighbors or one pass and one hub.
Next, we notice that for any θ and any c, the filter response (g θ c) [v] = cθ(g 1 1 |V | )[v] is fully determined by the neighborhood type of v ∈ V . Therefore, computing these boils down to a simple proof by cases: 1. Let v be a hub, then the corresponding response is (g θ c) [v] = c θ (1 + 1 3 + 1

2.
Let v be a pass with two pass neighbors, then the corresponding response is (g θ c) [v] = c θ (1 + 1 2 + 1 2 ) = 2 · c θ. 3. Let v be a pass with one hub neighbor and one pass neighbor, then the corresponding response is (g θ c) [v] = c θ (1 + 1 Finally, it is trivial to see that every cyclic substructure from the class G 7 contains at least one hub and two passes connected to that hub. The existence of a pass only connected to other passes follows from the choice of the minimal cycle lengths together with the requirement that two hubs within a cycle have maximal distance from each other. Let us now revisit the example given in the main paper (see Fig. 3 or a copy in Fig. 6). We consider a graph consisting of 14 nodes organized in 2 cycles (v 1 ∼ v 2 · · · v 6 ∼ v 1 and v 7 ∼ v 8 · · · v 14 ∼ v 7 here) of different length (i.e., 6 and 8 here), which are connected with one single edge between any two nodes taken from different cycles (v 4 and v 7 here). As this is a specific case of Lemma 3, the filter responses of the GCN filter g θ for a constant signal x would indeed not distinguish between cycles as discussed in Sec. 7 of the main paper (with the pattern shown in Figs. 3 and 6 for θ = 1).
On the other hand, the filter responses of Ψ 3 x on a constant signal (e.g., x = 1 14 ∈ R 14 ) on this graph can be verified empirically as follows:  These responses with appropriate color coding give the illustration in Fig. 2 in the main paper. A similar distinction between cycles with band-pass filters can also be empirically verified for other cases covered by Lemma 3. We leave further theoretical studies of this property of graph wavelets to future work.

C Further Discussion of Related Work
As many applied fields such as Bioinformatics and Neuroscience heavily rely on the analysis of graphstructured data, the study of reliable classification methods has received much attention lately. In this work, we focus on the particular class of semi-supervised classification tasks, where GCN models [4,8] recently proved to be effective. Their theoretical studies reveal however that graph convolutions can be interpreted as Laplacian smoothing operations, which poses fundamental limitations on the approach. Another branch of GNNs, manifested in [10], introduces self-attention mechanisms to determine adequate node-wise neighborhoods, which in turn alleviate the mentioned shortcomings of GCN approaches. Further, [9] developed a theoretical framework based on graph signal processing, relying on the relation between frequency and feature noise, to show that GNNs perform a low-pass filtering on the feature vectors. In [31], multiple powers of the adjacency matrix were used to learn the higher-order neighborhood information, while [22] used Lanczos algorithm to construct a low-rank approximation of the graph Laplacian that efficiently gathers multiscale information, demonstrated on citation networks and the QM8 quantum chemistry dataset. Finally, [32] studied wavelets on graphs and collected higher-order neighborhood information based on wavelet transformation.
Together with the study of learned networks, recent studies have also introduced the construction of geometric scattering transforms, relying on manually crafted families of graph wavelet transforms [11][12][13]. Similar to the initial motivation of geometric deep learning to generalize convolutional neural networks, the geometric scattering framework generalizes the construction of Euclidean scattering from [14] to the graph setting. Theoretical studies [e.g., 11,33,25] established energy preservation properties and the stability of these generalized scattering transforms to perturbations and deformations of graphs and signals on them. Moreover, the practical application of geometric scattering to whole-graph data analysis was studied in [12], achieving strong classification results on social networks and biochemistry data, which established the effectiveness of this approach.
As discussed in the main paper, this work aims to combine the complementary strengths of GCN models and geometric scattering and to provide a new avenue for incorporating richer notions of regularity in GNNs. Further, our construction integrates trained task-driven components in geometric scattering architectures. Finally, while most previous work on geometric scattering focused on whole-graph settings, we consider node-level processing, which requires new considerations about the construction.

D Technical Details
Similar to other neural networks, the presented Scattering GCN poses several architecture choices and hyperparameters that can be tuned and affect its performance. For simplicity, we set the last layer before the output classification to be the residual convolution layer and only consider one or two hybrid layers before it, each consisting of three GCN channels and two scattering channels. We note that this restricted setup simplifies the network tuning process and was sufficient in our experiments to obtain promising results (outperforming other methods, as shown in the main paper), but can naturally be generalized further to deeper or wider architectures in practice. Furthermore, based on preliminary results, Cora, Citeseer and Pubmed were set to use only one hybrid layer as the addition of a second one was not cost-effective (considering the added complexity of a grid search for tuning hyperparameters based on validation results). For DBLP, two layers were used due to a significant increase in performance. We note that even with a single hybrid layer our model achieves 73.1% test accuracy (compared to the reported 81.5% for two layers) and still significantly outperforms GAT (66.1%) and the other methods (below 60%).
Validation & testing procedure: All tests were done using train-validation-test splits of the datasets, where validation accuracy is used for tuning hyperparameters and test accuracy is reported in the comparison table. The same splits were used for all methods for a fair comparison. To ensure our evaluation is comparable with previous work, for Citeseer, Cora and Pubmed we used the same settings as in [4], following the standard practice used in other work reporting results on these datasets. For DBLP, as far as we know, no common standard is established in the literature. Here, we used a ratio of 5 : 1 : 1 between train, validation, and test.
Hyperparameter tuning: Given the general network architectures and train-validation-test splits, the hyperparameter tuning was performed for each dataset using grid search guided by validation accuracy. The grid covered the tuning of the residual convolution via α, the nonlinarity exponent q (inspired by scattering moments), the scattering channel configuration (i.e., scales used in these two channels), and the widths of channels in the network. The results of this tuning process are presented in the following table.
Scat. config.: Channel widths: It should be noted that for DBLP, the hybrid-layer parameters are shared between the two used layers in order to simplify the tuning process, which was generally less exhaustive than for the other three datasets, since even with limited tuning our method significantly outperformed all other methods. That being said, we note that the difference in effectiveness of architecture and hyperparameter choices (as well as the increased performance of our approach compared to others) observed in this case could be a result of the significantly different connectivity exhibited by its graph as discussed briefly in Sec. 8 (of the main paper). Regardless, as more exhaustive tuning would not degrade (and likely improve) the results obtained from Scattering GCN, we view our limited tuning done here as sufficient for establishing the advantages provided by our approach over other methods and leave a more intensive study of the DBLP dataset to future work.
Hardware & software environment: All comparisons were executed on the same HPC cluster with intel i7-6850K CPU and NVIDIA TITAN X Pascal GPU. Scattering GCN was implemented in Python using the PyTorch [34] framework. Implementations of all other methods were taken directly from the code accompanying their publications.

E Ablation Study
The two main components of our Scattering GCN architecture contribute together to achieve significant improvements over pure GCN models. Namely, these are the additional scattering channels (i.e., U J1 and U J2 ) and the residual convolution (controlled by the hyperparemeter α). To further explore their contribution and the hyperparameter space for their tuning, Tab. 3-7 show classification results over the Cora dataset for α = 0.01, 0.1, 0.35, 0.5, 1.0 (controlling the residual convolution layer) over multiple scattering channel configurations. For presentation brevity and simplicity, we focus our presented ablation benchmark on this dataset here, but note that similar results are also observed on the other datasets. The rows and columns in each table denote the two scattering channels used in the Scattering GCN, together with the three GCN channels (i.e., for A k , k = 1, 2, 3).
First, we consider the importance of the residual graph convolution layer. We note that setting α = 0 effectively ignores this layer (i.e., by setting its operation to be the identity), while increasing α makes the filtering provided by it to be more dominant until α = 1, where it essentially becomes a random walk-based low-pass filter. Therefore, to evaluate the importance of this component of our architecture, it is sufficient to evaluate the impact of α on the classification accuracy. Indeed, our results (see Tab. [3][4][5][6][7] indicate that increasing α to non-negligible nonzero values improves classification performance, which we interpret to be due to the removal of high-frequency noise. However, when α further increases (in particular when α = 1 in this case) the smoothing provided by this layer degrades the performance to a level close to the traditional GCN [4]. Therefore, these results suggest that when well tuned (e.g., as done via grid search in this work), the graph residual convolution plays a critical role in improving results, which can also be seen by the results of the hyperparameter tuning shown in the previous section.
Next, we consider the scales used in the two scattering channels of our hybrid architecture, which correspond to the rows and columns of Tab. 3-7 here. While our results show that the network is relatively robust to this choice, we can observe that generally utilizing purely second-order coefficients gives slightly worse results than either first-order ones or a mix of first-and second-order coefficients. Nevertheless, most configurations of scattering scales (with appropriate choice of α) give better results than pure GCN, thus indicating that added information is extracted by scattering channels.
We note that for α = 0.35 (Tab. 5), all scale configurations outperform GAT (83%) and all other reported methods in Tab. 2 (of the main paper). As a result, even the average accuracy over all scale configurations (83.5%) in this case shows an improvement over these other methods, thus further establishing the advantage of our approach. It is important to mention that while this improvement is affected by the tuning of the residual convolution, it also relies on the addition of scattering channels. Indeed, by itself, the residual convolution layer only applies a low-pass (smoothing) filter and therefore, without scattering channels, would essentially be equivalent to a conventional GCN.
We remark that the results presented in this work are based on a limited grid search, while the ablation study here indicates that many of the possible configurations provide noticeable classification     performance improvement over other methods. It is likely that the reported results, in fact, provide a lower bound on the improvement attained by Scattering GCN, while a more exhaustive optimization of the architecture and its hyperparameters can further improve and solidify its advantages. We leave such exhaustive study for future work, which will also consider the incorporation of other advanced components (e.g., attention mechanisms) in the model architecture.
Finally, to further validate the importance of band-pass information added by the presented architecture here, we provide an ablation study of the impact each channel has on classification performance. We focus here on α = 0.35 with the best configuration on Cora (i.e., achieving 84.2% accuracy when all channels are used). Then, we remove each of the band-pass or low-pass channels individually from the network, and reevaluate network performance with the remaining four channels. Our results, presented in Tab. 8, indicate that while information captured by A,A 2 and A 3 is important for the classification task, which is to be expected given the prevalence of such filters in GCNs, the band-pass information extracted by the scattering channels (with Ψ 2 and Ψ 1 in this case) plays a crucial role in achieving the performance of our method. In particular, we note that Ψ 1 in this case has a major impact on the accuracy, driving the difference between underperforming and outperforming GAT, thus strengthening the claim that important information in graph features is contained in higher frequencies extracted by band-pass filtering, which is not recovered by smoothing operations.

F Implementation
Python code accompanying this work is available on github.com/dms-net/scatteringGCN.