Hub-Damped Message Passing for Protein Complex Detection

Proteins do their work in teams called complexes: groups of two to dozens of proteins that bind together. Finding these teams in a protein–protein interaction network, a graph whose edges record which proteins were observed to touch, is a standard clustering problem in computational biology. Graph neural networks now lead on the largest benchmark in our file. A graph neural network is a model that builds each node's vector representation by repeatedly averaging in its neighbors' vectors. These networks are known to suffer from over-smoothing: after enough averaging, every node looks the same. The usual story says over-smoothing is a problem of depth, arising only when many layers are stacked. We argue that in interaction networks it shows up much earlier and in a specific place. A handful of "hub" proteins touch hundreds of partners. A hub's own vector is therefore an average over a large part of the graph. Standard attention normalizes over the receiving node's few neighbors, so a two- or three-member complex attached to a hub receives a large share of its information from that averaged vector. Small complexes get pulled toward the global mean after only two layers.

The proposal is to damp what hubs broadcast without silencing what they receive. Each node gets a learned sending gate. The gate closes for nodes whose own representation is a diffuse mixture of many neighbors. Receivers can then ignore hubs and keep their own identity, while hubs still collect evidence from all their partners and can belong to several complexes at once. The same gate also addresses scale. The number of nodes that can influence a given node within a few hops is dominated by hubs, so cutting hub broadcasts keeps that set small. Deeper propagation and mini-batch training then become cheap without the precomputed indexes other scalable methods need.

Core Claim

In unsupervised complex detection on sparse, hub-dominated interaction networks, the harmful form of over-smoothing is local rather than global. It is driven by receiver-normalized aggregation from high-degree senders. It hits small, hub-adjacent complexes first. Global anti-over-smoothing tools do not target it: normalizations that push all nodes apart, extra high-pass channels, and residual connections all act on every node equally. A sender-side gate removes this failure mode inside an otherwise unchanged detector. The gate is a function of each node's degree and of how spread out its own attention is. If the claim holds, three things should follow. Detection accuracy should improve, and the improvement should concentrate on small complexes next to hubs. Accuracy should stop falling as depth grows from 2 to 8 layers. The receptive field and memory per mini-batch should shrink.

Concretely, node $v$ is updated as

$$h_v' = W_s h_v + \sum_{u \in N(v)} g_u\, \alpha_{uv}\, W h_u, \qquad g_u = \sigma\big(a \log d_u + b\, H_u + c\big),$$

where $h_v$ is the current vector of node $v$ and $N(v)$ its neighbors. $\alpha_{uv}$ is the usual attention weight, normalized over $v$'s neighbors. $W_s$ and $W$ are learned matrices. $d_u$ is the degree of sender $u$. $H_u$ is the entropy of $u$'s own incoming attention, high when $u$ averages many neighbors evenly. $\sigma$ is the logistic function, and $a, b, c$ are learned scalars. The neighbor term no longer has to sum to one, so a node beside a diffuse hub can keep mostly its own vector.

Relation to Prior Work

The closest work is ReCycle Net. It is a feature-free two-layer graph attention network whose attention is biased by cycle-based random-walk edge weights. It is trained with a four-part unsupervised loss that includes a Laplacian smoothness term, a penalty on differences between the vectors of connected nodes. It reaches an overlapping normalized mutual information (ONMI) of 0.344 at $r=2$ on the Complex Portal network. This score measures agreement between predicted and true overlapping clusters. ReCycle Net supplies our backbone and loss, and we deliberately reuse both. It never measures over-smoothing. Its cycle weights also rescale only the attention logits, which are still softmax-normalized at the receiver, so a hub remains a large share of a low-degree protein's input. It also depends on random-walk preprocessing that grows expensive with graph size. We change only the propagation operator and replace that preprocessing with degree and entropy, which are nearly free to compute.

Three lines of over-smoothing work motivate and constrain the design. PairNorm rescales embeddings at every layer to hold total pairwise distance constant, which kept accuracy steady across 60 layers when features were missing. It pushes all pairs apart equally, which may break the within-complex similarity that clustering needs. Complete the Missing Half adds a parallel high-pass channel that keeps each node's differences from its neighbors. That channel acts on every node equally, with no notion of which senders cause the damage. Are we measuring oversmoothing correctly? shows that smoothness energy misses collapse, while effective rank, the entropy of the singular-value spread, tracks accuracy with average Pearson correlation 0.91. We use effective rank as our diagnostic, but compute it per complex and per hub neighborhood rather than over the whole graph. The paper's own caveat, that high rank is necessary but not sufficient, is why accuracy remains our primary metric.

On the scale side, CFGNN routes all messages through a small set of hub "cores" chosen by a shortest-path index, which avoids neighborhood explosion. Our design runs opposite: hubs become near-dead ends for outgoing information. Two results support that direction. Core-fringe link prediction found that pooling many low-degree peripheral nodes into core estimates adds noise rather than signal. CFGNN also leaves open the problem of collapse at dense hubs. The mechanism itself comes from RWDISK, which treats high-degree nodes as sinks to make random-walk proximity queries fast on disk-resident graphs. We borrow the hub-as-sink idea and make it learned and soft.

On the biology side, HirHide describes "overshadowing": dominant complexes hide nested or weaker ones. It repairs this after clustering by weakening edges of dominant clusters. We see hub-driven smoothing as the representation-level cause of the same effect and fix it inside the encoder. The scale asymmetry documented by CPredictor2.0 (small-complex F-measure far below large) and ELF-DPC (which discards clusters under three proteins) sets the target: small complexes must be detected, not filtered out.

Research Program

The first stage is diagnostic and could falsify the premise before any new model is built. We will train ReCycle Net and a plain graph attention network on Complex Portal at depths 2, 4, and 8. For every ground-truth complex we will record four quantities: its size, the maximum degree among its members' neighbors, the effective rank of its members' vectors, and a separation score. The separation score is the distance from the complex centroid to the centroid of its hub neighbors, divided by the within-complex spread. The premise predicts that at depth 2 already, separation and per-complex recovery fall as adjacent hub degree rises, most sharply for complexes of size three or less. It also predicts that global effective rank still looks healthy at depth 2. If recovery shows no dependence on hub adjacency, the local-smoothing premise is wrong and we stop.

The second stage builds the hub-damped operator inside ReCycle Net's backbone. The loss, clustering head, embedding initialization, and training schedule are unchanged. The gate inputs are degree and attention entropy only, so the operator needs no random-walk preprocessing. Hubs keep full incoming attention and receive soft memberships in several complexes through the existing head. We will also build a mini-batch version in which edges whose gate falls below a threshold are pruned from the sampled neighborhood. We will measure how the multi-hop receptive field and peak memory grow with depth.

The third stage tests transfer to the curated yeast networks. Gavin and Collins are much smaller but have established complex references and size-stratified results. The question there is whether the gains on small complexes carry over and whether the gated model matches classical and ensemble pipelines.

Baselines

The naive reference points are a plain two-layer graph attention network, which reaches ONMI 0.232 at $r=2$ on Complex Portal, and BigCLAM, a non-neural overlapping community model at 0.243. Both figures are reported in ReCycle Net. We will reproduce these numbers before running anything else, so that our evaluation pipeline is checked against the published ones.

The strongest existing method is ReCycle Net itself, at ONMI 0.344 at $r=2$ on Complex Portal. It is the strongest competitor because it is the best reported neural detector on the largest interaction network in the file. It is also the exact model we modify, so any gain is attributable to the propagation operator. It will be run with its published loss and depth, and then at depths 4 and 8. It gets the same data split, the same number of hyperparameter trials (we fix 30 per method), the same GPU, and five seeds. Beating it means a mean ONMI improvement larger than the seed spread. That improvement must be concentrated in small, hub-adjacent complexes, and the model must stay stable or improve as depth increases. On Gavin, the strongest reported pipeline is ELF-DPC, with F-measure 0.667. On Collins, CPredictor2.0 reports small- and large-complex F-measures of 0.272 and 0.624 against MIPS, and 0.392 and 0.621 against CYC2008. We found no reported result on Lacuna for ReCycle Net on Gavin or Collins, so we will run it there ourselves.

Three generic anti-over-smoothing baselines go inside the same backbone: PairNorm, the filterbank high-pass channel, and residual connections. Each gets the identical tuning budget. They test whether any anti-collapse device is enough or whether the sender-side targeting matters.

Four ablations isolate the key ingredient. The first uses a gate based on degree only, dropping the entropy term. The second uses a fixed gate equal to one over the sender's degree, which is column-normalized aggregation. The third is standard GCN symmetric normalization, which scales each message by one over the square root of the sender and receiver degrees. The fourth is hard hub removal: drop the top 1% of nodes by degree before training, then reattach each removed hub to the clusters of its neighbors.

Why not just…?

Why not just keep the shallow two-layer model? Our central claim is that two layers are already too many for hub-adjacent small complexes. Shallowness therefore does not avoid the failure we target. The stage-one diagnostic tests this directly on ReCycle Net at depth 2. If the diagnostic shows no hub-linked loss at depth 2, this alternative wins and we say so.

Why not just delete the hubs, or use GCN's degree normalization, which already down-weights hubs? This is the most serious threat, and it is why both appear as ablations with identical tuning. Hub removal throws away hub memberships, which matter in an overlapping benchmark, and it needs a hand-set threshold. Symmetric normalization damps senders by a fixed square root of degree, whatever the local structure. The entropy term should matter because some high-degree proteins sit inside large, coherent complexes and should keep broadcasting. If the fixed one-over-degree gate or hub removal matches the learned gate within seed noise, the contribution narrows. What remains is the diagnosis of local over-smoothing together with a one-line operator change, and we would report it that way.

Why not just add PairNorm or a high-pass channel? Both act on all nodes equally. PairNorm in particular pushes apart pairs that should cluster together, and its reported gains are on node classification with missing features, not clustering (PairNorm). Running both in the same backbone settles the question. Our prediction is that they recover global rank but not per-complex separation beside hubs.

Why not just use classical clustering such as MCL, BigCLAM, or seed expansion? On Complex Portal, BigCLAM trails ReCycle Net by about 0.10 ONMI in the reported results. On the yeast networks, however, CPredictor2.0 and ELF-DPC are strong and use annotation data we do not use. We compare against them and would accept a result where the gated model narrows but does not close that gap. That comparison is feature-free against annotation-rich, and we will say so explicitly.

Proposed Experiments

The main experiment is ONMI at $r=2$ on Complex Portal, averaged over five seeds, for every method in the Baselines section, at depths 2, 4, and 8. We will also report F-measure stratified into complexes of size three or less and larger ones, computed against Complex Portal's ground truth. On Gavin and Collins we report F-measure against MIPS and CYC2008, stratified by size, so results line up with the published CPredictor2.0 and ELF-DPC numbers. For scale, we report preprocessing time relative to ReCycle Net's random-walk weights, peak GPU memory, and mean three-hop receptive-field size per mini-batch as depth grows, with and without gate-based pruning.

Three checks decide the question. First, gains must concentrate where the mechanism says they should. When complexes are binned by adjacent hub degree and size, the ONMI and F-measure improvement over ReCycle Net should be largest in the small, high-hub-degree bin and near zero for large complexes far from hubs. A uniform improvement would mean the gate is working as generic regularization rather than for our reason. Second, per-complex separation should rise in exactly those bins. Global effective rank should not by itself explain the gains; if it did, PairNorm should have matched the gate. Third, the learned gate must beat the fixed one-over-degree gate and hard hub removal. If it does not, we report the simpler operator as the practical recommendation.