NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification
Nov 28, 2022
Speakers
Wentao Zhao
Speaker · 0 followers
David Wipf
Speaker · 0 followers
Junchi Yan
Speaker · 0 followers
About
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 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 layer-wise signals between arbitrary nodes. Specifically, the efficient computation per layer is enabled by a kernerlized Gumbel-Softmax operator that reduces the algorithmic complexity to linearity w.r.t. node numbers for learning latent 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 different sizes of graphs (1K 1M) and graph-enhanced applications where input topology is missing.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 topology for message passing, issues concerning quadratic complexity hinder simultaneous guarantees for scalability and precision in large networks. In this…
Organizer
NeurIPS 2022
Account · 961 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Approximate Bayesian Computation for Panel Data using Signature Maximum Mean Discrepancies
Watch later
Joel Dyer, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
HAPNEST: An efficient tool for generating large-scale genetics datasets from limited training data
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Provable Benefit of Multitask Representation Learning in Reinforcement Learning
Watch later
Yuan Cheng, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Geoclidean: Few-Shot Generalization in Euclidean Geometry
Watch later
Joy Hsu, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Generative Status Estimation and Information Decoupling for Image Rain Removal
Watch later
Di Lin, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
4l4SCience and Al4Social Good Collaborations
Watch later
Total of 1 viewers voted for saving the presentation to eternal vault which is 0.1%