Year: 2021

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 across datasets, which suggests that searching over 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 to 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.

text: 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 across datasets, which suggests that searching over 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 to 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.

heading: 1 INTRODUCTION
text: 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 a 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 in learning representations for graphs and associated entities (nodes, edges, subgraphs), and they have been employed in various applications such as node classification (Kipf & Welling, 2016a; Veličković 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 in an unsupervised manner (Chen et al., 2020; Kolesnikov et al., 2019; Doersch et al., 2015). Many self-supervised methods have also been developed to facilitate graph representation learning (Jin et al., 2020; Xie et al., 2021) such as DGI (Veličković et al., 2019), PAR/CLU (You et 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 PAR is to predict the graph partitions of nodes. We examine how a variety of SSL tasks including DGI, PAR, CLU, PAIRDIS (Peng et al., 2020) and PAIRSIM (Jin et al., 2020; 2021) perform over 3 datasets. Their node clustering and node classification performance ranks are illustrated in Figure 1a and 1b, respectively. From these figures, we observe that different SSL tasks have distinct downstream 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 a single task, as different tasks have distinct importance according to specific dataset and downstream 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 1c. 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.
It is evident that many real-world graphs such as friendship networks, citation networks, coauthorship networks and co-purchase networks (McPherson et al., 2001; Shchur et al., 2018) satisfy the homophily assumption, i.e., “like attracts like”, or that connected nodes tend to share the same label. This is useful prior knowledge, as it directly relates the label information of downstream tasks to the graph structure. In this work, we explicitly take advantage of this prior knowledge and assume 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 pseudohomophily, 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 pseudo-homophily maximization can help maximize the upper bound of mutual information between pseudo-labels and downstream labels. (2) Based on pseudo-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 to adjust the task weights during search as shown in Figure 1d. (3) We evaluate the proposed AUTOSSL by composing various individual tasks on 7 real-world datasets. Extensive experiments have demonstrated that AUTOSSL can significantly improve the performance of individual tasks on node clustering and node classification (e.g., up to 10.0% relative improvement on node clustering).

heading: 2 BACKGROUND AND RELATED WORK
text: Graph Neural Networks. Graph neural networks (GNNs) are powerful tools for extracting useful information from graph data (Liu et al., 2021; Wu et al., 2019b; Kipf & Welling, 2016a; Veličković
et al., 2018; Hamilton et al., 2017; Kipf & Welling, 2016b; Pan et al., 2018). They aim to learn a mapping function fθ parameterized by θ to map the input graph into a low-dimensional space. Most graph neural networks follow a message passing scheme (Gilmer et al., 2017) where the node representation is obtained by aggregating the representation of its neighbors and its own representation. 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 representations. 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; Veličković et al., 2019; You et al., 2020; Hassani & Khasahmadi, 2020; Hu et al., 2019; Qiu et al., 2020; Zhu et al., 2020b). Specifically, those SSL methods construct a pre-defined pretext task to 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 learning is proposed to automatically select data augmentation and focuses on graph classification task. Another related work is AUX-TS (Han et al., 2021), which also adaptively combines different SSL tasks but the combination happens at the fine-tuning stage and thus requires label information. Multi-Task Self-Supervised Learning. Our work is also related to multi-task self-supervised learning (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 to automate every aspect of machine learning applications (Yao et al., 2018; Liu et al., 2018), such as feature engineering, model architecture search and loss function search. Among them, our work is highly related to loss function search (Zhao et al., 2021; Xu et al., 2018; Wang et al., 2020; Li et al., 2019). However, these methods are developed under the supervised setting and not applicable in self-supervised learning. Another related work is ELo (Piergiovanni et al., 2020), which evolves multiple self-supervised losses based on Zipf distribution matching for action recognition. However, it 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.

heading: 3 AUTOMATED SELF-SUPERVISED TASK SEARCH WITH AUTOSSL
text: In this section, we present the proposed framework of automated self-supervised task search, namely AUTOSSL. Given a graph G, a GNN encoder fθ(·) and a set of n self-supervised losses (tasks) {`1, `2, . . . , `n}, we aim at learning a set of loss weights {λ1, λ2, . . . , λn} such that fθ(·) trained with the weighted loss combination ∑n i=1 λi`i 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-supervised task search as follows:
min λ1,··· ,λn H(fθ∗(G)), s.t. θ∗ = argmin θ L(fθ, {λi}, {`i}) = argmin θ n∑ i=1 λi`i(fθ(G)), (1)
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, we need an unsupervised quality measure H 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.

heading: 3.1 PSEUDO-HOMOPHILY
text: Most common graphs adhere to the principle of homophily, i.e., “birds of a feather flock together” (McPherson et al., 2001), which suggests that connected nodes often belong to the same class; e.g. connected publications in a 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 a graph (Zhu et al., 2020a). Formally, it can be defined as follows,
Definition 1 (Homophily). The homophily of a graph G with node label vector y is given by h(G, y) = 1 |E| ∑ (v1,v2)∈E 1(yv1 = yv2), (2)
where yvi indicates node vi’s label and 1(·) is the indicator function.
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 Physics 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 et al., 2018) which uses the cluster assignments of learned features as pseudo-labels to train the neural network, we propose to calculate the homophily based on the cluster assignments, which we term as pseudo-homophily. Specifically, we first perform k-means clustering on the obtained node embeddings to get k clusters. Then the cluster results are used as the pseudo labels to calculate homophily based on Eq. (2). Note that though many graphs in the real world have high homophily, there also exist heterophily graphs (Zhu et al., 2020a; Pei et al., 2020) which have low homophily. We leave such type of graphs for future work. We also include a discussion on the homophily assumption in Appendix D.
Theoretical analysis. In this work, we propose to achieve self-supervised task search via maximizing 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 1. Suppose that we are given with a graph G = {V, E}, a pseudo label vector A ∈ {0, 1}N and a ground truth label vector B ∈ {0, 1}N defined on the node set. We denote the homophily ofA andB over G as hA and hB , respectively. If the classes inA andB are balanced and hA < hB , the following results hold: (1) the mutual information between A and B, i.e., MI(A,B), has an upper bound UA,B , where UA,B = 1N [ 2∆ log( 4N∆) + 2( N 2 −∆) log ( 4 N ( N 2 −∆) )] with ∆ = (hB−hA)|E|2dmax and dmax denoting the largest node degree in the graph; (2) if hA < hA′ < hB , we have UA,B < UA′,B . Proof. The detailed proof of this theorem can be found in Appendix B.
The above theorem suggests that a larger difference between pseudo-homophily and real homophily results in a lower upper bound of mutual information between the pseudo-labels and ground truth labels. Thus, maximizing pseudo-homophily is to maximize the upper bound of mutual information between pseudo-labels and ground truth labels, since we assume high homophily of the graph.

heading: 3.2 SEARCH ALGORITHMS
text: In the last subsection, we have demonstrated the importance of maximizing pseudo-homophily. Thus in the optimization problem of Eq. (1), we can simply setH to be negative pseudo-homophily. However, the evaluation of a specific task combination involves fitting a model and evaluating its pseudo-homophily, which can be highly expensive. Therefore, another challenge for automated selfsupervised task search is how to design an efficient algorithm. In the following, we introduce the details of the search strategies designed in this work, i.e. AUTOSSL-ES and AUTOSSL-DS.

heading: 3.2.1 AUTOSSL-ES: EVOLUTIONARY STRATEGY
text: 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 the covariance matrix adaptation evolution strategy (CMA-ES) (Hansen et al., 2003), a state-of-theart optimizer for continuous black-box functions, to evolve the combined self-supervised loss. We name this self-supervised task search approach as AUTOSSL-ES. In each iteration of CMA-ES, it samples a set of candidate solutions (i.e., task weights {λi}) 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 {λi} in [0, 1] and sample 8 candidate combinations for each iteration, which is trivially parallelizable as every candidate combination can be evaluated independently.

heading: 3.2.2 AUTOSSL-DS: DIFFERENTIABLE SEARCH VIA META-GRADIENT DESCENT
text: While the aforementioned AUTOSSL-ES is parallelizable, the search cost is still expensive because it requires to evaluate a large population of candidate combinations where every evaluation involves fitting the model in large training epochs. Thus, it is desired to develop gradient-based search methods to accelerate the search process. In this subsection, we introduce the other variant of our proposed framework, AUTOSSL-DS, which performs differentiable search via meta-gradient descent. However, pseudo-homophily is not differentiable as it is based on hard cluster assignments from k-means clustering. Next, we will first present how to make the clustering process differentiable and then introduce how to perform differentiable search.
Soft Clustering. Although k-means clustering assigns hard assignments of data samples to clusters, it can be viewed as a special case of Gaussian mixture model which makes soft assignments based on the posterior probabilities (Bishop, 2006). Given a Gaussian mixture model with centroids {c1, c2, . . . , ck} and fixed variances σ2, we can calculate the posterior probability as follows:
p (x | ci) = 1√
2πσ2 exp
( −‖x− ci‖2
2σ2
) , (3)
where x is the feature vector of data samples. By Bayes rule and considering an equal prior, i.e., p(c1) = p(c2) = . . . = p(ck), we can compute the probability of a feature vector x belonging to a cluster ci as:
p (ci | x) = p (ci) p (x | ci)∑k j p (cj) p (x | cj) = exp− (x−ci) 2 2σ2∑k j=1 exp− (x−cj)2 2σ2 . (4)
If σ → 0, we can obtain the hard assignments as the k-means algorithm. As 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(fθ∗(G)) = 1
k|E| k∑ i=1 ∑ (v1,v2)∈E ` (p(ci | xv1), p(ci | xv2)) , (5)
where ` is a loss function measuring the difference between the inputs. With soft assignments, the gradient ofH w.r.t. θ becomes tractable. Search via Meta Gradient Descent. We now detail the differentiable search process for AUTOSSL-DS. A 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 {λi}. To address this issue, we can utilize meta-gradients, i.e., gradients w.r.t. hyperparameters, which have been widely used in solving bi-level problems in meta learning (Finn et al., 2017; Zügner & Günnemann, 2019). To obtain metagradients, we need to backpropagate through the learning phase of the neural network. Concretely, the meta-gradient ofH with respect to {λi} is expressed as
∇meta{λi} := ∇{λi}H(fθ∗(G)) s.t. θ ∗ = optθ(L(fθ, {λi, `i})), (6)
where optθ stands for the inner optimization that obtains θ ∗ and it is typically multiple steps of gradient descent. As an illustration, we consider optθ as T + 1 steps of vanilla gradient descent with learning rate , θt+1 = θt − ∇θtL(fθt , {λi, `i}). (7) By unrolling the training procedure, we can express meta-gradient as
∇meta{λi} := ∇{λi}H(fθT (G)) = ∇fθTH(fθT (G)) · [∇{λi}fθT (G) +∇θT fθT (G)∇{λi}θT ], (8)
with∇{λi}θT = ∇{λi}θT−1− ∇{λi}∇θT−1L(fθT−1 , {λi, `i}). Since∇{λi}fθT (G) = 0, we have
∇meta{λi} := ∇{λi}H(fθT (G)) = ∇fθTH(fθT (G)) · ∇θT fθT (G)∇{λi}θT . (9)
Note that θT−1 also depends on the task weights {λi} (see Eq. (7)). Thus, its derivative w.r.t. the task weights chains back until θ0. By unrolling all the inner optimization steps, we can obtain the meta-gradient∇meta{λi} and use it to perform gradient descent on {λi} to reduceH:
{λi} ←− {λi} − η∇meta{λi}, (10)
where η is the learning rate for meta-gradient descent (outer optimization).
However, if we use the whole training trajectory θ0, θ1, . . . , θT to calculate the precise metagradient, it would have an extremely high memory footprint since we need to store θ0, θ1, . . . , θT in memory. Thus, inspired by DARTS (Liu et al., 2018), we use an online updating rule where we only perform one step gradient descent on θ and then update {λi} in each iteration. During the process, we constrain {λi} in [0, 1] and dynamically adjust the task weights in a differentiable manner. The detailed algorithm for AUTOSSL-DS is summarized in Appendix C.

heading: 4 EXPERIMENTAL EVALUATION
text: In this section, we empirically evaluate the effectiveness of the proposed AUTOSSL on selfsupervised task search on real-world datasets. We aim to answer four questions as follows. Q1: Can AUTOSSL achieve better performance compared to training on individual SSL tasks? Q2: How does AUTOSSL compare to other unsupervised and supervised node representation learning baselines? Q3: Can we observe relations between AUTOSSL’s pseudo-homophily objective and downstream classification performance? and Q4: How do the SSL task weights, pseudo-homophily objective, and downstream performance evolve during AUTOSSL’s training?

heading: 4.1 EXPERIMENTAL SETTING
text: Since our goal is to enable automated combination search and discovery of SSL tasks, we use 5 such tasks including 1 contrastive learning method and 4 predictive methods – (1) DGI (Veličković et al., 2019): it is a contrastive learning method maximizing the mutual information between graph representation and node representation; (2) CLU (You et al., 2020), it predicts partition labels from Metis graph partition (Karypis & Kumar, 1998); (3) PAR (You et al., 2020), it predicts clustered labels from k-means clustering on 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 a dense diffusion matrix and is prohibitively memory/time-consuming 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, WikiCS, Citeseer, CoraFull, and ogbn-arxiv. To demonstrate the effectiveness 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 on the obtained embeddings. We set the number of 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 one-layer GCN (Kipf & Welling, 2016a) as our encoder and set the size of hidden dimensions to 512. We set 2σ2 = 0.001 and use L1 loss in the homophily loss function throughout the experiments. Further details of dataset statistics, data splits, and hyperparameter settings can be found in Appendix A.

heading: 4.2 PERFORMANCE COMPARISON WITH INDIVIDUAL TASKS
text: To answer Q1, Table 1 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, we 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-ES is 7.3% for WikiCS and 10.0% for Photo, 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 pseudo-homophily as shown in the P-H rows of Table 1. Among them, CLU tends to result in a low pseudo-homophily 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 to higher pseudo-homophily. Obs. 4: The performance of AUTOSSL-ES and AUTOSSLDS is close when their searched tasks lead to similar pseudo-homophily: the differences in pseudohomophily, 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 {λi} 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, if we hope to find the best task weights and retrain the model, we should turn to AUTOSSL-ES. More details on their differences can be found in Appendix E.3.

heading: 4.3 PERFORMANCE COMPARISON WITH SUPERVISED AND UNSUPERVISED BASELINES
text: To answer Q2, we compare AUTOSSL with representative unsupervised and supervised node representation learning baselines. Specifically, for node classification we include 4 unsupervised baselines, i.e., GAE (Kipf & Welling, 2016b), VGAE (Kipf & Welling, 2016b), ARVGA (Pan et al., 2018) and MVGRL, and 2 supervised baselines, i.e. GCN and GAT (Veličković et al., 2018). We also provide the logistic regression performance on raw features and embeddings generated by a 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 an end-to-end manner, while other baselines 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 Citeseer while the performance on Citeseer is still comparable to the state-of-the-art contrastive learning method MVGRL. When compared to supervised baselines, AUTOSSL-DS outperforms GCN and GAT in 4 out of 8 datasets, e.g., a 1.7% relative improvement over GAT on Computers. AUTOSSL-ES 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 performance. 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.

heading: 4.4 RELATION BETWEEN DOWNSTREAM PERFORMANCE AND PSEUDO-HOMOPHILY
text: In this subsection, we investigate the relation between downstream performance and pseudohomophily and correspondingly answer Q3. Specifically, we use the candidate task weights sampled in the AUTOSSL-ES searching trajectory, and illustrate their node clustering (NMI) and node classification performance (ACC) with respect to their pseudo-homophily. The results on Computers and WikiCS are shown in Figure 2 and results for other datasets are shown in Appendix E.1. We observe that the downstream performance tends to be better if the learned embeddings tend to have higher pseudo-homophily. We also can observe that clustering performance has a clear relation with pseudo-homophily for all datasets. Hence, the results empirically support our theoretical analysis in Section 3.1 that lower pseudo-homophily leads to a 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 to concentrate on the high pseudo-homophily regions for 5 out of 7 datasets.

heading: 4.5 EVOLUTION OF SSL TASK WEIGHTS, PSEUDO-HOMOPHILY AND DOWNSTREAM PERFORMANCE
text: Visualization for Learned Task Weights. To answer Q4, we visualize the final task weights searched by AUTOSSL-ES on all datasets through the heatmap in Figure 3a. From the figure, we
Clu Par PairSim PairDis DGI
Physics
Photo
CS
Wiki-CS
Citeseer
CoraFull
Computers
0.013 0.198 0.042 0.006 0.980
0.004 0.875 0.386 0.006 0.006
0.004 0.423 0.411 0.002 0.954
0.000 0.955 0.916 0.550 0.066
0.016 0.035 0.196 0.176 0.988
0.007 0.769 0.986 0.099 0.978
0.002 0.996 0.054 0.090 0.574
0.2
0.4
0.6
0.8
(a) AUTOSSL-ES
0 200 400 600 800 1000 Iteration
0.0
0.2
0.4
0.6
0.8
W ei
gh t v
al ue s Clu Par PairSim PairDis DGI
(b) AUTOSSL-DS
Figure 3: Visualization of Task Weights.
0 10 20 30 40 Iteration
0.82
0.84
0.86
0.88
0.90
Ps eu
do -h
om op
hi ly
(a) CoraFull
0 20 40 60 80 100 Iteration
0.88
0.89
0.90
0.91
0.92
0.93
0.94
Ps eu
do -h
om op
hi ly
(b) Citeseer
Figure 4: P-H change of AUTOSSL-ES
make three observations. Obs. 1: The searched task weights vary significantly from dataset to dataset. For example, the weights for PAR and DGI are [0.198, 0.980] on Physics while they are [0.955, 0.066] on WikiCS. Obs. 2: In general, Par benefits co-purchase networks, i.e. 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 in citation/co-authorship networks. Obs. 3: AUTOSSL-ES always gives very low weights to CLU. It could be the reason that the pseudo-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 are assigned with large values. Thus, both AUTOSSL-ES and AUTOSSL-DS agree that PAIRDIS and PAR are less important for CoraFull.
We further investigate how pseudo-homophily changes over iterations. For AUTOSSL-ES, we illustrate the mean value of resulted pseudo-homophily in each iteration (round) in Figure 4. We only show the results on CoraFull and Citeseer while similar patterns are exhibited in other datasets. It is clear that AUTOSSL-ES can effectively increase the pseudo-homophily and thus search for better self-supervised task weights. The results for AUTOSSL-DS are deferred to Appendix E.2 due to the page limit.

heading: 5 CONCLUSION
text: Graph self-supervised learning has achieved great success in learning expressive node/graph representations. 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 combinations 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 between the pseudo-labels and ground truth labels. Based on the pseudo-homophily measure, we develop two automated frameworks AUTOSSL-ES and AUTOSSL-DS to search the task weights efficiently. Extensive experiments have demonstrated that AUTOSSL is able to produce more generalize representations by combining various SSL tasks.

heading: A EXPERIMENTAL SETUP
text: Dataset Statistics. We evaluate the proposed framework on seven real-world datasets. The dataset statistics are shown in 4. 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 WikiCS (Mernyei & Cangea, 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/validation/test.
Hyper-parameter Settings. When calculating pseudo-homophily, we set the number of clusters to 5 for all datasets. Following DGI (Veličković et al., 2019) and MVGRL (Hassani & Khasahmadi, 2020), we we use a simple one-layer GCN (Kipf & Welling, 2016a) as our encoder. We set the size of hidden dimensions to 512, weight decay to 0, dropout rate to 0. For individual SSL methods and AUTOSSL-ES, we set learning rate to 0.001, use Adam optimizer (Kingma & Ba, 2014), train the models with 1000 epochs and adopt early stopping strategy with a patience of 20 epochs. 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 is 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, Computers, CoraFull, Photo, Physics, 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 we sample 2000 positive samples and 2000 negative samples for DGI on all datasets except Citeseer.
Hardware and Software Configurations. We perform experiments on one NVIDIA Tesla K80 GPU and one NVIDIA Tesla V100 GPU. Additionally, we use eight CPUs, with the model name as Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz. The operating system we use is CentOS Linux 7 (Core).

heading: B PROOF
text: Theorem 1. Suppose that we are given with a graph G = {V, E}, a pseudo label vector A ∈ {0, 1}N and a ground truth label vector B ∈ {0, 1}N defined on the node set. We denote the homophily of A and B over G as hA and hB , respectively. If the classes in A and B are balanced and hA ¡ hB , the following results hold: (1) the mutual information betweenA andB, i.e., MI(A,B), has an upper bound UA,B , where UA,B = 1N [ 2∆ log( 4N∆) + 2( N 2 −∆) log ( 4 N ( N 2 −∆) )] with ∆ = (hB−hA)|E|2dmax and dmax denoting the largest node degree in the graph; (2) if hA < hA′ < hB , we have UA,B < UA′,B . Proof. (1) We start with the proof of the first result. The mutual information between two random variables X and Y is expressed as
MI(X,Y ) = ∑ y∈Y ∑ x∈X p(A,B)(x, y) log ( p(X,Y )(x, y) pX(x)pY (y) ) . (11)
Let Ai and Bi denote the set of nodes in the i-th class in A and B, respectively. Following the definition in Eq. (11), the mutual information between A and B can be formulated as,
MI(A,B) = nA−1∑ i=0 nB−1∑ j=0 |Ai ∩ Bj | N log N |Ai ∩ Bj | |Ai| |Bj | , (12)
where nA, nB denote the number of classes in A and B. Since here we only consider 2 classes in A and B, we have
MI(A,B) = |A0 ∩ B0|
N log N |A0 ∩ B0| |A0| |B0| + |A0 ∩ B1| N log N |A0 ∩ B1| |A0| |B1|
+ |A1 ∩ B0|
N log N |A1 ∩ B0| |A1| |B0| + |A1 ∩ B1| N log N |A1 ∩ B1| |A1| |B1| . (13)
Let |A0 ∩ B0| = x, |A0| = a and |B0| = b. We then have |A0|+ |A1| = N ⇒ |A1| = N − a, |B0|+ |B1| = N ⇒ |B1| = N − b, |A0 ∩ B0|+ |A0 ∩ B1| = |A0| ⇒ |A0 ∩ B1| = a− x, |A0 ∩ B0|+ |A1 ∩ B0| = |B0| ⇒ |A1 ∩ B0| = b− x, |A0 ∩ B1|+ |A1 ∩ B1| = |B1| ⇒ |A1 ∩ B1| = N − b− a+ x.
(14)
With the equations above, we rewrite MI(A,B) as follows,
MI(A,B) = 1
N [x log
Nx ab + (a− x) log N(a− x) a(N − b)
+ (b− x) log N(b− x) (N − a)b + (N − b− a+ x) log N(N − b− a+ x) (N − a)(N − b) ]. (15)
Then we rewrite result (1) in the theorem as an optimization problem,
max f(x) = MI(A,B) (16)
with constraints,  0 ≤ |A0 ∩ B0| ≤ |A0| ⇒ 0 ≤ x ≤ a, 0 ≤ |A0 ∩ B0| ≤ |B0| ⇒ 0 ≤ x ≤ b, |A1 ∩ B1| ≥ 0⇒ x ≥ a+ b−N, |A0 ∩ B0|+ |A1 ∩ B1| ≤ N ⇒ x ≤ a+b2 , |A0 ∩ B1|+ |A1 ∩ B0| ≤ N ⇒ x ≥ a+b−N2 ,
(17)
Note that the equality of |A0 ∩ B0|+ |A1 ∩ B1| ≤ N holds when A and B are the same. However, A and B have different homophily, which indicates |A0 ∩ B0| + |A1 ∩ B1| cannot reach N (the same for |A0 ∩ B1|+ |A1 ∩ B0|). Let EA, EB denote the inter-class edges for A and B, respectively. Thus, hA = 1 − |EA||E| and hB = 1 − |EB | |E| . Since hA < hB , we have |EA| > |EB |. This indicates that there are at least |EA| − |EB | edges in A connecting nodes that belong to the same ground truth class, as shown in Figure 5.
Let dmax denote the maximum degree in the graph and we know that at least |EA|−|EB | dmax
nodes are “misplaced” inA, e.g., in Figure 5 the red node inA1 should be placed inA0 to achieve |A0 ∩ B0|+
|A1 ∩ B1| = N . Let ∆ = |EA|−|EB |2dmax = (hB−hA)|E| 2dmax , and we have |A0 ∩ B0|+ |A1 ∩ B1| ≤ N − 2∆ and |A0 ∩ B1|+ |A1 ∩ B0| ≤ N − 2∆. With the new constraints, we rewrite the optimization problem as
max f(x) = MI(A,B) s.t.  0 ≤ x ≤ a, x ≤ b, x ≥ a+ b−N, x ≤ a+b−2∆2 , x ≥ a+b−(N−2∆)2 ,
(18)
Further, the derivative of f(x) is expressed as follows,
f ′(x) = 1
N log x(N − b− a+ x) (a− x)(b− x) . (19)
Let f ′(x) > 0, we have x > abN ; let f ′(x) < 0, we have x < abN . Thus, f(x) is monotonically decreasing at [max(0, a + b − N, a+b−(N−2∆)2 ), ab N ] and monotonically increasing [abN ,min(a, b, a+b−2∆ 2 )].
Note that in the theorem we assume the pseudo-labels and ground truth classes are balanced, i.e., a = b = N2 . Then MI(A,B) becomes,
MI(A,B) = f(x) = 1
N
[ 2x log 4
N x+ 2(
N
2 − x) log
( 4
N ( N 2 − x)
)] . (20)
Hence, f(x) is monotonically decreasing at [∆, N4 ] and monotonically increasing [ N 4 , N 2 −∆]. So the maximum value of f(x) is at either x = ∆ or x = N2 − ∆. Further it is easy to know that f(N4 − x) = f( N 4 + x). Then we have f(∆) = f( N 2 −∆), and we can get the maximum value of f(x) as follows,
UA,B = max f(x) = f(∆) = 1
N
[ 2∆ log( 4
N ∆) + 2(
N
2 −∆) log
( 4
N ( N 2 −∆)
)] (21)
with ∆ = (hB−hA)|E|2dmax . In other words, MI(A,B) reaches its upper bound when |A0 ∩ B0| = (hB−hA)|E|
2dmax or N2 − (hB−hA)|E| 2dmax .
(2) From the constraints x ≤ a+b−2∆2 and x ≥ a+b−(N−2∆) 2 in Eq (18), we have a+b−(N−2∆)
2 ≤ a+b−2∆
2 ⇒ ∆ ≤ N 4 . Based on the discussion in (1), we know that f(∆) is monotonically decreasing at [0, N4 ], which means an increase of ∆ leads to a decrease in f(∆), i.e., a smaller value of UA,B . Since ∆ = (hB−hA)|E|2dmax , a decrease in hA will lead to a increase in ∆. Then we have UA,B < UA′,B if hA < hA′ < hB .
Remark on a more generalized case. We now discuss the case where we do not have assumptions on a and b. As we demonstrated in the above discussion, f(x) is monotonically decreasing at [max(0, a + b − N, a+b−(N−2∆)2 ), ab N ] and monotonically increasing [abN ,min(a, b, a+b−2∆
2 )]. Thus, the maximum value of f(x) should be one of the values of f(0), f(a+ b−N), f(a+b−(N−2∆)2 ), f(a), f(b) and f( a+b−2∆ 2 ). As our goal is to show that UA,B would be small with low hA, to simplify the analysis, we consider a large value of ∆ (or a small value of hA) which satisfies ∆ ≥ 12 |N − (a+ b)| and ∆ ≥ 1 2 |a− b|. This indicates x is bounded by [a+b−(N−2∆)2 , a+b−2∆ 2 ]. Then the maximum value of f(x), i.e., UA,B , is expressed as
UA,B = max(f( a+ b− (N − 2∆)
2 ), f( a+ b− 2∆ 2 )). (22)
When a+b−(N−2∆)2 ≤ ab N ≤ a+b−2∆ 2 , it is easy to see that larger ∆ (or smaller hA) will lead to smaller UA,B because both a+b−(N−2∆)2 and a+b−2∆ 2 will be closer to the minima point ab N . When abN ≤ a+b−(N−2∆) 2 ≤ a+b−2∆ 2 , UA,B = f( a+b−2∆
2 ). It decreases with the increase of ∆ (or the decrease of hA) because a+b−2∆2 gets closer to the minima point ab N . Similarly, when a+b−(N−2∆) 2 ≤ a+b−2∆ 2 ≤ ab N , UA,B decreases with the increase of ∆ (or the decrease of hA). To sum up, for small hA, the upper bound of MI(A,B), i.e., UA,B , decreases with the decrease of hA.

heading: C ALGORITHM
text: The detailed algorithm for AUTOSSL-ES is shown in Algorithm 1. Concretely, for each round (iteration) of AUTOSSL-ES, we sample K sets of task weights, i.e., K different combinations of SSL tasks, from a multivariate normal distribution. Then we train K graph neural networks independently on each set of task weights. Afterwards, we calculate the pseudo-homohily 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 is summarized in Algorithm 2. Specifically, we first update the GNN parameter θ through one step gradient descent; then we perform k-means clustering to obtain centroids, which are used to calculate the homophily lossH. Afterwards, we calculate the meta-gradient∇meta{λi}, update {λi} through gradient descent and clip {λi} to [0, 1].
Algorithm 1: AUTOSSL-ES: AutoSSL with Evolutionary Strategy for r in {0, . . . , R} do
1. Sample K sets of tasks weights from a multivariate normal distribution 2. 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 4. 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 {λi} and GNN parameters θ; for t in {0, . . . , T} do
1. θt+1 = θt − ∇θtL(fθt , {λi, `i}) 2. Perform k-means clustering on fθt(G) and obtain centroids {c1, c2, . . . , ck} 3. Calculate p (ci | x) according to Eq. (4) 4. Calculate homophily lossH according to Eq. (5) 5. {λi} ←− {λi} − η∇meta{λi} 6. Clip {λi} to [0,1]
end

heading: D DISCUSSIONS ON HOMOPHILY ASSUMPTION
text: Most of the graphs in our real life satisfy the homophily assumption (McPherson et al., 2001), such as social networks, citation networks, co-purchase networks, etc. Thus, in general, we can treat homophily as a prior knowledge for a majority of real-world graphs. Moreover, it has been shown in (Zhu et al., 2020a; Pei et al., 2020) that most GNNs (such as GCN, GAT, ChebyNet and GraphSage) heavily rely on the homophily assumption and fail to generalize to low-homophily (heterophily) graphs even with label information. Thus, following the design of most GNNs, we focus on the homophily graphs. In addition, to apply our method on heterophily graphs, we can use the graph transformation algorithm (Suresh et al., 2021) 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 in the unsupervised setting as a future work.

heading: E ADDITIONAL EXPERIMENTAL RESULTS
text: E.1 RELATIONSHIP BETWEEN DOWNSTREAM PERFORMANCE AND PSEUDO-HOMOPHILY
We provide more results on the relation between downstream performance and pseudo-homophily in Figure 6. Observations are already made in Section 4.4.
E.2 PSEUDO-HOMOPHILY OVER ITERATIONS
We investigate how pseudo-homophily changes over iterations for AUTOSSL-DS. The changes of pseudo-homophily, NMI, ACC and homophily loss (Eq. (5)) are plotted in Figure 7. From Figure 7a and 7b, we can observe that pseudo-homophily 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 in the figure, if we stop at the iteration when pseudo-homophily reaches the maximum value we can still get a high NMI and ACC. On a separate note, Figure 7c shows how the homophily loss used in AUTOSSL-DS changes over iterations. We note that in the first iterations the homophily loss is low but the pseudohomophily 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 is resolved as the embeddings become more distinguishable through iterations. Thus, we argue that the homophily loss in Eq. (5) is still a good proxy in optimizing pseudo-homophily.
E.3 EFFICIENCY ANALYSIS
E.3.1 TIME COMPLEXITY ANALYSIS
We analyze the time complexity of the proposed AUTOSSL. Here we call one set of task weights {λi} as one candidate solution. We denote the time of training one epoch on a given set of SSL tasks as to and the evaluation time is te. Suppose we need to train T epochs for the network. Then the time for running one single candidate solution is Tto+te; the time of runningR rounds of AUTOSSL-ES should be RTto +Rte. For AUTOSSL-DS, the running time is Tto + Tte. As an illustration, in an L-layer GCN with d as the number of hidden dimensions, to can be expressed as O(L|E|d+LNd2) and te has time complexity of O(KINd) with K being the number of clusters and I being the
number of iterations for k-means. Hence, we also express the time complexity of AUTOSSL-ES as O(RTL|E|d + RTLNd2 + RKINd) and that of AUTOSSL-DS as O(TL|E|d + TLNd2 + TKINd). Both of them linearly increase with the number of nodes N when E is proportional to N . We note that in AUTOSSL-DS, the complexity of calculating the second-order derivatives in backward propagation has an additional factor of O(|θ||{λi}|), which can be reduced to O(|{λi}|) with approximated Hessian-vector products. The factor can be neglected as the number of tasks O(|{λi}|) is small.
E.3.2 EMPIRICAL COMPARISON
For empirical comparison, we take Citeseer, Photo, CoraFull as examples to illustrate. As shown in Table 5, 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 a combination of 5 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 AUTOSSLES depends on the number of candidate solutions and usually takes a long time to run. However, AUTOSSL-DS significantly reduces the running time of AUTOSSL-ES. It is worth noting the stateof-the-art SSL task, MVGRL, takes a long time to run and suffers from the OOM issue when the dataset gets larger.

heading: F COMPARISON WITH DIFFERENT STRATEGY
text: In this subsection, we examine how other strategies of assigning task weights affect the quality of learned representations. The results are 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 underlined. 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, “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 information 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.

heading: G COMPARISON WITH RANDOM SEARCH
text: In this subsection, we choose Citeseer to study the difference between random search and evolutionary algorithm (AUTOSSL-ES), and report the result in Table 7. Specifically, the random search method randomly generates 800 sets of tasks weights and we evaluate the pseudo-homophily 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 AUTOSSLES: with the same search cost, the resulted pseudo-homophily of random search is not as 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.

heading: H BROADER IMPACT
text: 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 largescale social platforms for tasks including forecasting (Tang et al., 2020a), friend ranking (Sankar et al., 2021) and item recommendation (Ying et al., 2018; Wu et al., 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 is especially useful in low-resource settings or in pre-training/fine-tuning 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 or biased outcomes. We propose an approach to learn self-supervised representations by utilizing multiple types of pretext tasks in conjunction with one another. While this produces improved performance on 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.

Review summaries:
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 .   Homophily 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.   As 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).  Experiments 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. 

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.

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.   This 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).