Source-linked AI summary
Beyond Low-frequency Information in Graph Convolutional Networks
Deyu Bo, Xiao Wang, Chuan Shi, Huawei Shen
TL;DR
The paper asks whether low-frequency information alone is sufficient for GNN node representation learning across different network types. It introduces FAGCN, which adaptively integrates low- and high-frequency signals, and reports that both signals are useful, especially high-frequency signals in disassortative networks. Theoretical analysis and experiments support FAGCN’s broader expressive power and performance advantages.
Problem
The paper examines whether low-frequency information is sufficient, given that networks differ in assortativity and tasks may depend on raw, low-frequency, or high-frequency signals.
Method
FAGCN uses enhanced low- and high-pass filters with a self-gating mechanism to adaptively integrate low-frequency signals, high-frequency signals, and raw features without knowing network assortativity.
Results
Both low- and high-frequency signals help learn node representations; high-frequency signals are useful for disassortative networks, and FAGCN shows advantages over state-of-the-art methods.
Takeaways & Limitations
Effective GNN representations need not rely on low-frequency information alone, because adaptive frequency integration can address different network types.
Takeaways & Limitations
The paper identifies using additional frequency components, such as intermediate-frequency signals, as an important direction for future work.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) have been proven to be effective in various network-related tasks. Most existing GNNs usually exploit the low-frequency signals of node features, which gives rise to one fundamental question: is the low-frequency information all we need in the real world applications? In this paper, we first present an experimental investigation assessing the roles of low-frequency and high-frequency signals, where the results clearly show that exploring low-frequency signal only is distant from learning an effective node representation in different scenarios. How can we adaptively learn more information beyond low-frequency information in GNNs? A well-informed answer can help GNNs enhance the adaptability. We tackle this challenge and propose a novel Frequency Adaptation Graph Convolutional Networks (FAGCN) with a self-gating mechanism, which can adaptively integrate different signals in the process of message passing. For a deeper understanding, we theoretically analyze the roles of low-frequency signals and high-frequency signals on learning node representations, which further explains why FAGCN can perform well on different types of networks. Extensive experiments on six real-world networks validate that FAGCN not only alleviates the over-smoothing problem, but also has advantages over the state-of-the-arts.
1 Introduction
Existing GNNs primarily exploit low-frequency information, but its usefulness depends on network structure. FAGCN adaptively combines low- and high-frequency signals, with theory and experiments supporting broader expressiveness and improved performance.
- GNN neighbor aggregation acts as a low-pass filter, retaining common node-feature information while potentially making connected-node representations similar.
- High-frequency signals are useful for disassortative networks, where low-frequency information is not always optimal for learning node representations.
- The paper frames signal selection as difficult because networks vary in assortativity and traditional filters cannot simultaneously extract different frequency components.
- FAGCN uses enhanced filters and a self-gating mechanism to integrate low-frequency signals, high-frequency signals, and raw features.
- FAGCN adaptively changes the proportion of low- and high-frequency signals without knowing the network type.
- Theoretical analysis gives FAGCN greater expressive power than most existing GNNs and shows that it can alleviate over-smoothing.
2 An Experimental Investigation
Experiments on synthetic networks vary inter-connection probability to examine low- and high-frequency signals. Low-frequency performance declines as disassortativity increases, while FAGCN combines both signal types and performs best across the tested networks.
- Increasing inter-connection probability q decreases low-frequency accuracy and gradually increases high-frequency accuracy.
- Both low-frequency and high-frequency signals help learn node representations, but their effectiveness changes with network disassortativity.
- Existing GNNs lose discrimination as q increases because they aggregate low-frequency neighbor signals and make node representations similar.
- A single filter cannot achieve optimal results in all tested cases as the network becomes more disassortative.
- FAGCN aggregates low-frequency signals from same-class neighbors and high-frequency signals from different-class neighbors, achieving the best performance on every synthetic network.
3 Our Proposed Model: FAGCN
FAGCN separates low- and high-frequency signals, then adaptively combines them with raw features through self-gated message passing. Its architecture applies an initial nonlinear transform, normalized neighbor aggregation, and a final classifier with near-linear layer complexity.
- 3.1 Separation: FAGCN defines enhanced low-pass and high-pass filters to separate frequency signals from node features.The filters are expressed through the normalized Laplacian and graph convolution operations.
- 3.1 Separation: The second-order low-pass kernel amplifies low-frequency signals, while the high-pass filter provides greater value for high-frequency signals.For the low-pass kernel, gθ(λi)=(ε+1−λi)^2; the paper explicitly characterizes FH as an enhanced high-pass filter.
- 3.2 Aggregation: FAGCN avoids choosing one frequency in advance by learning low- and high-frequency proportions from node and neighbor features.The shared self-gating mechanism uses concatenated features and tanh-bounded coefficients, computed over first-order neighbors.
- 3.2 Aggregation: The aggregation combines low- and high-frequency neighbor signals, while near-zero gating coefficients limit neighbor contributions and preserve raw features.Degree normalization prevents aggregated representations from becoming too large.
- 3.3 The Whole Architecture of FAGCN: FAGCN first applies an MLP to raw features, propagates representations through the adaptive aggregation rule, and maps the final hidden representation to class outputs.The weight matrices transform input features to hidden dimensions and hidden representations to K classes.
- 3.3 The Whole Architecture of FAGCN: A single FAGCN layer has complexity O((N + |E|) × F′), approximately linear in the number of nodes and edges.The stated complexity concerns one layer and uses F′ for the hidden-layer dimension.
4 Theoretical Analysis
FAGCN extends existing graph convolutions by allowing signed, adaptive aggregation of low- and high-frequency information. Theoretical analysis shows that low-pass filtering homogenizes connected-node representations, whereas high-pass filtering makes them more discriminative.
- FAGCN reduces to GCN when αG_ij=1 and to GAT when αG_ij is normalized with softmax.
- Unlike GCN and GAT, FAGCN can learn positive or negative aggregation coefficients to combine low- and high-frequency signals.
- Low-pass filtering makes connected-node representations more similar, while high-pass filtering makes them more discriminative.The induced distances satisfy DH > D > DL.
- FAGCN can flexibly shorten or enlarge distances between node representations, whereas most existing GNNs cannot.
- Most existing GNNs such as GCN only make node representations more similar.For GCN, the analyzed representation distance is smaller than the original distance under approximately equal node degrees.
5 Experiments
Experiments across assortative and disassortative networks show that FAGCN adapts to different signal patterns, performs strongly across datasets and label rates, and alleviates over-smoothing as depth increases.
- Classification on Different Types of Networks: FAGCN exceeds benchmarks on most assortative networks, validating enhanced low-pass filtering for these datasets.
- Classification on Different Types of Networks: On disassortative networks, FAGCN performs best in most datasets and label rates, while GCN and GAT perform worse than other methods.APPNP and ChebNet perform better than GCN and GAT by preserving raw or high-frequency information to some extent.
- Alleviating Over-smoothing Problem: As model depth increases, GCN performance drops rapidly after two layers, whereas FAGCN remains stable and significantly higher across network types.Negative weights and injecting raw features at each layer help prevent node representations from becoming indistinguishable.
- Visualization of Edge Coefficients: FAGCN assigns mostly positive edge coefficients on highly assortative networks, indicating that low-pass filtering dominates classification there.
- Visualization of Edge Coefficients: On networks with small assortativity, many inter-edges receive negative coefficients, indicating an important role for high-frequency signals in node classification.
- Visualization of Edge Coefficients: On Actor, edge coefficients concentrate near zero, while raw features dominate classification because the network's assortativity is quite small.
- Details of Wikipedia Networks: After relabeling Chameleon and Squirrel by traffic categories, FAGCN performs best on all four Wikipedia datasets.The relabeling addresses an anomalous comparison in which GCN outperformed MLP despite MLP using raw features.
6 Related Work
Related work divides graph neural networks into spectral and spatial approaches. Spectral methods offer signal-processing interpretability, while spatial methods emphasize flexible aggregation and scalability.
- Spectral Graph Neural Networks: Spectral GNNs define convolution kernels in the spectral domain using graph signal processing.
- Spectral Graph Neural Networks: ChebNet approximates convolution kernels with Laplacian polynomials, and GCN is its first-order approximation with self-loops.
- Spectral Graph Neural Networks: GraphHeat uses a heat-kernel low-pass filter, while GWNN replaces eigenvectors with wavelet bases to improve efficiency.
- Spectral and Spatial Graph Neural Networks: Spectral methods are generally interpretable for graph signal processing but lack generalization, whereas spatial methods are more flexible and scalable but less interpretable.
- Spatial Graph Neural Networks: Spatial GNNs design aggregation functions, including permutation-invariant aggregation, attention-based neighbor weighting, personalized PageRank, and structural similarity.
- Spatial Graph Neural Networks: FAGCN is presented as a spatial method that retains interpretability while combining advantages associated with spectral and spatial approaches.
7 Conclusion
The paper shows that both low- and high-frequency signals help learn node representations and introduces a frequency-adaptive graph convolutional network to combine them. It identifies broader frequency coverage, including intermediate signals, as future work.
- Both low-frequency and high-frequency signals are helpful for learning node representations.
- FAGCN adaptively combines low-frequency and high-frequency signals.
- The model’s expressive power is greater than that of most existing GNNs.
- Future work could incorporate signals with additional frequencies, such as intermediate-frequency signals.