Task-Oriented Communication for Graph Data: A Graph Information Bottleneck Approach
Shujing Li Yanhu Wang Shuaishuai Guo Chenyuan Feng




Task-Oriented Communication for Graph Data: A Graph Information Bottleneck Approach
     Shujing Li, Yanhu Wang, Shuaishuai Guo,  Senior Member, IEEE, and Chenyuan Feng,  Member, IEEE
 Shujing Li, Yanhu Wang and Shuaishuai Guo are with School of Control Science and Engineering, Shandong University, Jinan 250061, China and also with Shandong Key Laboratory of Wireless Communication Technologies, Shandong University, Jinan, Shandong, P. R. China (e-mail: lishujing777@mail.sdu.edu.cn, yh-wang@mail.sdu.edu.cn, shuaishuai_guo@mail.sdu.edu.cn).
Chenyuan Feng is with Department of Communication Systems, EURECOM, Sophia Antipolis 06410, France (e-mail: Chenyuan.Feng@eurecom.fr).
    Received 2024; accepted 2024
===================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT  

Graph data, essential in fields like knowledge representation and social networks, often involves large networks with many nodes and edges. Transmitting these graphs can be highly inefficient due to their size and redundancy for specific tasks. This paper introduces a method to extract a smaller, task-focused subgraph that maintains key information while reducing communication overhead. Our approach utilizes graph neural networks (GNNs) and the graph information bottleneck (GIB) principle to create a compact, informative, and robust graph representation suitable for transmission. The challenge lies in the irregular structure of graph data, making GIB optimization complex. We address this by deriving a tractable variational upper bound for the objective function. Additionally, we propose the VQ-GIB mechanism, integrating vector quantization (VQ) to convert subgraph representations into a discrete codebook sequence, compatible with existing digital communication systems. Our experiments show that this GIB-based method significantly lowers communication costs while preserving essential task-related information. The approach demonstrates robust performance across various communication channels, suitable for both continuous and discrete systems.







Task-oriented communication, graph neural network, graph information bottleneck, vector quantization.





§ INTRODUCTION
 
In the swiftly changing realm of communication systems, marked by the emergence of 5G and its advancements, an increasing demand arises for efficient and smart communication frameworks capable of adjusting to intricate and ever-shifting environments. Conventional communication systems concentrate on enhancing metrics such as throughput and latency, frequently neglecting the distinct needs of task-oriented communications. In task-oriented scenarios, the objective extends beyond the mere effective transmission of raw data; it aims to optimize the performance for specific tasks like classification, prediction, or decision-making. It is worth noting that in addition to Euclidean data such as images and text, there are vast amounts of non-Euclidean data generated in social networks, biological networks, transportation networks and recommendation systems, etc. <cit.> This graph-structured data has no order or coordinate reference points, and is difficult to represent in a grid-like matrix or a tensor. A graph is usually composed of nodes and edges, which contain rich relational information. We can regard the graph data as a web of relationships, wherein the nodes are the subjects and the edges represent the relationships between the nodes. This feature makes graph an effective tool for modeling complex relationships in various non-Euclidean data scenarios <cit.>. 

Graph data is widely applied to knowledge representation, recommendation systems, and user behavior analysis <cit.>. However, the inherent complexity and size of graph data can pose challenges for transmission and storage. A complete graph, which contains all possible relationships between the nodes, is often not suitable for direct transmission due to the substantial bandwidth and storage resources required. Moreover, a complete graph tends to contain redundant information, leading to unnecessary resource consumption. In many practical applications, only specific task-related information within the graph needs to be transmitted to accomplish particular objectives. Additionally, graph data might contain sensitive information or personal privacy that should be safeguarded during transmission. Transmitting the entire graph increases the risk of information leakage. Therefore, an intelligent and concise communication system is needed to transmit graph data effectively. Within this context, the Graph Information Bottleneck (GIB) stands out as an innovative strategy to tackle these challenges. It draws upon the principles of information theory and graph neural networks to craft solutions. Central to this approach is the compression of transmitted information, ensuring that it retains only the most pertinent features relevant to the task. This targeted compression facilitates a more efficient and impactful mode of communication.



 §.§ Related Works

Task-oriented communication is a promising solution for graph data transmission. Different from traditional communication, it focuses on the accurate transmission of task-relevant information, rather than the bit-level precise transmission  <cit.>. Its characteristics align well with our demands for graph data transmission. It is difficult to characterize or extract task-related information with mathematical models, and the existing task-oriented communication systems mainly rely on deep learning technology <cit.>. That is, the neural networks (NNs)-based encoder and decoder are constructed and trained, so that the task-oriented communication system obtains the ability to extract task-relevant information <cit.>.

Precisely, Farsad et al. proposed a neural network architecture for text transmission task, that combines joint source-channel coding (JSCC) with recurrent neural network (RNN) based encoder, binarization layers, channel layers, and RNN-based decoder <cit.>. Xie et al. introduced a system for textual semantic restoration tasks based on Transformer model <cit.>. Their approach focuses on maximizing system capacity while minimizing semantic errors by restoring the meaning of sentences. Guo et al. proposed to utilize pre-trained language models to quantify the semantic importance of text and allocate unequal power based on semantic importance <cit.>. Some JSCC methods map image pixel values directly to input representations to achieve high-quality image reconstruction tasks <cit.>. Kang et al. proposed an image transmission method specifically designed for scene classification tasks <cit.>. Shao et al. developed a task-oriented communication scheme for edge inference using the information bottleneck (IB) <cit.>. Their scheme aims to improve the performance of image classification task at the edge server by efficiently transmitting relevant information. These NNs-based task-oriented communication systems have achieved outstanding outcomes, demonstrating  the capacity to effectively execute specific tasks.



 §.§ Motivation & Contributions

However, these works cannot be directly used for graph data transmission.
Because they are based on CNNs or fully connected networks and deal with regular data such as text (represented as sequences of characters) and images (represented as continuous two-dimensional or three-dimensional pixel sets).
Graph data exhibits a more intricate structure, which is composed of nodes and edges with attribute information.
When transmitting graph data, it is important to consider the efficiency of transmitting large-scale graph data while accurately preserving the correlation between nodes and edges <cit.>.
Therefore, it is necessary to design a new task-oriented communication system for graph data transmission.
Using information bottleneck theory to develop task-oriented communication systems is a good option <cit.>.
Because IB theory aims to find an optimal intermediate representation that can retain important information in the input data to ensure the accuracy of the output prediction while eliminating redundant information <cit.>. 

However, it should be noted that the direct utilization of IB-based frameworks in graph data processing is not feasible. This is because the IB framework assumes that the data follows an independent identically distributed (IID) pattern.
Whereas in graph data, the presence of edges and their attributes results in the data points being dependent on one another, which makes the graph data deviate from the IID assumption <cit.>. 





Recently, an information-theoretical design principle for graph data, named GIB, has been developed, which seeks the right balance between data compression and information preservation for graph data<cit.>. Specifically, employing GNNs[GNN is a deep learning model specifically designed to work with graph data.  In contrast to traditional deep learning models primarily handling vectorized data, GNNs excel at capturing intricate relationships within graphs, involving nodes and edges<cit.>. The fundamental principle of GNNs is to gradually aggregate local neighborhood information by iteratively updating the representation of nodes<cit.>. Typical GNN models include Graph Convolutional Networks (GCNs), Graph Isomorphism Network (GIN), Graph Attention Networks (GATs), etc.] as the foundational framework for graph data processing, GIB works well. Through the process of learning and parameter adjustments, GIB ensures the preservation of only task-relevant information while simultaneously compressing extraneous data.
One of the challenges in studying graph information bottleneck, i.e., how to handle the interdependencies between nodes in graph data, is the non-IID character of graph data. One of the primary technical contributions of our research is task-oriented transmission, which we will further optimize for.

In addition, the actual widespread use of digital communication systems makes the realization of compatibility between task-oriented communication systems and digital communication systems a necessity.
Thus, there is a requirement to identify a suitable digitization mechanism for communication systems geared towards graph data, ensuring both effective data compression and robustness. Vector quantization (VQ) emerges as a powerful technique that addresses these needs by mapping high-dimensional data into a finite set of lower-dimensional codewords. This process not only facilitates significant data compression but also enhances the system's robustness against noise and transmission errors. Furthermore, by integrating with deep learning, VQ is highly adaptive and can be dynamically adjusted to different data distributions and channel conditions.






Motivated by these issues, we design GIB-enabled task-oriented communication systems for graph data in this work. Our main contributions are summarized as follows:


    
  * We introduce GIB into a task-oriented communication system for graph data. We build a Markov chain model for information transmission and formulate an optimization problem to maximize the mutual information between the task target and received codewords while minimizing the mutual information between the received codewords and the raw graph data. This approach balances the preservation of critical information in the extracted features while eliminating redundant information, thereby enhancing task success rates and reducing communication overhead.
    
  * To address the difficulty of handling mutual information terms in GIB due to high-dimensional integration, we use the Mutual Information Neural Estimator (MINE) to directly estimate the mutual information between the original graph and the subgraphs. This approach overcomes the challenge of obtaining the prior distribution of the subgraphs in applying variational approximation methods.
    
  * Recognizing the importance of topological information in graph data, particularly in revealing community structures, we introduce a connectivity loss term into the objective function. This term leverages topological information during feature extraction, reduces fluctuations in ambiguous node assignments, and contributes to a more stable training process.
    
  * We map the resulting subgraph representation onto a jointly trained codebook to generate a discrete index sequence for transmission.  This mapping ensures compatibility with existing digital communication systems.  Experimental results show that the system is able to achieve higher compression rates while achieving task success rates comparable to traditional digital communication methods.





 §.§ Organization

The subsequent sections of this paper are organized as follows.
In Section 2, we outline the system model, describe the structure and design objectives of the task-oriented communication system for graph data. Section 3 introduces the details of GIB-enabled task-oriented communication systems for graph data, including the handling of GIB objectives and the system training strategy. Section 4 presents our proposed approach for digitizing the task-oriented communication system. In Section 5, we evaluate the performance and effectiveness of the proposed method through experiments. In Section 6, potential applications of the proposed method in practical scenarios are discussed. Finally, we make a brief summary of this paper in Section 7.




 §.§ Notations

In this paper, a graph with m nodes is defined as g or G=( V,E,A,𝒳), where V={V_i|i=1,2,...,m } is the set of nodes with cardinality m, E={( V_i,V_j)|i<j,V_iandV_j areconnected } is the edge set, A={ 0,1 }^m× m is the adjacent matrix, and 𝒳∈R^m× d is the feature matrix corresponding to V with feature dimension d. The pair ( G,Y ) stands for the graph data and its target variable. 
The entropy of Y is defined as H( Y ). The mutual information between X and Y is represented as I( X,Y ). 

 



§ SYSTEM MODEL AND PROBLEM DESCRIPTION



 §.§ System Model

In this paper, we consider a task-oriented communication system for graph data as shown in Fig. <ref>. The system mainly includes a transmitter and a receiver, where the transmitter consists of a feature extractor implemented by a GNN and a joint source-channel (JSC) encoder. The receiver is a neural network used for task inference. Given an input graph g, they cooperate to perform tasks to make the inference output ŷ consistent with the true target variable y.
The random variables (G, Y) together with the encoded codeword X and the channel-corrupted codeword X̂ form the following probabilistic model:


    ( Y )G → X →X̂→Ŷ,

which satisfy p( ŷ|g )=p_θ( ŷ|x̂)p_channel( x̂|x )p_ϕ( x|g ).
Herein, the lowercase letters g, x, x̂, y, and ŷ denote realizations of the variables represented by the corresponding uppercase letters.
p_ϕ( x|g ) represents the transmitter neural network parameterized by adjustable parameters ϕ.
For a given input graph g, the feature encoder identifies the representation x related to the task. The task-relevant features are encoded by the JSC encoder and then transmitted to the receiver through the channel. 

To accommodate both continuous channels and discrete channels within this framework, we introduce an indicator variable ζ that distinguishes between the channel types: ζ=0 for an continuous channel and ζ=1 for an discrete. The conditional probability distribution p_channel( x̂|x ) is thus defined as:

    p_channel(x̂|x; ζ) =
    1/√(2π N_0)exp(-(x̂-x)^2/2N_0),    if ζ = 0 
    
        P_X̂|X(x̂|x).    if ζ = 1

where we assume that the continuous channel is the additive white Gaussian noise (AWGN) channel and the discrete channel is the Symmetric Discrete Channel (SDC). 

AWGN is implemented using an untrained neural network layer, and the transfer function is expressed as:


    x̂=x+ϵ,

where the Gaussian noise ϵ∼𝒩( 0,N_0/2).

For SDC, P_X̂|X(x̂|x) signifies the transition probability matrix, encapsulating the likelihood of transitioning from input to output symbols.
The SDC model assumes that both channel inputs and outputs utilize the same symbol set, with each symbol corresponding to an identical output probability distribution. This probabilistic behavior is succinctly captured by a transition matrix:

    𝒫=[ ε   1-ε/r-1   ⋯   1-ε/r-1
    1-ε/r-1   ε   ⋯   1-ε/r-1
    ⋯   ⋯   ⋯   ⋯
    1-ε/r-1   1-ε/r-1   ⋯   ε
    ]_r× r,

where ε represents the probability of correct symbol transmission and 
r denotes the cardinality of the channel symbol set. Potential transmission errors could lead to the receiver retrieving incorrect vectors, impacting the inference task.


The conditional distribution p_θ( ŷ|x̂) stands for the task inference network parameterized by adjustable parameters θ at the receiver.
 It deduces the class label ŷ  based on x̂ based on the channel-corrupted codeword x̂.





 §.§ Problem Description

The effectiveness of task execution is intricately linked to the dimension of the feature vector produced by the transmitter. For instance, in the context of graph classification tasks, a higher dimension of the feature vector could lead to an elevated classification accuracy. However, this advantage comes at the cost of increased communication overhead. Thus, the challenge is to identify a concise and informative representation that aligns with the optimal subgraph.
To formalize this trade-off, we formulate the following objective function based on the GIB principle:

    ℒ_GIB=-I( Y,X̂)+β I( G,X̂),

in which I(Y,X̂) represents the mutual information capturing the relevance of task-specific information in the received codeword, I(G,X̂) represents the preserved information in X̂ given G, and β acts as a trade-off factor governing the relationship between the two.

Developing task-oriented communication based on GIB is a promising approach to solving the graph transmission challenges. 
This approach offers an information metric for the graph data and can effectively capture node and edge information.  However, there are a few noteworthy problems:



  * Problem 1: How to deal with mutual information containing graph data to get a tractable objective function?

The expansion of the first term in (<ref>) yields:

    I( Y,X̂)=    ∫ p(y, x̂) logp(y, x̂)/p(y) p(x̂) d y d x̂
    
    =    - ∫p(y,x̂)log p(y)dydx̂_H( Y )=constant
        + ∫p(y,x̂)log p(y|x̂)dydx̂,

where the first term of the second equation is the entropy of Y. For a given graph and a given task, the entropy of Y is determined, so this term can be regarded as a constant and can be ignored in subsequent optimization. Therefore, we can obtain the expression for (<ref>) in the optimization implication:

    I( Y,X̂) = ∫p(y,x̂)log p(y|x̂)dydx̂.


The joint distribution p( g,y ) for graph data and target labels is known. p_ϕ( x̂|g ) is determined by the transmitter network p_ϕ( x|g ) and channel model p_channel( x̂|x;ϵ). For the second integral term, we derive according to the Markov chain:

    p(y |x̂) =∫p(g,y) p_ϕ(x̂| g)/p(x̂) d g,




Next, we address the second mutual information term of (<ref>) and expand it:

    I( G,X̂)=∫p(x̂| g)p(g)logp_ϕ(x̂| g)/p(x̂)dgdx̂,

where p(x̂) is also an intractable high-dimensional integral:

    p(x̂) =∫ p(g) p_ϕ(x̂| g) d g.

It is customary in IB to substitute this marginal distribution with a tractable prior distribution<cit.>. In GIB, finding a suitable variational prior is difficult. This is because of GIB's interpretation of p(x̂): it represents the distribution of irregular subgraph structures, not just a latent graph data representation. Moreover, due to the non-IID nature of graph data, finding a simple function as a prior distribution is not feasible.
Therefore, a new method is needed to estimate that mutual information.



  * Problem 2: How to utilize topological information in graph data for communication tasks?


By designing a feature extractor  based on GIB theory, it becomes possible to selectively extract task relevant information, reducing redundancy and improving efficiency. Yet, when GNNs extract features from graph data, they often concentrate too much on nodes and neglect the graph's structural features.
However, for many tasks, the crucial information is deeply rooted in the graph's topology. Therefore, in the process of feature extraction, it is necessary to consider the topological structure of the graph. 
To do this, we need to impose constraints on the feature extractor to improve the role of topological information in feature extraction. 




  * Problem 3: How to be compatible with digital communication systems?

While the proposed task-oriented communication system effectively addresses the challenge of graph data transmission, its use of continuous signals poses compatibility issues with existing digital communication systems.  Given the well-established infrastructure of digital communication systems, it is impractical to abandon it completely.  Therefore, it is necessary to develop a task-oriented communication system compatible with the digital communication system to transmit graph data.









§ GIB-ENABLED TASK-ORIENTED COMMUNICATION


In this section, we develop a task-oriented communication system based on GIB theory. Specifically, we combine variational approximation and MINE techniques to improve the GIB formulation <cit.>.
This modification enables a more streamlined optimization process employing neural networks, which solves Problem 1. In addition, we describe the process of feature extraction in detail and also node assignment, including the network configuration and the pertinent revision made to the objective function, which solves Problem 2.



 §.§ Graph Information Bottleneck Reformulation

To solve Problem 1,
we introduce the variable distribution q_θ( y|x̂) as a substitute for the true posterior distribution p( y|x̂). θ represents the parameter of the inference neural network in the receiver computing the inference output ŷ. Consequently, (<ref>) is transformed into:

    I( Y,X̂)     = ∫p( y,x̂)logq_θ( y|x̂)dydx̂
        =E_p( y,x̂)[ logq_θ( y|x̂) ].

Subsequently, Monte Carlo sampling is used to derive the empirical distribution of the joint distribution as an approximation. N samples are taken for the given data, that is:

    p( y,x̂)≈1/N∑_i=1^Nδ_y( y_i)δ_x̂( x̂_i).

Here, δ( ·) denotes the Dirac function utilized for sampling the training data. y_i and x̂_i represent the label and representation received by the receiver for the i-th training data, respectively. This approximation leads to a tractable optimization objective from (<ref>):

    ℒ_inf( q_θ( y|x̂) ) = -1/N∑_i=1^Nlogq_θ( y_i|x̂_i).


Minimizing the objective function in (<ref>) is consistent with maximizing I( Y,X̂) and minimizing ℒ_inf.
This function is defined as the loss between the inference result Y and the ground truth for the received x̂. A smaller loss signifies superior performance of the inference neural network.


About the second mutual information term I( G,X̂) of (<ref>), indicating the transmission informativeness, we employ the MINE to directly approximate it without the need to estimate p(x̂). We express this term in the form of Kullback-Leibler (KL)-divergence:

    I( G,X̂)=D_KL[ P( G,X̂)||P( G )⊗ P( X̂) ].

For ease of analysis and mathematical treatment, we adopt the Donsker-Varadhan representation of KL-divergence, which expresses the mutual information term as the difference between the expected value and the logarithmic expected value:


    I( G,X̂)   = T:G×X̂→ℝsup E_P( G,X̂)[ T ]-logE_P( G )P( X̂)[ e^T]
       = ℒ_MI( T ),

in which T=f_κ( g,x̂) encompasses all functions that render two expectations finite. The MINE can be used to estimate the mutual information between regular input data and its vector representation. Due to the irregularity of graph data, GNN is employed to extract the vector representation before feeding it into the multi-layer perceptron (MLP) for processing alongside the representation X̂. f_κ( ·) serves as the statistics network, denoting the neural network that executes the process of obtaining the corresponding real numbers from G and X̂. The optimization of this estimator involves adjusting the MINE parameter κ such that the value on the right-hand side of (<ref>) closely approximates I( G,X̂). This optimization is formalized as:

    κmax ℒ_MI( κ ,X̂)=1/K∑_i=1^Kf_κ( g_i,x̂_i)-log1/K∑_i=1,j i^Ke^f_κ( g_i,x̂_i).

After training with K sets of training data, the training process generates a set of suboptimal MINE parameters denoted as κ^* (see Fig. <ref>).



Drawing from (<ref>) and (<ref>), we derive a reformulation of the overall loss function:

    ℒ_GIB   ( ϕ ,θ ,κ^*)= E_p( g,y ){E_p_ϕ( x̂|g )[ -logq_θ( y|x̂) ]
       +β[ E_p_ϕ( x̂|g )f_κ^*( g,x̂)-logE_p( x̂)e^f_κ^*( g,x̂)] }  .

By combining the sampling method, equations (<ref>) and (<ref>), we arrive at a tractable optimization problem for the entire system:

    ϕ ,θmin ℒ_GIB( ϕ ,θ ,κ^*)=ℒ_inf( θ,ϕ)+βℒ_MI( κ^*,X̂).




 §.§ Model Training Strategy

To solve Problem 2, we specially design the feature extraction module. Node assignment is the main step in the graph feature extraction process. First, we introduce assignment probabilities as a continuous relaxation in node assignment, to address the problem that the discrete nature of the graph make it difficult to optimize (<ref>) using gradient optimization methods.
Next, we introduce connectivity loss to improve the impact of topological information on feature extraction, which can also make the node assignment process more stable. 

The detailed design process of this module will be discussed below.


We devise a node assignment mechanism to determine the inclusion of each node in the graph within the subgraph. This mechanism involves GNN extracting node features X from the original graph G. These features are then input into an MLP to obtain preliminary node assignments. The Softmax function is subsequently employed to convert these assignments into a probabilistic form. We represent the selected subgraph as G_sub. Specifically, for a given graph G, nodes either belong to G_sub or G_sub. The node assignment mechanism yields a matrix S:

    S= Softmax( MLP_σ_2( X ) )   with   X=GNN_σ_1( A,X ).

The matrix S has dimensions m× 2, where m is the number of nodes in the input graph, and each row is a two-dimensional vector indicating the assignment probability of the corresponding node. Specifically, the i-th row of S,

    [ p( V_i∈G_sub|V_i),p( V_i∈G_sub|V_i) ],

represents the probability of the i-th node belonging to G_sub or G_sub.

We define ϕ_1={σ_1,σ_2} as the parameter of the node assignment mechanism, which is part of the parameter of the transmitter. Once adequately trained, the values in each row of S should converge to 0 or 1, achieving robust node assignment. We take the first row of S^TX to obtain the feature vectors of the n nodes belonging to the subgraph. 

In conjunction with the JSC encoder parameter ϕ_2, we obtain the transmitter parameter ϕ ={ϕ_1,ϕ_2}. For simplicity, we collectively refer to the node assignment mechanism and the JSC encoder as the feature extractor and encoder, denoted as g_ϕ( ·). Consequently, the objective function is explicitly expressed as:

    ϕ ,θmin ℒ_GIB( ϕ ,θ ,κ^*)=ℒ_inf( q_θ( g_ϕ( G ) ) )+βℒ_MI( κ^*,X̂).


We introduce a continuous relaxation with probabilistic assignment of nodes, alleviating the problems arising from the discreteness of the graph. Nevertheless, inadequate initialization may lead to poorly trained node allocation mechanisms and failure to achieve the desired outcomes. In other words, if the probabilities of a node belonging to G_sub or not are too close, nodes amay not be appropriately assigned. On one hand, over-assigning nodes to G_sub will lead to the presentation of a subgraph that includes an excessive amount of redundant information. On the other hand, assigning too few nodes to G_sub will result in an inadequate amount of task-related information in the subgraph, rendering it incapable of successfully executing the task.

To address the above issues, we assume that the model has an inductive bias that helps the model to focus more on the connectivity relationships between nodes. The model is thus better able to capture and utilize the topological information of the graph. We incorporate the connectivity loss proposed in <cit.> to introduce this inductive bias:

    ℒ_con= Norm( S^TAS )-I_2_F,

where Norm( ·) denotes row normalization, I_2 is the 2× 2 identity matrix , and ·_F is the Frobenius norm. Elements a_11 and a_12 in the first row of S^TAS are defined as follows:

    a_11=∑_i,jA_ijp( V_i∈G_sub|V_i)p( V_j∈G_sub|V_j),

and 

    a_12=∑_i,jA_ijp( V_i∈G_sub|N_i)p( V_j∈G_sub|V_j).



Intuitively, if a node belongs to G_sub, its neighboring nodes are highly probable to belong to G_sub as well. Conversely, if a node does not belong to G_sub, its adjacent nodes likely do not belong to G_sub either. Consistently with this, ensuring adequate nodes are assigned to G_sub while reducing redundancy is achieved through a_11/a_11+a_12→ 1. This occurs simultaneously with reducing redundancy in G_sub through a_12/a_11+a_12→ 0. Analogously, this holds for G_sub and the elements of the second row of S^TAS.



To summarize, we introduce the continuous relaxation with probabilistic node assignment to enhance the optimization process. To address potential challenges stemming from inadequate initialization, such as ambiguous node assignment and unstable training process, we incorporate the inductive bias with the connectivity loss ℒ_con. The overall loss function is refined as:


    ϕ ,θmin ℒ_GIB( ϕ ,θ ,κ^*)=ℒ_inf( q_θ( g_ϕ( G ) ) )
    
          +βℒ_MI( κ^*,X̂)+αℒ_con( g_ϕ( G ) ).


The training procedures for the GIB-enabled task-oriented communication system are illustrated in Algorithm <ref>.



 §.§ Computational Complexity Analysis

The computational complexity inherent in the proposed methodology primarily emanates from its reliance on GNNs. In our analysis, the GCN is chosen as the representative GNN to elucidate the computational complexity of the system. Characteristically, GCN employs a one-hop receptive field to assimilate local features, subsequently enlarging this receptive field through the stratification of layers. Denoting the number of GCN layers by L, the computational complexity attributed to GNNs can be articulated as 𝒪(|E|∑_i=1^LD_in^(i)D_out^(i)), where |E| signifies the quantity of edges in the graph, and D_in^(i), D_out^(i) represent the input and output dimensions of each respective layer. In parallel, the complexity associated with the MLP layer and the Softmax function within the node assignment mechanism is quantified as 𝒪(mD) and 𝒪(m) respectively, with 
m indicating the total number of graph nodes and 
D symbolizing the output dimension of GNNs. Consequently, the cumulative computational complexity of the proposed framework can be comprehensively expressed as 𝒪(|E|∑_i=1^LD_in^(i)D_out^(i)+ND).



 




§ DIGITIZATION OF GIB-ENABLED TASK-ORIENTED COMMUNICATIONS


This section extends the analog task-oriented communication system, introduced in Section 3, to suit digital communication environments. As outlined in Problem 3, practical applications necessitate compatibility with digital systems. We address this by integrating vector quantization for digital transmission adaptation.
 






 §.§ Digital Transmission

A pivotal strategy for transitioning to a digital framework involves discrete codebook mapping. This technique maps the continuous outputs of the neural network encoder into discrete codewords, as discussed in related works <cit.>. The mapping process employs a predefined discrete codebook alongside nearest neighbor rules <cit.>. Let x_1,x_2,… ,x_n∈ℝ^d be the continuous outputs from the encoder described in Section III. The codebook, denoted as ℰ∈ℝ^K× d consists of K codewords e_1,e_2,… ,e_K∈ℝ^d, where K represents the codebook size. The discrete mapping function is formulated as:

    x_i_q=e_k where k=jmin x_i-e_j_2.

Employing discrete codebook mapping, the probabilistic model of the system is transformed into a new Markov chain, represented as:

    ( Y )G → X → Z →Ẑ→X̂→Ŷ,

which adheres to the following relationship:

    p( ŷ|g )=p_ϕ( x|g )p_Q( z|x )p_SDC( ẑ|z )p_DQ( x̂|ẑ)p_inf( ŷ|x̂).

Here, the transition from 
 X to Z entails discretizing feature representations using the codebook. 
 Z represents the index sequence derived via the nearest neighbor rule, substituting X  as the input to the channel.
 For the discrete signal Z, we employ the discrete channel defined in (<ref>) for its transmission, that is:
 
    p_SDC( ẑ|z )=p_channel(ẑ|z; ζ=1)
         =P_Ẑ|Z(ẑ|z),

 where P_Ẑ|Z(ẑ|z) is the transition probability matrix of SDC described in Section II when ζ=1.
 

 




In digital transmission, as indicated in (<ref>), each vector x_i from the encoder output is aligned with its nearest embedding vector e_k from the shared codebook. The transmitter's role is simplified to sending the index k to the receiver. The assignment of indices for transmission is defined as:

    p(Z_i=k|x_i)={[                    1 for k=jmin x_i-e_j_2;                    0            otherwise;                      ]..

This results in a continuous vector being translated into a discrete one-hot codeword. However, channel imperfections can lead to erroneous index detection (Ẑ). We utilize the SDC to model this transmission of discrete indices.









 §.§ Design of Discrete Codebook

Each codeword e_i in the vector quantizer's codebook defines a Voronoi region 𝒱_i:

    𝒱_i={ x∈R^d: x-e_i≤ x-e_j, for all j i }.

These regions collectively span the entire vector space ℝ^d
  to which the encoder's output belongs. The quantization process entails finding the codeword closest to a given vector, which subsequently determines the Voronoi region and index for the vector. Balancing the size of the codebook is crucial as increasing it reduces quantization distortion but also elevates computational complexity.

We opted for a moderate-sized, suboptimally designed codebook to achieve acceptable quantization results. To enhance the codebook's performance, we introduce a learnable aspect, allowing codewords to adapt during training. Additionally, the encoder's output range is constrained to prevent extreme variations.

The non-differentiable nature of the quantization operation poses a challenge for encoder training. To address this, a straight-through estimator is employed, allowing gradients from the decoder input to flow back to the encoder output. Furthermore, a loss term (ℒ_vq) is added to reduce the distance between the encoder output and the corresponding codeword:

    ℒ_vq= sg[ x ]-e _2,

with sg[ ·] representing a stop gradient function. 

A commitment loss (ℒ_CM) is also introduced to ensure the encoder's output does not deviate excessively from the codewords:

    ℒ_CM= x-sg[ e ] _2.


The final objective function (
ℒ_VQ-GIB) encompasses these elements alongside the mutual information and connectivity losses, guiding the entire system:

    ℒ_VQ-GIB   =ℒ_inf( q_θ( g_ϕ( G ) ) )+βℒ_MI( κ^*,X̂)
         +αℒ_con( g_ϕ( G ) )+ℒ_vq+λℒ_CM

subject to the optimized mutual information parameters κ^*:

    κ^*=κmax ℒ_MI( κ ,X̂).




    ℒ_vq= sg[ x ]-e _2,

where sg[ ·] denotes stop gradient. Therefore, this item is solely valid for codebook learning, not encoder training.

Given that the volume of the encoder's output space is dimensionless, achieving satisfactory quantization mappings is challenging if the training of the codewords in the codebook does not align with the rate of parameter training in the encoder. Therefore a commitment loss is introduced to constrain the encoder's output from increasing:

    ℒ_CM= x-sg[ e ] _2.

This item only affects the encoder, bringing the output closer to the code vector without influencing codebook learning.

For codebook updating, we adopt an exponential moving average (EMA) approach akin to K-means clustering. This method assigns variable weights to cluster centers over training batches, ensuring that the codebook dynamically adapts to the encoder's output.




§ EXPERIMENTS AND DISCUSSIONS



In this section, we evaluate the performance of the proposed GIB-based task-oriented communication system on graph classification tasks, and investigate the adaptability and effectiveness of continuous and discrete communication systems respectively. 

Additionally, ablation studies are also conducted to illustrate the contributions of the MI loss ℒ_MI in GIB and the connectivity loss ℒ_con presented in Section 3, as well as the impact of the trade-off factor β on the system performance.








 §.§ Experimental Setup



  §.§.§ Datasets


For our graph classification experiments, we carefully select two datasets: COLLAB and PROTEINS.


    
  * COLLAB: This scientific collaboration dataset represents a researcher's ego network, where nodes correspond to researchers and edges indicate collaboration between them. Each researcher's ego network is labeled based on the field to which the researcher belongs, resulting in three possible labels. COLLAB consists of 5,000 graphs, with an average of 74 nodes and 2,457 edges per graph.
    
  * PROTEINS: This dataset comprises 1,113 proteins classified as enzymes or non-enzymes. Nodes in the graph represent amino acids, and edges exist between nodes if the distance between corresponding amino acids is less than 6 angstroms. On average, each graph in the PROTEINS dataset has 39 nodes and 73 edges.
  










  §.§.§ Setings and Baselines



To assess the performance of the proposed method in a graph classification task, we integrate GIB into two distinct backbones: Graph Convolutional Network (GCN) <cit.> and Graph Isomorphism Network (GIN) <cit.>.

We compare the proposed method with other graph-level representation learning methods: InfoGraph based on mean aggregation <cit.> and ASAP (Adaptive Structure Aware Pooling) based on pooling aggregation <cit.> in terms of graph classification accuracy, respectively. 


    
  * InfoGraph: InfoGraph is an unsupervised graph-level representation learning method that maximizes the mutual information between the representations of entire graphs and the representations of substructures at different granularity (e.g., nodes, edges, triangles) to make the graph representations adequately capture the features of substructures.
    
  * ASAP: ASAP utilizes self-attention network along with GNNs to capture the importance of each node in a given graph. It also learns a sparse soft cluster assignment for nodes at each layer to pool the subgraphs to form the pooled graph.



For a fair comparison, all methods use the same number of GNN layers in the backbone. Models are trained using Stochastic Gradient Descent (SGD) with the Adam optimizer. We employ 10-fold cross-validation to report classification accuracy in experiments to validate the performance of the models.




  §.§.§ Neural Network Architecture


 While we do not enforce complete consistency in the network architectures of different approaches, we ensure that the GNN backbone and the number of layers are consistent across methods. The neural network architectures for the proposed method are shown in Tables <ref> and <ref>, which are outlined below. In the tables, num is the number of nodes, batch is the batch size during training, class_n is the number of graph classes, and dim represents the hidden dimension. The size in Table <ref> refers to the size of the codebook, which was set to 256 in the experiment.



    
  * Table <ref> shows the network architecture of the proposed method where GCN is used as the backbone. We use two GCN layers to extract the node features of the graph and then perform node assignment. The output of the Node Assignment layer is multiplied with the full node features extracted by the GCN to obtain the node features of the selected subgraph. This output undergoes power normalization before passing through the AWGN channel.
    
    
    
  * Table <ref> illustrates the network architecture of the proposed digital communication system.  In discrete communication systems, subgraph representations require quantization before entering the channel. During the training process, the codebook utilized for vector quantization undergoes automatic updates until it reaches a stabilized state. The index sequence obtained from quantization passes through a symmetric discrete channel with a certain error transfer probability, and the decoder performs dequantization based on the codebook shared with the encoder.


We note that the hidden layer dimensions of the proposed method and baseline methods are set to the same. To comply with the original implementation idea of the baseline methods, the output dimension of their encoder network is twice as large as that of the proposed method, consuming more communication resources. In addition, since the vector quantization part is not involved in baselines, the same quantization method as the proposed method is adopted for comparison algorithms.





 §.§ Performance of GIB-enabled Task-oriented Communications Without Vector Quantization



 

In the experiments, we evaluated the robustness of the proposed method amidst varying channel conditions. Prior to transmission, we implemented signal power normalization. During the training phase, a consistent SNR of 5 dB was maintained, whereas for testing, the SNR was methodically varied within a range extending from -15 dB to 25 dB. Two distinct experimental sets were executed, each with a batch size of 128. The first set operated with a hidden dimension of 16, while in the second, this parameter was augmented to 32.


Fig. <ref> graphically illustrates the inference performance of the methods under evaluation across different channel quality scenarios. A discernible trend was noted, wherein the inference accuracy of all three methods demonstrated progressive enhancement in conjunction with rising SNR levels during testing, culminating in a plateau. Specifically, Fig. <ref> (a) delineates the variation of classification accuracy relative to SNR for the three methods on the PROTEINS dataset. Our proposed GIB-based method, alongside the ASAP method, showcased robust classification performance, with the former exhibiting particularly notable efficacy. The InfoGraph method achieved commendable classification accuracy, especially under near-ideal channel conditions and with a higher hidden dimension. Fig. <ref> (b) presents the experimental outcomes on the COLLAB dataset, a social network dataset characterized by complex topology and diverse node interrelations. The presence of densely connected communities within such networks significantly influences the graph's structural information, which in turn impacts the classification task. Both baseline methods exhibited suboptimal performance on this dataset, attributable to their inadequate consideration of graph topology. As explicated in Section III, the connectivity loss 
ℒ_con
  steers the model towards heightened consideration of the graph's structural characteristics, enhancing the performance of our approach.
  

 

Fig. <ref> compares the graph classification performance between our method, which employs the GIN as the backbone, and the alternative method utilizing the GCN. These experiments were conducted on both the PROTEINS and COLLAB datasets, with hidden dimensions set to 16 and 32, respectively. Notably, in the realm of graph classification, the GIN-based method surpassed its GCN-based counterpart. The GCN, a prevalent choice for graph data processing, updates node representations through uniform aggregation of neighboring nodes. In contrast, GIN adopts a distinct methodology, where each node initially aggregates its feature with those of its neighbors via weighted summation. This non-commutative aggregation process, which is indifferent to the order of nodes, imparts to the GIN model an invariance to graph isomorphism, thus enabling it to effectively capture both the structure and global information inherent in the graph.

Given the specific focus on graph classification in this study, the adoption of GIN as the backbone is recommended. However, for a broader spectrum of tasks, the selection of GNNs with varying intrinsic characteristics as backbones can significantly bolster task-specific performance.





 §.§ Performance of GIB-enabled Task-Oriented Communication Systems Utilizing Vector Quantization


In this part, the performance of the proposed discrete communication system, which incorporates digital codebooks, is rigorously evaluated. Our experiments are structured to assess system robustness under varying probabilities of correct transmission. Here, the probability of correct transmission, denoted as 
ε, signifies the likelihood that the index received by the receiver accurately corresponds with that transmitted by the sender. Consequently, higher values of 
ε are indicative of superior channel quality. During the model training phase, 
ε is fixed at 0.94, whereas for testing, an array of 
ε values, specifically [0.90, 0.92, 0.94, 0.96, 0.98], are examined.



Fig. <ref> graphically represents the classification performance of all three evaluated methods as a function of 
ε, with the hidden dimensions set at 16 and 32 respectively. The results delineated in these figures unequivocally demonstrate that our method significantly outperforms the baseline methods under various channel quality scenarios. The integration of InfoGraph with VQ is observed to be substantially ineffective for graph classification tasks within digital communication systems. The ASAP method exhibits moderate effectiveness on the PROTEINS dataset; however, its efficacy is markedly diminished when applied to the more complex COLLAB dataset. As illustrated in Figure <ref> (b), its classification accuracy is confined to approximately 0.6 or lower, indicating that minor transmission errors exert negligible impact on the outcomes. The curve illustrating the fluctuation of classification accuracy in relation to 
ε is characterized by irregular and unpredictable oscillations. In stark contrast, our proposed method demonstrates robust performance across both datasets, with classification accuracy exhibiting a modest but consistent upward trend in line with improvements in channel quality. This outcome aligns well with our initial hypotheses and theoretical underpinnings.



 

To further evaluate the performance of our proposed task-oriented digital communication system based on the GIB and VQ, we compared it against traditional digital communication method. Additionally, to validate the effectiveness of the VQ mechanism in task-oriented graph data transmission scenarios, we conducted experiment combining GIB with 8-bit scalar quantization followed by Quadrature Phase Shift Keying (QPSK) modulation.
Given the non-uniformity in the dimensionality of the signals produced by these methods, we apply the same error rate per symbol to all methods to ensure that the assessment is based on the methods' ability to handle equivalent levels of channel-induced errors, rather than on their inherent dimensions. Models were trained with a fixed error rate of 0.01 and tested across a range of error rates from 0.06 to 0.014. These experiments were carried out on two datasets, PROTEINS and COLLAB, respectively.
The experimental results are shown in Fig. <ref>.

On PROTEINS, all methods exhibited comparable outcomes. This is because the PROTEINS data set is relatively simple and does not require a more elaborate symbolic representation. However, on COLLAB, the performance of the GIB based methods is significantly better than that of traditional digital communication method, which reflects the effectiveness of GIB for extracting task-related information on complex graph data. Between the two GIB-based methods, vector quantization significantly outperforms the traditional digitization method, highlighting its advantages in handling complex datasets with higher dimensionality and complexity.
The superior performance of the proposed task-oriented digital communication system based on the GIB and VQ on the COLLAB dataset highlights its potential advantages over traditional communication systems and traditional digital schemes, particularly in scenarios where data is characterized by high dimensionality and intricate patterns. 


 




 §.§ Ablation Study









To empirically ascertain the contribution of the individual components in our proposed methodology, we executed a series of ablation studies. Specifically, we extracted ℒ_MI  and ℒ_con from the loss function, thereby deriving two distinct variants of our method: 
GIB lacking ℒ_MI
and GIB lacking ℒ_con. 




  §.§.§ Effectiveness of ℒ_MI


Observations from Tables <ref> and <ref> indicate that, across both datasets, the system based on GIB and its variant without the ℒ_MI component consistently exhibit superior performance at a hidden dimension of 32 compared to a hidden dimension of 16. 
This is because an increase in the hidden layer dimension increases the capacity of the model, which means that the network can capture more details in the data. Especially for graph data with complex structures, higher model capacity can help the model learn richer representations and thus improve performance. 

It is worth noting that the size of hidden dimension has a more significant effect on the performance of the variant without ℒ_MI than GIB. 
The absence of ℒ_MI in the variant causes the model to focus more on maximizing mutual information between the input graph data and the extracted representations, while neglecting the aspect of compression. Consequently, the extracted representations contain much redundant information that takes up space for useful information. Therefore, as the hidden dimension increases, the model capacity increases. This allows the model to capture richer information in the graph data and more information needed for the task. In other words, GIB takes into account information compression, meaning it can achieve good performance even with relatively smaller model capacity.









  §.§.§ Effectiveness of ℒ_con

Furthermore, the absence of the connectivity loss constraint, 
ℒ_con
 , not only detrimentally impacts system performance on certain datasets but also instigates volatility in node assignments, subsequently leading to inconsistent graph classification results. 
To illustrate the significance of connectivity loss and its impact on system reliability, we adopt the arithmetic mean of outcomes derived from a 10-fold cross-validation process as the benchmark for task execution accuracy. Complementarily, the standard deviation computed from these same 10 iterations serves as the metric to gauge the consistency and robustness of our system's performance under different communication conditions. 
It becomes evident upon analysis that the standard deviation associated with GIB added ℒ_con exhibits a reduction in comparison to its variant without ℒ_con under various channel conditions. This result suggests that the connectivity loss we incorporate plays a critical role in improving the robustness and stability of the system performance. 






  §.§.§ Influence of Variations in 
β on System Performance

The hyperparameter β, associated with the mutual information term, plays a pivotal role in modulating the extent of mutual information between the graph features and the subgraph features, thereby reflecting the relative importance of the graph's global structure versus its local features. To explore this interplay, we conducted experiments assessing the impact of varying β values on classification accuracy, with the findings presented in Table <ref>. The experimental data reveal that the system attains optimal performance at a moderate MI factor level, in contrast to either extremely high or low levels.

When β is set to a low value, the model predominantly accentuates local features, while marginalizing the global structural information of the graph. This can lead to the model's failure in capturing critical global relationships within the graph, culminating in a diminished classification accuracy. Inversely, a high β value results in the model prioritizing the global graph structure at the expense of local features. Such an overemphasis on the macro structure of the graph renders the classifier less receptive to nuanced local features, thereby constraining the model's task execution capabilities. By selecting a moderate value for β, the model achieves an equilibrium between harnessing the global structure and incorporating local features. This equilibrium enables the model to effectively utilize the intrinsic global structure of the graph while concurrently considering the node-specific local features. The resultant synergistic integration of global and local features thus significantly enhances the model's performance in graph classification tasks.



§ DISCUSSION

Task-oriented graph data transmission is a promising research avenue, especially relevant in smart city scenarios such as traffic management and environmental monitoring, where distributed edge computing plays a crucial role.  In these contexts, numerous sensors and devices across the city communicate with central servers for data processing.  This communication technique significantly reduces bandwidth usage while maintaining accurate inference capabilities, making it highly suitable for real-time applications in urban settings.  To effectively translate the theoretical foundations of the GIB approach into tangible applications, it is essential to demonstrate its practical utility in addressing real-world, task-oriented communication challenges. Here are some heuristics worth exploring.



 §.§ Heuristics for Inference Goal Formulation
 Real-world scenarios encompass a broad spectrum of inference objectives, contingent upon the specific application context. For example, in the realm of autonomous vehicles, the focus might be on detecting and responding to traffic signals and obstacles. In contrast, industrial IoT may concentrate on predicting equipment failures. The GIB framework is designed to fine-tune the communication process, thereby amplifying the precision and efficiency tailored to these particular tasks. The GIB model can be crafted to cater to either uni-task or multi-tasks. While task-specific models are optimized for a unique objective, task-agnostic models can be expanded to address a variety of tasks through strategic architectural enhancements and transfer learning techniques. This approach necessitates training the model across a diverse array of tasks and datasets, fostering its ability to generalize across varied communication scenarios.



 §.§ Heuristics for GIB Model Training
 The GIB model should be trained on data that mirrors the complexities of its target real-world task. This process entails amassing comprehensive datasets that encompass both raw input data, such as sensor readings or visual imagery, and the relevant task-specific labels, such as classifications of objects or indicators of faults. It is imperative that these data are meticulously annotated and preprocessed to construct a graph that encapsulates the interconnections and interdependencies among various data elements. The efficacy of GIB framework should be substantiated through rigorous experimentation with datasets that pertain to different task-oriented communication applications. For instance,  industrial datasets could be utilized to train the model in predictive maintenance tasks, employing sensor data to anticipate equipment failures. Additionally, deploying the GIB framework on medical imaging datasets could enhance communication efficiency in tasks such as diagnosing diseases and monitoring patient conditions. 



 §.§ Heuristics for Training Dataset Construction

To construct a training dataset for tasks without a standard dataset, follow these steps: First, clearly specify the task, such as node classification or link prediction; second, collect raw data needed for the graph-based task, typically in the form of nodes, edges, and node features; third, preprocess the data suitable for graph-based learning by normalizing node features, removing self-loops, and converting the graph to an appropriate format (e.g., adjacency matrix, edge list); Construct graph representations to serve as inputs to GNN, typically involving adjacency matrices and node feature matrices; Generate pairs of input graphs and target outputs specific to the task. For instance, for node classification, the input is subgraphs centered around each node with the output being the class label of the central node for node classification tasks, while for link prediction tasks, the input is subgraphs around a candidate link with the target being a binary label indicating whether the link exists; Implement GIB to identify and retain the most informative parts of the graph while discarding unnecessary information by encoding the graph data into a compressed representation and decoding it to approximate the original or task-specific output; Finally,  divide the dataset to ensure the model generalizes well to unseen data. Additionally, feature engineering, such as aggregating neighborhood information and generating higher-order features, can enrich node features. Data augmentation can also be used to improve the model's robustness in data-hungry cases.



§ CONCLUSION


In this study, we explored GIB-based task-oriented communication for graph data transmission, focusing on optimizing mutual information between received codewords and the task goal while reducing the mutual information with the original graph representation. Utilizing variational approximation, Monte Carlo sampling, and MINE, we devised a workable objective function, addressing the challenge of computing mutual information for irregular graph data. We also incorporated a connectivity loss term to account for community structure in graph data, which improved subgraph selection and stabilized training, as confirmed by our experiments. Furthermore, we adapted our method for digital transmission using vector quantization. Our tests across various SDC channel qualities consistently showed strong performance, underscoring the method's adaptability and efficacy. Future work will explore more practical application areas and include hands-on experiments with real-world data.


IEEEtran 

