近日NeurIPS 2022录取结果公布，共提交了10411篇论文，近2665篇论文接受，接受率在25.6%。本文对图神经网络（Graph Neural Networks）相关的论文进行了汇总与整理，涵盖表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统、异质/动态/有向图、以及各种下游任务。

NeurIPS 2022 Accepted Papers(nips.cc)

1. GNN

探究模型表达能力

• How Powerful are K-hop Message Passing Graph Neural Networks
• Ordered Subgraph Aggregation Networks
• Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited
• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
• Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective
• Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
• A Practical, Progressively-Expressive GNN

泛化性分析

• Generalization Analysis of Message Passing Neural Networks on Large Random Graphs

减少Message Passing中的冗余计算

• Redundancy-Free Message Passing for Graph Neural Networks

Scalability

• Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity

捕获长距离依赖

• Capturing Graphs with Hypo-Elliptic Diffusions
• MGNNI: Multiscale Graph Neural Networks with Implicit Layers

强化节点表征（通过引入结构，距离特征，etc）

• Geodesic Graph Neural Network for Efficient Graph Representation Learning
• Template based Graph Neural Network with Optimal Transport Distances
• Pseudo-Riemannian Graph Convolutional Networks
• Neural Approximation of Extended Persistent Homology on Graphs
• GraphQNTK: the Quantum Neural Tangent Kernel for Graph Data

模型结构设计

• Graph Scattering beyond Wavelet Shackles
• Equivariant Graph Hierarchy-based Neural Networks

优化梯度流向

• Old can be Gold: Better Gradient Flow can make Vanilla-GCNs Great Again

Library

• Graphein - a Python Library for Geometric Deep Learning and Network Analysis on Biomolecular Structures and Interaction Networks

2. Graph Transformer

• Recipe for a General, Powerful, Scalable Graph Transformer
• Hierarchical Graph Transformer with Adaptive Node Sampling
• Pure Transformers are Powerful Graph Learners
• Periodic Graph Transformers for Crystal Material Property Prediction

3. 过平滑

• Not too little, not too much: a theoretical analysis of graph (over)smoothing
• Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs

4. 图对比学习，图自监督

• Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination
• Uncovering the Structural Fairness in Graph Contrastive Learning
• Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum
• Decoupled Self-supervised Learning for Non-Homophilous Graphs
• Understanding Self-Supervised Graph Representation Learning from a Data-Centric Perspective
• Co-Modality Imbalanced Graph Contrastive Learning
• Graph Self-supervised Learning with Accurate Discrepancy Learning
• Contrastive Graph Structure Learning via Information Bottleneck for Recommendation
• Self-supervised Heterogeneous Graph Pre-training Based on Structural Clustering
• Does GNN Pretraining Help Molecular Representation?

5. 分布偏移以及OOD问题

• Learning Invariant Graph Representations Under Distribution Shifts
• Dynamic Graph Neural Networks Under Spatio-Temporal Distribution Shift
• Association Graph Learning for Multi-Task Classification with Category Shifts
• Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs
• Towards Debiased Learning and Out-of-Distribution Detection for Graph Data
• SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks
• Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks

6. 生成式模型

• Deep Generative Model for Periodic Graphs
• An efficient graph generative model for navigating ultra-large combinatorial synthesis libraries
• AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators
• Evaluating Graph Generative Models with Contrastively Learned Features
• Molecule Generation by Principal Subgraph Mining and Assembling
• A Variational Edge Partition Model for Supervised Graph Representation Learning
• Symmetry-induced Disentanglement on Graphs

7. Meta learning

• Graph Few-shot Learning with Task-specific Structures

8. 解释性

• Task-Agnostic Graph Explanations
• Explaining Graph Neural Networks with Structure-Aware Cooperative Games

9. 知识蒸馏

• Geometric Distillation for Graph Networks
• Knowledge Distillation Improves Graph Structure Augmentation for Graph Neural Networks

10. 因果

• Debiasing Graph Neural Networks via Learning Disentangled Causal Substructure
• CLEAR: Generative Counterfactual Explanations on Graphs
• Counterfactual Fairness with Partially Known Causal Graph
• Large-Scale Differentiable Causal Discovery of Factor Graphs
• Multi-agent Covering Option Discovery based on Kronecker Product of Factor Graphs

11. 池化

• High-Order Pooling for Graph Neural Networks with Tensor Decomposition
• Graph Neural Networks with Adaptive Readouts

12. 推荐系统

• Graph Convolution Network based Recommender Systems: Learning Guarantee and Item Mixture Powered Strategy

13. 鲁棒性

• Towards Reasonable Budget Allocation in Untargeted Graph Structure Attacks via Gradient Debias
• Robust Graph Structure Learning over Images via Multiple Statistical Tests
• Are Defenses for Graph Neural Networks Robust?
• Certifying Robust Graph Classification under Orthogonal Gromov-Wasserstein Threats
• EvenNet: Ignoring Odd-Hop Neighbors Improves Robustness of Graph Neural Networks
• On the Robustness of Graph Neural Diffusion
• What Makes Graph Neural Networks Miscalibrated?
• Randomized Message-Interception Smoothing: Gray-box Certificates for Graph Neural Networks

14. 强化学习

• DHRL: A Graph-Based Approach for Long-Horizon and Sparse Hierarchical Reinforcement Learning
• Non-Linear Coordination Graphs

15. 隐私保护

• CryptoGCN: Fast and Scalable Homomorphically Encrypted Graph Convolutional Network Inference
• Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank
• Private Graph Distance Computation with Improved Error Rate

16. 各种类型的图（异质图，异配图，超图，动态图，时空图，etc）

异质图（Heterogeneous Graphs）

• Descent Steps of a Relation-Aware Energy Produce Heterogeneous Graph Neural Networks
• Zero-shot Transfer Learning on Heterogeneous Graphs via Knowledge Transfer Networks

异配图（Non-Homophilous/Heterophilous/Disassortive graphs）

• Revisiting Heterophily For Graph Neural Networks
• Simplified Graph Convolution with Heterophily

超图

• Sparse Hypergraph Community Detection Thresholds in Stochastic Block Model
• Augmentations in Hypergraph Contrastive Learning: Fabricated and Generative
• SHINE: SubHypergraph Inductive Neural nEtwork

动态图（dynamic graphs）

• Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs

时空图

• Learning to Reconstruct Missing Data from Spatiotemporal Graphs with Sparse Observations
• Provably expressive temporal graph networks
• AZ-whiteness test: a test for signal uncorrelation on spatio-temporal graphs

有向图

• Iterative Structural Inference of Directed Graphs
• Transition to Linearity of General Neural Networks with Directed Acyclic Graph Architecture
• Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings
• Neural Topological Ordering for Computation Graphs

二部图

• Learning Bipartite Graphs: Heavy Tails and Multiple Components

Feedback graphs

• Learning on the Edge: Online Learning with Stochastic Feedback Graphs
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
• Stochastic Online Learning with Feedback Graphs: Finite-Time and Asymptotic Optimality

知识图谱

• Contrastive Language-Image Pre-Training with Knowledge Graphs
• Rethinking Knowledge Graph Evaluation Under the Open-World Assumption
• OTKGE: Multi-modal Knowledge Graph Embeddings via Optimal Transport
• Inductive Logical Query Answering in Knowledge Graphs
• Learning to Sample and Aggregate: Few-shot Reasoning over Temporal Knowledge Graph
• Few-shot Relational Reasoning via Pretraining of Connection Subgraph Reconstruction
• ReFactorGNNs: Revisiting Factorisation-based Models from a Message-Passing Perspective

17. 下游任务

链接预测

• OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems
• Parameter-free Dynamic Graph Embedding for Link Prediction

图分类

• Label-invariant Augmentation for Semi-Supervised Graph Classification

图聚类

• Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitions
• S3GC: Scalable Self-Supervised Graph Clustering
• Stars: Tera-Scale Graph Building for Clustering and Learning
• Hierarchical Agglomerative Graph Clustering in Poly-Logarithmic Depth

图像分类

• Vision GNN: An Image is Worth Graph of Nodes

异常值检测

• Dual-discriminative Graph Neural Network for Imbalanced Graph-level Anomaly Detection

分子图

• ComENet: Towards Complete and Efficient Message Passing for 3D Molecular Graphs

时间序列预测

• Multivariate Time-Series Forecasting with Temporal Polynomial Graph Neural Networks

电路图

• Versatile Multi-stage Graph Neural Network for Circuit Representation
• NeuroSchedule: A Novel Effective GNN-based Scheduling Method for High-level Synthesis

Robot manipulation

• Learning-based Manipulation Planning in Dynamic Environments Using GNNs and Temporal Encoding

17. Algorithms

Objective-space decomposition algorithms（ODAs）

• Graph Learning Assisted Multi-Objective Integer Programming

Dynamic Programming （DP）

• Graph Neural Networks are Dynamic Programmers

Bandits

• Graph Neural Network Bandits
• Maximizing and Satisficing in Multi-armed Bandits with Graph Information

Link selection

• Learning to Navigate Wikipedia with Graph Diffusion Models

Graph search

• Graph Reordering for Cache-Efficient Near Neighbor Search

Densest subgraph problem (DSG) and the densest subgraph local decomposition problem

• Faster and Scalable Algorithms for Densest Subgraph and Decomposition

Optimization

• Semi-Supervised Learning with Decision Trees: Graph Laplacian Tree Alternating Optimization

Dimension Reduction

• A Probabilistic Graph Coupling View of Dimension Reduction

Physics

• Learning Rigid Body Dynamics with Lagrangian Graph Neural Network
• PhysGNN: A Physics--Driven Graph Neural Network Based Model for Predicting Soft Tissue Deformation in Image-Guided Neurosurgery
• Physics-Embedded Neural Networks: -Equivariant Graph Neural PDE Solvers

图相似度计算

• Efficient Graph Similarity Computation with Alignment Regularization
• GREED: A Neural Framework for Learning Graph Distance Functions

NP-Hard problems

• Learning NP-Hard Joint-Assignment planning using GNN: Inference on a Random Graph and Provable Auction-Fitted Q-iteration
• Learning to Compare Nodes in Branch and Bound with Graph Neural Networks

18. Miscellaneous

• Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks
• Learning on Arbitrary Graph Topologies via Predictive Coding
• Graph Agnostic Estimators with Staggered Rollout Designs under Network Interference
• Exact Shape Correspondence via 2D graph convolution
• Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction
• Thinned random measures for sparse graphs with overlapping communities
• Learning Physical Dynamics with Subequivariant Graph Neural Networks
• On the Discrimination Risk of Mean Aggregation Feature Imputation in Graphs