Leveraging Frequency Information in Graph Convolutional Networks

Beyond Low-frequency Information in Graph Convolutional Networks Deyu Bo1, Xiao Wang1, Chuan Shi1, Huawei Shen2 1Beijing University of Posts and Telecommunications 2CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences

CONTENTS 1 Background Method 2 Experiments 3 Conclusions 4

CONTENTS 1 Background Method 2 Experiments 3 Conclusions 4

1Background Frequency in image Information is conveyed at different frequencies where higher frequencies are encoded with details and lower frequencies are encoded with global structures1 Raw image Lower frequency Higher frequency [1] Chen Y, Fan H, Xu B, et al. Drop an octave: Reducing spatial redundancy in convolutional neural networks with octave convolution. CVPR 2019

1Background Frequency in graph Spectral graph theory has been leveraged as a tool to define frequency spectra and expansion bases for graph Fourier transforms2 ? ?? = ? ? ? ? ? ?0 ?1 ?50 Lowest frequency Lower frequency Higher frequency [2] Shuman, David I., et al. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine 30.3 (2013): 83-98.

1Background Frequency in GNNs Most existing GNNs usually exploit low-frequency signals3, e.g., GCN and GAT GCN GAT Is the low-frequency information all we need? [3] Anonymous. Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective. ICLR 2021 under review

1Background An Experimental Investigation Low-frequency signals perform better on assortative graphs High-frequency signals perform better on disassortative graphs Assortative graph Disassortative graph Only use low-frequency information is not always optimal for the complex networks!

1Background Challenges How to use signals of different frequencies in GNNs? How to make GNNs suitable for different type of networks? Intuition of FAGCN High Low Low Low Low Low Frequency Adaptation Graph Convolutional Networks (FAGCN) Existing GNNs

CONTENTS 1 Background Method 2 Experiments 3 Conclusions 4

2 FAGCN Compared with previous methods low high Avg/Cat Avg/Cat low high Low-pass Filter High-pass Filter Signal Combination Ratio of low-frequency information

2 FAGCN Problems of signal combination Matrix multiplication Transductive Spatial vision of FAGCN Coefficients of edges Learning the coefficients of edges is equivalent to learn the ratio of low- and high- frequency signals

2 FAGCN Expressive power of FAGCN Raw feature Low-frequency signal High-frequency signal Connection with CNNs In CNNs, we actually do not constrain the weight of convolutional kernel to be positive. How about GNNs?

CONTENTS 1 Background Method 2 Experiments 3 Conclusions 4

3Experiments Assortative graphs Node classification Disassortative graphs

3Experiments Clustering Performance Alleviate over-smoothing ? Visualization of ???

CONTENTS 1 Background Method 2 Experiments 3 Conclusions 4

4Conclusions We study the roles of both low-frequency and high-frequency signals in GNNs and verify that high-frequency signals are useful for disassortative networks. We propose a novel graph convolutional networks FAGCN, which can adaptively change the proportion of low-frequency and high-frequency signals without knowing the types of networks. We theoretically prove that the expressive power of FAGCN is greater than other GNNs. Moreover, our proposed FAGCN is able to alleviate the over-smoothing problem. Extensive experiments on six real-world networks validate that FAGCN has advantages over state-of-the-arts.

Thank you ! Q&A