Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks

Yifan Chen, Tianning Xu, Dilek Hakkani-Tur, Di Jin, Yun Yang, Ruoqing Zhu

Research output: Contribution to journalJournal articlepeer-review

Abstract

Multiple sampling-based methods have been developed for approximating and accelerating node embedding aggregation in graph convolutional networks (GCNs) training. Among them, a layer-wise approach recursively performs importance sampling to select neighbors jointly for existing nodes in each layer. This paper revisits the approach from a matrix approximation perspective, and identifies two issues in the existing layer-wise sampling methods: suboptimal sampling probabilities and estimation biases induced by sampling without replacement. To address these issues, we accordingly propose two remedies: a new principle for constructing sampling probabilities and an efficient debiasing algorithm. The improvements are demonstrated by extensive analyses of estimation variance and experiments on common benchmarks. Code and algorithm implementations are publicly available at https://github.com/ychen-stat-ml/GCN-layer-wise-sampling .
Original languageEnglish
Pages (from-to)1-32
Number of pages32
JournalTransactions on Machine Learning Research
Publication statusPublished - Jan 2023

Fingerprint

Dive into the research topics of 'Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks'. Together they form a unique fingerprint.

Cite this