IMA-GNN: In-Memory Acceleration of Centralized and Decentralized Graph
  Neural Networks at the Edge
In this paper, we propose IMA-GNN as an In-Memory Accelerator for centralized
and decentralized Graph Neural Network inference, explore its potential in both
settings and provide a guideline for the community targeting flexible and
efficient edge computation. Leveraging IMA-GNN, we first model the computation
and communication latencies of edge devices. We then present practical case
studies on GNN-based taxi demand and supply prediction and also adopt four
large graph datasets to quantitatively compare and analyze centralized and
decentralized settings. Our cross-layer simulation results demonstrate that on
average, IMA-GNN in the centralized setting can obtain ~790x communication
speed-up compared to the decentralized GNN setting. However, the decentralized
setting performs computation ~1400x faster while reducing the power consumption
per device. This further underlines the need for a hybrid semi-decentralized
GNN approach.
Mehrdad Morsali, Mahmoud Nazzal, Abdallah Khreishah, Shaahin Angizi
# IMA-GNN: In-Memory Acceleration of Centralized and Decentralized Graph Neural Networks at the Edge

###### Abstract.

In this paper, we propose IMA-GNN as an In-Memory Accelerator for centralized and decentralized Graph Neural Network inference, explore its potential in both settings, and provide a guideline for the community targeting flexible and efficient edge computation. Leveraging IMA-GNN, we first model the computation and communication latencies of edge devices. We then present practical case studies on GNN-based taxi demand and supply prediction and also adopt four large graph datasets to quantitatively compare and analyze centralized and decentralized settings. Our cross-layer simulation results demonstrate that on average, IMA-GNN in the centralized setting can obtain \(\sim\)790\(\times\) communication speed-up compared to the decentralized GNN setting. However, the decentralized setting performs computation \(\sim\)1400\(\times\) faster while reducing the power consumption per device. This further underlines the need for a hybrid semi-decentralized GNN approach.

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science

+
Footnote †: journal journal: Journal of Computer Science

+
Footnote †: journal: Journal of Computer Science
ability to mitigate the computation overhead by load sharing, decentralized GNN operation faces a major bottleneck; the excessive communication overhead between nodes in different distributed devices (Beng et al., 2017). To the best of our knowledge, this work is among the first to explore and compare in-memory acceleration in both centralized and decentralized GNN settings and to offer a design guideline to the community. The main contributions of this paper are as follows: (1) We develop a PIM architecture with RRAM arrays based on a set of innovative micro-architectural designs that can be optimized and used for centralized and decentralized GNN inference for efficiency and speed-up; (2) We model the latency and power consumption of GNN accelerators implemented in centralized and decentralized settings considering the computation and communication between edge devices; and (3) We present a solid bottom-up evaluation framework to analyze the performance of the whole system in real scenarios and through adopting large graph datasets.

## 2. Proposed Ima-Gnn

### Architecture Overview

The IMA-GNN is a high-performance and energy-efficient RRAM crossbar-based accelerator developed to execute GNN's pivotal operations in both centralized and decentralized settings inspired by (Han et al., 2017). As shown in Fig. 2(a), IMA-GNN comprises three computation cores, i.e., traversal, aggregation, and feature extraction as well as peripherals such as a buffer array and a controller. The traversal core consists of resistive Content Addressable Memory (CAM) crossbars capable of search and comparison operations (Fig. 2(c)). All resistive CAM crossbars on the bottom side are connected to a shared vector generator & scheduler unit and then to a high-bandwidth bus to communicate with other cores at the top. The aggregation core includes resistive crossbars (Fig. 2(b)) to perform in-situ Matrix-Vector-Multiplication (MVM) operations for the feature aggregation. The feature extraction core is designed with a similar resistive crossbar but a different size to take care of transformation in GNN inference. The resistive MVM crossbars are connected to a shared activation unit.

### MVM & CAM Crossbars

The RRAM crossbar memory arrays are widely explored as a potential parallel engine to execute MVM operation and scan and search (Han et al., 2017; Han et al., 2017; Han et al., 2017). As shown in Fig. 2(b) in the MVM crossbars, the weight parameters are first stored as resistance states in each RRAM device in a 1-Transistor-1-RRAM (1T1R) structure, and then the input binary bit-strings, as the inputs to the crossbar array, are converted by the Digital-to-Analog Converter (DAC) into voltages \(V_{i}\) and applied to Bit-Lines (\(BL\)s) in parallel. The weighted currents generated from the RRAM cells sharing a Source-Line (\(SL\)) are accumulated resulting in an intrinsic dot-products operation. The accumulated values are then sampled by Sample & Hold unit and then converted to binary data using Analog-to-Digital Converters (ADC). The partial-product results from each \(SL\) are further processed by the Shift & Add unit to generate the final result. As shown in Fig. 2(c), in the CAM crossbars, each Ternary CAM (TCAM) cell consists of 2-Transistor-2-RRAM (2T2R) to accomplish the XNOR search operation on each pair of cells. For this operation, \(BL\) and \(\overline{BL}\)s are valued with the search data by the Search Data Driver. Accordingly, the Sense Amplifier connected to Match-Lines (\(ML\)SA) senses whether the row is a match or mismatch with the reference connected to Vdd. In the compare operation, \(BL\)s are grounded and \(\overline{BL}\)s are connected to increasing calibrated voltages from the Least Significant Bit (LSB) to the Most Significant Bits (MSB).

### Accelerator Dataflow

Once the edge buffers shown in Fig. 2(a) on the left have been loaded with graph data in either centralized or decentralized GNN settings, the traversal core starts processing edges. The traversal

Figure 2. (a) The proposed IMA-GNN architecture with resistive CAM traversal core, resistive MVM aggregation, and feature extraction cores, (b) Resistive MVM crossbar, (c) Resistive CAM crossbar.
core performs two essential CAM-based operations, i.e., search and compare. To maximize the data reuse of feature data in IMA-GNN, the traversal core implements an efficient node-stationary dataflow by buffering a set of node features in the buffer array and reusing it for the aggregation core. IMA-GNN leverages a Compressed Sparse Row (CSR) format (Krishnam et al., 2015) to form the Edge weight array (E), Column Index array (CI), and Row Pointer array (RP) and loads the graph data to search and scan CAMs (Fig. 2(a)). A sample graph adjacency matrix and the corresponding CSR format are shown in Fig. 3(a)-(b). Any destination node then operates as an input to the search CAM as shown in the data mapping in Fig. 3(c) and rows that match the search data are activated. Matching rows are reference inputs for comparison in the scan CAM, which determines the source nodes with edges to the destination node by comparing the input row with RP (Fig. 3(d)). Next, the vector generator & scheduler unit receives the result of scan CAM and edge data to render input control vectors for the aggregation core (Fig. 2(a)). This will activate particular rows of resistive aggregation core corresponding to incoming edges. Next, the aggregation core input buffers receive input vectors for each destination node along with the destination node. The aggregation core starts with source node features or feature dimensions across its own cluster. IMA-GNN is equipped with double buffering for feature data and graph data. This feature enables overlapping writing/programming phases and the traversal stage. Next, the updated destination node features are fed to the feature extraction core's crossbars programmed with weights. Besides, similar to (Beng et al., 2017), to maximize the crossbar utilization in the aggregation core, both the aggregation and feature extraction cores could work in parallel.

## 3. Network Modeling

We explore both centralized and decentralized GNN landscapes to fairly model the performance metrics in both settings. Figure 4 shows a sample graph with \(N\) (\(N\in\mathbb{Z}^{+}\)) nodes (edge devices). In the centralized GNN setting, a single powerful node as the accelerator is designed with embedded traversal, aggregation, and feature extraction cores to communicate through fast inter-network links (\(L_{n}\)) (Krishnam et al., 2015) to aggregate all edge devices' information and handle the computation burdens of transformation. These cores have \(M_{1},M_{2}\), and \(M_{5}\) times larger allocated computing hardware for traversal, aggregation, and feature extraction operations respectively than a single node in the decentralized mode. Thus, we assume the processing capability of the edge device in the centralized setting is \(M_{1}\), \(M_{2}\), and \(M_{3}\) times larger than the processing capability of a single node in the decentralized mode in the traversal, aggregation, and feature extraction operations, respectively. In the decentralized GNN setting, each edge device is observed as an accelerator with reduced traversal and aggregation cores and in addition to a copy of our network, has an embedded feature extraction core processing \(L\) layers. The output of the feature extraction core at each edge device is only communicated to the adjacent edge devices at a defined cluster as shown in Fig. 4(b). Therefore, the communication between neighbors through inter-cluster links (\(L_{c}\)) (Krishnam et al., 2015) generates a communication volume as well. The bidirectional communication volume between node-\(i\) to node-\(j\) is represented as \(\epsilon_{i,j}\). Therefore, the minimization of the accelerator's computational latency/power and communication latency/power is a pivotal need in the research community. We estimate the centralized and decentralized GNN accelerators' latency as:

\[T_{Net}(N)=T_{compute}(N)+T_{communicate}(N). \tag{1}\]

In an \(N\)-edge device graph shown in Fig. 4, denoting by \(t_{1}\), \(t_{2}\), and \(t_{3}\) the traversal, aggregation, and feature extraction cores' latency, respectively, the computation latency of a single node in the decentralized GNNs can be estimated by:

\[T_{compute-decentralized}=t_{1}+t_{2}+t_{3}, \tag{2}\]

where in the centralized setting, considering the processing capability of a single powerful edge device the computation latency is given by:

\[T_{compute-centralized}=(t_{1}/M_{1}+t_{2}/M_{2}+t_{3}/M_{5})\times(N-1). \tag{3}\]

In the decentralized setting, the communication latency, \(T_{communicate}\), can be given by:

\[T_{communicate-centralized}=(t_{k}+(c_{k}\times t(L_{c})))\times 2, \tag{4}\]

where \(t_{k}\) is the required time for establishing a connection between two adjacent nodes, \(c_{s}\) denotes the number of adjacent nodes inside a cluster, \(t(L_{c})\) denotes the latency of the inter-cluster link, and number \(2\) is to model a two-way link. We assume that data communication inside each cluster is done in a sequential way, thus the number of adjacent nodes is multiplied by the latency of the inter-cluster link. For the centralized setting, we assume data transfer between the central edge device and nodes is done in a concurrent way. Therefore, the communication latency, \(T_{communicate}\)

Figure 4. Intra- and inter-edge links in a sample (a) centralized versus (b) decentralized GNN.

Figure 3. IMA-GNN’s hardware mapping and acceleration in traversal core: (a) Sample graph adjacency matrix, (b) CSR representation, (c) Search CAM operation, (d) Scan CAM operation.
for centralized inference can be given by:

\[T_{communicate-decentralized}=t(L_{n}), \tag{5}\]

where \(t(L_{n})\) is the latency of the inter-network link. Suppose each edge device runs a GNN with \(X\)-layers, the number of input and output neuron activations for a layer \(x\) for \(1\leqslant x\leqslant\)X can be given by \(\alpha(x)\) and \(\alpha(x+1)\), respectively. The total power consumption of GNNs implemented in the proposed accelerator can be developed as:

\[P_{Net}(N)=P_{compute}(N)+P_{communicate}(N). \tag{6}\]

The first part accounts for the computation power and the second part considers communication power for inter-network and inter-cluster links. In the centralized setting, \(P_{compute-centralized}\) is given by \(\frac{E_{compute-centralized}}{T_{compute-centralized}}\) and \(P_{communicate-centralized}\) can be given by \(p(L_{n})\times 2\). Here \(p(L_{n})\) denotes the power consumption of the inter-network link and number \(2\) is to model a two-way transfer. \(E_{compute-centralized}\) is readily calculated by achieving the energy consumption values of traversal, aggregation, and feature extraction cores. As for the decentralized setting, \(P_{compute-decentralized}\) can be computed with respect to energy and latency parameters. We consider \(\sum_{n=1}^{c_{s}}p_{n}(c_{s}(n)(c_{s}(n)-1))\) transactions between all accelerators inside the cluster. Considering the X-layer GNN, \(P_{communicate}\) can be expressed as follow:

\[P_{communicate-decentralized}=\frac{1}{t(L_{c})}\times\sum_{x=1}^{X-1}\alpha(x+ 1)\times E_{perBtt} \tag{7}\]

## 4. Experiments

### Evaluation Framework

To evaluate the performance of the proposed architecture, a comprehensive bottom-up evaluation framework is developed as depicted in Fig. 5. At the circuit-level, we use the SPICE model for memristors with the Ag-Si memristor device parameters from (K
The enormous sizes of transportation graphs make it challenging to apply the model in (Zhou et al., 2017) in centralized GNN inference. This limitation is further aggravated by the hetGNNs and the huge volumes of local node information. As a remedy to resolve this limitation, the authors in (Zhou et al., 2017) propose a decentralized GNN inference approach. In this approach, each taxi node has a copy of the model (hetGNN-LSTM), exchanges messages with its \(k\)-hop neighbors, and then uses the hetGNN-LSTM model to predict the demands and supplies in its surrounding region. A natural advantage of this approach is handling dynamically varying graph structures. Nevertheless, despite the promising advantages of decentralization, there is still a demanding need for reducing the overall computation and communication latency in the operation of the model.

In this experiment, for the centralized GNN setting, the overall latency (in terms of transmission delay) for sending and receiving a packet of 300 Bytes is considered 1.1 ms where the range of the network is 300 meters (Kumar et al., 2017). This latency is the average overall latency to correctly receive a packet of 300 bytes. Thus, for a packet size of 864 bytes, which is the size of our data, the overall transmission delay can be \(\sim\)3.3 ms.

As for the decentralized GNN setting, we assume that nodes in the graphs of (Zhou et al., 2017) communicate with each other using an ad-hoc wireless network that uses channel 9 (2.452 GHz) of IEEE 802.11n, where the transmission power is fixed to \(\sim\)31 dBm, and bandwidth is 20 MHz. In this configuration, source nodes feed their messages to nearby proxy (relay) nodes which forward the messages to the next nodes, and so on. Since source nodes have more computation compared to proxy (relay) nodes, they incur more delay. We leverage the proposed bottom-up evaluation framework to estimate IMA-GNN architecture performance in both centralized and decentralized settings. In our evaluation, the number of nodes (taxis) of the graph and the cluster size (\(c_{s}\)) are set as 10000 and 10, respectively. The evaluation results of the latency and power consumption are tabulated in Table 1.

In view of the results, the decentralized setting in (Zhou et al., 2017) improves the total computation latency by a factor of \(\sim\)10\(\times\). This is achieved by reducing the traversal latency, aggregation latency, and feature extraction latency by factors of 5\(\times\), 10\(\times\), and \(\sim\)39\(\times\), respectively. Thus, a huge improvement can be observed in terms of computation latency. However, in terms of communication, the centralized setting acts much better than the decentralized setting by incurring a \(\sim\)120\(\times\) less latency. As for computation power consumption, we observe that the decentralized setting reduces the power budget per node by a factor of 18\(\times\). The aggregation core of IMA-GNN consumes most of the power in both centralized and decentralized settings as well as the highest latency. Overall, each of the settings has its own advantage from a different point of view. In the next subsection, more graph datasets with different characteristics are studied in order to further elucidate the pros and cons of centralized and decentralized settings.

### Graph Datasets

In the second case study, four graph datasets, LiveJournal, Collab, Cora, and Citeseer (Citeseer, 2015; Zhou et al., 2017) are used to evaluate the inference latency using the proposed IMA-GNN in centralized and decentralized settings. Key graph statistics of these datasets are provided in Table 2. A given vertex is mapped deterministically to a fixed-sized, uniform sample of its neighbors.

Figure 8 shows the latency for the four aforementioned graph datasets. Each bar consists of two parts; computation latency and communication latency. For each dataset, we have two bars representing the latency in the centralized (left) and decentralized (right) settings. By close observation, it can be realized that in all under-test datasets, the computation latency of the decentralized setting is less than that of the centralized setting. Especially, the difference between the computation latency of centralized and decentralized settings is huge in LiveJournal and Collab datasets, where the graph size is much larger than the other two datasets. In view of Fig. 8, amongst the four datasets, LiveJournal has the largest computation latency in the centralized settings because it owns the largest number of nodes. This is because in the decentralized mode, as each node is responsible to do its' own computation, the computation latency is independent of the total number of nodes and doesn't increase when the number of nodes grows. Conversely, in the centralized setting, by growing the number of nodes, the computation burden of the edge device will increase, causing an increment in the computation latency. On average for these four datasets, the decentralized setting performs computations \(\sim\)1400\(\times\) faster. However, the communication latency which is the dominant part of the total latency is much higher in the decentralized setting as each node is required to establish a peer-to-peer connection and transfer data with all adjacent nodes sequentially. According to Fig. 8, Collab has the largest communication latency amongst the four

\begin{table}
\begin{tabular}{|l|c|c|c|c|} \hline Settings & \multicolumn{2}{c|}{Centralized} & \multicolumn{2}{c|}{Decentralized} \\ \hline Figure of merits & Latency & Power & Latency & Power \\ \hline Traversal & 38.43 ns & 10.8 mW & 7.68 ns & 0.21 mW \\ \hline Aggregation & 142.77 \(\mu\)s & 780.1 mW & 14.27 \(\mu\)s & 41.6 mW \\ \hline Feature extraction & 14.53 \(\mu\)s & 32.21 mW & 0.37 \(\mu\)s & 3.68 mW \\ \hline Computation (Net) & 157.34 \(\mu\)s & 823.11 mW & 14.6 \(\mu\)s & 45.49 mW \\ \hline Communication & 3.30 ms & - & 406 ms & - \\ \hline \end{tabular}
\end{table}
Table 1. Computation and communication latency/power of IMA-GNN accelerator.

\begin{table}
\begin{tabular}{|l|c|c|c|c|} \hline Datasets & LiveJournal & Collab & Cora & Citeseer \\ \hline Number of Nodes & 4,847,571 & 372,475 & 2708 & 3,327 \\ \hline Number of Edges & 68,993,773 & 24,574,995 & 5429 & 4,732 \\ \hline Feature Length & 1 & 496 & 1433 & 3,703 \\ \hline Average \(C_{s}\) & 9 & 263 & 4 & 2 \\ \hline \end{tabular}
\end{table}
Table 2. Key statistics of the graph datasets used.

Figure 7. The architecture of the hetGNN-LSTM based prediction in (Zhou et al., 2017).
datasets, in the decentralized settings due to its large Average \(C_{s}\), where each node is required to communicate with a large number of adjacent nodes sequentially. However, in the centralized mode, all nodes are connected to the edge device using a fast and mature connection and can transfer data in a parallel way. In terms of the communication latency, for four under-test datasets, the centralized setting is \(\sim\)790\(\times\) faster than the decentralized setting.

In addition, we observe that the performance of the IMA-GNN architecture can increase linearly with an increase in the number of resistive CAM and MVM crossbars in decentralized setting for various datasets and saturate once the entire node feature data could be fitted onto the crossbars. However, it comes at the cost of higher power consumption for each node.

## 5. Conclusion

While the respective benefits of centralized and decentralized GNNs are known in software implementation, there is a lack of hardware implementation analysis to show the communication and computation loads in each setting. This work undertakes this task by modeling and analyzing practical case studies on GNN-based taxi demand and supply prediction and adopting large-scale graph datasets. Our cross-layer simulation results demonstrate our proposed platform called IMA-GNN in the centralized GNN setting can obtain \(\sim\)790\(\times\) communication speed-up compared to the decentralized GNN setting. However, the decentralized GNN setting performs computation \(\sim\)1400\(\times\) faster while reducing the power consumption per device. This study is conducted based on certain assumptions as discussed. Nevertheless, the results extrapolate that the decentralized GNN setting achieves gains in reducing the computation latency. However, this comes at the expense of increasing communication overhead and latency. This latency is more strongly pronounced with larger graphs. This finding confirms the necessity and the potential of balancing this communication-computation trade-off through a semi-decentralized setting (Zhou et al., 2020). In that setting, multiple edge devices are employed to decentralize the operation on a graph level while each edge device region works in a centralized fashion. Our future work will consider the hardware acceleration of the semi-decentralized GNN setting.
