Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph
Authors: Haonan Wang
Jieyu Zhang
Qi Zhu
Wei Huang
Kenji Kawaguchi
Xiaokui Xiao
Venue: Accepted by TMLR ()

Abstract: Existing graph contrastive learning (GCL) techniques typically require two forward passes for a single instance to construct the contrastive loss, which is effective for capturing the low-frequency signals of node features. Such a dual-pass design has shown empirical success on homophilic graphs, but its effectiveness on heterophilic graphs, where directly connected nodes typically have different labels, is unknown. In addition, existing GCL approaches fail to provide strong performance guarantees. Coupled with the unpredictability of GCL approaches on heterophilic graphs, their applicability in real-world contexts is limited. Then, a natural question arises: Can we design a GCL method that works for both homophilic and heterophilic graphs with a performance guarantee? To answer this question, we theoretically study the concentration property of features obtained by neighborhood aggregation on homophilic and heterophilic graphs, introduce the single-pass graph contrastive learning loss based on the property, and provide performance guarantees for 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 varying degrees of homophily, the features learned by the SP-GCL can match or outperform existing strong baselines with significantly less computational overhead, which demonstrates the usefulness of our findings in real-world cases.

Jieyu Zhang Published in Transactions on Machine Learning Research (08/2023)
Single-Pass Contrastive Learning Can Work for Both Ho- mophilic and Heterophilic Graph
Haonan Wang
haonan wang nus. nus.ed. edu
National University of Singapore
edu
University of Washington
Qi Zhu
giz3@ilknois.. edu
University of Mlinois Urbona- Chaaa--n
Wei Huang*
wei. Baaeang.rrrrii ur@riken.jp
RIKEN Center for Advanced Intelligence Project
Kenji Kawaguchi National University of Singapore
kenji@nus.edu.sa
Xiaokui Xiao
ækziao Gruss. Tru.s.du..s.. sg
National University of Singapore
Reviewed on OpenReview: https: // openreviee. net/ formm? 244KePn09t
Abstract
Existing graph contrastive learning (GCL) techniques typically require two forward passes for a single instance to construct the contrastive loss, which is effective for capturing the low-frequency signals of node features. Such a dual-pass design has shown empirical success on homophilic graphs, but its effectiveness on heterophilic graphs, where directly connected nodes typically have different labels, is unknown. In addition, existing GCL approaches fail to provide strong performance guarantees. Coupled with the unpredictability of GCL ap- proaches heterophilic graphs, their applicability in real-world contexts is limited. Then, natural question arises: Can design GCL method that works for both homophilic and heterophilic graphs with performance guarantee? To answer this question, we theoreti- cally study the concentration property of features obtained by neighborhood aggregation on homophilic and heterophilic graphs, introduce the single-pass augmentation--iee graph contrastive learning loss based on the property, and provide performance guarantees for 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 varying degrees of homophily, the features learned by the SP-GCL can match or outperform existing strong baselines with significantly less computa- tional overhead, which demonstrates the usefulness of our findings in real-world cases. The code is available at //github. com http//hannnn//SPPP /SPCCL.
1 Introduction
Graph Contrastive Learning (GCL) (Xie et al., 2021), as an approach for learning better representation without the demand of manual annotations, has attracted great attention in recent years. Existing works of GCL could be roughly divided into two categories according whether or not graph augmentation is
*Corresponding Author

---

Published in Transactions on Machine Learning Research (08/2023)
employed. First, the augmentatton--usse GCL (You et al., 2020; Peng et al, 2020; Hassani & Khasahmadi, 2020; Zhu et al., 2021;;b; 2020d;o; Thakoor et al., 2021) follows the initial exploration of contrastive learning in the visual domain (Chen et al., 2020; He et al., 2020) and involves 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 information about the way the inputs are transformed as possible during training, i.e.; to be invariant to set of manually specified transformations. Second, augmentation- free GCL (Lee et al., 2021; Xia al., 2022) follows the recent bootstrapped framework (Grill et al., 2020) and constructs different views through two encoders of different updating strategies and pushes together the representations of the same node/class. For both categories, there has been notable success on homophilic graphs (where directly linked nodes tend to have similar features or same class labels).
However, real-world graphs do not necessarily adhere to the homophily assumption, but may instead exhibit heterophily, in which directly connected nodes have contrasting characteristics and different class labels. In addition, carlier rescarch shows the importance of high-froquency information for heterophilic graphs (Bo et al., 2021), whereas the dual-pass GCL approaches tend to capture low-frequency information, which has been demonstrated in both theoretical analysis and empirical observations (Liu et al., 2022; Wang et al., 2022a). Morcover, the homophily degree is specified by the node labels, which are difficult to obtain in real-world situations; this makes it infeasible to determine if it is appropriate to apply a homophilic- customized GCL algorithm to a given graph. Coupled with the absence of a strong performance guarantee, the applicability of GCL methods in a variety of real-world scenarios is restricted. Therefore, this paper, we ask the following question:
Can one design simple graph contrastive learning method that is effective on both ho- mophilic and helerophilic graphs with performance guaranlee?
We provide an affirmative answer to this question both theoretically and empirically. First, study the neighborhood aggregation mechanism on a property of the aggregated features that is independent of the graph type. By exploiting such a property, we introduce the single-pas augmentation-free graph contrastive loss, and show that its minimizer is equivalent to that of Matrix 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 illustrate and derive the theoretical guarantee for the performance of the learned representations in the down-streaming node classification task.
hhtpeppii///eeeeohhiiiiiii graph and present the concentration
To verify our thcoretical findings, we present direct implementation of our analysis, Single-Pass Graph Contrastive Learning (SP-GCL). Experimental results show that SP-GCL achieves competitive perfor- mance on 8 homophilic graph benchmarks and outperforms state-offthe-art GCL, algorithms on 6 heterophilic graph benchmarks with a substantial margin. Besides, we analyze the computational complexity of SP- GCL and empirically demonstrate significant reduction of computational overhead brought by SP-GCL. Coupling with extensive ablation studies, we demonstrate that the techniques derived from our theoretical analysis are effective for real-world cases. Our contribution could be summarized as:
We demonstrate that the concentration attribute of representations derived by neighborhood feature aggregation is independent of graph type, which in turn drives our novel single-pass graph contrastive learning loss. A direct consequence is a single-pase augmentation-free graph contrastive learning method, SP-GCL, without relying on graph augmentations.
We derive a theoretical guarantee for the node embedding obtained by optimizing the graph contrastive learning loss in the downstream node classification task.
Experimental results show that without complex designs, compared with SOTA GCL methods, SP- GCL achieves competitive or better performance on 8 homophilic graph benchmarks and 6 heterophilic graph benchmarks, with significantly less computational overhead.
2

---

Published in Transactions on Machine Learning Research (08/2023)
2
Related Work
Graph contrastive learning. Existing graph contrastive learning methods can be categorized into augmentation-base based and augmentation-free methods, according to whether or not the graph augmentation tochniques are employed during training. The augmontation--assd methods (You ct al., 2020; Peng ot al., 2020; Hassani & Khasahmadi, 2020; Zhu et al., 2021a;b; 2020d; Thakoor et al., 2021; Zhu et al., 2020c) encourage the target graph encoder to be invariant. to the manually specified graph transformations. There- GCL. We summarized
fore, the design of graph augmentation is critical to the success of augmentation-basse the augmentation methods commonly used by recent works in Table 11 of Appendix D. Other works (Lee et 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 strategies and push together the representations of the same node/class from differ- ent views. In both categories, those existing GCL methods require two graph forward- pass. Specifically, two augmented views of the same graph will be encoded separately by the same or two graph encoders for augmentation- GCLs and the same graph will be encoded with two different graph encoders for augmentation-free GCLs. Besides, the theoretical 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 exlended to graph setting, since the non-Euclidean graph structure is far more complex.
Heterophilic graph. Recently, the heterophily has been recognized as an important issue for graph neural networks, which is outlinod by Pei al. (2020) firstly. To make graph ncural networks able to generalize well on the heterophilic graph, several efforts have been done from both the spatial and spectral perspect (Pei et al., 2020; Abu-El-Haija et al., 2019; Zhu et al., 2020a; Chien et al., 2020; Li et al., 2021; Bo et al., 2021). Firstly, Chien et al. (2020) and Bo et al. (2021) analyze the necessary frequency component for GNNs to achieve good performance on 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 et 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. In addition, from the network embedding view, recent work (Zhong ct al., 2022) proposed method to learn the node embodding for heterophilic graph with self-supervised learning objective.
3 Preliminary
Notation. Let G = (V, E) denote an undirected graph, where V = {riheen and E C V x V 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 R feature matrix denotes as X E Nx where x; Rf is the feature of node v; E V and F is the input feature dimension. We denote the adjacent matrix with self-loop as A {0, 1 where Aúi 1 and Aij = 1 if (v,, 12) E; and the corresponding degree matrix as D diag (d1...., dx), d, = =,, Ar,- Our objective is to unsupervisedly learn a GNN encoder fo X, A- - R receiving the node features and graph structure as input, that produces node representations in low dimensionality, i.e., K < F. The representations can benefit the downstream supervised or semi-supervised tasks, e.g., node classification.
which y/ E (l,....cc c} and e 2 the number of classes. The associated node
Homophilic and heterophilic graph. Various metrics have been proposed to measure the homophily degree of a graph (Zhu et al., 2020b; Pei et al., 2020). In this work, we adopt two representative metrics, namely, node homophily and edge homophily. The edge homophily (Zhu et al., 2020b) is the proportion And the node ho- which evaluates the average
of edges that connect two nodes of the same class: hedge = (ow..,
E
mophily (Pei et al., 2020) is defined as, Amode = N Eneev (e proportion of edge-label consistency of all nodes. They are all in the range of [0, 1] and a value close to 1 corresponds to strong homophily while a value close to 0 indicates strong heterophily. As conventional, we refer the graph with high homophily degree as 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 8 of Scction A.
3

---

Published in Transactions on Machine Learning Research (08/2023)
4 Theoretical Analyses
In this section, we first show the property of node representations obtained through neighbor aggregation (Theorem 1). Then, based on the property, we introduce the single-pase pass graph contrastive loss (Equation (4)), where the contrastive pairs are made using the node representations instead of the augmented graph. With Lemma we bridge the graph contrastive loss and the Matrix Factorization. Then, leveraging the analysis for matrix factorization, we obtain the performance guarantee for the embedding learned by SP-GCL in the downstream node classification task (Theorem 3).
4.1 Analysis of Aggregated Features
To obtain analytic and conceptual insights into the aggregated features, we first describe the graph data we considered. Consider the GNN model:
Z - W) NR
where a represents the nonlinear activation function, and W E RPx is the weight, x; E Rº represents the node features of i-th input node (i.c., the transpose of the i-th row of X). Define Wa E RF to be the k-th column of W. The assumption on the distribution of graph is given as follows:
Assumption 1 Consider a node vi with label yı. Let its node feature x, be sampled from the conditional distribution Pxty- Additionally, assume that the labels of v; 's neighbors are independently sampled according to the neighbor distribution Pg.. We further ossume the eristence of Rt, such that Yo, E V, ||x;||e S R.
Remark. The above assumption means that the label of neighbor is only determined by the label of the central node. This is leasible for both homophily and heterophily. Specifically, within the framework of our stated assumption, if the neighbor distribution Pg. exhibits a bias towards high probability of sampling a label identical to Yi (the label of the central node), then a homophily trend emerges. In such cases, nodes exhibit a higher likelihood of forming connections with other nodes that share the same label, thereby leading to graph characterized by homophily. Conversely, if the probability distribution Py, tends to sample labels that are different from ya, the graph displays tendency towards heterophily. This is because nodes are more likely to form connections with nodes that have different labels, echoing the definition of a heterophilic graph. A representative example of graph generative model adhering Assumption is the contextual stochastic block model (Deshpande et al., 2018; Lu & Sen, 2020). Specifically, in this model, the adjacency matrix A follows a Bernoulli distribution. We have Aij = aij: aij ~ Ber(p) when yı = Yj and Oij ~ Ber(s) when yi = -y. Additionally, the node feature is defined as x = yu + &, where ş E R² and & N~N(0 R...
Assumption has been extensively utilized in various studics, espocially those aiming to thcoretically com- prehend graph neural networks, as exemplified by Huang et al. (2023); Ma et al. (2021); Baranwal et al. (2021; 2023). This demonstrates the comprehensive applicability and relevance of this assumption across diverse applications. Furthermore, we provide our assumption on the activation function:
Assumption Assume that the nonlinear activation function a is homogeneous of degree T for some T 2 and (g) S oq for some ' O.
For example, ReLU activation satisfies Assumption 2 with t = - 1. Also, it covers the result of the lincar model too since if is identity (i.e., linear model), then = c = 1. With above assumptions, we present the following Theorem 1, where we denote the nodes representation obtained through one layer of graph neural network Z, and Z; represents the learned embedding with respect to node us
Theorem (Concentration Property of Aggregated Features) Under Assumptions 1 and 2, for any We FxK, the following statements holds:
For any pair (i, (") E E, such that y; = ye+
BiZ.] E[Z,] 0.
(1)
4

---

Published in Transactions on Machine Learning Research (08/2023)
2. With probability at least 1 5,
2 2l((2/8))
| Z.] Zilloo S ccR
max kE[K]
(2)
D.
3. Por any node pair (i,j), with probability at least 1 8",
K
2 2lm(2/8)) D DJj DD2
E Z,] - Z Zy S c R
(3)
Remark. The above theorem indicates that, for any graph following the graph data assumplion: (i) in expectation, nodes with the same label have the same representation, Equation (1); (ti) the representations of nodes with the same label tend to concentrate onto a certain area in the embedding space, which can be regarded as the inductive bias of the neighborhood aggregation mechanism, Equation (2); (ùti) the inner product of hidden representations approximates to its expectation with a high probability, Equation (3). (Proof is in Appendix C.I.)
Unlike the preliminary concentration study presented in Ma et al. (2021), our work advances the theoretical understanding of aggregated features in the non-linear setting, making it more applicable to the types of Graph Neural Network (GNN) models commonly used in real-world scenarios. We substantiate our theoretical contributions with empirical evidence, specifically validating the derived concentration properly (as stated in Theorem 1) using multi-class, real-world graph data in conjunction with a non-linear multi- layer graph neural network. The outcomes, as discussed Scction 6.4 and summarized Table 5, are accord with our analytical framework. This result is also consistent with findings from other multi-layer graph convolution studies, such as the one by Baranwal et al. (2022). Furthermore, we extend the discourse by offering comprehensive discussion of how the concentration property has been observed empirically in recent works, including those by Wang et al. (2022b) and Trivedi et al. (2022), in Section 7.
4.2 Single-Past Pass Graph Contrastive Loss
In order to learn more compact and linearly separable embedding space, we introduce the single-pass graph contrastive loss based on the property of aggregated features. Taking advantage of the concentration attribute explicitly, we consider nodes with a small distance in the embedding space to be positive pairs, and we characterize randomly chosen nodes as negative pairs by convention (Arora et al., 2019; Chen et al., 2020). Also, theoretical discussion is provided for this intuitive design (Theorem 2). We formally define the positive and negative pairs introduce the loss. For node V; E V, we draw the positive node Ust uniformly from the set St Spoer Ue+ Un The set Spoe is consisted by the Kpos nodes closest. to node Us. Concretely, Spos (u of ......, v2 K = arg m Zz, /l ||2, Kpn),, where Kpms E Z+ and arg max(,, poss) denotes the operator for the top-Kpos selection. Two nodes, (1;, U5+). ), form positive pair. For nodes Uy and uk, sampled independently from the node set V, can be regarded as a negative pair (v,, ux). Following the insight of contrastive learning (Wang & Isola, 2020), similar sample pairs stay close to each other while dissimilar ones are far apart, then the Single-Pass Graph Contrastive Loss defined as,
Zz Zu+] + E Bey--uuiyy (z] z.)
Lar-aci -2 E
v.-Uai * UUi(8
(4)
Compared with conventional Graph Contrastive Learning (GCL) methods (You et al., 2020; Peng et al., 2020; Hassani & Khasahmadi, 2020; Zhu et al., 2021a;b; 2020d;e; Thakoor et al., 2021), which heavily relied on graph augmentations for defining their contrastive losses (The various augmentation techniques employed by these hots are exhaustively detailed in the Table 11 of Appendix), our proposed approach circunvents the need for explicit augmentation techniques, a deviation that simplifies the contrastive learning process and potentially reduces the computational overhead. In addition, our approach stands distinct from other augmentation-free methods such as those proposed by Lee et al. (2021); Xia et al. (2022). These methods construct negative pairs through dual forward pass, leveraging a slower-moving average create different
5

---

Published in Transactions on Machine Learning Research (08/2023)
views. While this strategy certainly has its merits, it can introduce additional complexity, e.g. two forward pass, to the learning process.
The proposed SP-GCL is single-pass and augmentation-free. In contrast, it manages to avoid both the need for explicit augmentation techniques and the tual-forward-pass strategy. This unique approach does not rely on multiple views or passes to construct negative pairs, thereby streamlining the contrastive learning process. Our findings suggest that this approach is only feasible but also effective across both homophilic and heterophilic graphs.
4.3 Performance Guarantee for Learning Linear Classifier
For the convenience of analysis, we first introduce the concept of transformed graph as follows, which is constructed based on the original graph and the selected positive pairs. Note, the transformed graph is concept only used to illustrate the theoretical derivation, instead of the actual computation.
Definition 1 (Transformed Graph) Given the original gruph G and node set V, the transformed graph, G. has the same node set V but with the selected positive pairs as the edge set, E = U,((e, u Kpon }.
Remark. The transformed graph is formed by positive pairs selected based on aggregated features. Coupling with the Concentration Property of Aggregated Features (Theorem 1), the transformed graph tends to have larger homophily degree than the original graph. We provide more empirical verifications in Section 6.4.
Positive pairs
Transformed graph
Figure Transformed Graph formed with Positive Pairs.
The transformed graph is illustrated in Figure 1. We denote the adjacency matrix of transformed graph as A E {0, 1N the number edges as É, and the symmetric normalized matrix transformed graph as Asgm = D AD 11/2, where D = diag (di....,d,, ,d), d, = -E,,, A.g. Correspondingly, we denote the symmetric normalized Laplacian as Leym = À sym = UAUT. Here U E RNNN = [u,,..., unl, where u, RV denotes the i-th eigenvector of Lyym and A diag (AI,....AN)) is the corresponding eigenvalue matrix. A and dy be the smallest and largest eigenvalue respectively.
Then we show that optimizing a model with the contrastive loss (Equation (4)) is equivalent to the matrix factorization over the transformed graph, as stated in the following Lemma:
Lemma Denote the learnable embedding for matria factorization as F RNKK Let F; =; Fw))).. Then, the matria factorization loss function Lmt is equivalent to the contrastive loss, Equation (4), up an additive constant:
Lma (F)) = A - FF 1| Lsnveea + const
The above lemma bridges the graph contrastive learning and the graph matrix factorization and therefore allows us to provide the performance guarantec of SP-GCL by leveraging the power of matrix factorization.
We leave the derivation in Appendix C.2. With the Theorem and Lemina 1, we arrive at a conclusion about the expected value of the inner product of embeddings (More details in Appendix C.3):
Thcorem For a graph following the graph data assumption (Assumptions 1), then when the optimal of the contrastive loss is achieved, i.e., Lm (F*) O, we have,
E Z 19 1,,,,,
E Z bevtus 2
(6)
where δ- Uneey) (Ais 1 [1 + )ıl)-

---

Published in Transactions on Machine Learning Research (08/2023)
GNN fo
H
MLP Iw
Z
Figure 2: Overview of SP-GCL. The graph data is encoded by a graph neural network Jo and following projection head Iw. The contrastive pairs are constructed based on the representation Z.
I means the probability of an edge connecting two nodes from the same class, which can be regarded as the edge homophily of the transformed graph. Its value is always greater than The theorem implies that pair of nodes coming from the same class likely have larger inner product similarity than pair of nodes coming from different classes.
Remark. The 1-
Finally, with the Theorem 1 and Theorem 2, 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):
Theorem Let Z be minimizer of the contrastive loss, LSP-CCL. Then there erists linear classifier B' E Bex with norm |B"ll S x1-x) such thal, with probability at least 1 - 8',
| - B² 2-11"]] -
+ o² & Caegree AK+1
2ln(2/8') X2
|w 1
where Yi is the one-hot embedding of the label of node vi, Cdegree = Ev Uni(V) [(Daa) O deter- mined by node degree of the input graph and invoriant to the learning process. The positive real constant R and e defiend in Assumption and 2 respectively- Z' is obtained through the non-linear graph neural network, and the nonlinearity follows the assumption 2. ) are the i smallest eigenvalues of the symemetricaly normalized Laplacian matria of the transformed graph.
Remark. Our theorem elucidates a noteworthy correlation between a graph's average degree and its as- sociated classification error. Specifically, the thcorem posits that graphs with higher average degrees yicld reduced Cdegree: consequently enhancing node classification accuracy. This assertion is substantiated by empirical data presented in Tables 1 and 2. Although the relationship between the classification accuracy of SP-GCL and the average degree of the graphs (as detailed in Table 8) does not follow a strictly lin- car pattern, a discernible trend is evident. In particular, datasets with elevated average degrees- such as Amazon Computer, Photo, Coauthor CS, and the Physics sification performance. Moreover, the theorem suggests that smaller value of ΣX ||w 112 leads to better classification accuracy. This prediction prompted the inclusion of batch normalization in the SP-GCL im- plementation, providing more effective control over the magnitude of the weight vectors and hence improving our node classification procedure. The study of batch normalization's 's effect in Section 6.3 aligns with the theorem's prediction.
demonstrate superior clas-
5 Single-Pass Augmentation-Free Graph Contrastive Learning (SP-GCL)
As a direct consequence of our theory, we introduce the Single-Pass Augmentation-FFee Graph Contrastive Learning (SP-GCT.). Instead of relying on the graph augmentation function or the exponential moving average, our novel learning framework only forwards a single time and constructs contrastive pairs basod on the aggregated features. As shall see, this extremely simple, theoretically grounded strategy also achieves superior performance in practice than dual-pass graph contrastive learning methods on homophilic and heterophilic graph benchmarks.
According to the results of the analysis, for each class, the embedding generated through neighbor aggregation will converge on the expected class embedding. We build the self-supervision signal based on the discovered embedding and offer a novel singlo-pass graph contrastive learning framework without augmentation, SP- GCL, that picks similar nodes positive node pairings. As shown in Figure 2, in each iteration, the proposed framework firstly encodes the graph with graph encoder fo denoted by H [o(X Then,
7

---

Published in Transactions on Machine Learning Research (08/2023)
projection head with L2- u.2-oomalization, 9ur is employed to project the node embedding into the hidden representation Z = ( To scale up SP-GCT, on large graphs, the node pool, P, are constructed by the T-hop neighborhood of b nodes (the seed node set S) uniformly sampled from V. For each seed node U; S, the top-Kpos nodes with highest similarity from the node pool are selected as positive set for it which
Know] V, Sneg C V. denote as Spo== arg , (z. Z,/ // [22llZzlle 22l Kpos), and Sheg {o/ uz 1......
Concretely, the framework is optimized with the following objective:
Expoce
Σ vEV U. ESpox
Σ
Z Zet
Σ V,EV Sne
Σ
(Z]]z)²)
Kpox pos
Knng
(8)
With or PI N, the empirical contrastive loss is an unbiased estimation of the Equation (4). With T > 1 and [P] N, the sampling will bias towards nodes with large degree. Overall, the training algorithm SP-GCL is summarized in Algorithm 1.
Algorithm Single-Pass Augmentation-FFre Graph Contrastive Learning (SP-GCL).
Input: Graph neural network for MLP projection head Iw, input adjaceney matrix A, node features X, batch size b, number of hops T, number of positive nodes K Kpos.
for epoch 1, 2, do
1. Obtain the node embedding, = foX, A).
2. Obtain the hidden representation, Z Iw (H).
3. Sample b nodes as seed node set. S and construct the node pool P with the T-hop neighbors of each node in the set S.
Select top-Kpus similar nodes for every U/ E form the positive node set Spos- Compute the contrastive objective with Eq. (8) and update parameters by applying stochastic gradient.
end for return Final model fe.
Although our theoretical analysis indicates that SP-GCL can ensure performance for both homophilic and heterophilic graphs, it is yet unknown whether the proposed strategy is effective in real-world situations. In the subsequent part, empirically validate the effectiveness of the method and the applicability of our conclusions across a wide variety of graph datasets.
6 Experiments
We conduct experiments to evaluate the SP-GCL by answering the following questions:
How does the SP-GCL perform compared with other GCL methods on homophilic and heterophilic graphs?
RQ1:
RQ2:
What's the empirical memory consumption of SP-GCL compared with prior works?
RQ3: Whether the learning procedure is stable? And whether node representation have expected behavior during training?
RQ4: How do the specific hyper- parameeessss of SP-GCL, such the selection of top-K K and sampling hop-T, affect its performance?
To answer these questions, we apply supervised approaches, augmentation--ased and angmentation-ffre GCL methods (a Lotal of 14 baseline methods) in accordance with the linear evaluation scheme described in Velickovic et al. (2019). In addition, we utilize 14 benchmarking graph data to assess SP-GCL on diverse datascts with varying scales and features. We present the selected datascts, baselines, evaluation protocol and implementation details in the Appendix A.1, A.2, A.3, and A.4 respectively. In addition, Appendix A contains most details about infrastructures and hyperparameter configurations.
8

---

Published in Transactions on Machine Learning Research (08/2023)
6.1 Performance 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 in Appendix A. The result is summarized in Table 1, in which the best performance achieved by self-supervised methods is marked in boldface. Compared with augmentation- basod and augmentation-froe GCL methods, SP-GCL outperforms previous methods on datascts and achieves competitive performance on the others, which shows the effectiveness of the single-pass contrastive loss homophilic graphs. We further assess the model performance on heterophilic graph benchmarks that employed in Pei et al. (2020) and Lim et al. (2021a). As shown in Table 2, SP-GCL 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 with different homophily degree. Additionally, we assess the combination of SP-GCL with three other popular GNNs, namely GAT (Veličković et al., 2017), GIN (Xu et al., 2018), and GraphSAGE (Hamilton et al., 2017). The findings, presented in Table 10 of Appendix B.1, affirm the feasibility of our proposed training approach across diverse graph neural network architectures. For an in-depth discussion this matter, we direct the readers to Appendix B.1.
Table 1: Graph Contrastive Learning on Homophilic Graphs. The highest performance of unsupervised models is highlighted in boldface. OOM indicates Of-moryyyyrry on a 32GB GPU.
MODEL
CORA
CITESBER
PUBMED
WIKISS
AMZ- CMMP.
AMZ- PHOTO
COAUTROR-CS CS
COAUTHOR PHY.
AvG.
MLP
49.31
0.20
69.14
71.98
73.81 0.21
71.83
GCN
51.54 + 0.68
70.73
0.65
79.16 + 0.25
78.02 1 0.11
86.51 = 0.54
92.42 : 0.22
93.03 = 0.31
95.65 = 0.16
81.63
DEEPWALK
70.72 4
51.39
73.27
85.68 0.07
77.65
NODg2CEC
71.08
+ 0.91
0.84 47.31
66.23
+ 0.95
71.76 : 0.14
81.41 = 0.14
89.68 : 0.19
85.16 = 0.01
91.23 = 0.07
75.86
SELENK
00M
0.81
OOM
00M
00M
GAE
71:49 4 0.41
65.83
0:40
72.23 + 0.71
73.97
2 0.16
85.27 = 0.19
91.62 1 0.13
96.01 = 0.71
91.92 = 0.08
80.66
VGAB
67.41
0.62
86.40
0:22
82.66
DGI
82.34 + 0.71
71.83
0.54
76.78
+ 0.31
75.37
0.13
84.01
+ 0.52
91.62 + 0.42
92.16 = 0.62
94.52 + 0.47
83.58
GMI
62.39 1: 0.65
71.72
0.15
79.341
1.04
74.87
0.13
82.18
0.27
90.68 1 0.18
0OM
0OM
MVGRL
83.45 + 0.68
7S.28
0.48
80.09
: 0.62
77.51
0.06
57.53 + 0.12
91.74 1 0.08
92.11 = 0.14
95.33 2 0.05
85.13
GRACE
81,92 + 0.89
71.21
0.64
80.54
+ 0.38
78.19
0.10
85.35
0.44
92.15 + 0.25
92.91 0:20
95.26 (6 0.22
84.82
GCA
82.07 + 0.10
71.33
0.37
80.21
+ 0.39
78.40
0.13
0.31
92.49 +
92.87
+ 95.68
85.11
BGRL
$1.44 +: 0.72
71.22
0.48
80.18
- 0.63
76.96
0.61
89.62 4 0.37
93.07
4 0.34
92.67
0.21
95.47 = 0.28
85.15
AFGRL
71.02
0.37
0.48
0.40
0.36
93.27
0.17
95.69
85.29
SP-GCL
53.16 4 0.13
71.96
0.42
79.16 + 0.73
79.01
0.51
89.68
0.19
92.49 + 0.31
91.92 0.10
95.12 0.15
85.31
Table 2: Graph Contrastive Learning on Heterophilic Graphs. The highest performance of unsupervised models is highlighted in boldface. OOM indicates Out-Of-Memory on a 32GB GPU.
MODEL
CHAMELEON
SQUIRREL
ACTOR
TwITCH-DE
TWITCH-GAMERS
GENIUS
AvG.
MLP
47.59 + 0.73
31.67 = 0.61
35.93 = 0.61
69.44 + 0.67
60.71 +-t 0.18
86.62 + 0.11
55.32
GCN
66.45 4 0.48
53.03 + 0.57
28.79
0.23
73.43 i 0.71
62.74 t 0.03
87.72 1 0.18
62.02
DEEPWALK
43.99
0.67
30.90 = 1.09
25.50
0.28
70.39 = 0.77
61.71 0.41
68.98 0.15
50.24
NODE2CEC
31.49
1.17
27.64 + 1.36
27.04
0.56
70.70
1.15
61.12 0.29 OOM
67.96 0.17 00M
47.65
SELENE
61.37
0.67
44.84 = 2.01
27.59 = 0.59
71.67 = 1.87
GAE
39.13 1 1.34
34.65 1 0.81
25.36 0.23
67.43 1 1.16
56.26 1 0.50
83.36 1 0.21
51.03
VGAE
42.65 + 1.27
35.11 = 0.92
28.43 0.57
68.62 - 1.82
60.70 + 0.61
85.17 + 0.32
53.44
DGI
60.27 0.70
42.22 =
28.30 0.76
72.77 - 1.30
61.47 0.56
86.96 0.44
58.66
CMI
52.81 0.63
35.25 + 1.21
27.28 0.87
71.21 1 1.27
OOM
OOM
MVGRL
53.81 1.09
38.75 + 1.32
28.64 0.78
71.86 + 1.21
OOM
OOM
GRACE
61.24 + 0.53
41.09 + 0.85
28.27 0.43
72.49 + 0.72
OOM
OOM
GCA
60.94 + 0.81
41.53 - 1.09
28.89 0.50
73.21 - 0.83
OOM
00M
BGRL
64.86 0.63
46.24 = 0.70
28.80 0.54
73.31
1.11
60.93 0.32
86.78 0.71
60.15
AFGRL
59.03 0.78
42.36 - 0.40
27.43 1.31
69.11
0.72
OOM
OOM
SP-GCL
65.28 + 0.53
52.10 + 0.67
28.94 + 0.69
73.51 + 0.97
62.04 + 0.17
90.06 + 0.18
61.98
9

---

Published in Transactions on Machine Learning Research (08/2023)
Table 3: Computational requirements on a set of standard benchmark graphs. O0M indicates running out of memory on a 32GB GPU.
DATASET
CS.
PHY.
GENIUS
GAMERS.
# NODES
18.333
34,493
421,961
168,114
# EDGES
327,576
991,848
984,979
6,797,551 557
GRACE
13.21 GB
30.11 GB
OOM
OOM
BGRL
3.10 GB
5.42 GB
8,18 GB
26.22 GB
SP-GCL
2.07 GB
3.21 GB
6.24 GB
22.15 GB
Table 4: True positive ratio of selected edges at the end of training. The minimal, maximal, average, standard deviation of 20 runs are presented.
Table 5: Edge homophily of the transformed graph at the initial stage. Homophily value of original graphs is shown in parentheses.
Dataset
Audge of 0
Dataset
Min
Max
Avg
Std.
Cora
0.812- + 0.0022 (0.810)
Cora
0.817
0.836
0.826
0.0061
CiteSeer
0.6914 + 0.0018 (0.736)
CiteSeer
0.708
0.719
0.713
0.0033
PubMed
0.819t = 0.0011 (0.802)
PubMed
0.820
0,832
0.825
0.0037
Coauthor CS
0.8831 + 0,0018 (U.808)
Coauthor CS
0.892
0.905
0.901
0,0025
Coauthor Phy.
0.9521 + 0.0021 (0.931)
Coauthor Phy.
0.952
0.963
0.959
0.0028
Amazon Comp-
0.8661 + 0.0019 (0.777)
Amazon Comp.
0.871
0,896
0.878
0.0076
Amazzon Photo
0,908t + 0.0012 (0.827)
Amazon Photo
0.903
0.926
0.916
0,0054
WIkICS
0.7511 + 0.0027 (0.654)
WikiCS
0.757
0.771
0.761
0.00+1
Chameleon
0.6311 + 0.0047 (0.234)
Chameleon
0.703
0.785
0.711
0.0183
Squirrel
0.5261 + 0.0042 (0.223)
Squirrel
0.529
0.541
0.530
0.0024
Actor
0.3781 i 0.0026 (0.216)
Actur
0.388
0.399
0.396
0.0016
Twisch-DE
0.6691 + 0.0033 (0.632)
Twitch-DE
0.693
0.726
0.703
0.0073
Twitch-gamers
0.6171 + 0.0021 (0.545)
Twitch-gamers
0.620
0.633
0.627
0.0022
Genius
0.7851 1 0.0028 (0.618)
Genius
0.786
0.797
0.790
0.0029
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-officient contrastive method, BGRL (Thakoor ct al., 2021). Consider a graph with N nodes and E edges, and a graph neural network (GNN), J, that compute node embeddings O(N + F.). 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 angmentation), plus 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 as a forward pass. Both of them will compute 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 [E + N) + PCpro + Cprod + Caug and 4Cencoder (F + N) + 4Cpros + C2rod + Caug for GCA. The Cpred 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 Kpoe and Kneg inner product for the loss computation. Then for SP-GCL, we have; 2Cencoder N) + 2Cproj.V N + C (proo((Kpm + Kneg)? which is significantly lower than BGRL and GCA. Wo 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 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.
time and space
6.3 Effective Way to Keep the Summation of the 12- of Weight Vectors (EK1, || (1))
be Small
Theorem postulates that a decrease the sum of the 12-norm of the weight matrix vectors for GNN layer will result in a lower upper bound for classification error. Two commonly employed techniques to minimize the sum of the vector norm are batch normalization and I.2-regularization. We carry out thorough
10

---

Published in Transactions on Machine Learning Research (08/2023)
analysis of the impacts of these two techniques on both the performance and the summation of vector norms, represented by Ek=1 //wlll2- The findings of our investigation are consolidated in Table 6 and 7. The results compellingly illustrate that batch normalization proves to be more effective in maintaining a relatively lower Ei= [ and concurrently improving performance. This comprchensive study underscores the critical role batch normalization plays SP-GCT, thereby enhancing our understanding of SP-GCLs operational nuances and guiding implementation efforts.
Table The effect of BatchNorm within SP-GCL on the summation of 12-norm of weight matrix E ([wxel2) and performance. Comparing the network with same number of layers but w/wo batch nor- malization, the larger values of the summation of (2-norm of weight matrix are marked as red. And, the higher values of performance are marked are green.
Chameleon
Squirrel
Photo
WikICS
12-norm sum.
Acc.
12-norm sum.
Acc.
12-porm sum.
Aec.
12-norm sum.
Acc.
layer w/
672.23
61.40
000.84
49.63
[574.07]
93.29
[44.445
77.49
layer w/o BN
686.11]
11. 49
676.799
33.87
[609.15
26.68
[41.51
21.68
layer 2 w/ BN
665.04,
613.83
63.33
0688996,366.00
51.91
14.600.
94.08
442.24,511.64
78.36
layer w/o BN
687.44.529.60
32.91
1681.29,528,
34.93
594.422528.cr 89]
25.32
437.05,526.33
21.69
layer 3 w/ BN
6633.66553.5005111533
61.60
167.24.315.71.5188
51.40
286.51,519.24,522
93.57
141.722,16.12..5
12,515.25
78.27
layer 3 w/o BN
084450,525.44.551..
34.74
(681.77,529.395520
36.26
(583.74,534.645522
25.29
[430.40,529, (26.5.26666660..0.0
25.37
Table 7: The elfect 12 regularization on the summation of 12-norm of weight matrix ( Ek=1 [|wx113) and performance.
Regularization Strength
le-05
1e-04
1e-03
Te-02
1c-01
Acc.
41.49
41.45
41.40
41.43
41.51
Chameleon
12 Norm.
673.21
673.2
673.11
672.39
665.27
Squirrel
Acc.
27.87
27.89
27.88
27.88
27.83
12 Norm.
661.86
661.85
661.8
661.29
656.23
Acc.
26.32
26.56
26.78
26.86
25.87
Photo
12 Norm.
579.12
579.99
579.77
576.99
557.59
Acc.
24.68
24.68
24.66
24.67
24.55
WikiCS
12 norm.
448.28
448.44
448.36
447.62
439.54
6.4 Empirical Verification for the Theoretical Analysis
Homophily of transformed graph (Initial Stage). The homophily of transformed graph largely depends on the hidden representations. We theoretically shows the concentration property of the representations (Theorem 1) with mild assumptions. It implies that the transformed graph formed by selected positive pairs will have large edge homophily degree. But it is still unclear whether the derived conclusion is still hold over real-world datasets. Thus, 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 Table 5. The edge homophily of all transformed graphs are larger than the original one with small standard deviation, except the CiteSeer in which relatively high edge homophily (0.691) can still be achieved. The result indicates that the Theorem 1 is feasible over wide-range real-world graph data.
Distance to class center and Node Coverage (Learning Process). We measure change of the average cosine distance (1- --CooineSimilarity) between the node embeddings and the 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 discussed above, the SP-GCL iteratively leverage the inductive bias to refine the embedding space. Furthermore, to study whether the representation ion of all 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 Kpas positive selection at epoch t as et and define the Overlapped Selection Ratio sttime" |.|
embeddings during
Besides, we denote the set of
11

---

Published in Transactions on Machine Learning Research (08/2023)
positive nodes at epoch as v'. Then the Node Cover Ratio at epoch is defined as: |='nv".."" the hyperparameters described previously, we measure the node cover ratio and overlapped selection ratio during training. As shown in Figure 4, the overlapped selection ratio is low during the training and the node cover ratio coverage to 1 at the beginning of training. The result implies that all nodes can be benefited from the optimization procedure.
N Following
Infchhe
Champlegn
Average Cosine Distance Curve
0.63
Squirel
0.55
Orea
Node Coue Ralp
Overapoec fats
Chameloon
0.50
Actor
0.5
Epcch
Epoch
0.40
0.35
044
0.30
Overlecoed Seactes fatt
Training
02
Heir Crue dote
Overapowe fats
Figure 3: Average cosine distance be- tween node embeddings and their cor- responding class centers.
Spoch
Figure 4: The Node Cover Ratio and Over- lapped Selection Ratio.
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 4, the relatively large TPR and low variance suggests that the quality of the selected positive pairs is good and the learning process is stable.
6.5 Ablation Study for Hyper-parameter Selection
Effect of Top-K Positive Sampling. We study the effect top- positive sampling on the node classification performance by measuring the classification accuracy and the corresponding standard deviation with a 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 to the selection of K from 2 to 18.
Effect of T-hop Neighbors. Factor T is the other factor involved in node sampling. We provide study about the the effect of 7-hop 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 5, the performance achieved by SP-GCL is insensitive to the selection of T.
23
sparis
23
Curekee
12
bgp
10tp Nagrostiod
Figure The effect of top-K K positive sampling and T-hop neighborhood on the performance.
12

---

Published in Transactions on Machine Learning Research (08/2023)
7 Connection with Existing Observations
In Theorem 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 Figure 1 of Wang et al. (2022b), t-SNE visualization of node representations of the Amazon- dataset shows that the representations obtained by a randomly initialized untrained SGC (Wu et al., 2019) model will concentrate to certain area if they are from the same class. This observation also provides an explanation for the salient performance achieved by SP-GCL on the Amazon-Pholo, as shown in Table 1.
8 Conclusion
In this work, to build a practical GCL approach that can perform well on both homophilic and heterophilic graphs, begin by analyzing the concentration property of aggregated features for homophilic and het- erophilic graphs. We then introduce the single-pass graph contrastive loss by utilizing the concentration property. We establish a link between the contrastive objective and the matrix factorization. Then, by utilizing the analysis of matrix factorization, we establish a theoretical guarantee for the downstream classi- fication task using node reprosentations learnt by optimizing the contrastive loss. We implement Single-Pass Graph Contrastive Learning (SP-GCL). Empirically, we demonstrate that SP-GCL outperforms or is com- petitive with SOTA approaches on 8 homophilic and 6 heterophilic graph benchmarks, while incurring a much lower computational overhcad. The empirical findings demonstrate the viability and efficacy of our method in real-world situations.
9 Limitation and Future Work
Our work is only the first step in understanding the possibility of single-pass graph contrastive learning and the corresponding performance guarantee on both the homophilic graph and heterophilic graph. There is still a lot of future work to be done. Below we indicate three questions that need to be addressod.
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. It is still an open question to understand the graph contrastive learning on those graphs.
Recently, several Graph neural networks (Zhu al., 2020b; Chien al., 2020; Luan al., 2021; Li 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 icel findings, we keep the implementation to be simple. Whether a better empirical result can be achieved by involving more complex techniques still need to be explored.
References
Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyun-
yan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21-29. PMLR, 2019.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. A the- oretical analysis of contrastive unsupervised representation learning. arXiv preprint X9w:1992.00229, 2019.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-disttibution generalization. arXiv preprint arXiv:2102.06966, 2021.
Ascem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. arXiv preprint ar urXi:2204.009900 2022.
Ascem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. Tn The Fleventh International Conference on Learning Representations, 2023.
13

---

Published in Transactions on Machine Learning Research (08/2023)
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolu- tional networks. arXie preprint or "Xxx:2101.00700 2021.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and GeofTrey Hinton. simple framework for rastivvv learning of visual representations. In International conference on machine learning, pp. PMLR, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. Xiv preprint arXiw:2006.0799 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. Advonces in Neural Information Processing Systems, 31, 2018.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1 (3):211-218, 1936.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometrie. arXiv preprint Xii::1903.02428 2019.
Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Beruardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach self-supervised learning. Advances in Neural Information Processing Systems, 33:21271-21284, 2020.
Aditya Grover and Jure Leskovec. node2voc: 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 large graphs arviv preprint XrXi::1706 02216, 2017.
Jelf Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guaranlees for self-supervised deep learning with spectral contrastive loss. arXiv preprint arXiv:2106. 0ann21066041180 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, Haoqi Fan, Yuxin Wu, Saining Xie, 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.
Wei Huang, Yuan Cao, Haonan Wang. Xin Cao, and Taiji Suzuki. Graph neural networks provably benefit from structural information: feature learning perspective. arXiv preprint arXiv:2306.19926 2023.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint Xrxio:1600 1699. 02907, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint
2016b.
Jason D Lee, Qi Tei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable self-supervised learning. arXiv preprint arXiv:2008. 01066, 2020.
Namkyeong Lee, Junseok Lee, and Chanyoung Park. Augmentation-free self-supervised learning on graphs.
arXiv preprint arXim:2112.02472 72, 2021.
Shouheng Li, Dongwoo Kim, and Qing Wang. Beyond low-pass filters: Adaptive feature propagation on graphs. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 450-465. Springer, 2021.
14

---

Published in Transactions on Machine Learning Research (08/2023)
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 orXin:2205.00 073000 2022.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalcrao, 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, Xiuyn Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. Xiviv preprint arXiv:2104.01 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: peattps://oppee htt.hhtts://ppereiiieeee wwt.//rrrttfrrt id=LOU7TUWRt X.
Chen Lu and Subhabrata Sen. Contextual stochastic block model: Sharp thresholds and contiguity. arXiv preprinl Xiv:2001 1..90011.998.. 1.0944,, 2020.
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao Wen Chang, and Doina Precup. Is heterophily real nightmare for graph neural networks to do node classification? arXi preprint Xiv:22119. 05641, 2021.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? arXiv preprint xrxim:2106.0000 061061 2021.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprinl arXie:2002 0087700000008 2020.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pp. 259 270, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701 710, 2014.
Jiczhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1150-1160, 2020.
Benedek Rozemberezki and Rik Sarkar. Twitch gamers: a dataset for evaluating proximity preserving and structural rolo-basod node embeddings. arXiv preprint arX1v:200.00001,, 2021.
Benodek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 922)ccaab114, 2021.
Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Piufalls of graph neural network evaluation. arXio preprint arXiv:1811.05888 2018.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Rémi Munos, Petar Veličković, and Michal Valko. Bootstrapped representation learning on graphs. arXiv preprint arXiv:2102.06514 2021.
Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pp. 1206. PMT.R, 2021.
15

---

Published in Transactions on Machine Learning Research (08/2023)
Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan, Yaoqing Yang, and Danai Koutra. Augmentations in graph contrastive learning: Current methodological flaws & towards better practices. In Proceedings of the A ACM Web Conference 2022, pp. 1538 1549, 2022.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXi:1710010000: 2017.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Lio, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR (Poster), 233):4, 2019.
Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang, Augmentation-free graph contrastive learning, arXiv preprinl ar 2Tf::2244.48777 2022a.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformily on the hypersphere. In International Conference on Machine Learning, pp. 9929-999999999 192999999. PMI.R, 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.0000 00900, 2022b.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying 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 Conference 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 arXi::2102.109 10757, 2021.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint ar Xio:1 0.00026, 2018.
Yuming You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-558 2020.
Zhiqiang Zhong, Guadalupe Gonzalez, Daniele Grattarola, and Jun Pang. Unsupervised network embedding beyond homophily. Transactions on Machine Learning Research (TMLR), 2022.
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. 110000066.1144.. 11468, 2020b.
Qi Zhu, Yidan Xu, Haonan Wang, Chao Zhang, Jiawei Han, and Carl Yang. Transfer learning of graph neural networks with ego-graph information maximization. arXie preprint arXiv:2009 20X0:22009.0524,, 2020c.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive represen- tation learning. arXie preprint orxiv:2006. 04131, 2020d.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. 202
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Läu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pp. 2069 2080, 2021b.
16

---

Published in Transactions on Machine Learning Research (08/2023)
A Appendix: Experiment Setting
A.1 Dataset Information
We analyze the quality of reprosentations learned by SP-GCL on transductive node classification bench- marks. 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- Computers, Amazon-Photo, Coauthor- CS, Coauthor-Physicce (Shchur et al., 2018), as well as heterophilic graph datasets, namely, Chameleon, Squirrel (Rozemberczki et al., 2021), Actor (Pei et al., 2020), Twitch-DE DE, Twitch-gamers (Rozemberezki & Sarkar, 2021), and Genius (Tim et al., 2021b). The datasets from real-world networks from different domains; their detailed statistics summarized in Table 8. 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, 3 of them, e.g., Chameleon, Squirrel and Actor are pro- vided by PyTorch Gcometric library. The other three dataset, genius, twitch-DE and twitch-gamers can be obtained from the official github repository', in which the standard splits for all the 6 heterophilic graph datasets can also be obtained. Those graph datasets follow the MIT license, and the personal identifiers are not included. We do not foresce any form of privacy issues.
collected
Table Statistios of datasets used in experiments.
Name
Nodes
Edges
Class.
Feat.
hnnds
Avg.
Degree
Cora
2,708
6,429
1,433
.825
810
4.01
CiteSeer
4,732
PubMed
19.717
44,338
3
500
.792
8022
4.50
Coauthor
18,333
327,576
15
6,805
Coauthor Phy.
34,493
991,848
8,451
.915
.931
57.51
Amazon Comp.
13.752
574.418
10
767
.785
.777
83.54
Amazon Photo
7,650
287,326
745
.836
.827
72.
WikiCS
11,701
216,123
10
300
.658
.651
36,91
Chameleon
2,277
36,
2,325
31.71
Squirrel
5,201
216,933
5
2,089
.088
.23
83.45
Actor
7,600
33,544
9,31
.154
.216
8.83
Twitch-DE
9,498
133,138
2,514
.529
.632
32.25
Twitch-gamers
168,114
6,797,557
2
7
.552
.545
80.86
Genius
421,961
984,979
A.2 Baselines
We consider reprosentative baseline mothods belonging to the following three categorics (1) Traditional unsupervised graph embedding methods, including DeepWalk (Perozzi et al., 2014), Node2Vec (Grover & Leskovec, 2016) and SELENE (Zhong et al., 2022), which fuses node attributes and network structure information without additional supervision. It employs self-supervised learning loss on structural repre- sentations, and reconstruction loss node features (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-View 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 et al., 2021), (3) Supervised learn- ing and Semi-supervised learning, e.g., Multilayer Perceptron (MLP) and Graph Convolutional Networks (GCN) (Kipf & Welling, 2016a), where they are trained in an end-to-end fashion.
A.3 Evaluation Protocol
We follow the evaluation protocol of previous statc-of-tho-art graph contrastive learning approaches. Specif- ically, for every experiment, we employ the linear evaluation scheme as introduced in Velickovic et al. (2019), where each model firstly trained in an unsupervised manner; then, the pretrained representations are used to train and test via simple linear classifier. For the datasets that came with standard train trainvvalid, //a/avall/eeeeee /tsst splits,
hhttps://gtthul wwctshhub..om///// /UUT/ Hamophi
Cageee///eetttoaaaaaaaaaaaaaaaaa Large--eScalle
17

---

Published in Transactions on Machine Learning Research (08/2023)
evaluate the models the public splits. For datasets without standard split, e.g., Amazon-Compiin Amazon-Photo, Coauthor-CS, Coauthor-Physies, randomly split the datasets, where 10% 006611%/800 880% of nodes are selected for the training, validation, and test set, respectively. For most datasets, we report the averaged test accuracy and standard deviation over 10 runs of classification. While, following the previous works (Lim et al., 2021b;a), we report the Lest. ROC AUC on genius and Twitch-DE datasets.
A.4 Implementation Details
Model architecture and hyperparamters. We employ a two-layer GCN (Kipf & Welling, 2016a) as the encoder for all methods. The propagation for single layer GCN is given by,
GCN, = (D (D- AD AD AD-AX..)) AxW.).
where Å = i the adjacency matrix with self-loops, is the degree matrix, is a non-linear activation function, such as ReLU, and W, the learnable weight matrix for the 7'th layer. Besides, following the previous works (Lim et al., 2021a;b), we use batch normalization without learnable affine parameters (to keep the implementation close to the thcorctical analysis) within the graph encoder for the heterophilic graphs. The hyperparameters configuration for all experiments are summarized in Appendix A.
Linear evaluation of embeddings. In the linear evaluation protocol, the final evaluation is over repre- sentations obtained from pretrained model. When fitting the linear classifier top of the frozen Iearned 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), PyTorrh 1.9.0 (Paszke al., 2017). We conduct experiments on a com- puter with four NVIDIA Tesla, V100 SXM2 GPUs (with 32GB memory each) and twelve Intel Xeon Gold 6240R 2.40GHzz CPUs.
Table 9: Hyperparameter settings for all experiments.
lr.
K pos
Kneg
b
T
K
Cora
.0010
100
512
1024
CiteSeer
.0020
10
200
256
1024
PubMed
.0010
100
256
1024
WikiCS
.0010
100
512
1024
Amz-Comp.
.0010
100
256
1024
Amz-Photo
.0010
100
512
1024
Coauthor-CS
.0010
100
512
1024
Coauthor-Phy:
.0010
100
256
1024
Chameleon
.0010
100
512
1024
Squirrel
.0010
100
512
1024
Actor
.0010
10
100
512
4
1024
Twitch-DE
.0010
100
1024
Twitch-gamers
.0010
5
100
256
4
128
Genius
.0010
100
256
512
B More Experimental Results
B.1 Single-Par Pass Augmentation- Free Graph Contrastive Learning with Different Types of Graph Encoders
In the previous section, we demonstrated the efficacy the single-pass augmentation-frre approach in Graph Contrastive Learning (GCL. using the Graph Convolutional Network (GCN) encoder (Kipf & Welling,
18

---

Published in Transactions on Machine Learning Research (08/2023)
2016a). In the current section, aim to further assess the adaptability of the proposed approach when paired with various types of graph encoders. Specifically, we elaborate on our experimental setup that incorporates three widely adopted graph encoders: Graph Isomorphism Network (GLN) (Xu et al., 2018), Graph Attention Network (GAT) (Veličković et al., 2017), and GraphSAGE (Hamilton et al., 2017). These experiments are conducted over a variely of graph datasets.
The result are summarized in Table 10. Our results underscore that our proposed contrastive learning technique exhibits consistent performance across broad spectrum of graph neural networks. We posit that this consistency can be attributed to the shared foundational principle of these GNNs, specifically their reliance on neighborhood aggregation mechanisms. Furthermore, these results exemplify the flexibilityy and wide-ranging applicability of the SP-GCL approach, showcasing its potential to accommodate diverse graph encoder types and perform effectively across different graph data contexts.
Cora
WikiCS
Comp.
Amazon Photo
Phy.
Chameleon
Squirrel
Actor
Twitch-E
GIN
79.45
72.73
85.14
90.31
93.88
60.22
40.88
27.
69.70
+S-+SL
80.30
73.52
87.08
91.47
94.20
62.93
42.66
28.45
70.88
GAT
82.90
78.68
87.17
91.03
93.90
65.39
44.98
28.14
72.76
GAT+SP-GCL
83.11
79.96
89.52
93.22
96.05
65.99
46.56
30.70
73.43
GraphSage
81.70
76.06
86.72
92.08
93.14
64.61
43.70
32.06
70.60
GraphSage+SP-GGS
82.67
77.87
90.46
92.37
95.76
64.69
44.89
33.19 19
71.26
Table 10: The performance of SP-GCL combining with different graph neural networks as the encoder.
C Appendix: Detailed proofs
C.1 Proof of Theorem 1
Assumptions on graph data. Consider the GNN model:
Z = W) WN
where a represents the nonlinear activation function, the X E NNF is the input layer, and D E R is the degree matrix, A NNN the adjacency matrix, and W Rxx is the weight. Assume that ||x;||a S R for some R 0, where X; E R represents the node features of i-th input node (i.e., the transpose of the i-th row of X). Define W₁ IR to be the k-th column of W. Given label y, the node feature x is sampled from some distribution Pa Paly- For node U; its neighbors labels independently sampled from neighbor distribution Py..
We assume that the nonlinear activation function a is homogeneous of degree T for some T 2 1 and o(4) S oq for some c 2 O. For example, ReLU activation satisfics these assumptions with 5 = c = 1. Also, it recoverse the result of the linear model too since if identity (i.e,, linear model), then T = c
Theorem (Concentration Property of Aggregated Features) For any W gFxk the following statements holds:
For any pair (i,8') such that y: = yr.
E Z
E[ZE] O.
(9)
With probability at least 1 - 8,
2ln(2K/8)
Z. loc cl
max KE[K]
|Wallz) V
(10)
D
For any node pair (i,j), with probability at least 1 8',
K Z 2,1 - Z, < 2 R²
22n(2/)))
(11)
D2-
D27
19

---

Published in Transactions on Machine Learning Research (08/2023)
Proof. For any matrix M, M. and M.j denote the i-th row vector and the j-th column vector of M. We first calculate the expectation of aggregated embedding:
)
2 = Ex 0
X, Du JEN(()
Σ
= (5x))
o
Σ JEN((s)
Dis
x W
Eg Pvy R Re k= Due
o
Σ
X
Di
(EN((1)
Therefore, for any pair (i, such that = yv' we have
Ex Z.]
Ex [Zp] = 0.
Moreover,
[xx Zz] - Z:1100
E
Σ
X W )
-0 -o
(
E
Σ
1
X.J. W
(12)
Dii
Dis
(EN(())
iEN(()
1
E
Σ
XJ.W
Σ
X.. w
D
JEN())
(EN(())
max RE(R]
1
E
Σ
X W.
Σ (EV(())
X
W.
D
(EV(()
where the first line follows the definition and the last line holds because the nonlinear activation function o is homogencous of degree т. Furthermore, since σlq)= S cq.
X,, W Σ (EN(()
Sc Σ X, W. S Se
Σ X JEN(O
JEN(()
Wellellle
Σ
Σ
X3
(13)
JEN()) t=1
S <cl W
Σ R²
JEN(
= cR W WolleVDa D#
Thus, the random variable ex ~ (EjeNt)) X,, W.). is bounded DE
S Up
1 where prr
cRl WallavDa. Thus, by applying Hoeffding's inequality to the RHS of equation (12),
(- P
P P(uz E[va] 2 t) S 2exp
2r
{ D22
Setting 8 = =2exp
and solving for t, this means that with probability at least 1 - 5,
2y
2r (2/88)
cR Walley 2D In(2/5)
2l1(2/8) D22-11
I1
[ux] <
cR W W
D2
D2
By taking union bound over E [K], with probability at least 1 1-8. 8,
2 21 (2K/5)
Ex [Z,] - Zg
max KE[K]
114 E [ux]
<
cR
max
W 1.2ll22
kE[K]
D
20

---

and solving for 1, this means that with probability at Published in Transactions on Machine Learning Research (08/2023)
Furthermore,
I = o E X. W)To( Σ
1 Xy.
(14)
Di
DJs
VEN(()
PEN(J)
Σ a E
X W.) of E
1 X.y.
(15)
Dii
Djj
& VEN(6)
JENU)
E
X W.) o( E Xy. W.))
(16)
D D
PEN((
J'ENG)
Σ
o( Σ
X² Wn)
X..Wa))
a( Σ Xy.Ww)
(17)
D D
PEN(()
J'EN())
Coupling with the Equation (13);
z 2,ト
1
Σ
D 53
Thus, the random variable stj DT DJJ as S sij I ( 1 r where applying Hoeffding's inequality,
EL X. W.) (E)ENn)) Xy. X, W.s) is bounded
Σn [(CENOO X W.) o(Ei'ENO) Xy. W..). Thus, by
CD DJj
P (( EB [s 2 2xxp
2r
EDD D3r
Correspondingly, we set 8' 2exp
2r
least 1 - 8'
2r 1n (2/8'))
2ln(2/5')
8sjj E [svg] S
2 R² Σ
D D3J
D
22
With probability at least 1 1-6% 8',
2 2lm(2/8))
Ex(2, 2,1-2,122 2
2 Σ
W 11
-
C.2
Proof of Lemma
To prove this lemma, we first introduce the concept of the probability adjacency matrix. For the transformed graph G. denote its probability adjacency matrix W, in which Wij = 1 Aij. way can be understood the probability that two nodes have an edge and the weights sum to because the total probability mass 1: Ens Wiss' = 1, for Us. Uy E V. The corresponding symmetric normalized matrix is W sym = W 11 and the Dw diag diag((v),,. (Ir),..., where wi = =, Ei We then introduce the Matrix Factorization Loss which is defined as:
E
CFr(F) A FF
min FERNXA
(18)
By the classical theory on low-rank approximation, Eckart- Eckart-Young Young Mirsky theorem (Eckart & Young, 1936). any minimizer F of (F)(F) contains scaling of the smallest eigenvectors of Lyy (also, the largest cigenvectors
of A Agym) up to a right transformation for some orthonormal matrix R E RK* We have F F*
diag ([v1 S/V1-1j...... AI...., v1 >k)) R. where F [nn Ug.... .u]] N To proof the Lemma 1, we first
present the Lemma 2.
21

---

Published in Transactions on Machine Learning Research (08/2023)
Lemma 2 For transformed graph, its probability adjacency matriz W, and adjacency matrix Å are equal after the symmetric normalization, W symm = A Asym-
Proof. For any two nodes Us, U4 Uy E V and + j, we denote the the element in i-th row and j-th column of matrix W eym as Wij sgm
W
A
4gmm
Ex dik
Tkz
E.
(19)
U sym
Au Leveraging the Lemma 2, present the proof of Lemma 1.
Ex Ack Σx
Proof of Lemma 1 We start from the matrix factorization loss over Asym to show the equivalence.
Agm
FF
W sym
FF 1|
Vin Smi((s)) Smr(1s))
Wy
(smi(wr) fmr((s)))
diy Smi((s) Smi((s)) + II =ym 1
(20)
2
ViDi in
Σ wniy [( Van fmn((ss) {(
Viy f
15
(mn( ( Smi(u;)) +C
2
Des
Vag
where fmr(v;) is the i-th row of the embedding matrix F. The w; which can be understood the node selection probability which is proportional to the node degree. Then, we can define the corresponding sampling distribution as Pdeg- and only if /w; FF((s)) fm;(U;) F,, the we have:
B Paep Vy Paeg
(F((s))
(21)
E w % -Unil(()))
(Fo(us) Fo(u,)))+
where M(x)) denotes the neighbor set of node v; and Uni(-) 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
E Eec-Uni(V) ---Umi(()
(Z. 2 2 vy-e vit sttusspp.)
(Z Zet +
(22)
Due to the node selection procedure, the factor wW; is a constant and can be absorbed by the neural network, Fg. Then, because Z, = (u;), we can have the Equation 22. Therefore, the minimizer of matrix factorization loss is equivalent. with the minimizer of the contrastive loss.
C.3 Proof of Theorem 2
Proof. Now provide the proof for the inner product of embedding. In particular, when we can achieve near-zero contrastive learning loss, i.e., (F) 0, the minimizer F of Cmr(F) contains scaling of the smallest eigenvectors of Eegm (also, the largest eigenvectors of Asgm), F [ni ug. ux] N according to the Eckart-Young-iinse theorem (Eckart & Young, 1936). Recall that y (1,-111 1 e Nxi is label of all nodes. Then we show there is a constraint on the quadratic form with respect to the optimal classifier. According to graph spectral theory (Chung & Graham, 1997), the quadratic form
y L Lsgmy
Σg A sgm )i (ys y
22

---

Published in Transactions on Machine Learning Research (08/2023)
which captures the amount of edges connecting different labels. Furthermore, suppose that the expected homophily over distribution of graph feature and label, i.e., y P(u:), x ~ Py(x). through similarity selection
satisfies Elhedge (9) c. Here O Em,sy--Umi()) (Ar, 1[y + æ,l). Since we have defined that as the density of edges that connects different labels, can directly show that y Leymy ON. Then we expand the above expression accoding Laym A Asym
y L symy = y- (I- A Ay N yyy
A'Aaay -Y' A
Next we consider the situation that we achieve the optimal solution of the contrastive loss, Z = arg min Lsp-ccL. Then, we have Lmf(E (F*) = O, which implies that Asym FF") As we analyzed in Section C.2, we have Z = F in this case. Furthermore, we have,
y Leymy = y² (I Asym)y y = N y z Zy
= yy (Z, Z₁ (i).Enn))))
(23)
2 Zi MI= - Σ
Z Zii vuw
This leads to,
2: Zz 1, - Σ 2. Zi [vi
i.j
1.
(24)
E Z₁ [,,,,,,]
ElZ, Z₁ |u. 2 1-
C.4 Proof of Theorem 3
Recently, HaoChen et al. (2021) presented the following theoretical guarantce for the model learned with the matrix factorization loss.
Lemma 3 For graph G, let fir E arg Vin be minimizer of the matriz factorization loss, (F)(F), where F; fmr(v;). Then, for any label y, there exists linear classifier B E IRex with norm |[ 1/ (1 Aς) such that
Exg
[18k
B But (vx)11a S AK+1
(25)
where T. is the one-hot embedding of the label of node ex The difference between labels of connected data points is measured by o², 0² : En.eeev Aij [y # ys]-
Proof of Theorem 3. This proof a direct summary on the established lemmas in previous section. By
Lemma 1 and Lemma 3, have,
Evy
11 - B
2: <
y AR+1
(26)
where ' the i-th smallest eigenvalue of the Laplacian matrix Laym A Aay-- Z obtained through the non-linear graph neural network, and the nonlinearity follows the assumption Note that @ of Lemma 3 equals 1 hedge-
23

---

Published in Transactions on Machine Learning Research (08/2023)
Then we apply Theorem 1 and Theorem 2 for hedge to conclude the proof:
Be,
I1
B zi
e + U n²²
Σ k=1
We
21n(2/d')
hedge
D
Dj
Ak+1
dK+1
6
K
2lm(2/6")
AK+1
+ te²r? R??
|
Eu. (D):
-2(07-11)
(27)
k=1
K
21n(2/6")
+ +2H
|wall2
(Dx)
12r--11
Akt1
k=1
2lm(2/8")
+ 2 RRC
Ax+1
where Cdegree = R ((Ds) > 0 is determined by input graph structure and is invariant to the learning process. The positive real constant R and c are defined in Assumption 1 and 2 respectively.
D Augmentations in Existing Works
Graph augmentation techniques are commonly used Graph Contrastive Learning (GCL) to generate different views of the same graph, facilitating the learning of invariant and robust representations. The following sections provide detailed insights into the methods mentioned in Table 11, including edge removing, edge adding, node dropping, and subgraph induction by random walks.
Edge Removing: This is a simple yet effective augmentation technique where random edges are removed from the graph to create a new view. The goal is to train the model to learn representations that can predict the missing edges, enhancing its ability to capture the underlying connectivity pattern of the graph. This method requires careful calibration as removing too many edges might disrupt the graph structure, whereas removing too few may not provide enough learning signal for the model.
Complementary to edge removing, edge adding involves introducing new edges to the graph. The new edges can be randomly generated or based on certain heuristics such as node similarity. The objective here is to encourage the model to recognize and adapt to changes in the graph's connectivity. This augmentation can help the model understand the importance of cach edge and improve its ability to generalize to unseen graph structures.
Edge Adding:
Node Dropping: In this augmentation technique, random nodes (along with their associated edges) are dropped from the graph. This can help the model learn robust representations that are resilient to changes in the node set. However, similar to edge removing, the number of nodes to be dropped needs to be carefully tuned to maintain the balance between providing enough learning signal and preserving the essential structure of the graph.
Subgraph Induced by Random Walks: This method involves generating a subgraph by performing random walks on the original graph. Each random walk starts from a node and moves its neighboring nodes randomly, creating path. The subgraph consists of the nodes and edges visited during the walk. This technique can reveal local neighborhood structures and dependencies among nodes, aiding the model in learning local as well as global graph structures.
Node Shuflling: Node shuflling is a technique where the identities or features of nodes in the graph are permuted, meaning that the feature vector of a node reassigned to another node. This is done while maintaining the adjaconcy structure of the graph, esscntially changing the correspondence between nodes and their features without changing the graph topology. This can help the model to learn representations that are invariant to changes in node identities features.
24

---

Published in Transactions on Machine Learning Research (08/2023)
Diffusion: Diffusion is process that propagates information (or features) across the graph based the adjacency matrix of the graph. For graph augmentation, diffusion process can be used to create new graph where node features are updated based on their neighbors' features. This can simulate the spread of information or influence in the graph, and the resulting graph can be used as a different view for contrastive learning.
Table 11: 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 el al., 2019)
Node Shuflling
GMI (Peng et al., 2020)
Node Shuffling
MVGRL (Hassani & Khasahmadi, 2020)
Diffusion
GCC (Qiu et al., 2020)
Subgraph
GraphCT (You et 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 et al, 2020)
Edge Removing
Feature Masking
25


Reviews:
[{"review_id": "BicwFZZz7p", "reviewer": "Reviewer_h4vc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength is that the authors have done a thorough empirical evaluation of the proposed method, which comprehensively demonstrated its advantage compared with a wide array of baselines. The writing (language) is of publication standard.\n\nThe cons are that (1) the technical quality can be improved (see below), and (2) the proposed method is not compared with the other GCL methods in the early theoretical sections. For example, after eq.(4), it should be highlighted how it differs from the other GCL methods in terms of formulations.\n\nOverall, I think the authors made great efforts but it should not be accepted in the current form. I also highlight the essential requirement of TMLR on the Technical Clarify, which is not satisfactory (many issues currently).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposed a meta-framework called \"Single-Pass Graph Contrastive Learning\" (SPGCL). The authors argued that it satisfies certain \"concentration attributes\" as stated in theorems 1 to 3. The authors also showed its advantages as compared to SOTA alternative GCL methods.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "section 3. mention whether self-loopes are added to the graph (which is common in graph convolution networks).\n\nWhat is the difference between $Z$ at the end of page 3 and $\\mathbf{Z}$ in theorem 1?\n\n$\\mathbf{Z}$ needs an explicit expression, as it is important for Theorem 1, and only informally introduced in the last sentence before the theorem.\n\"we denote the learned embedding through the neighbor aggregation and a linear projection by $\\mathbf{Z}$...\"\n\nTheorem 1, any pair $(i,i')$, mention the domain of the pair (e.g. V^2 that is any pair of nodes).\n\nTheorem 1, restate the assumptions e.g. by cross reference.\n\nPage 5: \"The set $S^i_{pos}$ is consisted by the $K_{pos}$ nodes closest to node $v_i$\"\nBy the author's definition, the set is defined by the neighbours with the maximum value of $z_i^Tz_j$, which is not exactly \"closeness\" (unless all $z_i$ are constrained on a hypersphere.)\n\nafter eq.(4), explain all notations, including the distribution \"Uni()$. Also, highlight its key difference from prior work.\n\n\"Theorem 2\" make clear what \"graph data assumption\" refers to (e.g. by pointing to prior assumptions).\n\neq.(6), use $\\mathbf{Z}^\\star$ (corresponding to $\\mathbf{F}^\\star$) instead of $\\mathbf{Z}$\n\nTheorem 3 is confusing, as $\\mathcal{L}_{SP-GCL}$ is defined with respect to $\\mathbf{Z}$, and a minimizer should be in the form of $\\mathbf{Z}^\\star$, however, the theorem states that \"Let $f^\\star$ be a minimizer of the contrastive loss...\"\n\neq.(7), what is $f^*_{gcl}$, $c$, and $\\tau$? What is the expectation $\\mathbb{E}_{v_i}$?\n\nAfter theorem 3, remark on its meaning, is that useful in practice? How?\n\nSection 5 \"the top-Kpos nodes with highest similarity from the node pool are selected as positive set for it which denote as $S^i_{pos}$\"\nHere, why $S^i_{pos}$ conflict with its prior definition at the beginning of page 5. I suggest using a different notation for the new set.\n\nEq.(8) the statement of \"the empirical contrastive loss is an unbiased estimation of the Equation 4\" needs more justification, as it depends on the concept of \"the node pool, P, are constructed by the T-hop neighborhood of b nodes (the seed node set S) uniformly sampled from V.\", while eq.(4) does not. Is that just an approximation? What is the bias? These discussions can strengthen the theoretical contribution.\n", "broader_impact_concerns": "I could not identify any ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sHtFuALDma", "reviewer": "Reviewer_cMtq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper provides some theoretical understanding and analyses for the concentration property of aggregated features and the proposed contrastive learning approach. The empirical study exhibits promising performances on multiple homophily and heterophily datasets.\n\nWeakness:\n\n1. The single-pass graph contrastive learning does not seem to be a unique feature of this work. There exist many self-supervised learning approaches that only need one pass-forward computation. The work [1] provides some examples.\n\n2. An important paper [2] published in TMLR 2022 has proposed a self-supervised graph learning framework for both homophilic and heterophilic graphs. This work is highly relevant but is missing. Comprehensive comparisons in methodology, efficiency, and effectiveness will be needed.\n\n3. The so-called graph assumption is quite vague and unclear: \"For node $v_i$, its neighbors' labels are independently sampled from the neighbor distribution $P_{y_i}$.\" This seems to be a very loosely defined assumption. What is exactly this distribution? To what extent can this neighbor pattern be generally satisfied in real-world datasets? Moreover, the concentration property is highly similar to previous analyses in the work [3], and the provided analysis is incremental if the only improvement is to include non-linear activation. \n\n[1] Self-supervised Learning on Graphs: Deep Insights and New Directions, 2020\n\n[2] Unsupervised Network Embedding Beyond Homophily, TMLR 2022\n\n[3] Is homophily a necessity for graph neural networks? ICLR 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a single-pass graph contrastive learning loss (SP-GCL) and provides theoretical analyses on the performance guarantees for the minimizer of the loss. The proposed SP-GCL method empirically achieves promising performance on both homophily and heterophily benchmark datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "\nIt is recommended to clearly state the assumptions being used in Theorem 1 instead of putting those assumptions into separating remarks.\n\nIt is recommended to comprehensively compare with other graph contrastive learning approaches. One example will be \"Unsupervised Network Embedding Beyond Homophily\" published in TMLR 2022.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "kTFH1AZBQM", "reviewer": "Reviewer_31ov", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\ni) The concentration property seems to be new and interesting, which provides a homophily agnostic characterization of node representations in GCL.\n\nii) The experiments are extensive and cover a broad scope of homophilic and heterophilic datasets, with various homophily degrees. The improvements of SP-GCL over previous GCL approaches on multiple heterophilic datasets are impressive.\n\niii) The authors also provide plentiful analysis to demonstrate the usefulness of the proposed sampling (or graph transformation) method, as well as the applicability of theoretical assumptions.\n\n**Weakness**\n\ni) The motivation of the work is not clearly presented.\n\nii) The concentration property theory assumes a specific graph family, which could rarely hold in practice.\n\niii) The experimental improvements are limited on various datasets. The experiments merely consider a specific GNN backbone, i.e., GCN. It’s unknown whether SP-GCL can be applied to more complicated GNN backbones, such as GAT, Sage and GIN.\n\niv) Some related works are missing discussion.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies Graph Contrastive Learning (GCL) on both homophilic and heterophilic graphs. The authors propose a concentration property for features obtained by neighborhood aggregation on homophilic and heterophilic graphs, and find that the inner product of hidden representations approximates to its class-wise expectation with a high probability, no matter on homophilic or heterophilic graphs. Then, the authors leverage the property to sample positive and negative samples based the hidden representation similarity, and developed a new GCL algorithm called Single-Pass GCL (SP-GCL), which does not need multiple passes as required by previous augmentation based GCL approaches. The authors conduct extensive experiments on multiple homophilic and heterophilic benchmarks and verify the effectiveness of SP-GCL.\n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While I acknowledge the considerable effort put into the experiments, I believe there is room for improvement in the work, specifically in addressing the following weaknesses:\n\ni) (as well as iv) The motivation of the work is not clearly presented: To my understanding, the authors seem to claim that previous dual-pass design does not have theoretical guarantees and can be costly on large-scale graphs. However, there has already been formal analysis of GCL generalization ability in [1], as well as efficient design for dual-pass algorithms in [2]. \n\nAddressing the heterophilic node classification via GCL is the main motivation of this work, while the node feature based homophily has already been proposed in [3]. If so, why not directly using the augmentation based strategies, but instead using the single pass sampling?\n\nI believe the motivation of this work could be presented more clearly by clarifying the aforementioned issues as well as complementing the related work discussion.\n\n\nii) The concentration property theory poses strong assumptions and is limited to a specific graph family:\n- The node feature $x$ is independently sampled from $P_{x|y}$ solely based on the label $y$, which does not consider the graph structures. It seems merely using a MLP is sufficient for learning the desired node representation.\n- The neighbors’ labels are further sampled from $P_y$, but neither $P_y$ nor $P_{x|y}$ are formally defined. Why do the authors adopt such a graph data model? How can the data model reflect the graphs generation in real-world applications?\n- It’s unclear why “the assumption means that the label of a neighbor is only determined by the label of the central node”, and why it is feasible for both homophily and heterophily.\n\n\niii) The empirical improvements are limited:\n- On homophilic graphs, previous GCL approaches seem to perform better than SP-GCL;\n- On heterophilic graphs, SP-GCL seems to perform better than previous GCL methods on small scale datasets while the improvements are decreased for large scale datasets;\n- SP-GCL can not outperform the MLP on heterophilic graphs, which seems to justify the limitations of the theoretical assumptions.\n\nBesides, only GCN is considered as the backbone in the experiments. Is SP-GCL also compatible with other more complicated backbones such as Sage, GIN, and GAT? Can the analysis in Section 6.7 also hold for those complicated backbones?\n\nThe computational cost analysis seems not consider the transformation operations in SP-GCL. \n\n**Minor**\n- “, And the node homophily” in Section 3 should be “. And”;\n- The font size for “SP-GCL” in Table 4 seems to be too small;\n\n\n**References**\n\n[1] Improving graph representation learning by contrastive regularization, arXiv 2021.\n\n[2] Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination, NeurIPS 2022.\n\n[3] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR 2022.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I apologize for the lateness of this recommendation.

From the start, the reviewers have acknowledged that this work is interesting and relevant. In particular, the concentration properties are an important addition to the literature and the resulting algorithm is both novel and useful. There were some concerns on clarity of the manuscript, relationship to existing work, and assumptions made. The authors have done a great job with their revision, greatly improving the clarity of the paper and explaining the missing relationships and assumptions. I recommend acceptance of the paper, but would like to pass on some minor comments that should be incorporated to improve clarity of the manuscript:

* Please ensure notation in the supplement matches updated notation in the main paper
* Some vector norms are explicit, e.g., $||w_k||_2$, and the Frobenious norm in eq(5). Some are not, e.g. $||Z_i||$ in section 4.2. Please unify this notation.
* Suggest changing $Uni(\cdot)$ to $\text{Uni}(\cdot)$
* In section 4.1, the adjacency matrix $\mathbf{A}$ is row-normalized. However, in section 4.3, the transformed graph adjacency matrix $\hat{\mathbf{A}}$ is symmetric normalized. Please add a sentence explaining the move to symmetric normalized
* In Theorem 3, $c$ is not defined. $\vec{y}$ is only introduced in Appendix C.4. It would be worth defining $c$, reiterating the definition of $\vec{y}$, and referring back to the original use of $R$ and $\delta'$ to make this easier to follow.
* On p7, $\mathbf{w}k$ should be $\mathbf{w}_k$
* Figures 1 and 2 would benefit from a higher resolution
* The theoretical analysis is only for the single-layer case, as how  is constructed in sec 4.1. There should be a few sentences to explain how they are useful/generalizable for the multi-layer case.

Decision: Accept (poster)