Constant Time Graph Neural Networks
  The recent advancements in graph neural networks (GNNs) have led to
state-of-the-art performances in various applications, including
chemo-informatics, question-answering systems, and recommender systems.
However, scaling up these methods to huge graphs, such as social networks and
Web graphs, remains a challenge. In particular, the existing methods for
accelerating GNNs either are not theoretically guaranteed in terms of the
approximation error or incur at least a linear time computation cost. In this
study, we reveal the query complexity of the uniform node sampling scheme for
Message Passing Neural Networks, including GraphSAGE, graph attention networks
(GATs), and graph convolutional networks (GCNs). Surprisingly, our analysis
reveals that the complexity of the node sampling method is completely
independent of the number of the nodes, edges, and neighbors of the input and
depends only on the error tolerance and confidence probability while providing
a theoretical guarantee for the approximation error. To the best of our
knowledge, this is the first paper to provide a theoretical guarantee of
approximation for GNNs within constant time. Through experiments with synthetic
and real-world datasets, we investigated the speed and precision of the node
sampling scheme and validated our theoretical results.
