PaperlayerView exact revision on arXiv

Source-linked AI summary

Hard Sample Aware Network for Contrastive Deep Graph Clustering

Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Zhen Wang, Ke Liang, Wenxuan Tu, Liang Li, Jingcan Duan, Cancan Chen

arXiv:2212.08665v3cs.LGcs.AI

TL;DR

Contrastive deep graph clustering needs better hardness measurement and attention to hard positive as well as hard negative pairs. HSAN combines attribute-structure similarity with dynamic weighting guided by high-confidence clustering information. The paper reports superiority and effectiveness across six datasets, while noting that its fixed confidence threshold may be improved by future learnable or dynamic designs.

  • Problem

    Existing hard-sample methods overlook structural information in similarity measurement and neglect hard positive pairs, including low-similarity samples within the same cluster.

  • Method

    HSAN combines attribute and structural similarities with high-confidence pseudo-label-based dynamic weighting that up-weights hard pairs and down-weights easy ones.

  • Results

    HSAN demonstrates superiority and effectiveness over classical, contrastive, and hard-sample-mining methods across six datasets.

  • Takeaways & Limitations

    By focusing contrastive learning on both hard positive and hard negative pairs, HSAN further improves sample discriminative capability.

  • Takeaways & Limitations

    The confidence threshold is fixed, and the authors identify learnable or dynamic confidence selection as future work.

Abstract

from arXiv · show

Contrastive deep graph clustering, which aims to divide nodes into disjoint groups via contrastive mechanisms, is a challenging research spot. Among the recent works, hard sample mining-based algorithms have achieved great attention for their promising performance. However, we find that the existing hard sample mining methods have two problems as follows. 1) In the hardness measurement, the important structural information is overlooked for similarity calculation, degrading the representativeness of the selected hard negative samples. 2) Previous works merely focus on the hard negative sample pairs while neglecting the hard positive sample pairs. Nevertheless, samples within the same cluster but with low similarity should also be carefully learned. To solve the problems, we propose a novel contrastive deep graph clustering method dubbed Hard Sample Aware Network (HSAN) by introducing a comprehensive similarity measure criterion and a general dynamic sample weighing strategy. Concretely, in our algorithm, the similarities between samples are calculated by considering both the attribute embeddings and the structure embeddings, better revealing sample relationships and assisting hardness measurement. Moreover, under the guidance of the carefully collected high-confidence clustering information, our proposed weight modulating function will first recognize the positive and negative samples and then dynamically up-weight the hard sample pairs while down-weighting the easy ones. In this way, our method can mine not only the hard negative samples but also the hard positive sample, thus improving the discriminative capability of the samples further. Extensive experiments and analyses demonstrate the superiority and effectiveness of our proposed method.

Introduction

Existing hard-sample methods overlook structural information in similarity measurement and hard positive pairs. HSAN addresses both issues with attribute-structure similarity and dynamic weighting of hard pairs.

  • Existing methods neglect structural information when measuring hardness, weakening the representativeness of selected hard negative samples.
  • Previous methods focus on hard negatives but overlook low-similarity positive pairs within the same cluster.
  • HSAN combines a comprehensive similarity criterion with a dynamic sample weighting strategy for contrastive deep graph clustering.
  • The method uses high-confidence clustering pseudo labels to identify potential positive and negative sample pairs.
  • HSAN dynamically up-weights hard sample pairs and down-weights easy ones, covering both positive and negative pairs.
  • Experiments on six datasets demonstrate the superiority and effectiveness of the proposed method.

Related Work

Deep graph clustering uses neural networks to divide graph nodes into disjoint clusters, while contrastive learning has become an increasingly used approach. Related work emphasizes sample selection and develops several hard negative mining strategies, but commonly neglects hard positive pairs.

  • Deep graph clustering encodes nodes with neural networks and divides them into disjoint clusters.
  • Contrastive mechanisms have succeeded across images, graphs, and knowledge graphs, motivating their adoption in deep graph clustering.
  • Positive and negative sample selection is a key factor in contrastive learning performance.
  • GDCL uses clustering pseudo labels to correct negative-sample selection bias, while ProGCL filters false negatives and expands the negative set through interpolation.
  • Existing graph methods explore hard negative mining through curriculum learning, local structure patterns, or probability-based hardness measures.
  • Previous methods neglect hard positive sample pairs, which can lead to sub-optimal performance.

Method

HSAN combines attribute and structure information to measure sample similarity, then uses high-confidence clustering information to dynamically emphasize hard positive and negative pairs during contrastive learning.

  • Attribute and Structure Encoding: HSAN uses separate attribute and structure encoders to embed both node attributes and graph structural information.
  • Attribute and Structure Encoding: The attribute-structure similarity function combines attribute and structural cosine similarities through a learnable trade-off parameter to better reveal sample relations.This similarity measure assists hard sample mining by incorporating both information sources.
  • High-Confidence Pair Guidance: K-means clustering produces pseudo labels, after which the method selects high-confidence samples using their distances to cluster centers.The pseudo relations identify likely positive and negative sample pairs.
  • Hard Sample Aware Contrastive Learning: HSAN extends contrastive learning with a weight-modulating function that dynamically adjusts pair weights during training.The function uses the proposed similarity measure and pseudo labels, while retaining the original InfoNCE setting for pairs lacking high-confidence samples.
  • Hard Sample Aware Contrastive Learning: The weighting strategy up-weights hard positive and negative pairs and down-weights easy pairs, directing the loss toward samples with weaker appropriate similarity.For positive pairs, low similarity indicates greater pulling difficulty; analogous weighting is applied to negative pairs.

Experiments

HSAN is evaluated against thirteen deep graph clustering methods across six benchmark datasets using four clustering metrics and repeated runs. The experiments include quantitative comparisons and 2D t-SNE visualizations of learned embeddings.

  • Experimental Setup: The experiments evaluate CORA, CITE, AMAP, BAT, EAT, and UAT benchmark datasets.The dataset information is summarized in the appendix.
  • Experimental Setup: Experiments compare HSAN with thirteen state-of-the-art methods across six benchmark datasets.The baselines are grouped into classical deep graph clustering, contrastive deep graph clustering, and hard sample mining methods.
  • Experimental Setup: The reported clustering results use four metrics, with mean values and standard deviations averaged over ten runs.Table 2 identifies the best and runner-up results using red and blue values, respectively.
  • Embedding Visualization: Figure 3 visualizes learned node embeddings with 2D t-SNE, using CORA in the first row and AMAP in the second.The figure compares seven methods across the two datasets.
  • Comparison Results: HSAN surpasses classical and other contrastive graph clustering methods, while addressing hard-positive and structural-information omissions in existing hard-sample methods.On CORA, HSAN exceeds ProGCL by 18.99% in NMI.

Ablation Study

Ablation and sensitivity analyses examine HSAN’s similarity and weighting components, confidence parameter, embedding structure, and convergence behavior. The results support the contributions of both components while identifying dataset-dependent confidence settings.

  • Component Ablation: Combining the attribute-structure similarity function S and weight modulating function M achieves the strongest clustering performance among the ablation variants.On CORA, Ours exceeds the baseline by 8.48% in NMI.
  • Component Ablation: The similarity function S improves the baseline by incorporating both attribute and structure information into sample similarity.This combination is described as better revealing potential relations between samples.
  • Component Ablation: The weighting function M improves the baseline by guiding the network to focus on hard sample pairs.The stated effect is enhanced discriminative capability of samples.
  • Hyper-parameter Analysis: Performance is promising for τ ∈[0.1, 0.3] on BAT and CITE, and for τ ∈[0.7, 0.9] on the other datasets.The confidence parameter is fixed in this paper, with learnable or dynamic confidence proposed as future work.
  • Convergence Analysis: The loss and clustering ACC gradually converge after 350 epochs, while the proposed loss achieves better performance than infoNCE after 50 epochs.The proposed loss is larger because it down-weights easy pairs and up-weights hard pairs.

Conclusion

HSAN mines hard samples in contrastive deep graph clustering by combining attribute and structure information with dynamic weighting of positive and negative pairs. The paper reports effectiveness and superiority, while noting fixed confidence as future work.

  • HSAN combines attribute and structure encoders with comprehensive similarity measurement to reveal potential sample relations.
  • High-confidence clustering information guides dynamic weighting that up-weights hard sample pairs and down-weights negative ones.
  • The hard sample aware contrastive loss focuses the network on both positive and negative pairs to improve discriminative capability.
  • Time and space analyses indicate that the proposed loss does not bring large costs compared with classical infoNCE loss.
  • Experiments demonstrate the effectiveness and superiority of HSAN, while the fixed confidence parameter motivates learnable confidence as future work.

Details of the Proposed Method

The paper identifies its arXiv version and presents an implementation section centered on PyTorch-style pseudocode for the proposed method.

  • The document is identified as arXiv version 3, dated 28 January 2023.
  • The implementation section introduces the method using PyTorch-style pseudocode.
  • Algorithm 1 is presented as the PyTorch-style pseudocode of the proposed method.

Additional Experiments

Additional experiments address comparison and visualization analyses, extending the paper’s experimental reporting beyond its original pages.

  • The supplementary section conducts additional experiments because of limitations in the original paper pages.
  • The additional experiments include comparison experiments.
  • The additional experiments also include visualization analysis experiments.

Statistics and Hyper-parameter Settings

The paper reports statistics and hyper-parameter settings for HSAN in Table 1 to support reproducibility.

  • Table 1 reports the statistics summary of the proposed method.
  • Table 1 reports the hyper-parameter settings of the proposed method.
  • The reported statistics and settings are intended to guarantee reproducibility.

Additional Comparison Experiments

Additional experiments compare HSAN with deep clustering, classical deep graph clustering, and contrastive deep graph clustering methods across six benchmark datasets. The analyses also examine the focusing factor β and trade-off parameter α.

  • Comparison Results: HSAN outperforms the compared contrastive deep graph clustering method on six benchmark datasets.The comparison evaluates clustering performance using four metrics with mean and standard deviation.
  • Comparison Results: Deep clustering methods achieve un-promising performance because they overlook graph structure.
  • Comparison Results: Classical deep graph clustering methods cannot compare with HSAN, which benefits from contrastive learning’s supervision information capture capability.
  • Hyper-parameter Analysis: HSAN performs better when the focusing factor β is in the range [1, 2].As β increases, the down-weighting rate of easy positive and negative sample pairs also increases.
  • Hyper-parameter Analysis: The learnable trade-off parameter α is optimized to around 0.4 on the CORA and CITESEER datasets.α is initialized at 0.99999 for the analysis.
Loading 2212.08665v3…