PaperlayerView exact revision on arXiv

Source-linked AI summary

Truncated Affinity Maximization: One-class Homophily Modeling for Graph Anomaly Detection

Hezhe Qiao, Guansong Pang

arXiv:2306.00006v5cs.SIcs.AIcs.LG

TL;DR

Graph anomaly detection methods often use reconstruction or self-supervised objectives, while overlooking the observed pattern that normal nodes have stronger mutual affinity than abnormal nodes. TAM uses local node affinity and maximizes it on iteratively truncated graphs; across 10 real-world GAD datasets, it outperforms seven SOTA detectors.

  • Problem

    Existing GAD methods commonly use reconstruction or self-supervised objectives, while overlooking the observed one-class homophily pattern in which normal nodes have stronger mutual affinity than abnormal nodes.

    Source: §1 · pp. 1–2

  • Method

    TAM learns representations by maximizing local node affinity on truncated graphs that iteratively remove non-homophily edges.

    Source: §1 · p. 2, §3.1 · p. 4

  • Results

    Across 10 real-world GAD datasets, TAM outperforms seven SOTA detectors.

    Source: §5 · p. 10

  • Takeaways & Limitations

    The paper reports that one-class homophily can also be exploited to enhance existing GAD methods.

    Source: §5 · p. 10

    TAM cannot directly handle primarily isolated nodes and requires large memory on graphs with very large node or edge sets; one-class homophily may not hold in datasets with strong heterophily.

    Source: §5 · p. 10

Abstract

from arXiv · show

We reveal a one-class homophily phenomenon, which is one prevalent property we find empirically in real-world graph anomaly detection (GAD) datasets, i.e., normal nodes tend to have strong connection/affinity with each other, while the homophily in abnormal nodes is significantly weaker than normal nodes. However, this anomaly-discriminative property is ignored by existing GAD methods that are typically built using a conventional anomaly detection objective, such as data reconstruction. In this work, we explore this property to introduce a novel unsupervised anomaly scoring measure for GAD, local node affinity, that assigns a larger anomaly score to nodes that are less affiliated with their neighbors, with the affinity defined as similarity on node attributes/representations. We further propose Truncated Affinity Maximization (TAM) that learns tailored node representations for our anomaly measure by maximizing the local affinity of nodes to their neighbors. Optimizing on the original graph structure can be biased by nonhomophily edges (i.e., edges connecting normal and abnormal nodes). Thus, TAM is instead optimized on truncated graphs where non-homophily edges are removed iteratively to mitigate this bias. The learned representations result in significantly stronger local affinity for normal nodes than abnormal nodes. Extensive empirical results on 10 real-world GAD datasets show that TAM substantially outperforms seven competing models, achieving over 10% increase in AUROC/AUPRC compared to the best contenders on challenging datasets. Our code is available at https://github.com/mala-lab/TAM-master/.

1 Introduction

The introduction identifies one-class homophily as an anomaly-discriminative property: normal nodes tend to connect strongly with one another, unlike abnormal nodes. It proposes local node affinity and Truncated Affinity Maximization (TAM) to use this property for unsupervised graph anomaly detection.

1 Introduction

  • GNN-based GAD methods commonly use data reconstruction [11] [59] or self-supervised objectives [17] [28] [63] to learn node representations.The introduction describes graph structure and node-attribute reconstruction, as well as proxy tasks such as neighbor-hop and node–subgraph relationship prediction.Source: §1 · p. 1
  • Normal nodes tend to have stronger connections or affinity with one another than abnormal nodes, a one-class homophily pattern observed in real-world GAD datasets.The paper reports this pattern in datasets with synthetic or real anomalies.Source: §1 · pp. 1–2
  • Local node affinity scores nodes as more anomalous when they are less affiliated with their neighbors, using similarity on node attributes or representations.The paper notes that abnormal nodes may still connect to neighbors with similar abnormal behaviors.Source: §1 · p. 2
  • TAM learns tailored node representations by maximizing local affinity on truncated graphs, reducing bias from edges connecting normal and abnormal nodes.The paper identifies LAMNet and Normal Structure-preserved Graph Truncation (NSGT) as components implementing TAM.Source: §1 · p. 2
  • On six real-world GAD datasets, TAM substantially outperforms seven competing models.The stated contributions include LAMNet and NSGT as TAM components.Source: §1 · p. 2

2 Related Work

Prior graph anomaly detection work includes shallow methods, GNN-based reconstruction approaches, and non-reconstruction self-supervised approaches. TAM differs by directly optimizing an explicitly defined local-affinity anomaly measure rather than relying on reconstruction or a proxy task.

2 Related Work

  • Shallow graph anomaly detection methods can be bottlenecked by limited representation power for rich graph semantics, high-dimensional attributes, and sparse structures.Examples named include Radar, AMEN [43], and ANOMALOUS.Source: §2 · pp. 2–3
  • GNN-based reconstruction methods such as DOMINANT use graph auto-encoders, but may overfit and struggle to learn discriminative representations.Other approaches add mechanisms such as attention, sampling, edge removal, or residual information.Source: §2 · p. 3
  • TAM defines an anomaly measure from local node affinity, unlike reconstruction methods that reconstruct a node’s structure from neighbor similarities.Both approaches use neighborhood information, but they are learned with different objectives.Source: §2 · p. 3
  • Non-reconstruction self-supervised GAD methods use proxy tasks such as contrastive learning or classification [53], and their performance depends on the task’s relation to anomaly detection.Examples include CoLA [28], SL-GAD [63], and hop-count prediction in HCM-A [17].Source: §2 · p. 3
  • Unlike proxy-task approaches, TAM’s unsupervised optimization is directly driven by its explicitly defined anomaly measure.The paper presents this as enabling end-to-end optimization of that measure.Source: §2 · p. 3

3 Method

TAM uses local node affinity to score anomalies and learns representations that distinguish normal from abnormal nodes by maximizing affinity on iteratively truncated graphs. NSGT reduces bias from non-homophily edges, while sequential truncation and an ensemble use multiple graph views.

3.1 The Proposed TAM Approach

  • TAM learns tailored representations by maximizing local affinity on NSGT-truncated graphs, then ensembles models to use truncation randomness for unsupervised graph anomaly detection.LAMNet performs affinity maximization on sequentially truncated graphs; NSGT iteratively removes edges with probability proportional to connected-node distance.Source: §3.1 · p. 4, Figure 2 · p. 4

3.2 Local Node Affinity as Anomaly Measure

  • Local node affinity is the average similarity to a node’s neighbors, and its opposite defines the anomaly score: weaker affinity indicates greater abnormality.The paper contrasts this measure with reconstruction-error scoring and uses it to exploit one-class homophily without class labels.Source: §3.2 · p. 4

3.3 TAM: Truncated Affinity Maximization

  • LAMNet learns GNN representations that maximize neighboring-node affinity while regularizing non-adjacent nodes to remain distinguishable.The first objective term maximizes local affinity in learned representations; the second is a regularizer on representations of non-adjacent nodes.Source: §3.3 · p. 5
  • NSGT probabilistically removes an edge when its attribute-space distance exceeds randomly selected thresholds for both endpoints, favoring removal of non-homophily edges while preserving homophily structure.The thresholds are sampled from ranges based on mean graph distance and each endpoint’s maximum neighbor distance; removal probability rises with distance.Source: §3.3 · p. 6
  • Sequential truncation produces progressively smaller edge sets, increasing normal-node homophily while gradually removing non-homophily edges.LAMNet message passing uses the truncated adjacency matrices to mitigate bias from non-homophily edges.Source: §3.3 · pp. 6–7
  • TAM trains LAMNets across truncation depths and independent NSGT runs, then aggregates their local-affinity anomaly scores; weaker learned affinity yields a larger score.The local-affinity objective is computed on the original adjacency matrix, while graph convolutions use truncated adjacency matrices.Source: §3.3 · p. 7

4 Experiments

Experiments evaluate TAM on six commonly used real-world GAD datasets and four large-scale graphs, alongside comparisons of anomaly types, learned representations, runtime, and model components. TAM generally performs strongly across the evaluated settings, with additional tests examining graph truncation and camouflaged attributes.

4.1 Main Results

  • TAM outperforms all seven competitors on five of six datasets in both metrics, with up to 9% AUROC and 12% AUPRC improvement on Amazon; it ranks second on Reddit.For structural and contextual anomalies, it achieves the best AUPRC in all four dataset-and-anomaly cases.Source: Table 1 · p. 8, §4.1 · p. 8, Table 2 · p. 8
  • TAM’s learned representations significantly outperform raw attributes and DGI- and GMI-learned spaces on all six datasets.Table 3 compares local node affinity across the raw-attribute and learned representation spaces.Source: Table 3 · p. 8, §4.1 · p. 8
  • TAM takes longer than DOMINANT and ComGA but runs much faster than HCM-A, CoLA, and SL-GAD on most datasets.The runtime comparison includes training and inference.Source: Table 4 · p. 9, §4.1 · p. 9

4.2 Ablation Study

  • NSGT consistently and significantly outperforms raw-graph optimization, random edge dropping, and similarity-cut truncation.Raw-graph optimization is biased by non-homophily edges; random dropping can remove homophily edges, while similarity cut can remove homophily edges associated with normal nodes.Source: Table 5 · p. 9, §4.2 · p. 9
  • LAMNet significantly and consistently outperforms scoring affinity directly after NSGT and replacing affinity maximization with graph reconstruction.Applying DOM to truncated graphs also improves over its original DOMINANT version on most datasets.Source: Table 6 · p. 9, §4.2 · p. 9
  • TAM outperforms both degree-based scoring and affinity computed on the truncated graph; aggregating scores across truncation depths improves performance.TAM-T is affected by randomness and uncertainty in graph truncation.Source: Figure 4 · p. 9, §4.2 · pp. 9–10

4.3 Performance on Large-scale Graphs

  • On four large-scale graphs, TAM performs consistently well and outperforms four comparison methods.These experiments use K = 7 for the large-scale datasets.Source: Table 7 · p. 10, §4.3 · p. 10

4.4 Handling Camouflage Attributes

  • TAM remains robust to high levels of camouflaged attributes and maintains superiority over state-of-the-art methods using original features.The tests replace 10%, 20%, or 30% of sampled abnormal-node attributes with the mean feature value of normal nodes; the authors attribute the result to NSGT removing some non-homophily edges in the local domain.Source: §4.4 · p. 10

5 Conclusion and Future Work

The paper concludes that TAM uses one-class homophily for unsupervised graph anomaly detection and outperforms seven competing detectors across 10 real-world datasets. The appendix notes that homophily patterns vary, including a dataset where normal and abnormal nodes have similar homophily distributions.

5 Conclusion and Future Work

  • TAM outperforms seven competing detectors in experiments on 10 real-world graph anomaly detection datasets.The paper also reports that one-class homophily can enhance existing GAD methods.Source: §5 · p. 10
  • TAM cannot directly handle primarily isolated nodes, and adaptations are needed for datasets with strong heterophily or very large graphs.The paper also notes that TAM requires large memory on graphs with very large node or edge sets.Source: §5 · p. 10

A One-Class Homophily Phenomenon

  • Homophily and heterophily are defined as the proportions of a node’s edges to same-class and different-class nodes, respectively.Source: A One-Class Homophily Phenomenon · p. 15
  • In YelpChi-RUR, normal and abnormal nodes have similar homophily distributions, unlike the larger distribution gaps in three other datasets.The passage identifies YelpChi-RUR as an example where one-class homophily is weak.Source: A One-Class Homophily Phenomenon · p. 15
  • Even in the weak-gap YelpChi-RUR case, normal nodes’ generally stronger homophily makes non-homophily edges more likely to be removed than homophily edges.The resulting truncated graph has stronger one-class homophily.Source: A One-Class Homophily Phenomenon · p. 15

B Description of Datasets

The evaluation spans real-world graph datasets with injected and genuine anomalies, as well as large-scale graphs. The datasets represent social, citation, shopping, review, transaction, and biological settings.

B Description of Datasets

  • The experiments include two real-world datasets with injected anomalies, four with genuine anomalies, and four large-scale graph datasets.Source: B Description of Datasets · p. 15
  • BlogCatalog and ACM use injected structural and contextual anomalies, while the described real-world datasets include fraud, banned users, and filtered or recommended reviews as anomalies.Source: B Description of Datasets · p. 15
  • The dataset settings span social and citation graphs, user-review networks, transaction networks, and a biological protein network.Examples include BlogCatalog, ACM, Amazon-UPU, T-Finance, and OGB-Protein.Source: B Description of Datasets · p. 15
  • Isolated nodes were removed before modeling because evaluation on them was considered difficult.Source: B Description of Datasets · p. 15

C.1 Hyperparameter Analysis

The analysis examines how ensemble size and regularization affect TAM. Performance generally stabilizes around four ensemble models, while regularization’s effect varies across datasets.

Ensemble Hyperparameter T

  • TAM generally performs better as ensemble parameter T increases and becomes stable around T ≈ 4.Averaging local affinity across multiple truncated graph sets is more conducive to anomaly detection.Source: §C.1 · p. 17

Regularization Hyperparameter λ

  • Regularization substantially improves BlogCatalog and Facebook, but for most genuine-anomaly datasets, increasing λ does not significantly improve effectiveness and can decrease performance.The passage attributes the gains to preventing identical node representations and says the regularization role is not reflected on Amazon, Reddit, and YelpChi because their attributes are diverse.Source: §C.1 · p. 17, Figure 7 · p. 18

C.2 Complexity Analysis

TAM’s overall time complexity combines distance calculation, graph truncation, and LAMNet computation across truncation depth and ensemble models.

C.2 Complexity Analysis

  • TAM has overall time complexity O(md0 + (N^2 + md1h + 2Nη)KT), with K as truncation depth and T as ensemble parameter.The passage says this is lower than the complexity of many existing GNN-based GAD methods using subgraph sampling and hop counting.Source: §C.2 · p. 18

C.3 Anomaly Scoring

TAM’s multi-scale anomaly scores are more stable than single-scale scores, whose performance can vary with truncation depth and dataset. Scores from different truncation scales improve detection and stabilize as depth increases.

C.3 Anomaly Scoring

  • TAM consistently and significantly outperforms Degree and TAM-T on AUPRC, with a similar pattern on AUROC.Aggregating anomaly scores across truncation scales also largely improves detection, with results stabilizing as graph truncation depth K increases.Source: §C.3 · p. 18
  • Increasing K improves single-scale performance on Amazon but often downgrades it on Reddit and YelpChi.The passage attributes the difference to more similar node attributes in Reddit and YelpChi, which restrict the effect of graph truncation.Source: §C.3 · p. 18
  • Averaging scores across LAMNets trained at all truncation depths produces a more stable multi-scale anomaly score than single-scale scoring.The single-scale effect of increasing K can be opposite across datasets.Source: §C.3 · p. 18

C.4 Shared-weights LAMNet vs. Non-shared-weights LAMNet

TAM performs comparably to or better than its shared-weight variant across six datasets. The accompanying results also favor NSGT over the tested similarity-based edge-removal ratios, and ROC and precision-recall curves are presented for TAM.

C.4 Shared-weights LAMNet vs. Non-shared-weights LAMNet

  • TAM performs consistently better than, or comparably well to, TAM-S across six datasets.TAM uses independently trained LAMNets by default, whereas TAM-S shares a single GNN backbone across LAMNets.Source: §C.4 · pp. 18–19, Table 10 · p. 20

C.5 Simple Similarity-based Non-homophily Edge Removal

  • NSGT outperforms SimilarityCut configurations removing 10% or 30% of least-similar edges.The main-text ablation also reports inferior performance for SimilarityCut removing 5% of least-similar edges.Source: §C.5 · p. 19, Table 11 · p. 20

C.6 ROC and Precision-Recall Curves

  • TAM’s ROC and precision-recall curves are shown for six datasets.The datasets are BlogCatalog, ACM, Amazon, Facebook, Reddit, and YelpChi.Source: §C.6 · p. 19

D.1 Competing Methods

The competing-method descriptions cover feature, reconstruction, contextual, contrastive, and community-based approaches. TAM’s pseudocode uses distance-based graph truncation and trains LAMNets across truncation depths to produce aggregated anomaly scores.

D.1 Competing Methods

  • iForest isolates feature-based outliers, ANOMALOUS combines attribute selection with residual analysis, and DOMINANT scores feature and structure reconstruction errors.HCM-A estimates hop counts from global and local context and uses Bayesian shortest-path prediction; CoLA and SL-GAD use contrastive scoring, with SL-GAD adding generative attribute regression.Source: §D.1 · p. 20
  • ComGA learns node representations by explicitly capturing community structure, and baseline implementations come from official pages or PyGOD.The cited implementation source passage does not identify individual source pages in this excerpt.Source: §D.1 · p. 20

D.2 Pseudo Codes of TAM.

  • NSGT takes an attributed graph and distance matrix, then removes an edge only when both connected nodes mark it for removal as non-homophilous.For each node, it samples a threshold between the mean edge distance and that node’s maximum distance, marking edges above the threshold.Source: §D.2 · p. 22
  • TAM iteratively truncates graphs, trains LAMNets to maximize affinity, and outputs aggregated anomaly scores across T sets of truncation depths.The training procedure computes distances for connected pairs and uses graph input, layer count, epochs, ensemble parameter, and truncation depth.Source: §D.2 · p. 23

Related papers

Loading 2306.00006v5…