research-article

Unifying and Improving Graph Convolutional Neural Networks with Wavelet Denoising Filters

Authors:

Feng XiaAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 177 - 187

https://doi.org/10.1145/3543507.3583253

Published: 30 April 2023 Publication History

Abstract

Graph convolutional neural network (GCN) is a powerful deep learning framework for network data. However, variants of graph neural architectures can lead to drastically different performance on different tasks. Model comparison calls for a unifying framework with interpretability and principled experimental procedures. Based on the theories from graph signal processing (GSP), we show that GCN’s capability is fundamentally limited by the uncertainty principle, and wavelets provide a controllable trade-off between local and global information. We adapt wavelet denoising filters to the graph domain, unifying popular variants of GCN under a common interpretable mathematical framework. Furthermore, we propose WaveThresh and WaveShrink which are novel GCN models based on proven denoising filters from the signal processing literature. Empirically, we evaluate our models and other popular GCNs under a more principled procedure and analyze how trade-offs between local and global graph signals can lead to better performance in different datasets.

References

[1]

James Atwood and Don Towsley. 2016. Diffusion-Convolutional Neural Networks. Advances in neural information processing systems (2016), 9.

[2]

Davide Boscaini, Jonathan Masci, Simone Melzi, Michael M Bronstein, Umberto Castellani, and Pierre Vandergheynst. 2015. Learning class-specific descriptors for deformable shapes using localized spectral convolutional networks. In Computer graphics forum, Vol. 34. Wiley Online Library, 13–23.

[3]

J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. 2013. Spectral Networks and Locally Connected Networks on Graphs. ArXiv e-prints (Dec. 2013).

[4]

Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. [n. d.]. Simple and Deep Graph Convolutional Networks. ([n. d.]), 11.

[5]

Mark Crovella and Eric Kolaczyk. 2003. Graph wavelets for spatial traffic analysis. In IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No. 03CH37428), Vol. 3. IEEE, 1848–1857.

[6]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. arXiv:1606.09375 [cs, stat] (Feb. 2016). http://arxiv.org/abs/1606.09375 arXiv:1606.09375.

[7]

Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. 2018. Learning Structural Node Embeddings Via Diffusion Wavelets. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (July 2018), 1320–1329. https://doi.org/10.1145/3219819.3220025 arXiv:1710.10321.

Digital Library

[8]

David L. Donoho, Iain M. Johnstone, Gérard Kerkyacharian, and Dominique Picard. 1995. Wavelet Shrinkage: Asymptopia¿Journal of the Royal Statistical Society. Series B: Methodological 57, 2 (1995), 301–337.

[9]

S. Fortunato. 2009. Community detection in graphs. Physics Reports (2009).

[10]

Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017).

[11]

W. L. Hamilton, R. Ying, and J. Leskovec. 2017. Representation Learning on Graphs: Methods and Applications. ArXiv e-prints (Sept. 2017).

[12]

David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. 2011. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis 30, 2 (2011), 129–150.

[13]

Renata Khasanova and Pascal Frossard. 2017. Graph-based isometry invariant representation learning. In International conference on machine learning. PMLR, 1847–1856.

[14]

Thomas N. Kipf and Max Welling. 2017. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2017).

[15]

H. J. Landau and H. O. Pollak. 1961. Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty II. Bell System Technical Journal 40, 1 (Jan. 1961), 65–84. https://doi.org/10.1002/j.1538-7305.1961.tb03977.x

[16]

Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. 2018. Cayleynets: Graph convolutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing 67, 1 (2018), 97–109.

Digital Library

[17]

Anat Levin, Assaf Zomet, Shmuel Peleg, and Yair Weiss. 2004. Seamless image stitching in the gradient domain. In European conference on computer vision. Springer, 377–389.

[18]

Shutao Li, Xudong Kang, and Jianwen Hu. 2013. Image fusion with guided filtering. IEEE Transactions on Image processing 22, 7 (2013), 2864–2875.

[19]

Meng Liu, Hongyang Gao, and Shuiwang Ji. 2020. Towards Deeper Graph Neural Networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (Aug. 2020), 338–348. https://doi.org/10.1145/3394486.3403076 arXiv:2007.09296.

Digital Library

[20]

Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M. Bronstein. 2017. Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).

[21]

Cristopher Moore and Stephan Mertens. 2011. The Nature of Computation. Oxford University Press, Inc., USA.

[22]

Mark Newman. 2010. Networks: An Introduction. Oxford University Press, Oxford. https://doi.org/10.1093/acprof:oso/9780199206650.001.0001

[23]

Nikhil S Rao, Robert D Nowak, Stephen J Wright, and Nick G Kingsbury. 2011. Convex approaches to model wavelet sparsity patterns. In 2011 18th IEEE International Conference on Image Processing. IEEE, 1917–1920.

[24]

Raif Rustamov and Leonidas J Guibas. 2013. Wavelets on graphs via deep learning. Advances in neural information processing systems 26 (2013).

[25]

A. Sandryhaila and J. M. F. Moura. 2013. Discrete Signal Processing on Graphs. IEEE Transactions on Signal Processing 61 (April 2013), 1644–1656. https://doi.org/10.1109/TSP.2013.2238935

Digital Library

[26]

F. Scarselli, M. Gori, Ah Chung Tsoi, M. Hagenbuchner, and G. Monfardini. 2009. The Graph Neural Network Model. IEEE Transactions on Neural Networks 20, 1 (Jan. 2009), 61–80. https://doi.org/10.1109/TNN.2008.2005605

Digital Library

[27]

David I. Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2012. Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Data Domains. CoRR abs/1211.0053 (2012). http://arxiv.org/abs/1211.0053

[28]

D. Slepian and H. O. Pollak. 1961. Prolate Spheroidal Wave Functions, Fourier Analysis and Uncertainty I. Bell System Technical Journal 40, 1 (Jan. 1961), 43–63. https://doi.org/10.1002/j.1538-7305.1961.tb03976.x

[29]

Aaron Smalter, Jun Huan, and Gerald Lushington. 2009. Graph wavelet alignment kernels for drug virtual screening. Journal of Bioinformatics and computational biology 7, 03 (2009), 473–497.

[30]

C. Taswell. 2000. The what, how, and why of wavelet shrinkage denoising. Computing in Science & Engineering 2, 3 (June 2000), 12–19. https://doi.org/10.1109/5992.841791

Digital Library

[31]

Nicolas Tremblay and Pierre Borgnat. 2014. Graph wavelets for multiscale community mining. IEEE Transactions on Signal Processing 62, 20 (2014), 5227–5239.

[32]

Mikhail Tsitsvero, Sergio Barbarossa, and Paolo Di Lorenzo. 2016. Signals on Graphs: Uncertainty Principle and Sampling. IEEE Transactions on Signal Processing 64, 18 (2016), 4845–4860. https://doi.org/10.1109/TSP.2016.2573748

Digital Library

[33]

Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903 (2017).

[34]

Hongwei Wang, Jialin Wang, Jia Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Wenjie Li, Xing Xie, and Minyi Guo. 2019. Learning graph representation with generative adversarial nets. IEEE Transactions on Knowledge and Data Engineering 33, 8 (2019), 3090–3103.

[35]

Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. 2021. Graph Learning: A Survey. IEEE Transactions on Artificial Intelligence 2, 2 (2021), 109–127. https://doi.org/10.1109/TAI.2021.3076021

[36]

Feng Xia, Lei Wang, Tao Tang, Xin Chen, Xiangjie Kong, Giles Oatley, and Irwin King. 2022. CenGCN: Centralized Convolutional Networks with Vertex Imbalance for Scale-Free Graphs. IEEE Transactions on Knowledge and Data Engineering (2022). https://doi.org/10.1109/TKDE.2022.3149888

Digital Library

[37]

Bingbing Xu, Huawei Shen, Qi Cao, Yunqi Qiu, and Xueqi Cheng. 2019. Graph Wavelet Neural Network. arXiv:1904.07785 [cs, stat] (April 2019). http://arxiv.org/abs/1904.07785 arXiv:1904.07785.

[38]

Xiaoran Yan, Brian M Sadler, Robert J Drost, L Yu Paul, and Kristina Lerman. 2017. Graph filters and the Z-Laplacian. IEEE Journal of Selected Topics in Signal Processing 11, 6 (2017), 774–784.

Cited By

Wan LHan HSun LZhang ZNing ZYan XXia FBaeza-Yates RBonchi F(2024)Flexible Graph Neural Diffusion with Latent Class Representation LearningProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671860(2936-2947)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671860

Index Terms

Unifying and Improving Graph Convolutional Neural Networks with Wavelet Denoising Filters
1. Computing methodologies
  1. Machine learning
    1. Machine learning approaches
      1. Learning latent representations
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Research on improved wavelet convolutional wavelet neural networks
Abstract
Convolutional neural network (CNN) is recognized as state of the art of deep learning algorithm, which has a good ability on the image classification and recognition. The problems of CNN are as follows: the precision, accuracy and efficiency of ...
Convolutional neural networks for wavelet domain super resolution

Proposed a super resolution method with higher reconstruction accuracy than before.Cast super resolution as a problem of estimating sparse wavelet detail coefficients.Estimated sparse wavelet coefficients using a convolutional neural network (CNN)...
Edge-preserving image denoising using a deep convolutional neural network
Highlights
- This paper makes use of a deep CNN for image denoising.
- The network is trained ...
Abstract
This paper introduces a novel denoising approach making use of a deep convolutional neural network to preserve image edges. The network is trained by using the edge map obtained from the well-known Canny algorithm and aims at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)134
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wan LHan HSun LZhang ZNing ZYan XXia FBaeza-Yates RBonchi F(2024)Flexible Graph Neural Diffusion with Latent Class Representation LearningProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671860(2936-2947)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671860

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents