Rethinking Node-wise Propagation for Large-scale Graph Learning
Xunkai Li Jingyuan Ma Zhengyu Wu Daohan Su Wentao Zhang Rong-Hua Li Guoren Wang
Scalable graph neural networks (GNNs) have emerged as a promising technique,
which exhibits superior predictive performance and high running efficiency
across numerous large-scale graph-based web applications. However, (i) Most
scalable GNNs tend to treat all nodes in graphs with the same propagation
rules, neglecting their topological uniqueness; (ii) Existing node-wise
propagation optimization strategies are insufficient on web-scale graphs with
intricate topology, where a full portrayal of nodes' local properties is
required. Intuitively, different nodes in web-scale graphs possess distinct
topological roles, and therefore propagating them indiscriminately or neglect
local contexts may compromise the quality of node representations. This
intricate topology in web-scale graphs cannot be matched by small-scale
scenarios. To address the above issues, we propose \textbf{A}daptive
\textbf{T}opology-aware \textbf{P}ropagation (ATP), which reduces potential
high-bias propagation and extracts structural patterns of each node in a
scalable manner to improve running efficiency and predictive performance.
Remarkably, ATP is crafted to be a plug-and-play node-wise propagation
optimization strategy, allowing for offline execution independent of the graph
learning process in a new perspective. Therefore, this approach can be
seamlessly integrated into most scalable GNNs while remain orthogonal to
existing node-wise propagation optimization strategies. Extensive experiments
on 12 datasets, including the most representative large-scale ogbn-papers100M,
have demonstrated the effectiveness of ATP. Specifically, ATP has proven to be
efficient in improving the performance of prevalent scalable GNNs for
semi-supervised node classification while addressing redundant computational
costs.