【KDD2020】动态图的拉普拉斯变换点检测，Laplacian Change Point Detection for Dynamic Graphs

主题： Laplacian Change Point Detection for Dynamic Graphs

摘要： 动态图和时间图是丰富的数据结构，用于对实体之间的复杂关系进行建模，尤其是时间图的异常检测是现实世界中至关重要的应用，例如网络系统中的入侵识别，生态系统扰动的检测和流行病的检测。在本文中，我们专注于动态图的变化点检测，并解决与该问题相关的两个主要挑战：I）如何跨时间比较图快照，II）如何捕获时间依存关系。为了解决上述挑战，我们提出了拉普拉斯异常检测（LAD），它使用每个快照上图结构的拉普拉斯矩阵的频谱来获得低维嵌入。 LAD通过应用两个滑动窗口显式地对短期和长期依赖性进行建模。在合成实验中，LAD的性能优于最新方法。我们还将在三个真实的动态网络上评估我们的方法：UCI消息网络，美国参议院共同赞助网络和加拿大法案投票网络。在所有三个数据集中，我们证明了我们的方法可以根据重大的现实事件更有效地识别异常时间点。