Simple and Asymmetric Graph Contrastive Learning without Augmentations
Authors: Teng Xiao
Huaisheng Zhu
Zhengyu Chen
Suhang Wang
Venue: NeurIPS 2023 poster (2023)
Keywords: Contrastive Learning
Graph Representation Learning

Abstract: Graph Contrastive Learning (GCL) has shown superior performance in representation learning in graph-structured data. Despite their success, most existing GCL methods rely on prefabricated graph augmentation and homophily assumptions. Thus, they fail to generalize well to heterophilic graphs where connected nodes may have different class labels and dissimilar features. In this paper, we study the problem of conducting contrastive learning on homophilic and heterophilic graphs. We find that we can achieve promising performance simply by considering an asymmetric view of the neighboring nodes. The resulting simple algorithm, Asymmetric Contrastive Learning for Graphs (GraphACL), is easy to implement and does not rely on graph augmentations and homophily assumptions. We provide theoretical and empirical evidence that GraphACL can capture one-hop local neighborhood information and two-hop monophily similarity, which are both important for modeling heterophilic graphs. Experimental results show that the simple GraphACL significantly outperforms state-of-the-art graph contrastive learning and self-supervised learning methods on  homophilic and heterophilic graphs. The code of GraphACL is available at https://github.com/tengxiao1/GraphACL.

Simple and Asymmetric Graph Contrastive Learning without Augmentations
Teng Xiao Huaisheng Zhu'r, Zhengyu Chen', Suhang Wang
'The Pennsylvania State University, "Zhejiang University, s2w494) @psu.
s2243,, s2s edu, chenzhengyu@zju. edu, cn
Abstract
Graph Contrastive Learning (GCL) has shown superior performance in representa- tion learning in graph-structured data. Despite their success, most existing GCL methods rely on prefabricated graph augmentation and homophily assumptions. Thus, they fail to generalize well to heterophilic graphs where connected nodes may have different class labels and dissimilar features. In this paper, we study the problem of conducting contrastive learning on homophilic and heterophilic graphs. We find that we can achieve promising performance simply by considering an asymmetric view of the neighboring nodes. The resulting simple algorithm, Asymmetric Contrastive Learning for Graphs (GraphACL.), is easy to implement and does not rely on graph augmentations and homophily assumptions. We pro- vide theoretical and empirical evidence that GraphACI, can capture one-hop local neighborhood information and two-hop monophily similarity, which both im- portant for modeling heterophilic graphs. Experimental results show that the simple GraphACL significantly outperforms cate-of-the-an art graph contrastive learning and self-supervised learning methods on homophilic and heterophilic graphs. The code of GraphACL is available at httph::////// thub. com tengxi aoggxiall///o GraphACL
Introduction
Contrastive lcarning has emerged as a promising regime for unsupervised vision representation learning without using annotated labeled data [1]. Recently, graph contrastive learning (GCL. has also been introduced to graph-structured data due to the lack of task-specific node labels (2 5 6 7
GCL has achieved competitive (or even better) performance many downstream tasks graphs compared to its counterparts trained with annotated ground-truth labels [7] g]
Generally, existing GCL methods can be categorized into two categories. The first contrastive reconstructs the local network structure (i.e., observed edges) to align with traditional network sewber--embdddingg objectives 13 14] Specifically, this scheme treats one-hop
scheme [ TO
IT 12
random- walk local neighboring nodes of the target node as positive examples and noi-neigbboring nodes as negative samples. It then employs contrastive loss functions to minimize the representation distance of positive pairs and maximize the distance of negative pairs 100 The key motivation behind this scheme is the explicis homophily assumption that semantically similar nodes more likely to be linked than dissimilar ones. Thus, connected nodes should have similar representations in the latent space. However, in heterophilic graphs, connected nodes
necessarily from the same semantic class [15 [6], and should not be simply pulled together in the latent space. This scheme empirically faces issues with performance in graphs exhibiting heterophily 117 [8]
The second graph contrastive scheme involves graph augmentations 3
5 77. Specifically,
it constructs two views through stochastic graph augmentation and then learn representations by contrasting these views based on the information maximization principle 19] positive node
Equal contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

pair consists of two views resulting from stochastic data augmentation of the same node, while a negative pair might consist of two views of different nodes [8]. This scheme built based on the idea that augmentations can preserve the semantic nature of samples, i.e. augmented nodes have consistent semantic labels with the same original nodes. However, recent work has shown that graph augmentation methods struggle to achieve good performance on heterophilic graphs [T8] as they still implicitly rely on homophily [20]. Studies have shown that stochastic augmentation primarily captures the common low-frequency information between two views, while neglecting the high-frequency one (20) (also see Appendix (.44. The latter is known to be more crucial for
heterophilic graphs 121 [2 Given that heterophilic graphs are prevalent across various real- woold
domains [16 231. a fundamental and open question naturally arises: What kind of contrastive learning
objectives can learn robust node representations both homophilic and heterophilic graphs?
This work is the first to address the aforemen- tioned question without relying on augmenta- tions and homophily assumptions. Instead, we take into account two more generalized insights, as depicted in Figure D (i) Even in heterophilic graphs, two nodes of the same semantic class often share a similar one-hop neighborhood con- text [24] 18]. Thus, capturing this heterophilic one-hop neighborhood context can lead to more discriminative node representations. (īi) While homophily might be minimal or non-existent in heterophilic graphs, another frequently observed phenomenon in real-world graphs is monophily graphs where the attributes of a node's friends are likely be similar the attributes of that node's other friends (25). Put another way, "monophily" essentially induces similarities between two-hop neighbors. As noted by 225 26). the two-hop similarities brought about by monophily can persist even in the total absence of any one-hop similarities that might be suggested by homophily.
(a) Homophily
(b) Heterophily
The graphs of pure homophily and pure het- erophily, where color denotes the semantic class. For both graphs, nodes with a similar one-hoy hop neighborhood context have similar semantic classes and two-ho hop simi- larities still exist even without the one-hop homophily. [25]. Monophily describes situations in real-world
Figure 1:
To support our motivations, provide statistics of homophily, two-hop monophily ratios, and neighborhood similarities of various graphs in the real-world in Appendix [ As shown in these statistics, homophilic and heterophilic graphs in the real-world exhibit relatively strong neighborhood similarity calculated based on one-hop neighborhoods compared to homophily. In cases where homophily is weak or non-existent, monophily has been shown to still hold in real-world graphs.
In this work, we focus on exploiting the above insights to design new objectives for better node repre- sentations on both homophilic and heterophilic graphs. We propose simple yet effective framework termed as graph asymmetric contrastive learning (GraphACL) for better node representation learning. Essentially, we faced with the challenge of simultancously capturing the one-hop neighborhood context and monophily in the contrastive objective. To solve this challenge, we consider each node to play two roles: the node itself (identity representation) and specific "neighbors" of other nodes (context representation), and thus should be treated differently. GraphACI trains the node identity representation by predicting the context representation of one-hop neighbors through an asymmetric predictor. Intuitively, by enforcing identity representations of two-hop neighbors to reconstruct the same context representation of the same central nodes, GraphACL implicitly makes representations of two-hop neighbors similar and captures the one-hop neighborhood context (Figure 2
Our primary technical contributions are: (1) We propose a simple, effective, and intuitive graph contrastive learning approach which captures one-hop neighborhood context and two-hop monophily similarities in a simple asymmetric learning framework. (2) We theoretically analyze the learning behavior and prove that GraphACL is guaranteed to yield good node representations for both homophilic and heterophilic graphs. (3) Empirically, we corroborate the effectiveness of GraphACL on 15 graph benchmarks. The results demonstrate that GraphACL can significantly outperform previous GCL methods. The surprising effectiveness of GraphACL shows that in the context of GCL, simpler methods have been underexplored in favor of more elaborate algorithmic contributions.
2 Related Work
Graph Contrastive Learning. Contrastive methods are central to traditional network-embedddng methods [27 13 [4) but have recently been applied in graph self-supervised learning [9 28, [0].

---

predict
prediot
similar
similla
stmtlar
predtom
predict
similas
(a) Graph
(b) Homophily
(c) Context
(d) Monophily
Figure 2: An illustration of various design motivations. (a) The heterophilic graph where the color
denotes node's semantic class. (b) Contrastive objectives with the homophily assumption encourage one-hop neighbors to have similar representations. GraphACL simply encourages the node predict its neighbors, which can implicitly capture neighborhood context (c) and two-hop monophily (d).
The key motivation behind them is the explicit homophily assumption that connected nodes belong to the same class and, thus, should be treated positive pairs in contrastive learning. However, real-world graphs do not always obey the homophily assumption [6]. limiting their applicability to heterophilic graphs [8). Recently, many GCL algorithms with augmentations (2
6 29] have
been proposed. However, (20] recently proved that GCL with augmentations attempts to manipulate the encoder to capture low-frequency information instead of the sighfrreuencc part and suffers performance degradation in heterophilic graphs [18]. In contrast, we propose a simple asymmetric contrastive learning framework for graphs without augmentations and homophily assumption.
Heterophilic Graphs. There are many heterophilic graphs in the real world that exhibit nonho- mophilic properties, such transaction [30
31], ecological food [32 and molecular networks (15), where the linked nodes have different characteristics and different class labels. Various graph neural 23
36 37 have been proposed to achieve higher performance in low homophily settings. They focus on designing advanced GNN architectures and consider the semi-supervised setting with labels. In contrast, we focus designing the contrastive learning algorithm without labels, not on specific GNN architectures. Recently, DSSL [88] and HGRL [29] have been proposed to conduct self self-supervised learning nonhomophilous graphs by capturing global and high-order information. Specifically, HGRL is based on graph augmentation, and DSSL works by assuming graph generation process, which may always hold true for real-world graphs. In contrast, our work provides a novel perspective on graph contrastive learning, which does not make any assumptions about the generation process or rely on any augmentations.
networks (GNNs) [33 15 21
[4 35
Preliminaries
Notations and Problem. Let (V, be input graph, where V (U1, (U1,...,,u) )dll is the of [ nodes and & is the set of edges. Let X [x1, X2, ... [lag E IR D= be node attribute matrix, where is the D2 D.-dimeesional feature vector of u; Each edge eij E & denotes link between node U and ug. The graph structure can be denoted by adjacency matrix A [o, 1] |||||| with A., eiy E E, otherwise A,, = 0. We denote the normalized adjacency matrix À 1/2 AD 1/2 where D is the diagonal degree matrix. Let L = I- be the symmetric normalized graph Laplacian matrix. We also define the unweighted two-hop graph G2, whose adjacency matrix is Ag. (A2):s = there exists j such that Gig E E and 6zk E E. The input graph g can be denoted as a tuple of matrices G (X, A). Our goal is to learn GNN encoder fe parameterized by 6, such that the representation of node v: v= fo (G) R, can perform well for downstream tasks.
Homophily Ratio. Typically, the graph homophily ratio 33 15 is defined the fraction of edges connecting nodes with the same labels, i.e., H(g) = (u, w) : (u, v) E & A yv = yo l/(E). Homophily Graphs have high edge homophily ratio H(G) + while heterophilic graphs (i.e..
low/weak homophily) correspond to small edge homophily ratio H(g) - O [15] 16].
ensures that local neighboring nodes have similar representations and has also been shown to be equivalent to factorizing graph proximity (38). Despite minor differences, the objective for this paradigm can be expressed as:
GCL with Representation Smoothing. This paradigm [3]
28 12
4
1 Σ EVV Wwo) V
Σ Emerrio)
log exp (v u/r) + E. ev exp v-T)
exp(v u/r)
(I)
Here v. u and v_ are the projected node representations by fo of nodes v, u and v_, respectively. is the temperature hyper-parameter. Typically, (vv)) is the positive sample set containing one-hop
3

---

Reprissntation
Reprepentaton
Resccseniation
V
2
1
Ropresentation
Representatoon
Begcesrctation
(b) GCL with Augmented Views (c) Graph Asymmetric Contreative Learning Figure 3: Illustration of existing contrastive schemes and GraphACL. (a) forces neighboring nodes to have similar representations based on the homophily assumption. (b) augments the graph and learns the augment- invariant representations of the same node. Our GraphACL (c) simply reconstructs the neighborhood signal of each node based on an asymmetric predictor without relying on the homophily assumption and augmentation.
(a) GCL with Representation Smoothing
local neighborhoods of node v, and V- is the negative sample set that can be randomly sampled from the node space V/ or sampled proportionally to the power 3/4 of the degree of the node [14]. Figure (a) illustrates this contrastive learning scheme with this explicit homophily assumption.
GCL with Augmented Views. This paradigm 44 20 39 3 learns representations by contrasting views based on stochastic augmentations. Specifically, Il, for node v, its representation in one augmented view is learned to be close to the representation of the same node from the other augmented view and far away from the representations of negative samples from other nodes. Given two augmentations Gi and G2 extracted from original graph G in predefined way, the contrastive objective is follows:
1 Lv = 1 1V| E vEN
exp(v v? /T)
log exp (vl v2/r) + E. ev exp vv'-T/T))
(2)
Here v² [o(G))(v] and v² = [o( are projected representations of node e from two augmented views. V- is the set of negative samples of u from the inter- intra-view [39]. Inspired by BYOL [40]. non-contrastive BGRL [5] 41) predicts the target augmented view of the nodes:
Lv = 1 z' vv2 //|lz/[|[vv|,, where z' (vv))) is the prediction of the representation from the target augmented view. An illustration for this scheme is presented in Figure (b).
4 Simple Asymmetric Contrastive Learning of Graphs
In this section, we elaborate on GraphACL. The key idea behind GraphACL is encouraging the encoder to learn representations by simultaneously capturing one-hop neighborhood context and two-hop monophily, which generalizes the homophily assumption for modeling both homophilic and heterophilic graphs. Specifically, GraphACL introduces an additional predictor Is which maps the graph G to node representations that can predict the one-hop neighborhood context from the representation of the central node as shown in Figure (c). Importantly, unlike previous contrastive schemes, which force neighboring nodes to have similar representations, GraphACL directly predicts the original neighborhood signal of each node through an asymmetric design induced by predictor. This simple asymmetric design allows neighboring nodes to have different representations but still can capture the one-hop neighborhood context and two-hop monophily as illustrated in Figure 2
4.1 Graph Asymmetric Contrastive Learning
Based on the above motivation, for each node v, we first propose to learn its representation by capturing its one-hop neighborhood signal. A natural idea of capturing the neighborhood signal is learning the representations of v that can well predict the original features of v's neighbors, i.c., X.. of neighbor u. However, the original features are typically noisy and high-dimensional [42]. To solve this issue, we cast the prediction problem in the representation space, i.e., the representation of the central node should be predictive of representations of its neighbors. Specifically, we adopt the following simple prediction loss induced by an asymmetric predictor on neighbors:
LyRE
M Σ VEV [(v)
Σ 2 (1 ul/2.
(3)
where v = [v] and u = [o) are representations, and g-(-) is a introduced predictor which maps the latent representation v to reconstruct the neighbor's representation u. Intuitively, this case, each node is treated as a specific neighbor "context", and nodes with similar distributions over the neighbor "context" are assumed to be similar. Here, we utilize only one single simple gø to predict representations of all v's neighbors and empirically find that it works very well.

---

This simple prediction objective in Equation can preserve local neighborhood distribution in representations without homophily assumption since we do not directly enforce v and to be similar to each other. 'o prevent Je from degenerating to the identity function, we consider the representations of central node and the one-hop neighbor u come from two decoupled encoders: [o( and u fe [u), where fa is the online identity encoder and f& is the preference target encoder. Importantly, the gradient of the loss in Equation (5) is only used to update the online encoder fe. while being blocked in the target encoder fe shown in Figure (c). The weights of the target network E are updated using the exponential moving average of online network weights Ç < + (1 X) where À [0. 1] is the target decay rate. An intuitive illustration for using two encoders is that each node typically plays two roles: the node itself and a specific context of other nodes, corresponding to separated notions of node identity and node preference in callwwrld graphs. The key principle of decoupled encoders is to allow the identity representation of a node to be more possibly different from the identity representation with which the node prefers to link.
The simple objective in Equation (3) can capture the one-hop neighhorhood context without relying on the homophily assumption or requiring graph augmentation as shown in Figure (c)). This matches our first motivation in the introduction part. Another remaining problem is why optimizing this simple objective helps capturing 2-hop node similarity, i.e., monophily. Consider pair of 2-hop neighbors and U2 which both neighbor on the same node u. Intuitively, by enforcing v and uy to reconstruct the same context representation of neighborhood u, we implicitly make their representations similar. Thus, the 2-hop neighbors serve as positive pairs that will be implicitly aligned as shown in Figure 2 (d). We formally prove this intuition in Theorem in our following theoretical analysis.
We note that some contrastive objectives based on augmentations such as BGRL. (5) and BYOL also utilize predictor as shown in Figure 2 (b). However, the idea behind our loss in Equation 3 differs significantly from them. Specifically, they rely on data augmentations, and are built based on the idea that the augmentation can preserve the semantic nature of samples, i.e., the augmented samples have consistent semantic labels with the original ones. Nevertheless, unlike images, is theoretically difficult to design graph augmentations without changing the semantic nature of nodes 7 and augmentations tend to capture homophily [20] [8]. In contrast, the simple loss in 3 does not rely augmentations but directly considers modeling one-hop neighborhood distribution. We thcoretically prove that our GraphACL maximizes the mutual information between representations and one-hop neighhorhood context, and captures two-hop monophily in $
Equation
Although this simple neighborhood prediction objective can capture both one-hop neighborhood pat- tern and two-hop monophily, it may result in collapsed and trivial encoder: all node representations degenerate to a the same single vector on the hypersphere. The main reason is that the prediction loss operates in fully flexible latent space, and it can be minimized when the encoder produces a constant representation for nodes. To address this issue, we introduce an explicit uniformity regularization to further enhance the representation diversity. Specifically, we add the following explicit regularization on representation uniformity into Equation (3):
LUNI 1 1 E LEV E.eev v-
(4)
M
where v = [u] and v_ = [u-]. Here, we consider the representations of negative samples v_ coming from the same online encoder as central sample. This uniformity loss is typically approximated by randomly sampling K negative samples v.. Intuitively, minimizing this term will push all node representations away from each other and alleviate the representation collapse issue.
Graph Asymmetric Contrastive Loss. Directly combining Equations 3 and 4 arrives at a loss function: LCOm LerE + LUNI- However, minimizing this combination loss is ill-posed problem, it approaches - oo as we can simply scale the norm of representations to reduce the loss. Even the representations are normalized, minimizing Luni still leads to relatively poor performance as shown in our experiments. To address this issue, we instead minimize an upper bound of LCOm. which results in the following simple objective of GraphACL (see Appendix A. for details):
LA= =
1 Σ ev [V(()) M
Σ EvENTO) log exp (p u//) + E. ev exp (vTv-/T)
exp(p u/r)
(5)
Here prediction p- (v) with v [o) representations u [e( and v_ so [G) LA is a simple generalization of the graph contrastive loss with representation smoothing in Equa- tion II) from symmetric view to an asymmetric view. Note that when the predictor 9o becomes the
5

---

identity function, L. degenerates to the GCL loss Ls. We demonstrate in extensive experiments that such asymmetric framework via a simple predictor helps achieve better downstream performance on both homophilic and heterophilic graphs than many GCL methods with prefabricated augmentations.
5 Theoretical Analysis
In this section, we provide theoretical understandings of GraphACI. We show that our simple GraphACI. can simultaneously capture one-hop neighborhood context and two-hop monophily, which are important for heterophilic graphs. We also establish theoretical guarantees for the downstream performance of the learned representations. All proofs can be found Appendix B
Notations. We denote the random variable node representations as V, and define the mean representations from the one-hop neighborhoods of node the representation z profiles the one-hop neighborhood pattern of node v. Since two nodes of the same semantic class tend to share similar neighborhood patterns in real-worlds, z can be viewed sampled from Z|Y Af (zy.1) I) where Y the latent semantic class indicating the one-hop pattern of v. Given the above, we first demonstrate the rationality of GraphACL. in capturing one-hop patterns: Theorem 1. Minimizing GraphACL's L's objective in Equation (5) with exponential moving average is equivalent to maximizing mutual information between representation V aand the one-hop pattern Y:
N(te) ΣueA(e) u. This means that
LA H(VYY) HVV) ((V;Y)
(6)
Theorem D indicates that minimizing GraphACL loss in Equation promotes maximizing the mutual information ((VYY) between representations and one-hop neighborhood context. Next, we theoretically verify that our GraphACL can capture intuition about the two-hop monophily similarity.
Theorem 2. Let (v) denote the set of two-hop neighbors of u. Minimizing the GraphACL objective in Equation 55 approximately minimizing the following alignment loss between two-hop neighbors:
Lowo-hop
1 M 2L DEE [N2(6]
E
EnpENatO 11v u2l12
(7)
where L is the L-bi-Lipschitz constant of 94- V(VI, -
(9.(vv)) ( (v2)
The above theorem shows that minimizing the GraphACL objective implies a small alignment loss of two-hop neighbors. Thus, GraphACL not only captures the one-hop neighborhood pattern, but also the two-hop monophily implicitly, i.e., encouraging a large similarity between two-hop neighbors.
Next, we theoretically show that the learned representations can achieve better downstream perfor- mance. We evaluate the representation by its performance on a multi-class classification task using the mean classifier [43 44, 45). Specifically, we consider the classifier pw (v) arg max Wv, where v = [e) and W E CRD is the weight of the linear classification head. The yth row of W is the mean M of representations of nodes with the label y: M, [vly For simplicity, we assume that the node classes are balanced but our results can be easily extended to unbalanced settings by considering label shift term as shown in the domain adaptation literature [46].
Theorem 3. Let fı2 H(G2) be the homophily ratio of the two-hop graph G2- Suppose that the downstream task is the M-categorical linear classification and the class is balanced. Then, Va E the hypothesis class with q = g f, the upper bound for the classification error on the optimal v" is
(y + pwwwv)) S (ALL(A)))))))) + (1 -h2)) + const.
(8)
This theorem says that the downstream error on representations bounded by GraphACI. loss and homophily ratio h2 of the two-hop graph G2, i.e, monophily. Specifically, larger monophily ratio fn would provably imply a smaller downstream classification error. Prior work (15] and the statisties of real-world graphs in Appendix Appendix[[sshow that although the one-hop graph may be heterophily-dominnt the two-hop graph will always be homophily-dominant (h2 is large). This theorem reveals why the simple GraphACL enjoys good performance on both homophilic and heterophilic graphs.
6 Experiments
6.1 Experimental Settings
Datasets and Splits. We conduct experiments on both homophilic and heterophilic graphs. For heterophilic graphs, we adopt Wisconsin, Cornell, Texas [33], Actor, Squirrel, Crocodile, and

---

Table 1: Node classification accuracy (%) on heterophilic and homophilic graphs. The best and
second best performance under each dataset are marked with boldface and underline, respectively.
Method
LINE
VGAE
DGI
GCA
CCA-SSG
BGRL
L-GCL
HGRL
DSSL
SP-GCL
GraphACL
Squirel
38,92.1.1
29.13
16
48.09
46.7610.
36,22.14:
52.94.0.5
48.31
40.51.0.8
52,10
54,05taas
Chameloon
48.59-1.11
42.65
60.27-a:1
63.66-0:3
62.41.am
64.86433
68.74.a.9
65,
65.82.
65-15
65.28+0.3
69.12.a24
Chocodile
42.21.1.11
45.72.1.77
51.25
60.73
56.77
53.87.0ss
60.18
61.87.045
62.98.a51
61.72kam
67.174
Actor
27.55.am:
26.99.1.56
30
28.77
27.82
28.80
32.55-1.1
27.95-a30
15-15-031
28.94
30.03+a33
Wisconsin
37.45.251
55.67.1.7
15.2
59.55
58.461096
51.233.17
65.28.e451
63.90ia5
62.25:a55
60.12:0.1
69.22.0.0
Comell
43.68-2.1
48.734415
11
52.31+169
50.33+229
3
51.78-108
53.15=1as
52.29
49.33-1445
Texas
48.69.1.19 50.27
58.534244
52.92
79,89
52.77
60.68...x
61.83amm
62.1
19.81
71.08.6.4
Roman
55.42-057
50.89.0.6
-3.7
79
67.35
69. 29.74
71.84-a.1
71.70.a54
70.88
14.9
Arxiv-year
33.21:0m1
39.26.0022
42.96
37.3840-11
43.022042
43.92ko.1
43.71
45.80.a57
44.1140.15
47.2148.9
Cora
68. 68.25a031
76.30s0.2
82. 62
82.93
84,00
82.
82.70g
84,00=a35
82.52ah31
83.51=042
83. 16
84,20sa31
Citeseer
43.92-031
66.80-e.3
72. 71.80-a7
39
73.10
71.10-oab
73.26-8.8
71.05-0.9
73.20-a11
71.964447
73.6348.21
Pubmed
66.29sa.00
75.80
66.80
80. 49.45
81 81.00
79.60za50
81.82+a.3
79.83a031
81.25
79. 16
82.02
Computer
86.50-a3:
85.80+0.1
83.95-047
88.7440m 87.85-031
89.694a.17
88.72.au
18.5340
89.24-033
89.684a.9
89..00
Photo
89. 30.82a0.0
91.50
91.61
70
93. 14
92.90
22.000
93.15+947
92. 85...8
93. 10..:0
92.49sa.3
93.31
Arxiv
65.22-030
66.40-0.00
70.32-a35
69.374039
71.2140:0
71.644823
71.33+030
68.5540.3
69.87-047 68.25
71.7248.6
Chamelcon 33 47 We also use two large heterophilic graphs proposed recently: Roman-empire
(Roman) 48 and arXiv-year [6] (~~ 170k) nodes. For homophilic graphs, we adopt three citation graphs: Cora, Citeseer and Pubmed 49 50], and two co-purchase graphs: Computer and Photo [T] We further include a large-scale homophilic graph Ogbn-Arxiv (Arxiv) 52 For all datasets, we use the public and standard splits used by cited papers. Detailed descriptions, splits, and one-hop homophily and two-hop monophily statistics of datasets are given in the Appendix C.1
Baselines. We compare GraphACI. with a traditional network embedding method: LINE [4] and the recent state-of-the-art self-supervised learning methods: VGAE (9], DGI (2), GCA 4.
Local (L)-GCL (12). HGRL [29]. BGRL (5), CCA-SSG [6]. SP-GCL [53), and DSSL [18]. The
descriptions and implementation details of baselines are given in Appendix C.2
Evaluation Protocol. We utilize node and graph classification and node clustering to evaluate the quality of the representation. For classification, we follow the standard linear evaluation protocol 22. We train a linear classifier on top of the frozen representation and report the test accuracy. For node clustering, we perform k-means clustering on the obtained representations and set the number of clusters to the number of ground truth classes and report the normalized mutual information [54].
Setup. For all methods, we use standard GCN model [49] as the encoder. We randomly initialize the model parameters and use the Adam optimizer to train the encoder. We run experiments with ten random seeds and report the average performance and standard deviation. For fair comparison, for all methods, we select the best configuration of hyperparameters only based on accuracy on the validation set. For baselines that did not report results in part of datasets or do not use standard public data splits [18 29], we reproduce the results using the official code of the authors. More details on the implementation and the hyperparameter search space can be found in Appendix C.3
6.2 Overall Performance Comparison
T the average node classification accuracy on both heterophilic and homophilic graphs. We provide the graph classification and node clustering results in Appenxi C.6 and C.5 respectively. showing that GraphACL can also effectively adapt to various downstream tasks. Surprisingly, among all methods, our simple GraphACL achieves the best performance in 14 of 15 data sets with various homophily ratios, as shown in Table [ Specifically, GraphACL achieves significant improvements on most of the heterophilic datasets and comparable performance on homophilic graphs compared with the second-bes method. Specifically, GraphACL achieves 4.3% (Roman). 11.6% (Cornell), 14.4% (Texas), 5. (Crocodile), and 3.1% (Arxiv-ycar) relative improvement over the second-best method. We can observe that contrastive strategies (CCA-SSG, GCA, and BGRL) with augmentations can not work well on heterophilic graphs compared to homophilic graphs. This verifies that they still implicitly leverage homophily. In contrast, GraphACL does not need augmentations, and we attribute our significant improvement to modeling the one-hop neighborhood context and two-hop monophily.
6.3 Ablation Study and Sensitivity Analysis
Ablation Study, We conduct an ablation study in Table validate our motivation and design, with the following three ablations: (i) directly minimize the combination loss LcOm. (ii) Removing the
7

---

100.0
90.0
0 65
76
26
0.0
7.0
two-hop
hop
Density
10
8
one-hop two hop rendom
Accuracy
80.0
random
4
70.0
43
0
60.0
0
20
Wassrar
20.0
512 1024 2048 4096
21 256
512 1024
2048 4096
1.
1.0
00.
-0.5
0.5
Dimension D
Dimension D
Similarity
Similarity
(8) Sensitivity of representation dimension
(b) Cora
(c) Squirrel
Figure 4: The effect of representation dimension, and the pair-wise similarities of randomly sampled node pairs, one-hop and two-hop neighbors. More results are provided in Appendix (..10
asymmetric encoder architecture, (iii) Removing the uniformity loss with negative samples. We also test the combination (ii) & (iii) by removing both asymmetric architecture and uniformity loss. First, minimizing the ill-posed combination loss is valid baseline, but can not achieve better performance and is unstable with large standard deviations. We also find that the model without uniformity loss (ablation (ii) does not achieve the best in homophily graphs, although it does still serve as a strong ablation. When each component is individually applied, the asymmetric architecture alone achieves the very best performance Cornell and arXiv-year. This confirms our motivation that the asymmetric architecture is of more importance for modeling neighbors in heterophilic graphs where connected nodes have different classes. The full model (last row) achieves the best performance, demonstrating that our designed components are complementary to each other.
Representation Dimension. In Fig- ure (a), we analyze the effect of the dimension of node representations. We can observe that having a large dimension can generally lead bet- ter performance for both homophilic and heterophilic graphs. Moreover, we find that the dimension effect is more obvious in heterophilic graphs compared to it in homophily graphs. This could be justified by our Theorems 3 which give the lower bound and upper bound of GraphACL loss in terms of the homophily ratio. Specifically, since the two-hop homophily ratio is still smaller in heterophilic graphs compared to homophilic graphs, and a small downstream error requires a small loss. Thus, a large dimension can effectively reduce the lower bound of the training loss and benefit the learning on heterophilic graphs. Training with extremely large dimensions for some graphs may lead to a slight drop of performance as GraphACL may suffer from the over-fitting issue, limiting its generalization performance.
Table 2: Ablation studies on the node classification task.
Baseline
Cora
Pubmed
Cornell
arXiv-year
(i minimize Looss
83.08e075
81.31
38.10
45. 45.79
asymmetric encoder
82.21 10.00
81.05
57.13:011
45.33
(iii) wo uniformity loss
81.39.o20
80,56
57.87
46.54
(ii) & (tif) w/o both
80.85.065
77.05
42.03
42.71mam
GraphACL
84.20=a.31
82.02aa.15
59.33s1.45 47.21an.0
Figure shows the performance with various decay rate A. We observe that (i) À plays an important role in GraphACL. Having a large À typically improves the model performance; (ii) Instantaneously updating the target network, i.e., when O, destabilizes training and leads to poor performance. Thus, there is a trade-off between updating the target too often and updating it too slowly. The temperature t and the number of negative samples K are not included here since they are not directly relevant to key motivation and have been employed and evaluated in the recent works [55] (6). Thus, we provide corresponding results in Appendices C.8 and
Other
6.4 Qualitative Analysis and Case Study
Similarity Visualization. Figures 4 (b) and (c) plot the distribution of pair-wise cosine similari- ties of randomly sampled nodes, one-hop neighbor, and two-hop neighbor pairs based on learned representations. We can observe that, for the homophilic graph, that is, Cora, nodes are forced to have representations similar to those of their neighbors. GraphACL enlarges the similarities between neighbor nodes compared to randomly sampled node pairs, demonstrating that GraphACL can well preserve one-hop neighborhood contexts. Compared to the homophilic graph Cora, GraphACL seeks to further pull the two-hop neighbor nodes together on the heterophilic graph, i.e., Squirrel. This observation matches our motivation and analysis that GraphACL can effectively discover the underlying two-hop monophily, which benefits the learning on heterophilic graphs. Figures (a) and (b) show the cosine similarity between the v and prediction go for each node. We find that the cosine similarities are typically smaller than 1, showing that the predictor do is not an identity matrix after convergence. Moreover, we can observe that, compared to the homophilic graph Cora, the
8

---

Cora
Pubmed
Squirrel
85.0
82.0
55.0
Accuracy (%)
80.0
54.0
78.0
53.0
81.0
52.00
A=0.00
76.0
A=0.00
A=0,00
79.0
1=0.80
Amb.90
51.0
Am0.90
2-0.97
74.0
A-0.97
50.0
A=0.97
77.0
1=0.99
72.0
A.0.99
49.0
A=0.99
75.0
70.0
48.0
30
60
120
150
50
100
125
60
90
120
150
Iterations
Iterations
Iterations
Figure The testing performance varying decay rate A. More results are given in Appendix
C.7
5.0
Density
4.0
3.0
3.0
2.0
1.0
1.0
.1.0
-0.5 0.0
10
0.0 0.5 1.0
Similarity (v, p)
Similarity (v, p)
Node ID 2329
Node ID 258 (c) Squirel
(a) Cora
(b) Squirrel
(c) Cora
Figure 6: (a) and (b) show the similarity between representation v and prediction p. (c) and (d) show case studies, where we randomly pick node with the drastic neighborhood variations and visualize its neighborhood. Node colors denote ground-truth labels. The size of the node is proportional to its representation similarity to the central node denoted as star. See Appendix C.II
C.II for more results.
similarities on the heterophilic graph Squirrel are smaller. This verifies that GraphACI. automatically differentiates node identity and context representations, which is important for heterophilic graphs.
Case Study. In Figures and (d), randomly sample the two-hop subgraph of a central node and calculate the cosine similarity based on learned representations between the central node and neighbor nodes. We can observe that GraphACL can successfully identify the node whose local neighborhood patterns are similar to the central node on both homophilic and heterophilic graphs. Additionally, our GraphACL can pull two-hop neighbor nodes, which share a similar semantic class to the central nodes, instead of favoring nearby one-hop neighbor nodes. These observations endorse our intuition that heterophilic graphs can not benefit much from one-hop neighbor nodes, and our GraphACI. can effectively capture the latent semantic information related to two-hop monophily.
7 Conclusions
We propose a simple contrastive learning framework named GraphACL for homophilic and het- erophilic graphs. The key idea of GraphACL is to capture both local neighborhood context of one hop and a monophily similarity of two hops in one single objective. Specifically, we present simple asymmetric contrastive objective for node representation learning. We provide theoretical under- standing of GraphACL, which shows that GraphACL can explicitly maximize mutual information between representations and one-hop neighborhood patterns. We show that GraphACL. also implicitly aligns the two-hop neighbors and enjoys good downstream performance. Extensive experiments on 15 graph benchmarks show that GraphACL significantly outperforms state-of-the-art methods. We hope that the straightforward nature of our approach serves as reminder to the community to reevaluate simpler alternatives that may have been overlooked, thus inspiring future research.
Acknowledgments
This work supported by, or part by, the National Science Foundation (NSF) under grant number 199-990,702, the Army Research Office (ARO) under grant number W91 INF21-1-0198 Department of Homeland Security (DNS) CINA under grant number F205949D, and Cisco Faculty Research Award. The findings in this paper do not necessarily reflect the view of the funding agencies.

---

References
[1] Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive 2018.
predictive coding. arXiv preprint arXiv:
[2] Petar Veličković, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2018.
[3] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. NeurIPS, pages 5812-5823, 2020.
[4] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In The Web Conference, pages 2069-2080 2021.
[5] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In ICLR, 2021.
[6] Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S Yu. From canonical correlation analysis to self-supervised graph neural networks. NeurIPS, 2021.
[7] Puja Trivedi, Ekdeep S Lubana. Mark Heimann, Danai Koutra, and Jayaraman Thiagarajam. Analyzing data-centric properties for graph contrastive learning. NewrlPS, 2022.
[8] Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. arXiv preprint arXiv:2109.01111 2021.
[9] Thomas Kipf and Max Welling. Variational graph auto-encoders. ArXiv, 2016.
[10] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint arXiv: 2017.
[11] Hao Zhu, Ke Sun, and Peter Koniusz. Contrastive laplacian eigenmaps. NeurIPS, 2021.
[12] Hengrui Zhang, Qitian Wu, Yu Wang, Shaofeng Zhang, Junchi Yan, and Philip S Yu. Localized contrastive learning on graphs. arXiv preprint vrXiv:2212.04604 2022.
[13] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In KDD, pages 855-864, 2016.
[14] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large- scale information network embedding. WWW, pages 1067-1077, 2015.
[15] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. NeurIPS, pages 7793-7804, 2020.
[16] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. NeurlPS, pages 20887-20902, 2021.
[17] Mingyue Tang, Pan Li, and Carl Yang. Graph auto-encoder via neighborhood wasserstein reconstruction. In ICLR, 2021.
[18] Teng Xiao, Zhengyu Chen, Zhimeng Guo, Zeyang Zhuang, and Suhang Wang. Decoupled self-supervised learning for non-homophilous graphs. arXiv preprinl arXiv:2206.03601 2022.
[19] Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning visual representations. In ICML, pages 1597-1607, 2020.
[20] Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. In NeurIPS. 2022.
[21] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In ICLR, 2020.
10

---

[22] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequeney information in graph convolutional networks. In AAAI, 2021.
[23] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.07082. 2022.
[24] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? In ICLR, 2021.
[25] Kristen M Altenburger and Johan Ugander. Monophily in social networks introduces similarity among friends-of-friends. Nature human behaviour, pages 284-290, 2018.
[26] Alex Chin, Yatong Chen, Kristen M. Altenburger, and Johan Ugander. Decoupled smoothing on graphs. In WWW, 2019.
[27] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD, pages 701-710, 2014.
[28] William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurlPS, 2017.
[29] Jingfan Chen, Guanghui Zhu, Yifan Qi, Chunfeng Yuan, and Yihua Huang. Towards self- supervised learning on graphs with heterophily. In CIKM, pages 201-211, 2022.
[30] Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. Netprobe: fast and scalable system for fraud detection in online auction networks. In WWW, 2007.
[31] Teng Xiao and Donglin Wang. A general offline reinforcement learning framework for interac- tive recommendation. In AAAI, 2021.
[32] Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns, In KDD, 2021.
[33] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2019.
[34] Teng Xiao, Zhengyu Chen, Donglin Wang, and Suhang Wang. Learning how to propagate messages in graph neural networks. In KDD, pages 1894-1903, 2021.
[35] Huaisheng Zhu, Guoji Fu, Zhimeng Guo, Zhiwei Zhang, Teng Xiao, and Suhang Wang. Fairness- aware message passing for graph neural networks. arXiv preprint 22x1::3306.1113..222
[36] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In NewrlPS, 2022.
[37] Zhimeng Guo, Teng Xiao, Charu Aggarwal, Hui Liu, and Suhang Wang. Counterfactual learning on graphs: A survey. arXiv preprint arXiv:2304. 01391, 2023.
[38] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM, 2018.
[39] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning, arXiv preprint arXiv:2006.04/11 2020.
[40] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach self-supervised learning. NeurlPS, 2020.
[41] William Shiao, Zhichun Guo, Tong Zhao, Evangelos E Papalexakis, Yozen Liu, and Neil Shah. Link prediction with non-contrastive learning. arXiv preprint 2tXiv:22/1.14399) 2022.
[42] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view on graph neural networks graph signal denoising. In CIKM, pages 1202-1211, 2021.

---

[43] Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A theoretical analysis of contrastive unsupervised representation learning. In ICML. pages 1994-99233 2019.
[44] Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is ladder: A new theoretical understanding of contrastive learning via augmentation overlap. Arxiv, 2022.
[45] Qi Zhang, Yifei Wang, and Yisen Wang. How mask matters: Towards theoretical understandings of masked autoencoders. NeurlPS, 35, 2022.
[46] Remi Tachet des Combes, Han Zhao, Yu-Xiang Wang, and Geoffrey J Gordon. Domain adaptation with conditional distribution matching and generalized label shift. In NewrIPS, 2020.
[47] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
[48] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In ICLR, 2023.
[49] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[50] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, pages 93, 2008.
[51] Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommendations on styles and substitutes. In SIGIR, pages 43-52, 2015.
[52] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs NeurlPS, pages 22 281112221111111 221333 2020.
[53] Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. Can single- contrastive learning work for both homophilic and heterophilic graph? arXiv preprint arXiv:2211.10800 2022.
[54] Nguyen Xuan Vinh, Julien Epps, and James Bailey. Information theoretic measures for cluster- ings comparison: is a correction for chance necessary? In ICML., 2009.
[55] Ting Chen, Simon Korblithh Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In ICML, pages 1597-1607, 2020.
[56] Jun Xia, Lirong Wu, Ge Wang, Jintao Chen, and Stan Z Li. Progel: Rethinking hard negative mining in graph contrastive learning. In ICML, pages 24332-24346, 2022.
[57] Malik Boudiaf, Jérôme Rony, Imtiaz Masud Ziko, Eric Granger, Marco Pedersoli, Pablo Piantanida, and Ismail Ben Ayed. A unifying mutual information view of metric learning: cross-entropy vs. pairwise losses. In ECCV, pages 548-564, 2020.
[58] Meihong Wang and Fei Sha. Information theoretical clustering via semidefinite programming. In AISTATS, pages 761-769, 2011.
[59] Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. In NeurIPS, 2022.
[60] Jeff 7. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. NeurlPS, 34:5000-5011 2021.
[61] Minjie Yu Wang. Deep graph library: Towards efficient and scalable deep learning on graphs. In ICLR workshop representation learning on graphs and manifolds, 2019.
[62] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1xXiv:141.66980. 2014.
[63] Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. CVPR, pages 15750-15758, 2021.
12

---

A The Omitted Details of GraphACL
A.1 The Loss of Graph Asymmetric Contrastive Learning
We provide details of the derivations of GraphACL in Equation ( and show that minimizing GraphACL is approximately minimize the combination of prediction and uniformity losses.
exp(p' u/T)
LA
M Σ WE [V(I)
E EmEN(N)
log
exp (p (D/UT) + Ex_Ev exp exp (viv-/T)
Σ DE ((vi)
ΣVEN(O) WEN(
p
log
exp P ('/UT) + Σ -.LLv exp vvv=/T))
M
T
p puu u log Σ
2
Σ NE [W(v)]
Σ uEN(v)
EEE exp v vvv-/T)
(9)
M
1 V DEV W(v)
Σ WEN(")
plu log Σ
EV exp (v v-T
exp (p v/T)
Σ DEV ((O))
E UEN(U))
p
log
|V|
M
T
BLEV
|
exp (v (vTv_/T)
M NE
1
Σ
(W(I)
WEN())
log | Σ
ELEV log
V
(10)
1
E WEN(N)
pJu
V E,
1
ev logexp (v v-////
V NE W(r)
Σ
Σ EVENTO)
-P u
uu+
M Σ
v._
M DE W(w)
M Σ DE W(v)
Σ WEN(M)
|pp ull2
En v v |
(11)
where the symbol & indicates equality to multiplicative and/or additive constant. Here, we utilize Jensen's inequality in Equation (TO). Equation (IT) holds because p and u are both lg- normalized. Given the above, we can conclude that minimizing GraphACL objective is approximately to minimizing the combination the prediction and uniformity losses.
B Proofs in Section
B.1 Proof of Theorem
Theorem I. Minimizing GruphACL's objective in Equation (5) with exponential moving average is equivalent to maximizing mutual information between representation V and the one-hop pattern Y:
La 2 H(VIV) - H(V) = YV.
(12)
Proof. According the derivations in Appendix A.I we have:
L >
E EvEViO)
-P
Tu+
V Eveey VTV_
V DEV
W(v)
Σ
llp
[W(w] Σ EMENTO
u112
Σ
DEV Σ
|V v-
(13)
M
DEV
[
M Σ
DEV |p- 21
1 1
Σ DEV -v-
(14)
M
where z Niw) EmeN(w) u is the mean representations from one-hop neighborhoods of node Equation (1) holds because that gradient of u being blocked in the target encoder with exponential moving average; thus it can be viewed as a constant that depends only on the target encoder but not the variable fo- Since two nodes of the same semantic class tend to share similar one-hop neighborhood patterns even in non non-homophilous graphs, thus we view the neighborhood representations is
13

---

sampled from the conditional distribution given the pseudo label Y which indicates the one-hop neighborhood pattern: Z|Y N (zy I). As demonstrated in [57]. we can interpret the first term as a conditional cross-entropy between V and another random variable Z whose conditional distribution given the pseudo-label Y indicates the one-hop neighborhood pattern: Z|Y ~ ~N (zy, T):
1 Σ DEV 1p- - 2 - HVV = H(VIV) + DKL(V 2 H(VY), (15) M
where H-) and DEL (-) denote the entropy and KI.-divergence, respectively. Minimizing the first term in Equation (14) is approximately minimizing H (V))). We then inspect the second term in Equation 14). As shown in [58] [7], the second term is close the differential entropy estimator:
DV IV Em - v x H(V).
(16)
As result, minimizing the loss of GraphACL can be seen proxy for maximizing the mutual information between the representations V and the pseudo-labels Y which indicates the neighborhood patterns of one hop nodes. Thus, the proof is completed.
B.2 Proof of Theorem
Theorem 2 N2(v) denote the set of two-hop neighbors of v. Minimizing the CraphACLeoheective in Equation (5) is approximately minimizing the following alignment loss between two-hop neighbors:
Easo-hop
1 [V] 2T
E.Ev [Na(vi]
Σ EmpeAsto) 1/v 1-21111 u2l12
(17)
where L is the L-bi-Lipschitz constant of gø: V(vi, v2), 1/4 llv1 - vel s (9o((v) - (v(2))
Proof. Given the derivations in Appendix A.l we have:
La _ 1
Σ
Σ uEN((
u log [exp (p (p/u/r) + exp (vTv-/t))
M DEv
W(m)
1
E.Ee DEY [(r)
golv) C Σ (EN(())
MV Σ GEV W(o) E EmEN(o) u u'golv), (18)
1
M
where the last line holds because E V: Ev_ev exp vvTv-/r) > exp(v v) =e> 1. To conduct the proof, we first formulate the degree-related predictions and representations two matrices: P and U. Here, U., 0 Vd is the u-th row of the matrix Ü NxD and P. ViT go(v) is the e-th row of the matrix P E NxD, Recall that the normalized adjacency matrix À D 1/2 10-1/AAD AD A where is the diagonal degree matrix. With the above and Equation (18), we have:
1/2
La 2
(v)
V VE [(w)]
Σ EmENion vdlvod Volgglv) Vd.u
M VEv [W(v)]
dm
E vdovda Volgolv) Vd.u
M NE W(v)
Emexio, nEN(W) vdvvd, Vdogolv) Vd..u 1
D ((PUT
(IAP1 1
| (13)
(19)
1V
2 in (P
1
Σ
d. ||
2
11 M In II(PPTAAA)) A
(20)
M
2
NEV
where dm the maximum degree of nodes and tr( denotes the matrix trace. In Equation 19). we
utilize the inequality: tr(PQ) (IIPI[ |Q for any two matrices P E R and Q E gnxt
Equation (20) holds as is normalized. Since the trace is the sum of elements on the main diagonal
14

---

of the matrix, the w-th diagonal value of (PPTA A A) is:
(PP A AT J,, = Σ (ATA) oo (PP Juzie
Σ
E
duzp. Puz
"gEV ((
EueNto) E (seA((u) du vdo duz
Volo v dugpu Puz
Pnz Pu2 - - Euentoo) E Emzex(w) [Vu)] [p. - P Euerro) E ZuzeNtw) W(x)) p.
-Euextos
E Eupestoos [Wu)] (l9o(v) - (o(())
$ - 1 1-1- EugeN(i))) E EueNio) [N(")] l|v uzllă. L
(21)
where Equation 21 holds is because the decoder is L-bi-Lipschite A (x1, x2), ||x x211
1 (x1) - Is (x2)
2 Combining Equations
(8)
20 and (2T). we have:
min La = min 0.0
Σ
Σ UEN(C)
u go(v)
DEW [V(
min 0.0
[V] 2
1
(PP A A)
min
0,0
2
11 Σ
EEV
(PP A A)e,
min 2L [V]
1
Σ DEV (EN(()
uzEN(u) 1/v ug
N(u)
min 0.0
1
Σ "EV E HEN()) M(u)]
dm
22EN(w) 11
2L
[V]
1 1 2L
EEV Σ EmDENS(O) 1|v--alle
min 0.0
I
min 0.0 2L
vev [Na(2)]
Σ ug)
||v
U2
(22)
where ming fi + ming f2 represents that minimizing function fi with respect to 0 is equivalent to maximizing function f2 with respect to 0. Thus, the proof is completed.
B.3 Proof of Theorem 3
Theorem 3 Let he H())) be the homophily ratio of the two-hop graph G2. Suppose that the downstream task is the M-categorical linear classification and the class is balanced. Then, Vi E the hypothesis class with q = g f, the upper bound for the classification error on the optimal v" is:
P P + pw())) S (A + +1 - -hz)) + const,
(23)
Proof. We define the adjacency matrix of the two-hop graph of as A i.e., (Ag)a = if there exists node j such that Eij E & and ejk- E E, otherwise (A2)a = 0. The normalized form of A where D2 is the diagonal degree matrix of the two-hop graph. (V) is the set of the neighbors of on the two-hop graph. We also define the label matrix of all nodes as V
is A₂
Y E x and the representation matrix V RMXD with the w-th node representation
Let c; be the number of nodes belonging to class For any class i, we have c; = c [V] since we assume the ideal balanced setting for simplicity. However, our theoretical results can be easily extended to unbalanced settings by explicitly considering the shift of label distributions 46). Given the above definitions, we have the following:
Bey.yy Wv
Σ
lly Wv
Y -
VW 12
M
EE
V
1
Y A,C + A,C - VW 1
M
S
1
2
- A2 + 2 A₂C VW VW 13)
(24)
M
where C c ' 1y.=i and 1 is the indicator function. ye is the label index of node and yo is
the one-hot vector of label ye. The last line holds because |P + Q < 2 PI
3 + 2 Q for any
15

---

two matrices P and Q of the same dimension. The (v, i)-th elements of matrices Y and A₂C are:
Y u, L and (,, = EmzeNa(o) Q 1u If yo = i, we have:
(Y - A2C,03 = yy==i= E -uveNaatt Gi Uuz == E
weseN(lo) 1 I
(25)
Similarly, for yo F i, we have:
(Y - A2 = =ly -E - - -
(26)
Given the above, we further have:
M
JJ -=0 = E, 11 - A.C),11= Σ. -( - -
Muz Imng=e x) + (1 - Im.= E EneeN( Im =1)²
No
UzeNa(v) G
M
Σ. (1 EuzeNa(e) 1
Muz Wun )2
1 Iln
I1)==1)² =1)
(ggNN((e)
(geNa(e) C
1m1
M
>.. (1- Σ o2EN2(0)
1 Mug= Wu )
Mosts Σ (gg
Buz =1
Σ. (1 Σ w2EN2(1) &i
1
vug==o) 2
Nott Ci mi)
N2(
Σ. 1+ MM
Mo 1l Vuz =))
MII
(1)
Σ. 1+
MM
Aong + |V] E EnEnesscon
MM
|IM
(2)NN(())
(27)
For the second term |AaC VW 1 in Equation
we have:
|A VW 1 = (A VV + VV Jc vw
(28)
= ||( [A VV V w 1
S (A VV WT)
S (A
w
>1
S (A) VV 3V
AA - VV )[ C
(29)
.MM
= 2 |V] [I VV )|{
(30)
where Equation 29 holds because the in row of W is the mean of representations of nodes with
label i: II(V C
W T) = 0. Combining Equations
27 and 30), we have:
Ey Iy
W S
M (2 - A2C 2 + A1 VW
1
DII I[(A VV 11 2(1 + MM
MM
M Σ, Σ (M) 1 1 Moy #vw)
$
$ 4 DII
MM
I[(A
VV
)12 + M Σ, [2(w))]
MM
VI Σ EmpENs(i)) Hurg
< M.
I[A,
11 TV (1 hrz) + 2,
VV
(31)
16

---

where h, 2( is the homophily ratio of the two-hop graph. Based on the derivations in Theorem and Equation 2 have:
Cx(a) 2 | 2L E vev [N((v)]
Σ
o22M2(0)) 1/v I - log E, Ev exp (v (vTv-/T))
1
Σ DEv Wa(v)
log exp(V T v2/T)
(32)
[ 2T.
UsEN2(e)
Ee_ey exp (vT v-/T)
2
1 MIDV 2T.
E .EV E (22
E log
exp(v v2/T)
|II 2T. LSimLLR (V).
(33)
Ev_
We can find the last line is exactly the SimCLR-style loss 55 over two-hop graphs. Recent work
59
proves that finding the global optimum of the un un-normalized SimCLR- style objective LSiCLLR V equivalent to solving the matrix factorization problem: and 33
miny | VV
Given Equations (11
further have:
P (y. # pw (v') - y. llv Wv 1
(34)
MM
I [VIDI] I(A2 - V-V 1112 4M h2) +
M
= DIINY CSIICIR + h2) +4+
3 LCA(") 1M2 122) +
2 (ALL())) + -1- h2)) -1- B.
(35)
Here, convert the mean-squared error bound to classification error bound in Equation (34) as shown by Claim B.9 in (60). The a the constant indicating the gap between the optimal loss value of SiyCLR-style and matrix factorization losses 559 and /
C Experimental Details
C.1 Datasets Details and Statisties
Table 3: Statistics of used homophilic and heterophilic graph datasets in this paper.
Dataset
#Nodes
# Edges
#Classes
#Features
H(G)
H(G2)
S(G)
Cora 2,708
5,278
7
1,433
0.81
0.71
0.89
Citeseer
3,327
4,552
6
3,703
0.74
0.56
0.81
Pubmed
19,717
44,324
3
500
0.80
0.74
0.87
Photo
7,650
119,081
8
745
0.83
0.66
0.91
Computer
13,752
574,418
10
767
0.78
0.55
0.90
Arxiv
169,343
2,332,386
40
128
0.66
0.61
0.79
Texas
183
309
5
1,793
0.11
0.54
0.79
Cornell
183
295
5
1,703
0.30
0.40
0.40
Wisconsin
251
466
5
1,703
0.21
0.42
0.42
Chameleon
2,277
36,101
5
2,325
0.23
0.35
0.67
Squirrel
5,201
216,933
5
2,089
0.22
0.22
0.73
Crocodile
11,631
360,040
5
2,089
0.25
0.30
0.71
Actor
7,600
33,544
5
931
0.22
0.21
0.68
Roman
22,662
32,927
18
300
0.05
0.67
0.59
Arxiv-year
169.343
1,166.243
5
128
0.22
0.58
0.77
C.1.1 One-hop Homophily Levels
We utilize the following edge homophily ratio [15]
measure the one-hop neighbor homophily of the graph. Specifically, the edge homophily ratio H(G) is the proportion edges that connect two nodes of the same class:
H()) {(u, v) (u, v) E & ya. -yy}
(36)
3
17

---

C.1.2 Neighborhood Context Similarity
To justify our first intuition that two nodes of the same semantic class tend to share similar one-hop neighborhood patterns even in heterophilic graphs, we consider if the same label shares similar one-hop neighborhood distributions of labels in the neighborhoods regardless of the homophily, To measure this property, we calculate the class neighborhood similarity [24] defined as follows:
mm)
Σ
cos(d(u),
(37)
WEV...EV....
where M is the number of classes, Vm is the set of nodes with class m, and d(u) is the empirical label histogram of node u's neighbors over M classes, cos(.) represents the cosine similarity function. This cross-class neighborhood similarity measures the neighborhood distributions between different classes. When m = m', smm, m') calculates the intra-class similarity. To measure the neighborhood similarity, we average the intra-class similarities of all classes:
S(G) = Σ
M smm m).
1
(38)
m=1
If nodes with the same label share the same neighborhood distributions, the class neighborhood similarity H. (G) is high.
C.1.3 Two-hop Monophily Levels
To further verify our second intuition in the introduction: two-hop similarities (monophily) still exist even without the one-hop homophily assumption, we also consider monophily properties of two-hop neighborhoods. Following [16], we use the following two-hop homophily to measure the monophily, where the neighborhood of each node is defined to be the nodes of exactly two hops away.
1 Σ, [N2(v)) Σ EmeeNaao) 1 yy.
H(G22 = M
(39)
where (2(v) denotes the set of two-hop neighborhoods u.
The statistics of datasets, including their one-hop and two-hop homophily levels and neighborhood similarities, are given in Table 3 We can observe both homophilic and heterophilic graphs exhibit strong neighborhood similarity calculated based on one-hop neighborhoods. In addition, the two-hop homophily level is generally higher than the one-hop homophily level in heterophilic graphs. This observation confirms intuition that two-hop similarities still exist without strong one-hop homophily level. The descriptions of the datasets are given below:
Cora, Citeseer, and Pubmed 44 benchmarks. Each dataset is citation and high-homophily graph, where nodes are documents, and edges are citation relationships from one to another. The class label of each node is based on the research field. A bag of words of its abstracts is used as the features of nodes. The public split is used for these datasets, where each class has fixed 20 nodes for training, another fixed 500 nodes and 1000 nodes for validation/test, respectively for evaluation.
They are among the most widely used node classification
They are co- purchasee graphs from Amazon, where nodes represent products and frequently bought products are connected by edges. Node features represent product reviews, and class labels indicate the product category. Following the experiment settings from [1] we randomly split the nodes into train/validationntest (10%/10%//8%) sets.
Computer and Photo 5 51
For these homophilic datasets, we utilized the process version of them provided by Deep Graph Library [6]]. These datasets can be found in htttps://docs.. wttpa////...////////////a//a//// dgl. dala. html
Ogbn-arxiv (Arxiv) [52 It is citation network between all Computer Science (CS) arXiv papers. Each node represents one paper and each edge indicates the citation relationships between two papers. The feature of each node is obtained by 128-dimensiona feature vector through averaging the embeddings of words in its title and abstract. The embeddings words are obtained by running the skip-gram over the MAG corpus. Following [2], we also use (0%/10%//80% split for this dataset.
Texas, Wisconsin and Cornell [3 They are webpage networks collected from computer science departments of different universities by Carnegie Mellon University. For each network, nodes are
18

---

web pages and edges indicate hyperlinks between web pages. Node features are bag-of wordd representations of web pages. The task is to classify nodes into five categories: student, project, course, staff, and faculty.
They are Wikipedia networks, where nodes represent web pages and edges represent hyperlinks between them. Features of nodes are several informative nouns on Wikipedia pages. Labels of nodes are based on the average daily traffic of the web page.
Chameleon, Crocodile and Squirrel 47
Actor 33 an actor-only induced subgraph of the cum-dirrector-ccto-vvee
network. Nodes correspond to actors and edges represent the co-occurrence of two nodes the same Wikipedia page. Node features are keywords Wikipedia pages. Labels are assigned five categories in terms of words the actor's Wikipedia.
For Texas, Wisconsin, Cornell, Chameleon, Crocodile, Squirrel and Actor, we use the raw data provided by the Geom-GCN 33 with the standard fixed 10-fold split for our experiment. These datasets can be downloaded from: https://github. httpe///githuuu.comrgggaaga wwom/ggrphmmll-.m.mm www-uuuuu-lli www.e-jlu/geom-eeee
Roman-empire (Roman) 48 is heterophilous graph based on the Roman Empire article in English Wikipedia. Each node in the graph corresponds one (non-unique) word in the text. The node features are from word embeddings. The class of a node is its syntactic role (the 17 most frequent roles as unique classes and all the other roles are grouped into the 18th class). Following [48]. we utilize the fix 10 random 50% train/validationntest splits. This dataset can be found in https:// gi thub. www.yandex-ecoooooeoooooooooeoa www.o//yadee--eeeeeeeeeeeeeeeeee rwweerreeeeeeeeeeeeeeeeeee wwwpaaarrcchheeeopoph.c. http///heeeettteueeeeeeeeeeeeeee www.pphpppssssssssss..
Arxiv-year [6 is a citation network from a subset of the Microsoft Academic Graph, where the task focuses on predicting the year that paper is posted. Nodes papers, and edges relevant to citations. The node features correspond to the average of word embeddings of the title and abstract of the papers. Following (16), 50%/25%/25% train/val/test split is utilized for this dataset. This dataset - Large-Scale
can be found in attpps:/ee thub.
C.2 Baselines
This network embedding model proposed an objective function to preserve both the first-order and second-order proximities.
LINE [4]
VGAE is a generative model based on variational autoencoder for node representation learning by directly reconstructing adjacency matrix.
VGAE 9
DGI 2]: self-supervised learning method that maximizes the mutual information between node representations and graph summary.
GCA 4 This is graph contrastive representation learning method with adaptive augmentation that incorporates various priors for topological and semantic aspects of the graph.
BGRL 55: This model is graph contrastive learning method, where the alternative augmentations of the graph are predicted to learn representations of nodes.
CCA-SSG 66]: CCA-SSG is a graph contrastive learning model, which encourages the learned representations of nodes by reducing the correlation between different views.
L-GCL [2]] It is a self-supervised node representation learning method, which samples positive samples from the first order neighborhoods and kernelizes negative loss reduce the training time.
SP-GCL [53] : This a single-pass graph contrastive learning method based on the concentration property of node representations.
HGRL 29 This is self-supervised representation learning framework graphs with heterophily, which leverages the node original features and the high-order information.
This method introduces representation learning framework by decoupling the diverse neighborhood context of a node in an unsupervised manner.
DSSL [8]
C.3 Setup and Hyper- parameter Settings
We use official implementation publicly released by the authors on Github of the baselines. For fair comparison, we used grid search to find the best hyperparameters of the basclines. We run
19

---

GCA PubMed
ADGCL PubMed
Pubmed
1.75
Aagranmta Wer
1.75
Asgmerad
84
01.
0 1.550
2 1..25
80
0.75
1.00
0.8
1.000
0.75
78
0.50
0..50
74
0.25
0.25
72
0.00
low
middle
high
0.0
OW
middle
high
0.00
low
middle
high
Frequency Band
Frequency Band
Frequency Band
Method
2.00
BGAA Squirel
GGA Squirre
2,00
ADSCL Squirel
Squirrel
8
1.75
Augrarsed 2
3 1.50
1.75
Aagneras Vin
0
1.75
Augreridd Yew
g
200
0.77
1.00
3 0.75
1.00
1.25
0.75
1:25
1,00
Accuracy
30
40
0.550
0.50
0 0.50
0.25
0.00
Tow
Frequency Band
miodle
high
0.00
0.25
Frequency Band
middle
high
0.00
0.25
low
Frequency Band
middle
high
20
Methad
Figure The average spectrum changes across these frequency bands for two augmented views. The
perturbations resulting from augmentations reveal a consistent trend in the graph spectrum.
experiments on machine with NVIDIA RTX A6000 GPU with 49GB of GPU memory. In all experiments, we use the Adam optimizer (62. A small grid search is used to select the best hyperparameter for all methods. In particular, for our GraphACL, we search À from I0, 0.90, 0.95, 0.97, 0.99, 0.999, 1). D from {256, 512, 1024, 2048, 4096, 8192), T from {0.25, 0.5, 0.75, 0.99, 1). and K from {1, 5, 10) when we utilize the negative sampling. We tune the learning rate over (0.001, 0.0005, 0.0001) and weight decay over {0, 0.0001, 0.0003, 0.000001). We select the best configuration of hyper-parameter based on average accuracy only based on the validation set.
Table 4: Node clustering performance terms of NMI (%) on homophilic and heterophilic graphs
Method
Citeseer
Computer
Photo
Arxiv
Texas
Cornell
Squirrel
Arxiv-year
VGAE
36.40s0.01
22.30
53.0020.01
31.1020.01
27.752016
17.87a013
10.834009
25.641005
DGI
43.90+n.0
31.80+am
47. 47.60+a.0
31.90=om1
34.17=007
15.92-a1s
8.49+n.15
24.35+oas
BGRL
45.38+0.04
36.20+o.7
+4.61
30.7
33.59-015
19.74-014
15.13+000
25.31
DSSL
45.9
36.82an.s
54.99am0
32.98
38.22=0.15
20.36sauN
19,85
24.45
L-GCL
46.52sn.08
37.51
55.25
32.7720.05
37.92s0.10
19.25a005
15a0m
26.87
GraphACI.
46.82xn.07
39.51
55.97
35..5
43.31
22.79
23.96:n.9
29.84
C.4 The Spectrum Changes in Augmented Views
In Figure 7 we categorize the eigenvalues (spectrum) of the symmetric normalized graph Laplacian into five distinct frequency bands, ranging from low to high. Subsequently, we computed the average spectrum changes across these frequency bands for two augmented views. The perturbations resulting from augmentations reveal a consistent trend in the graph spectrum. After augmenting the graph, we can observe that the perturbations comparatively smaller than those observed in the high-frequency components (far right) for both homophilic (PubMed) and heterophilic (Squirrel) graphs. This observation confirms that mainstream GCL methods can not work well on heterophilic graphs, particularly when the perturbation in high- figh-frequency signals more significant.
the cow-fregynncy components (far left) are
C.5 Node Clustering Performance
We also conduct node clustering to evaluate the quality of the learned node representations. Specifi- cally, we obtain node representation with GraphACL, then perform k-means clustering on the obtained representations and set the number of clusters to the number of ground truth classes. The experiment conducted five times. We report the average normalized mutual information (NMI) for clustering in Table 4 on both homophilic and heterophilic graphs. From the table, we can observe that our GraphACL can consistently improve node clustering performance compared to the state-of-the-ar self-supervised learning baselines on eight datasets. This observation, along with the results of the node classification, demonstrates the effectiveness of GraphACI. in learning more expressive and robust node representations for various downstream tasks. These results further validate that
20

---

Table 5: Experimental results (%) on the graph classification results.
Method
LINE
VGAE
GraphCL
L-GCL
DSSL
GraphACL
MUTAG
75.6+23
84.4+0.
86.8-13
85.3+ns
87.2+1.5
89.4=2.
PROTEINS
61.1a17
74.020.5
74.4.0.5
72.920.
73.5
75.3
modeling one-hop neighborhood pattern and two-hop monophily similarity benefit downstream tasks on real-world graphs with various homophily ratios.
C.6 Graph Classification Performance
Existing works for heterophilic graphs typically focus on node-level tasks (node classification and node clustering). Thus, an empirical comparison of the graph-level task is relatively not straightfor- ward. Nevertheless, for graph classification, we function, e.g. McanPooling, to obtain the graph-level representation. For graph classification, we conduct experiments on three graph classification benchmarks: MUTAG and IMDB-B, and follow the same setting in GraphCL [3]. The results are shown in Table From the table, we can observe that our ACL framework can also work well on the graph classification task and still can achieve
non-parameterized graph pooling (readout)
better (or competitive) performance compared to baselines.
Computer
Citeseer
Photo
90.0
74.0
93.5
- 89.0
73.0
93.0
88.0
92.5
887.0
72.0
Acul
86.0
A-0 00
71.0
A 00
92.0
1=0 00
NC
85.0
84.0
2-0.95
0=9797
1-0.99
70.0
0=0.97
1-0.95
A-0.99
91.0
91.5
4=0.97
83.0
69.0
90.5
0
60
120
180
240 300
30
120 150
30
60
120
150
Iterations
Iterations
Iterations
Figure The classification performance curves with varying decay rate on homophilic graphs.
Actor
Crocodile
Wisconsin
30.4
66.0
70.0
Accuracy (%)
30.2
65.5
68.0
65.0
66.0
30.0
3 64.0
64.5
1-0.00
29.8
1-0.30
1-0090
62.0
A- 0.000
1=0.95
64.0
A.0.95
60.0
A20.55
29.6
A=1.00
1=0.59
63.5
Aw0.30
A=1.00
< 58.0
A=1000
A-0.55 0.50
29.4
63.0
56.0
0
100 200 300
500
50
100
150
200 250
40
80 100
Iterations
Iterations
Iterations
Figure 9: The node classification performance with varying decay rate À on other heterophilic graphs.
C.7 The Effect of Target Decay Rate
Figures g and ? show the results of node classification with varying decay rate À on four other homophilic and four heterophilic graphs, respectively. We can still observe that having large values of A improves the overall performance. We observe that GraphACL obtains a competitive but not the best result when À 0, which confirms that slowly updating the target network is crucial in obtaining superior performance. We also notice that we can achieve good performance even with a random target encoder, i.e., 1 on some datasets, which can be explained by the recent work [63] that shows only using the simple stop-gradient operation can sometimes prevent collapsing.
C.8
The Effect of Temperature
Figures 10 and [] show the results node classification with variable temperature 7 homophilic and heterophilic graphs. We can observe that our GraphACL is not very sensitive to temperature on heterophilic graphs, while moderate hardness the softmax (large 7) produces the best result. For homophilic graphs, the large small temperature can lead to poor performance.
21

---

85
Cora
74.0
Giteseer
82.2
Pubmed
93.3
Photo
g 89.0
Computer
884
283
82
72.0
172.0
#: 92.0
881.6
x.1.8
893.2
293.1
93.0
68.0
31
21.2
92.9
87.0
80
0.5
0.790.99
0.5 0.75 0.99
81.00
0.5
0.75
10
92.8
05
1.0 Temperature
0.50
0.99
0.3 0.75
0.99
1.0
Temperature
Temperature
Temperature
Temieeralure
Figure 10: The effect of temperature on five homophilic graphs.
Chamelcon
60
Cornell
65.
Crocadile
2 238
2: 88.
229.5
254.0
28.5
29.0
150.0
08 0
02 8
28.0
0.5
0
75
0.59
1.0
0.5
0.75
0.99 1.5
46.00
0.5
0.5 0.99 1.0
65.8
0.5
0.75 0.90 1.0
65.00
0.75
0.95
1.0
Temperature
Temperature
Temperature
Figure 11: The effect of temperature on five heterophilic graphs.
Obgn-Arxiv
arXiv-year
Cornell
76.0
60.0
60.0 88
74.0
58.0
Accuracy
56.0
72.0
Accurac
56.0
54.0
Accura
52.0
50.0
68.0
52.0
48.0
10
10
5
10
Squirrel
Wisconsin
Crocodile
66.8
53.1
69.5
66.5
-6.00-
66.22
53.0
68.5
66..0
52.9
68.0
@ 65.8
52.8
65.5
52.7
67.0
66.5
65.2
65.0
52.6
66.0
K
K
Figure 12: The effect of the number of negative samples K.
Texas
Chameleon
Comell
Crocodile
Density
10.0
12.0
8.0
Inc-top
andwmn
Density
20.0
15.0
two-hop
enchro
midoo
Densit
15.0
oncihes twohss raddew
Density
40.0
bwarss Istron
30.0
4.0
10.0
10.0
20.0
2.0
5.0
5.0
10.0
0.0
1.0
-05
0.5
1.0
1.0
0055
0.5
1.0
0.0
1.0
-0.
0.5
1.0
1.0
-05
0.0
0.5
1.0
Similarity
Similarity
Similarity
Similarity
Citeseer
Pubmed
Computer
Photo
5.0
12.5
15.0
tvetep
undom
Density
4.0-
4.0
twa
rantom
4.0-
randem
3.0
7.5
2.0
2.0
2.0
5.0
2.5
1.0
0.0
0.5
0.0
0.5
1.0
0.0
1.0
0.5
0.0
0.5
1.0
0.0
1.0
-0.
0.0
0.5
1.0
0.0
1.0
0.5
0.0
0.5
1.0
Similarity
Similarity
Similarity
Similarity
Figure 13: The distribution of pair-wise cosine similarity calculated by learned representations on randomly sampled node pairs, one-hop neighbors and two-hop neighbors.
C.9 The Effect of the Number of Negative Samples
We run a sweep over the size of negative samples K to study how it affects performance. We vary as (1, 10). For each K, we first learn node representation and then use the learned node representation for node classification. Figure 12 shows the results with varying K. From the figure, we can observe that a small number of negative samples (e.g.. = 5) is enough to achieve good performance all graphs. For homophilic graphs,
observe that large K can promote the
22

---

Citeseer
Pubmed
Photo
Computer
2.5
7.0
8.0
Density
4.0
Density
2.0
25.0
6.0
7.0
5.0-
2.0
1.0
3 3
4.0
3.0
1.0
0.5
1.0
2.0
1.0
0.0
1.0
-0.5
0.0
0.5
1.0
-100
-.0
-0.5
0.0
1.0
0.0
Cosine Similarity(v, p)
Cosine Simi (iMilarity(V, p)
Cosine Similarity(v, p) Crocodile
Cosine Similarity(V, p)
Wisconsin
Chameleon
Actor
Density
12.0
10.0
8.0
Densit
8.0-
6.0
Density
10.0
8.0
5.0
4.0
6.0
6.0
4.0
6.0
4.0-
4.0-
2.0
2.0
2.0
2.0
1.0
0.0
1.0
-0.5
0.0
0.5
0.0
1.0
-0.5
0.0
0.5
1.0
0.0..0
-0.5
0.0
0.5 1.0
0.0
1.0
40.
0.0
0.5 1.0
Cosine Similaritylv. p)
Cosine Similarity(v. p)
Cosine Similarity(v.
Cosine Similarity(v. p)
Figure 14: Similarity (cosine similarity between representation and prediction = -o((v) his-
togram on different graphs.
Pubmed (i 19803)
Citesear (id 2483)
Computer
Comnel (id 106)
Texas
Crocodile 7849)
Wisconsin (id 83)
Chameleon (id
Figure 15:
Case studies. Node colors denote the semantic labels of nodes. The size of the node is proportional to its similarity to the central node denoted the star.
performance of GraphACL. In contrast, for heterophilic graphs, training with large K will lead to slight drop in performance, A possible reason is that the randomly sampled negative samples can not represent the whole node-set, given the heterogeneous and diverse patterns of heterophilic graphs.
C.10 More Similarity Histograms of Node Pairs
Figure 13 shows the additional results the representation similarity. The observations are generally similar to the results in the main body of the paper. As shown by the figure, we can observe that the randomly sampled node pairs easier be distinguished from one-hop and two-hop neighbors based on the representation similarity, which demonstrates that our GraphACL indeed captures the semantic meaning of node and will desirably push away the semantically dissimilar nodes. Moreover, the two-hop similarities in heterophilic graphs are much larger than that in homophilic graphs. These phenomena provide explanations for why GraphACL achieves good performance by capturing two-hop monophily structure information. Figure 14 shows the cosine similarity between the and prediction (v) for each node on other graphs. We can find that the cosine similarities are typically smaller than 1, which shows that the predictor is not an identity matrix after convergence. Moreover, we can observe that, compared to homophilic graph Cora, the similarities on heterophilic graph Squirrel are smaller. Since the objective of GraphACL will pull and u together, thus GraphACI, can automatically differ identity representation v and preference representation which is important for modeling heterophilic graphs. For the homophilic graph
(v)
23

---

Cora, the node identity representation v and the preference representation should be similar, which also captured by our simple contrastive objective GraphACL.
C.11 Additional Case Study Results
In Figure [5] we provide the additional case studies and visualization results on other graphs. We can find that, in most cases, nodes sharing the same semantic classes with the central nodes have larger similarities to the central nodes. This observation interprets the reason why GraphACL can achieve good performance. We observe that GraphACL can effectively capture the local neighborhood pattern and two-hop monophily for both homophilic and heterophilic graphs, which empirically verifies our theoretical analysis given in the main body of the paper.
D Societal Impacts and Limitations
There are numerous graphs in the real world that exhibit heterophilic properties, such as transaction networks, ecological food networks, and molecular networks, in which the connected nodes possess dissimilar features and distinct class labels. Given the successful deployment of Graph Neural Networks (GNNs) in various human-related real-world applications, including social networks, knowledge graphs, and molecular property prediction, it is crucial propose unsupervised represen- tation learning techniques for GNNs that can effectively handle both homophilic and heterophilic graphs, thereby potentially yielding direct social impacts.
The collection of labeled data is often expensive and impractical, particularly domains requiring specialized knowledge, such medicine and chemistry. Considering the potential positíve impact, we believe that our work can assist researchers and practitioners in devising solutions that alleviate the reliance on labeled data. However, it is important to acknowledge the potential negative consequences, as these learned representations could also be exploited for malicious purposes, such as adversarial attacks GNNs that exploit systematic biases. Nonetheless, we believe that our simple framework and theoretical insights derived from this work contribute as small step towards advancing the simplicity and generalizability of graph contrastive learning models within the research community.
24


Reviews:
[{"review_id": "0Vix0Xklsj", "reviewer": "Reviewer_fMCY", "summary": "The paper presents GraphACL, a contrastive learning method for graph representation learning. It aims to address the limitations of current methods that only consider the homophily property of graphs or rely heavily on graph augmentation methods. The authors propose an asymmetric predictor approach where the one-hop local neighborhood context and the two-hop monophily similarity are captured.", "questions": "see weakness", "limitations": "\nOverall, the paper presents an interesting and valid argument. However, to enhance its strength, the author could provide more empirical data, concrete examples, and clearer explanation of the concepts and methodology.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The premise of the need for a new contrastive learning method that does not overly rely on graph augmentation methods or the homophily property of graphs is reasonably argued and valid. Evidence from other studies or more data to support this argument could further its strength.", "weaknesses": "- The explanation of how GraphACL works and how it captures both the one-hop local neighborhood context and the two-hop monophily similarity might be difficult to comprehend for readers lacking technical background. The use of concrete examples or analogies could strengthen this argument.\n\n- The argument strength could be improved through more detailed explanation of the theoretical analysis of GraphACL, giving more justifications or linking it to established theoretical or empirical studies in the field of contrastive learning.\n\n- The paper's argument that GraphACL is a superior tool when compared to current state-of-the-art graph contrastive learning methods is backed by empirical evidence on both homophilic and heterophilic graphs. However, some rencent proposed method are missing (i.e., [1] and [2])\n\n[1] Spectral Augmentation for Self-Supervised Learning on Graphs\n\n[2] Spectral Feature Augmentation for Graph Contrastive Learning and Beyond", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer fMCY,  **we appreciate your positive feedback on our paper's soundness, novel insights, and contribution. Please find our detailed responses below:**\n \n**(C1). The explanation of how GraphACL works and how it captures both the one-hop neighborhood context and the two-hop monophily similarity might be difficult to comprehend for readers lacking technical background. The use of concrete examples or analogies could strengthen this argument.**\n \n**(R1).** We thank the reviewer for your good suggestion, which is helpful for the further improvement of our work! We will give a concrete example to help introduce monophily and one-hop local neighborhood context in the introduction part. More specifically, as mentioned by the reviewer ycWA, we will move our Figure 3 to the beginning of the introduction part, which can serve as a good concrete toy example of various design motivations (homophily, one-hop neighborhood context, and two-hop monophily) of GraphACL. \n \n**(C2). The argument strength could be improved through explanation of the theoretical analysis of GraphACL.**\n \n**(R2).** Thank you for your suggestion. We would like to give the following explanation of our theoretical analysis.  We will highlight the following discussions in the revision.\n \n- (1) Although there are many theoretical works [3,4,5,6,7] trying to theoretically understand how contrastive learning works, these works mainly focus on contrastive learning in the image IID setting, the theoretical analysis on the non-IID node representation learning (each instance is a node in one large graph and instances are inter-connected resulting in a non-IID nature) is still quite limited. Our theoretical analysis shows that our simple GraphACL can simultaneously capture one-hop neighborhood context and two-hop monophily. We also theoretically and empirically show that the learned representations by GraphACL can achieve better downstream performance and the connection between GraphACL and graph eigenvalues. **Thus, our theoretical analysis is significantly different from those works and is complementary to established theoretical studies in contrastive learning.**\n\n- (2) In addition, many established theoretical or empirical studies on image contrastive learning [3,4,5,6,7], and graph contrastive learning [1,2,8,9,10] are based on augmentations and hope that augmentations can preserve the invariant semantic nature of samples, i.e., the augmented samples have invariant semantic labels with the original ones. **However, our theoretical analysis is not based on augmentations but directly considers analyzing neighborhood distribution. Thus, GraphACL provides new perspectives on graph contrastive learning that are quite distinctive from current theoretical and empirical works.**\n \n**(C3). The paper's argument that GraphACL  is a superior tool when compared to current state-of-the-art graph contrastive learning methods is backed by empirical evidence on both homophilic and heterophilic graphs. However, some recent proposed method are missing (i.e., [1] and [2]).**\n \n**(R3).** We thank the reviewer for sharing these two works [1,2]! **We kindly want to remind the reviewer that we have conducted an extensive evaluation on  10 methods on 15 datasets , including many state-of-the-art contrastive learning methods. Thus, we believe our experiments can strongly corroborate the effectiveness and scalability of GraphACL. Nevertheless, we completely agree with the reviewer that including an empirical comparison with SPAN [1] and SFA [2] would be beneficial.** Since the code of SFA [2] has not been publicly available, we decided to compare our GraphACL with COSTA [11], which also employs feature augmentation like SPAN [2] and provides publicly available code. We ran additional experiments on SPAN [1] and COSTA [11]. For all methods and datasets, we used the same public and standard splits as in our paper, and we will include the following results in the revision:\n\n| Dataset  |     Citeseer |  (Ogbn)-Arxiv  |   Squirrel  | Chameleon |     Crocodile|    Arxiv-year |\n| --- | --- | --- | --- | --- | --- | --- |\n| COSTA  | 72.31±0.27 |  71.00±0.40 | 48.36±0.25 | 61.82±0.24 | 59.70±0.33 | 42.21±0.28 |\n| SPAN  | 72.01±0.58  | 70.94±0.24 | 49.47±0.39 | 62.55±0.36 | 61.53±0.52 | 43.95±0.41 |\n| GraphACL | **73.63±0.22**  | **71.72±0.26** | **54.05±0.13** | **69.12±0.24** | **66.17±0.24** |**47.21±0.39** |\n\nThe results are encouraging and further strengthen our contribution! The results show that our GraphACL outperforms these two competitive baselines [1,11] based on augmentations, especially on heterophilic graphs.\n\n**In light of these responses, we sincerely hope our rebuttal has addressed your comments, and believe that your comments do not affect our key contributions and can be easily addressed in the revision. We also genuinely hope you will reconsider increasing your score. If you have any other comments, please do share them with us, and we will address them further. Thank you for your efforts!**\n \n[1] Spectral Augmentation for Self-Supervised Learning on Graphs. ICLR 2023\n\n[2] Spectral Feature Augmentation for Graph Contrastive Learning and Beyond. AAAI 2023\n\n[3] A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML 2019\n\n[4] Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere. ICML 2020\n \n[5] Understanding Self-Supervised Learning Dynamics without Contrastive Pairs. ICML 2021\n \n[6] Provable Guarantees for Self-supervised Deep Learning with Spectral Contrastive Loss. NeurIPS 2021\n \n[7] Generalization Analysis for Contrastive Representation Learning. ICML 2023\n \n[8] Graph Contrastive Learning with Augmentations. NeurIPS 2020\n\n[9] Graph Contrastive Learning with Adaptive Augmentation. WWW 2021\n\n[10] Large-Scale Representation Learning on Graphs via Bootstrapping. ICLR 2021\n\n[11] COSTA: Covariance-Preserving Feature Augmentation for Graph Contrastive Learning. KDD 2022"}, {"review_id": "Aj5TulzNF2", "reviewer": "Reviewer_1K5Q", "summary": "This paper propose a simple and effective contrastive learning framework named GraphACL for both homophilic and heterophilic graphs. In particular, GraphACL can capture both one-hop local neighborhood context and two-hop monophily similarties in one single objective. The authors theoretically analyze the learning process of the GraphACL and show that GraphACL can explicitly maximize the mutual information between representations and one-hop neighborhood patterns. The experiments and theoretical analysis show the effectiveness of the proposed approach.", "questions": "1.The 184 lines of \"node identity and node preference in real-world graphs\" is not very understandable. Is this a metaphor of your own?\n2.In a general GCL methods (such as GraphCL), the representations are usually mapped into the contrastive space via a projection head before the contrastive loss is calculated. Is this operation similar to the one you mentioned in this paper.\nSome typos:\n-In Eq.9, $\\mathcal{L}_{A C L}(q)$ -> $ \\mathcal{L}_{A}(q) $", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-This paper is well written and well structured. The authors first analyze the common limitations of existing GCL frameworks, and then propose some ideas and validate them on many datasets, and finally solve these limitations through the proposed methods and theorems, making this paper well understandable.\n-The experiments and theories are sufficient to demonstrate the effectiveness.\n-This paper is an early investigation of GCL on heterophilic graphs, which provides a new direction for the subsequent development of GCL.", "weaknesses": "-It is common to know about the graph contrastive learning with graph augmentations mentioned in paragraph 3 of the introduction. For the first contrastive scheme mentioned in paragraph 2, the authors should give more details.\n-The authors should make a more specific presentation and explanation of the high-frequency and low-frequency information mentioned in the introduction and give a specific instance that high-frequency information is more beneficial for heterophilic graphs.\n-Some nodes mentioned in the description of the monophily property of the graphs in lines 190 to 192 can be corresponded to the subgraph d in Figure 3, thus making it less difficult for the reader to read.\n-The experimental setup is inconsistent. In the 296 line the authors introduce experiments on five random seeds, while in section 6.2 it is changed to ten runs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 1K5Q,  **we appreciate your great summarization and recognition of our contributions and your positive comments on our work: \"well written,\" \"early investigation,\" and \"sufficient experiments and theories.\"** Please find our responses to your comments below:\n \n**(C1). For the first contrastive scheme mentioned in paragraph 2, the authors should give more details.**\n \n**(R1).** Thank you for your valuable suggestion! The first contrastive scheme differs from augmentation-based methods. Instead, it leverages the graph's rich structure to generate contrastive signals [1,2,3,4]. This scheme operates on the homophily assumption, aiming to ensure that connected nodes exhibit similar representations in the latent space. Typically, this scheme utilizes contrastive losses similar to shallow embedding algorithms, as depicted in Table 1 of the related work [4]. We will give and emphasize these details in the revision.\n\n**(C2). The authors should make a more specific presentation and explanation of the high-frequency and low-frequency information mentioned in the introduction and give a specific instance that high-frequency information is more beneficial for heterophilic graphs.**\n \n**(R2).** We greatly appreciate the reviewer's insightful suggestion, which we believe will improve our work. **Please see our detailed responses in Global Response 2**, where we provide a more specific presentation and explanation of the high-frequency and low-frequency.\n \n \n**(C3). Some nodes mentioned  in lines 190 to 192 can be corresponded to the subgraph d in Figure 3.**\n \n**(R3).** Thanks for your suggestion! We will correspond the mentioned nodes to the subgraph d in Figure 3.\n \n**(C4). In the 296 line the authors introduce experiments on five random seeds, while in section 6.2 it is changed to ten runs.**\n \n**(R4).**  **We apologize for your confusion and we believe there are some misunderstandings.** The reason we conducted ten runs is because the standard and public split for heterophilic graphs follows a fixed 10-fold split. On the other hand, for homophilic graphs, the standard and public split is the fixed one-fold split, which is why we just used five random seeds in those experiments. However, to ensure  consistency and robustness, we also ran ten random seeds for the homophilic graphs using our published code. The results  in the table below with ten random seeds showed minimal (no) differences when compared to the five random seeds results. We apologize for your confusion and will more clearly state this in the revision.\n \n| Dataset  |     Cora |     Citeseer  |    Pubmed  | Computer |    Photo|   Arxiv-year |\n| --- | --- | --- | --- | --- | --- | --- |\n| 10 random seeds | 84.20±0.27  | 73.62±0.20 | 82.01±0.13 | 89.83±0.22 | 93.31±0.18 |71.75±0.31 |\n| 5 random seeds | 84.20±0.31  | 73.63±0.22 | 82.02±0.15 | 89.80±0.25 | 93.31±0.19 |71.72±0.26 |\n \n \n \n**(C5). The  \"node identity and node preference in real-world graphs\" is not very understandable. Is this a metaphor of your own?**\n \n**(R5).** Thanks for your insightful questions! Regarding these concepts, please see our clarifications and responses in **Global Response 1.**\n \n \n**(C6). Is the projection head in GraphCL similar to the one you mentioned in this paper.**\n \n**(R6).** Thanks for your insightful question! The projection head in GraphCL is **inherently different** from our work:\n \n- **Motivation and Method**. The projection head in GraphCL is symmetrical, relies on graph augmentations, and is built based on the idea that augmentations can preserve the semantic nature of samples, i.e., augmented nodes have consistent semantic labels with the same original nodes. However, our predictor is asymmetric and does not rely on augmentations. Instead, GraphACL directly considers predicting the neighborhood distribution in the original graph via an asymmetric predictor. Thus, our motivation and model is inherently different from GraphCL.\n \n- **Theories**. As also noticed by the reviewer, we provide a theoretical analysis to show the connection between our asymmetric predictor and one-hop neighbor context and two-hop monophily, and we prove that learned representations by GraphACL probably enjoy good downstream performance. However, the projection head in GraphCL is unclear theoretically and intuitively in its ability to capture structural information in graphs, especially for heterophilic graphs. This significant difference further sets our work apart from GraphCL.\n \n- **Experiments**. We conducted extensive experiments and analysis on both homophilous and heterophilic graphs. While GraphCL only works on homophilous graphs, for heterophilic graphs, contrastive learning has received little attention to date. Thus, we believe that demonstrating the effectiveness of our GraphACL on heterophilic graphs further distinguishes it from GraphCL\n\n**(C7). Some typos $\\mathcal{L}_{ACL} (q) $ in Eq.9.**\n \n**(R7).** Thanks for pointing out the typo! We have corrected it.\n \n**We sincerely hope that our responses can address your comments. Moreover, as noticed by the reviewer, our work presents some interesting findings, a simple yet effective framework, and some theoretical contributions. The reviewer's suggestions can be easily and effectively addressed, and we genuinely hope that the reviewer can consider increasing the score. Please feel free to let us know if there are any remaining comments. Thank you for your efforts!**\n \n[1]  Variational graph auto-encoders. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016\n\n[2] Contrastive laplacian eigenmaps. NeurIPS 2021\n\n[3] Localized contrastive learning on graphs. arXiv preprint arXiv:2212.04604, 2022\n\n[4] Representation Learning on Graphs: Methods and Applications. arXiv preprint arXiv:1709.05584"}, {"review_id": "59ksL3mY1T", "reviewer": "Reviewer_ycWA", "summary": "This paper presents GraphACL, which aims to tackle limitations of other graph contrastive learning works which have implicit or explicit homophily assumptions, and suffer in learning effective representations for heterophilic tasks.  The approach is designed to leverage the principle of monophily, and the authors evaluate their work on several homophilic and heterophilic datasets, achieving at-par performance on the former and improved performance on the latter, on downstream node classification tasks. ", "questions": "Please see \"Weaknesses\" for general comments / concerns which would be helpful during rebuttal.", "limitations": "These are addressed in Appendix E.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The approach presented here is intuitive once the monophilic principle is understood, and the implementation seems straightforward.\n\n- Results suggest the approach is strongly effective (e.g. Table 1), and hte improvement on heterophilic datasets without any material performance loss / delta on homophilic datasets is compelling.\n\n- The paper is well-written, and the figures help clarify the principles motivating the design.", "weaknesses": "- Lines 69-80 could greatly benefit from a toy example with nodes illustrated; it is confusing to understand the principles of monophily and the design of GraphACL without such an example early in the paper.\n\n- \"we are faced with the challenge of simultaneously capturing the one-hop neighborhood context and monophily in the contrastive objective\" (line 74) -- it's not clear why this is a particular challenge; is there something about capturing these two together that is difficult to reconcile in an objective?  If so, I didn't understand this from the text.\n\n- Lines 40 and 97 rely quite a bit on the (in paper) reference [22] to reference issues with contrasting view-based GCL approaches on heterophilic graphs; it would be helpful to include some more formal claims or concrete examples in this work to make it more self-contained, since the work strongly seems to draw motivation from [22]'s findings.  Without this, it is difficult to fully appreciate the supposed homophilic biases in those GCL approaches.\n\n- The section in Related Work from line 137 onwards seems to categorize BGRL as a contrastive method.  BGRL is not conventionally contrastive due to its lack of utilizing negative examples.  There are other such non-contrastive methods (several mentioned in [1]) which are used in graph SSL which should probably be mentioned in the related work in this paper.  In fact, I believe the authors' intent to pursue a graph SSL approach which does not use augmentations but instead uses induced asymmetry is actually the objective of many \"non-contrastive\" methods.  I would encourage they look into the literature and evaluate whether they indeed think their method is contrastive or not, given it's lack of need of negative samples.\n\n- The words \"context\" and \"preference\" are used quite often throughout the paper (I think sometimes to mean the same thing).  It would be helpful to formalize these words and just use the same word frequently, as it can be confusing to disambiguate which representation is which.\n\n- Can the authors clarify if/why the loss in Eqn 4 is required?  Methods like SimSiam, BYOL, BGRL etc. which use this kind of predictor structure and stop-gradient show they avoid collapse through the asymmetric predictor and the EMA procedure on target weight update.  Does GraphACL not naturally avoid collapse for the same reasons?  Does it require this uniformity regularization?\n\n- Figure 3 could go earlier to help introduce monophily and the intuition behind what existing GCL methods prioritize and what this method prioritizes.\n\n- There are a few very strong self-supervised GNN approaches missing from baselines, e.g. [2] or the approach mentioned in [1].\n\n- There are opportunities to better evaluate the quality of self-supervised representations using link-level tasks (e.g. link prediction), or several of the tasks mentioned in [2], which may offer improved understanding beyond node classification and node clustering (referenced in Sec 6.1)\n\n- Evaluation on some larger datasets with greater data diversity and lower homogeneity would have been more compelling, e.g. ogbn-arxiv or ogbn-products.  Flickr might also be a useful moderate-size heterophilic dataset to try out.\n\n- The node clustering results should be included in the main paper in my opinion -- the evaluation on just 1 downstream SSL task is fairly \"light\" and could use greater support to evidence that GraphACL is a generally strong SSL method, rather than \"SSL for node classification\" method.  This is one of the biggest gripes in this paper -- the results demonstrating that GraphACL is a very effective SSL method are sparse, with only 1 demonstrated task in the main (evaluated) paper in terms of node classification. Other graph SSL work typically considers several downstream tasks and evaluates across them.\n\n[1] Link Prediction with Non-Contrastive Learning (Shiao et al, ICLR'23)\n[2] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization (Ju et al, ICRL'23)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer ycWA, **we appreciate your perception that our model is implementation-wise simple, strongly effective, and intuitive. We thank your insightful comments and give our responses below:**\n\n**(C1). Lines 69-80 could greatly benefit from a toy example**\n\n**(R1).** Thanks for your great suggestion! As mentioned in your following comments, we will move toy examples in Figure 3 to Lines 69-80.\n\n**(C2). It's not clear why this is a particular challenge (line 74)**\n\n**(R2).** Thanks for your insightful question! We apologize for your confusion and will clearly state the following in the revision. Reconciling the objective of capturing both the one-hop neighborhood (heterophilic) context and monophily (two-hop similarity) in one contrastive objective is challenging. For instance, although homophily-driven objectives can indirectly induce monophily by directly encouraging one-hop similarity, they neglect the heterophilic context, where one-hop connected nodes are not similar. Thus, our GraphACL focuses on addressing the challenges of simultaneously and theoretically capturing one-hop neighborhood (heterophilic) context and monophily in one simple contrastive objective.\n\n**(C3). …issues with contrasting view-based GCL approaches on heterophilic graphs... include some concrete examples to make it more self-contained…**\n\n**(R3).**  Thanks for your suggestion! Please see our detailed responses in **Global Response 2**.\n\n**(C4). ...whether they indeed think BGRL and [1]  are contrastive or not, given the lack of need for negative samples...**\n\n**(R4).** Thanks for your insightful comments! The BGRL and [1] should definitely be viewed as non-contrastive due to the lack of negative samples. Our intention in Lines 142-143 is to say that BGRL is a graph self-supervised learning method based on augmentations. We will clearly state this in the main text. Moreover, as mentioned in our paper (section 4.1), even though they also use an asymmetric projection head, our motivation, objective, and theoretical insights differ significantly from BGRL which is based on invariant augmentation assumption.\n\n**(C5). It would be helpful to formalize  \"context\" and \"preference\" and just use the same word frequently**\n\n**(R5)**. Thanks for your suggestion! Please see our detailed responses in **Global Response 1**. We agree and will utilize the same \"preference\" word.\n\n**(C6). Does GraphACL not naturally avoid collapse compared to SimSiam, BYOL, and BGRL  for the same reasons? Does it require this uniformity regularization?**\n\n**(R6).** Thanks for your very insightful questions! Uniformity is important and required for GraphACL, especially for homophily graphs. As shown in our ablation studies, GraphACL w/o uniformity loss will lead to a performance drop instead of completely collapsed solutions since it still serves as a strong baseline. Moreover, the ablation (w/o both asymmetric predictor and uniformity loss) also serves as a valid baseline and does not lead to a completely collapsed solution. This is contrary to SimSiam, BYOL, and BGRL, which focus on predicting the sample representation in one augmented view via the same sample from another view. One possible reason is that GraphACL is not based on augmentation but tries to predict the representations of neighbors via an asymmetric predictor. Thus, the observed graph structure serves as a strong prior and inductive bias. Since neighbors in the graph, even in homophily graphs, do not always share the same class or similar features, making GraphACL hard to completely collapse.\n\nWe leave the theoretical and deeper understanding of this phenomenon for future work, as it may extend beyond the scope of a single paper. Nonetheless, as demonstrated in our experiments, adding a uniformity loss remains crucial for enhancing representation diversity and increasing inter-class variation, ultimately leading to good generalization. We will explicitly state this in the main text.\n\n**(C7). Fig. 3 could go earlier to help introduce monophily**\n\n**(R7).** Thank you! We agree and will move Fig. 3 earlier into introduction.\n\n**(C8). A few very strong self-supervised GNN approaches [1,2] missing from baselines**\n\n**(R8).** Thanks for raising the great works [1,2]! Following your suggestions, we compare GraphACL with [1,2]. Please see details and results in **Global Response 3.**\n\n**(C9). Beyond node classification and node clustering and using link-level tasks or the tasks in [2]**\n\n**(R9)**. Thanks for your suggestions! **We want to kindly remind the reviewer that we already have not only evaluated node classification (Table 1) and node clustering (Table 5), but also the graph classification (Table 8).** Nevertheless, we agree that including more tasks will be better. Thus, we include two more tasks: link prediction and partition prediction. For simplicity,  we follow the same settings as [2] as it provides splits for heterophilous graphs. The results given in attached PDF (Table 2) in Global Response show that GraphACL can still achieve better (or competitive) performance compared to elaborate methods.\n\n**(C10). Evaluation on some larger datasets, e.g. ogbn-arxiv or ogbn-products**\n\n**(R10).** Thanks for your great suggestions! **We believe there are misunderstandings. We have tested ogbn-arxiv, denoted as Arxiv, in Table 1 in our paper.** We also want to kindly remind the reviewer that we have tested GraphACL on 15 diverse datasets, as listed in Table 4, including various areas, sizes, and homophily ratios.\n\n**(C11). The node clustering results should be included in the main paper**\n\n**(R11).** Thank you! We will move them from the appendix to the main paper.\n\n**We sincerely hope that our responses can address your comments and hope you will consider increasing your score. Thank you so much for your efforts!**\n\n[1] Link Prediction with Non-Contrastive Learning. ICLR 2023\n\n[2] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization. ICLR 2023"}, {"review_id": "mHlcrzD1wr", "reviewer": "Reviewer_cxpZ", "summary": "This work first points out that existing GCL can fail to generalize to heterophilic graphs, then develops a new framework called GraphACL based on an encoder capturing one-hop neighbourhood context and two-hop monophyly. Experiments validate the effectiveness of the proposed method.", "questions": "Does GADC have the potential to be applied to graph tasks other than node classification shown in the paper?", "limitations": "The authors adequately addressed their work's limitations and potential societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well organized. Each part has a clear goal and supports the authors' claim well.\n\nThe proposed method, Graph Asymmetric Contrastive Learning, is not only explained in detail but also justified by solid theoretical analysis. The authors adequately answered how and why it works.\n\nIn the empirical study, the choice of baselines has good coverage. The selection of datasets respects the theme of each subsection, and the experiment setup is reasonable. The experiments are well explained, making it easy to reproduce them.", "weaknesses": "There are no significant weaknesses in this paper. The application scenario of the proposed method may be a little bit limited, but this is completely acceptable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " Dear reviewer cxpZ, **thank you for the great summarization of our contributions on both theoretical  and empirical analysis, and we appreciate your very positive and encouraging comments.** Please see our responses below:\n \n**(C1). There are no significant weaknesses in this paper. The application scenario of the proposed method may be a little bit limited, but this is completely acceptable.**\n \n**(R1).** Thanks for your positive comments! **We would like to further clarify that the application scenario of our method is actually wide due to the following two important reasons:**\n \n-  (1) Heterophilic graphs are important in various real-world domains, making them worth studying and essential to understand. Many real-world graphs demonstrate heterophilic properties. For example, in online transaction networks, fraudsters tend to connect with customers rather than other fraudsters [1]. In molecular networks, protein structures often consist of different types of amino acids linked together [2, 3]. Recent work [3] also provides a comprehensive review of so many GNNs for heterophilic graphs. High-quality datasets covering various heterophilic real-world applications have been made available through recent work [4]. For instance, malicious node detection, an important application of graph machine learning, is known to be heterophilic in many settings [4]. **Thus, studying heterophilic graphs is a significant research problem with benefits for many applications involving them.**\n-  (2) Learning effective representations for both homophilic and heterophilic graphs is also crucial for various real-world applications. In many scenarios, **collecting labeled data can be expensive and impractical, especially when domain knowledge is required, as in medicine and chemistry [5, 6].** Our model, as a key simple yet effective representation learning method, will show great potential in various high-level applications, including molecular property prediction [5,6], molecular graph generation, and drug-drug interaction prediction [7].\n\n \n**(C2). Does GraphACL have the potential to be applied to graph tasks other than node classification shown in the paper?**\n \n**(R2).** **Yes, actually, we have already conducted experiments on graph classification tasks. The reviewer can find the results in Table 8 in our Appendix D.5.** From the table, we can observe that our GraphACL performs well on the graph classification task and achieves better (or competitive) performance compared to baselines, which further strengthens our contribution.\n \n**We appreciate the efforts from the reviewer and also sincerely hope our posted responses can address your questions. We also believe your comments can also be easily addressed in the revision. As noticed by the reviewer, our work is  simple yet effective, and provides extensive theoretical and experimental analysis. In light of these responses, we sincerely hope you could consider increasing your score.  Please feel free to let us know if there are any remaining questions. Thank you for your efforts!**\n \n \n[1] NetProbe: A Fast and Scalable System for Fraud Detection in Online Auction Networks. WWW 2007\n \n[2] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. NeurIPS 2020\n \n[3] Graph Neural Networks for Graphs with Heterophily: A Survey. ArXiv preprint\n \n[4] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. NeurIPS 2021\n \n[5] Self-supervised Graph Transformer on Large-scale Molecular Data. NeurIPS 2020\n \n[6] Motif-based Graph Self-supervised Learning for Molecular Property Prediction. NeurIPS 2021\n \n[7] A Systematic Survey of Chemical Pre-trained Models. In Arxiv."}, {"review_id": "sIUp1Vnix9", "reviewer": "Reviewer_gZUY", "summary": "This paper proposes an asymmetric contrastive learning framework for the homophilic and heterophilic graphs, which does not rely on graph augmentations and homophily assumptions. The theoretical analysis and empirical results further support the effectiveness of the proposed method.", "questions": "See above", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is easy to understand and the motivation is clear and reasonable.\n2. The proposed method is simple yet effective. The authors further demonstrate the effectiveness of the proposed method from the information theory and downstream tasks perspectives. Such results give a theoretical understanding of this work.\n3. Extensive experimental results including comparison experiments, ablation study, visualization, and case study empirically verify the effectiveness of the proposed method. Moreover, the proposed method shows superior performance on both the  homophilic and heterophilic graph datasets.\n", "weaknesses": "1. This paper is somewhat over-claim and some important references are missed. In lines 45-47, the authors claim that this work makes the first attempt to design contrastive learning objectives by neither relying on explicit nor implicit homophily assumptions. Actually, there are several works already done. For example,\n[1] Wang H, Zhang J, Zhu Q, et al. Augmentation-free graph contrastive learning. arXiv preprint arXiv:2204.04874, 2022.\n\n2. The proposed objective function seems like a variant of the GCL with representation smoothing diagram and the GCL with augmented views diagram. Actually, the difference between them and the proposed method is the definition of the positive pairs. \n\n3. In this work, the authors claim that the proposed method does not rely on the homophily assumption and conduct a theoretical analysis to further support the proposed method. Are these theorems hold without any assumptions? ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer gZUY, we thank you for your valuable suggestions and positive feedback. **We are happy to hear that you found our paper to be well-written and strong in both empirical and theoretical aspects.** The following is our point-to-point response to your comments:\n \n**(C1). This paper is somewhat over-claim and the important references [1] are missed.**\n \n**(R1).** We appreciate your insightful comments! **We believe there are some important misunderstandings:**\n \n- We would like to clarify that **we did not miss the reference [1]. We cited this reference as [48] and also empirically compared their method in our experiments. It is essential to note that [1] and [48] refer to the same model and same experimental results from the same authors, with the titles being different.**\n\n- In addition, the model in [1] (i.e., [48]) actually cannot outperform many recent GCL methods on many homophilic datasets (Cora, CiteSeer, PubMed, and Photo), as reported in their paper. Conversely, our GraphACL achieves state-of-the-art results on those homophilic datasets. Thus, our claim that we are the first to attempt answering the question, \"What kind of insights and contrastive learning objectives should we look for, in order to ensure good node representations on **both homophilic and heterophilic graphs**\", **is indeed valid and not an over-claim**. We appreciate your comments and will ensure that these points are clearly stated in the revision.\n\n**(C2). The proposed objective function seems like a variant of the GCL with representation smoothing diagram and GCL with augmented views diagram. Actually, the difference between them and the proposed method is the definition of the positive pairs.**\n\n**(R2).** Thank you for your comments. While GraphACL involves positive pairs, our contributions and differences compared to other contrastive schemas go beyond that. Here, we will provide a detailed clarification:\n\n- *Comparisons with GCL methods with representation smoothing:* Different from this scheme which is based on the homophily assumption, GraphACL is asymmetric contrastive learning induced by a simple asymmetric predictor. **We theoretically and empirically show that this simple asymmetric predictor can jointly capture one-hop heterophilic patterns and two-hop monophily, which are important for heterophilic graphs.**\n\n- *Comparisons with GCL methods with augmented views:* This contrastive learning scheme relies on graph augmentations, and are built based on the idea that the augmentation can preserve the semantic nature of samples, i.e., the augmented samples have invariant semantic labels with the original one. However, our GraphACL is not based on augmentations, but  a simple asymmetric predictor. GraphACL directly considers analyzing neighborhood distribution in the original graph. **Thus, our GraphACL design is inherently different from GCL methods with augmented views.** Moreover, We theoretically show that GraphACL also implicitly aligns the two-hop neighbors and enjoys a good downstream performance for both homophilic and heterophilic graphs, which is theoretically and intuitively unclear for GCL with augmented views.\n\nGiven the above, our studied problems and insights are fundamentally different from these two schemes. Our theoretical analyses are novel and have not been proposed by these two GCL schemes. We believe that our work offers unique insights, and our technical contributions remain significant, when compared to the current GCL schemes.\n\n**(C3). In this work, the authors claim that the proposed method does not rely on the homophily assumption and conduct a theoretical analysis to further support the method. Are these theorems hold without any assumptions?**\n\n**(R3).** Thank you for your insightful questions! Actually, our theorems 1, 2, and 4 do not rely on any assumptions. Only theorem 3 makes some lightweight, reasonable, and widely-used assumptions, as mentioned in our paper. Not surprisingly, some assumptions are necessary for theoretical analysis in generalization for unsupervised node representation learning [2, 3, 4]. Specifically, our theorem 3 (downstream error on learned representation) assumes that the used downstream classifier is a mean classifier. This mean classifier assumption is very mild and has been utilized by many works [2, 3, 4]. Another lightweight assumption mentioned in our paper is the balanced class distributions. This assumption is also mild and widely-used in the literature [5]. Moreover, our theorem 3 can be easily extended to unbalanced settings in the future by considering a label shift term, as shown in domain adaptation literature [6]. Moreover, GraphACL consistently outperforms the baselines even when the classes are not well balanced, indicating that GraphACL is robust to violations of the class balance assumption.\n\n**In light of these responses, we sincerely hope our posted responses have addressed your comments and clarified any misunderstandings. We believe your comments can be easily addressed in the final version and genuinely hope that you could consider increasing your score. If you have any notable points of concern that remain unaddressed, please do share them with us, and we will promptly address them. Thank you for your efforts!**\n\n[1] Augmentation-free graph contrastive learning. arXiv preprint arXiv:2204.04874, 2022\n\n**[48] (the cited number in our submission)** Can Single-Pass Contrastive Learning Work for Both Homophilic and Heterophilic Graph? arXiv preprint arXiv:2211.10890, 2022\n \n[2] A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML 2019\n \n[3] Understanding Negative Samples in Instance Discriminative Self-supervised Representation Learning. NeurIPS 2021\n \n[4] On the Surrogate Gap between Contrastive and Supervised Losses. ICML 2022\n \n[5] Debiased Contrastive Learning. NeurIPS 2020\n \n[6] Domain Adaptation with Conditional Distribution Matching and Generalized Label Shift. NeurIPS 2020"}]

Author rebuttal:
**We sincerely thank all the reviewers for their insightful comments and helpful suggestions. Overall, the reviewers praised our work's originality, soundness, and clarity. We deeply appreciate the numerous positive comments on our work, such as describing it as "simple, effective, and intuitive," "well-written," and the "solid theoretical and empirical analysis".**

We provide this **Global Response** to address similar comments or misunderstandings from reviewers. Additionally, we have **attached a one-page PDF** containing additional experimental results suggested by some reviewers.

**(Global C1) The concept of  "node identity" and "node preference" (context) in real-world graphs**

**(Global R1)** Thanks for your comments! We would like to clarify this and will add the following responses in the revision.**

The "node true identity" and "node preference" in real-world graphs have been mainly introduced as the social concepts by [1,2]. Specifically, monophily in graphs implies the existence of nodes with strong preferences for specific nodes, which differ from their own identity. For example, users of a certain gender may not always prefer neighbors of the same gender, leading to a preference that deviates from their identity.

In our work, **we incorporate these social concepts into a practical contrastive learning framework.** We achieve this by converting the central node's identity representation to its preference (context) representation using a simple asymmetric predictor. Subsequently, the preference (context) representation of the central node is used to predict identity representations of its neighbors. **Our theoretical and empirical analysis demonstrate GraphACL effectively captures these social concepts, leading to a good performance on both homophilic and heterophilic graphs.**

**(Global C2) More explanation of the high-frequency and low-frequency information for augmentation-based GCL approaches on heterophilic graphs**

**(Global R2)**  Thanks for your great comments! We want to clarify the following points and will add the discussion below in the final version.

- **(1)** From a spectral perspective of graphs, capturing low-frequency signals involves smoothing features across the graph, ensuring similarity among node representations. This is crucial for homophilic graphs. For instance, studies [3,4,5] have shown that using different signals is an effective approach for dealing with diverse graphs: low-frequency signals for homophilic graphs and high-frequency signals for heterophilic graphs
- **(2)** GCL with augmentation operates on the principle that augmentation should retain crucial information, encouraging the model to learn invariant representations by disregarding perturbations in unimportant information. Thus, preserving important frequency signals in graph augmentation becomes essential for GCL. The previous work [6] (i..e, [22] in our paper) has theoretically shown learned representations by GCL with augmentations essentially capturing the invariant low-frequency information. **Consequently, current GCL with augmentation implicitly relies on the homophily assumption, and can not perform well on heterophilic graphs with diverse neighbors [4]. This has been also supported empirically in previous research [4], as well as in our own experimental results on both real-world  and synthetic datasets.**
- **(3) To further support the above motivation and make our work more self-contained, we evaluate the eigenvalue (spectrum) change of the augmented graph views under different methods: GCA [9], BGRL [10], and AD-GCL [11].** The results is shown in Figure 1 in our attached one-page PDF.  The results show that the variation in the low-frequency components are smaller than those in the high-frequency components, for both homophilic and heterophilic graphs. This observation confirms that mainstream GCL methods with augmentations often maintain the invariance of low-frequency signals while perturbing high-frequency signals. Moreover, these methods exhibit lower effectiveness on heterophilic graphs compared to GraphACL, particularly when the perturbation in high-frequency signals is more significant. This highlights the importance of preserving high-frequency signals in augmentation-based GCL methods for heterophilic graphs.

**(Global C3) There are a few approaches missing from baselines, e.g. [12] or [13]**

**(Global R3)** Thanks for raising great works T-BGRL  [12] and PARETOGNN [13]! Following your suggestions, we compare GraphACL with [12,13]. We follow the same data splits as our paper and present the results in Table 1 in our attached one-page PDF. We will include this comparison in our final revision. From the results, we can observe that GraphACL performs better than [12, 13], especially on heterophilic graphs. **These additional results, combined with the comparison against 10 baselines on 15 datasets using our source code in our submission, can strongly validate the effectiveness of GraphACL.**

[1] Monophily in Social Networks Introduces Similarity among Friends-of-friends. Nature Human Behaviour. 2018.
[2] Decoupled Smoothing on Graphs. WWW 2019. [3] Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021.
[4] Adaptive Universal Generalized PageRank Graph Neural Network. ICLR 2021.
[5] Revisiting Heterophily For Graph Neural Networks. NeurIPS 2022.
[6] Revisiting Graph Contrastive Learning from the Perspective of Graph Spectrum. NeurIPS 2022.
[7] Decoupled Self-supervised Learning for Graphs. NeurIPS 2022.
[8] Deep Graph Infomax. ICLR 2019.
[9] Graph Contrastive Learning with Adaptive Augmentation. WWW 2021.
[10] Large-Scale Representation Learning on Graphs via Bootstrapping. ICLR 2022.
[11] Adversarial Graph Augmentation to Improve Graph Contrastive Learning. NeurIPS 2021.
[12] Link Prediction with Non-Contrastive Learning. ICLR 2023.
[13] Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization. ICLR 2023

Meta-review: The reviewers' consensus is that the paper is well-written, and the claims are supported both by experimental evidence and theoretical analysis.
Decision: Accept (poster)