Localizing anomalous changes in time-evolving graphs
The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Abstract
Given a time-evolving sequence of undirected, weighted graphs, we address the problem of localizing anomalous changes in graph structure over time. In this paper, we use the term `localization' to refer to the problem of identifying abnormal changes in node relationships (edges) that cause anomalous changes in graph structure. While there already exist several methods that can detect whether a graph transition is anomalous or not, these methods are not well suited for localizing the edges which are responsible for a transition being marked as an anomaly. This is a limitation in applications such as insider threat detection, where identifying the anomalous graph transitions is not sufficient, but rather, identifying the anomalous node relationships and associated nodes is key. To this end, we propose a novel, fast method based on commute time distance called CAD (Commute-time based Anomaly detection in Dynamic graphs) that detects node relationships responsible for abnormal changes in graph structure. In particular, CAD localizes anomalous edges by tracking a measure that combines information regarding changes in graph structure (in terms of commute time distance) as well as changes in edge weights. For large, sparse graphs, CAD returns a list of these anomalous edges and associated nodes in O(n\log n) time per graph instance in the sequence, where $n$ is the number of nodes. We analyze the performance of CAD on several synthetic and real-world data sets such as the Enron email network, the DBLP co-authorship network and a worldwide precipitation network data. Based on experiments conducted, we conclude that CAD consistently and efficiently identifies anomalous changes in relationships between nodes over time.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Chandola, V., Banerjee, A., & Kumar, V. (2009) · ACM Computing Surveys · doi:10.1145/1541880.1541882 · Cited by 11,687
Borgatti, S. P. (2005) · Social Networks · doi:10.1016/j.socnet.2004.11.008 · Cited by 3,191 · cited 1×
“Finally, given the commonplace nature of node centrality measures [5], we also evaluate the performance of centrality for the purpose of determining anomalous nodes.”
Background
Cited by
AddGraph: Anomaly Detection in Dynamic Graph Using Attention-based Temporal GCN
Zheng, L., Li, Z., Li, J., Li, Z., & Gao, J. (2019) · Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/614 · Cited by 268
Anomaly Detection in Dynamic Graphs via Transformer
Liu, Y., Pan, S., Wang, Y. G., Xiong, F., Wang, L., Chen, Q., & Lee, V. C. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2021.3124061 · Cited by 169
“CAD [13] detects node relationships by tracking a measure that combines information regarding changes in graph structure and changes in edge weights.”
MethodDeep Graph-level Anomaly Detection by Glocal Knowledge Distillation
Ma, R., Pang, G., Chen, L., & van den Hengel, A. (2022) · Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining · doi:10.1145/3488560.3498473 · Cited by 86
“Most existing GAD studies are to identify anomalous graph changes in a sequence of time-evolving graphs [9, 17, 21, 37, 46, 47, 52].”
BackgroundA Flexible Attentive Temporal Graph Networks for Anomaly Detection in Dynamic Networks
Zhu, D., Ma, Y., & Liu, Y. (2020) · 2020 IEEE 19th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom50675.2020.00117 · Cited by 19
“CAD [16] detects abnormal changes in the network structure based on an approximate commute time embedding method.”
MethodAnomaly Detection in Graph Structured Data: A Survey
Lamichhane, P. B., & Eberle, W. (2024) · arXiv · doi:10.48550/arxiv.2405.06172 · Cited by 4
Metadata
- Authors
- Sricharan, K., & Das, K.
- Venue
- Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
- Publisher
- ACM
- Published
- 2014-06-18
- Pages
- 1347-1358
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W1986644953
- Cited by
- 72
- References
- 2
- FWCI
- 4.15
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Localizing anomalous changes in time-evolving graphs. https://app.cochat.ai/papers/10.1145/2588555.2612184
- The paper
- Sricharan, K., & Das, K. (2014). Localizing anomalous changes in time-evolving graphs. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data. https://doi.org/10.1145/2588555.2612184
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.