An edge stream is a common form of presentation of dynamic networks. It can evolve with time, with new types of nodes or edges being continuously added. Existing methods for anomaly detection rely on edge occurrence counts or compare pattern snippets found in historical records. In this work, we propose Isconna, which focuses on both the frequency and the pattern of edge records. The burst detection component targets anomalies between individual timestamps, while the pattern detection component highlights anomalies across segments of timestamps. These two components together produce three intermediate scores, which are aggregated into the final anomaly score. Isconna does not actively explore or maintain pattern snippets; it instead measures the consecutive presence and absence of edge records. Isconna is an online algorithm, it does not keep the original information of edge records; only statistical values are maintained in a few count-min sketches (CMS). Isconna's space complexity $O(rc)$ is determined by two user-specific parameters, the size of CMSs. In worst case, Isconna's time complexity can be up to $O(rc)$, but it can be amortized in practice. Experiments show that Isconna outperforms five state-of-the-art frequency- and/or pattern-based baselines on six real-world datasets with up to 20 million edge records.

翻译：边缘流是一种常见的动态网络演示形式。 它可以随着时间而演化, 新的节点或边缘类型会不断增加。 异常现象探测的现有方法依赖于边缘发生数或比较历史记录中发现的模式片块。 在这项工作中, 我们提议Isconna, 它既注重频率, 也注重边缘记录模式。 防爆探测组件针对单个时间戳之间的异常, 而模式探测组件则突出时间戳各部分之间的异常。 这两个组成部分共产生三个中间分, 并会合并到最后的异常分数中。 Isconna 不积极探索或保持模式片断; 而是测量边缘记录的连续存在和缺失。 Isconna 是一条在线算法, 它不保存边缘记录原始信息; 仅保留在少数数分数草图中( CMS) 。 Isconna 的空间复杂性 $O( rc) 是由两个用户特定参数决定的大小 CMS 。 在最坏的情况下, Isconna 的时间复杂性可以高达$( rc) 。 但是, 它可以在实际的轨道上显示 5- am- sloveal s