Sketch-Based Streaming Anomaly Detection in Dynamic Graphs

Overview

AnoGraph

Implementation of

Existing methods only detect edge or subgraph anomalies. We extend count-min sketch to higher-order preserving the dense subgraph structure & detect both. Our approach is the first streaming method that uses dense subgraph search to detect graph anomalies in constant memory and time.

(a) Dense subgraph in the original graph between source nodes s1, s2, and destination nodes d1, d2, d3 is transformed to a (b) Dense submatrix between rows r1, r2, and columns c1, c2, c3 in the higher order CMS.

AnoEdge-G and AnoEdge-L detect edge anomalies by checking whether the received edge when mapped to a sketch matrix element is part of a dense submatrix. AnoEdge-G finds a Global dense submatrix and performs well in practice while ANOEDGE-L maintains and updates a Local dense submatrix around the matrix element and therefore has better time complexity.

AnoGraph and AnoGraph-K detect graph anomalies by first mapping the graph to a higher-order sketch, and then checking for a dense submatrix. AnoGraph greedily finds a dense submatrix with a 2-approximation guarantee on the density measure. AnoGraph-K greedily finds a dense submatrix around K strategically picked matrix elements performing equally well in practice.

Demo

  1. To run on DARPA dataset bash demo.sh DARPA
  2. To run on ISCX dataset bash demo.sh ISCX

Datasets

  1. DARPA
  2. ISCX-IDS2012
  3. CIC-IDS2018
  4. CIC-DDoS2019

CIC-IDS2018 and CIC-DDoS2019 Datasets are larger than 100MB and cannot be uploaded on Github. They can be downloaded from here. Please unzip and place the respective folders in the data folder of the repository.

Environment

This code has been tested on OS X 10.15.3 with a 2.4GHz Intel Core i9 processor.

Owner
Stream-AD
Streaming Anomaly Detection
Stream-AD
Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog

In this project, Canny edge detection, one of the efficient edge detection algorithms is implemented on a Zedboard FPGA using verilog. The input image is stored on a PC and fed to the FPGA. The output processed image is displayed on a VGA monitor.

Jeffrey Samuel 2 May 9, 2022
Croquis: plot graphs 100x faster on Jupyter Notebook

Croquis is a lightweight Python library for drawing interactive graphs really fast on Jupyter Notebook. It lets you effortlessly browse and examine much larger data than other similar libraries.

Yongjik Kim 29 Jan 31, 2022
A library in Javascript to create graphs in the browser similar to Unreal Blueprints.

A graph node engine and editor written in Javascript similar to PD or UDK Blueprints, comes with its own editor in HTML5 Canvas2D. The engine can run client side or server side using Node. It allows to export graphs as JSONs to be included in applications independently.

Javi Agenjo 3k Aug 4, 2022
Selfies but in C++. Celfies is for HPC. Robust representation of semantically constrained graphs, in particular for molecules in chemistry.

celfies Selfies but in C++. Why? Because RDKit in C++ and other speed reasons. Follow the originators of the ideas & code @MarioKrenn, @AlstonLo, @Sey

sevenTM 3 Nov 24, 2021
Real-Time SLAM for Monocular, Stereo and RGB-D Cameras, with Loop Detection and Relocalization Capabilities

Real-Time SLAM for Monocular, Stereo and RGB-D Cameras, with Loop Detection and Relocalization Capabilities

Raul Mur-Artal 7.5k Aug 11, 2022
FFVideo - an example FFmpeg lib, and wxWidgets Player with video filters and face detection

An example FFmpeg lib, and wxWidgets Player application with video filters and face detection, it is a no-audio video player intended for video experiments and developers learning how to code media applications.

Blake Senftner 20 Mar 26, 2022
Bullet Physics SDK: real-time collision detection and multi-physics simulation for VR, games, visual effects, robotics, machine learning etc.

Bullet Physics SDK: real-time collision detection and multi-physics simulation for VR, games, visual effects, robotics, machine learning etc.

Bullet Physics SDK 9.6k Aug 10, 2022
A multi core friendly rigid body physics and collision detection library suitable for games and VR applications.

A multi core friendly rigid body physics and collision detection library suitable for games and VR applications.

null 2k Aug 7, 2022
Minimal A* implementation in C. No dynamic memory allocation.

Micro A Star Path Finder This is a minimal A* path finder implementation in C, without any dynamic memory allocation. Usage The maximum size of the ma

Felipe da Silva 79 Aug 9, 2022
2D GPU renderer for dynamic UIs

vger vger is a vector graphics renderer which renders a limited set of primitives, but does so almost entirely on the GPU. Works on iOS and macOS. API

Audulus LLC 123 Aug 7, 2022
Plot dynamic 3d functions z = f(x, y, t)

A tool for plotting 3D functions Controls Button Description Arrows Rotate view F Enable/Disable filling surface faces G Enable/Disable showing coordi

Boris Starkov 2 Oct 15, 2021
physically based renderer written in DX12 with image-based lighting, classic deffered and tiled lighting approaches

Features Classical Deferred Renderer Physically Based shading Image Based Lighting BRDF Disney model (Burley + GGX) Tangent space normal mapping Reinh

Alena 35 Jun 2, 2022
Yocto/GL: Tiny C++ Libraries for Data-Driven Physically-based Graphics

Yocto/GL: Tiny C++ Libraries for Data-Oriented Physically-based Graphics Yocto/GL is a collection of small C++17 libraries for building physically-bas

Fabio Pellacini 2.3k Aug 11, 2022
An OCR Library based on PaddleOCR & OnnxRuntime

An OCR Library based on PaddleOCR & OnnxRuntime

Daniel 0 Mar 27, 2021
Vision-based quadrotor fault-tolerant flight controller.

This repository contains the flight controller, and the vision-based state estimator for a quadrotor subjected to complete failure of a single

Robotics and Perception Group 127 Aug 9, 2022
A path tracer based on hardware ray tracing

GoldenSun GoldenSun is a GPU path tracer. It uses hardware ray tracing APIs to do the tracing. As an experimental project, there is no release plan, n

Minmin Gong 20 Feb 27, 2022
[WIP] A media playback library for Dart & Flutter apps on Windows & Linux. Based on libVLC & libVLC++.

dart_vlc Bringing power of VLC to Flutter & Dart apps on Windows & Linux Installation dependencies: ... dart_vlc: ^0.0.1 Documentation Create a ne

Hitesh Kumar Saini 353 Aug 2, 2022
Vulkan physically based raytracer including denoising

VulkanPBRT Vulkan physically based raytracer including denoising. The GPU raytracer is based on Vulkan only, as well as for the denoising only the Vul

null 15 May 26, 2022
SoL (for Speed of Light, or sun in Spanish) is a Physically-based rendering library written in modern C++

SoL (for Speed of Light, or sun in Spanish) is a small rendering library written in C++20. Its goal is to strike a good balance between performance and usability, and allow easy experimentation for rendering researchers.

Arsène Pérard-Gayot 10 May 19, 2022