Mitigating Homophily Disparity in Graph Anomaly Detection: A Scalable and Adaptive Approach
Authors: Yunhui Liu, Qizhuo Xie, Yinfeng Chen, Xudong Jin, Tao Zheng, Bin Chong, Tieke He
Organizations: State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China · National Engineering Laboratory for Big Data Analysis and Applications, Peking University, Beijing, China
Graph anomaly detection (GAD) aims to identify nodes that deviate from normal patterns in structure or features. While recent GNN-based approaches have advanced this task, they struggle with two major challenges: 1) homophily disparity, where nodes exhibit varying homophily at both class and node levels; and 2) limited scalability, as many methods rely on costly whole-graph operations. To address them, we propose SAGAD, a Scalable and Adaptive framework for GAD. SAGAD precomputes multi-hop embeddings and applies reparameterized Chebyshev filters to extract low- and high-frequency information, enabling efficient training and capturing both homophilic and heterophilic patterns. To mitigate node-level homophily disparity, we introduce an Anomaly Context-Aware Adaptive Fusion, which adaptively fuses low- and high-pass embeddings using fusion coefficients conditioned on Rayleigh Quotient-guided anomalous subgraph structures for each node. To alleviate class-level disparity, we design a Frequency Preference Guidance Loss, which encourages anomalies to preserve more high-frequency information than normal nodes. SAGAD supports mini-batch training, achieves linear time and space complexity, and drastically reduces memory usage on large-scale graphs. Theoretically, SAGAD ensures asymptotic linear separability between normal and abnormal nodes under mild conditions. Extensive experiments on 10 benchmarks confirm SAGAD's superior accuracy and scalability over state-of-the-art methods.
Figures & tables
Figure 1. (a), (b): Distribution of node homophily on Weibo and T-Finance. (c), (d): Performance disparity across node homophily quartiles (Q1 = top 25% homophily, Q4 = bottom 25%) on Weibo and T-Finance.
Figure 2. Overview of our proposed SAGAD. It consists of three main designs: 1) Dual-pass Chebyshev Polynomial Filter extracts both low- and high-frequency embeddings to capture homophilic and heterophilic patterns; 2) Anomaly Context-aware Adaptive Fusion dynamically integrates these embeddings based on node-specific structural contexts; 3) Frequency Preference Guidance Loss regularizes fusion weights to align with class-specific spectral preferences, enhancing anomaly discrimination.
Model
Reddit
Weibo
Amazon
Yelp.
T-Fin.
Ellip.
Tolo.
Quest.
DGraph.
T-Social
Avg.
GCN
4.2±0.8
86.0±6.7
32.8±1.2
16.4±2.6
60.5±10.8
43.1±4.6
33.0±3.6
6.1±0.9
2.3±0.2
8.4±3.8
29.3
GIN
4.3±0.6
67.6±7.4
75.4±4.3
23.7±5.4
44.8±7.1
40.1±3.2
31.8±3.2
6.7±1.1
2.0±0.1
6.2±1.7
30.3
SAGE
4.5±0.6
58.5±6.2
42.5±6.1
20.9±3.5
11.7±5.2
43.1±5.6
34.0±2.1
5.5±1.3
2.0±0.2
7.8±1.3
23.0
GAT
4.7±0.7
73.3±7.3
81.6±1.7
25.0±2.9
28.9±8.6
44.2±6.6
33.0±2.0
7.3±1.2
2.2±0.2
9.2±2.0
30.9
H2GCN
4.6±0.7
76.5±5.8
80.9±2.6
24.4±3.7
34.2±10.1
46.8±8.1
33.6±2.2
7.4±1.3
2.4±0.3
10.4±1.9
32.1
ACM
4.4±0.7
66.0±8.7
54.0±19.0
21.4±2.7
29.2±16.8
55.1±4.8
34.4±3.5
7.2±1.9
2.2±0.4
6.0±1.6
28.0
Table 1. Comparison of AUPRC for each model. "-" denotes "out of memory".
Dataset
Weibo
T-Finance
Amazon
YelpChi
Q1-Q2
Q1-Q3
Q1-Q4
Q1-Q2
Q1-Q3
Q1-Q4
Q1-Q2
Q1-Q3
Q1-Q4
Q1-Q2
Q1-Q3
Q1-Q4
AMNet
9.40
32.88
27.32
3.44
30.27
58.66
5.43
20.65
47.10
-0.71
-0.19
0.54
BWGNN
10.73
39.18
44.89
9.47
56.56
86.60
8.89
26.14
56.74
-1.09
-0.60
0.43
ConsisGAD
13.43
43.95
54.96
3.75
25.04
89.25
-3.24
14.63
39.47
-1.75
-0.19
-0.06
SAGAD
1.95
7.37
35.26
1.46
26.26
70.22
5.42
14.95
46.93
4.30
6.25
7.07
Table 2. Performance gaps (AUPRC difference) between Q1 and other quartiles across datasets. Lower absolute values indicate smaller homophily disparity.
Figure 3. Performance disparity across node homophily quartiles (Q1 = top 25% homophily, Q4 = bottom 25%) on Amazon and YelpChi.
Model
YelpChi
T-Social
Time (s)
Mem. (MB)
Time (s)
Mem. (MB)
GCN
1.93
547.73
61.75
13241.26
AMNet
4.09
773.38
213.82
18970.04
BWGNN
2.66
729.17
112.01
16146.46
GHRN
3.22
3360.71
161.00
28080.33
ConsisGAD
89.28
16390.42
1674.87
14145.61
Table 3. Scalability comparison in terms of training time and GPU memory.
ZL
ZH
GRQ
Lfpg
Fusion
Reddit
Amazon
Yelp.
T-Fin.
Ellip.
Tolo.
DGraph.
AUPRC
AUROC
AUPRC
AUROC
AUPRC
AUROC
AUPRC
AUROC
AUPRC
AUROC
AUPRC
AUROC
AUPRC
AUROC
✓
✓
✓
✓
Eq. (7)
5.6±0.6
66.5±3.0
84.7±2.0
94.5±2.1
27.8±2.4
68.8±2.5
82.8±1.0
94.4±0.4
57.1±4.1
90.9±0.9
40.5±1.6
73.6±0.8
2.6±0.3
70.8±1.9
✓
✓
✓
✗
Eq. (7)
5.3±0.7
63.9±3.6
83.8±2.4
94.3±1.9
26.6±1.7
68.1±2.5
78.1±6.1
93.2±2.1
56.6±6.0
90.5±1.1
35.0±2.0
69.1±1.8
2.3±0.2
69.6±1.3
✓
✓
✢
✓
Eq. (7)
5.5±0.7
65.6±2.9
83.0±2.3
93.8±2.0
23.1±2.8
63.9±4.3
78.1±4.3
93.2±1.3
51.9±3.9
90.1±1.2
33.7±1.3
68.2±1.7
2.2±0.2
69.0±1.3
✓
✓
✗
✓
Eq. (7)
5.2±0.7
63.8±3.7
83.2±2.0
93.9±2.1
23.1±2.8
63.8±4.3
79.1±3.6
93.3±1.3
51.7±3.3
90.2±1.2
34.0±1.4
68.8±1.2
2.2±0.2
69.1±1.5
✓
✓
✗
✗
Mean
5.1±0.7
66.0±2.4
82.3±3.3
93.9±2.0
23.1±3.0
64.1±4.8
67.1±0.9
88.2±1.3
52.5±3.8
90.4±0.7
33.2±1.2
68.3±1.4
2.2±0.2
68.8±1.4
Table 4. Ablation study on each component of our SAGAD in terms of AUPRC and AUROC.
Figure 4. Visualization of the learned coefficients for the top 8 dimensions. Nodes ( a1,a2,a3 ) and ( n1,n2,n3 ) are randomly selected abnormal and normal nodes, respectively.
Dataset
#Nodes
#Edges
#Feat.
Anomaly
h
ha
hn
Relation Concept
Feature Type
Reddit
10,984
168,016
64
3.3%
0.947
0.000
0.994
Under Same Post
Text Embedding
Weibo
8,405
407,963
400
10.3%
0.977
0.858
0.977
Under Same Hashtag
Text Embedding
Amazon
11,944
4,398,392
25
9.5%
0.954
0.102
0.968
Review Correlation
Misc. Information
YelpChi
45,954
3,846,979
32
14.5%
0.773
0.195
0.867
Reviewer Interaction
Misc. Information
T-Finance
39,357
21,222,543
10
4.6%
0.971
0.543
0.976
Transaction Record
Misc. Information
Elliptic
203,769
234,355
166
9.8%
0.970
0.234
0.985
Payment Flow
Misc. Information
Table 5. Dataset statistics including the number of nodes and edges, the node feature dimension, the ratio of anomalies, the homophily ratio, the concept of relations, and the type of node features. h , ha , and hn represent the edge homophily, the average homophily for abnormal nodes, and the average homophily for normal nodes, respectively. As we can see, ha is much smaller than hn , indicating that abnormal nodes exhibit significantly lower homophily compared to normal nodes. "Misc." refers to node features that are heterogeneous attributes, which may include categorical, numerical, and temporal information.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5. How the AUPRC score varies with different values of pa and pn .
Model
Reddit
Weibo
Amazon
Yelp.
T-Fin.
Ellip.
Tolo.
Quest.
DGraph.
T-Social
Avg.
GCN
56.9±5.9
93.5±6.6
82.0±0.3
51.2±3.7
88.3±2.5
86.2±1.9
64.2±4.8
60.0±2.2
66.2±2.5
71.6±10.4
72.0
GIN
60.0±4.1
83.8±8.3
91.6±1.7
62.9±7.3
84.5±4.5
88.2±0.9
66.8±5.2
62.2±2.2
65.7±1.8
70.4±7.4
73.6
SAGE
60.3±3.8
81.8±6.5
81.4±2.0
58.9±4.3
68.9±5.5
87.4±1.0
67.6±4.2
61.2±2.9
64.8±3.3
72.0±2.9
70.4
GAT
60.5±3.9
86.4±7.7
92.4±1.9
65.6±4.0
85.0±4.5
88.5±2.1
68.1±3.0
62.3±1.4
67.2±1.9
75.4±4.8
75.1
H2GCN
60.3±4.4
87.8±5.7
91.4±2.4
65.0±4.5
86.3±3.9
89.3±2.1
69.1±2.5
61.9±4.2
69.0±1.9
74.5±3.7
75.5
ACM
60.0±4.3
92.5±2.9
81.8±7.9
61.3±3.8
82.2±8.1
90.0±0.8
69.3±4.2
60.8±4.1
67.6±5.3
68.3±4.9
73.3
Appendix
Table 6. Comparison of AUROC for each model. "-" denotes "out of memory".
Model
Reddit
Weibo
Amazon
Yelp.
T-Fin.
Ellip.
Tolo.
Quest.
DGraph.
T-Social
Avg.
GCN
6.2±2.2
79.2±4.3
36.9±2.6
16.9±3.0
60.6±7.6
49.7±4.2
33.4±3.5
9.8±1.2
3.6±0.4
10.2±8.1
30.6
GIN
4.8±1.9
66.5±7.3
70.4±5.7
26.5±6.1
54.4±5.0
47.6±3.1
33.6±3.0
10.3±1.1
2.1±0.5
5.3±2.9
32.2
SAGE
5.8±0.8
63.4±6.0
48.0±5.6
22.9±3.6
18.5±9.4
48.2±5.8
35.2±2.2
8.8±2.5
2.5±0.7
9.5±2.9
26.3
GAT
6.5±2.3
70.2±4.6
77.1±1.7
28.1±3.4
36.2±10.3
51.4±5.8
35.1±1.8
10.9±0.9
3.1±0.7
11.6±3.0
33.0
H2GCN
5.8±2.2
71.1±4.9
77.5±2.5
27.2±4.2
43.6±11.7
53.9±6.9
35.2±2.0
11.2±1.9
3.4±0.9
14.9±2.9
34.4
ACM
5.4±1.8
70.7±9.5
56.1±14.2
23.9±3.8
37.2±19.3
55.2±3.3
35.8±4.2
11.4±2.6
1.9±0.7
8.1±1.8
30.6
Appendix
Table 7. Comparison of Rec@K for each model. "-" denotes "out of memory".
Graph anomaly detection aims to identify nodes that deviate from normal behavioral patterns within graphs. However, existing methods largely rely on the homophily assumption, which makes it difficult to distinguish spurious affinities and to capture the diverse behaviors of normal nodes,limiting their robustness in complex real-world scenarios. To address this problem, we propose RagGAD, an unsupervised graph anomaly detection framework based on rationale-aware conditional Gaussian mixture normalizing flow. RagGAD introduces an adaptive rationale disentangler to disentangle stable rationales from spurious correlations within node interrelationships, and further decomposes stable rationales into robust and fragile components. The learned rationales capture underlying interaction patterns that characterize normal behaviors under varying conditions, while anomalies emerge as deviations associated with unstable or spurious correlations. To model the intricate distributions of normal and abnormal nodes, RagGAD integrates rationale-non-rationale Gaussian mixture modeling with a robust-fragile rationale mixture learning strategy. By mitigating spurious homophilic correlations and embracing the heterogeneity of normal patterns, RagGAD identifies anomalies as low-density regions within a structure-aware distribution space. Extensive experiments on multiple benchmark datasets demonstrate that RagGAD outperforms state-of-the-art methods.
Junxin Lu, Jing Zhao, Shiliang Sun
School of Computer Science and Technology, East China Normal University, Shanghai 200062, China · State Key Laboratory of Submarine Geoscience, School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, 800 Dongchuan Road, Shanghai 200240, China
Graph anomaly detection aims to identify irregular patterns in graph-structured data. Most unsupervised GNN-based methods rely on the homophily assumption that connected nodes share similar attributes. However, real-world graphs often exhibit attribute-level heterophily, where connected nodes have dissimilar attributes. Our analysis of attribute-level heterophily graphs reveals two phenomena indicating that current approaches are not practical for unsupervised graph anomaly detection: 1) attribute similarities between connected nodes show nearly identical distributions across different connected node pair types, and 2) anomalies cause consistent variation trends between the graph with and without anomalous edges in the low- and high-frequency components of the spectral energy distributions, while the mid-part exhibits more erratic variations. Based on these observations, we propose NK-GAD, a neighbor knowledge-enhanced unsupervised graph anomaly detection framework. NK-GAD integrates a joint encoder capturing both similar and dissimilar neighbor features, a neighbor reconstruction module modeling normal distributions, a center aggregation module refining node features, and dual decoders for reconstructing attributes and structures. Experiments on seven datasets show NK-GAD achieves an average 3.29% AUC improvement.
Zehao Wang, Lanjun Wang
College of Intelligence and Computing, Tianjin University, Tianjin, China · School of New Media and Communication, Tianjin University, Tianjin, China
Graph anomaly detection (GAD) aims to identify irregular nodes or structures in attributed graphs. Neighbor information, which reflects both structural connectivity and attribute consistency with surrounding nodes, is essential for distinguishing anomalies from normal patterns. Although recent graph neural network (GNN)-based methods incorporate such information through message passing, they often fail to explicitly model its effect or interaction with attributes, limiting detection performance. This work introduces NeiGAD, a novel plug-and-play module that captures neighbor information through spectral graph analysis. Theoretical insights demonstrate that eigenvectors of the adjacency matrix encode local neighbor interactions and progressively amplify anomaly signals. Based on this, NeiGAD selects a compact set of eigenvectors to construct efficient and discriminative representations. Experiments on eight real-world datasets show that NeiGAD consistently improves detection accuracy and outperforms state-of-the-art GAD methods. These results demonstrate the importance of explicit neighbor modeling and the effectiveness of spectral analysis in anomaly detection. Code is available at: https://github.com/huafeihuang/NeiGAD.
Qing Qing, Huafei Huang, Mingliang Hou +2
College of Computer Science and Technology, Jilin University, Changchun 130012, China · School of Computer Science and Information Technology, Adelaide University, SA 5095, Australia · Guangdong Institute of Smart Education, Jinan University, Guangzhou 510632, China +1