arxiv: 2604.15668 · v1 · submitted 2026-04-17 · 💻 cs.LG

Recognition: unknown

NK-GAD: Neighbor Knowledge-Enhanced Unsupervised Graph Anomaly Detection

Zehao Wang , Lanjun Wang

Authors on Pith no claims yet

Pith reviewed 2026-05-10 09:04 UTC · model grok-4.3

classification 💻 cs.LG

keywords graph anomaly detectionunsupervised learningattribute heterophilygraph neural networksspectral analysisneighbor reconstructiondual decoders

0 comments

The pith

NK-GAD improves unsupervised graph anomaly detection on heterophilous graphs by jointly encoding similar and dissimilar neighbors and using dual reconstruction.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that common unsupervised GNN methods for graph anomaly detection assume homophily, where neighbors share similar attributes, but many real graphs instead show attribute-level heterophily with dissimilar neighbors. Analysis of such graphs reveals two stable patterns: attribute similarity distributions between connected nodes look nearly identical no matter the pair type, and anomalies produce consistent shifts in low- and high-frequency spectral energy while the middle frequencies vary more randomly. To exploit these patterns, NK-GAD adds a joint encoder that handles both similar and dissimilar neighbor features, a module that reconstructs normal neighbor distributions, center feature aggregation, and separate decoders for attributes and graph structure. Experiments across seven datasets confirm an average 3.29 percent AUC gain, making the approach more reliable for label-free detection in complex networks.

Core claim

By observing that attribute similarities between connected nodes follow nearly identical distributions across pair types and that anomalies induce predictable variation trends in low- and high-frequency spectral components, the authors establish that a neighbor-knowledge framework consisting of a joint encoder, neighbor reconstruction module, center aggregation, and dual decoders can capture both homophilous and heterophilous signals to improve unsupervised anomaly detection.

What carries the argument

The NK-GAD framework, whose joint encoder captures both similar and dissimilar neighbor features, neighbor reconstruction module models normal distributions, center aggregation refines features, and dual decoders reconstruct attributes and structures.

If this is right

The method yields consistent AUC gains across seven datasets without requiring anomaly labels.
Dual reconstruction of attributes and structure allows separate modeling of content and connectivity anomalies.
Center aggregation after joint encoding produces refined node representations that better separate normal and anomalous nodes.
The approach remains fully unsupervised while explicitly handling the heterophily that defeats standard homophily-based GNN detectors.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The spectral variation observation could be turned into an explicit frequency-based anomaly score that operates independently of the reconstruction losses.
If the uniform similarity distribution holds more broadly, many existing homophily-regularized GNNs may need similar dual-path encoders for other tasks such as node classification on heterophilous graphs.
The neighbor reconstruction module could be adapted to detect anomalous edges rather than nodes by treating edge reconstruction error as the primary signal.

Load-bearing premise

The two observed patterns in attribute-level heterophily graphs are general properties that the joint encoder, neighbor reconstruction, center aggregation, and dual decoders reliably address.

What would settle it

Running the same experiments on additional heterophilous graphs where the similarity distributions or spectral energy trends deviate from the described patterns and finding no AUC improvement would falsify the claim.

Figures

Figures reproduced from arXiv: 2604.15668 by Lanjun Wang, Zehao Wang.

**Figure 2.** Figure 2: Graph spectral energy distribution for the graphs w/ and w/o anomalous [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: Overview of NK-GAD. NK-GAD integrates four core components to re [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: Impacts of λjoint in the joint graph convolutional encoder and λca in the center aggregation module across datasets. 5.5 Computational Complexity Analysis We further analyze the computational complexity of the proposed NK-GAD. The joint graph convolutional encoder processes low-pass and high-pass filters over L and L ′ layers, respectively. Each layer involves sparse graph convolution with complexity O(|E|… view at source ↗

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

NK-GAD gives a small average AUC bump on heterophilic graph anomaly detection by adding joint encoding and dual reconstruction, but the two motivating observations look dataset-specific and the experiments need more controls to hold up.

read the letter

The paper's core move is to drop the homophily assumption that most unsupervised GNN anomaly detectors still use. The authors point out two patterns in attribute-level heterophily graphs: connected node pairs show nearly identical attribute similarity distributions no matter the pair type, and anomalies produce steady shifts in low- and high-frequency spectral energy while the middle band varies more. They then build NK-GAD with a joint encoder that handles both similar and dissimilar neighbors, a neighbor reconstruction step that models normal distributions, a center aggregation step, and dual decoders for attributes and structure. That combination is what is actually new here, and it is a reasonable engineering response to the heterophily problem they flag. The reported 3.29% average AUC lift across seven datasets is the main empirical result, and it is presented as evidence that the modules help on real heterophilic data. That is worth noting for anyone who works on graph anomaly detection where homophily fails. The soft spots are straightforward. The two phenomena are treated as general properties, yet the abstract gives no quantitative check that they appear consistently across the datasets or that removing any module erases the gain. Without error bars, significance tests, or a clear list of baselines and hyper-parameter choices, it is hard to know how much of the lift is from the new pieces versus tuning or dataset quirks. The method itself is a collection of existing ideas stitched together rather than a new theoretical claim, so the justification rests heavily on those observations holding up. This is the kind of paper that matters to the graph anomaly detection community, especially people who already know the homophily limitation and want practical fixes for heterophilic cases. A reader who cares about incremental improvements on standard benchmarks will find the dataset results and module descriptions useful. It is coherent on its own terms and engages the literature honestly, so it deserves a serious referee even though the gains are modest and the supporting analysis needs tightening. I would send it out for review rather than desk reject.

Referee Report

2 major / 2 minor

Summary. The manuscript presents NK-GAD, a framework for unsupervised graph anomaly detection in attribute-level heterophily graphs. It first analyzes two phenomena: nearly identical attribute similarity distributions across node pair types and consistent low/high-frequency spectral energy variations caused by anomalies. Based on this, it introduces a joint encoder for similar and dissimilar neighbors, a neighbor reconstruction module, center aggregation, and dual decoders for attribute and structure reconstruction. Experiments on seven datasets demonstrate an average 3.29% AUC improvement over existing methods.

Significance. If the observed phenomena hold generally and the proposed modules effectively exploit them, NK-GAD could advance unsupervised GAD by relaxing the homophily assumption common in GNN methods. The multi-dataset evaluation is a positive aspect, providing some evidence of robustness. The contribution is primarily empirical and engineering-oriented, with potential impact in applications like fraud detection or network security where graphs are heterophilic.

major comments (2)

§3 (Observations): The two phenomena are illustrated using the seven evaluation datasets, but the paper does not demonstrate that these are general properties of attribute-level heterophily graphs beyond these datasets. This is load-bearing for the motivation of the joint encoder and reconstruction modules in §4, as the design is directly derived from these observations.
§5 (Experiments): The average 3.29% AUC improvement is reported without accompanying standard deviations, error bars, or statistical significance tests across the seven datasets. This makes it difficult to determine if the improvement is consistent and reliable or influenced by specific hyperparameter choices.

minor comments (2)

The description of the dual decoders could benefit from clearer mathematical formulation to distinguish attribute and structure reconstruction losses.
Additional references to recent work on heterophily-aware GNNs would help contextualize the contribution.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments on our manuscript. We address each major comment point by point below, outlining planned revisions where appropriate.

read point-by-point responses

Referee: §3 (Observations): The two phenomena are illustrated using the seven evaluation datasets, but the paper does not demonstrate that these are general properties of attribute-level heterophily graphs beyond these datasets. This is load-bearing for the motivation of the joint encoder and reconstruction modules in §4, as the design is directly derived from these observations.

Authors: We agree that the observations are derived from the seven evaluation datasets and that broader generality is not proven. These datasets are standard, diverse benchmarks spanning multiple domains with varying heterophily levels. In the revision, we will clarify in Section 3 that the phenomena motivate the design based on empirical patterns in representative heterophilic graphs, add references to related heterophily studies, and include a brief analysis on one additional synthetic heterophilic graph to illustrate the trends in a controlled setting. This strengthens the motivation section without overclaiming universality. revision: partial
Referee: §5 (Experiments): The average 3.29% AUC improvement is reported without accompanying standard deviations, error bars, or statistical significance tests across the seven datasets. This makes it difficult to determine if the improvement is consistent and reliable or influenced by specific hyperparameter choices.

Authors: We agree that variability measures and significance testing are necessary for assessing reliability. In the revised manuscript, we will report mean AUC scores with standard deviations from five independent runs using different random seeds, include error bars in the performance tables and figures, and add statistical significance tests (e.g., paired t-tests or Wilcoxon signed-rank tests) comparing NK-GAD against baselines. Hyperparameter sensitivity will also be briefly discussed. revision: yes

Circularity Check

0 steps flagged

No significant circularity; empirical method motivated by independent observations.

full rationale

The paper identifies two phenomena via analysis of heterophily graphs, then constructs NK-GAD (joint encoder, reconstruction module, center aggregation, dual decoders) to exploit them, and reports empirical AUC gains on seven datasets. No equations, self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear. The claimed improvement is presented as an experimental outcome rather than a derivation that collapses to its inputs by construction. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 4 invented entities

The central claim rests on the domain assumption that real-world graphs exhibit attribute-level heterophily with the two stated phenomena, plus the engineering assumption that the four newly introduced modules correctly exploit those phenomena. No numerical free parameters are mentioned in the abstract. The modules themselves function as invented methodological components without independent falsifiable evidence supplied in the summary.

axioms (2)

domain assumption Real-world graphs frequently exhibit attribute-level heterophily where connected nodes have dissimilar attributes.
Explicitly stated as the motivation for moving beyond the homophily assumption.
domain assumption The two observed phenomena (identical similarity distributions across pair types and consistent low/high-frequency spectral shifts from anomalies) hold generally.
Presented as the basis for designing the NK-GAD components.

invented entities (4)

Joint encoder capturing both similar and dissimilar neighbor features no independent evidence
purpose: To process heterophilic neighbor information
New architectural component introduced to address the heterophily observations.
Neighbor reconstruction module modeling normal distributions no independent evidence
purpose: To reconstruct typical neighbor patterns for anomaly scoring
New module proposed as part of the framework.
Center aggregation module refining node features no independent evidence
purpose: To refine node representations
New aggregation step in the pipeline.
Dual decoders for reconstructing attributes and structures no independent evidence
purpose: To reconstruct both node attributes and graph structure
New dual-decoder design.

pith-pipeline@v0.9.0 · 5489 in / 1663 out tokens · 38621 ms · 2026-05-10T09:04:07.143343+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

36 extracted references · 3 canonical work pages · 2 internal anchors

[1]

In: Proceedings of the 13th international conference on web search and data mining

Bandyopadhyay,S., N, L.,Vivek,S.V., Murty,M.N.: Outlier resistant unsupervised deep architectures for attributed network embedding. In: Proceedings of the 13th international conference on web search and data mining. pp. 25–33 (2020)

2020
[2]

In: The Twelfth International Conference on Learning Representations (2024)

Chen, J., Zhu, G., Yuan, C., Huang, Y.: Boosting graph anomaly detection with adaptive message passing. In: The Twelfth International Conference on Learning Representations (2024)

2024
[3]

In: Proceedings of the 29th ACM Interna- tionalConferenceonInformation&KnowledgeManagement.pp.1989–1992(2020)

Chen, Z., Liu, B., Wang, M., Dai, P., Lv, J., Bo, L.: Generative adversarial at- tributed network anomaly detection. In: Proceedings of the 29th ACM Interna- tionalConferenceonInformation&KnowledgeManagement.pp.1989–1992(2020)

1989
[4]

In: Proceedings of the 2019 SIAM international conference on data mining

Ding, K., Li, J., Bhanushali, R., Liu, H.: Deep anomaly detection on attributed net- works. In: Proceedings of the 2019 SIAM international conference on data mining. pp. 594–602. SIAM (2019)

2019
[5]

In: Proceedings of the ACM on Web Conference 2025

Dong, X., Zhang, X., Sun, Y., Chen, L., Yuan, M., Wang, S.: Smoothgnn: Smoothing-aware gnn for unsupervised node anomaly detection. In: Proceedings of the ACM on Web Conference 2025. pp. 1225–1236 (2025) NK-GAD: Unsupervised Graph Anomaly Detection 15

2025
[6]

IEEE Signal processing magazine37(6), 117–127 (2020)

Dong, X., Thanou, D., Toni, L., Bronstein, M., Frossard, P.: Graph signal process- ing for machine learning: A review and new perspectives. IEEE Signal processing magazine37(6), 117–127 (2020)

2020
[7]

In: ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)

Fan, H., Zhang, F., Li, Z.: Anomalydae: Dual autoencoder for anomaly detection on attributed networks. In: ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). pp. 5685–5689. IEEE (2020)

2020
[8]

In: Proceedings of the ACM Web Conference 2023

Gao, Y., Wang, X., He, X., Liu, Z., Feng, H., Zhang, Y.: Addressing heterophily in graph anomaly detection: A perspective of graph spectrum. In: Proceedings of the ACM Web Conference 2023. pp. 1528–1538 (2023)

2023
[9]

International Journal of Electrical Engineering & Education 60(1_suppl), 1736–1749 (2023)

HC, M.: Retracted: Bmadsn: Big data multi-community anomaly detection in social networks. International Journal of Electrical Engineering & Education 60(1_suppl), 1736–1749 (2023)

2023
[10]

In: Proceedings of the AAAI Conference on Artificial Intelligence

He, J., Xu, Q., Jiang, Y., Wang, Z., Huang, Q.: Ada-gad: Anomaly-denoised au- toencoders for graph anomaly detection. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 38, pp. 8481–8489 (2024)

2024
[11]

In: Proceedings of the ACM Web Conference 2023

Huang, J., Du, L., Chen, X., Fu, Q., Han, S., Zhang, D.: Robust mid-pass filtering graph convolutional networks. In: Proceedings of the ACM Web Conference 2023. pp. 328–338 (2023)

2023
[12]

Advances in Neural Information Processing Systems35, 22765–22777 (2022)

Huang,X.,Yang,Y.,Wang,Y.,Wang,C.,Zhang,Z.,Xu,J.,Chen,L.,Vazirgiannis, M.: Dgraph: A large-scale financial dataset for graph anomaly detection. Advances in Neural Information Processing Systems35, 22765–22777 (2022)

2022
[13]

Semi-Supervised Classification with Graph Convolutional Networks

Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016)

work page internal anchor Pith review arXiv 2016
[14]

Physica A: Statistical Mechanics and its Applications553, 124289 (2020)

Kumar, A., Singh, S.S., Singh, K., Biswas, B.: Link prediction techniques, ap- plications, and performance: A survey. Physica A: Statistical Mechanics and its Applications553, 124289 (2020)

2020
[15]

In: Proceedings of the 25th ACM SIGKDD inter- national conference on knowledge discovery & data mining

Kumar, S., Zhang, X., Leskovec, J.: Predicting dynamic embedding trajectory in temporal interaction networks. In: Proceedings of the 25th ACM SIGKDD inter- national conference on knowledge discovery & data mining. pp. 1269–1278 (2019)

2019
[16]

In: IJCAI

Li, J., Dani, H., Hu, X., Liu, H.: Radar: Residual analysis for anomaly detection in attributed networks. In: IJCAI. vol. 17, pp. 2152–2158 (2017)

2017
[17]

Advances in Neural Information Processing Systems35, 27021–27035 (2022)

Liu, K., Dou, Y., Zhao, Y., Ding, X., Hu, X., Zhang, R., Ding, K., Chen, C., Peng, H., Shu, K., et al.: Bond: Benchmarking unsupervised outlier node detection on static attributed graphs. Advances in Neural Information Processing Systems35, 27021–27035 (2022)

2022
[18]

In: Proceedings of the web conference 2021

Liu, Y., Ao, X., Qin, Z., Chi, J., Feng, J., Yang, H., He, Q.: Pick and choose: a gnn-based imbalanced learning approach for fraud detection. In: Proceedings of the web conference 2021. pp. 3168–3177 (2021)

2021
[19]

Advances in Neural Information Processing Systems36(2024)

Luan, S., Hua, C., Xu, M., Lu, Q., Zhu, J., Chang, X.W., Fu, J., Leskovec, J., Precup, D.: When do graph neural networks help with node classification? inves- tigating the homophily principle on node distinguishability. Advances in Neural Information Processing Systems36(2024)

2024
[20]

In: 2013 IEEE 29th international conference on data engi- neering workshops (ICDEW)

Müller, E., Sánchez, P.I., Mülle, Y., Böhm, K.: Ranking outlier nodes in subspaces of attributed graphs. In: 2013 IEEE 29th international conference on data engi- neering workshops (ICDEW). pp. 216–222. IEEE (2013)

2013
[21]

Deep graph anomaly detection: A survey and new perspectives,

Qiao, H., Tong, H., An, B., King, I., Aggarwal, C., Pang, G.: Deep graph anomaly detection: A survey and new perspectives. arXiv preprint arXiv:2409.09957 (2024)

work page arXiv 2024
[22]

In: Proceedings of the 17th ACM International Conference on Web Search and Data Mining

Roy, A., Shu, J., Li, J., Yang, C., Elshocht, O., Smeets, J., Li, P.: Gad-nr: Graph anomaly detection via neighborhood reconstruction. In: Proceedings of the 17th ACM International Conference on Web Search and Data Mining. pp. 576–585 (2024) 16 Zehao Wang and Lanjun Wang

2024
[23]

Sánchez, P.I., Müller, E., Laforet, F., Keller, F., Böhm, K.: Statistical selection of congruentsubspacesforminingattributedgraphs.In:2013IEEE13thinternational conference on data mining. pp. 647–656. IEEE (2013)

2013
[24]

Transportation research part C: emerging technologies145, 103921 (2022)

Shaygan, M., Meese, C., Li, W., Zhao, X.G., Nejad, M.: Traffic prediction us- ing artificial intelligence: Review of recent advances and emerging opportunities. Transportation research part C: emerging technologies145, 103921 (2022)

2022
[25]

Digital signal processing107, 102802 (2020)

Stanković, L., Mandic, D., Daković, M., Scalzo, B., Brajović, M., Sejdić, E., Con- stantinides, A.G.: Vertex-frequency graph signal processing: A comprehensive re- view. Digital signal processing107, 102802 (2020)

2020
[26]

In: International Conference on Machine Learning

Tang, J., Li, J., Gao, Z., Li, J.: Rethinking graph neural networks for anomaly detection. In: International Conference on Machine Learning. pp. 21076–21089. PMLR (2022)

2022
[27]

Signal, Image and Video Processing17(4), 1053–1059 (2023)

Tekin, S.F., Kozat, S.S.: Crime prediction with graph neural networks and multi- variate normal distributions. Signal, Image and Video Processing17(4), 1053–1059 (2023)

2023
[28]

In: 2024 International Conference on Science Technology Engineering and Management (ICSTEM)

Thilagavathi, M., Saranyadevi, R., Vijayakumar, N., Selvi, K., Anitha, L., Sud- harson, K.: Ai-driven fraud detection in financial transactions with graph neural networks and anomaly detection. In: 2024 International Conference on Science Technology Engineering and Management (ICSTEM). pp. 1–6. IEEE (2024)

2024
[29]

Graph Attention Networks

Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. arXiv preprint arXiv:1710.10903 (2017)

work page internal anchor Pith review arXiv 2017
[30]

In: Proceedings of the 41st International Conference on Machine Learn- ing

Wang, J., Guo, Y., Yang, L., Wang, Y.: Understanding heterophily for graph neural networks. In: Proceedings of the 41st International Conference on Machine Learn- ing. Proceedings of Machine Learning Research, vol. 235, pp. 50489–50529. PMLR (21–27 Jul 2024)

2024
[31]

In: ACM SIGKDD International Con- ference on Knowledge Discovery and Data Mining (2019)

Weber, M., Domeniconi, G., Chen, J., Weidele, D.K.I., Bellei, C., Robinson, T., Leiserson, C.: Anti-money laundering in bitcoin: Experimenting with graph con- volutional networks for financial forensics. In: ACM SIGKDD International Con- ference on Knowledge Discovery and Data Mining (2019)

2019
[32]

IEEE transactions on neural networks and learning systems32(1), 4–24 (2020)

Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive sur- vey on graph neural networks. IEEE transactions on neural networks and learning systems32(1), 4–24 (2020)

2020
[33]

Machine Vision and Applications33(1), 4 (2022)

Xiao, S., Wang, S., Dai, Y., Guo, W.: Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications33(1), 4 (2022)

2022
[34]

International Journal of Advanced Computer Science and Applications14(4), 912–920 (2023)

Zardi, H., Alrajhi, H.: Anomaly discover: A new community-based approach for de- tecting anomalies in social networks. International Journal of Advanced Computer Science and Applications14(4), 912–920 (2023)

2023
[35]

In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining

Zhang, N., Jia, Q., Deng, S., Chen, X., Ye, H., Chen, H., Tou, H., Huang, G., Wang, Z., Hua, N., et al.: Alicg: Fine-grained and evolvable conceptual graph construc- tion for semantic search at alibaba. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 3895–3905 (2021)

2021
[36]

In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management

Zhao, T., Deng, C., Yu, K., Jiang, T., Wang, D., Jiang, M.: Error-bounded graph anomaly loss for gnns. In: Proceedings of the 29th ACM International Conference on Information & Knowledge Management. pp. 1873–1882 (2020)

2020