Automated Self-Supervised Learning for Graphs
Authors: Wei Jin
Xiaorui Liu
Xiangyu Zhao
Yao Ma
Neil Shah
Jiliang Tang
Venue: ICLR 2022 Poster (2022)
Keywords: Self-supervised learning
Graph neural networks
AutoML

Abstract: Graph self-supervised learning has gained increasing attention due to its capacity to learn expressive node representations. Many pretext tasks, or loss functions have been designed from distinct perspectives. However, we observe that different pretext tasks affect downstream tasks differently cross datasets, which suggests that searching pretext tasks is crucial for graph self-supervised learning.  Different from existing works focusing on designing single pretext tasks, this work aims to investigate how to automatically leverage multiple pretext tasks effectively. Nevertheless, evaluating representations derived from multiple pretext tasks without direct access to ground truth labels makes this problem challenging. To address this obstacle, we make use of a key principle of many real-world graphs, i.e., homophily, or the principle that ``like attracts like,'' as the guidance to effectively search various self-supervised pretext tasks. We provide theoretical understanding and empirical evidence to justify the flexibility of homophily in this  search task. Then we propose the AutoSSL framework which can automatically search over combinations of various self-supervised tasks. By evaluating the framework on 7 real-world datasets, our experimental results show that AutoSSL can significantly boost the performance on downstream tasks including node clustering and node classification compared with training under individual tasks. 

Published as a conference paper at ICLR 2022
AUTOMATED GRAPHS
SELF-SUPERVISED
LEARNING
FOR
Wei Jin
Xiaorui Liu
Xiaoyu Zhao
Michigan State University j inwei2@msu. edu
Michigan State University x aarrui @msu edu
City University of Hong Kong xy zww.@chalcccooooooo ci cititiitttuu tu edu hhk
Yao Ma
Neil Shah
Jiliang Tang
New Jersey Institute of Technology yao. www.maanniit.oom
Snap Inc. nshahe snap. com
Michigan State University tangjil1 anngiil@mssl edu
ABSTRACT
Graph self-supervised learning has gained increasing attention due to its capacity learn expressive node representations. Many pretext tasks, or loss functions have been designed from distinct perspectives. However, we observe that differ- ent pretext tasks affect downstream tasks differently across datasets. which sug- gests that searching over pretext tasks is crucial for graph self-supervised learn- ing. Different from existing works focusing on designing single pretext tasks, this work aims to investigate how to automatically leverage multiple pretext tasks ef- fectively. Nevertheless, evaluating representations derived from multiple pretext tasks without direct access to ground truth labels makes this problem challeng- ing. To address this obstacle, we make use of key principle of many real-world graphs, i... homophily, the principle that "like attracts like," as the guidance to effectively search various self-supervised pretext tasks. We provide theoretical understanding and empirical evidence justify the flexibility of homophily in this search task. Then we propose the AUTOSSL framework to automatically search over combinations of various self-supervised tasks. By evaluating the framework on 8 real-world datasets, our experimental results show that AUTOSSL can sig- nificantly boost the performance on downstream tasks including node clustering and node classification compared with training under individual tasks.
INTRODUCTION
Graphs are pivotal data structures describing the relationships between entities in various domains such as social media, biology, transportation and financial systems (Wu et al.) 2019b Battaglia et al., 2018 Due to their prevalence and rich descriptive capacity, pattern mining and discovery on graph data is prominent research area with powerful implications. As the generalization of deep neural networks on graph data, graph neural networks (GNNs) have proved to be powerful learning representations for graphs and associated entities (nodes, edges, subgraphs), and they have been employed various applications such as node classification (Kipf Welling 2016a VVličkovid et al. 2018), node clustering (Pan et al. 2018), recommender systems (Ying et al. 2018 and drug discovery (Duvenaud et al. 2015).
In recent years, the explosive interest in self-supervised learning (SSL) has suggested its great potential in empowering stronger neural networks an unsupervised manner (Chen et al. 2020 Kolesnikov al. [019 Doersch et al. 2015). Many self-supervised methods have also been de- veloped to facilitate graph representation learning (Jin et al.] 2020 Xie et al. 2021 Wang et al.) 2022) such DGI (Veličković al. 2019), PAR/CLU (You al. 2020) and MvGRL (Hassani & Khasahmadi 2020). Given graph and node attribute data, they construct pretext tasks, which are called SSL tasks, based on structural and attribute information to provide self-supervision for training graph neural networks without accessing any labeled data. For example, the pretext task of
Work partially done while author was internship at Snap Inc.

---

Published as a conference paper at ICLR 2022
Dooest Pro Corpltry Croke
Pota compaaee Chame
64
Sarmm
640
0.36
0.37
D1E Aurti Ratho Sul.S
By Pail Paclor
Palsi
Hor atian
(a) Node Clustering
(b) Node Classification
(c) Combining Two Tasks (d) AUTOSSI.
Figure I: (a)(b): Performance of 5 SSL tasks ranked best (1) worst (5) by color node clustering and classification, showing disparate performance across datasets and tasks. (c): Clustering perfor- mance heatmap on Citeseer when combining 2 SSL tasks, PAIRSIM and PAIRDIS, with different weights. (d) AUTOSSL's 's search trajectory for task weights, achieving near-ideal performance.
PAR is predict the graph partitions of nodes. We examine how variety of SSL tasks including DGI, PAR, CLU, PAIRDIS (Peng et al., 2020) and PAIRSIM (Jin et al. 2020 2021) perform over datasets. Their node clustering and node classification performance ranks are illustrated in Figure La and [b respectively. From these figures, we observe that different SSL tasks have distinct down- stream performance cross datasets. This observation suggests that the success of SSL tasks strongly depends on the datasets and downstream tasks. Learning representations with a single task naturally leads to ignoring useful information from other tasks. As a result, searching SSL tasks is crucial, which motivates us to study on how to automatically compose a variety of graph self-supervised tasks to learn better node representations.
However, combining multiple different SSL tasks for unlabeled representation learning is immensely challenging. Although promising results have been achieved in multi-task self-supervised learning for computer vision, most of them assign equal weights to SSL tasks (Doersch & Zisserman 2017 Ren & Lee 2018 Zamir et al. 2018). Such combination might not always yield better performance than single task, as different tasks have distinct importance according to specific dataset and down- stream tasks. To illustrate this intuition, we combine two SSL tasks, PAIRDIS and PAIRSIM, with varied weights and illustrate the corresponding node clustering performance in Figure Ic] It clearly indicates that different choices of weights yield different performance. To circumvent this problem, we could plausibly search different weights for SSL tasks to optimize downstream tasks. However, to achieve such goal, we have two obstacles. First, the search space is huge, and thus search can be highly expensive. Hence, it is desirable to automatically learn these weights. Second, searching for optimal task weights typically requires guidance from downstream performance, which is naturally missing under the unsupervised setting. Thus, how to design an unsupervised surrogate evaluation measure that can guide the search process is necessary.
is evident that many real-world graphs such as friendship networks, citation networks, co- authorship networks and co-purchase networks (McPherson et al., 2001: Shchur et al., 2018) satisfy the homophily assumption, i.c.. "like attracts like", or that connected nodes tend to share the same it directly relates the label information of downstream tasks
label. This is useful prior knowledge, to the graph structure. In this work, we explicitly take advantage of this prior knowledge and as- sume that the predicted labels from good node embeddings should also adhere to homophily. Given the lack of ground-truth labels during SSL, we propose a pseudo-homophily measure to evaluate the quality of the node embeddings trained from specific combinations of SSL task. With pseudo- homophily, we are able to design an automated framework for SSL task search, namely AUTOSSL. Our work makes three significant contributions:
(1) To bridge the gap between unsupervised representation and downstream labels, we propose pseudo-homophily to measure the quality of the representation. Moreover, given graphs with high homophily, we theoretically show that the upper bound of mutual information between pseudo-labels and downstream labels.
maximization can help maximize
(2) Based pscudo-homophily, we propose two strategies to efficiently search SSL tasks, one employing evolution algorithm and the other performing differentiable search via meta-gradient descent. AUTOSSL is able adjust the task weights during search as shown in Figure Id
(3) We evaluate the proposed AUTOSSL by composing various individual tasks on 8 world datasets. Extensive experiments have demonstrated that AUTOSSI. can significantly improve
2

---

Published as a conference paper at ICLR 2022
the performance of individual tasks on node clustering and node classification (e.g., up to 10.0% relative improvement on node clustering).
BACKGROUND AND RELATED WORK
Graph Neural Networks. Graph neural networks (GNNs) are powerful tools for extracting useful information from graph data (Liu et al., 202T; Wu et al. 2019b Kipt & Welling 2016a] Veličkovid
et al. 2018 Hamilton et al. aim to learn a mapping function to parameterized by & to map the input graph into low-dimensional space. Most graph neural networks follow message passing scheme (Gilmer et al. 2017 where
& Welling 2016b Pan et al. 2018 Liu et al. 2020). They
the node representation is obtained by aggregating the representation of its neighbors.
Self-Supervised Learning in GNNs. Graph neural networks have achieved superior performance in various applications; but they also require costly task-dependent labels to learn rich represen- tations. To alleviate the need for the huge amount of labeled data, recent studies have employed
self-supervised learning in graph neural networks to provide additional supervision (Jin et al. 2020
2019 You al., 2020 Hassani & Khasahmadij 2020 Hu et al., 2019 Qiu et al, 2020 Zhu et al. 2020b Specifically, those SSL methods construct a pre-defined pretext task to
Veličković et al.,
assign pseudo-labels for unlabeled nodes/graphs and then train the model on the designed pretext task to learn representations. A recent work JOAO (You et al. 2021) on graph contrastive learn- ing is proposed to automatically select data augmentation and focuses on graph classification task. Another related work is AUX-TS (Han et al., (021). which also adaptively combines different SSL tasks but the combination happens at the tine-tuning stage and thus requires label information.
Multi-Tash SeperSuuee Learning. Our work is also related to multi-task self-supervised learn- ing (Doersch & Zisserman| 2017 Ren & Lee 2018 Zamir et al., 2018). Most of them assume the tasks with equal weights and perform training under the supervised setting. But our work learns different weights for different tasks and does not require access to labeled data.
Automated Loss Function Search. Tremendous efforts have been paid automate every aspect
of machine learning applications (Yao et al. 2018 Liu et al. 2018 Zhao et al. (021b), such as feature engincering. model architecture search and loss function search. Among them, our work is highly related to loss function search (Zhao et al. 202 Xu et al. 2018 [Wang et al. 2020 Li et al.) 2019. However, these methods are developed under the supervised setting and not not applicable in self- supervised learning. Another related work, ELo (Piergiovanni et al. (020). evolves multiple self- supervised losses based on Zipf distribution matching for action recognition. However, is designed exclusively for image data and not applicable to non-grid graph-structured data. The problem of self-supervised loss search for graphs remains rarely explored. To bridge the gap, we propose an automated framework for searching SSL losses towards graph data in an unsupervised manner.
AUTOMATED SELF-SUPERVISED TASK SEARCH WITH AUTOSSL
In this section. we present the proposed framework of automated self-supervised task search, namely AUTOSSL. Given a graph G. GNN encoder fo(.) and a set of n self-supervised losses (tasks) {ei, f2..... }. we aim at learning a set of loss weights {)1, A2........ with the weighted loss combination اn= X can extract meaningful features from the given graph data. The key challenge is how to mathematically define "meaningful features". If we have the access to the labels of the downstream task, we can define "meaningful features" as the features (node embeddings) that can have high performance on the given downstream task. Then we can simply adopt the downstream performance as the optimization goal and formulate the problem of automated self-supervise task search as follows:
such that fo(-) trained
min As.tm An
Hi(fo- (9)), s.t. = mig Lifo, (4)) = arg min (A(F(()))
(I)
where H denotes the quality measure for the obtained node embeddings, and it can be any metric that evaluates the downstream performance such as cross-entropy loss for the node classification task. However, under the self-supervised setting, we do not have the access to labeled data and thus cannot employ the downstream performance to measure the embedding quality. Instead, need an unsupervised quality measure ' to evaluate the quality of obtained embeddings. In a nutshell, one challenge of automated self-supervised learning is: how to construct the goal of automated task search without the access to label information of the downstream tasks.
3

---

Published as a conference paper at ICLR 2022
3.1
PSEUDO-HOMOPHN "SEUDO-HOMOPHILY
Most common graphs adhere to the principle of homophily, i.e. "birds of feather flock together" (McPherson et al., 2001). which suggests that connected nodes often belong to the same class; e.g. connected publications in citation network often have the same topic, and friends in social networks often share interests (Newman, 2018). Homophily is often calculated as the fraction of intra-class edges in graph (Zhu al., (020a). Formally, it can be defined as follows,
Definition 1 (Homophily). The homophity of graph 9 with node label vector y is given by
1
h(G.v)
(1) Lyy, Vo2)),
(2)
where Vv, indicates node v, 's label and 1() is the indicator functtonn
We calculate the homophily for seven widely used datasets as shown in Appendix A and we find that they all have high homophily, e.g., 0.93 in the P Physi as dataset. Considering the high homophily in those datasets, intuitively the predicted labels from the extracted node features should also have high homophily. Hence, the prior information of graph homophily in ground truth labels can serve as strong guidance for searching combinations of self-supervised tasks. As mentioned before, in self-supervised tasks, the ground truth labels are not available. Motivated by DeepCluster (Caron al., 2018) which uses the cluster assignments of learned features as pseudo-label to train the neural network, we propose to calculate the homophily based on the cluster assignments, which we term as pseudo- hreuoo-hompphll. Specifically, we first perform k-means clustering on the obtained node embeddings to get l clusters. Then the cluster results used as the pseudo labels calculate homophily based on Eq. (2). Note that though many graphs in the real world have high homophily, there also exist heterophily graphs (Zhu al. 2020a; Pei et al., 2020) which have low homophily. We include a discussion on the homophily assumption in Appendix
Theoretical analysis. In this work, we propose achieve self-supervised task search via maxi- mizing pseudo-homophily. To understand its rationality, we develop the following theorem to show that pseudo-homophily maximization is related to the upper bound of mutual information between pseudo-labels and ground truth labels.
Theorem Suppose that we are given with a graph G = E,, a pseudo label vector E {0, 13 and a ground truth label vector B E 10,11N defined the node set. We denote the homophily of A and B over G as A and hg. respectively. 1fe classes in A and are balanced and hA < hg, the following results hold: (1) the mutual information between A and B, i.e., M),A,)) has an upper bound UA,B, where UA,B = N [2A log( A) + 2 A) log ( - A)]] with
A (h. x)]E) and dmax denoting the largest node degree the graph: (2) if hA < ha < hB, we
2d
have UA,B ....
Proof. The detailed proof of this theorem can be found in Appendix B
The above theorem suggests that a larger difference between pscudo-homophily and real homophily results in a lower upper bound of mutual information between the pseudo-labels and ground truth labels. Thus, maximizing tion between pseudo-labels and ground truth labels, since we assume high homophily of the graph. Notably, while maximizing the upper bound does not guarantee the optimality of the mutual infor- mation, we empirically found that it works well in increasing the NMI value in different datasets, showing that it provides the right direction to promote the mutual information.
homodohhly is to maximize the upper bound of mutual informa-
3.2 SEARCH ALGORITHM
In the last subsection, we have demonstrated the importance of maximizing homppplll. Thus in the optimization problem of Fq. (T). we can simply set H. to be negative seeudo-hompphiy However, the evaluation of specific task combination involves fitting model and evaluating its pseudo-homophily, which can be highly expensive. Therefore, another challenge for automated self- supervised task search is how to design an efficient algorithm. In the following, we introduce the details of the search strategies designed in this work, ie.. AUTOSSL-ES and AUTOSSL-DS.
3.2. AUTOSSL-ES: EVOLUTIONARY STRATEGY
Evolution algorithms are often used in automated machine learning such as hyperparameter tuning due to their parallelism nature by design (Loshchilov & Hutter 2016). In this work, we employ
4

---

Published as a conference paper at ICLR 2022
the covariance matrix adaptation evolution strategy (CMA-ES) (Hansen al. 2003 state-of-the- art optimizer for continuous black-box functions, to evolve the combined sulf-super loss. We name this self-supervised task search approach AUTOSSL-ES. In each iteration of CMA-ES, it samples a set of candidate solutions (i.e., task weights {A;}) from a multivariate normal distribution and trains the GNN encoder under the combined loss function. The embeddings from the trained encoder are then evaluated by H. Based on H. CMA-ES adjusts the normal distribution to give higher probabilities to good samples that can potentially produce a lower value of H. Note that we constrain } in [0, 1] and sample 8 candidate combinations for each iteration, which is trivially parallelizable as every candidate combination can be evaluated independently.
3.2.2 AUTOSSL-DS: DUFFRENTIABLE SEARCH VIA META-GRADIEN DESCENT
While the aforementioned AUTOSSI.-ES parallelizable, the search cost is still expensive because it requires to evaluate large population of candidate combinations where every evaluation involves fitting the model in large training epochs. Thus, it is desired to develop gradient-basee search meth- ods to accelerate the search process. In this subsection, we introduce the other variant of our pro- posed framework, AUTOSSL-DS, which performs differentiable search via meta-gradient descent. However, hheuhlyhoopphily is not differentiable k-means clustering. Next, we will first present how to make the clustering process differentiable and then introduce how perform differentiable search.
it is based on hard cluster assignments from
Soft Clustering. Although k-means clustering assigns hard assignments of data samples to clus- ters, it can be viewed as a special case of Gaussian mixture model which makes soft assignments based on the posterior probabilities (Bishop (006). Given Gaussian mixture model with centroids {c1, S51,C,,.... .2,..., Cj and fixed variances o we can calculate the posterior probability as follows:
X 1x;l2
p (x c,)
exp
(3)
V2TO2
2o
where x is the feature vector of data samples. By Bayes rule and considering an equal prior, i.e., p(c1)= = p(c2) =... p(c;), we can compute the probability of feature vector x belonging
cluster c; as:
pcc, x) p(c)p(x(c)
exp (x
p(c))(((((c) Σ) exp
(x-e,)
2
If + O, we can obtain the hard assignments as the k-means algorithm. we can see, the probability of each feature vector belonging to a cluster reduces to computing the distance between them. Then we can construct our homophily loss function as follows:
H(fo- E
Σ
(p(c, Xn;), ( Xxz)),
(5)
1=1 (E1,
where l is a loss function measuring the difference between the inputs. With soft assignments, the gradient of H w.r.t. 0 becomes tractable.
Search via Meta Gradient Descent. We now detail the differentiable search process for AUTOSSI-DDS. naive method to tackle bilevel problems is to alternatively optimize the inner and outer problems through gradient descent. However, we cannot perform gradient descent for the outer problem in Eq. [1) where H is not directly related to {A.). To address this issue, we can uti- lize meta grediggra,,nnss i.c., gradients w.r.t. hyperparameters, which have been widely used in solving bi-level problems in meta learning (Finn et al. 2017 Zügner & Günnemann 2019). To obtain meta- gradients, we need to backpropagate through the learning phase of the neural network. Concretely, the meta-gradient of H with respect to (X:) is expressed as
(x.) == V (G)) s.t. 0" = opt,( (,)),
where opt, stands for the inner optimization that obtains 0* and it is typically multiple steps of gradient descent. As an illustration, we consider opt, as T + steps of vanilla gradient descent with learning rate e,
Oc+1 O, - L(fo, (Ar,e))
By unrolling the training procedure, express meta- meta-gradient as
mieeta : (G)) Vo, [A.}
(()) (V. (G) + (GV (8)
5

---

Published as a conference paper at ICLR 2022
with V Va.orr V 0 -1----Vip (A)) - V [(fr- (A:) == (2.) Hifo, (G) = V fog H(for (G)) Ve, fo, (G)V (2.0r.
(Ac,le)) Ver_,
Since V Vor (G) O, we have
((A) meta
(9)
Note that 0r-1 also depends on the task weights {A,} (see Eq. 7 Thus, its derivative w.r.t. the task weights chains back until On. By unrolling all the inner optimization steps, we can obtain the meta-gradient ((.) and use it to perform gradient descent on {A:} to reduce H:
(A: + (A:) V
{A.}
(10)
where 77 is the learning rate for meta meta-gradieet descent (outer optimization).
However, if we use the whole training trajectory 0, 0......00 0r to calculate the precise meta- gradient, would have an extremely high memory footprint since we need to store fn .,...., Or in memory. Thus, inspired by DARTS (Liu al. 2018), we use an online updating rule where we only perform one step gradient descent on O and then update } in each iteration. During the process, constrain } in [0, 1] and dynamically adjust the task weights in a differentiable manner. The detailed algorithm for AUTOSSL-DS is summarized in Appendix C
4 EXPERIMENTAL EVALUATION
In this section, we empirically evaluate the effectiveness of the proposed AUTOSSL self- supervised task search on real-world datasets. We aim to answer four questions as follows. Q1: Can AUTOSSL achieve better performance compared to training How does AUTOSSL compare to other unsupervised and supervised node representation learning baselines? Q3: Can observe relations between AUTOSSI's 's pseudo-homoohily objective and downstream classification performance? and Q4: How do the SSI. task weights, pseudo-homophily objective, and downstream performance evolve during AUTOSSL's training?
individual SSL tasks? Q2:
4.1 EXPERIMENTAL. SETTING
Since our goal is to enable automated combination search and discovery of SSI. tasks, we use such tasks including 1 contrastive learning method and 4 predictive methods - (1) DGT (Veličkovid cet al. 2019): it is a contrastive learning method maximizing the mutual information between graph representation and node representation: (2) CLU (You et al. (020). it predicts partition labels from
Metis graph partition (Karypis& & Kumar 1998); (3) PAR You et al., 2020). it predicts clustered labels from k- k-means clustering node features; (4) PAIRSIM (Jin et al. 2020 2021). it predicts
pairwise feature similarity between node pairs and (5) PAIRDIS (Peng et al. 2020). it predicts shortest path length between node pairs. The proposed AUTOSSL framework automatically learns to jointly leverage the 5 above tasks and carefully mediate their influence. We also note that (1) the recent contrastive learning method, MvGRL (Hassani & Khasahmadi 2020), needs to deal with dense diffusion matrix and is prohibitively memory/tme htw.or//ccmm-ccuuiinggg for larger graphs; thus, we only include it as a baseline to compare as shown in Table 2 and (2) the proposed framework is general and it is straightforward to combine other SSL tasks.
We perform experiments on 8 real-world datasets widely used in the literature (Yang et al. 2016 Shchur et al., 2018 Mernyei & Cangea 2020 Hu et al.] 2020). i.e., Physics, CS, Photo, Computers, Wikiss, Citeseer, CoraFull, 1, and ogbn-
To demonstrate the effec- tiveness of the proposed framework, we follow (Hassani & Khasahmadi] 2020) and evaluate all methods on two different downstream tasks: node clustering and node classification. For the task of node clustering, we perform k-means clustering clusters to the number of ground truth classes and report the normalized mutual information (NMI) between the cluster results and ground truth labels. Regarding the node classification task, we train a logistic regression model on the obtained node embeddings and report the classification accuracy on test nodes. Note that labels are never used for self-supervised task search. All experiments are performed under 5 different random seeds and results are averaged. Following DGI and MvGRL, we use a simple lne-layer GCN (Kipf & Welling, 2016a) as our encoder and set the size of hidden dimensions to 512. We set 2n = 0.001 and use [.1 loss in the homophily loss function throughout the experiments. Further details of experimental setup can be found Appendix A.
the obtained embeddings. We set the number of
4.2 PERFORMANCE COMPARISON WITH INDIVIDUAL TASKS
To answer Q1. Table ! summarizes the results for individual self-supervised tasks and AUTOSSL under the two downstream tasks, i.e., node clustering and node classification. From the table,

---

Published as a conference paper at ICLR 2022
Table 1: Performance comparison of self-supervised tasks (losses) on node clustering and node clas- sification. The NMI rows indicate node clustering performance; ACC rows indicate node classifica- tion aceuracy (%); P-H stands for pseudo homophll AUTOSSL regularly outperforms individual pretext tasks. (Bold: best in all methods; Underline: best in individual tasks). Blue and red numbers indicate the statistically significant improvements over the best individual task, via paired t-test at level 0.05 and 0.1, respectively (same for Table 2 and Table 3).
Self Supervised Task
ALTOSSL
Datasel
Metric
Ct.
PAR
PAIS
PAIRDNS
Dri
E8
DS
NMI
0.177.10.00
0.262.0.02
0.341
0.160.0.04
0.310 02
0.366
0.344_o.02
MikiCS
ACC
74.19+0.a1
75. 10.17
75.80+0.37
75. 78.2840..0
70.4
76 60 80.0.13
76.58
P-H
0.549
0.567
0.603
0.463
0.600
0.751
0.749
NMI
0.318
1.416
0.428
0.404
0.438 do
0. 0.449.0.01
0.449
Citasear
ACC
+5-00
71.36-0.44
70.72+p.a3
71.6410
14.444
72.00-0.32
P-H
0.787
0.916
0.885
0.901
0.934
0.543
D.934
NMI
0.17120.00
0.433
1:0
0.387
0.300
0.318go.m 02
0.487 01
0. 10.01
Computers
ACC
76.20 70.20
87, 87.26 15.15
82.64-1.15
85 45.20+0.41
63:45
87:26-0..4
88. 1840.43
P-H
0.473
0.314
0,206
0.238
0.503
0.611
NMI
0. 1128
0.498
0.409
0.406
0.462
0.508
0. g..00
CoraPull
ACC
44 11.93+u.aa 53
67 67.54-0.33
56.23+0..0
58 58.48+p.50
60.42
61.01 -0.01
11.10s
P-H
0.494
0.887
0.649
0.728
0.888
0.503
0.805
NMI
0.858
0.767 01
0.T49
0.635
0o.0.
0.772
=..71
CB
ACC
88.6810.22 27
92. 22.78
92.68 0s
80.561101
90.91 10
93.26
98.35 38.35.00.0
P-H
0.845
0.882
0.886
0.786
0,883
0.896
0.800
NMI
0. 0.6922+0.o
0.704
0.674-6.00
0. 0.420
0.670
0. 0.726.
Physice
ACC
93.60
95.07
95.05.0.
11.601100
94.031o
19..57.9.08
95. 13..13...0
P-H
0.911
0.913
0.505
0.821
0.906
0.921
0.9223
NMI
0.327
+o.01
0.439-0.04
0.203+p.0s
0.376+o.n3 oo.
0.560+p.04
0.515
Photo
ACC
90.33 1......0 20
91. 91.76
91.1310.35
91.97 19.32
92.08
92.04 s9
92.71 10.33
P-H
0.4234
0.002
0.428
0.327
0.401
0.791
0.616
NMI
0.305 01
0.410+0.01
0.379
0.314
0.318
0 0.424
0.417go.00
oghn-arxiv
ACC
66.66 1.0 34
67.9010.110
67.82
67.63
67.98 so
05.0 0.830
60.13.0004
P-H
0.441
0,080
0.482
0.326
0.391
0.780
NMI
6.3
4.1
65
Average
ACC
688
4.9
5.4
make several observations. Obs 1: individual self-supervised tasks have different node clustering and node classification performance for different datasets. For example, in Photo, DGI achieves the highest classification accuracy while PAR achieves the highest clustering performance; CLU performs better than PAIRDIS in both NMI and ACC on Physics while it cannot outperform PAIRDIS in WikiCS, Citeseer, Computers and CoraFull. This observation suggests the importance of searching suitable SSL tasks to benefit downstream tasks on different datasets. Obs. 2: Most of the time, combinations of SSL tasks searched by AUTOSSL can consistently improve the node clustering and classification performance over the best individual task on the all datasets. For example, the relative improvement over the best individual task on NMI from AUTOSSL-RS is 7.3% for WikiCs and 10.0% for Photo, o, and its relative improvement on ACC is 1.3% for Wikics. These results indicate that composing multiple SSL tasks can help the model encode different types of information and avoid overfitting to one single task. Obs. 3: We further note that individual tasks resulted in different dneudo-homophine as shown in the P-H rows of Table [ Among them, CLU tends to result in low pseudo-homophit and often performs much worse than other tasks in node clustering task, which supports our theoretical analysis in Section 3.1 It also demonstrates the necessity to increase pseudo-homophily as the two variants of AUTOSSL effectively search tasks that lead higher pseudo- hooouuooo Obs. 4: The performance of AUTOSSL-ES and AUTOSSL- DS is close when their searched tasks lead to similar homophily, NMI and ACC are relative smaller in datasets other than Photo and Computers. It is worth noting that sometimes AUTOSSL-DS can even achieve higher pseudo-homophily than AUTOSSL-ES. This indicates that the online updating rule for } in AUTOSSL-DS not only can greatly reduce the searching time but also can generate good task combinations. In addition to efficiency, we highlight another major difference between them: AUTOSSL-ES directly finds the best task weights while AUTOSSL-DS adjusts the task weights to generate appropriate gradients to update model parameters. Hence, we hope to find the best task weights and retrain the model, we should tum to AUTOSSL-ESS. More details on their differences can be found in Appendix H.3
the differences in pseudo-
7

---

Published as a conference paper at ICLR 2022
4.3 PERFORMANCE COMPARISON WITH SUPERVISED AND UNSUPERVISED BASELINES
To answer Q2, we compare AUTOSSL with representative unsupervised and supervised node rep- resentation learning baselines. Specifically, for node elassification we include 4 unsupervised base- lines, i.c. GAE (Kipf & Welling 2016b), VGAE (Kipf & Welling, 2016b). ARVGA (Pan et al. 2018) and MvGRL, and supervised baselines, i.c. GCN and GAT (Veličković et al.) 2018). We also provide the logistic regression performance on raw features and embeddings generated by ran- domly initialized encoder, named as Raw-Feat and Random-Init, respectively. Note that the two supervised baselines, GCN and GAT, use label information for node representation learning in end-to-end manner, while other buselines and AUTOSSL do not leverage label information to learn representations. The average performance and variances are reported in Table 2 From the table, we find that AUTOSSL outperforms unsupervised baselines in all datasets except Ci teseer while the performance Citeseer is still comparable to the state-of- of contrastive learning method MVGRL. When compared to supervised baselines, AUTOSSI-DDS outperforms GCN and GAT in 4 out of 8 datasets, e.g., a 1.7% relative improvement over GAT on Computers. AUTOSSL-ESS also outperforms GCN and GAT in 3/4 out of 8 datasets. In other words, our unsupervised representation learning AUTOSSL can achieve comparable performance with supervised representation learning baselines. In addition, we use the same unsupervised baselines for node clustering and report the results in Table 3 Both AUTOSSL-ES and AUTOSSL-DS show highly competitive clustering per- formance. For instance, AUTOSSL-ES achieves 22.2% and 27.5% relative improvement over the second best baseline on Physics and Wikics; AUTOSSL-DS also achieves 22.2% and 19.8% relative improvement on these two datasets. These results further validate that composing SSL tasks appropriately can produce expressive and generalizable representations.
Table 2: Node classification accuracy (%) The last two rows are supervised baselines. AUTOSSL consistently outperforms alternative supe-supe approaches, and frequently outperforms super- vised ones. (Bold/Underlinn best/runner-up among self-supervised approaches)
Model
Clteseer
Computers
CoraFoll
Physios
Fhoto
oghn wreelv
Avg
Randon-fnit
75.07
64.06 64.06:2.22
24.4220.29
45.07
28. 20.0
g3.33
87 07.01 87.01
67.55
60
Ran Feat
72.0620..0
61 01.50gn.00
74. 21.15an.
37.17
87 12:20.42
92.8 2n
79. 07
51.07
7.0
GAB
74.85.0.24
64.76.1.15
80. 80.25:10.2
57.55
92 30.0..0
20.66
91 21.51: s1.51
52.57 s..00
4.1
VGAE
74. 16.
67 07.50gn..r
81 81-05ge-a
53. n3
92 1520
94.5820017
88
52.0010
ARVGA
71 21.64-21.03
46. 20.18
67 67.01
45, 3..30
87 27.00
95.84 20.13
77: 17..74ss..e
$1.57
71
MVGRL
75.8920.12
72.3620.ez
84 $4.66.0.00
00.56:0.33
90.
94,30.0.20
49, s0.40
00M
AUTOSSL-ES
72:14.0.41
BT j0.44
00.50
10.10
07 -0.02
05.00....
09:31, y..0
AUTOSSL as
76.38 20.38.0.22
72.00
58. 18 :8:44
61.10 00.05
s3.35
90, 90.13
82.77 92.71:0.32
69. 69.13 -0.04
155
GEN
70.42.0.02
71.26
87.53
63.77
90 00.04:2..0
90.06
23..09
71.74:0.29 71.4620a4
77.30.0:1
71.00g0.69
86.7440.09
63.73g0.4
02.58,0..
95.54...00
02.30....0
Table 3: Clustering performance (NMI). AUTOSSL embeddings routinely exhibit superior NMI to alternatives. (Bold: best; Underline: runner-up).
Model
NIKICs
Citesaer
Carputera
CoraFul1
Plysics
Photo
oobc-arkiv
Rank
Rundom
0.107-20.00
0.35dga.os os
0.15
0.318gnot
0.716gm.0
0.301_m.m
0.246_20.1
0.306ga.01
2..02200.0
0.31020.00
0.100g3.0
0.2152a.0
0.61220.00
0.489 0:489_0.00
0:28220.00
0.150.0.01
GAB
0:243-20.02
0.313220.0
0.04122.00
0.4852n.co
0.045_n0.0
0.616 01
0.32520.m
YOAR
0:261 -0.0
0.38340.00
0.0231 a0.00
0.4b34p..0
0.7033-n.00
0.563... 0..0
0.530 -.00
0.311
ARVGA
0.257 -0.02
0.191 10.02
0.207
0.301 sb.01
8.616
0.325-
0.301 10.01-0000
0.201 0.201 +0.02
6.4
MvGRL
0.263_00.0
0.452
0.284ga.00
0.400
a.
D. 0.504 0..00
0.344.0.01
0OM
ALTOSSI-EES
0.566 go
0..49go.00
0 8066
0. 0.772
0.7255
D. 0.560_n0.4
0.424
166
AUTOSSL-DS
p.345_n.o
0.049
0. 0.448
0,500 go.
2.771gmm
0.726.0.00
0.515
0.417 on
2.1
4.4 RELATION BETWEEN DOWNSTREAM PERFORMANCE AND HSEUDO-HOMOPHILY
In this subsection, we investigate the relation between downstream performance and pseudo- homophily and correspondingly answer Q3. Specifically, we use the candidate task weights sampled in the AUTOSSL-EI searching trajectory. and illustrate their node clustering (NMI) and node clas- sification performance (ACC) with respect to their pseudo-homophily. The results on Computers rs and Wik i CS are shown in Figure 2 and results for other datasets are shown in Appendix E.. We observe that the downstream performance tends to be better the learned embeddings tend to have higher pseudo-homophily. We also can observe that clustering performance has clear relation with for all datasets. Hence, the results empirically support our theoretical analysis in Section 3.1 that lower pseudo- homophhly leads to lower upper bound of mutual information with ground truth labels. While classification accuracy has a less evident pattern, we can still observe that higher accuracy tends concentrate on the high pseudo-homophily regions for 5 out of 7 datasets.
8

---

Published as a conference paper at ICLR 2022
7330
$2650
Ness
houdsshomeppity
hauds-hommphhl
(a) Computers: NMI
(b) Wikics: NMI
(c) Computers: ACC
(d) Wikics: ACC
Figure 2: Relationship between downstream performance and pseudo-homophin
Peecc 8.31
6.54
WB6-- 1:00
005
8:00
Conputrr 2:00
Banatoon
teiaton
(a) AUTOSSL-ES
(b) AUTOSSL-DS
(a) CoraFull
(b) Citeseer
Figure 3: Visualization of Task Weights.
Figure 4: P-H change of AUTOSSI-ES
4.5 EVOLUTION OF SSL TASK WEIGHTS, PSEUDO-HOMOPHILY AND PERFORMANCE
To answer Q4, we visualize the final task weights searched by AUTOSSL-ES on all datasets through the heatmap in Figure Bal From the figure, we make three observations. Obs 1: The searched task weights vary significantly from dataset to dataset. For example, the weights for PAR and DGn [0.198, 0.980] Physics while they are [0.955, 0.066) WikiCS ksc. Obs 2: In general, Par benefits co-purchase networks, i.c. Photo and Computers; DGI is crucial for citation/co- authorship networks, i.e. Physics, CS, Citeseer, and CoraFull. We conjecture that local structure information (the information that PAR captures) is essential for co-purchase networks while both local and global information (the information that DGI captures) are necessary citation/co- authorship networks. Obs. 3: AUTOSSL-ES always gives very low weights to CLU, which indicates the pseudo-labed labels clustered from raw features are not good supervision on the selected datasets.
We also provide the evolution of task weights in AUTOSSL-DS for CoraFull dataset in Figure 3b The weights of the 5 tasks eventually become stable: CLU and PAIRDIS are assigned with small values while PAIRSIM, DGI and CLU assigned with large values. Thus, both AUTOSSL-ES and AUTOSSL-DS agree that PIIRDIS and PAR are less important for CoraFull.
We further investigate how pseudo-homoohily changes over iterations. For AUTOSSL-ES,, we il- lustrate the mean value of resulted pscudo-homophily in each itcration (round) in Figure 4 We only show the results CoraFull and Citeseer while similar patterns exhibited in other datasets. It is clear that AUTOSSL-ES can effectively increase the hempolyy and thus search for better self-supervised task weights. The results for AUTOSSL-DS are deferred to Ap- pendix E.2 due to the page limit.
5 CONCLUSION
Graph self-supervised learning has achieved great success in learning expressive node/graph repre- sentations. In this work, however, we find that SSL tasks designed for graphs perform differently on different datasets and downstream tasks. Thus, it is worth composing multiple SSL tasks to jointly encode multiple sources of information and produce more generalizable representations. However, without access to labeled data, it poses a great challenge in measuring the quality of the combi- nations of SSL tasks. To address this issue, we take advantage of graph homophily and propose pseudo-homophily to measure the quality of combinations of SSL tasks. We then theoretically show that maximizing pseudo-homophily can help maximize the upper bound of mutual information be- tween the pseudo-labels and ground truth labels. Based on the hhouddohy measure, we develop two automated frameworks AUTOSSL-ES and AUTOSSL-DS efficiently. Extensive experiments have demonstrated that AUTOSSL is able to produce more gen- eralize representations by combining various SSL tasks.
search the task weights

---

Published as a conference paper at ICLR 2022
ACKNOLWEDGEMENT
Wei Jin and Jiliang Tang are supported by the National Science Foundation (NSF) under grant num- bers IIS1714741, CNS1815636, IIS1845081 IIS1907704, IIS IIS1928278, IIS1955285, IO$2107215, and IOS2035472, the Army Research Office (ARO) under grant number 1NN-111---- the Home Depot, Cisco Systems Inc. and SNAP Inc.
ETHICS STATEMENT
To the best of our knowledge, there are no ethical issues with this paper.
REPRODUCIBILITY STATEMENT
To ensure reproducibility of our experiments, we provide our source code at https: //ap:://gta /ggithb. are described details in the appendix.
com/ SchandleBBang/Auttosss The We also provide a pseudo-code implementation of our framework in the appendix.
REFERENCES
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.011 2018.
Vinicius Zambaldi,
Emily M Bender, Timnit Gebru, Angelina McMillan Majaor,, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, pp. 610-623, 2021.
Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
Mathilde Caron, Piotr Bojanowski, Armand Joulin, and Matthijs Douze. Deep clustering for unsu- pervised learning of visual features. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 132-149, 2018.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
Enyan Dai and Suhang Wang. Say no the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pp.
2021.
Carl Doersch and Andrew Zisserman. Multi-task self-supervised visual learning. In Proceedings of the IEEE International Conference on Computer Vision, pp. 2051-2060, 2017.
Carl Doersch, Abhinav Gupta, and Alexei Efros. Unsupervised visual representation learning by context prediction. In ICCV, 2015.
David K Duvenaud, Dougal Maclaurin, Jorge Hauilera-pprrrgguirre Rafael Gómez-Bombarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, 2015.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.0244 02428, 2019.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference Machine Learning, pp. 1126-1135. PMLR, 2017.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In 2017.
10

---

Published as a conference paper at ICLR 2022
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances neural information processing systems, 2017.
Xueting Han, Zhenhuan Huang, Bang An, and Jing Bai. Adaptive transfer learning on graph neural networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery amp; Data Mining, KDD '21, pp. 565-574. Association for Computing Machinery, 2021.
Nikolaus Hansen, Sibylle D Müller, and Petros Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (cma-es). Evolutionary computation, 11(1):1-18, 2003.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In International Conference on Machine Learning, 2020.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. International Conference on Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 2020.
Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang. Zitao Liu, and Jiliang Tang. Self-supervised learning on graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10141, 2020.
Wei Jin, Tyler Derr, Yiqi Wang, Yao Ma, Zitao Liu, and Jiliang Tang. Node similarity preserving graph convolutional networks. In Proceedings of the 14th ACM International Conference Web Search and Data Mining. ACM, 2021.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on scientificc Computing. 1998.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, arXiv preprint arXiv:1412.6980 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- 2016a.
works. arXiv preprint
Thomas N Kipf and Max Welling. arXiv:1611.07308, 2016b.
Variational graph auto-encoders.
arXiv preprint
Alexander Kolesnikov, Xiaohua Zhai, and Lucas Beyer. Revisiting self-supervised visual represen- tation learning. In In CVPR, pp. 1920-1929, 2019.
Chuming Li, Xin Yuan, Chen Lin, Minghao Guo, Wei Wu, Junjie Yan, and Wanli Ouyang. Am-lfs: Automl for loss function search. In Proceedings of the IEEF/CVF International Conference on Computer Vision, pp. 8410-8419, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.09055 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining- ACM, 2020.
Xiaorui Liu, Wei Jin, Yao Ma. Yaxin Li, Hua Liu, Yigi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference on Machine Learning, 2021.
Ilya Loshchilov and Frank Hutter. Cma-es for hyperparameter optimization of deep neural networks. arXiv preprint arXiv: 1604.0726,, 2016.
Miller McPherson, Lynn
and James M Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, 27(1):11555) 444, 2001.

---

Published as a conference paper at ICLR 2022
Péter Mernyei and Cätälina Cangea. Wiki-cs: A wikipedia-based benchmark for graph neural net- works. arXiv preprint axXiv:200.00291, 2020.
Mark Newman, Networks. Oxford university press, 2018.
Shirui Pan, Ruiqi Hu, Guodong Long, Jing Jiang, Lina Yao, and Chengqi Zhang, Adversarially regularized graph autoencoder for graph embedding. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI' 18, pp. 2609-2611 AAAI Press, 2018.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 20Xiv:2002.022877. 2020.
Zhen Peng. Yixiang Dong, Minnan Luo, Xiao-Ming Wu, and Qinghua Zheng. Supf-supe graph representation learning via global context prediction. arXiv preprint arXiv:2003. 01604, 2020.
AJ Piergiovanni, Anelia Angelova, and Michael S Ryoo. Evolving losses for unsupervised video representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 133-142, 2020.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 150-11600, 2020.
Zhongzheng Ren and Yong Jae Lee. Cross-domain self-supervised multi-task feature learning us- ing synthetic imagery. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 762-771, 2018.
Claudia Veronica Roberts et al. Quantifying the extent which popular pre-trained convolutional neural networks implicitly learn high-level protected attributes. PhD thesis, Princeton University, 2018.
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference 2021, pp. 2535-25446 2021.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.0558 2018.
Shubhranshu Shekhar, Neil Shah, and Leman Akoglu. Fairod: Fairness-aware outlier detection.
arXiv preprini arXiv:2012.03063, 2020.
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns, arXiv preprint arXiv:2106.0m 06586, 2021.
Xianfeng Tang, Yozen Liu, Neil Shah, Xiaolin Shi, Prasenjit Mitra, and Suhang Wang. Knowing your fate: Friendship, action and temporal explanations for user engagement prediction so- cial apps. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge 2020a.
Discovery & Data Mining, pp.
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-relater biases in graph convoltuional net- works. In Proceedings the 29th ACM International Conference on Information & Knowledge Management, pp. 1435-1444, 2020b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Veličković, William Fedus, William L.. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. In International Conference Learning Representations, 2019. URL
net Etr.m/iduuddd/eee
Xiaobo Wang. Shuo Wang, Cheng Chi, Shifeng Zhang, and Tao Mei. Loss function search for face recognition. In International Conference on Machine Learning, pp. 10029-10038.0. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
Yu Wang, Wei Jin, and Tyler Demr Graph neural networks: Self-supervised learning. In Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 391-420. Springer, 2022.
Shu Wu, Yuyuan Tang, Yanqiao Zhu, Liang Wang, Xing Xie, and Tieniu Tan. Session-based rec- ommendation with graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 346-353, 2019a.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey on graph neural networks. arXiv preprint wrXiv:/9110005900 2019b.
Yaochen Xic, Zhao Xu, Jingtun Zhang, Zhengyang Wang. and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. arXiv preprint arXiv:2102.107557 2021.
Haowen Xu, Hao Zhang, Zhiting Hu, Xiaodan Liang, Ruslan Salakhutdinov, and Eric Xing. Au- toloss: Learning discrete schedules for alternate optimization. arXiv preprint arXiv:1810.0244 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pp. 40-48. PMLR, 2016.
Quamming Yao, Mengshuo Wang, Yuqiang Chen, Wenyuan Dai, Yu-Feng Li, Wei-Wei Tu, Qiang Yang, and Yang Yu. Taking human out of learning applications: A survey on automated machine learning. arXiv preprint 1rXiv:1810.13300 2018.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD. ACM, 2018.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? ICML, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning auto- mated. Proceedings of International Conference Machine Learning, 2021.
Amir R Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proceedings of the IEEE con- ference on computer vision and pattern recognition, pp. 3712-3722, 2018.
Jieyu Zhao, Tianlu Wang, Mark Yatskar, Ryan Cotterell, Vicente Ordonez, and Kai-Wei Chang-
Gender bias in contextualized word embeddings. arXiv preprint arXiv:1904.033100 2019.
Xiangyu Zhao, Haochen Liu, Wenqi Fan, Hui Liu, Jiliang Tang, and Chong Wang. Autoloss: Au- tomated loss function search in recommendations. Proceedings of the 27th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2021a.
Yue Zhao, Ryan Rossi, and Leman Akoglu. Automatic unsupervised outlier model selection. Ad- vances in Neural Information Processing Systems, 34, 2021b.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020a.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. arXiv preprint arXiv:2010. 14945, 2020b.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning, arXiv preprint arXiv:1902.084121 2019.
13

---

Published as a conference paper at ICLR 2022
A EXPERIMENTAL SETUP
Dataset Statistics. We evaluate the proposed framework on seven real-world datasets. The dataset statistics are shown in All datasets can be loaded from PyTorch Geometric (Fey & Lenssen 2019). When we evaluate the node classification performance. we need to use the training and test data, For Wi k CS (Mernyei & Cangea 2020), agbn-arx: aaxiv v (Hu et al. 2020) and Citeseer (Yang et al.) 2016), we use the public data splits provided by the authors. For other datasets, we split the nodes into 10%/10%/80% for training/valiaationnesst
Table 4: Dataset statistics.
Dataset
Network Type
#Nodes
#Edges
#Classes
#Features
Homophily
Nikics
Reference network
11,701
216,123
10
300
0.70
Co-suthorsbip network
18.333
81,894
6,805
0.81
Physics
Co-suthorship network
34,493
247,962
5
8,415
0,93
Computiers
purchase network
13.381
245,778
767
Phoso
Co-purchase network
7,487
119,043
8
745
0.83
CozaFull
Citation network
19.793
65,311
70
8,710
0.57
Citesees
Citation network
3,327
4,732
3.703
0.74
ogbn-arxiv
Ciation network
169,343
1,166,243
40
128
0.78
Klyper-paramedd Settings. When calculating hoopphlhom,hhily, we set the number of clusters to 10 for ogbn arxiv and Computers, and for other datasets. A small number of clusters can be more efficient but could be less stable. Following DGI (Veličković et al. 2019) and MvGRL (Has-) simple one-layer GCN (Kipt & Welling 2016a)
sani & Khasahmadi 2020), we encoder. We set the size of hidden dimensions to 512, weight decay to O, dropout rate to 0. For indi- vidual SSL methods and AUTOSSL-ES,
set learning rate 0.001, Adam optimizer (Kingmal & Ba 2014). train the models with 1000 epochs and adopt early stopping strategy. For AUTOSSL- DS, we train the models with 1000 epochs and choose the model checkpoint that achieves the highest pseudo-homophily. We use Adam optimizer for both inner and outer optimization. The learning rate for outer optimization set to 0.05. For AUTOSSL- ES, we use a population size of 8 for each round. Due to limited computational resources, we perform 80 rounds for Citeseer, 40 rounds for CS, Comput ers, CoraFull, Photo, Physics isc, Computers and Wikics. We repeat the experiments on 5 different random seeds and report the mean values and variances for downstream performance, To fit DGI into GPU memory on larger datasets and accelerate its training, instead of using all the nodes sample 2000 positive samples and 2000 negative samples for DGI all datasets except Citeseer.
Hardware and Software Configurations. We perform experiments one NVIDIA Tesla K80 GPU and one NVIDIA Tesla V100 GPU. Additionally, we use eight CPUs, with the model name as IRtel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz. The operating system we is CentOS Linux 7 (Core).
B PROOF
Theorem 1. Suppose that we are given with a graph = (V,E). pseudo label vector A (0, 1NN and a ground truth label vector B E 10.1)N defined on the node set. We denote the homophily of and B over as AA and ha, respectively. 1he classes in A and are balanced and hA i has the following results hold: (1) the mutual information between A and B. iee, MI( A, B), has an upper bound UAAB, where UA,B = [2A log A + 2 A) log (
( A))] with
A (hg bb)]E and dmace denoting the largest node degree in the graph; (2) if hA < h < hBs
2dws
have UA,B U.r..
Proof. (1) We start with the proof of the first result. The mutual information between two random variables X and Y is expressed as
(x,, px (x)pp
MI(X,Y)=
ΣΣ VEY FE
(2,))) log
(11)
14

---

Published as a conference paper at ICLR 2022
Let A, and B; denote the set of nodes in the i-th class in A and B, respectively. Following the definition in Eq. (II). the mutual information between and B can be formulated as,
nA- MI(A,
RA-Ina-
A n J
N NIA,
Σ
log
(12)
N
|A:1
i=0
j=U
where A, Bg denote the number classes A and B. Since here we only consider classes in A and B, we have
Ao n
Bol
N |.A0
n
Bul
|. A
N
|A n B1
MI(A, B)
log
log
A
|Bol
[A
|B|]
A
B
N |
n
Bol
|A 1
N
|A1 n Bil
log
log
(13)
N
AA [Bu]
N
|A [B
Let [A (0)55 Bol v, |A = a and
[B0
= b.
We then have
Aul + |A
= N + |A = N 0,
Bo + [
N + [Bi]
b,
Ag n Bol
+ Ao B
[Aol + |A n B = a I,
(14)
Au Bol
A1 B,
|Byl A Bg b R.
Au n B1
+ [A nnn B
BB =
|A n B, N 0 0 T.
With the equations above, rewrite MI(A, B) follows,
Nx
N(a x)
MI(A,B)
N F log
+ (a - x) log
ab
a(N - b)
N(b x)
(N a}b + (N b - a + x)) log N(N a x)
+
(b
x) log
(15)
(N a) - -b)
Then we rewrite result (1) in the theorem as an optimization problem, MI(A,
max f(x)
(16)
with constraints,
Ao 0 Bn
< Aol 0 a
S
Ao
0
Bg
S
= =
20= 2
(17)
A Bol
+|1 1 5
N
2---
[o B1
14 C B
N
Note that the equality of |Ao n Bbl |An n n | S N holds when A and B are the same. However, + |A, n B₁| cannot reach N (the + [A, n (. Let E.. denote the inter-class edges for A and B, respectively.
and B have different homophily, which indicates
same for |o n B1
Thus, AA
[aal and hB
|nll Since hΛ < hB, have |&A] |E This indicates | edges in connecting nodes that belong to the same ground truth
T2T
TeT
that there are at least
E
class, shown in Figure
EA E
Nodes 2n
Nodes B;
Intra-class edges
A
Inter-class edges
Figure 5: Iusttrationn for |A4 n Bol |A, n B The two dashed rectangles divide the nodes into Ag and Ai red and blue nodes denote nodes in Bg and B,, respectively.
Let dmax denote the maximum degree in the graph and we know that at least |Al-|Eul nodes "misplaced" in A, e.g., in Figure the red node in Ai should be placed in Ao achieve |An Bol
dmace
15

---

Published as a conference paper at ICLR 2022
|| n 1 N. Let A
Ex
(Ag-ha))E) and we have |AAu n Bol + |A, nB. S N NN-2 24
2d
2dha
and AA Bi| + A Bol
S N
2A.
With the new constraints, we rewrite the optimization problem as
0 x S a, I S b x 2 a + N,
max f(x) M) s.t.
(18)
x S ath 2A
a+b (N-2A) x 2
Further, the derivative of f(x) is expressed as follows,
1 z(N - 6 b- x f(()) N (a x (b x) Let f'(x) 0, we have x ab. N. let (x)
log
(19)
we have x N. Thus, fax is monotonically decreasing at [0ax((0, + b N, atb a+b-(N- (N-22),, ) de pab
and monotonically increasing
NN N. miiim,,,,b b, s+b-2 ].
2
Note that in the theorem we assume the pseudo-labels and ground truth classes are balanced, i.e., a b N. Then MI B) becomes,
1 MI(A, B) = f(x) - N 2x log
4 N x + 2( N
4 N --
]
2)) log
(20)
Hence, (x) is monotonically decreasing at [A, N
4 and monotonically increasing 1
I N A]. So
the maximum value of f(x) is at either A or z
N A. Further it is easy to know that A), and get the maximum value of
S( - ==)= = 1( x.). Then we have f(A) f( x
f(x) as follows,
A) + 2 N
(
4 N N
+)]]
UA = max f(x) = f(A) = N
2A log(
-
(21)
N
2
with
A
(kn-ha)le
In other words, MI(A, B) reaches its upper bound when |.o n Bol
20hea
(hn ha)--
N
(bn ann-Aaal
or
2dam
2
2dlax
(2) From the constraints x S atb-24 2A and > xNb-(N-2 in Eq (8). we have -+
e+h-22 22
A < N. Based on the discussion in (1), we know that f(A) is monotonically decreasing
at [0, ]. which means an increase of A leads to a decrease in f f(A), i.e., a smaller value of UA
Since A= (hn-ha)]el decrease in hA will lead to a increase in A. Then we have UA.B M
hA- < h, < 2dm.
hg-
Remark on more generalized case. We now discuss the case where we do not have assumptions on and b. As we demonstrated in the above discussion, f(x) is mono- tonically decreasing at [max(0, a + b - N, ((+6-(N-2A) ), ab and monotonically increasing [ minna,,, b, at 2))] Thus, the maximum value of f(x) should be one of the values of lab
2 )2))),
N.
f(0), f(a+b- b- N), 1attb-iNN-22 would be small with low h. to simplify the analysis,
f(a), and f( f(*th_2)) As our goal is to show that UA,
consider large value of A (or small value of ha) which satisfies A 2 |// (( + b)l and A 2 =//a- -bb. b). This indicates x is bounded by
a+b (2-24)
24 Then the maximum value of f(x), i.e., BA is expressed as
2
2
1 a (N 24), ), S + b 24
(22)
2
When (N
ab
a+b-2a it is easy see that larger A (or smaller ha) will lead S
2
N
to smaller UA, because both a+b- and 2t will be closer to the minima point ab N When ab N
< a+b-(N (N
atb-24 UA = |( ((= It decreases with the increase of 3
2 A (or the decrease of hea) because atb-24 gets closer to the minima point ab N. Similarly, when c+b-(N-22) < 2th 22 < gb. UA decreases with the increase of A (or the decrease of ha) To 2
sum up, for small AA the upper bound of MT(A, B), i.e., MA,B, B, decreases with the decrease of h
16

---

Published as a conference paper at ICLR 2022
C ALGORITHM
The detailed algorithm for AUTOSSL-ES is shown in Algorithm 1. Concretely, for cach round (it- eration) of AUTOSSL-ES, we sample K sets of task weights, i.e., K different combinations of SSL. tasks, from multivariate normal distribution. Then train K graph neural networks indepen- dently on each set of task weights. Afterwards, we calculate the pseudo-homohine for each network and adjust the mean and variance of the multivariate normal distribution through CMA-ES based on their pseudo-homohily.
The detailed algorithm for AUTOSSL-DS summarized in Algorithm 2. Specifically, first up- date the GNN parameter 9 through one step gradient descent; then we perform k-means clustering obtain centroids, which are used calculate the homophily loss H. Afterwards, we calculate the meta-gratn meta-gradient Vmeen update { through gradient descent and clip {A₂} to [o, 1].
(},)
Algorithm 1: AUTOSSL-ES: AutoSSL with Evolutionary Strategy
for
r (O..... R) do
1. Sample K sets of tasks weights from a multivariate normal distribution
Train K networks w.r.t. each set of task weights from scratch
3. Calculate pseudo-homophily P-H of node embeddings from each network
Adjust the multivariate normal distribution through CMA-ES based on P-H
end
Algorithm 2: AUTOSSL-DS: AutoSSL with Differential Search
Initialize self-supervised task weights {Xi] and GNN parameters 0; for in {0...., T) do
1. 0/+1 = 02 eVo,C(fn, ())
Perform k-means clustering on Jo, (g) and obtain centroids (c1, C2....; Ck.
3. Calculate (c, x) according to Eq. (4
Calculate homophily loss H according to Eq.
5. {Ai} {A+} V (x}
Clip (A:) to [0,1]
end
D DISCUSSIONS ON HOMOPHILY ASSUMPTION
Most of the graphs in our real life satisfy the homophily assumption (McPherson al. 2001
such as social networks, citation networks, co-purchase networks, etc. Thus, in general, we can treat homophily shown in (Zhu et al., 2020a| Pei et al.) 2020) that most GNNs (such as GCN, GAT, ChebyNet and GraphSage) heavily rely the homophily assumption and fail to generalize low-homophily (heterophily) graphs even with label information. Thus, following the design of most GNNs, we focus on the homophily graphs. addition, to apply our method on heterophily graphs, we can use the graph transformation algorithm (Suresh et al. (021) to increase the homophily of a given graph. While heterophily graphs also exist in real-world applications, the research of GNNs on heterophily graphs is still at the very early stage even in the cases where the label information is available. Therefore, we will leave the research for heterophily graphs the unsupervised setting as a future work.
prior knowledge for majority of real-world graphs. Moreover, it has been
E ADDITIONAL EXPERIMENTAL RESULTS
E. RELATIONSHIP BETWEEN DOWNSTREAM PERFORMANCE AND PSEUDO-HOMOPHILLY
We provide more results on the relation between downstream performance and
in 6 Observations are already made in Section 4.4
17

---

Published as a conference paper at ICLR 2022
CoraPul1: NMI
(b) CS: NMT
Citeseer: NMI Physica: NMI
(c) Photo: NMT
(f) CoraFull: ACC
CS: ACC
(h)
Citeseer: (i) Physics: ACC
Photo: ACC
ACC
Figure 6: Relationship between downstream performance and pseudo-homophily
2.15
ATE
431
(a) Clustering
(b) Classification
(c) Homophily loss
Figure 7: Pseudo-honee homoolyyy versus NMI/ACC/Loss on Citeseer for AUTOSSL-DS. The vertical
dashed line indicates the iteration when pseudo-homophily reaches the maximum value.
E.2 PSEUDO-HO HOMOPHILY OVER ITERATIONS
We investigate how pseudo-homophily, NMI, ACC and homophily loss (Eq. (5)) are plotted in Figure From Figure and 7b can observe that houpppll first increases and then becomes stable through iterations. The situation is a bit different for clustering and classification performance: NMI and ACC first increase with the increase of pseudo-homophily and then drop when pseudo-homophily is relatively stable. This indicates that overtraining can hurt downstream performance as the model will have the risk of overfitting on the combined SSL tasks. However, as shown the figure, we stop at the iteration when sgeudo-homophil reaches the maximum value we can still get a high NMI and ACC. On separate note, Figure 7c shows how the homophily loss used AUTOSSL-DS changes over iterations. We note that in the first iterations the homophily loss is low but the pseudo- homophily is also low. This is because the embeddings in the first few epochs are less separable and would lead to very close soft-assignment of clusters. As shown in the figure, however, the problem resolved as the embeddings become more distinguishable through iterations. Thus, we argue that the homophily loss in Eq. (5) is still good proxy in optimizing homophh.
changes over iterations for AUTOSSL-DS. The changes of
E.3 EFFICIENCY ANALYSIS
E. TIME COMPLEXITY ANALYSIS
We analyze the time complexity of the proposed AUTOSSI. Here we call one set of task weights { as one candidate solution. We denote the time of training one epoch on a given set SSL tasks as to and the evaluation time is f.. Suppose we need to train 7 epochs for the network. Then the time for running one single candidate solution Tt, + tt; the time of rumning R rounds of AUTOSSL-ES should be RTt, + Rte. For AUTOSSL-DS, the running time is Tt, Tt.. As an illustration, in an L-layer GCN with d as the number of hidden dimensions, t, can be expressed as (LL d LNd)) and has time complexity of (K)Nd) with K being the number of clusters and / being the
18

---

Published as a conference paper at ICLR 2022
number of iterations for k-means. Hence, we also express the time complexity of AUTOSSL-ES as O(RTLE + RTLNd + d)INd) and that of AUTOSSL-DS as O(TLEE + TLNd + TKINd). Both of them linearly increase with the number of nodes N when & is proportional to N. We note that in AUTOSSI.-DS, the complexity of calculating the second-order derivatives in backward propagation has additional factor of ((0)) which can be reduced to (({);))) with approximated Hessian-vector products. The factor can be neglected as the number of tasks O((Aa))) is small.
E.3.2 EMPIRICAL COMPARISON
For empirical comparison, we take Citeseer, Photo, CoraFull as examples to illustrate. As shown Table we compare the running time of different methods for training 1000 epochs on one NVIDIA-K80 GPU. The column of 5-Tasks indicates the running time of training combination of SSL. tasks, i.e. CLU, PAR, PAIRSIM, PAIRDIS and DGI, for 1000 epochs. Note that we report the running time of AUTOSSL-ES as the multiplication between 500 and the time of 5-Tasks, i.e., running 500 candidate solutions. From the table, we can see that the running time of AUTOSSL- ES depends on the number of candidate solutions and usually takes long time to run. However, AUTOSSL-DS significantly reduces the running time of AUTOSSL-ES. It is worth noting the state- of-the-ar art SSL task, MvGRL, takes long time run and suffers from the OOM issue when the dataset gets larger.
Table 5: Comparison of running time for training 1000 epochs on one NVIDIA-K80 GPU (12 GB memory). OOM indicates out-of-memory on this GPU.
DGI
MvGRL
5-Tasks
AUTOSSL-ES
AUTOSSL-DS
Citeseer
222s
1220s
322s
322sx500
1222s
Photo
177s
1074s
507s
507sx500
1766s
CoraFull
553s
OOM
858s
858sx500
3584s
F COMPARISON WITH DIFFERENT STRATEGY
In this subsection, we examine how other strategies of assigning task weights affect the quality of learned representations. The results summarized in Table 6 In this table, "Best SSL" indicates the best performance achieved by the individual tasks; "Random Weight" indicates the performance achieved by randomly assigning task weights; "Equal Weight" indicates the performance achieved by assigning the same task weights (i.e., all 1). The values that outperform "Best SSL." are under- lined. From the table, we make two observations. Obs 1. Unlike AUTOSSL, "Random Weight" and "Equal Weight" would hurt both NMI and ACC on some datasets, e.g., Citeseer. This suggests that SSL tasks might conflict with each other and thus harm the downstream performance. Obs 2. In some cases like Physics. iss "Equal Weight" can also improve both ACC and NMI, which aligns well with our initial motivation that combinations of SSL can help capture multiple sources of infor- mation and benefit the downstream performance. The two observations suggest that it is important to design a clever strategy that can automatically compose graph SSL tasks.
G COMPARISON WITH RANDOM SEARCH
In this subsection, we choose Citeseer to study the difference between random search and evolu- tionary algorithm (AUTOSSL-ESS), and report the result in Table Specifically, the random search method randomly generates 800 sets of tasks weights and we evaluate the homppilyy from the models trained with those task weights. Note that in AUTOSSL-ES we also evaluated 800 sets of tasks weights in total. From the table, we can see that random search is not as efficient as AUTOSSL- Es: with the same search cost, the resulted peudo-hhmophill of random search is not high as AUTOSSL-ES and the downstream performance is also inferior. This result suggests that search with evolutionary algorithm can find the optimum faster than random search.
19

---

Published as a conference paper at ICLR 2022
Table 6: Performance comparison of different strategies of assigning task weights. The NMI rows indicate node clustering performance; ACC rows indicate node classification accuracy (%); P-H stands for pseudo-homoohily. (Underline: better than "Best SSL").
Datinet
Metric
Best SSL
Random Weight
Equal Weight
AUTOSSL-ES
AUTOSSL-DS
NMI
0.439
0.
0.408
0.449
0.119
tittaaa Caaer
ACC
71.6410.4
70.6420.07
70.80
72.14
72,00
P-I
0.897
0.904
0.943
0.934
NMI
0.0
0.311
0.290
0.447 +00
0.418 20.01
Computers
ACC
87.2610.15
86.86
87.24
87.26
88. +8..4
0.406
0.378
0.503
0.511
NMI
0.4981.000
0. 0.458 0.002
0.493g0000
U.506
0.500 0.500
CoraFull
60.42.9.39
58.88g0.32
59.01
61.01 +0.50
61.10
P-II
0.811
0.868
0.903
0.895
NMI
0.767.10.01
0.761.1001
0.770 =0.01
0.772
+0.03
0.771+0.00
ACC
92.75+
92.88 + 0.220
93.22
93.26 +0.16
93.35 93.35-+0.00
P.H
0.879
0.881
0.895
0.890
NMI
0.509
0.341+0.02
0.366=0.02
0.560 +0.04
0.511+0.00
Photo
ACC
92.08
92.04g0:225
92.54 0.22
92, 122.044:0.e0
92.71 +0.52
P-H
0,412
0.472
0.791
0.626
NMI
0. 0.000
0.692=0.00
0.709 0.00
95, 37, +0.00
0.725
0.726 +0,00
Physice
ACC
00.07
95.09 15.09=0.00
95.39
95. 93.13 13.30.30
0.914
0.916
0.923
NMI
0.341
0.305
0.323
0.366 2
0.344
wikics
75.81
76.29 20.17
0..1
+0.18
76.58 20.28
P-I1
0.675
0.690
0.751
0.749
Table 7: Comparison with random search. The NMI indicates node clustering performance; ACC indicates node classification accuracy (%); P-H stands for eseudo-homophhe
Dataset
Metric
Random Search
AUTOSSL-ES
NMI
0.44322.00
0.449-a.01
Citeseer
ACC
71.68
72.14_0.41
P-H
0.934
0.943
H BROADER IMPACT
Graph neural networks (GNNs) are commonly used for node and graph representation learning tasks due to their representational power. Such models have also been recently proposed for use in large- scale social platforms for tasks including forecasting (Tang al.
(020a). friend ranking (Sankar 2019a), which impact many end users. Like other machine learning models, GNNs can suffer from typical unfairness issues which may arise due to sensitive attributes, label parity issues, and more (Dai & Wang. 2021). Moreover, GNNs can also suffer from degree-related biases (Tang et al., 2020b). Self-supervised learning (SSL) is often used to learn high-quality representations without supervision from labeled data sources, and especially useful in low-resource settings or in gre-training/finettmiin
let al. 2021) and item recommendation (Ying et al. [2188) Wu et al.
scenarios. Several works have illustrated the potential for representations learned in a self-supervised way to encode bias unintentionally, for example in language modeling (Bender et al.) 2021 Zhao et al. 2019), image
representation learning (Roberts et al. 2018) and outlier detection Shekhar et al. 2020).
Our work on automated self-supervised learning with graph neural networks shares the caveats of these two domains in terms of producing inadvertent biased outcomes. We propose approach to learn self-supervised representations by utilizing multiple types of pretext tasks in conjunction with one another. While this produces improved performance standard tasks used for benchmarking representation quality, it does not guarantee that these representations are fair and should be used without typical fairness checks in industrial contexts. However, such concerns are not inherently posed by our proposed ideas, but by the foundations it builds on in GNNs and SSL. We anticipate our ideas will drive further research in more sophisticated and powerful self-supervised graph learning, and do not anticipate direct negative outcomes from this work.
20


Reviews:
[{"review_id": "sD-3YadW2KU", "reviewer": "Reviewer_yXJg", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n(1) Performance gains are small or non-significant. Closely examining Tables 1-3, I see many scenarios where the best performing AutoSSL model performs on par with the strongest baselines or offers minuscule improvements. (that is, when taking into account standard variation of performance across independent runs). For example, in Table 2, results for CoraFull are 61.10±0.68 vs. 60.56±0.33 (= on-par performance), results for Physics are 95.57±0.02 vs. 94.66±0.10 (= minuscule improvement, which we only see after considering the stronger AutoSSL-ES variant, AutoSSL-DS performs at 95.13±0.36, which leads to essentially no performance). There are many such scenarios in Tables 1-3. \n\n(2) The AutoSSL approach is concerned with finding an effective way to combine individual SSL tasks (problem definition in Eq. 1, where $\\mathcal{H}$ is set to the negative pseudo-homophily). That is, it assumes that a set of $n$ SSL tasks are already given and it will find a good combination of those tasks formulated as a weighted addition of individual SSL tasks, each task associated with a learned task weight $\\lambda_i$. Such formulation seems quite restrictive. It does not allow for any interaction between the loss functions. Further, it also assumes that the user already knows what are potentially good SSL tasks. \n\n(3) It is unclear how the proposed strategy could be used for other contexts, such as link prediction and graph classification.", "summary_of_the_paper": "Self-supervised learning (SSL) methods for graphs take a given graph with node attribute information and construct various SSL tasks using structural and attribution information. These tasks provide self-supervision for training graph neural networks without accessing any labeled data. Existing studies show that different SSL tasks can lead to varying downstream performance across tasks, suggesting that the success of SSL tasks strongly depends on the dataset and the downstream task. This observation is important, yet not surprising, as similar findings were made in other data modalities (text, vision). As a result, selecting the 'right' SSL tasks can be important, which serves as a motivation for this study. \n\nThis study develops an approach (called AutoSSL) for combining multiple SSL tasks for unlabeled representation learning. To this end, it defines a pseudo-homophily metric to measure the quality of learned representations. Based on the pseudo-homophily, the study describes two techniques to search & combine SSL tasks, one using an evolutionary algorithm and the other using meta-gradient descent. The AutoSSL approach is evaluated on eight datasets considering combinations of five SSL tasks (one contrastive learning task and four predictive tasks). ", "summary_of_the_review": "Both AutoSSL variants (evolutionary strategy and the gradient descent version) seem ad-hoc and straightforward combinations of existing tools. This is not a problem on its own, however, the empirical gains are not convincing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QXdpgdEd0I-", "reviewer": "Reviewer_DNwN", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\n1. \"Is Homophily a Necessity for Graph Neural Networks?\" is a paper. In that paper, it states Homophily is not necessity. If dataset is Homophily, the task comes to easy. In this paper, authors use such easy datasets.\n2. If the meta-learning is the contribution, it is not a contribution of the paper but is a tool.\n3. The experimental results show it obtains better performance.\n4. Is the \"evolutionary strategy\" a contribution? \n", "summary_of_the_paper": "Authors use homophily datasets and meta learning. For self-supervised learning, authors use evolutionary strategy.", "summary_of_the_review": " homophily datasets is used and authors shows theoretical analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "H4w78OOPsSZ", "reviewer": "Reviewer_H8HY", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Strengths:\nThe paper is well-written and easy to follow. I can easily understand the idea of this paper.\n\nThis paper conducts extensive experiments on 7 different datasets from different domains to show their improved performances, which is very reasonable and convincing to me.\n\nWeaknesses:\nThe main concern I have towards this paper is its novelty. I can see there is much effort of this paper to make adjusting different pretext tasks on a graph, especially the authors bring up the important \"homophily\" property of graph to create pseudo labels for self-supervision. However, the essence of this paper is still dynamically adjusting weights for different losses, as the authors mentioned in the section Related Work of Automated Loss Function Search. There is so much work on reweighting different loss functions which have been well studied. Though the authors mentioned that \"the problem of self-supervised loss search for graphs remains rarely explored\", I find out the solved problem in this paper is actually an old problem, which is limited in novelty and significance.\n\nThe core contributions of this paper mainly include (i) making use of homophily to create pseudo labels for self-supervision; (ii) proposing AutoSSL-ES based evolutionary strategy (iii) proposing AutoSSL-DS based on meta-gradient descent. For (i), after checking the paper and appendix, I think it is good and reasonable. But why should the authors propose two different methods to solve the problem? The author mentions AutoSSL-ES requires evaluating a large population of candidate combinations which is not practical and AutoSSL-DS is much efficient. So, what are the advantages of AutoSSL-ES? The authors should give more explanations and analysis towards choosing these two methods. Otherwise, I would consider they are simply a combination of existing works without much contribution.\n\nI observe that the improvement of AutoSSL compared with the best result of individual tasks is not that significant. Moreover, the best results of individual tasks are from PAR and DGI. This leads to a question that does is really needs to weigh these 5 tasks. Maybe considering the other 3 tasks is not that helpful.\n\nAlso, more recent works of graph self-supervised learning can be considered and cited. For example, Han X, Huang Z, An B, et al. Adaptive Transfer Learning on Graph Neural Networks[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021: 565-574.", "summary_of_the_paper": "This paper mainly studies the problem of automatically weighting multiple self-supervised tasks on a graph without information of true labels, in order to make downstream node-level prediction tasks perform better. To overcome the challenge of missing ground truth in pre-training tasks, the authors propose to use a property named \"homophily\" of the graph to create pseudo labels. Then, they propose two algorithms to automatically adjust weights among different tasks: one is based on evolution algorithms; another is based on gradient descent. Extensive experiments on different real-world datasets show the improvement of the proposed methods compared with a single pretext task.", "summary_of_the_review": "Though this paper is well-written and studies an important and popular problem in graph learning. I still have concerns in different aspects.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2CtULa8R3t0", "reviewer": "Reviewer_3wSZ", "summary": "", "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": "Strengths:\n1. Paper is well written and easy to follow.\n2. Pseudo-homophily is shown to be a good surrogate measure for mutual information, and combining with search strategies proves effective on several benchmark datasets and tasks.\n\n\nWeaknesses:\n1. Method is somewhat simple and intuitive\n2. Method underperforms significantly on clustering task for Photos dataset. ", "summary_of_the_paper": "The proposed work looks at the task of automated self-supervised learning (SSL) on graphs, by using pseudo-homophily as a surrogate objective combined with a search strategy for the proposed approach, AutoSSL . \n\nHomophily is defined as the average of sameness of labels over pairs of connected vertices. Pseudo-homophily is computed by assigning labels based on k-means clustering. The work theoretically shows that maximizing pseudo-homophily is shown to maximize the upper bound of mutual information between pseudo-labels and downstream labels. \n\nAs cluster assignments are not differentiable and need search over a large space, the work looks at using evolutionary strategies (AutoSSL-ES) and differentiable search through soft cluster assignments using Gaussian mixture model (AutoSSL-DS).\n\nExperiments are performed on 5 SSL tasks and 8 datasets. AutoSSL based approaches outperform several other unsupervised baselines and perform comparably to supervised baselines when measured using normalized mutual information, accuracy of node classification and psuedo-homophily. ", "summary_of_the_review": "The method is well motivated and quite intuitive, the paper is easy to follow. Extensive experimental results are provided on several tasks and datasets, but statistical significance of improvements is missing, which is needed given large confidence intervals reported. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Strengths:
* Strong empirical study across multiple datasets. However, the gains are not as impressive as for other pretraining domains, such as text or images.
* Interesting formulation of pseudo-homophily as an objective to optimize in the self-supervision stage
* Well-written paper

Weaknesses:
* Novelty may be limited by the fact that the method is essentially learning (or searching) for a weighted average of self-supervised training objectives
* In that case, while the pseudo-homophily angle is interesting, there may be other appropriate baselines for yielding this weighted combination of tasks that are not explored
* There is concern about the degree of empirical improvements on certain datasets
Decision: Accept (Poster)