Power Allocation for Device-to-Device Interference Channel Using Truncated Graph Transformers ^††thanks: This work was supported by The Hong Kong University of Science and Technology (HKUST) Startup Fund under Grant R9249.

Consider a single-input single-output (SISO) ad hoc interference network with $n$ transmitter-receiver pairs. Denote $h_{ij}$ to be the channel coefficient between transmitter $i$ and receiver $j$, $p_{i}$ as the power allocated to transmitter $i$, and $\sigma^{2}$ as the additive white Gaussian noise (AWGN) power level. The channel rate of the $i$-th transmitter-receiver pair can be expressed as:

The design objective is to maximize the sum rate across all pairs under the maximum power constraint. Additionally, each pair would have a weight $w_{i}$ on the channel rate to enforce priority or fairness across devices. The constrained weighted sum rate maximization problem can be written as:

Our goal is to find a data-driven model that determines the maximizing power $\textbf{p}\in\mathbb{R}_{+}^{n}$ given an instantiated channel state $\textbf{H}\in\mathbb{R}_{+}^{n\times n}$with $\textbf{H}_{i,j}=h_{ij}$ and noise power $\sigma^{2}$.

GNN is a family of neural network architectures designed to be trained on graph data structures. A single pass of a GNN layer consists of three stages: message formulation, neighbor aggregation, and feature update. The message formulation function $m(\cdot)$ creates a message feature vector, generally using the corresponding node embedding $\textbf{x}_{i}$ and edge embedding $\textbf{e}_{ij}$. Neighbor aggregation $\bigoplus$ is a symmetric operation across all neighbors of a specific node, which grants permutation invariance to the input sequence. $j\in\mathcal{N}(i)$ is a set of nodes that are connected with node $i$ in the graph. Generally, these would be summation, average, or maximum, but any other symmetrical operations would suffice. The authors of [10] discussed the efficacy for various candidates, and showed that no specific operation is superior and subject to case by case identification. Finally, the feature update $\sigma(\cdot)$ takes both the aggregated message and its node feature embedding to compute the new embedding for node i.

Note that if $\bigoplus$ is a sum operation, this is equivalent to multiplying the node feature matrix $\textbf{X}\in\mathbb{R}^{n\times d}$ with the adjacency matrix $\textbf{A}\in\mathbb{N}_{0}^{n\times n}$, where the value of $\textbf{A}_{ij}=1$ if node i and j are connected, and 0 otherwise. In this case, we can imagine a basic message passing GNN as a masked linear layer in relation to the adjacency matrix. Various architectures of GNN have been utilized in the literature for the power allocation problem. The authors of [4] proposed a GNN to accelerate WMMSE, and [5] utilized a message passing GNN where the message is generated with concatenated node and edge feature embeddinigs .

While GNNs show better expressitivity in graph data, they have their limits. The limit relevant to our problem formulation is their strong bias on homophily, which means nodes connected with each other will have the same label. Detailed analysis in regards to the power control problem will be discussed in Section V-C.

Transformer is another family of neural network architectures that was developed for NLP problems [11]. Its attention mechanism was devised to circumvent the problem of gradient vanishing in long sentences. Information of words at the start of the sentence would not pass through the model when inferring on the words on the later part. Attention solves this by placing a soft weight on all words in the sentence for each step, which is calculated on run-time. The attention map is calculated using a query, key, and value matrix. If the model has an input feature vector $\textbf{x}_{\textbf{i}}\in\mathbb{R}^{n\times f}$, the attention module would contain linear weight $\textbf{W}_{\textbf{q}}\in\mathbb{R}^{d\times n},\textbf{W}_{\textbf{k}}\in\mathbb{R}^{d\times n},\textbf{W}_{\textbf{v}}\in\mathbb{R}^{d\times n}$ which would compute the feature matrix $\textbf{Q},\textbf{K},\textbf{V}\in\mathbb{R}^{d\times f}$. When multiple attention modules are stacked, this is called a multi-head attention. The attention module could be expressed as:

Because attention is individually computed for each word, and the matrix multiplication of the attention weights to the value matrix is equivalent to a sum neighbor aggregation, transformer models are inherently permutation invariant. Note that the input that generates the Q ,K, and V can be from different input vectors. This is called cross-attention, which would be used for our proposed method as the query comes from the target node, and the keys and values come from the neighboring nodes.

Transformers take a sequence input of arbitrary length and compute a permutation invariant operation. This can be alternatively viewed as a GNN on a fully connected simple graph. The authors of [9] generalized the transformer to a GNN framework, named graph transformers. Details of the structure is nearly identical with the original self attention, but the difference comes from how the input data is handled. Here, the queries and keys are generated from the corresponding node embeddings, and the attention is mapped across the neighbors. A possible integration of edge feature vector to the process is also introduced.

We revise the graph transformer architecture discussed in [9] for better convergence on the power allocation problem. Fig. 1 illustrates the proposed model. First, both the node and edge features are passed through a fully connected layer with batch normalization into a higher dimension embedding with dimension $d$. The embedding is then fed through a multi-head cross attention 3-layer model defined as:

In this section, we attempt to explain why TGT outperforms basic GNNs by showing that the power control problem with low noise is heterophilous. Graph homophily is an index that measures whether a node with an adjacent edge would have the same label. We start with the index definition by [14]:

Where $||^{\textbf{1}}$ is a function that returns 1 if the two values are the same, and $d_{i}$ is the degree of node $i$. $h$ would map to a value $[0,1]$, where 1 represents that the graph is highly homophilic. Citation graphs or relation graphs are known to be homophilic, as papers with similar topics would be cited together and similar people will be in a closer relationship. GNNs are known to better perform in homophilic datasets, which is due to their neighbor aggregation design on a fixed graph structure. The author of [15] showed that when removing the non-linearity of the GNN, it can be abstracted into a Chebyshev low pass filter on the graph, which indicates that the performance gained from utilizing GNNs may not be from the non-linear feature extractions. In order to circumvent this issue, researchers are exploring more sophisticated GNN architectures that include sub-graph information [16], sheaf diffusion [17], and mapping the graph into a hyperbolic space [7].

Due to the network modeled in the problem formulation is a fully connected graph with a scalar edge weights and power allocation, we expand the definition of graph homophily for a graph with scalar edge weight $e_{ij}$ and node label $x_{i}\in[0,1]$ as:

Graph Network Transformers are more resilient to heterophilous datasets due to the attention weights acting as active graph rewiring. The wireless network is formulated as a graph with soft neighbor connections, in which every node is connected with a scalar weight associated to it. By applying attention to each neighbors, the model is effectively rewiring the graph each layer, avoiding the over smoothing issue of GNNs when aggregating with a fixed graph topology.

We perform experiments on a simulated SISO D2D network over an AWGN channel of fixed noise $\sigma^{2}=2.6\times 10^{-5}$. $n$ transmitters are uniformly distributed on a square plane with range $[-n,n]^{2}$, where the receiver is placed within the distance of $[1,n/4]$ around the target transmitter. A lower bound on the receiver location is placed to prevent numerical instability when calculating the path gain. The channel is constructed with a constant path-loss defined as $h^{p}_{ij}=||t_{i}-r_{j}||^{-2.2}$, where $t_{i},r_{j}$ are the coordinates of the corresponding transmitter and receiver. We then multiply with the large-scale channel coefficient coefficient $h^{f}_{ij}\sim\text{Rayleigh}(1)$. This specific problem setting has been used across various data driven power allocation publications, and has been chosen here for ease of comparison across different methods [4, 6]. We assume equal weight $w_{i}=1$ for all pairs.
For all data-driven benchmarks, the models were trained on a dataset of 25,000 network instances, which consists of 50 randomly sampled channel states on a 500 randomly sampled network topology. For the data-driven benchmarks, published configurations for model dimension and training strategies were retained, but the learning rate were adjusted so that the model could stably converge due to difference in simulated conditions. Then the model was tested on previously unseen 1000 network instances with 50 randomly sampled channel states on 50 randomly sampled network topologies.

The proposed model, TGT, is a 3 layer graph transformer model with 32 head attention, where the embedding dimension $d=64$. As the channel $h_{ij}$ is a near zero value, we normalize the channel matrix H to a range of $[0,1]$. The model was trained using a AdamW[18] optimizer with learning rate set to $5\times 10^{-4}$. All models were trained for 50 epochs. The channel state H needs to be represented as a graph data to be processed by a GNN. For our method, we convert H to an undirected graph $G$ with $n$ nodes. In particular, $G$ is a fully connected graph with self loops where feature vector of the $i$-th node and the $ij$-edge are given by $\textbf{x}_{i}^{0}=[h_{ii},w_{i}]\in\mathbb{R}^{2}$ and $\textbf{e}_{ij}=[h_{ij},h_{ji}]\in\mathbb{R}^{2}$, respectively. Implementation details can be accessed through the github repository [19].

We perform numerical comparison across the following benchmarks:

• •

  Max Power is a naive strategy where all transmitters transmit maximum power $P_{max}=1$.

• •

  WMMSE[3] acts as a baseline for the classical method, which is run for 100 iterations.

• •

  PCGNN[5] utilizes a variant of a GNN with its edge weights embedded onto the message. It achieves state-of-the-art performance on complex interference channels.

• •

  UWMMSE[4] is a model-driven approach that utilizes GNNs to accelerate the conversion of WMMSE with only 4 iterations. It achieves state-of-the art performance on a fixed network topology.

• •

  Graph Trasformer [9] is run with the same number of layers, heads, and $d$ to compare with the proposed method. Note that this model has 173K trainable parameters, while ours only have 13.1K.

Table II shows the comparison across various number of pairs. Each data-driven model is trained only on the dataset with the corresponding network size. Multi-node is a single model that was trained on a even distribution of network size of $\{20,30,40,50\}$, with the same number of samples as mentioned above. The proposed method outperforms all methods across various network sizes for both fixed node training and multi-node training. As the training dataset only contains 50 channel instances, we do further comparison of the models on a fixed network topology with 32,000 randomly sampled channel fading. Fig. 2 shows that the proposed method follows a similar distribution curve as WMMSE, with a consistent advantage on all range of channel instances.

While deep learning models outperform classical algorithms with lower computational complexity, it’s performance is only guaranteed within the training data distribution, and thus must be tested with its generality across unseen data distributions to understand when to retrain the model. We test the model’s generality across network size, fading distribution, and pair density. We then compare the computational complexity, and provide analysis on the relationship between model size and generality.

In Table II, each model was trained only on a fixed number of $n$. We compare how our model performs across a sweep of network sizes, ranging from 20 to 100 pairs. 10 channel instances are sampled for each 100 random network topologies. Fig. 3 shows the result across three different plots $n=30,50$ and multi-node model, where the sum-rate is normalized with WMMSE for ease of comparison. A taper of performance is clearly visible from the model’s trained network size, but the model is able to outperform WMMSE even outside of the trained pair size. However, we can see that the multi-node model has a more stable performance drop off, performing better on average than fixed size training. This shows the model should be trained on the expected data distribution of the deployed scenario, to prevent frequent retraining of the model.

We now consider a scenario where the fading coefficient of the Rayleigh fading changes. Using the same configuration as in Table II, Table III shows that the proposed model generalizes well from its original fading coefficient 1, outperforming WMMSE up to a fading coefficient of 4 for both fixed model and the multi-node model.

While the model is able to generalize across multiple network size and fading coefficients, the proposed method struggles when the overall density of the network changes from the training data. We test the proposed model on a fixed pair network of $n=50$, but change the the distribution of transmitters from $[-n,n]^{2}$ to $[-n/r,n/r]^{2}$, where $r\in[0.25,4]$. Table IV shows the model struggles to generalize on deviation from the trained pair density. Note that the model still out perform WMMSE when trained on the different density data.

One advantage of data-driven models over iterative classical algorithms is their simpler computational complexity. WMMSE is known to be run on $O(KN^{3})$ time, where N is the number of pairs and K is the number of iterations. Like all other GNN based models, the proposed model has a computational complexity of $O(LFN^{2})$, where L is the number of layers, F is the dimension of the linear weights, and N is the number of pairs. Since the computational complexity rely on the model parameter, we compare how the proposed model performs across various number of parameter size. We compare the model with various widths from $d=[4,104]$, in which the model parameter ranges from 960 to 33.7K. Fig. 4 compares the performance of the proposed model trained on a fixed pair size of $n=30$. For the different parameter sizes, we retain the original ratio of the hidden layers dimensions and scale accordingly while keeping the training conditions same as Section IV-A. The proposed method outperforms WMMSE already at the parameter size of 3.5K, and seems to converge at the parameter size of 13K. Graph transformer achieves equivalent performance with ten times more parameters.

While the proposed model outperforms WMMSE at a smaller parameter size, this comes with a price of generality. Fig. 5 shows that models with smaller parameters fail to generalize to unseen network configurations while models with larger parameters have a slower drop off. Thus, there is a trade-off of computational simplicity and model generality, which decides the frequency of retraining required once the deployed network deviates from its trained data distribution.