GNN at the Edge: Cost-Efficient Graph Neural Network Processing Over Distributed Edge Servers

Edge intelligence has arisen as a promising computing paradigm for supporting miscellaneous smart applications that rely on machine learning techniques. While the community has extensively investigated multi-tier edge deployment for traditional deep learning models (e.g. CNNs, RNNs), the emerging Graph Neural Networks (GNNs) are still under exploration, presenting a stark disparity to its broad edge adoptions such as traffic flow forecasting and location-based social recommendation. To bridge this gap, this paper formally studies the cost optimization for distributed GNN processing over a multi-tier heterogeneous edge network. We build a comprehensive modeling framework that can capture a variety of different cost factors, based on which we formulate a cost-efficient graph layout optimization problem that is proved to be NP-hard. Instead of trivially applying traditional data placement wisdom, we theoretically reveal the structural property of quadratic submodularity implicated in GNN’s unique computing pattern, which motivates our design of an efficient iterative solution exploiting graph cuts. Rigorous analysis shows that it provides parameterized constant approximation ratio, guaranteed convergence, and exact feasibility. To tackle potential graph topological evolution in GNN processing, we further devise an incremental update strategy and an adaptive scheduling algorithm for lightweight dynamic layout optimization. Evaluations with real-world datasets and various GNN benchmarks demonstrate that our approach achieves superior performance over de facto baselines with more than 95.8% cost reduction in a fast convergence speed.

I. Introduction

Recent advances in neural networks have emerged as a powerful technique in a broad range of smart applications, including object detection, speech recognition, and data mining [1], [2], [3]. With the rapidly increasing computation resources as supporting platforms and tremendous training data as materials, Deep Neural Networks (DNNs) are able to extract latent representations from existing statistics, especially data in Euclidean or sequential form [1]. Yet there are still enormous data generated with complex graph structures including social graph [4], wireless sensor network [5], etc. Analytics on these graphs bring significant challenges to traditional DNNs due to their structure irregularity and feature complexity [6].