HashNWalk: Hash and Random Walk Based Anomaly Detection in Hyperedge Streams

1 Introduction

A variety of real-world graphs, including computer networks, online social networks, and hyperlink networks, have been targets of attacks. Distributed denial-of-service attacks block the availability by causing an unexpected traffic jam on the target machine. In addition, fake connections in online social networks degrade the quality of recommendations, and those in hyperlink networks manipulate the centrality of webpages. Due to its importance and necessity in real-world applications, anomaly detection in graphs has received considerable attention. To detect nodes, edges, and/or subgraphs deviating from structural and temporal patterns in graphs, various numerical measures of the deviation have been proposed with search algorithms [Akoglu et al., 2010; Hooi et al., 2016; Shin et al., 2018]. As many real-world graphs evolve over time, detecting anomalies in real-time, as they appear, is desirable [Bhatia et al., 2020; Eswaran and Faloutsos, 2018].

While graphs model pairwise interactions, interactions in many real-world systems are groupwise (collaborations of co-authors, group interactions on online Q&A platforms, copurchases of items, etc). Such a groupwise interaction is naturally represented as a hyperedge, i.e., a set of an arbitrary number of nodes. A hypergraph, which is a set of hyperedges, is an indispensable extension of a graph, which can only describe pairwise relations. Moreover, many of such real-world hypergraphs evolve over time (e.g., emails exchanged continuously between sets of users, co-authorships established over time, and daily records of co-purchased items), and thus they are typically modeled as a stream of hyperedges.

Despite the great interest in anomaly detection in graphs, the same problem in hypergraphs has been largely unexplored. High-order relationships represented by hyperedges exhibit structural and temporal properties distinguished from those in graphs and hence raise unique technical challenges. Thus, instead of simply decomposing hyperedges into pairwise edges and applying graph-based methods, it is required to take the underlying high-order structures into consideration for anomaly detection in hypergraphs.

To this end, we propose HASHNWALK, an online algorithm for detecting anomalous hyperedges. HASHNWALK maintains a constant-size summary that tracks structural and temporal patterns in high-order interactions in the input stream. Specifically, HASHNWALK incorporates so-called edge-dependent node weights [Chitra and Raphael, 2019] into random walks on hypergraphs to estimate the proximity between nodes while capturing high-order information. Furthermore, we develop an incremental update scheme, which each hyperedge is processed by as it appears.

The designed hypergraph summary is used to score the anomalousness of any new hyperedge in the stream. While the definition of anomaly depends on the context, in this work, we focus on two intuitive aspects: unexpectedness and burstiness. We assume that unexpected hyperedges consist of unnatural combinations of nodes, and bursty hyperedges suddenly appear in a short period of time. Based on the information in the form of a hypergraph summary, we formally define two anomaly score metrics that effectively capture these properties. We empirically show that HASHNWALK is effective in detecting anomalous hyperedges in (semi-)real hypergraphs.

In summary, our contributions are as follows:

• Fast: It takes a very short time for HASHNWALK to pro-

cess each new hyperedge. Specifically, in our experimental setting, it processed 1.4 billion hyperedges within 3 hours.

• Space Efficient: The user can bound the size of the summary, which HASHNWALK maintains.
• Accurate: HASHNWALK successfully detects anomalous hyperedges. Numerically, it outperforms its state-of-the-art competitors with up to 47% higher AUROC.

Reproducibility: The source code and datasets are available at https://github.com/geonlee0325/HashNWalk.

2 RelatedWorks

We discuss prior works on the three topics relevant to this paper: (a) anomaly detection in (hyper)graphs; (b) summarization of edge streams; and (c) hypergraphs and applications.

2.1 Anomaly Detection in Graphs &Hypergraphs.

The problem of detecting anomalous nodes, edges, and/or subgraphs has been extensively studied for both static and dynamic graphs [Akoglu et al., 2015]. In static graphs, nodes whose ego-nets are structurally different from others [Akoglu et al., 2010], edges whose removal significantly reduces the encoding cost [Chakrabarti, 2004], or subgraphs whose density is abnormally high [Beutel et al., 2013; Hooi et al., 2016; Shin et al., 2018] are assumed to be anomalies. In dynamic graphs, temporal edges are assumed to be anomalous if they connect sparsely connected parts in graphs [Eswaran and Faloutsos, 2018] or are unlikely to appear according to underlying models [Aggarwal et al., 2011; Yoon et al., 2019; Bhatia et al., 2020]. In addition, dense subgraphs generated within a short time are considered to be anomalous [Shin et al., 2017; Eswaran et al., 2018]. Recently, embedding based methods have shown to be effective in detecting anomalies in graphs [Yu et al., 2018; Chang et al., 2021].

On the other hand, detecting anomalies in hypergraphs is relatively unexplored. Anomalous nodes in the hypergraph have been the targets of detection by using scan statistics on hypergraphs [Park et al., 2009] or training a classifier based on the high-order structural features of the nodes [Leontjeva et al., 2012]. The anomalousness of unseen hyperedges is measured based on how likely the combinations of nodes are drawn from the distribution of anomalous co-occurrences, which is assumed to be uniform, instead of the distribution of nominal ones [Silva and Willett, 2008]. Approximate frequencies of structurally similar hyperedges obtained by locality sensitive hashing are used to score the anomalousness of hyperedges in the hyperedge stream [Ranshous et al., 2017].

In this paper, we compare ours with the methods that detect anomalous interactions in online settings, i.e., anomaly detectors designed for (hyper)edge streams.

2.2 Summarization of Edge Streams.

Summarization aims to reduce the size of a given graph while approximately maintaining its structural properties. It has been particularly demanded in the context of real-time processing of streaming edges. In [Bhatia et al., 2020], a count-min-sketch is maintained for approximate frequencies of edges. Edge frequencies have been used to answer queries regarding structural properties of graphs [Zhao et al., 2011; Tang et al., 2016]. In [Bandyopadhyay et al., 2016], local properties, such as the number of triangles, are estimated by maintaining topological information of a given graph.

2.3 Empirical Analysis of Hypergraphs.

Structural patterns [Benson et al., 2018a; Do et al., 2020; Lee et al., 2020; Lee et al., 2021; Choe et al., 2022] and dynamical patterns [Benson et al., 2018a; Benson et al., 2018b; Kook et al., 2020; Lee and Shin, 2021; Choo and Shin, 2022] in real-world hypergraphs have been studied extensively, and they are useful for finding anomalies that deviate from them.

3 Preliminaries

In this section, we introduce notations and preliminaries.

3.1 Notations and Concepts

Hypergraphs. A hypergraph G = (V,E) consists of a set of nodes V = {v1, ..., v|V |} and a set of hyperedges E = {e1, ..., e|E|}. Each hyperedge e ∈ E is a non-empty subset of an arbitrary number of nodes. The incidence matrix of G is denoted by H ∈ {0, 1}|E|×|V | , where each entry Hij is 1 if vj ∈ ei and 0 otherwise. A hyperedge stream {(ei, ti)}∞i=0 is a sequence of hyperedges where each hyperedge ei arrives at time ti. For any i and j, if i < j, then ti ≤ tj.

Clique Expansion and Information Loss. Clique expansion [Zhou et al., 2007], where each hyperedge e ∈ E is converted to a clique composed of the nodes in e, is one of the most common ways of transforming a hypergraph G into an ordinary pairwise graph. Clique expansion suffers from the loss of information on high-order interactions. That is, in general, a hypergraph is not uniquely identifiable from its clique expansion. Exponentially many non-isomorphic hypergraphs are reduced to identical clique expansions.

RandomWalks onHypergraphs. A randomwalk on a hypergraph G is formulated in [Chitra and Raphael, 2019] as follows. If the current node is u, (1) select a hyperedge e that contains the node u (i.e., u ∈ e) with probability proportional to ω(e) and (2) select a node v ∈ e with probability proportional to γe(v) and walk to node v. The weight ω(e) is the weight of the hyperedge e, and the weight γe(v) is the weight of node v with respect to the hyperedge e. The weight γe(v) is edge-independent if it is identical for every hyperedge e; and otherwise, it is edge-dependent. If all node weights are edgeindependent, then a random walk on G becomes equivalent to a random walk on its clique expansion [Chitra and Raphael, 2019]. However, if node weights are edge-dependent, random walks on hypergraphs are generally irreversible. That is, they may not be the same as random walks on any undirected graphs. In this sense, if edge-dependent weights are available, random walks are capable of exploiting high-order information beyond clique expansions and thus empirically useful in many machine learning tasks [Hayashi et al., 2020].

Transition Matrix. To incorporate edge-dependent node weights, the incidence matrix H is generalized to a weighted incidence matrix R ∈ R|E|×|V | ≥0 where each entry Rij is γei (vj) if vj ∈ ei and 0 otherwise. Then, the transition probability matrix P ∈ R|V |×|V | of a random walk on the hypergraph G is written as P = D-1 V WD-1 E R, where W ∈ R|V |×|E| denotes the hyperedge-weight matrix where each entry Wji is ω(ei) if vj ∈ ei and 0 otherwise. The matrices DV ∈ R|V |×|V | and DE ∈ R|E|×|E| are diagonal matrices of node degrees and hyperedge weights, respectively. That is, if we let q ∈ R|E| and r ∈ R|V | be the vectors whose entries are all ones, then DV = diag(Wq) and DE = diag(Rr).

3.2 ProblemDescription

The problem that we address in this paper is as follows.

Problem 1. Given a stream {(ei, ti)}∞i=1 of hyperedges, detect anomalous hyperedges, whose structural or temporal properties deviate from general patterns, in near real-time using constant space.

While the definition of anomalous hyperedges depends on the context, we focus on two intuitive perspectives. In one aspect, a hyperedge is anomalous if it consists of an unexpected subset of nodes. That is, we aim to detect hyperedges composed of unusual combinations of nodes. In the other aspect, we aim to identify a set of similar hyperedges that appear in bursts as an anomaly. The sudden emergence of similar interactions often indicates malicious behavior harmful in many applications. In addition, for time-critical applications, we aim to detect such anomalous hyperedges in near real-time, as they appear, using bounded space. While one might tempt to reduce hyperedges into subgraphs and solve the problem as anomalous subgraph detection, this harms the high-order information of the hyperedges. Also, existing works on anomalous subgraphs assume static graphs [Hooi et al., 2016] or detect only the single most anomalous subgraph [Shin et al., 2017], while we aim to score every hyperedge in the stream.

4 ProposedMethod

In this section, we propose HASHNWALK (Algorithm 1), which is a fast and space-efficient algorithm for detecting anomalies in a hyperedge stream. Our main focus is speed and space efficiency since HASHNWALK is expected to process a potentially infinite stream. As illustrated in Figure 2, it maintains a concise and informative summary of a hyperedge stream (Sect. 4.1), which is incrementally updated as each new hyperedge arrives (Sect. 4.2). Once the summary is updated, anomalous hyperedges are identified immediately based on two principled metrics (Sect. 4.3). While HASHNWALK is based on multiple summaries (Sect. 4.4), we assume that it consists of a single summary for ease of explanation.

4.1 Hypergraph Summarization

Hyperedge Representation. We describe how to concisely represent each hyperedge using constant space. Hyperedges, by definition, are flexible in their sizes, and it is non-trivial to represent each hyperedge using the same amount of space. To this end, we map each node into one of M different values using a hash function h(·) : V → {1, ...,M}. We consider each hash value as a supernode that contains the nodes with the same hash value. Due to hash collisions, a hyperedge may contain a supernode multiple times, and the number of occurrences becomes the weight of the supernode with respect to the hyperedge. Formally, we represent each hyperedge e of any size into a M-dimensional vector m(e) ∈ ZM , whose kth element indicates the number of the nodes that are contained in e and mapped into the hash value k (i.e., mk(e) := ∑v∈e 1(h(v) = k)). It is also interpreted as the weight of the supernode k with respect to the hyperedge e. We denote ˜ e as the set of supernodes that hyperedge e contains, i.e., ˜ e := {k |mk(e) > 0}. Note that a hyperedge of any size is represented as a fixed-size vector, whose size M is user-controlled. In addition, the edge-dependent weights of supernodes can be utilized by random walks (see Section 3.1). If we use a constant-time hash function h and a sparse vector format, for each hyperedge e, the time complexity of generating the vector m(e) is O(|e|), as stated in Lemma 1.

Lemma 1 (Time Complexity of Generating m(e)). Given a hyperedge e, it takes O(|e|) time to generate the vector m(e). PROOF. Creating a zero vector in a sparse format (e.g., a hash table) and incrementing mh(v)(e) for every node v ∈ e takes O(|e|) time.

Hypergraph Summary. Below, we describe how to summarize the entire hypergraph for rapid and accurate anomaly detection. We note that the key building block for identifying anomalous hyperedges of both types (i.e., unexpected ones and similar ones in bursts) is to estimate the proximity or structural similarity between nodes. Thus, we summarize

Algorithm 1 HASHNWALK

Input: (1) hyperedge stream: E = {(ei, ti)}∞i=1, (2) number of supernodes M, (3) number of hash functions K, (4) time-decaying parameter α

Output: stream of anomaly scores {yi}∞i=1

• 1: S ∈ RM×M and T ∈ RM ▷ Initialize to zeros
• 2: for each hyperedge (ei, ti) ∈ E do
• 3: m(ei) ← summarize ei via hashing
• ▷ Sect. 4.1
• 4: update S and T

▷ Sect. 4.2

• 5: yi ← (scoreU(ei), scoreB(ei)) ▷ Sect. 4.3
• 6: end for
• 7: return {yi}∞i=1

the input hypergraph in the form of proximity between supernodes, and we extend random walks to measure the proximity. Our summary is based on random walks extended with edge-dependent supernode weights and hyperedge weights; and we use the transition probabilities as their approximation for rapid updates (see Section 4.2). Specifically, we summarize the input hypergraph as a matrix ˜ P := ˜D-1 V ˜W ˜D-1 E ˜R ∈ RM×M , where ˜R ∈ R|E|×M is the weighted incidence matrix where each entry ˜Ri˜ v is γ˜ e(˜ v) if ˜ v ∈ ˜ ei and 0 otherwise. The matrix ˜W ∈ RM×|E| denotes the hyperedge-weight matrixwhere ˜W˜ v˜ e is ω(˜ e) if ˜ v ∈ ˜ e and 0 otherwise. The matrices ˜DV ∈ RM×M and ˜DE ∈ R|E|×|E| are diagonal matrices of supernode degrees and hyperedge weights, respectively. Then, ˜ P is the transition probability matrix where each entry ˜ P˜u˜ v is the transition probability from supernode ˜u to ˜ v:

where ˜W˜u is the weighted degree of the ˜u, i.e., ˜W˜u := ∑|E| i=1 ω(˜ ei) · 1(˜u ∈ ˜ ei), and ˜R˜ ei is the sum of the weights of the supernodes in the ˜ ei, i.e., ˜R˜ ei := ∑˜ v∈˜ ei γ˜ ei (˜ v).

Edge-Dependent Supernode Weights. If edge-dependent supernode weights are available, random walks utilize highorder information beyond clique expansions. Such weights are naturally obtained from the aforementioned vector representation of hyperedges. That is, we use the number of the occurrences of each supernode ˜ v in each hyperedge ˜ ei as the weight of ˜ v with respect to ˜ ei. Formally, γ˜ ei (˜ v) = m˜ v(ei), and thus R˜ ei = ∑˜ v∈˜ ei γ˜ ei (˜ v) = ∑Mk=1 mk(ei) = |ei|.

Time-Decaying Hyperedge Weights. In order to facilitate identifying recent bursts of similar hyperedges, which are one of our focuses, we emphasize recent hyperedges with large weights. Specifically, at current time t, we define the weight of each hyperedge ei, which is arrived at time ti, as ω(ei) = ker(t - ti) = αt-ti (1 - α) where ker(x) := αx (1 - α) is a kernel function for quantifying time decay and α ∈ [0, 1) is a hyperparameter that determines the degree of emphasis. Specifically, smaller α more emphasizes recent hyperedges.

4.2 Incremental Update

Challenges. Constructing ˜ P from scratch, which takes O(|E|·M 2 ) time, is undesirable when immediate responses to anomalies are demanded. In addition, when hyperedges are streamed indefinitely, materializing ˜W, ˜DE, and ˜R, which are used to compute ˜ P, is prohibitive since their sizes are proportional to the number of hyperedges.

ProposedUpdated Scheme. We present an incremental algorithm for efficiently but exactly updating ˜ P in response to a new hyperedge. The proposed update scheme maintains only ˜ P , whose size is controllable by the user, without materializing any larger matrix. Assume m hyperedges e1, ..., em have arrived, and let ˜ P (m) ˜u˜ v be the proximity from supernode ˜u to supernode ˜ v in them. We introduce a matrix S ∈ RM×M and a vector T ∈ RM , and for any supernodes ˜u and ˜ v, their entries when the hyperedge em arrives at time tm are

Then, based on Eq. (1) and the predefined hyperedge weight function ker(x) = αx (1-α), ˜ P (m) ˜u˜ v is written as

Instead of directly tracking the proximity matrix ˜ P, we track aforementioned S and T , whose entries are initialized to zero. Each entry S˜u˜ v and T˜u can be updated in constant time, as presented in Lemmas 2 and 3, and once they are updated, we can compute ˜ P (m) ˜u˜ v in O(1) time by Eq. (2), if necessary.

Lemma 2 (Updating S˜u˜ v). For any m≥ 0, when the hyperedge em+1 arrives at tm+1, Eq. (3) holds.

Lemma 3 (Updating T˜u). For any m ≥ 0, when the hyperedge em+1 arrives at tm+1, Eq. (4) holds.

Lemma 2 and Lemma 3 are immediate from the definitions of S(m) ˜u˜ v and T (m) ˜u .

Complexity. Notably, if ˜u /∈ ˜ em+1, 1(˜u ∈ ˜ em+1) = 0 holds and if ˜ v /∈ ˜ em+1, γ˜ em+1 (˜ v) = 0 holds. Thus, if ˜u or ˜ v is not included in the new hyperedge (i.e., ˜u /∈ ˜ em+1 or ˜ v /∈ ˜ em+1), S˜u˜ v remains the same (i.e., S(m+1) ˜u˜ v = S(m) ˜u˜ v ) and thus does not need any update. Similarly, T˜u does not change if ˜u is not included in ˜ em+1. These facts significantly reduce the update time of the summary, enabling near realtime processing of each hyperedge. To sum up, in response to a new hyperedge, HASHNWALK updates the summary in a short time using constant space, as stated in Lemmas 4 and 5, respectively.

Lemma 4 (Update Time Per Hyperedge). Given the sparse vector representation m(e) of a hyperedge e, updating S ∈ RM×M and T ∈ RM using Eq. (3) and Eq. (4) takes O(min(M, |e|)2 ) time.

PROOF. The number of supernodes in e is |˜ e|, which is at most the number of nodes |e| and the number of supernodes M, and thus |˜ e|= O(min(M, |e|)). Then, |˜ e|2 elements of S and |˜ e| elements of T are updated by Eq. (3) and Eq. (4), and the update time is constant per element. Therefore, the total time complexity is O(min(M, |e|)2 ). ■

Lemma 5 (Constant Space). The maintained summary ˜ P takes O(M 2 ) space.

PROOF. The matrix S and the vector T require O(M 2 ) and O(M) space, respectively. ■

4.3 Anomaly Detection

Hyperedge Anomaly Score. We now propose an online anomalous hyperedge detector, which is based on the structural and temporal information captured in the summary ˜ P . We evaluate each newly arriving hyperedge by measuring a hyperedge anomaly score defined in Definition 1.

Definition 1 (Hyperedge Anomaly Score). Given a newly arriving hyperedge ei at time ti, its anomaly score is defined as

where d˜u,ti is the number of occurrences of ˜u at time ti, β ∈ [0,∞) is a hyperparameter for the importance of the occurrences, a˜u,˜ v = γ˜ ei (˜ v) ˜R˜ ei , and s˜u,˜ v is ˜ P˜u,˜ v just before ti. Intuitively, a˜u,˜ v and s˜u,˜ v are the "observed" proximity (i.e., the proximity in the current hyperedge) and "expected" proximity (i.e., the proximity in all past hyperedges appearing before ti) from supernode ˜u to supernode ˜ v, respectively.

Note that the relationships between all pairs of supernodes in the hyperedge, including the pairs of the same supernode, are taken into consideration, and they are aggregated using any aggregation functions. The hyperparameter β and the aggregate function can be controlled to capture various types of anomalies. For the two types of anomalies, we define scoring functions scoreU and scoreB as described below.

Unexpectedness (scoreU). Intuitively, a˜u,˜ v/s˜u,˜ v in Eq. (5) measures how much the proximity from the supernode ˜u to ˜ v in the new hyperedge ei deviates from the proximity in the past hyperedges. Specifically, the ratio is high if two supernodes ˜u and ˜ v that have been far from each other in past hyperedges unexpectedly co-appear with high proximity in the new hyperedge. Thus, in scoreU, which is the anomaly score for identifying unexpected hyperedges, we focus on the ratio by setting β = 0. In order to detect any such unexpected pairs of supernodes in the hyperedge, scoreU uses the maximum ratio as the final score (i.e., aggregate = max).

Burstiness (scoreB). In order to detect similar hyperedges that appear in bursts, the number of occurrences of supernodes is taken into consideration. Supernodes, by definition, are subsets of nodes, and similar hyperedges tend to share many supernodes. If a large number of similar hyperedges appear in a short period of time, then the occurrences of the supernodes in them tend to increase accordingly. Thus, in scoreB, which is the anomaly score for identifying recent bursts of similar hyperedges, we set β to a positive number (specifically, 1 in this work) to take such occurrences (i.e., dβ˜u,ti in Eq. (5)) into consideration, in addition to unexpectedness (i.e., a˜u,˜ v/s˜u,˜ v in Eq. (5)). We reflect the degrees of all supernodes in the hyperedge by averaging the scores from all supernode pairs (i.e., aggregate = mean).

Complementarity of the Anomaly Scores. While the only differences between scoreU and scoreB are the consideration of the current degree of supernodes (i.e., dβ˜u,ti ) and the aggregation methods, the differences play an important role in identifying specific types of anomalies (see Section 5.2).

Complexity. For each new hyperedge e, HASHNWALK computes score(e) in a short time, as stated in Lemma 6.

Lemma 6 (Scoring Time Per Hyperedge). Given the hypergraph summary ˜ P and a hyperedge e in the form of a vector m(e), computing score(e) takes O(min(M, |e|)2 ) time.

PROOF. The number of supernodes in e is O(min(M, |e|)). We maintain and update the current degrees of supernodes, which takes O(min(M, |e|)) time for each new hyperedge e. There are O(min(M, |e|)2 ) pairs of supernodes in ˜ e, and the computation for each supernode pair in Eq. (5) takes O(1) time. Hence, the total time complexity is O(min(M, |e|)2 ).■

Theorem 1 (Total Time Per Hyperedge). HASHNWALK takes O(|e|+min(M, |e|)2 ) time to process a hyperedge e. PROOF. Theorem 1 follows from Lemmas 1, 4, and 6. ■

4.4 UsingMultiple Summaries (Optional)

Multiple hash functions can be used in HASHNWALK to improve its accuracy at the expense of speed and space. Specifically, if we use K hash functions, maintain K summaries, and compute K scores independently, then the space and time complexities become K times of those with one hash function. Given hyperedge anomaly scores fromK different summaries, we use the maximum one as the final score, although any other aggregation function can be used instead.

5 Experiments

We review our experiments to answer Q1-Q4:

• Q1. Performance: How rapidly and accurately does HASHNWALK detect anomalous hyperedges?
• Q2. Discovery: What meaningful events can HASHNWALK detect in real-world hypergraph streams?
• Q3. Scalability: How does the total runtime of HASHNWALK change with respect to the input stream size?
• Q4. Parameter Analysis: How do the parameters of HASHNWALK affect its performance?

5.1 Experimental Settings

Datasets. We used five different real-world datasets in Table 1. They are described in detail in later subsections.

Machines. We ran F-FADE on a workstation with an Intel Xeon 4210 CPU, 256GB RAM, and RTX2080Ti GPUs. We ran the others on a desktop with an Intel Core i9-10900KF CPU and 64GB RAM.

Baselines. We consider four streaming algorithms for anomaly detection in graphs and hypergraphs as competitors:

• SEDANSPOT [Eswaran and Faloutsos, 2018]: Given a stream of edges, it aims to detect unexpected edges, i.e., edges that connect nodes from sparsely connected parts of the graph, based on personalized PageRank scores.
• MIDAS [Bhatia et al., 2020]: Given a stream of edges, it aims to detect similar edges in bursts. To this end, it uses the Count-Min-Sketch.
• F-FADE [Chang et al., 2021]: Given a stream of edges, it uses frequency-based matrix factorization and computes the likelihood-based anomaly score of each edge that combines unexpectedness and burstiness.
• LSH [Ranshous et al., 2017]: Given a stream of hyperedges, it computes the unexpectedness of each one using its approximate frequency so far.

For graph-based anomaly detection methods, we transform hypergraphs into graphs via clique expansion (Section 3.1). That is, each hyperedge ei is reduced to |ei|2 pairwise edges, and the timestamp ti is assigned to each edge. The anomaly score of the hyperedge is computed by aggregating the anomaly scores of the pairwise edges, using the best one among arithmetic/geometric mean, sum, and maximum.

Implementation. We implemented HASHNWALK and LSH in C++ and Python, respectively. For the others, we used the official open-source implementation.

Evaluation. Given anomaly scores of hyperedges, we measure AUROC and Precision@k (i.e., the ratio of true positives among k hyperedges with the highest scores).

5.2 Q1. Performance Comparison

We consider three hypergraphs: Transaction, SemiU, and SemiB. Transaction [Dal Pozzolo et al., 2015] is a real-world hypergraph of credit card transactions. Each timestamped transaction is described by a 28 dimensional feature vector. There exist 492 frauds, which account for 0.172% of the entire transactions. For each transaction, we generate a hyperedge by grouping it with 5 nearest transactions that occurred previously. Thus, each node is a transaction, and each hyperedge is a set of transactions that are similar to each other.

In Email-Enron, each node is an email account and each hyperedge is the set of the sender and receivers. The timestamp of each hyperedge is when the email was sent. We consider two scenarios INJECTIONU and INJECTIONB, where we generate two semi-real hypergraphs SemiU and SemiB by injecting 200 unexpected and bursty hyperedges, respectively, in Email-Enron. The two injection scenarios are designed as follows:

• INJECTIONU: Injecting unexpected hyperedges.
• Select a hyperedge (ei, ti) ∈ E uniformly at random.
• Create a hyperedge by replacing ⌈|ei| /2⌉ nodes in ei with random ones, and set their timestamp to ti.
• Repeat (1)-(2) g times to generate g hyperedges.
• INJECTIONB: Injecting bursty hyperedges.
• Select a time t ∈ {tsetup + 1, · · · , tm} uniformly at random.
• Sample a set of n nodes N ⊆ V uniformly at random.
• Create m uniform random subsets of N at time t. Their sizes are chosen uniformly at random from {1, · · · , n}.
• Repeat (1) - (3) l times to generate m · l hyperedges.

All anomalies are injected after time tsetup, and thus all methods are evaluated from time tsetup where we set tsetup = t100 (< t|E|·0.01). In INJECTIONU, we set g = 200. In INJECTIONB, we set m = 20, n = 5, and l = 10.

Accuracy. In Transaction, we use scoreU and set α = 0.98, K = 4, and M = 350. In SemiU and SemiB, we use scoreU and scoreB, respectively, and commonly set α = 0.98, K = 15, and M = 20. As discussed later, these summaries take up less space than the original hypergraphs. As shown in Figure 3, HASHNWALK accurately detects anomalous hyperedges in real and semi-real hypergraphs. Notably, while most methods fail to find any anomalous hyperedges in their top 50 (see Figure 1a in Section 1) or top 100 (Figure 3a) hyperedges with the highest anomaly scores, HASHNWALK is successful. In addition, HASHNWALK accurately detects both unexpected and bursty hyperedges. Note that while several competitors successfully spot bursty hyperedges in SemiB, most of them fail to spot unexpected ones in SemiU. Specifically, in SemiU, HASHNWALK achieves 6.01× higher precision@100 with 27× faster speed than SEDANSPOT.

Speed. As seen in Figure 3, HASHNWALK is one of the fastest methods among the considered ones. Notably, in SemiU, HASHNWALK is 27× faster than the second most accurate method.

Space Usage. We analyze the amount of space used by HASHNWALK. Let CZ and CF be the numbers of bits to encode an integer and a floating number, respectively, and we assume CZ = CF = 32. The size of the original hypergraph G = (V,E) is the sum of the hyperedge sizes, and precisely, CZ ·∑e∈E |e| bits are required to encode the hypergraph. As described in Lemma 5 in Section 4.2, for each hash function, HASHNWALK tracks a matrix S ∈ RM×M and a vector T ∈ RM , and thus it requires CF · K · (M 2 +M) bits with K hash functions. We set K = 4 and M = 350 in Transaction; and K = 15 and M = 20 in SemiU and SemiB. As a result, HASHNWALK requires about 28.6% and 22.5% of the space required for the original hypergraphs, in Transaction and semi-real hypergraphs, respectively. For competitors, we conduct hyperparameter tuning, including configurations requiring more space than ours. 1

Complementarity of scoreU and scoreB. As seen in Table 2, while scoreU is effective in detecting unexpected hyperedges, it shows relatively low accuracy in detecting bursty hyperedges. The opposite holds in scoreB. These indicate the two metrics scoreU and scoreB are complementary.

1 See https://github.com/geonlee0325/HashNWalk for details.

5.3 Q2. Discovery

Here, we share the results of case studies conducted on the DBLP, Cite-patent, and Tags-overflow datasets.

Discoveries in Co-authorship Hypergraph. DBLP contains information of bibliographies of computer science publications. Each node represents an author, and each hyperedge consists of authors of a publication. The timestamp of the hyperedge is the year of publication. Here, we investigate how authors co-work with different researchers. For each author v who have published at least 100 papers, we compute the average unexpectedness and burstiness scores of the hyperedges that v is contained in, which we denote by avgU(v) and avgB(v), respectively. We analyze several authors whose ratio avgU(v)/avgB(v) is the highest or the lowest. Intuitively, authors with low ratios tend to co-work in a bursty manner with expected co-authors, while those with high ratios tend to work steadily with unexpected co-authors. Surprisingly, Dr. Bill Hancock, whose avgU(v)/avgB(v) ratio is the lowest, published 186 papers all alone. Furthermore, Dr. Hancock published 139 papers in 2000. On the other hand, Dr. Seymour Ginsburg, whose avgU(v)/avgB(v) is the highest, published 114 papers from 1958 to 1999 (2.7 papers per year). In addition, 18 co-authors (out of 38) coauthored only one paper with Dr. Ginsburg. In fact, avgU and avgB of the most authors are clustered as seen in Figure 4a, and the top authors are those with the largest (or the smallest) slope. We further conduct case studies on two specific authors Dr. Shinji Sakamoto and Dr. King-Sun Fu, whose co-working patterns are very different. As seen in Figure 4b, while Dr. Sakamoto collaborated on most papers with a few researchers, Dr. Fu enjoyed co-working with many new researchers. These findings support our intuition behind the proposed measures, scoreU and scoreB.

Discoveries in Patent Citation Hypergraph. We use Cite-patent [Tang et al., 2012], which is a citation hypergraph where each node is a patent and each hyperedge is the set of patents cited by a patent. The timestamp of each hyperedge is the year of the citation ranging from 2000 to 2012. Using HASHNWALK, we extract some hyperedges with high scoreU or scoreB. Then, we represent each hyperedge as a |V |-dimensional binary vector indicating which nodes belong to the hyperedge. We visualize the hyperedges after reducing the dimension of the vectors via T-SNE in Figure 5. While unexpected hyperedges are spread, bursty hyperedges are closely located, indicating structurally similar hyperedges arrive in bursts. In addition, we closely examine the citation patterns of suspicious patents detected by HASHNWALK. As seen in Figure 1c, patents with unexpected or bursty citations are effectively detected.

Discoveries in Online Q&A Cite. We share the results of a case study using Tags-overflow. In the dataset, nodes are tags and hyperedges are the set of tags attached to a question. Hyperedges with high scoreU (i.e., sets of unexpected keywords) include: {channel, ignore, antlr, hidden, whitespace}, {sifr, glyph, stling, text-styling, embedding}, and {retro-computing, boot, floppy, amiga}. Hyperedges with high scoreB (i.e., sets of bursty keywords) include: {python, javascript}, {java, adobe, javascript}, and {c#, java}. Notably, sets of unpopular tags tend to have high unexpectedness, while those containing popular keywords, such as python and javascript, have high burstiness.

5.4 Q3. Scalability

To evaluate the scalability of HASHNWALK, we measure how rapidly it updates the hypergraph summary and computes the anomaly scores as the number of hyperedges grows. To this end, we upscale Email-Enron, which originally consists of 10,885 hyperedges, by 21 to 217 times, and measure the total runtime of HASHNWALK. As seen in Figure 1b, the total runtime is linear in the number of hyperedges, which is consistent with our theoretical analysis (Theorem 1 in Section 4). That is, the time taken for processing each hyperedge is near constant. Notably, HASHNWALK is scalable enough to process a stream of 1.4 billion hyperedges within 3 hours.

5.5 Q4. Parameter Analysis

We evaluate HASHNWALK under different parameter settings, and the results are shown in Figure 6. In most cases, there is a positive correlation with M (i.e., the number of supernodes) and K (i.e., the number of hash functions). Intuitively, a larger number of supernodes and hash functions collectively reduce the variance due to randomness introduced by hash functions. However, since the space usage is dependent on these parameters, a trade-off between the accuracy and the space usage should be considered. In addition, properly setting α (i.e., time decaying parameter) improves the accuracy, as shown in Figure 6, which indicates that not only structural information but also the temporal information is critical in detecting anomalies in hyperedge streams.

6 Conclusion

In this work, we propose HASHNWALK, an online anomaly detector for hyperedge streams. HASHNWALK maintains a random-walk-based hypergraph summary with constant space, and it is incrementally updated in near real-time. Using the summary, HASHNWALK computes two anomaly scores that are effective in identifying (a) hyperedges composed of unexpected combinations of nodes and (b) those appearing in bursts. Our experiments demonstrate the speed, accuracy, and effectiveness of HASHNWALK in (semi-)real datasets.

Acknowledgments

This work was supported by National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. NRF-2020R1C1C1008296) and Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. 2019-0-00075, Artificial Intelligence Graduate School Program (KAIST)).