Perfect Alignment May be Poisonous to Graph Contrastive Learning

A graph can be represented as ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$, where ${\mathcal{V}}$ is the set of $N$ nodes and ${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ represents the edge set. The feature matrix and the adjacency matrix are denoted as ${\bm{X}}\in\mathbb{R}^{N\times F}$ and ${\bm{A}}\in\{0,1\}^{N\times N}$, where $F$ is the dimension of input feature, ${\bm{x}}_{i}\in\mathbb{R}^{F}$ is the feature of node $v_{i}$ and ${\bm{A}}_{i,j}=1$ iff $(v_{i},v_{j})\in{\mathcal{E}}$. The node degree matrix ${\bm{D}}=\mathrm{diag}(d_{1},d_{2},...,d_{N})$, where $d_{i}$ is the degree of node $v_{i}$.

In contrastive learning, data augmentation is used to create new graphs ${\mathcal{G}}^{1},{\mathcal{G}}^{2}\in{\mathbb{G}}^{\text{aug}}$, and the corresponding nodes, edges, and adjacency matrices are denoted as ${\mathcal{V}}^{1},{\mathcal{E}}^{1},{\bm{A}}^{1},{\mathcal{V}}^{2},{\mathcal{E}}^{2},{\bm{A}}^{2}$. In the following of the paper, $v$ is used to represent all nodes including the original nodes and the augmented nodes; $v_{i}^{+}$ is used to represent the augmented nodes including both $v_{i}^{1}$ and $v_{i}^{2}$; $v_{i}^{0}$ represents the original nodes only.

Nodes augmented from the same one, such as $(v_{i}^{1},v_{i}^{2})$, are considered as positive pairs, while others are considered as negative pairs. It is worth noting that a negative pair could come from the same graph, for node $v_{i}^{1}$, its negative pair could be $v_{i}^{-}\in\{v_{j}^{+}|j\neq i\}$. Graph Contrastive Learning (GCL) is a method to learn an encoder that draws the embeddings of positive pairs similar and makes negative ones dissimilar (Chen et al., 2020; Wang & Isola, 2020). The encoder calculates the embedding of node $v_{i}$ by $f(v_{i})$, and we assume that $||f(v_{i})||=1$.

Previous work (Wang & Isola, 2020) proposes that effective contrastive learning should satisfy alignment and uniformity, meaning that positive samples should have similar embeddings, i.e., $f(v_{i}^{1})\approx f(v_{i}^{2})$, and features should be uniformly distributed in the unit hypersphere. However, Wang et al. (2022b) pointed out that perfect alignment and uniformity does not ensure great performance. For instance, when $\{f(v_{i}^{0})\}_{i=1}^{N}$ are uniformly distributed and $f(v_{i}^{0})=f(v_{i}^{+})$, there is a chance that the model may converge to a trivial solution that only projects very similar features to the same embedding, and projects other features randomly, then it will perform random classification in downstream tasks although it achieves perfect alignment and uniformity.

Wang et al. (2022b) argues that perfect alignment and intra-class augmentation overlap would be the best solution. The augmentation overlap means support overlap between different intra-class samples, and stronger augmentation is likely to bring more augmentation overlap. If two intra-class samples have augmentation overlap, then the best solution is projecting the two samples and their augmentation to the same embedding, which is called perfect alignment. For example, if two different nodes $v_{i}^{0}$, $v_{j}^{0}$ get the same augmentation $v^{+}$, then the best solution to contrative learning is $f(v_{i}^{0})=f(v^{+})=f(v_{j}^{0})$. As the intra-class nodes are naturally closer, augmentation overlap often occurs between intra-class nodes, so perfect alignment and augmentation overlap could help intra-class gathering.

However, Saunshi et al. (2022) proposes that augmentation overlap is actually quite rare in practice, even with strong augmentation. Also augmentation overlap requires for strong augmentation, which makes alignment harder and conflicts with perfect alignment, so the success of contrastive learning may not be contributed to intra-class gathering brought by augmentation overlap. Therefore, it is important to understand how is contrastive learning working, and why stronger augmentation helps. More related work are introduced in Appendix E.

To begin with, we give an assumption on the label consistency between positive samples, which means the class label does not change after augmentation.

This assumption is widely adopted (Arora et al., 2019; Wang et al., 2022b; Saunshi et al., 2022) and reasonable. If the augmentation still keeps the basic structure and most of feature information is kept, the class label would not likely to change. Else if the augmentation destroys basic label information, the model tends to learn a trivial solution, so it is meaningless and we do not discuss the situation. The graph data keeps great label consistency under strong augmentation as discussed in Appendix C.3.

To further understand how is data augmentation working in contrastive learning, we use graph edit distance (GED) to denote the magnitude of augmentation, Trivedi et al. (2022) proposes that all allowable augmentations can be expressed using GED which is defined as minimum cost of graph edition (node insertion, node deletion, edge deletion, feature transformation) transforming graph ${\mathcal{G}}^{0}$ to ${\mathcal{G}}^{+}$. So a stronger augmentation could be defined as augmentation with a larger graph edit distance.

This is a natural assumption that is likely to hold because a bigger difference in input will lead to a bigger difference in output. Also we can notice that $\delta_{aug}$ is actually the distance between the anchor node and the augmented node, so $\delta_{aug}$ could naturally represent the alignment performance, a smaller $\delta_{aug}$ means a better alignment. Then Assumption 2.2 means that stronger augmentation would lead to larger $\delta_{aug}$, i.e., worse alignment. This phenomena is common in real practice as shown in Appendix C.3.

Note that we calculate the class center $\mu_{y}$ by averaging nodes from both original view and augmented views. As the augmentation on graphs are highly biased (Zhang et al., 2022), i.e., the mean of augmented nodes are different from the original node, so the class center tends to be different. Also contrastive learning actually learns embedding on the augmented view, so the class gathering result is largely affected by the augmentation, so it is more appropriate to include the augmented nodes when calculate the class center.

With the assumptions, we can get the theorem below:

The proof can be found in Appendix A.1. This shows that the distance between a node and the class center could be represented by the augmentation distance $\delta_{aug}$ and the inter-class/intra-class divergence $\delta_{y^{-}}$, $\delta_{y^{+}}$. We then use positive and negative center distance to represent $\mathbb{E}_{p(v_{y}^{0}|y)}||f(v_{y}^{0})-\mu_{y}||$ and $\mathbb{E}_{p(v_{y}^{0}|y)}||f(v_{y}^{0})-\mu_{y^{-}}||$, respectively.

As we assumed in Assumption 2.2, when the augmentation becomes stronger, augmentation distance i.e., $\delta_{aug}$ would increase. Also we notice that both positive and negative center distance are positively related to the magnitude of augmentation $\delta_{aug}$. Therefore, stronger augmentation separates both inter-class and intra-class nodes, i.e., it helps inter-class separating and hinders intra-class gathering. But the downstream performance tends to be better with stronger augmentation (Wang et al., 2022b; Zhu et al., 2020), so the performance gain may be brought by inter-class separating more than intra-class gathering.

The experiment shown in Figure 1 confirms our suspicion. We use dropout on edges and features to perform augmentation, and the dropout rate naturally represents the magnitude of augmentation i.e., graph edit distance. We present the positive/negative center distance and downstream accuracy to show the changing tendency. Figure 1 shows that initially, as the dropout rate increases, positive center distance is not decreasing, but downstream performance could be enhanced as negative center distance increases sharply. So the better performance correlates to inter-class separating, and the intra-class nodes may not be gathered.

We show the results on more datasets including shopping graph, graph with heterophily and coauthor network in Appendix C.2. From those experiments, we can conclude that contrastive learning mainly contributes to downstream tasks by separating nodes of different classes (increasing negative center distance) rather than gathering nodes of the same class (non-decreasing positive center distance). This explains why contrastive learning can achieve satisfying performance with limited augmentation overlap and relatively weak alignment (Saunshi et al., 2022).

We can also understand the phenomena intuitively, The InfoNCE loss ${\mathcal{L}}_{\mathrm{NCE}}$ can be written as below:

The numerator stands for positive pair similarity, so stronger augmentation would make positive pair dissimilar and the numerator is harder to maximize. Then GCL would pay more attention to the minimize the denominator as shown in Appendix C.5. Minimizing the denominator is actually separating negative samples, and separating negative samples could effectively separate inter-class nodes as most negative samples are from the different classes. In contrast, with stronger augmentation augmentation overlap is still quite rare and positive pair are harder to be aligned, so intra-class nodes are hard to be gathered while the existence of intra-class negative nodes further weaken intra-class gathering. As a result intra-class nodes may not gather closer during contrastive learning. Also we can observe from Figure 1 that when we drop too much edges/features, downstream performance decreases sharply, and both positive and negative center similarity increases as too much information is lost and the basic assumption $p(y|v_{i}^{0})=p(y|v_{i}^{+})$ does not hold, then a trivial solution is learned.

Although GCL with a stronger augmentation may help to improve downstream performance, why it works stays unclear. We need to figure out the relationship between augmentation distance, contrastive loss and downstream performance to further guide algorithm design. We first define the mean cross-entropy (CE) loss below, and use it to represent downstream performance.

It is easy to see that mean CE loss could indicate downstream performance as it requires nodes similar to their respective class center, and different from others class centers. Also it is an upper bound of CE loss ${\mathcal{L}}_{\mathrm{CE}}=\mathbb{E}_{p(v^{0},y)}\left[-\log\frac{\exp(f(v^{0})^{T}\omega_{y}}{\sum_{i=1}^{K}\exp(f(v^{0})^{T}\omega_{i})}\right]$, where $\omega$ is parameter to train a linear classifier $g(z)=Wz$, $W=[\omega_{1},\omega_{2},...,\omega_{k}]$. Arora et al. (2019) showed that the mean classifier could achieve comparable performance to learned weights, so we analyze the mean CE loss instead of the CE loss in this paper.

The proof can be found in Appendix A.2. Theorem 2.6 gives a lower bound on the mean CE loss, we find that when we perform stronger augmentation, the lower bound would be smaller. The smaller lower bound does not enforce a better performance, but it shows a potential better solution. When the lower bound becomes smaller, the best solution is better so the model potentially performs better. For example, if there exists two models with $\hat{{\mathcal{L}}}_{\mathrm{CE}}\geq 0.7$ and $\hat{{\mathcal{L}}}_{\mathrm{CE}}\geq 0.3$ respectively, the latter one would be prefered as it is more likely to perform better, and the former one can never achieve performance better than 0.7. The upper bound instead shows the worst case, smaller upper bound means that the model could perform better at the worst case. From experimental results shown in Appendix C.2, we can observe that the downstream performance tends to be better with stronger augmentation which corresponds to the decreasing lower bound, so the model is powerful enough to be close to the lower bound. Therefore, a smaller lower bound could lead to better performance.

Theorem 2.6 suggests a gap between $\hat{{\mathcal{L}}}_{\mathrm{CE}}$ and ${\mathcal{L}}_{\mathrm{NCE}}$, meaning that the encoders that minimize ${\mathcal{L}}_{\mathrm{NCE}}$ may not yield optimal performance on downstream tasks. Furthermore, it suggests that a higher augmentation distance $\delta_{aug}$ would make the bound smaller and enhance generalization, improve performance on downstream tasks. This aligns with previous finding that a stronger augmentation helps downstream performance. Also Inequality (1) demonstrates that the positive center distance is positively related to $\delta_{aug}$, so better generalization correlates with higher positive center distance. This aligns with the experiments before that better downstream performance may come with a high positive center distance.

Theorem 2.6 also highlights the significance of augmentation magnitude in graph contrastive learning algorithms like GRACE (Zhu et al., 2020). A weak augmentation leads to better alignment but also a weak generalization, InfoNCE loss might be relatively low but the downstream performance could be terrible (Saunshi et al., 2022). When augmentation gets stronger, although perfect alignment cannot be achieved, it promotes better generalization and potentially leads to improved downstream performance. And when the augmentation is too strong, minimizing the InfoNCE loss becomes challenging (Li et al., 2022), leading to poorer downstream performance. Therefore, it is crucial to determine the magnitude of augmentation and how to perform augmentation as it directly affects contrastive performance and generalization.

Due to the inherent connection between contrastive learning and information theory, we try to analyse it through information perspective. As shown by Oord et al. (2018), ${\mathcal{L}}_{\mathrm{NCE}}$ is a lower bound of mutual information. And, $\operatorname*{Var}(f(v^{0})|y)$, $\operatorname*{Var}(f(v^{+}|y))$ and $\operatorname*{Var}(\mu_{y})$ can be represented by inherent properties of the graph and the augmentation distance $\delta_{aug}$. Thus, we can understand the process through information and augmentation, we can reformulate Theorem 2.6 as follows:

The proof can be found in Appendix A.3. Corollary 3.1 suggests that the best augmentation would be one that maximize the mutual information and augmentation distance. Tian et al. (2020) propose that a good augmentation should minimize $I(v^{1};v^{2})$ while preserve as much downstream related information as possible, i.e., $I(v^{1};y)=I(v^{2};y)=I(v^{0};y)$. However, downstream tasks is unknown while pretraining, so this is actually impossible to achieve. Our theory indicates that the augmentation should be strong while preserving as much information as possible, and the best augmentation should be the one satisfying InfoMin which means the augmentation gets rid of all useless information and keeps the downstream related ones. So InfoMin propose the ideal augmentation which can not be achieved, and we propose an actual target to train a better model.

To verify our theory, we propose a simple but effective method. We first recognize important nodes, features and edges, then leave them unchanged during augmentation to increase mutual information. Then for those unimportant ones, we should perform stronger augmentation to increase the augmentation distance.

We utilize gradients to identify which feature of node $v$ is relatively important and carries more information. We calculate the importance of feature by averaging the feature importance across all nodes, the importance of node $v$ could be calculated by simply averaging the importance of its features, and then use the average of the two endpoints to represent the importance of an edge:

where $\alpha_{v,p}$ is importance of the $p^{th}$ feature of node $v$, $\alpha_{p}$ is the importance of $p^{th}$ feature, $\alpha_{v}$ iss importance of node $v$, and $\alpha_{e_{i,j}}$ means the importance of edge $(v_{i},v_{j})$.

For those edges/features with high importance, we should keep them steady and do no modification during augmentation. For those with relatively low importance, we can freely mask those edges/features, but we should make sure that the number of masked edges/features is greater than the number of kept ones to prevent $\delta_{aug}$ from decreasing. The process can be described by the following equation:

where $\ast$ is hadamard product, $\vee$ stands for logical OR, $\wedge$ stands for logical AND. ${\bm{M}}_{e}$, ${\bm{M}}_{f}$ represent the random mask matrix, which could be generated using any masking method, ${\bm{S}}_{e}$, ${\bm{S}}_{f}$ are the importance based retain matrix, it tells which edge/feature is of high importance and should be retained. For the top $\xi$ important edges/features, we set ${\bm{S}}_{e}$, ${\bm{S}}_{f}$ to $1$ with a probability of 50% and to $0$ otherwise. ${\bm{D}}_{e}$, ${\bm{D}}_{f}$ show those edges/features should be deleted to increase $\delta_{aug}$, for the least 2$\xi$ important edges/features, we also set ${\bm{D}}_{e}$, ${\bm{D}}_{f}$ to $0$ with a probability of 50% and to $1$ otherwise.

This is a simple method, and the way to measure importance can be replaced by any other methods. It can be easily integrated into any other graph contrastive learning methods that require edge/feature augmentation. There are many details that could be optimized, such as how to choose which edges/features to delete and the number of deletions. However, since this algorithm is primarily intended for theoretical verification, we just randomly select edges to be deleted and set the number to be deleted as twice the number of edges kept.

In fact, most graph contrastive learning methods follow a similar framework as discussed in Appendix B.1.

In this section, we attempt to analyze InfoNCE loss and augmentation distance from graph spectrum perspective as graph and GNNs are deeply connected with spectrum theory. We start by representing them using the spectrum of the adjacency matrix ${\bm{A}}$.

Theorem 2.6 suggests that we should strive to make ${\mathcal{L}}_{\mathrm{NCE}}$ small while increase $\delta_{aug}$, but they are kindly mutually exclusive. As shown in Theorem 3.2, and Corallary 3.3 proved in Appendix A.4, when $\theta_{i}$ is positive, a small ${\mathcal{L}}_{\mathrm{NCE}}$ requires for large $|\lambda_{i}|$ while a large $\delta_{aug}$ requires for small $|\lambda_{i}|$, and it works exclusively too when $\theta_{i}$ is negative. As contrastive learning is trained to minimize ${\mathcal{L}}_{\mathrm{NCE}}$, $\theta$s are going to increase as the training goes, so we can assume that $\theta$s will be positive, the detailed discussion and exact definition of $\theta$ can be found in Appendix C.1. Therefore, to achieve a better trade-off, we should decrease $|\lambda_{i}|$ while keep InfoNCE loss also decreasing.

In fact, reducing $|\lambda_{i}|$ actually reduces the positive $\lambda_{i}$ and increases the negative $\lambda_{i}$, which is trying to smoothen the graph spectrum and narrow the gap between the spectrum. As suggested by Yang et al. (2022b), graph convolution operation with unsmooth spectrum results in signals correlated to the eigenvectors corresponding to larger magnitude eigenvalues and orthogonal to the eigenvectors corresponding to smaller magnitude eigenvalues. So with enough graph convolution operations, if $|\lambda_{i}|>|\lambda_{j}|$, then we can get the embedding $f(v)$ satisfying $\mathrm{sim}(f(v),e_{i})\gg\mathrm{sim}(f(v),e_{j})$ where $e_{i}$ denotes the eigenvector corresponding to $\lambda_{i}$, causing all representations similar to $e_{i}$. Therefore, an unsmooth spectrum may lead to similar representations and result in over-smooth. This can also be observed from Inequality (4), where a higher $|\lambda_{i}|$ draws $f(v_{i}^{1})$ and $f(v_{i}^{2})$ more similar.

We now know that smoothing the graph spectrum can help with graph contrastive learning. The question is how to appropriately smooth the spectrum. We propose a simple method. As the training aims to minimize ${\mathcal{L}}_{\mathrm{NCE}}$, the parameter $\theta_{i}$s are supposed to increase. Therefore, we can use $\theta_{i}$ as a symbol to show whether the model is correctly trained. When $\theta_{i}$ gradually increases, we can decrease $\lambda$ as needed. However, when $\theta_{i}$ starts to decrease, it is likely that the change on the spectrum is too drastic, and we should take a step back. The process could be described as follows:

where $\alpha$ is a hyperparameter that determines how much we should decrease/increase $\lambda_{i}$. $\epsilon$ is used to determine whether $\theta_{i}$ is increasing, decreasing, or just staying steady. $\mathrm{cur}(\theta_{i})$ and $\mathrm{pre}(\theta_{i})$ represents the current and previous $\theta_{i}$.

In this way, the contrastive training will increase $\theta_{i}$ and result in a lower ${\mathcal{L}}_{\mathrm{NCE}}$, while we justify $\lambda_{i}$ to achieve a better augmentation distance, which promises a better generalization ability. Also some spectral augmentations implicitly decreases $|\lambda|$s as shown in Appendix B.2.

Figure 2 shows that for all three algorithms, our augmentation methodologies can conduct stronger augmentation while preserving similar mutual information. In this way, our methods achieve higher augmentation distance while capturing similar information of the original view. So our methods achieve similar contrastive loss with better generalization, resulting in improved downstream performance.

While reducing $|\lambda_{i}|$, we obtain a graph with smoother spectrum, and could relieve the over-smooth by preventing nodes being too similar with the eigenvector corresponding to the largest eigenvalue. This enables the application of relatively more complex models. We can verify this by simply stacking more layers. As shown in Figure 3, if applied spectrum augmentation, the model tends to outperform the original algorithm especially with more layer, and the best performance may come with a larger number of layers, which indicates that more complicated models could be applied and our method successfully relieve over-smooth.