Where Tasks Collide on Graphs: Clustering-Aware Task Sharing

When one graph neural network predicts many labels per node at once, such as 112 protein functions on the same protein network, it must decide how much the tasks share. Current multi-task methods make that decision globally. They either average all the losses or reshape the summed gradient the same way everywhere. This note argues that on graphs the conflict between tasks is not spread evenly. It concentrates at a specific, label-free structural location: nodes and edges whose neighbors are not linked to one another, the "bridges" between tightly knit local groups. The local clustering coefficient measures exactly this property. It is the fraction of a node's neighbor pairs that are themselves connected, and an analogous triangle count can be defined per edge.

The proposal has two parts. The first is a measurement that could be wrong: per-node disagreement between task gradients should rise as local clustering falls, even after controlling for degree. The second is a cheap architecture that only makes sense if the measurement holds. Message passing is split into two channels, one over edges that sit inside triangles and one over bridge edges. A shared backbone does all the heavy lifting, and each task learns its own mix of the two channels. In plain terms, tasks share freely along cohesive local communities and choose individually whether to listen across bridges.

Core Claim

Two lines of work motivate the claim. Studies of the local community paradigm found that in self-organizing networks such as protein interactomes and connectomes, links among shared neighbors predict link formation better than raw neighbor counts. The same work found that node pairs shielded inside their local community carry the most dependable interactions (From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks). Permanence formalizes how strongly a vertex belongs to its community by weighing internal clustering against the pull of the strongest rival community (On the permanence of vertices in network communities).

Our reading is that a low-cohesion node aggregates messages from several communities whose label profiles differ by task. One task's head wants that mixture and another's does not. That is a structural source of negative transfer, meaning the case where training tasks together makes one of them worse. Parameter-space gradient surgery cannot target it, because the mixing happens inside message passing before any task loss is computed.

The claim is falsifiable on three counts. Gradient disagreement should correlate with low clustering beyond degree. A two-channel split by triangle membership should beat both global gradient surgery and a single structural bias shared across tasks. The advantage should vanish when triangles are destroyed by degree-preserving rewiring.

Relation to Prior Work

The closest structural work is CA-GAT (Local Cluster-Aware Attention for Non-Euclidean Structure Data). It adds a clustering-coefficient bias to graph attention scores and reports gains on single-task node classification. Its bias is shared across all outputs. We instead ask whether tasks should treat cohesive and bridging structure differently, which a shared bias cannot express.

The closest multi-task work on neighborhoods is MT-KNN (Heterogeneous-Neighborhood-based Multi-Task Local Learning Algorithms). It borrows nearest neighbors across tasks in feature space through a single global task-correlation matrix. We make task sharing depend on graph topology rather than on feature distance, and we let it vary by structural location rather than holding one matrix for all points.

The gradient-surgery family supplies the main competitor and our diagnostic tool. PCGrad projects out conflicting task-gradient components (Gradient Surgery for Multi-Task Learning). CAGrad maximizes worst-case task improvement near the mean gradient (Conflict-Averse Gradient Descent for Multi-task learning). RotoGrad rotates the shared representation per task (RotoGrad: Gradient Homogenization in Multi-Task Learning). All three treat every sample identically.

One finding constrains the proposal rather than motivating it. Tuned classic graph networks match far more complex architectures on 17 of 18 node classification datasets (Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification). Every comparison here therefore starts from tuned baselines.

Research Program

Measuring conflict per node. For a node $v$ with shared final representation $h_v$ and linear sigmoid task heads $w_t$, the gradient of task $t$'s cross-entropy loss with respect to $h_v$ has a closed form: $g_{v,t} = (\sigma(w_t^\top h_v) - y_{v,t})\, w_t$. This makes it cheap to compute for all 112 tasks on every node. We summarize agreement with a coherence score

$$\rho_v = \frac{\left\| \sum_t g_{v,t} \right\|}{\sum_t \left\| g_{v,t} \right\|},$$

which equals 1 when all task gradients at $v$ point the same way and approaches 0 when they cancel.

We then regress $1-\rho_v$ on three structural quantities: local clustering, permanence computed from a MaxPerm partition (Permanence and Community Structure in Complex Networks), and log-degree. Comparisons are made within degree bins, because clustering and degree are strongly anticorrelated and degree is the obvious confound. We repeat the measurement at checkpoints through training. Because head gradients only see the final layer, we also measure backpropagated per-node gradients at the first layer on a node subsample.

Two-channel architecture. For each edge $(u,v)$ we compute its edge clustering, the number of triangles through it normalized by the smaller endpoint degree. Edges above a threshold $\tau$ form the cohesive channel and the rest form the bridge channel. The threshold $\tau$ is chosen by quantile on the validation set.

A tuned GraphSAGE or GAT backbone aggregates each channel separately at every layer, producing $h_v^{c}$ and $h_v^{b}$. Task $t$ reads a mix $\alpha_t h_v^{c} + (1-\alpha_t) h_v^{b}$, with one learned scalar $\alpha_t$ per task and layer, or optionally a small per-task gate. The added cost is one extra sparse aggregation and roughly 112 × L scalars, where L is the number of layers. This is far cheaper than per-task attention. It is also a localized task-affinity mechanism: two tasks share on cohesive structure and diverge on bridges exactly when their $\alpha$ values differ. The learned $\alpha_t$ values are themselves an interpretable output. Tasks with low $\alpha_t$ should be functions whose annotations cross community boundaries.

Triangle counting on ogbn-proteins (132,534 nodes, about 39.5M edges, from Open Graph Benchmark: Datasets for Machine Learning on Graphs) uses masked sparse products once, as preprocessing. If memory forbids an exact count, we fall back to edge-sampled estimates and report how sensitive the results are to sampling.

Baselines

The do-nothing reference is a tuned classic network trained on the flat average of all task losses. This is GraphSAGE and GAT configured with the normalization, residual, dropout and depth search of the tunedGNN codebase (LUOyk1999/tunedGNN, art_43357ea5ec1b4021980dc7e713c7e8de) from Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification. It is the most likely reason a reviewer would dismiss any gain. Every other method uses the same backbone, the same hyperparameter search budget (equal trial count and GPU hours), and the official OGB split. Results are reported as mean ± standard deviation over ten seeds.

The strongest existing multi-task competitor is gradient surgery applied to the same backbone. We run PCGrad and CAGrad, using CAGrad-Fast-style task sampling to handle 112 tasks, and tune CAGrad's conflict radius $c$ over the same budget. We also run RotoGrad on PPI, where its per-task rotations remain affordable. No reported result was found on Lacuna for gradient surgery on any graph benchmark, so we establish these numbers ourselves.

The strongest structural competitor is CA-GAT with its shared clustering bias. On PPI it reports micro-F1 of 0.937 (Local Cluster-Aware Attention for Non-Euclidean Structure Data), and on BlogCatalog it reports 0.296. We reimplement it and also re-run it under the tuned-baseline protocol.

On ogbn-proteins, AGDN reports top-1 performance at a fraction of RevGNN's cost (Adaptive Graph Diffusion Networks), but no reported ROC-AUC value for it was found on Lacuna. We therefore rerun AGDN rather than quote it.

Three ablations isolate the key ingredient. The first splits edges by degree product instead of triangle count, at matched channel sizes. The second uses a random split at matched sizes. The third keeps the two-channel model but ties $\alpha_t$ to be shared across all tasks. A win requires a statistically significant improvement in mean ROC-AUC on ogbn-proteins and in micro-F1 on PPI over tuned flat loss, PCGrad, CAGrad and CA-GAT. It also requires the triangle split to beat the degree split and the random split. If shared $\alpha$ matches per-task $\alpha$, the gain is structural but not multi-task, and we would report it as such.

Why not just…?

Why not just apply PCGrad or CAGrad to a graph network? They are the right default and may capture much of the gain. However, they modify one summed parameter update and cannot change how messages are mixed before the losses are computed. If conflict is localized at bridge nodes, global surgery applies the same correction to the cohesive majority, which loses positive transfer there. The diagnostic tests this directly. If $1-\rho_v$ is flat across clustering levels within degree bins, the localization premise fails, and gradient surgery is the correct answer. We would then report that. We also combine surgery with the two-channel model to check whether the two are complementary or redundant.

Why not just append the clustering coefficient as a node feature? It is a single shared input that every task reads identically, and its influence can wash out over layers. More fundamentally, the hypothesis is about edges and tasks: a bridge edge helps task A and hurts task B. A node scalar cannot express that. This variant is included as a baseline, so the comparison is empirical rather than argued.

Why not let per-task attention learn which neighbors to trust? With 112 tasks, separate attention per task multiplies memory on a 39M-edge graph. Shared attention, as in CA-GAT, cannot make task-dependent choices at all. A per-task GAT on PPI, where it is affordable, is a real threat. If it matches the two-channel model, the contribution narrows to cost and interpretability, and we would say so.

Why not gate gradient surgery by measured per-node conflict instead of clustering? At training time this is legitimate and possibly stronger, and we run it as an upper-bound variant. The test it cannot pass is inference. Measured conflict requires labels, whereas triangle membership is label-free. Only a structural routing rule therefore changes how unseen nodes are predicted.

Decisive Checks

The first check is the conflict–cohesion relation on ogbn-proteins, PPI and BlogCatalog. We report Spearman correlation within degree deciles, with permutation tests across seeds, and track how the relation changes over training. If it is absent, we stop and publish the negative result.

The second check is the main accuracy comparison under the protocol above.

The third check is the topological falsification test. Following the community-paradigm finding that triadic structure is what separates predictable self-organizing networks (From link-prediction in brain connectomes and protein interactomes to the local-community-paradigm in complex networks), we rewire each graph with degree-preserving edge swaps to progressively remove triangles. The two-channel advantage over the degree-split ablation should shrink in step with the remaining clustering. If it persists on rewired graphs, the gain is not coming from clustering.

The fourth check validates the learned task mixes biologically. On ogbn-proteins, tasks with low $\alpha_t$ should be the Gene Ontology functions whose positive nodes have lower permanence in the MaxPerm partition. This is a prediction the model was never trained to satisfy.