  Graph neural networks (GNNs) have achieved state-of-the-art performance in
various graph-based tasks. However, as mainstream GNNs are designed based on
the neural message passing mechanism, they do not scale well to data size and
message passing steps. Although there has been an emerging interest in the
design of scalable GNNs, current researches focus on specific GNN design,
rather than the general design space, limiting the discovery of potential
scalable GNN models. This paper proposes PasCa, a new paradigm and system that
offers a principled approach to systemically construct and explore the design
space for scalable GNNs, rather than studying individual designs. Through
deconstructing the message passing mechanism, PasCa presents a novel Scalable
Graph Neural Architecture Paradigm (SGAP), together with a general architecture
design space consisting of 150k different designs. Following the paradigm, we
implement an auto-search engine that can automatically search well-performing
and scalable GNN architectures to balance the trade-off between multiple
criteria (e.g., accuracy and efficiency) via multi-objective optimization.
Empirical studies on ten benchmark datasets demonstrate that the representative
instances (i.e., PasCa-V1, V2, and V3) discovered by our system achieve
consistent performance among competitive baselines. Concretely, PasCa-V3
outperforms the state-of-the-art GNN method JK-Net by 0.4\% in terms of
predictive accuracy on our large industry dataset while achieving up to
$28.3\times$ training speedups.
