NeurIPS'22上的GNN好文集合 (表示能力、架构设计、图对比/自监督学习、分布偏移、可解释、推荐系统等)

2022 年 9 月 20 日 图与推荐

近日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