# Boosting Multitask Learning on Graphs through
Higher-Order Task Affinities

Dongyue Li  Northeastern University<EMAIL_ADDRESS>,  Haotian Ju
Northeastern University<EMAIL_ADDRESS>,  Aneesh Sharma  Google
<EMAIL_ADDRESS>and  Hongyang R. Zhang  Northeastern University
<EMAIL_ADDRESS>
(2023)

###### Abstract.

Predicting node labels on a given graph is a widely studied problem with many
applications, including community detection and molecular graph prediction.
This paper considers predicting multiple node labeling functions on graphs
simultaneously and revisits this problem from a multitask learning
perspective. For a concrete example, consider overlapping community detection:
each community membership is a binary node classification task. Due to complex
overlapping patterns, we find that negative transfer is prevalent when we
apply naive multitask learning to multiple community detection, as task
relationships are highly nonlinear across different node labeling. To address
the challenge, we develop an algorithm to cluster tasks into groups based on a
higher-order task affinity measure. We then fit a multitask model on each task
group, resulting in a boosting procedure on top of the baseline model. We
estimate the higher-order task affinity measure between two tasks as the
prediction loss of one task in the presence of another task and a random
subset of other tasks. Then, we use spectral clustering on the affinity score
matrix to identify task grouping. We design several speedup techniques to
compute the higher-order affinity scores efficiently and show that they can
predict negative transfers more accurately than pairwise task affinities. We
validate our procedure using various community detection and molecular graph
prediction data sets, showing favorable results compared with existing
methods. Lastly, we provide a theoretical analysis to show that under a
planted block model of tasks on graphs, our affinity scores can provably
separate tasks into groups.

Multitask Learning; Boosting; Modeling Task Relationships

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining; August
6–10, 2023; Long Beach, CA, USA††booktitle: Proceedings of the 29th ACM SIGKDD
Conference on Knowledge Discovery and Data Mining (KDD ’23), August 6–10,
2023, Long Beach, CA, USA††doi: 10.1145/3580305.3599265††isbn:
979-8-4007-0103-0/23/08††ccs: Computing methodologies Multitask Learning††ccs:
Computing methodologies Neural Networks

##  1\. Introduction

Figure 1. Overview of our boosting procedure: (1) We sample random subsets of
tasks, each subset containing a fixed number of tasks. (2) For each subset
$S_{k}$, for $k=1,2,\dots,n$, we fit a multitask learning (MTL) model on the
combined data sets of all tasks in $S_{k}$, using a graph neural network (GNN)
as the shared encoder. After fitting the MTL model, we evaluate its prediction
performance for each task $i\in S_{k}$, denoted as $f_{i}(S_{k})$. (3) We
compute an affinity score $\theta_{i,j}$ by averaging task $i$’s scores among
all subsets as in equation (1), where $n_{i,j}$ is the number of subsets
including both $i,j$. This results in a $T$ by $T$ affinity matrix, denoted as
$[\theta_{i,j}]_{T\times T}$. (4) We apply spectral clustering on this matrix
to find clusters of task groups and fit one GNN for each task group.

Given multiple node label prediction tasks on graphs, can we design a model to
predict all of them simultaneously? For example, consider supervised,
overlapping community detection (chen2017supervised, 96): Given a set of
labels as a seed set, can we learn to predict whether another node of the
graph belongs to a community? This is an example of multi-label learning: The
input involves labels of multiple communities. The goal is to predict
community labels for the remaining nodes of each community. In this paper, we
cast this multi-label classification problem into a more general formulation
of multitask learning (caruana1997multitask, 67, 120), which has numerous
other applications in knowledge graphs (wang2019multi, 100) and protein-
protein interactions (hu2019strategies, 107). Traditionally, multitask
learning works by fitting a single model on all tasks (crammer2008learning,
78, 79). By contrast, we investigate task relationships on graphs with a
shared graph neural network. We observe notable negative transfers between
various tasks. We address this challenge by designing a boosting procedure to
cluster tasks into groups and then fit multiple graph neural networks, one for
each task group.

Negative transfer refers to scenarios where learning multiple tasks using a
shared encoder can worsen performance compared to single-task learning (STL)
for one task (wu2020understanding, 113), and this has been observed for
various data modalities (yang2016deep, 91, 111, 112, 116). The cause can often
be attributed to heterogeneity in input features or dataset sizes. Much less
is known about graph data. (zhu2021transfer, 121) and (ju2023generalization,
130) identify structural differences for transfer learning on graphs due to
the graph diffusion process. These structural differences can also cause
negative interference in multitask learning. Thus, building multitask graph
neural networks requires better modeling of structural differences between
tasks. This modeling could also be used to identify task grouping
(fifty2021efficiently, 115).

The classical multitask learning literature has studied task relatedness
through heuristics and theoretical perspectives (caruana1997multitask, 67, 72,
79). These results do not naturally apply to nonlinear neural networks. A
naive solution to optimize multitask learning performance is to search through
all possible combinations of tasks to select the best subset. This is costly
to compute for a large number of tasks. Prior work (standley2020tasks, 110)
computes pairwise task affinity scores by training one model for every pair of
tasks and approximates higher-order task affinities by averaging first-order
affinity scores. (fifty2021efficiently, 115, 114) compute first-order task
affinities using gradient similarity. These methods are much more efficient
than naive search, but they ignore higher-order relationships among tasks,
such as combining more than two tasks. This is critical as higher-order task
affinities can exhibit more complexities. We observe that they cannot be
reliably predicted from first-order affinity scores (cf. Figure 5, Section
5.1) as transfer relationships are not monotone or submodular, meaning that
adding more task data does not necessarily help performance (see Figure 4,
Section 3.2). Moreover, naively computing all pairwise affinities requires
fitting $T^{2}$ models given $T$ tasks, which is costly even for tens of
tasks.

This paper’s main contribution is to design an efficient algorithm to cluster
tasks into similar groups while accounting for higher-order transfer
relationships. One can compare the performance of a multitask model, such as a
GNN trained on all tasks, against several multitask GNNs, each trained for a
task group. Section 5 shows that this approach yields the best results among a
wide set of baselines on various real-world datasets. Our method can be viewed
as a _boosting_ procedure (breiman2001random, 69) and can be used on top of
any graph learning algorithm.

Approach. We outline the overall procedure; See also Figure 1 for an
illustration. Given $T$ tasks, we first compute a task affinity score
$\theta_{i,j}$ for every pair of tasks $i$ and $j$. A higher value of
$\theta_{i,j}$ indicates task $j$ transfers better to task $i$ while also
accounting for the presence of other tasks. Conceptually, $\theta_{i,j}$ is
similar to the feature importance score in random forests when hundreds of
other features are available. This higher-order task affinity score can also
predict whether a set of tasks transfer positively or negatively to a target
task. Given the affinity score matrix $[\theta_{i,j}]_{T\times T}$, we use a
spectral clustering algorithm (ng2001spectral, 70, 68) to separate tasks into
similar groups, which is more suitable for joint training. Specifically, our
algorithm optimizes the sum of task affinity scores within groups through
spectral clustering.

Next, we describe the steps to estimate the affinity score matrix. A naive
approach is to compute each entry individually, requiring $O(T^{2})$
complexity. We design an efficient sampling procedure that only requires
$O(T)$ complexity. Concretely, we sample $n=O(T)$ random subsets from
$\\{1,2,\dots,T\\}$ of a fixed size $\alpha$ (in practice, $\alpha=5$
suffices). We fit an MTL model for each subset and evaluate its prediction
loss for each task in the subset; Let $f_{i}(S)$ denote the prediction loss of
task $i$, given a subset $S\subseteq\\{1,2,\dots,T\\}$, which we evaluate on a
holdout set. Thus, $f_{i}(S)$ measures the information transfer from $S$ to
$i$. Then, we compute $\theta_{i,j}$ as the average among all subsets
including $i,j$:

(1) $\displaystyle\theta_{i,j}=\frac{1}{n_{i,j}}\Big{(}\sum_{1\leq k\leq
n:\,\\{i,j\\}\subseteq S_{k}}f_{i}(S_{k})\Big{)},~{}~{}\text{ for all }1\leq
i,j\leq T.$

To rigorously justify the rationale behind our affinity scores, we conduct a
theoretical analysis in a stochastic block model style setting, where tasks
follow a well-separated structure. We prove that under this planted model, the
affinity score matrix $[\theta_{i,j}]_{T\times T}$ exhibits a block-diagonal
structure, each block corresponding to one cluster. This characterization
shows that the spectral clustering algorithm recovers the underlying task
structure.

Summary of Contributions. The contribution of this work is threefold. First,
we design a task affinity score to measure higher-order task relationships and
estimate the scores with an efficient sampling procedure, which only requires
fitting $O(T)$ MTL models. Second, we propose a spectral clustering step to
find task groups based on the affinity score matrix. We provide recovery
guarantees for this clustering procedure and show that the affinity scores can
be used to provably group related tasks in a planted model. Third, we validate
the benefit of our boosting approach using various community detection and
molecular graph prediction datasets. The experimental results show that our
approach improves test accuracy over different community detection and MTL
baselines.

Organization. The rest of this paper is organized as follows. We first outline
related work in Section 2. In Section 3, we provide empirical grounding for
the claim that accounting for negative transfer among tasks is crucial for MTL
on graphs. Our boosting procedure is described in Section 4, followed by a
thorough empirical study of its performance in Section 5. Finally, in Section
6, we describe the theoretical analysis of our algorithm. In Appendix A, we
provide complete proofs for our theoretical results. In Appendix B, we
describe additional experimental results left from the main text.

##  2\. Related Work

###  2.1. Modeling task relationships in MTL

The importance of learning from a pool of disparate data sources is well-
recognized in the data mining literature (ben2002theoretical, 71). However,
naively combining several heterogeneous data sources can result in negative
interference between their feature representations (wu2020understanding, 113).
Researchers have designed methods to extract shared information from different
tasks. For instance, explicit regularization applied to the representations of
all tasks can help encourage information transfer (evgeniou2004regularized,
73). These regularization schemes can be rigorously justified for convex
hypothesis classes (nie2018calibrated, 94). For nonconvex hypothesis spaces
such as graph neural networks, explicitly regularizing the feature spaces of
all tasks is a non-trivial challenge (yang2016deep, 91, 122). (ma2018modeling,
93) introduce a mixture-of-experts model to capture the task relationships,
with each expert being an MTL network. (yu2020gradient, 114) design gradient-
based similarity measures that can be efficiently computed using the cosine
similarity of gradients during training. This can be extended to measure the
similarity between two sets of tasks by averaging the gradient of tasks in
each set. Recent work (li2022task, 127, 131) points out that first-order
affinity measures deteriorate as a transferability measure when applied to a
large set of tasks.

Task Grouping. Instead of sharing layers and model parameters across all
tasks, (kumar2012learning, 82) proposes mitigating negative transfers by
dividing tasks into several related groups. Our paper takes inspiration from
Datamodels (ilyas2022datamodels, 125), which extrapolates the outcome of deep
networks as influence functions. In particular, (ilyas2022datamodels, 125)
find that a linear regression method can accurately approximate the outcome of
deep nets trained with a subset of samples on popular image benchmarks. Our
results (e.g., Figure 5) show that the affinity scores can also accurately
predict transfer types in multitask learning.

###  2.2. Transferable graph neural networks

Graph neural networks have emerged as widely used tools for graph learning.
Ideally, we want to learn a powerful embedding for all downstream tasks
(lee2017transfer, 90, 99, 97, 109, 86, 101). (zhu2021transfer, 121) analyzes
the transferability of GNN from graph $A$ to graph $B$ and highlights the
complex correspondence between structural similarity and transferability
between GNNs. Besides GNN, researchers have also observed negative
interference while applying graph embedding to perform transfer learning on
Graphs (gritsenko2022graph, 124). (ju2023generalization, 130, 126) show non-
vacuous generalization bounds for graph neural networks in the fine-tuning
setting using Hessian. Our paper expands on these prior works in two aspects.
First, we consider a multi-label learning setting involving as many as 1000
tasks, whereas the work of (zhu2021transfer, 121, 124) focuses on transfer
learning from graph $A$ to graph $B$. Second, we consider multiple node
prediction tasks on a single graph, which is different from graph pretraining
(e.g., (qiu2020gcc, 109, 107)) and graph algorithmic reasoning
(velivckovic2022clrs, 128).

Multitask Learning Applications for Graph-Structured Data. Combining multiple
graph learning tasks jointly can potentially enhance the performance of single
tasks. Our results support this claim in the context of supervised overlapping
community detection. Besides, we believe many graph learning tasks can be cast
into the multitask learning framework. For instance, consider extracting
entity relationships on knowledge graphs; Each entity relation may be viewed
as one task. (wang2019multi, 100) find that learning the dependencies of
different relations through multitask representation learning can
substantially improve the prediction performance. There has also been some
study on the trade-off between fairness and accuracy in MTL
(wang2021understanding, 118). It is conceivable that the new tools we have
developed may benefit these related applications. This is a promising
direction for future work.

###  2.3. Overlapping community detection

Identifying community structures is one of the most widely studied problems in
network science (fortunato2010community, 80). A common approach to finding
communities given a seed set is to measure the local connectivity of a
subgraph using spectral graph properties (e.g., the conductance of a cut).
(yang2013overlapping, 85) describe an efficient algorithm using non-negative
matrix factorization for finding overlapping communities.
(whang2013overlapping, 84) finds local clusters by identifying low conductance
set near a seed. These approaches use the connectivity of edges to compute
spectral properties. Besides, higher-order structures from hypergraphs are
found to be useful for overlapping community detection (benson2016higher, 87,
92). Lastly, community detection can be cast in the correlation clustering
framework, which does not require specifying the number of communities
(bonchi2022correlation, 123, 75, 76, 117).

Our paper is closely related to the work of (chen2017supervised, 96). The
difference is that we formulate the problem of predicting community labeling
via multitask learning, whereas (chen2017supervised, 96) consider a multi-
class classification setup. Our formulation is more suitable when we are
dealing with a large number of overlapping communities. This is a novel
perspective on community detection to the best of our knowledge. Our results,
compared with strong baselines including VERSE embedding (tsitsulin2018verse,
95) and BigClam (yang2013overlapping, 85), suggest that modeling higher-order
task relationships can significantly improve empirical performance for
multitask learning.

##  3\. Investigating Task Relationships

We investigate task relationships in the setting of overlapping community
detection. We demonstrate that negative transfer is widespread across tasks
and persists in large models. We show that task relationships are neither
monotone nor submodular in the higher-order regime. Motivated by these
considerations, we propose a task grouping problem for conducting MTL on
graphs.

###  3.1. Setup and background

Figure 2. This figure illustrates the widespread negative transfer effect
among tasks by noting that MTL performance can dip below STL for four separate
(randomly selected) target tasks. We fix a target task $i$ for each plot, then
randomly pick ten source tasks (out of $100$) and for each source task $j$
train an MTL with $i$ and $j$; we report the MTL accuracy for $i$ minus $i$’s
STL accuracy. Thus, bars above zero indicate positive transfers from source to
target tasks, while bars below zero indicate negative transfers.

Figure 3. In each subfigure, we visualize the personalized PageRank vectors of
a set of nodes in one community. They differ dramatically across non-
overlapping communities.

Problem setup. We conduct an empirical study using multiple overlapping
community detection tasks as a concrete example. Given a graph $G=(V,E)$, we
have a list of $T$ communities as subgraphs of $G$. Let
$C_{1},C_{2},\dots,C_{T}$ denote the vertex set of these communities. We are
given a vertex subset of each community during training as seed sets. For
every $i=1,2,\dots,T$, deciding whether a node $v\in V$ belongs to $C_{i}$ is
a binary classification task. Note that this formulation differs from
supervised community detection (chen2017supervised, 96) but is more suitable
for overlapping community detection. This formulation is an example of multi-
label learning, a particular case of multi-task learning (see, e.g., Fig. 1b
of (zhang2021survey, 120)). Casting multi-label learning into this more
general formulation provides new perspectives in solving the problem.

  * •

The prediction of membership in $C_{i}$ is task $i$, which is a binary
classification task, given $G$ and node features.

  * •

There are $T$ tasks, one for each community.

Datasets. We use social network datasets with known community labels,
including the Amazon, YouTube, DBLP, and LiveJournal networks from SNAP
(yang2012defining, 83). We use the 100 largest communities from each network
and keep the subgraph induced by the nodes in the 100 communities. For each
community detection task, we randomly sample 10% of the nodes from the
community in the training set, together with 10% of nodes outside the
community as negative samples. We randomly sample another 20% of nodes as the
validation set and treat the rest as a test set. We evaluate the performance
of each task using the F1 score on the test set. See Table 2 for details
statistics of the four datasets.

Models. We consider an MTL model that consists of a single encoder to obtain
shared representations and a separate prediction layer for each task. We train
this model by minimizing the average loss over all tasks’ training data. Our
experiments in this section use the SIGN model (frasca2020sign, 105) as the
encoder, which is more efficient to train than GCN. The encoder involves 3
layers, each with a fixed width of 256 neurons. Our choice of this encoder is
without loss of generality, and our observations also apply to other encoders.
We construct the node features from the VERSE embedding (tsitsulin2018verse,
95), which encodes personalized PageRank vectors known as valuable features
for community detection (andersen2006communities, 74).

Negative transfer on graphs. A common phenomenon with multitask learning is
negative transfer (pan2010survey, 81), meaning that combining one task with
another worsens performance compared with training a task separately. We show
that negative transfer occurs during MTL on graphs. We take $100$ tasks from
the YouTube dataset. First, we fix a randomly chosen task $i$ as the target
task and use the rest as source tasks. Then, we train a GNN for task $i$, and
99 MTL models, each combining one source task with task $i$. The performance
gap between the MTL and STL models indicates the transferability from a source
task to task $i$.

Figure 2 above shows the results of this experiment, repeated over four
randomly chosen target tasks. The bars above zero correspond to _positive
transfers_ as MTL performance exceeds STL, while bars below zero correspond to
_negative transfers_. We observe that both positive and negative transfers
appear in all four settings.

Structural differences. Why do negative transfers happen during multitask
learning on graphs? A common belief in the MTL community is that this is due
to differences in the task labels (wu2020understanding, 113, 119, 131). We
argue that graph neural networks involve another kind of heterogeneity due to
graph diffusion. We appeal to a connection between GNN propagation and
personalized PageRank (PPR) (klicpera2018predict, 98, 103, 104), positing that
dramatically different PPR structures among communities will induce different
graph diffusion for GNNs. In Figure 3, we visualize the PPR vectors of four
randomly chosen tasks from the YouTube dataset. Within each subfigure, each
row corresponds to the PPR vector of one node that belongs to a particular
community. We plot the PPR vectors of a set of nodes from the same community.
Clearly, PPR vectors differ dramatically for nodes from different communities,
suggesting that the diffusion processes are highly heterogeneous. We also
observe that tasks yield positive transfers tend to have higher similarity
between their PPR vectors. Detailed results are described in Appendix B.1.

Will larger models address negative transfers? A natural approach to
addressing negative transfers is to increase the model size, but this does not
account for the above structural differences. We hypothesize that due to
innate data heterogeneity, negative transfers between tasks cannot be
addressed by increasing the model capacity. To verify this, we use the first
target task from Figure 2 and select the source task in the rightmost bar with
the strongest negative transfer. We gradually increase the number of neurons
in the hidden layer from 32, 64, 128, 256, 512, 1024, to 2048, corresponding
to larger model capacities. Figure 4(a) shows the results. We observe
consistent negative transfers, i.e., the accuracy improvements stay negative,
after increasing the model capacity. We have also observed the same result on
a more powerful GNN with attention, i.e., GAMLP (zhang2022graph, 129). See
Appendix B.2 for these results.

(a) Varying model size

(b) $f$ is not monotone

(c) $f$ is not submodular

Figure 4.  (4(a)) We show a consistent negative transfer even after increasing
the model size (measured by width). (4(b)) The $x$-axis refers to the number
of added source tasks to train with the target task. The $y$-axis refers to
the difference in performance between MTL and STL (with the target task
alone). We observe that the MTL performance of a target task starts to
decrease after adding two or more source tasks, even though these are all
“positive” source tasks (in the sense of pairwise transfer). (4(c)) Under the
presence of a negatively interfering source task, the benefit of adding more
“positive” tasks diminishes, implying that the $f(\cdot)$ function is not
submodular.

###  3.2. How do task relationships behave?

Next, we study the multitask learning performance involving more than two
tasks. At the extreme, this would involve $2^{T}$ combinations of task
subsets. To be precise, given any subset of tasks
$S\subseteq\\{1,\ldots,T\\}$, let $f_{i}(S)$ denote the MTL performance of
combining data from all tasks in $S$, evaluated on task $i$, for each $i\in
S$.

Q1: Is $f$ monotone? To better understand how $f$ behaves, we pick a target
task $t$ and measure $f_{t}(\\{t\\})$. Then, we add new tasks to be combined
with $t$. We only add a task $i$, if task $i$ is beneficial for task $t$,
i.e., $f_{t}(\\{t,i\\})\geq f_{t}(\\{t\\})$. Figure 4(b) shows the result of
applying the above setting to the first target task. We observe that after
adding more than two positive source tasks, the MTL performance decreases.
This shows that $f_{t}(\cdot)$ is not monotone.

Q2: Is $f$ submodular? A function $f(\cdot)$ is submodular if for any two
subsets $S\subseteq S^{\prime}\subseteq\\{1,2,\dots,T\\}$ and any single task
$x$, $f(\\{x\\}\cup S^{\prime})-f(S^{\prime})\leq f(\\{x\\}\cup S)-f(S)$. We
pick one negative source task as $x$ and ask if adding positive source tasks
mitigates the negative transfer. In Figure 4(c), we find that adding positive
tasks does not always help, which implies that $f$ is not submodular. The
scales of $f$ are also different compared to Figure 4(b), because the presence
of the negative task reduces the effect of positive tasks. The takeaway is
that $f$ is not monotone or submodular, motivating our approach to extrapolate
$f$ via sampling.

###  3.3. Task grouping for multitask graph learning

We aim to obtain a set of networks where each network is trained on a subset
of tasks. The objective is to optimize the overall performance of all tasks
after combining the networks. To approach this problem, we consider finding
subsets of tasks, namely task groups, to maximize the positive transfers of
tasks within each group. We want to divide $\\{1,2,\dots,T\\}$ into possibly
overlapping subsets of tasks. Let $\mathcal{S}$ denote the collection of
subsets. Given $\mathcal{S}$, the performance of task $i$ is the highest one
among all networks:

${L}_{i}(\mathcal{S})=\max_{X\in\mathcal{S}}f_{i}(X).$

Thus, the overall performance of all tasks on a solution is
$\sum_{i=1}^{T}{L}_{i}(\mathcal{S})$. Suppose there is a limited inference
budget $b$, the number of MTL models we can deploy in inference. We want to
find at most $b$ groups that achieve the highest performance:
$\sum_{i=1}^{T}{L}_{i}(\mathbf{S})$.

To address this problem, we need to evaluate the multitask learning
performance for all subsets of tasks, which total $2T$ combinations. Because
task relationships are highly non-linear, we need a more efficient procedure
to capture transfer relationships. More generally, finding the optimal task
groups is NP-hard via a reduction from the set-cover problem (see, e.g.,
(standley2020tasks, 110)).

##  4\. Our Approach

We now present our approach to optimize multitask model performance through
grouping tasks that utilize higher-order task affinities. Recall the steps in
our pipeline from Figure 1: (1,2) Repeatedly sample a random subset of tasks,
and evaluate the model’s performance that combines the tasks in each subset.
(3) Average the multitask learning performances over subsets that involve two
specific tasks, yielding the task affinity score. (4) Then, we use these task
affinity scores to group tasks using a spectral clustering algorithm on the
matrix of task affinity scores.

###  4.1. Estimating higher-order task affinities

Notations. Suppose we are given a graph $G=(V,E)$ where $|V|=N$ and $|E|=M$,
with node features $X\in{}^{N\times d}$. There are $T$ semi-supervised tasks
on the graph. For each task $i$, we are given a set of nodes $\hat{V}^{(i)}$
with known labels ${Y}^{(i)}$. The goal of task $i$ is to predict the labels
for the rest of the nodes on the graph $V/\hat{V}^{(i)}$. Note that the set
$\hat{V}^{(1)},\ldots,\hat{V}^{(T)}$ can be either overlapped or disjoint with
each other. The objective is to optimize the average prediction performance
over the $T$ tasks.

Let $\phi$ be the encoder network shared by all tasks. Let
$\psi_{1},\ldots,\psi_{T}$ be prediction layers for tasks $1,\ldots,T$ that
map feature vectors to task outputs. When the input is a graph, we consider
using graph neural networks as the encoder $\phi$. Given
$S\subseteq\\{1,2,\dots,T\\}$, let $\phi^{(S)}$ and $\psi^{(S)}_{i}$, for
$i\in S$, be the trained model on the combined dataset of $S$. We evaluate the
prediction loss on each task’s validation dataset. Let $\widetilde{V}^{(i)}$
denote a set of nodes in $V$, which is used as a validation set for the task
$i$. Let $\ell$ be an evaluation metric, e.g., the cross-entropy loss. We
define multitask learning performance for any $i\in S$ as:

(2) $\displaystyle
f_{i}(S)=\frac{1}{|\widetilde{V}^{(i)}|}\sum_{v\in\widetilde{V}^{(i)}}\ell\Big{(}\psi_{i}^{(S)}\big{(}\phi^{(S)}(X_{v};G)\big{)},Y^{(i)}_{v}\Big{)}$

Measuring task affinity scores. Our approach measures higher-order task
affinities to indicate how well a task transfers another task when combined in
a subset. We show that such task affinity measures can be estimated by
training $n$ models, where $n$ only needs to grow linearly to the number of
tasks $T$. Moreover, our measure gives a more accurate prediction of higher-
order multitask transfer results than previous notions of task affinity.

We view task affinity as a transferability measure from source to target
tasks. Given a task $i\in\\{1,\ldots,T\\}$ as a target task, denote the
affinity of another task $j$ to $i$ as $\theta_{i,j}$. To model the relations
of higher-order transfers. we define the task affinity score $\theta_{i,j}$ as
the average MTL prediction loss $f_{i}(S)$ on target task $i$ over subsets
that contain both task $i$ and $j$. We emphasize that the affinity scores
account for the presence of other tasks. Also note that a higher value of
$\theta_{i,j}$ indicates higher usefulness of task $j$ to task $i$.

We estimate the task affinity scores through a sampling approach.
Conceptually, this is analogous to graph embedding methods that optimize
embeddings to approximate proximity scores. Similarly, we sample random
subsets from tasks $1$ to $T$ and estimate the task affinity scores on the
sampled subsets using this procedure:

  1. (1)

Sample $n$ subsets from tasks $1$ to $T$, denoted as $S_{1},\ldots,S_{n}$. We
sample each subset from the uniform distribution over subsets with size
$\alpha$. In other words, among all subsets of $\\{1,2,\dots,T\\}$ with size
$\alpha$ (note there are $\binom{T}{\alpha}$ of them), we pick one uniformly
at random, with probability $1/\binom{T}{\alpha}$.

  2. (2)

Evaluate prediction loss $f_{i}(S)$ for every task $i\in S_{k}$ and every
subset $S\in\\{S_{1},\ldots,S_{n}\\}$ by training a multitask model on $S$.

  3. (3)

Estimate the task affinity scores $\theta_{i,j}$ by averaging the MTL
performances $f_{i}$ over subsets containing both task $i$ and $j$:

(3) $\displaystyle\theta_{i,j}=\frac{1}{n_{i,j}}\Big{(}\sum_{1\leq k\leq
n:\\{i,j\\}\subseteq S_{k}}f_{i}(S_{k})\Big{)}.$

where $n_{i,j}$ is the number of subsets that contain tasks $i,j$. In
particular, when $i$ and $j$ are the same, we set $\theta_{i,i}$ as the
average of $f_{i}(S)$ over all $S$ having $i$.

To summarize, the above procedure yields a $T$ by $T$ affinity score matrix,
denoted as $\bm{\Theta}=[\theta_{i,j}]_{T\times T}$.

###  4.2. Finding task groups by spectral clustering

Since the affinity scores serve as a proxy of higher-order task relationships,
we optimize MTL performance by finding task groups with the highest task
affinity scores within each group. Our task grouping algorithm, as described
below, contains two major steps. The complete procedure is given in Algorithm
1.

Algorithm 1 Task Grouping Using Higher-Order Task Affinities

Input: $T$ tasks; Training and validation sets of the task.
Require: The size of each subset $\alpha$; Number of sampled subsets $n$;
Inference budget $b$; Multitask learning algorithm $f$.
Output: $b$ trained multitask models.

1: For $k=1,\dots,n$, sample a random subset $S_{k}$ from $\\{1,2,\dots,T\\}$
with size $\alpha$; evaluate $\bm{f}(S_{k})$ following equation (2).

2: Estimate the task affinity scores ${\bm{\Theta}}$ following equation (3).

3: Generate task groups $\mathbf{S}^{\star}=\\{S_{1},\ldots,S_{b}\\}$ by
applying spectral clustering on a symmetric matrix constructed from
$\bm{\Theta}$.

4: Train $b$ multitask models for each task group $S_{1},\ldots,S_{b}$.

First, we construct a transformed affinity score matrix for clustering. Since
the sum of affinity scores between two tasks $i$ and $j$ within a group is
$(\theta_{i,j}+\theta_{j,i})$, we define a symmetric matrix
$\bm{A}_{1}=(\bm{\Theta}+\bm{\Theta}^{\top})/2$. Additionally, we find
auxiliary source tasks for each group that yield positive transfer to the
group. This is achieved by viewing the matrix $\bm{\Theta}$ as directional
task relationships, with source tasks represented along the rows and target
tasks along the columns. To find a set of source tasks that yield the highest
affinity scores to a set of target tasks, it is natural to consider the
symmetrized matrix $\left[\begin{smallmatrix}\bm{0}&\bm{\Theta}\\\
\bm{\Theta}^{\top}&\bm{0}\end{smallmatrix}\right]$. Thus, based on the
affinity score matrix $\Theta$, we construct a symmetric matrix:

$\bm{A}=\left[\begin{matrix}\bm{A}_{1}&\bm{\Theta}\\\
\bm{\Theta}^{\top}&\bm{0}\end{matrix}\right].$

Second, we apply spectral clustering algorithms (e.g., (ng2001spectral, 70,
68)) on $\bm{A}$ and merge the clustered target and source tasks in one group
of final task groupings. Afterward, we train one multitask model for each
group by combining all the data from that group.

##  5\. Experiments

We now evaluate our approach empirically on various community detection and
molecular graph data sets. First, we show that our task affinity scores can be
estimated efficiently to predict negative transfers more accurately than
first-order task affinities. Second, we apply our approach to overlapping
community detection tasks on several datasets with ground-truth community
labels: our approach outperforms the naive MTL by 3.98% and task grouping
baselines by 2.18%. Third, we evaluate our approach on molecular graph
prediction tasks and show a 4.6% improvement over prior MTL methods. Lastly,
we provide ablation studies to show that our approach is stable under various
settings. The code for reproducing our experiments is available at
https://github.com/VirtuosoResearch/boosting-multitask-learning-on-graphs.

###  5.1. Results for predicting negative transfers

Experiment setup. We use task affinity scores $\theta_{i,j}$ for predicting
negative transfers as follows. Given a target task $i$ and a subset of tasks
$S$ containing $i$, we predict whether the subset $S$ transfers negatively to
a task $i$, i.e., the MTL prediction loss $f_{i}(S)$ of training task $i$ with
subset $S$ is worse than the STL loss of task $i$.

We set up the prediction as binary classification. For each task $i$, input
feature for a subset $S$ is the task affinity scores of tasks in $S$ to task
$i$: $\text{1}_{S}\circ[\theta_{i,1},\ldots,\theta_{i,T}]$. The label is
whether the subset $S$ transfers negatively to a task $i$. Then, we fit a
logistic regression model that maps the features to the binary labels. We fit
$T$ models in total and evaluate the average F1-score over the $T$ models.

We evaluate the above prediction on the YouTube dataset with $T=100$ tasks and
estimate task affinities of order $5$, $10$, and $20$ (which means that the
size of sampled subsets is $\alpha=5$, $10$, or $20$). We use the transfer
results on $n=2000$ task subsets to fit logistic regression models and
evaluate the predictions on 500 new task subsets that do not appear in
training.

Figure 5.  We use task affinity scores from tasks in a subset $S$ to task $i$
to predict whether training with subset $S$ decreases the STL performance of
task $i$. Left: Compared with two first-order task affinity scores, our
higher-order task affinity scores achieve consistently better F1-score for
predicting negative transfers of combining up to $\alpha=20$. Right: The
F1-score for predicting negative transfers converges when the sampled subsets
$n$ reach $2000$. Results consistently hold for different subset sizes.

Results. First, we illustrate the convergence of $F_{1}$-score of negative
transfer prediction when increasing the sample size $n$, as shown in the right
of Figure 5. We observe that with $n\leq 2000=20T$, using higher-order task
affinity scores predicts negative transfers with $F_{1}$-score above 80%. This
result consistently holds for sampling subsets of different sizes.

Second, we compare our approach to two previous notions of affinity scores.
One involves computing first-order task affinity through the effect of one
task’s gradient on another task’s loss (fifty2021efficiently, 115). Another
approximates the higher-order task transfers by averaging the first-order task
affinity scores (standley2020tasks, 110). Figure 5 on the left shows that the
$F_{1}$-score from previous measures gradually gets worse; Ours are accurate
for subsets of size ranging from $2$ to $20$.

Figure 6. Comparing the runtime for computing higher-order vs. first-order
task affinity (standley2020tasks, 110, 115).

Run time analysis. Then, we present the run time of our approach. Our approach
requires training $n$ networks, one for each random subset. We find that using
$n\leq 20T$ samples suffice for estimating the task affinity scores to
convergence. In contrast, previous methods (standley2020tasks, 110, 115)
estimate task affinities for every pair of tasks, resulting in training on
$O(T^{2})$ task pairs. Concretely, we report the run time of our approach in
Figure 6, evaluated on a single NVIDIA RTX GPU. Compared with the two previous
methods, our approach requires 3.7$\times$ less running time, averaged over
the four data sets.

Speed up training. In practice, we can further speed up training with early
stopping and downsampling. Our experiments found that this leads to a
significant speed-up, and the overhead on top of Naive MTL is only up to
2-3$\times$. In Table 5 of Appendix B.3, we report the running time of our
approach by incorporating the speed-up methods, as compared with all MTL
baselines.

###  5.2. Results for overlapped community detection

Baselines. We compare our approach with three classes of baseline approaches,
which are selected to be representative in terms of relative improvement. The
first class of methods is a set of popular methods for community detection,
including:

  * •

BigClam (yang2013overlapping, 85).

  * •

Louvain clustering (blondel2008fast, 77).

  * •

Network embedding methods including Node2Vec (grover2016node2vec, 88) and
VERSE (tsitsulin2018verse, 95). We use a logistic regression classifier on the
node embedding for each community.

  * •

GNN-based community detection methods including MinCutPool
(bianchi2020spectral, 102) and Deep Modularity Networks (tsitsulin2023graph,
132).

Second, we consider two baseline methods that optimize all tasks using a
shared model:

  * •

Naive MTL (caruana1997multitask, 67) trains all tasks jointly in a shared
model.

  * •

Mixture-of-Experts (ma2018modeling, 93) that trains multiple expert models on
all tasks and uses a gating network to combine model outputs for each task in
a weighted manner.

Third, we consider four task grouping baselines that find task groups and
train a network on each group.

  * •

Forward selection: Start from all empty groups. Enumerate all tasks, add the
task to each existing group, and assign it to the group, resulting in the best
average performance.

  * •

Backward selection: Start from a group with all tasks and other groups as
empty. Enumerate all tasks in the first group, combine the task with the rest
groups, and assign the task to the group resulting in the best average
performance.

  * •

First-order task affinity that evaluates the effect of one task’s gradients on
another task’s loss (fifty2021efficiently, 115).

  * •

Averaging the first-order task affinity scores to approximate higher-order
task affinities (standley2020tasks, 110).

We note that (fifty2021efficiently, 115) and (standley2020tasks, 110) use a
branch-and-bound algorithm to search for task groups but do not scale to one
hundred tasks for the data sets. We use their task affinity scores to compare
these two methods but apply the spectral clustering procedure to find task
groups.

Implementations. We use a 3-layer SIGN model as the encoder for all MTL
approaches, with a width of 256 neurons. We use the VERSE embedding as the
input node features. We compare approaches for splitting tasks into $b=20$
groups. We use the same amount of model parameters for other MTL baselines. In
the evaluation, we report the macro F1-score of predicted communities to
ground-truth community labels on the test set.

For our approach, we set the size of the subset as $\alpha=10$ and the number
of samples as $n=2000$. We ablate the two parameters in Section 5.4 and find
that the performance of our approach remains stable while varying them. We set
the MTL performance metric $f_{i}(S)$ as the (negative) cross-entropy loss on
the validation set. We apply the spectral clustering algorithm in
(ng2001spectral, 70, 68) to find task groups on the symmetric adjacency matrix
constructed from task affinity scores.

Table 1. Macro F1-score of community detection tasks on four social networks. We compare our approach with graph embedding, MTL optimization, and feature subset selection methods. We report the averaged result for each experiment over three random seeds, including the standard deviations. Dataset | Amazon | Youtube | DBLP | LiveJournal
---|---|---|---|---
Nodes | 3,225 | 16,751 | 57,368 | 18,433
Edges | 20,524 | 104,513 | 420,122 | 1,397,580
BigClam |  27.30 $\pm$ 0.26 |  18.84 $\pm$ 0.18 |  13.46 $\pm$ 0.11 |  22.50 $\pm$ 0.31
Louvain clustering |  60.95 $\pm$ 0.19 |  29.03 $\pm$ 0.34 |  36.73 $\pm$ 0.34 |  64.08 $\pm$ 0.17
Node2Vec |  39.05 $\pm$ 0.10 |  32.44 $\pm$ 0.18 |  28.72 $\pm$ 0.10 |  50.40 $\pm$ 0.29
VERSE |  61.00 $\pm$ 0.32 |  38.17 $\pm$ 0.12 |  53.48 $\pm$ 0.24 |  58.71 $\pm$ 0.48
Naive MTL |  87.08 $\pm$ 4.04 |  43.42 $\pm$ 2.24 |  67.95 $\pm$ 2.28 |  82.56 $\pm$ 3.21
Multi-Gate MoE |  88.92 $\pm$ 6.65 |  44.65 $\pm$ 4.28 |  68.83 $\pm$ 4.06 |  83.08 $\pm$ 4.89
Forward Select |  90.45 $\pm$ 3.63 |  47.62 $\pm$ 2.84 |  68.58 $\pm$ 2.96 |  86.19 $\pm$ 2.61
Backward Select |  90.41 $\pm$ 5.98 |  47.68 $\pm$ 3.01 |  68.63 $\pm$ 2.97 |  85.91 $\pm$ 4.18
Alg. 1 (Ours) | 92.66 $\pm$ 4.85 | 49.62 $\pm$ 2.26 | 70.68 $\pm$ 2.65 | 88.43 $\pm$ 2.70

Table 2. Test performance on multitask molecular graph prediction datasets. We compare our approach with MTL optimization methods and feature subset selection methods. We report the averaged result over three random seeds, including the standard deviations. Dataset | QM9 | Alchemy | OGB-molpcba
---|---|---|---
Metric |  MAE ($\downarrow$) |  MAE ($\downarrow$) |  AP ($\uparrow$)
Graphs | 129,433 | 202,579 | 437,929
Nodes per graph | 18.0 | 10.1 | 26.0
Edges per graph | 18.6 | 10.4 | 28.1
Tasks | 12 | 12 | 128
Groups | 3 | 3 | 20
Naive MTL |  0.081 $\pm$ 0.003 |  0.103 $\pm$ 0.001 |  27.03 $\pm$ 0.23
Multi-Gate MoE |  0.079 $\pm$ 0.003 |  0.100 $\pm$ 0.001 |  28.38 $\pm$ 0.34
Forward Select |  0.077 $\pm$ 0.002 |  0.099 $\pm$ 0.001 |  28.72 $\pm$ 0.21
Backward Select |  0.073 $\pm$ 0.002 |  0.095 $\pm$ 0.004 |  28.50 $\pm$ 0.16
Alg. 1 (Ours) | 0.067 $\pm$ 0.003 | 0.090 $\pm$ 0.001 | 29.73 $\pm$ 0.12

Results. Table 2 reports the evaluation of four social networks with ground-
truth community labels. First, we find that VERSE embedding achieves the best
performance among all the node embedding methods. Thus, we use the VERSE
embedding as a node feature for conducting MTL on graph neural networks. Due
to the space constraint, we report the results of other community detection
methods in Appendix B.4.

  * •

Benefit of task grouping: Compared with methods that optimize a joint model on
all tasks, task grouping consistently performs better than the naive MTL and
Mixture of Experts. Our approach outperforms them by 3.98% on average.

  * •

Benefit of modeling higher-order relationships: Compared with forward and
backward selection, our approach achieves an average improvement of 2.18% over
the datasets. Moreover, we compare our approach with clustering by two first-
order task affinities. The results show that our approach outperforms them by
2.49% on average. This validates the advantage of using higher-order task
affinities over first-order task affinities. The results are shown in Table 6
of Appendix B.4.

###  5.3. Results for molecular graph prediction

Next, we apply our approach to molecular graph prediction tasks, including two
multi-task regression data sets from TUDatasets (morris2020tudataset, 108) and
one multi-task classification dataset from OGB (hu2020open, 106). In the
graphs, nodes represent 3D coordinates of atoms in molecules, and edges encode
distances between atoms. Each task corresponds to predicting a specific
molecular property. We use a 6-layer GIN model as the encoder, with a width of
64. We evaluate the mean absolute error (MAE) on the regression datasets and
the average precision (AP) on the classification dataset.

Table 2 compares our approach with MTL baselines, including naive MTL, Mixture
of Experts, and forward/backward selection. We find that on these three data
sets, our method still outperforms the baselines relatively by 4.6% on
average.

###  5.4. Ablation studies

Number of task groups $b$. We discuss how the number of task groups is
determined in our approach. We hypothesize that a larger number of task groups
gives greater flexibility and tends to have better performance. Ideally, we
can generate $T$ task groups, each for a particular target task, and select
helpful source tasks for the target task in each group. We validate the
hypothesis by varying the number of task groups between 5, 10, 20, and 100.
The results validate that more group achieves better performance.
Interestingly, we also find that using 20 groups achieves results comparable
to those of using 100 groups. Thus, we set $b=20$ in our experiments. The
details are reported in Appendix B.5.

Subset size $\alpha$. Recall that we collect MTL prediction losses through
sampling random subsets of a size $\alpha$. We evaluate the performance of our
approach by varying the size $\alpha\in\\{5,10,20\\}$. First, we observe
similar convergence results using different sizes, as shown in Figure 5. Next,
we apply algorithm 1 with different values of $\alpha$. We notice that the
performances are comparable. Using $\alpha=10$ achieves slightly better
performance than the other two. We posit that using a larger $\alpha$ does not
help because the number of related tasks in our community detection data sets
is limited.

Number of samples $n$. We further explore how $n$ affects the algorithm
results. Our observation in Figure 5 is that collecting $n=20T$ is sufficient
for task affinity scores to converge. Meanwhile, using a smaller $n$ can also
achieve near 80% F1-score for predicting negative transfers. Thus, we test the
performance of algorithm 1 by varying $n\in\\{1000,1500,2000\\}$. We observe
that using $n=1000$ still achieves comparable performance as using $n=2000$.
The performance difference is within 0.5%.

##  6\. Theoretical Analysis

In this section, we aim to develop a principled understanding of our higher-
order affinity scores $[\theta_{i,j}]_{T\times T}$. To this end, we study a
planted model in a theoretical setup, where the tasks are assumed to follow a
block structure. We note that planted models have been widely used to study
graph clustering (abbe2017community, 89). In this setting, we ask:

  * •

Do our affinity scores provably capture higher-order task relationships?

  * •

Could the affinity scores be used to successfully separate related tasks from
each block?

We provide a positive answer to both questions in a theoretical setup, where
the labels of each task have been drawn from a linear model. Our finding is
that for two tasks from the same group in the planted model, their affinity
scores will be provably higher than two tasks from different groups. To
describe this result, we first formally introduce the setup.

Setup. Suppose we are learning $T$ tasks. For each task, $i$ from $1$ up to
$T$, let the node labels of this task be given by a vector $\tilde{Y}^{(i)}$,
all of which are observed on a set of nodes denoted as $\tilde{X}$. Let $m$
denote the size of the observed set of nodes. We focus on regression tasks in
the analysis. Thus, the values of $\tilde{Y}^{(i)}$ are all real values. To
further simplify the analysis, we consider a one-layer linear graph diffusion
layer as $f(X,G)=P_{{}_{G}}X$, where $P_{{}_{G}}$ (e.g., the normalized graph
Laplacian matrix) denotes the diffusion matrix of the graph neural network,
and $X$ denotes the matrix of node features. We assume that $X$ is drawn from
an isotropic Gaussian distribution, and $P_{{}_{G}}$ is full rank. We measure
the loss of this GNN against the label vector $\tilde{Y}^{(i)}$ using the Mean
Squared Error (MSE):

(4)
$\displaystyle\ell_{i}(W)=\frac{1}{m}\left\|\tilde{P}_{{}_{G}}\tilde{X}W-\tilde{Y}^{(i)}\right\|_{2}^{2}.$

where $\tilde{P}_{{}_{G}}$ denotes the propagation matrix restricted to the
set of nodes in $\tilde{X}$. Based on our algorithm, we first show that the
relevance score $\theta_{i,j}$ admits a structure that measures the distance
between $\tilde{Y}^{(i)}$ and $\tilde{Y}^{(j)}$. When we sample a set of tasks
$S\subseteq\\{1,2,\dots,T\\}$ with a total of $\alpha$ tasks, then we average
their per-task losses as

(5) $\displaystyle\ell_{S}(W)=\frac{1}{\alpha}\sum_{i\in S}\ell_{i}(W).$

Notations. We follow the convention of big-O notations for stating the result.
Given two functions $h(n)$ and $h^{\prime}(n)$, we use
$h(n)=\textup{O}(h^{\prime}(n))$ or $h(n)\lesssim h^{\prime}(n)$ to indicate
that $h(n)\leq C\cdot h^{\prime}(n)$ for some fixed constant $C$ when $n$ is
large enough.

Characterization of affinity scores. Minimizing equation (4) over $W$ leads to
a closed form solution on $W$—let us denote this as $\hat{W}_{S}$, which we
can then plug into task $i$’s loss $\ell_{i}(\hat{W}_{S})$. We then average
the value of $\ell_{i}(\hat{W}_{S})$ for subsets $S_{1},S_{2},\dots,S_{n}$
that include $j$ as part of the subset. This gives the relevance score
$\theta_{i,j}$:

(6) $\displaystyle\theta_{i,j}=\frac{1}{n_{i,j}}\sum_{1\leq k\leq
n:\,\\{i,j\\}\subseteq S_{k}}\ell_{i}\big{(}\hat{W}_{S_{k}}\big{)}.$

In the following result, we derive an explicit form of the score
$\theta_{i,j}$. For any matrix $A\in{}^{m\times n}$, let $A^{\dagger}$ be its
Moore-Penrose inverse.

###### Lemma 6.1.

In the setting described above, let the projection matrix $\tilde{\Sigma}$ be
given by
$\tilde{\Sigma}=\tilde{P}_{{}_{G}}\tilde{X}\big{(}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}\big{)}^{\dagger}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}$.
For any $1\leq i,j\leq T$, we have that the relevance score $\theta_{i,j}$ is
equal to

(7) $\displaystyle\theta_{i,j}=\frac{1}{n_{i,j}\cdot m}\sum_{1\leq k\leq
n:\,\\{i,j\\}\subseteq
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2}.$

###### Proof of Lemma 6.1.

From equation (5), $\hat{W}_{S}$ is the quadratic minimization of $L_{S}(W)$,
expressed as

$\displaystyle\hat{W}_{S}=\Big{(}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}\Big{)}^{\dagger}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\Bigg{(}\frac{1}{\alpha}\sum_{i\in
S}\tilde{Y}^{(i)}\Bigg{)}.$

We have that for any subset $S\subseteq\\{1,2,\dots,k\\}$,

(8)
$\displaystyle\ell_{i}(\hat{W}_{S})=\frac{1}{m}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2}.$

and for any $1\leq i,j\leq n$, by definition (cf. equation (1))

(9) $\displaystyle\theta_{i,j}$ $\displaystyle=\frac{1}{n_{i,j}\cdot
m}\sum_{1\leq k\leq n:\,\\{i,j\\}\subseteq
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2}$

Hence, the proof of equation (7) is completed. ∎

Block structure of affinity scores. Next, we show that under a separation
condition between the label vectors $Y^{(1)},Y^{(2)},\dots,Y^{(T)}$, our
algorithm can be used to separate the tasks into separated groups provably.
More precisely, let
$\Sigma=P_{{}_{G}}X(X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X)^{\dagger}X^{\top}P_{{}_{G}}^{\top}$.

###### Assumption 6.2.

Suppose that the label vectors can be separated into $C$ groups such that:

  * •

For any two different $i$ and $j$ within each group,

$\left\|\Sigma\Big{(}Y^{(i)}-Y^{(j)}\Big{)}\right\|_{2}\leq a.$

  * •

For any two different $i^{\prime}$ and $j^{\prime}$ from different groups,

$\left\|\Sigma\Big{(}Y^{(i^{\prime})}-Y^{(j^{\prime})}\Big{)}\right\|_{2}\geq
b.$

Now we are ready to state a structural characterization on the affinity scores
$[\theta_{i,j}]_{T\times T}$.

###### Theorem 6.3.

Suppose the features and the label vectors of every task are given based on
the setup specified within this section and satisfy Assumption 6.2. Assume
that the propagation matrix $P_{{}_{G}}$ is full rank. Let $\epsilon$ be a
fixed constant that does not grow with $n$ and $m$, and $\delta$ be a value
that is less than one.

When $m=O\big{(}d^{2}\log^{4}d\log^{2}(T\delta^{-1})\varepsilon^{-2}\big{)}$,
$n=O\big{(}\log(T\delta^{-1})\varepsilon^{-2}\big{)}$, and $b^{2}-a^{2}\geq
O\big{(}d^{4}\log^{8}d\log^{4}(T\delta^{-1})\varepsilon^{-4}\big{)}$, then
with probability at least $1-\delta$ over the randomness of the training
samples, the affinity scores $[\theta_{i,j}]_{T\times T}$ satisfy the
following block structure: For any $1\leq i,j,k\leq T$ such that $i,j$ come
from the same group, but $i,j^{\prime}$ come from different groups, then

(10)
$\displaystyle\theta_{i,j^{\prime}}-\theta_{i,j}\geq\frac{\varepsilon}{2}.$

Our result characterizes the block structure of the affinity scores. The
affinity scores are lower within the block of nodes from the same community.
Conversely, the affinity scores would be higher for any pair of nodes that
cross two communities. Based on this characterization, it is clear that by
applying a spectral clustering algorithm over $[\theta_{i,j}]_{T\times T}$,
one could recover the group structures specified under Assumption 6.2. For
future work, it would be interesting to strengthen our analysis with relaxed
assumptions further and extend it to more general losses and planted models.
The complete proof can be found in Appendix A.

##  7\. Conclusion

This paper studied multitask learning on graphs and designed a generic
boosting procedure that improves MTL by finding related tasks and training
them in groups. We first estimate higher-order task affinities by sampling
random task subsets and evaluating multitask performances. Then, we find task
groups by clustering task affinity scores. Experiments show that our higher-
order task affinity scores predict negative transfers from multiple tasks to
one task. Our approach improves over previous MTL methods on various community
detection data sets. The theoretical analysis further demonstrates that using
our task affinity scores provably separates related and unrelated tasks.

Our work opens up interesting questions for future work. For example, can we
incorporate various node or link prediction tasks to enhance community
detection in multitask learning? Can we apply recent developments in
correlation clustering (mandaglio2021correlation, 117, 123) to determine the
number of clusters?

Acknowledgement. Thanks to the anonymous referees for providing constructive
feedback that improved our work significantly. Thanks to Ruoxuan Xiong,
Xiaojie Mao, and Yi Liu for fruitful discussions during various stages of this
work. D. L. is supported by a start-up fund from Khoury College of Computer
Sciences, Northeastern University.

[sorting=nyt]

## References

  * (1) Emmanuel Abbe  “Community detection and stochastic block models: recent developments”  In _Journal of Machine Learning Research_ , 2017
  * (2) Nir Ailon, Moses Charikar and Alantha Newman  “Aggregating inconsistent information: ranking and clustering”  In _JACM_ , 2008
  * (3) Reid Andersen and Kevin J Lang  “Communities from seed sets”  In _World Wide Web_ , 2006
  * (4) Guangji Bai and Liang Zhao  “Saliency-Regularized Deep Multi-Task Learning”  In _KDD_ , 2022
  * (5) Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira and Jennifer Wortman Vaughan  “A theory of learning from different domains”  In _Machine learning_ , 2010
  * (6) Shai Ben-David, Johannes Gehrke and Reba Schuller  “A theoretical framework for learning from a pool of disparate data sources”  In _KDD_ , 2002
  * (7) Shai Ben-David and Reba Schuller  “Exploiting task relatedness for multiple task learning”  In _Learning Theory and Kernel Machines_ , 2003, pp. 567–580  Springer
  * (8) Austin R Benson, David F Gleich and Jure Leskovec  “Higher-order organization of complex networks”  In _Science_ , 2016
  * (9) Filippo Maria Bianchi, Daniele Grattarola and Cesare Alippi  “Spectral clustering with graph neural networks for graph pooling”  In _ICML_ , 2020  PMLR
  * (10) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte and Etienne Lefebvre  “Fast unfolding of communities in large networks”  In _Journal of statistical mechanics: theory and experiment_ , 2008
  * (11) Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik and Stephan Günnemann  “Scaling graph neural networks with approximate pagerank”  In _KDD_ , 2020
  * (12) Francesco Bonchi, David Garcia-Soriano and Francesco Gullo  “Correlation clustering”  In _Synthesis Lectures on Data Mining and Knowledge Discovery_ , 2022
  * (13) Leo Breiman  “Random forests”  In _Machine Learning_ , 2001
  * (14) Rich Caruana  “Multitask learning”  In _Machine learning_ , 1997
  * (15) Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du and Ji-Rong Wen  “Scalable graph neural networks via bidirectional propagation”  In _NeurIPS_ , 2020
  * (16) Zhengdao Chen, Xiang Li and Joan Bruna  “Supervised community detection with line graph neural networks”  In _ICLR_ , 2019
  * (17) Koby Crammer, Michael Kearns and Jennifer Wortman  “Learning from Multiple Sources.”  In _Journal of Machine Learning Research_ , 2008
  * (18) Erik D Demaine, Dotan Emanuel, Amos Fiat and Nicole Immorlica  “Correlation clustering in general weighted graphs”  In _Theoretical Computer Science_ , 2006
  * (19) Theodoros Evgeniou and Massimiliano Pontil  “Regularized multi-task learning”  In _KDD_ , 2004
  * (20) Chris Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil and Chelsea Finn  “Efficiently identifying task groupings for multi-task learning”  In _NeurIPS_ , 2021
  * (21) Santo Fortunato  “Community detection in graphs”  In _Physics Reports_ , 2010
  * (22) Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein and Federico Monti  “Sign: Scalable inception graph neural networks”  In _arXiv preprint arXiv:2004.11198_ , 2020
  * (23) Ashish Goel, Sanjeev Khanna, Sharath Raghvendra and Hongyang Zhang  “Connectivity in random forests and credit networks”  In _SODA_ , 2014
  * (24) Ke Gong, Yiming Gao, Xiaodan Liang, Xiaohui Shen, Meng Wang and Liang Lin  “Graphonomy: Universal human parsing via graph transfer learning”  In _CVPR_ , 2019
  * (25) Andrey Gritsenko, Kimia Shayestehfard, Yuan Guo, Armin Moharrer, Jennifer Dy and Stratis Ioannidis  “Graph transfer learning”  In _Knowledge and Information Systems_ , 2022
  * (26) Aditya Grover and Jure Leskovec  “node2vec: Scalable feature learning for networks”  In _KDD_ , 2016
  * (27) 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 _NeurIPS_ , 2020
  * (28) Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande and Jure Leskovec  “Strategies for pre-training graph neural networks”  In _ICLR_ , 2020
  * (29) Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc and Aleksander Madry  “Datamodels: Predicting predictions from training data”  In _ICML_ , 2022
  * (30) Haotian Ju, Dongyue Li, Aneesh Sharma and Hongyang R Zhang  “Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion”  In _AISTATS_ , 2023
  * (31) Haotian Ju, Dongyue Li and Hongyang R Zhang  “Robust fine-tuning of deep neural networks with hessian-based generalization guarantees”  In _ICML_ , 2022
  * (32) Johannes Klicpera, Aleksandar Bojchevski and Stephan Günnemann  “Predict then propagate: Graph neural networks meet personalized pagerank”  In _ICLR_ , 2019
  * (33) Abhishek Kumar and Hal Daume III  “Learning task grouping and overlap in multi-task learning”  In _ICML_ , 2012
  * (34) Jaekoo Lee, Hyunjae Kim, Jongsun Lee and Sungroh Yoon  “Transfer learning for deep learning on graph-structured data”  In _AAAI_ , 2017
  * (35) Dongyue Li, Huy Nguyen and Hongyang Ryan Zhang  “Task Modeling: Approximating Multitask Predictions for Cross-Task Transfer”  In _NeurIPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications_ , 2022
  * (36) Dongyue Li, Huy L Nguyen and Hongyang R Zhang  “Identification of Negative Transfers in Multitask Learning Using Surrogate Models”  In _Trans. Mach. Learn. Res._ , 2023
  * (37) Dongyue Li and Hongyang R. Zhang  “Improved regularization and robustness for fine-tuning in neural networks”  In _NeurIPS_ , 2021
  * (38) Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong and Ed H Chi  “Modeling task relationships in multi-task learning with multi-gate mixture-of-experts”  In _KDD_ , 2018
  * (39) Domenico Mandaglio, Andrea Tagarelli and Francesco Gullo  “Correlation clustering with global weight bounds”  In _ECML PKDD_ , 2021
  * (40) Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel and Marion Neumann  “Tudataset: A collection of benchmark datasets for learning with graphs”  In _ICML GRL+ workshop_ , 2020
  * (41) Andrew Ng, Michael Jordan and Yair Weiss  “On spectral clustering: Analysis and an algorithm”  In _Advances in neural information processing systems_ 14, 2001
  * (42) Feiping Nie, Zhanxuan Hu and Xuelong Li  “Calibrated multi-task learning”  In _KDD_ , 2018
  * (43) Sinno Jialin Pan and Qiang Yang  “A survey on transfer learning”  In _TKDE_ , 2010
  * (44) Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang and Jie Tang  “Gcc: Graph contrastive coding for graph neural network pre-training”  In _KDD_ , 2020
  * (45) Jianbo Shi and Jitendra Malik  “Normalized cuts and image segmentation”  In _IEEE Transactions on pattern analysis and machine intelligence_ Ieee, 2000
  * (46) Trevor Standley, Amir Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik and Silvio Savarese  “Which tasks should be learned together in multi-task learning?”  In _ICML_ , 2020
  * (47) Anton Tsitsulin, Davide Mottin, Panagiotis Karras and Emmanuel Müller  “Verse: Versatile graph embeddings from similarity measures”  In _WWW_ , 2018
  * (48) Anton Tsitsulin, John Palowitch, Bryan Perozzi and Emanuel Müller  “Graph Clustering with Graph Neural Networks”  In _JMLR_ , 2023
  * (49) Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell and Charles Blundell  “The CLRS algorithmic reasoning benchmark”  In _ICML_ , 2022
  * (50) Saurabh Verma and Zhi-Li Zhang  “Learning universal graph neural network embeddings with aid of transfer learning”  In _arXiv preprint arXiv:1909.10086_ , 2019
  * (51) Tu Vu, Tong Wang, Tsendsuren Munkhdalai, Alessandro Sordoni, Adam Trischler, Andrew Mattarella-Micke, Subhransu Maji and Mohit Iyyer  “Exploring and predicting transferability across NLP tasks”  In _EMNLP_ , 2020
  * (52) Hongwei Wang, Fuzheng Zhang, Miao Zhao, Wenjie Li, Xing Xie and Minyi Guo  “Multi-task feature learning for knowledge graph enhanced recommendation”  In _World Wide Web_ , 2019
  * (53) Yuyan Wang, Xuezhi Wang, Alex Beutel, Flavien Prost, Jilin Chen and Ed H Chi  “Understanding and improving fairness-accuracy trade-offs in multi-task learning”  In _KDD_ , 2021
  * (54) Joyce Jiyoung Whang, David F Gleich and Inderjit S Dhillon  “Overlapping community detection using seed set expansion”  In _CIKM_ , 2013
  * (55) Sen Wu, Hongyang Zhang, Gregory Valiant and Christopher Ré  “On the generalization effects of linear transformations in data augmentation”  In _ICML_ , 2020
  * (56) Sen Wu, Hongyang R Zhang and Christopher Ré  “Understanding and improving information transfer in multi-task learning”  In _ICLR_ , 2020
  * (57) Fan Yang, Hongyang R Zhang, Sen Wu, Weijie J Su and Christopher Ré  “Analysis of information transfer from heterogeneous sources via precise high-dimensional asymptotics”  In _arXiv preprint arXiv:2010.11750_ , 2021
  * (58) Jaewon Yang and Jure Leskovec  “Defining and evaluating network communities based on ground-truth”  In _KDD Workshop on Mining Data Semantics_ , 2012
  * (59) Jaewon Yang and Jure Leskovec  “Overlapping community detection at scale: a nonnegative matrix factorization approach”  In _WSDM_ , 2013
  * (60) Yongxin Yang and Timothy Hospedales  “Deep multi-task representation learning: A tensor factorisation approach”  In _ICLR_ , 2017
  * (61) Hao Yin, Austin R Benson, Jure Leskovec and David F Gleich  “Local higher-order graph clustering”  In _KDD_ , 2017
  * (62) Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman and Chelsea Finn  “Gradient surgery for multi-task learning”  In _NeurIPS_ , 2020
  * (63) Hongyang Zhang, Huacheng Yu and Ashish Goel  “Pruning based distance sketches with provable guarantees on random graphs”  In _The World Wide Web Conference_ , 2019
  * (64) Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang and Bin Cui  “Graph attention multi-layer perceptron”  In _KDD_ , 2022
  * (65) Yu Zhang and Qiang Yang  “A survey on multi-task learning”  In _IEEE Transactions on Knowledge and Data Engineering_ , 2021
  * (66) Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang and Jiawei Han  “Transfer learning of graph neural networks with ego-graph information maximization”  In _NeurIPS_ , 2021

## References

  * (1) Rich Caruana  “Multitask learning”  In _Machine learning_ , 1997
  * (2) Jianbo Shi and Jitendra Malik  “Normalized cuts and image segmentation”  In _IEEE Transactions on pattern analysis and machine intelligence_ Ieee, 2000
  * (3) Leo Breiman  “Random forests”  In _Machine Learning_ , 2001
  * (4) Andrew Ng, Michael Jordan and Yair Weiss  “On spectral clustering: Analysis and an algorithm”  In _Advances in neural information processing systems_ 14, 2001
  * (5) Shai Ben-David, Johannes Gehrke and Reba Schuller  “A theoretical framework for learning from a pool of disparate data sources”  In _KDD_ , 2002
  * (6) Shai Ben-David and Reba Schuller  “Exploiting task relatedness for multiple task learning”  In _Learning Theory and Kernel Machines_ , 2003, pp. 567–580  Springer
  * (7) Theodoros Evgeniou and Massimiliano Pontil  “Regularized multi-task learning”  In _KDD_ , 2004
  * (8) Reid Andersen and Kevin J Lang  “Communities from seed sets”  In _World Wide Web_ , 2006
  * (9) Erik D Demaine, Dotan Emanuel, Amos Fiat and Nicole Immorlica  “Correlation clustering in general weighted graphs”  In _Theoretical Computer Science_ , 2006
  * (10) Nir Ailon, Moses Charikar and Alantha Newman  “Aggregating inconsistent information: ranking and clustering”  In _JACM_ , 2008
  * (11) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte and Etienne Lefebvre  “Fast unfolding of communities in large networks”  In _Journal of statistical mechanics: theory and experiment_ , 2008
  * (12) Koby Crammer, Michael Kearns and Jennifer Wortman  “Learning from Multiple Sources.”  In _Journal of Machine Learning Research_ , 2008
  * (13) Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira and Jennifer Wortman Vaughan  “A theory of learning from different domains”  In _Machine learning_ , 2010
  * (14) Santo Fortunato  “Community detection in graphs”  In _Physics Reports_ , 2010
  * (15) Sinno Jialin Pan and Qiang Yang  “A survey on transfer learning”  In _TKDE_ , 2010
  * (16) Abhishek Kumar and Hal Daume III  “Learning task grouping and overlap in multi-task learning”  In _ICML_ , 2012
  * (17) Jaewon Yang and Jure Leskovec  “Defining and evaluating network communities based on ground-truth”  In _KDD Workshop on Mining Data Semantics_ , 2012
  * (18) Joyce Jiyoung Whang, David F Gleich and Inderjit S Dhillon  “Overlapping community detection using seed set expansion”  In _CIKM_ , 2013
  * (19) Jaewon Yang and Jure Leskovec  “Overlapping community detection at scale: a nonnegative matrix factorization approach”  In _WSDM_ , 2013
  * (20) Ashish Goel, Sanjeev Khanna, Sharath Raghvendra and Hongyang Zhang  “Connectivity in random forests and credit networks”  In _SODA_ , 2014
  * (21) Austin R Benson, David F Gleich and Jure Leskovec  “Higher-order organization of complex networks”  In _Science_ , 2016
  * (22) Aditya Grover and Jure Leskovec  “node2vec: Scalable feature learning for networks”  In _KDD_ , 2016
  * (23) Emmanuel Abbe  “Community detection and stochastic block models: recent developments”  In _Journal of Machine Learning Research_ , 2017
  * (24) Jaekoo Lee, Hyunjae Kim, Jongsun Lee and Sungroh Yoon  “Transfer learning for deep learning on graph-structured data”  In _AAAI_ , 2017
  * (25) Yongxin Yang and Timothy Hospedales  “Deep multi-task representation learning: A tensor factorisation approach”  In _ICLR_ , 2017
  * (26) Hao Yin, Austin R Benson, Jure Leskovec and David F Gleich  “Local higher-order graph clustering”  In _KDD_ , 2017
  * (27) Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong and Ed H Chi  “Modeling task relationships in multi-task learning with multi-gate mixture-of-experts”  In _KDD_ , 2018
  * (28) Feiping Nie, Zhanxuan Hu and Xuelong Li  “Calibrated multi-task learning”  In _KDD_ , 2018
  * (29) Anton Tsitsulin, Davide Mottin, Panagiotis Karras and Emmanuel Müller  “Verse: Versatile graph embeddings from similarity measures”  In _WWW_ , 2018
  * (30) Zhengdao Chen, Xiang Li and Joan Bruna  “Supervised community detection with line graph neural networks”  In _ICLR_ , 2019
  * (31) Ke Gong, Yiming Gao, Xiaodan Liang, Xiaohui Shen, Meng Wang and Liang Lin  “Graphonomy: Universal human parsing via graph transfer learning”  In _CVPR_ , 2019
  * (32) Johannes Klicpera, Aleksandar Bojchevski and Stephan Günnemann  “Predict then propagate: Graph neural networks meet personalized pagerank”  In _ICLR_ , 2019
  * (33) Saurabh Verma and Zhi-Li Zhang  “Learning universal graph neural network embeddings with aid of transfer learning”  In _arXiv preprint arXiv:1909.10086_ , 2019
  * (34) Hongwei Wang, Fuzheng Zhang, Miao Zhao, Wenjie Li, Xing Xie and Minyi Guo  “Multi-task feature learning for knowledge graph enhanced recommendation”  In _World Wide Web_ , 2019
  * (35) Hongyang Zhang, Huacheng Yu and Ashish Goel  “Pruning based distance sketches with provable guarantees on random graphs”  In _The World Wide Web Conference_ , 2019
  * (36) Filippo Maria Bianchi, Daniele Grattarola and Cesare Alippi  “Spectral clustering with graph neural networks for graph pooling”  In _ICML_ , 2020  PMLR
  * (37) Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik and Stephan Günnemann  “Scaling graph neural networks with approximate pagerank”  In _KDD_ , 2020
  * (38) Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du and Ji-Rong Wen  “Scalable graph neural networks via bidirectional propagation”  In _NeurIPS_ , 2020
  * (39) Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein and Federico Monti  “Sign: Scalable inception graph neural networks”  In _arXiv preprint arXiv:2004.11198_ , 2020
  * (40) 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 _NeurIPS_ , 2020
  * (41) Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande and Jure Leskovec  “Strategies for pre-training graph neural networks”  In _ICLR_ , 2020
  * (42) Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel and Marion Neumann  “Tudataset: A collection of benchmark datasets for learning with graphs”  In _ICML GRL+ workshop_ , 2020
  * (43) Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang and Jie Tang  “Gcc: Graph contrastive coding for graph neural network pre-training”  In _KDD_ , 2020
  * (44) Trevor Standley, Amir Zamir, Dawn Chen, Leonidas Guibas, Jitendra Malik and Silvio Savarese  “Which tasks should be learned together in multi-task learning?”  In _ICML_ , 2020
  * (45) Tu Vu, Tong Wang, Tsendsuren Munkhdalai, Alessandro Sordoni, Adam Trischler, Andrew Mattarella-Micke, Subhransu Maji and Mohit Iyyer  “Exploring and predicting transferability across NLP tasks”  In _EMNLP_ , 2020
  * (46) Sen Wu, Hongyang Zhang, Gregory Valiant and Christopher Ré  “On the generalization effects of linear transformations in data augmentation”  In _ICML_ , 2020
  * (47) Sen Wu, Hongyang R Zhang and Christopher Ré  “Understanding and improving information transfer in multi-task learning”  In _ICLR_ , 2020
  * (48) Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman and Chelsea Finn  “Gradient surgery for multi-task learning”  In _NeurIPS_ , 2020
  * (49) Chris Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil and Chelsea Finn  “Efficiently identifying task groupings for multi-task learning”  In _NeurIPS_ , 2021
  * (50) Dongyue Li and Hongyang R. Zhang  “Improved regularization and robustness for fine-tuning in neural networks”  In _NeurIPS_ , 2021
  * (51) Domenico Mandaglio, Andrea Tagarelli and Francesco Gullo  “Correlation clustering with global weight bounds”  In _ECML PKDD_ , 2021
  * (52) Yuyan Wang, Xuezhi Wang, Alex Beutel, Flavien Prost, Jilin Chen and Ed H Chi  “Understanding and improving fairness-accuracy trade-offs in multi-task learning”  In _KDD_ , 2021
  * (53) Fan Yang, Hongyang R Zhang, Sen Wu, Weijie J Su and Christopher Ré  “Analysis of information transfer from heterogeneous sources via precise high-dimensional asymptotics”  In _arXiv preprint arXiv:2010.11750_ , 2021
  * (54) Yu Zhang and Qiang Yang  “A survey on multi-task learning”  In _IEEE Transactions on Knowledge and Data Engineering_ , 2021
  * (55) Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang and Jiawei Han  “Transfer learning of graph neural networks with ego-graph information maximization”  In _NeurIPS_ , 2021
  * (56) Guangji Bai and Liang Zhao  “Saliency-Regularized Deep Multi-Task Learning”  In _KDD_ , 2022
  * (57) Francesco Bonchi, David Garcia-Soriano and Francesco Gullo  “Correlation clustering”  In _Synthesis Lectures on Data Mining and Knowledge Discovery_ , 2022
  * (58) Andrey Gritsenko, Kimia Shayestehfard, Yuan Guo, Armin Moharrer, Jennifer Dy and Stratis Ioannidis  “Graph transfer learning”  In _Knowledge and Information Systems_ , 2022
  * (59) Andrew Ilyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc and Aleksander Madry  “Datamodels: Predicting predictions from training data”  In _ICML_ , 2022
  * (60) Haotian Ju, Dongyue Li and Hongyang R Zhang  “Robust fine-tuning of deep neural networks with hessian-based generalization guarantees”  In _ICML_ , 2022
  * (61) Dongyue Li, Huy Nguyen and Hongyang Ryan Zhang  “Task Modeling: Approximating Multitask Predictions for Cross-Task Transfer”  In _NeurIPS 2022 Workshop on Distribution Shifts: Connecting Methods and Applications_ , 2022
  * (62) Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell and Charles Blundell  “The CLRS algorithmic reasoning benchmark”  In _ICML_ , 2022
  * (63) Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang and Bin Cui  “Graph attention multi-layer perceptron”  In _KDD_ , 2022
  * (64) Haotian Ju, Dongyue Li, Aneesh Sharma and Hongyang R Zhang  “Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion”  In _AISTATS_ , 2023
  * (65) Dongyue Li, Huy L Nguyen and Hongyang R Zhang  “Identification of Negative Transfers in Multitask Learning Using Surrogate Models”  In _Trans. Mach. Learn. Res._ , 2023
  * (66) Anton Tsitsulin, John Palowitch, Bryan Perozzi and Emanuel Müller  “Graph Clustering with Graph Neural Networks”  In _JMLR_ , 2023

##  Appendix A Proof of Theorem 6.3

Proof Sketch: The proof of Theorem 6.3 is by carefully examining the sampling
structures of our algorithm. A key insight is that $\theta_{i,j}$ measures the
relevance score of task $i$ to task $j$ while accounting for the presence of
other tasks besides $i$ and $j$. There are two steps in the proof. First, we
show that $\theta_{i,j}$ deviates from a population average that takes into
account all subsets of size $\alpha$ by an error of $O(n^{-1/2})$. This is
based on Hoeffding’s inequality. See equation (16) in Appendix A. Second,
since $\tilde{\Sigma}$ is a projection matrix based on equation (15), we have
that for any $i$ and $S_{k}$,

(11)
$\displaystyle\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2}=\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}-\tilde{Y}^{(i)}\Bigg{)}\right\|_{2}^{2}+\left\|\Big{(}\operatorname{Id}-\tilde{\Sigma}\Big{)}\cdot\tilde{Y}^{(i)}\right\|_{2}^{2}.$

Thus, for $\theta_{i,j^{\prime}}-\theta_{i,j}$, the second term from equation
(11) is canceled out. Then, we apply Assumption 6.2 to separate the first term
between $i,j$ and $i,j^{\prime}$. Our proof follows several previous works
that analyze information transfer in multitask learning (yang2020analysis,
119, 131).

Next, we argue that for any $i,j$, the following holds with probability
$1-\delta$.

###### Claim A.1.

In the setting of Theorem 6.3, we have that for any $1\leq i<j\leq T$:

(12)
$\displaystyle\left\|\frac{1}{m}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\Big{(}\tilde{Y}^{(i)}-\tilde{Y}^{(j)}\Big{)}-\frac{1}{N}X^{\top}P_{{}_{G}}^{\top}\Big{(}Y^{(i)}-Y^{(j)}\Big{)}\right\|_{2}\leq\frac{4B\sqrt{d}\log
d\left\|P_{{}_{G}}\right\|_{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}.$

###### Proof.

We use the matrix Bernstein inequality (cf. Theorem 6.1.1 in Tropp (2015))
here. Let the $i$-th column of $XP_{{}_{G}}$ be denoted as $u_{i}$. Thus, we
have $u_{i}^{\top}\Big{(}Y^{(i)}-Y^{(j)}\Big{)}\leq
2BN\left\|P_{{}_{G}}\right\|_{2}\sqrt{d}\log d$ For all $t\geq 0$, we have:

$\displaystyle\Pr\left[\left\|\frac{1}{m}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\Big{(}\tilde{Y}^{(i)}-\tilde{Y}^{(j)}\Big{)}-\frac{1}{N}X^{\top}P_{{}_{G}}^{\top}\Big{(}Y^{(i)}-Y^{(j)}\Big{)}\right\|_{2}\geq
t\right]\leq
2T^{2}\cdot\exp\left(-\frac{(mt)^{2}/2}{(2B\|P_{{}_{G}}\|_{{}_{2}}\sqrt{d}\log
d)^{2}m+(2B\|P_{{}_{G}}\|_{{}_{2}}\sqrt{d}\log d)mt/3}\right).$

∎

Recall we have assumed that $X$ is drawn from an isotropic Gaussian. Thus,
each row vector of $P_{{}_{G}}X$ follows a Gaussian distribution with a full-
rank covariance matrix since $P_{{}_{G}}$ is full rank. Thus, by Gaussian
concentration results, for a random subset of $m$ row vectors of
$P_{{}_{G}}X$, they must be invertible. Thus, we will next argue that under
the condition $m\geq d\log d$, with probability at least $1-\delta$, the
following holds.

###### Claim A.2.

In the setting of Theorem 6.3, provided that $m\geq d\log d$, with probability
at least $1-\delta$, we have that

(13)
$\displaystyle\left\|\Bigg{(}\frac{1}{m}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}\Bigg{)}^{-1}-\Bigg{(}\frac{1}{N}\frac{}{}X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X\Bigg{)}^{-1}\right\|_{2}\lesssim\frac{2\left\|P_{{}_{G}}\right\|_{2}\sqrt{d}\log
d\cdot\log(2T^{2}\delta^{-1})}{\sqrt{m}}.$

###### Proof.

We use the matrix Bernstein inequality (cf. Theorem 6.1.1 in Tropp (2015)) to
deal with the above spectral norm. Let the $i$-th column of
$X^{\top}P_{{}_{G}}^{\top}$ be denoted as $v_{i}$. Thus, we have that
$\|v_{i}\|\leq\left\|P_{{}_{G}}\right\|_{2}\cdot\sqrt{d}\log d$.

In expectation over the randomness of $\tilde{P}_{{}_{G}}\tilde{X}$, for all
$t\geq 0$, we have:

$\displaystyle\Pr\left[\left\|\frac{1}{m}\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}-\frac{1}{N}X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X\right\|_{2}\geq
t\right]\leq
2T^{2}\cdot\exp\left(-\frac{(mt)^{2}/2}{(\|P_{{}_{G}}\|_{{}_{2}}\sqrt{d}\log
d)^{2}m+(\|P_{{}_{G}}\|_{{}_{2}}\sqrt{d}\log d)mt/3}\right).$

With some standard calculations, this implies that for any $\delta\geq 0$,
with probability at least $1-\delta$, equation (13) holds.

Next, denote by

$E=\frac{\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}}{m}-\frac{X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X}{N}~{}~{}\text{
and }~{}~{}A=\frac{X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X}{N}.$

By the Sherman-Morrison formula calculating matrix inversions, we get

$\displaystyle\left\|\Big{(}\frac{\tilde{X}^{\top}\tilde{P}_{{}_{G}}^{\top}\tilde{P}_{{}_{G}}\tilde{X}}{m}\Big{)}^{-1}-\Big{(}\frac{X^{\top}P_{{}_{G}}^{\top}P_{{}_{G}}X}{N}\Big{)}^{-1}\right\|_{2}=\left\|(E+A)^{-1}-A^{-1}\right\|_{2}=$
$\displaystyle\left\|A^{-1}\Big{(}AE^{-1}+\operatorname{Id}_{T\times
T}\Big{)}^{-1}\right\|_{2}$ $\displaystyle=$
$\displaystyle\left\|A^{-1}E\Big{(}A+E\Big{)}^{-1}\right\|_{2}$
$\displaystyle\leq$
$\displaystyle\big{(}\lambda_{\min}(A)\big{)}^{-1}\cdot\|E\|_{2}\cdot\big{(}\lambda_{\min}(A+E)\big{)}^{-1}$
(14) $\displaystyle\leq$
$\displaystyle\frac{\|E\|_{2}}{\lambda_{\min}(A)(\lambda_{\min}(A)-\|E\|_{2})}.$

∎

Now we are ready to prove the main theorem.

###### Proof of Theorem 6.3.

There are two steps in the derivation of this theorem. First, we examine the
difference between equation (7) and the population average, given by:

(15) $\displaystyle\bar{\theta}_{i,j}=\frac{1}{A_{i,j}\cdot m}\sum_{1\leq
k\leq T:\,\\{i,j\\}\in
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2},$

where $T=\binom{T}{\alpha}$ is the total number of possible subsets of
$\\{1,2,\dots,T\\}$ that have a fixed size $\alpha$, and
$A_{i,j}=\binom{T-2}{\alpha-2}$ is the number of subsets of size $\alpha$ such
that $i,j$ are both in the subset. Thus,
$\mathop{\mathbb{E}}\left[\theta_{i,j}\right]=\bar{\theta}_{i,j}$. We will
first argue that the difference between $\theta_{i,j}$ and
$\bar{\theta}_{i,j}$. Let $B=\sup_{1\leq i\leq
k}\left\|Y^{(i)}\right\|_{\infty}$. We will show that for any $1\leq i,j\leq
T$, their difference satisfies:

(16)
$\displaystyle{\left|{\theta_{i,j}-\bar{\theta}_{i,j}}\right|}\leq{4B^{2}}\sqrt{\frac{\log(T/\delta)}{n}},$

by the Chernoff bound and the union bound.

Since $\tilde{\Sigma}^{2}=\tilde{\Sigma}$, the eigenvalues of $\tilde{\Sigma}$
only consist of some ones and zeros. For any subset $S_{k}$, We have

$\displaystyle\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}\Bigg{)}-\tilde{Y}^{(i)}\right\|_{2}^{2}$
$\displaystyle\leq\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\left\|\tilde{\Sigma}\cdot\tilde{Y}^{(l)}\right\|_{2}+\left\|\tilde{Y}^{(i)}\right\|_{2}\Bigg{)}^{2}$
$\displaystyle\leq$ $\displaystyle\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\left\|\tilde{Y}^{(l)}\right\|_{2}+\left\|\tilde{Y}^{(i)}\right\|_{2}\Bigg{)}^{2}\leq
4B^{2}m.$

By the Chernoff bound, with probability $1-2\delta$ and for any $i,j$ and $k$,
the gap between $\theta_{i,j}$ and $\bar{\theta}_{i,j}$ can be bounded as
follows:

(17)
$\displaystyle{\left|{\theta_{i,j}-\bar{\theta}_{i,j}}\right|}\leq{4B^{2}}\sqrt{\frac{\log(\delta^{-1})}{2n_{i,j}}}\leq
4B^{2}\sqrt{\frac{\log(\delta^{-1})}{2n}}.$

By union bound, with probability $1-2\binom{T}{2}\cdot\delta$, we have

(18)
$\displaystyle{\left|{\theta_{i,j}-\bar{\theta}_{i,j}}\right|}\leq{4B^{2}}\sqrt{\frac{\log(\delta^{-1})}{2n}}.$

Thus, the first step of proof has been completed.

In the second step, we want to compare $\theta_{i,j}$ with
$\theta_{i,j^{\prime}}$ where $i,j$ are from the same group, but
$i,j^{\prime}$ are from different groups. Based on equation (11), we have that

$\displaystyle\bar{\theta}_{i,j^{\prime}}-\bar{\theta}_{i,j}=\frac{1}{A_{i,j^{\prime}}\cdot
m}\sum_{1\leq k\leq T:\,\\{i,j^{\prime}\\}\subseteq
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}-\tilde{Y}^{(i)}\Bigg{)}\right\|_{2}^{2}-\frac{1}{A_{i,j}\cdot
m}\sum_{1\leq k\leq T:\,\\{i,j\\}\subseteq
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}-\tilde{Y}^{(i)}\Bigg{)}\right\|_{2}^{2}.$

Next, recall that $A_{i,j}=A_{i,j^{\prime}}=\binom{\alpha-2}{k-2}$. Thus, the
right-hand side of the above equation is equal to

(19)
$\displaystyle\bar{\theta}_{i,j^{\prime}}-\bar{\theta}_{i,j}=\frac{1}{A_{i,j}\cdot
m}\Bigg{(}$ $\displaystyle\sum_{1\leq k\leq T:\,\\{i,j^{\prime}\\}\subseteq
S_{k},j\notin
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}-\tilde{Y}^{(i)}\Bigg{)}\right\|_{2}^{2}-\sum_{1\leq
k\leq T:\,\\{i,j\\}\subseteq S_{k},j^{\prime}\notin
S_{k}}\left\|\tilde{\Sigma}\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}\tilde{Y}^{(l)}-\tilde{Y}^{(i)}\Bigg{)}\right\|_{2}^{2}\Bigg{)}.$

Based on Claim A.1 and Claim A.2, with probability at least $1-\delta$,

$\displaystyle\left\|\tilde{\Sigma}\Big{(}\tilde{Y}^{(i)}-\tilde{Y}^{(j)}\Big{)}-\Sigma\Big{(}Y^{(i)}-Y^{(j)}\Big{)}\right\|_{2}\leq$
$\displaystyle~{}\Big{(}2B\sqrt{d}\log
d\left\|P_{{}_{G}}\right\|_{2}\Big{)}\frac{2\sqrt{d}\log
d\left\|P_{{}_{G}}\right\|_{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}$
$\displaystyle+\Big{(}\sqrt{d}\log
d\left\|P_{{}_{G}}\right\|_{2}\Big{)}\frac{4B\sqrt{d}\log
d\left\|P_{{}_{G}}\right\|_{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}$ (20)
$\displaystyle=$
$\displaystyle\frac{8Bd\log^{2}d\left\|P_{{}_{G}}\right\|_{2}^{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}.$

We can see that for any $k$ and $i,j$, with probability at least $1-\delta$,
the equation (19) is

$\displaystyle\bar{\theta}_{i,j^{\prime}}-\bar{\theta}_{i,j}\geq$
$\displaystyle\frac{1}{A_{i,j}\cdot m}\Bigg{(}\sum_{1\leq k\leq
T:\,\\{i,j^{\prime}\\}\subseteq S_{k},j\notin
S_{k}}\left\|\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}Y^{(l)}-Y^{(i)}\Bigg{)}\right\|_{2}^{2}-\sum_{1\leq k\leq
T:\,\\{i,j\\}\subseteq S_{k},j^{\prime}\notin
S_{k}}\left\|\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S_{k}}Y^{(l)}-Y^{(i)}\Bigg{)}\right\|_{2}^{2}\Bigg{)}$
$\displaystyle-8B\cdot\frac{8Bd\log^{2}d\left\|P_{{}_{G}}\right\|_{2}^{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}$

Consider a subset $S^{*}$ where $i\in S^{*}$ and $j,j^{\prime}\notin S^{*}$.
$|S^{*}|=\alpha-1$. We have

$\displaystyle\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in S^{*}\cup
j}Y^{(l)}-Y^{(i)}\Bigg{)}$ $\displaystyle=\frac{1}{\alpha}\sum_{l\in
S^{*}}\Sigma\cdot\Bigg{(}Y^{(l)}-Y^{(i)}\Bigg{)}+\frac{1}{\alpha}\cdot\Sigma\cdot\Bigg{(}Y^{(j)}-Y^{(i)}\Bigg{)}$
$\displaystyle\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in S^{*}\cup
j^{\prime}}Y^{(l)}-Y^{(i)}\Bigg{)}$ $\displaystyle=\frac{1}{\alpha}\sum_{l\in
S^{*}}\Sigma\cdot\Bigg{(}Y^{(l)}-Y^{(i)}\Bigg{)}+\frac{1}{\alpha}\cdot\Sigma\cdot\Bigg{(}Y^{(j^{\prime})}-Y^{(i)}\Bigg{)}$

Thus, we have

$\displaystyle\left\|\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in S^{*}\cup
j^{\prime}}Y^{(l)}-Y^{(i)}\Bigg{)}\right\|_{2}^{2}-\left\|\Sigma\cdot\Bigg{(}\frac{1}{\alpha}\sum_{l\in
S^{*}\cup j}Y^{(l)}-Y^{(i)}\Bigg{)}\right\|_{2}^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{\alpha^{2}}\Bigg{(}\left\|\Sigma\cdot\Big{(}Y^{(j^{\prime})}-Y^{(i)}\Big{)}\right\|_{2}^{2}-\left\|\Sigma\cdot\Big{(}Y^{(j)}-Y^{(i)}\Big{)}\right\|_{2}^{2}\Bigg{)}+2\cdot\Bigg{\langle}\frac{1}{\alpha}\sum_{l\in
S^{*}}\Sigma\cdot\Big{(}Y^{(l)}-Y^{(i)}\Big{)},\frac{1}{\alpha}\cdot\Sigma\Big{(}Y^{(j^{\prime})}-Y^{(i)}\Big{)}-\frac{1}{\alpha}\cdot\Sigma\Big{(}Y^{(j)}-Y^{(i)}\Big{)}\Bigg{\rangle}.$

After taking the sum over all $S^{*}$, we obtain

$\displaystyle\bar{\theta}_{i,j^{\prime}}-\bar{\theta}_{i,j}\geq$
$\displaystyle\frac{1}{\alpha^{2}m}\Bigg{(}\left\|\Sigma\cdot\Big{(}Y^{(j^{\prime})}-Y^{(i)}\Big{)}\right\|_{2}^{2}-\left\|\Sigma\cdot\Big{(}Y^{(j)}-Y^{(i)}\Big{)}\right\|_{2}^{2}+\Bigg{\langle}2\frac{\binom{T-3}{\alpha-3}}{\binom{T-2}{\alpha-2}}\sum_{1\leq
l\leq T:~{}l\neq
i,j,j^{\prime}}\Sigma\cdot\Big{(}Y^{(l)}-Y^{(i)}\Big{)},\Sigma\Big{(}Y^{(j^{\prime})}-Y^{(j)}\Big{)}\Bigg{\rangle}\Bigg{)}$
$\displaystyle-\frac{64B^{2}d\log^{2}d\left\|P_{{}_{G}}\right\|_{2}^{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}$

Since $\binom{T-3}{\alpha-3}/\binom{T-2}{\alpha-2}=\frac{\alpha-2}{T-2}$, the
above equation can be simplified as follows:

$\displaystyle\bar{\theta}_{i,j^{\prime}}-\bar{\theta}_{i,j}\geq$
$\displaystyle\frac{1}{\alpha^{2}m}\Bigg{(}b^{2}-a^{2}-\frac{2(\alpha-2)}{T-2}(T-3)\cdot
4B^{2}\Bigg{)}-\frac{64B^{2}d\log^{2}d\left\|P_{{}_{G}}\right\|_{2}^{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}$

From equation $\eqref{eq_theta_dist}$, we get

(21) $\displaystyle\theta_{i,j^{\prime}}-\theta_{i,j}\geq$
$\displaystyle\frac{1}{\alpha^{2}m}\Bigg{(}b^{2}-a^{2}-\frac{2(\alpha-2)}{T-2}(T-3)\cdot
4B^{2}\Bigg{)}-\frac{64B^{2}d\log^{2}d\left\|P_{{}_{G}}\right\|_{2}^{2}\log(2T^{2}\delta^{-1})}{\sqrt{m}}-8B^{2}\sqrt{\frac{\log(T/\delta)}{n}}$

In conclusion, we have shown that provided that

(22) $\displaystyle b^{2}-a^{2}\geq 8\alpha B^{2}m\varepsilon,$

then under the condition that

(23) $\displaystyle m\geq
64^{2}B^{4}d^{2}\log^{4}d\left\|P_{{}_{G}}\right\|_{2}^{4}\log^{2}(2T^{2}\delta^{-1})\varepsilon^{-2},~{}~{}\text{
and }$ (24) $\displaystyle n\geq B^{4}\log(T\delta^{-1})\varepsilon^{-2},$

the following holds: For any $i=1,2,\dots,T$, if $j^{\prime}$ comes from the
same group as $i$, but $j$ comes from a different group compared with $i$,
then $\theta_{i,j^{\prime}}-\theta_{i,j}\geq\varepsilon/2$.

Thus, we have shown that there exists a block structure in the affinity scores
matrix $[\theta_{i,j}]_{T\times T}$. The proof of Theorem 6.3 is now
completed. ∎

##  Appendix B Additional Experiments

In this section, we provide additional experiments to support our approach.
First, we provide additional observations regarding task relationships. These
include structural differences between tasks in terms of PPR vectors and
studying the effect of model size on mitigating negative transfer. Second, we
compare the running time of our approach with baselines. Third, we provide
comparisons with other baseline methods and ablation studies.

###  B.1. Comparing structural differences between tasks

We study why negative transfers happen between two community assignment tasks
when trained together. We hypothesize that the difference in graph diffusion
processes of the two tasks contributes to negative transfer in graph neural
networks. If their graph diffusion processes are very different, using a
shared GNN would lead to a negative transfer. Otherwise, we expect a positive
transfer between the two tasks. To validate this hypothesis, we compute each
task’s personalized PageRank (PPR) vector using its community labels as the
seed set. Then, we measure the cosine similarity of the PPR vectors between
tasks from the same group and tasks from different groups. We conduct this
comparison based on the task groupings found by our method. Across four
community detection datasets, tasks within the same group exhibit 8.8$\times$
higher cosine similarities in their PPR vectors than tasks from different
groups. Table 3 reports the results. This suggests that graph diffusion
processes of tasks clustered together are more similar.

Table 3. This table reports the cosine similarity of PPR vectors between tasks from the same group and tasks from different groups. For tasks from the same group, their PPR vectors have higher cosine similarities than tasks from different groups. Dataset | Amazon | Youtube | DBLP | LiveJournal
---|---|---|---|---
PPR Cosine Similarity for tasks from the same group | 0.234 | 0.248 | 0.234 | 0.284
PPR Cosine Similarity for tasks from different groups | 0.078 | 0.022 | 0.014 | 0.069

###  B.2. Studying negative transfers by increasing the model size

Previously in Section 3, we demonstrate that increasing the model size cannot
address negative transfers between two tasks, using the SIGN model as the base
model. We observe similar results of using a more powerful GNN with attention,
i.e., GAMLP (zhang2022graph, 129). We select one target task and one source
task whose joint MTL performance is worse than STL for the target task. Then,
We vary the hidden width of a GAMLP model from 32 to 2048 and repeat MTL
training. Table 4 reports the $F_{1}$ scores of the MTL and STL models on the
target task. We observe that the MTL performance is consistently lower than
STL, even as the width increases. This reaffirms our hypothesis that despite
using larger models as width increases, they still do not fix the negative
transfers from the source task to the target task in multi-task learning.

Table 4. This table reports the $F_{1}$ score of a target task, comparing the STL and MTL with a source task that causes negative transfer. Even after increasing the model size of GAMLP, there exists a consistent negative transfer.  Model size | 32 | 64 | 128 | 256 | 512 | 1024 | 2048
---|---|---|---|---|---|---|---
MTL | 24.8 $\pm$ 0.3 | 25.5 $\pm$ 0.2 | 28.8 $\pm$ 0.3 | 32.4 $\pm$ 0.6 | 27.7 $\pm$ 0.2 | 26.5 $\pm$ 0.3 | 19.7 $\pm$ 0.1
STL | 46.3 $\pm$ 0.4 | 46.3 $\pm$ 0.2 | 47.0 $\pm$ 0.3 | 43.3 $\pm$ 0.3 | 42.9 $\pm$ 0.5 | 43.3 $\pm$ 0.3 | 43.6 $\pm$ 0.2

###  B.3. Comparing the running time

We provide a comparison of the running time of our approach with the baselines
in terms of GPU hours evaluated on a single GPU. We notice that the running
time of our approach is comparable to the naive MTL approach, using
$3.5\times$ running time on average compared to the Naive MTL. This is
achieved by using early stopping and downsampling in our implementation to
speed up the training of each MTL model, i.e., computing $f_{i}(S)$ on each
subset $S$. The results are reported in Table 5.

Table 5. Running time (GPU hours) of our approach after adding early stopping and downsampling to speed up the training of MTL models, as compared with baseline approaches. Method | Amazon | YouTube | DBLP | LiveJournal
---|---|---|---|---
Naive MTL | 0.80H | 1.27H | 1.96H | 3.35H
Multi-Gate MoE | 7.01H | 10.39H | 17.28H | 31.74H
Forward Selection | 26.91H | 49.61H | 53.38H | 88.28H
Backward Selection | 37.90H | 62.89H | 69.39H | 105.94H
Clustering by First-Order Task Affinity | 92.68H | 199.99H | 224.22H | 305.69H
Clustering by Higher-Order Approximation | 87.35H | 197.26H | 207.56H | 294.69H
Our approach w/o Early Stopping and Downsampling | 24.46H | 52.79H | 59.19H | 87.17H
Our approach w/ Early Stopping and Downsampling | 2.19H | 4.29H | 4.92H | 7.49H

###  B.4. Comparison with additional community detection and task grouping
methods

We compare our approach with two other community detection methods, including
MinCutPool (bianchi2020spectral, 102) and Deep Modularity Networks
(tsitsulin2023graph, 132). These methods design GNN pooling methods for graph
clustering. For each method, we train the pooling module together with the
SIGN base model. The results are shown in Table 6. We find that our approach
can also outperform them by 5.8% on average.

Furthermore, we compare our approach with clustering by two first-order task
affinities, including the first-order task affinity (fifty2021efficiently,
115) and approximating higher-order task affinity through averaging
(standley2020tasks, 110). The results are shown in Table 6. The results show
that our approach outperforms them by 2.5% on average. This validates the
advantage of using higher-order task affinities over first-order task
affinities.

Table 6. Macro F1-score of community detection tasks on four social networks. We compare our approach with GNN-based community detection methods and two previous task grouping methods based on first-order task affinity. Each result is averaged over three random seeds.  Dataset | Amazon | Youtube | DBLP | LiveJournal
---|---|---|---|---
MinCutPool (bianchi2020spectral, 102) | 84.24 $\pm$ 0.19 | 44.28 $\pm$ 0.49 | 67.49 $\pm$ 0.96 | 81.87 $\pm$ 1.06
Deep Modularity Networks (tsitsulin2023graph, 132) | 83.30 $\pm$ 1.07 | 43.58 $\pm$ 0.77 | 66.32 $\pm$ 0.15 | 79.84 $\pm$ 0.80
Clustering by First-order Task Affinity (fifty2021efficiently, 115) | 90.99 $\pm$ 4.06 | 45.23 $\pm$ 2.73 | 68.23 $\pm$ 3.24 | 83.76 $\pm$ 3.77
Clustering by Higher-order Approximation (standley2020tasks, 110) | 91.61 $\pm$ 3.86 | 46.34 $\pm$ 2.57 | 68.87 $\pm$ 2.23 | 84.61 $\pm$ 2.56
Alg. 1 (Ours) | 92.66 $\pm$ 4.85 | 49.62 $\pm$ 2.26 | 70.68 $\pm$ 2.65 | 88.43 $\pm$ 2.70

###  B.5. Ablation study of Algorithm 1’s parameters

We discuss the three parameters in our approach: the number of task groups
$b$, the subset size $\alpha$, and the number of subsets $n$. We find that a
larger number of task groups yields better performance. Furthermore, our
approach remains stable under the variation of subset size and number of
subsets. The results are reported in Table 7.

First, we ablate the number of task groups $b$ and vary it between 5, 10, 20,
and 100. The results confirm our hypothesis that a larger number of task
groups leads to better performance. Moreover, $b=20$ yields comparable results
to $b=100$, which achieves a 49.76 $F_{1}$ score. Therefore, we use $b=20$ in
our experiments.

Second, We vary the subset size $\alpha$ between 5, 10, and 20. We observe
similar performance for different task grouping settings, using $\alpha=10$
slightly outperforming the other two. The result suggests that using a larger
$\alpha$ does not help because the number of related tasks in community
detection applications is limited.

Third, we vary the number of subsets $n$ between 1000, 1500, and 2000. We
observe that using $n=1000$ still achieves comparable performance as using
$n=2000$. The performance difference is within 0.5%.

Table 7. Study of parameter sensitivity on the Youtube Dataset by varying the number of clusters $b$, the subset size $\alpha$, and the number of samples $n$. $b$ | 5 | 10 | 20
---|---|---|---
Fix $\alpha=10$ and $n=2000$ | 46.65 $\pm$ 3.26 | 48.10 $\pm$ 3.09 | 49.62 $\pm$ 2.62
$\alpha$ | 5 | 10 | 20
Fix $n=2000$ and $b=20$ | 49.02 $\pm$ 3.10 | 49.62 $\pm$ 2.62 | 49.06
$n$ | 1000 | 1500 | 2000
Fix $\alpha=10$ and $b=20$ | 49.20 $\pm$ 2.99 | 49.42 $\pm$ 3.20 | 49.62 $\pm$ 2.62