{'fraction_non_alphanumeric': 0.048925549615888415, 'fraction_numerical': 0.009416929231422805, 'mean_word_length': 4.520422122337307, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sketch-Based Anomaly Detection in Streaming Graphs

Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? For example, in intrusion detection, existing work seeks to detect either anomalous edges or anomalous subgraphs, but not both. In this paper, we first extend the count-min sketch data structure to a higher-order sketch. This higher-order sketch has the useful property of preserving the dense subgraph structure (dense subgraphs in the input turn into dense submatrices in the data structure). We then propose 4 online algorithms that utilize this enhanced data structure, which (a) detect both edge and graph anomalies; (b) process each edge and graph in constant memory and constant update time per newly arriving edge, and; (c) outperform state-of-the-art baselines on 4 real-world datasets. Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.


INTRODUCTION
Consider an intrusion detection system, in which many forms of anomalous behavior can be described as a group of attackers making a large number of connections to some set of targeted machines to restrict accessibility or look for potential vulnerabilities. We can model this as a dynamic graph, where nodes correspond to machines, and each edge represents a timestamped connection from one machine to another. In this graph, anomalous behavior often takes the form of a dense subgraph, as shown in several real-world datasets in [1][2][3]. Thus, we ask the question: Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to both edges and subgraphs in an online manner, for the purpose of detecting unusual behavior, using constant memory and constant update time per newly arriving edge?
Several approaches [4][5][6][7][8][9][10] aim to detect anomalies in graph settings. However, these approaches focus on static graphs, whereas many real-world graphs are time-evolving in nature. In streaming or online graph scenarios, some methods can detect the presence of anomalous edges, [3,[11][12][13], while others can detect anomalous subgraphs [1,2,14]. However, all existing methods are limited to either anomalous edge or graph detection but not able to detect both kinds of anomalies, as summarized in Table 1. As we discuss in Section 7, our approach outperforms existing methods in both accuracy and running time; and on both anomalous edge and subgraph detection scenarios. Moreover, our approach is the only streaming method that makes use of dense subgraph search to detect graph anomalies while only requiring constant memory and time.
We first extend the two-dimensional sketch to a higher-order sketch to enable it to embed the relation between the source and destination nodes in a graph. A higher-order sketch has the useful property of preserving the dense subgraph structure; dense subgraphs in the input turn into dense submatrices in this data structure. Thus, the problem of detecting a dense subgraph from a large graph reduces to finding a dense submatrix in a constant size matrix, which can be achieved in constant time. The higherorder sketch allows us to propose several algorithms to detect both anomalous edges and subgraphs in a streaming manner. We introduce two edge anomaly detection methods, AnoEdge-G, and AnoEdge-L, and two graph anomaly detection methods AnoGraph, and AnoGraph-K, that use the same data structure to detect the presence of a dense submatrix, and consequently anomalous edges, or subgraphs respectively. All our approaches process edges and graphs in constant time, and are independent of the graph size, i.e., they require constant memory. We also provide theoretical guarantees on the higher-order sketch estimate and the submatrix density measure. In summary, the main contributions of our paper are: (1) Higher-Order Sketch (Section 4): We transform the dense subgraph detection problem into finding a dense submatrix (which can be achieved in constant time) by extending the count-min sketch (CMS) [15] data structure to a higher-order sketch. (2) Streaming Anomaly Detection (Sections 5,6): We propose four novel online approaches to detect anomalous edges and graphs in real-time, with constant memory and update time. Moreover, this is the first streaming work that incorporates dense subgraph search to detect graph anomalies in constant memory/time. (3) Effectiveness (Section 7): We outperform all state-of-theart streaming edge and graph anomaly detection methods on four real-world datasets.  [41,42] discuss deep learning based anomaly detection and [43][44][45][46][47] discus dense subgraph discovery, however, such approaches are unable to detect anomalies in a streaming manner. [4][5][6][7][8][9][10] are limited to anomaly detection in static graphs. In this section, however, we limit our review only to methods detecting edge and graph anomalies in dynamic graphs; see [48] for an extensive survey.
Edge Stream Methods: HotSpot [49] detects nodes whose egonets suddenly change. RHSS [50] focuses on sparsely-connected graph parts. CAD [51] localizes anomalous changes using commute time distance measurement. More recently, DenseStream [1] maintains and updates a dense subtensor in a tensor stream. SedanSpot [11] identifies edge anomalies based on edge occurrence, preferential attachment, and mutual neighbors. PENminer [12] explores the persistence of activity snippets, i.e., the length and regularity of edge-update sequences' reoccurrences. F-FADE [13] aims to detect anomalous interaction patterns by factorizing their frequency. MIDAS [3] identifies microcluster-based anomalies. However, all these methods are unable to detect graph anomalies.
Graph Stream Methods: DTA/STA [52] approximates the adjacency matrix of the current snapshot using matrix factorization. Copycatch [53] spots near-bipartite cores where each node is connected to others in the same core densely within a short time. SPOT/DSPOT [33] use extreme value theory to automatically set thresholds for anomalies. IncGM+ [54] utilizes incremental method to process graph updates. More recently, DenseAlert identifies subtensors created within a short time and utilizes incremental method to process graph updates or subgraphs more efficiently. SpotLight [2] discovers anomalous graphs with dense bi-cliques, but uses a randomized approach without any search for dense subgraphs. AnomRank [14], inspired by PageRank [55], iteratively updates two score vectors and computes anomaly scores. However, these methods are slow and do not detect edge anomalies. Moreover, they do not search for dense subgraphs in constant memory/time.

PROBLEM
Let ℰ = { 1 , 2 , · · · } be a stream of weighted edges from a timeevolving graph G. Each arriving edge is a tuple = ( , , , ) consisting of a source node ∈ V, a destination node ∈ V, a weight , and a time of occurrence , the time at which the edge is added to the graph. For example, in a network traffic stream, an edge could represent a connection made from a source IP address to a destination IP address at time . We do not assume that the set of vertices V is known a priori: for example, new IP addresses or user IDs may be created over the course of the stream.
We model G as a directed graph. Undirected graphs can be handled by treating an incoming undirected edge as two simultaneous directed edges, one in each direction. We also allow G to be a multigraph: edges can be created multiple times between the same pair of nodes. Edges are allowed to arrive simultaneously: i.e. +1 ≥ , since in many applications is given as a discrete time tick.
The desired properties of our algorithm are as follows: • Detecting Anomalous Edges: To detect whether the edge is part of an anomalous subgraph in an online manner. Being able to detect anomalies at the finer granularity of edges allows early detection so that recovery can be started as soon as possible and the effect of malicious activities is minimized. • Detecting Anomalous Graphs: To detect the presence of an unusual subgraph (consisting of edges received over a period of time) in an online manner, since such subgraphs often correspond to unexpected behavior, such as coordinated attacks.

HIGHER-ORDER SKETCH & NOTATIONS
Count-min sketches (CMS) [15] are popular streaming data structures used by several online algorithms [56]. CMS uses multiple hash functions to map events to frequencies, but unlike a hash table uses only sub-linear space, at the expense of overcounting some events due to collisions. Frequency is approximated as the minimum over all hash functions. CMS, shown in Figure 1(a), is represented as a two-dimensional matrix where each row corresponds to a hash function and hashes to the same number of buckets (columns). We introduce a Higher-order CMS (H-CMS) data structure where each hash function maps multi-dimensional input to a generic tensor instead of mapping it to a row vector. H-CMS enhances CMS by separately hashing the individual components of an entity thereby maintaining more information. Figure 1(b) shows a 3-dimensional H-CMS that can be used to hash two-dimensional entities such as graph edges to a matrix. The source node is hashed to the first dimension and the destination node to the other dimension of the sketch matrix, as opposed to the original CMS that will hash the entire edge to a one-dimensional row vector as shown in Figure  1(a).
We use a 3-dimensional H-CMS (operations described in Algorithm 1) where the number of hash functions is denoted by , and matrix M corresponding to -th hash function ℎ is of dimension × , i.e., a square matrix. For each ∈ [ ], the -th hash function denoted by ℎ ( , ) maps an edge ( , ) to a matrix index (ℎ ′ ( ), ℎ ′′ ( )), i.e., the source node is mapped to a row index and the destination node is mapped to a column index. That is, ℎ ( , ) = (ℎ ′ ( ), ℎ ′′ ( )). Therefore, each matrix in a 3dimensional H-CMS captures the essence of a graph adjacency matrix. Dense subgraph detection can thus be transformed into a dense submatrix detection problem (as shown in Figure 2) where   Figure 2: (a) Dense subgraph in the original graph between source nodes 1 , 2 , and destination nodes 1 , 2 , 3 is transformed to a (b) Dense submatrix between rows 1 , 2 , and columns 1 , 2 , 3 in the H-CMS. Since the H-CMS can overestimate the count by possible collisions (but not underestimate because we update and keep all the counts for every hash function), we have ( , ) ≤ˆ( , ). We define to be the number of all observations so far; i.e., = , ( , ). The following theorem shows that the 3-dimensional H-CMS has the estimate guarantees similarly to the CMS:
Proof. Fix ∈ [ ]. Let = ( , ) and = ( , ) such that ≠ . This implies that at least one of the following holds: ≠ or ≠ . Since ℎ ′ (and ℎ ′′ ) is chosen uniformly at random Thus, in the both cases, the probability of the collision is (ℎ ( ) = ℎ ( )) = . Thus, by defining , = . By the Markov's inequality on the right-hand side, we have that Theorem 1 shows that we have the estimate guarantee even if we use the same hash function for both the source nodes and the destination node (i.e., ℎ ′ = ℎ ′′ ). Thus, with abuse of notation, we write ℎ( , ) = (ℎ( ), ℎ( )) when ℎ ′ = ℎ ′′ by setting ℎ = ℎ ′ = ℎ ′′ on the right-hand side. On the other hand, in the case of ℎ ′ ≠ ℎ ′′ , it would be possible to improve the estimate guarantee in Theorem 1. For example, if we can make ℎ to be chosen uniformly at random from a weakly universal set of hash functions (by defining corresponding families of distributions for ℎ ′ and ℎ ′′ under some conditions), then we can set = ⌈ √︃ ⌉ to have the same estimate guarantee as that of Theorem 1 based on the proof of Theorem 1. The analysis for such a potential improvement is left for future work as an open problem.
Frequently used symbols are discussed in Table 2, and we leverage the subgraph density measure discussed in [57] to define the submatrix ( , ) density.

EDGE ANOMALIES
In this section, using the H-CMS data structure, we propose AnoEdge-G and AnoEdge-L to detect edge anomalies by checking whether the received edge when mapped to a sketch matrix element is part of a dense submatrix. AnoEdge-G finds a Global dense submatrix and performs well in practice while AnoEdge-L maintains and updates a Local dense submatrix around the matrix element and therefore has better time complexity.

AnoEdge-G
AnoEdge-G, as described in Algorithm 2, maintains a temporally decaying H-CMS, i.e. whenever 1 unit of time passes, we multiply all the H-CMS counts by a fixed factor (lines 2,4). This decay simulates the gradual 'forgetting' of older, and hence, more outdated information. When an edge ( , ) arrives, , are mapped to matrix indices ℎ( ), ℎ( ) respectively for each hash function ℎ, and the corresponding H-CMS counts are updated (line 5). Edge-Submatrix-Density procedure (described below) is then called to compute the density of a dense submatrix around (ℎ( ), ℎ( )). Density is reported as the anomaly score for the edge; a larger density implies that the edge is more likely to be anomalous.
Edge-Submatrix-Density procedure calculates the density of a dense submatrix around a given index (ℎ( ), ℎ( )). A 1×1 submatrix represented by and , is initialized with row-index ℎ( ) and column index ℎ( ) (line 9). The submatrix is iteratively expanded by greedily selecting a row from (or a column from ) that obtains the maximum row (or column) sum with the current submatrix (lines 11,12). This selected row (or column ) is removed from (or ), and added to (or ) (lines 14,16). The process is repeated until both and are empty (line 10). Density of the current submatrix is computed at each iteration of the submatrix expansion process and the maximum over all greedily formed submatrix densities is returned (lines 17,18).

AnoEdge-L
Inspired by Definition 1, we define the likelihood measure of a matrix index (ℎ( ), ℎ( )) with respect to a submatrix ( , ), as the sum of the elements of submatrix ( , ) that either share row with index ℎ ′′ ( ) or column with index ℎ ′ ( ) divided by the total number of such elements. Definition 2. Given matrix M, likelihood of an index ℎ( , ) with respect to a submatrix represented by ⊆ and ⊆ , is: AnoEdge-L, as described in Algorithm 3, maintains a temporally decaying H-CMS to store the edge counts. We also initialize a mutable submatrix of size 1 × 1 with a random element, and represent it as ( , ). As we process edges, we greedily update ( , ) to maintain it as a dense submatrix. When an edge arrives, H-CMS counts are first updated, and the received edge is then used to check whether to expand the current submatrix (line 7). If the submatrix density increases upon the addition of the row (or column), then the row-index ℎ( ) (or column-index ℎ( )) is added to the current submatrix, ( , ). To remove the row(s) and column(s) decayed over time, the process iteratively selects the row (or column) with the minimum row-sum (or column-sum) until removing it increases the current submatrix density. This ensures that the current submatrix is as condensed as possible (line 9). As defined in Definition 2, AnoEdge-L computes the likelihood score of the edge with respect to ( , ) (line 10). A higher likelihood measure implies that the edge is more likely to be anomalous.

GRAPH ANOMALIES
We now propose AnoGraph and AnoGraph-K to detect graph anomalies by first mapping the graph to a higher-order sketch, and then checking for a dense submatrix. These are the first streaming algorithms that make use of dense subgraph search to detect graph anomalies in constant memory and time. AnoGraph greedily finds a dense submatrix with a 2-approximation guarantee on the density measure. AnoGraph-K leverages Edge-Submatrix-Density from Algorithm 2 to greedily find a dense submatrix around strategically picked matrix elements performing equally well in practice.

AnoGraph
AnoGraph, as described in Algorithm 4, maintains an H-CMS to store the edge counts that are reset whenever a new graph arrives. The edges are first processed to update the H-CMS counts. Ano-Graph-Density procedure (described below) is then called to find the dense submatrix. AnoGraph reports anomaly score as the density of the detected (dense) submatrix; a larger density implies that the graph is more likely to be anomalous.
AnoGraph-Density procedure computes the density of a dense submatrix of matrix M. The current dense submatrix is initialised as matrix M and then the row (or column) from the current submatrix with minimum row (or column) sum is greedily removed. This process is repeated until and are empty (line 11). The density of the current submatrix is computed at each iteration of the submatrix expansion process and the maximum over all densities is returned (lines 18, 19).
Algorithm 4 is a special case of finding the densest subgraph in a directed graph problem [57] where the directed graph is represented as an adjacency matrix and detecting the densest subgraph essentially means detecting dense submatrix. We now provide a guarantee on the density measure.

AnoGraph-K
Similar to AnoGraph, AnoGraph-K maintains an H-CMS which is reset whenever a new graph arrives. It uses the AnoGraph-K-Density procedure (described below) to find the dense submatrix. AnoGraph-K is summarised in Algorithm 5.
AnoGraph-K-Density computes the density of a dense submatrix of matrix M. The intuition comes from the heuristic that the matrix elements with a higher value are more likely to be part of a dense submatrix. Hence, the approach considers largest elements of the matrix M and calls Edge-Submatrix-Density from Algorithm 2 to get the dense submatrix around each of those elements (line 13). The maximum density over the considered dense submatrices is returned.  In this section, we evaluate the performance of our approaches as compared to all baselines discussed in Table 1. Table 3 shows the statistical summary of the four real-world datasets that we use: DARPA [58] and ISCX-IDS2012 [59] are popular datasets for graph anomaly detection used by baselines to evaluate their algorithms; [60] surveys more than 30 datasets and recommends to use the newer CIC-IDS2018 and CIC-DDoS2019 datasets  [61, 62] containing modern attack scenarios. | | corresponds to the total number of edge records, | | and | | are the number of unique nodes and unique timestamps, respectively. Appendix C describes the experimental setup. Hyperparameters for the baselines are provided in Appendix D. All edge (or graph)-based methods output an anomaly score per edge (or graph), a higher score implying more anomalousness. Similar to baseline papers, we report the Area under the ROC curve (AUC) and the running time. Unless explicitly specified, all experiments including those on the baselines are repeated 5 times and the mean is reported. We aim to answer the following questions:

EXPERIMENTS
Q1. Edge Anomalies: How accurately do AnoEdge-G and AnoEdge-L detect edge anomalies compared to baselines? Are they fast and scalable? Q2. Graph Anomalies: How accurately do AnoGraph and AnoGraph-K detect graph anomalies i.e. anomalous graph snapshots? Are they fast and scalable?

Edge Anomalies
Accuracy: Table 4 shows the AUC of edge anomaly detection baselines, AnoEdge-G, and AnoEdge-L. We report a single value for DenseStream and PENminer because these are non-randomized methods. PENminer is unable to finish on the large CIC-DDoS2019 within 24 hours; thus, that result is not reported. SedanSpot uses personalised PageRank to detect anomalies and is not always able to detect anomalous edges occurring in dense block patterns while PENminer is unable to detect structural anomalies. Among the baselines, MIDAS-R is most accurate, however, it performs worse when there is a large number of timestamps as in ISCX-IDS2012. Note that AnoEdge-G and AnoEdge-L outperform all baselines on all datasets.
Running Time: Table 4 shows the running time (excluding I/O) and real-time performance of AnoEdge-G and AnoEdge-L. Since AnoEdge-L maintains a local dense submatrix, it is faster than AnoEdge-G. DenseStream maintains dense blocks incrementally for every coming tuple and updates dense subtensors when it meets an updating condition, limiting the detection speed. SedanSpot requires several subprocesses (hashing, random-walking, reordering, sampling, etc), PENminer and F-FADE need to actively extract patterns for every graph update, resulting in the large computation time. When there is a large number of timestamps like in ISCX-IDS2012, MIDAS-R performs slower than AnoEdge-L which is fastest.
AUC vs Running Time: Figure 3(a) plots accuracy (AUC) vs. running time (log scale, in seconds, excluding I/O) on ISCX-IDS2012 dataset. AnoEdge-G and AnoEdge-L achieve much higher accuracy compared to all baselines, while also running significantly faster. Scalability: Figures 3(b) and 3(c) plot the running time with increasing number of hash functions and edges respectively, on the ISCX-IDS2012 dataset. This demonstrates the scalability of AnoEdge-G and AnoEdge-L.

Graph Anomalies
Accuracy: Table 5 shows the AUC of graph anomaly detection baselines, AnoGraph, and AnoGraph-K. We report a single value for DenseAlert and AnomRank because these are non-randomized methods. AnomRank is not meant for a streaming scenario, therefore the low AUC. DenseAlert can estimate only one subtensor at a time and SpotLight uses a randomized approach without any actual search for dense subgraphs. Note that AnoGraph and Ano-Graph-K outperform all baselines on all datasets while using a simple sketch data structure to incorporate dense subgraph search as opposed to the baselines. We provide results with additional set of parameters in Table 6.
Running Time: Table 5 shows the running time (excluding I/O). DenseAlert has (|ℰ|) worse case time complexity (per incoming edge). AnomRank needs to compute a global PageRank, which does not scale for stream processing. Note that AnoGraph and AnoGraph-K run much faster than all baselines.
AUC vs Running Time: Figure 4 (a) plots accuracy (AUC) vs. running time (log scale, in seconds, excluding I/O) on the CIC-DDoS2019 dataset. AnoGraph and AnoGraph-K achieve much higher accuracy compared to the baselines, while also running significantly faster.
Scalability: Figures 4(b), 4(c), and 4(d) plot the running time with increasing factor (used for top-in Algorithm 5), number of hash functions and number of edges respectively, on the CIC-DDoS2019 dataset. This demonstrates the scalability of AnoGraph and AnoGraph-K.  Table 6 shows the performance of AnoGraph and AnoGraph-K for different time windows and edge thresholds. The edge threshold is varied in such a way that a sufficient number of anomalies are present within the time window. AnoGraph and AnoGraph-K perform similar to that in Table 5. Table 7 shows the robustness of AnoEdge-G and AnoEdge-L as we vary the temporal decay factor .

CONCLUSION
In this paper, we extend the CMS data structure to a higher-order sketch to capture complex relations in graph data and to reduce the problem of detecting suspicious dense subgraphs to finding a dense submatrix in constant time. We then propose four sketchbased streaming methods to detect edge and subgraph anomalies in constant time and memory. Furthermore, our approach is the first streaming work that incorporates dense subgraph search to detect graph anomalies in constant memory and time. We also provide a theoretical guarantee on the submatrix density measure and prove the time and space complexities of all methods. Experimental results on four real-world datasets demonstrate our effectiveness as opposed to popular state-of-the-art streaming edge and graph baselines. Future work could consider incorporating rectangular H-CMS matrices, node and edge representations, and more general types of data, including tensors.
Proof. Procedure Edge-Submatrix-Density removes rows (or columns) iteratively, and the total number of rows and columns that can be removed is + − 2. In each iteration, the approach performs the following three operations: (a) pick the row with minimum row-sum; (b) pick the column with minimum columnsum; (c) calculate density. We keep -sized arrays for flagging removed rows (or columns), and for maintaining row-sums (or column-sums). Operations (a) and (b) take maximum steps to pick and flag the row with minimum row-sum (or column-sum). Updating the column-sums (or rows-sums) based on the picked row (or column) again takes maximum steps. Time complexity of (a) and (b) is therefore ( ). Density is directly calculated based on subtracting the removed row-sum (or column-sum) and reducing the row-count (or column-count) from the earlier density value. Row-count and column-count are kept as separate variables. Therefore, the time complexity of the density calculation step is (1). Total time complexity of procedure Edge-Submatrix-Density is (( + − 2) * ( + + 1)) = ( 2 ). Time complexity to initialize and decay the H-CMS data structure is ( * 2 ). Temporal decay operation is applied whenever the timestamp changes, and not for every received edge. Update counts operation updates a matrix element value ( (1) operation) for matrices, and the time complexity of this step is ( ). Anomaly score for each edge is based on the submatrix density computation procedure which is ( 2 ); the time complexity of matrices becomes ( * 2 ). Therefore, the total time complexity of Algorithm 2 is (|ℰ| * ( + * 2 )) = (|ℰ| * * 2 ).
For procedure Edge-Submatrix-Density, we keep an -sized arrays to flag rows and columns that are part of the current submatrix, and to maintain row-sums and column-sums. Total memory complexity of Edge-Submatrix-Density procedure is (4 * ) = ( ). Memory complexity of H-CMS data structure is ( * 2 ). Dense submatrix search and density computation procedure require ( ) memory. For matrices, this becomes ( * ). Therefore, the total memory complexity of Algorithm 2 is ( * 2 + * ) = ( * 2 ). □
Proof. As shown in Proposition 1, the time complexity of H-CMS is ( * 2 ) and update operation is ( ). Current submatrix ( , ) is updated based on expand and condense submatrix operations. (a) We keep an -sized array to flag the current submatrix rows (or column), and also to maintain row-sums (or column-sums). Expand submatrix operation depends on the elements from row ℎ( ) and column ℎ( ), and the density is calculated by considering these elements, thus requiring maximum steps. Upon addition of the row (or column), the dependent column-sums (or row-sums) are also updated taking maximum steps. Time complexity of expand operation is therefore ( ). (b) Condense submatrix operation removes rows and columns iteratively. A row (or column) elimination is performed by selecting the row (or column) with minimum row-sum (or column-sum) in ( ) time. Removed row (or column) affects the dependent column-sums (or row-sums) and are updated in ( ) time. Time complexity of a row (or column) removal is therefore ( ). Condense submatrix removes rows (or columns) that were once added by the expand submatrix operation which in worse case is |ℰ|.
Proof. Procedure AnoGraph-Density iteratively removes row (or column) with minimum row-sum (or column-sum). Maximum number of rows and columns that can be removed is + − 2. We keep -sized arrays to store the current submatrix rows and columns, and row-sums and column-sums. At each iteration, selecting the row (or column) with minimum row-sum (or columnsum) takes ( ) time, and updating the dependent row-sums (or column-sums) also ( ) time. Density is calculated in ( ) time based on the current submatrix row-sum and column-sum. Each iteration takes ( + + ) = ( ) time. Hence, the total time complexity of AnoGraph-Density procedure is (( + − 2) * ) = ( 2 ).
For procedure AnoGraph-Density, we keep -sized array to flag rows and columns that are part of the current submatrix, and to maintain row-sums and column-sums. Hence, memory complexity of AnoGraph-Density procedure is (4 * ) = ( ).