  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.
