Blind Graph Topology Change Detection

Blind Graph Topology Change Detection: A Graph Signal Processing approach

Mahabir, Ashvant (TU Delft Electrical Engineering, Mathematics and Computer Science)

Leus, G.J.T. (mentor)
Isufi, E. (graduation committee)

Delft University of Technology

Electrical Engineering | Signals and Systems

2017-12-20

Graphs are used to model irregular data structures and serve as models to represent/capture the interrelationships between data. The data in graphs are also referred as graph signals. Graph signal processing (GSP) can then be applied which basically extends classical signal processing to solve problems. Anomaly detection is an example of such a problem. Two hypothetical situations are given, and a detector has to be designed to distinguish between these. Under the null hypothesis, graph structures are considered to be untouched. Under the alternative hypothesis, (unknown) topological changes might have occurred. Now by incorporating a priori knowledge about the graphs, the decision making process should improve.
In most works, a priori knowledge of the graphs under the null and alternative hypothesis was incorpo- rated. This means that detectors were designed which were able to anticipate on possible topological changes. In this thesis, the problem is considered where only a priori knowledge of the graph under the null hypothesis is exploited. This means that detectors are not able to anticipate on potential changes and this where blind detection comes into play. Blind detection is important because it considers a more realistic scenario. In this work, the blind topology change detector (BTCD) and the constrained blind topology change detector (CTCD) are derived which exploit different properties of the data re- lated to the known graph structure. For the BTCD, the bandlimitedness of graph signals was exploited and for the CTCD, the graph signal smoothness. The main question in this work, was to find out what the potentials are with the blind detection principle for graph change detection.

Different test scenarios are used to evaluate the detectors on both synthetic and real data. For the BTCD, the obtained results compare well when information about the alternative graph is available. For this detector, the potential of blind detection was highly visible. For bandlimited graph signals, the BTCD as good as detectors using full information. For the CTCD, comparable results (with detectors using full information) are attained for just a few test scenarios. For small changes, the graph signal smoothness seems to be less powerful as to the graph signal bandlimitedness.

This study showed that graph change detection is still possible without having full information. Some graph signal properties are more powerful w.r.t. others.

graph theory
Detection
Graphs
anomaly detection
blind

http://resolver.tudelft.nl/uuid:9b58f037-5c2a-4444-97f4-f8dacef6eb5f

Student theses

master thesis

© 2017 Ashvant Mahabir