Coloring Learning for Heterophilic Graph Representation
Authors: Miaomiao Huang
Yuhai Zhao
Zhengkui Wang
Fenglong Ma
Yejiang Wang
Meixia Wang
Xingwei Wang
Venue: NeurIPS 2025 poster ()
Keywords: Graph Representation
Graph Self-Supervised Learning
Primary area: general_machine_learning
TL;DR: We propose a self-supervised coloring learning framework for heterophilic graph representation, which effectively captures both local and global structures without relying on delicate augmentation strategies.

Abstract: Graph self-supervised learning aims to learn the intrinsic graph representations from unlabeled data, with broad applicability in areas such as computing networks. Although graph contrastive learning (GCL) has achieved remarkable progress by generating perturbed views via data augmentation and optimizing sample similarity, it performs poorly 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) for 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 that 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 dynamically and utilizes the edges' triplet relations 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.

Coloring Learning for Heterophilic Graph Representation
Miaomiao Huang Yuhai Zhao 12.,, Zhengkui WangS, Fenglong Ma²,
Yejiang Wang'. Meixia Wang Xingwei Wang*
School of Computer Science and Engineering, Northeastern University, China Key Laboratory Intelligent Computing Medical Image of Ministry of Education, Northeastern University, China
3 InfoComm Technology Cluster, Singapore Institute of Technology. Singapore
College of Information Sciences and Technology, Pennsylvania State University, United States
(huangmiaomian wangyejiang, meixiawang lasraannggnsttmall.mmmmmm neu. edu.cn,
(zhaoyuhai, wangxw] @mail neu. edu. cn, zhengkui. www.::/wwwwggggggttttteoooo edu sg, f fenglong@psu. edu
Abstract
Graph self-supervised learning aims to learn the intrinsic graph representations from unlabeled data, with broad applicability in areas such computing networks. Although graph contrastive learning (GCL) has achieved remarkable progress by generating perturbed views via data augmentation and optimizing sample similar- ity, it performs poorly in heterophilic graph scenarios (where connected nodes are likely belong different classes or exhibit dissimilar features). In heterophilic graphs. existing methods typically rely on random or carefully designed augmenta- tion strategies (e.g., edge dropping) for contrastive views. However, such graph structures exhibit intricate edge relationships, where topological perturbations may completely alter the semantics 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: I) Pioneers a coloring classifier to generate coloring labels, explicitly minimizing the discrepancy between homophilic nodes while maximizing that 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 eval- uator to guide the coloring learning dynamically and utilizes the edges' triplet relations to enhance its robustness. 3) Leverages Soonbel-Softax differentially discretize color distributions, suppressing noise via a redundancy constraint and enhancing intra-class compactness. Experimental results 14 benchmark datasets demonstrate that CoRep significantly outperforms current sate-of-the-aan methods.
Introduction
Self-supervised graph representation learning aims to extract effective low-dimensional representa- tions from graphs without label supervision, which has been widely applied various fields, such as bioinformatics, social networks, and computing networks [48 33 In recent years, graph contrastive learning (GCL) has been identified as one of most promising self-supervised graph learning methods & 32 GCL primarily consists of two core components: data augmentation and contrastive loss. The former employs various augmentation techniques to create perturbed views for an anchor
*Corresponiigg author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

graph, while the latter maximizes the similarity between two views of the same anchor (i.e., positive pairs) and minimizes the similarity between two views from different anchors (i.e., negative pairs).
Although effective for graphs with strong homophily (where adjacent nodes commonly share similar labels or features) [50), these methods fall short when applied to heterophilic graphs. In heterophilic graphs, connected nodes may belong to different classes or exhibit dissimilar attributes [3] (0) This property is prevalent in many real-world graph structures. For example, in molecular networks, protein structures are typically formed by covalently bonded amino acids of various types Similarly, in online transaction networks, fraudsters tend establish links with legitimate users [6
47
Recent studies have increasingly focused on graph contrastive learning under heterophily. Existing methods typically explore two main directions: structural decoupling and adaptive augmentation strategies. Structure decoupling- baadd approaches [27 48 explicitly separate homophilic and heterophilic structures within the graph based on node or topological similarity, and apply random perturbations (e.g., edge dropping) to each type of structure to construct contrastive views. In contrast, adaptive augmentation-basee -ased approaches [4 o aim to generate augmented views through carefully designed strategies or learnable generators to better preserve heterophilic connection patterns.
However, the approaches above still suffer from two inherent limita- tions. First, they heavily rely on random or carefully designed aug- mentation strategies. However, for heterophilic graphs with complex adjacency structures, such augmentation is challenging and fragile, as may drastically alter the semantics of the neighborhood. For exam-
ple, in an online transaction network (as illustrated in Figure [(a). fraudsters (brown nodes) tend to establish connections with legitimate users (blue nodes). Applying topological perturbations to such a highly heterophilic structure (as shown in Figure ((b) may weaken the sparse yet crucial intra-group connections among fraudsters (brown-brown connections), thereby concealing their collaborative behavior. More- over, it may mistakenly introduce connections among users (blue-blue connections), disrupting the clear fraud patterns. Such alterations can significantly destroy the semantics of neighborhoods and hinder the model from identifying the underlying behaviors of fraudsters. Sec- ond, most approaches concentrate solely on local signals to enforce node-level alignment, which neglects global structural constraints. Con- sequently, models may overemphasize the consistency of the same node across views while overlooking important relationships among semanti- cally related nodes, thereby sacrificing overall intra-class cohesiveness and inter-class discrimination.
(a) An online transaction net- work with brown fraudsters and blue users.
2
(b) Topological perturbations disrupt the key connections.
Figure 1: Illustrations of an online transaction network.
To address the challenges, we propose a novel Coloring learning for heterophilic graph Representation framework (CoRep) that aims to assign colors nodes within the graph such that the colors of adjacent nodes reflect their type differences. Specifically, unlike GCL approaches that depend on data augmentation, CoRep proposes to employ a coloring classifier to generate similar coloring labels to homophilic nodes to explicitly encourage their representations to be close, while assigning different coloring labels to heterophilic nodes to push their representations apart. To dynamically guide the coloring learning, we introduce a learnable edge evaluator that integrates feature and structural information identify the property of node pairs, while utilizing the edges' triplet relationship to enhance its robustness. Furthermore, we use the Gumbel-Softmax technique for differentiable discretization of color distributions, combined with a pparsity-inducing redundancy constraint to suppress noise and enhance intra-class compactness. To capture global structural consistency, we construct the positive sample set using multi-hop same-color neighbors, thereby ensuring that distant yet semantically related nodes are aligned. Our main contributions can be summarized as follows:
We propose a CoRep framework for heterophilic graph representation learning through the gener- ated coloring labels, which effectively captures both local and global structures without relying on delicate augmentation strategies.
CoRep leverages a learnable edge evaluator and a global positive sample set to capture homophily and heterophily more precisely. Moreover, it utilizes a Guumbel-Softmax trick for differentiable discretization, along with a sparsity constraint to enhance intra-class compactness.
We conduct extensive experiments on 14 benchmark datasets, ranging from relatively citation networks to Wikipedia networks. Experimental results demonstrate that CoRep consistently surpasses state-of-the thet--rr homophilic and heterophilic graph learning methods.

---

2 Related Work
Graph Neural Networks with Heterophily. Heterophilic graphs have been widely observed in various scenarios, such as dating networks, online transaction networks, and molecular networks 45]. To better model heterophily structures, recent approaches have proposed a series of Graph Neural Network (GNN) models 23 based on different aggregation mechanisms. including adaptive message propagation [ 49
16 36 47
43 26]. fregffrreuency signal exploration [4. [3 23], ego
and neighbor separation [57] 53 and latent neighbor discovery [20) [54] [1O]. Despite their success, these methods often rely on external supervision signals. However, high-quality labels are often searce in real-world settings. Unlike these methods, this paper focuses self-supervised learning for heterophilic graphs, aiming to generate discriminative node representations without label supervision.
sele-vuuer Learning on Graphs. Graph self-supervised learning (SSL) has been a promising paradigm for learning representations without labels [2) Early studies often utilize random walks or graph reconstruction [5 for graph embedding, but they may lose topological information. GCL methods [8 59 53) have attracted considerable attention, aiming to maximize similarity between positive pairs. However, such methods are built upon strong homophily assumption and perform poorly under heterophily. Until recently. people started to explore SSL on heterophilic
carefully then align the augmented positive pairs. However, they heavily rely on effective augmentations, where perturbations the topology may significantly alter the semantic relationships of neighbors. Differentially, we perform SSL by assigning distinct colors to different types of nodes, fully preserving the structural properties of heterophilic graphs. See Appendix A. for more details.
graphs. These methods generate perturbed views by leveraging random 227 48 56
designed augmentation strategies 44 7 [),
Graph Coloring. Graph coloring problem (GCP) is one of the most classical problems in graph theory [1S] (24. and has received much attention in many real-world applications, e.g., air traffic flow management (2). register allocation [55), and job scheduling [5]. Its objective is to find way to assign colors (i.e., coloring labels) to the nodes of a graph such that no two adjacent nodes share the same color while using few colors possible. Schuetz al. (37 proposes to treat graph coloring as a multiclass node classification task and utilize a Potts model for unsupervised learning. In our work, the notion of coloring is used as heuristic inspiration rather than solving the classical GCP directly. Instead of enforcing distinct colors for adjacent nodes, we extend the coloring concept to heterophilic graph learning: nodes are encouraged to share the same or different colors according to their homophilic or heterophilic relations. This relaxation, combined with a learnable edge evaluator, allows us to capture both affinity and disparity between nodes, thereby facilitating effective representation learning on heterophilic graphs. See Appendix A.2 for more details.
3 Methodology
In this section, we elaborate on our Coloring learning for heterophilic graph Representation (CoRep). The core design of CoRep is illustrated in Figure which comprises three key components: edge evaluation, edge-aware coloring matching learning, and multi-hop neighborhood contrastive learning. In edge evaluation module, we introduce a learnable edge evaluator that evaluates the properties of node pairs to dynamically guide the coloring learning (Section 3.3). In edge-aware coloring matching learning module, we learn a coloring classifier to generate coloring labels that explicitly encourage similarity between homophilic nodes and dissimilarity between heterophilic nodes (Section 3.4). In edge-aware coloring matching learning module, we construct the positive sample set using multi-hop same-color neighbors to capture global structural consistency (Section 3.5).
3.1 Notations and Problem
Let G = (V,E) denote an undirected graph, where V= [....... Un represents the set of n nodes and & C V x V represents the set of edges. The adjacency matrix and the node feature matrix are denoted as A E 10,1) and X E Raxdd respectively, where Aij the raw feature of node v; E V. and Laplacian matrix is defined as L= I, D- D-1/2/10/0// 1D2 AD2122 where D E R=** is a diagonal degree matrix with D,,: Σj Ar,y and ln denotes the identity matrix. Let [[a]]] = {1,..... n) C N. For node u, N ((.)) fu, E Vl(e,, vy)) E E} is its neighbors, and (v:) ;= |M (vx) is its degree. We define |.1
if (1;, U;) &, x; E R the input feature dimension. The normalized graph
3

---

Input Graph
Edge Evaluation
High Heterophily
Heterophilic
Relaiio
Lower
Random
high Homophily
Higher
Homophilic
Encode
Guide
Calibrate
OH
Closer
Heterophilic
Dissimilar
E
Positive
LMI
OB
Similar
Farther
Homophilic
2-hop
Negative
Edge-aware Coloring Matching L
Learning
Multi-hop Neighborhood Contrastive earning
Figure 2: framework of CoRep.
as the number of elements, |- |] represents the concatenation operation. In this work, we focus on solving the node-level self-supervised graph representation learning problem. Given = (V, E), we aim to learn an encoder fo G - Raxdd (dt < d) in an unsupervised manner to map the nodes in G into the d' oi-dimensional representations, where 0 denotes the parameter of the encoder. These representations preserve graph structures, which can be utilized for downstream tasks, like node classification.
3.2 Coloring Matching Learning
In general, obtaining distinguishable node representations in heterophilic graphs without externally supervised signals is challenging problem. The primary reason lies the intricate and interwoven connections within heterophilic graphs. Previous GCL methods [27 43 44
7 6
typically rely
on either random or carefully designed augmentation strategies, which tend to cause a complete alteration of neighborhood semantics. For instance, illustrated in Figure 1, disconnecting links between fraudsters can obscure fraudulent group behaviors. A natural idea is to leverage the inherent properties of heterophilic graphs for representation learning. Fortunately, graph coloring, which assigns different colors (i.e., coloring labels) to adjacent nodes, offers an effective way for our purpose. Inspired by this, propose coloring matching learning scheme coloring learning for heterophilic graph representation. We first encode the structural information of the graph, and then leverage coloring matching to prompt the model to learn distinet coloring labels for adjacent nodes of different types, thereby better adapting to the heterophily structure.
preliminary exploration of
as the graph encoder fo 9 - Rexd to utilizes attention mechanism adaptively capture both low- and high-ffrquency signals in G, enabling the effective aggregation from different neighbors. Considering the importance of positional information in recognizing heterophily, we introduce the positional encoding [14] into the attention mechanism to enhance global structural awareness. Each node ;; receives d -dddimensional position encoding P: through d' steps random walk-based based diffusion:
Structural Encoding. We first employ an adaptive GNN
extract node representations.
TE.. T2 1,0
T E Rd
where T = AD represents the diffusion transition matrix. See Appendix F.4 for additional details regarding positional encoding. The attention mechanism is defined as:
a! tanh (CT
w
(6)) (6(0)
ll vh 6 659))
where 6:9) h000 vo h(th) E a is the node representation at the 1-th iteration, th : Rd d
and wh dR Ra are mapping layers, g(!) denotes weight, and tanh(-) is activation function. The node representation h, (1+1) at the (I + 1)-th iteration is updated in a cessage-passingg manner as:
(++1) = Eh. +
Σ (v,))
(
(3)
(v:)

---

where h100) = (x4)x)) denotes a transformed node feature by applying nonlinear mapping layer 4/2 Rd + Rdd, (vs) is the neighbors of node vi (v;) is the degree of vi, and & is a scaling hyperparameter. The output of the last layer h. is denoted as h; where L is the number of layers.
Coloring Matching. After obtaining the node representations, our objective is to ensure they are well-suited to the heterophily property. Excitingly, we observe that the objective of the graph coloring problem is highly aligned with our learning goal, providing a novel insight for addressing structural heterophily. Graph coloring aims to assign different colors to adjacent nodes while minimizing the number of colors. Let Xe N denote the number of available colors, the coloring function Soot V + [xe] assigns a color to node vi, where [xs] (1,...,Xcr ) To evaluate the validity of a coloring scheme, the conflict function 5 :V x + {0, 1] is defined as follows:
< wy) = {0. otherwise
[1, if (v:) = Coa (vy) and (vi, 1y)) E
(4)
The objective of graph coloring is to learn a coloring function Soot that minimizes the total conflicts (1,, my)] while reducing the number of used colors Xg. However, this solution fails to address two fundamental issues: 1) The inherent diversity of relational patterns. Heterophilic graphs commonly encompass both heterophilic and homophilic connections, yet this solution cannot distinguish these connection patterns and semantic relationships effectively. 2) The intractabiliiyy of direct optimization. The graph coloring task is inherently a computationally complex combinatorial optimization task, making its direct application to heterophilic graph representation learning difficult to solve in practice.
3.3 Edge Evaluation
To address the challenge posed by diverse relational patterns, this section introduces an edge evaluation module. Its core idea lies in the accurate identification of homophilic and heterophilic edges, thereby providing dynamic guidance for the coloring learning process. To achieve this, we introduce a learnable edge evaluator f& G + _ax= that integrates feature and structural information to estimate the homophily probability of node pairs Specifically. in heterophilic graphs, relying solely on raw features is insufficient to distinguish node relationships. while positional encodings provide complementary global structural information that enhances node distinguishability. Thus, they are fed into two nonlinear feature mapping layers ΦΙ : Rd++d -> IR and Φ2 R2dd + R to estimate the homophily probability Way for U)):
[27], where e denotes the parameter of the evaluator.
X = th ([x: ll p.]), x = s (bx ll pz)): Wi, = (x>( x31) + (2x) II xD)) /2
where x Rd denotes a transformed feature, where d is mapping dimension. To more accurately represent edge properties, we aim to sample from wi,, to obtain a discriminative result. However, this process introduces con-differentiability issue. To address this, we adopt the Gumbel-Max reparameterization trick [28] 19 to provide smooth approximation of the sampling process:
Wi Sigmoid ((wi) + log = - log(1 - -w))/Tm.)
where Wi,y is the homophily score on (v;, 0z). higher value implies a higher homophily between U; and uy. while lower value indicates higher heterophily. w ~ Uniform(O,) 1) denotes the sampled Gumbel random variate, Sigmoid(-) is the activation function, and Tm denotes the temperature hyperparameter. As Tm approaches 0, samples from the Gumbel-Max distribution become binary.
3.4 Edge-aware Coloring Matching Learning
The previous section establishes the foundation for our method, CoRep, by identifying the types of node pairs in the graph. In the following, we will assign similar coloring labels to homophilic node pairs to encourage their representations to be close, while assigning different coloring labels to heterophilic node pairs to push them apart. However, as the second challenge discussed in Section 3.2 the combinatorial optimization problem in coloring matching difficult to solve directly. Motivated by 37 we transform the optimization problem into penalty-based loss function, and propose a coloring matching loss and a coloring redundancy constraint to guide the model in generating reasonable coloring labels, thus adapting to the complex structure of heterophilic graphs. Furthermore,
5

---

based on the generated coloring labels, a triplet relation ranking loss is proposed to calibrate the edge evaluator, enabling more accurately capture the relational properties of node pairs.
Coloring Matching Loss. We first propose to employ a coloring classifier f.p: : Rdd' Rx that
maps each node to a latent label space, yielding soft coloring labels _, fo (h:), where denotes the parameter of the classifier. To quantify conflicts within the graph, we redefine the conflict function 5 as a similarity metric function A IRx9 x Rxş - [0, 11, which measures the similarity of pairs of nodes the label space. Based on the homophily score Wa.j. we encourage adjacent homophilic nodes to share similar coloring labels, while heterophilic nodes are assigned dissimilar ones to reduce overall conflicts in the graph. Accordingly, we propose a coloring matching loss as:
Lm = ((5))
Σ NEE
Σ (wz)
(1 (5-) A(Ti; TT2)
where ()::) denotes similarity metric function, e.g., cosine similarity. This design in the Equation 7 enables CoRep to directly capture the semantic relations between node pairs based on intrinsic graph structure, leading to more discriminative node representations.
Coloring Redundancy Constraint. In practice, the coloring classifier may assign excessive or semantically uninformative color classes when fitting heterophilic structures, leading to redundant colors that introduce noise and reduce intra-class compactness. To mitigate this issue, we leverage the Gumbel-Softmax trick [19] to approximate discrete color sampling in differentiable manner, allowing for more diverse color assignments, and propose a sparsity-inducin coloring redundancy constraint that encourages each node to be confidently assigned to more relevant color suppres diffuse and noisy color distributions:
exp ((log(TTg) + pcg)/To) Σ exp (Iog(TT.)) + 26) 2/))
Ls
Σ jE[xol
mmax (10 he(m)) Gool
(8)
jElxa]
where Pmaz R" + R is column-wise max pooling operator, 2y denotes a sampled Gumbel random variate and To is temperature parameter. In our work, we set a small To to encourage Ee approach a one-hot vector. Egge provides an effective way to explore diverse color assignments to avoid deterministic selection that may lead to suboptimal local minima.
Triplet Relation Ranking LOss. The coloring learning process described above relies on the reliability of edge relations. However, accurately evaluating these connections without supervision signals is inherently difficult. To dynamically calibrate the edge evaluation, design triplet relation ranking loss that controls the deviation between the homophily and heterophily degrees of node pairs and the similarity of their assigned coloring labels, ensuring that the output of the evaluator accurately reflects their relationships. Specifically, we randomly sample a node pair (Up, 22y from the input graph and aim for all node pairs satisfy the following relationship: A (c,, 22) E & > (Uir v2) b V (ui, 0y) G where > represents an ordering relation such that tn > (1 means ty is ranked before (1, 6 and G represent the sets of homophilic and heterophilic edges:
= -(11)) U5) (ri, U3) ~ IThomo ( 8, = { (1s, v5) | (Ma,2)) ~ hetee (1 - (1,) (9)
where hoom (w).s) and Ih (1- - denote the probability distribution based on the scores wis and wx respectively. IIhomo (ar,)) is used to sample node pairs with higher homophily, while Ih (1 (ر is used to sample node pairs with higher heterophily. By leveraging the above triplet relation ranking to ensure that the similarity of node pairs with homophily is ranked higher than randomly sampled node pairs, while the similarity of node pairs with heterophily is ranked lower than randomly sampled node pairs, we can dynamically calibrate the joint optimization of edge evaluation and representation learning. To enforce this ordering, we propose a triplet relation ranking loss to penalize the ranking errors of node pairs:
C, = Σ (1 (i.z)) log (a (Apad Amal)) ييsة log (1 (A Andd EL,
A mat)
(10)
where A = A A(Ti, Tz) and Arnd A (ps Tr) denote the semantic similarity between (v,, and between (ep, vy), respectively.

---

3.5 Multi-hop Neighborhood Contrastive Learning
Due the inherent heterophily of the graph structure, semantically similar nodes are often distributed in non-adjacent topological regions. Relying only on locally connected neighbors is insufficient to capture the global semantic consistency. To address this, we design robust multi-hop neighborhood contrastive learning module that compels our model to preserve the semantic consistency of long- range neighbor nodes. This module identifies multi-hop neighbors with the same semantics through positive sample selection and aligns their representations using a contrastive loss.
Positive Sample Selection. To identify distant yet semantically related nodes, we propose to construct the global positive sample set using multi-hop neighbor nodes that share the same colors. Specifically, we leverage Efco and E determine whether two nodes e; and Vj are semantically related. Based on this, the semantically related x hop neighbor nodes are selected as the positive sample set:
Po(u: U3 Vj ( E5 EGool
(11)
where N (1;) denotes the neighbor nodes of node es within x hops, which is defined as follows: (u:) = (wx) if (r))))) = ((xx))())) (U)) ((s)) if x
Multi-hop Neighborhood Contrastive Loss. Given the positive sample set above, further design a multi-hop neighborhood contrastive loss, which aims to bring distant yet semantically related multi-hop neighbor nodes closer, while pushing apart other nodes. Specifically, we utilize projector fo Ed + dd map each node representation into dF-dimensional latent representation z, = (h.) for a fair comparison, where denotes the parameter of the projector. Inspired by the InfoNCE contrastive loss [59], the multi-hop neighborhood contrastive loss is defined as:
C. = - Σ (P((:.)
exp (sim(z;, 2;)mZZ
log
(12)
exp (sim(z, TT)/Te
(TEP)()))
PLEV
where sim(..-) denotes consine similarity, and Te a temperature hyperparameter.
3.6 Overall Loss
As the coloring label distribution approaches uniformity, node representations become less distin- guishable. We introduce an entropy regularization term L. Lie["] ...' log क, to encourage the generation of more definitive coloring labels. Hence, the overall loss then formulated as:
L Lm + aCa + BC, + 7Le + n.c
(13)
where a, B, y, and 1) are trade-off hyperparameters. We present the overall algorithm in Appendix B
3.7 Complexity Analysis
In this section, we analyze the time complexity of CoRep. Let [V] and |E| be the number of nodes and edges. For the computation of positional encodings and multi-hop neighborhoods, their com- plexities are ([V(EE) and [[V](E) Note that these two steps are computed at once. For the edge evaluator and graph encoder, their costs are O( Vld (d + dF) + (E)d)) and ( (IV) + [E]). CoRep contains three core losses: f.m. fy,, and f.. and their complexities are O(xo (E), (xgl and ((V) bxdd), where & denotes the average number of positive samples (k < [V), and b is the batch size of the loss. Detailed complexity analysis can be found in Appendix
4 Experiments
This section empirically evaluates the proposed CoRep method on 14 benchmark datasets and analyzes its behavior on graphs to gain further insights. More results can be found in the Appendix F
4.1 Experimental Setup
Datesets. To assess the quality of the learned representations, we employ transductive node clas- sification as the downstream task. Our experiments are conducted on 14 widely used benchmark
7

---

Table 1: Results in terms of classification accuracies (in percent + standard deviation) on homophilic benchmarks. The best and second-best performance under each dataset are marked with boldface and underline, respectively. OOM indicates Out-Of-Memory.
Methods
Cora
CiteSeer
PubMed
Wiki-CS
Computers
Photo
CS
Physies
GCN
81.50=#1.30
70.30+ 28
28.80+2.90
76,89=0.37
86.3420.48
92.35=0.255
93.10=00.11
95,54+0.11
GAT
12.80+1.30
71.30+0049
78.50+0.27
77.42+0.19
87.06+00.35
92,64+40.2
92.41
95.45++0.17
MLP
56.11=0.34
56.91:0.42
71.35+0.05
72.02:::211
73.88+0.10
78.54::0.05
90:42::0088
93.54:0.05
H2GCN
80,23+00.20
69.97-4066
78.79+0.30
79.73++0.1
84.32-00.52
91.86++0.27
91.18++0.58
93.56+0048
FAGCN
77.00=0.66
69.81 80
06.7440.66
74.34:0.53
83.51:11004
92.72:40.22
23.8110.24
96. 96.16:#0.15
PC-Conv
82.47-00.56
69.92-41.33
79.57+1.23
79.94-00.2
87.89+0.266
93.89+0.14
94.244-0112
95.99+0.14
DeepWalk Walk
69.47=00.55
58.82:0.61 61
1.287+1.22
74.35:0.06
85 68.08600.06
89,44::0111
91.77=0.15 84.61+0.22
node2vec
71.24400.89
0.77
66.477+1100 1.00
71.79+00.05
84, 34.39-00.88
89.67+0012
85.08+00.03
91.19-00.04
GAF
71.07=00.39
65,22:1::33
71.73++0.92
70.15::0.01
85.27:10.19
91.62:40.13
90.01
94,92++0.07
VGAE
79.81+00.87
66.75++0.37
77.16+0.31
75.63++0.19
86.374-0211
92.20+0.11
92.11+0.09
94.52+00.0
DGI
02.29:00556
71.49:10.14
77.43+00.84
75.73=10.13
84.09
91.49:+0.25
91,95+0.400
94.57=0.38
GMI
12,51+1.447
71.56-+0.56
09.83-0.90
75.06-+0.13
81.76-+-0.52
90.72.40.33
0OM
OOM
MVGRL
83.03=00.27
72.75:1046
0..63+0.38
77.97:10118
87.09:0.22
92.01=0.113
91.97:00.19
95.53:10.10
GRACE
80.08=0.53
71.41=0.38
80.15+0.34
79.16=0.33
87.2110,44
92.65=0.32
92.78+10.23
05.3
GCA
80.39=0042
71.21:10.44
80.37+0.77
79.35=00112
87.84+1.227
92.78:10.17
92.324+011
95.87=10.15
BGRL
81.08=0.17
71.5940.42
79.97
78.74:0.22
88.92410.33
93,24:0.29
93.2610.36
95.76
HGRL
80.66=0.43
68.56:11110
80.35+0.588
76.68:10.17
84.30:0.47
93,53=0022
93.99110.15
OOM
GREET
83.32-#0.49
12.20:11011
80.5010.66
79,87-1049
87.55
92.99
94.68-10,21
95.9110.14
HeteGCL
81.55:00.65
70.63++1.16
82.50+0.57
79.1240..25
85. 85.76+0..21
93.82.40.22
94.79:-0.06
00M
CoRep
85.04=0.34
73.67:1.40
83.50
82.20-10.51
89.1713.81
93.84:1.89
94.3910.31
96.2110.11
datasets, consisting of 8 homophilic graph datasets (i.e.. Cora. CiteSeer, PubMed, Wiki-CS, Amazon Computers, Amazon Photo, CoAuthor CS, and CoAuthor Physics) [38 29 39
and 6 heterophilic
graph datasets (i.e., Chameleon, Squirrel, Actor, Cornell, Texas, and Wisconsin) 31 of all datasets are summarized in Appendix[D) [D]
The statistics
Baselines. We compare CoRep with 5 groups of baseline methods, including 1) supervised/semi-
supervised learning methods (i.e. GCN (22). GAT 42), and MLP), 2) supervised learning methods
specially designed for heterophilic graphs (i.e. H2GCN (77. FAGCN 4,, and PC- CC-Conv (3 ), 3) conventional unsupervised graph representation learning methods (i.e., DeepWalk [35], 2ode2vec
[17,
GAE, and VGAE (21 4) contrastive self-supervised learning methods (i.c., DGI [41), GMI
34 MVGRL 18), GRACE [59]. GCA (60) and BGRL 40)), and 5) contrastive self-supervised learning methods designed for heterophilic graphs (i.e., HGRL (6) GREET 277. and HeteGGI. 44
Evaluation Protocol. For CoRep and all unsupervised baselines, we follow the standard linear evaluation protocol of previous state-of-the-art graph self-supervised learning approaches the node classification task [50 6) where linear classifier is trained on top of the frozen representation, and test accuracy is used proxy for representation quality. For datasets, we adopt the standard dataset splits used in previous studies, i.e., public splits (52 |2 31 or commonly used splits [60 27].
Experimental Details. All methods were implemented in PyTorch with the Adam Optimizer. We run 10 times of experiments and report the average test accuracy with standard deviation. For fair comparison, the parameters of all baselines tuned according to the parameter ranges reported by the authors. Specific hyperparameter settings and more implementation details are in Appendix H.
4.2 Performance Comparison
Table 1 and Table 2 display the node classification results for 8 homophilic datasets and 6 heterophilic
datasets, respectively. Comparing the results in Tables [ and 2 we have the following major observations. First, we find that our CoRep outperforms all baseline methods in 10 out of 14 benchmarks and achieves the second and third-best performance on the remaining 4 benchmarks. For example, CoRep achieves accuracies of 85.04% and 82.20% on the Cora and Wiki-CS datasets, respectively. which is a relative improvement of over 1.72% and 2.26% compared to the best baselines. For heterophilic graphs, CoRep achieves a relative improvement of over 5.71% and 2.97% on the Squirrel and Texas datasets compared to the best baselines. The superior performance indicates that coloring learning on heterophilic graphs can produce expressive and generalizable representations. Moreover, we also observe that CoRep significantly outperforms conventional and contrastive unsupervised graph learning methods, surpasses neterophily-oriente unsupervised learning methods in 85.71% of cases, and outperforms supervised learning methods under heterophily
8

---

Table 2: Results in terms of classification accuracies (in percent standard deviation) on heterophilic benchmarks. The best and second-best performance under each dataset are marked with boldface and underline, respectively. OOM indicates Out-Of-Memory.
Methods
Chameleon
Squirrel
Actor
Cornell
Texas
Wisconsin
GCN
29.63.12.32
36,28.11.5 52
30.8310.77
57.03-13.30
4..00.1..80
56,47.16.55
GAT
56.3812.19
32.09:1..27
28.06
59.4611..6
61.6213.78
54.7116.87
MLP
46.91=2.15
29.28=1.33
35.66=0.94
81.0847.93
81.62=5.51
84,31+3,40
H12GCN
19.39.11.98
37.90.12.02
35,8611103
82.16.14.80 80
84,86.16.77
86.67.14.69
FAGCN
63.44:12.05
41.17=1.99 1.94
36.81-0.26
81.3545.005
84.32=6.022
83,33:22,01
PC-Conv
53.20=11.00
35.79:10.62
36.07=0.661
78.65++2.70
85.68=2.97
88,63++2,94
DeepWalk
47.74:12.005
32.93-11.58
22.7810.64
39.1815..57
46.49
33,53:14,92
node2vec
41.93:t:.29
22.84:10.72
2..2
42.9411.46
41.92:7.776
37.45:47.09
GAB
33.84.12.777
28.03:1:1.61
1..03
58.85
58 4.55
3..85.13.80
VGAE
35.22.12.71
29 1..4
1..9911.56
59.19114.09
59.20 49.20.14.26
56.67:15.51
DGI
39.95:t:.75
01.80
29.82++0.69
63.35-1-4.1
70.59
5.99
GMI
46.97.13.43
30.1111..92
27.82.10.90
54.76.15.06
50.4911..21
45.98.12.76
MVGRL
51.07:2.668
35.4711.229
30.02.1.700
64.30115.43
62.38-5.61
62.37.1..22
GRACE
48.05=11881
31.33-#1.22
29.01=0,78
64.86-16.95
57.57=5.68
50.00=5.83
GCA
19.80=#1.81
35.50=+0.91
19.65=+147
55.41+4.566
59.46=6.116
40.78:+4.06
BGRL
47.46.12.74
32.64.10.78
29.86.10.75
57.3015.51
59.1915.88
52.3511.112
HGRL
1..29:#1.64
35.79:10.89
36.97-00998
79.46:14.45
82.16=66.00
8.,28
GREET
63.09+22.18
40.86++1.93
1.07
73.78+3.64
85.41=3.67
14.1244..76
HeteGCL
48.77:11.55
34.2711.558
37.5
81.32:1.266
82.37-5.83
80.3945.23
CoRep 65.64+1.39
46.88:11.56
37.32+1.13
82.70++4.55
88.65=33.97
86.86+3.17
in 85.71% of cases as well. This result suggests that goal consistency between coloring learning and heterophilic graph learning can facilitate the model's effective adaptation to heterophily structures.
4.3 Ablation Study
To examine the contribution of key designs in CoRep, we consider the following ablations. (A1) We remove the edge-aware color- ing matching learning (w/o Col. Mat.), where the hard assign- ment ar jegmaxeelxel Jijj of predicted coloring labels is directly used to guide positive sample selection in multi-hop neighbor- hood contrastive learning. (A2) We remove the learnable edge evaluator (w/o Ed. Eva.). where the coloring matching loss is computed directly from the coloring labels without using edge evaluation. (A3) We remove the Gumbel-Softtax technique (w/o Gum. Soft.), where the hard assignment ar grgmazzexx=]
Table 3: Ablation studies results
(mean classification accuracy) on the Cornell and Texas datasets.
Ablation
Cornell
Texas
Al w/o Col. Mat.
70.00
77.57
A2 w/o Ed. Eva.
76.49
85.95
Gum. Soft.
77.57
82.16
A4 w/o Ca
79.73
85,95
A5 w/o C.
81.62
86.49
w/o C.
75.14
84.32
A4+A5
78.92
85.14
replaces the node's color Gool in Equation (11) to identify the
A4+A6
73.78
83.78
A5+A6
74.59
78.65
positive sample set. (A4) We remove the coloring redundancy constraint (w/o La) by setting a 0. (A5) We remove the triplet relation ranking loss (w/o L,) by setting 3 = O. (A6) We remove
CoRep
82.70
88.65
the multi-hop neighborhood contrastive loss (w/o L.e) by setting 7 O. We show the ablation study results in Table (More results can be found in the Appendix[F]] A1 has significant impact on the model's performance, highlighting the importance of edge-aware coloring matching learning. The introduction of A2 and A3 further improves its performance, indi- cating the efffectiveness of edge evaluation and the Gumbel-Softmax. The performance degradation observed in A4, A5, and A6 highlights the critical role of the loss terms L,, L,, and C. in CoRep, as they are essential for maintaining intra-class compactness, edge discriminability. and global structural consistency, respectively. We also observe that the combination of losses La, Lr, and Le yields better results compared to using each loss individually. The complete model (last row) achieves the best performance, demonstrating that the different components of the proposed CoRep framework are complementary and work synergistically.
From Table we can see that
4.4 Parameter Analysis
In this section, we perform a detailed sensitivity analysis on the number of colors and neighborhood hops. Additional hyperparameter experiments can be found in Appendix F22

---

Effect of the Number of Colors Xg. We vary
XG from 5 to 20 with a 5-umit interval exam-
Acturaoy (88)
Accursay (R0)
ine its impact on the model. The classification accuracies under different XG choices are shown
80
60
Oudia
in Figure 3(a) We observe that the best results across Seer, Cornell, and Texas datasets of- ten occur when Xg is relatively large. This phe- nomenon suggests that appropriately increasing the number of colors helps the model uncover un- derlying semantic information. Meanwhile, the coloring redundancy constraint ensures intra-class compactness to avoid introducing irrelevant colors.
90
50
(a) XG
(b) x
Figure 3: Parameter sensitivity of Xg and x.
Effect of the Neighhorhood Hops x. We then vary neighborhood hops x to investigate the model's sensitivity to the neighborhood scope. As shown in Figure [5b] we observe that superior performance obtained using only one-hop neighbors on the CiteSeer dataset, suggesting that local structures are sufficient to reflect class consistency highly homophilic graphs. In contrast, the Cornell and Texas datasets, relying on multi-hop neighbors leads to better performance, indicating that in highly heterophilic graphs, incorporating broader structural information helps preserve features of distant yet semantically related nodes, thereby maintaining global semantic consistency.
5 Conclusion
In this paper, inspired by graph coloring. we proposed a coloring learning for heterophilic graph representation (CoRep). Unlike prevailing GCL approaches that rely heavily on carefully designed augmentations, our method focuses on assigning distinct colors to different types of nodes, Specif- ically, we: 1) Pioneered coloring classifier to generate similar/dissimilar coloring labels to ho- mophilichheterppiili nodes to encourage them to be closer/farther; Constructed global positive sample using multi-hop same-color neighbors capture global structural consistency. 2) Intro- duced learnable edge evaluator to guide the coloring learning dynamically and utilized edges' triplet relationship enhance its robustness. 3) Leveraged the Gumbel-Softtax and redundancy constraint to enhance intra-class compactness. Extensive experiments on 14 benchmark datasets showed the effectiveness of CoRep. The limitations and broader impacts of CoRep are discussed Appendix H
Acknowledgments
We thank the anonymous reviewers for their constructive suggestions. This project was part sup- ported by the following projects: the National Natural Science Foundation of China (No.62432003).
References
[1] Lu Bai, Zhuo Xu, Lixin Cui, Ming Li, Yue Wang, and Edwin Hancock. HC-GAE: The hierarchical cluster-based graph auto-encoder for graph representation learning. Advances in Neural Information Processing Systems, 37:127968-12788
2024.
[2] Nicolas Barnier and Pascal Brisset. Graph coloring for air traffic flow management. Annals of Operations Research, 130:163-178. 2004.
[3] Wendong Bi, Lun Du, Qiang Fu, Yanlin Wang, Shi Han, and Dongmei Zhang. Make heterophilic graphs better fit gnn: A graph rewiring approach. IEEE Transactions on Knowledge and Data Engineering, 2024.
[4] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3950-3957, 2021.
[5] Assia Brighen, Hachem Slimani, Abdelmounaam Rezgui, and Hamamache Kheddouci. A new distributed graph coloring algorithm for large graphs. Cluster Computing, 27(1)885-8911, 2024.
[6] Jingfan Chen, Guanghui Zhu, Yifan Qi, Chunfeng Yuan, and Yihua Huang. Towards self- supervised learning on graphs with heterophily. In Proceedings of the 3 ACM International Conference Information & Knowledge Management, pages 201-211, 2022.
10

---

[7] Jingyu Chen, Runlin Lei, and Zhewei Wei. PolyGCL: Graph contrastive learning via learnable spectral polynomial filters. In The Twelfth International Conference on Learning Representa- lions, 2024.
[8] Yuzhou Chen, Jose Frias, and Yulia R Gel. Top graph contrastive learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 1453-11461, 2024.
[9] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In Interationall Conference on Learning Representations, 2020.
[10] Siddhartha Shankar Das, SM Ferdous, Mahantesh M Halappanavar, Edoardo Serra, and Alex Pothen, AGS-GNN: Attribute- Atrribute-uiide sampling for graph neural networks. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 538-549, 2024.
[11] Bowen Deng, Lele Fu, Jialong Chen, Sheng Huang, Tianchi Liao, Zhang Tao, and Chuan Chen. Towards understanding parametric generalized category discovery on graphs In Forty-second International Conference on Machine Learning.
[12] Bowen Deng, Tong Wang, Lele Fu, Sheng Huang, Chuan Chen, and Tao Zhang. Thesaurus: contrastive graph clustering by swapping fused wasserstein couplings. Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 16199-16207, 2025.
[13] Rui Duan, Mingjian Guang, Junli Wang, Chungang Yan, Hongda Qi, Wenkang Su, Can Tian, and Haoran Yang. Unifying homophily and heterophily for spectral graph neural networks via triple filter ensembles. Advances in Neural Information Processing Systems, 37:93540-935611 2024.
[14] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference on Learning Representations.
[15] Agoston E Eiben, Jan K Van Der Hauw, and Jano van Hemert. Graph coloring with adaptive evolutionary algorithms. Journal of Heuristics, 4:25-46, 1998.
[16] Junyuan Fang, Han Yang, Jiajing Wu, Zibin Zheng, and Chi K Tse. What contributes more to the robustness of heterophilic graph neural networks? IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2025.
[17] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 855-864, 2016.
[18] Kavch Hassani and Amir Hosein Khasahmadi. Contrastive multi-viww representation learning on graphs. In International Conference on Machine Learning, pages 4116-4126. PMLR, 2020.
[19] Eric Jang, Shixiang Gu, and Ben Poole. rategorical reparametrizatiio with gumble-softman In International Conference on Learning Representations, 2017.
[20] Di Jin, Zhizhi Yu, Cuiying Huo, Rui Wang, Xiao Wang, Dongxiao He, and Jiawei Han. Universal graph convolutional networks. Advances in Neural Information Processing Systems, 34:10654-10664, 2021.
[21] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1111v:1611.07338, 2016.
[22] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[23] Bingheng Li, Erlin Pan, and Zhao Kang, PC-Conv: Unifying homophily and heterophily with two-fold filtering. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 13437-13445, 2024.
11

---

[24] Wei Li, Ruxuan Li, Yuzhe Ma, Siu On Chan, David Pan, and Bei Yu. Rethinking graph neural networks for the graph coloring problem. arXiv preprint arXiv:2208.06977 2022.
[25] Langzhang Liang, Fanchen Bu, Zixing Song, Zenglin Xu, Shirui Pan, and Kijung Shin. Mit- igating over-squashing in graph neural networks by spectrum-preservinn sparsification. In Forty-second International Conference on Machine Learning.
[26] Langzhang Liang. Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi. Sign is not a remedy: Multiset-to-multise message passing for learning on heterophilic graphs. arXiv preprint arXiv:2405.20652, 2024.
[27] Yixin Liu, Yizhen Zheng. Daokun Zhang, Vincent CS Lee, and Shirui Pan. Beyond smooth- ing: Unsupervised graph representation learning with edge heterophily discriminating. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4516-4524, 2023.
[28] Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. arXiv preprint arXiv: 1611.0072, 2016.
[29] Péter Mernyei and C Cangea. Wiki-cs: A wikipedia- benchmark for graph neural networks. arXiv preprint arXiv:2007.000 02900,, 2020.
[30] Junjun Pan, Yixin Liu, Xin Zheng, Yizhen Zheng, Alan Wee-Chung Liew, Fuyi Li, and Shirui Pan. A label-free heterophily- approach for unsupervised graph fraud detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 12443-12451, 2025.
[31] Hongbin Pei, Bingzhe Wei, Kevin Chen Chuan Chang. Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In 8th International Conference Learning Repre- sentations, 2020.
[32] Tianhao Peng, Haitao Yuan, Yongqi Zhang, Yuchen Li, Peihong Dai, Qunbo Wang. Senzhang Wang, and Wenjun Wu. Tagrec: Temporal-aware graph contrastive learning with theoretical augmentation for sequential recommendation. IEEE Transactions on Knowledge and Data Engineering, 2025.
[33] Wei Peng. Zhengnan Zhou, Wei Dai, Ning Yu, and Jianxin Wang. Multi-network graph contrastive learning for cancer driver gene identification. IEEE Transactions on Network Science and Engineering, 2024.
[34] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pages 259-270, 2020.
[35] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 701-710, 2014.
[36] Lingfei Ren, Ruimin Hu, Zheng Wang, Yilin Xiao, Dengshi Li, Junhang Wu, Yilong Zang, Jinzhang Hu, and Zijun Huang. Heterophilic graph invariant learning for out-of-distributiin of fraud detection. In Proceedings of the 32nd ACM International Conference on Multimedia, pages 11032-11040, 2024.
[37] Martin J. A. Schuetz, J. Kyle Brubaker, Zhihuai Zhu, and Helmut G. Katzgraber. Graph coloring with physics-inspired graph neural networks. Physical Review Research, 4:043131, 2022.
[38] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Bliassi- Rad. Collective classification in network data. Al Magazine, 29(3):93-93, 2008.
[39] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint / 2018.
[40] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. In ICLR 2021 Workshop Geometrical and Topological Representation Learning, 2021.
12

---

[41] Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations.
[42] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations. 2018.
[43] Botao Wang, Jia Li, Heng Chang, Keli Zhang, and Fugee Tsung. Heterophilic graph neural networks optmization with causal message- gressage-passing. In Proceedings of the Eighteenth ACM International Conference on Web Search and Data Mining, pages 829-837, 2025.
[44] Chenhao Wang, Yong Liu, Yan Yang, and Wei Li. HeterGCL: graph contrastive learning framework heterophilic graph. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 2397-2405, 2024.
[45] Kun Wang, Guibin Zhang, Xinnan Zhang. Junfeng Fang, Xun Wu, Guohao Li, Shirui Pan, Wei Huang, and Yuxuan Liang. The heterophilic snowflake hypothesis: Training and empower- ing gnns for heterophilic graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 3 3164-3175, 2024.
[46] Yejiang Wang, Yuhai Zhao, Zhengkui Wang. Ling Li, Jiapu Wang, Fangting Li, Miaomiao Huang, Shirui Pan, and Xingwei Wang. Equivalence is all: unified view for self-supervised graph learning. In Forty-second International Conference on Machine Learning.
[47] Zichen Wen, Yawen Ling, Yazhou Ren, Tianyi Wu, Jianpeng Chen, Xiaorong Pu, Zhifeng Hao, and Lifang He. Homophily-related. Adaptive hybrid graph filter for multi-view graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 15841-15849, 2024.
[48] Zengyi Wo, Minglai Shao, Wenjun Wang, Xuan Guo, and Lu Lin. Graph contrastive learning via interventional view generation. In Proceedings of the ACM Web Conference 2024, pages 1034, 2024.
[49] Teng Xiao, Zhengyu Chen, Donglin Wang, and Suhang Wang. Learning how to propagate messages in graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1894-1903, 2021.
[50] Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for graphs. Advances in Neural Information Processing Systems, 35: 620-634, 2022.
[51] Liang Yang, Weixiao Hu, Jizhong Xu, Runjie Shi, Dongxiao He, Chuan Wang, Xiaochun Cao, Zhen Wang, Bingxin Niu, and Yuanfang Guo. Gauss: Graph-customized universal self-supervised learning. In Proceedings of the ACM Web Conference 2024, pages 582-593, 2024.
[52] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, pages 40-48. PMLR, 2016.
[53] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
[54] Zhizhi Yu, Bin Feng, Dongxiao He, Zizhen Wang. Yuxiao Huang, and Zhiyong Feng. Lg-gnn: Local-global adaptive graph neural network for modeling both homophily and heterophily. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, pages 2513, 2024.
[55] Wenshuo Yue, Teng Zhang. Zhaokun Jing, Kai Wu, Yuxiang Yang. Zhen Yang, Yongqin Wu, Weihai Bu, Kai Zheng, Jin Kang, et al. A scalable universal ising machine based on interaction-centric storage and compute-in-ment memorr.. Nature Electronics. (10):904-913) 2024.
13

---

[56] Yuhai Zhao, Yejiang Wang, Zhengkui Wang, Wen Shan, Miaomiao Huang, and Xingwei Wang. Graph contrastive learning with progressive augmentations. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. I, pages 2079-2088, 2025.
[57] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7800 2020.
[58] Jiong Zhu, Gaotang Li, Yao-An Yang, Jing Zhu, Xuehao Cui, and Danai Koutra. On the impact of feature heterophily on link prediction with graph neural networks. arXiv preprint arXiv:2409. 17475, 2024.
[59] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint arXiv:2006.00 000::0006.0411,,, 2020.
[60] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 202/, pages 2069-2080, 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our study aims to propose novel coloring learning framework to address the challenge of self-supervised learning on heterophilic graphs, and we have made this claim clear in the Abstract and Introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have stated the limitations of the proposed CoRep model in the Appendix.
Guidelines:
The answer NA means that the paper has no limitation, while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model cell-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
15

---

Answer:
[NA]
Justification:
There are no theoretical results in this paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide full explanations and implementation details for the proposed CoRep model in the main paper and in the appendix. All datasets required for the exper- iments are public datasets. We run 10 times of experiments and report the average test accuracy with standard deviation in the Experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
16

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification: We provide the source code and data supplementary material in the sub- mission. In addition, we believe that the main paper and appendix provide sufficient experimental details to ensure the reproducibility of our model.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
mniiss.cc/public//ee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We present the experimental setup in the main text and provide details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For all experiments using the CoRep model, we provide the mean and standard deviation of 10 runs on widely used or random splits.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide the experimental platform in the main paper and appendix, includ- ing the settings of hardware, hyper-parameters, and so on, as well as providing the time complexity of the model.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htt.t///i..////////.//.////////a
Answer: [Yes]
Justification: We followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discuss both potential positive societal impacts and negative socictal impacts of the work performed in Appendix.
Guidelines:
18

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We use the public datasets for experiments in this paper and have cited the original paper that produced the dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
19

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
20

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt:p///earrrppccc/ooooeereeee/ /ct/////oeeeeeecc//22////.. for what should or should not be described.
21


Reviews:
[{"review_id": "anbEhHHHxm", "reviewer": "Reviewer_avE4", "summary": "This paper addresses the limitations of graph contrastive learning (GCL) on heterophilic graphs, where existing methods rely on random augmentations and neglect global structural constraints. The proposed CoRep framework introduces a coloring-based approach: 1) a coloring classifier generates labels to minimize homophilic and maximize heterophilic node discrepancies, with multi-hop same-color nodes forming global positive sets; 2) a learnable edge evaluator guides coloring learning using triplet relationships; 3) Gumbel-Softmax and redundancy constraints enhance intra-class compactness. Experiments on public datasets show CoRep outperforms SOTA methods, with ablation studies validating each component's effectiveness.", "questions": "Please refer to the limitations part.", "limitations": "n/a", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall, the manuscript does not have significant flaws; however, some methodological details and certain experimental aspects need to be further supplemented and clarified, as outlines below.\n\n1. In Section 3.2, regarding the structural encoding, the authors state that \"Each node $v_i$ receives a $d^\\#$ \\-dimensional position encoding $\\mathbf{p}_i$ through $d^\\#$ steps random walk-based diffusion\" (with Eq. 1). The details and role of this position embedding (PE) require further clarification. Specifically, the authors should specify the value of $d^\\#$, and clarify whether the PE, once initialized, is treated as a trainable parameter during the entire network training process. Furthermore, it is important to discuss the impact of PE on both homophilic and heterophilic graphs. An ablation study regarding the effectiveness of PE should be provided.\n    \n2. The complexity analysis in Section 3.7 is well presented. However, the authors should also compare the time complexity of the proposed method with that of the baselines. Additionally, reporting the actual time and space complexity in practice (such as training time) would make the results more convincing.\n    \n3. The datasets selected for the ablation study (Table 3) are relatively small. Conducting ablation experiments on larger datasets would provide a more comprehensive evaluation of the contribution of each component.\n    \n4. The authors should further elaborate on the detailed settings of the ablation experiments, as the current description is somewhat too brief. Please provide detailed configurations for each ablation study. Given the overall framework, the removal of certain key components may affect the subsequent structure, and any ambiguous settings need to be clarified. For example, in the A3 setting, after removing Gumbel-Softmax, how is positive sample selection conducted in Multi-hop Neighborhood Contrastive Learning?\n    \n5. The visualization results (Figure 5) are very informative. Considering that this work focuses on unsupervised learning on heterophilic graphs, why not also provide visualization results on a heterogeneous graph to intuitively demonstrate the effectiveness of CoRep for heterophilic graphs?", "was_revised": true, "final_justification": "The authors have responded to my comments and the previous concerns were addressed. I would like to keep my rating as weak accept.", "rebuttal": ">**In Section 3.2, regarding the structural encoding, the authors state that \"Each node vi receives a d^# -dimensional position encoding pi through d^# steps random walk-based diffusion\" (with Eq. 1). The details and role of this position embedding (PE) require further clarification. Specifically, the authors should specify the value of d^#, and clarify whether the PE, once initialized, is treated as a trainable parameter during the entire network training process. Furthermore, it is important to discuss the impact of PE on both homophilic and heterophilic graphs. An ablation study regarding the effectiveness of PE should be provided.**\n\nWe appreciate the reviewer's suggestion. We clarify the details and certain experiments as follows. (1) Following [1,2], we set the dimension of the position embedding (PE) $d^\\sharp$ to 16 in all experiments. This choice achieves a balance between information effectiveness and computational efficiency: it is sufficient to encode meaningful structural information of the graph while keeping memory usage and training overhead within a reasonable range. (2) The PE is computed once via the random walk-based diffusion process and remains fixed (non-trainable) during training. This design allows the PE to serve as a stable structural prior independent of the specific task, which helps prevent overfitting and promotes better generalization across datasets. (3) To evaluate the impact of PE, we conducted an ablation study by removing it from the model in Table I. From Table I, the model's performance drops when PE is removed, highlighting the utility of PE in capturing long-range and structurally meaningful dependencies. We also observe that PE contributes more significantly to heterophilic datasets such as Texas and Cornell, where local feature aggregation is less informative and global structural cues from PE help guide the learning process. We will include this clarification and the ablation study in the revised version. \n\nTable I. An ablation study on position embedding (PE).\n|Ablation|Cornell|Texas|Chameleon|Photo|CS|\n|--------|-------|-----|---------|-----|---|\n|w/o PE|81.08±2.70|85.95±5.24|64.78±1.36|93.20±2.36|94.12±0.23|\n|CoRep|**82.70±4.55**|**88.65±3.97**|**65.64±1.39**|**93.84±1.89**|**94.39±0.31**|\n\n[1] Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating. AAAI 2023.\n\n[2] Graph neural networks with learnable structural and positional representations. ICLR 2022.\n\n>**The complexity analysis in Section 3.7 is well presented. However, the authors should also compare the time complexity of the proposed method with that of the baselines. Additionally, reporting the actual time and space complexity in practice (such as training time) would make the results more convincing.**\n\nThank you for your valuable suggestion. We have added the theoretical time and space complexities of our method and baseline methods during training in Table II for clearer comparison. Additionally, we report the actual training time of these methods in Table III. The results show that our method achieves comparable running speed to BGRL, one of the most efficient graph contrastive learning methods, and even outperforms it on larger datasets such as PubMed, CS, and Physics. This improvement is primarily attributed to sparse computation and mini-batch processing. Furthermore, compared to other baselines, our approach demonstrates significant efficiency advantages. For example, on the Physics dataset, our method is approximately 45 times faster than GREET. We will include these results in the revised version.\n\nTable II. The time and space complexities of the six methods.\n|Methods|Time Complexity|Space Complexity|\n|-------|----------------|----------------|\n|MVGRL|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 d^\\dagger+{\\|\\mathcal{V}\\|d^\\dagger}^2)$|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 +\\|\\mathcal{V}\\|d^\\dagger)$|\n|BGRL|$\\mathcal{O}(\\|\\mathcal{E}\\| d^\\dagger+{\\|\\mathcal{V}\\|d^\\dagger}^2)$|$\\mathcal{O}(\\|\\mathcal{E}\\| +\\|\\mathcal{V}\\|d^\\dagger+{\\|\\mathcal{V}\\|d^\\dagger}^2)$|\n|HGRL|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 d^\\dagger+{d^\\dagger}^2)$|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 +\\|\\mathcal{V}\\|d^\\dagger)$|\n|GREET|$\\mathcal{O}(\\|\\mathcal{E}\\| d^\\dagger+\\|\\mathcal{V}\\|b \\kappa d^\\natural+\\|\\mathcal{V}\\|dd^\\dagger)$|$\\mathcal{O}(\\|\\mathcal{E}\\| +\\|\\mathcal{V}\\|d^\\natural)$|\n|HeteGCL|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 d^\\dagger+{d^\\dagger}^2)$|$\\mathcal{O}(\\|\\mathcal{V}\\|^2 +\\|\\mathcal{V}\\|d^\\dagger)$|\n|CoRep|$\\mathcal{O}(\\|\\mathcal{E}\\| d^\\dagger+\\|\\mathcal{V}\\|b \\kappa d^\\natural+\\|\\mathcal{V}\\|dd^\\dagger)$|$\\mathcal{O}(\\|\\mathcal{E}\\| +\\|\\mathcal{V}\\|d^\\natural)$|\n\nwhere $|\\mathcal{V}|$ and $|\\mathcal{E}|$ denote the number of nodes and edges in the graph. $d$, $d^\\dagger$, and $d^\\natural$ are the dimensionality of the original node features, final node representations, and projected node representations. $\\kappa$ represents the average number of positive samples. $b$ is the batch size of the contrastive loss. \n\nTable III. The average elapsed time per training epoch of the methods (in seconds). OOM indicates Out-Of-Memory. \n|Methods|CiteSeer|PubMed|CS|Physics|Cornell|Texas|\n|-------|--------|------|---|-------|-------|-----|\n|MVGRL|0.343|0.345|2.004|OOM|0.034|0.034|\n|BGRL|**0.033**|0.182|0.202|0.568|**0.022**|**0.022**|\n|HGRL|0.058|0.836|1.770|OOM|0.031|0.037|\n|GREET|0.202|OOM|OOM|21.891|0.025|0.025|\n|HeteGCL|0.154|0.851|1.627|OOM|0.061|0.061|\n|CoRep|0.047|**0.156**|**0.164**|**0.491**|**0.022**|0.023|\n\n>**The datasets selected for the ablation study (Table 3) are relatively small. Conducting ablation experiments on larger datasets would provide a more comprehensive evaluation of the contribution of each component.**\n\nThank you for the helpful suggestion. To further validate the effectiveness of each component, we conduct ablation studies on larger datasets. As shown in Table IV, each module positively impacts overall performance. Specifically, we observe that removing A1 leads to a performance drop across all three datasets. The results on the Chameleon and Photo datasets are particularly unstable, indicating A1’s importance in the model. Similarly, drops caused by removing A2 and A3 highlight the key roles of the edge evaluator and the Gumbel-Softmax trick. The performance degradation in A4, A5, and A6 highlights the critical role of the loss terms $\\mathcal{L}_d$, $\\mathcal{L}_r$, and $\\mathcal{L}_c$ in CoRep, as they are essential for maintaining intra-class compactness, edge discriminability, and global structural consistency, respectively. We also observe that the combination of losses yields better results compared to using each loss individually. The complete model (last row) achieves the best performance, demonstrating the complementary and synergistic effects of all components.\n\nTable IV. Ablation experiments on larger datasets.\n|Ablation|Chameleon|Photo|CS|\n|--------|---------|-----|---|\n|A1 w/o Col.Mat.|62.78±7.16|91.32±2.36|93.18±0.35|\n|A2 w/o Ed.Eva.|64.52±1.73|88.71±9.53|94.19±0.12|\n|A3 w/o Gum.Soft.|65.18±1.21|92.24±3.28|93.27±2.44|\n|A4 w/o $\\mathcal{L}_d$|65.37±1.70|93.74±1.83|94.21±0.28|\n|A5 w/o $\\mathcal{L}_r$|65.31±2.10|93.79±1.82|94.18±0.22|\n|A6 w/o $\\mathcal{L}_c$|51.64±7.14|89.62±3.50|89.84±4.25|\n|A4+A5|64.77±1.38|93.20±1.92|93.63±0.40|\n|A4+A6|51.36±8.32|88.92±3.19|88.56±3.91|\n|A5+A6|50.96±7.21|88.90±2.84|88.00±4.40|\n|CoRep|**65.64±1.39**|**93.84±1.89**|**94.39±0.31**|\n\n>**The authors should further elaborate on the detailed settings of the ablation experiments, as the current description is somewhat too brief. Please provide detailed configurations for each ablation study. Given the overall framework, the removal of certain key components may affect the subsequent structure, and any ambiguous settings need to be clarified. For example, in the A3 setting, after removing Gumbel-Softmax, how is positive sample selection conducted in Multi-hop Neighborhood Contrastive Learning?**\n\nWe thank the reviewer for this valuable observation.  We clarify the ablation settings as follows: \n(A1) Removing the edge-aware coloring matching module (w/o Col. Mat.). Instead, the hard assignment $argmax_{j\\in⟦\\chi_{\\mathcal{G}}⟧}\\pi_{i,j}$ of predicted coloring labels is directly used to guide the positive sample selection in multi-hop neighborhood contrastive learning. (A2) Removing the learnable edge evaluator (w/o Ed.Eva.). In this case, the coloring matching loss is computed directly based on the coloring labels, without relying on the edge evaluation. (A3) Removing the Gumbel-Softmax technique (w/o Gum.Soft.). We use the hard assignment of coloring labels, i.e., $argmax_{j\\in⟦\\chi_\\mathcal{G}⟧}\\pi_{i,j}$, to replace the node’s color $\\mathscr{C}_i^{col}$ in Equation (11) to identify positive sample set in the contrastive learning. This setting evaluates whether the Gumbel-Softmax technique is essential for selecting positive samples. (A4) Removing the coloring redundancy constraint (w/o $\\mathcal{L}_d$) by setting $\\alpha=0$. (A5) Removing the triplet relation ranking loss (w/o $\\mathcal{L}_r$) by setting $\\beta=0$.  (A6) Removing the multi-hop neighborhood contrastive loss (w/o $\\mathcal{L}_c$) by setting $\\gamma=0$, to examine the role of global semantic consistency. We will include these detailed settings in the revised version.\n\n>**The visualization results (Figure 5) are very informative. Considering that this work focuses on unsupervised learning on heterophilic graphs, why not also provide visualization results on a heterogeneous graph to intuitively demonstrate the effectiveness of CoRep for heterophilic graphs?**\n\nThank you for your helpful suggestion. We fully agree that visualizing results on a heterophilic graph could further demonstrate the effectiveness of CoRep for heterophily settings. Due to the figure limitations of this conference submission, we were unable to include additional visualizations. We will add such visualization results in the revised version. Thank you again."}, {"review_id": "Aljw6ZyylT", "reviewer": "Reviewer_aqBg", "summary": "In this paper, the authors propose a new method “CoRep” for heterophilic graph representation learning. CoRep seeks to capture local and global structures via coloring learning instead of graph contrastive learning. It generates coloring labels to encourage homophilic nodes to be closer and push heterophilic nodes farther apart. A learnable edge evaluator and a global positive sample set are used to capture graph structure more precisely. Extensive experiments on 14 benchmark datasets show the superiority of this method.", "questions": "1. The method proposed by the authors is designed for heterophilic graph structures. Could the authors clarify whether the proposed approach is specifically tailored to heterophilic graphs and whether its applicability to homophilic graphs is limited? A discussion on the generalizability of the method across different types of graph structures would strengthen the paper.\n2. The authors employ two Gumbel distributions in the proposed method. Could the authors elaborate on whether these two distributions serve distinct roles within the modeling process?\n3. The paper introduces redundancy constraints to reduce “redundant colors”, but does not explain what “redundant” means (e.g., in complex structures, assigning more colors may be semantically necessary rather than noise).", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. This paper proposes a novel coloring learning framework for heterophilic graph representation learning. This idea is interesting. It provides a different perspective from the mainstream data augmentation paradigm to solve the heterophilic graph problem, directly modeling the core feature of \"different neighbor node categories\" in heterophilic graphs.\n2. This paper is written clearly and well organized. The presentation of examples and illustrations is very clear and easy to understand.\n3. The proposed method is intuitive and easy to follow. \n4. Extensive experimental studies show the effectiveness of this method, providing support for their conclusions.\n\nWeaknesses:\n1. This paper lacks experiments on large-scale datasets to demonstrate the scalability of the proposed method.\n2. Some concepts are not clearly illustrated. See the questions below.", "was_revised": false, "final_justification": "", "rebuttal": "> **This paper lacks experiments on large-scale datasets to demonstrate the scalability of the proposed method.**\n\nThank you for your valuable suggestion. We have conducted experiments on two large-scale datasets: the homophilic dataset OGBN-Arxiv and the heterophilic dataset Arxiv-Year. Both datasets are large in scale, containing 169,343 nodes and 1,166,243 edges. The experimental results are presented in Table I. From Table I, we can see that our proposed method ranks second on the OGBN-Arxiv dataset, slightly behind BGRL, and achieves the best performance on the Arxiv-Year dataset. These results demonstrate that our method maintains strong performance and scalability on large-scale graphs with both homophilic and heterophilic structures. We will add these results in the revised version.\n\nTable I. Results on homophilic and heterophilic large-scale graphs. OOM indicates Out-Of-Memory.\n| Methods   | OGBN-Arxiv   | Arxiv-Year    |\n|-----------|--------------|---------------|\n| node2vec  | 70.07±0.13   | 39.69±0.09    |\n| DGI       | 70.19±0.73   | 40.60±0.21    |\n| MVGRL     | OOM          | OOM           |\n| BGRL      | **71.24±0.35**   | 41.43±0.04    |\n| HGRL      | OOM          | OOM           |\n| GREET     | OOM          | OOM           |\n| CoRep     | 70.59±0.07   | **42.59±0.42** |\n\n> **The method proposed by the authors is designed for heterophilic graph structures. Could the authors clarify whether the proposed approach is specifically tailored to heterophilic graphs and whether its applicability to homophilic graphs is limited? A discussion on the generalizability of the method across different types of graph structures would strengthen the paper.**\n\nWe appreciate the reviewer’s insightful comment. Our method is not only applicable to heterophilic graphs but also well-suited for homophilic graphs, demonstrating strong generality and adaptability. Specifically, our approach introduces a learnable edge evaluator that adaptively quantifies the relationships between node pairs. In heterophilic graphs, this component enables the model to effectively differentiate between various types of neighboring nodes by assigning distinct scores, thereby capturing diverse relational patterns. In contrast, in homophilic graphs, the evaluator tends to produce similar scores for neighbors sharing similar features or labels, which helps preserve label consistency and reflect underlying community structures. Moreover, the edge-aware coloring mechanism in our model further supports this adaptability by assigning similar/dissimilar colors to nodes of the same/different types. This flexible design allows our method to act as a general framework capable of handling varying levels of homophily without requiring architectural changes. \n\nTo demonstrate its generalizability, we have conducted extensive experiments on multiple homophilic graph datasets in the paper. As shown in Table 1 (Section 4.2), our method achieves superior performance compared to baselines, highlighting its effectiveness beyond heterophilic scenarios. \n\n> **The authors employ two Gumbel distributions in the proposed method. Could the authors elaborate on whether these two distributions serve distinct roles within the modeling process?**\n\nThank you for the valuable feedback. Although both techniques are based on Gumbel distributions, they are applied to different components of the model to address distinct challenges: Gumbel-Max is used for sampling discrete edge-level homophily indicators, while Gumbel-Softmax is employed for approximating node-level color assignments in a differentiable way. Specifically, the Gumbel-Max trick in Equation (6) is employed to sample the homophily score between node pairs in a differentiable manner. The ambiguity of estimated homophily probabilities makes them difficult to use directly for discrimination, while sampling discrete indicators from them is inherently non-differentiable. By leveraging the Gumbel-Max trick, we achieve approximate sampling of explicit homophily scores, which helps the edge evaluator effectively distinguish between homophilic and heterophilic node pairs. In contrast, the Gumbel-Softmax trick in Equation (8) is used to facilitate more effective color assignments. Due to the structural complexity of heterophilic graphs, the coloring classifier may generate noisy or redundant class assignments. The Gumbel-Softmax trick provides a differentiable approximation to discrete color sampling, encouraging confident and sparse color assignments. This mitigates redundancy and enhances intra-class compactness.\n\n> **The paper introduces redundancy constraints to reduce “redundant colors”, but does not explain what “redundant” means (e.g., in complex structures, assigning more colors may be semantically necessary rather than noise).**\n\nWe appreciate the reviewer’s insightful comment regarding the definition of “redundant colors.” In our paper, redundant colors refer to excessive or semantically uninformative color classes that emerge during model training as a result of overfitting to heterophilic structures. These assignments often do not contribute meaningfully to the classification objective and instead reduce intra-class compactness. To address this issue, our proposed redundancy constraint does not arbitrarily limit the number of color classes. Instead, it promotes sparse color distributions at the node level to encourage confident and semantically meaningful color assignments. This is achieved via a differentiable Gumbel-Softmax sampling mechanism, which maintains flexibility in exploring diverse coloring patterns, while the sparsity term guides the model away from diffuse and noisy assignments. We will add this discussion to the revised version."}, {"review_id": "4XGJYqLjw5", "reviewer": "Reviewer_1zrg", "summary": "The paper proposes a self-supervised heterophilic graph representation framework based on coloring learning.  Unlike augmentation-based GCL approaches that rely on complex augmentation strategies, this work introduces the coloring classifier and learnable edge evaluator to generate adaptive coloring labels to effectively capture both local and global heterophilic structures.  It achieves the state-of-the-art performance across multiple datasets.", "questions": "**Questions**\n\n1.In the parameter analysis experiment, the CiteSeer dataset demonstrates the best performance with one-hop neighbors. It would be valuable if the authors could provide further analysis or insights into why this is the case, particularly in terms of the dataset's characteristics or the model's behavior, which might explain the observed performance trend.\n\n2.The method introduced in this paper performs excellently on both homophilic and heterophilic graphs, demonstrating strong adaptability to various graph structures. However, could the authors discuss the scalability of their model on larger graphs, such as ogbn-arxiv?\n\n3.How does the runtime of your method compare to other baseline approaches? A comparison of computational efficiency across different methods would provide valuable insights into the practicality and feasibility of your method.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "**Strengths**\n\nS1. Novel Integration of coloring learning and heterophilic graph learning. The framework innovatively proposes coloring learning to generate different coloring labels for different node pairs to explore local and global heterophilic structures, offering a meaningful solution for unsupervised heterophilic graph learning.\n\nS2. The paper is well-written and easy to understand. The illustrations and problem descriptions in the paper are well-matched and clearly presented, effectively highlighting the problem the paper aims to address.\n\nS3. The proposed method demonstrates good adaptability, performing consistently across both homophilic and heterophilic graphs. This suggests its robustness to varying graph structures.\n\nS4. Comprehensive experimental validation. The effectiveness of the proposed method is well-supported through extensive comparisons with a wide range of baseline approaches across numerous datasets.\n\n**Weakness**\n\nW1. The explanation of the triplet relation ranking loss lacks clarity. It would be helpful to elaborate on what the partial order among the three elements represents, and how this ordering is reflected in the design of the ranking loss.\n\nW2. Lack of some setting details: Some hyperparameters, such as the temperature parameter $\\tau$ and the dimensionality of the position encoding, are not provided in experiments.", "was_revised": true, "final_justification": "I have read all the reviews and response. My concerns have been fully addressed. I think the authors present an interesting perspective on self-supervised graph representation learning, which offers valuable insights to the field. The experimental results are strong and convincing. Therefore, I am in favor of accepting this paper.", "rebuttal": "> **The explanation of the triplet relation ranking loss lacks clarity. It would be helpful to elaborate on what the partial order among the three elements represents, and how this ordering is reflected in the design of the ranking loss.**\n\nThank you for the suggestion. In the triplet constraint \n$\\forall\\left(v_i, v_j\\right)\\in\\mathscr{E}_{i, j}^{+}\\succcurlyeq\\left(v_p, v_q\\right)\\succcurlyeq\\forall\\left(v_i, v_j\\right)\\in\\mathscr{E} _{i, j}^{-}$, \n\nthe three elements represent node pairs sampled from the sets of homophilic edges, randomly selected edges, and heterophilic edges, respectively. The partial order among them is designed to establish a relative ranking, such that the semantic similarity of homophilic pairs is expected to be higher than that of randomly sampled pairs, which in turn should be higher than that of heterophilic pairs. This ordering is explicitly enforced through the design of the triplet relation ranking loss, which penalizes violations of the expected relative similarity among the three types of relations. Specifically, the loss function penalizes cases where the similarity of a randomly sampled node pair  $(v_p, v_q)$ exceeds that of a homophilic pair $(v_i, v_j)$ (where a high $\\widehat\n{\\omega}_ {i, j} $ indicates stronger homophily), as well as cases where the similarity of $(v_p, v_q)$ is lower than that of a heterophilic pair (where a low $\\widehat{\\omega}_{i, j}$ indicates stronger heterophily). In this way, the evaluator is encouraged to better distinguish homophilic and heterophilic relations. We will clarify this ordering relation and its implementation in the revised version.\n\n> **Lack of some setting details: Some hyperparameters, such as the temperature parameter $\\tau$ and the dimensionality of the position encoding, are not provided in experiments.**\n\nThank you for the valuable feedback.  In our experiments, we set the temperature parameters $\\tau_m$, $\\tau_o$, and $\\tau_c$ to 1.0, 1.0, and 0.2, respectively. The dimensionality of the position encoding $d^\\sharp$ is set to 16, and the hidden dimension of the edge evaluator $d^\\circ$ is set to 128. We will include these details in the revised version of the paper.\n\n> **In the parameter analysis experiment, the CiteSeer dataset demonstrates the best performance with one-hop neighbors. It would be valuable if the authors could provide further analysis or insights into why this is the case, particularly in terms of the dataset's characteristics or the model's behavior, which might explain the observed performance trend.**\n\nThank you for your valuable suggestion. We analyze this phenomenon from two perspectives: dataset characteristics and model behavior. From the perspective of dataset characteristics, compared to more heterophilic graphs such as Texas and Cornell, the CiteSeer dataset has a relatively simple structure and exhibits strong homophily (with an edge homophily score of 0.736). This high level of homophily indicates that one-hop neighbors already provide sufficient class-consistent information, offering clear and effective semantic supervision for representation learning. From the model behavior perspective, contrastive learning relies on constructing semantically consistent positive pairs from a node's neighbors to enhance the discriminative power of node representations. While incorporating multi-hop neighbors can help capture global semantic relationships, in strongly homophilic graphs like CiteSeer, distant neighbors often span class boundaries and are less semantically relevant. Treating these multi-hop nodes as positive samples may introduce false positives, thereby weakening the effectiveness of the contrastive loss and even hindering the training process. As a result, restricting contrastive neighbors to the one-hop level proves more beneficial for learning high-quality representations on CiteSeer. \n\n> **The method introduced in this paper performs excellently on both homophilic and heterophilic graphs, demonstrating strong adaptability to various graph structures. However, could the authors discuss the scalability of their model on larger graphs, such as ogbn-arxiv?**\n\nWe conducted experiments on two large-scale datasets: OGBN-Arxiv (homophilic) and Arxiv-Year (heterophilic). Both datasets are large in scale, containing 169,343 nodes and 1,166,243 edges. Table I presents the node classification results on two large-scale datasets. As shown in Table I, our method achieves the best performance on Arxiv-Year and ranks second on OGBN-Arxiv, closely following BGRL. These results confirm the effectiveness and scalability of our approach on large-scale graphs.\n\nTable I. Results on homophilic and heterophilic large-scale graphs. OOM indicates Out-Of-Memory.\n| Methods   | OGBN-Arxiv   | Arxiv-Year    |\n|-----------|--------------|---------------|\n| node2vec  | 70.07±0.13   | 39.69±0.09    |\n| DGI       | 70.19±0.73   | 40.60±0.21    |\n| MVGRL     | OOM          | OOM           |\n| BGRL      | **71.24±0.35**   | 41.43±0.04    |\n| HGRL      | OOM          | OOM           |\n| GREET     | OOM          | OOM           |\n| CoRep     | 70.59±0.07   | **42.59±0.42** |\n\n> **How does the runtime of your method compare to other baseline approaches? A comparison of computational efficiency across different methods would provide valuable insights into the practicality and feasibility of your method.**\n\nWe appreciate the reviewer’s suggestion. The runtime of our method compared to baseline approaches has already been presented in Table II. Experimental results show that our method achieves comparable running speed to BGRL, one of the most efficient graph contrastive learning methods, and even outperforms it on larger datasets such as PubMed, CS, and Physics. This improvement is primarily attributed to our use of sparse computation and mini-batch processing. Furthermore, compared to other baseline methods, our approach demonstrates significant efficiency advantages. For example, on the Physics dataset, our method is approximately 45 times faster than GREET.  We will include these results in the revised version of the paper.\n\nTable II. The average elapsed time per training epoch of the methods (in seconds).\n| Methods   | CiteSeer | PubMed | CS     | Physics | Cornell | Texas  |\n|-----------|----------|--------|--------|---------|---------|--------|\n| MVGRL     | 0.343    | 0.345  | 2.004  | OOM     | 0.034   | 0.034  |\n| BGRL      | **0.033** | 0.182  | 0.202  | 0.568   | **0.022** | **0.022** |\n| HGRL      | 0.058    | 0.836  | 1.770  | OOM     | 0.031   | 0.037  |\n| GREET     | 0.202    | OOM    | OOM    | 21.891  | 0.025   | 0.025  |\n| HeteGCL   | 0.154    | 0.851  | 1.627  | OOM     | 0.061   | 0.061  |\n| CoRep     | 0.047    | **0.156** | **0.164** | **0.491** | **0.022**   | 0.023  |"}, {"review_id": "rx7UuqBEJS", "reviewer": "Reviewer_e6Mg", "summary": "This paper introduces CoRep, a self-supervised framework for heterophilic graph representation learning. Arguing that traditional augmentation-based GCL methods damage crucial heterophilic structures, CoRep proposes a novel pretext task inspired by graph coloring. Instead of altering the graph, the model learns to assign different latent \"colors\" to adjacent dissimilar nodes and similar colors to adjacent similar nodes. This is achieved through a framework that includes a learnable edge evaluator to guide the process, an edge-aware coloring matching loss to learn representations, and a multi-hop contrastive module to enforce global consistency between distant, same-colored nodes. Extensive experiments on 14 benchmark datasets demonstrate that CoRep achieves state-of-the-art performance.", "questions": "See Weaknesses.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n1. Redefining the classic Graph Coloring Problem (GCP) and applying it to self-supervised heterophilic graph learning is a novel idea. It elegantly circumvents the difficulties faced by traditional GCL methods in performing data augmentation on heterophilic graphs, providing a new perspective for addressing this issue.\n2. The design of the CoRep framework is comprehensive, integrating multiple modules that work collaboratively.\n3. The authors conduct extensive experiments on 14 datasets, and the results are convincing, supporting the effectiveness of their approach.\n4. The paper is clearly written and easy to understand.\n\nWeaknesses\n\n1. The edge evaluator relies solely on the original node features $ x $ and positional encodings $ p $ to predict edge homogeneity. This method appears to depend heavily on the quality of the input features. If the original features $ X $ are noisy or not sufficiently discriminative, how does the edge evaluator avoid failure? Could more direct structural information, such as the number of common neighbors or higher-order neighborhood structures, be incorporated to assist in the assessment?\n\n2. The core argument of the paper is its design for heterophilic graphs. Why does it also perform well on homogeneous graphs? Is it because the edge evaluator can accurately identify that all edges are homogeneous, causing the model to degenerate into a standard homogeneous graph learning method? If so, this framework is not just a \"heterophilic graph\" solution, but rather a more general one. This universality is worth deeper discussion in the paper to enhance the generality of the work.\n\n3. The authors could more clearly delineate the differences and connections between their notion of \"coloring\" and the classical GCP in the related work or methods section. Clarifying that it serves as a heuristic idea could help avoid theoretical controversies.\n\n4. The partial order definition after Equation (9) is somewhat obscure. It would be helpful to explain the underlying idea in more intuitive terms: namely, that the color similarity of matched edges should be higher than that of random edges, and the similarity of random edges should, in turn, be higher than that of mismatched edges.", "was_revised": true, "final_justification": "This paper draws inspiration from the graph coloring problem and introduces a self-supervised learning approach designed for heterophilic graphs. The idea is interesting and provides a fresh perspective by addressing some of the difficulties that traditional GCL methods encounter in data augmentation for heterophilic graphs. I think these contributions are meaningful and deserve acceptance.", "rebuttal": "> **The edge evaluator relies solely on the original node features $ x $ and positional encodings $ p $ to predict edge homogeneity. This method appears to depend heavily on the quality of the input features. If the original features $ X $ are noisy or not sufficiently discriminative, how does the edge evaluator avoid failure? Could more direct structural information, such as the number of common neighbors or higher-order neighborhood structures, be incorporated to assist in the assessment?**\n\nWe appreciate the reviewer’s insightful comment. We agree that the edge evaluator’s discriminative power may degrade when the input node features are noisy or insufficiently informative. However, our model does not rely solely on the raw node features. We also incorporate $d^\\sharp$-dimensional positional encodings, which capture structural information up to $d^\\sharp$-hop neighborhoods. This integration helps mitigate the weakness of noisy node attributes by introducing richer topological information into the edge evaluation process. In addition, we propose a triplet relation ranking loss that explicitly measures and penalizes the discrepancy between the predicted edge homophily score and node coloring labels. This auxiliary supervision further regularizes the learning of the edge evaluator and enhances its robustness. \n\nTo better understand the impact of noisy input, we conduct a robustness analysis by adding Gaussian noise to the inputs of the edge evaluator during training at each epoch. As shown in Table I, although the model performance degrades when 20% or 50% noise is added, the overall drop is relatively small, indicating that the edge evaluator maintains strong robustness under noisy conditions. \n\nWe also acknowledge the reviewer’s suggestion to incorporate more explicit structural cues, such as the number of common neighbors or higher-order neighborhood patterns. This is a promising direction, and we plan to explore it in future work to further enhance edge assessment reliability.\n\nTable I. Model performance under Gaussian noise in edge evaluator inputs.\n|Noise Ratio|Cornell|Texas|Chameleon|Photo|CS|\n|-----------|-------|-----|---------|-----|---|\n|20%|82.16±2.16|85.41±4.71|65.57±1.50|93.79±1.83|94.37±0.34|\n|50%|80.54±5.51|84.86±4.39|65.44±1.26|93.77±1.78|94.33±0.33|\n|CoRep|**82.70±4.55**|**88.65±3.97**|**65.64±1.39**|**93.84±1.89**|**94.39±0.31**|\n\n> **The core argument of the paper is its design for heterophilic graphs. Why does it also perform well on homogeneous graphs? Is it because the edge evaluator can accurately identify that all edges are homogeneous, causing the model to degenerate into a standard homogeneous graph learning method? If so, this framework is not just a \"heterophilic graph\" solution, but rather a more general one. This universality is worth deeper discussion in the paper to enhance the generality of the work.**\n\nWe are truly grateful for the reviewers’ insightful understanding of our method and their valuable recognition. While our primary motivation is to address the challenges posed by heterophily, our design is inherently general. Specifically, our approach leverages a learnable edge evaluator that dynamically assesses the relationships between node pairs. In heterophilic graphs, this enables the model to distinguish between different types of neighboring nodes and assign them different scores. In homophilic graphs, the edge evaluator tends to assign similar scores to neighboring nodes with similar labels or features, effectively capturing community structures and preserving label consistency. Moreover, the edge-aware coloring mechanism in our model further supports this adaptability by assigning similar/dissimilar colors to nodes of the same/different types. This flexible design allows our method to act as a general framework capable of handling varying levels of homophily without requiring architectural changes. \n\nTo validate this generality, we have conducted thorough experiments on several benchmark homophilic datasets in the paper. As shown in Table 1 (Section 4.2), our method generally performs better than strong baselines. These results confirm that our framework is not limited to heterophilic scenarios but is broadly effective across different graph types.  We will include this discussion in the revisions of the paper.\n\n> **The authors could more clearly delineate the differences and connections between their notion of \"coloring\" and the classical GCP in the related work or methods section. Clarifying that it serves as a heuristic idea could help avoid theoretical controversies.**\n\nWe appreciate the reviewer’s insightful comment. We fully agree that the classical Graph Coloring Problem (GCP) serves as a heuristic inspiration for our work, rather than being directly solved in our method. Specifically, the classical GCP seeks to assign different colors to adjacent nodes while minimizing the total number of colors, which is a well-known NP-hard combinatorial optimization problem and often impractical to solve exactly for large graphs. In contrast, our method extends the concept of coloring to heterophilic graph learning. We do not directly solve the classical GCP; instead, we leverage the coloring idea along with a learnable edge evaluator to assign the same or different colors to node pairs based on their homophilic or heterophilic relations, which achieves representation learning for heterophilic graphs.  This allows the model to effectively capture both affinity and disparity between nodes, that is, the underlying homophilic and heterophilic dependencies and semantics. We will include this discussion in the revisions to better distinguish our approach from the classical GCP.\n\n> **The partial order definition after Equation (9) is somewhat obscure. It would be helpful to explain the underlying idea in more intuitive terms: namely, that the color similarity of matched edges should be higher than that of random edges, and the similarity of random edges should, in turn, be higher than that of mismatched edges.**\n\nThank you for the insightful comment. We will incorporate this clarification in the revised version of the paper. Specifically, we will explain that the partial order is meant to reflect a similarity ranking: homophilic edges should have higher similarity than random edges, which in turn should be more similar than heterophilic ones. This encourages the model to better distinguish different types of node relations. Thanks again."}]

Author rebuttal:

Meta-review: The paper introduces a new approach to self-supervised graph learning tailored to heterophilic graphs. The proposed framework follows a novel formulation based on graph coloring, introducing a classifier that assigns similar coloring labels to homophilic nodes. Beyond the originality of this formulation, the methodology is supported by a thorough experimental evaluation on both homophilic and heterophilic benchmark graphs. Overall, the paper makes a solid and well-executed contribution to the field. I encourage the authors to carefully consider the comments of the reviewers to enhance the proposed methodology and its presentation.
Decision: Accept (poster)