【CMU博士论文】使用静态和动态图来异常检测，Mining Anomalies using Static and Dynamic Graphs

题目：

Mining Anomalies using Static and Dynamic Graphs

简介：

在许多情况下，例如安全性，医疗保健，财务和网络，异常检测，即稀有或异常模式是一个紧迫的问题。审查欺诈和网络入侵攻击之类的异常编码可疑，欺诈或恶意行为，不仅影响人们做出次优的决策，而且稳定地削弱了他们对业务的信任。这样，检测正在进行的异常并警告即将发生的异常的算法对企业和最终用户都具有很大的影响。本文通过开发可利用连接性和时间信息来检测异常行为或事件的原理化，可扩展算法，来考虑异常检测问题。这些方法对于大型动态复杂数据集很有用，这些数据集具有很强的关系和时间特性，多个实体相互交互，并且会随着时间而发展。如今，此类数据集是在多种多样的环境中生成的，其示例范围从电子商务日志到在线社交网络再到物联网。 论文的前半部分着重于图形中的异常检测，在这些图中，只有静态连接信息是已知的。给定一个图和一些标记的顶点，我们如何推断其余顶点的标记？例如，我们如何从一小组手动标记的诚实和伪造帐户中发现Amazon或Facebook上的所有伪造用户帐户？与现有文献相比，我们的工作利用了现实世界图中的三个关键属性，即顶点和边类型的异质性，偏度分布和高阶结构，可以产生更准确的顶点标记。所提出的算法具有封闭形式的解决方案，严格的收敛性保证，可以使用稀疏矩阵运算有效地实现，并且可以随图形大小线性缩放。 本文的后半部分着重于从连接结构随时间变化的数据中挖掘异常。在许多情况下，尤其是与安全和卫生保健有关的情况，新发现或预期的异常的价值在于当下，而不是不久的将来。因此，给定一个随时间变化的图表（显式图或隐式图），我们如何才能近乎实时地检测异常或事件，甚至可能在它们发生之前提早发出警报？我们的算法可以通过仅存储到目前为止所看到的图形的简短摘要并且不需要监督，就可以实时检测异常图形的足迹，例如密集子图的突然出现或消失以及桥边。我们还展示了如何以在线方式从时间序列数据推断状态转换图，并使用它来提前警告用户标记的异常，例如不利的医疗条件。在整个论文中，着重强调的算法不仅（a）在实践中有效，而且（b）高效，可以在几秒钟内在普通笔记本电脑上处理数百万条边缘，并且（c）有原则可以进行严格的推理，从而为推理，检测或利用数据相关的见解提供理论上的保证。我们证明了我们的算法在从社交网络和电子商务到安全和医疗保健的一系列应用中的功效。