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

arXiv: https://arxiv.org/abs/2306.14009 · HTML: https://mlsanity.com/paper/2306.14009/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 69 references that are in the map.
- First posted on arXiv 24 Jun 2023.

## Builds on (most cited first, 30 of 36)

- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [Which Tasks Should Be Learned Together in Multi-task Learning?](https://mlsanity.com/paper/1905.07553/) (2019)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Efficiently Identifying Task Groupings for Multi-Task Learning](https://mlsanity.com/paper/2109.04617/) (2021)
- [Datamodels: Predicting Predictions from Training Data](https://mlsanity.com/paper/2202.00622/) (2022)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Exploring and Predicting Transferability across NLP Tasks](https://mlsanity.com/paper/2005.00770/) (2020)
- [Understanding and Improving Information Transfer in Multi-Task Learning](https://mlsanity.com/paper/2005.00944/) (2020)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization](https://mlsanity.com/paper/2009.05204/) (2020)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Graph Attention Multi-Layer Perceptron](https://mlsanity.com/paper/2206.04355/) (2022)
- [Graphonomy: Universal Human Parsing via Graph Transfer Learning](https://mlsanity.com/paper/1904.04536/) (2019)
- [Multi-Task Feature Learning for Knowledge Graph Enhanced Recommendation](https://mlsanity.com/paper/1901.08907/) (2019)
- [Deep Multi-task Representation Learning: A Tensor Factorisation Approach](https://mlsanity.com/paper/1605.06391/) (2016)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [On the Generalization Effects of Linear Transformations in Data Augmentation](https://mlsanity.com/paper/2005.00695/) (2020)
- [Improved Regularization and Robustness for Fine-tuning in Neural Networks](https://mlsanity.com/paper/2111.04578/) (2021)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Understanding and Improving Fairness-Accuracy Trade-offs in Multi-Task Learning](https://mlsanity.com/paper/2106.02705/) (2021)

## Built on by (most cited first, 15 of 15)

- [Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity](https://mlsanity.com/paper/2409.06091/) (2024)
- [Graph Neural Networks for Road Safety Modeling: Datasets and Evaluations for Accident Analysis](https://mlsanity.com/paper/2311.00164/) (2023)
- [Scalable Fine-tuning from Multiple Data Sources: A First-Order Approximation Approach](https://mlsanity.com/paper/2409.19458/) (2024)
- [Linear-Time Demonstration Selection for In-Context Learning via Gradient Estimation](https://mlsanity.com/paper/2508.19999/) (2025)
- [Scalable Multi-Objective and Meta Reinforcement Learning via Gradient Estimation](https://mlsanity.com/paper/2511.12779/) (2025)
- [Causal Representation Learning from Multimodal Clinical Records under Non-Random Modality Missingness](https://mlsanity.com/paper/2509.17228/) (2025)
- [Learning Tree-Structured Composition of Data Augmentation](https://mlsanity.com/paper/2408.14381/) (2024)
- [Hierarchical Structure Sharing Empowers Multi-task Heterogeneous GNNs for Customer Expansion](https://mlsanity.com/paper/2410.22089/) (2024)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [Empowering Power Outage Prediction with Spatially Aware Hybrid Graph Neural Networks and Contrastive Learning](https://mlsanity.com/paper/2604.04916/) (2026)
- [When Does Global Attention Help? A Unified Empirical Study on Atomistic Graph Learning](https://mlsanity.com/paper/2510.05583/) (2025)
- [Learning Multimodal Embeddings for Traffic Accident Prediction and Causal Estimation](https://mlsanity.com/paper/2512.02920/) (2025)
- [Learning Dynamic Representations and Policies from Multimodal Clinical Time-Series with Informative Missingness](https://mlsanity.com/paper/2604.21235/) (2026)
- [MoPLEx: Estimating Plackett-Luce Mixture Models for Multi-Objective Alignment](https://mlsanity.com/paper/2608.25200/) (2026)
- [Long-Context Demonstration Selection Using State Space Models](https://mlsanity.com/paper/2609.17888/) (2026)

## Abstract (arXiv)

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.