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.

本文通过多任务学习的视角重新考虑了在给定图上预测多个节点标签函数的问题，并且提出了一种基于高阶任务亲和力度量的任务分组算法，可以更准确地预测负转移。

通过更高维任务关联性提升图上的多任务学习

Boosting Multitask Learning on Graphs through Higher-Order Task  Affinities

In this paper, we provide a theory of using graph neural networks (GNNs) for
multi-node representation learning (where we are interested in learning a
representation for a set of more than one node, such as link). We know that GNN
is designed to learn single-node representations. When we want to learn a node
set representation involving multiple nodes, a common practice in previous
works is to directly aggregate the single-node representations obtained by a
GNN into a joint node set representation. In this paper, we show a fundamental
constraint of such an approach, namely the inability to capture the dependence
between nodes in the node set, and argue that directly aggregating individual
node representations does not lead to an effective joint representation for
multiple nodes. Then, we notice that a few previous successful works for
multi-node representation learning, including SEAL, Distance Encoding, and
ID-GNN, all used node labeling. These methods first label nodes in the graph
according to their relationships with the target node set before applying a
GNN. Then, the node representations obtained in the labeled graph are
aggregated into a node set representation. By investigating their inner
mechanisms, we unify these node labeling techniques into a single and most
general form -- labeling trick. We prove that with labeling trick a
sufficiently expressive GNN learns the most expressive node set
representations, thus in principle solves any joint learning tasks over node
sets. Experiments on one important two-node representation learning task, link
prediction, verified our theory. Our work explains the superior performance of
previous node-labeling-based methods, and establishes a theoretical foundation
of using GNNs for multi-node representation learning.

该论文介绍了使用图神经网络（GNN）进行多节点表示学习的理论，指出之前的方法不能有效地捕捉节点集中节点之间的依赖关系，探究了节点标注技巧，证明其是解决节点集合联合学习任务的最通用方法。

标签技巧：使用图神经网络进行多节点表示学习的理论

Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node  Representation Learning

We state a combinatorial optimization problem whose feasible solutions define
both a decomposition and a node labeling of a given graph. This problem offers
a common mathematical abstraction of seemingly unrelated computer vision tasks,
including instance-separating semantic segmentation, articulated human body
pose estimation and multiple object tracking. Conceptually, the problem we
state generalizes the unconstrained integer quadratic program and the minimum
cost lifted multicut problem, both of which are NP-hard. In order to find
feasible solutions efficiently, we define two local search algorithms that
converge monotonously to a local optimum, offering a feasible solution at any
time. To demonstrate their effectiveness in tackling computer vision tasks, we
apply these algorithms to instances of the problem that we construct from
published data, using published algorithms. We report state-of-the-art
application-specific accuracy for the three above-mentioned applications.

定义了一个组合优化问题，其可行解定义了给定图形的分解和节点标记，并提出了两种局部搜索算法来高效地找到可行解，应用于计算机视觉任务达到 state-of-the-art 应用特定精度。