Weak matching of temporal interval graphs of sensors for robust multi-modal event detection in noise
Lakshman Prasad, Boian S. Alexandrov, Benjamin T. Nebgen · 2020
We present a weak matching algorithm for interval graphs, to detect recurrent patterns in multimodal temporal data, with feature time series extracted by nonnegative tensor factorization (NTF). NTF enables latent feature extraction as well as uniform representation of multimodal observables. This work builds on our previous work introducing an interval graph representation framework for multi-sensor data. Salient data regions and their relationships are represented by temporal interval graphs, where observables are captured as time intervals (nodes), and temporally proximate nodes are related by edges. Comparing events is then posed as a subgraph matching problem. However, subgraph matching is notoriously difficult (NP-complete) with polynomial algorithms for only very restricted families of graphs. Even in these cases, perturbations to graph structure from missing or extra nodes and edges can lead to brittle matching results. Indeed, realworld sensing involves noisy environments where extraneous or missing observables interfere with event interval graph structures. To cope with these challenges, we propose a proxy representation of interval graphs via their shortest and longest paths and compare graphs by matching their path sets. We describe an attributed path matching scheme that is robust to inclusions and exclusions of nodes by adapting the longest common subsequence algorithm using dynamic programming for attributed path matching. We demonstrate the efficacy of interval graph analysis of tensor features on real-world multimodal sensor data where we investigate the detectability, similarity, and distinguishability of three sets of known events based on ground truth. We illustrate our results with match matrices and ROC curves.