超边缘流异常检测：基于Hash和Random Walk的新算法

+v：mala2277获取更多论文HashNWalk：基于Hash和Random Walk的超边缘流异常检测Geon Lee、Minyoung Choe和Kijung ShinKim Jaechul人工智能研究生院，KAIST，韩国{geonlee0325，minyoung.choe，kijungs} @ kaist.ac.kr摘要群体互动的序列，如电子邮件、在线讨论和合著，无处不在;它们自然地被表示为一串超边。尽管超图具有广泛的潜在应用，但超图中的异常检测（即，超边集）与图中的超边集相比，受到了令人惊讶的关注。 虽然将超图简化为图并应用现有的基于图的方法是诱人的，但根据我们的实验，考虑超图的高阶结构是值得的。我们提出了HASH NWALK，一种增量算法，可以检测超边流中的异常它维护和更新关于流的结构和时间信息的恒定大小的摘要。使用摘要，这是一个接近矩阵的形式，HASHNWALK措施的每个新的超边缘，因为它出现的粗糙度。HASH NWALK是（a）快速的：它几乎实时地处理每个超边，并且在几个小时内处理数十亿个超边，（b）空间高效的：所维护的摘要的大小是预定义的常数，（c）有效的：它成功地检测真实世界超图中的异常超边。1介绍包括计算机网络、在线社交网络和超链接网络在内的各种真实世界的图都分布式拒绝服务攻击通过在目标机器上造成意外的流量堵塞来阻止可用性。此外，在线社交网络中的虚假连接降低了推荐的质量，而超链接网络中的虚假连接操纵了网页的中心性由于其在实际应用中的重要性和必要性，图中的异常检测受到了广泛的关注。为了检测偏离图中的结构和时间模式的节点、边和/或子图，已经提出了利用搜索算法对偏离进行各种数值测量[Akogluet al. ， 2010;Hooiet al. ， 2016;Shin 等 人 ，2018]。由于许多真实世界的图形随着时间的推移而演变，因此在异常出现时实时检测异常是可取的[Bhatiaetal. ，2020;Eswaran and Faloutsos，2018].虽然图形对成对交互进行建模，但许多现实世界系统中的交互是分组的（共同作者的协作、在线问答平台上的分组交互、项目的共同购买等）。这样的成组相互作用自然地表示为超边缘，即，一组任意数量的节点。超图是图的一个不可缺少的扩张，它是一组超边的集合，只能描述两两关系。此外，许多这样的现实世界超图随着时间的推移而演变（例如，在多组用户之间连续交换的电子邮件、随时间建立的共同作者关系、以及共同购买项目的每日记录），因此它们通常被建模为超边流。尽管对图的异常检测有很大的兴趣，但超图中的同样问题在很大程度上还没有被探索。由超边表示的高阶关系表现出与图不同的结构和时间特性，因此提出了独特的技术挑战。因此，不是简单地将超边分解成成对边并应用基于图的方法，而是需要考虑底层高阶结构以用于超图中的异常检测。为此，我们提出了HASHNWALK，一个在线算法检测异常超边缘。HASH NWALK维护一个恒定大小的摘要，用于跟踪输入流中高阶交互的结构和时间模式。具体来说，HASH NWALK将所谓的边相关节点权重[Chitra和Raphael，2019]纳入超图上的随机游走中，以估计节点之间的接近度，同时捕获高阶信息。此外，我们开发了一个增量更新方案，其中每个超边是由它的出现进行处理。设计的超图摘要用于对流中任何新的超边的粗糙度进行评分。虽然异常的定义取决于上下文，在这项工作中，我们专注于两个直观的方面：意外和突发性。我们假设意外的超边由节点的非自然组合组成，并且突发超边在短时间内突然出现。基于超图摘要形式的信息，我们正式定义了两个异常评分指标，有效地捕捉这些属性。我们的经验表明，HASH NWALK是有效的检测异常超边（半）实超图。我们的贡献概括如下：• 快速：HASH NWALK需要很短的时间才能产生arXiv：2204.13822v1 [CS.SI] 2022年4+v：mala2277获取更多论文≤∈联系我们联系我们{}∈||(a) 快速、准确(b) 扩展性意外Hyperedges（专利）节点（专利）(c) 有效性突发图1：HASHNWALK的优势。(a)HASH NWALK在真实超图中快速准确地发现异常超边。(b)HASH NWALK的总运行时间与输入超边缘流的大小成线性关系。(c)HASH NWALK检测有趣的专利。专利1引用了多个以前没有一起引用过的专利，专利5-7引用了几乎相同的一组专利。详见第5节。cess每个新的hyperedge。具体来说，在我们的实验环境中，它在2.5小时内处理了14亿个hyperedges。• 节省空间：用户可以限制HASH NWALK维护的总和的大小。• 准确：HASH NWALK成功检测异常超边缘。从数字上看，它的表现优于最先进的竞争对手，AUROC高出47%复制：源代码和数据集可在www.example.com上获得https://github.com/geonlee0325/HashNWalk。2相关作品我们讨论了与本文相关的三个主题的先前工作图超图中的异常检测问题对于静态和动态图，已经广泛地研究了检测异常节点、边和/或子图的Lems [Akogluet al. ，2015]。在静态图中 ， 其 自 我 网 络 在 结 构 上 与 其 他 节 点 不 同 的 节 点[Akogluet al. ，2010]，其去除显著降低编码成本的边[Chakrabarti，2004]，或其密度异常高的子图[Beuteletal. ，2013;Hooiet al. ，2016;Shin等人2018年]被认为是异常的。在动态图中，如果时间边缘连接图中的稀疏连接部分[Eswaran和Faloutsos，2018 ]，或者根据基础模型不太可能出现[Aggarwal等人，2018 ]，则认为时间边缘是异 常 的 。 ， 2011; Yoonet al. ， 2019;Bhatiaet al. ，2020]。此外，在短时间内生成的稠密子图被认为是异常的[Shinetal. ，2017;Eswaranet al. ，2018]。 最近，基于在本文中，我们将我们的方法与在线设置中检测异常交互的方法进行了比较，即，为边缘流设计的异常检测器[Bhatiaet al. ，2020;Eswaran and Faloutsos，2018;Changetal. ，2021]和超边缘流[Ranshouset al. ，2017]。边缘流的总结：总结的目的是减少给定图的大小，同时近似地保持其结构属性。在流边缘的实时处理的上下文中特别需要它。在[Bhatiaet al. ，2020]中，为边缘的近似频率保持计数最小值草图。边频率已被用来回答有关图 的 结构 属 性 的 查询 [Zhaoet al. ， 2011;Tanget al. ，2016]。 在[Bandyopadhyayet al. ，2016]，通过维护给定图的拓扑信息来估计局部属性，诸如三角形的数量和邻域重叠。超图和应用：超图出现在许多领域，包括生物信息学[Hwanget al. ，2008]、电路设计[Karypiset al. ，1999]、计算机视觉[Huanget al. ，2009;Kimet al. ，2020]，自然语言 处理 [Dinget al. ， 2020]，社 交网 络分 析[Yangetal. ， 2019] 和 建 议 [Maoet al. ， 2019] 。 结 构 特 性[Bensonet al. ， 2018 a;Doet al. ， 2020;Lee 等 人 ，2020;Lee 等 人 ， 2021;Choeet al. ， 2022] 和 动 态 特 性[Bensonet al. ，2018 a;Bensonet al. ，2018 b;Kooket al. ，2020; Lee和Shin，2021; Choo和Shin，2022]已经被广泛研究。3预赛在本节中，我们将介绍符号和符号表。3.1符号和概念超图：超图G=（V，E）由一个集合组成，方法已被证明是有效的检测异常，图[Yuet al. ，2018; Changet al. ，2021]。节点V={v1，...，v|V| }和一组超边E=另一方面，检测超图中的异常是相对未探索的。超图中的异常节点已经成为通过使用超图上的扫描统计来检测的目标[Parket al. ，2009]或基于节点的高阶结构特征训练分类器[Leontjevaet al. ，2012]。不可见超边的复杂性是根据节点组合从异常同现分布（假设是均匀的）而不是名义分布中提取的可能性来测量的[Silva和Willett，2008]。通过局部敏感散列获得的结构相似的超边缘的近似频率用于对超边缘流中的超边缘的粗糙度进行评分[Ranshouset al. ，2017]。e1，.， E. 每个超边e E是任意数目节点的非空子集我们可以用关联矩阵H 0，1表示G|E| ×|V|，其中每个条目H ij为1如果vj否则为0。一个超环gest环（ei，ti）∞i=0是每个超边ei到达的超边序列在时间t1。对任意i和j，如果i j，则ti tj。集团扩张和信息损失：集团扩张[Zhouet al. ，2007]，其中每个超边e E被转换成由e中的节点组成的团，是将超图G转换成普通成对图的最常见方法之一。团扩张会损失高阶相互作用的信息。也就是说，一般来说，超图不是从其零HashNWalk线性（斜率1234HashNWalkSedanSpotF-FADELSH5 6 7+v：mala2277获取更多论文∈∈←∈E∈∈E{}≥0∈∈∈∈--Σ∈∈| |·→{}{1}|}VE集团扩张指数地将许多非同构的超图约化为相同的团展开。超图上的随机游走：超图G上的随机游走在[Chitra andRaphael，2019]中公式化如下。如果当前节点是u，（1）选择包含节点u的超边e（即，ue），概率与ω（e）成比例，以及（2）选择节点v与概率propor-（v），并走到节点v。权重ω（e）是超边e的权重，权重γe（v）是权重节点v相对于超边e权重γe（v）为算法1HASHNWALK输入：（1）h超边缘流：=（ei，ti）∞i=1，（2）超节点数M，（3）散列函数数K，（4）时间衰减参数α输出：异常分数流{yi}∞i=11：SRM×M和TRMd初始化为零2：f或每个H超边（ei，ti）do3：m（ei）通过散列d来总结e i。4.14：更新S和Td节。第4.2节5：yi←（sc oreU（ei），sc oreB（ei））dSect. 4.3如果它对于每个超边e都是相同的，则它是与边无关的;以及6：结束锻造∞否则，它是边缘相关的。如果所有节点权重都是边独立的，则G上的随机游走等价于其团扩展上的随机游走[Chitra和Raphael，2019]。然而，如果节点权重是边依赖的，超图上的随机行走一般是不可逆的。也就是说，它们可能与任何未知图上的随机游动不同。在这个意义上，如果边相关权重可用，则随机游走能够利用团扩展之外的高阶信息，因此在许多机器学习任务中经验上有用[Hayashiet al. ，2020]。转移矩阵：为了包含边相关的节点权重，将关联矩阵H推广为加权关联矩阵R ∈ R|E| ×|V|其中每个条目R ij是当v j ∈ ei时，γei（vj），否则为0。其次，转型问题--能力矩阵P∈R|V| ×|V|在超图G上的随机游动的可积性记为P=D−1WD−1R，其中W∈R|V| ×|E|表示超边权重矩阵，其中如果v j ∈ e i，则每个条目Wji为ω（ei），否则为0。矩阵D VR|V| ×|V|D ER|E| ×|E|分别是节点度和超边权重的对角矩阵。即如果我们让qR|E|r R|V|是其条目都是1的向量，则DV=diag（Wq）和DE= diag（Rr）。3.2问题描述我们在本文中解决的问题如下。问题1。 给定炒作数据的一个st r eam（ei，ti）∞i=1，利用常数空间近实时地检测出结构或时间性质偏离一般模式的异常超边.虽然异常超边的定义取决于上下文，我们专注于两个直观的角度。在一个方面，如果一个超边由一个不期望的节点子集组成，那么它是异常的也就是说，我们的目标是检测由不寻常的节点组合组成的超边。在另一方面，我们的目标是确定一组类似的超峰，出现在突发作为一个异常。突然出现的类似的相互作用往往表明恶意行为有害的许多应用程序.此外，对于时间关键的应用程序，我们的目标是检测这种异常超边缘在近实时，因为它们出现，使用有界空间。虽然人们可能试图将超边减少到子图中并解决异常子图检测的问题，但这损害了超边的此外，现有的工作anomous子图假设静态图[Hooiet al. ，2016]或仅检测单个最异常的子图[Shinet al. ，2017]，而我们的目标是对流中的每个超边缘进行评分。7：返回n{yi}i=14该方法在本节中，我们提出了HASH NWALK（算法1），这是一种用于检测超边缘流中异常的快速且节省空间的算法。我们主要关注的是速度和空间效率，因为HASHNWALK预计将处理潜在的无限流。如图2所示，它维护了超边缘流的简明且信息丰富的摘要（4.1节），随着每个新的超边缘到达，该摘要会逐渐更新（4.2节）。一旦更新了摘要，异常超边将立即根据两个原则性指标进行识别（第4.3节）。虽然HASH N-WALK是基于多个总结（第11节）。4.4），为便于解释，我们4.1超图摘要超边缘表示：我们描述如何使用恒定空间简洁地表示每个超边缘。根据定义，超边的大小是灵活的，并且使用相同的空间量来表示每个超边为此，我们将每个节点映射到M个不同值中的一个使用散列函数h（）：V1，...，M. 我们将每个哈希值视为一个超级节点，其中包含具有相同哈希值的节点。由于散列冲突，超边可以多次包含超级节点，并且超边的数目可以是超节点的数目。发生的事件变成关于超边的超节点的权重。形式上，我们将任何大小的每个超边e表示为M维向量m（e）ZM，其第k个元素指示包含在e中并映射到散列值k的节点的数量（即，mk（e）：=v e1（h（v）=k））。它也被解释为超节点k相对于超边e的权重。我们将e表示为超边缘e包含的超节点的集合，即， e_n：=kmk（e）>0. 请注意，任何大小的H超边都表示为固定大小的向量，其大小M由用户控制。此外，超节点的边依赖权重可以被随机游走利用（见3.1节）。如果我们使用一个常数时间散列函数h和一个稀疏向量对于每个超边e，生成向量m（e）的时间复杂度为O（|e|），如引理1所述。引理1（生成m（e）的时间复杂度）。给定一个超边e，生成向量m（e）需要O（e）时间。P屋顶。以稀疏格式创建零矢量（例如，（2）如果n = 1，则n = 1，n =2，n = 1，n|e|）时间。+v：mala2277获取更多论文| |·乌什夫河∈∈∈∈PΣ乌什夫河≥VE我埃吉v∈ei埃吉边相关超节点权重： 如果边缘依赖乌什夫河我v∈ei我k=1Σ||ω（ei）·（u∈ei），和Reγe（v）γ（v）图2：HASHNWALK的概述。(a)新的超边到达输入超边流。(b)通过散列将节点合并成具有边相关权重的M个超节点，并且将包括新的超边的超边表示为M维向量（在该示例中M=3）。(c)超图摘要由矩阵S和向量T组成，并且它响应于新的超边缘而递增地更新。（d）根据可直接从S和T得到的总结P（Eq. （2））、新超边的对称性使用建议的评分函数（等式2）测量。（5））。超图摘要：下面，我们将介绍如何对整个超图进行摘要，以快速准确地进行异常检测。我们注意到，用于识别两种类型的异常超边的关键构建块（即，意想不到的具体来说，较小的α更强调最近的超边缘。4.2增量更新挑战：从碎片ch中构建以及突发中的相似节点）是估计节点之间的接近度或结构相似性。因此，我们将输入超图概括为超结点间的邻近性形式，并推广了随机游动来度量其邻近性。我们的总结是基于扩展了边依赖超节点权重和超边权重的随机游动;我们使用转移概率作为快速更新的近似值（见4.2节）。具体来说，我们总结-将输入h型r图化为矩阵P：=D−1WD−1R∈RM×M，其中R∈R|E|×M是加权关联矩阵，其中每个条目Riv是γe（v），如果v∈ei，否则为0。矩阵W∈RM×|E|表示h型权重ma，O（EM2）的时间，是不可取的，当立即响应异常的要求.此外，当超边被不确定地流式传输时，禁止具体化用于计算P的W、D、 E和R，因为它们的大小与超边的数量成比例。提出的更新方案：我们提出了一个增量算法，用于有效地更新P_∞以响应新的超边缘。所提出的更新方案仅保持P_n，其大小可通过使用r来控制，而不对任何更大的矩阵进行材料化。 假设m个超边e1，...，e mh aveiv ed，并且令Pm（m）是距超节点的接近度其中W<$ v<$e <$是ω（e<$），如果v<$∈e<$，否则为0。矩阵DVRM×M和DER|E| ×|E|是对角矩阵的超节点度和超边权重。然后，P是转移概率矩阵，其中每个en-到超级节点v。我们引入一个矩阵SRM×M与向量TRM，并且对于n y个超节点u和v，当超边e m在时间t m到达时，它们的条目是试试P是从超节点u到v的转移概率：S（m）：=μmα−ti·1（u∈e）·γei（v）乌什夫河P=Σ|E|ω（ei）·1（u∈ei）·γei（v）（一）乌什夫河i=1iR埃吉乌什夫河i=1吴瑞吉（米）u：=mα−ti·1（u∈e∈i），其中，W u 是u的加权系数，即，你好！i=1E1i=1i以太网中的超级节点，即，R是以下各项的权重之和：：=γ（v）。根据Eq。并且预定义的超边缘权重函数ker（x）=αx（1-α），Pr（m）被写为：超级节点权重可用，随机游走利用高-超越集团扩张的信息。 此类重量（m）乌什夫河Mi=1αtmM−ti（1−α）·1（u∈e<$i）·埃吉瑞吉 =（米）uv（m）是从上述载体中天然获得的。hyperedges的发音也就是说，我们使用<$αtm−ti（1−α）·1（u<$∈e<$i）Tu（二）每个超节点v_i在每个超边e_i中的出现次数作为v_i相对于e_i的权重。对 于形式y，γei（v）=mv（ei），因此Re=γe（v）=Mmk（ei）=|ei|.代替直接跟踪邻近度矩阵P*，我们跟踪前面提到的S和T，它们的条目被初始化为零。每个条目Suv和Tu可以在恒定时间内更新，如下所示：时间衰减超边缘权重：为了便于识别最近爆发的类似超边，这是我们的重点之一，我们强调最近的超边与大的权重。具体地，在当前时间t，我们将在时间ti到达的每个超边ei的权重定义为ω（ei）=ker （ t−ti ） =αt−ti （ 1−α ） 其 中 ker （ x ） ： =αx（1−α）是用于量化时间衰减的核函数，并且α∈[0，1]在引理2和引理3中，一旦它们被更新，我们（2）在O（1）时间内计算P（m）（2）如果需要，引理2（更新Suv）. F或任何m0，当炒作r-边em+1到达t m+1时，方程：（3）保持。S（m+1）=S（m）+α−tm+1·1（u∈e）·m+1。（三）是一个决定强调程度的超参数。乌什夫河乌什夫河m+1Rem+1不.i=1S=+v：mala2277获取更多论文≥| || |||||你，我| || || |u| |||um+1引理3（更新Tu）. F或任何m0，当炒作r-边em+1到达t m+1时，方程：（4）保持。T（m+1）=T（m）+α−tm+1·1（u∈e）。（四）意想不到（scoreU）：在等式中的Intuit iv el y，au，v/su，v。（5）测量从超节点U到N中的V的接近度如何偏离N中的引理2和引理3直接来自S（m）和T（m）。在过去的hype中彼此远离的odesu和v在新的hype中以高度接近的方式意外地共同出现乌鲁夫河超边缘。 因此，在分数中，这是异常分数，复杂性：值得注意的是，如果u∈/em+1，1（u∈em+1）=0成立，如果v∈/em+1，γem+1（v）=0成立。如果v=v，则v=v，包括在NEW超边缘中（即，u∈/em+1或v∈/em+1），U识别意外的超边缘，我们通过设置β=0来关注比率。为了检测任何这种意想不到的配对，S保持相同（即，S（m+1）=S（m）），因此超边中的超节点，得分U使用最大比率乌什夫河乌什夫河乌什夫河作为最终得分（即，aggregate = max）。不需要更新。类似地，如果u不包括在em+1中，则T u不改变。这些因素显著减少了摘要的更新时间，从而实现了对每个超边缘的近实时 总之，为了应对一个新的超-edge， HASHNWALK使用恒定空间在短时间内更新概要，分别如引理4和5所述引理4（每个超边缘的更新时间）。给定超边e的稀疏向量表示m（e），使用等式（1）更新S∈RM×M和T∈RM。（3）Eq. （4）时间复杂度为O（min（M，|e|2）时间。突发性（分数B）：为了检测在突发中出现的类似超峰，考虑超节点的出现次数。根据定义，超节点是节点的子集，并且类似的超边倾向于共享许多超节点。如果在短时间内出现大量类似的超边，其中的超级节点会相应地增加。因此，在得分B中，这是用于识别最近的类似超峰爆发的异常得分，我们将β设置为正数（具体来说，在这项工作中，1）采取这种情况（即，PROOF. e中的超级节点数为|e|，而在最多节点数|e|超级节点的数量βu，ti由方程式（5）除了意料之外，考虑到M，因此e=O（min（M，e））。然后，e=S的2个元素和e=T的2个元素由等式（1）更新。（3）Eq. （4），并且每个元素的更新时间恒定。因此，总的时间复杂度为O（min（M，|e|（2）。□˜Edness（即， au，v/su，vinEq. （5））。 我们反映了通过平均来自所有超节点对的分数来确定超边缘中的所有超节点合计=平均值）。异常评分的互补性：虽然评分U和评分B之间的唯一差异是考虑引理5（常数空间）. 维护的摘要P时间复杂度为O（M2）超节点的当前度（即，dβ）和ag-P屋顶。 因此，时间复杂度为O（M2）。时间复杂度为O（M）的空间。□4.3异常检测超边缘异常评分：我们现在提出一种在线异常超边缘检测器，它基于摘要P中捕获的结构和时间信息。我们通过测量定义1中定义的超边缘异常分数来评估每个新到达的超边缘。定义1（超边缘异常评分）。 如果一个新的-在使用分离方法时，差异在识别特定类型的异常中起着重要作用（见第5.2节）。复杂性：对于每个新的超边缘e，HASH NW ALK在短时间内计算得分（e），如引理6中所述。引 理 6 （ 每 超 边 缘 的 评 分 时 间 ） 。 给 定 hyper-graphsummaryP和向量m（e）形式的hype r ed ge，计算score（e）需要O（min（M，e）2）时间。P屋顶。因此，时间复杂度为O（min（M，e））。我们维护和更新超级节点的当前度，这需要O（min（M，|e|））每个新超边e的时间。在时间ti处分割超边缘ei，其异常分数被定义为e中的超级节点对的计算为O（min（M，e）2），并且等式（1）中的每个超级节点对的计算为O（min（M，e）2）。（5）算法复杂度为O（1）得分（ei）=合计u，v∈eiβu，ti·日志auvsuv、（五）时间因此，总的时间复杂度是O（min（M，|e|（2）。 □定理1（每个超边缘的总时间）。HASHNWALK当你被解雇时， β∈[0，∞）是时间ti处u的出现次数，β∈[0，∞]是重要性的超参数，时间复杂度为O（e+min（M，e）2）。P屋顶。定理1由引理1、4和6得出。□事件，au，v =γei（v），且s瑞吉u，v 是Pu，v 就在ti之前。4.4使用多个汇总（可选）直观地，aun ，vn和sun ，vn是“观察到的”普适性（即，例如，当前超边缘中的接近度）和“预期”接近度在从超节点U到超节点V出现的所有过去超边中的接近度，具体地说是。注意，考虑超边中的所有超节点对（包括相同超节点对）之间的关系，并且使用任何聚合函数来聚合它们。可以控制超参数β和聚合函数以捕获各种类型的异常。对于这两种类型的异常，我们定义如下所述的评分函数scoreU和scoreB在HASH NWALK中可以使用多个散列函数来提高其准确性，但代价是速度和空间。具体地说，如果我们使用K个散列函数，维护K个摘要，并独立计算K个分数，那么空间和时间复杂度是使用一个散列函数的K给定来自K个不同总和的超边缘异常分数，我们使用最大值作为最终分数，尽管可以替代地使用任何其他聚合函数。5实验我们回顾我们的实验来回答Q1-Q4：DΣD超越超边缘特别是，如果两个超级大国的比例很高，.+v：mala2277获取更多论文| || |·∈E）||¶HashNWalkSedanSpotMidasF-FADELSH1.47倍6.01X19.8倍(a) 交易（b）SemiU（c）SemiB图3：HASH NWALK是准确的（根据AUROC和Prec。100)而且要快例如，在Transaction数据集中，H ASH N-W ALK的AUROC比4高出47%。7倍更快的速度，相比F-FADE。表1：五个真实世界的超图。数据集|V||E|平均e∈E|e| maxe ∈ E|e|电子邮件-安然14310,8852.47237交易284,807284,8075.996DBLP1,930,3783,700,6812.790280Cite-patent4,641,0211,696,55418.1032,076标签溢出49,99814,458,8752.9685Q1. 性能：HASH-NWALK检测异常超边缘的速度和准确性如何Q2. 发现：什么有意义的事件可以HASH NWALK在真实世界的超图流中检测到的？Q3. 可伸缩性：HASHN-WALK的总运行时间如何随输入流大小而变化？Q4. 参数分析：HASH-NWALK的参数如何影响其性能？5.1实验设置数据集：我们在表1中使用了五个不同的真实世界数据集。在后面的小节中将详细介绍这些方法。机器：我们在一个配备英特尔至强4210 CPU、256 GBRAM和RTX 2080 Ti GPU的工作站上运行F-FADE。我们其他人在配备英特尔酷睿i9- 10900 KF CPU和64 GBRAM的台式机上运行。基线：我们认为四种用于图和超图中异常检测的流算法是竞争对手：• SEDANSPOT[Eswaran和Faloutsos，2018]：给定边缘流 ， 它 旨 在 检 测 意 外 边 缘 ， 即 ， 根 据 个 性 化 的PageRank分数，连接图中稀疏连接部分的节点的边。• MIDAS[Bhatia et al. ，2020]：给定边缘流，其旨在检测 突 发 中 的 相 似 边 缘 。 为 此 ， 它 使 用 Count-Min-Sketch。• F-FADE [Chang et al. ，2021]：给定边缘流，它使用基于频率的矩阵分解，并计算每个边缘的基于似然的异常分数，该异常分数结合了意外性和突发性。• LSH [Ranshous et al. ，2017]：给定一个超边缘流，它使用到目前为止的近似频率计算每个超边缘的意外性。对于基于图的异常检测方法，我们通过团扩展将超图转换为图（第3.1节）。也就是说，每个超边ei被简化为ei2个成对边，并且时间戳ti被分配给每个边。超边缘的异常分数通过聚合成对边缘的异常分数来计算，使用算术/几何平均值、总和和最大值中的最佳值。实现：我们分别在C++和Python中实现了HASH NWALK和LSH对于其他人，我们使用他们的开源实现。SEDANSPOT和MIDAS用C++实现，F-FADE用Python实现评价：鉴于超边缘的异常评分，我们认为-确保AUROC和Precision@k（即，具有最高分数的K个超边中的真阳性的比率5.2Q1.性能比较我 们 考 虑 三 个 超 图 ： Transaction ， semiU 和semiB。交易[Dal Pozzoloet al. ，2015]是信用卡交易的真实世界超图。每个带时间戳的事务由28维特征向量描述。存在欺诈行为492起，占总数的0. 172%的交易。对于每个事务，我们通过将其与之前发生的5个最近的事务分组来生成超边缘。每一个节点都是一个跨动作，每个超边是一组彼此相似的事务。在Email-Enron中，每个节点是一个电子邮件帐户，每个超边是发送者和接收者的集合。每个超边缘的时间戳是发送电子邮件的时间。我们考虑两种情况INJECTION U和INJECTION B，其中我们通过注入200个意外 和 突 发 的 超 边 分 别 生 成 两 个 半 实 超 图 SemiU 和SemiB，在Email-Enron中。两种注入方案设计如下：• 注射U：注入意外的超边缘。1. 选择一个H超边（ei，ti）均匀随机分布。2. C通过用随机节点替换e i中的ei/2个节点来创建一个超边，并将它们的时间戳设置为ti。3. 重复（1）-（2）g次，生成g条超边。• 注射B：注入爆发性超边缘。1. 随机均匀地选择时间t ∈ {t setup +1，···，tm}。2. 随机均匀采样一组n个节点N<$V3. 在时间t创建N的m个均匀随机子集。它们的大小是从{1，···，n}中随机均匀选择的。4. 重复（1）-（3）l次，生成m·l条超边。所有异常在时间t设置之后被注入，并且因此所有方法从时间t设置被评估，其中我们设置t设置= t100（

下载后可阅读完整内容，剩余1页未读，立即下载