Relation-Wise Smoothing Resistance for Anomaly Detection on Heterogeneous Graphs

Graph neural networks repeatedly average each node's features with its neighbors'. Run this averaging long enough and every node looks the same, a failure called over-smoothing. SmoothGNN turned this failure into a detector. Normal nodes blend into their neighborhoods within a few averaging steps, while anomalous nodes stay distinct for many more. SmoothGNN measured this only on homogeneous graphs, where every node and every edge is of one kind. Fraud and misinformation graphs are heterogeneous: users, accounts and items are connected by different relations such as "co-reviews", "transfers to" and "lists as emergency contact". A camouflaged fraudster can look perfectly ordinary through its social links while standing out through its transaction links. Flatten all edges into one graph and those two behaviors average out.

We propose to run the averaging separately along each relation and record, for every node and every relation, how quickly the node stops standing out. The anomaly signal is then twofold. A node may resist smoothing more than other nodes of its own type do under the same relation. It may also smooth normally under one relation but resist under another. A second claim is what makes this useful for adapting across graphs. After calibration within each node type, these resistance curves are numbers on a common scale whatever the graph's schema is: its set of node and edge types, and its feature dimensions. A detector trained on the curves of some graphs can therefore be applied, with no retraining, to a graph with different node types, relations and feature spaces. Aligning the smoothing dynamics removes the need to align the feature spaces.

Core Claim

The claim has three parts. First, on graphs with several node and edge types, per-relation smoothing resistance, calibrated against same-type peers, detects anomalies without labels better than smoothing resistance computed on the flattened graph. Second, much of the gain on camouflaged anomalies comes from disagreement across relations, not from resistance on any single relation. Third, because the representation is a set of calibrated curves rather than a feature vector, a small scorer trained on source graphs transfers zero-shot to graphs with unseen schemas. That transfer is the case where feature-alignment methods fail: they need the source and target to share types to align.

Concretely, fix a target node type $t$ with features $X_t$. For each relation $r$ we build a propagation operator $P_r$, the row-normalized adjacency among type-$t$ nodes. When $r$ links $t$ to another type $u$, $P_r$ comes from the two-hop return path $t \to u \to t$. These paths are enumerated automatically from the schema, so no expert chooses meta-paths. We propagate linearly, $H^{(k)}_r = P_r^k X_t$, with no learned nonlinear layers. We define node $i$'s resistance under relation $r$ at step $k$ as

$$ \rho_{i,r}(k) = \frac{\lVert H^{(k)}_{r,i} - \bar H^{(k)}_{r,\mathcal{N}_r(i)} \rVert}{\lVert H^{(0)}_{r,i} - \bar H^{(0)}_{r,\mathcal{N}_r(i)} \rVert + \epsilon}, $$

where $\bar H^{(k)}_{r,\mathcal{N}_r(i)}$ is the mean representation of $i$'s neighbors under $r$ at step $k$ and $\epsilon$ is a small constant. This is a per-node, per-relation version of SmoothGNN's neighborhood smoothing pattern, and it is invariant to feature scale and dimension. Each curve $\rho_{i,r}(\cdot)$ is then replaced by its conditional quantile among type-$t$ nodes of similar degree under the same relation. This step reuses the idea of CADET, which showed that uncalibrated anomaly residuals flag hard normal samples; its quantile calibration cut the false-positive rate on the hardest quarter of normal samples from about 19% to about 5%. In our setting, hub nodes and node types that naturally mix slowly play the role of hard normals.

Research Program

The work has four pieces.

The first is a premise check. We have not yet established that smoothing resistance separates anomalies relation by relation in heterogeneous graphs. SmoothGNN observed it only on flattened graphs. We will plot calibrated resistance curves for labeled anomalies against normal nodes, per relation, on the benchmarks below, before building anything else.

The second is an unsupervised scorer. It combines the strongest calibrated resistance across relations with the spread of calibrated resistance across relations. The spread is the "normal here, strange there" term. The scorer has no trainable parameters apart from the quantile fits.

The third is a generalist scorer. This is a small permutation-invariant network over the set of per-relation curves, so it accepts any number of relations. It is trained with labels on source graphs and frozen for targets, following the train-on-some, test-on-rest protocol of DR-GGAD.

The fourth is an analysis of feature alignment. It asks whether aligning neighbor-type features into the target type's space adds anything once dynamics are calibrated, or whether it smooths away the signal. The alignment variant tested is the closed-form Gaussian optimal transport of TAGDN.

The design choices follow from prior work in three distinct roles. Several papers motivate the gap. SmoothGNN supplies the resistance phenomenon but uses one uniform random-walk operator. ChiGAD shows that different meta-paths have very different frequency profiles, for example bursty transaction paths against smooth social paths, which is why a single flattened curve should lose information. AHEAD shows that modeling heterogeneity helps even without any smoothing analysis. ChiGAD also acts as a constraint. It argues that nonlinear alignment layers act as low-pass filters that erase anomaly spikes, which is why our propagation is linear and our alignment step is an optional ablation, not a core component. TAGDN supplies an alignment method we test but do not rely on. Its Gaussian assumption and its low-pass diffusion, Personalized PageRank or heat kernel, are exactly what ChiGAD warns against for anomalies. DR-GGAD supplies the transfer protocol and the closest generalist competitor. It uses homogeneous GCN layers, so it must flatten ACM-like graphs. Finally, GNNSafe reports that iterating energy propagation too long erases the in/out-of-distribution boundary. That warning is why we score whole curves over $k$ instead of a single deep step.

Baselines

The naive reference points come first. One is an isolation-style score on raw node features, computed separately for each node type, which uses no graph at all. The other is a zero-step version of our scorer, which uses only initial neighbor discrepancy, $\rho(0)$ before propagation. If our method does not beat both, the smoothing dynamics add nothing.

The most direct competitor is SmoothGNN run on the flattened graph. It is the only published method that scores anomalies from smoothing behavior, and it scales to multi-million-node graphs, including DGraph-Fin and T-Social. It reports an average 14.66% AUROC and 7.28% average-precision gain over eleven baselines, but the file gives no per-dataset numbers, so we must reproduce it. We will use its public configuration, give it the same number of propagation steps and the same hyperparameter search budget as our method, and run it on identical splits.

For unsupervised heterogeneous detection, the strongest cited method is AHEAD. It reports AUC 0.6287 on PolitiFact against DOMINANT's 0.5586, and AUC 0.9139 on IMDB. We will rerun it on our splits and also quote these published numbers. Beating it means higher mean AUROC across IMDB, CoAID, PolitiFact and GossipCop.

For zero-shot transfer, the strongest competitor is DR-GGAD. It reports average rank 1.0 across eight targets and a mean AUROC gain of 5.14% over ARC, including +9.96% on ACM. The file does not give absolute AUROC values, so we will run the released code (bfrnlkj/DR-GGAD) under its own protocol and ours. AnomalyGFM (mala-lab/AnomalyGFM) and UNPrompt (mala-lab/UNPrompt) serve as further generalist baselines; for these, no reported result was found on Lacuna. Beating DR-GGAD means better mean AUROC and AUPRC on the heterogeneous targets, with no loss on its homogeneous targets.

The supervised ceiling is ChiGAD, which reports AUROC 0.9702 on ACM with labels. On DGraph, the file reports supervised AUCs of 0.792 for the temporal attention model TGAT and 0.784 for a relational GCN. We do not expect to match these without labels. They calibrate how much of the supervised gap label-free relation-wise dynamics can close.

The ablation that isolates the key ingredient is per-relation SmoothGNN pooled. It computes SmoothGNN-style scores on each relation separately and takes their sum or maximum, with no type-conditioned calibration and no cross-relation spread term. A second ablation removes only the calibration, and a third removes only the spread term.

Why not just…?

Why not just flatten the graph and run SmoothGNN or DR-GGAD? Flattening mixes relations whose frequency profiles differ sharply, according to ChiGAD. AHEAD's 0.6287 against DOMINANT's 0.5586 on PolitiFact and DGraph's RGCN gain from 0.751 to 0.784 both indicate that edge types carry signal. None of this is evidence about smoothing-based detectors specifically, so the flattened-SmoothGNN comparison, together with the synthetic camouflage test below, is where this is actually decided.

Why not just run SmoothGNN per relation and add up the scores? This is the real threat. It keeps most of our machinery, and if it matches us the contribution shrinks to "apply SmoothGNN per relation". Our bet is that raw per-relation scores are dominated by relations and node types that mix slowly for benign reasons, which is CADET's hardness bias, and that summation hides camouflage. We will report this ablation on every dataset. If it comes within noise of the full method on real data, and wins only on synthetic injections, we will say that the calibration and spread terms do not earn their place.

Why not align the node types into one feature space first, for example with TAGDN's optimal transport, and then detect? Alignment requires the source and target graphs to share types, so it cannot support zero-shot transfer to new schemas. ChiGAD also argues that alignment layers smooth away anomalies. Still, Gaussian optimal transport is linear, so ChiGAD's argument may not apply to it. The alignment ablation tests this directly on the single-graph benchmarks.

Why not just use a shallow two-layer heterogeneous model? A shallow model keeps only $\rho(1)$ and $\rho(2)$ and discards the later part of the curve, which is where SmoothGNN locates the separation. Truncating our curves at $k=2$ is a direct test of this. If truncation costs nothing, the depth story is wrong for heterogeneous graphs.

Proposed Experiments

The single-graph unsupervised study uses heterogeneous graphs with labeled anomalies: IMDB, CoAID, PolitiFact and GossipCop from AHEAD, ACM, and YelpChi with its review relations. It adds DGraph-Fin, where the emergency-contact edges and the 2.4 million background nodes give a natural second node type, as a large-scale test (3.7M nodes, 1.3% anomalies). The Tencent R-I and R-II graphs used by ChiGAD are likely not public; we will use them only if they can be obtained. Metrics are AUROC and AUPRC, averaged over five seeds, plus wall-clock time and peak memory against SmoothGNN on DGraph-Fin.

The zero-shot study follows DR-GGAD's protocol. We train the curve scorer on PubMed, Flickr, Questions and YelpChi. We then test frozen on ACM, IMDB and PolitiFact with their native relations, and on DR-GGAD's homogeneous targets, which amount to a single relation, to confirm nothing breaks. A stricter split holds out every graph that shares a relation type with any source graph.

Three checks decide whether the idea works:

  • Premise check. Calibrated per-relation resistance separates anomalies from normal nodes on at least some relations of each real benchmark. If it does not, the project stops or narrows.
  • Controlled camouflage injection. On ACM and IMDB, we inject anomalies whose features are consistent with their neighbors under one relation and inconsistent under another. Flattened SmoothGNN and pooled per-relation scoring should degrade as the camouflaged relation's share of edges grows, while the spread term should not.
  • Schema-transfer test. The frozen curve scorer should beat DR-GGAD on heterogeneous targets whose relations never appear in the source graphs. If it only wins when schemas overlap, the claim that dynamics are schema-invariant is false.