Directed Graph Contrastive Learning
Authors: Zekun Tong
Yuxuan Liang
Henghui Ding
Yongxing Dai
Xinke Li
Changhu Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Contrastive Learning
Directed Graph
Graph Neural Network
Curriculum Learning

Abstract: Graph Contrastive Learning (GCL) has emerged to learn generalizable representations from contrastive views. However, it is still in its infancy with two concerns: 1) changing the graph structure through data augmentation to generate contrastive views may mislead the message passing scheme, as such graph changing action deprives the intrinsic graph structural information, especially the directional structure in directed graphs; 2) since GCL usually uses predefined contrastive views with hand-picking parameters, it does not take full advantage of the contrastive information provided by data augmentation, resulting in incomplete structure information for models learning. In this paper, we design a directed graph data augmentation method called Laplacian perturbation and theoretically analyze how it provides contrastive information without changing the directed graph structure. Moreover, we present a directed graph contrastive learning framework, which dynamically learns from all possible contrastive views generated by Laplacian perturbation. Then we train it using multi-task curriculum learning to progressively learn from multiple easy-to-difficult contrastive views. We empirically show that our model can retain more structural features of directed graphs than other GCL models because of its ability to provide complete contrastive information. Experiments on various benchmarks reveal our dominance over the state-of-the-art approaches.

Directed Graph Contrastive Learning
Zekun Tong'
Yuxuan Liang'
Henghui Ding 2,3,*
Yongxing Dai
Xinke Li'
Changhu Wang²
National University Singapore 'ByteDance
"ETH Zürich "Peking University
{zekuntong, 1 Liangyuxuan, xinke. 1i] @u nus. .du edu henghui www.ddiiiiiiooooo ee ethz. ch, yongxingdai edu. cn changhu. wang@bytedance..om
Abstract
Graph Contrastive I Learning (GCL) has emerged to learn generalizable representa- tions from contrastive views. However, is still in its infancy with two concerns: 1) changing the graph structure through data augmentation to generate contrastive views may mislead the message passing scheme, as such graph changing action de- prives the intrinsic graph structural information, especially the directional structure in directed graphs; 2) since GCL usually uses predefined contrastive views with hand-picking parameters, it does not take full advantage of the contrastive informa- tion provided by data augmentation, resulting in incomplete structure information for models learning. In this paper, we design directed graph data augmentation method called Laplacian perturbation and theoretically analyze how it provides contrastive information without changing the directed graph structure. Moreover, we present a directed graph contrastive learning framework, which dynamically learns from all possible contrastive views generated by Laplacian perturbation. Then we train it using multi-task curriculum learning to progressively learn from multiple easy-to-de to-diffulff contrastive views. We empirically show that our model can retain more structural features of directed graphs than other GCL models because of its ability to provide complete contrastive information. Experiments on various benchmarks reveal our dominance over the state-of-ther approaches.
Introduction
There is a growing interest in learning from directed graphs using Graph Neural Networks (GNNs)
[17, 12, 18, 50] to tackle practical problems, such as time-series problems [1, 4, 491, fine-grained traffic prediction [29, 21] and recommendation system [35, 7, 40]. Current GNNs designed for learning from directed graphs [23, 43, 44] are trained end-to-end under supervision. This training scheme shows excellent performance by virtue of enough labeled data. Correspondingly, to make use of rich unlabeled data, several Graph Contrastive Learning (GCL) [39, 63, 69, 34, 13, 67] works proposed based on GNNs and Contrastive Learning (CL) [5, 45, 14]. They utilize data augmentation methods to generate contrastive views from the original graphs, then force views generated from the same instance (node or graph) closer while views from different instances apart using InfoNCE-lit [28] objective function. However, current GCL methods encounter some issues in processing directed graphs, mainly in data augmentation method and contrastive learning framework.
Firstly, most data augmentation methods used in GCL [63, 69, 68] do take the directed graph structure into account and may discard distinctive direction information. For example, the idea of dropping nodes/edges [68, 63, 52] borrowed from random erasing used in images [66] which overlooks the discrepancy of nodes and edges in different graph structures. Moreover, by grasping contrastive information through changing graph structure, part of the distinctive direction information, e.g., irreversible ume-series relationships, will inevitably be lost. The message passing scheme will
"Corresonniigg author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

also be mislead, making it difficult for GNN-based encoders to learn from directed graphs. There is lack of data augmentation methods that are specifically designed for directed graphs to retain the original directed graph structure while providing enough contrastive information.
Besides, common contrastive learning frameworks are not optimized for directed graphs, they can only learn from a limited number of contrastive views [63, 69, 13J. However, due to the complex structure of directed graphs. it is insufficient to use small number of contrastive views to fully understand their structural characteristics [43]. Furthermore, since the contrastive views have to be determined before training, it becomes another problem to select the ideal views for the downstream task during pre-pro pre-processing, about which we actually have no knowledge in advance [42, 59]. Hand- picking contrastive views also cause a decrease in generalization. Several works [41, 61] try to obtain more information by increasing the number of contrastive views. However. they still have to pre-define the views and trade off between the number of views and the training difficulty.
To address these two issues, we first propose a directed graph data augmentation method called Laplacian perturbation. Since the contrastive views are passed to the encoder in the form of Laplacian matrix, a desirable data augmentation method is to perturb the Laplacian matrix without changing the directed graph structure. To achieve this, we adopt the approximate directed graph Laplacian [43] where teleport probability is introduced to control the degree of approximation. Thus, by adding a perturbation term to this probability, we can simply augment the Laplacian matrix without altering the directed graph structure. As it is time-con time-consuiing to calculate the Laplacian matrix, we then speed it up using the power method [24]. In addition, from the theoretical analysis, we find that the Laplacian perturbation is essentially perturbation to the directed graph entropy. The perturbation term essentially determines the magnitude of the entropy perturbation error, which affects the magnitude of the contrastive information.
To learn the complete structural characteristics of directed graphs, we design a directed graph contrastive learning framework to learn from contrastive views generated by Laplacian perturba- tion. First, we introduce generalized dynamic-view contrastive objective which maximizes the sum of the mutual information between the representations of all contrastive views. This objective allows the contrastive views to change dynamically during training and motivates the encoder to learn a generalized representation from all views provided by data augmentation. However, this dynamic-view objective function hard to optimize. Thus, we leverage the multi-task curriculum learning strategy [33, 36, 10, 26] to divide multiple contrastive views into sub-tasks with various difficulties and progressively learn from -oifffcuif sub-tasks. In this way, we can learn all views step-by-step to reach the final objective. Moreover, learning from all contrastive views eliminates the need to adjust the data augmentation parameters anymore.
We empirically show that our Directed Graph Contrastive Learning (DiGCL) outperforms the competitive baselines in the settings of unsupervised and supervised learning. Systematic analysis is also carried out to analyze the performance of various augmentations on the mainstream benchmarks and the impact of different pacing functions on the performance of directed graph contrastive learning.
2 Directed Graph Data Augmentation
In this section, we first design directed graph data augmentation scheme named Laplacian perturba- tion. As it is time-consuming to calculate the Laplacian matrix, we then speed it up using the power method [24]. Finally, we analyze the proposed data augmentation scheme theoretically.
2.1 Directed Graph Laplacian and its Approximation
Formally, let a directed graph 9 (V, its adjacency matrix can be denoted as A {0, 1 where n D The nodes are described by the feature matrix X mxx with the number of features e per node. Intuitively, the data augmentation can be performed at the topological- and feature-level. operating A and X, respectively [63, 69]. The distinctive attribute of directed graphs is the directionality of the edges, which leads us to focus on topological node-level data augmentation.
The augmented directed graph is fed to the CNN-based encoder in the form of Laplacian matrix to learn the representation. Since G may contain isolated nodes or could be formed into bipartite graph, it is not appropriate to trivially use directed graph Laplacian [6]. To relax this constraint, use its

---

approximate form: the approximate directed graph Laplacian matrix [43], which is defined as Appe PIT
Lappr (G, a) =
II
appe + Happ P I'I appr
(1)
2
where aappr
Diag(Tappr) (Tpppr). The approximate eigenvector Tappr is defined as
Tappell
1 a 1xm = Tappr:
(1- Tappe n2 nl+a
(2)
where P A+ Iax denotes the transition matrix with added self-loops and the diagonal
degree matrix D(u,u) = Evey A v), Tong el al. [43] add self-loops to the original directed graph to ensure 9 to be aperiodic and redefine the transition matrix based on personalized PageRank with
the teleport probability a (0, 1) to guarantee the redefined matrix to be irreducible. Note that we follow the [43] and set 0.1 in this paper.
According to Eq. (1), existing data augmentation methods [63, 69], e.g., node/edge dropping, sub- graph sampling, need to obtain the contrastive information by changing P. Their use of sampling- based methods invitably corrupts the directed graph structure and thus misleads the message passing in the GNN- encoder. A desirable data augmentation method on appr is perturb Tappr reasonably without altering the directed graph structure P!.
2.2 Directed Draph Data Augmentation with Laplacian Perturbation
From Eq. (2), it is easy find that the eigenvector Tappe depends the P and a. In other words, can shift the teleport probability a without changing the directed graph structure P, thus altering the eigenvector Tappr and finally perturbing the Laplacian matrix Lappe.
DEFINITION Laplacian perturbation. Given a directed graph G = (V.E) and the teleport proba- bility a, we define the Laplacian perturbation opertation (()) the Lappe (P. (P, a)
Lsa(G, a) Lapp: a+ Da);
(3)
where Aa is a perturbation term that satisfies Aa > and a Aa E (0,
Through this operation, the directed graph structure and the sparsity of the Laplacian matrix are maintained, which means there is training burden to the subsequent GNN-based encoder. However, using this operation for data augmentation is very time-consuming, since the time complexity of computing Eq. (2) O (n²). To deal with it, we design an accelerating algorithm for computing this approximate eigenvector based on the power method [24].
We take advantage of the sparsity of the transition matrix P to compute the approximate eigenvector Tappr and rewrite Eq. (2) the form of discrete-time Markiv chain at time /
aappr = (1 - (1-a)=appr) P
1xn
(4)
n1+a
As stated in Tong el al. [43], 7 "aper has a special property that mh Tappr the last term of Eq. (4) with (1 a) nxx to
1 axx = Ita
1.
We then multiply
1++ x appr = - (1-a) ai P+
[(1 a) T app
nx
Ixn a1-
P Q
n n appp"
axn
(5)
1 +
We solve Eq. (5) iteratively using the power method [24]. Therefore, the complexity decreases O (nk), where & is the number of iteration times. Due to page limit, we do not discuss the number of iterations and convergence rate here. Please refer [22] for more details. We take A = 100 and the tolerance as 1e-6 throughout. It can be seen easily that for large-scale graphs, our method can significantly improve the speed and makes possible to do Laplacian perturbation during the training. which is the basis for the framework proposed in Section 3. In addition, we compare the running time of our fast Laplacian perturbation with different data augmentation methods in Section 5.2.
Note that adding self-loops to transform P into P is a common trick 56), and we ignore the effect of this operation the directed graph structure.
3

---

1/6
Approximate directed
graph Laplacian
Laplacian Perturbation
Add teloport probability Ot
á
a
Aa
4
Original
appp (G.a) o)
Figure 1: Illustration of Laplacian perturbation, is the auxiliary node defined in [43] and the red dotted lines represent adding the self-loops.
2.3 Justification of Laplacian Perturbation
Noticing the inherent connections between graph Laplacian and von Neumann entropy [62], we can use the propricties of von Neumann entropy to analyze the Laplacian perturbation operation quantitatively. We start with defining the von Neumann entropy of directed graphs.
DEFINITION Directed graph von Neumann entropy. Given directed graph (V,8), its Neumann entropy [62] based on the Lappr is defined as
Tappr (u)
HvN(g,,)) =
Σ
Σ
(6)
n
2n
(u,w)eE
ded dest
Tappr (d)deuu?
(u,w))E
deu deye
where & {(u, v) (u. v) E & and (v, u) é E). di Evey A(U, u) and de Evev Vu, are the in- and our-degree of the node u.
Since the Laplacian perturbation does not involve the nodes/edges and only changes the teleport probability connecting to the auxiliary node as shown Figure 1, the number of nodes n and the degrees of nodes du (edge distribution) will not change. Conversely, the approximate eigenvector Tappr has been changed. According Eq. the essence of this operation is perturbation the directed graph entropy. We further introduce the perturbation error to quantify this impact.
DEFINITION Perturbation error. Given the perturbation term aa, we define the perturbation error of directed gruph von Neumann entropy caused by Laplacian perturbation as A Aa) = - a a Aa).
THEOREM 1 Monotonicity of the perturbation error. monotonically with the Laplacian perturbation term Aa.
The perturbation error Alvx increases
THEOREM? 2 Bounds on the perturbation error. Given a directed graph G EV and the teleport probability a, the inequality
Tappr (u)
0 < AHvv(a, Aa) < 2n
Σ
dow?
TT "appr ()deuur
[u.
holds. When the perturbation term Aa = 0, AHYN O and when Aa + 1 a-a, a, the perturbation error AHYN towards the upper bound.
We show in THEOREM that Laplacian perturbation can provide contrastive information in various magnitude for the encoder to learn the representations by changing Aa. Meanwhile, since it does not need to alter the structure and the number of nodes n is generally high, the perturbation error will be in very small range as shown in THEOREM 2. This can help the encoder to focus more on the directed graph structure rather than just learning from the errors. Proofs of THEOREM and are attached in the Supplementary Material.
3 Directed Graph Contrastive Learning
In this section, we introduce new directed graph contrastive learning framework (DiGCL) with more generalized objective, and then we present multi-task curriculum learning scheme to help DiGCL progressively learn from multiple easy-to-difficull contrastive views. The model illustration is in Figure 2 and the pseudo-code is given in the Supplementary Material.

---

L appr
f Dous
Difficully
MMM
Head
Scorting Fundion
Encoder
L appp
+ Amm
Vyr
Contrast
Vanu
L appr
An2
Lappr
4 4da1
Pacing Function P
Original G Augmentation 4b
Multi-tack Curriculum Learning
Input Views
Encoder
/"
Head
Loss
Figure Illustration of our DiGCL model using Laplacian perturbation. For a directed graph, we first generate M different pairs of contrastive views by Laplacian perturbation. The different contrastive view pairs are then scored by a scoring function and mapped to different training paces by a pacing function. Finally, the arranged contrastive view pairs are input into shared encoder to progressively learn the unsupervised graph representation with contrastive loss.
3.1 Learning with Dynamic-view Contrastive Objective
As we have defined the directed graph data augmentation in Eq. (3), we follow the common graph contrastive learning (GCL) paradigm using our Laplacian perturbation.
Fixed-view Objective. GCL seeks maximize the mutual information (MI) between the represen-
tations of augmented graphs under different views [63, 69]. Based on it, we design framework for directed graph contrastive learning, which contains three steps. (1) First, given a directed graph 9 (V, E) and the teleport probability
we generate two correlated views using for the G: Usa; T Aay (G and Vaag 4 (9,a) as a contrastive pair. This generation through exe- cuting Laplacian perturbation & on the input & with the parameters λaj, Aaz separately. (2) Second, we take a GNN-based encoder f() to extract representation Ha f(Usa, ). Ha = =((as)) of two contrastive views. (3) Finally, the encoder is trained with the contrastive objective as
max I (HAm, HAm. max I Aon a); (G)))(
(8)
f
where T(.) is the mutual information. This framework lets the encoder s(+) learn the representation of two different views USay. Van, while preserving as much MI as possible.
As shown in Eq. (8), the view generation is controlled by two perturbation terms Aaj and Σaz. which may affect the objective function. The current GCLs manually select these parameters in advance, e.g. grid search, and fix contrastive views during training. This parameter selection strategy could make the encoder obtained by Eq. (8) learn only the contrastive information in some particular views and lead reduced generalization of the model [59].
Dynamic-view Objective. To deal with it, we propose a more generalized objective to learn from dynamic changing contrastive views. We rewrite Eq. (8) as
max / (Ham H max IE Aa1
(9)
which requires the obtained optimal encoder works well with V Vdai, Aaz [0, 1-) to learn a balanced and generalized representation. Note that InfoMin [42] designs similar strategy that iteratively maximizes the MI the worst views. In contrast, our objective maximizes the average MI in all views because finding the worst views is related to the downstream task, about which we have zero prior knowledge. Besides, unlike other contrastive learning methods that also use multiple contrastive views [41, 13, 61], there is no fixed number of views in our approach, and we do not preset the parameters to fix the contrastive views but let them dynamically change during training.
However, maximizing Eq. (9) is not easy. Varying the perturbation term brings changes to the MI of views, which may result in large variance during the training process and unable to converge [42]. To increase the stability, we empirically make one of the views unperturbed in this paper, i.e., Aoi = 0. We mark this view U and design multi-task training scheme to optimize proposed objective?.
3.2 Training using Multi-task Curriculum Learning
To tackle this problem, we propose a training scheme using curriculum learning, which utilizes prior knowledge about the difficulty of the learning tasks to learn from easy-to-difficult contrastive views.
"The objective of fixing view is not exactly the same the original one, and ignore this trick's impact.
5

---

Multi-task Curriculum Learning. Curriculum Learning facilitates the optimization on such a
complex objective by scheduling the sub-objectives in a certain order [2, 33]. Inspired by it, we
regard the process of training DiGCL as multi-task problem [33, 36, 10, 11, 26, 20] and decompose it into M sub-tasks 7,,....;'M
-IM- Thus, the objective Eq. (9) can be rewritten as
M E E (L (9,a)); (9 (G,
max M
(10)
where Aum E {()) (O.....M) ) is uniform partition of θ = [0,1 and the sub-task 7/mm is associated with the Aom. Then we consider sub-tasks that have less difficulty to learn the optimization process as easy sub-tasks and vice versa difficult sub-tasks. We quantify this difficulty into difficulty score by means of scoring function D(.). Based on it, we learn sub-tasks sequentially in certain order decided by the pacing function P(-) to solve the main multi-task problem. Via information transmission by a shared encoder, the previously solved easy sub-tasks will assist in solving the next difficult sub-tasks, while the latter can fine-tune the encoder learned by the former.
Scoring Function. The scoring function (-)) measures how difficult the sub-task 7h is, and can be any function D(-): (,...... 'TM) [di...., dM) ), where d denotes the difficulty score. In each sub-task, there exists a pair of contrastive views as defined in Eq. (10). We empirically assume that the difficulty dm of the sub-task 7m depend on how difficult it is for the encoder ʃ(.) to learn the contrastive information from this sub-task. Referring to DEFINITION 3, we can find Laplacaian perturbation provides contrastive information to the encoder, and the perturbation term aa controls how much of this information is. Therefore, we can define the scoring function (-) to calculate the difficulty dm of a sub-task 1/m.
dm = (1mm) = Aam
(1I)
1-a
The higher this score represents the smaller the perturbation error, the less contrastive information provided, and the less the encoder is able to distinguish the difference between the two views, resulting more difficult sub-task. This idea coincides with the design of the discriminator in GAN [65, 9].
Pacing Function. The pacing function decides the learning sequence of sub-tasks and can be any function P(-): (()):[L..... (I, L} + {di....,dhy. d where L denotes all the learning iterations. We consider three function families [58]: logarithmic, exponential, and linear. Table in Figure 3(left) illustrates the pacing functions used in our experiments, which are parameterized by (da,d)). Here d, the initial difficulty and d, is the difficulty at the end of training, thus any pacing function with da d. equivalent to fixed view contrastive learning. We mark their corresponding perturbation terms as ( (Aa., Aa²) Considering the score in Eq. (11) is defined in a continuous domain, we set the step size of the pacing function to 1, the fmest-grained unit, i.e., M. This can help the model to switch between different training views in a more delicate way.
do
Name
Expression P(da. (1)
Diftoutt
log
dg (dg da) + 1/3log (1+1/31o/g 1 3))
cxp
d, e-
da-da (exp (1) 1))
d.
lgg BC
linear
do (do d.)
Inear
opoch [
Figure 3: (Ieft) pacing function definitions for the three families of pacing functions used throughout; (right) the plot of pacing function curves from each family. I is the training epoch.
It is desired find the optimal solution over the entire definition domain of Aa 10,1-a) we set the start point Ao. = 0.9 - a (0.9 is used because the boundary value cannot be obtained) and ending point Ao; 0 in this paper, i.e., d, 1/9,d, dp 1. More analysis the pacing functions can be seen in the Supplementary Material.
Contrastive loss. After discussing how to measure expectations in the objective, our attention shifts to maximizing the MI. Several works have investigated the lower bound of MI in contrastive learning, here we adopt InfoNCE [28]. For h node u; in view U, the node-wis wiie objective is defined as
exp (5 (zt, xtssm)) /T)
ll (u, v.) -log
(12)
Σj exp (s (/am)) /T)

---

where o2 is its corresponding positive node in view Vaa.. and other nodes in view Va is negative nodes of ug. ziy is the projection of node feature that z Zu = g (. A non-linear transformation g(-) named projection head maps augmented representations H another lower dimension where the contrastive loss is calculated. S()) denotes cosine similarity function and T denotes the temperature parameter. The final loss is computed across all positive node pairs in the views of one pace. Note that GRACE [68] proposes similar InfoNCE-like loss function. Different from it, we do not treat antra-view nodes (nodes in U except u4) as the negative samples since GNN-based encoder is already able to learn intra-grape structure well, we want to focus on inter-graph contrastive information.
4 Related Work
Directed Graph Neural Networks. Several works have tried to learn the complex directed graph structure by defining motifs [25], using magnetic Laplacian [64], inheritance relationships [16], re- defining the propagation scheme from Markov process view [43, 23] and second-order proximity| [44]. However, these methods are supervised, and they cannot learn the structural features without labels. Our model is unsupervised. which is the most significant difference between them.
Directed Graph Data Augmentation. Good data augmentations are the prerequisite for contrastive learning [63, 48, 54]. Most current data augmentation methods, such dropping nodes edges [63, 68, 69, 51] and attribute masking [15, 63, 55] are migrated from methods of visual representation [57, 66] with graph structural improvements. Other methods learn graph structure features by combining with traditional graph algorithms to go self-supervised, for example, subgraph sampling
[63, 34, 52], graph diffusion based PageRank/HHat kernel [13], and multi-hop neighbor prediction [31]. However, most of these methods are not optimized for directed graphs and thus cannot efficiently obtain structure information that can be used for self- eeffssuperiiee learning. The performance of existing methods on directed graphs can be seen in Table 2.
Dynamic-view GCL and Multi-task Curriculum Learning. Previous works [41, 13, 61] have found the powerful capabilities of using multiple contrastive views at the same time in contrastive learning. However, their methods require to set contrastive views in advance, which means the views are fixed during training [13, 41]. Unlike them, we do not preset the parameters to fix the contrastive views but let them dynamically change during training. However, our dynamic-view contrastive objective is hard to optimize. thus we adopt the idea of multi-task curriculum learning [33, 36, 10, 11, 26, 20] progressively learn from multiple easy-to-difficull contrastive views. Besides, using curriculum learning [8, 53] in graph learning tasks is not a new idea, but we are the first use curriculum learning as a solution to the self supervisd graph contrastive learning problem.
Experiments
We conduct extensive experiments to evaluate the effectiveness our model. Our implement can be obtained at attps://2/ thub. cwwm fl/f/lyii/ flyingtango/ /DiGCL. The Supplementary Material reports further details on the experiments and reproducibility.
5.1 Experimental Settings
Experimental Task. As explained Section 2.1, our approach is more applicable to node-level contrastive learning, thus, we adopt the task of node classification in directed graphs [43] to verify the learning ability of models. Compared with the common experiments for undirected graphs [6, 18], the challenge is that the given adjacency matrix A is asymmetric, which means message passing has its direction. We will also use datasets of undirected graphs for controlled trials. Task definition, model structures and configurations are included in the Supplementary Material.
Datasets and Splitting. We use several widely-used datasets including directed graph datasets:
CORA-MB [3], CITESEER [37] and AM-PHOTO [38]; undirected graph datasets: PUBMED [27] and DBLP [30]. The split of the datasets would have a significant effect on models' results [38]. Thus, we divide the datasets randomly and conduct multiple tests to achieve consistent outcomes. For train/validation/nest split, following the nules in GCN [17], we choose 20 labels per class for training set, 500 labels for validation set, and rest for the test set.
7

---

Baselines. We compare our model to the 11 SOTA models divided into four main categories; 1) supervised models for undirected graph with GCN [17], GAT [46] and [18]: 2) supervised models for directed graph with MagNet [64] and DiGCN [43]; 3) self-supervised models without augmentations
including DGI [47] and GMI [32]; 4) contrastive learning models with augmentations containing
MVGRL [13), GraphCL. [63], GRACE [68], and GCA [69].
5.2 Experimental Results
Overall accuracy. The performance comparisons between our model and baselines on five datasets are reported in Table 1. We use two-layer GCN our encoder and first train our model in an unsupervised manner to obtain the embedding. Then we take a simple fz-regularized logistic regression as the classifier [47]. For curriculum learning scheme, we select the log pacing function and the start and ending difficulties are set in Section 3.2. We train all models according to their default settings, then calculate mean test accuracy with STD in percent (%) averaged over 20 random dataset splits with random weight initialization.
It can be seen easily that our methods achieve the state-of-the-ard results all datasets. In general, the unsupervised methods including MVGRL, GRACE, and GCA, do not perform well on directed graphs compared their good performance in undirected graphs. This is mainly due to the models' data augmentation methods are not applicable to digaphs, resulting in the inability to learn contrastive information from complex directed structures. Notice that GraphCL performs relatively mediocre in unsupervised methods, most notably because it focuses mainly on graph-level unsupervised methods, and does not apply well node-level contrastive learning task. Since DGI and GMI do not require data augmentation to provide contrastive information, they perform very well on both undirected and directed graphs, which shows good suitability for different graph structure. Moreover, supervised methods such as GCN, GAT and APPNP are inferior to DiGCN and MagNet, which are specifically designed for directed graphs, in terms of performance. Since our Laplacian perturbation uses the approximate Laplacian matrix proposed by DiGCN, we compare their performance. It is not difficult to find that our model outperforms DiGCN on all datasets, which shows that contrastive learning can learn good encoders by performing certain data augmentation in unsupervised manner.
Table 1: Overall accuracy (%) with STD, "No Curr" means do not use curriculum learning and we set two fixed views as Aa, Aas = a. "Random" means random order, "Anti Curr" means using anti-curriculum order and "Curr" indicates using curriculum order. The best results are highlighted with bold and the second are marked with underline. OOM means out of memory on a 12GB GPU.
DIRECTED
UNDIRECTED
Method
CORA-ML
CITESEER
AM-PHOTO
PUBMED
DBLP
GCN [17]
70.92 0.39
63.00 0.45
88.52 a 0.47
78.78 0.30
73.54 0.77
UNSUPERVISER SUPERVISED
GAT [46]
72.22 + 0.57
63.73 0.57
88.36 1.25
77.49 0.47
76.08 0.54
APPNP [18]
70.31 + 0.67
61.63 + 0.63
87.43 = 0.98
79.35 = 0.48
77.92 + 0.75
MagNet [64]
76.32 1 0.10
65.04 0.47
86.80 = 0.65
74.23 4 0.46
69.73 0.98
DiGCN [43]
77.03 + 0.70
64.60 + 0.60
88.66 = 0.51
76.79 = 0.49
73.37 # 0.72
0.72
DGI[47] GMI[2]]
75.21 + 1.29
64.58 1.78
85.25 + 0.59
74.11 + 0.62
76.53 +: 1.24
76.59 +: 0..55
63.29 + 0.70
81.12 = 0.01
80.27 + 0.16
76.66 + 0.48
MVGRL[13]
76.67 + 0.12
62.22 0.02
86.15 = 0.21
79.98 0.04
OOM
GraphCL. [63]
67.34 0.12
57.84 0.11
67.66 + 0.05
75.29 + 0.08
77.85 + 0.22
GRACE [68]
73.88 + 0.25
61.20
87.95 0.32
79.54 0.05
78.03 0.09
GCA [69]
76.32 + 0.33
6
87.35 0.27
79.81 + 0.61
77.83 0.35
Ours + No Curr
75.86 0.09
66.99
87.32 0.14
79.57 0.12
78.28 0.05
Ours + Random
76.52 + 1.66
67.15
49.03+0.48
80.75 * 0.10
19.58+0.14
Ours + Anti Curr
76.12 + 1.04
66.83 + 1.18
88.83 = 0.73
80.22 = 0.37
79.42 + 0.15
Ours + Curr
77.53 + 0.14
67.42 4 0.14
89.41 0.11
80.69 + 0.08
79.70 0.13
Ablation study on curriculum learning. We validate the effectiveness of curriculum learning strategy and the results are shown in Table 1. We find that even with the contrastive views containing the maximum information (with the largest perturbation term), the effect of the model without curriculum learning is significantly lower than the model with curriculum learning. This means
8

---

that features learned from fixed views is always incomplete. Besides, we also find that the order of curriculum learning vital. the ACC of learning from easy-to-dificult > random order difficult-to- easy. This substantially validates that scoring function do help to learn from multiply tasks.
Impact of different pacing functions. We study the three different pacing functions defined in Table 3 and the results in Figure 4(a) show that using different path functions can have an impact on the performance but not as much as changing the order of curriculum learning. Among them, the log pacing function performs best as it speeds up learning on easy tasks and stays on harder tasks for more epochs, thus helping the model grasp the more subtle differences between contrastive views.
Effect of Laplacian perturbation and other data augmentation methods. Table 2 shows the effect of the different data augmentation methods the five contrastive learning models. We our Laplacian perturbation works best on both directed and undirected graphs. But the difference with other methods is not significant the undirected graph dataset PURMED. In addition this, also compare with random removing edges used in GRACE ACA under our DiGCL framework. We find that the data augmentation approach without damaging the graph structure can achieve better performance.
Table 2: Overall accuracy (%) with STD with various data augmentation methods. Our model uses curriculum learning, and use the log pacing function. The best results are highlighted with bold.
Methods
Data Augmentation Method
CITESEER
AM-PHOTO
PUBMED
Edge perturbation
57.84 0.11
67.66 0.05
75.29 + 0.09
GraphCL [63]
Node dropping
57.45 0.12
66.69 + 0.07
75.25 + 0.08
Subgraph sampling
57.59 0.10
66.75 4 0.07
74.75 1 0.11
GRACE [68]
Random removing edges
61.20 0.20
87.95 + 0.32
79.54 + 0.05
Graph diffusion with heat kernel
61.22 0.07
79.63 0.31
78.54 + 0.33
MVGRL [13]
Graph diffusion with PageRank kemel
62.22 0.02
86.15 + 0.21
79.98 + 0.04
Removing edges by degree Removing edges by PageRank score
63.25 0.10
87.35 0.27
79.81 0.61
GCA [69]
62.21 0.16
86.88 + 0.37
78.92 = 0.37
Removing edges by eigenvalue score
63.12 0.08
87.02 + 0.56
79.70 = 0.09
Random removing edges Laplacian perturbation
64.97 0.08
88.45 + 0.01
79.66 + 0.13
Ours
67.42 a 0.14
89.41 + 0.11
80.69 + 0.08
Generalization of Laplacian perturbation. Here, will add generalizability experiments that migrate Laplacian perturbation to MVGRL [13] and GCA [69]. We replace the topological data augmentation method in the original model with Laplacian perturbation and follow all the configurations in the original model, including the parameters of the data augmentation, the number of contrastive views, the structure of the model, and the training parameters. We test the generalization performance of our Laplacian perturbation in the node classification task. The results are shown Figure 4(b). We can clearly find that the performance of the model on directed graphs can be improved after using Laplacian perturbation, which indicates that our method can help existing contrastive learning models to learn structure information from complex networks.
Monotonicity of the perturbation error in real-world datasets. To visualize the variation of the perturbation error with the perturbation term, empirically show the variation of directed graph entropy in the three real-world directed graph datasets: CORA-ML, CITESEER and
We
190
linear log
HNYGRE
COE
ACC
ACC
13
Dattsets
Tatzsees
Ac
Figure 4: (a) node classification results with various pacing functions; (b) node classification results for the generalizability of Laplacian perturbation on two datasets, Lp means with Laplacian perturbation; (c) perturbation error with various perturbation terms Ac.

---

Auquentation time (I8))
450
1:24 MAA
Srophin pate
Tiae per oponis (mno)
248
248 INGEE
140
100
55
14
Number of Edges
Graph Size
Datasets
Figure 5: (a) time of different data augmentation methods on random graphs with different size; (b) running time per epoch of different models on random size graphs, OOM means out of memory; (c) generalization experiment of graph classification task based on MVGRL.
set 0.1 and take Aore e {0, 0.1, 0.2, 0.6, 0.7, 0.8, 0.85, 0.89). The results are shown in Figure 4(c), and it is clearly shown that as the perturbation term increases, the degree of perturbation elevated, and the perturbation error will increase.
Augmentation time at different graph scales. We construct 20 random directed graphs of different scales, with the number of edges ranging from IK to 2M, then test four different data augmentation methods' mean running time in milliseconds (ms) for times. Figure 5(a) summarizes the results and shows that our Laplacian perturbation is very competitive in terms of runtime among these methods. In contrast to the graph diffusion, which also require the computation of eigenvectors, we can reduce the time by factor of one hundred with our fast algorithm proposed in Section 2.2. This makes it possible to dynamically perform Laplacian perturbation to generate contrastive views during training.
Running time with different graph size. To generate arbitrary graph size, we construct a simple random graph with N nodes and assign 10.V directed edges uniformly random. We compare with GRACE[68] and GCA [69] since these two models have the similar accuracy with ours. We record the running time of the models for each epoch at different graph sizes, and the results are shown in Figure 5(b). We can find that processing 20,000 nodes and 200,000 edges with 12 GB memory is the limit for these three models. Since our model requires a Laplacian perturbation operation, this will take more time than the data augmentation performed by GCA and GRACE.
Generalization to graph classification task. To validate the generalization ability of our DiGCL model, we migrate it to MVGRL [13] and test on three graph classification datasets: MUTAG [19], PTC [19], and IMDB-B BIN [60]. The generalized MVGRL. model is denoted by MVGRL+ and the results are shown in Figure 5(c). Using our model can improve the accuracy on all datasets, however, the improvement not significant. We consider there are three main potential reasons for this: 1) the datasets are undirected graphs, and the effect of using Laplacian perturbation on them is not as obvious as in directed graphs; 2) the graph classification problem requires more graph-level contrastive information, while our model focuses on node-level; 3) our scoring function designed for node-level curriculum learning is not suitable for graph-level difficulty measure.
Conclusion, Limitation and Future Work
In this paper, we design directed graph data augmentation scheme called Laplace perturbation and theoretically investigate how it can provide contrastive information without changing the directed graph structure. Moreover, we present the DiGCL which utilizes Laplacian perturbation and cur- riculum learning to progressively learn from dynamic easy-to-difficull contrastive views. Finally, we use several tasks on various datasets to demonstrate the effectiveness and generalization ability of our proposed DiGCL. We empirically show that DiGCL can retain more structural features of directed graphs than other GCL models while providing adequate contrastive information. Extensive experiments show that our DiGCL outperforms the state-of-the-ar approaches.
As elaborated in Section 2.1 and 5.2, our approach is more suitable for obtaining node-level contrastive information. This limits us use the model to solve some graph-level problems, such as pre-training on protein molecular, drug property prediction, etc. We will extend our approach to graph-level tasks subsequent work. Meanwhile, we manually design the pacing function to preplan the training speed, such as linear or exponential functions. However, in many cases, the pacing during training is not perfectly planned by the ideal curve. We need dynamically adjust the pacing function according to the training situation, such as using self- self- paced learning [20].
10

---

Acknowledgments and Disclosure of Funding
The authors would like to thank Changsheng Sun, Xu Cai and Jinyang Wang for the great help in discussion and proofreading. This research is supported by NUS Research Scholarship.
References
[1] M. Barigozzi and C. Brownlees, "Nets: Network estimation for time series," Journal of Applied Econometrics, vol. 34, no. 3, pp. 347-364, 2019.
[2] Y. Bengio, J. Louradour, R. Collobert, and J. Weston, "Curriculum learning." in Proceedings of the 26th annual international conference on machine learning, 2009, pp. 41-48.
[3] A. Bojchevski and Günnemann, "Deep gaussian embedding of attributed graphs: Unsuper- vised inductive learning via ranking." arXiv preprint arXiv: 20177
[4] Y. Cai, I. Ge, J. Liu, J. Cai, T.-J Cham, J. Yuan, and N. M. Thalmann, "Fxploiting spatial- temporal relationships for 3d pose estimation via graph convolutional networks," in Proceedings of the IEEE International Conference on Computer Vision, 2019, pp. 2272-2281.
[5] T. Chen, S. Korbblith, M. Norouzi, and G. Hinton, "A simple framework for contrastive learning of visual representations," " arXiv preprint arXiv:2002.05709 2020.
[6] Chung. "Laplacians and the cheeger inequality for directed graphs," Annals of Combinatorics, vol. 9, no. 1, pp. 1-19, 2005.
[7] T. Dettmers, P. Minervini, P. Stenetorp, and S. Riedel, "Convolutional 2d knowledge graph embeddings." " in Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
[8] C. Gong, J. Yang, and D. Tao, "Multi-modal curriculum learning over graphs." ACM Transac- tions on Intelligent Systems and Technology (TIST), vol. 10, no. 4, pp. 1-25, 2019.
[9] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, "Generative adversarial networks," arXiv preprint arXiv:1406.26611 2666.2661, 2014.
[10] H. Guo, R. Pasunuru, and M. Bansal, "Autosem: Automatic task selection and mixing in multi-task learning," arXiv preprint arXiv: 1904.04400 2019.
[11] M. Guo, A. Haque, D.-A. Huang, Yeung. and L. Fei-Fei, "Dynamic task prioritization for multitask learning," in Proceedings of the European Conference Computer Vision (ECCV), 2018, pp. 270-287.
[12] W. Hamilton, Z. Ying, and J. Leskovec,"Inductii "Inductive representation NIPS, 2017, pp. 1024-1034.
learning on large graphs," in
[13] K. Hassani and A. H. Khasahmadi, "Contrastive multi-view representation learning on graphs," arXiv preprint urXiv:2006.05582. 2020.
[14] K. He, H. Fan, Y. Wu. Xie, and R. Girshick, "Momentum contrast for unsupervised visual representation learning," arXiv preprint arXiv: 1.201..05577 .05722, 2019.
[15] W. Hu, B. Liu, J. Gomes, M. Zitmik, P. Liang, V. Pande, and J. Leskovec, "Strategies for pre- trainirinng graph neural networks," arXiv preprint arXiv: 12265, 2019.
[16] M. Kampffmeyer, Y. Chen, X. Liang, H. Wang. Y. Zhang, and E. P. Xing, "Rethinking knowledge graph propagation for zero-shot learning," in CVPR, 2019, pp. 11 487-11 496.
[17] T. N. Kipf and M. Welling, "Semi-superrised classification with graph convolutional networks," arXiv preprini arXiv: 1609.009070 2016.
[18) Klicpera, A. Bojchevski, and S. Günnemann, "Predict then propagate: Graph neural networks meet personalized pagerank," arXiv preprini arXiv: 1810.0997 2018.
[19] N. Kriege and P. Mutzel, "Subgraph matching kernels for attributed graphs," arXiv preprint arXiv: Stfv:1200.6465 6483, 2012.
[20] C. Li, J. Yan, F. Wei, W. Dong, Q. Liu, and H. Zha, "Self-paced multi-task learning," in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017.
[21] Y. Liang, Ke, J. Zhang, Yi, and Zheng, "Geoman: Multi-level attention networks for geo-sensory time series prediction." in IJCAI, 2018, pp. 3428-3434.

---

[22] C. Liu and Y. Li, "A parallel pagerank algorithm with power iteration acceleration,"
aecelration,""Itmmrationdd International
Journal of Grid and Distributed Computing, vol. 8. no. 2. pp. 273-284, 2015.
[23] Y. Ma, Hao, Y. Yang, H. Li, J. Jin, and G. Chen, "Sppetral-based graph convolutional network for directed graphs." arXiv preprint arXiv: arXiv: 1907008990 2019.
[24] C. B. Moler, Experiments with MATLAB. Society for Industrial and Applied Mathematics, 2011.
[25] F. Monti, K. Otness, and M. M. Bronstein, "Motifnet: a motif-based graph convolutional network for directed graphs," in IEEE DSW. IEEE, 2018, pp. 228.
[26] K. Murugesan and J. Carbonell, "Self-paced multitask learning with shared knowledge." arXiv preprint arXiv: 1703.009777 2017.
[27] G. Namata, B. London, L. Getoor, B. Huang, and U. EDU, "Query-driven active surveying for collective classification," in 10th International Workshop on Mining and Learning with Graphs, vol. 8, 2012.
[28] A. v. d. Oord, Y. Li, and O. Vinyals, "Representation learning with contrastive predictive coding," arXiv preprini arXiv: 0088000.7744 2018
[29] K. Ouyang, Y. Liang, Y. Liu, Z. Tong, S. Ruan, Y. Zheng, and D. S. Rosenblum, "Fine-grained urban flow inference," " arXiv preprini urXiv:2002.02318 2020.
[30] S. Pan, J. Wu, X. Zhu, C. Zhang, and Y. Wang, "Tri-party deep network representation," Network,
vol. 11, no. 9, p. 12, 2016.
[31] Z. Peng. Y. Dong, M. Luo. X.-M. Wu, and Q. Zheng. "Self-supervised graph representation learning via global context prediction," arXiv preprint arXiv:2003.01600 2020.
[32] Z. Peng, W. Huang, M. Luo. Q. Zheng, Y. Rong. T. Xu, and J. Huang, "Graph representation learning via graphical mutual information maximization," in Proceedings of The Web Conference 2020, 2020, pp. 259-270.
[33] A. Pentina, V. Sharmanska, and C. H. Lampert, "Curriculum learning of multiple tasks," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2015, pp- 5492-5500.
[34] J. Qiu, Q. Chen, Y. Dong, J. Zhang, H. Yang. M. Ding, K. Wang, and J. Tang, "Gec: Graph contrastive coding for graph neural network pre-training." " in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2020, pp. 1150- 1160.
[35] R. Qiu, H. Yin, Z. Huang, and T. Chen. "Gag: Global attributed graph neural network for streaming bession-based recommendation." in Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020, pp. 669-678.
[36] N. Sarafianos, T. Giannakopoulos, C. Nikou, and I. A. Kakadiaris, "Curriculum learning of visual attribute clusters for multi-task classification," Pattern Recognition, vol. 80, pp. 94- 2018.
[37] P. Sen, G. Namata, M. Bilgic, L.. Getoor, B. Galligher, and T. Eliassi-Rad, "Collective classifica- tion in network data," Al magazine, vol. 29, no. 3, pp. 93-93, 2008
[38] O Shehur, M. Mumme, A. Bojchevski, and S. Günnemann, "Pitfalls of graph neural network evaluation," arXiv preprint
/tfi:////1.00880 2018.
[39] Q Sun, J. Li, H. Peng, J. Wu, Y. Ning, P. S. Yu, and L. He, "Sugar: Subgraph neural network with reinforcement pooling and self-supervised mutual information mechanism," " in Proceedings of the Web Conference 2021, 2021, pp. 2081-222 1-20...
[40] Q. Sun, H. Peng. J. Li, S. Wang, X. Dong, L. Zhao, S. Y. Philip, and L. He, "Pairwise learning for name disambiguation in large-scale heterogeneous academic networks." in 2020 IEEE International Conference on Data Mining (ICDM). IEEF, 2020, pp. 511-520.
[41] Y. Tian, D. Krishnan, and P. Isola, "Contrastive multiview coding," arXiv preprint arXiv: 150499 2019.
[42] Y. Tian, C. Sun, B. Poole, D. Krishnan, C. Schmid, and P. Isola, "What makes for good views for contrastive learning," arXiv preprint arXi::2005.10243 2020.
12

---

[43] Z. Tong, Y. Liang, C. Sun, X. Li, D. Rosenblum, and A. Lim, "Digraph inception convolutional networks," Advances in Neural Information Processing Systems, vol. 33, 2020.
[44] Z. Tong, Y. Liang, C. Sun, D. S. Rosenblum, and A. Lim, "Directed graph convolutional network," arXiv preprint arXiv:2004. 13970, 2020.
[45] M. Tschannen, J. Djolonga, P. K. Rubenstein, S. Gelly, and M. Lucic, "On mutual infor- mation maximization for representation learning," in International Conference on Learning Representations, 2019.
[46] P. Veliëković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, "Graph attention networks." arXiv preprini arXiv: 10903, 2017.
[47] P. Veličković, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm, "Deep graph infomax," " arXiv preprint arXiv: 10341, 2018.
[48] V. Verma, M. Qu, A. Lamb, Y. Bengio, J. Kannala, and J. Tang, "Graphmix: Regularized training of graph neural networks for semi-supervised learning." arXiv preprint arXiv: /909. 1715, 2019.
[49] L. Wang, C. Gao. C. Huang, R. Liu, W. Ma, and S. Vosoughi, "Embedding heterogeneous networks into hyperbolic space without meta-path," in Proceedings of the AAAI conference on artificial intelligence, 2021.
[50] L. Wang, C. Huang, W. Ma. X. Cao, and S. Vosoughi, "Graph embedding via iiffusiion-wavllet. based node feature distribution characterization. 2021.
[51] Y. Wang. S. Liu, M. Yoon, H. Lamba, W. Wang. C. Faloutsos, and B. Hooi, "Provably robust node classification via low-pass message passing," " in 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020, pp. 621-630.
[52] Y. Wang, W. Wang, Y. Liang, Y. Cai, and B. Hooi, "Graphcrop: Subgraph cropping for graph classification," arXiv preprint arXiv:2009. 10564, 2020.
[53] Y. Wang. W. Wang, Y. Liang, Y. Cai, and B. Hooi, "Curgraph: Curriculum learning for graph classification," in Proceedings of the Web Conference 2021, 2021, pp. 1238-1248.
[54] Y. Wang, W. Wang, Y. Liang, Y. Cai, and B. Hooi, "Mixup for node and graph classification," in Proceedings of the Web Conference 2021, 2021, pp. 3663-3674.
[55] Y. Wang, W. Wang. Liang. Cai, J. Liu, and B. Hooi, "Nodeaug: Semi-supervised node classification with data augmentation." in KDD, 2020, pp. 207-217.
[56] F. Wu, T. Zhang, A. H. d. Souza Jr, C. Fifty, T. Yu, and K. Q. Weinberger, "Simplifying graph convolutional networks," " arXiv preprint 1eXiv:1902.071:: 2019.
[57] M. Wu, C. Zhuang, M. Mosse, D. Yamins, and N. Goodman, "On mutual information in contrastive learning for visual representations" arXiv preprint 1rXiv:2005.13140 2020.
[58] X. Wu, E. Dyer, and B. Neyshabur, "When do curricula work?" arXiv preprint 201.0300, 2020.
[59] T. Xiao, X. Wang, A. A. Efros, and T. Darrell, "What should not be contrastive in contrastive learning," " arXiv preprint arXiv:2008.0565 2020.
[60] Yanardag and S. Vishwanathan, "Deep graph kernels," in Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, 2015, pp. 1365- 1374.
[61] C. Yang. Z. An, and Y. Xu, "Multi-view contrastive learning for online knowledge distillation," in ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2021. pp. 3750-3754.
[62] C. Ye, R. C. Wilson, C. H. Comin, L. d. F. Costa, and E. R. Hancock, "Approximate von neumann entropy for directed graphs," " Physical Review E, vol. 89, no. 5, p. 052804, 2014.
[63] Y. You, T. Chen, Y. Sui, T. Chen, Z.. Wang, and Y. Shen, "Graph contrastive learning with augmentations," Advances in Neural Information Processing Systems, vol. 33, 2020.
[64] X. Zhang, N. Brugnone, M. Perlmutter, and M. Hirn, "Magnet: A magnetic neural network for directed graphs," arXiv preprint 13X1 2021.
[65] Zhao, M. Mathieu, and Y. LeCun, "Energy-based generative adversarial network," arXiv preprint arXiv: 1609.006000332... 2016
13

---

[66] Z. Zhong, L. Zheng, G. Kang, S. Li, and Y. Yang, "Random erasing data augmentation." in AAAI, 2020, pp. 13 001-13 008.
[67] Y. Zhu, Y. Xu, Q. Liu, and Wu, "An empirical study of graph contrastive learning." " 2021.
[68] Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang, "Deep graph contrastive representation learning," arXiv preprint (xXi::000600413/11 2020.
[69] Y. Zhu, Y. Xu. F. Yu, Q. Liu, S. Wu, and L. Wang, "Graph contrastive learning with adaptive augmentation," arXiv preprint PrXiv:2010.149453 2020.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The main content of this paper is theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 2 and 3.
(b) Did you include complete proofs of all theoretical results? [Yes] See the Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] Our implement can be obtained at https: // thub.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Supplementary Material.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 5.2.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the Supplementary Material.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 5.2.
(b) Did you mention the license of the assets? [Yes] See the Supplementary Material.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "DtiKjT58Au_", "reviewer": "Reviewer_haDS", "summary": "The paper proposes to adopt graph contrastive learning (GCL) on directed graphs by addressing two problems: (i) retaining structure information (specific for digraph) in augmentations; (ii) increasing views of contrasting in the CL framework.\nTo reach these goals, authors propose Laplacian perturbation and the digraph contrastive learning framework (DiGCL).\nExperimental results verify the advantage of the proposed method.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(Originality) Studying GCL from the perspective of digraphs is novel for me.\n\n(Quality) The paper is generally well-presented, with the idea clearly conveyed. Experiments are conducted on multiple compared methods which is appreciated, but it would be better if larger datasets can be examined (e.g. ogb-level of scale of graphs) since small benchmarks though are conventionally used, are easy to be overfitted for certain methods to be less convinced.\nBesides, I have the following questions.\n\n(i) The motivation to propose Laplacian perturbation as augmentation is to preserve structure information which is presumably crucial for digraphs. Experiments support this by stating that, methods with structure-disrupting augmentations (MVGRL, GraphCL...) underperform while methods without augmentations (DGI, GMI) are competitive. I would challenge this assumption that should be application-specific. The examined datasets in this paper focus on citation networks and social networks, which are usually noisy that the preserved structure knowledge might not be desired. Thus, perturbation invariance is introduced from previous GCL methods to make models more robust to generate good representations. From this sense, I am not fully persuaded of the groundedness of this assumption. Further, in DGI actually augmentations are applied if you refer to their negative pairs, which should be also structure-disrupting but still maintain good performance.\n\n(ii) In Section 2.3 the connection between Laplacian perturbation and von Neumann entropy is drawn which is good, but in Section 3 the DiGCL framework then goes back to InfoNCE loss, which makes me feel dispartment of the story. Can authors clarify the connection of between Section 2.3 and Section 3?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "8bseQ-i3jr2", "reviewer": "Reviewer_WA6U", "summary": "The paper describes a self-supervised framework called Laplacian perturbation to generate multiview, which can preserve the intrinsic graph structure. Unlike the original contrastive learning, the multi-view digraph contrastive learning framework can learn from all possible contrastive views generated by Laplacian perturbation. Training the contrastive learning in a multi-task curriculum learning way can progressively learn from multiple easy-to-hard contrastive views.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positives:\n- It is novel to train contrastive learning progressively in a curriculum learning way, and the experiments validate that this is a very effective modification.\n\n- Using perturbation to create data augmentation is an interesting insight. I feel it is somehow related to SimCSE, applying dropout to create noises. Also, the progressively changing levels of perturbation automatically push the model to learn from easy to difficult contrastive views is also new to me. It could be applied in other contrastive learning like to increase the dropout rate to a larger proportion.\n\nConcerns:\n- The caption for Figure 1 is not illustrative enough for understanding the overall structure. For example, how do U and V come from the pacing function? Why one node is red-colored and the other ones are blue-colored? I understand that every component is written in subsections clearly, but this figure should serve as the most important and informative part of the work in this paper.\n\n- Equation 10, the expectation is taken over \\Delta \\alpha1 and \\Delta\\alpha2, then maximize the whole objective function over f, right? It is not equivalent to what it said below: it requires the obtained optimal encoder works well with \\forall \\Delta \\alpha1 and \\Delta\\alpha2 \\in [0, 1 -\\alpha) to learn a more balanced and generalized representation. For all alpha1 and alpha2 should be equivalent to taking maximum over all \\Delta \\alpha1 and \\Delta\\alpha2 \\in [0, 1 -\\alpha). Then they take one of the views unperturbed, which deviates a little bit from the original objective, I feel it is possible to derive some theoretical guarantees in this change.\n\n- Laplacian perturbation part involves too many mathematical formulations, which is not easy to follow. Maybe the authors could provide some examples to illustrate the change before and after Laplacian perturbation, and move some of the theoretical justification parts to supplementary.\n\n- I feel that easy subtasks and hard subtasks are not a pair. Most of the papers I have read would say easy subtasks and difficult subtasks, or something like soft negatives and hard negatives. \n\n- I am not very familiar with graph learning, the results this paper present is like the performance of unsupervised learning can surpass those supervised learning, which is not common in the vision area. Can you elaborate more on this phenomenon? And I found out that in some other papers, like GRACE, the results on CITESEER is 72.1±0.5, which is much higher than 61.20 ± 0.20 reported here. Maybe it is due to the different network architecture, I feel some clarification should be made to explain the performance gap.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6hours"}, "extra_text": {}}, {"review_id": "2AbODgA2pPf", "reviewer": "Reviewer_fews", "summary": "This paper focuses on learning with directed graphs (digraphs), and aims to address the problems with existing GCL methods that 1) the augmentations undesirably alter meaningful structural information, and 2) the number of contrastive views is limited.\n\nAs the first contribution, the authors propose a solution called \"Laplacian perturbation\", where contrastive views are produced through changing the approximate eigenvector by tuning the teleport probability (of page rank). Laplacian perturbation preserves structural information, can be speeded up by power method (please see my question about this in the main review), and allows to produce an infinite number of contrastive views (please see my comments in the main review).\n\nThe second contribution of this work is the DiGCL framework, which performs graph contrastive learning between views by minimizing the InfoNCE loss, a lower bound to the mutual information. The authors also use curriculum learning to help with training, where they gradually \"anneal\" the difficulty of the contrastive tasks.\n\nThe effectiveness of DiGCL is demonstrated on various node-classification datasets, where DiGCL performs particularly well on directed graphs as desired.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strength**: The proposed Laplacian perturbation addresses the problem of altering informative structural information with previous augmentation methods, and has shown superior empirical performance especially on node-level tasks on directed graphs.\n\n**Concerns**: I do not agree with the claim about providing \"an infinite number of views\" and would consider the proposed method as offering two views instead, since the contrastive loss is calculated over two terms. Continuous augmentation (which in this case means varying $\\Delta\\alpha$) shouldn't count towards the number of views; for example, for images, we consider there to be 2 views rather than infinite views, even though color jittering is a continuous augmentation (modulo the discretization of pixel values).\n\n**Questions**:\n* About power method: the last equality of eq (5) is wrong, i.e. $\\mathbf{1}^{1 \\times n} \\pi_{\\text{appr}}^t \\mathbf{1}^{n\\times 1} \\neq \\pi_{\\text{appr}}^{t}$, since matrix (vector) multiplication is not commutative. This means the power method is not applicable.\n\n* Curriculum learning:\n  * how is the number of subtasks $M$ chosen? How would its choice affect the performance, and can it be tuned?\n  * What's the reason for using a uniform partition on $[0, 1-\\alpha)$, as opposed to e.g. randomly sample $M$ choices of $\\Delta\\alpha$ in $[0, 1-\\alpha)$?\n\n**Writing & Clarity**:\n* The paper is clearly situated in the literature which is appreciated.\n* Sec 2 currently refers heavily to a previous work and could benefit from some cleanup.\n* Definition of the scoring & pacing function: the notation should be from the domain to the image, both of which are sets, but $M, L, d$ are all numbers.\n* For related work, citation [12] actually states that more views don't help with learning (e.g. they compared with 3 views in the experiments), which is different from the premise of this work that graph learning needs more views. I think the discrepancy lies in what counts as a \"view\"; maybe changing from \"multi-view\" to \"multiple level of augmentation strength\" is more suitable and can help clarify.\n\n=======\nPost-rebuttal update: I thank the authors for their thoughtful and detailed responses. Unfortunately I think the current version doesn't provide either strong theoretical results or compelling experiments, so would not recommend an accept as of now. I encourage the authors to resubmit though, especially given that the additional results in your responses already look promising. Best of luck!", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As the authors explained, the main limitation is that since DiGCL is designed at node-level, its performance for graph-level tasks may not be as strong.\n\nThere is no direct societal impact for this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "10cKhnaotOo", "reviewer": "Reviewer_ZF6P", "summary": "This work presents a multi-view digraph contrastive learning framework. It can generate contrastive views by Laplacian perturbation and learn from them. The model is trained by the multi-task curriculum learning to progressively learn from multiple easy-to-hard contrastive views. Experiments on several datasets show the effectiveness.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work proposes the contrastive learning algorithm on directed graphs. To learn the characteristics of digraphs, this work first generates an arbitrary number of contrastive views with Laplacian perturbation. Then, it uses curriculum learning strategy to optimize the objective function. Through experiments, the authors empirically show the method outperforms various baselines.\n\nThe strengths of this work are as follows. 1) The research problem is important. Contrastive learning on digraphs is relatively under-explored in previous works. 2) The paper is relatively well-written and the ideas are clearly clarified. The figures illustrate the model framework clearly. 3) The proposed method achieves better results over various baselines on some datasets. The baselines considered in the experiments are extensive. \n\nI also have some concerns/questions on this work: 1) The motivation is not very clear. Why is it insufficient to use a small number of views? Why is the multi-task curriculum learning adopted in the method? What is the primary difference between contrastive learning on undirected and directed graphs? 2) The novelty and technical contributions of this work are limited. Although the theoretical part of the method is correct to me, it is incremental and similar to related works (see Digraph Inception Convolutional Networks. NeurIPS 2020). The data augmentation strategy using Laplacian perturbation is trivial. 3) The experiments are not convincing enough. To validate the performance, the authors choose few and small graph datasets. It can be more convincing if some popular larger datasets are considered (such as Open Graph Benchmark). More analysis of the experimental results should also be present to give more insights to the readers. How much performance gain comes from the part of the model design and the curriculum learning strategy?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work cannot solve the graph-level problems, such as pre-training on protein molecular, drug property prediction, etc. This work needs to manually design the pacing function to preplan the training speed, such as linear or exponential functions.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a novel idea of self-supervised learning with digraphs. The scores of the paper are somewhat borderline and the reviewers have had adequate reviews and discussions with the authors. The pros and cons of the paper are well discussed by the reviewers in the reviews. The AC finds the concerns on the novelty and significance of the idea slightly outweigh the pros. The reviewers also pointed out the lack of large-scale experiments and the authors responded that the paper's main contribution is the novel algorithm proposed but not large-scale experiments. This also seems to raise the bar for the theoretical contribution, which the paper does not seem to meet so far. 
Decision: Accept (Poster)