Source-linked AI summary
Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks
Yimeng Min, Frederik Wenkel, Guy Wolf
TL;DR
GCNs model node relationships by smoothing neighboring activations, but deeper smoothing can make nodes indistinguishable. Scattering GCN combines GCN and node-level geometric scattering operations; the paper reports advantages over GCNs and other methods on semi-supervised node classification, including significant improvements on DBLP.
Problem
Method
Results
The authors report advantages over GCNs and other popular graph-processing approaches for semi-supervised node classification, including significant improvements on DBLP.
Source: §1 · p. 2Takeaways & Limitations
Theoretical and experimental results support combining scattering features with GCNs to capture graph information beyond smoothed activations.
Source: §7 · p. 7, §9 · p. 9The notation assumes all channels have the same number of neurons, although the authors say relaxing this assumption works in practice.
Source: §5 · p. 6
Abstract
from arXiv · showhide
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.
1 Introduction
Geometric deep learning uses graph structure to build structure-aware models, while node-classification GCNs learn from features and graph structure when only some nodes are labeled. This paper adds geometric scattering pathways to GCNs to capture graph regularities beyond neighboring-node smoothing.
1 Introduction
- Geometric deep learning generalizes structure-aware architectures from Euclidean data such as images and time series to non-Euclidean geometries.Graphs can represent data geometry and quantified interactions; GNNs are used in applications including biology, chemistry, and social networks.Source: §1 · pp. 1–2
- For semi-supervised node classification, GCNs use node features and graph structure when only a small portion of nodes is labeled.The dataset is treated as one graph, and the model learns node representations for classification.Source: §1 · p. 2
- Most graph neural networks enforce similarity between neighboring-node activations, which can make nodes indistinguishable as deeper GCNs oversmooth.Graph attention uses adaptive weights but still smooths neighboring nodes and requires gradient computations driven by both nodes and edges.Source: §1 · p. 2
- Scattering pathways add band-pass filtering to GCNs’ low-pass operations, enabling node features to encode higher-order graph regularities.The authors report advantages over GCNs and other approaches for semi-supervised node classification, including significant improvements on DBLP.Source: §1 · p. 2
2 Graph Signal Processing
This section establishes graph signals and graph convolution using the graph Laplacian and its Fourier representation. It motivates polynomial filters as a practical way to define localized graph convolutions.
2 Graph Signal Processing
- The normalized graph Laplacian is symmetric and positive semidefinite, with eigenvectors serving as Fourier modes and eigenvalues as graph-frequency magnitudes.A graph signal is a node-indexed vector, and its Fourier transform consists of its inner products with the Laplacian eigenvectors.Source: §2 · pp. 2–3
- Graph convolution multiplies the Fourier coefficients of the filter and signal, then transforms the result back to the node domain.This lets graph filters be parameterized by their Fourier coefficients.Source: §2 · p. 3
- Polynomial filter forms yield spatially localized convolutions expressible using powers of the Laplacian, without spectral decomposition.The paper follows the standard practice of using polynomial filters.Source: §2 · p. 3
3 Graph Convolutional Network
The section describes GCN filtering as a low-pass operation that averages node features with those of their neighbors. Repeated application suppresses higher-frequency information and can lead to oversmoothing.
3 Graph Convolutional Network
- GCNs are presented for semi-supervised node classification, using a single learnable filter parameter to avoid overfitting.The filter is parameterized as θ(2 − λ_i), and a renormalization trick is introduced because the preceding matrix can have eigenvalues in [0, 2].Source: §3 · p. 3
- Repeated graph convolutions replace node features with weighted averages of each node and its neighbors, extending similarity across higher-order neighborhoods.The propagation uses a renormalized adjacency matrix; the layer weights mix features before an element-wise activation.Source: §3 · pp. 3–4
- GCN filtering weights low-frequency harmonics more heavily, progressively reducing the contribution of higher frequencies.The section interprets this operation as low-pass filtering before the renormalization trick.Source: §3 · p. 4
- As layers are stacked, high-frequency information diminishes until nodes may no longer be distinguishable, the oversmoothing problem.The section links this to GCNs’ low-pass filtering behavior.Source: §3 · p. 4
4 Geometric Scattering
Geometric scattering augments low-pass graph propagation with multiscale wavelets that extract differences across neighborhoods. The paper adapts the transforms to node-level classification by retaining node-wise features rather than aggregating them over the graph.
4 Geometric Scattering
- Lazy random-walk propagation is low-pass, while wavelet matrices recover multiscale differences from neighborhoods rather than simply averaging them.The wavelet responses and a pure low-pass filter form a filter bank whose responses sum to the identity, enabling reconstruction.Source: §4 · p. 4
- Scattering features are built by cascading wavelet transforms across tuples of bandwidth scales, with element-wise absolute-value nonlinearities between transforms.The illustrated node-level cascade includes orders up to two, though more orders can be used.Source: §4 · p. 4, Figure 1 · p. 5
- Node-level scattering replaces the GCN low-pass filter with a geometric scattering operation while omitting the graph-level aggregation step.The network uses a subset of scattering tuples chosen as part of its design.Source: §4 · p. 4
5 Combining GCN and Scattering Models
Scattering GCN combines GCN low-pass operations with scattering band-pass operations in a hybrid node-level architecture. Learned channel widths determine how many neurons represent each frequency component, and the model uses three GCN channels and two scattering channels in the described setup.
5 Combining GCN and Scattering Models
- The hybrid layer concatenates GCN and scattering channels, combining information from different neighborhood scales and frequency ranges.Each GCN channel uses a different propagation matrix for k-step neighborhoods; scattering channels cover different orders and scales.Source: §5 · p. 5
- The described architecture uses three GCN channels, two scattering channels, and node-level qth-power nonlinearity.Unlike classical scattering's graph-level moment aggregation, the qth power is applied at each node to retain node-wise activations.Source: §5 · p. 6
- Wider channels provide more learned parameters and represent their captured regularities more fully, while narrower channels suppress the information learned in those frequency windows.The input to the first layer is the original node features; channel transformations are learned through weights and biases.Source: §5 · p. 6
6 Graph Residual Convolution
Graph residual convolution follows the hybrid GCN-scattering layer to reduce high-frequency noise while retaining node-level features. Its hyperparameter α controls an interpolation from the identity operation to the non-resting random walk.
6 Graph Residual Convolution
- Graph residual convolution applies a low-pass filter after the hybrid layer, reducing the captured frequency spectrum up to a cutoff while keeping information localized at the node level.It addresses high-frequency noise that can arise when scattering features distinguish labeled from unlabeled nodes in very sparse graph sections.Source: §6 · p. 6
- α controls the residual propagation from the identity at α = 0 to W D^-1 as α approaches infinity.The residual update applies this matrix to the hybrid layer output, followed by learned weights and biases.Source: §6 · p. 6
7 Additional Information Introduced by Node-level Scattering Features
Theoretical examples show that scattering can preserve node distinctions that GCN filtering removes, and can encode graph geometry not present in constant input signals. These results concern alternating or two-coloring signals and cyclic structures connected by a bottleneck.
7 Additional Information Introduced by Node-level Scattering Features
- Band-pass filtering can retain periodic or harmonic regularities that low-pass smoothing does not retain.The section frames this as a difference in the regularity patterns considered by GCN and scattering channels.Source: §7 · pp. 6–7
- For a 2-periodic signal on a cycle, any finite cascade of GCN filters produces a constant signal, while a cascade of Ψ0 scattering filters preserves the 2-periodic pattern.This result is stated for cyclic graphs with 2n nodes and alternating values a and b, where a ≠ b.Source: §7 · p. 7
- On a constant-degree bipartite graph, GCN filtering makes a two-coloring signal constant, while Ψ0 scattering preserves a non-constant two-coloring, including under finite cascades.The signal assigns constant but distinct values to the two parts of the graph.Source: §7 · p. 7
- On two differently sized cycles joined by one bottleneck edge, the GCN response to a constant signal does not distinguish the cycles, whereas the Ψ3 scattering response does.The GCN response is nonconstant but has matching values across the cycles; the authors leave broader study of geometric information in wavelets to future work.Source: §7 · p. 7, Figure 3 · p. 7
8 Empirical Results
Across the reported training-size and training-time comparisons, Scattering GCN is generally more stable under sparse training and often reaches low validation error faster than leading alternatives. Its comparative performance and runtime patterns vary by dataset.
8 Empirical Results
- The evaluation compares Scattering GCN with GCN, GAT, partially absorbing walks, Chebyshev filters, belief propagation, graph scattering, and a node-feature-only SVM.Methods use original implementations and standard benchmark splits; Scattering GCN is tuned by grid search using the same cross-validation setup as competitors.Source: §8 · pp. 7–8, Table 2 · p. 8
- Scattering GCN generally shows greater stability as training data are reduced; on Citeseer it outperforms all other methods below 60% of the original training size.GAT leads at the original Citeseer training size but degrades rapidly below 60%; on Pubmed, reducing training size to 80% creates a significant gap between Scattering GCN and GAT.Source: §8 · p. 9, Figure 4 · p. 9
- Scattering GCN reaches low validation errors significantly faster than Partially Absorbing and GAT3, while its relative convergence rate varies across Pubmed and DBLP.On Pubmed its error decays at a rate similar to GCN and better than the other methods; on DBLP it takes longer than GCN to converge but has a double-digit performance lead over all methods.Source: §8 · p. 9, Figure 4 · p. 9
9 Conclusion
The paper concludes that adding scattering channels and residual convolutions to GCNs benefits semi-supervised node classification. It identifies adaptive scattering configurations and more intricate architectures as future directions.
9 Conclusion
- Scattering channels and residual convolutions each contribute benefits to the presented GCN architectures for semi-supervised node classification.The paper also expects their combination in more intricate architectures to provide new capabilities for pattern recognition and local information extraction.Source: §9 · p. 9
- The authors suggest attention mechanisms could tune scattering configurations at each node, rather than using the global graph-level configuration considered here.They leave exploration of this and other research avenues for future work.Source: §9 · p. 9
- GAT’s increased training runtime could reflect its larger number of weights and gradient computations over nodes and edges.The passage offers this as a possible explanation based on GAT’s original implementation.Source: §9 · p. 9
Broader Impact
The paper places graph node classification in the context of network analysis across several applied fields. It describes the work as computational research on graph processing and geometric deep learning, not expected by itself to raise ethical concerns or have adverse societal effects.
Broader Impact
- Graph node classification is relevant to network analysis in social studies, biochemistry, and epidemiology.Source: Broader Impact · p. 10
- The work addresses foundations of graph processing and geometric deep learning through computational research.Source: Broader Impact · p. 10
- The authors do not expect this work, by itself, to raise ethical concerns or have adverse societal effects.Source: Broader Impact · p. 10
Supplement
The supplement proves results about GCN and scattering responses on bipartite and cyclic graphs, illustrates their differing ability to distinguish graph structure, and records related work and experimental setup choices.
A Proofs and Illustrative Examples of Lemmas 1 and 2
- For a 2-coloring signal x, Ψ0x = (I_n − P)x retains the original two-coloring, shifting the original colors by the constant −(a+b)/2.For the cyclic graph case, the graph is bipartite with constant node degree β = 2.Source: A Proofs and Illustrative Examples of… · p. 13
B Geometric Information Encoded by Graph Wavelets (supp. info. Sec. 7)
- For the specified chain of cyclic substructures, GCN filter responses on a constant signal share values across every other cycle, so they do not distinguish the cycles.The construction connects consecutive cycles by bottleneck edges and separates the two bottleneck nodes in intermediate cycles by maximal shortest-path distance.Source: B Geometric Information Encoded by… · p. 14
- In the 14-node example of 6- and 8-node cycles joined by one edge, GCN responses on a constant signal do not distinguish the cycles, while Ψ3 responses are illustrated empirically.Source: B Geometric Information Encoded by… · p. 14
- The authors report similar empirical cycle distinctions for other cases covered by Lemma 3, but leave further theoretical study of this wavelet property to future work.Source: B Geometric Information Encoded by… · p. 15
C Further Discussion of Related Work
- Prior work studied GCN smoothing, attention, and multiscale graph methods, while geometric scattering work established stability properties and whole-graph classification results; this paper combines task-driven scattering with GCNs for node-level processing.Source: C Further Discussion of Related Work · p. 15
D Technical Details
- The reported architecture uses a residual convolution before classification and one or two hybrid layers, each with three GCN channels and two scattering channels.Cora, Citeseer, and Pubmed use one hybrid layer; DBLP uses two, while a single-layer DBLP model reaches 73.1% test accuracy versus 81.5% for two layers and 66.1% for GAT.Source: D Technical Details · pp. 15–16
- Evaluation uses shared train-validation-test splits across methods; DBLP uses a 5:1:1 split, and validation accuracy guides dataset-specific grid search.Citeseer, Cora, and Pubmed follow the settings in [4].Source: D Technical Details · p. 16
- For DBLP, hybrid-layer parameters are shared and tuning is less exhaustive than for the other datasets; the authors leave a more intensive study to future work.They note that observed architecture and performance differences could relate to DBLP’s distinct graph connectivity.Source: D Technical Details · p. 16
E Ablation Study
At α = 0.35, every tested scattering-scale configuration outperforms GAT and the other reported methods, while ablations show that performance depends on both tuned residual convolution and scattering channels. The study also finds that most scale choices outperform pure GCN, but its reported results are based on a limited grid search.
E Ablation Study
- Increasing α from zero to non-negligible values improves accuracy, but α = 1 adds enough smoothing to bring performance close to traditional GCN.The authors attribute the improvement to removal of high-frequency noise and note that α must be tuned.Source: E Ablation Study · p. 17
- Performance is relatively robust to scattering-scale choice, though purely second-order coefficients generally fare slightly worse than first-order or mixed coefficients.Most scale configurations outperform pure GCN when α is chosen appropriately, indicating added information from scattering channels.Source: E Ablation Study · p. 17
- At α = 0.35, all scale configurations outperform GAT (83%) and the other reported methods, with an average accuracy of 83.5% on Cora.The table reports classification accuracies for Cora at α = 0.35.Source: E Ablation Study · p. 17, Table 5 · p. 17
- The reported results come from a limited grid search; the authors leave exhaustive architecture and hyperparameter optimization for future work.They suggest the results may be a lower bound on Scattering GCN's improvement.Source: E Ablation Study · pp. 17–18
- Removing individual channels from the best Cora configuration (84.2% with all channels) shows that Ψ1 has a major impact, while A, A², and A³ also contribute important information.The reported Ψ1 ablation separates underperforming from outperforming GAT; scattering channels capture band-pass information.Source: E Ablation Study · p. 18, Table 8 · p. 18