Graph Harmony: Denoising and Nuclear-Norm Wasserstein Adaptation for Enhanced Domain Transfer in Graph-Structured Data

Our model adopts encoding and decoding structures from the Variational Graph Auto-Encoders (VGAE) Kipf & Welling (2016b), an unsupervised learning model for graph-structured data based on Variational Auto-Encoder (VAE) concepts. Given a graph sample $G=(X,A)$ with $n$ nodes, the encoder in VGAE generates a corresponding latent variable $Z$. $q_{\phi}(Z|A,X)$ is used to denote the feature encoder, characterized by the parameter $\phi$. $q_{\phi}$ aims to approximate the real posterior distribution $p(Z|A,X)$. The decoder of a standard VGAE is represented as $P_{\theta}(A|Z)$, defined by parameters $\theta$. The prior distribution is denoted by $P(Z)$. The prior distribution is assumed to be a normal distribution, specifically $P(Z)\sim\mathcal{N}(0,I)$. The variational lower bound of the marginal likelihood for standard VGAE is given as:

where $D_{KL}(q(\cdot)||P(\cdot))$ represents the Kullback-Leibler divergence between distributions $q(\cdot)$ and $P(\cdot)$. The standard VGAE is trained through maximizing the $\mathcal{L}_{\text{ELBO}}$. Similar to the training process of VGAE, however, we have some variations. Given a graph sample $G=(X,A)$, we train the VGAE on both $G=(X,A)$ and $G_{o}(X,A^{o})$, where $A_{o}$ denoted the augmented adjacency matrix. We add noise to the adjacency matrices to implement data augmentation. Specifically, we benefit from a random manipulation-based approach Cai et al. (2021). To this end, edges are dropped and added randomly by modifying the values in the adjacency matrix $A$ of the original graph. The modified adjacency matrix $A^{o}$ is constructed as follows:

where $p^{\text{{add}}}$, $p^{\text{{edge}}}$, and $p^{\text{{drop}}}$ denote the edge addition rate, the sparsity of the adjacency matrix $A$, and the edge dropping rate. $\odot$ represents the element-wise multiplication between two matrices. $M^{\text{drop}}$ and $M^{\text{add}}$ represent mask matrices with the same dimensions as $A$. For each element $m_{ij}^{\text{add}}\in M^{\text{add}}$ or $m_{ij}^{\text{drop}}\in M^{\text{drop}}$, we sample its value from a Bernoulli distribution.

In a standard Variational Graph Autoencoder setup, if the input is an augmented adjacency matrix $A^{o}$, then the VGAE reconstructs $A^{o}$. However, in our approach, we aim to reconstruct the original adjacency matrix before augmentation. In other words, we reconstruct $A$ given either $G=(X,A)$ or $G^{o}=(X,A^{o})$. This way, we train the variational graph autoencoder to function as a sophisticated filter purifying the data. This purification is crucial for aligning the source and target domain distributions. The process can be likened to enhancing one’s vision in dense fog: the feature encoder, through training, becomes proficient at distinguishing unwanted random information and can reliably identify and extract the core features fundamental to source and target domains. These core features, distilled by the denoising process, are then used to align the distributions of the source and target domains. By focusing on these essential features, we hypothesize that the distribution alignment can be based on the intrinsic similarities of the source and target domains rather than on noisy information not representative of the actual distribution. Following this idea, we modify the variational lower bound of the marginal likelihood to be:

by replacing $P_{\theta}(A^{o}|Z)$ with $P_{\theta}(A|Z)$. We utilize Graph Attention Networks (GAT) as the encoder $q_{\phi}$ of the VGAE. The encoding equations are given as follows:

The element $z_{i}$ corresponds to the $i^{th}$ row of $Z$. This same row-wise correspondence applies to $\mu_{i}$ and $\log\sigma_{i}$ as well. Using the reparameterization trick, we transform the generated $\mu_{i}$ and $\sigma_{i}$ into latent variable $z_{i}$. After obtaining the latent variable $Z$, an inner product decoder $P_{\theta}(A|Z)$ is applied to $Z$ to reconstruct the adjacency matrix before data augmentation. This decoder translates each pair of node representations into a binary value, indicating whether an edge exists in the reconstructed adjacency matrix $A^{\prime}$. Specifically, we first use an MLP layer to enhance the expressive capacity of the latent variable $Z$ and then compute the dot product for each node representation pair as:

where $h_{i}$ represents the $i^{th}$ row of $H$ and $A^{\prime}_{ij}$ is an element of reconstructed adjacency matrix $A^{\prime}$. The decoder is described by parameter $\theta$ that includes the parameters $\{W_{0},W_{1}\}$. To eliminate redundant information within the latent variables, an element-wise maximum entropy loss, denoted as $L_{e}$, is applied to the latent variable $Z$. The regularization factors work to repel extraneous information from them, ensuring a cleaner reconstruction of the latent variable. The specifics of this regularization process are described below:

where $n_{k}$ is the number of nodes in the graph sample $G^{k}$ and $F$ denotes the dimension of $G^{k}$’s latent variable $Z^{k}$.

By introducing the new variational lower bound for the marginal likelihood, the VGAE encoder is better equipped to grasp the essential features of both domains. However, we still face a crucial challenge: addressing the performance degradation that occurs when a model trained on data from a source domain is applied to a target domain with a different data distribution. As mentioned in the previous sections, traditional approaches in unsupervised domain adaptation often use a domain discriminator that engages in a min-max game with a feature extractor to produce domain-invariant features. However, these methods primarily focus on confusing features at the domain level, which might negatively impact class-level information and lead to the mode collapse problem Kurmi & Namboodiri (2019); Tang & Jia (2020). To address these challenges, our approach integrates the Nuclear-norm Wasserstein discrepancy (NWD) Chen et al. (2022) to effectively align the source and target domains’ feature representations while maintaining class-level discrimination by considering it as a loss function to enforce domain alignment. Our method utilizes a graph variational autoencoder described in the previous section and a classifier $C$ with parameter $\theta_{c}$. We construct $C$ with two fully connected layers. The classifier $C$ serves two purposes. As a classifier, it distinguishes between categories, and as a discriminator, it aligns features to close the gap. The empirical NWD loss is defined as:

where $Z^{k}_{s}$ represents the latent variable for the graph sample $G^{k}_{s}$ and $Z^{k}_{t}$ represents the latent variable for the graph sample $G^{k}_{t}$. $\|\cdot\|_{*}$ denotes the Nuclear norm. $N_{s}^{\text{train}}$ is the number of training samples in the source dataset, and $N_{t}^{\text{train}}$ is the number of training samples in the target dataset. To avoid complex alternating updates, we employ a Gradient Reverse Layer (GRL) Ganin et al. (2016), which allows for updating in a single backpropagation step without gradient penalties or weight clipping. The distribution alignment is achieved through a min-max game, optimized as:

In addition to distribution alignment, to ensure accurate classification, we optimize the encoder in VGAE and the classifier $C$ using a supervised classification loss $\mathcal{L}_{\text{cls}}$ for the source domain:

Then, by combining all the loss described in the previous sections, our total optimization object is formulated as follows:

where $\phi$ is the parameter of the feature encoder of the VAE, $\theta$ is the parameter of the decoder of the VAE, $\theta_{c}$ is the parameter of the classifier and $\lambda_{e}$ is a hyperparameter weigh the maximum entropy loss $\mathcal{L}_{\text{e}}$. It is worth noting that we balance the supervised classification loss and the NWD loss equally. In this case, our model learns transferable and discriminative features and has prediction accuracy and diversity in the target domain. The complete procedures of our UDA approach for graph-structured data are summarized in Algorithm  1.

Tables 5 and 6 present our performance results. The bold font denotes the highest performance in each column.

We first perform analytic experiments to offer a deeper insight into our approach. We then performed an ablative experiment to demonstrate that all components in our algorithm are important to achieve optimal performance.

An important concern for most algorithms is tuning the hyperparameters and measuring the performance sensitivity with respect to them. We evaluate the sensitivity of DNAN with respect to various hyperparameters on two tasks: Twitter to Digg (T to D) and Digg to Twitter (D to T). We varied the dimension of the latent embedding space, the hidden dimension of the graph decoder, the weight of the maximum entropy loss, and the batch size. We present the F1-scores of the DNAN model as a linear function of these hyperparameters in Figure 3, with the blue lines representing the T to D task and the yellow lines representing D to T task. Through inspecting this figure, we deduce:

• •

  Dimension of the Latent Embedding Space: We test the performance of DNAN on five different dimension sizes for the embedding space: 32, 64, 128, 256, and 300. The performance of DNAN peaks at a latent variable size of 256 for the T to D task and a less pronounced peak on the D to T task, indicating that a moderately large value for the dimension of the latent variable is beneficial for capturing the salient features of the data. Performance declines when the dimension is too small to capture the complexity or too large, potentially introducing noise or overfitting. We note, however, that the result indicates that the performance remains relatively decent for a wide range of embedding sizes.

• •

  Hidden Dimension of the Graph Decoder: Similar to the experiments on the dimension of the latent variable, we test the performance of DNAN on five dimension sizes: 32, 64, 128, 256, and 300. The hidden dimension of the graph decoder shows a performance peak at 64 for the T to D task and the D to T task. This observation suggests that a moderately small representation capacity in the graph decoder is more beneficial. Compared with performances on the D to T task, the T to D task is less sensitive to this hyperparameter.

• •

  Weight of the Maximum Entropy Loss: We test the DNAN on six weights: 0.1,0.5,1.0,2.0,3.0,5.0. The weight of the maximum entropy loss presents a clear peak at 1.0 for both the T to D and D to T tasks, suggesting that a balanced contribution of the entropy loss is critical for performance.

• •

  Batch Size: We test five batch sizes: 64, 128, 256, 512, 1024. For batch size, there is a trend of increasing performance as the size grows, with a notable peak at a batch size of 1024 for the T to D and D to T tasks. This implies that the performance of DNAN benefits from larger batch sizes, possibly due to more stable gradient estimates. Compared with the T to D task, the D to T task is less affected by batch size variations.

The sensitivity analysis of hyperparameters for the DNAN model on the T to D and D to T tasks demonstrates the stability of DNAN models when using different hyperparameter values, as there is only a moderate fluctuation around $\pm 3\%$. However, fine-tuning hyperparameters to the specific characteristics of the task and the dataset is beneficial. Although optimal performance is achieved with a latent variable of 256, a hidden decoder dimension of 64, an entropy loss weight of 1.0, and a batch size of 1024, tuning the hyperparameter is not necessary to achieve a good performance.

The analysis of the training time and model complexity for various domain adaptation methods on the IMDb$\&$Reddit dataset is presented in Table  10 and Table  10.

• •

  Training Time: The training times reported in Table  10 illustrate the efficiency of the DNAN model relative to its counterparts. For the I to R task, DNAN required 10 minutes, positioning it the fastest in terms of training time, together with DANN and ToAlign, compared to other methods. In the R to I task, DNAN again demonstrated moderate efficiency with 5 minutes, with MMD being the fastest at 2 minutes and BIWAA the slowest at 34 minutes. These results suggest that DNAN provides a balanced trade-off between model performance and training efficiency without adding a significant computational overload.

• •

  Model Complexity: The model complexity, as shown in Table  10, is assessed based on the number of parameters in the models, which is a function of the input features dimension (K), hidden dimension (M), and the output dimension of the Decoder (D). Compared to other methods like DANN and SDAT, which have similar forms, DNAN introduces additional complexity due to the parameters in the graph decoder. However, it remains less complex than DIVA, which includes an extra (7M+2D+1)M term.

We conclude that the DNAN model shows competitive training time that is significantly lower than the most time-consuming method (BIWAA) while maintaining comparable or better performance. Model complexity analysis reveals that DNAN, while not the simplest, avoids the higher complexity seen in more complex methods such as DIVA, balancing the computational cost with the capacity to learn and transfer knowledge effectively for better UDA performance. This observation is important because, in some applications, UDA should be performed fast because the input distribution changes relatively continually, and the time needed to update the model is limited.