GALOPA: Graph Transport Learning with Optimal Plan Alignment
Authors: Yejiang Wang
Yuhai Zhao
Daniel Zhengkui Wang
Ling Li
Venue: NeurIPS 2023 poster (2023)
Keywords: graph neural network; self-supervised learning; optimal transport;
TL;DR: It proposes a novel graph self-supervised scheme that is positive-free and negative-free via plans alignment from the representation space to graph space.

Abstract: Self-supervised learning on graph aims to learn graph representations in an unsupervised manner. While graph contrastive learning (GCL - relying on graph augmentation for creating perturbation views of anchor graphs and maximizing/minimizing similarity for positive/negative pairs) is a popular self-supervised method, it faces challenges in finding label-invariant augmented graphs and determining the exact extent of similarity between sample pairs to be achieved. In this work, we propose an alternative self-supervised solution that (i) goes beyond the label invariance assumption without distinguishing between positive/negative samples, (ii) can calibrate the encoder for preserving not only the structural information inside the graph, but the matching information between different graphs, (iii) learns isometric embeddings that preserve the distance between graphs, a by-product of our objective. Motivated by optimal transport theory, this scheme relays on an observation that the optimal transport plans between node representations at the output space, which measure the matching probability between two distributions, should be consistent to the plans between the corresponding graphs at the input space. The experimental findings include: (i) The plan alignment strategy significantly outperforms the counterpart using the transport distance; (ii) The proposed model shows superior performance using only node attributes as calibration signals, without relying on edge information; (iii) Our model maintains robust results even under high perturbation rates; (iv) Extensive experiments on various benchmarks validate the effectiveness of the proposed method.

GALOPA: Graph Transport Learning with Optimal Plan Alignment
Yejiang Wang1.2 Yuhai Zhao 1.2, Zhengkui Wang" Ling Li
School of Computer Science and Engineering. Northeastern University, China
2 Key Laboratory of Intelligent Computing in Medical Image of Ministry of Education, Northeastern University, China
3 InfoComm Technology Cluster, Singapore Institute of Technology, Singapore jangyyeiinggsttmmaiii neu. edu. en, zhaoyuhai@maile neu. edu. en, zhengkui.
edu.sg, lilingneu@gmail.c com
Abstract
Self-supervised learning on graphs aims learn graph representations in an unsu- pervised manner. While graph contrastive learning (GCL relying on graph augmentation for creating perturbation views of anchor graphs and maximiz- ing/minimizing similarity for positive/negative pairs) is a popular self-supervised method, it faces challenges in finding label-invariant augmented graphs and deter- mining the exact extent of similarity between sample pairs to be achieved. In this work, we propose an alternative self-supervised solution that (i) goes beyond the label invariance assumption without distinguishing between positive/negative sam- ples, (ii) can calibrate the encoder for preserving not only the structural information inside the graph, but the matching information between different graphs, (iii) learns isometric embeddings that preserve the distance between graphs, by-product of our objective. Motivated by optimal transport theory, this scheme relies observation that the optimal transport plans between node representations at the output space, which measure the matching probability between two distributions, should be consistent with the plans between the corresponding graphs at the input space. The experimental findings include: (i) The plan alignment strategy signifi- cantly outperforms the counterpart using the transport distance; (ii) The proposed model shows superior performance using only node attributes calibration signals, without relying on edge information; (iii) Our model maintains robust results even under high perturbation rates; (iv) Extensive experiments on various benchmarks validate the effecttivness of the proposed method.
Introduction
Self-supervised graph learning involves learning representations of real-world graph data without the need for human supervision. Graph contrastive learning (GCL) [6. 16, 71] has been identified as one of the most successful graph self-supervised learning approaches, with its key components consisting of graph augmentation and contrastive learning. The former creates perturbation views of anchor graphs via various augmenting techniques, while the latter maximizes the similarity for two augmentations (positive pairs) of the same anchor and minimizes the similarity for those of two different anchors (negative pairs). The effectiveness of contrastive learning dependent on the assumption that the augmented operations preserve the nature of data points and ensure that the augmented samples have consistent labels with the original ones.
Corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

However, graph data structures are discrete and their properties may vary significantly even with slight perturbations, which makes it much more challenging to design reasonable augmentations that guarantee the label-invariant assumption for graphs, in contrast to images or text. Additionally, the concept of "maximum similarity" in contrastive learning is difficult to measure since it vague and lacks clear indication of how much similarity should be maximized (or minimized) for given pair of positive (or negative) views.
To address these challenges, an intuitive solution is to introduce the concept of distance from the input space, whereby the distance between the learned embeddings is forced to be equal to the distance between the corresponding input graphs. However, this requirement is challenging to achieve as the input objects (graphs) and output representations (vectors) are two distinct concepts, making it difficult to agree on their distance metrics. For instance, comparing the graph edit distance between graphs [15] and the Euclidean distance between vectors directly is inconceivable.
In response to the aforementioned challenges, in this paper, we propose a novel self-supervised learning method that seeks to align optimal transport plans [59] from graph space to node representation space, instead of transport distance [44]. This method is referred to as Graph Transport Learning (GTL), and it exploits the key concept in optimal transport (OT) theory, which aims to identify an optimal match (i.e., transport plan) between two data distributions (e.g., node sets of graphs) that minimizes the matching cost (i.... transport distance). As shown in Figure 1, the transportation plan explicitly determines how to match particles from the source distribution to the target distribution v. Our approach involves several key steps. First, we obtain two graph views by augmenting a graph and generating node embeddings using backbone model, such as Graph Neural Network (GNNs) [25]. Two optimal transport plans can be computed from the graph space and the representation space, respectively. To accurately capture the matching relationships in the original graph space, we enforce the backbone to learn representations that exhibit consistency with the optimal transport plans between the corresponding source graphs in the input space. This is achieved by minimizing the discrepancy between the two plans. Unlike distance- based approaches, the transport plan alignment shows several advantages: (i) Direct comparability; Plans with the same dimension can be compared directly, regardless of differences between the graph and representation spaces. The value of the transport plan is dimensionless, representing the joint probability of two particles; (ii) Accurate match relationship: For discrete objects, the transport plan retains more accurate matching relation between data compared to distance; (iii) Label-variant: Importantly, our self-supervised model does not require differentiating between positive and negative samples after graph augmentation. This is due to the availability of corrective information from the input space, which eliminates the need for a label-invariant assumption. Notably, our experimental findings in Section 7 demonstrate that our model maintains robust performance even under high perturbation rates, such as when 80% of both edges and node attributes are destroyed during graph augmentation. In summaryy we make the following contributions:
Figure 1: An illustra- tion of discrete opti- mal transport plan.
We propose a novel paradigm for superviedd graph learning based on optimal plan alignment, GALOPA, which offers a distinct objective compared to contrastive learning methods. This approach eliminates the need for a label-invariant assumption.
By constraining the discrepancy between the transport plans, we introduce a new loss to enable the sharing of the exact matching information from the graphs space the representation space.
Multiple comprehensive experiments, including distance v.s plan, node feature v.s edge, robustness test and comparison with state-of -fht---rrt methods demonstrate remarkable performance of GALOPA.
2 Related Work
Self-supervised Learning on Graphs. Graph self superviedd learning has been a promising paradigm for learning useful representations of unlabeled graph data. The node embedding methods aim to learn a low-dimensional vector embedding of vertex preserving different kinds of order proximity via factorization [3], random walk [17] or deep learning [8, 61]. Recently, graph contrastive learning has achieved unprecedented success [6, 28, 55, 64]. where the goal is to ensure representations have high similarity between positive views of a graph and high dissimilarity between negative views. A common way of contrastive objective is contrasting views at the node level. For the

---

representations (positive views) h and h of same node i in two augmented graphs G1 and G2 the pairwise contrastive loss can be defined
((h).22)/ Σ log D(L + Exe D(u b21/T
Cecentrstt
(I)
where D is a discriminator that maps two views an agreement (similarity) score, such as the inner product. т denotes the temperature. Obviously, this type of loss strongly relies on the label invariance assumption. other words, it needs know (or assume) beforehand that the two views are positive/negative samples, which is challenging for discrete graph structures. For example, there exist some graphs, such as molecular graphs, whose labels are very sensitive to perturbation/coorupiionn Some studies have explored the lahel-invariant augmentation [29, 31, 74], but such augmentations require very careful design and adjustment, and sometimes limit the power of graph augmentation. More recently, [22] utilizes the graph edit distance to train graph discriminator to predict whether graph an original graph or a perturbed one. However, this model still requires positive and negative samples and relies the assumption of label invariance.
Optimal Transport. Optimal transport (OT) [59] mathematical tool for aligning probability distributions has received much attention in the machine learning community in many applications. e.g., computer vision [4, 51]. generative adversarial network [2, 30], domain adaptation [18]. OT aims to derive a transport plan between a source and target distribution, such that the transport cost. minimized. [34] proposes the Gromov-Wasserstr Wasserstein (GW) distance between metrics defined within each space rather than between samples across different spaces, which has been used as a distance between graphs in several applications [56, 60, 67]. However, these studies can only perform graph classification on datasets with multiple graphs and cannot be applied to network analysis, such as node representation classification, where only one network is available. In this work, we combine optimal transport problem with graph neural network to form novel self supervied learning paradigm that allows both graph and network learning. See Appendix A for more details.
3 Background
(V, A. be a graph of n nodes where V denotes the set of nodes, A E {0, 1)ax= is the adjacency matrix. / E IR" is the empirical distribution of nodes in G. Generally, is a uniform discrete probability distribution. When the node label (or attribute) is available, we represent the node feature matrix as X E Raxd where d denotes the dimension of node attributes.
Notations. Let == =
X' represents the i-row of X. Let [n] f1,.............. ... n}, [m] [n|] x [m] and (---) denotes the inner product for matrices. We denote @ the iensor-matrix multiplication. 1, represents the vector with ones as all the n elements. |. denotes absolute value.
Plan and Optimal Transport. The optimal transport (OT) problem is pioneered by Monge [35] in order to seek the most cost-effective transport plan that transforms the mass of pile of sand into another one. In particular, studies how find an optimal coupling or optimal plan iT for transforming the distribution to with minimum total transport cost (i.e., optimal transport distance), where the element of ı describes the probability of moving mass from one position to another. In this work, we mainly focus on the discrete case. Given two sets of features X, = {Xi] and X2 = {X²) where n and are are the number of features, respectively. distributions of the entities in the two sets, respectively. The formulation of the OT distance is
R² and I are the probability
ΣΣ W(XI, X2) = min
cx cx
X²)
Faj
min =ET((U.))
(2)
rETT(W.)) iE|m] JE[m]
where
I( v) = f E x T1m = M4 1,
(3)
denotes all the joint distributions with marginals μ and v. cost (work) of moving X X2, the cosine distance between X and X; a popular choice. The E Ruxm is called as transport plan. This distance is also known as the Wasserstein distance.
cx( is the
Optimal Transport for Graphs. The Wasserstein problem requires the two distributions of point sets to lie in the same space. But for graphs, it is difficult to measure the cost between two nodes on
3

---

different graphs without node label (attribute). Even if the cost between nodes could be calculated, the Wasserstein distance cannot take the edge information into account. To compare distributions that are not necessarily in the same space, [34] defines wonmov-Wassersteinn distance between two graphs without node label 91 = (A1, ()) and G2 (A2, v) as follow
Wow (91,92) = min
Σ A. J.E[m]
Σ ca(Af 2R A!") T = min (L(A1, A2) & n. TEl((.))
(4)
where L(AI, A2) is 4-D tensor and L(A1, A2) CAl A The cost function CA is commonly defined as (A(" AA.') |A A!
Consider two graphs with node attributes G1 = (A1,X1,1 and G2 (A2, X2, where A E Rax* and A₂ E Rm denote their adjacency matrices, Xi E Rund and X₂ E Rmmxd are feature distance [56] between graphs 91 and G2 be defined as
matrices. The fused
WF
min =o)
>Exxe Cxx(Xix Xx) oi + (1 σ) Σ cA A!" mH T (5) iikl
which is equivalent to
min ng Ell(
(a (a + (1-))((A, A2) & Tg. kg)
(6)
where K(X1, X2); cx X2). A2),,4)))44 ca(A)" Ag") and
[0; 1] denotes
trade-off parameter. Obviously, this definition is a fusion of Equations (2) and (4).
Graph Transport Alignment
As analyzed in the previous section, the cent graph contrastive techniques are deeply plagued by positive and negative sample generation, since graph properties could be- come completely different even with slight perturbations. To design a universal self- supervision scheme, are motivated cal- ibrate the similarity between different repre- sentations in the output space using the match- ing signal between corresponding graphs from the input space. In particular, we first perturb the given graph to obtain two differ- ent graphs (e.g., a perturbed graph and the original one) and generate the node embed- dings of the two graphs using the backbone model (e.g.. GNNs). After computing the op- timal transport plans for the graphs and the sets of node representations respectively (Sec- tion 4.1,, we take the discrepancy between the two plans as the loss to calibrate the backbone for obtaining representation with rich geometry awareness and interpretable correspondences (Section
Encoder
9.
Encoder
Aligning
Figure 2: A framework of graph transport self- supervised learning.
4.2). We compare the proposed graph self-supervised learning paradigm with graph contrastive learning in Section 4.3. The framework can be found in Figure 2.
4.1 Optimal Transport Plan
In general, it is challenging to define two similarity metrics (e.g., distances), which can be directly compared, in two different spaces. This is especially the case for graphs and vectors, two distinct objects by nature. Fortunately, optimal transport theory offers a glimmer of hope, transportation plan, for such comparison. In this section, we present objectives that aim at finding the optimal plan for two graphs (or sets of vectors) to minimize the transport cost. For the graph, natural idea is to jointly take into account both node attributes and explicit topology information (i.e., edges) in the transportation plan. In this work, we leverage [56] to present an objective function for calculating the optimal transport plan which integrates the edge structure and the feature information nodes.

---

Specifically, the fused optimal transport plan z E R between two node-attribute graphs G1 and G2 can be defined as
G argmin ell
(o X2 +1-
X ng. mg)
(7)
with the fused Gromov- Wasserstein distance (6). By tuning the parameter a we can control the bias of the learned optimal plan between node attributes and edge structure. Intuitively might think that combining more edge information could greatly benefit the expressiveness power of the model. However, observe that the performance of the proposed method does not degrade significantly in the absence of edge information, and even increases rather than decreases on some datasets. It will be explained in detail later.
For the node representations of graph encoded by the backbone model (e.g., GNNs), we can either use Equation (2) directly to calculate the optimal plan 22 R=xm or set in Equation (7) as
Tz 11. Zz) = argmin
(J(Z1, Z2). T2)
(8)
=zEl((p,))
where J(Z, Z2)1; Cz Zi Z3), Z and Zz denote the node representations corresponding to 91 and 92, respectively.
4.2 Optimal Transport Alignment
The previous section establishes the foundation that comparing the similarity metrics defined on graph space and vector space can be reduced into comparing the two optimal transport plans from these spaces, each of which can be solved using Equations (7) or (2). This is a valid comparison because the optimal transport plan acts as probabilistie matching of two distributions, while the two plan matrices have the same dimensions (i.e., 1. X m.)
Naturally, the encoder may succeed in obtaining good representations for graph if it learns the node embeddings that not only retain its structural information inside the graph, but also capture matching information with other graphs. This motivates us to force the encoder to preserve the matching relationship in the graph space by aligning the plan between the two graphs with the plan of their corresponding node representations. We define a match alignment loss by minimizing the discrepancy between the two transport plans as follows
Lmatch = A T me 2 Zz)
(9)
where the discrepancy function A(.,-) can be any commonly used metric, e.g., the Frobenius-nowe norm || or the divergence (--Il-)
In addition, to guide the encoder to learn a representation retaining structural information inside the graph, we also calibrate the cost matrix J (Zz, Z2), which implies the implicit structure relationships between nodes, in the representation space as follow
Limyarre = A( K (K X²) + (1 - L) A2) & mg. J ( Zz)
(10)
To understand the concept of 'im- plicit structure' intuitively, here we consider the one-dimensional case. As shown in Figure 3, given a point set iZ
(z))
(zi,
(z(Zi,
7 the loca- tion of each of its points is fixed. If the position of a point (yellow) Z unknown but the transportation cost from this point to all points (blue) in the point set P is known, then the location of this point is determined with respect to the entire point set P. The same holds true for another point Z Thus
Figure
illustration of implicit structure in one-dimension.
relative position relationship between points Z and Z can be captured implicitly by the transport costs matrix J J(Z,, Zz)-
To this end, we define the overall graph transport alignment loss as
LGALOPA Lmatch + PC
(11)
where p is the trade-off parameter.
5

---

4.3 Compare with Graph Contrastive Learning
Although our objective function is different from the contrastive loss as shown in Equation (1), we find that the algorithmic philosophy of both is very similar. Here we analyze at the node level. Given graph G, the perturbation graphs G1 and G2 are obtained by augmenting G. If the attribute and context of node in G are corrupted in similar way and obtained two node views in G1 and G2. The cost between these two views quite small (almost zero) and thus the optimal transport plan yields a high probability of matching between these two node views. With Equations (9) and (10), the model GALOPA calibrates the matching probability and cost of the corresponding node representations in the output space, which is actually making the representations of two similar nodes similar enough. And for two different nodes! and & of G. the cost between their corresponding node views in graphs 91 and G2 is relatively larger. This leads to the opposite correction, i.e., making the representation of two dissimilar nodes sufficiently dissimilar.
From the contrastive learning perspective, the above process is not inconsistent with its goals. But there is fundamental difference between graph transport alignment and graph contrastive learning: GALOPA directly utilizes calibration signal from the graph space. Precisely because of this signal, we do not have distinguish between positive and negative samples, like Maxwell's 's demon.
4.4 Complexity
The time complexity of the model GALOPA is mainly influenced by the optimization process of Equations (7) and (8). To optimize Equation (7), which contains the fused - term, we utilize a conditional gradient (CG) solver [21]. This solver necessitates the computation of gradient with nearly cubic time complexity at each iteration concerning the size of the graph, i.c. the number of nodes. On the other hand, Equation (8) with the Wasserstein term can be optimized using the Kaokhorn-Knopp algorithm [12], which highly time-efficient with a nearly square complexity.
Plan or Distance?
Thanks to the alignment of the plan and cost for the representation, as byprod- uct, we find that the OT distance between the optimal node representations Z' in Equation (11) is equal to the distance be- tween its corresponding graphs. This is due to the two losses (10) and (9) con- strain the optimal node representation to satisfy J [Z Zi) o (1 L(), A2) & T and ( Zz) = TÚ. respectively. This means that our losses can prompt the encoder to learn an isomet- ric embedding that preserves the distance between graphs, which is one of the pur- suits of the general representation model. Hence, we became interested in the ques- tion of who more important, distance or plan? How would the model perform if we drop the alignment the plan and cost but instead optimize the distance directly? this section, we assess and rationalize the role of the plan for graph structure data in our self-supervised framework. To compare the possible performance gap between distance and plan, instead of directly optimizing the plan, we construct new loss with distance as following
0.95
0.9
ACCURACY
0.75
0.7
6.6
diet
0.55
0.5
CITESEER
PROTEINS
MUTAG
Figure 4: Plan versus distance. Comparing mean graph/node classification accuracy between transport alignment loss and distance loss on datasets.
Laist = WW 92) W(Z, Zz)l
(12)
where |-1 denotes absolute value, and Wo G2) = min, Eng cx (x X
a) Eight (A(A A²") T T
We evaluate the performance of using the pretraining representations on 2 social network datasets, CORA and CITESEER [25] for node classification, and 2 graph classification data PROTEINS and

---

MUTAG from TUDataset [36] for graph classification. See Section 8 for detailed experimental configurations. Figure 4 reports the averaged node/graph classification accuracy results over the node/graph-Ievel datasets. The results suggest that the model using the plan as an objective signif- icantly outperforms the counterpart models using the distance. Although the experimental result may lead to 'surprise", it demonstrates that the plan is closer to the essence than the distance, for discrete structured data. The optimal transport formulation Equation (5) contains both matching and implicit structural information. If only the final distance is retained instead of capturing the two types of information separately, the learned representation may fail to align properly with the input element. Because the optimal transport plan for the discrete OT problem is not unique in general and the optimal distance may correspond to several plans.
6 Node Attributes or Edges?
Among the information encoded in a graph. the structure and node attributes are two crucial elements for representation learning. The basic requirement of the encoder is to preserve the topology structures and capture the vertex feature of graphs. Thus a prob- lem encountered in our self-supervised learning paradigm: if we try to calibrate the representations learned by the backbone encoder, which is more important, the edge structure or the node attributes? In other words, if the calibration signal from the in- put space contains only node attribute in- formation and completely ignores the ex- plicit edge connectivity, will the perfor- mance of the proposed model deteriorate significantly? The answer seems obvious it should be. But the case seems to be different. Let's take look the experiment below.
I pnO, arl
pro, ar1
Bppo, am0.5 I pr0, am0
0.6
0.83
0.23
0748
0.398
0.355
0.55
0.99
0.98
0.50
ACCURACY
CORA
CITESEER
PROTEINS
MUTAS
Figure 5: The mean graph/node classification accuracy on datasets under different values of parameter a.
As in the previous section, we performed the comparative experiments on four datasets CORA, CITESEER, PROTEINS, and MUTAG. Here we first consider the normal case of our loss function (i... P * 0). We set the value of the parameter o to adjust the bias of node attributes or edge connections for the plan in the graph space. If a = 1, the model takes into account only node attributes in the transportation plans. When o = 0, it integrates explicit edge information while completely ignoring the node feature. Figure 5 reports the results with different and shows surprising outcome: With only node attributes for the calculation of the plan, the model achieves outstanding performance to remove the implicit structure constraint term Liimsstee the performance of the model suddenly deteriorates dramatically.
all the datasets, even optimal some data. However, if we set p 0
This verifies that the constraint Liimsste necessary and the implicit structural information it captures does calibrate the encoder even in the case of missing explicit edge connection. It therefore inspires self-supervised graph learning: it may not be able to tell that edge information does not contribute to correction for significant performance gains, but it is perfectly feasible to use only node attributes as a calibration supervisory signal for backbone model. This is a practical and valuable finding since the number of edges in real-world graph dataset is much more than the number of nodes. The time and space complexity of the model can be reduced greatly if only the node information is used in the calculation of the correction signal while ignoring the edge connections.
7 Are the Transport Alignment Free from Positive/Negative Samples?
As shown in Equation (11), the proposed objective function does not distinguish whether the two different graphs/nodes are positive (negative) samples or not. Here, we want to show that the graph transport alignment strategy can be independent of the label invariance assumption. We conduct experiments below to see how different levels of perturbation affect the performance of GALOPA. When augmenting the graph, we fixed one of the augmentations as NoAug and the other augmentation
7

---

PROTEINS
MUTAG
CTEEEER
CORA
0.8
0, 0.766
0.766
0.756
0.762
0.733
0
0.903
0.901
0.901
0,902
0
0
0.739
0.737
0.741
0.74
0.742
0.037
0.833
0.827
0.627
0.82
Fosture Masièng Ratt
08
6
8
8
04
0,761
0.76
0.768
0.759
0,755
0.898
0.91
0.507
0.508
0.911
0.742
0.739
0.74
0.732
0.739
8
0.84
0.642
0.838
0.832
0.631
02
0.767
0.76
8
0.907
8
0.741
8
0.837
0.841
01
0.766
0.761
0.761
0.757
0.759
8
900
0:91
0.
900
0.91
0
5000
0.743
0.74
3.741
0.730
0.74
0.04
0.819
2.641
5.8
0.826
Perturbation
Perturbation
Edge Perturbation
Edge Perturbation Rate
Figure 6: The mean graph/node classification accuracy when contrasting with different perturbation rates under datasets. Fix one of the augmentations as NoAug and the other augmentation be the combination of edge perturbation and feature masking. Darker colors indicate better performance.
requires a hyper-parameter "aug ratio" that controls the portion of node attributes/edge that selected for perturbing. Note that different augmentation strategies can be combined. Since the computation of the optimal transport plan in this paper involves node attributes and edge, we perform two augmentation policies, edge perturbation and feature masking, with different augmentation rates on four datasets (i.e., CORA, CITESEER, MUTAG, and PROTEINS) as shown in Figure 6.
we find that the performance of our model does not change much even when the original graph is perturbed heavily. For example, even if eighty percent of the edges are removed while eighty percent of the node attributes are destroyed, the model's 's performance on the dataset CITESEER (0.742) is almost equal to the optimal result (0.743). Fluctuations of only zero point five to two percent are also observed on other data sets, such as one point three in PROTEINS data. Hence, it validates that the alignment of optimal transport between the source space and target space is indeed free from the label-invariant assumption.
From Figure 6
8 Comparison with the State-of-the-art Methods
In this section, we compare our proposed self-supervised pre-training framework, GALOPA, with state-of-the-ard methods the settings of unsupervised learning on graph/node classification. More results can be found in the Appendix.
Table I: Mean node classification accuracy (%) for supervised and unsupervised models. The highest performance of unsupervised models is highlighted boldface. OOM indicates Out-Of-Memory
Model
CORA
CITESEER
PUBMED
WIkICS
Amz- Comp.
Amz-Photo
Coautbor-CS
Average
MLP
47.92 0.41
49.31 1: 0.26
69.14 1: 0.34
71.98 1: 0.42
73.81 1 0.21
78.53 1 0.32
90.37 1 0.19
68.72 1 0.31 85.20 +: 0.39
GCN
81.54 0.68
70.73
0.65
79.16
0.25
93.02
0.11
86.51 + 0.54
92.42 + 0.22
93.03 + 0.31
DEEPWALK
70.72 1: 0.63
51.39
+: 0.41
73.27
1 0.86
74.42
0.13
85.68 1 0.07
89:40 1 0.11 89.68
84.61 :: 0.22 85.16 0.04
75.64 0.35
NODE2VEC
71.08 0.91
47.34
0.84
66.23
0.95
71.36
84.41
GAE
71.49 1: 0.41
65.83
0.40
72.23
1 0.71
73.97
1 0.16
85.27 1 0.19
91.62 1 0.13
90.01 1: 0.71
78.63 1. 0.39
77.31 1.02
0.24
75.85
0.62
75.56
1:
92.13 0.16
DGr
82.34 0.71
71.83
+: 0.54
76.78
0.31
75.37
4 0.13
84.01
: 0.52
91.62 +: 0.42
92.16 :: 0.62
82.02 0.46
GMI
82.39 0.65
71.72
1: 0.15
79.34
1.04
74.87
1 0.13
82,18 1 0.27
90.68 1 0.18
00M
MVGRI.
83.45 0.68
73.28
0.48
80.09
0.62
77.51
0.06
87.53
91.34
92.11
GRACE
81.92 1 0.89
71.21
1. 0.64
80.54
1 0.36
78.
0.10
86.35
1 0.44
92.15 1 0.25
92.91 1: 0.20
83.32 1 0.41
GCA
82.38
0.47
71.51
0.32
80.89
0.28
78,
+ 0.36
87.83
0.26
92.33
+ 0.68
92.64 0.34
83.70 0.39
BGRL
81.30
0.54
72.06
1: 0.63
80.52
1. 0.30
76.13
1 0.18
89.09
0.51
92.15
1 0.32
92.33
0.39
83.37
0.41
GALOPA
84,21 0.30
74.34
0.18
84.57
0.34
81,23
1. 0.19
88.65 1 0.11
92.77 1 0.40
93.04
0.25
85.54 0.25
8.1 Experimental Setup
Datasets. We analyze the quality of representations learned by GALOPA on node and graph classifi- cation benchmarks. For node classification, we evaluate the performance of using the pretraining representations on 7 benchmark graph datasets, namely, CORA, CITESEER, PUBMED [25] and Wiki-CS, Amazon-Computee
Amazon-Paae -hoto, and Coauthor-CS [47]. For graph classification, follow GRAPHCL [72] to perform evaluations on 6 graph classification data NCI1, PROTEINS, DD, MUTAG, COLLAB, and IMDB-B from TUDataset [36].
Baselines. For node-level tasks, we adopt three types of baselines: 1) Supervised learning methods, including MLP and GCN [25]; 2) Graph embedding methods, including DEEPWALK [42] and
8

---

NODE2VEC [17]; 3) Graph contrastive learning methods, including GAE, VGAE [24]. DGI [58], GMI [41], MvGRL [19], GRACE [77]. GCA [78], and BGRL [55]. For graph-level task, we evaluate the performance of GALOPA in terms of the linear classification accuracy and compare it with 1) two supervised learning methods, including GCN [25] and GIN [69]] 2) seven kernel-hased methods, including SP [5], GK [49], WL [5], WLPM [39], FGW [56], DGK [70], and MLG [26]; 3) three unsupervised methods, including NODE2V EC [17]. SUB2 EC [1], GRAPH2 VEC [37]; 4) five recent SOTA supervise learning methods based contrastive learning, including INFOGRAPII [52],
GRAPICL [72], AD-GCL [53], JOAOv2 [73], RGCL [28] and SIMGRACE [66].
Protocol. We follow the standard evaluation protocol of previous state-of-the-an graph self- supervised learning approaches at the graph and node levels, respectively. Specifically, for graph classification, we report the mean 10-fold cross- cross- validation accuracy after 5 runs followed by linear SVM. The linear SVM is trained by applying cross-validatio is reported. For node classification, we report the mean accuracy on the test set after 50 runs of training followed by a linear neural network model. For the graphs (nodes) datasets, we randomly split the data, where 80%/10%//0% (10%/10%%/80%% of graphs (nodes) are selected for the training, validation, and test set, respectively.
on training data folds and the best mean accuracy
Implementation Details. In the experiments, we use the Adam optimizer [23] with learning rate tuned in {0.0001, 0.001, 0.013. The optimization routine and the convergence analysis are summarized in Appendix B. We conduct the experiment with the trade-off parameter P and o, the parameter C of SvM. batch size in the sets {10 3, 10 ..... 102, 10 {0, o.,,..., ., 0.9, 1}. (10-3 ... ) {16, 64, 128, 256, 512), respectively. To perform graph augmentation, we use 4 types of operations: Edge Perturbation, Feature Masking, Node Dropping. and Graph Sampling. Our model is implemented with Pytorch Geometric [13] and Deep Graph Library [63].
Table 2: Supervised and unsupervised representation learning classification accuracy (%) along with average accuracy of the algorithms on TU datasets. Bold indicates the best performance for unsupervised methods on each dataset. '-' means that the results are unavailable.
Model
PROTEINS
DD
MUTAG
NCI1
COLLAB
IMDB-B
Average
GCN
74,92 0.33
76.24 = 0,14 78.91
85.63 + 0.24
80.20 + 0.14
79.01 : 0.18
70:45 : 0.37
77.74 0.23 80.22 0.25
GIN
76.28 0.28
0.13
89.47 0116
82.75
80,23
0.19
73.70 0.60
SP
75.07 0.54
>id
85.25 + 0.24
73.53 +
55.62 0.02
GK
71.67 + 0.55
78.53 = 0.03
81.71 + 0.21
66.06 + 0.12
71.81 : 0.31
65.93 = 0.10
72,61 +: 0.22
WL
72,92 +: 0.56
79.78
4 0.36
80.76 + 0.30
80.01
+ 0.50
69.30 : 0.42
72.30 :: 0.44
75.84 1: 0.43
WLPM
0.38 78.79
87.13 0.42
86.32
FGW
88.34 + 0.12
86.24 + 0.31
62.97 : 0.24
DGK
73,21 0.61
74.79 4 0.32
87,51 + 0.65
79.98 + 0.36
64.43 1 0.48
67.09 + 0.37
74.50 +: 0.46
41.23 0.27
>1d
87.94 + 0.16
>1d
66.67
NODE2VEC
57.58 0.36
72.62 # 1.02
$4.93 +: 0.16
$6.12
0.02
50.25
0.09
SUB2VEC
53,06
54.33
+ 0.24
61.17 + 1.59
52.82 + 0.15
55,26 : 0.15
55.34 1:24=00 0.15
55,33 0.47
GRAPH2VEC
73.33
79.32 + 0.29
83.28 + 0.93
73.21 + 0.18
71.10 + 0.54
0.05 71.16
75.23 +: 0,36
INFOGRAPH
0.331
72.85
1.78
89.01 + 1.13
76.20 + 1.06
70.05 + 1.13
73.03
0.87
75.93 1.04
GRAPHCL.
74.39 0.45
78.62
0.40
86.80
1.34
77.87 +
71.36
71.14 0.44
76.69
0.69
AD-GCL
73,28
0.87
88.74 - 1.85
73.91 + 0.77
72.02 : 0.56
70:21 = 0.68
75.65 1: 0.86
JOA0V2
0.51
77.32 - 0.29
87.17 + 1.09
78.40
1: 0.17
69.19 :: 0.16
70.37 + 0.37
76.09 +: 0.43
RGCL
75.03
78.86
0.48
87.66
1.01
78.14
70.92
0.65
71.85
0.84
77.07 0.74
SIMGRACE
75.23 1.23
77.45
= 1.03
89.27 - 1.39
79.10
1: 0.25
71.37
2 0.44
71.45
1:45::00 0.29
77.31 + 0.59
GALOPA
76.93 1: 0.18
83.87 = 0.42
91.11 + 1.27
77.86 +: 0.36
73,20 1 0.37
70.72 : 0.48
78.94 0,51
8.2 Performance Comparison
Performance under Node-level. Table I reports the averaged results over the node-level datasets. Comparing the results in Table 1, we have the following major observations. The proposed method outperforms the state-of-the-ar self-supervised models significantly and even exceeds the supervised models on several datasets. For example, on PUBMED, GALOPA achieves 84.57% accuracy, which 3.68% relative improvement over previous state-of-the-arr unsupervised algorithms. When compared to supervised baselines, it outperforms strong supervised baselines: On CORA, CITESEER and PUBMED benchmarks we observe 2.67%, 3.61% % and 5.41 % relative improvement over GCN, respectively. On Coauthor-CS, the proposed unsupervised method shows competitive performance compared to the supervised models. Tabel 1 lists the average accuracy of 7 benchmark datasets, from which GALOPA achieves the best performance as well. For example, our proposed GALOPA

---

outperforms the unsupervised SOTA baseline SIMGRACE by 1.84% on average, and even outperforms supervised GCN by 0.34%. These results further validate that calibrating the backbone model by optimal transport alignment can produce expressive and generalizable representations.
Performance under Graph-level In this section, examine whether the proposed GAL.OPA performs better than state-of-the-art methods at graph-level datasets. The results of supervised learning baselines and unsupervised methods are reported in Table 2. The results shown in Table suggest that GALOPA achieves tate-of-the-an results with respect to unsupervised models. For example, on DD it achieves 83.87% accuracy, a 4. 4.09% relative improvement over the previous sfate-of-the-ar baselines. For kernel methods, our approach achieves better performance on most datasets. When compared to supervised baselines individually, our model outperforms GCN in out of 6 datasets and outperforms GIN in 3 out of 6 datasets, c.g., a 1.64% relative improvement on GIN for the NCT1 dataset. Our approach outperforms the state-of-the-art graph contrastive learning approaches. For example, compared to SIMGR ACE,, which is one of the best SOTA methods, GALOPA has a relative improvement of 1.63% on average across all datasets. GALOPA outperforms GRAPHCI. and INFOGRAPH with a relative improvement of 2.25% and 3.01% % on average, respectively. To summarize, our newly proposed GALOPA for graph self-supervised has achieved SOTA performance.
Discussion
Conclusion. In this paper, we investigated the self-supervised graph learning problem, addressing the challenges posed by label-invariant issues in contrasting graph learning. Unlike cxisting methods that adopt contrastive or distance-based regularization approaches, we propose novel paradigm based on optimal transport for self-supprrvied graph learning. Our approach focuses on aligning optimal transport plans between the graph space and the representation space. By aligning the transport plans, our method enforces the backbone model to learn representations that precisely preserve the matching relationships in the original graph space. Our observations reveal several noteworthy findings: (i) The optimal transport plan serves as a more informative calibration signal for the encoder compared to the transport distance, capturing essential characteristics; (ii) It is feasible to utilize only node attributes as correction signal for the backbone model, without relying on edge information; (iii) Our proposed graph self supersupee model eliminates the need to distinguish between positive and negative samples and overcomes the label-invariant assumption; Furthermore, extensive experiments conducted on multiple benchmark datasets demonstrate the state-of-the-ar performance our proposed framework in terms of generalizability and robustness.
Limitations and Future Work. Although the transport plan opens the door for direct communication between the input graph space and the output representation space, it also becomes computational bottleneck for the model to some extent due to the limitation of optimal transport computation complexity. To reduce the time complexity, we can utilize the properties of the proposed model and/or the scaling optimal transport techniques that can reduce the time complexity from cubic to square or even to linear, we provide 4 ways to do this below: (i) Unlike general OT settings, where the two graphs are typically quite different and the matching relationship between them completely unknown, the difference between the original and augmented graphs in GALOPA is quite small and the matching relations for subgraph components except with different part (i.e., complementary set of difference part) is known. This means that we can utilize the matching prior to reduce the computational cost. Hence, we can split the difference part with its neighborhood from the two graphs and compute the optimal transport plan only for that part. Since the percentage of that part is very small, it can greatly reduce the time complexity; (ii) According to the observation in Section 6, we can avoid the cubic complexity of optimizing GW by using only the node attributes for computing the optimal plan in graph space, while retaining similar performance with near-square time complexity; (ii) Alternatively,
can reduce the computational cost by utilizing sparsity [27] or graph partitioning [10, 67]. In particular, we can employ the most recent work on linear optimal transport [9, 38), which computes FGW term and/or Wasserstein term in linear time; (iv) We have the option to combine the aforementioned methods. For instance, by merging insights from the first point, a significant portion of subgraph pairs acquired via graph partitioning in the third point turns out to be identical. This realization can further pare down the complexity of partitioning methods.
As the main goal of this paper is to propose an alternative self-supervised graph learning paradigm beyond the label-invariant assumption that accurately links/communicates the input and we leave the scalability issuc as our future work.
output spaces,
10

---

Acknowledgments and Disclosure of Funding
We thank Edouard Pauwels and Samuel Vaiter for their valuable work and for proving the convergence of the derivatives of -inkhorn-Knopp. We also thank the anonymous reviewers for their constructive suggestions. This project was in part supported by the following projects: the National Natural Science Foundation of China (No.62032) NN.66032013, No.92267206); Singapore Institute of Technology Ignition Grant (No. (oo.R-1E2-A455-000))
References
[1] Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learning for subgraphs. In Pacific-Asia Conference on KDDM, pages 170-182. Springer, 2018.
[2] Jonas Adler and Sehastian Lunz. Banach wasserstein gan. Advances in Neural Information Processing Systems, 31, 2018.
[3] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in Neural Information Processing Systems, 14, 2001.
[4] Nicolas Bonneel, Michiel Van De Panne, Sylvain Paris, and Wolfgang Heidrich. Displacement interpolation using lagrangian mass transport. In Proceedings of the 201 SIGGRAPH Asia Conference. pages 1-12, 2011.
[5] Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernlls on graphs. In IEEE International Conference on Data Mining, pages 8 pp--. IEFE, 2005.
[6] Xuheng Cai, Chao Huang, Lianghao Xia, and Xubin Ren. LightGCL: Simple yet effective graph contrastive learning for recommendation. In International Conference on Learning Representations, 2023.
[7] Jiezhang Cao, Langyuan Mo, Yifan Zhang, Kui Jia, Chunhua Shen, and Mingkui Tan. Multi- marginal wasserstein gan. Advances in Neural Information Processing Systems, 32, 2019.
[8] Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph rep- resentations. In Proceedings of the AAAI Conference on Artificial Intelligence, number 2016.
[9] Yidong Chen, Chen Li, and Zhonghua Lu. Computing wasserstein-p distance between images with linear cost. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 519-528, 2022.
[10] Samir Chowdhury, David Miller, and Tom Needham. Quantized Fromov-wasserstein In Machine Learning and Knowledge Discovery in Databases, pages 81 1-877. Springer, 2021.
[11] Nicolas Courty, Rémi Flamary, Amaury Habrard, and Alain Rakotomamoniy. Joint distribution optimal transportation for domain adaptation. Advances in Neural Information Processing Systems, 30, 2017.
[12] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems, 26, 2013.
[13] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint /903.0/903.022
2019.
[14] Gao, Xiao Huang, and Jundong Li. Unsupervised graph alignment with wasserstein distance discriminator, In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 426 435, 2021.
[15) Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and Applications, 13:113-129 2010.
[16] Amur Ghose, Yingxue Zhang, Jianye Hao, and Mark Coates. Spectral augmentations for graph contrastive learning. aoxivv23022.02000 2023.
[17] Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 855-864, 2016.
[18] Xiang Gu, Yucheng Yang. Wei Zeng, Jian Sun, and Zongben Xu. Keypoint-guided optimal transport with applications heterogeneous domain adaptation. Advances in Neural Information Processing Systems, 35:14972-149985 2022.

---

[19] Kaveh Hassani and Amir Hosein Khasahmadi, Contrastive multi representation learning on graphs. In Proceedings of the International Conference on Machine Learning, pages 4116-4126.
PMLR, 2020.
[20] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs.
Advances in Neural Information Processing Systems, 33:22118 18:2211,-- 2020.
[21]
Projection- sparse convex optimization. In Proceed- ings of the International Conference on Machine Learning, pages 427-435. PMLR, 2013.
Martin Jaggi. Revisiting
[22] Dongki Kim, Jinheon Back, and Sung Ju Hwang. Graph self-supervised learning with accurate discrepancy learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint urXiv:1412.6900 2014.
[24] Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv: 2016.
[25] Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv: I /20.6609.00222 02907, 2016.
[26] Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. Advances in Neural Information Processing Systems, 29, 2016.
[27] Mengyu Li, Jun Yu, Hongteng Xu, and Cheng Meng- Efficient approximation of gromov- wasserstein distance using importance sparsification. Journal of Computational and Graphical Statistics, pages 1-12, 2023.
[28] Sihang Li, Xiang Wang. An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In Proceedings of the International Conference on Machine Learning, pages 13052-13065, 2022.
[29] Lu Lin, Jinghui Chen, and Hongning Wang. Spectral augmentation for self-supervised learning on graphs. arXiv preprint arXiv:2210.0066 2022.
[30] Huidong Liu, Xianfeng Gu, and Dimitris Samaras. Wasserstein gan with quadratic transport cost. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 4832 4842, 2019.
[31] 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, editors, Advances in Neural Information P Processing Systems, 2022.
[32] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in Neural Information Processing Systems, 35: 136-13355 2022.
[33] Facundo Mémoli. Spectral gromov- wasserstein distances for shape matching. In Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops, pages 256-263. IEEE, 2009.
[34] Facundo Mémoli. Gcromov-waseerster distances and the metric approach to object matching. Foundations of Computational Mathematics, 11:417-487, 2011.
[35] Gaspard Monge. Mémoire sur la théorie des déblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., pages 666-704, 1781.
[36] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv:2007.0m 00660, 2020.
[37] Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu. and Shantanu Jaiswal. Graph2vec: Learning distributed representations of graphs. 17X1v:1007.05005, 2017.
[38] Dai Hai Nguyen and Koji Tsuda. On a linear fused gromov-wasserstein distance for graph structured data. Pattrnn Recognition, 138:109351, 2023.
[39] Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node em- beddings for graph similarity. Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
12

---

[40] Edouard Pauwels and Samuel Vaiter. The derivatives of sinkhorn -inhhom-knopp converge. SIAM Journal on Optimization, 33(3):149-11517, 2023.
[41] Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang. Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pages 259-270, 2020.
[42] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 701-710, 2014.
[43] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov-wasserstein averaging of kernel and distance matrices. In Proceedings of the International Conference on Machine Learning, pages 2664-2672. PMLR, 2016.
[44] Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, I 1((-66)335-607, 2019.
[45] Meyer Scetbon and Marco Cuturi. Linear time sinkhorn divergences using positive features. Advances in Neural Information Processing Systems, 33:13468- 2020.
[46] Thibault Séjoumé, François- Vialard, and Gabriel Peyré. The unbalanced gromov wasserstein distance: Conic formulation and relaxation. Advances in Neural Information Processing Systems, 34:8766-877 (7777,67777.-11 2021.
[47] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. 18X 2018.
[48] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[49] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Arlificial Intelligence and Statistics, pages 488-495. PMIRR, 2009.
[50] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[51] Justin Solomon, Fernando De Goes, Gabriel Peyré. Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transportation on geometric domains. ACM Transactions on Graphics, 34(4):1-11, 2015.
[52] Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi-supervised graph-level representation learning via mutual information maximization. arXiv: 00000, 2019.
[53] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation to improve graph contrastive learning. Advances in Neural Information Processing Systems, 34: 15920-15933, 2021.
[54] Jianheng Tang, Weiqi Zhang, Jiajin Li, Kangfei Zhao, Fugee Tsung, and Jia Li. Robust attributed graph alignment via joint structure learning and optimal transport. arXiv preprint arXiv:2301.12722 2023.
[55] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In International Conference on Learning Representationss 2022.
[56] Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs. In Proceedings of the International Conference on Machine Learning, pages 6275-6284. PMLR, 2019.
[57] Vayer Titouan, levgen Redko, Rémi Flamary, and Nicolas Courty. Co-optimal transport. Advances in Neural Information Processing Systems, 33:1 33:17559-17570, 2020.
[58] Petar Velickovic, William Fedus, William Hamilton, Pictro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. International Conference Learning Representations, 2019.
[59] Cédric Villani al. Optimal transport: old and new, volume 338. Springer, 2009.
13

---

[60] Cédric Vincent- Sinent-Cuaz, Rémi Flamary. Marco Corneli, Titouan Vayer, and Nicolas Courty. Semi- relaxed Fromov-wassersie divergence and applications on graphs. In International Conference on Learning Representations, 2022.
[61] Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1234- 2016.
[62] Haonan Wang. Jieyu Zhang. Qi Zhu, and Wei Huang. Can single-pass contrastive learning work for both homophilic and heterophilic graph? arXiv preprint arXiv:2211. 2022.
[63] Minjie Yu Wang- Deep graph library: Towards efficient and scalable deep learning on graphs. In International Conference on Learning Representations Workshop on Representation Learning on Graphs and Manifolds, 2019.
[64] Yejiang Wang, Yuhai Zhao, Zhengkui Wang, and Meixia Wang. Robust self-supervised multi- instance learning with structure awareness. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10218-10222 2023.
[65] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International Conference on Machine Learning. pages 6861-6871. 1. PMLR, 2019.
[66] 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, pages 1070-1079, 2022.
[67] Hongteng Xu, Dixin Luo, and Lawrence Carin. Scalable wrsser-wassrsttein learning for graph partitioning and matching. Advances in Neural Information Processing Systems, 32, 2019.
[68] Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. Gromov-wasserstinn learn- ing for graph matching and node embedding. In Proceedings of the International Conference on Machine Learning, pages 6932-6941. PMLR, 2019.
[69] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv: httv:/810.000 810.00826, 2018
[70] Pinar Yanardag and SVN Vishwanathan. Deep graph kernlls. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1365-1374, 2015.
[71] Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. Autogel: Auto- mated graph contrastive learning via learnable view generators. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8892-8900, 2022.
[72] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5555 52232, 2020.
[73] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. Marina Meila and Tong Zhang, editors, Proceedings of the International Conference on Machine Learning, pages 12121-12132. PMLR, 18-24 Jul 2021.
[74] Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi-supervised graph classification. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[75] Yuhai Zhao, Yejiang Wang, Zhengkui Wang, and Chengqi Zhang. Multi-graph multi-label learning with granllatyyl labeling. In Proceedings of the 27th ACM SIGKDD Conference
on Knowledge Discovery & Data Mining, pages 2327-2337, 2021.
[76] Xin Zheng, Yixin Liu, Shirui Pan, Miao Zhang, Di Jin, and Philip S Yu. Graph neural networks for graphs with heterophily: A survey. arXiv preprint arXiv:2202.0m 222:022022070822. 2022.
[77] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. arXiv:2006. 04 131, 2020.
[78] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, pages 2069-2080, 2021.
14


Reviews:
[{"review_id": "1CVIpM5CAe", "reviewer": "Reviewer_YJ1t", "summary": "In this paper, the authors study a new method \"GALOPA\" for self-supervised learning on graph. \n\nFor the two input views of graphs, they first compute the optimal transport plans w.r.t. fused GW distance between input graphs G1 and G2; for the corresponding outputs Z1=f(G1), Z2=f(Z2) of GNN f(), they compute the optimal transport plan w.r.t. a tunable cost J(Z1, Z2). They propose two losses to enforce the consistency between two plan matrices and two cost matrices. \n\nThey also propose some interesting findings through empirical experiments.", "questions": "### Minor\n\n1. The concept of “maximum similarity” in Line 35 is not well explained.\n2. Could you further explain why it \"is challenging for discrete graph structures to know (or assume) beforehand that the two views are positive/negative samples\" in Line 92-93. Solving it seems an important contribution of the paper, while I don't get it here.\n3. It is better to directly introduce the concept of fused GW distance in Section 3, and therefore better convey the idea in Section 4.1.\n4. Some strong claims (in Section 5-7) are made based on experiments on small datasets. Can the authors add some medium to large datasets, e.g. from Open Graph Benchmark (OGB), to the experiments?\n\n\n### Major\n\n1. The implementation of \"GALOPA\" is not clearly introduced. For me, the authors propose two new losses, while the backbone can be any models for obtaining graph node embedding. I don't understand why in the experiments we contrast some backbone models (MLP, GCN) to \"GALOPA\".\n2. As mentioned, the analysis of computational complexity is not provided. Please also compare it to common baseline methods.\n3. The loss $L_{match}$ needs more discussions. Specifically, I feel it is non-trivial to discuss the differentiability of $\\pi_z^*(Z_1, Z_2)$. It is hard to obtain the explicit form of the gradient of it w.r.t. $Z_i$, and I'm not sure whether the auto differentiation in common DL package can ensure the gradient in use will exactly be the real gradient of $\\pi_z^*(Z_1, Z_2)$, considering the complex procedure of obtaining the OT plan.\n4. Can you further explain the claim in Line 236 that \"the OT distance between the optimal node representations Z∗ in Equation (10) is **equal** to the distance between its corresponding graphs\".\n    - Eqn. (10) is composed of two losses, so it is better to specify more clearly the \"OT distance between the optimal node representations\".\n    - Can you show the derivation why the \"OT distance\" is \"equal to the distance between its corresponding graphs\"?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- originality: \n    - This paper proposes a new type of loss based on **transport plan** for self-supervised learning on graph.\n\n- quality:\n    - The new framework they propose does work and can provide comparable performance to existing deep kernel methods.\n\n- clarity: \n    - They provide multiple illustrations to introduce the main ideas of different parts.\n\n- significance: \n    - This paper provides a new type of loss, which can be a good reference for self-supervised learning on graph.", "weaknesses": "- quality:\n    - The analysis of computational complexity is not provided. From my perspective it can be an issue since the cost for doing OT is high, especially for GW distance.\n    - The theoretical justifications for some claims are lacked. I also leave some questions below.\n    - Some empirical results may be unconvincing due to the small size of datasets. E.g., the experiments in Section 5-7.\n\n- clarity: \n    - Some concepts are not clearly illustrated. See the questions below.\n\n- significance: \n    - The lack of theoretical results and insignificant improvement can make the paper less attractive to audience in this theoretical field.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for constructive feedback and for describing our work as good reference for self-supervised learning and demonstrating interesting findings in the experiments. We respond to the reviewer’s concerns **below** and in the **global response above**.\n\n> **Q1. Large scale data in Section 5-7?**\n\nWe performed the experiments in Sections 5-7 on the dataset ogb-arxiv, which contains 169,343 nodes with 1,166,243 edges. We first partition the graph and compute the plan between subgraphs. We **perform self-supervised pre-training** with all training data and **supervised fine-tuning with 10% of them** then evaluate on the test sets, which is repeated for 10 times.\n\nIn **Section 5**, we compare the plan and distance. Table I records the node classification accuracies on the ogb-arxiv when pre-training using the Eqs. (10) and (11) as losses. \n\n*Table I. Plan versus distance on large-scale ogb-arxiv.*\n\n|  Algo.  | Test |\n| :--------: | :--------: |\n|   NoPretrain   | 0.512±0.31 |\n| Plan | **0.544±0.18** |\n| Dist | 0.527±0.26 |\n\n‘NoPretrain’ refers to direct fine-tuning without pre-training. We can find that using the plan as losses outperforms the counterpart using the distance, which is consistent with the conclusions in the paper.\n\nIn **Section 6**, we compare node attributes and edges. If $\\sigma=1$, the model takes into account only node attributes. When $\\sigma=0$, it integrates only edge. We set $\\rho = 0$ (or $\\rho \\neq 0$) to remove (or add) the implicit structure term $\\mathcal{L}_{(im)struc}$.\n\n*Table II. Results on ogb-arxiv under different values of parameters.*\n\n|  Para  | Test |\n| :--------: | :--------: |\n|   $\\rho=0, \\sigma=1$   | 0.523±0.24 |\n| $\\rho \\neq 0, \\sigma=1$ | 0.542±0.37 |\n| $\\rho \\neq 0, \\sigma=0.5$ | 0.544±0.34 |\n| $\\rho \\neq 0, \\sigma=0$ | 0.540±0.25 |\n\nFrom the table we can see similar conclusions to the paper.\n\nIn **Section 7**, we test the robusness of GALOPA. Table III records the performance  when both feature masking (vertical axis) and edge perturbations (horizontal axis) are used.\n\n*Table III. Results on ogb-arxiv with diffrent perturbation rate.*\n\n|  Aug Rate  | 0.1 | 0.2 | 0.4 | 0.6 | 0.8 |\n| :--------: | :---: | :--------: | :--------: | :--------: | :--------: |\n|   0.1   | 0.542±0.23 | 0.543±0.36 | 0.540±0.32 | 0.538±0.31 | 0.532±0.26 |\n| 0.2 | 0.543±0.30 | **0.544±0.27** | 0.544±0.18 | 0.543±0.35 | 0.538±0.45 |\n| 0.4 | 0.539±0.16 | 0.541±0.33 | **0.544±0.29** | 0.542±0.17 | 0.540±0.39 |\n| 0.6 | 0.534±0.38 | 0.539±0.19 | 0.543±0.26 | 0.542±0.32 | 0.539±0.19 |\n| 0.8 | 0.531±0.23 | 0.535±0.25 | 0.539±0.19 | 0.537±0.36 | 0.537±0.41 |\n\nWe can find that our model is robust on ogb-arxiv.\n\n\n> **Q2. Backbone (MLP, GCN) on experiment?**\n\nIn the experiments, our aim is not to contrast GALOPA with different backbones. Instead, we aim to assess the performance gap between GALOPA (with GNNs backbone) and established supervised methods (e.g., MLP algorithm [1] and GCN algorithm [2]). This comparison intends to reveal the performance difference between unsupervised GALOPA and the supervised approach.\n\n[1] Graph attention networks. STAT2017\n\n[2] Semi-supervised classiﬁcation with graph convolutional networks. arXiv2016\n\n\n\n> **Q3.  Analysis of computational complexity.**\n\nReviewer can refer to the *GQ2* in the $\\color{red}\\text{global rebuttal}$.\n\n\n> **Q4.  Differentiability of** $\\pi_Z^*(Z_1, Z_2)$.\n\nIt is difficult to derive the optimal closed-form solution for the Eq.(7) and the differentiation of $\\pi_z^*(Z_1, Z_2)$ with respect to $Z_i$ directly. To solve the problem, we use the Sinkhorn-Knopp algorithm [1] to iteratively approximate the optimal solution $\\pi_Z^*$, where the derivatives in each iteration step are solvable. Specifically, Sinkhorn-Knopp algorithm add an additional entropy regularizer and perform a scheme of alternating Sinkhorn projections: $\\pi^{(0)}=\\exp(-\\boldsymbol{J}(\\boldsymbol{Z}_1, \\boldsymbol{Z}_2)/\\lambda)$ and $\\pi^{(t+1)} = \\mathcal{S} (\\mathcal{T}(\\pi^{(t)}))$, where $t$ denotes the number of iterations, $\\lambda$ weights the regularization, $\\mathcal{S}(\\pi)=\\pi \\oslash(\\mathbf{1} \\mathbf{1}^{\\top} \\pi) \\odot(\\mathbf{1} \\boldsymbol{b}^{\\top})$ and $\\mathcal{T}(\\pi)=\\pi \\oslash(\\pi \\mathbf{1} \\mathbf{1}^{\\top}) \\odot(\\boldsymbol{a} \\mathbf{1}^{\\top})$, $\\odot$ denotes the Hadamard product and $\\oslash$ denotes element-wise division. As shown by [1], in the limit this scheme converges to a minimizer $\\pi^{(t)} \\stackrel{t \\rightarrow \\infty}{\\longrightarrow} \\pi^*$. Hence, the differential $\\partial\\pi^{(t)}/\\partial Z_i$ can be solved by the chain rule.\n\n[1] Sinkhorn distances: Lightspeed computation of optimal transport. NeurIPS2013\n\n> **Q5. Can you explain the claim that \"the OT distance between the optimal node representations** $\\boldsymbol{Z}^*$ **in Eq. (10) is equal to the distance between its corresponding graphs\" (Line 236)?**\n\nWe apologize for the distress caused by our lack of explanation here. Eq. (10) is obtained by adding the two loss (Eq. 9 and 8), which constrain the optimal node representation $\\boldsymbol{Z_i}^*$ to satisfy  $\\boldsymbol{J}(\\boldsymbol{Z_1}^*, \\boldsymbol{Z_2}^*)=\\sigma \\boldsymbol{K}(\\boldsymbol{X_1}, \\boldsymbol{X_2})+(1-\\sigma) \\boldsymbol{L}(\\boldsymbol{A_1}, \\boldsymbol{A_2}) \\otimes \\pi_\\mathcal{G}^*$ and $\\pi_\\mathcal{Z}^*(\\boldsymbol{Z_1}^*, \\boldsymbol{Z_2}^*) = \\pi_\\mathcal{G}^*$, respectively. Hence, the OT distance between the optimal node representations $\\mathcal{W}(\\boldsymbol{Z_1}^*, \\boldsymbol{Z_2}^*)=\\langle\\boldsymbol{J}(\\boldsymbol{Z_1}^*, \\boldsymbol{Z_2}^*), \\pi_\\mathcal{Z}^*(\\boldsymbol{Z_1}^*, \\boldsymbol{Z_2}^*)\\rangle$ is equal to the distance between its corresponding graphs $\\mathcal{W}_G(\\mathcal{G}_1, \\mathcal{G}_2)=\\langle\\sigma \\boldsymbol{K}(\\boldsymbol{X_1}, \\boldsymbol{X_2})+(1-\\sigma) \\boldsymbol{L}(\\boldsymbol{A_1}, \\boldsymbol{A_2}) \\otimes \\pi^*_G,\\ \\pi^*_G\\rangle$.\n\nWe place the remaining 3 questions Q6-Q8 below."}, {"review_id": "PIDxHxI3Uq", "reviewer": "Reviewer_zpGL", "summary": "This paper proposes a new paradigm for self-supervised graph learning  GALOPA based on optimal transport. It seeks to align optimal transport plans from graph space to node representation space instead of distance alignment in graph contrastive learning. The extensive experiments show that the optimal transport plan is more informative and overcomes the label-invariant assumption.", "questions": "- The authors can provide the algorithms concerning how to compute the transport plan （e.g. Sinkhorn-Knopp.)\n\n- The authors use gradient descent to optimize the Eq(12) instead of Sinkhorn-Knopp. I wonder whether the accuracy of those optimized methods will affect the results.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": " - The problem to overcome the label-invariant assumption in augmentation-based graph self-supervised learning is interesting and significant. The idea to align the transport plan between the graph space and representation space is novel and interesting. \n- The paper is well-organized and easy to follow. The introduction of related knowledge is very clear and helpful for understanding.\n- The experiment can validate its conclusion.", "weaknesses": "- The connection and difference between the two parts of Loss is not clear\n- The experiment is insufficient. It is better to add an ablation study on the two proposed losses to observe which part contributes much.\n- This paper just uses the optimal transport method for self-supervised graph learning, which cannot be considered as a great innovation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for describing our work as interesting and significant. We respond to the reviewers’ questions below.\n\n> **Q1. The connection and difference between the two parts of Loss is not clear.**\n\nThanks to the reviewer's suggestion, we describe the relationship between these two losses in more detail below. These two losses come from calibration of two aspects of the encoder: STRUCTURAL INFORMATION and MATCHING INFORMATION, both of which are expected to be captured in the output node representation of the encoder. $\\mathcal{L_{match}}$ force the encoder to preserve the matching relationship between graphs in the graph space by minimizing the discrepancy between the two transport plans. $\\mathcal{L_{(im)strc}}$ guide the encoder to learn a representation retaining structural information inside the graph by calibrating the cost matrix of node representations. Also from the optimal transmission perspective, these two losses focus on the optimal transport plan and the transportation cost, respectively, which together determine the optimal transport distance.\n\n\n> **Q2. Add an ablation study on the two proposed losses to observe which part contributes much.**\n\nAt the request of the reviewer here we perform loss ablation experiments. We compare the performance of the algorithms when using Eq. (8) and Eq. (9) alone as losses below\n\n*Table IV. Ablation study on the losses $\\mathcal{L_{match}}$ and $\\mathcal{L_{(im)strc}}$.*\n\n|  Loss  | Cora | CiteSeer | PROTEINS | MUTAG |\n| :--------: | :---: | :--------: | :--------: | :--------: |\n| $\\mathcal{L_{match}}+\\mathcal{L_{(im)strc}}$ | **0.842±0.30** | **0.743±0.18** | **0.769±0.18** | **0.911±1.27** |\n|   $\\mathcal{L}_{match}$   | 0.820±0.36 | 0.689±0.34 | 0.758±0.21 | 0.879±1.14 |\n| $\\mathcal{L}_{(im)strc}$ | 0.812±0.25 | 0.684±0.24 | 0.762±0.23 | 0.869±1.21 |\n\nFrom the table we can see that using only one loss alone leads to performance degradation, which verifies that each loss is indispensable. In addition we find that the plan matching loss $\\mathcal{L_{match}}$ gives relatively better performance on most datasets compared to the implicit structure loss $\\mathcal{L_{(im)strc}}$, which also suggests that the former may contribute more.\n\n\n\n> **Q3. Provide the algorithms concerning how to compute the transport plan (e.g. Sinkhorn-Knopp).**\n\nWe describe the optimization algorithms below.\n\nTo solve the FGW problem of Eq. (6), we optimize the transport plan with the conditional gradient (CG) solver. The conditional gradient algorithm [1] consists in solving a linearization $\\langle \\mathbf{X}, \\nabla_\\pi \\rangle$ at each iteration $r$. It can be solved by gradient descent with a direction $\\mathbf{X}^{(r)} - \\pi^{(r)}$, followed by a line search for the optimal step. The detail of the algorithm is summarized in Algorithm 1 in the Appendix.\n\nTo solve the Wassersttein problem of Eq. (7), in the paper we use the Sinkhorn-Knopp algorithm [2] to iteratively approximate the optimal solution $\\pi_z^*$. Specifically，Sinkhorn-Knopp algorithm add an additional entropy regularizer and perform a scheme of alternating Sinkhorn projections: $\\pi^{(0)}=\\exp(-\\boldsymbol{J}(\\boldsymbol{Z}_1, \\boldsymbol{Z}_2)/\\lambda)$ and $\\pi^{(t+1)} = \\mathcal{S} (\\mathcal{T}(\\pi^{(t)}))$, where $t$ denotes the number of iterations, $\\lambda$ weights the regularization, $\\mathcal{S}(\\pi)=\\pi \\oslash(\\mathbf{1} \\mathbf{1}^{\\top} \\pi) \\odot(\\mathbf{1} \\boldsymbol{b}^{\\top})$ and $\\mathcal{T}(\\pi)=\\pi \\oslash(\\pi \\mathbf{1} \\mathbf{1}^{\\top}) \\odot(\\boldsymbol{a} \\mathbf{1}^{\\top})$, $\\odot$ denotes the Hadamard product and $\\oslash$ denotes element-wise division. As shown by [2], in the limit this scheme converges to a minimizer $\\pi^{(t)} \\stackrel{t \\rightarrow \\infty}{\\longrightarrow} \\pi^*$. \n\n[1] Revisiting frank-wolfe: Projection-free sparse convex optimization. ICML2013\n\n[2] Sinkhorn distances: Lightspeed computation of optimal transport. NeurIPS2013\n\n\n\n> **Q4.  The authors use gradient descent to optimize the Eq. (12) instead of Sinkhorn-Knopp. I wonder whether the accuracy of those optimized methods will affect the results.**\n\nEq. (12) involves the Gromov-Wasserstein term rather than just the traditional Wasserstein term, and the Sinkhorn-Knopp algorithm is designed for Wassertein term and cannot be used to optimize the Gromov-Wasserstein term. We therefore use the conditional gradient (CG) solver, which often appears to optimize GW, to optimize Eq. (12). Thus, these two algorithms cannot be directly compared. Also as mentioned in the previous problem, for Eq. (7), which contains only Wasserstein terms, we optimize it with the Sinkhorn-Knopp algorithm."}, {"review_id": "7o8qVSP23m", "reviewer": "Reviewer_bARL", "summary": "In this submission, the authors proposed a new self-supervised method for graph representation learning. \nUnlike existing contrastive learning methods, the authors consider 1) the consistency between the optimal transport plan defined on the graph pairs and that defined on their node embeddings and 2) the consistency between the grounding cost defined on the graph pairs and the cost derived by the node embeddings.\nTaking these two consistency terms as the objective function, the authors learn the representation model, achieving encouraging performance in node classification and graph classification tasks.\nIn addition, detailed analytic experiments are designed, providing valuable insights for graph self-supervised learning.\n\n--- After rebuttal ---\n\nThanks for the authors' efforts in the rebuttal phase. Although the proposed method needs some modifications when dealing with heterophilic graphs, the methodology itself provides a new perspective of self-supervised learning for GNNs, and the experimental results are convincing. Therefore, my final score is \"borderline accept\".", "questions": "1. When applying the proposed method, if the graphs are augmented randomly in different batches/epochs, we have to compute the fused GW distance between the augmented graphs iteratively. If my understanding is correct, the computational complexity of the method will be very high. How to solve/mitigate this problem? \n\n2. For the node classification experiments in Table 1 and the analytic experiments in Figure 4, the authors seem to consider the homophilic graphs only. Could the authors test the proposed method on heterophilic graphs?\n\n3. In Tables 1 and 2, the authors compared the proposed method with other graph contrastive learning methods. Are all the methods use the same backbone GNN? If the methods use different GNNs, how to ensure the fairness of the comparison?", "limitations": "The high computational cost may limit the application of the proposed method.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is easy to follow. \n\n2. The analytic experiments are comprehensive. Some analytic results are interesting and can provide useful insights for the design of graph self-supervised learning methods.\n\n3. The idea of leveraging the OT-based consistency between raw data and latent representation is interesting and differs from existing graph self-supervised learning methods.", "weaknesses": "1. The sigma in the fused GW term and the rho in the objective function are key hyperparameters, which may impact the performance of the proposed method significantly. However, the authors neither show the robustness of the method to the hyperparameters nor discuss the selection mechanism of the hyperparameters.\n\n2. In my opinion, the computational complexity of the proposed method may be very high, which may limit the practical applications of the proposed method.\n\n3. Some implementation details are missed, e.g., the algorithms to compute the fused GW distance between graphs and the OT distance between node embeddings. Additionally, it would be nice if the authors could provide an algorithmic scheme to show the whole self-supervised learning pipeline.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for describing our work as interesting and for recognizing the valuable insights of our work for graph self-supervised learning. We respond to the reviewer’s concerns **below** and in the **global response above**.\n\n> **Q1. The sensitivity analysis of $\\sigma$ and $\\rho$, and discuss the selection mechanism.**\n\nFor the selection of $\\rho$ and $\\sigma$, we search the optimal configuration for them from the set {$10^{-3}, 10^{-2}, \\ldots, 10^2, 10^3$} and {$0, 0.1, 0.2, \\ldots, 0.9, 1$}, which is also described in the Implementation Details section (Line 350) of the paper. At the request of the reviewer, we conducted robustness experiments on these two parameters. The following table shows the average node classification accuracy on the dataset Cora for different values of the parameter $\\rho$ (vertical axis) and the parameter $\\sigma$ (horizontal axis). For ease of viewing, we have bolded the values corresponding to non-zero $\\rho$ and $\\sigma$.\n\n*Table V. The sensitivity analysis of GALOPA on data Cora to the hyperparameters $\\sigma$ and $\\rho$.* \n|  $\\rho$ vs. $\\sigma$  | 0 | 0.3 | 0.5 | 0.8 | 1 |\n| :--------: | :---: | :--------: | :--------: | :--------: | :--------: |\n| **0** | 0.813±0.35 | 0.809±0.26 | 0.801±0.38 | 0.784±0.22 | 0.776±0.30 |\n| $10^{-3}$ | 0.816±0.21 | ***0.823±0.18*** | ***0.834±0.31*** | ***0.836±0.37*** | ***0.838±0.30*** |\n| $10^{-2}$ | 0.814±0.27 | ***0.828±0.45*** | ***0.831±0.36*** | ***0.840±0.32*** | ***0.838±0.21*** |\n| $10^{-1}$ | 0.818±0.34 | ***0.830±0.31*** | ***0.829±0.31*** | ***0.839±0.43*** | ***0.842±0.34*** |\n| $10^0$ | 0.823±0.24 | ***0.834±0.26*** | ***0.835±0.15*** | ***0.838±0.20*** | ***0.841±0.27*** |\n| $10^1$ | 0.819±0.29 | ***0.838±0.40*** | ***0.834±0.38*** | ***0.833±0.27*** | ***0.832±0.38*** |\n| $10^2$ | 0.821±0.18 | ***0.826±0.29*** | ***0.829±0.34*** | ***0.841±0.14*** | ***0.839±0.38*** |\n| $10^3$ | 0.820±0.33 | ***0.824±0.36*** | ***0.833±0.26*** | ***0.832±0.28*** | ***0.841±0.31*** |\n\nFrom the table we can see that when we **remove the implicit structure constraint** $\\mathcal{L}_{(im)strc}$ ($\\rho=0$), the performance of GALOPA drops dramatically if we do not use the explicit edge structure ($\\sigma=1$) at the same time. Whereas, if we use the edge structure ($\\sigma<1$) to a greater extent, i.e., the smaller the $\\sigma$, the better performance of the algorithm. Additionally, we discuss the case where **only the node attributes are considered without using explicit edge structure** ($\\sigma=1$). In this case if we add implicit structure constraints ($\\rho \\neq 0$) we can get superior performance. \n\nCombining these two cases, it can be concluded that **implicit structural constraint** $\\mathcal{L}_{(im)strc}$ **do capture the internal structure of the graph**. Furthermore, we find that the algorithm is robust to the parameters $\\rho$ and $\\sigma$, which **fluctuate slightly for different values (>0)** of $\\rho$ and $\\sigma$.\n\n\n> **Q2. Provide the algorithms to compute the fused GW distance between graphs and the OT distance between node embeddings.**\n\nReviewer can refer to the *GQ1* in the $\\color{red}\\text{global rebuttal}$.\n\n\n> **Q3. Reduce the complexity of  computing the FGW between the augmented graphs iteratively?**\n\nReviewer can refer to the *GQ2* in the $\\color{red}\\text{global rebuttal}$.\n\n> **Q4. Could the authors test the proposed method on heterophilic graphs?**\n\nThanks to the reviewers for the suggestions. However, our proposed algorithm mainly focuses on homophilic rather than heterophilic graph. If we want to process heterophilic graph well we may need to make some modifications to the algorithm, which may consume considerable time. Specifically, the implicit structural constraint $\\mathcal{L_{(im)strc}}$ of the algorithm contains an assumption on homophilic graphs, i.e., the implicit structure captured by term $\\mathcal{L_{(im)strc}}$ has the property that \"**similar nodes tend to be neighborly**\", which is contrary to the explicit edge connectivity assumption of heterophilic graph, i.e., **neighboring nodes are dissimilar**.\n\n\n\n> **Q5. Are all the methods use the same backbone GNN? If the methods use different GNNs, how to ensure the fairness of the comparison?**\n\nYes, as mentioned by the reviewer, in order to ensure experimental fairness, we try to ensure that each algorithm uses backbone encoders with the same implementation (e.g., the number of layers and dimensions of the hidden layers).\n"}, {"review_id": "t6aJCawZgV", "reviewer": "Reviewer_q42Z", "summary": "The paper proposes a novel paradigm for self-supervised graph learning based on optimal plan alignment named GALOPA, which leverages optimal transport theory to align the optimal transport plans for graphs and node representations, resulting in an improvement in the quality of graph representations. Unlike existing methods, GALOPA does not require generating positive/negative sample pairs, simplifying the data requirements. GALOPA further introduces a new loss to enable the sharing of the exact matching information from graphs space to the representation space. The paper experimentally shows that GALOPA achieves state-of-the-art performance and robustness compared to previous methods on various benchmark datasets.", "questions": "1、\tThe authors should provide more detailed information about the experimental setup, such as the size of the graph dataset used.\n2、\tThe authors can provide a reasonable explanation for why using only node attributes yields the best performance in Section 6.\n3、\tPlease review the paper and ensure that all the characters are in black color.\n4、\tIn Figure 5, ‘ACCUTACY’ -> ‘ACCURACY’.\n", "limitations": "The authors have well discussed the limitations of their model and possible solutions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThe problem studied is an interesting and intuitive one that directly exploits and aligns the matching information common to both input and output spaces. This seems to combine the ideas of both graph contrastive learning and graph auto-encoders, while avoiding the limitations of both: the former needs to distinguish between positive and negative samples, while the latter needs to reconstruct the original signals (e.g. structure or node features), where the comparison takes place in the same space (graph space). The idea seems to be useful and extendable to other types of data (e.g. images or text) for self-supervised representation learning.\n2.\tThe paper is well written and organized. I can easily understand the motivation and the proposed method. The illustrations can give readers a deeper understanding.\n3.\tThe experimental design is good, and sections 5 and 6. They explore the rationality of the proposed methodology and dissect its validity. The interpretation of the experimental results is convincing. The results in section 8 verify that the algorithm is state of the art.\n", "weaknesses": "1.\tThe time complexity analysis may be better placed in the text than in the appendix.\n2.\tSome typos: L54 (generate->generating), L155 (node->nodes), L310 (require->requires).\n3.\tThe authors should conduct Wilcoxon signed rank test to verify proposed method in Table 1-2.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for describing our work as interesting and demonstrating superior performance and good design for the experiment. We respond to the reviewers’ questions below.\n\n\n> **Q1. The time complexity analysis may be better placed in the text than in the appendix.**\n\nThanks for pointing this out. We will add time complexity analysis to the paper. In addition we have analyzed more ways to reduce time complexity in *GQ2* of the $\\color{red}\\text{global rebuttal}$.\n\n\n> **Q2. Some typos: L54 (generate->generating), L155 (node->nodes), L310 (require->requires). In Figure 5, ‘ACCUTACY’ -> ‘ACCURACY’.**\n\nThanks for your valuable feedback on the typos. We will correct these errors and carefully check for any other errors that may exist in the paper.\n\n> **Q3. Conduct Wilcoxon signed rank test to verify proposed method in Table 1-2.**\n\nUpon the request of the reviewer, we performed Wilcoxon signed rank test on GALOPA and baseline on the node classification dataset and the graph classification dataset, respectively. Table VI and VII report the p-values for the Wilcoxon signed-ranks test for GALOPA at 0.05 significance level with node classification baselines and graph classification baselines, respectively. If the p-value is small, it can reject the idea that the difference is a due to chance and conclude that the population has a median distinct from the performance of baseline model.\n\n*Table VI.  The p-values for the Wilcoxon signed-ranks test on **node** classification datasets at 0.05 significance level.* \n|  GALOPA vs.  | p-value |\n| :--------: | :---: |\n|   BGRL   | 0.015 |\n| GCA | 0.007 |\n| GRACE | 0.007 |\n| MVGRL | 0.007 |\n| DGI | 0.007 |\n| VGAE | 0.007 |\n| GAE | 0.007 |\n| Node2Vec | 0.007 |\n| DeepWalk | 0.007 |\n\n*Table VII.  The p-values for the Wilcoxon signed-ranks test on **graph** classification datasets at 0.05 significance level.* \n|  GALOPA vs.  | p-value |\n| :--------: | :---: |\n|   SimGrace   | 0.078 |\n| RGCL | 0.078 |\n| Java2 | 0.046 |\n| AD-GCL | 0.015 |\n| GranpCL | 0.078 |\n| InfoGraph | 0.078 |\n| Graph2Vec | 0.031 |\n| Sub2Vec | 0.015 |\n| DGK | 0.031 |\n| WL | 0.078 |\n| GK | 0.015|\n\nAs show in the table, GALOPA achieves superior performance against all the baselines.\n\n\n\n> **Q4. Provide more detailed information about the experimental setup, such as the size of the graph dataset used.**\n\nThanking the reviewer q42Z for the suggestions, we add the description of the node classification and graph classification datasets used as follows\n\n*Table VIII. The statistical information of node classiﬁcation datasets.*\n|  Dataset  | Nodes | Edges | Classes | Feat. |\n| :--------- | ----: | -----: | ------: | ----: |\n|   Cora   | 2708 | 10556 | 7    | 1433 |\n|  CiteSeer  | 3327 | 9228  | 6    | 3703 |\n|  PubMed  | 19717 | 88651 | 3    | 500  |\n| WikiCS | 11701 | 216123 | 10 | 300 |\n|   Coauthor-CS   | 18333 | 327576 | 15   | 6805 |\n| Amz-Comp. | 13752 | 574418 | 10   | 767  |\n| Ama-Photo | 7650 | 287326 | 8    | 745  |\n\n*Table IX. The statistical information of graph classiﬁcation datasets.*\n|  Dataset  | Graphs | Avg. Nodes | Avg. Edges | Classes |\n| :--------- | ----: | -----: | ------: | ----: |\n|   PROTEINS   | 1113 | 39.06 | 72.82 | 2 |\n| DD | 1178 | 284.32 | 715.66 | 2 |\n| MUTAG | 188 | 17.93 | 19.79 | 2 |\n| NCI1 | 4110 | 29.87 | 32.30 | 2 |\n| COLLAB | 5000 | 74.49 | 2457.78 | 3 |\n| IMDB-B | 1000 | 19.77 | 96.53 | 2 |\n\nWe'll add it to the paper.\n\n> **Q5. Provide a reasonable explanation for why using only node attributes yields the best performance in Section 6.**\n\nThe main reasons why good performance can be achieved by utilizing only the node attributes in Section 6 are as follows: 1) The constraint $\\mathcal{L_{(im)strc}}$ aims to correct the encoder so that the output node representations capture the implicit structure information. Thus, it also provides correction information to the encoder when explicit structural information (edges) is missing. 2) This implicit structural information may not only manifest the explicit structure, but in addition provide abundant auxiliary relation. Thus the best performance may be obtained even if only node attributes are used.\n\n> **Q6. Please review the paper and ensure that all the characters are in black color.**\n\nThanks for pointing this out. We used red markers for some key concepts to make them easier for the reviewers to read, and we'll change those colors back to black afterwards.\n"}]

Author rebuttal:
We sincerely thank all the reviewers for their insightful feedback.

Here we respond to common/main concerns raised by reviewers.

> **GQ1. The algorithms to compute the FGW (Eq. (6)) between graphs and the OT distance (Eq. (7)) between node embeddings. (zpGL, bARL)**

We describe the optimization algorithms for both of these terms below, which were previously mentioned in Appendix B of the original submission.

To solve the FGW problem of Eq. (6), we optimize the transport plan with the conditional gradient (CG) solver. The conditional gradient algorithm [1] consists in solving a linearization $\langle \mathbf{X}, \nabla_\pi \rangle$ at each iteration $r$. It can be solved by gradient descent with a direction $\mathbf{X}^{(r)} - \pi^{(r)}$, followed by a line search for the optimal step. The detail of the algorithm is summarized in Algorithm 1 in the Appendix.

To solve the Wassersttein problem of Eq. (7), in the paper we use the Sinkhorn-Knopp algorithm [2] to iteratively approximate the optimal solution $\pi_z^*$. Specifically, Sinkhorn-Knopp algorithm add an additional entropy regularizer and perform a scheme of alternating Sinkhorn projections: $\pi^{(0)}=\exp(-\boldsymbol{J}(\boldsymbol{Z}_1, \boldsymbol{Z}_2)/\lambda)$ and $\pi^{(t+1)} = \mathcal{S} (\mathcal{T}(\pi^{(t)}))$, where $t$ denotes the number of iterations, $\lambda$ weights the regularization, $\mathcal{S}(\pi)=\pi \oslash(\mathbf{1} \mathbf{1}^{\top} \pi) \odot(\mathbf{1} \boldsymbol{b}^{\top})$ and $\mathcal{T}(\pi)=\pi \oslash(\pi \mathbf{1} \mathbf{1}^{\top}) \odot(\boldsymbol{a} \mathbf{1}^{\top})$, $\odot$ denotes the Hadamard product and $\oslash$ denotes element-wise division. As shown by [2], in the limit this scheme converges to a minimizer $\pi^{(t)} \stackrel{t \rightarrow \infty}{\longrightarrow} \pi^*$. 

[1] Revisiting frank-wolfe: Projection-free sparse convex optimization. ICML2013

[2] Sinkhorn distances: Lightspeed computation of optimal transport. NeurIPS2013



> **GQ2. The analysis and reducing of computational complexity. (YJ1t, bARL)** 

**Analysis of computational complexity:** We provided a time complexity analysis in the appendix of our submission. We describe it in more detail below plus some additional comparisons with baseline algorithms: The time complexity of the GALOPA comes mainly from the optimization of Eqs. (6) and (7). For Eq. (6) containing Fused Gromov Wasserstein term, we use conditional gradient (CG) solver for optimization, which requires the computation of a gradient with near-cubic $\mathcal{O}(n^3)$ time complexity at each iteration, where $n$ denotes the size of graph, i.e., the number of nodes. For Eq. (7) with the Wasserstein term, we can use Sinkhorn-Knopp algorithm for time efﬁcient with near-square $\mathcal{O}(n^2)$ complexity.

**Reducing complexity**: To reduce the time complexity, we utilize the properties of the proposed model and/or the scaling optimal transport techniques that can reduce the time complexity from $\color{red}{\mathcal{O}(n^3)}$ to $\color{red}{\mathcal{O}(n^2)}$ or even to $\color{red}{\mathcal{O}(n)}$, we provide 4 ways to do this below:

1) Unlike general OT settings, where the two graphs are typically quite different and the matching relationship between them is completely unknown, the **difference between the original and augmented graphs** in GALOPA **is quite small** and the **matching relations for subgraph component** except with difference part (i.e., complementary set of difference part) **is known**. This means that we can utilize the *matching prior* to reduce the computational cost. Hence, we can split the difference part with its neighborhood from the two graphs and compute the optimal transport plan only for that part. Since the percentage of that part is very small, it can greatly reduce the time complexity. For example, with the perturbation rate is set to 1%, the time complexity of two million-sized graphs ($(10^{6})^3$ or $(10^{6})^2$) is directly reduced by 6 (or 4) orders of magnitude to $(10^6)^2$ or $(10^{6})^{1.3}$.

2) According to the observation in Section 6, we can avoid the cubic complexity $\mathcal{O}(n^3)$ of optimizing GW by **using only the node attributes** for computing the optimal plan in graph space, while retaining similar performance with near-square time complexity $\mathcal{O}(n^2)$.

3) Alternatively, we can reduce the computational cost by utilizing sparsity [1] or graph partitioning [2, 3]. In particular, we can employ the most recent work on linear optimal transport [4, 5], which compute FGW term and/or Wasserstein term in **linear time** $\mathcal{O}(n)$.

4) We have the option to combine the aforementioned methods. For instance, by merging insights from point 1, a significant portion of subgraph pairs acquired via graph partitioning methods in point 3 turns out to be **identical**. This realization can further pare down the complexity of graph partitioning methods.

[1] Efficient approximation of gromov-wasserstein distance using importance sparsification. JCGS2023

[2] Scalable gromov-wasserstein learning for graph partitioning and matching. NeurIPS2019

[3] Quantized gromov-wasserstein. PKDD2021

[4] Computing wasserstein-p distance between images with linear cost. CVPR2022

[5] On a linear fused gromov-wasserstein distance for graph structured data. PR2023

**Complexity of GCL:** We further analysis the time complexity of the contrastive learning algorithm. The contrastive loss (e.g., InfoNCE loss) computes all-pair distance for nodes as negative pairs which induces quadratic time complexity $\mathcal{O}(n^2)$ with respect to the graph size. Thus, general graph contrastive learning algorithms (e.g., GRACE, MVGRL, GraphCL, etc.) have quadratic time complexity $\mathcal{O}(n^2)$ with respect to graph size. BGRL introduced loss that does not require negative pairs with linear computation cost $\mathcal{O}(n)$.

Meta-review: Graphs are notoriously hard to learn as their connections are arbitrary and the degrees of freedom are uncontrolled. With this, the paper presents a novel approach to the important task of self-supervised learning, a subject that attracts interest in the community. Although the work still have some drawbacks (e.g., runtime) that might influence the assimilation of these techniques, the novelty and possible applicability of the approach are of interest to the NeurIPS community.
Decision: Accept (poster)