Timezone: »
Graph neural networks have been extensively studied for learning with inter-connected data. Despite this, recent evidence has revealed GNNs' deficiencies related to over-squashing, heterophily, handling long-range dependencies, edge incompleteness and particularly, the absence of graphs altogether. While a plausible solution is to learn new adaptive topology for message passing, issues concerning quadratic complexity hinder simultaneous guarantees for scalability and precision in large networks. In this paper, we introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes, as an important building block for a new class of Transformer networks for node classification on large graphs, dubbed as NodeFormer. Specifically, the efficient computation is enabled by a kernerlized Gumbel-Softmax operator that reduces the algorithmic complexity to linearity w.r.t. node numbers for learning latent graph structures from large, potentially fully-connected graphs in a differentiable manner. We also provide accompanying theory as justification for our design. Extensive experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs (with up to 2M nodes) and graph-enhanced applications (e.g., image classification) where input graphs are missing. The codes are available at https://github.com/qitianwu/NodeFormer.
Author Information
Qitian Wu (Shanghai Jiao Tong University)
Wentao Zhao (Shanghai Jiao Tong University)
Zenan Li (SJTU)
David P Wipf (AWS)
Junchi Yan (Shanghai Jiao Tong University)
Related Events (a corresponding poster, oral, or spotlight)
-
2022 Poster: NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification »
Thu. Dec 1st through Fri the 2nd Room Hall J #121
More from the Same Authors
-
2021 : A Closer Look at Distribution Shifts and Out-of-Distribution Generalization on Graphs »
Mucong Ding · Kezhi Kong · Jiuhai Chen · John Kirchenbauer · Micah Goldblum · David P Wipf · Furong Huang · Tom Goldstein -
2022 Poster: Learning Enhanced Representation for Tabular Data via Neighborhood Propagation »
Kounianhua Du · Weinan Zhang · Ruiwen Zhou · Yangkun Wang · Xilong Zhao · Jiarui Jin · Quan Gan · Zheng Zhang · David P Wipf -
2022 Poster: Improving Generative Adversarial Networks via Adversarial Learning in Latent Space »
Yang Li · Yichuan Mo · Liangliang Shi · Junchi Yan -
2022 Poster: ZARTS: On Zero-order Optimization for Neural Architecture Search »
Xiaoxing Wang · Wenxuan Guo · Jianlin Su · Xiaokang Yang · Junchi Yan -
2022 Poster: Learning Substructure Invariance for Out-of-Distribution Molecular Representations »
Nianzu Yang · Kaipeng Zeng · Qitian Wu · Xiaosong Jia · Junchi Yan -
2023 Poster: Going Beyond Linear Mode Connectivity: The Layerwise Linear Feature Connectivity »
Zhanpeng Zhou · Yongyi Yang · Xiaojiang Yang · Junchi Yan · Wei Hu -
2023 Poster: H2RBox-v2: Incorporating Symmetry for Boosting Horizontal Box Supervised Oriented Object Detection »
Yi Yu · Xue Yang · Qingyun Li · Yue Zhou · Feipeng Da · Junchi Yan -
2023 Poster: Relative Entropic Optimal Transport: a (Prior-aware) Matching Perspective to (Unbalanced) Classification »
Liangliang Shi · Haoyu Zhen · Gu Zhang · Junchi Yan -
2023 Poster: Unleashing the Power of Graph Data Augmentation on Covariate Shift »
Yongduo Sui · Qitian Wu · Jiancan Wu · Qing Cui · Longfei Li · Jun Zhou · Xiang Wang · Xiangnan He -
2023 Poster: HubRouter: Learning Global Routing via Hub Generation and Pin-hub Connection »
Xingbo Du · Chonghua Wang · Ruizhe Zhong · Junchi Yan -
2023 Poster: Simplifying and Empowering Transformers for Large-Graph Representations »
Qitian Wu · Wentao Zhao · Chenxiao Yang · Hengrui Zhang · Fan Nie · Haitian Jiang · Yatao Bian · Junchi Yan -
2023 Poster: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization »
Yang Li · Jinpei Guo · Runzhong Wang · Junchi Yan -
2023 Poster: OpenLane-V2: A Topology Reasoning Benchmark for Scene Understanding in Autonomous Driving »
Huijie Wang · Tianyu Li · Yang Li · Li Chen · Chonghao Sima · Zhenbo Liu · Bangjun Wang · Peijin Jia · Yuting Wang · Shengyin Jiang · Feng Wen · Hang Xu · Ping Luo · Junchi Yan · Wei Zhang · Hongyang Li -
2022 Spotlight: Lightning Talks 5B-3 »
Yanze Wu · Jie Xiao · Nianzu Yang · Jieyi Bi · Jian Yao · Yiting Chen · Qizhou Wang · Yangru Huang · Yongqiang Chen · Peixi Peng · Yuxin Hong · Xintao Wang · Feng Liu · Yining Ma · Qibing Ren · Xueyang Fu · Yonggang Zhang · Kaipeng Zeng · Jiahai Wang · GEN LI · Yonggang Zhang · Qitian Wu · Yifan Zhao · Chiyu Wang · Junchi Yan · Feng Wu · Yatao Bian · Xiaosong Jia · Ying Shan · Zhiguang Cao · Zheng-Jun Zha · Guangyao Chen · Tianjun Xiao · Han Yang · Jing Zhang · Jinbiao Chen · MA Kaili · Yonghong Tian · Junchi Yan · Chen Gong · Tong He · Binghui Xie · Yuan Sun · Francesco Locatello · Tongliang Liu · Yeow Meng Chee · David P Wipf · Tongliang Liu · Bo Han · Bo Han · Yanwei Fu · James Cheng · Zheng Zhang -
2022 Spotlight: Lightning Talks 5A-2 »
Qiang LI · Zhiwei Xu · Jia-Qi Yang · Thai Hung Le · Haoxuan Qu · Yang Li · Artyom Sorokin · Peirong Zhang · Mira Finkelstein · Nitsan levy · Chung-Yiu Yau · dapeng li · Thommen Karimpanal George · De-Chuan Zhan · Nazar Buzun · Jiajia Jiang · Li Xu · Yichuan Mo · Yujun Cai · Yuliang Liu · Leonid Pugachev · Bin Zhang · Lucy Liu · Hoi-To Wai · Liangliang Shi · Majid Abdolshah · Yoav Kolumbus · Lin Geng Foo · Junchi Yan · Mikhail Burtsev · Lianwen Jin · Yuan Zhan · Dung Nguyen · David Parkes · Yunpeng Baiia · Jun Liu · Kien Do · Guoliang Fan · Jeffrey S Rosenschein · Sunil Gupta · Sarah Keren · Svetha Venkatesh -
2022 Spotlight: Improving Generative Adversarial Networks via Adversarial Learning in Latent Space »
Yang Li · Yichuan Mo · Liangliang Shi · Junchi Yan -
2022 Spotlight: Self-supervised Amodal Video Object Segmentation »
Jian Yao · Yuxin Hong · Chiyu Wang · Tianjun Xiao · Tong He · Francesco Locatello · David P Wipf · Yanwei Fu · Zheng Zhang -
2022 Spotlight: Learning Substructure Invariance for Out-of-Distribution Molecular Representations »
Nianzu Yang · Kaipeng Zeng · Qitian Wu · Xiaosong Jia · Junchi Yan -
2022 Spotlight: Rethinking and Improving Robustness of Convolutional Neural Networks: a Shapley Value-based Approach in Frequency Domain »
Yiting Chen · Qibing Ren · Junchi Yan -
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 -
2022 Poster: Geometric Knowledge Distillation: Topology Compression for Graph Neural Networks »
Chenxiao Yang · Qitian Wu · Junchi Yan -
2022 Poster: Rethinking and Improving Robustness of Convolutional Neural Networks: a Shapley Value-based Approach in Frequency Domain »
Yiting Chen · Qibing Ren · Junchi Yan -
2022 Poster: Transformers from an Optimization Perspective »
Yongyi Yang · zengfeng Huang · David P Wipf -
2022 Poster: GraphDE: A Generative Framework for Debiased Learning and Out-of-Distribution Detection on Graphs »
Zenan Li · Qitian Wu · Fan Nie · Junchi Yan -
2022 Poster: The Policy-gradient Placement and Generative Routing Neural Networks for Chip Design »
Ruoyu Cheng · Xianglong Lyu · Yang Li · Junjie Ye · Jianye Hao · Junchi Yan -
2022 Poster: Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks »
Hongjoon Ahn · Yongyi Yang · Quan Gan · Taesup Moon · David P Wipf -
2022 Poster: Towards Out-of-Distribution Sequential Event Prediction: A Causal Treatment »
Chenxiao Yang · Qitian Wu · Qingsong Wen · Zhiqiang Zhou · Liang Sun · Junchi Yan -
2022 Poster: Self-supervised Amodal Video Object Segmentation »
Jian Yao · Yuxin Hong · Chiyu Wang · Tianjun Xiao · Tong He · Francesco Locatello · David P Wipf · Yanwei Fu · Zheng Zhang -
2022 Poster: Learning Manifold Dimensions with Conditional Variational Autoencoders »
Yijia Zheng · Tong He · Yixuan Qiu · David P Wipf -
2022 Poster: Trajectory-guided Control Prediction for End-to-end Autonomous Driving: A Simple yet Strong Baseline »
Penghao Wu · Xiaosong Jia · Li Chen · Junchi Yan · Hongyang Li · Yu Qiao -
2022 Poster: GraphQNTK: Quantum Neural Tangent Kernel for Graph Data »
Yehui Tang · Junchi Yan -
2021 : A Closer Look at Distribution Shifts and Out-of-Distribution Generalization on Graphs »
Mucong Ding · Kezhi Kong · Jiuhai Chen · John Kirchenbauer · Micah Goldblum · David P Wipf · Furong Huang · Tom Goldstein -
2021 Poster: From Canonical Correlation Analysis to Self-supervised Graph Neural Networks »
Hengrui Zhang · Qitian Wu · Junchi Yan · David Wipf · Philip S Yu -
2021 Poster: Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach »
Qitian Wu · Chenxiao Yang · Junchi Yan -
2021 Poster: Bridging Explicit and Implicit Deep Generative Models via Neural Stein Estimators »
Qitian Wu · Rui Gao · Hongyuan Zha -
2020 Poster: Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning »
Runzhong Wang · Junchi Yan · Xiaokang Yang -
2020 Poster: Further Analysis of Outlier Detection with Deep Generative Models »
Ziyu Wang · Bin Dai · David P Wipf · Jun Zhu -
2020 Poster: The Diversified Ensemble Neural Network »
Shaofeng Zhang · Meng Liu · Junchi Yan -
2020 Poster: Adversarial Learning for Robust Deep Clustering »
Xu Yang · Cheng Deng · Kun Wei · Junchi Yan · Wei Liu -
2019 Poster: Learning Latent Process from High-Dimensional Event Sequences via Efficient Sampling »
Qitian Wu · Zixuan Zhang · Xiaofeng Gao · Junchi Yan · Guihai Chen -
2018 Poster: Generalizing Graph Matching beyond Quadratic Assignment Model »
Tianshu Yu · Junchi Yan · Yilin Wang · Wei Liu · baoxin Li -
2012 Poster: Dual-Space Analysis of the Sparse Linear Model »
David P Wipf -
2011 Poster: Sparse Estimation with Structured Dictionaries »
David P Wipf -
2011 Spotlight: Sparse Estimation with Structured Dictionaries »
David P Wipf -
2009 Poster: Sparse Estimation Using General Likelihoods and Non-Factorial Priors »
David P Wipf · Sri Nagarajan -
2008 Poster: Estimating the Location and Orientation of Complex, Correlated Neural Activity using MEG »
David P Wipf · Julia Owen · Hagai Attias · Kensuke Sekihara · Sri Nagarajan -
2008 Spotlight: Estimating the Location and Orientation of Complex, Correlated Neural Activity using MEG »
David P Wipf · Julia Owen · Hagai Attias · Kensuke Sekihara · Sri Nagarajan -
2007 Poster: A New View of Automatic Relevance Determination »
David P Wipf · Srikantan Nagarajan -
2006 Poster: Analysis of Empirical Bayesian Methods for Neuroelectromagnetic Source Localization »
David P Wipf · Rey R Ramirez · Jason A Palmer · Scott Makeig · Bhaskar Rao -
2006 Spotlight: Analysis of Empirical Bayesian Methods for Neuroelectromagnetic Source Localization »
David P Wipf · Rey R Ramirez · Jason A Palmer · Scott Makeig · Bhaskar Rao