StructComp: Substituting propagation with Structural Compression in Training Graph Contrastive Learning
Authors: Shengzhong Zhang
Wenjie Yang
Xinyuan Cao
Hongwei Zhang
Zengfeng Huang
Venue: ICLR 2024 poster (2024)
Keywords: Graph Contrastive Learning
Scalable Training
Structural Compression
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Graph contrastive learning (GCL) has become a powerful tool for learning graph data, but its scalability remains a significant challenge. In this work, we propose a simple yet effective training framework called Structural Compression (StructComp) to address this issue. Inspired by a sparse low-rank approximation on the diffusion matrix, StructComp trains the encoder with the compressed nodes. This allows the encoder not to perform any message passing during the training stage, and significantly reduces the number of sample pairs in the contrastive loss. We theoretically prove that the original GCL loss can be approximated with the contrastive loss computed by StructComp. Moreover, StructComp can be regarded as an additional regularization term for GCL models, resulting in a more robust encoder. Empirical studies on various datasets show that StructComp greatly reduces the time and memory consumption while improving model performance compared to the vanilla GCL models and scalable training methods.

Published as a conference paper at ICLR 2024
STrUCTCOMP: SUBSTITUTING PROPAGATION WITH STRUCTURAL COMPRESSION IN TRAINING GRAPH
CONTRASTIVE LEARNING
Shengzhong Zhang
Wenjie Yang
Fudan University, Shanghai, China s2zhang1 7 fudan. edu. cn
Fudan University, Shanghai, China yangw @m. fudan. edu. cn
Xinyuan Cao
Hongwei Zhang
Georgia Institute of Technology, Midtown, USA xcao78@gatech.
Fudan University, Shanghai, China hwzhang22 2mm @m. fudan. edu. on.
Zengfeng Huang"
Fudan University, Shanghai, China huangzfe fudan. edu.
ABSTRACT
Graph contrastive learning (GCL) has become powerful tool for learning graph data, but its scalability remains a significant challenge. In this work, we propose simple yet effective training framework called Structural Compression (Struct- Comp) to address this issue. Inspired by a sparse low-rank approximation on the diffusion matrix, StruetComp trains the encoder with the compressed nodes. This allows the encoder not to perform any message passing during the training stage, and significantly reduces the number of sample pairs in the contrastive loss. We theoretically prove that the original GCL loss can be approximated with the con- trastive loss computed by StructComp. Moreover, StructComp can be regarded additional regularization term for GCL models, resulting in more robust encoder. Empirical studies on various datasets show that StructComp greatly re- duces the time and memory consumption while improving model performance compared to the vanilla GCL models and scalable training methods.
INTRODUCTION
Graph neural networks (GNNs) (Kipf & Welling 2017 Velickovic et al. 2018 Chen al. 2020b
Liu et al.] 2020) provide powerful tools for analyzing complex graph datasets and are widely ap- plied in various fields such as recommendation system (Cai et al.] 2023), social network analysis Zhang et al. a0) traffic flow prediction (Wang et al.) 2020). and molecular property prediction
Alex Fout Ben-Hur (019). However, the scalability límitation of GNNs hampers their extensive
adoption in both industrial and academic domains. This challenge is particularly pronounced within the realm unsupervised graph contrastive learning (GCL). Compared to the research on the scala-
bility of supervised GNNs (Hamilton et al.) 2017 Chen al.] 2018c bj Zou et al.) 2019 Cong al.
2020
Ramezani et al., 2020; Markowitz et al. 2022: Zeng et al.] (0TT]2200) [Chiang et al. 2019 Zeng
al. 2021), there is little attention paid the scalability of GCL (Wang et al.) 2022 Zheng al.
2022
and there is no universal framework for training various GCL models.
The scalability issue of GCL mainly has aspects: Firstly, the number of nodes that need to be computed in message passing grows exponentially. Secondly, GCL usually requires computation of a large number of sample pairs, which may require computation and memory quadratic in the
number of nodes, At the same time, the graph sampling (Zeng et al., 2020 Chiang et al. 2019
Zeng et al. 2021) and decoupling technology (Wu al.) 2019 Zhhu & Koniusz] (021) used for
"Corresponding author

---

Published as a conference paper at ICLR 2024
supervised GNN training not applicable GCL. Graph sampling might affect the quality of positive and negative samples, thereby reducing the performance of the model. As GCL usually involves data augmentation, the decoupling method that precomputes the diffusion matrix is not feasible.
In order to solve the aforementioned problems simultaneously, trix to replace message passing, which is low-rank approximation of the diffusion matrix. Utilizing the assignment matrix, we can compute the mixed node features, which contain all the local node information and can be regarded as the community center feature. By controlling the similarity of similar communities close each other. Since the number of sample pairs needed for computation by mixed nodes is significantly less than that for full nodes, and the encoder no longer computes message passing, the computational resources required for training are greatly saved.
sparse assignment ma-
the community center embeddings, we can make node embeddings to each other, and node embeddings in dissimilar communities distant from
Specifically, we propose extremely simple yet effective GCL training framework, called Struc- tural Compression (StructComp). This framework is applicable to various single-view GCL models and multi-view GCL models. During the training process, the GNN encoder does not need to per- form message passing, at which point the encoder can be regarded as a MLP. Our model takes the compressed features as input and trains in the same way the corresponding GCL model (i.c., the same loss function, optimization algorithm). In the inference process, we take the complete graph structure information and node features as input, and use the GNN encoder obtain the embedding representations of all nodes.
Our contributions are summarized follows:
1. We propose a novel GCL training framework, StructComp. Motivated by a low-rank ap- proximation of the adjacency matrix, StructComp significantly improves the scalability of GCLs by substituting message-passing with node compression. StructComp trains MLP encoder on these mixed nodes and later transfers parameters GNN encoder for inference.
2. We customize data augmentation method specifically for StructComp, making Struct- Comp adaptive to both single-view and multi-view GCL models. To the best of our knowl- edge, StructComp is the first unified framework designed specifically for GCL training.
3. We theoretically guarantee that the compressed contrastive loss can be used to approximate the original graph contrastive loss. And we prove that our method introducing an extra regularization term into the scalable training, which makes the model more robust.
4. We empirically compare StructComp with full graph training and other scalable training methods under four GCL models. Experimental results seven datasets demonstrate that StructComp improves the GCL model's performance, and significantly reduces memory consumption and training time.
2 PRELIMINARIES
Notation. Consider an undirected graph G (A, X), where A E {0. 1 represents the adja- cency matrix of G, and X = as V and E, with the number of vertices and edges given by = [V] and m E respectively. The degree of node i; denoted as d,, The degree matrix D a diagonal matrix and its i-th diagonal entry is dz
x is the feature matrix. The set of vertices and edges is represented
Graph neural network encoders. The GNN encoders compute node representations by aggregat- ing and transforming information from neighboring nodes. One of the most common encoders is the Graph Convolutional Network (GCN) (Kip' & Welling 2017), and its propagation rule is defined as follows:
( (D- 1 (ww))
where Ā A+ - D and W( is a learnable parameter matrix. GCNs consist of multiple convolution layers of the above form, with each layer followed by activation such as ReLU.
Graph contrastive learning. Graph contrastive learning is an unsupervised graph representation learning method. Its objective is to learn the embeddings of the graph by distinguishing between
2

---

Published as a conference paper at ICLR 2024
similar and dissimilar nodes. Common methods of graph contrastive learning be divided into
two types: single-view graph contrastive learning (Zhang et al.
2020:
Zhu et al. 202 and multi-
view graph contrastive learning (Zhu et al. 2020 2021b Zhang et al. 2021b Zheng al. 2022).
In single-view graph contrastive learning, positive and negative sample pairs are generated under the same view of graph. In this case, the positive samples are typically pairs of adjacent connected nodes, while the negative samples are randomly selected pairs of non-adjacent nodes. Then, through GNN encoder and contrastive loss function, the algorithm learns bring the embedding vectors of positive sample pairs closer and push the embedding of negative sample pairs further apart. The common single-view contrastive loss function (Hamilton al. 2017) of node u is as follows:
C(u) = log(o 20))
Σ k=1
log(o(-22)
(2)
Here, node v is the positive sample of node u, node k is the negative sample of node u, and K represents the number of negative samples.
Multi-view graph contrastive learning uses different views of the graph to generate sample pairs. These views be contracted by different transformations of the graph, such as DropEdge (Rong et al. 2020) and feature masking (Zhu et al., 2020). We generate the embeddings of the nodes, aim- ing bring the embedding vectors of the same node but from different views closer, while pushing the embedding vectors from different nodes further apart. The common multi-view contrastive loss function of each positive pair (u, v) is as follows:
+ L(u, v) = log co(zu + +E EKpoo (0(T.. + EkPuMEGG (a(2u
(3)
Here u and v represent the same node from different views, ø is a function that computes the simi- larity between two embedding vectors. G1 and G2 two different views of the same graph. is temperature parameter.
STRUCTURAL COMPRESSION
3.1 MOTIVATION
To reduce the training complexity of GCLs, we start with low-rank approximation C of the ad- jacency matrix A such that Á CCT Although the complexity of matrix multiplication is significantly reduced by the approximation, the actual training time will not decrease due to the dense nature of C. Moreover, the amount of negative pairs needed for the contrastive learning mains (n?²). )) To address the above issues simultaneously. we introduce sparse constraint for the low-rank approximation and force C' to be graph partition matrix Pr E Ruxnn (P/) = 1 if and only the node belongs cluster i), where n' is the number of clusters in the partition. Using 1r p'p"' X to approximate A X (where in the same cluster share the same embedding, and PT X contains all the information needed to compute the loss function. Therefore, we only compute PT X E IR" xd, a "node compression" operation, where nodes in the same cluster are merged together. Since nodes in the same cluster share their embeddings, performing contrastive learning these compressed nodes is equivalent to that on the nodes after the low-rank propagation (i.e., p'p X). Thus, the number of negative pairs reduced to n² Moreover, the complexity of matrix multiplication is now down to O(n) while persevering the sparsity. solved simultaneously by our method.
the row- normalzzee version of P'), key advantage is that nodes
nutshell, two major challenges for scalable GCL in Section [ can be
To generate the graph partition matrix P, we need to solve the following optimization problem:
minimize
|P'PT A
subject to P' (0, 10xn) P',, 1
Intuitively, P'pT is normalized graph that connects every pair of nodes within community while discarding all inter-community edges. Thus, |P''T Áll equals the number of inter-community
3

---

Published as a conference paper at ICLR 2024
edges plus the number of disconnected node pairs within communities. Minimizing the former is the classic minimum cut problem, and minimizing the latter matches well with balanced separation, given the number of nodes pair grows quadratically. These objective aligns well with off offtthe-seeff graph partition methods, so we directly utilize METIS to produce P.
From the perspective of spatial domain, we always hope to obtain an embedding ff fAA XW) of the following form: embeddings of nodes of the same class close enough, while embeddings of nodes of different classes are far apart. Intuitively, this goal can be simplified to the class centers of the various class node embeddings being far apart, and the similarity of nodes within the same class being as high as possible. In other words, we can use the community center f(P" X XW) as the embedding that needs to be computed in the loss function, instead of using all nodes in the com- munity for computation. On the other hand, if the embeddings of nodes within the community are identical, we no longer need to compute the similarity of nodes within the community. Considering these, it is natural to use pT X in place A X to compute the loss function. Moreover, since P is solved based graph partitioning, the result of the graph partitioning tion of positive and negative samples. The idea of using structural compression as a substitute of message- passang can be extended to multi-layer and non-linear GNN, which is shown in Appendix A.
facilitate the construc-
3.2 FRAMEWORK OF STRUCTCOMP
Preprocessing. We carry we use the METIS algorithm to obtain the graph partition matrix, and then take the mean value of the features of the nodes in each cluster the compressed feature, i.c., X p After computing the compressed features, we also construct compressed graph, i.e., A. = AP. Each node in A, represents cluster the original graph, and the edges represent the relationships between these clusters. A. is only used when constructing the contrastive loss and is not involved the computations related to the encoder. To make our StructComp adaptive to different types of GCL models, we carefully design some specific modules for single-view and multi-view GCLs, respectively.
operation termed "node compression". Based on the above analysis,
Input Graph
Compressed Feature
Compreseed
Embedding
Cantrastive
Single-view Training
Node
Input
Enceder
Congresion
Shared
Weight
Input Craph
Embedding
Inference!
Input
GCN Encoder
A,
Output
Figure 1: The overall framework of single-view StructComp.
Single-view StructComp. In single-view graph contrastive learning, we use the preprocessed com- pression features X, as input, and replace the GNN encoders with MLP encoders. For instance, two-layer neural network and embedding can be represented as follows:
Z. oox
We proposed to sample positive and negative pairs based on the compressed graph A. instead of A. One additional advantages of using the compressed graph over the original graph is that it significantly improves the accuracy of negative pairs sampling. For instance, since highly connected the
nodes compressed together, they not able to be selected negative pairs. Then same loss function and optimization algorithm as original GCL models to optimize the single-view contrastive learning loss (..)).. Figure shows the flow chart of single-view StructComp.
4

---

Published as a conference paper at ICLR 2024
Once the model is adequately trained, transition to the inference phase. We revert the changes made during the training phase by replacing the MLP encoder back to the GNN encoder. Then, we imput the complete graph structure information and node features to generate the embeddings for all nodes, as detailed below:
Z = (Ax
(6)
Multi-view StructComp. In multi-view contrastive learning, need to compare two perturbed views of the graph. This requires us not only to compress the node features but also to apply data augmentation to these compressed features. However, traditional data augmentation methods such as DropEdge are not applicable in StructComp, as there is no longer an A available for them to perturb during training. To fill this gap, introduce ber'. This technique offers a novel way to generate different representations of compressed nodes, which are essential for multi-view contrastive learning under StructComp.
data augmentation method called 'DropMem-
The DropMember method is implemented based on predetermined assignment matrix P. For each node in the compressed graph, which represents a community, we randomly drop a portion of the nodes within the community and recalculate the community features. Formally, for each cluster j in the augmented X we have:
Here, represents the number of nodes contained in cluster j. m, is independently drawn from a Bernoulli distribution and s' = Ei= M,, By performing contrastive learning the compressed features obtained after DropMember and the complete compressed features, we can train robust encoder. The loss of some node information within the community does not affect the embedding quality of the community.
Compressed
Feature
Compression
Encoder
Graph
Contrastive Loss
Multi-view Training
-respMeebber())
Shared Weight
Compressed Feature
MLP Encoder
Figure The training process multi-view StructComp.
For the multi-view graph contrastive learning model, we need to compute the representations two different views. Figure shows shows the training process of multi-view StructComp. In our implementa- tion, we use the complete X. and the perturbed X after DropMember as two different views. The embeddings of the two views as follows:
Z. = o())(WW))))))) ===o(o(x;..WW))
(8)
We use the same loss function and optimization algorithm original multi-view GCL models to optimize the contrastive loss (ZZ,, Z.). Once the model is trained, the inference process of multi- view StructComp is the same that of single-view StructComp.
5

---

Published as a conference paper at ICLR 2024
4 THEORY ANALYSIS OF STRUCTCOMP
4.1 THE EQUIVALENCE OF THE COMPRESSED LOSS AND THE ORIGINAL LOSS
In this section, we demonstrate that the contrastive loss on the original graph is close the sum of the compressed contrastive loss and the low-rank approximation gap. In other words, if the low-rank approximation in section 3.1 properly satisfied, we can estimate the original GCL loss using the compressed contrastive loss.
Here we consider the Erdös-Rén model, denoted as Gn,, p). where edges between n vertices are included independently with probability We use || ||2 to represent l2 norm and Frobenius norm. Additionally, we denote the feature vector of each node as X; E TRC. Then we can prove the following theorem, for simplicity, unweighted node compression. We leave the proof and details notations in Appendix A..
represent
only consider one-layer messsaee-passingg and an
Theorem 4.1. For the random graph G(n. p) from Erdös-Rényi model, we construct an even par- tition p = {S1, .......... }. Let fa(X) = AXW be a feature mapping in the original graph and [x(X) p'I XW as a linear mapping for the mixed nodes, where W E &Rdxe', Then by conduct- ing single-view contrastive learning. the contrastive loss for the original graph, denoted as (W),, can be approximated as the the compressed contrastive loss, (PWW), and term related to the low-rank approximation. Assume the features are bounded by Sx == max; ||Xx]l2, we have
(Lo(W) (P(W) < || P' p'p'' Sx ||
For a similar upper bound without the Lénōs--ééni graph assumption, please refer to Appendix A.3
4.2 THE REGULARIZATION INTRODUCED BY STRUCTCOMP
Following Fang al. 20233) show that multi-view StructComp is equivalent to random masking on the message matrices M, where Ma,j = (h,, hy, eij) and & is a function that takes the edges
eij and the attached node representations h4, hy. First, the low rank approximation P|P'P A+I is dropping the inter-cluster edges Edrop { F I the cluster that node! belongs to. And the latter is then equivalent to DropMessage Marop = Edrop where edge(M;) E Edrop indicates which edge that M, corresponds to. Our DropMember for the cluster is dropping Vårop = {X, 0 and S(i) = c}. This is equivalent to Marop =
and S(i) S(j)). where S(i) denote
E U. Vårup. Then we have the following theorem:
Theorem 4.2. Consider no-augmentation InfoNCE loss,
LInfONCE
E (TT EE Σ Σ
jEpas(i)
jEncg(i)
Optimizing the expectation of this with augmentation [[CINNNN introduce an additional regular- ization term, i.e.,
E[CInfONCE LIntoNCE + + Σ
o(h,, Var((h.),,.
(10)
jEnek()
where @hh;, h2) ( +c ((6 tc
2 424
Theorem 4.2 shows that, multi-view StructComp only improves the scalability of GCLs training, but also introduces an additional regularization term into the InfoNCE loss. By optimizing the variance of the augmented representations, encoders trained with StructComp are more robust to minor perturbation. Please refer to the Appendix A.4 for more details.
5 RELATED WORK
Scalable training on graph. To overcome the scalability issue of training GNNs, most of the pre- vious scalable GNN training methods sampling techniques (Hamilton al. 2017 Chen al.

---

Published as a conference paper at ICLR 2024
2018c bi Zou et al.; 2019 Cong al., 2020 Ramezani et al., 2020: Markowitz al. 2021 Zeng
et al.] 2020; Chiang et al. 2019 Zeng et al. 2021). including node wise sampling, layer-wist wise sam- pling, and graph sampling. The key idea is to train GNNs with small subgraphs instead of the whole graph at each epoch. However, graph sampling techniques are mainly used for training supervised GNNs and are not applicable unsupervised GNNs, as it is difficult to guarantee the provision of high-quality positive and negative samples after sampling. Another direction for scalable GNNs is to simplify models by decoupling the graph diffusion process from the feature transformation. The diffusion matrix is precomputed, and then standard mini-batch training can be applied (Bojchevski al., 2020 Chen al.) 2020a] Wu al., 2019). This preprocessing method is also not applicable to graph contrastive learning, as the adjacency matrix and feature matrix are perturbed in contrastive learning, which necessitates the repeated computation of the diffusion matrix, rather than only in preprocessing. Besides, methods represented by GraphZoom (Chen et al., [20 Liang al. 2018 Deng et al. 2019) learn node embeddings on the coarsened graph, and then refine the learned coarsed embeddings to full node embeddings. These methods mainly consider graph structural information, only applicable to handling traditional graph embedding (Perozi et al., [2014] Grover & Leskoved, 2016), but not suitable for GCL models. Most importantly, these methods require a lot of time to construct the coarsened graph, and the coarse-to-refine framework inevitably leads to information loss.
See the Appendix B for a discussion of the related work on graph contrastive learning.
EXPERIMENT
6.1 EXPERIMENTAL SETUP
The results are evaluated on night real-world datasets (Kipf & Welling 2017; Veličković et al. 2018 Zhu et al., 2021b Hu et al.) 2020), Cora, Citeseer, Pubmed, Amazon Computers, Amazon Photo, Ogbn-Arixv, Proon-rossuct and seer, Pubmed, Amazon Photo and Computers, performance is evaluated on random splits. We ran- domly select 20 labeled nodes per class for training, while the remaining nodes are used for testing. All results on small-scale datasets are averaged over 50 runs, and standard deviations are reported. For Ogbn-Arixx
On small-scale datasets, including Cora, Cite-
and Pgbn-Paperr 100M, we fixed data splits as in previous stud- ies Hu et al. (2020). More detailed statistics of the night datasets are summarized in the Appendix
We use StructComp to train two representative single-view GCL models, SCE Zhang et al. 2020) and COLES Zhu et al. 2021a), and two representative multi-view GCL models, GRACE (Zhu et al. 2020) and CCA-SSG (Zhang et al. 2b221b). To demonstrate the effectiveness of StructComp, we compare the classification performance of the original models and StructComp trained models on small-scale datasets. For scalability on large graphs, we compare StructComp with three scal- able training methods (i.e., Cluster-GCN (Chiang et al. 2019), Graphsaint (Zeng et al. (020) and Graphzoom (Deng et al.) al.] (219)). For all the models, the learned representations are evaluated by classifiers under the same settings.
The key hyperparameter of our framework is the number of clusters, which is set to [300, 300, 2000, 1300, 700, 20000, 25000, 5000] on night datasets, respectively. All algorithms and models are implemented using Python and PyTorch Geometric. More implementation details can be found in Appendix C Additional discussions and experimental results are included in Appendix D
6.2 EXPERIMENTAL. RESULTS
Performance on small-scale datasets. Table T shows the model performance on small datasets using the full graph training and StructComp training. The results show that StruetComp improves the performance of the model in the vast majority of cases, especially the multi-view GCL models. In the single-view GCL models, StructComp improves the average accuracy of SCE and COLES by 0.4% and 0.2%, respectively. In the multi-view GCL models, StructComp improves the average accuracy of GRACE and CCA-SSG by 2.6% and 1.6%, respectively. The observed performance improvement can be attributed to two main factors. First, StructComp constructs high-quality posi- tive and negative pairs, e.g., it ensures that highly-connected nodes are not erroneously selected as
7

---

Published as a conference paper at ICLR 2024
negative pairs in multi-view GCLs. Second, mentioned in Section 4.2
StructComp implicitly introduces regularization into the contrastive learning process, resulting in a more robust encoder.
Table 1: Comparison between StructComp and full graph training across four GCL models on small datasets. The performance measured by classification accuracy. "Ave A" is the average improve- ment achieved by StructComp.
Method
Cora
Citeseer
Pubmed
Computers
Photo
Ave A
SCE
81.0+11.3
71.7+1.1
76.5+228
79.2 +1.7
87.8 +1.4
81.6.10.9
71.51:0
77.2.1..9
79.7 1.7
88.2 11.4
+0.4
COLES
81.7+t0.9
71.2+1.2
74.6+3.4
1..5+1.6
18.5+1..4
StmiciCopp
81,8++0.8
71.6=
75.3+3.1
1..411
88.5+1.4
+0.2
GRACE
78.5+0.9
68.9+1.0
76.1+22.8
7..2+1.9
1..1
GRACEsmetonm
79.7+00.9
1.0
17.2+1.4
80.6
9..0+1.11
+2.6
CCA-SSG 79,211.4
71.8+10
76.0+2.0
82.7+100
88.7=1.1
CCA-SSG SSCSSooooopp
82.3+:0.8
71.6=0.9
78.3+2.5
83.1
90.8+1.0
+1.6
Time and memory usage for small-scale datasets. Table shows the improvements in runtime and memory usage of each GCL model. StructComp saves the memory usage of the GCL models on the Cora, Citeseer, Pubmed, Computers, and Photo datasets by 5.9 times, 4.8 times, 33.5 times, 22.2 times and 57.1 times, respectively. At the same time, the training is speeded up by 1.8 times, 2.1 times, 17.1 times, 10.9 times and 21.1 times, respectively. This improvement particularly evident when the dataset is large. The memory consumption for GRACE on the Computers dataset even reduced by two orders of magnitude. These results strongly suggest that our method significantly reduces time consumption and memory usage while enhancing model performance.
Table 2: Time (s/epoch) and memory usage (MB) for GCL training small-scale datasets. "Ave improvement" is the proportion of training resources used by StructComp to the resources used by full graph training.
Method
Corn
Puhmed
Computers
Mem
Time
Mem
Time
Mem
Time
Mem
Mem
Time
SCR SCEmmstCuup
82
0.003
159
0.004
1831
0.027
329
0.006
920
0.015
23
0.002
59
0.002
54
0.003
16
0.002
0.002
COLES
0.004
204
1851
0.033
378
0.031
COLES
24
0.002
60
0.003
61
0.003
21
0.008
39
0.003
GRACE
441
0.017
714
0.025
11677
0.252
1996
0.106
5943
0.197
GRACEssweCoup
37
0.009
72
0.009
194
0.009
59
0.008
54
0.008
CCA-SSG
132
0.010
225
0.011
825
0.123
1197
0.112
2418
0.210
CCA-SSCA SSGgmaran
38
0.006
71
0.005
85
0.006
0.005
0.005
Ave improvement
5,9x
1.8x
4.8x
2.1x
33.5x
17.1x
22.2
10.9
57.1x
2L.x
Scalability on large graphs. Table 3 and Table 4 show the results of StructComp on two large datasets Arxiv and Products, and compare them with three scalable training methods: Cluster-GCN, Graphsaint, and Graphzoom. We tested these training methods on four GCL models. Our method achieves the best performance on all GCL models on both datasets. The experimental results for Papers 100M are listed in Appendix D.I The models trained by our method achieve the highest accuracy, while also require significantly lower memory and time consumption compared other models. These results highlight the effectiveness of method in handling large-scale graph data.
Table 3: Performance and training consumption (time in s/epoch and memory usage in GB) on the Ogbn-Arxiv dataset. Each model is trained by StructComp and three scalable training frameworks.
Method
SCE
COLES
GRACE
CCA-SSG
Acc
Time
Mem
Aoc
Time
Mem
Acc
Time
Mem
Acc
Time
Mem
Cluser GCN
70.4:10.2
10.8
4.2
71.4:10.2
13.0
4.2
70.1.10.1
3.5
17.3
72.2110.1
2.2
Graphsaint
70.4:10.2
7.6
9.0
71.34...1
26.9
22.5
70.0:10.2
3.6
14.1
72.1
4,4
1.8
Graphzoom
70.6:20.2
0.04
9.8
70.0-10.3
0.08
14.3
68.24::.3
3.9
13.7
71.3+:0.2
1.0
StructComp
71.6:10.2
0.03
1.8
71.8:10.2
0.05
3.4
71.7+:022
1.2
11.7
72.2:10.1
0.9
0.5
8

---

Published as a conference paper at ICLR 2024
Table 4: Performance and training consumption (time in s/epoch and memory usage in GB) on the Ogbn-Produces dataset. Each model is trained by StructComp and three scalable training frame-
works.
SCE
COLES
GRACE
CCA-SGG
Method
Acc
Time
Mem
Acc
Time
Mem
Acc
Time
Mem
Acc
Time
Mem
Cluser-GCN
74.6.10.2
196,8
8.0
75.2
239.1
8.0
75.2:10.1
35.1
16.2
74.11:0.3
37.1
5.7
Graphsaint
74,5:10.3
18.5
9.5
75.3=
20.6
9.9
75.4:::0.2
36.8
14.3
74.8::0.4
35.4
3.3
Graphzoom
60.6.10.5
68.1-:044
61.0.10.44
11.1
68.6100.3
StrecCComp
75.2:
0.05
2.7
75.5=0.1
0.08
5.3
75.7=:0.1
4.0
12.0
75.8+00.2
3.7
0.6
135
02-
-329
125
g19
0:5
-02
1
25
(a) SCE on Cora
(b) COLES on Cora
(c) GRACE on Cora
(d) CCA-SSG on Cora
122
14
-55
-21
00a
52
225
64
7.2
(I) COLES on CiteSeer (g) GRACE on CiteSeer (h) CCA-SSG CiteSeer Figure 3: The trends of the original GCL loss and the loss that computed by StructComp-train trained parameters. "loss_o" is C(A) X; W) and "loss.c" L(A, U') where is trained with C(Xoi U).
(c) SCE CiteSeer
Comparison of loss trends. To examine the equívalence of StructComp training and traditional GCL training, we plug the parameters U trained with the compressed loss L(X2; U) back into the GNN encoder and compute the complete loss function C(A, U)). Figure 3 shows the trends of C(A,X; U)) and the original loss C(A, X; W) trained with full graph. The behavior of the two losses matches astonishingly. This observation implies that, StructComp produces similar parameters to the traditional full graph GCL training.
Effect of compression rate. We study the influence of the compression rate the performance of StructComp. We use StructComp to train four GCL models under different compression rates on Cora, Citeseer, and Pubmed. Figure 4 shows the performance change with respect to compression rates. We observed that when the compression rate is around 10%, the performance of the models optimal. If the compression rate is too low, it may leads less pronounced coarsened features, thereby reducing the effectiveness of the training.
Eaa
Daa
Daa
Daca
Kins
Kimsi
Tozs
Foze
635
035
035
335
018
415
Dn
(a) SCE
(b) COLES
(c) GRACE
(d) CCA-SSG
Figure 4: The influence of the compression rate on the performance of StructComp.
7 CONCLUSION
In this paper, we introduce StructComp, a scalable training framework for GCL. StructComp is driven by a sparse low-rank approximation of the diffusion matrix. In StructComp, the message- passing operation is substituted with node compression, leading to substantial reductions in time and memory consumption. Theoretical analysis indicates that StructComp implicitly optimizes the original contrastive loss with fewer resources and is likely produced robust encoder.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work is supported by National Natural Science Foundation of China No. U2241212, No. 62276066.
REFERENCES
Basir Shariat Alex Fout, Jonathon Byrd and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In NeurlPS 2017, 2019.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeshwar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and Devon Hjelm. Mutual information neural estimation. In International Conference on Machine Learning, pp. 531-540, 2018.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473, 2020.
Xuheng Cai, Chao Huang, Lianghao Xia, and Xubin Ren. Lightgel: Simple yet effective graph con- trastive learning for recommendation. In International Conference on Learning Representations, 2023.
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. HARP: hierarchical representation learning for networks. In Proceedings of AAAI, pp. 2127-2134, 2018a.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-950, 2018b.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 201 &c.
Ming Chen, Zhewei Wei, Bolin Ding. Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. Scal- able graph neural networks via bidirectional propagation. In Advances in Neural Information Processing Systems, 2020a.
Ming Chen, Zhewei Wei, Zengfeng Huang. Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-GGI An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In ACM SIGKDD interna- tional conference on Knowledge Discovery and Data Mining, pp. 1393-1403, 2020.
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng. Graphzoom: multi- level spectral approach for accurate and scalable graph embedding. International Conference on Learning Representations, 2019.
Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmes- sage: Unifying random dropping for graph neural networks. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 2023.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of International Conference on Knowledge Discovery and Data Mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances Neural Information Processing Systems, pp. 1024-1034, 2017.
Kaveh Hassani and Amir Hosein Khas Ahmadi. Contrastive multi-view representation learning on graphs. In International Conference Machine Learning, pp. 4116-4126, 2020.
10

---

Published as a conference paper at ICLR 2024
R Devon Hjelm, Alex Fedorov, Samuel Trischler, and Yoshua Bengio. Learning deep representations by mutual information estimation and maximization. In International Conference on Learning Representations, 2019.
Karan Grewal, Phil Bachman, Adam
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in neural information processing systems, pp. 221 18-22133, 2020.
Zengfeng Huang, Shengzhong Zhang, Chong Xi, Tang Liu, and Min Zhou. Scaling up graph ral networks via graph coarsening. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 675-684, 2021.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Jintang Li, Wangbin Sun, Ruofan Wu, Yuchang Zhu, Liang Chen, and Zibin Zheng. Scaling up, scaling deep: Blockwise graph contrastive learning. Arxiv, 2023.
Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. Mile: multi-level framework for scalable graph embedding. arXiv preprint arXiv:1802.09612. 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2020.
Kaili Ma, Haochen Yang, Han Yang. Yongqiang Chen, and James Cheng. Calibrating and improving graph contrastive learning. Transactions on Machine Learning Research, 2023.
Elan Sopher Markowitz, Keshav Balasubramanian, Mehrnoosh Mirtaheri, Sami Abu-El-Haija, Bryan Perozzi, Greg Ver Steeg, and Aram Galstyan. Graph traversal with tensor functionals: A meta-algorithm for scalable learning. In International Conference on Learning Representations, 2021.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social represen- tations. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, 2014.
Morteza Ramezani, Weilin Cong, Mehrdad Mahdavi, Anand Sivasubramaniam, and Mahmut Kan- demir. Gen meets gpu: Decoupling "when to sample" from "how to sample". In Advances in Neural Information Processing Systems, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2020.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. International Conference on Learning Representations, 2018
Haonan Wang, Jieyu Zhang, Qi Zhu, Wei Huang, Kenji Kawaguchi, and Xiaokui Xiao. Single- pass contrastive learning can work for both homophilic and heterophilic graph. Transactions on Machine Learning Research, 2023.
Xiaoyang Wang, Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. Traffic flow prediction via spatial temporal graph neural network. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 1082-1092, 2020.
Yili Wang, Kaixiong Zhou, Rui Miao, Ninghao Liu, and Xin Wang. Adagel: Adaptive subgraph contrastive learning to generalize large-scale graph training. In ACM International Conference on Information and Knowledge Management, 2022.

---

Published as a conference paper at ICLR 2024
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp- 6861-6871, 2019.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in neural information processing systems, pp. 5812-5823, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2020.
Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kan- nan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. In Advances in Neural Information Processing Systems, 2021.
Guozhen Zhang, Yong Li, Yuan Yuan, Fengli Xu, Hancheng Cao, Yujian Xu, and Depeng Jin. Community value prediction in social e-commerce. In Jure Leskovee, Marko Grobelnik, Mare Najork, Jie Tang, and Leila Zia (eds.), The Web Conference, pp. 2958 2967, 2021a.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and Philip S. Yu. From canonical correlation analysis to self-supervised graph neural networks. In Advances Neural Information Processing Systems, 2021b.
Shengzhong Zhang, Zengfeng Huang, Haicang Zhou, and Ziang Zhou. SCE: scalable network em- bedding from sparsest cut. In ACM SIGKDD international conference on Knowledge Discovery and Data Mining, pp. 257-265, 2020.
Yizhen Zheng, Shirui Pan, Vincent C. Lee, Yu Zheng, and Philip Yu. Rethinking and scaling up graph contrastive learning: An extremely efficient approach with group discrimination. In Advances in Neural Information Processing Systems, 2022.
Hao Zhu and Piotr Koniusz. Simple spectral graph convolution. In International Conference on Learning Representations, 2021.
Hao Zhu, Ke Sun, and Peter Koniusz. Contrastive laplacian eigenmaps. In Advances in neural information processing systems, pp. 5682-5695, 2021a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. In International Conference on Machine Learning Workshop on Graph Representation Learning and Beyond, 2020.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In The Web Conference, pp. 2069-2080, 2021b.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in neural information processing systems, 2019.
12

---

Published as a conference paper at ICLR 2024
A PROOF DETAILS
A.1 THE NON-LINEAR EXTENSION FOR EQUATION
We explain how extend the results to non-linear deep models below. Equation motivation of structural compression on a linear GNN (which can also be considered as an approx- imation one layer in multi-layer non-linear GNN). The analysis can be extended to non-linear deep GNNs. For instance, given two-layer non-linear GCN a (Aa (AXW1) we first approxi- mate Å by P'p"", then the whole GCN can be approximated as a(P' pT (P p" 22) = PPP'PT P'o(P" W = ('o(o(P"\W..WW)))
4 provides the
(1I)
The first equality holds because P' is a partition matrix and the last equality follows from the fact that PT p' I. Therefore, our analysis provides theoretical justifications of using StructComp substitute for non-linear deep GNNs.
A.2 PROOF FOR THEOREM
Single-view Graph Contrastive Learning. We view adjacent nodes positive pairs and non- adjacent nodes as negative pairs. In coarse graph of supernodes, we define pair of supernodes as positive if there exist two nodes within each supernode that are adjacent in the original graph. Let f: X + Rd be a feature mapping. We are interested in a variant of the contrastive loss function that aims to minimize the distance between the features of positive pairs v, v².
[()) = Eggut 11(()) f(v lll.
(12)
Graph Partition. For a graph = E, X). we consider the Erdös-Réng model, denoted as G(n, p). where edges between vertices are included independently with probability p. We compute a partition P on the nodes. We denote P = {Si, ... ).,) such that V = Uド Sj and Sj SS = / for J1 * j2. We define a partition P to be an even partition if each subset has the same size |- For each vertex u, we denote S(v) P as the subset that belongs to. We denote N(v) = {s v) E E or (u E E} as the set of neighbors of v. Denote M(v) = ((v) be the set of v's neighbors that are not in the subset with v.
|S1| |Sal
For the partition P, we denote p' E {0, 1) as its corresponding partition matrix, where P.j = if the node v2 belongs to the subset Sy. Let R = A-P' p'p'"" pr be the partition remainder. By definition, Ríj if node j E (i). Here we define the partition loss as
Cpartition = | F = || - P'p'T l|., where || || denotes the Frobenius norm.
Now are ready to prove Theorem 4.1
Theorem 4.1. For the random graph G(n, p) from Eydös-Rényí model, we construct an even par- tition P {Si, " Let fx(X) AXW be a feature mapping in the original graph and fx(X) prf XW as a linear mapping for the mixed nodes, where W gdxd' Then by conduct- ing single-view contrastive learning, the contrastive loss for the original graph, denoted as La (W), can be approximated as the sum of the compressed contrastive loss, Lp and term related to the low-rank approximation. Assume the features are bounded by Sx == max, ||Xill,. we have
).
Ca(W) (W)) S ||A P'p Sx [|]2
Proof. We denote the transpose of i-th row of X as X,. In the original graph, by the definition of adjacent matrix A, the embedding of each node v; is
fa.w (v.) = (AXW); = Σ W
(.E)(
For the compressed loss, each mixed node corresponds to subset S; of the partition P. We denote B(S)) == {S, E P: 3u E St, v E Sj, 8.,(fu v) E E} as the set of mixed nodes that are connected to S;. Then the embedding of mixed node S; can be written
(S.)(S:) (P" XW);
13

---

Published as a conference paper at ICLR 2024
For positive pair u, in the original graph, measure their difference in the feature subspace as follows.
Sa.w(u) - [c,w(v) ()x:(())((XX)......) - (AXW),
-W" Σ X₁
Σ
X
Σ X,
Σ x;)
e/ES(a)
wEE((e
(EM((N
=(p" XW)s(w)
(p XW) (RXW) (RXW).-
For positive pair (S,, S,) in the compressed loss, their difference in the feature subspace is
(p.w(S:) (p, (PT xw); - (PT)))))
For any i.j E [m]. (i; U3) is an edge in G independently with probability p. We denote pos as the set of positive pairs in the compressed loss. Then by calculating contrastive loss both graphs, have
La(W) Cp(WW
E (1) (c,w(,)l22- E (S,,S)) pos
(s,, f.. (S,)
(u,v)EE
IE' (u,D)E
II(PIT XW))(()) XW)(w))()))))) + (RXW), - (RXW)oll
I1(PTT XW): (PTXW)))
(E. pos
< E (M,D)E
[I(PTT (W)s(u)) -(PT (W) XW)s(
E
[[ (W); - xW)sll
pos
(RXW), (RXW)olk
(LLDEE
E (N,))E
(RXW)) (RXW)ol2.
The last step holds because the partition is even. On the other hand,
CP(W) Lo(W) [[P"TX)); - (P (PTXXW
E. ( pos
II(PT (W' D(W) (PTXW) D()) (RXW), (RXW)
(,,e)E
[I XW); (PTXW),lla
(S,,)))E pos
E
[I XW) - (P" XW"X
E (u,)EE
[[RXW), - (RXW))xl22
(u,e)E
= E [[RXW),, (RXW)oll. (a.)ER
We combine both inequalities. Denote 1|A P' [|.. Then we have
[Co(W) CP(W) < [(RXW) (RXW)>.l
(a.v)E
18 XW|
D E RR" is an sparse vector with 0, +1 entries
Σ
|X
s6 :
<nS x W
= =IIA P'p || W|l2.
14

---

Published as a conference paper at ICLR 2024
A.3 AN UPPER BOUND OF THE APPROXIMATION GAP WITHOUT ER GRAPH
We give extra analysis arbitrary graphs. For non-random graphs, the approximation gap of losses is simply bounded by the Equation 4
Suppose the loss is L-Lipschitz continuous,
[C(P'P"XW) xW) - C(Á'((AX & L'P'P A | [|]]
(13)
Equation
And for a spectral contrastive loss Lopec assume the graph partition are even, we have:
2 n +
n
Lspea PTT XW)
Σ 11 i=1
T e2,)
n2
i=
n'
n'
02,))
02,
n
k=
SES
i=1 1=
JES
n
n' mn
ET
E2
F2. ?
(14)
n
k=
1=1
2
ET,
ET
c E2,)
n
k=1
R=
2
ET. E2,
E E2,) (P'
n'
n2
where e1,; denotes the representations a recovered node and E denotes the representations of compressed node. The above analysis shows that our approximation is reasonable for fixed graphs.
A.4 PROOF FOR THEOREM 4.2
Theorem 4.2. Consider no-augmentation InfoNCE loss,
LInfONCE Σ Σ hhT
+
Σ Σ
[log(e AT + + (.)h))].
(15)
jEpos(s)
jEneg(i)
Optimizing the expectation of this with augmentation [[[InSaNCE) introduce additional regular- ization term, ie..
EIntONNE = LIafONCE + 1 -
Σ
o(h,, Var
(16)
2 jEnog(i)
(dRRRtcci ) 2 ho 2(0 1333
where @(h,, h2)
Proof.
E E[CnntNNC]]
=
Σ Σ
[n/ +
Σ Σ
cchlhi log(chThe + E|A2), (17)
jEpos(K)
jEnog(s)
where
E E = E Σ Σ
[ny(h: - h(]l =
(18)
jEpos(1)
15

---

Published as a conference paper at ICLR 2024
and
2 = E
Σ Σ
log(e hichs + hihs) - loggee Mshe + tchile))
jEneg
clestehs + ehulbslig (hr - -ii)
~ B
chilis chilay
JEneg
(19)
(e he + chishe chiiee (c
clibss) (ehith; + chihshng) (h: 12)
+
2(elihh + chilis)
hehing + elilks h2) + chil)s) (chi + chittshh h2) Var(h.).
2(e + ehehra2
jEneg
Thus,
ElLintaNCr] = LInIONCE +
Σ
Σ
(hss (i,,h;))ari Var(he),
(20)
jEneg
(e (e"int+e Noh ( 123) (e
where (h,, h1)
2 #2
B MORE RELATED WORK
Graph contrastive learning. Graph contrastive learning is an unsupervised representation learning technique that learns node representations by comparing similar and dissimilar sample pairs. Classi- cal graph contrastive learning models, such as DGI (Veličković et al.) (018)) and MVGRL (Hassani & Ahmadi 22220), use loss function based on mutual information estimation (Belghazi al. 2018
Hjelm et al.) 2019 to contrast node embeddings and graph embeddings. GRACE (Zhu et al. 2020
and its variants (Zhu et al. 202Tb; You et al., 2020) strive to maximize the similarity of positive pairs while minimizing the similarity of negative pairs in augmented graphs, intending to learn more effective node embeddings. However, the computational complexity of these methods too high for datasets, limiting their applications in large-scale graphs. To reduce computational consumption, CCA-SSG (Zhang et al. 22221b simplified the loss function by eliminating negative pairs. Recently, GGD Zheng al.) 2022) uses binary cross-entropy loss to distinguish between two groups of node samples, further reducing computational usage. Despite recent related work focusing on the scala- bility problem of graph contrastive learning (Wang et al.) [002)), these methods still need to rely graph sampling techniques when processing graphs with millions of nodes.
C IMPLEMENTATION DETAILS
The detailed statistics for the datasets used for transductive node classification are shown in Table 5 We compare GCL models trained with full graph and those trained with StructCompon small datasets. On Arxiv and Products, most GCL models cannot perform full graph training, so we com- pare the performance of different scalable training methods. For all GCL models, the learned rep- resentations evaluated by training and testing a logistic regression classifier smaller datasets. Due to Ogbn-Arxiv, Ogbn- Products and Ogbn-Papers 1 100M exhibits more complex characteristics, use three-layers MLP as classifier.
16

---

Published as a conference paper at ICLR 2024
Table 5: Summary of the datasets used in our experiments
Dataset
Nodes
Edges
Features
Classes
Cora
2,708
5,429
1,433
7
Citeseer
3,327
4,732
3,703
6
Pubmed
19.717
44,338
Amazon-Photo
7,650
238,163
745
8
Amazon
Amazon-Computee Computers
13,752
491,722
767
10
Ogbn-Arxiv
169,343
1,157,799
128
40
Dgbn-Proouce
2,449.029
61,859,140
100
47
Papers 100M
111,059,956
1,615,685,872
128
172
Details of Baselines. We test the performance of StructComp four GCL models: SCI
COLES GRACH CCA-SSC" And we compared StructComp with three scalable training meth-
ods Cluster-GCNII Graphsain o and Graphzoom on large graphs.
Details of our model. In Table 6 we present the specific formulations of both the embeddings and the loss functions that we have trained in our experiments. All models are optimized using the Adam optimizer. The hyperparameters for GCL models trained with StructComp are basically the same those used for full graph training of GCL models. We show the main hyperparameters in Table 7 and 8 The remaining hyperparameter settings for each GCL model are list in our code:
https: : g thub. com/
Table 6: The compression and loss function of GCL models under StructComp framework.
Model
Compression embeldiing
Function
Z.
TiZ 26
2.
Tr(2 L.C0Ze) Tr1 Lc
2. ReLU((X,
GRACE
C(u, cb(r::2o)/T + Legen cblu.aa))> Expu oblauisn)/r
%/ (MLU((XX(WWMM))
Z. ReLU((X.
11 2.11 M12. 1112 12 1113)
2. ReLU((X(WW))))
Table 7: Summary of the main hyper-parametedt small datasets.
Cora
Citeseer
Pubmed
Photo
Computers
Model
Epoch
Epoch
Epoch
Epoch
Epoch
SCEşmanCrmp 0.001
0.0001
50
0.02
0.001
20
0.001
COLES Cuscrpopppp
0.001
0.0001
50
0.02
0.001
20
0.001
GR ACT GRACFauuataa FauuusComp
0.001
0.0001
30
0.02
0.001
200
0.001
150
CCA-SSGanatimm
0.001
0.0001
50
0.01
100
0.005
Configuration. All the algorithms and models are implemented in Python and PyTorch Geometric. Experiments are conducted on server with an NVIDIA 3090 GPU (24 GB memory) and an Intel(R)
Xeon(R) Silver 4210R CPU @ 2.40GHz.
'SCE (MIT httpgh/gww.....ttocccccccc/c///r
ding
"COLES (MIT http:///w.ass..........ooaaaaaaa
*GRACE (Apache License [ccamm//hhhhiiaee///ttoooooooonn
*CCA-SSG
License httpp//......//aaaoo///////////a
$Cluster-GCN (MIT License) |
(MIT
aster/exampl e3/ httpmmmmeeeegapppaaaaaa.o
"Graphzoom (MIT License): http:nee)hhtts:///gii///
17

---

Published as a conference paper at ICLR 2024
Table 8: Summary of the main hyper-parameters large datasets.
Ogba-Arxiv
Ogbn-Produce
Dabe-PaperstOMM
Lr
Epoch
Weight decay
Epoch
Weight decay
Lr
Epoch
Weight decay
SCEsmaComp
0.0001
10
0.0001
0,0005
0.001
0.0005
COLLStmacCorp
0.001
0.0005
GRACCTSmotCnn
0.001
5
0.0005
0.001
0.0005
0.001
0.0005
CCA- SSnSSaa
0.0001
10
0.001
0.001
0.0005
D MORE EXPERIMENTAL RESULTS AND DISCUSSIONS
D.1 EXPERIMENTS ON PAPERS1001
We conduct experiments the Ogbn-Papers 100M dataset. The experimental results shown in T We use StructComp to train four representative GCL models. Here, we compressed ogbn- papersI00M into feature matrix X R5500+128 and trained GCL using StructComp. The table also presents the results of GGD trained with ClusterGCN, Although GGD is specifically designed for training large graphs, when dealing with datasets of the scale of ceonn-pppssIOO.. it still re- quires graph sampling to construct subgraphs and train GGD on large number of subgraphs. In contrast, our StructComp only requires training simple and small-scale MIP, resulting in signifi- cantly lower resource consumption compared to GGD++ClusterGCN.
Table The accuracy, training time per epoch and memory usage on the Oghn-Papers 1eeess00000. 100M dataset.
Method
Acc
Time
Mem
GGD
63.5+0.5
1.6h
4,3GB
SCESenaCoop
63.6::0.4
0.18s
0.1GB
COLES StrucCCump
63.6.10.4
0.16s
0.3GB
GRACI EttracCComp
DRACCEStacComm
64.0+10.3
0.44s
0.9GB
CCA-SSGiss SimsetComp
63.5-40.2
0.18s
0.1GB
D.2 EXPERIMENTS ON THE STABILITY OF STRUCTCOMP
We conduct extra experiments study the robustness of StruetComp. We randomly add 10% of noisy edges into three datasets and perform the node classification task. The experimental results are shown in Table I0 On the original dataset, the models trained with StructComp showed per- formance improvements of 0.36, 0.40, 1.30 and 1.87, respectively. compared to the models trained with full graphs. With noisy perturbation, the models trained with StructComp showed performance improvements of 0.80, 1.27. 2.47, and 1.87, respectively, compared to full graph training. This indicates that GCL models trained with StructComp exhibit better robustness.
Table 10: The results over 50 random splits the perturbed datasets.
Method
Cora
Citeseer
Pubmed
SCE
7..8+112
6..7+1.0
73.4+2222
SCESmaacCom
79.3+
69.3+0.9
75.7+22.8
COLES
78.7+11.
68.0+1.0
66,5
COLES StaneCoom
79.0
68.310.9
69.7:22.6
GRACE
77.6111.1
6..11
64.5
GRACE
BRACESsmaCooo CormeCComp
78.3:10.8
69.110.9
66.2:12.4
CCA-SSG
75.5++1.3
69.1+
73.5++2.2
SirictComp
78.2-10.7
69.210088
76.312.5
18

---

Published as a conference paper at ICLR 2024
D.3 EXPERIMENTS DEEP GNN ENCODER
In order to verify the approximation quality to the diffusion matrix of StructComp, we test the performance on deep GNN architecture called SSGC (Zhu & Koniusz 2021). We transferred the trained parameters of StructComp to the SSGC encoder for inference. For full graph training in GCL, both the training and inference stages were performed using the SSGC encoder. Table [T] shows our experimental results, indicating that even with deeper and more complicated encoder, StructComp still achieved outstanding performance.
Table 11: The results of GCLs with SSGC encoders over 50 random splits.
Method
Cora
Citeseer
Pubmed
SCE
81,810.9
78.4::2.8 72.010.9
82.0.10.8
71.710.9
77.8:1..9
COLES
81,810.9
71.311.11
74.8.13.4
COLES StmssComp
82.0.1.88
7..61..0
75.6:13.0
GRACE
80.210.88
7.0
77.312.7
GRACES ScrueCompp
81.1
1..0
78.2
CCA-SSG
82.1
71.9
78.2+288
CCA-SSG Smuueooo
82.6++0.7
71.7+009
79.4422.6
D.4 COMPARISON WITH RECENT GCL BASELINES
We provide comparison between StructComp and recent GCL basclines (Li et al., 2023 Wang iet al. 2023: Ma et al. 2023 Zheng et al. 2022). The specific results are shown in Table 12 For SP-GCL, we are unable to get the classification accuracy on CiteSeer since it does not take isolated nodes as input. The performance and resource consumption of various GCL models trained with StructComp are superior to recent GCL baselines.
It should be noted that the goal of these studies and our work are different. The aim of SPGCL is to handle homophilic graphs and heterophilic graphs simultaneously. BlockGCL attempts explore the application of deep GNN encoder in the GCL field. Contrast-Reg is novel regularization method which is motivated by the analysis of expected calibration error. GGD is a GCL model specifically designed for training large graphs, it is not training framework. On the other hand, StructComp is a framework designed to scale up the training of GCL models: it aims to efficiently train common GCL models without performance drop. It is not new GCL model that aims to achieve SOTA performance compared to existing GCL models. So our work is orthogonal to these previous works. In fact, StructComp can be used as the training method for SP-GCL, BlockGCL, Contrast-Reg Reg and GGD. In future work, we will further investigate how to train these recent graph contrastive learning methods using StructComp.
Table The results of StructComp-trained GCLss and some GCL baselines over 50 random splits.
Cora
Citeseer
Pubmed
Method
Ace
Time
Mem
Acc
Time
Mem
Acc
Time
Mem
BlockGCL
78.1
0.026
180
64.5+2.0
0.023
329
74.7+:3.1
0.037
986
SP-OCL
81.4=112
0.016
247
0.021
319
74.8:13.22
0.041
1420
Contrast Reg
79.2 1.3
0.048
355
6.6
0.097
602
72.4:133.5
0.334
11655
GGD
79.9 1.7
0.013
118
71.3-10.7
0.018
281
74.0.12.44
0.015
311
SCE SCEsmaaCump
81.6=0.9
0.002
23
71.5+
0.002
77.2422.9
0.003
54
COLES COLES
81.8=088
0.002
24
71.62:099
0.003
60
73.3:13..1
0.003
61
GRACEs ACEsmnatinpp
79.7=0.9
1.0
77.24114
0.009
194
CCA-SSGruutteupp
82.3=008
0.006
38
71.6+00.9
0.005
71
78.3+22.5
0.006
85
D.5 DISCUSSION ON GRAPH PARTITIONING
We conducted additional experiments to investigate the impact of graph partitioning on the perfor- demonstrate the effects of three algorithms, algebraic JC,
mance of StructComp. In Table 13
19

---

Published as a conference paper at ICLR 2024
variation neighborhoods, and affinity GS, the performance of StructComp. These three graph
coarsening algorithms are widely used in scalable GNNs (Huang et al. 2021). J. from which we can
obtain the specific graph partition matrix P. The experimental results suggest that different graph partition methods has little impact on StructComp on these datasets.
Table 13: The results of different graph partition methods.
Method
Cora
Citeseer
Pubmed
VN+ VN+SCEsmusCom
StruciComp
81.310.8
71.51100
77.51.2.7
JC+SCE JC+ StruCoomp
81.2:10.9
71.51:11
77.3:12.7
GS+SCE StrretCoom
81.5:10.8
71.41:100
77.41..0
METIS+SCEs Exmmettoom
81.6:10.9
71.5+10
77.2+2.9
VN+COLES StruciComp
81.4+-0.9
71.6++0.9
75.5+33.0
JC+COLEE StmeeCCmpp
81.4+00.
71.5++1.0
75.3++3.0
GS+COLES StrecrCoomp
818810.8
71.61:10
75,5
METIS+COLES StreerCoomp
81.810.8
71.610.9
75.343.1
D.6 EXPERIMENTS INDUCTIVE DATASETS
Our StructComp can also be used to handle inductive node classification tasks (Hamilton et al. Zeng et al., 202T). We provide additional experiments on inductive node classification in Table 14 Clearly, the GCL models trained with StructComp also perform exceptionally well on inductive node classification tasks.
2017
Table 14: The results on two inductive datasets. OOM means Out of Memory on GPU.
Flickr Time
Reddit Time
Method
Acc
Mem
Acc
Mem
SCE
50.6
0.55
8427
OOM
SCF SCSsucooomp
51.6
0.003
43
94.4
0.017
1068
COLES
50.3
0.83
9270
OOM
COLES SSLEeSsncCompp
50.7
0.003
48
94.2
0.024
1175
GRACE 51.5
OOM
OOM
GRACE EStracCComp
GRACEStnaiioop
0.010
221
94.3
0.079
8683
CCA-SSG
51.6
0.125
1672
94.9
0.21
$157
CCA UCA-SSGsaan SSGStratii
51.8
0.007
99
95.2
0,56
457
D.7 EXPERIMENTS HETEROPHILOUS GRAPHS
We conduct experiments to train SP-GCL WWang et al. 2023) with StructComp, in order to verify the performance of StructComp on heterophilous graphs. The experimental results are shown in Table Overall, the SP-GCL trained by StructComp is superior to full graph training. This is our initial attempt to use StructComp to handle heterophilous graphs, and is obviously a valuable direction worth further research.
15
Table 15: The results on heterophilous datasets.
Chameleon
Squirrel
Actor
Method
Acc
Time
Mom
Acc
Time
Mcm
Acc
Time
Mcm
SP-GCL
65 0.53 66.65=11.63
0.038
739
52. 10-0.67
0.080
3623
28 94-9--99.69
0.041
802
SP.GCLosrncommp
0.011
53.08=1.39
0.009
217
28.70+t
0.013
20


Reviews:
[{"review_id": "ruxtljuUs1", "reviewer": "Reviewer_PXMh", "summary": "The paper proposes Structural Compression (StructComp), a new training framework that improves the scalability of graph contrastive learning (GCL) models. The key idea is to substitute propagation with a sparse, low-rank approximation of the diffusion matrix to compress the nodes. Contrastive learning is performed on these compressed nodes, reducing computation and memory costs. Theoretical analysis shows the compressed loss approximates the original loss and StructComp implicitly regularizes the model.  Experiments on various single-view and multi-view GCL methods demonstrate StructComp's improvements in performance and efficiency.", "questions": "See the weakness above", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1.\tThe paper is well-written and easy to follow. The problem is motivated well, and the method is explained clearly. \n\n2.\tScalability is a major bottleneck hindering wider adoption of graph neural networks. This work makes an important contribution by enabling efficient training of GCL models.", "weaknesses": "1. Additional experiments could help verify claims on scalability and robustness of StructComp: \n\n- Evaluating on larger datasets like papers100M and or OGBG-LSC datasets  would better support scalability claims, since the experimented datasets are rather small or medium scale.  \n\n- Would be great to verify the model stability/robustness with the proposed regularization, since it is claimed in the presentation. \n\n\n2. Would be great to discuss the approximation quality to the diffusion matrix  of StructComp for more complicated graphs and other models architectures (like GAT, GraphSAGE) .\n\n3. There is a lack of  comparisons with certain related works, such as recent graph contrastive learning methods  [1-2] \n\n\n[1] ] Wang, H., Zhang, J., Zhu, Q., & Huang, W. (2022). Can Single-Pass Contrastive Learning Work for Both Homophilic and Heterophilic Graph?. arXiv preprint arXiv:2211.10890.\n\n[2] Li, J., Sun, W., Wu, R., Zhu, Y., Chen, L., & Zheng, Z. (2023). Scaling Up, Scaling Deep: Blockwise Graph Contrastive Learning. arXiv preprint arXiv:2306.02117.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qOmghInatf", "reviewer": "Reviewer_v4Cz", "summary": "This paper aim at resolving the scalability issue of graph contrastive learning training. In graph representation learning, the most compiutation  overhead comes from message passing, where its complexity grows exponentially wrt the num of layers in GNN. \n\nTo overcome this scalability issue, the authors propose **StructComp** trains the encoder with the compressed nodes. StructComp allows the encoder not to perform any message passing during the training stage.", "questions": "How theoritical results could be generalized to non-linear models?\n\nDoes the proposed method work for graphs with multiple node/edge types?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "I like the idea of using compressing nodes to replace the need of message passing.", "weaknesses": "- The theoritical results only hold in linear-GNN, which over-simplifies the problem. It is well know that deep neural network behave different from linear model in contrastive learning [1]. Without consider non-linearity, the problem in Eq. 4 is simply matrix decomposition problem (e.g., [2] section 3).\n\n[1] Understanding the Role of Nonlinearity in Training Dynamics of Contrastive Learning. https://arxiv.org/abs/2206.01342\n[2] Understanding Deep Contrastive Learning via Coordinate-wise Optimization https://arxiv.org/pdf/2201.12680.pdf\n\n- Experiment datasets are too small (even arxiv dataset is small)... please try some large-scale graph datasets (e.g., Yelp, Reddit datasets that previously GraphSaint paper) to validate the effectiveness. Especially when this paper is focussing on improving the scalability issue. \n\n- Repeat experiment multiple times instead of just once. For example Figure 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AaEoXdzQBe", "reviewer": "Reviewer_iDuQ", "summary": "This paper introduces StructComp, a scalable training framework for Graph Contrastive Learning (GCL). By replacing the message-passing operation in GCL with node-compression, StructComp achieves significant reductions in both time and memory consumption. The authors provide both theoretical analysis and empirical evaluations to underscore the effectiveness and efficiency of StructComp in training GCL models.", "questions": "1. Adding more discussions about graph partition: The authors should delve deeper into the topic of graph partitioning, as highlighted in the first weakness.\n\n2. Considering not over-claiming your work: It's crucial to avoid overstating the contributions. While the authors assert that they have provided theoretical proof, the strong assumptions (like the ER model) limit its applicability. It might be prudent to either temper such claims in the abstract and introduction or offer more exhaustive proof.\nIn essence, while I acknowledge the novelty and results presented in this paper, I urge the authors to provide a more in-depth rationale behind their impressive outcomes. Without this, the paper leans more toward a technical report than a comprehensive research paper.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The storyline is relatively clear, it is easy to follow for the authors.  \n2. The experiment results are amazing, especially the time-saving.  \n3. The used method is quite simple.", "weaknesses": "1. Lack of discussion of graph partition: The paper lacks a comprehensive discussion on graph partitioning. Given that the efficacy of the method hinges on graph partitioning—a classic NP-hard problem—a detailed exploration of its impact on the proposed method is warranted. A cursory introduction does not suffice.  \n2. Inadequate theoretical provements: The theoretical justifications provided are somewhat limited. The authors' attempt to establish the equivalence between the compressed loss and the original loss is based solely on the ER model, which may not be representative of real-world datasets.  \n3. Lack of the discussion about the limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "duQIbs6gkc", "reviewer": "Reviewer_kF3D", "summary": "This paper studies improving efficiency of graph contrastive learning. The authors propose a structural compression framework, StructComp, that adopts a low-rank approximation of the diffusion matrix to obtain compressed node embeddings. They show that the original GCL loss can be approximated with the contrastive loss computed by StructComp, with an additional benefit of the robustness. Experiments on seven benchmark datasets show that StructComp greatly reduces the time and memory consumption while improving model performance compared to the vanilla GCL models and scalable training methods.", "questions": "1. The applicability of StructComp seems to be limited:\n\n- Theoretically, StructComp has to rely on the approximation of the diffusion matrix for a specific graph and GNN model, as demonstrated in Theorem 4.1. How well StructComp can approximate to more complicated graphs such as heterophilous graphs, and more complicated while commonly used GNNs such as GraphSage, GIN, GAT, or even more interesting variants such as PNA?\n\n- Empirically, what is the exact setting of StructComp for node classification? Can StructComp be applied to both transductive and inductive node classification?\n\n- How well can StructComp approximate different augmentations in GCL?\n\n2. Several claims have not been verified:\n\n- The paper claims that StructComp can work for large scale graphs, while the benchmarked datasets are rather small or medium scale. Although it’s claimed that ogbn-products and arxiv are large datasets, while they are indeed medium scale datasets according to OGB (https://ogb.stanford.edu/docs/nodeprop/). To support the claim, it’s expected to evaluate StructComp in large datasets such as papers100M, reddit, or OGBG-LSC datasets.\n\n- The paper also claims that StructComp has better robustness and stability with the additional regularization, while no evidence’s been found.\n\n3. Some related works have not been compared or discussed:\n\n-  Some GCL works have not been discussed in the paper, for example, [1,2,3].\n\n- Why not comparing efficient GCL baselines such as CCA-SSG, and GGD discussed in the paper?\n\n4. How the time and memory cost are computed? Do they count in the preprocessing steps?\n\n\n**References**\n\n[1] Calibrating and Improving Graph Contrastive Learning, TMLR’23.\n\n[2] Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph, TMLR’23.\n\n[3] Scaling Up, Scaling Deep: Blockwise Graph Contrastive Learning, arXiv’23.\n\n[4] Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data, arXiv’23.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(+) The proposed structural compression idea is new and interesting;\n\n(+) The presentation and organization are clear and easy to follow;", "weaknesses": "(-) The applicability of StructComp seems to be limited;\n\n(-) Several claims have not been verified;\n\n(-) Some related works have not been compared or discussed;", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)