Accelerating Graph Neural Networks via Edge Pruning for Power Allocation
  in Wireless Networks
Graph Neural Networks (GNNs) have recently emerged as a promising approach to
tackling power allocation problems in wireless networks. Since unpaired
transmitters and receivers are often spatially distant, the distance-based
threshold is proposed to reduce the computation time by excluding or including
the channel state information in GNNs. In this paper, we are the first to
introduce a neighbour-based threshold approach to GNNs to reduce the time
complexity. Furthermore, we conduct a comprehensive analysis of both
distance-based and neighbour-based thresholds and provide recommendations for
selecting the appropriate value in different communication channel scenarios.
We design the corresponding neighbour-based Graph Neural Networks (N-GNN) with
the aim of allocating transmit powers to maximise the network throughput. Our
results show that our proposed N-GNN offer significant advantages in terms of
reducing time complexity while preserving strong performance and generalisation
capacity. Besides, we show that by choosing a suitable threshold, the time
complexity is reduced from O(|V|^2) to O(|V|), where |V| is the total number of
transceiver pairs.
Lili Chen, Jingge Zhu, Jamie Evans
# Accelerating Graph Neural Networks via Edge Pruning for Power Allocation in Wireless Networks

###### Abstract

Graph Neural Networks (GNNs) have recently emerged as a promising approach to tackling power allocation problems in wireless networks. Since unpaired transmitters and receivers are often spatially distant, the distanced-based threshold is proposed to reduce the computation time by excluding or including the channel state information in GNNs. In this paper, we are the first to introduce a neighbour-based threshold approach to GNNs to reduce the time complexity. Furthermore, we conduct a comprehensive analysis of both distance-based and neighbour-based thresholds and provide recommendations for selecting the appropriate value in different communication channel scenarios. We design the corresponding distance-based and neighbour-based Graph Neural Networks with the aim of allocating transmit powers to maximise the network throughput. Our results show that our proposed GNNs offer significant advantages in terms of reducing time complexity while preserving strong performance. Besides, we show that by choosing a suitable threshold, the time complexity is reduced from \(\mathcal{O}(|\mathcal{V}|^{2})\) to \(\mathcal{O}(|\mathcal{V}|)\), where \(|\mathcal{V}|\) is the total number of transceiver pairs.

 Power allocation, Graph neural networks, Threshold, Low complexity

## I Introduction

The proliferation of fifth-generation (5G) communication technology has resulted in an escalating need for high-rate wireless access services. This trend has engendered formidable challenges to the availability of spectrum resources due to their finite nature. As an auspicious technique to alleviate the predicament of spectrum scarcity, device-to-device (D2D) communications have recently garnered considerable attention [1].

In D2D communication, two devices can communicate directly without relying on the involvement of the base station (BS) or access point (AP). The short-range D2D links facilitate high data rates for local devices, reduce power consumption in mobile devices, and relieve the traffic of BSs. However, power allocation in D2D networks is often a non-convex problem and computationally hard. Inspired by recent success in computer science, graph neural networks (GNNs) have been applied to power allocation problems in wireless networks.

In D2D networks, unpaired transmitters and receivers are often spatially distant. In light of the distance-dependent nature of interference decay, eliminating connections between distant nodes appears to be a logical approach towards reducing computational complexity, while not significantly compromising performance.

In [2], the authors proposed the distance-based threshold to reduce computation time by excluding the channel state information (CSI) in GNN when the distance is over a specific threshold. Similarly, the authors in [3] removed the edges between the transmitter to the non-paired receivers if the CSI between them is smaller than a specific threshold.

However, the threshold was chosen arbitrarily, lacking further elaboration. In response to this issue, a recent study explored the delicate balance between performance and time complexity by implementing the threshold [4]. The authors demonstrated that selecting an appropriate threshold can significantly reduce the anticipated time complexity, while concurrently preserving favorable performance outcomes. However, the results presented in [4] are restricted to a single path loss exponent, therefore, their generalisability to alternative path loss exponents is not assured. To address this limitation, the present investigation undertakes a comprehensive analysis of thresholds and provides recommendations for selecting the appropriate threshold value that corresponds to different path loss exponents. To accomplish this objective, we evaluate various thresholds in terms of their potential to catch the expected interference. Furthermore, we introduce a neighbour-based threshold that enables the reduction of time complexity from quadratic to linear with the number of transceiver pairs.

The contributions of this paper are summarised as follows:

* This research is the first to introduce a neighbour-based threshold approach to GNNs that offers significant advantages in terms of reducing time complexity while preserving the strong performance.
* This study is the first to systematically investigate appropriate threshold selection from a stochastic geometry perspective. We provide recommendations for selecting the appropriate threshold value in terms of their potential to catch the expected interference. Our findings highlight the importance of carefully considering these thresholds and the potential implications of their selection, which can vary based on the specific wireless networks in which they are applied.
* We conduct extensive experiments to verify the effectiveness of our proposed guideline for selecting the appropriate threshold. We demonstrate the neighbour-based threshold is preferable under the network density of interest. We show that by choosing a suitable neighbour-based threshold, the time complexity is reduced from \(\mathcal{O}(|\mathcal{V}|^{2})\) to \(\mathcal{O}(|\mathcal{V}|)\), where \(|\mathcal{V}|\) is the total number of transceiver pairs.
## II Preliminaries

### _System Model_

We consider a wireless communication network containing \(T\) transmitters, where they all share the same channel spectrum. We denote the index set for transmitters by \(\mathcal{T}=\{1,2,...,T\}\). For each \(t\) in \(\mathcal{T}\), we define \(\mathrm{D}(t)\) to be the index of the paired receiver. The received signal at the \(\mathrm{D}(t)\)-th receiver for any \(t\in\mathcal{T}\) is given by

\[y_{\mathrm{D}(t)}=h_{t,\mathrm{D}(t)}s_{t}+\sum_{j\in\mathcal{T}\setminus\{t \}}h_{j,\mathrm{D}(t)}s_{j}+n_{\mathrm{D}(t)},\quad t\in\mathcal{T}, \tag{1}\]

where \(h_{t,\mathrm{D}(t)}\in\mathbb{C}\) represents the communication channel between \(t\)-th transmitter and its intended \(\mathrm{D}(t)\)-th receiver, \(h_{j,\mathrm{D}(t)}\in\mathbb{C}\) represents the interference channel between \(j\)-th transmitter and \(\mathrm{D}(t)\)-th receiver. The transmitted data symbol for the \(t\)-th transmitter is represented by \(s_{t}\in\mathbb{C}\), while the additive Gaussian noise at the \(\mathrm{D}(t)\)-th receiver is modeled as \(n_{\mathrm{D}(t)}\sim\mathcal{CN}\left(0,\sigma_{\mathrm{D}(t)}^{2}\right)\). The signal-to-interference-plus-noise ratio (SINR) of the \(\mathrm{D}(t)\)-th receiver is expressed as follows:

\[\mathrm{SINR}_{\mathrm{D}(t)}=\frac{\left|h_{t,\mathrm{D}(t)}\right|^{2}p_{t} }{\sum_{j\in\mathcal{T}\setminus\{t\}}\left|h_{j,\mathrm{D}(t)}\right|^{2}p_{ j}+\sigma_{\mathrm{D}(t)}^{2}},\quad t\in\mathcal{T}, \tag{2}\]

where \(p_{t}=\mathbb{E}\left[|s_{t}|^{2}\right]\) is the power of the \(t\)-th transmitter, and we have the constraints \(0\leq p_{t}\leq P_{max}\), where \(P_{\max}\) is the maximum power constraint for transmitters. We denote \(\mathbf{p}=[p_{1},\cdots,p_{T}]\) as the power allocation vector. For a given power allocation vector \(\mathbf{p}\) and channel information \(\left\{h_{ij}\right\}_{i\in\mathcal{T},j\in\mathrm{D}(i)}\), the achievable rate \(\mathcal{R}_{\mathrm{D}(t)}\) of the \(\mathrm{D}(t)\)-th receiver is given by

\[\mathcal{R}_{\mathrm{D}(t)}(\mathbf{p})=\log_{2}\bigl{(}1+\mathrm{SINR}_{ \mathrm{D}(t)}\bigr{)},\quad t\in\mathcal{T}. \tag{3}\]

### _Optimisation Problem_

In this study, we address the problem of maximising the weighted sum-rate, a widely studied optimisation problem in the literature [2, 4, 5, 6]. The objective is to maximise the performance under maximum power constraints, which is formulated as,

\[\begin{array}{ll}\underset{\mathbf{p}}{\mathrm{maximise}}&\sum_{t}w_{t} \mathcal{R}_{\mathrm{D}(t)}(\mathbf{p}),\\ \text{subject to}&0\leq p_{t}\leq P_{\max},\quad\forall t\in\mathcal{T},\end{array} \tag{4}\]

where \(w_{t}\in[0,1]\) is the weight for the \(t\)-th transmitter.

## III Threshold-based

Graph Neural networks for power allocation

In this section, we propose a general guideline for selecting appropriate thresholds that achieves reasonably good performance while minimising complexity. Specifically, we provide recommendations in terms of their potential to catch the expected interference. We then formulate the proposed distance-based and neighbour-based graph representations and apply them to the GNNs for power allocation problems.

### _Traditional Graph Representation_

Generally, wireless networks need to be transformed into suitable graph representations in graph neural networks. The most common graph representation for power allocation in D2D networks is treating the transmitter and receiver pairs as a vertex [2]. The edge between the transceiver pairs can represent the interference between them (see Figure 1 as an example). Normally, this graph representation is a complete graph due to the existing interference between each transceiver pair. However, this representation method has several drawbacks. First, since unpaired transmitters and receivers are often spatially distant, this pair might have negligible effects on power allocation due to interference decay with distance. Besides, the complexity of GNNs depends on the total number of edges [2]. Therefore, this fully-connected graph would induce relatively high complexity compared to other graph modellings.

### _Motivation_

To address these issues, the distance-based threshold is first proposed in [2] to reduce the training workload of GNNs. The authors implemented the threshold to GNN based on the distance between the transmitter and the non-paired receivers. Similarly, the authors in [3] used the channel-based threshold to reduce the complexity by removing a neighbour of a transceiver pair if the CSI is smaller than the threshold. To explain the effect of threshold, an investigation of the trade-off between performance and complexity when thresholds are used is completed by [4]. Their simulation results showed that an appropriately chosen threshold reduces required training time by roughly \(20\%\) while preserving the performance. However, neither of them justifies their choice with theoretical analysis. To overcome this limitation, we systematically study appropriate threshold selection from a stochastic geometry perspective.

Alternatively, we also considered another threshold which is the neighbour-based threshold in GNNs to reduce the complexity while maintaining the good performance of the algorithm. The idea is instead of fixing the distance, we fix the total number of neighbours. For a specific transmitter, it only allows connecting the \(n\) nearest neighbours.

### _The Proposed Guideline for Choosing Appropriate Threshold_

Appropriate threshold selection is typically achieved by running algorithms for various densities and path-loss

Fig. 1: D2D Communication Network.
exponents. However, this approach is time-consuming due to the dynamic nature of wireless network environments. To address this challenge, we aim to find a good proxy for the appropriate threshold. We first derive a mathematical expression that models the relationship between the threshold and interference. Generally, we expect that the performance of the GNN will improve if it can capture more information about the interference in the network. However, increasing the amount of information captured also results in higher time complexity for the algorithm. To strike a balance between performance and computational efficiency, we hypothesise that if the algorithm can capture a significant proportion of the interference (e.g. \(95\%\)), then the resulting performance will be satisfactory for most practical applications.

Let us consider an infinite network, we randomly place transceiver pairs \(i\) to be the points of a Stationary Poisson Process \(\Phi\subset\mathbb{R}^{2}\) of intensity \(\lambda\)[7]. Denote \(r_{i}\) as the distance between \(i\)-th transceiver pair and the target pair. Assuming each transceiver pair is transmitting with unit power and the path loss is \(g(r)=\min\{1,(\frac{r}{d_{0}})^{-\alpha}\}\) with path loss exponent \(\alpha\) and reference distance \(d_{0}\). Here, we assume \(\alpha>2\) to ensure the expected interference is finite [8]. According to Campbell's Theorem [7], the expected interference for the target pair is

\[\begin{split} E[I]=& E[\sum_{i\in\Phi}g(r_{i})]= \lambda\int_{0}^{2\pi}\int_{0}^{\infty}g(r)rdrd\beta\\ =&\pi\lambda d_{0}^{2}+2\pi\lambda\cdot\frac{d_{0}^ {2}}{\alpha-2}=\pi\lambda d_{0}^{2}(1+\frac{2}{\alpha-2})\end{split} \tag{5}\]

where \(dr\) and \(d\beta\) represent differential elements pertaining to the radial and angular directions, respectively.

#### Iii-B1 Distance-based Threshold

Consider removing all the transceiver pairs \(i\) when the distance \(d_{i}\geq t\), where \(t\) is the distance-based threshold. Assuming the threshold \(t\geq d_{0}\), the expected interference \(E[I_{d}(t)]\) within this area with threshold \(t\) is

\[E[I_{d}(t)]=\pi\lambda d_{0}^{2}(1+2\frac{1-(\frac{t}{d_{0}})^{2-\alpha}}{ \alpha-2}) \tag{6}\]

The interference ratio \(A_{t}\) is defined as the expected interference resulting from applying a distance-based threshold \(t\) to the expected total interference. The expression is given by,

\[A_{t}=\frac{E[I_{d}(t)]}{E[I]}=\frac{\alpha-2(\frac{t}{d_{0}})^{2-\alpha}}{\alpha} \tag{7}\]

#### Iii-B2 Neighbour-based Threshold

For a specific transceiver pair, the probability density function (pdf) of the nearest neighbour within distance \(r\) is given by [8]

\[f_{R_{1}}(r)=2\lambda\pi re^{-\lambda\pi r^{2}}. \tag{8}\]

Therefore, the expected interference with only the closest neighbour is

\[\begin{split} E[I_{n}(1)]=&\int_{0}^{\infty}g(r)f_ {R_{1}}(r)dr=\int_{0}^{\infty}g(r)2\lambda\pi re^{-\lambda\pi r^{2}dr}\\ =& 1-e^{-\lambda\pi d_{0}^{2}}+d_{0}^{\pi}\int_{ \lambda\pi d_{0}^{2}}^{\infty}r^{-\alpha}e^{-t}dt\\ =& 1-e^{-\lambda\pi d_{0}^{2}}+d_{0}^{\pi}(\lambda\pi)^{ \frac{\alpha}{2}}\Gamma\Big{(}1-\frac{\alpha}{2},\lambda\pi d_{0}^{2}\Big{)} \end{split} \tag{9}\]

where \(\Gamma(s,\,x)=\int_{x}^{\infty}t^{s-1}e^{-t}dt\) is a incomplete gamma function. Similarly, the pdf for the distance to the \(n\)-th nearest neighbour (\(n\geq 1\)) is given by [8]

\[f_{R_{n}}(r)=e^{-\lambda\pi r^{2}}\cdot\frac{2\big{(}\lambda\pi r^{2}\big{)}^ {n}}{r(n-1)!} \tag{10}\]

Therefore, the expected interference with only \(n\)-th closest neighbour is given by

\[\begin{split} E[I_{n}(n)]=&\int_{0}^{\infty}g(r) \cdot f_{R_{n}}(r)dr\\ =&\int_{0}^{d_{0}}\!\!e^{-\lambda\pi r^{2}}\frac{2 \big{(}\lambda\pi r^{2}\big{)}^{n}}{r\cdot\Gamma(n)}dr+\int_{d_{0}}^{\infty}( \frac{r}{d_{0}})^{-\alpha}e^{-\lambda\pi r^{2}}\cdot\frac{2\big{(}\lambda\pi r ^{2}\big{)}^{n}}{r\cdot\Gamma(n)}dr\\ =& 1-\left(\sum_{i=0}^{n-1}\frac{(\lambda\pi r^{2})^{i} }{i!}\right)\!\!e^{-\lambda\pi d_{0}^{2}}+\frac{d_{0}^{\alpha}(\lambda\pi)^{ \frac{\alpha}{2}}}{\Gamma(n)}\Gamma\Big{(}n-\frac{\alpha}{2},\lambda\pi d_{0}^ {2}\Big{)}\end{split} \tag{11}\]

We define the interference ratio \(O_{n}\) as the expected interference with \(n\) closest neighbours to the expected total interference. The expression is given by,

\[O_{n}=\frac{\sum_{i=1}^{n}E[I_{n}(i)]}{\pi\lambda d_{0}^{2}(1+\frac{2}{\alpha -2})} \tag{12}\]

By systematically varying the path-loss exponents and intensities, we are able to determine the corresponding distances and neighbours required to achieve \(95\%\) interference, as detailed in Table I and Table II. Here, we consider the practical intensities up to 0.03 [9] and set 1 meter as the reference distance [10].

#### Iii-B3 The Proposed Guideline

To evaluate the relative strengths and weaknesses of distance-based and neighbour-based thresholds, we conducted a simulation using a Poisson point process with varying densities. The simulation was performed on a square area with dimensions \(B=10000m^{2}\), where the number of transceiver pairs was modeled as a Poisson random variable with mean \(\lambda B\)[11]. Once the number of transceiver pairs was determined, they were randomly distributed within the area. In our simulations, we selected theoretical distance-based and neighbour-based thresholds that could achieve a \(95\%\) interference ratio from Table I and II, and we recorded the variance of the total interference under both types of thresholds. The results for

\begin{table}
\begin{tabular}{|l|c|c|c|c|c|} \hline  & \(\alpha=3\) & \(\alpha=3.5\) & \(\alpha=4\) & \(\alpha=4.5\) & \(\alpha=5\) & \(\alpha=5.5\) \\ \hline \(\lambda=0.002\) & 2 & 1 & 1 & 1 & 1 & 1 \\ \hline \(\lambda=0.004\) & 3 & 2 & 1 & 1 & 1 & 1 \\ \hline \(\lambda=0.01\) & 5 & 2 & 2 & 1 & 1 & 1 \\ \hline \(\lambda=0.02\) & 9 & 3 & 2 & 2 & 2 & 2 \\ \hline \(\lambda=0.03\) & 13 & 4 & 2 & 2 & 2 & 2 \\ \hline \end{tabular}
\end{table} TABLE II: The number of nearest neighbours required to capture \(95\%\) of the total interference on average.
distance-based and neighbour-based thresholds are shown in Table III and Table IV, respectively. We observe that distance-based threshold tends to perform worse in low intensity since it has a larger variance. This is because when we fix the distance-based threshold value for every realisation, there exist some cases where none of the transceivers is within this area. Therefore, distance-based threshold fails to capture the dominant interference. The large variance also affects sum-rate performance which will be verified in Section IV. We also observed that neighbour-based thresholds perform relatively well in both low and high intensity. The neighbour-based threshold is preferable in wireless network optimisation because it guarantees that each target node will be able to connect with at least one neighbouring node. We found out the variance of the neighbour-based threshold is around 100 times smaller than the distance-based threshold in a lower intensity and higher \(\alpha\). Therefore, neighbour-based threshold is preferable at the intensity of interest.

### _Threshold-based Graph Neural Network_

In this subsection, we introduce graph representation of both distance-based and neighbour-based methods and the structure of proposed GNNs.

#### Iv-D1 Graph Representation

we define the set of vertices and edges of a graph \(G\) as \(\mathcal{V}\) and \(\mathcal{E}\), respectively. For any given vertex \(v\!\in\!\mathcal{V}\), its set of neighbours is defined as \(\mathcal{N}(v)\).

Let \(V_{v}\) and \(E_{v,u}\) represent vertex features of vertex \(v\) and edge features between vertex \(v\) and vertex \(u\), respectively.

With definitions in place, we define the vertex features of the vertices to be

\[V_{v}\!=\!\{h_{v,D(v)},\!w_{v},\!d_{v,D(v)}\} \tag{13}\]

where \(h_{v,u}\!\in\!\mathbb{C}\) and \(d_{v,u}\!\in\!\mathbb{R}\) are the channel coefficient and distance between \(v\)-th transmitter and \(u\)-th receiver, \(w_{v}\) is the weight for \(v\)-th transmitter. We define the edge features to be

\[E_{v,u}\!=\!\{h_{v,u},\!d_{v,u}\} \tag{14}\]

In the distance-based threshold method, \(v\) only connects \(u\) when the distance between them \(d_{v,u}\) is smaller than \(t(\alpha)\), where \(t(\alpha)\) is the appropriate distance-based threshold with path-loss exponent \(\alpha\). For example, as in Figure 2, the edge between vertex \(V_{2}\) to \(V_{3}\) indicates the distance between receiver \(\mathrm{D}(2)\) and transmitter \(T_{3}\) is within the threshold. In the neighbour-based threshold method, \(v\) only connects \(n\) closest neighbours, where \(n(\alpha\),\(\lambda)\) is the appropriate neighbour-based threshold with path-loss exponent \(\alpha\) and intensity \(\lambda\).

#### Iv-D2 The Structure of Graph Neural Network

An illustration of the distance-threshold-based GNN structure is shown in Figure 3. Our proposed GNNs consist of three steps: Pruning, Aggregation and Combination. First, the edges of a target vertex are pruned based on either distance-based or neighbour-based threshold. Then, the target vertex collects the information from its current neighbour. We adopt MLP for both aggregating information from a local graph-structured neighbourhood and combining its own features with the aggregated information. Besides, we use SUM operation to retain the permutation invariance property of GNN.

The updating rule of the proposed threshold-based GNN at \(l\)-th layer is given by

For distance-based threshold

\[\mathcal{N}(v)\!=\!\{u\!\in\!\mathcal{V}\!:\!d_{v,u}\!\leq\!t( \alpha)\} \tag{15}\]

For neighbour-based threshold

\[\mathcal{N}(v)\!=\!\{u\!\in\!\mathcal{V}\!:\!u\text{ is the $n(\alpha,\! \lambda)$ closest neighbours}\}\] \[\alpha_{v}^{\!(l)}\!=\!\mathrm{SUM}\Big{(}\Big{\{}f_{A}\Big{(}m_ {u}^{(l-1)},\!E_{vu}\Big{)},\!\forall u\!\in\!\mathcal{N}(v)\Big{\}}\Big{)},\] \[p_{v}^{(l)}\!=\!f_{C}\Big{(}\alpha_{v}^{(l)},\!m_{v}^{(l-1)}\Big{)},\]

where \(\alpha_{v}^{(l)}\) and \(m_{v}^{(l)}\!=\!\{V_{v},p_{v}^{(l)}\}\) represent the aggregated information from the neighbours and embedding feature vector of vertex \(v\), respectively.

The model includes two 3-layer fully connected neural networks, denoted by \(f_{A}\) and \(f_{C}\), respectively, with hidden sizes of \(\{6,16,32\}\) and \(\{36,16,1\}\), respectively. Here, \(p_{v}^{(l)}\) represents the allocated power for vertex \(v\) and we initialise the power \(p_{v}^{(0)}\!=\!P_{\max}\).

\begin{table}
\begin{tabular}{|l|c|c|c|c|c|c|} \hline  & \(\alpha\!=\!3\) & \(\alpha\!=\!3.5\) & \(\alpha\!=\!4\) & \(\alpha\!=\!4.5\) & \(\alpha\!=\!5\) & \(\alpha\!=\!5.5\) \\ \hline \(\lambda\!=\!0.002\) & 2.71 & 4.81 & 2.74 & 2.41 & 1.63 & 1.55 \\ \hline \(\lambda\!=\!0.004\) & 1.02 & 0.42 & 2.21 & 2.78 & 2.33 & 2.29 \\ \hline \(\lambda\!=\!0.01\) & 0.37 & 0.41 & 0.04 & 3.34 & 3.01 & 2.97 \\ \hline \(\lambda\!=\!0.02\) & 0.15 & 0.18 & 0.08 & 0.13 & 0.06 & 0.06 \\ \hline \(\lambda\!=\!0.03\) & 0.09 & 0.12 & 0.09 & 0.21 & 0.11 & 0.11 \\ \hline \end{tabular}
\end{table} TABLE IV: The variance of the interference for neighbour-based threshold.

\begin{table}
\begin{tabular}{|l|c|c|c|c|c|c|} \hline  & \(\alpha\!=\!3\) & \(\alpha\!=\!3.5\) & \(\alpha\!=\!4\) & \(\alpha\!=\!4.5\) & \(\alpha\!=\!5\) & \(\alpha\!=\!5.5\) \\ \hline \(\lambda\!=\!0.004\) & 0.97 & 1.90 & 2.83 & 5.52 & 21.05 & 23.12 \\ \hline \(\lambda\!=\!0.01\) & 0.25 & 0.39 & 0.50 & 0.34 & 1.48 & 2.47 \\ \hline \(\lambda\!=\!0.02\) & 0.10 & 0.19 & 0.19 & 0.22 & 0.46 & 0.98 \\ \hline \(\lambda\!=\!0.03\) & 0.06 & 0.12 & 0.12 & 0.14 & 0.28 & 0.58 \\ \hline \end{tabular}
\end{table} TABLE III: The variance of the interference for distance-based threshold.

Fig. 2: D2D Communication Network with distance-based threshold.
## IV Simulations and results

### _Simulation Setup_

We consider channels with large-scale fading and Rayleigh fading which the CSI is formulated as, \(h_{v,u}=\sqrt{g_{v,u}}r_{v,u}\), where \(g_{v,u}\!=\!\min\{1,\!(\frac{d_{v,u}}{d_{0}})^{-\alpha}\}\ r_{v,u}\!\sim\! \mathcal{CN}(0,1)\), \(\alpha\) is the path-loss exponent and \(d_{0}\) is reference distance. Here, we consider different intensities within a \(100\!\times\!100\ m^{2}\) area and use 1 \(m\) as the reference distance [10]. Following the similar simulation steps in Section III-C3, we randomly placed the transmitters from \(\{20,\!40,\!100,\!200,\!300\}\) within a designated area, where the expected intensity \(\lambda\) range from \(\{0.002,\!0.004,\!0.01,\!0.02,\!0.03\}\). Here, we consider the practical intensities up to 0.03 [9]. Then each receiver was placed at a random location between \(2m\) and \(10m\) away from the corresponding transmitter. To develop an effective power allocation strategy for our wireless network, we adopted the negative sum rate as our objective loss function, which can be expressed in (16).

\[L(\theta)\!=\!-\hat{\mathbb{E}}_{\mathbf{H}}\!\left\{\!\sum_{t\in\mathcal{T}}\!w _{t}\!\log_{2}(1\!+\!\frac{\left|h_{t,\mathrm{D}(t)}\right|^{2}\!p_{t}}{\sum_ {j\in\mathcal{T}\backslash\{t\}}\left|h_{j,\mathrm{D}(t)}\right|^{2}\!p_{j}+ \sigma_{\mathrm{D}(t)}^{2}})\right\} \tag{16}\]

In practice, we generate 10000 training samples for calculating the empirical loss, and we also generate 2000 testing samples for evaluation. We assumed that only partial CSI (a subset of full CSI) is available to the algorithms.

To validate the effectiveness of our proposed guideline, we conduct the experiments among the following four algorithms:

* Full-GNN [2]: This is state-of-art GNN algorithm for power allocation problem. It should be noted that the fully connected graph is used in this approach.
* D-GNN: Our proposed GNN when the distance-based threshold is applied.
* N-GNN: Our proposed GNN when the neighbour-based threshold is applied.
* WMMSE [5]: This is the advanced optimisation-based algorithm for power allocation in wireless networks, also see [2, 6, 12] for references.

### _Performance_

The distance-based threshold and neighbour-based threshold required that achieve a \(95\%\) normalised performance are shown in Table V and VI. Compared the simulation results with Table I and II, the theoretical guideline offers significant information. For distance-based threshold, our simulations show that the D-GNN requires \(14\) unit distance to achieve good performance. Notwithstanding, as outlined in Section III-C3, there is a significant variance in performance with respect to density. Our empirical findings also indicate that the N-GNN approach, as proposed, yields satisfactory performance even when restricted to the use of only six neighbours. This outcome is primarily attributed to the fact that the six nearest neighbours are typically responsible for the majority of interference under practical densities [9]. Consequently, a limited number of edges suffice to provide the requisite information for the GNN to allocate power effectively.

We conducted a further investigation into the effectiveness of the proposed guideline by setting the threshold to the values that capture \(95\%\) interference from Table I and II for both D-GNN and N-GNN. The sum-rate performance of all the algorithms is presented in Figure 4. The results indicate that N-GNN tends to perform better than D-GNN in all scenarios due to its flexibility in using neighbour-based threshold. It is noteworthy that Full-GNN achieves better performance by using all the available information, but it comes at the cost of increased time complexity as shown in Figure 5.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline  & \(\alpha\!=\!3\) & \(\alpha\!=\!3.5\) & \(\alpha\!=\!4\) & \(\alpha\!=\!4.5\) & \(\alpha\!=\!5\) & \(\alpha\!=\!5.5\) \\ \hline \(90\%\) & 7 & 7 & 7 & 7 & 7 & 7 \\ \hline \(95\%\) & 11 & 11 & 10 & 10 & 10 & 9 \\ \hline \(98\%\) & 14 & 13 & 13 & 13 & 12 & 12 \\ \hline \end{tabular}
\end{table} TABLE V: The unit distance required for GNN to achieve \(90\%\), \(95\%\) and \(98\%\) performance of WMMSE (\(d_{0}\!=\!1\)).

Fig. 3: The structure of distance-threshold-based GNN.

\begin{table}
\begin{tabular}{|c|c|c|c|c|c|c|} \hline  & \(\alpha\!=\!3\) & \(\alpha\!=\!3.5\) & \(\alpha\!=\!4\) & \(\alpha\!=\!4.5\) & \(\alpha\!=\!5\) & \(\alpha\!=\!5.5\) \\ \hline \(\lambda\!=\!0.002\) & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \(\lambda\!=\!0.004\) & 2 & 2 & 2 & 2 & 2 & 2 \\ \hline \(\lambda\!=\!0.01\) & 3 & 3 & 2 & 2 & 2 & 2 \\ \hline \(\lambda\!=\!0.02\) & 4 & 4 & 3 & 3 & 3 & 3 \\ \hline \(\lambda\!=\!0.03\) & 6 & 5 & 5 & 4 & 4 & 4 \\ \hline \end{tabular}
\end{table} TABLE VI: The number of nearest neighbours required for GNN to achieve \(95\%\) performance of WMMSE.
### _Time complexity_

The average running time for the algorithms under the same experimental setting is depicted in Figure 5. We observe that N-GNN has significantly lower complexity compared to Full-GNN. For instance, by selecting \(|V|\!=\!200\), N-GNN achieves a \(95\%\) optimal performance while reducing the required running time by roughly \(63\%\) compared to Full-GNN. This is due to the fact that the time complexity for each GNN layer is \(\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)\), which is dominated by \(|\mathcal{E}|\), and pruning the edges helps to reduce the complexity. To further investigate the time complexity of N-GNN and D-GNN, the running time for all algorithms when the performance achieves \(98\%\) of WMMSE is shown in Figure 6. We observe that D-GNN requires around \(40\%\) time more than N-GNN when \(T\!=\!250\). Furthermore, the observed time disparities are amplified with an increase in the number of transmitters.

In neighbour-based GNN, the total number of edges for each transceiver pair is fixed by the threshold \(n(\alpha,\lambda)\). Since the total number of edges \(|\mathcal{E}|\!=\!n(\alpha,\lambda)|\mathcal{V}|\), the time complexity for neighbour-based GNN with the threshold \(n(\alpha,\lambda)\) will be \(\mathcal{O}((1+n(\alpha,\,\lambda))|\mathcal{V}|)\). Therefore, we could reduce the time complexity from quadratic to linear with the number of transceiver pairs by introducing the neighbour-based threshold.

## V Conclusion

This research provides recommendations for selecting the appropriate threshold value in terms of their potential to catch the expected interference. We are the first to introduce a neighbour-based threshold approach to GNNs and show that by choosing a suitable neighbour-based threshold, the time complexity for GNNs is reduced from \(\mathcal{O}(|\mathcal{V}|^{2})\) to \(\mathcal{O}(|\mathcal{V}|)\), where \(|\mathcal{V}|\) is the total number of transceiver pairs.
