Mitigating Local Cohesion and Global Sparseness in Graph Contrastive Learning with Fuzzy Boundaries

W1.

We chose Max Pooling as the Comb operator due to its theoretical advantage, however, it is indeed necessary to compare it with other pooling strategies in practice. We have conducted additional experiments on other Comb operators, and the results on node classification are shown in Table 1.

From the results, we could find that the Max Pooling could get the best results across all the datasets since Max Pooling better tightens the samples within each cluster when compared with other general operators. Besides, the samples inside the fuzzy boundary constructed with Max Pooling have the greatest degree belonging to the corresponding cluster, which effectively avoids incurring samples from other clusters.

Table 1. Comparisons among different Comb operators on node classification.

Q1.

I guess you may wonder why we choose to use a coordinate difference that is multiplied by one rather than another scaling factor, and I give the following answers. Firstly, the coordinate difference between crisp and fuzzy representations is used to define an acceptable distance (semantic discrepancy) between positives, which is in line with the condition that the scaling factor is one. Secondly, the membership degree is adjusted adaptively during the training process, which can also be viewed as a scaling factor to construct the fuzzy boundaries, so we do not need to set an additional fixed scaling factor.

Q2.

We chose DGI, GRACE, and BGRL as representative models because they are the three types most representative of current contrastive learning approaches. While these models are not the most recent graph contrastive models, they represent mainstream and fundamental GCL paradigms: (1) DGI focuses on a global-local contrastive framework. (2) GRACE adopts a node-level contrastive framework. (3) BGRL is a non-negative-sample-based GCL method. Even though these models adopt different learning paradigms, they share similar shortcomings in the representation distribution, which implies that the shortcomings originate from the inherent contrastive learning mechanism. Besides, existing advanced GCL models inherit these frameworks, so we think these issues still exist in most GCL models, which could be demonstrated in the quantitative analysis that the advanced models present unideal GMs and TINs.

Q3.

According to the statement in Section 4.3, it is a general condition that a larger “Eps” leads to fewer Mean Groups (MGs), but there also exist special cases where a larger “Eps” leads to great MGs since the “Eps” is too small to form groups. In other words, the DBSCAN algorithm is hard to detect valid groups since the minimal distance between the sparsely scattered samples is greater than “Eps”, and these samples are finally viewed as isolated samples. This can be demonstrated by the results that the “MGs” of GREET with “Eps=0.5” is higher than that with “Eps=0.7”, but the number of total isolated samples (TINs) of GREET with “Eps=0.5” is also more than that with “Eps=0.7”. Therefore, it also inspires us to evaluate the models by comprehensively considering both MGs and TINs but not only one of them. That’s also our motivation to propose the two metrics for evaluating global sparseness and local cohesion.

Q4.

We select SOTA methods for a fair comparison. However, they fail to generate an ideal feature distribution for local cohesion and global sparseness. Including outdated methods may reduce these insights due to performance gaps caused by weaker architectures rather than inherent shortcomings. We highlight that even the SOTA models face the challenge to reinforce the necessity of our model, and a similar comparison method is adopted by [1].

[1]Augmentation-free self-supervised learning on graphs, in AAAI 2022.

Q5.

Negative correlation learning in ensemble methods encourages diversity among individual learners to enhance overall performance. Similarly, the fuzzy boundary construction introduces several different Gaussian membership functions to make each cluster (individual learner) display flexibility and diversity for fitting various samples. This process prevents over-concentration within local groups and enhances the model ability to capture a more globally structured distribution.

A direct analogy can be drawn to ensemble methods that introduce perturbations or penalize excessive similarity between learners, which in our model is to apply the prototypical contrastive loss for enlarging the distances between different clusters. The exploration for regularization techniques from ensemble learning could inspire additional improvements in optimizing fuzzy boundary formation.

W1.

We compare our model with two advanced graph generative models, S2GAE [1] and Bandana [2]. S2GAE reconstructs randomly masked edges while Bandana samples edge masks from a continuous distribution. As shown in Table 1, these graph generative models perform competitively but are limited to small datasets. On large datasets like Ogbn_arxiv, their performance declines due to graph sparsity that limits topology-based knowledge extraction. In contrast, our proposed model can connect and tighten similar samples in the representation space by introducing the fuzzy boundary, which effectively explores the commonalities regardless of dataset size.

Table 1

[1]S2GAE: Self-supervised graph autoencoders are generalizable learners with graph masking, in WSDM 2023.

[2]Masked graph autoencoder with non-discrete bandwidths, in WWW 2024.

W2.

Section B.4 shows that the hyperparameters such as temperature coefficient and penalty coefficient are not sensitive and don’t impact the performance significantly for a given dataset.

Additionally, it is standard to adopt dataset-specific hyperparameters in graph representation learning due to variations in graph properties and sizes, which is easily found in numerous literature [1,2]. For a small dataset like Amazon Photo (a co-purchase network) and a large dataset like Ogbn-arxiv (a citation network), their differences should be addressed with subtle hyperparameter settings. However, for similar datasets, hyperparameters transfer easily, which facilitates the hyperparameter search process. For example, the Amazon Photo and Amazon Computers datasets have similar graph properties (co-purchase networks) and dataset size (this condition also applies to Cora and Citeseer datasets), so the hyperparameters for them are usually similar. It also means that it won’t spend much overhead when knowing more about the dataset properties. Thus, hyperparameter tuning is reasonable and manageable.

[1]Homogcl: Rethinking Homophily in Graph Contrastive Learning, in KDD 2023.

[2]A New Mechanism for Eliminating Implicit Confict in Graph Contrastive Learning, in AAAI 2024.

Q1.

We provide concrete definitions of the terms: (1) A Group is a set of nodes that are close to each other in the embedding space, with the maximal distance between each node pair smaller than pre-defined “Eps”, where “Eps” is a hyperparameter of DBSCAN to limit the maximal distance between the representations in a detected local group. (2) A Group list is a list containing the number of groups detected within each class cluster, with each element in the list corresponding to the number of groups in a given cluster. (3) Isolated nodes are the nodes whose distances between themselves and any other group are greater than “Eps”, and these nodes are not assigned to any group and contribute to global sparseness.

Q2.

To ensure rigor, we supplement Table 2 with results for models without pre-training. Comparisons show that pre-training significantly improves performance, especially on small datasets like Cora. This confirms that pre-training helps extract critical features from the data and gather samples with great similarities to form reliable clusters.

Table 2

Q3.

Fuzzy boundaries dynamically adapt to evolving cluster structures, unlike fixed hyperparameters which fail to adjust to data distribution changes. Since clusters become tight enough during training, the pre-defined hyperparameters may be too large and prone to including samples from other clusters, which degrades the performance quickly.

Besides, Fixed hyperparameters also struggle with feature dimensions of varying scales. Our fuzzy boundary with learnable membership functions flexibly adapts to different feature scales.

Finally, we also provide the experiment results to compare the fuzzy boundary (represented as “Fuzzy”) with the fixed margin expansion in Table 3, which confirms that models with fixed margins require fine-tuning yet still underperform compared with our model, demonstrating the difficulty of using static hyperparameters in a dynamic training process.

Table 3

W1.

The details of the centralization are as follows:

When centralizing the node representations, we use the K-means clustering algorithm to obtain the cluster prototype $C\in\mathbb{R}^{C_p\times d}$, where $C_p$ is the number of clusters, and $d$ is the dimension of the prototype vector. For each node $v_i$ belonging to a specific cluster $k$, we assign it to its corresponding prototype $c_k$ and perform the centralization as follows:

$z_i = h_i - c_k$

where $h_i$ is the original node representation and $c_k$ is the prototype of the cluster that node $v_i$ belongs to. We also provide a matrix form by constructing an assignment matrix $M \in \mathbb{R}^{N\times C_p}$, where $M_{ik}=1$ if node $v_i$ belongs to cluster $k$, and 0 otherwise. Then, the centralized representation can be expressed as:

$Z=H-MC$

where $MC$ selects the corresponding prototype for each node. This modification with the matrix form ensures the dimensions are consistent during the centralization process.

W2.

The visualization of Figure 4(a) is affected by the choice of view angle. To ensure a fair comparison, we have updated the visualization with a new version of Figure 4(a) using a more ideal view angle and supplemented the further analysis in the refined paper. Due to inconvenience in providing images in the rebuttal phase, we only provide the analysis as follows:

For the adjusted angle in Figure 4(a), only three clusters become clearer and the embedding distribution in Figure 4(a) is inferior to Figure 4(b) since most samples in different classes are overlapped together, which further verifies that the fuzzy boundaries have the ability to refine the embedding distribution.

Q1.

Equation 9 aims to tighten samples in a cluster while pushing samples away from different clusters. Specifically, the loss encourages each node representation $h_i$ to be close to its corresponding cluster prototype $p_i$. A lower distance $\||h_i-p_i\||^2_2$ results in a higher probability that pushes representations toward their prototypes, thus tightening clusters.

For better understanding Equation 9, we use a softmax-based probability function that $v_i$ belongs to the corresponding prototype $p_i$ as:

$P(i)=\frac{e^{-\tau\||h_i-p_i\||^2_2}}{\sum_{j=1}^{C_p}e^{-\tau\||h_i-p_j\||^2_2}}=\frac{1}{\sum_{j=1}^{C_p}e^{\tau(\||h_i-p_i\||^2_2-\||h_i-p_j\||^2_2)}}$

where $h_i$ is the representation of node $v_i$, $\tau$ is the temperature coefficient that scales the Euclidean distances. According to the assumption that $v_i$ belongs to the corresponding prototype $p_i$, $\||h_i-p_i\||^2_2-\||h_i-p_j\||^2_2$ is negative in general since $p_j$ is not the corresponding prototype of $h_i$, so $\||h_i-p_j\||^2_2\geq\||h_i-p_i\||^2_2$. A larger $\tau$ will make the denominator smaller, and $P(i)$ becomes larger accordingly, which implies the cluster becomes more compact.

Q2.

Although fuzzy boundary contraction mainly focuses on intra-cluster compactness, the model also ensures inter-cluster separateness through the prototype contrastive loss (Equation 9). The key factor is that the prototype contrastive loss adjusts the distances between the node representation and the prototypes. The training process with Equation 9 pulls the representations and their corresponding prototypes together and pushes representations away from non-corresponding prototypes $p_j$j\neq i$$, which explicitly increases inter-cluster distances.

Additionally, the fuzzy boundaries also implicitly enhance inter-cluster separateness, which is explained in Figure 6(b) and Figure 6(c). Concretely, the fuzzy clusters include both real samples (also forming the inner real clusters) and fuzzy boundary elements that are always outside the real samples. When the training process ends, the virtual fuzzy boundary elements are removed and the distances between the inner real clusters are further enlarged. As a result, the clusters embody higher intra-cluster compactness and inter-class separateness merits.

Thus, the combination of fuzzy boundary and prototype contrastive loss results in both intra-cluster compactness and inter-cluster separateness, achieving the desired global structural distribution.

W1.

Following your kind suggestion, we provide a related work compassing graph prototype learning as follows:

Graph prototypical learning has emerged as a significant direction in graph representation learning, addressing limitations in traditional contrastive and few-shot learning approaches. Existing GCL methods are limited to sub-optimal representations due to sampling bias where semantically similar graphs are incorrectly treated as negatives. To overcome this, PGCL introduces a clustering-based approach by grouping semantically similar graphs and ensures that negative samples come from different clusters [1]. Similarly, GPCL [2] enhances GCL by integrating both node-level and prototype-level contrastive objectives, maintaining consistency across different augmentations. To further capture global semantic structures, GraphLoG [3] employs K-means clustering to derive hierarchical prototypes. At the same time, X-GOAL [4] extends prototypical learning to multiplex heterogeneous graphs for aligning embeddings across different relational layers. In the domain of few-shot learning, GPN [5] leverages meta-learning to extract transferable prototypes for node classification with scarce labels. Similarly, S4GPN [6] integrates self-supervised learning with prototypical networks to improve hyper-spectral image classification. These advancements demonstrate the effectiveness of prototype-based graph learning in mining cluster-level semantic consistency which is important for realizing ideal global structural distribution.

[1]Prototypical graph contrastive learning, in TNNLS 2024.

[2]Graph prototypical contrastive learning, in INS 2022.

[3]Self-supervised graph-level representation learning with local and global structure, in ICML 2021.

[4]X-GOAL: Multiplex heterogeneous graph prototypical contrastive learning, in CIKM 2022.

[5]Graph prototypical networks for few-shot learning on attributed networks, in CIKM 2022.

[6]Self-supervised spectral-spatial graph prototypical network for few-shot hyperspectral image classification, in TGRS 2023.

W2.

Thanks for your careful observation regarding Figure 2. To address this issue, we have revised Figure 2 by (1) adopting a different line shape to represent the local groups, and (2) replacing the samples inside the local groups with crisp representations. The updated model architecture will be provided in the refined paper to avoid misinterpretation.

Q1.

The difference in visualization between the two figures is attributed to different data processing. For realizing the 3-dimension visualization in Figure 4, we first condense the raw data into a 3-dimension feature space with graph auto-encoder, then use the crisp and the proposed fuzzy models to train the 3-dimension features for visualization. Since the raw data is condensed into a low-dimension feature space from a high-dimension space, the data information is heavily lost, which presents terrible visualization. Even so, the proposed fuzzy model could also gather similar samples in the clusters, which leads to much clearer decision cluster boundaries when compared with the crisp model.

The visualization in Figure 6 is general t-sne. We first apply the proposed model to train the raw graph data, and then implement the t-sne algorithm on the produced representations. In this case, the models could preserve more critical information in the feature space than in the 3-dimension space, which makes Figure 6 have much better visualization than Figure 4.