Timezone: »
Designing spectral convolutional networks is a challenging problem in graph learning. ChebNet, one of the early attempts, approximates the spectral graph convolutions using Chebyshev polynomials. GCN simplifies ChebNet by utilizing only the first two Chebyshev polynomials while still outperforming it on real-world datasets. GPR-GNN and BernNet demonstrate that the Monomial and Bernstein bases also outperform the Chebyshev basis in terms of learning the spectral graph convolutions. Such conclusions are counter-intuitive in the field of approximation theory, where it is established that the Chebyshev polynomial achieves the optimum convergent rate for approximating a function. In this paper, we revisit the problem of approximating the spectral graph convolutions with Chebyshev polynomials. We show that ChebNet's inferior performance is primarily due to illegal coefficients learnt by ChebNet approximating analytic filter functions, which leads to over-fitting. We then propose ChebNetII, a new GNN model based on Chebyshev interpolation, which enhances the original Chebyshev polynomial approximation while reducing the Runge phenomenon. We conducted an extensive experimental study to demonstrate that ChebNetII can learn arbitrary graph convolutions and achieve superior performance in both full- and semi-supervised node classification tasks. Most notably, we scale ChebNetII to a billion graph ogbn-papers100M, showing that spectral-based GNNs have superior performance. Our code is available at https://github.com/ivam-he/ChebNetII.
Author Information
Mingguo He (Renmin University of China)
Zhewei Wei (Renmin University of China)
Ji-Rong Wen (Renmin University of China)
More from the Same Authors
-
2022 Poster: Log-Polar Space Convolution Layers »
Bing Su · Ji-Rong Wen -
2022 Poster: EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks »
Runlin Lei · Zhen Wang · Yaliang Li · Bolin Ding · Zhewei Wei -
2022 Poster: Debiased, Longitudinal and Coordinated Drug Recommendation through Multi-Visit Clinic Records »
Hongda Sun · Shufang Xie · Shuqi Li · Yuhan Chen · Ji-Rong Wen · Rui Yan -
2023 Poster: Reward Imputation with Sketching for Contextual Batched Bandits »
Xiao Zhang · Ninglu Shao · Zihua Si · Jun Xu · Wenhan Wang · Hanjing Su · Ji-Rong Wen -
2023 Poster: REASONER: An Explainable Recommendation Dataset with Comprehensive Labeling Ground Truths »
Xu Chen · Jingsen Zhang · Lei Wang · Quanyu Dai · Zhenhua Dong · Ruiming Tang · Rui Zhang · Li Chen · Xin Zhao · Ji-Rong Wen -
2023 Poster: Evaluating and Improving Tool-Augmented Computation-Intensive Math Reasoning »
Beichen Zhang · Kun Zhou · Xilin Wei · Xin Zhao · Jing Sha · Shijin Wang · Ji-Rong Wen -
2022 Panel: Panel 4B-1: Convolutional Neural Networks… & Uncovering the Structural… »
Ruijia Wang · Mingguo He -
2022 Spotlight: Lightning Talks 2B-2 »
Chenjian Gao · Rui Ding · Lingzhi LI · Fan Yang · Xingting Yao · Jianxin Li · Bing Su · Zhen Shen · Tongda Xu · Shuai Zhang · Ji-Rong Wen · Lin Guo · Fanrong Li · Kehua Guo · Zhongshu Wang · Zhi Chen · Xiangyuan Zhu · Zitao Mo · Dailan He · Hui Xiong · Yan Wang · Zheng Wu · Wenbing Tao · Jian Cheng · Haoyi Zhou · Li Shen · Ping Tan · Liwei Wang · Hongwei Qin -
2022 Spotlight: Log-Polar Space Convolution Layers »
Bing Su · Ji-Rong Wen -
2022 Spotlight: EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks »
Runlin Lei · Zhen Wang · Yaliang Li · Bolin Ding · Zhewei Wei -
2022 Spotlight: Lightning Talks 1B-1 »
Qitian Wu · Runlin Lei · Rongqin Chen · Luca Pinchetti · Yangze Zhou · Abhinav Kumar · Hans Hao-Hsun Hsu · Wentao Zhao · Chenhao Tan · Zhen Wang · Shenghui Zhang · Yuesong Shen · Tommaso Salvatori · Gitta Kutyniok · Zenan Li · Amit Sharma · Leong Hou U · Yordan Yordanov · Christian Tomani · Bruno Ribeiro · Yaliang Li · David P Wipf · Daniel Cremers · Bolin Ding · Beren Millidge · Ye Li · Yuhang Song · Junchi Yan · Zhewei Wei · Thomas Lukasiewicz -
2021 Poster: BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation »
Mingguo He · Zhewei Wei · zengfeng Huang · Hongteng Xu -
2021 Poster: Compressed Video Contrastive Learning »
Yuqi Huo · Mingyu Ding · Haoyu Lu · Nanyi Fei · Zhiwu Lu · Ji-Rong Wen · Ping Luo -
2020 Poster: Scalable Graph Neural Networks via Bidirectional Propagation »
Ming Chen · Zhewei Wei · Bolin Ding · Yaliang Li · Ye Yuan · Xiaoyong Du · Ji-Rong Wen -
2018 Poster: Domain-Invariant Projection Learning for Zero-Shot Recognition »
An Zhao · Mingyu Ding · Jiechao Guan · Zhiwu Lu · Tao Xiang · Ji-Rong Wen