Multi-task Self-supervised Graph Neural Networks Enable Stronger Task Generalization
Authors: Mingxuan Ju
Tong Zhao
Qianlong Wen
Wenhao Yu
Neil Shah
Yanfang Ye
Chuxu Zhang
Venue: ICLR 2023 poster (2023)
Keywords: Graph Neural Network
Self-supervised Learning

Abstract: Self-supervised learning (SSL) for graph neural networks (GNNs) has attracted increasing attention from the graph machine learning community in recent years, owing to its capability to learn performant node embeddings without costly label information. One weakness of conventional SSL frameworks for GNNs is that they learn through a single philosophy, such as mutual information maximization or generative reconstruction. When applied to various downstream tasks, these frameworks rarely perform equally well for every task, because one philosophy may not span the extensive knowledge required for all tasks. To enhance the task generalization across tasks, as an important first step forward in exploring fundamental graph models, we introduce PARETOGNN, a multi-task SSL framework for node representation learning over graphs. Specifically, PARETOGNN is self-supervised by manifold pretext tasks observing multiple philosophies. To reconcile different philosophies, we explore a multiple-gradient descent algorithm, such that PARETOGNN actively learns from every pretext task while minimizing potential conflicts. We conduct comprehensive experiments over four downstream tasks (i.e., node classification, node clustering, link prediction, and partition prediction), and our proposal achieves the best overall performance across tasks on 11 widely adopted benchmark datasets. Besides, we observe that learning from multiple philosophies enhances not only the task generalization but also the single task performances, demonstrating that PARETOGNN achieves better task generalization via the disjoint yet complementary knowledge learned from different philosophies. Our code is publicly available at https://github.com/jumxglhf/ParetoGNN.

Published as a conference paper at ICLR 2023
MULTI-TASK SELF-SUPERVISED GRAPH NEURAL NET- WORKS ENABLE STRONGER TASK GENERALIZATION
Mingxuan Ju', Tong Zhao?, Qianlong Wen', Wenhao Yu',
Neil Shah?, Yanfang Ye!l, Chuxu Zhang University of Notre Dame, SSnap Inc., Brandeis University
1 [[mju,, yye7 edu; {t zhao, nshah) @ snap. com; 3 "chuxozharg@braaddei edu
ABSTRACT
Self-supervised learning (SSL) for graph neural networks (GNNs) has attracted increasing attention from the graph machine learning community in recent years, owing to its capability to learn performant node embeddings without costly label information. One weakness of conventional SSL frameworks for GNNs is that they learn through single philosophy, such as mutual information maximization or generative reconstruction. When applied to various downstream tasks, these frame- works rarely perform equally well for every task, because one philosophy may not span the extensive knowledge required for all tasks. To enhance the task general- ization across tasks, as an important first step forward in exploringfundammee fundamental graph models, we introduce PARETOGNN, multi-task SSL framework for node representation learning over graphs. Specifically, PARETOGNN is self-supervised by manifold pretext tasks observing multiple philosophies. To reconcile different philosophies, we explore a multiple-gradient descent algorithm, such that PARE- TOGNN actively learns from every pretext task while minimizing potential conflicts. We conduct comprehensive experiments over four downstream tasks (i.e., node classification, node clustering. link prediction, and partition prediction), and our proposal achieves the best overall performance across tasks on 11 widely adopted benchmark datasets. Besides, we observe that learning from multiple philosophies enhances not only the task generalization but also the single task performances, demonstrating that PARETOGNN achieves better task generalization via the dis- joint yet complementary knowledge learned from different philosophies. Our code is publicly available at https: //gptt/tth//////////////////tttt com/ juwxgghh//aret..ooo.
INTRODUCTION
Graph-structured data is ubiquitous in the real world (McAuley et al., 2015; Hu et al., 2020). To model the rich underlying knowledge for graphs, graph neural networks (GNNs) have been proposed and achieved outstanding performance on various tasks, such node classification (Kipf & Welling, 2016a; Hamilton et al., 2017), link prediction (Zhang & Chen, 2018; Zhao et al., 2022b), node clustering (Bianchi et al., 2020; You al., 2020b), etc. These tasks form the archetypes of many real-world practical applications, such as recommendation systems (Ying et al., 2018; Fan et al., 2019), predictive user behavior models (Pal et al., 2020; Zhao et al., 2021a; Zhang et al., 2021a).
Existing works for graphs serve well to make progress on narrow experts and guarantee their effectiveness on mostly one task or two. However, given a graph learning framework, its promising performance on one task may not (and usually does not) translate to competitive results on other tasks. Consistent task generalization across various tasks and datasets a significant and well-studied research topic in other domains (Wang et al., 2018; Yu et al., 2020). Results from the Natural Language Processing (Radford et al., 2019; Sanh et al., 2021) and Computer Vision (Doersch & Zisserman, 2017; Ni et al., 2021) have shown that models enhanced by self- self-supe learning (SSL) over multiple pretext tasks observing diverse philosophies can achieve strong task generalization and learn intrinsic patterns that are transferable to multiple downstream tasks. Intuitively, SSL over multiple pretext tasks greatly reduces the risk of overfitting (Baxter, 1997; Ruder, 2017), because
Corresponding Author.

---

Published as a conference paper at ICLR 2023
learning intrinsic patterns that well-address difficult pretext tasks is non-trivial for only one set of parameters. Moreover, gradients from multiple objectives regularize the learning model against extracting task ireeeeatll information (Ren & Lee, 2018; Ravanelli et al., 2020), that the model can learn multiple views of one training sample.
Nonetheless, current tfae-of-tthe-ee graph SSL frameworks mostly introduced according to only one pretext task with a single philosophy, such as mutual information maximization (Velickovic et al., 2019; Zhu et al., 2020; Thakoor et al., 2022), whitening decorrelation (Zhang al., 2021b), and generative reconstruction (Hou et al., 2022). Though these methods achieve promising results in some circumstances, they usually do not retain competitive performance for all downstream tasks across different datasets. For example. DGI (Velickovic et al., 2019), grounded on mutual information maximization, excels at the partition prediction task but underperforms on node classification and link prediction tasks. Besides, GRAPHMAR (Hou et al., 2022), based on feature reconstruction, achieves strong performance for datasets with powerful node features (e.g., graph topology can be inferred simply by node features (Zhang et al., 20), but suffers when node features are less informative, which is empirically demonstrated in this work. To bridge this research gap, we ask:
How combine multiple philosophies to enhance task generalization for SSL-based GNNs?
A very recent work, AUTOSSL (Jin et al., 2022), explores this research direction by reconciling different pretext tasks by learning different weights joint loss function so that the nove-level heedo-homophily is promoted. This approach has two major drawbacks: (i) Not all downstream tasks benefit from the homophily assumption. In experimental results shown by Jin et al. (2022), we observe key pretext tasks (e.g., DGI based on mutual information maximization) being assigned zero weight. However, our empirical study shows that the philosophies behind these neglected pretext tasks essential for the success of some downstream tasks, and this phenomenon prevents GNNs from achieving better task generalization. (ii) In reality, many graphs do not follow the homophily assumption (Pei et al., 2019; Ma et al., 2021). Arguably, applying such inductive bias to heterophilous graphs is contradictory and might yield sub-optimal performance.
In this work, we adopt different perspective: remove the reliance the graph task alignment with homophily assumptions while self-supervising GNNs with multiple pretext tasks. During the self-supervised training of our proposed method, given single graph encoder, all pretext tasks simultaneously optimized and dynamically coordinated. We reconcile pretext tasks by dynamically assigning weights that promote the Pareto optimality (Désidéri, 2012), such that the graph encoder actively learns knowledge from every pretext task while minimizing conflicts. We call our method PARETOGNN. Overall, our contributions are summarized as follows:
We investigate the problem of task generalization on graphs in more rigorous setting, where good SSL-based GNN should perform well not only over different datasets but also at multiple distinct downstream tasks simultaneously. We evaluate of-te-of-the-ar graph SSL frameworks in this setting and unveil their sub-optimal task generalization.
To enhance the task generalization across tasks, as an important first step forward in exploring fundamental graph models, we first design five simple and scalable pretext tasks according to philosophies proven to be effective in the SSL. literature and propose PARETOGNN, a multi-task SSL framework for GNNs. PARETOGNN is simultancously self-supervised by these pretext tasks, which are dynamically reconciled to promote the Pareto optimality, such that the graph encoder actively learns knowledge from every pretext task while minimizing potential conflicts.
We evaluate PARETOGNN along with 7 state-of-the-ar SSL-based GNNs on 11 acknowledged benchmarks over 4 downstream tasks (i.e., node classification, node clustering, link prediction, and partition prediction). Our experiments show that PARETOGNN improves the overall performance by up to +5.3% over the state-of-the-art SSL-based GNNs. Besides, we observe that PARE- TOGNN achieves SOTA single-task performance, proving that PARETOGNN achieves better task generalization via the disjoint yet complementary knowledge learned from different philosophies.
2 MULTI-TASK SELF-SUPERVISE LEARNING VIA PARETOGNN
In this section, we illustrate our proposed multi- task self supf-super learning framework for GNNs, namely PARETOGNN. As Figure illustrates, PARETOGNN is trained with different SSL tasks
2

---

Published as a conference paper at ICLR 2023
SSL Task-specific Augmentation
Node Representation Generation
Task Specific Projection Feat. Recon fi(+;0,)
Objective Formulation
Full Graph
JOO
L (G.TT.
Conv Loyer
Cocu Loper A?
Mutual Info. f2(+:0g)
L LzGGTTz.g.02
J2()
Lg 0
Decorelattion fa(+:0a)
T2(.)
:
GNN Encoder f(:;0g)
Lx Tk
Tx(
K-th SSL fx:
Forward Pass
Descent Direction for f f(; 0g)
Multi-Task Reconciliation
(VegL. Veg 22. L2 Vog VegErl
00
01 C
Convex Hull
U1 7o,
Min-norm
Gradient Calculation
+ a2 vogL2
Promoting
Pareto Optimality
+ as vogLs
Verlo
Vo Ey
+ ax Vog Ck
Vo, Fx
Vog
Figure 1: PARETOGNN is simultaneously self-supervised by K SSL tasks. All SSL tasks share the same GNN encoder and have their own projection heads (i.e., /x(:;Ox)) and augmentations (i.e., (+)))) such as node or edge dropping, feature masking, and graph sampling. To dynamically reconcile all tasks, assign weights to tasks such that the combined descent direction has minimum norm in the convex hull, which promotes Pareto optimality and further enhances task generalization.
simultancously to enhance the task generalization. Specifically, given a graph G with N nodes and their corresponding D-dimensional input features X E ND PARETOGNN learns GNN encoder fg(: 0,)
R Xxd parameterized by 0y. that maps every node in & to a d-dimensional vector (s.t. d < N). The resulting node representations should retain competitive performance across various downstream tasks without any update on 0g. With K self-supervised tasks, we consider the loss function for k-th SSL task (9; Tk, 0g. 0s) : G R where Ti refers the graph augmentation function required for k-th task, and 02 refers to task-specific parameters for k-th task (e.g., MLP projection head and/or GNN decoder). In PARETOGNN, all SSL tasks are dynamically reconciled by promoting Pareto optimality, where the norm of gradients w.r.t. the parameters of our GNN encoder 0y is minimized in the convex hull. Such gradients guarantee descent direction the Pareto optimality, which enhances task generalization while minimizing potential conflicts.
2.1 MULTI-TASK GRAPH SELF-SUPERVISED LEARNING
PARETOGNN a general framework for multi-task self-supervised learning over graphs. We regard the full graph G the data source; and for each task, PARETOGNN is self-supervised by sub-graphs sampled from G. followed by task-specific augmentations (i.e.. T&(-)). The rationale behind the exploration of sub-graphs is two-fold. Firstly, the process of graph sampling is naturally type of augmentation (Zeng et al., 2019) by enlarging the diversity of the training data. Secondly, model- ing over sub-graphs is more memory efficient, which is significant especially under the multi-task scenario. In this work, we design five simple pretext tasks spanning three high-level philosophies, including generative reconstruction, whitening decorrelation, and mutual information maximization. However we note that PARETOGNN is not limited to the current learning objectives and the incorpo- ration of other philosophies is a straightforward extension. Three high-level philosophies and their corresponding five pretext tasks are illustrated as follows:
Generative reconstruction. Recent studies (Zhang al., 2021d; Hou et al., 2022) have demon- strated that node features contain rich information, which highly correlates to the graph topology. To encode node features into the representations derived by PARETOGNN, we mask the features of a random batch of nodes, forward the masked graph through the GNN encoder, and reconstruct the masked node features given the node representations of their local sub-graphs (Hou et al., 2022). Furthermore, nodes to retain the pair-wise topological knowledge (Zhang & Chen, 2018). 1).. Feature and topology reconstruction denoted FeatRec and TopoRec respectively.
conduct the similar reconstruction process for links between the connected
3

---

Published as a conference paper at ICLR 2023
Whitening decorrelation. SSL based on whitening decorrelation has gained tremendous attention, owing its capability of learning representative embeddings without prohibitively expensive negative pairs offline encoders (Ermolov et al., 2021; Zbontar al., 2021). We adapt the same philosophy to graph SSL. by independently augmenting the same sub-graph into two views, and then minimize the distance between the same nodes in the two views while enforcing the Reature-wiss covariance of all nodes equal to the identity matrix. We denote this pretext as RepDecor.
Mutual Information Maximization. Maximizing the mutual information between two corrupted views of the same target has been proved to learn the intrinsic patterns, as demonstrated by deep infomax-based methods (Bachman et al., 2019; Velickovic et al., 2019) and contrastive learning methods (Hassani Khasahmadi, 2020; Zhu et al., 2020). We maximize the local-global mutual information by minimizing the distance between the graph-level representation of the intact sub-graph and its node representations, while maximizing the distance between the former and the corrupted node representations. Besides, we also maximize the local sub-graph mutual information by maximizing similarity of representations of two views of the sub-graph entailed by the same anchor nodes, while minimizing the similarities of the representations of the sub- graphs entailed by different anchor nodes. The pretext tasks based on node-graph mutual information and node-subgraph mutual information are denoted as MI-NG and MI -SGG, respectively.
Technical details and objective formulation of these five tasks are provided in Appendix B. As described above, pretext tasks under different philosophies capture distinct dimensions of the same graph. Empirically, observe that simply combining all pretext SSL tasks with weighted summation can sometimes already lead to better task generalization over various downstream tasks and datasets. Though promising, according to our empirical studies, such multi-task supervuue GNN falls short on some downstream tasks, if compared with the hest-performing experts on these tasks. This phenomenon indicates that with the weighted summation there exist potential conflicts between different SSL tasks, which is also empirically shown by previous works from other domains such as Computer Vision (Sener& & Koltun, 2018; Chen et al., 2018).
2.2 MULTI-TASK GRAPH SSL PROMOTING PARETO OPTIMALITY
To mitigate the aforementioned problem and simultaneously optimize multiple SSL tasks, we can derive the following empirical loss minimization formulation as:
K
min O 0g
Σ az Lx 0x).
where ag is the task weight for k-tth SSL task computed according to pre-defined heuristics. For instance, AUTOSSL (Jin et al., 2022) derives task weights that promote pheudo-homophe Though such a formulation intuitively reasonable for some graphs and tasks, heterophilous graphs, which are not negligible in the real world, directly contradict the homophily assumption. Moreover, not all downstream tasks benefit from such homophily assumption, which we later validate in the experiments. Hence, it is non-trivial to come up with a unified heuristic that suits all graphs and downstream tasks. In addition, weighted summation of multiple SSL objectives might cause undesirable behaviors, such as performance instabilities entailed by conflicting objectives or different gradient scales (Chen et al., 2018; Kendall et al., 2018).
Therefore, we take an alternative approach and formulate this problem multi-objective optimization with a vector-valued loss L, as the following:
L 0g 0,, 0k) = min (4, 0, 0 0......0x
min
(2)
0g.
0 0......x
The focus of multi-objective optimization is approaching Pareto optimality (Désidéri, 2012), which in the multi-task SSL setting can be defined as follows:
Definition (Pareto Optimality). A set of solution (0), 0i...., 0jk) is Pareto optimal if and
only if there does not exists set of solution that dominates (0;, 0,, .... 0g). (0), 0 .... 0k) dominates (0,. ...,, 0g) if for every SSL task k. Lu(9; Tx. 0 0x) 2 (9 Tu. 0 0 and C( 0, 0, 0x) + L(G, 03 i..... 05...,0k) 0x)
4

---

Published as a conference paper at ICLR 2023
In other words, if self-suuer GNN is Pareto optimal, it is impossible to further optimize any SSL task without sacrificing the performance of at least one other SSL task. Finding the Pareto optimal model is not sensible if there exist set of parameters that can easily fit all SSL tasks (i... no matter how different SSL. tasks are reconciled, such a model approaches Pareto optimality where every SSL. task is perfectly fitted). However, this is rarely the case, hecause solving all difficult pretext tasks is non-trivial for only one set of parameters. By promoting the Pareto optimlaity, PARETOGNN enforced learn intrinsic patterns applicable to a number of pretext tasks, which further enhances the task generalization across various downstream tasks.
2.3 PARETO OPTIMALITY BY MULTIPLE GRADIENT DESCENT ALGORITHM
To obtain the Pareto optimal parameters, we explore the Multiple Gradient Descent Algorithm (MGDA) (Désidéri, 2012) and adapt it to the multi-task SSL setting. Specifically, MGDA leverages the saddle-point test and theoretically proves that a solution (i.e., the combined gradient descent direction or task weight assignments in our case) that satisfies the saddle-point test gives a descent direction that improves all tasks and eventually approaches the Pareto optimality. We further elaborate descriptions of the saddle-poin test for the share parameters 6, and task specifie parameters 02 in Appendix G. In our multi-task SSL scenario, the optimization problem can be formulated as:
K
K
min 01
Σ as Vo, Lo Tk. Bg. 0k)
S.L.
a =1 and Vk a 1220 0,
(3)
where Ve, Th. gg 0&) E RIX refers to the gradients of parameters for the GNN encoder w.r.t. the k-th SSL task. PARETOGNN can be trained using Equation (1) with the task weights derived by the above optimization. As shown in Figure 1, optimizing the above objective is essentially finding descent direction with the minimum norm within the convex hull defined by the gradient direction of each SSL task. Hence, the solution Equation (3) is frowart when K only two gradient descent directions involved). If the norm of one gradient is smaller than their inner product, the solution is simply the gradient with the smaller norm (i.e., (a: O, 0g 1) or vice versa). Otherwise, a can be calculated by deriving the descent direction perpendicular to the convex line with only one step, formulated as:
(i.e.,
0n = Ve, C2(: T2, 0g. 02) C2 T2, 02. Vo, Vo, (9: 0g. C2 T2, 02) Li TI, 0.g. 01) F
When K > 2, we minimize the quadratic form a ((Vo. C), where vo, C E k refers to the vertically concatenated gradients w.r.t. 0, for all SSL tasks, and a E RIIK is the vector for task weight assignments such that |||| 1. Inspired by Frank-Wolfe algorithm (Jaggi, 2013), we iteratively solve such a quadratic problem as special case of Equation (4). Specifically, we first initialize every element in a as 1/K, and we increment the weight of the task (denoted as I) whose descent direction correlates least with the current combined descent direction (i.e., EK ag (e, Tw, 0g, 0x)). The step size 17 of this increment can be calculated by utilizing the idea of Equation (4), where we replace Vo,Co T2, 0g. 02) with Σx= ag Ve, CG: Tk. oy 0s) and replace Lo Tı, Og 01) with Vo, Te, O go 0.). One iteration of solving this quadratic problem is formulated as:
Vo, (Vo, Vo, Vo, 0.)
a= a== - x0 11+ et, s.t. 1 Vo, Vo, (G: 0y. 0:)
(5)
where / = arg min, Ei=1 04 Vo, C. O,, 0,) Vo, (G: 0,, 0,) and Vo, = k=1
>K Ox Ve, (G: Tx. 0g. 2s). e, in the above solution refers an one-hot vector with t-th element equal to 1. The optimization described in Equation (5) iterates until 17 is smaller than a small constant & or the number of iterations reaches the pre-defined number 7. Furthermore, the above task reconciliation of PARETOGNN satisfies the following theorem.
Theorem 1. Assuming that ax(V.. (V o, C)TxT is 8-smooth. a converges the optimal point at rate of O(17)), and a is at most 43/(7 + 1) away from the optimal solution.
The proof of Theorem is provided in Appendix A. According to this theorem and our empirical observation, the optimization process in Equation (5) would terminate and deliver well vell-approximated results with 7 set an affordable value (e.g., ? 100).
5

---

Published as a conference paper at ICLR 2023
3 EXPERIMENTS
3.1 EXPERIMENTAL. SETTING
Datasets. We conduct comprehensive experiments on 11 real-world benchmark datasets extensively explored by the graph community. They include 8 homophilous graphs, which are Wiki-Cs, Pubmed, Amazon-Photer
Amazon Ciaazon-Computers ogbn-arxiv, and ogbn products (McAuley et al., 2015; Yang et al., 2016; Hu al., 2020), as well as 3 heterophilous graphs, which are Chameleon Squirrel. 1, and Actor (Tang et al., 2009; Rozemberczki et al., 2021). Besides the graph homophily, this list of datasets covers graphs with other distinctive characteristics (i.e., from graphs with thousands of nodes to millions, and features with hundred dimensions to almost ten thousands), to fully evaluate the task generalization under different scenarios. The detailed description of these datasets can be found in Appendix C.
Coauthor-CS. Coauthor-Physics
Downstream Tasks and Evaluation Metrics. We evaluate all models by four most commonly- used downstream tasks, including node classification, node clustering. link prediction, and partition prediction, whose performance is quantified by accuracy, normalized mutual information (NMI), area under the characteristic curve (AUC), and accuracy respectively, following the same evaluation protocols from previous works (Tian et al., 2014; Kipf & Welling, 2016a; Zhang & Chen, 2018).
Evaluation Protocol. For all downstream tasks, we follow the standard lincar-evaluation protocol on graphs (Velickovic et al., 2019; Jin et al., 2022; Thakoor et al., 2022), where the parameters of the GNN encoder are frozen during the inference time and only logistic regression models (for node classification, link prediction and partition prediction) or K-Means models (for node clustering) are trained to conduct different downstream tasks. For datasets whose public splits are available (i.e., ogbn-arxiv and oglon-prodcct node classification, node clustering and partition prediction. Whereas for other datasets, we explore a random 10%/%0%%0%% split for the aaiin/vlldationntes. split, following the same setting as explored by other literature. To evaluate the performance on link prediction, for large graphs where permuting all possible edges is prohibitively expensive, we randomly sample 210,000, 30,000, and 60,000 edges for training, evaluation, and testing. And for medium-scale graphs, we explore the random split of 70%/10%/20% following the same standard as explored by (Zhang & Chen, 2018: Zhao et al., 2022b). To prevent label leakage for link prediction, we evaluate link prediction by another identical model with testing and validation edges removed. Label for the partition prediction is induced by metis partition (Karypis& & Kumar, 1998), and we explore 10 partitions for each dataset. All reported performance averaged over 10 independent runs with different random seeds.
we utilize their given public splits for the evaluations on
Baselines. We compare the performance of PARETOGNN with 7 state-of the-rrrt self-supervised GNNs, including DGI (Velickovic al., 2019), GRACE (Zhu al., 2020), MVGRL (Hassani & Khasahmadi, 2020), AUTOSSL (Jin et al., 2022), BGRL (Thakoor et al., 2022), CCA-SSG (Zhang et al., 2021b) and GRAPHMAE (Hou et al., 2022). These baselines are experts at least one of the philosophies of our pretext tasks, and comparing PARETOGNN with them demonstrates the improvement brought by the multi-task self-supervised learning as well as promoting Pareto optimlaity.
To ensure a fair comparison, for all models, we explore the GNN encoder with the same architecture (i.e., GCN encoder with the same layers), fix the hidden dimension of the GNN encoders, and utilize the recommended settings provided by the authors. Detailed configurations of other spprr-pprameters for PARETOGNN are illustrated in Appendix D.
Hyper-parameters
3.2 PERFORMANCE GAIN FROM THE MULTI-TASK SELF-SUPERVISED LEARNING
We conduct experiments on our pretext tasks by individually evaluating their performance as well as task generalization, as shown in Table 1. We first observe that there does not exist a single-task model that can simultaneously achieve competitive performance on every downstream task for all datasets, demonstrating that knowledge learned through single philosophy does not suffice the strong and consistent task generalization. Models trained by a single pretext tasks alone are narrow experts (i.e., delivering satisfactory results only few tasks or datasets) and their expertise does not translate to the strong and consistent task generalization across various downstream tasks and datasets. For instance, TopoRec achieves promising performance on link prediction (i.e., average rank of 3.7), but falls short on all other tasks (i.c., ranked 5.9, 5.3, and 5.9). Similarly, MI-NSG performs reasonably well on the partition prediction (i.e., average rank of 3.0), but underperforms the link

---

Published as a conference paper at ICLR 2023
Table 1:
Performance and task generalization of our proposed SSL pretext tasks. w/o Pareto stands for combining all the objectives via vanilla weighted summation. RANK refers to the average rank among all variants given an evaluation metric. Bold indicates the best performance and underline indicates the runner-up. with standard deviations as subscripts.
Method WIKLeS PURMID
Plimm
AM.COMP.
Co.CS
Co.PHY.
SQUIRRU.
ACTOR
AVERAGE PERFORMANCE
Teat Rec
74.06
69:48
84.76
77.76
K6.61
75.20
64.66
$2.43
31.63
4.6
TopoRec
70:44
66.32
85.18
79.41
85.23
77.45
61.20
52.59
38.56
5.0
AepUecor
67.42
83.74
78.49
84.49
78.31
52.19
MI-NG
71.89
67.35
85.33
79.95
$3.01
75,00
63.72
19.56
30.60
5.7
MI-N3G
75.59
69.25
82.99
80.85
$6.02
80.30
61.69
$3.59
38.22
3.6
PARETOGNN
76.03
72.48
86.58
82.57
$7.80
83.35
65.21
55.31
40.76
w/o Pareto
74.64
69.82
85.82
$2.09
$6.54
$2.32
64.37
$1.90
10.12
NODE CLASSIPICATION (Accuracy)
ZeatRec
81.00
$2.78_00
93.24__0
89.63
12.12
95.4910.05
63.97_00s
13
24.41.0.:
3.7
TopoRec
80.25
$1.99.0.31
92.88
87 68 ,0.31
90.97 10.05
94.31
63:01.014
40.24..04
25.29.000
RepDecor
92.21_000
29.05
92.53
94.31
57.46_0
44.37g1
25.11
MT-NG
80.7210.77
81.62_0oo
93 02, o.00
89. c.
19.04
93.07
62.27.005
41.566.03
25,41
5.7
MI MI-NBG
81.21
86.93.0
93.18_025
90.34.6.ax
92.01
20.35
13.13
63.14_1
46.21
23.5420ar
3.6
PARETOGNN
82.87 10:3
87.03 a5
93.85 _oss
90.75 pc.17
92.21 20.34
95.45 1o
63.13_00t
16.60.1
26.62.0007
w/o Pareto
13.09
36.81g0.0
69.69
90.81
92.78
14.52
63.37,017
45.54..0s
25.79.n.4:
NODE CLUSTERING (NMI)
ZeatRec
43.04
63.25 30.24:0.0
43.83
21.04
37.83
14.77.0:13
3.8 3.84
a.62gnos
4.0
IopoRec
36.06
19.22:002
66.27-1.0
48. 15.56
69.83
8.07=00:
3.22
2.19
RepDecor
34,96 10.50
26.51 20.5
61,28 3.
19.78
66.53
47.65
9.09
3.17
0.22.nm:
5.1
NI-NG
39.78 39.78
24.70:04:
65. 65.32:u1.87
48. 28.78
66.
66.1620.42
49.98.0.34
14.18:0067
4.082004
0.91anot
4.1
MI-NGG
10:34
m.m
14.9
10.8
15
2.94
0.13 1oos
PARETOGNN
47.5229.20
34.7420.08
68.25 21.25
$2.53
74.94
60.44340.33
14, 14,49:2077
2.
1.53
2.1
w/o Pareto
12.0.5
26
22
51.5
24.01
60.71go.21
11.91200
2.82
0.90gn.1
LINK PREDICTION (AUCC
ReatRec
09.794
9% 93.96.000
95 47.4
96.51 90.51
95.97 95.97.0.05
94.1320
89.47200:
67.22:2004
4.3
Topokee
92.69g0.06
94.17.094
95.13g1
1:55
95 89:88966.
96.43 23..
97. 97.98-20.)
89.35 as
23.9120a
84.03.0
3.7
RegDecor
93 93.6429.00
87.552000
94 86
86.45
94.0020.10
96. 96.48400s
87.50=20
86.442021
71.13
6.0
MI-NG
92.48
91.48.0.19
03.33_00
19.00
97.83
90. 18
94.26-200
87.262001
69.16200s
MT-NSG
95. 24.04
92. 02.22-20.2
95. 22
94. 11 socurr
92. 320.01
93. 93.134005
95.17=002
92.042002
81.26 31.26-0011
4.4
PARETOGNN
20.48
94.58.00z2
96.08
97.1620.04
98.18
98.33400s
95.78_00:
96.462005
84 24.29.000
1.1
wfo Pareto
94.13
93.17.0
14.52_00 15
95.7 go.ra
12.000
36.51
05.54_0
13
05.17.007
PARTITION PREDICTION (Accuracy)
Rec
20
70
N7. g0 1a
83.21
10:004
21
85,77
34,27 24.27.0083
TopoRec
72.7849.35
69.91 20.11
86.45-0.22 20
16
83.71 20.00
69. 60.38
84.39 24
74.20=a02
14.74
RepDecor
71.472006
20.23
86.59
88.00 (8.6726,.1
84.91 20.10
74.80a0.5
S1.86.2032
74.77
48.67-001
4.7
MT-NG
34.57103
71.60.0.30
87
NT. 14.14
79.01
66. 66.7610.n
84.17.074
65.34_001
36.92.0.0
MI-N8G
37.49
73.50.0.s
89 39.34.0.00
45.00
26.132
85.11
74.37
47.96.a0s
PARETOGNN
37.23
88.13_0.0
89 29.84.0..0
X5.89
79.1910.0
87.43_1
15.39.005
20.61.005
1.3
w/o Pareto
15.22
73.12.0.
0.00
89.97 pc.41
14.21
77.54.0a3
16.66.003
76.09 Lo
48.61.014
prediction task (i.e., average rank of 4.4). However, comparing them with the model trained by combining all pretext tasks through the weighted summation (i.e., w/o Pareto), we observe that the latter achieves both stronger task generalization and better single-task performance. The model w/o Pa Pareto achieves average rank of 2.4 on the average performance, which is 1.2 ranks higher than the best single-task model. This phenomenon indicates that multi-task self-supervised GNNs indeed enable stronger task generalization. Multiple objectives regularize the learning model against extracting redundant information so that the model learns multiple complementary views of the given graphs. Besides, multi-task training also improves the performance of the single downstream task by 1.5, 0.7, 0.3, and 0.6 ranks, respectively.
In some cases (e.g., node clustering PUBMED and CHAMELEON, or link prediction WIKI. CS and CO.CS), we observe large performance margins between the best-performing single-task models and the vanilla multi-task model w/o Pareto, indicating that there exist potential conflicts between different SSL tasks. PARETOGNN further mitigates these performance margins by promoting Pareto optimality, which enforces the learning model to capture intrinsic patterns applicable to a number of pretext tasks while minimizing potential conflicts. As shown in Table 1, PARETOGNN is the top-ranked at both average metric and other individual downstream tasks, demonstrating the strong task generalization as well as the promising single-task performance. Specifically, PA PARETOGNN achieves an outstanding average rank of 1.0 on the average performance of the four downstream tasks. As for the performance on individual tasks, PARETOGNN achieves average rank of 1.7, 1.6. 1.0, and 1.2 on the four individual downstream tasks, outperforming the corresponding best baselines by 0.2, 1.2, 1.3, and 1.1 respectively. This phenomenon demonstrates that promoting Pareto optimality not only helps improve the task generalization across various tasks and datasets but also enhances the single-task performance for the multi-task seff-supervised learning.
7

---

Published as a conference paper at ICLR 2023
Table 2: Performance and task generalization of PARETOGNN as well as the state-of-the-an unsuper- vised baselines. OOM stands for out-of-memory on RTX3090 GPU with 24 GB memory.
WIKECS
PUBMIO
AM. PHOTO
AM. COMP:
Co.Cs
Co.PHY.
CHAM.
SQUIRRI
ActmiR
AVERAGE
PERFORMANCE
DGI
72.50
59.84
83.67
77.91
85.67
79.86
61.34
50.23
33.77
GRACE
71.01
00M
51.02
32.59
MVGRL
68.59
63.23
$2.49
67.80
82.69
75.72
59.77
45.01
31.22
7.1
AUTOSSI.
71.72
65.90
83.96
77.02
85.88
80.03
60.87
49.76
31.33
4.4
BGRL
74.68
67.15
80.14
79.06
87.26
81.42
60.20
29.14
32.33
CCA-SSG
73.44
64.12
83.62
78.71
83.65
79.77
62.80
51.63
35.90
GRAPIMAR
67.83
62.15
76.94
72.18
86.80
77
58.27
45.22
31.49
6.8
PARETOUNN
76.03
72,48
86.58
82,57
87.80
83.35
65.21
55,31
40.76
NODE CLASSIFICTTION (Accuracy)
DGI
83.52 g5.5
91.61 10.37
83.59
92.15 15..5s
20.5
61.00
g0.5
g5.19
5.9
GRACE
80, 24.000
26.05
92.78-20.49
89, 89.53
91. 12.12.
(IO
58. 194.55
41. 36..6
24 24.63
5.0
MVGRL
19:11
83.62 1o.32
92.18
12.78
90.33
10.05
19.37
19.0
18.01
AUTOSSL
29.55
H6.2660.20
92.71
88, 7640.22
92. 97.17T
95. 134.,4
58 58.9420.04
40 20.635
24.542
4.7
BGRL
12.58
86.03 17:17
93.17
10.15
11.77.0.47
15.73
56.05
24.03 1a.61
4.1
CCA-SSG
a2.48
86, 36.36
93. 93.29
29.58
94.24
23.63
$7.39
42. 22....
26, 26.35
2.8
GRAPHMAE
17.12
83.91
90.71e0.40
79.44...s
93.13
25.79
55.50ga.52
35.87
28.97
5.3
PARETOGNN
82.87 20.33
87.03 20.25
93.85 20.25
20.78
V2.3 20.34
95. 25.4520.30
63.13
46.60
26.62gnus7
NODE CLUSTERING (NMI)
DGI
9 9.68 g4.35
60.31
47.76
72.88
58. 38.7620.43
6.99
2.16,0.14
1.49,.00
5.1
GRACE
10
25.64
55,20 To
41.77
76.61
00M
11.73
g.53
1.09 gm:m
MVGRI.
a6.20
24.87 1o:10
56.3618.3
31.27
58.27 73.3416.01
18.57
4.40 1o00
2.63.00.
4.3
AUTOSSL
36.99
28.99 28.99.a.a
64 GA.0640.4
41.8522.00
74.0440.59
55 55.233o.1
9.67
2.11
1.35
5.0
BGRL
44.95.aae
16.38
50.30
44.04
74.06
11.29
2.28
1.32
CCA-SSG
24.1720.00
25.15
49. 49.78.9..11
67. 43.14.0.40
54.33
12.1740.0
3.02
101
4.3
GRAPHMAE
15.73
19.00
31.42
23.31 10.36
16.18
8.66
PARETOGNN
p7.52
34.74
68.25
$2.53
74.94.0.00
60.43
14.49
281 po.20
1,53gb00
1.9
LINK PREDICTION (AUC)
DGI
g4.36
78.59
94.24.0.10
90.37
93.46
88.8220.05
91.6420.12
92.45
72.01:n.4
5.0
GRACE
go.00
87.44g..00
91.82
68.58 10.06
97.00
00M
93.81
13.57
82:31:na7
4.6
MVGRL
04.34
20.31
93.86
15.15
92.444..00
87.54
94.50,a.44
28.8
7799
5.0
AUTOSSL
93.8
86.84
95.57
10.99
95.71
95.93
90.05
93.84
70.5 70.51g0m
4.3
BGRL
11.35
10.00
10.05
97.37
13.38
92.21
83.60,a.0
26.91
CCA-SSG
90.92
73.53
89.47 10721.
86, 16.72.o.13
91.77
93.64
95.4 95.43
s7.30
78. 14.14.mm
5.7
GRAPHMAE
19.47
86.24
20.30
13.33100.r
11.05
96.1816.17
96.5 10.00
19.10
16.18
80.65
PARETOGNN
96.48
94.58
96.08
97.16
98.18
98.33
98.78
96.46
84.29 =0.0
1.0
PARTITION PREDECTION (Accuracy)
g
67.58ggoo1
88.50 1.:03.0000 30
84.19 89.91
27.34.o.01
85.75
65. gm.77
16.40.mm
GRACE
71.19
61.01 13:57
83.66
10.36
83.89 10.42
00X
84.76
66.61
22 22.32_
3.4
MVGRL
64.73
14.11
87.25 10
81.99
74 74.6644.11
66. 66.03
76.1241.06
47 47.03gass
16.312001
7.2
AUTOSSL
76.47
61.52
83.51
83.46
81.59
73.85
84.83
62.45
18.90_net
BGRL
46.87
61.8423.00
83.51 23.50
88 88.45
85.8441.29
75.5334..1
81.21
69. 69.04
27.072004
3.9
CCA-SSG
T6.
69.46...m
87.67
88.77.0..1
21.44g0.0
75.4910.10
86.22
73.97
18.11gnm
3.1
GRAPIMAR
69.01
59,
10.40
82.31 10.13
11.11
81.39
19....m
70.671...e 1o.36
70.67
79.50
Lo.07
15.09) am
7.2
PARETOGNN
77.23
73.57 20.00
13.13
89.84.0.00
85.89
19.19
87.43
75.39
50.61.00s
1.2
3.3 PERFORMANCE COMPARED WITH OTHER UNSUPERVISED BASELINES
We compare PARETOGNN with 7 state-of-the-art SSL frameworks for graphs, as shown in Table 2. Similar to our previous observations, there does not exist any SSL baseline that can simultaneously achieve competitive performance on every downstream task for all datasets. Specifically, from the perspective of individual tasks, CCA-SSG performs well on the node classification but underperforms on the link prediction and the partition prediction. Besides, DGI works well on the partition prediction but performs not as good on other tasks. Nevertheless, from the perspective of datasets, we can observe that AUTOSSL has good performance on homohpilous datasets but this phenomenon does not hold for heterophilous ones, demonstrating that the assumption of reconciling tasks by promoting graph homophily is not applicable to all graphs. PARETOGNN achieves a competitive average rank of 1.0 on the average performance, significantly outperforming the runner-ups by 2.7 ranks. Moreover, PARETOGNN achieves an average rank of 1.8, 1.9, 1.0, and 1.2 on the four individual tasks, outrunning the rest-performing baseline by 0.9, 2.3, 3.3, and 1.6 respectively, which further proves the strong task generalization and single-task performance of PARETOGNN.
3.4 PERFORMANCE WHEN SCALING TO LARGER DIMENSIONS
To evaluate the scalability of PARETOGNN, we conduct experiments from two perspectives: the graph and model dimensions. We expect our proposal to retain its strong task generalization when applied to large graphs. And should expect even stronger performance when the model dimension scales up, compared with other single-task frameworks with larger dimensions as well, since multi-task SSL settings enable the model capable of learning more. The results are shown below.
8

---

Published as a conference paper at ICLR 2023
Table 3: Task generalization large graphs. ( Graphs are sam- pled by GRAPHS (Zeng et al., 2019) matching the memory of oth- ers due to OOM. Individual tasks are reported in Appendix F.
BORL ParetoGNN
BGRL ParetoGGhNN
Average Perf.
Method
ARXIV
PRODUCTS
RANK
128
Hidden Dimension
256
512
Hidden Dimension (b) ogbn-arxiv
AVERAGE PERFORMANCE
(a) Am. Computer
DGI
09.75
75.48'
3.5
GRACE
68.82'
75.58'
4,0
Figure 2: Task generalization (i.e., average performance) over Ama Amazon-Coon -ommutttt and ogbn-arxiv for PARETOGNN and BGRL w.r.t. hidden dimensions of the graph encoder.
AUTOSSL
68,02
DOM
7.0
BGRI
70.04
75.19"
3.5
CCA-SSG
69.62
72.92"
5.5
GRAPHMAE
71.15
74, 89
3.5
PARETOGNN
71.39
From Figure 2, we observe that the task generalization of PARETOGNN is proportional to the model dimension, indicating that PARETOGNN is capable of learning more, compared with single-task models like BGRL, whose performance gets saturated with less parameterized models (e.g.. 128 for AM. COMP. and 256 for ARXIV). Moreover, from Table we notice that the graph dimension is not a limiting factor for the strong task generalization of our proposal. Specifically, PARETOGNN outperforms the runner-ups by 2.5 on the rank of the average performance.
RELATED WORKS
Graph Neural Networks. Graph neural networks (GNNs) are powerful learning frameworks to extract representative information from graphs (Kipf & Welling, 201 Veličković et al., 2017; Hamilton et al., 2017: Xu et al., 2018b; Klicpera et al., 2019; Xu et al., 2018a; Fan et al., 2022;
Zhang et al., 2019). They aim at mapping the input nodes into low-dimensional vectors, which can be further utilized to conduct either graph-level or node-level tasks. Most GNNs explore layer-wise message passing scheme (Gilmer et al., 2017; Ju et al., 2022a), where node iteratively extracts information from its first-order neighbors. They are applied in many real-world applications, such as predictive user behavior modeling (Zhang al., 2021c; Wen et al., 2022), molecular property prediction (Zhang et al., 2021e; Guo et al., 2021), and question answering (Ju et al., 2022b).
Sepe-supe Learning for GNNs. For node-level tasks, current state-of-the-ar graph SSL frameworks are mostly introduced according to single pretext task with a single philosophy (You et al., 2020b), such mutual information maximization (Velickovic et al., 2019; Zhu et al., 2020; Hassani & Khasahmadi, 2020; Thakoor et al., 2022), whitening decorrelation (Zhang et al., 2021b), and generative reconstruction (Kipf & Welling, 2016b; Hou al., 2022). Whereas for graph-level tasks, previous works explore mutual information maximization to encourage different augmented views of the same graphs sharing similar representations (You al., 2020a; Xu et al., 2021; You et al., 2021; Li et al., 2022; Zhao et al., 2022a).
Multi-Task Self-supervised Learning. Multi-task SSL is broadly explored in computer vision (Lu et al., 2020; Doersch & Zisserman, 2017; Ren & Lee, 2018; Yu et al., 2020; Ni et al., 2021) and natural language processing (Wang et al., 2018; Radford et al., 2019; Sanh et al., 2021; Ravanelli et al., 2020) fields. For the graph community, AutoSSI. (Jin et al., 2022) explores a multi-task setting where tasks are reconciled in a way that promotes graph homophily (Zhao et al., 2021b). Besides, Hu et al. (2019) focused on the graph-level tasks and pre-trains GNNs in separate stages. In these frameworks, tasks are reconciled according to weighted summation or pre-defined heuristics.
CONCLUSION
We study the problem of task generalization for SSL-based GNNs in a more rigorous setting and demonstrate that their promising performance on one task or two usually does not translate into good task generalization across various downstream tasks and datasets. In light of this, we propose PARETOGNN enhance the task generalization by multi-task self-supervised learning. Specifically, PARETOGNN is self-supervised by manifold pretext tasks observing multiple philosophies, which are reconciled by cuultiple-gradien descent algorithm promoting Pareto optimality. Through our extensive experiments, we show that multi-task SSL indeed enhances the task generalization. Aided by our proposed task reconciliation, PARETOGNN further enlarges the margin by actively learning from multiple tasks while minimizing potential conflicts. Compared with 7 state-of-the-art SSL-based GNNs, PARETOGNN is top-ranked on the average performance. Besides stronger task generalization. PARETOGNN achieves better single-tas, performance, demonstrating that disjoint yct complementary knowledge from different philosophies is learned through the multi-task SSL.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work partially supported by the NSF under grants IIS-2209814 IIS-2203262, IIS-2214376, IIS-2217239, OAC-2218762. CNS-2203261, CNS-2122631, CMMI-2146007, and the NIJ 2018-75- CX-0032. Any opinions, findings, and conclusions or recommendations expressed in this material those of the authors and do not necessarily reflect the views of any funding agencies.
ETHICS STATEMENT
We observe no ethical concern entailed by our proposal, but note that both ethical unethical applications based on graphs may benefit from the stronger task generalization of our work. Care should be taken ensure socially positive and beneficial results of machine learning algorithms.
REPRODUCIBILITY STATEMENT
Our code is publicly available at https:://// :/ts:://iiii httptttttbbut//gg com jumxglht retoGNN. The hyper- parameters and other variables required to reproduce our experiments are described in Appendix D.
REFERENCES
Philip Bachman, R Devon Hjelm, and William Buchwalter. Learning representations by maximizing mutual information across views. In Procs. of NeurlPS, 2019.
Jonathan Baxter. A bayesian/information theoretic model of learning to learn via multiple task sampling. Machine learning, 1997.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Prucs. ICML, 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In Procs. of ICML, 2020.
Zhao Chen, Vijay Badrinarayanan, Chen-Yu Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In Procs. of ICML, 2018.
Zhengyu Chen, Jixie Ge, Heshen Zhan, Siteng Huang, and Donglin Wang. Pareto self-supervised training for few-shot learning. In Procs. of CVPR, 2021.
Jean-Antoine Désidéri. Muultipe-grrdiee descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Muthematique, 2012.
Carl Doersch and Andrew Zisserman. Multi-task self-supervised visual learning. In Procs. of CVPR, 2017.
Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe. Whitening for self- supervised representation learning. In Procs. of ICML., 2021.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In Procs. of WWW, 2019.
Yujie Fan, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye. Heterogeneous temporal graph neural network. Procs. of SDM, 2022.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Procs. of ICML, 2017.
Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh V Chawla. Few-shot graph learning for molccular property prediction. In Procs. of WWW, 2021.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Procs. of NeurlPS, 2017.
10

---

Published as a conference paper at ICLR 2023
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In Procs. of ICML, 2020.
Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang, Chunjie Wang, and Jie Tang.
Graphmae: Self-supervised masked graph autoencoders. In Procs. of SIGKDD, 2022.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovee. Strategies for pre-training graph neural networks. In Procs. of ICLR, 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. In Procs. of Neur/PS, 2020.
Martin Jaggi. Revisiting frank-wolfe: Projection-free sparse convex optimization. In Procs. of ICML, 2013.
Wei Jin, Xiaorui Liu, Xiangyu Zhao, Yao Ma, Neil Shah, and Jiliang Tang. Automated self-supervised learning for graphs. In Procs. of ICLR, 2022.
Mingxuan Ju, Shifu Hou, Yujie Fan, Jianan Zhao, Yanfang Ye, and Liang Zhao. graph neural network. In Procs. of AAAI, 2022a.
Adaptive kernel
Mingxuan Ju, Wenhao Yu, Tong Zhao, Chuxu Zhang, and Yanfang Ye. Grape: Knowledge graph enhanced passage reader for open-domain question answering. In Findings of EMNLP. 2022b.
George Karypis and Vipin Kumar. fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 1998.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. Procs. of CVPR, 2018.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Procs. of ICLR, 2016a.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 2016b.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Procs. of SIGKDD, 2019.
Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In Procs. of ICML, 2022.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-task learning. Procs. of NeurlPS, 2019.
Jiasen Lu, Vedanuj Goswami, Marcus Rohrbach, Devi Parikh, and Stefan Lee. 12-in-1: Multi-task vision and language representation learning. In Procs. of CVPR, 2020.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In Procs. of ICLR, 2021.
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In Procs. of ICML, 2020.
Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and comple- mentary products. In Procs. of SIGKDD, 2015.
Minheng Ni, Haoyang Huang, Lin Su, Edward Cui, Taroon Bharti, Lijuan Wang, Dongdong Zhang, and Nan Duan. M3p: Learning universal representations via multitask multilingual multimodal pre-training. In Procs. of CVPR, 2021.
Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, and Jure Leskovec. Pinnersage: Multi-modal user embedding framework for recommendations at pinterest. In Procs. of SIGKDD, 2020.
11

---

Published as a conference paper at ICLR 2023
Hongbin Pei, Bingzhe Wei, Kevin Chen- Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In Procs. of ICLR, 2019.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 2019.
Mirco Ravanelli, Jianyuan Zhong, Santiago Pascual, Pawel Swietojanski, Joao Monteiro, Jan Trmal, and Yoshua Bengio. Multi-task self-supervised learning for robust speech recognition. In Procs. of ICASSP. 2020.
Zhongzheng Ren and Yong Jae Lee. Cross-domain self-supervised multi-task feature learning using synthetic imagery. In Procs. of CVPR, 2018.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
Sebastian Ruder. An overview of multi-task learning in deep neural networks. arXiv preprint arXiv:1706.05098, 2017.
Victor Sanh, Albert Webson, Colin Raffel, Stephen Bach, Lintang Sutawika, Zaid Alyafeai, Antoine Chaffin, Arnaud Stiegler, Arun Raja, Manan Dey, et al. Multitask prompted training enables zero-shot task generalization. In Procs. of ICLR, 2021.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. Procs. of NeurlPS, 2018.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Procs. of SIGKDD, 2009.
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scall scage-scale representation learning on graphs via bootstrapping. In Procs. of ICLR, 2022.
Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie- Yan Liu. Learning deep representations for graph clustering. In Procs. of AAAI, 2014,
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Procs, of ICLR, 2017.
Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In Procs. of ICLR, 2019.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Procs. of ICLR, 2018.
Qianlong Wen, Zhongyu Ouyang, Jianfei Zhang, Yiyue Qian, Yanfang Ye, and Chuxu Zhang Disentangled dynamic heterogeneous graph learning for opioid overdose prediction. In Procs. of KDD, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? Procs. of ICLR, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Procs. of ICML, 2018b.
Minghao Xu, Hang Wang. Bingbing Ni, Hongyu Guo, and Jian Tang. Self-supervised graph-level representation learning with local and global structure. In Procs. of ICML, 2021.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Procs. of ICML, 2016.
12

---

Published as a conference paper at ICLR 2023
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Procs. of SIGKDD, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Procs. of NeurIPS, 2020a.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self superviiiv help graph convolutional networks? In Procs. of ICML, 2020b.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In Procs. of ICML., 2021.
Fisher Yu, Haofeng Chen, Xin Wang, Wenqi Xian, Yingying Chen, Fangchen Liu, Vashisht Madhavan, and Trevor Darrell. Bdd100k: A diverse driving dataset for heterogeneous multitask learning, In Procs. of CVPR, 2020.
Jure Zbontar, Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In Procs. of ICMI, 2021.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In Procs. of ICLR, 2019.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heterogeneous graph neural network. In Procs. of KDD, 2019.
Chuxu Zhang, Huaxiu Yao, Lu Yu, Chao Huang, Dongjin Song, Haifeng Chen, Meng Jiang, and Nitesh V Chawla. Inductive contextual relation learning for personalization. ACM Transactions on Information Systems, 2021a.
Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, and S Yu Philip. From canonical correlation analysis to self-supervised graph neural networks. In Procs. of NeurlPS, 2021b.
Jianfei Zhang, Ai-Te Kuo, Jianan Zhao, Qianlong Wen, Erin Winstanley, Chuxu Zhang, and Yanfang Ye. Rxnet: Rx-refill graph neural network for overprescribing detection. In Procs. of CIKM, 2021c
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Procs. of NeurIPS, 2018.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. In Procs. of ICLR, 2021d.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee. Motif-based graph self- supervised learning for molecular property prediction. Procs. of NeurlPS, 2021c.
Tong Zhao, Tianwen Jiang, Neil Shah, and Meng Jiang. A synergistic approach for graph anomaly detection with pattern mining and feature learning. IEEE Transactions on Neural Networks and Learning Systems, 2021a
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Procs. of AAAI, 2021b.
Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey, arXiv preprint arXiv:2202.0887// 2022a.
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfactual links for link prediction. In Procs. of ICML, 2022b.
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
13

---

Published as a conference paper at ICLR 2023
A PROOF TO THEOREM
Here we re-state Theorem before diving into its proof:
Theorem 1. Assuming that aVVo, 0, (V,,, C) is B-smooth. converges to the optimal point at a rate of ((177), and a is at most 43/(7 + 1) away from the optimal solution.
Proof. Let ((a) denotes a aVVo, [) (Ve, C)aT, If of)
is f-smooth, have:
||V((a) Vo(a')ll S B ||e 1|a-a'lll
(6)
from which we can also derive quadratic upper-bound:
<(a') < δ(a) Vé(a)) (a' a) _ ||a' -xl?
3
(7)
where a' refers to the weight combination after one iteration from a. Combining Equations (5) and (7), we have:
((a') x(a)= s Vo(a)) (a' aa) 3 1|aa -al1?
(8)
3 R²a
S Vé(a)) (e: -)) a
2
where R = SUPai
axll) refers to the diameter of the domain of or (Vaa,, (Vo,, (V)
and SuP(-) is the supremum operation. In our case, R v2 since ||<|| = The derivation above is valid because a' = (1 - 7)) a + ez, as shown in Equation (5).
(T: 0g 0,) we have: Since t = arg min, Σ a4 Ve,C,(9:T T., og 01) Ve, CG:
s(a') ((a) S Vo(a) (a a) 33
(9)
Sn (ó(a") ((a)) +B-r)²
where ax is the unknown optimal solution. By rearranging terms in the above inequality, we have: s(a') s(a") s (1 (1-r)) 1)) (ø(a) ()a))) + 3-2
(10)
The left hand side of the above equation is the distance between the updated solution and the optimal solution (we denote this distance as = o(a') $(a²)) And on the right hand side, inside the parenthesis we have the distance between the previous solution and the optimal solution (denoting
this distance as ((a)) $(a*)) )) as:
8' 5'5 - 8-
(11)
where in our case, 77 V., (Vo, C.TT.,00000 1[ (..T,....,
this proof, we assume 17 7 where Y
refers the index of the current iteration. Such assumption is relaxed version our formulation upon 1). hence any proof that holds for this assumption also holds for our case.
Next, we show 6y S 7+I in Theorem through proof-by-induction:
It's straight-forward and easy to validate that our derivation stands for the base case = 2, where
82 < 3. Here we show that it also holds for + 1:
8 S (1 17)
8, + 2 8-7
2
43
2
$ 5
)2 + 8
7+
7
7
7-1
43
48
7+1
7+1
(y 1)2
(12)
43
7
7+1 7+1*
48
++1
14

---

Published as a conference paper at ICLR 2023
B DESCRIPTION OF THE PRETEXT TASKS
In this section, we demonstrate the design of our proposed five pretext tasks, including two based on generative reconstruction (i.e., FeatRec and TopoRec), one based whitening decorrelation (i.e., RepDecor) and two based on mutual information maximization (i.e., MGG and MI MI-NSG).
We first explain the operation of graph convolution as proposed by Kipf & Welling (2016a). The key mechanism of graph convolution is layer-wirg wise message passing where a node iteratively extracts information from its first-order neighbors and information from milti-hop neighbors can be captured through stacked convolution layers. Specifically, at 1-th layer, this process is formulated as follows:
H = a H' W²),
(13)
where H = A [0,1]NxN is the adjacency matrix of the input graph, at)) refers to the non-linear activation function, W E IRd x refers to the learnable parameters of /-th layer, and d' and d2 are the hidden dimensions at these two consecutive layers respectively. The graph encoder [g(: (g) - Raxd of PARETOGNN is constructed by stacked graph convolution layers as:
fo 0g) H (A H w
(14)
where I. stands for the number of layers in the encoder of PARETOGNN and 0g (W")--
As briefly described in Section 2. we regard the full graph as the data source; and for each task, PARETOGNN is self-supervieed by sub-graphs sampled from G. followed by task-specific augmentations (i.e., T(()). The graph sampling strategy is fairly straightforward. For the pretext task t, we select the sub-gra sub-graph constituted by nodes within ke hops of N₂ randomly selected seed nodes, where k and N2 are two task lusk-specific hyper-parameters. The graph augmentation operations we explore include feature masking, edge dropping, and node dropping. For the simplicity of denotation, we unify the operation of graph sampling and graph augmentation together as Te()). Task-specific prper-parameters for graph augmentation and sub-graph sampling are covered in Appendix D.
B.1 GENERATIVE RECONSTRUCTION
Feature reconstruction, denoted as FeatRec, utilizes the high-level idea from Zhang et al. (2021d), proving that topological information can be referred purely from the node features. Hence to utilize such inductive bias, following the implementation of GraphMAE (Hou et al., 2022), we mask the node features and forward the masked graphs through (: 0y)) Then re-mask the previous masked nodes and feed the resulted graph to a convolution- convolution-based based decoder, formulated as:
X'= A'. (G'; :gy) O M- Deee
(15)
where @ refers to Hadamard product, A' is the adjacency matrix of the sampled sub-graph g' (g)), M E {0, 1) is the feature mask matrix whose rows equal to 1 if their corresponding nodes are targeted for reconstruction, and De Rdx is the parameter matrix for the feature decoder. The objective for FeatRec is formulated as:
X M X M|]
CreatRee
(16)
O
where M E 13 is the mask matrix defined similarly to M with different dimension, and X' E N'D is the feature matrix of the sampled sub-graph g' ~ (Gr)
Topological reconstruction, denoted as TopoRec, aims at capturing the wair-wise relationships between the connected nodes, Given sampled sub-graph g' TropcRee (9), we randomly select B
pairs of nodes V = {(i,j) = 1} and another B pairs of nodes V = ((1.j) A', = =0.. The
connection between two node and j is measured by a logit calculated as:
Proporec (i. o (U, 0 o (G'; 0,)(i)) ( w
(17)
where [|] refers to the indexing operation, and Topo dd is the parameter vector. The objective of TopoRec is maximizing the PrepoRec for nodes in V and minimizing for nodes in V-, formulated as a binary cross entropy loss as:
LiTOORRe
1
Σ (i.))VV
Log(P: DPPoPopcRoc +
log(1 Properoe (i,
(18)
2B
15

---

Published as a conference paper at ICLR 2023
B.2 WHITENING DECORRELATION
Representation decorrelation, denoted as RepDecor, encourages the similarities between the representations of the same nodes in two independently augmented sub-graphs. During this process, to the prevent the node representations from collapsing into a trivial solution, the covariance between representations matrices of two sub-graphs are enforced be an identity matrix, such that the knowledge learned by each dimension in the hidden space is orthogonal to each other (Ermolov et al., 2021; Zbontar et al., 2021; Zhang al., 2021b). Given two sub-graphs Gi, 92 TropoRce that are constituted by the same seed nodes but augmented differently, the objective of RepDecor is formulated as:
Cxephecor
-5 0b) a (.10 fg(C); -dxd
(19)
F
where the first term encourages the node similarity and the second term regularize the solution from collapsing, Idxd is the square identity matrix with dimension d d, and refers to pre-defined balancing term (i.e., we use an a of le-3 across all datasets).
B.3 MUTUAL INFORMATION MAXIMIZATION
Mutual information between nodes and the whole graph, denoted as MI-NG, enables the graph encoder to learn coarse graph-level knowledge. Specifically, given a sampled sub-graph g' ~ (M)- we first corrupt G' into G" by feature shuffling (Velickovic et al., 2019). Then we extract the hidden graph-level representation of g' by the graph mean pooling (Xu et al., 80), and enforce the representations of nodes in G' similar to the pooled representation while nodes in G" far away from the pooled representation. This pretext task allows the graph encoder to capture the perturbation brought by the topological change (i.e., feature shuffling). The objective of MI MI is formulated as binary cross entropy as:
N'
LXI NG
log (1 Pac nG (9 h2)), Σ log (Pez (G (.),,,,)))
2N
s.t. hg Pool (f 0g)), and PAI-NG (h, h₂) = (h|(hg) WMI-NG
(20)
where POOL(.) refers to the graph mean pooling function (Xu et al., 2018a), || is the horizontal concatenation operation, and W e 2dxx1 is the parameter vector.
Mutual information between nodes and their sub-graphs, denoted as MI-NSG, enables the graph encoder to learn fine-grained graph-level knowledge. Unlike MI-NG that enforces mutual information between node representations and the graph-level representation, MI MI-NSG maximizes the mutual information between the independently augmented sub-graphs entailed by the which learns fine- -rniindd knowledge compared with MI-NG. Specifically, given two sub-graphe Gi 9h TTopoRec that are constituted by the same seed nodes but augmented differently, the objective of MI-NSG is formulated as a variant of InfoNCE (Chen et al., 2020):
anchor nodes,
Exp (s((s0((1d000000005000000..
Lui Ni > log
(21)
Dja Exe (m011110000000001110000
Exn (1
where SIM(h,, h2) Thy -- hall is the similarity metric, ExP(-) stands for the exponential function, and is the temperature hyper-parameter used to control the sharpness of the similarity distribution (i.e., we explore 7 of 0.1 across all datasets).
C DATASET DESCRIPTION
We evaluate our proposed PARETOGNN as well as unsupervised SSI.-based GNNs on 11 real- world datascts spanning various fields such as citation network and merchandise network. Their statistics are shown in Table 4. For Wiki-CS, Pubmed, zm Pan--Photoo.. o, zon Zma-onnnne Computer, Coauthor-CS, and Seautho-PPhysicee we use the API from Deep Graph Library (DGL)'
hhttps://ww/ 1...a..
16

---

Published as a conference paper at ICLR 2023
to load the datasets, For ogbn-arxiv and ogbn-products,, Benchmark (OGB)". For Chame leon, Actor and Squirrel, the datasets are downloaded from the official repository of Geom-GCN (Pei et al., 2019)².
the API from Open Graph
Table 4: Dataset Statistics.
Dataset
Nodes
# Edges
Features
Type
Split
Wiki-CS
11,701
216,123
300
Homophilous
10%%/10%/80%
Pubmed
19,717
88,651
500
Homophilous
10%\/19%/80%
Amazon-Photo
7,650
119,043
745
Homophilous 10%//0%/80%
Amazon-Computer
13,752
245,778
767
Homophilous
10%\/19%/80%
Coauthor-CS
18,333
81,894
6,805
Homophilous
10%6/10%/80%
Coauthor-Physics
34,493
247,962
8,415
Homophilous 10%/10%%/80%
ogbn-arxiv
169,343
1,166,243
128
Homophilous
Public Split
ogbn-products
2,449.029
61,859,140
100
Homophilous
Public Split
Chameleon
2,277
36,101
2.325
Heterophilous
10%\/10%/80%
Actor
7,600
33.544
931
Hetcrophilous
10%\/1%%/80%
Squirrel
5,201
217,073
2,089
Heterophilous 10%\/0%%/80%
D ADDITIONAL EXPERIMENTAL SETTINGS
Hyper-parameters. The hyper-parameters for PARETOGNN across all datasets are listed in Table 5.
Table Hyper-parameters used for PARETOGNN. SAINT stands for sampling strategy proposed in GRAPHSAINT (Zeng et al., 2019), and its node version.
Hyper-parans
wiki.co
Pubsed
An Photo
An. Comp.
Co.
Co Phy.
Chan.
Squai cree
Actioe
product.
Hyper parameters wit. FoatRoe
Sampling Strategy
SAINT 200,000
Scal
Node Mask Raãio
used for datasets 0.35 usd all danasets
Edge Drop Razio
Hyper-gerameters will TopoRee
Sumpling Stratogy
-oder samplex (Humiitoo (K eguis
layers
5,120
10,240
10,240
10,240
5,120
Hypenpprameters winl RepDecor
Strategyy
used datinets.
Seed Nodes
10,000
10,000
10,000
20,000
1,500
100,000
0.2
Featun: Mask
02
Sampling Stritegy
C-nnder sub graphs
SAINT
Full Full
Full Full
3
Full Full
3
3
Scod Nockes
$.120
10,340
10,340
1,004
3,073
5,170
10,340
20.450
Hyper parumeters w.L. 119-
Sampling Strategy
& order sub graphs
SAINT
3
3
3
3
Sced Nodes
5,120
5,120
$,120
5.120
10,240
5,120
1,044
3JU72
3,072
512
20,450
Edge Drup Bazio
0.2
0.2
0.2
0.2
0.5
0.5
0.2
0.2
0.2
0.2
0.2
Peature Mask Ratio
0.2
0.2
0.2
0.2
0.5
0.5
0.2
0.2
0.2
0.2
0.2
Hype-parameters wit. the CINN modder
Lavess
2
2
3 256x3
Hidden Dimension
1512, 256)
[512. 256]
[512, 236)
[512, 236)
[512, [312, 256)
1312. 256]
[512, 236)
[512,256]
512x3
Activtiion
PRcl useal for danoots
Bunch Nerm.
Y
Y
Y
Y
N
Layer Nerm
N
N
Optimizer
AdamW with le-5 weight decar used for all dittners
Training Stogs
10,000 used for datroets.
Strpping constant
le-5 mood all dittects
Learning Rate
5e-4
le:3
1e-4
Se-4
Se
1e-4
Se
1e.3
1e:3
1e-4
1e-4
Hardware and software configurations. We conduct experiments on a server having one RTX3090 GPU with 24 GB VRAM. The CPU we have on the server is an AMD Ryzen 3990X with 128GB RAM. The software we use includes DGL 1.9.0 and Py Tyrchh 1.11.0.
hhtpps://op..stafoodd.dt sta.b.staaood..d.
'https://ee thgght.h.......g com www.///aw/mmmooa/// -ii waciiiccjjluuueeeee /lu/geon-gon
17

---

Published as a conference paper at ICLR 2023
Baseline Implementation. As for the baseline models that compare PARETOGNN with, explore the implementations provided by code repositories listed as follows:
DGI (Velickovic al., examplees/pytorrcc///gg
GRACE (Zhu et al., 2020):
exampless/pytoxcch/grre
MVGRL (Hassani & Khasahmadi, 2020):
https://ggthhub.cc////m////////
AUTOSSL (Jin et al., http://////ttttaooooo///aaaaaaaa
BGRL (Thakoor al., 2022): https:
examples//pttorch/bggr httpg///t//ctoo//oac/////////o//
CCA-SSG (Zhang et al., 2021b); http:s//ghhhabb.cc////ggguuuuuu
CCA-SSG.
GRAPHMAE (Hou et al., 2022): httppp///ggthhbb..cc////////////
We sincerely appreciate the authors of these works for open-soureing their valuable code and researchers at DGL for providing reliable implementations of these models.
E TRAINING TIME AND MEMORY CONSUMPTION
The scalability w.r.t. the graph dimensions is well leveraged by utilization of sampled sub -ub-ggaahs and experimentally verified by PARETOGNN's strong performance over large graphs, as shown in Table 3. On top of this, also measure the training time and GPU memory consumption give direct empirical understanding of PARETOGNN's overhead, as shown in Table 6. For AUTOSSL, notice that the calculation of the homooplly is extremely slow because such a process cannot enjoy the GPU acceleration. GPU remains mostly idle during the training of AUTOSSL. Though PARETOGNN is not as efficient as BGRL when the graphs are small-scaled; for large graphs such OGBN-PROD PRODUCTS all methods require sampling strategies and in this case the efficiency of PARETOGNN is on par with that of BGRL. BGRL learns from one large graph (though sampled), and PARETOGNN learns from multiple relatively small graphs, which entails similar computational overheads.
Table 6: Training time and memory consumption of PARETOGNN. *; model is trained sub- -ibb-graps with dimensions matching the maximum GPU memory (i.e., 24 GB).
Dataset
AUTOSSL GRACE BGRL
PARETOGNN
Training time per 1,000 iterations (s)
Wiki-CS
7,319
197
34
234
Co.CS
11,340
662
121
618
ogbn-arxis
1.76 10s
844*
331
690
ogbn-products
OOM
1,573*
1,108*
1,134
Peak Memory Consumption (GB)
Wiki-CS
15.7
6.3
1.9
12.1
Co.CS
23.7
13.8
5.4
12.6
ogbn-arxiv
23.7
23.8*
8.9
21.4
ogbn-products
OOM
24.0*
23.7*
22.8
F PERFORMANCE OF INDIVIDUAL TASKS ON LARGE GRAPHS
In Table 3, we demonstrate the task generalization of models over large graphs (i.e., oobnn arxiv and ogbn-grooeeooooo pronn--rroctss quantified by the average performance the four downstream tasks. Here
18

---

Published as a conference paper at ICLR 2023
Table 7: The performance and task generalization of PARETOGNN as well as state-of-the-ar unsupervised baselines over large graphs. (#: Graphs are sampled by GRAPHSAINT (Zeng et al., 2019) matching the memory of others due OOM.)
Dataset
Method
Node Clas.
Node Clus.
Link Pred.
Part. Pred.
Average
DGI
70.26
42.4640.17
98.02-t0.04
68.27
69.75
GRACE
71.04
42.01
95. .99
67.11
68.82
AUTOSSL
69.13
41.7040.00
96.1210.00
65.12
68.02
ogbn-arxiv
BGRL
20.55
44.2540.10
95.05
69.32...11
70.04
CCA-SSG
71.24
42.45
96.63 oz2
68.17 28.112
69.62
GRAPHMAE
71.21
44.21
96.02++.17
73.14
71.15
PARETOGNN
71.47
46.71 10.11
97.66
69.70
71.39
DGI
72.52
50.00
98.81 98.81
80.59
75,48
GRACE
72.65
50.12
97. 97.9640.14
80.59
75.58
AUTOSSI.
OOM
ogba-products
BGRL
72.11
49.87
98.89
79.87
75.19
CCA-SSG
72.09:0.21
47.78:1031
94.28
77.50
72.92
GRAPHMAR
72.60
47.08
98.87+0.10
80.99
74.89
PARETOGNN
*
73.25
50.17
98.5440.13
81.97 +0.23
75.98
we provide additional experimental results on models' performance of every individual task, as shown in Table 7.
We notice that the graph dimension is a limiting factor for the strong task generalization of our proposal. Besides the conclusion we have drawn in Section 3.4, where PARETOGNN outperforms the runner-ups by 2.5 on rank the average performance calculated over the four tasks, we also observe strong single-task performance on some tasks, demonstrating that PARETOGNN achieves better task generalization via the disjoint yet complementary knowledge learned from different philosophies.
G SADDLE-POINT TEST FOR PARAMETERS IN PARETOGNN
In PARETOGNN, the saddle point test conditions (Désidéri, 2012) for the shared GNN encoder (i.e., fg(: 0g)) as well the task-specific heads (i.e., fa (1; 0x)) defined as the following:
For Og. there exist such that every element in is greater than equal to 0, ||o/| = 1,
and Σ ag Vo, (9: Te, 0g 0k) O.
* For [0x] we have Vo. Lu (9; Te, 0g. 0x)= =
According to MGDA, the solution above gives a descent direction that improves all tasks, which improves the task generalization while minimizing potential conflicts.
H CONNECTIONS TO OTHER PARETO LEARNING FRAMEWORKS
This section greatly inspired by valuable comments from the reviewers of this paper". We sincerely appreciate endeavors from the reviewers to help further refining this paper.
Task reconciliation by Pareto learning is mostly explored by works in the Computer Vision com- munity (Lin al., 2019; Mahapatra & Rajan, 2020; Chen al., 2021). In their settings, usually there exist one main task and multiple auxiliary tasks. They explore Pareto learning with preference vectors enforce the learning models to remain good performance on the main task while extracting information from auxiliary tasks as much as possible. Pareto learning with user-defined preference vectors sensible in their cases, as they do not want the auxiliary tasks to hinder the learning of the main task (i.e., a preference of the main task over the auxiliary tasks). For example, PSST (Chen al., 2021) enhances the model's few-shot learning capability (i.c., the main task) by optimizing the model with the main task as well as additional pretext tasks (i.e., the auxiliary tasks). In this case,
Detailedd reviews available httpt::t///......... /ttp:///ppee//eeeeeeee we. forum? 1 HHHAARRFMM.
19

---

Published as a conference paper at ICLR 2023
while remaining competitive performance the main task, PSST also regularizes the learning model against extracting task-irrelevan information (Ren & Lee, 2018; Ravanelli et al., 2020) by training with auxiliary tasks, which empirically further improves the performance on the main task.
However, our scenario is completely different from theirs because we do not want a task governing others (i.e., all tasks are main tasks). The task reconciliation proposed in paper is not biased toward any task. If preference vectors are explored, some pretext tasks will definitely be jeopardized due to the definition of Pareto optimality (i.e., Definition 1). Such bias over the pretext tasks would cause the self-supervised GNNs not performing equally well on every downstream task and dataset. hurts the overall average performance and task generalization, which are the main focuses of this paper. To empirically validate that an utilization of preference vector contradicts our goal, we conduct experiments on PARETOMTL. (L.in al., 2019) with five preference vectors (i.e., five vectors for different preferences over five tasks), as shown in Table 8.
Table 8: The task generalization of multi-task learning with weighted summation (i.e., w/o Pareto), PARETOGNN, and five PARETOMTL variants with preferences favoring different tasks.
PARETOMTL with FeatRec
PARETOMTL with TopoRes
PARETOMTL with RepDezer
PARETOMTL with MI-NG
PAKETOMTL with MI NSG
Dataset
N/o Pareto
PARETOGNN
WIKLCS
74.64
76.03
74.15
72.42
70.36
72.44
75.89
PUBMED
69.82
72.48
70.66
67,92
67,59
68,30
09.01
We observe that multi-task self-supervised learning via Pareto learning with preference vector under most of the time does not even outperform the vanilla weighted summation (i.e., w w/o Pareto) due the bias introduced by the preference vectors. Our proposed PARETOGNN consistently outperforms variants based on PARETOMTL with different preferences. Though sometimes variants with preference vectors approach the performance of PARETOGNN (i.e.. PARETOMTL with MI-NSG in WIKICCS) coming to this results needs a grid-search on all possible preference vectors, which is inefficient when heuristics such as the prior knowledge are not available. Including preferences in multi-tast learning could be very helpful when one or set of training tasks need to be highlighted, whose success demonstrated by the experiments in PARETOMTL. But this not our case, because to achieve strong task generalization for GNNs, philosophies contained in all pretext tasks are equally important. Our implementation of PARETOMTL comes from its official Github repository".
20


Reviews:
[{"review_id": "j8GrftA7AA", "reviewer": "Reviewer_WfQN", "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": "", "summary_of_the_paper": "This paper proposes a multi-task self-supervised learning framework namely ParetoGNN for node representation learning on graphs. The proposed method adopts five pretext self-supervised learning tasks and designs a multiple-gradient descent algorithm to reconcile different tasks by actively learning and minimizing conflicts. Extensive experiments over four downstream tasks and 11 benchmark datasets show that the proposed method can improve the model's task generalization ability.", "summary_of_the_review": "See above. ", "strength_and_weaknesses": "Pros:  \n[+] Multi-task SSL for node representation learning over graphs is a novel and important problem.   \n[+] This paper shows that task conflicts commonly exist in real-world graph datasets and theoretically proves that the proposed method can resolve task conflicts.  \n[+] This paper conducts extensive experiments over four downstream tasks and 11 benchmark datasets.  \n[+] The illustration of motivation, method design, and experiments are quite clear.  \n[+] Experiment details are contained in the appendix, including hyperparameters, settings, etc. Source codes are also included.  \n\nCons:  \n[-] It seems that the proposed method to resolve task conflicts is agnostic of domains, i.e., not specifically designed for graphs. It would make the paper stronger if further analysis of the difference between conflicts in graphs and other domains could be analyzed. For this reason, I think that the technical novelty is somewhat limited.  \n\n=== after rebuttal ===\nI have read the rebuttal and thank the authors for further clarifications. All things considered (including the quality of my other reviewed papers), I'd like to keep a slight positive score as 6.\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "6bhnqkS3R-m", "reviewer": "Reviewer_15ww", "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": "", "summary_of_the_paper": "The paper investigates the use of multi-task learning for GNN self-supervised learning and particularly uses a combined gradient based on pareto optimality. The model seems to improve upon existing ones, interestingly, especially also in terms of generalization capability w.r.t. heterophily/homophily.\n", "summary_of_the_review": "Altogether, this work seems to be a solid contribution to me. I am too few expert of self-supervised learning to judge if it is really novel w.r.t. SOTA. If the other reviewers can confirm the latter, I would suggest acceptance.\n", "strength_and_weaknesses": "(+) The question represents an interesting topic to be investigated and the paper presents a reasonable approach which, to the best of my knowledge, is novel, especially the integration of the gradients.\n\n(+) The authors provide theory proving convergence. Please note that I did not check all that in full detail.\n\n(+) The evaluation considers various datasets, also challenging ones from OGB, tasks, and baselines. I am no expert in SSL to be able to judge if the most important competitors are considered.\n\n(-) Some statements seem unlucky/misleading to me:\n- The main question \"Does combining multiple philosophies enhance task generalization for SSL-based GNNs?\" sounds a bit too easy. \"Yes\" should be a very likely I would think. \n- Similarly, the authors claim throughout the paper that models focusing on a single task perform \"poorly\" (as narrow experts) and generalization beyond a single task is needed. I would think that these are too bold claims. If we developed perfect experts over time, this would not be a problem. Nevertheless, the fact that the paper shows that the generalization obtained helps improving over single-task-focused models is great. I just would frame it differently.\n\n(-) The paper is missing related work. For example, [1] propose to combine different self-supervised learning strategies and demonstrate that the combination is beneficial. Similarly, I would consider multi-task learning in GNNs as related work to be mentioned in more detail.\np.9 \"In these frameworks\" - if there are more, these should be referenced as well since this is closely related work.\n\n[1] Hu et al. STRATEGIES FOR PRE-TRAINING GRAPH NEURAL NETWORKS, ICLR 2020\n\n", "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": "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": {}}, {"review_id": "1hKkiskOcA", "reviewer": "Reviewer_wz1H", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The authors propose PARETOGNN, which is a multi-task SSL framework using the concept of Pareto optimality.\n\n\nThe self-supervised learning (SSL) for multi-task is still challenging especially over graph-structured data.\n\n\nIn this environment, the SSL frameworks for the graph that adhere to just one objective might perform poorly to the others.\n\n\nTo improve task generalization, PARETOGNN is simultaneously trained on various SSL tasks while promoting Pareto optimality using the Multiple Gradient Descent Algorithm(MGDA).\n\n\nIt allows the model to capture inherent patterns that are relevant to several pretext tasks while reducing possible conflicts.\n\n\nAs a result, the model learns different patterns transferable to multiple tasks on graphs.", "summary_of_the_review": "I set the confidence of this review to a low score because I would change (or finalize) my decision after the discussion period (regarding the novelty issue).", "strength_and_weaknesses": "**Strengths**\n\n\n- The paper including the appendix is well-written and organized. \n\n- The authors compare several features of the existing methods with the proposed method and provide a detailed discussion.\n\n- The results on benchmarks are comparable to or better than most baselines.\n\n---\n\n\nThere has been papers that explore Pareto optimality for SSL or MTL [1,2].\n\nWhat is the main contribution of your work compared to them?\n\nOf course I could have noticed, but I'm asking for the benefit of other readers.\n\nBecause it might seem to just simple extension of these series of works into graph version.\n\nIn Pareto MTL [2], the authors claim that the multiple gradient descent algorithm (MGDA) is not capable to incorporate different trade-off preference information as illustrated in Figure 2 of [2].\n\nDoes it mean ParetoGNN also can have the same weakness?\n\n---\n\n\n[1] Pareto Self-Supervised Training for Few-Shot Learning, Chen et al., CVPR 2021\n\n[2] Pareto Multi-Task Learning, Lin et al., NeurIPS 2019", "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": {}}]

Author rebuttal:

Decision: Accept: poster