(2015)Graph-based Anomaly Detection and Description : A survey 论文笔记

1. detecting outlying points lying in a multi-dimensional feature space

• While numerous techniques have been developed in past years for spotting outliers and anomalies in unstructured collections of multi-dimensional points,

2. detecting abnormalities in graph data

why graphs?

graph data becoming ubiquitous, techniques for structured graph data have been of focus recently. As objects in graphs have long-range correlations,

• Inter-dependent nature of the data
• Powerful representation
• Relational nature of problem domains
• Robust machinery

3. Challenges

3.1 Data-specific challenfes

• Scale and Dynamics:
• Complexity

3.2 Problem-specific challenges

Additional challenges arise with respect to the anomaly
detection task itself.

• Lack and Noise of Labels
• Class Imbalance and Asymmetric Error:\
• Novel Anomaliers
• Explaining-away

3.3 Graph-specific challenges

• Inter-dependent Objects
• Variety of Definitions
• Size of Search Space

4. the state-of-the-art methods for anomaly detection in data represented as graphs.

As a key contribution, we give a general framework for the algorithms categorized under various settings:

• unsupervised vs. (semi-)supervised approaches,
• static vs. dynamic graphs,
• attributed vs. plain graphs.
  

5. Open Challenges

5.1 Theoretical research challenges.

While there has been considerable amount of work on static graphs, there still remain problems in the study of dynamic graphs.(尽管在静态图上的研究方法很多，在动态图上的却比较稀少)

• Anomaly Detection on Attributed Dynamic Graphs.
• The History/Trace of Dynamic Updates.
• Choosing the ‘Right’ Time Window/Granularity.
• Adversarial Robustness
• The Cost of Graph Anomaly Detection
• Scalable Real-time Discontinuity Detection

5.2 Practical research challenges.

Challenges from the practitioner’s point of view, which could also be posed as research problems, include the following.

• Finding the X-factor
• Evaluation
• Graph Construction
• Anomaly Detection on Multi-Graphs
• Balance between Attribution and ‘Novelty’ Detection.
• Augmented Graph Anomaly Detection