Coloring Learning for Heterophilic Graph Representation
Miaomiao Huang, Yuhai Zhao, Daniel Zhengkui Wang, Fenglong Ma, Yejiang Wang, Meixia Wang, Xingwei Wang
Graph self-supervised learning aims to learn the intrinsic representations of graph structures from unlabeled data. Although graph contrastive learning (GCL) has achieved remarkable progress by generating perturbed views through data augmentation and optimizing sample similarity, its performance is poor in heterophilic graph scenarios (where connected nodes are likely to belong to different classes or exhibit dissimilar features). In heterophilic graphs, existing methods typically rely on random or carefully designed augmentation strategies (e.g., edge dropping) to create contrastive views. However, such graph structures exhibit intricate edge relationships, where topological perturbations may completely alter the semantics of neighborhoods. Moreover, most methods focus solely on local contrastive signals while neglecting global structural constraints. To address these limitations, inspired by graph coloring, we propose a novel Coloring learning for heterophilic graph Representation framework, CoRep, which: 1) Pioneers a coloring classifier to generate coloring labels, explicitly minimizing the discrepancy between homophilic nodes while maximizing the discrepancy of heterophilic nodes. A global positive sample set is constructed using multi-hop same-color nodes to capture global semantic consistency. 2) Introduces a learnable edge evaluator to guide the coloring learning process dynamically and utilizes the edges' triplet relationship to enhance its robustness. 3) Leverages Gumbel-Softmax to differentially discretize color distributions, suppressing noise via a redundancy constraint and enhancing intra-class compactness. Experimental results on 14 benchmark datasets demonstrate that CoRep significantly outperforms current state-of-the-art methods.