Telling Heterophily From Noise, One Relation at a Time

Graph neural networks learn about a node by averaging information from its neighbors. When the graph contains wrong edges, whether random errors or edges planted by an attacker, that averaging spreads the damage. The standard defense is to delete edges between nodes that look dissimilar. That defense breaks on graphs where dissimilar nodes are supposed to be connected. This property is called heterophily: fraudsters link to victims, and a movie links through its actors to movies of other genres. It is worse on heterogeneous graphs, which have many node and edge types, because each edge type can mix classes in its own way. On IMDB, for example, the Movie–Director–Movie path connects movies of the same class, while Movie–Actor–Movie connects movies of different classes (AHGNN). A similarity-based cleaner applied to such a graph deletes exactly the edges that carry the signal.

We propose a different test for whether an edge is real. For each relation type, estimate which pairs of classes that relation usually connects, and keep an edge if its endpoints form a pair the relation plausibly connects. Similarity plays no part. Genuine heterophily is structured, because a relation that mixes classes still mixes them in a predictable, non-uniform pattern. Random noise pushes that pattern toward uniform mixing. So the question to ask of an edge is "does this relation usually connect classes like these?" rather than "are these two nodes alike?" The same random-mixing component is what drives deep networks toward over-smoothing, the collapse of all node representations toward one value as layers are stacked. Removing it should therefore also let networks go deeper on noisy graphs.

Core Claim

In a heterogeneous graph, structural noise and heterophily can be separated per relation using a small class-compatibility matrix. This matrix records how often relation $r$ connects a node of class $a$ to a node of class $b$. Under random edge corruption the observed matrix is a known mixture of the clean one and a uniform component, so the uniform part can be estimated and removed. Each edge can then be scored by how much more likely its endpoint classes are under the cleaned relation-specific pattern than under random mixing. We claim three things. This score, combined with a hard top-$T$ neighbor mask, keeps heterophilous edges that similarity-based cleaners delete. It matches those cleaners on homophilous relations. And it extends the depth at which standard and sheaf-based networks remain accurate on noisy graphs.

Mechanism

Let $H_r \in \mathbb{R}^{C\times C}$ be the clean compatibility matrix of relation $r$ over $C$ classes, normalized to a joint distribution over endpoint class pairs. Let $\pi_r$ be the vector of class frequencies of relation-$r$ endpoints, and let $\eta_r$ be the fraction of relation-$r$ edges that are random insertions. Under random insertion, the observed matrix is

$$\hat H_r = (1-\eta_r)\,H_r + \eta_r\,\pi_r\pi_r^\top .$$

This follows because a randomly inserted edge draws its endpoint classes independently, which gives the rank-one term $\pi_r\pi_r^\top$. We estimate $\hat H_r$ from soft class predictions, meaning predicted class probability vectors, on the relation's edges, with labeled nodes clamped to their labels. We estimate $\eta_r$ as the largest weight whose subtraction keeps $H_r$ entrywise nonnegative. This is a simple, identifiable choice that errs toward under-cleaning. Given soft predictions $p_u, p_v$ for the endpoints of edge $(u,v)$, the edge score is the expected pointwise log-ratio

$$s_r(u,v) = \sum_{a,b} p_u(a)\,p_v(b)\,\log\frac{H_r(a,b)}{\pi_r(a)\pi_r(b)} .$$

A strongly heterophilous relation gives high scores to cross-class pairs and low scores to the pairs it rarely produces. An edge is suspicious when its score is negative, meaning the relation connects that class pair less often than chance.

Following RoHe, the score feeds a hard top-$T$ mask before aggregation rather than a soft attention weight. RoHe showed that softmax attention leaves many small nonzero weights on injected neighbors, and together those weights dominate the node's representation. Masking alternates with re-estimating the class predictions for a few rounds. This is an expectation-maximization-style loop close in spirit to the iterate-reconstruct-propagate cycle of R²LP. The difference is that we never rebuild a single homophilous graph, which R²LP does. We keep the typed schema and change only which typed edges survive.

The scoring works at the level of meta-paths, meaning multi-hop typed paths such as Movie–Actor–Movie, as well as at the level of raw relations. Scoring at the meta-path level is what defends against the perturbation enlargement effect. That effect occurs when one inserted edge to a hub, a very high-degree node, creates hundreds of spurious meta-path neighbors, whose endpoint classes then look like uniform mixing.

Relation to Prior Work

Two lines of work motivate the gap. Towards Understanding and Reducing Graph Structural Noise measures structural noise with a spectral signal-to-noise ratio and rewires graphs with a feature-based edge predictor (GPS). It is homogeneous, and its signal is feature similarity. RoHe defends heterogeneous networks with transition probabilities from random walks plus feature similarity, and was evaluated only on homophilous datasets (ACM, DBLP, Aminer). On heterophilous relations it would prune valid edges. AHGNN and the H2GB benchmark establish that heterophily varies across meta-paths. The H2GB index measures how far edge mixing deviates from random, which is the same quantity our score uses per edge. Neither paper considers noise. We take RoHe's hard mask and AHGNN's per-meta-path view, and replace similarity with relation-conditioned compatibility.

A second group constrains the design. GGCN and structural balanced propagation fight over-smoothing with negative edges derived from feature or label similarity. Both assume clean edges, and both inherit the similarity confusion we target. MTGCN identifies indiscriminate mixing of messages across classes as the common cause of over-smoothing and over-squashing. That finding supplies our hypothesis that removing the random-mixing component should extend usable depth. The sheaf models, Neural Sheaf Diffusion and HetSheaf, resist over-smoothing by letting propagation increase the spread of node features. We expect that same property to amplify noise on corrupted graphs. We test this rather than assume it, and use the sheaf models as backbones that the cleaner could protect.

Research Program

The work has four parts. First, we build the estimator. Per-relation and per-meta-path compatibility matrices come from soft predictions, with the noise-weight correction applied. The implementation runs in linear time over edges, since everything is $C\times C$ per relation, so it scales to ogbn-mag.

Second, we analyze when separation is possible. Under a typed stochastic block model with random insertions, the clean and noise components are identifiable exactly when $H_r$ is not itself close to $\pi_r\pi_r^\top$. Relations that are truly uninformative cannot be cleaned, and they should not need to be. We will make this condition precise and relate it to the H2GB index.

Third, we attach the mask to four kinds of backbone and leave everything else unchanged. These are a decoupled precomputed model in the SeHGNN style (SeHGNN), AHGNN, HetSheaf, and a deep relational GCN swept in depth.

Fourth, we probe the method's limit with an adaptive attacker. This attacker knows the compatibility matrices and inserts only edges whose predicted endpoint classes look plausible. No compatibility-based method can reject such edges when predictions are correct. We will measure how much harm such edges can do, since they are constrained to look like real relation structure.

Baselines

The naive reference points are each backbone trained on the corrupted graph with no cleaning, plus a feature-only MLP. The MLP shows whether the graph helps at all once it has been corrupted. GGCN's authors note that it was the only model in their study to consistently beat an MLP on heterophilous data (GGCN).

The strongest existing defense is RoHe, because it is the only published heterogeneous defense and it already uses the hard mask we reuse. RoHe reports that HAN under attack on ACM falls from 92.6% to 52.8% accuracy, and that RoHe restores it to 90.4% (RoHe). We reproduce this setting first. We match RoHe on ACM within noise, and we win if we clearly beat it on heterophilous relations (IMDB Movie–Actor–Movie, and H2GB datasets). No reported result was found on Lacuna for RoHe on IMDB or H2GB, so we run it ourselves.

The second strongest competitor is GPS-style rewiring (GPS), extended with one edge predictor per relation. A learned edge predictor could in principle pick up heterophilous patterns. GPS reports GCN accuracy of 74.6% on Cornell, 80.0% on Texas and 78.8% on Wisconsin after rewiring, against 43.5%, 66.2% and 52.9% without it. On clean heterogeneous data the reference is H2G-former, at 28.47% accuracy on oag-cs versus 22.51% for HGT (H2GB). We aim to hold that level on clean data and lose less of it under noise.

Two ablations isolate the key ingredient. The first keeps the hard mask and the loop but replaces the compatibility score with cosine feature similarity. The second pools a single compatibility matrix across all relations. All methods share the same splits and noise seeds, the same backbone and hidden size, and an equal hyperparameter search budget of 50 trials per method. Mask sizes and thresholds are tuned on clean validation data only.

Why not just…?

Why not just use RoHe or Jaccard-style similarity pruning with a separate threshold per relation? This is the most serious alternative. A low enough threshold on a heterophilous relation simply stops pruning, which avoids damage but also removes the defense. Similarity cannot tell "dissimilar and legitimate" from "dissimilar and injected" on a relation whose true edges are mostly dissimilar. Our score can, because it asks which dissimilar class pair is involved. The similarity-swap ablation, run with per-relation thresholds, settles the question. If it matches us on IMDB Movie–Actor–Movie and the H2GB datasets, the idea adds nothing and we will report that.

Why not just train a per-relation link predictor on features, as GPS does? A link predictor trained on the observed graph learns to reproduce whatever edges exist, including the noise. It has no explicit model of what noise looks like. Our estimator subtracts a known noise form in a $C\times C$ space and needs only class predictions. We expect the gap to widen as the noise rate grows and as labels become scarce. If per-relation GPS equals us across noise rates, we would conclude the explicit noise model is unnecessary.

Why not just precompute meta-path averages and train a shallow model (SeHGNN), or drop the graph (MLP)? Decoupling avoids depth-driven collapse. It does not remove injected hub paths, which are averaged directly into the precomputed features. The SGC-style failure analysis in GGCN predicts this breaks on low-homophily nodes. Because the mask is applied to SeHGNN itself, the comparison of SeHGNN with and without the mask answers the question directly. The MLP stays in the tables as the floor any graph method must clear.

Why not just use soft attention to down-weight bad neighbors? RoHe's ACM result already shows soft attention collapsing under hub injection. We include soft score weighting as a variant of our own method to confirm that the hard mask is needed with our score too.

Proposed Experiments

The heterogeneous benchmarks are ACM, DBLP and IMDB, where IMDB supplies both a homophilous and a heterophilous meta-path. We also use H2GB's oag-cs, RCDD, IEEE-CIS-G and H-Pokec, and ogbn-mag for scale. Cornell, Texas, Wisconsin, Chameleon and Squirrel serve as a single-relation sanity check, where MTGCN's reported 92.10% on Texas and 90.20% on Wisconsin set the clean ceiling.

Corruption comes in four forms: random per-relation insertion at 10–50%, hub-targeted insertion that exploits perturbation enlargement, RoHe's attack setting, and the compatibility-aware adaptive attacker. Metrics are accuracy or micro-F1, together with edge-level precision and recall at recovering the edges we inserted, reported separately for homophilous and heterophilous relations.

Three checks decide the proposal. First, on heterophilous relations, our method must keep a clearly higher fraction of original edges than similarity pruning at equal recall of injected edges. Second, the estimated $\eta_r$ must track the true insertion rate on synthetic typed block models and on real graphs with known injections. Third, in a depth sweep from 2 to 64 layers for the relational GCN and HetSheaf, cleaning must shift the depth at which accuracy collapses. If the depth curves under noise do not move after cleaning, the link to over-smoothing claimed above is wrong, and we will limit the contribution to robustness.