Boosting Multitask Learning on Graphs through Higher-Order Task Affinities

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.

16 pages. Appeared in KDD 2023

References in corpus (30)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Higher-order organization of complex networks
• GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• Open Graph Benchmark: Datasets for Machine Learning on Graphs
• Predict then Propagate: Graph Neural Networks meet Personalized PageRank
• Scaling Graph Neural Networks with Approximate PageRank
• TUDataset: A collection of benchmark datasets for learning with graphs
• VERSE: Versatile Graph Embeddings from Similarity Measures
• Learning Task Grouping and Overlap in Multi-task Learning
• Which Tasks Should Be Learned Together in Multi-task Learning?
• SIGN: Scalable Inception Graph Neural Networks
• Supervised Community Detection with Line Graph Neural Networks
• Graph Attention Multi-Layer Perceptron
• Deep Multi-task Representation Learning: A Tensor Factorisation Approach
• Spectral Clustering with Graph Neural Networks for Graph Pooling
• Scalable Graph Neural Networks via Bidirectional Propagation
• Understanding and Improving Information Transfer in Multi-Task Learning
• Understanding and Improving Fairness-Accuracy Trade-offs in Multi-Task Learning
• Efficiently Identifying Task Groupings for Multi-Task Learning
• Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
• Datamodels: Predicting Predictions from Training Data
• Saliency-Regularized Deep Multi-Task Learning
• On the Generalization Effects of Linear Transformations in Data Augmentation
• Improved Regularization and Robustness for Fine-tuning in Neural Networks
• Learning Universal Graph Neural Network Embeddings With Aid Of Transfer Learning
• The CLRS Algorithmic Reasoning Benchmark
• Robust Fine-Tuning of Deep Neural Networks with Hessian-based Generalization Guarantees
• Identification of Negative Transfers in Multitask Learning Using Surrogate Models
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion

Cited by in corpus (1)

• Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity