Propagating Anomaly Scores Across Graph Neighborhoods

16 concepts9 papers1 proposal

When machine learning models evaluate data points in isolation, they are highly susceptible to noise. A single unusual feature can cause a model to flag an ordinary sample as an anomaly or an out-of-distribution (OOD) input. However, in many real-world applications, data points do not exist in a vacuum—they are interconnected.

A growing body of research leverages these interconnections through a simple yet powerful insight: homophily. If a data point is anomalous or out-of-distribution, its structural neighbors are likely to be as well. By propagating and smoothing anomaly scores across a graph's neighborhood, models can reach a local consensus, effectively filtering out individual node noise and amplifying true systemic signals.

The Intuition: Noise Reduction via Local Consensus

To understand why neighborhood propagation works, consider a standard classification model operating on a graph. If the model relies solely on individual node features, a minor corruption in a node's attributes might push its predicted score into the outlier zone.

Isolated Prediction:
[Node A: Noisy Features] ---> Model ---> High Anomaly Score (False Positive)

Neighborhood Propagation:
[Neighbor 1 (Low)] \
[Neighbor 2 (Low)]  ---> Average/Filter ---> Node A's Score is Smoothed Down
[Node A     (High)] /

By introducing a post-processing step that averages a node's predicted score with those of its immediate neighbors, we exploit structural dependencies. As demonstrated by Tang et al. in a comprehensive benchmarking study, even simple tree ensembles (like XGBoost) combined with basic neighborhood score averaging can consistently outperform complex Graph Neural Networks (GNNs) in semi-supervised anomaly detection. The neighborhood average acts as a corrective mechanism, smoothing out isolated errors when labeled data is scarce.

This principle forms the basis of broader out-of-distribution detection. Hoffmann et al. formalize this as a meta-method for lifelong graph learning, showing that explicitly aggregating OOD scores from adjacent vertices refines individual detection accuracy by leveraging the homophily assumption. Similarly, Song et al. utilize this structural consistency within a specialized attention framework (OODGAT) to smooth detection scores across connected communities, ensuring that open-world outliers are identified collectively rather than in isolation.

Energy-Based Propagation

A particularly robust framework for implementing this idea involves energy-based models (EBMs). In these setups, a model assigns a scalar "energy" value to each input; lower energy corresponds to familiar, in-distribution (ID) data, while higher energy signifies unfamiliar, out-of-distribution data.

When applied to graphs, raw energy scores can be propagated directly through the graph's adjacency matrix. Wu et al. introduced this via an "Energy Belief Propagation" scheme (GNNSAFE). By smoothing energy values across adjacent nodes, the framework forces neighboring nodes to align their distribution assessments, which significantly reduces individual node noise and boosts OOD detection accuracy.

Raw Energy Scores:       [ID: 1.2] --- [OOD: 8.5] --- [OOD: 9.0]
                                            \             /
                                             [ID (Noisy): 7.8]  <-- Misaligned

After Propagation:       [ID: 2.1] --- [OOD: 8.4] --- [OOD: 8.6]
                                            \             /
                                             [OOD: 8.3]         <-- Corrected!

This propagation alters the energy landscape in two beneficial ways, as detailed by Zhang et al.:

  1. It lowers the energy of known-class clusters by averaging out minor feature variations.
  2. It raises the energy of potential outliers by pooling the high-energy signals of neighboring anomalous nodes.

To prevent energy from bleeding inappropriately across the boundaries between different distributions, advanced architectures add constraints. For instance, Zhang et al. implement a structure-aware propagation mechanism that weights connections based on distribution similarity. This ensures that energy aggregates primarily among neighbors that share similar underlying distributions, further amplifying the contrast between ID and OOD regions.

Generalizing Beyond Native Graphs

The power of neighborhood score propagation is not restricted to datasets that arrive as native graphs. The same mathematical intuition applies to any domain where a similarity network can be constructed from the data.

3D Point Clouds

In computer vision, models trained on clean synthetic 3D data often struggle with messy, real-world scans due to domain shift. Goodge et al. address this by constructing a similarity graph of test samples within the latent space of a Vision-Language Model. By propagating classification and anomaly scores through this constructed graph, their method (SODA) aggregates scores from nearby neighbors to correct individual misalignments caused by domain noise—all without requiring additional training.

Civil Aviation and Streaming Signals

The mechanism also scales to macro-system monitoring and streaming data. Wu et al. model civil aviation systems as global networks where hubs represent nodes and routes represent edges. Their iterative smoothing algorithm refines local anomaly scores based on the principle that related routes should exhibit correlated behavior, allowing them to detect systemic market anomalies while suppressing random, isolated fluctuations.

For continuous data streams, Wang et al. apply graph filters to local anomaly scores of manifold-valued signals. This spatial smoothing acts as a low-pass filter over the network, making the system highly sensitive to subtle, community-wide shifts while filtering out high-frequency random noise from individual sensors.

Summary

Neighborhood score propagation works because it shifts the burden of anomaly detection from isolated feature analysis to collective structural consensus. Whether smoothing raw probabilities, energy scores, or change-point statistics, passing these values through a graph structure leverages homophily to act as a natural error-correcting mechanism. The result is a dramatic reduction in false positives and a significantly more robust detection of true, systemic outliers.

Key Foundational Work

Learning on Graphs with Out-of-Distribution Nodes (2022) — contributed 1 concept elements to this direction.
Discovering abnormal civil aviation requirements by analyzing users' online query behaviors (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_neighborhood_score_propagation_14631f51,
  title = {neighborhood score propagation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neighborhood-score-propagation/rdr_14631f51f58f44e3aaee9712edb8459b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_neighborhood_score_propagation_14631f51_v1,
  title = {neighborhood score propagation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/neighborhood-score-propagation/rdr_14631f51f58f44e3aaee9712edb8459b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake