NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks

By Wenchao Yu, Wei Cheng, Charu C. Aggarwal, Kai Zhang, Haifeng Chen, Wei Wang. Knowledge Discovery and Data Mining, 2018

406 citations recorded by the source corpus.

Massive and dynamic networks arise in many practical applications such as social media, security and public health. Given an evolutionary network, it is crucial to detect structural anomalies, such as vertices and edges whose "behaviors'' deviate from underlying majority of the network, in a real-time fashion. Recently, network embedding has proven a powerful tool in learning the low-dimensional representations of vertices in networks that can capture and preserve the network structure. However, most existing network embedding approaches are designed for static networks, and thus may not be perfectly suited for a dynamic environment in which the network representation has to be constantly updated. In this paper, we propose a novel approach, NetWalk, for anomaly detection in dynamic networks by learning network representations which can be updated dynamically as the network evolves. We first encode the vertices of the dynamic network to vector representations by clique embedding, which jointly minimizes the pairwise distance of vertex representations of each walk derived from the dynamic networks, and the deep autoencoder reconstruction error serving as a global regularization. The vector representations can be computed with constant space requirements using reservoir sampling. On the basis of the learned low-dimensional vertex representations, a clustering-based technique is employed to incrementally and dynamically detect network anomalies. Compared with existing approaches, NetWalk has several advantages: 1) the network embedding can be updated dynamically, 2) streaming network nodes and edges can be encoded efficiently with constant memory space usage, 3). flexible to be applied on different types of networks, and 4) network anomalies can be detected in real-time. Extensive experiments on four real datasets demonstrate the effectiveness of NetWalk.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/68f6fe021bd8efd8baf648138a8fe2182858e7cb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Temporal Graph Networks for Deep Learning on Dynamic Graphs (2020, background): “Learning on dynamic graphs is relatively recent, and most works are limited to the setting of discrete-time dynamic graphs represented as a sequence of snapshots of the graph over time [37, 15, 69, 54, 48, 71].”
Neural Networks and Deep Learning (2018, neutral): “Various types of network embeddings are discussed in [62, 512, 547, 548].”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, background): “This network has 1,899 nodes and 59,835 edges [151, 196, 248].”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “To mitigate this challenge, the ANOS ND model NetWalk [84] is also capable of detecting anomalous edges in dynamic graphs.”
Deep Anomaly Detection on Attributed Networks (2019, background): “Even though the recently proposed NetWalk [35] combines network representation learning and anomaly detection in a joint framework, it is proposed to solve the problem of anomaly detection on dynamic networks, which cannot be directly applied to our attributed network scenario.”
Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning (2021, methodology): “For dynamic networks, NetWalk [50] learns dynamically network representations with random walk sampling and autoencoder model, and detects anomalies with a clustering-based detector.”
CGLB: Benchmark Tasks for Continual Graph Learning (2022, background): “Finally, the essential difference between CGL, dynamic graph learning [14, 48, 18, 60, 35, 66, 33, 13, 5], and few-shot graph learning [65, 16, 57, 43] is worth noting.”