Can Single-Pass Contrastive Learning Work for Both Homophilic and Heterophilic Graph?
Authors: Haonan Wang
Jieyu Zhang
Qi Zhu
Wei Huang
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Contrastive Learning

Abstract: Existing graph contrastive learning (GCL) typically requires two forward pass for a single instance to construct the contrastive loss. Despite its remarkable success, it is unclear whether such a dual-pass design is (theoretically) necessary. Besides, the empirical results are hitherto limited to the homophilic graph benchmarks. Then a natural question arises: Can we design a method that works for both homophilic and heterophilic graphs with a performance guarantee? To answer this, we theoretically analyze the concentration property of features obtained by neighborhood aggregation on both homophilic and heterophilic graphs, introduce the single-pass graph contrastive learning loss based on the property, and provide performance guarantees of the minimizer of the loss on downstream tasks. As a direct consequence of our theory, we introduce the Single-Pass Graph Contrastive Learning method (SP-GCL). Empirically, on 14 benchmark datasets with varying
degrees of heterophily, the features learned by the SP-GCL can match or outperform existing strong baselines with significantly less computational overhead, and empirical results show the feasibility of conclusions derived by our analysis in real-world cases.

Under review as a conference paper at ICLR 2023
CAN SINGLE-PASS CONTRASTIVE LEARNING WORK FOR BOTH HOMOPHILIC AND HETEROPHILIC GRAPH?
Anonymous authors Paper under double-blind review
ABSTRACT
Existing graph contrastive learning (GCL) typically requires two forward pass for a single instance to construct the contrastive loss. Despite its remarkable suc- cess, it is unclear whether such a dual-pass design is (theoretically) necessary. Besides, the empirical results are hitherto limited to the homophilic graph bench- marks. Then a natural question arises: Can we design method that works for both homophilic and heterophilic graphs with a performance guarantee? To an- swer this, analyze the concentration property of features obtained by neigh- borhood aggregation on both homophilic and heterophilic graphs, introduce the single-pas tingle-pas graph contrastive learning loss based the property, and provide per- formance guarantees of the minimizer of the loss on downstream tasks. As a direct consequence of our analysis, we implement the Single-Pass Graph Contrastive Learning method (SP-GCL). Empirically, on 14 benchmark datasets with vary- ing degrees of heterophily, the features learned by the SP-GCL can match or out- perform existing strong baselines with significantly less computational overhead, which verifies the usefulness of our findings in real-world cases.
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf& & Welling, 201 Xu et al., 2018; Veličković et al., 2017;
Hamilton et al., 2017) have demonstrated great power in various graph-related tasks, especially the problems centered around node representation learning, such as node classification (Kipf & Welling, 2016a), edge prediction (Kipf& & Welling, 2016b), graph classification (Xu et al., 2018), etc. Prior studies posit that the good performance of GNNs largely attribute to the homophily nature of the graph data (Pei et al., 2020; Lim et al., 2021b; Zhu et al., 2020b; Abu-El-Haija et al., 2019; Chien et al., 2020; Li et al., 2021; Bo al., 2021), iee. the linked nodes are likely from the same class in homophilic graphs, e.g. social network and citation networks (McPherson et al., 2001). In contrast, for heterophilic graphs, on which existing GNNs might suffer from performance drop (Pei et al., 2020: Chien et al., 2020; Zhu et al., 2020b), similar nodes are often far apart (c.g.. the majority of people tend to connect with people of the opposite gender (Zhu et al., 2020b) in dating networks). As remedy, researchers have attempted to design new GNNs able to generalize well on heterophilic graph data (Pei et al., 2020; Abu-El-Haija al., 2019; Zhu et al., 2020a; Chien et al., 2020; Li et al., 2021; Bo al., 2021).
For both homophilic and heterophilic graphs, GNNs, like other modern deep learning approaches, require sufficient amount of labels for training enjoy decent performance, while the recent trend of the Graph Contrastive Learning (GCL) (Xie et al., 2021). 1), as an approach for learning better representation without the demand of manual annotations, has attracted great attention. Existing work of GCL could be roughly divided into two categories according to whether or not a graph augmentation is employed. First, the augmentation-basse Hassani & Khasahmadi, 2020; Zhu et al., 2021 2020d;c; Thakoor et al., 2021) follows the initial exploration of contrastive learning in the visual domain (Chen et al., 2020; He et al., 2020) and in- volves pre-specified graph augmentations (Zhu et al., 2021a); specifically, these methods encourage representations of the same node encoded from two augmentation views to contain as less informa- tion about the way the inputs are transformed possible during training, i.e., to be invariant to set of manually specified transformations. Secondly, augmentation GCL (Lee et al., 2021; 1; Xia et al., 2022) follows the recent bootsrapped framework (Grill et al., 2020) and constructs different
GCL (You et al., 2020; Peng et al., 2020;

---

Under review as a conference paper at ICLR 2023
views through nwo encoders of different updating strategies and pushes together the representations of the same node/class.
In both categories, existing GCL methods typically require two graph forward-pass, i.e., one forward-pass for each augmented graph in the augmentation- based GCL or one for each encoder in augmentation-free GCL. Unfortunately, theoretical analysis and empirical observation (Liu al., 2022; Wang et al., 2022a) show that previous GCL methods tend to capture low-frequency informa- tion, which limit the success of those methods to the homophilic graphs. Therefore, in this paper, we ask the following question:
Can one design simple single-pass graph contrastive learning method effective on both homophilic and heterophilic graphs?
We provide an affirmative answer to this question both theoretically and empirically. First, we theoretically analyze the neighborhood aggregation mechanism on a homophilic/heleropiiii graph and present the concentration property of the obtained features. By exploiting such property, we introduce the single-pun pasle graph contrastive loss and show its minimizer is equivalent to that of Ma- trix Factorization (MF) over the transformed graph where the edges are constructed based on the aggregated features. In turn, the transformed graph introduced conceptually is able to help us illus- trate and derive the theoretical guarantee for the performance of the learned representations in the down-streaming node classification task.
To verify our theoretical findings, we introduce a direct implementation of our analysis, Single- Pass Graph Contrastive Learning (SP-GCL). Experimental results show that SP-GCL achieves competitive performance on 8 homophilic graph benchmarks and outperforms state-of-ther teefttheart GCL algorithms on all 6 heterophilic graph benchmarks with nontrivial margin. Besides, analyze the computational complexity of SP-GCL and empirically demonstrate a significant reduction of computational overhead brought by SP-GCL. Coupling with extensive ablation studies, we verify that the conclusions derived from our theoretical analysis are fcasible for real-world cases.
Our contribution could be summarized as:
We show the concentration property of representations obtained by the neighborhood feature aggregation, which in turn inspires our novel single-pass graph contrastive learning loss. A directly consequence is graph contrastive learning method, SP-GCI, without relying on graph augmentations.
We provide the theoretical guarantee for the node embedding obtained by optimizing graph contrastive learning loss in the down-streaming node classification task.
Experimental results show that without complex designs, compared with SOTA GCL methods, SP-GCL achieves competitive or better performance on homophilic graph benchmarks and heterophilic graph benchmarks, with significantly less computational overhead.
2 RELATED WORK
Graph neural network on heterophilic graph. Recently, the heterophily has been recognized as an important issue for graph neural networks, which is outlined by Pei et al. (2020) firstly. To make graph neural networks able to generalize well the heterophilic graph, several efforts have been done from both the spatial and spectral perspectives (Pei et al., 2020; Abu-El-Haija et al., 2019; Zhu et al., 2020a; Chien al., 2020; Li et al., 2021; Bo al., 2021). Firstly, Chien et al. (2020) and Bo et al. (2021) analyze the necessary frequency component for GNNs to achieve good performance heterophilic graphs and propose methods that are able to utilize high-frequency information. From the spatial perspective, several graph neural networks are designed to capture important dependencies between distant nodes (Pei et al., 2020; Abu-El- Haija et al., 2019; Bo al., 2021; Zhu et al., 2020a). Although those methods have shown their effectiveness on heterophilic graphs, human annotations are required to guide the learning of neural networks.
Graph contrastive learning. Existing graph contrastive learning methods can be categorized into augmentation-basee and augmentation-free methods, according to whether or not the graph aug- mentation techniques are employed during training. The iugmentation-basee methods (You et al., 2020; Peng et al., 2020; Hassani & Khasahmadi, 2020; Zhu et al., 202 2021a;b; 2020d; Thakoor et al., 2021; Zhu et al., 2020c) encourage the target graph encoder be invariant to the manually spec- ified graph transformations. Therefore, the design of graph augmentation is critical to the success of augmentation-basel GCL. We summarized the augmentation methods commonly used by recent
2

---

Under review as a conference paper at ICLR 2023
works in Table 9 of Appendix D. Other works (Lee al., 2021; Xia et al., 2022) try to get rid of the manual design of augmentation strategies, following the bootstrapped framework (Grill et al,, 2020). They construct different views through two graph encoders updated with different strate- gies and push together the representations of the same node/class from different views. In both categories, those existing GCL methods require two graph forward-pass, Specifically, two aug- mented views of the same graph will be encoded separately by the same or two graph encoders for augmentation-baas based GCLs and the same graph will be encoded with two different graph encoders for augmentation-fie ical analysis for the performance of GCL in the downstream tasks is still lacking. Although several efforts have been made in the visual domain (Arora et al., 2019; Lee et al., 2020; Tosh et al., 2021; HaoChen et al., 2021), the analysis for image classification cannot be trivially extended to graph setting, since the non-Euclidean graph structure is far more complex.
GCLs, which is prohibitively expensive for large graphs. Besides, the theoret-
PRELIMINARY
Notation. Let 9 = (V.E) E) denote an undirected graph, where V (ui)eeN and C denote the node set and the edge set respectively. We denote the number of nodes and edges as N and E, and the label of nodes as y E H. in which y4 E [L.c],c c 2 2 is the number of classes. The associated node feature matrix denotes as X E NxF, where E IR" is the feature of node Us E V and F is the input feature dimension. We denote the adjacent matrix as A E {0, 1] NNN where A.j- = 1 if (vs; v;) E E; and the corresponding degree matrix as = diag (d1, (di,.... dy), d, = E, A.g-- Our objective is to unsupervisedly learn a GNN encoder fo : A + N receiving the node features and graph structure as input, that produces node representations low dimensionality, i.e., K < F. The representations can benefit the downstream supervised or semi- supervised tasks, c.g., node classification.
Homophilic and heterophilic graph. Various metrics have been proposed to measure the ho- mophily degree of graph. Here we adopt two representative metries, namely, node homophily and edge homophily. The edge homophily (Zhu et al., 2020b) is the proportion of edges that connect two nodes of the same class:
[[(m,.,5) (1,,,, my)l And the node homophily (Pei et al.,
hedge
2020) is defined as, knode = N En,ev [[u:aee. JEEAM, vill, which evaluates the average propor- tion of edge-label consistency of all nodes. They are all in the range of [0, 1] and value close to 1 corresponds to strong homophily while a value close to O indicates strong heterophily. As con- ventional, we refer the graph with high homophily degree homophilic graph, and the graph with a low homophily degree as heterophilic graph. And we provided the homophily degree of graph considered in this work in Table 7 of Appendix A.I.
THEORETICAL ANALYSES
In this section, we firstly show the property of node representations obtained through the neighbor aggregation (Lemma 1). Then, based on the property, we introduce the single-pass graph contrastive loss (Equation (5)), in which the contrastive pairs are constructed according to the node similarity, instead of the graph augmentations. And Theorem shows the viability of the pair selection through the node similarity computed based on node feature. We bridge the graph contrastive loss and the Matrix Factorization (Lemma 2). Then, leveraging the analysis for matrix factorization, we obtain the performance guarantee for the embedding learned with SP-GCL in the downstream node classification task (Theorem 2).
4.1 ANALYSIS OF AGGREGATED FEATURES
Assumptions on graph data. To obtain analytic and conceptual insights of the aggregated features, we firstly describe the graph data we considered. We assume that the node feature follows the Gaussian mixture model (Reynolds, 2009). For simplicity, problem. Conditional on the (binary-) label y and a latent vector l NN(0, Ir/ where the identity matrix 1 E IR FxF, the features governed by:
focus the binary classification
= +
(1)
VF
where random variable q; E R² has independent standard normal entries and yi E {-1, 1} rep- resenting latent classes with abuse of notation. Then, the features of nodes with class y; follow
3

---

Under review as a conference paper at ICLR 2023
the same distribution depending on Yt, ie.. x, Pu. (x). Furthermore, make an assumption about the neighborhood patterns, For node i, its neighbor's labels are independently sampled from a distribution P(ys).
Remark. The above assumption implies that the feature of a node depends on its label and the neighbor's label is generated from distribution only dependent the label of the central node, which contains both cases of homophily and heterophily.
With this assumption, present the following Lemma I, where we denote the learned embedding through the neighbor aggregation and a linear projection by Z, and Z; is the learned embedding with respect input x;, and the W denotes the linear weight.
Lemma 1 (Concentration Property of Aggregated Features) Consider graph G following the graph data assumption and Eq. (1), then the expectation of embedding is given by
[Z
B
W Pyy [x].
(2)
Furthermore, with a probability at least - 8 over the distribution for the graph, we have:
o Flg(2)))))/)
Z ElZilla S
(3)
2D x||22112
and
Punn (W W) log(2N22 /8) |D 1|
z Z, - BIZZ 1ill s
(4)
||x min; |l sub-exponential norms ||x lly, min, all for d [1, Besides, max (W)
where Di is the degree of node U,
D = min, Da. and the sub lob--gaussin norms
is the largest singular value of W.
Remark. Extending from Theorem in (Ma et al., 2021), the above lemma indicates that, for any graph following the graph data assumption, (i) in expectation, nodes with the same label have the same embedding, Equation (2); (ii) the embeddings of nodes with the same label tends to concen- trate onto a certain area in the embedding space, which can be regarded as the inductive bias of the neighborhood aggregation mechanism with the graph data assumption, Equation (3); (iii) the inner product of hidden representations approximates to its expectation with a high probability. Equa- tion (4); (fv) with commonly used initialization, e.g. Kaiming initialization (He et al., 2015) and Lecun initialization (LeCun et al., 2012), the o² d (WT W) is bounded and the concentration is relatively tight. (Proof and detailed discussion are Appendix C.I and C.5 respectively.)
Although the Gaussian mixture modeling on the feature, the neighborhood patterns modeling on the graph structure and the linearization on the graph neural network are commonly adopted in several recent works for the theoretical analysis of GNNs (Deshpande et al., 2018; Baranwal et al., 2021; Ma et al., 2021), 1), and their high-level conclusions still hold empirically for wide range of real-world cases, we empirically verify the derived Concentration Property (Lemma 1) on the multi- class real-world graph data and the non-linear graph neural network ( Section 6.3 and Table 6) and provide discussion about the empirical observations of the concentration property in other recent works (Wang et al., 2022b; Trivedi et al., 2022) (Appendix 1.
4.2 SINGLE-PASS GRAPH CONTRASTIVE LOSS
In order to learn a more compact and linearly separable embedding space, we introduce the single- pass graph contrastive loss based on the property of aggregated features. Exploiting the concen- tration property explicitly, we regard nodes with small distance in the embedding space as positive pairs, and nodes with large distance as negative pairs. We formally define the positive and nega- tive pairs to introduce the loss. We draw a node U, uniformly from the node set V, Us ~ Uni(V), and draw the node Uet uniformly from the St, where the S is consisted by the Kpoz nodes closest to node vs Concretely, S = {o, u?,...,, KKp = arg max (Z. Zj. K Kpos), where Kpos E - and arg max(-, Koos) denotes the operator for the top- selection. The two sampled nodes form a positive pair (v; U,+), Two nodes Uy and Uk sampled independently from the node set, can be regarded as negative pair (vz, 2k) (Arora et al., 2019). Following the insight of Contrastive
4

---

Under review as a conference paper at ICLR 2023
Learning (Wang & Isola, 2020), similar sample pairs stay close each other while dissimilar ones are far apart, the Single-Pase Graph Contrastive Loss is defined as,
Lsp-ocL- 2 E =C--na(())
Z Z++
(z) )
(5)
"st Nunnt(ppoe
"k~Cma(V)
4.3 PERFORMANCE GUARANTEE FOR LEARNING LINEAR CLASSIFIER
For the convenience of analysis, we firstly introduce the concept of transformed gruph as follows, which is constructed based on the original graph and the selected positive pairs.
Definition (Transformed Graph) Given the original graph G and its node set V, the trans- formed graph, G. has the same node set V but with the selected positive pairs as the edge set, E (vL of **)
Note, the transformed graph is formed by positive pairs selected based on aggregated features. Cou- pling with the Concentration Property of Aggregated Features (Lemma 1), the transformed graph tends have a larger homophily degree than the original graph. We provide more empirical verifi- cations in Section 6.3.
The transformed graph illustrated in Figure 1. We denote the adjacency matrix of transformed graph A E {0, {0,1)N the number of edges E, and the symmetric normalized matrix as A Agym D-1/2Añ-1/2 where D = diag (di,...,dy, E,A., Correspondingly, we denote the symmet-
Positive puirs
Transforedd graph
Figure 1: Transformed Graph formed with Positive Pairs.
ric normalized Laplacian as Laym UAUT. Here E N iu..... unl. where u, E RN denotes the i-th eigenvector of L Eym and A diag (Aı,..., AN) ) is the corresponding eigenvalue matrix. X and Ax be the smallest and largest eigenvalue respectively.
Asym
Then show that optimizing model with the contrastive loss (Equation (5)) is equivalent to the matrix factorization over the transformed graph, as stated in the following lemma:
Lemma 2 Denote the learnable embedding for matrix factorization as F E R Let F; (V:). Then, the matrix factorization loss function Lus is equivalent to the contrastive loss, Equa- tion (5), up additive constant:
CF) Asym FF Csr-ocL + const
The above lemma bridges the graph contrastive learning and the graph matrix factorization and therefore allows us to provide the performance guarantee of SP-GCL by leveraging the power of matrix factorization. We leave the derivation in Appendix C.2. With the Lemma I and 2, we arrive at conclusion about the expected value of the inner product of embeddings (More details in Appendix C.3):
Theorem For graph G following the graph data assumption, then when the optimal of the contrastive loss achieved, i.e., L (F*) = 0, we have,
BlZ Z [ ElZ, Zolwetu
where δ- Bu,,eyUnaa)) (Air 5 1 [p: vjl)-
Remark. The theorem shows that the embedding inner product of nodes from the same class is larger than the inner product of nodes from different classes. Besides, the ē, indicating the probability of an edge connecting two nodes from the same class, can be regarded as the edge homophily of the transformed graph. Therefore, the theorem implies that if the edge homophily of the transformed graph is larger, embeddings of nodes from the same class will be more compact in the high dimensional space.
Finally, with the Theorem and Lemma 1, we obtain a performance guarantee for node embeddings learned by SP-GCL with linear classifier in the downstream task (More details in Appendix C.4):
5

---

Under review as a conference paper at ICLR 2023
Theorem 2 Let fsr-GCu arg y. be minimizer of the contrastive loss, Lss-OCL. Then
there exists linear classifter B Roxk with norm probability at least - 6,
B 1p S 1/ (1 Ax) such that, with
m (W W) log(2N%/0)
Es, Ilue B fga(())) S
+
(8)
AK+1
2D
da are the smallest eigenvalues of the symmetrically normalized Laplacian matrix of the trans- formed graph
5 SINGLE-PASS GRAPH CONTRASTIVE LEARNING (SP-GCL)
As direct consequence of theory, introduce the Single-Pass Graph Contrastive Learning (SP-GCL) to verify our findings. Instead of relying on the graph augmentation function or the exponential moving average, our new learning framework only forwards single time and the con- trastive pairs are constructed based on the aggregated features. As we shall see, this exceedingly simple, theory motivated method also yields better performance in practice compared to dual-pass graph contrastive learning methods on both homophilic and heterophilic graph benchmarks. As the analysis revealed, for each class, the embedding obtained from neighbor aggregation will con- centrate toward the expectation of embedding belonging to the class. Inspired by this, we design the self-supervision signal based on the obtained embedding and propose novel single-pass graph contrastive learning framework, SP-GCL, which selects similar nodes positive node pairs. As
GNN fa
H
MLP 9w
Z
Figure 2:
Overview of SP-GCL. The graph data is encoded by graph neural network fo and following projection head Iw- The contrastive pairs are constructed based on the representation Z.
shown in Figure 2, In each iteration, the proposed framework firstly encodes the graph with graph encoder fe denoted by H fX( A). Then, a projection head with L2-normalization, Iws is employed to project the node embedding into the hidden representation Z = 9. (H). To scale up SP-GCL on large graphs, the the node pool, P, are constructed by the T-hop neighborhood of nodes (the seed node set S) uniformly sampled from V. For each seed node v; SS the top- Kpos nodes with highest similarity from the node pool are selected as positive set for which denote as S arg m (Z, Zj,, Kpos), and Kneg nodes are sampled from V to form the negative set Sneg Sheg S V. Concretely, the framework is optimized with the following objective:
2
Σ>
Σ
Z 2.
Σ
(2, Zi
N
pos
N Kung NyEVeLESE
OLEV
2et ES
Notably, the empirical contrastive loss an unbiased estimation of the Equation (5). Overall, the training algorithm SP-GCL is summarized in Algorithm 1.
Although we provide a theoretical discussion about the manner of self-selection for positive pairs and the proposed method, whether the method is effeetive and whether the self-selected manner is feasible for real-world cases are still not answered. In the following section, we empirically verify the effectiveness of the method and usefulness of our findings wide range of graph datasets.
EXPERIMENTS
6.1 PERFORMANCE ON HOMOPHILIC AND HETEROPHILIC GRAPH
The homophilic graph benchmarks have been studied by several previous works (Velickovic et al., 2019; Peng et al., 2020; Hassani & Khasahmadi, 2020; Zhu et al., 2020d; Thakoor et al., 2021; Lee et al., 2021). We re-use their configuration and compare SP-GCL with those methods and leave the detailed description about the experiment setting Appendix A. And we leave the imple- mentation details and the hyperparameter selection in Appendix A.4. The result is summarized in Table in which the best performance achieved by self-supervised methods is marked in boldface.

---

Under review as a conference paper at ICLR 2023
Algorithm 1: Single-Pass Graph Contrastive Learning (SP-GCL).
Input: Graph neural network fo, MIP projection head jun input adjacency matrix A, node features X, batch size b, number of hops T, number of positive nodes K pos- for epoch f- 1, 2. .... do
1. Obtain the node embedding, H
2. Obtain the hidden representation, Z = gw
3. Sample nodes seed node set S and construct the node pool P with the T-hop neighbors
of each node in the set S.
4. Select top-K pos similar nodes for every vi ESt to form the positive node Spos
5. Compute the contrastive objective with Eq. (5) and update parameters by applying stochastic gradient.
end for return Final model fo-
Compared with augmentation-based and augmentation-free GCL methods, SP-GCL outperforms previous methods on 2 datasets and achieves competitive performance the others, which shows the effectiveness of the single-pass contrastive loss on homophilic graphs. We further assess the model performance on heterophilic graph benchmarks that employed in Pei et al. (Pei et al., 2020) and Lim et al. (Lim et al., 2021a). As shown Table 2, SP-GCI. achieves the best performance on 6 of 6 heterophilic graphs by an evident margin. The above result indicates that, instead of relying on the augmentations which are sensitive to the graph type, SP-GCL is able to work well over a wide range of real-world graphs (described in Appendix A.I) with different homophily degree.
Table 1: Graph Contrastive Learning on Homophilic Graphs. The highest performance of unsuper- vised models is highlighted in boldface. OOM indicates Out- on 32GB GPU.
Model
Cora
CiteSeer
PubMed
WikiCS
Amz-Comp.
Amz-Photo
Coauthor-CS
Coauthor-Pho Phy.
MLP
47.92
+:
69.14
71.98 + 0.42 73.81
78.53
0.32
0.19
93.58 0.41
GCN
81.54 +: 0.68
70.73
+: 0.65
79.16 0.25
93.02 0.11
86.51 + 0.54
92.42 = 0.22
93.03 = 0.31
95.65 0.16
DeepWall Walk
70.72 0.72:0.05
31.39
0.41
73.27
0.88
0.13
85.68
+ 0.07
0.14
84.61 = 022
91.77
Node2cec
11.08:000
47.34
0.84
66.23
71.76
0.14
84.41
85.16
0.04
91.23 +
GAB
11.49
65.83
0.40
0.71
73.97
85,27
0.19
91.62=0.13
90.01
0.71
94.92
VGAE
1..21
67.41
+ 0.24
75.85
0.62
75.56
0.28
86.40
0.22
92.13 92.16
0.16
94.46 - 0.13
DGI
82.34
71.83
1: 0.54
76.78
0.31
1.13
84.01
1: 0.52
9..62
92.16
0.62
94.52 14.52:0.44 0.47
GMI
82.39 0.65
71.72
+: 0.15
79.34+
1.04
74.87
0.13
82.18
0.27
90.68
0.18
00M
00M
MVGRL
83.45 +: 0.68
73.28
+
062
77.51
87.53
92.11 9..74
95.33
GRACE
81.92 0.89
71.21
+: 0.64
80,54=036
78.19
92.15
92.1
0.20
95.26
GCA
82.07
71.33
0.37
78.40
0.13
87.85
0.14
9287
0.14
95.68
BGRL
81.44 + 0.72
71.82
+ 0.48
80.18 = 0.63
76.96
+ 0.61
89.62
+ 0.37
93.07
0.34
92.67 021
0.288
AFGRL
81.60
1 0.54
71.02
1: 0.37
80.02 = 0.48
77.98
1 0.49
89.66
+ 0.40
93.14
= 0.36
0.17 93.27
95.69 0.10
SP.GCI.
83.16 4:
71.96
76.16
79.01
89.68
0.19
92.49
91.92
0.15
Table 2: Graph Contrastive Learning on Heterophilic Graphs. The highest performance of unsuper- vised models is highlighted in boldface. OOM indicates Off-Or-yemory on a 32GB GPU.
Model
Chamelcon
Squirrel
Actor
Twitch-DE
Twitch-gamers
Genius
MLP
47.59 0.73
31.67 1 0.61
35.93 1 0.61
69.44 1 0.67
60.71 1 0.18
86.62 0.11
GCN
66.45 + 0.48
53.03
0.57
28.79 4 0.23
73.43 0.71
62.74 1 0.03
87.72 + 0.18
DeepWalk
43.99 = 0.67
30.90 = 1.09
25.50 + 0.28
70.39 = 0.77
01.7100.41
68.98 0.15
Node2eec
31.49 1.17
27.64 + 1.36
27.04 + 0.56
70.70 = 1.15
61.12 0.29
67.96 = 0.17
GAE
39.13 1.34
34.65
0.81
25.36 0.23
67.43 = 1.16
56.26:0.55
83.36 = 0.21
VGAE
42.65 + 1.27
0.92
28.43 - 0.57
0.57
68.62 + 1.82
60,70
0.61
85.17 - 0.52
DGI
60.27 0.70
42.22
+
28.30 + 0.76
72.77 + 1.30
61.47
+ 0.56
86.96 + 0.44
GMT
52.81 + 0.63
+
27.28 + 0.87
1.27
OOM
OOM
MVGRL
53.81 + 1.09
1.32 38.75
32.09 + 1.07
71.86 + 1.21
0OM
OOM
GRACE
61.24 + 0.53 0.53
41.09
28.27 + 0.43
72.49 + 0.72
OOM
OOM
GCA
60.94 + 0.81
4
28.89 1 0.50
73.21 0.83
OOM
OOM
BGRL
64.86 + 0.63
28.80 1 0.54
73.31 + 1.11
60.93 1 0.32
86.78 1 0.71
AFGRL
59.03 1 0.78
42.36
106611000 0.40
27.43
1 1.31
69.11 1 0.72
0OM
OOM
SP-GCL
65.28 1 0.53
52.10 1 0.67
28.94 1 0.69
73.51 J. 0.97
62.04 T 0.17
90.06 1 0.18

---

Under review as a conference paper at ICLR 2023
Computational requirements of standard benchmark graphs. 0OM indicates run- ning out of memory on a 32GB GPU.
Table 3:
Table 4: The performance of SP-GCL with differ- ent hidden dimension. The average accuracy over 10 runs is reported.
Dataset
CS.
Phy.
Genius
Gamers.
Nodes
18,333
34,493
421,961
168.114
WikiCS
Comp.
Actor
Twitch-DE.
Edges
327,576
991,848
984,979
6,797,557
K 256
78.32
88,40
28.12
72.53
GRACT
13.21 GB
30.11 GB
00M
00M
K 512
79.01
89.01
28.94
72.87
BGRL
GB
5.42 GB
8.18 GB
26.22 GB
K = 1024
79.07
89.68
29.87
73,51
SP-GCL
2.07 GB
3.21 GB
6.24 GB
22.15 GB
6.2 COMPUTATIONAL COMPLEXITY ANALYSIS
In order to illustrate the advantages of SP-GCL, we provide a brief comparison of the time and space complexities between SP-GCL, the previous strong contrastive method, GCA (Zhu et al., 2021b), and the memory-efficient contrastive method, BGRL (Thakoor et al., 2021). Consider a graph with N nodes and E edges, and graph neural network (GNN), J, that compute node embeddings in time and space O(N + E). BGRL performs four GNN computations per update step. in which twice for the target and online encoders, and twice for each augmentation, and a node-level projection; GCA performs two GNN computations (once for each augmentation), plus a node-level projection. Both methods backpropagate the learning signal twice (once for each augmentation), and we assume the backward pass to be approximately as costly the augmented graphs by feature masking and edge masking on the fly, the cost for augmentation computation is nearly the same. Thus the total time and space complexity per update step for BGRL, is 6Cencoder +NN)+4ppropp +Cprodt + +Caug and 4Cencoder EE [E+N ++4+++Crppo N Cprood Caug for GCA. The Cprod depends on the dimension of node embedding and we assume the node embeddings of all the methods with the same size. For our proposed method, only one GNN encoder is employed and we compute the inner product of b nodes to construct positive samples and K pos and Kneg inner product for the loss computation. Then for SP-GCL, we have: 2Ceneoder (E + N
a forward pass. Both of them will compute
N) + p-oCprooNN + Cproa(Kpor poz + Kneg)² We empirically measure the peak of GPU memory usage of SP-GCL, GCA and BGRL. As a fair comparison, we set the embedding size as 128 for all those methods on the four datasets and keep the other syper-parameters of the three methods the same as the main experiments. As shown by Table 3, the computational overhead of SP-GCL is much less than the previous methods.
Table 5: True positive ratio of selected edges at the end of training. The minimal, maximal, average, standard deviation of 20 runs are presented.
Table 6: Edge homophily of the transformed graph at the initial stage. Homophily value of original graphs is shown in parentheses.
Dataset
Aedge of Ø
Dataset
Min
Max
Avg
Std
Cora
0.812- + 0.0022 (0.810)
Cora
0.817
0.836
0.826
0.0061
CiteScor
0.6911 + 0.0018 (0.736)
CiteSeer
0.708
0.719
0.713
0.0033
PubMed
0.8197 0.0011 (0.802)
PubMed
0.820 0.832 0.825
0.0037
Coauthor CS
0.8831 1: 0.0018 (0.808)
Coauthor CS
0.892 0.905 0.901
0.0025
Coauthor Phy.
0.9521 0.0021 (0.931)
Coauthoe Phy.
0.952
0.963 0.959
0.0028
Amazon Comp.
0.8661 + 0.0019 (0.777)
Amazon Comp.
0.874
0.896 0.878
0.0076
Amazon Photo
0.9081 0.0012 (0.827)
Amazon Photo
0.916
0.0054
WikiCS
0.7511 0.0027 (0.654)
WikiCS
0.757 0.771 0.761
0.0040
Chameleon
0.6311 1. 0.0047 (0.234)
Chumeleon
0.703 0.785
0.711 0.0183
Squirrel
0.5261 0.0042 (0.223)
Squirrl
0.529 0.541 0.530 0.0024
Actor
0.3781 + 0.0026 (0.216)
Actor
0.388
0.399
0,396 0.0016
Twitch-DE
0.6691
0.0033 (U.632)
Twitch-DE:
0.693
0.703
Twitch gamers
0.6171
0.0021 (0.545)
Twiteb-gamers
0.620
0.633
0.627 0.0022
Genius
0,7851 + 0.0028 (0.618)
Genius
0.786
0.797
0.790
0.0029
6.3 EMPIRICAL VERIFICATION FOR THE THEORETICAL ANALYSIS
Effeet of embedding dimension (Scaling Behavior). We observe performance gains by scaling up models, as shown in Table 4. These observations are aligned with our analysis (Theorem 2), larger hidden dimension, K, leads to better performance (larger ÅK+1 leads to a lower bound). Coupling with the efficiency property (Section 6.2), our scalable approach allows for learning high-capacity models that generalize well under the same computational requirement.
Homophily of transformed graph (Initial Stage). The positive sampling depends largely how the hidden representation is obtained. In other words, if starting from a "poor" initialization, the GNN encoder could yield false positive samples since the inner product is not correctly evaluated in
8

---

Under review as a conference paper at ICLR 2023
the beginning. Although, our analysis shows that the concentration property (Lemma 1) is relatively tight with commonly used initialization methods (amax( (W W) of the Equation (4) is bounded, Appendix C.5) and indicates that the transformed graph formed by selected positive pairs will have large edge homophily degree, we empirically measure the edge homophily of the transformed graph at the beginning of the training stage with 20 runs. The mean and standard deviation are reported in Table 6. The edge homophily of all transformed graphs are larger than the original one with a small standard deviation, except the CiteSeer in which relatively high edge homophily (0.691) can still be achieved. The result indicates that the initialization is "good" enough at the beginning stage to form a useful transformed graph and, in turn support the feasibility of the Lemma I over the real-world data.
Distance to class center and Node Coverage (Learning Process). We measure change of the average cosine distance (1 - Ul-CoosinnSiiinn Similarity) between the node embeddings and the class-center embeddings during training. Specifically, the class-center embedding is the average of the node embeddings of the same class. As shown in Figure 3, we found that the node embeddings will concentrate on their corresponding class centers during training, which implies that the learned embedding space becomes more compact and the learning process is stable. Intuitively, coupling with the "good" initialization as discussed above, the SP-GCL iteratively leverage the inductive bias in the stable learning process and refine the embedding space. Furthermore, to study which nodes are benefited during the learning process, we measure the Node Cover Ratio and Overlapped Selection Ratio on four graph datasets. We denote the set of edges forming by the Kpos positive t't',e', Besides, we denote selection at epoch t as e' and define the Overlapped Selection Ratio as |
the set of positive nodes at at epoch t as v², Then the Node Cover Ratio at epoch is defined as: !''l Following the hyperparameters described in the previous section, we measure the Node Cover Ratio and Overlapped Selection Ratio during training. The results are shown in Figure 4, which shows that all nodes are benefited from the optimization procedure. Besides, we attribute the relatively small and non- con-increasing overlapped selection ratio to the batch training.
Selected positive pairs (End of Training). To further study the effect of the proposed method, we provide the true positive ratio (TPR) of the selected pairs at the end of training with 20 runs As shown in Table 5, the relatively large TPR and low variance suggests that the quality of the selected positive pairs is good and the learning process is stable Average Cosine Distance Curve
Ove
2.60
0.30
ChnGzer
Chamelice
2.50
2.5
2.0
0.35
Nole Loar caee
3.50
-0
40
Talting Taach
Figure 3: Average cosine distance between node emheddings and their corresponding class centers.
Figure 4: The Node Cover Ratio and Over- lapped Selection Ratio.
7 CONCLUSION
In this work, we firstly analyze the concentration property of embedding obtained through neigh- borhood aggregation which holds for both homophilic and heterophilic graphs. Then, exploiting the concentration property, we introduce the single-pass graph contrastive loss. We theoretically show that the equivalence between the contrastive objective and the matrix factorization. Further, leveraging the analysis of the matrix factorization, we provide a theoretical guarantee for the node embedding, obtained through minimizing the contrastive loss, in the downstream classification task. To verify the usefulness of our findings in real-world datasets, we implement the Single-Pass Graph Contrastive Learning framework (SP-GCL). Empirically, we show that SP-GCL can outperform or be competitive with SOTA methods on 8 homophilic graph benchmarks and 6 heterophilic graph benchmarks with significantly less computational overhead. The empirical results verify the fea- sibility and effectiveness of our analysis in real-world cases. We leave the discussion about the connection with existing observation, limitation and future work in Appendix E.
9

---

Under review as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
To ensure the results and conclusions of our paper are reproducible, we make the following efforts:
Theoretically, state the full set of assumptions and include complete proofs of theoretical results in Section 4 and Appendix C.
Experimentally, provide code, and instructions needed reproduce the main experimental results. And we specify all the training and implementation details in Section 6 and Appendix A. Besides, we independently run experiments and report the mean and standard deviation.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sami Abu-El-Haija, Bryan Perozz,, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, In international conference on machine learn- ing, pp. 21-29. PMLR, 2019.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv: arXiv:/902.00 (09.....99999 2019.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprini urXiv:2102.06966 2021.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low- frequency information in graph convolutional networks, arXiv preprint arXiv:2101.00797, 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
Fan RK Chung and Fan Chung Graham, Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual stochastic
block models. Advances in Neural Information Processing Systems, 31, 2018
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychome- trika, 1(3):211-22 111-28,, 1936.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint 1XXiv:9003002444 2019.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernaroo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances Neural Information Processing Systems, 33:21271-2122 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. arXiv preprint arXiv:1706. 022116 2017.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. arXiv preprint arXiv:2106.04156. 2021.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116-4126. PMLR, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings the IEEE international conference on computer vision, pp. 2015.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xic, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pp. 9729-9738, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02007, 2016a.

---

Under review as a conference paper at ICLR 2023
Thomas N Kipf and Max Welling. 1rXiv:161..073000 2016b.
Variational
graph auto-encoders.
arXiv preprint
Yann A LeCun, Léon Bottou, Genevieve B Orr, and Klaus Robert Müller. Efficient backprop. In Neural networks: Tricks of the trade, pp. 9-48. Springer, 2012.
Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008 01064, 2020.
Namkycong Lee. Junseok Lee, and Chanyoung Park. Augmentation-free self-supervised learning
on graphs. arXiv preprint vrXiv:2112.02477 2021.
Shouheng Li, Dongwoo Kim, and Qing Wang. Beyond low-pass filters: Adaptive feature propaga- tion on graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 450-465. Springer, 2021.
Xiang Li. Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. arXiv preprint arXiv:2205.073388, 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021a.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs arXiv preprint S0tiv:2200.01400 2021b.
Nian Liu, Xiao Wang, Deyu Bo, Chuan Shi, and Jian Pei. Revisiting graph contrastive learning from the perspective of graph spectrum. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https:
/pperreveeeeeeeeeeeeeeeee .nt worumrrrmmmmmmm Lo-.mmmT----LLLTT----.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109. (0t::2/09.05444 05641, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? arXiv preprint 2xxiv:200.06//:. 2021.
Miller McPherson, Lynn Smith-Lovin, and James Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):415-444, 2001.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Vito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 2020.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Pro- ceedings of The Web Conference 2020, pp. 259-270, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang. and Jie Tang. Gce: Graph contrastive coding for graph neural network pre-training. In Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1150-1160, 2020.
Douglas A Reynolds. Gaussian mixture models. Encyclopedia of biometrics, 741(659-663), 2009.
12

---

Under review as a conference paper at ICLR 2023
Benedek Rozemberezki and Rik Sarkar. Twitch gamers: dataset for evaluating proximity preserv- ing and structural role-based node embeddings. arXiv preprint arXiv:2101.03091, 2021.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9()xcnab014, 2021.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.0586 2018.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning graphs. arXiv preprint arXiv:2102.06514. 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redun- dancy, and linear models. In Algorithmic Learning Theory, pp.
PMLR, 2021.
Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan, Yaoqing Yang, and Danai Koutra. Augmentations in graph contrastive learning: Current methodological flaws & towards better practices. In Pro- ceedings of the ACM Web Conference 2022, pp. 1538 1549, 2022.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXivv1110.109000 2017.
Petar Velickovic, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 2(3):4, 2019.
Haonan Wang. Jieyu Zhang, Qi Zhu, and Wei Huang. Augmentation-fiee graph contrastive learning. arXiv preprint ar arxiv: 220..0444444444 2022a.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference Machine Learning, pp- 9929-9939. PMLR, 2020.
Yuansheng Wang, Wangbin Sun, Kun Xu, Zulun Zhu, Liang Chen, and Zibin Zheng. Fastgel: Fast self-supervised learning graphs via contrastive neighborhood aggregation. arXiv preprint arXiv:2205.00900 2022b.
Eugene P Wigner. Characteristic vectors of bordered matrices with infinite dimensions i. In The Collected Works of Eugene Paul Wigner, pp. 524 540. Springer, 1993.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6871. PMLR, 2019.
Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z Li. Simgrace: A simple framework for graph contrastive learning without data augmentation. In Proceedings of the ACM Web Confer- ence 2022, pp. 1070-1079, 2022.
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. arXiv preprint arXiv:2102.107577 2021.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances Neural Information Processing Systems, 33:5812-5823, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra, Graph neural networks with heterophily. arXiv preprint arXiv:2009.13566, pp. 11168- 11176, 2020a.
Jiong Zhu. Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. arXiv preprint arXiv:2006. 1468, 2020b.
13

---

Under review as a conference paper at ICLR 2023
Qi Zhu, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han, and Carl Yang. ing of graph neural networks with ego-graph information maximization. w0X1::2009.05204, 2020c.
Transfer learn- arXiv preprint
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv preprint 2tt::2000.44331 2020d.
Yangiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings the Web Conference 2021, pp. (069-2080, 2021b.
14

---

Under review as a conference paper at ICLR 2023
A APPENDIX: EXPERIMENT SETTING
A.1 DATASET INFORMATION
We analyze the quality of representations learned by SP-GCL on transductive node classification benchmarks. Specifically, we evaluate the performance of using the pretraining representations on benchmark homophilic graph datasets, namely, Cora, Citeseer, Pubmed (Kipf Welling, 2016a) and Wiki-CS, Amazon Amazon-Compunn Computers, Amazon-Phhote Coauthor-CS, Coauthor-Physse 2018), as well as 6 heterophilic graph datasets, namely, Chameleon, Squirrel (Rozemberczki al., 2021), Actor (Pei et al., 2020), Twitch-DE, Twitch-gamers (Rozemberczki & Sarkar, 2021), and Genius (Lim et al., 2021b). The datasets are collected from real-world networks from different domains; their detailed statisties summarized in Table 7. For the 8 homophilic graph data, we use the processed version provided by PyTorch Geometric (Fey & Lenssen, 2019). Besides, for the 6 heterophilic graph data, of them, e.g., Chameleon, Squirrel and Actor are provided by PyTorch Geometric library. The other three dataset, genius, twitch-DE and twitch-gamers can be obtained from the official github repository's in which the standard splits for all the heterophilic graph datasets can also be obtained. Those graph datasets follow the MIT license, and the personal identifiers are not included. We do not foresee any form of privacy issues.
(Shchur et al.,
Table 7: Statistics of datasets used in experiments.
Name
Nodes
Edges
Classes
Feat.
Anode
hedge
Cora
2,708
5,429
7
1,433
.825
.810
CiteScer
3,327
4,732
6
3,703
.717
.736
PubMed
19,717
44,338
500
.792
.802
Coauthor CS
18,333
327.576
15
6,805
.832
.808
Coauthor Phy.
34,493
991,848
5
8,451
.915
.931
Amazon Comp.
13,752
574,418
10
767
.785
.777
Amazon Photo
7,650
287,326
745
.836
.827
WikiCS
11,701
216,123
10
300
.658
.654
Chameleon
2,277
36,101
5
2,325
.103
.234
Squirrel
5,201
216,933
5
2,089
.088
.223
Actor
7,600
33,544
9,31
.154
.216
Twitch-DE
9,498
153,138
2
2,514
.529
.632
Twitch-gamer saaeers
168,114
6,797,557
2
7
.552
.555
Genius
421,961
984,979
2
12
.477
.618
A.2 BASELINES
We consider representative baseline methods belonging to the following three categories (1) Tra- ditional unsupervised graph embedding methods, including DeepWalk (Perozzi et al., 2014) and Node2Vec (Grover & Leskovec, 2016). (2) Self-supervised learning algorithms with graph neural networks including Graph Autoencoders (GAE, VGAE) (Kipf & Welling, 2016b) Deep Graph In- fomax (DGI) (Velickovic et al., 2019) Graphical Mutual Information Maximization (GMI) (Peng et al., 2020), and Multi-Viee Graph Representation Learning (MVGRL) (Hassani & Khasahmadi, 2020), graph contrastive representation learning (GRACE) (Zhu et al., 2020d) Graph Contrastive learning with Adaptive augmentation (GCA) (Zhu et al., 2021b), Bootstrapped Graph Latents (BGRL) (Thakoor et al., 2021). Augmentation-Free Graph Representation Learning (AFGRL) (Lee al., 2021), (3) Supervised learning and Semi-supervised learning, e.g., Multilayer Perceptron (MLP) and Graph Convolutional Networks (GCN) (Kipf & Welling, 2016a), where they are trained an end-to-end fashion.
A.3 EVALUATION PROTOCOI.
We follow the evaluation protocol of previous state-of-the-un graph contrastive learning approaches. Specifically, for every experiment, we employ the linear evaluation scheme as introduced (Velick- ovic et al., 2019), where each model is firstly trained in unsupervised manner, then, the pretrained
'https:: :/ club.ccom/cJA /Non Homoph i Ly-laarge salaaa--scaaaa Scale
15

---

Under review as a conference paper at ICLR 2023
representations used to train and test via simple linear classifier. For the datasets that came with standard train/valid/test splits, we evaluate the models on the public splits. For datasets without stan- dard split, e.g., AmaazonComputern Amazon- Photo, Coauthor-CS, Soauthor-Physice split the datasets, where 10%/10%/80% of nodes are selected for the training, validation, and test set, respectively. For most datasets, report the averaged test accuracy and standard deviation 10 runs of classification. While, following the previous works (Lim et al., 2021b;a), we report the test ROC AUC on genius and Twitch-DE datasets.
randomly
A.4 IMPLEMENTATION DETAILS
Model architecture and hyperparamters. We employ a two-layer GCN (Kipf Welling, 2016a) the encoder for all methods. The propagation for single layer GCN is given by,
GCN,(X, - (D ( xw.).
where Á = I the adjacency matrix with self-loops, D is the degree matrix, is linear activation function, such as ReLUU, and W; is the learnable weight matrix for the i'th layer. Besides, following the previous works (Lim al., 2021a;b), the graph encoder for the heterophilic graphs. The hyperparameters setting for all experiments are summarized in Table 8. We would like release our code after acceptance.
batch normalization within
Linear evaluation of embeddings. In the linear evaluation protocol, the final evaluation is over representations obtained from pretrained model. When fitting the linear classifier on top of the frozen learned embeddings, the gradient will not flow back to the encoder. We optimize the one layer linear classifier 1000 epochs using Adam with learning rate 0.0005.
Hardware and software infrastructures. Our model are implemented with PyTorch Geometric 2.0.3 (Fey & Lenssen, 2019), PyTorch 1.9.0 (Paszke et al., 2017). We conduct experiments on computer server with four NVIDIA Tesla V100 SXM2 GPUs (with 32GB memory each) and twelve Intel Xeon Gold 6240R 2.40GHz CPUs.
Table 8: Hyperparameter settings for all experiments.
Ir
K
Kneg 100
b
T
K
pose
Cora
.0100
512
1024
CiteSeer
.0020
200
256
1024
PubMed
.0010
256
1024
WikiCS
.0010
5
100
512
1024
Amz-Comp.
.0010
5
100
256
1024
Amz-Photo
.0010
100
512
1024
Coauthor-CS
.0010
1024
Coauthor- Phy.
.0010
100
256
1024
Chameleon
.0010
5
100
512
1024
Squirrel
.0100
5
100
512
1024
Actor
.0010
100
512
1024
Twitch-DE
.0010
1024
Twitch-gamers
.0010
100
256
128
Genius
.0010
5
100
256
512
B APPENDIX: ABLATION STUDY
B. EFFECT TOP-K POSITIVE SAMPLING
We study the effect of top-K positive sampling on the node classification performance by measuring the classification accuracy and the corresponding standard deviation with wide range of K. The results over WikiCS, Chameleon. Squirrel, Cora, and Photo are summarized in Figure 5. We observe that the performance achieved by SP-GCL is insensitive the selection of K from 2 18.
16

---

Under review as a conference paper at ICLR 2023
09
00
06
dhamekocn
944
Cora
aqaim
chama
T0pk
T-hop Neightrthodd
Figure effect of top-K positive sam- pling on the Performance.
Figure 6: The effect T-hop neighborhood the Performance.
B.2 EFFECT OF HOHOP NEIGHBORS
Factor T' is the other factor involved in node sampling. We provide a study about the the effect of T-hopp neighbors on the node classification performance by measuring the classification accuracy or ROCAUC score and the corresponding standard deviation with different T. Specifically, with the same evaluation protocol described in Section A.3, we measure the classification accuracy on Squirrel, Cora, Actor, and Chameleon dataset and ROCAUC score on twitch-DE. As shown in Figure 6, the performance achieved by SP-GCL is insensitive the selection of T.
C APPENDIX: DETAILED PROOFS
C.I PROOF OF LEMMA
Proof. We first calculate the expectation of aggregated embedding:
Blfo(x.)] = E W
Σ SENT()
=
W Ps; Px (x)
(10)
D
This equation is based the graph data assumption such that xj P (x) for every j. Now we provide a concentration analysis. Because each feature x, a sub-Gaussian variable, then by Hoeffding's inequality, with probability least 1 8 for each d E [1, FJ. we have,
1 D., Σ (x,.. E(x,,a))
$ -Exx,))))
log(2/5') 2D Dl.lll,,
(11)
where |x is sub-Gaussian norm of Xj.d- Furthermore, because each dimension of x; is i.i.d. thus have ||x; ll = ولل for d F). Then we apply union bound by setting 8' F8 on the feature dimension k. Then with probability at least d we have
1 D
- -
s
log (2F/8)))
(12)
2D |
Next, use the matrix perturbation theory,
D Σ - E(x,,a)
SVF
Ex E(x;,))
Dii
(13)
Flog(2F/6)
2D., |x|
Finally, plug the weight matrix into the inequality,
(x)) E[fe(x))]] < Fmax (W)
D., E(x,, - Bxx.a)
(14)
17

---

Under review as a conference paper at ICLR 2023
where max is the largest singular value of weight matrix.
Next, we perform a concentration analysis for the inner product. We first write down the detailed expression for each pair of i,
x; W Wx,
(15)
We first bound x Xj. Because x, and x; independently sampled from identical distribu- tion, then the product x xj is sub-exponential. This been seen from Orilicz norms relation that ||*² ([]x2Il=2) where |x]| is sub-exponential norm of x². Then by the Hoeffding's inequality for sub-exponential variable, with a probability at least 6, we have
W
W) (2/()
x Xj Px (x] x;|1 S
(16)
x 1
Because that the aggregated feature is normalized by the degree of corresponding node, we have, for each pair of i,j
log(2/8)o max (W W)
P
W W) log(2/6)
88y E]s I
(17)
2 x 11 DaDjj
2 x2 12 D2
where = min, Di for E [1. Finally we apply a union bound over a pair of i.j. Then with probability least 1 we have
T W) (log(2N2/))
z, Z, E 2, S
(18)
2D 1D1 llu
C.2 PROOF LEMMA
To prove this lemma, we first introduce the concept of the probability adjacency matrix. For the transformed graph 9, we denote its probability adjacency matrix W, in which ú:s 1/2 A.y. uy can be understood as the probability that two nodes have an edge and the weights sum to because the total probability mass
Eij Wi.s' = 1, for U4 Uj E V. The corresponding symmetric normalized matrix is W eym = D / and the Dw diag([w),.... WNl). where w; Σ, Way. Wj.. We then introduce the Matrix Factorization Loss which is defined as:
min FERNKE
(m)(F) = Aayin FF
(19)
By the classical theory on low-rank approximation, Eckart- Bckart-Young-Na Young-Mirsky theorem (Eckart Young, 1936), any minimizer F of Cmr(F) contains scaling of the smallest cigenvectors of Laym (also, the largest eigenvectors of A symm) up to right transformation for some orthonormal matrix R E RKXK We have F F* diag To proof the Lemma 2, we first present the Lemma 3.
Xi...., VI-Viili Axx R, where F [n u.. .u]] RNX
Lemma 3
For transformed graph, its probability adjacency matrix W. and adjacency matrix A are equal after the symmetric normalization, W sym Asym-
Proof. For any two nodes Us Uy E V. and * j. we denote the the element i-th row and j-th column of matrix W sym Wii
W
Av A agm-
sym
En Wisk /
Waj
E
Ex Ary Eg Ans
(20)
Leveraging the Lemma 3, present the proof of Lemma 2.
18

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 2
We start from the matrix factorization loss over Asym show the equivalence.
A sym
FF
1
W
sym
FF FF 11
Smi((s))
Vios / B3
(mu [mn(
fun (ms( fma((;)) + IIW mym 11
Vin / v0,
(21)
Σ
Smr(v:))
Smr(uy))]
Viog
V0g
wis Σ
fmi((:))) Smm((;))) + C T
where [mi( is the i-th row of the embedding matrix F. The wy which can understood as the node selection probability which is proportional to the node degree. Then, we can define the corresponding sampling distribution as Pdeg. If and only if /w, Fo(ei) = fme(wr) = F,, the we
have:
E Ex,-Paco PyrPPag
(Fo(ue) (Fu(u)"FFo(us) E vyntimtt SCRAN(O))
(Fo(oE) (Fo(ot))Fo((tt))) +C
(22)
where NV(:;) denotes the neighbor set of node 8s and Uni(-) is the uniform distribution over the given set. Because we constructed the transformed graph by selecting the top- Kpos nodes for each node, then all nodes have the same degree. We can further simplify the objective as:
Eei-Urity) By my
[z) (z.
2
Z Z,++ ) +C.
(23)
Due to the node selection procedure, the factor /w, is a constant and can be absorbed by the neural network, Fs.. Then, because Z, F& (v:). we can have the Equation 23. Therefore, the minimizer of matrix factorization loss is equivalent with the minimizer of the contrastive loss.
C.3 PROOF OF THEOREM
Proof. Now we provide the proof for the inner product of embedding. In particular, when can achieve near-zero contrastive learning loss, i.e,, Lut (F) = 0, the minimizer F of (F) contains scaling of the smallest eigenvectors of L Lym (also, the largest eigenvectors of A Asym), F juj U2. ux] E I N according to the Eckart- Morskyyirsky theorem (Eckart & Young, 1936). Recall that y {1, 1 Nx1 is label of all nodes. Then we show there is constraint on the quadratic form with respect to the optimal classifier. According to graph spectral theory (Chung & Graham, 1997), the quadratic form
y L Lym = (A - y2r)² 2 2,87
which captures the amount of edges connecting different labels. Furthermore, suppose that the expected homophily over distribution of graph feature and label, i.c., y P(yi), Ps (x). through similarity selection satisfies ([Mhadge()) = 1 - Φ. Here Ø Ee,eerUUrr(() (Ai,j [yy + vzl)- Since we have defined that / as the density of edges that connects different labels, we can directly show that y" T Leymy S 2N. Then we expand the above expression accoding to Leym = I syms
Lsymy - Agmm Jy N y Asgny
Next we consider the situation that we achieve the optimal solution of the contrastive loss, Z = arg min LSP-OCL- Then, we have f analyzed in Section C.2, we have Z = F in this case. Furthermore, we have,
O, which implies that A Asym (F*) As
y I Legmy = y T A A by = y Z Zy = N N (Z. Z7)..EEE)))
= N - [
2 Zy luc - Σ Z Z, (lm
(24)
1,j
19

---

Under review as a conference paper at ICLR 2023
This leads to,
Σ z Zy 1u
Zylsc
Σ 2 Zy [. 1,3
E|Z 2ylu:=zy] -E|Z, Z Zyluceus
(25)
N
C.4 PROOF OF THEEREMM
Recently, HaoChen et al. (2021) presented the following theoretical guarantee for the model learned with the matrix factorization loss.
Lemma For a graph g, let fint E arg min fu::V--RKK be minimizer of the matrix factorization loss, Linf (F), where F, [mf((e)) Then, for any label y, there exists linear classifier B R with norm B I 11/ Xx) such that
Φ²
E
11
B Smr
S
(26)
AK+1*
where Ts is the one-hot embedding of the label of node us The difference between labels of connected data points is measured by Φ², 6x :- E Evagye Aij [y: # vi]-
Proof of Theorem 2. This proof is direct summary on the established lemmas in previous section. By Lemma and Lemma 4, we have,
Eu || TBB.BB'Jaa faa
(27)
Ak+1
where Å is the i-th smallest eigenvalue of the Laplacian matrix Leym I À sym. Note that @ in
Lemma 4 equals hedge.
Then we apply Theorem and Lemma 1 for hedge to conclude the proof:
3 + o (W W) (og(2/222/8)
1 - hedge
20 1x
Ex T B' fa (u)(
ÂK+1
(28)
3
Faax
W) (2g(2.22/))
Ax+1
2D x2 11 82+11
C.5 INFLUENCE OF RANDOM INITIALIZATION
Recall that the concentration inequality for inner product of embedding in Lemma 1 is:
a2
max (WT W) log(2N2/6)
Z Z3 E 2,
S
2D x2 llv
As shown by Lemma 1, the accuracy of using the graph encoder to obtain the similarity between two nodes is determined by the maximum singular value of the weight of the graph encoder. In other words, the quality of the transformed graph is guaranteed if we can be sure that the maximum singular value of the weight (of the graph encoder) bounded. When initializing the network, we generally use Gaussian initialization, such as, Kaiming and Lecun initialization (He et al., 2015; LeCun al., 2012). Then T W will a Wishart matrix, and the limiting spectral density can be shown to be the Marchenko-Pasee bounded when K/F bounded, where W E IR P As result, the quality the transformed graph can be guaranteed with high probability under condition that K/ F is bounded.
distribution (Wigner, 1993), whose largest singular value is
On the other hand, we assume that for node i, its neighbor's 's labels are independently sampled from distribution P(y)). This means that the probability of edge between two nodes be fixed given labels. In this case, the degree seales linearly with number nodes N. In the large graph limit, D will tends infinity, thus bound can be tighter.
20

---

Under review as a conference paper at ICLR 2023
Table 9; Summary of graph augmentations used by representative GCL models. Multiple" denotes multiple augmentation methods including edge removing, edge adding, node dropping and subgraph induced by random walks.
Method
Topology Aug.
Feature Aug.
DGI (Velickovic et al., 2019)
Node Shuffling
GMI (Peng et al., 2020)
Node Shuffling
MVGRL (Hassani Khasahmadi, 2020)
Diffusion
GCC (Qiu et al., 2020)
Subgraph
GraphCL (You ct al., 2020)
Multiple"
Feature Dropout
GRACE (Zhu et al., 2020d)
Edge Removing
Feature Masking
GCA (Zhu et al., 2021b)
Edge Removing
Feature Masking
BGRL (Grill al., 2020)
Edge Removing
Feature Masking
D AUGMENTATIONS IN EXISTING WORKS
DISCUSSION
E.I CONNECTION WITH EXISTING OBSERVATIONS
In Lemma 1, we theoretically analyze the concentration property of aggregated features of graphs following the Graph Assumption (Section 4.1). The concentration property has also been empirically observed in some other recent works (Wang et al., 2022b; Trivedi et al., 2022). Specifically, in the Figure of Wang al. (2022b), a t-SNE visualization node representations of the Amazon-Phon dataset shows that the representations obtained by randomly initialized untrained SGC (Wu al., 2019) model will concentrate to a certain area if they are from the same class. This observation also provides explanation for the salient performance achieved by SP-GCL the Amazon-Phon Photo, as shown in Table
E.2 LIMITATION AND FUTURE WORK
Our work only the first step in understanding the possibility of single-pass graph contrastive learn- ing and the corresponding performance guarantee on both the homophilic graph and heterophilic graph. There is still lot future work to be done. Below we indicate three questions that need to be addressed.
Our theoretical framework is built upon the graph assumption (Section 4.1) in which we assume the neighbor pattern. The graph assumption includes the homophilic graph and the "benign" heterophilic graph. However, there could exist graphs in which the neighbor pattern is messy or arbitrarily distributed. still an open question to understand the graph contrastive learning on those graphs
Recently, several Graph neural networks (Zhu et al., 2020b; Chien et al., 2020; Luan et al., 2021; Li et al., 2022) have been proposed to work on heterophilic graphs. Whether further improvement can be achieved through combining with those GNNs is still an open question. To verify the effectiveness of our theoretical findings, we keep the implementation to be simple. Whether a better performance can be achieved by involving more complex techniques still need to be explored.
21


Reviews:
[{"review_id": "sI-guOYhF7k", "reviewer": "Reviewer_Lvdk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Summary and main concern. Is a dual-pass necessary for computing contrastive loss even when heterophily is taken into account? The concentration analysis and the factorization interpretation are very interesting in answering this question. A single passs contrastive learning is implemented. Many benchmarks are explored in the experimental section. \n\nThe key to this insight is to embed nodes from the same class close and nodes from different classes far apart. In this regard, aggregated features as normal variables less to bound the variance (concentration lemma). Interestingly the bounds are governed by the singular values of the weights and also their correlation. As a result, nodes with similar labels have a similar embedding, and a contrastive loss can emerge from distinguishing close nodes from far away (in the sense of adjacency powers or k-hops).  Close nodes lead to positive edges (pairs) with in turn lead to a transformed graph that bridges graph contrastive learning with matrix factorization. \n\nExperimental results are very impressive. The appendix is very informative and the code is released. \n\nSuggestion. Using the concentration property explore the minimization o the entropy (can be a nice regularizer since the concavity of entropy)", "summary_of_the_review": "A nice paper, very direct and out-standing. ", "strength_and_weaknesses": "* Strengths. The simplicity of single-pass contrastive learning with a nice theoretical background (concentration bounds). \n* Weaknesses. K-hops are not really scalable (suggest using other measures such as learnable commute times to avoid OOM). ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "f95G-WF8WP", "reviewer": "Reviewer_yTDn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a single-pass contrastive learning method for graph data, without the need of graph augmentation or encoder perturbation to generate contrastive samples. In particular, they select the positive samples based on the inner-product of the hidden representation for each central node. The method is quite simple. For evaluations on both homophilic and heterophilic graphs, the performance of the proposed method is sufficiently justified.", "summary_of_the_review": "The biggest concern about this paper is that the theoretical results seem unable to support the benefit of the proposed contrastive learning method against other previous approaches.", "strength_and_weaknesses": "Strengths:\n\n1. Directly exploring the inner-product of hidden representations as the similarity to select positive samples is able to handle the heterophilic case, which is more reasonable than typical methods such as DGI and GMI where the positive samples are constructed from the neighbors. \n\n2. While the proposed method is simple, the authors have tried to theoretically reveal the benefits of the proposed method. Although the conclusions from Lemma 1 to Theorem 1 are not that surprising, they somehow strictly explain the motivation of this paper. \n\n3. Experiments are fully carried out, with sufficient comparisons with many baselines and the ablations. Even in certain cases, the performance is not as good as SOTA, the validity of the proposed method and stability of the training process are mostly supported.\n\nWeaknesses:\n\n1. The assumption that each node is generated IID is not very reasonable. This makes the conclusion of Lemma 1 irrelated to the graph structure of the input data. In graph learning, people are more interested in how the distribution of different node is related to each other, and prefer that the nodes are sampled from a non-IID distribution. Otherwise, Lemma 1 is also applicable to the case when using MLP (instead of GNN) for node hidden representation, which is not desirable. When considering the goal of this paper, Lemma 1 is also less informative in telling how the node homophily affects the hidden representation.\n\n2. Lemma 2 and Theorem 1 are interesting, and make valuable results on how the contrastive loss in Eq. (5) is related to transformed graph, why performing contrastive learning helps node classification (Eq. 7), and how the edge homophily of the transformed graph affects the contrastive learning bound (Eq. 7). However, all these results are unable to justify the validity of selecting the positive nodes according to the inner product of hidden representation vectors, which is the central contribution of this paper. Lemma 2 and Theorem 1 hold regardless of how the transformed graph (the positive samples) is constructed. It is still unclear why the proposed theorems can support the benefit of the proposed single-pass contrastive learning against previous methods such as DGI and GMI. In other words, if we build the transformed graph by DGI or other sampling method, do Lemma 2 and Theorem 1 still hold? If so, what is the point they make?\n\nI am happy if the authors can comment if I have missed something important. \n\n\nQuestions:\n\n1. What is the theorem in (Ma et al. 2021)\n\n2. It is suggested to indicate that F_i is Z_i in Lemma 2. \n\n3. What is the relationship between Lemma 1 and other theorems?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QuqS3paJML", "reviewer": "Reviewer_5Ey9", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of conducting contrastive learning on graphs and introduce a single-pass graph contrastive learning framework for both homophilic and heterophilic graphs. The authors also try to provide some theoretical analysis to demonstrate that the design is effective. The experimental results show that the proposed objective outperforms existing graph contrastive learning works.", "summary_of_the_review": "Overall, this paper's high-level idea and the objective function have been proposed by previous work [2]. The clarity and evaluation of this paper should also be improved. ", "strength_and_weaknesses": "This paper is generally well organized, and the motivation of the proposed method is clearly described. The reviewer has the following concerns:\n\n(i) Originality: My first concern is the novelty, and the reviewer feels the technical contributions are quite limited. For theoretical contribution, the theoretical analysis provided by the paper is quite similar to previous works. For instance, Lemma 1 (Concentration Property of Aggregated Features) has been proposed by work [1]; the inner product with the spectral norm in Lemma 1 is just a trivial extension of [1]. Lemma 2  and Theorem 2 (contrastive loss is equivalent to the matrix factorization) have also been proposed by [2]. The concept of the augmentation graph has been proposed by  [2]. Moreover, the proposed objective function (Single-Pass Graph Contrastive Loss in Eq. (9)) is the same as the spectral contrastive loss proposed by previous work [2]. The contribution of this paper is over-claimed.\n\n(ii) Clarity. The design of the model is also unclear, and there is no clear connection between the theoretical results and the algorithm. For instance, the design of hard top-k positive and negative pairs and neighbor sampling are important but do not have theoretical justification. There are several assumptions on the node label/feature/neighborhood distributions. The non-linear operations in the GCN have also been dropped. Although theorem 1 is related to homophily and heterophily, why can the single-pass graph contrastive loss address the learning problem homophily in definition 1? What is the relation between Theorem 1 and single-pass graph contrastive loss? Current theorems can not prove the effectiveness of the proposed objective on homophily and heterophily graphs.\n\n(iii) Quality: The experimental results are also not sufficient. Lack of some important ablation studies and qualitative analysis. For instance, what are the effects of top-k positive sampling and surrounding T-hop neighbors on the performance? To gain more insight into the behavior of the unsupervised method, it would also be better to visualize the embedding space learned.  \n\n[1] Is Homophily a Necessity for Graph Neural Networks. ICLR 2022.\n[2] Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss. NeurIPS 2021.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1deQtRIJnsC", "reviewer": "Reviewer_RpbG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In summary, this paper provides one single-pass contrastive learning method which can work for both homophiles and heterophilous graphs. One single-pass contrastive loss is designed based on the concentration property, and its minimizer is equivalent to MF over the transformed graph. \n\n", "summary_of_the_review": "It is interesting to designing the single-pass loss for contrastive learning, while it is not well motivated when applying them under the heterophily settings. Then, the contribution compared with the existing methods is limited.", "strength_and_weaknesses": "Pros:\n1. The proposed single-pass contrastive loss is interesting and effective for both two kinds of graphs.\n2. The model performance can be guaranteed under a set of assumptions.\n\n\nCons:\n\nCompared with the existing contrastive learning methods, the advantages of single-pass loss are unclear.\nBased on the assumptions mentioned in Section 4.1, the Concentration Property can be guaranteed for both two graphs. Then, what are the challenges to applying contrastive learning methods on the heterophilous graphs? And how the proposed single-pass loss solved this problem? What are the advantages? Besides, \nIn the experiments, it would be better to show the influence of $K_{pos}$ in Section 6.3.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject