Gaussian Mixture Models Based Augmentation Enhances GNN Generalization

Authors: Yassine ABBAHADDOU, Fragkiskos D. Malliaros, Johannes F. Lutzeyer, Amine M. Aboussalah, Michalis Vazirgiannis
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Data Augmentation

Abstract:
Graph Neural Networks (GNNs) have shown great promise in many learning tasks, notably including node and graph classification, but they face difficulties when tested on new or unseen data. These challenges are exacerbated when training data is limited in size or diversity. To address this issue, we introduce a theoretical framework using Rademacher complexity to compute a regret bound on the generalization error and then characterize the effect of data augmentation. This framework informs the design of GMM-GDA, a new, efficient graph data augmentation (GDA) algorithm leveraging the capability of Gaussian Mixture Models (GMMs) to approximate any distribution. Our approach not only outperforms existing augmentation techniques but also offers improved time complexity, making it highly suitable for real-world applications.

Decision: reject
Reviewer scores: 1, 5, 6, 6

Reviews and discussion:
<thread>
creation date:
1730018607026

thread_type:
official_review

<thread_object>
creator: reviewer_qdd6

<content>
summary:
The authors propose a novel graph data augmentation based approach to tackle the graph OOD problem. To be specific, they first train a GNN model using the training data. Then, graphs within each class in the training data are fed to the GNN model and the output of the readout layer are treated as the embeddings of this class. After that, the authors propose to fit a Gaussian Mixture Model (GMM) on the embeddings for each class using the classical EM algorithm. Finally, the augmented embeddings are generated by sampling from the GMMs for each class, which are combined with the embeddings of training data and used for fine tuning the post-Readout function. The proposed framework enjoy a high computation efficiency since the post-Readout function contains only a linear layer and the (time) complexity of fitting GMMs is linear. The authors also provide some theoretic analysis. First, they analyze the excess risk of the graph augmentation approach and the result shows that minimizing the expected distance between original graphs and augmented ones could reduce the excess risk. Second, they use influence functions to quantify the affect of augmented data on model's performance on testing data. Experimental results show that the their proposed method has competitive performance against baselines and has a significant benefit on advantages in robustness against structure corruption and time complexity.

strengths:
The proposed technique is reasonable and efficient. The experimental results provided in the paper are sufficient to support the effectiveness of this technique. Considering the balance between effectiveness and computational efficiency of this technique, it has a potential application on real-world scenarios. Besides, the paper is well-written and easy to follow.

weaknesses:
Although using a generative models to learn the graph representation distribution is reasonable, the motivation of adopting GMMs is still unclear. GMM is universal approximator of densities could be one of the reasons, yet how many component need to achieve a small approximation error is unknown. Besides, the theoretic results provided in this paper do not seem to explain why this method that generating augmentations in representation space is superior or comparable to previous methods that generating augmentations in data space, which could be a promising direction to be explored.

questions:
Q1: The number of Gaussian distributions $K$ in GMMs is an important hyperparameter and has impact on the performance of GMM. How do you properly choose this hyperparameter in practices? Please describe the tuning process of $K$ or provide hyperparameter sensitivity analysis to show how performance varies with different values of $K$.

Q2: In line 349, the subscripts $i,j$ of the notation $\\mathcal{L}^{aug}_{i,j}$ are ambiguous. I think the correct one should be $\\mathcal{L}^{aug} _ {n,m}$.

Q3: The proof between line 703 to line 715 seems confusing. The first equality only holds when the right hand side also includes a expectation w.r.t. $\lambda_{n,m}$. Indeed, I think the proof should be proceeded as
\begin{equation}
\left\Vert \\frac{1}{N} \\sum_{n=1}^N \\mathbb{E}_{\\lambda \sim \\mathcal{P}} [\ell(\\mathcal{G}_n,\theta) - \ell(\\mathcal{G}'_n,\theta) ] \right\Vert =  \\left\\Vert \\frac{1}{N}  \\mathbb{E} _ {\\lambda \\sim \\mathcal{P}} [\ell(\\mathcal{G} _ k,\theta) - \ell(\\mathcal{G}' _ k,\theta)] \\right\\Vert \leq \\frac{1}{N}  \\mathbb{E} _ {\\lambda \\sim \\mathcal{P}} [\Vert \ell(\\mathcal{G}_k,\theta) - \ell(\\mathcal{G}'_k,\theta) \Vert ] \leq \frac{1}{N}.
\end{equation}
The first equality is obtained by your claim that $\\mathcal{G} _ k = \\mathcal{G}' _ k$ for $k = 1,\ldots, N$ and $k \neq n$. The last inequality is obtained by $\ell(\cdot) \in [0,1]$.
Please clarify this issue or correct this part of proof following the above steps.

Q4: In line 754, you claim that $\\hat{\theta} _ {aug}$ is the optimal parameter of the loss $\frac{1}{N} \\sum_{n=1}^N \\mathbb{E} _ {\\lambda \sim \\mathcal{P}}  [\ell(\\mathcal{G}^{\\lambda} _ n,\theta)]$, which is different from the definition of $\\hat{\theta}_{aug}$ in line 195 where $\\hat{\theta} _ {aug} = \\mathop{\rm argmin} _ {\theta} \\frac{1}{NM} \\sum _ {n=1}^N \\sum _ {m=1}^M \ell(\\mathcal{G} _ n^{\\lambda _ {n,m}}, \theta)$. This could make the inequality $v_3 \leq 0$ do not hold. Please clarify and check the definition of $\\hat{\theta} _ {aug}$. If the above issue do exist, you should consider revising your proof accordingly.

Q5: In line 221-223, you claim that minimizing the term $\\mathbb{E} _ {\\mathcal{G} \sim G} \\mathbb{E} _ {\\lambda \sim \\mathcal{P}} [\Vert \\mathcal{G}^{\\lambda} - \\mathcal{G} \Vert ]$ can guarantee with a high probability to decrease both the Rademacher complexity and the generalization risk. And you also show that the Rademacher complexity term $\\mathcal{R}(\ell _ {aug})$ is upper bounded by $\\mathop{\rm max} _ {n=1,\ldots,N} \\mathbb{E} _ {\\lambda \sim \\mathcal{P}} [ \Vert \\mathcal{G}^{\\lambda} _ n - \\mathcal{G} _ n \Vert ]$, which is a empirical estimation of $\\mathbb{E} _ {\\mathcal{G} \sim G} \\mathbb{E} _ {\\lambda \sim \\mathcal{P}} [\Vert \\mathcal{G}^{\\lambda} - \\mathcal{G} \Vert ]$ w.r.t. $\\mathcal{G}$. Therefore, minimizing the term $\\mathbb{E} _ {\\mathcal{G} \sim G} \\mathbb{E} _ {\\lambda \sim \\mathcal{P}} [\Vert \\mathcal{G}^{\\lambda} - \\mathcal{G} \Vert ]$ may not guarantee to decrease the Rademacher complexity term $\\mathcal{R}(\ell _ {aug})$. Please clarify this issue or modify your claim in line 221-223.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730687259127

thread_type:
official_review

<thread_object>
creator: reviewer_yuek

<content>
summary:
This paper proposed GMM-GDA, a graph data augmentation algorithm with better generalization abilities and faster training speed. GMM-GDA is presented based on a theoretical analysis relying a Rademacher complexity, which bounded the generalization error by the difference between the augmented data and original data. Furthermore, this paper verified the effectiveness of GMM-GDA from the perspective of influence functions and detailed experiments show the priority of the proposed algorithm.

strengths:
1.	This paper analyzes the problem of GNN generalization capability, which is well-written and clearly clarified. The whole paper is easy to understand.

2.	This paper provides theoretical insights before presenting the algorithm. 

3.	The experiments of this paper is closely related to the research goal proposed.

weaknesses:
1.	This paper did not explain the necessity of performing data augmentation by GMM. The authors should strengthen the explanation of the relationship between theory and the algorithm. 

2.	Some tables and figures do not seem to support the conclusions in the paper, which needs more explanation.

questions:
1.	Based on theorem 3.1, the motivation of the proposed method is to guarantee the alignment of the augmented data and original data, so the authors apply GMM to fit the embeddings of the training data. But there lacks an explanation of why GMM is applied, it seems that a simple DNN (or other more complex generative data augmentation techniques) can also fit the embeddings. Please explain the advantages of GMM. 

2.	It seems that only the post-readout function is trained by the combination of augmented data and original data (line 264). Why do not take several more iterations, and update the parameters of message passing layers? Please explain why only generate the embeddings of training data once but not re-generate them after updating the network. 

3.	Figure 2 shows the influence scores of the augmented embeddings on different datasets. But the authors did not analyze why in dataset DD their algorithm perform worse. This is an interesting phenomenon and worth a deeper analysis. 

4.	The authors claim that GMM-GDA is efficient in the augmentation steps and training steps and provide results in table 6 (line 315). But table 6 did not show the efficiency of GMM-GDA since it still cost much augmentation time or training time. Please explain why such a conclusion can be drawn from table 6. 

5.	In the result of table 1&2, it seems that GMM-GDA has a better performance in the setting of GIN compared with GCN. This phenomenon worth a deeper analysis. 

6.	The authors claim that the configuration models (line 470) is part of an ablation study, but it is hard to understand. Please explain more clearly about the conclusion of this experiment.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730812203040

thread_type:
official_review

<thread_object>
creator: reviewer_25li

<content>
summary:
In this paper the authors introduce a method to perform data augmentation algorithm for graph datasets. 
The algorithm leverages Gaussian Mixture Models (GMM) to find the maximum likelihood estimates for each cluster given by the embedding ofdifferent classes. Finlly they use the GMM to generate augmented data. Notice that augmented samples are generated directly in. the embedding space. The authors provide a bound for the Rademacher complexity fro the loss function  modified to account for augmented data.

strengths:
- The proposed approach introduces a novel method for graph data augmentation. 
- The problem studied is relevant and interesting
- The algorithm's time complexity is  analyzed.

weaknesses:
- The clarity of the paper, particularly in Section 3, could be enhanced to guide the reader more effectively through the discussion.
- The method requires pre-training of the model  and moreover is dependent on the specific model architecture, meaning that the augmented dataset cannot be used by other GNN models.
- Baselines in Table 1 could be expanded to include additional augmentation techniques, such as edge insertion and feature drop.
- The metric used to measure the distance between $\mathcal{G}^{\lambda}$ and $\mathcal{G}$ in Theorem 3.1 and subsequent sections is not clearly defined.

questions:
- In the case of GMM what does the parameter $\lambda$ represent ?
- Does the GMM-based sample generation method ensure that the augmented samples remain within the distribution of the original data?
 - Can the method be extended to different tasks on graphs? such as node classification and link prediction? 
Comment: 
If the maximum of the expectations $\mathbb{E}_{\lambda}[\mathcal{G}_n^{\lambda} - \mathcal{G}n]$ is non-zero, the Rademacher complexity of $\ell{aug}$ may not necessarily be smaller than the Rademacher complexity of $\ell$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730835530728

thread_type:
official_review

<thread_object>
creator: reviewer_7b8k

<content>
summary:
The paper discusses data augmentation for graphs. The concrete proposal is to use a Gaussian mixture model. The justification for this proposed approach is that Gaussian mixture models are universal density estimators.

strengths:
Data augmentation for graphs is a topic that warrants investigation. There is little work on the subject. 
Numerical evaluations are comprehensive

weaknesses:
The proposed data augmentation method is not specific to graphs. It could apply to any data type. No arguments are given as to whether this is suitable way of augmenting graph datasets.

Numerical evaluations are comprehensive but underwhelming. Improvements are marginal relative to training without data augmentation. All but 1 improvement in Tables 1 and 2 are well within one standard deviation and can be explained by random chance.

questions:
I do not understand Theorem 1. Please expand explanation.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a data augmentation method to enhance GNN generalization. The proposed method applied Gaussian Mixture Models (GMMs) to the readout features, and augment data following the trained GMM. Then the classifier is trained on the augmented data.  

Unfortunately, the proposed method does not give a significant improvement of the performance. The proposed method just applies a general data augmentation method to the GNN setting and does not make use of any specific property of GNNs, which limits the novelty of the proposal. The reason why the proposed method does not give significant performance improvement would be that the method requires to fit GMMs (generative model) that is harder than just solving classification problem. Thus, this data augmentation approach does not necessarily perform well in not only GNNs but also general classification problems.  

For these reasons, I don't recommend acceptance of this paper.