# Sketch-Based Streaming Anomaly Detection in Dynamic Graphs

Siddharth Bhatia
National University of Singapore
<EMAIL_ADDRESS>
&Mohit Wadhwa
<EMAIL_ADDRESS>
&Philip S. Yu
University of Illinois at Chicago
<EMAIL_ADDRESS>
&Bryan Hooi
National University of Singapore
<EMAIL_ADDRESS>

###### Abstract

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 four 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 four real-world datasets.
Our method is the first streaming approach that incorporates dense subgraph
search to detect graph anomalies in constant memory and time.

##  1 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, [11, 3,
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 higher-order 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. 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. 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. 3.

Effectiveness (Section 7): We outperform all state-of-the-art streaming edge
and graph anomaly detection methods on four real-world datasets.

Reproducibility: Our code and datasets are available at
https://github.com/Stream-AD/AnoGraph.

Table 1: Comparison of relevant anomaly detection approaches.

Property | DenseStream | SedanSpot | MIDAS-R | PENminer | F-FADE | DenseAlert | SpotLight | AnomRank | Our Method
---|---|---|---|---|---|---|---|---|---
| (KDD’17) | (ICDM’20) | (AAAI’20) | (KDD’20) | (WSDM’21) | (KDD’17) | (KDD’18) | (KDD’19) | ($2021$)
Edge Anomaly | ✓ | ✓ | ✓ | ✓ | ✓ | – | – | – | ✔
Graph Anomaly | – | – | – | – | – | ✓ | ✓ | ✓ | ✔
Constant Memory | – | ✓ | ✓ | – | ✓ | – | ✓ | – | ✔
Constant Update Time | – | ✓ | ✓ | ✓ | ✓ | – | ✓ | – | ✔
Dense Subgraph Search | ✓ | – | – | – | – | ✓ | – | – | ✔

##  2 Related Work

Our work is closely related to areas like anomaly detection on graphs [16, 17,
18, 19, 20, 21, 22, 23] and streams [24, 25, 26, 27, 28, 29, 30, 31, 32], and
streaming algorithms [33, 34, 35, 36, 37]. Higher-order sketches are discussed
in [37], however, they are restricted to count-sketches and non-graph
settings. [38, 39] discuss deep learning based anomaly detection, however,
such approaches are unable to detect anomalies in a streaming manner. [4, 7,
8, 5, 10, 6, 9] 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 [40] for an extensive survey.

Edge Stream Methods: HotSpot [41] detects nodes whose egonets suddenly change.
RHSS [42] focuses on sparsely-connected graph parts. CAD [43] 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 [44] approximates the adjacency matrix of the
current snapshot using matrix factorization. Copycatch [45] spots near-
bipartite cores where each node is connected to others in the same core
densely within a short time. SPOT/DSPOT [30] use extreme value theory to
automatically set thresholds for anomalies. IncGM+ [46] 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 [47],
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 and time.

##  3 Problem

Let $\mathscr{E}=\\{e_{1},e_{2},\cdots\\}$ be a stream of weighted edges from
a time-evolving graph $\mathcal{G}$. Each arriving edge is a tuple
$e_{i}=(u_{i},v_{i},w_{i},t_{i})$ consisting of a source node
$u_{i}\in\mathcal{V}$, a destination node $v_{i}\in\mathcal{V}$, a weight
$w_{i}$, and a time of occurrence $t_{i}$, the time at which the edge is added
to the graph. For example, in a network traffic stream, an edge $e_{i}$ could
represent a connection made from a source IP address $u_{i}$ to a destination
IP address $v_{i}$ at time $t_{i}$. We do not assume that the set of vertices
$\mathcal{V}$ is known a priori: for example, new IP addresses or user IDs may
be created over the course of the stream.

We model $\mathcal{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 $\mathcal{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. $t_{i+1}\geq t_{i}$, since in many
applications $t_{i}$ 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.

  * •

Constant Memory and Update Time: To ensure scalability, memory usage and
update time should not grow with the number of nodes or the length of the
stream. Thus, for a newly arriving edge, our algorithm should run in constant
memory and update time.

##  4 Higher-Order Sketch & Notations

Count-min sketches (CMS) [15] are popular streaming data structures used by
several online algorithms [48]. 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).

Figure 1: (a) Original CMS (b) Higher-order CMS

######  Theorem 1.

(Proof in Appendix C) H-CMS has the same estimate guarantees as the original
CMS.

We use a 3-dimensional H-CMS (operations described in Appendix A) where the
number of hash functions is denoted by $n_{r}$, and matrix $\mathcal{M}$
corresponding to each hash function is of dimension $n_{b}\times n_{b}$, i.e.,
a square matrix. A hash function denoted by $h(u)$ maps an entity $u$ to an
integer in the range $[0,n_{b})$. A 3-dimensional H-CMS maps edge $(u,v)$ to a
matrix index $(h(u),h(v))$, i.e. the source node is mapped to a row index and
the destination node is mapped to a column index. Therefore, each matrix in a
3-dimensional 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 the size of the matrix is a small
constant, independent of the number of edges or the graph size.

Figure 2: (a) Dense subgraph in the original graph between source nodes
$s_{1},s_{2}$, and destination nodes $d_{1},d_{2},d_{3}$ is transformed to a
(b) Dense submatrix between rows $r_{1},r_{2}$, and columns
$c_{1},c_{2},c_{3}$ in the H-CMS.

Frequently used symbols are discussed in Table 2, and we leverage the subgraph
density measure discussed in [49] to define the submatrix $(S_{x},T_{x})$
density.

Table 2: Table of symbols. Symbol |  Definition
---|---
$n_{r}$ |  number of hash functions
$n_{b}$ |  number of buckets
$h(u)$ |  hash function $u\rightarrow[0,n_{b})$
$\mathcal{M}$ |  a square matrix of dimensions $n_{b}\times n_{b}$
$\mathcal{M}[i][j]$ |  element at row index i and column index j
$S$ |  set of all row indices
$S_{cur}$ |  set of current submatrix row indices
$S_{rem}$ |  set of remaining row indices i.e. indices not part of current submatrix
$T$ |  set of all column indices
$T_{cur}$ |  set of current submatrix column indices
$T_{rem}$ |  set of remaining column indices i.e. indices not part of current submatrix
$[z]$ |  set of all integers in the range $[1,z]$, i.e., $\\{1,2,...,z\\}$
$\mathcal{D}(\mathcal{M},S_{x},T_{x})$ |  density of submatrix ($S_{x}$, $T_{x}$)
$\mathcal{E}(\mathcal{M},S_{x},T_{x})$ |  sum of elements of submatrix ($S_{x}$, $T_{x}$)
$\mathcal{R}(\mathcal{M},u,T_{x})$ |  submatrix row-sum i.e. sum of elements of submatrix ($\\{u\\}$, $T_{x}$)
$\mathcal{C}(\mathcal{M},S_{x},v)$ |  submatrix column-sum i.e. sum of elements of submatrix ($S_{x}$, $\\{v\\}$)
$\mathcal{L}(\mathcal{M},u,v,S_{x},T_{x})$ |  likelihood of index $(u,v)$ w.r.t. submatrix $(S_{x},T_{x})$
$d_{max}$ |  maximum reported submatrix density

######  Definition 1.

Given matrix $\mathcal{M}$, density of a submatrix of $\mathcal{M}$
represented by $S_{x}\subseteq S$ and $T_{x}\subseteq T$, is:

$\mathcal{D}(\mathcal{M},S_{x},T_{x})=\frac{\sum_{s\in S_{x}}\sum_{t\in
T_{x}}\mathcal{M}[s][t]}{\sqrt{|S_{x}||T_{x}|}}$ (1)

##  5 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.

###  5.1 AnoEdge-G

AnoEdge-G, as described in Algorithm 1, 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 $\alpha$ (lines 2,4). This decay simulates the gradual
‘forgetting’ of older and hence more outdated information. When an edge
$(u,v)$ arrives, $u$, $v$ are mapped to matrix indices $h(u)$, $h(v)$
respectively for each hash function $h$, 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 $(h(u),h(v))$.
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 $(u,v)$. A $1\times 1$ submatrix represented by $S_{cur}$
and $T_{cur}$, is initialized with row-index $u$ and column index $v$ (line
9). The submatrix is iteratively expanded by greedily selecting a row $u_{p}$
from $S_{rem}$ (or a column $v_{p}$ from $T_{rem}$) that obtains the maximum
row (or column) sum with the current submatrix (lines 14,16). This selected
row $u_{p}$ (or column $v_{p}$) is removed from $S_{rem}$ (or $T_{rem}$), and
added to $S_{cur}$ (or $T_{cur}$) (lines 15,17). The process is repeated until
both $S_{rem}$ and $T_{rem}$ are empty (line 11). 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 (line
18).

1

Input: Stream $\mathscr{E}$ of edges over time

Output: Anomaly score per edge

2

1 Procedure  _AnoEdge-G(_$\mathscr{E}$_)_

Initialize H-CMS matrix $\mathcal{M}$ for edge count

// H-CMS data structure

2 while  _new edge $e=(u,v,w,t)\in\mathscr{E}$ is received_ do

Temporal decay H-CMS with timestamp change

// decay count

Update H-CMS matrix $\mathcal{M}$ for new edge $(u,v)$ with value $w$

// update count

3 output $score(e)\leftarrow$ Edge-Submatrix-Density($\mathcal{M},h(u),h(v)$)

4

5

6 Procedure  _Edge-Submatrix-Density(_$\mathcal{M}$ , $u$, $v$_)_

7 $S\leftarrow[n_{b}];\enspace T\leftarrow[n_{b}];\enspace
S_{cur}\leftarrow\\{u\\};\enspace T_{cur}\leftarrow\\{v\\};\enspace
S_{rem}\leftarrow S/\\{u\\};\enspace T_{rem}\leftarrow T/\\{v\\}$

8 $d_{max}\leftarrow\mathcal{D}(\mathcal{M},S_{cur},T_{cur})$

9 while  _$S_{rem}\neq\emptyset\enspace\vee\enspace T_{rem}\neq\emptyset$_ do

$u_{p}\leftarrow\operatorname*{argmax}_{s_{p}\in
S_{rem}}\mathcal{R}(\mathcal{M},s_{p},T_{cur})$

// submatrix max row-sum index

$v_{p}\leftarrow\operatorname*{argmax}_{t_{p}\in
T_{rem}}\mathcal{C}(\mathcal{M},S_{cur},t_{p})$

// submatrix max column-sum index

10 if  _$\mathcal{R}(\mathcal{M},u_{p},T_{cur})
>\mathcal{C}(\mathcal{M},S_{cur},v_{p})$_ then

11 $S_{cur}\leftarrow S_{cur}\cup\\{u_{p}\\};\enspace S_{rem}\leftarrow
S_{rem}/\\{u_{p}\\}$

12

13 else

14 $T_{cur}\leftarrow T_{cur}\cup\\{v_{p}\\};\enspace T_{rem}\leftarrow
T_{rem}/\\{v_{p}\\}$

15

16 $d_{max}\leftarrow max(d_{max},\mathcal{D}(\mathcal{M},S_{cur},T_{cur}))$

17

return $d_{max}$

// dense submatrix density

18

19

Algorithm 1 AnoEdge-G : Streaming Anomaly Edge Scoring

######  Proposition 1.

(Proof in Appendix D.1) Time complexity of Algorithm 1 is
$O(|\mathscr{E}|*n_{r}*n_{b}^{2})$ 111This is for processing all edges; the
time per edge is constant..

######  Proposition 2.

(Proof in Appendix D.1) Memory complexity of Algorithm 1 is
$O(n_{r}*n_{b}^{2})$.

###  5.2 AnoEdge-L

Inspired by Definition 1, we define the likelihood measure of a matrix index
$(u,v)$ with respect to a submatrix $(S_{x},T_{x})$, as the sum of the
elements of submatrix $(S_{x},T_{x})$ that either share row with index $v$ or
column with index $u$ divided by the total number of such elements.

######  Definition 2.

Given matrix $\mathcal{M}$, likelihood of an index $(u,v)$ with respect to a
submatrix represented by $S_{x}\subseteq S$ and $T_{x}\subseteq T$, is:

$\mathcal{L}(\mathcal{M},u,v,S_{x},T_{x})=\frac{\sum_{(s,t)\;\in\;\;S_{x}\times{v}\;\cup\;{u}\times{T_{x}}}\mathcal{M}[s][t]}{|S_{x}\times{v}\;\cup\;{u}\times{T_{x}}|}$
(2)

AnoEdge-L, as described in Algorithm 2, maintains a temporally decaying H-CMS
to store the edge counts. We also initialize a mutable submatrix of size
$1\times 1$ with a random element, and represent it as $(S_{cur},T_{cur})$. As
we process edges, we greedily update $(S_{cur},T_{cur})$ 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 $h(u)$ (or column-index $h(v)$) is added to the
current submatrix, $(S_{cur},T_{cur})$. 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 $(S_{cur},T_{cur})$ (line 10). A
higher likelihood measure implies that the edge is more likely to be
anomalous.

1

Input: Stream $\mathscr{E}$ of edges over time

Output: Anomaly score per edge

1 Procedure  _AnoEdge-L(_$\mathscr{E}$_)_

Initialize H-CMS matrix $\mathcal{M}$ for edges count

// H-CMS data structure

Initialize a randomly picked $1\times 1$ submatrix $(S_{cur},T_{cur})$

// mutable submatrix

2 while  _new edge $e=(u,v,w,t)\in\mathscr{E}$ is received_ do

Temporal decay H-CMS with timestamp change

// decay count

Update H-CMS matrix $\mathcal{M}$ for new edge $(u,v)$ with value $w$

// update Count

3 $\triangleright$ Check and Update Submatrix:

Expand $(S_{cur},T_{cur})$

// expand submatrix

Condense $(S_{cur},T_{cur})$

// condense submatrix

output $score(e)\leftarrow\mathcal{L}(\mathcal{M},h(u),h(v),S_{cur},T_{cur})$

// from Definition 2

4

5

6

Algorithm 2 AnoEdge-L : Streaming Anomaly Edge Scoring

######  Proposition 3.

(Proof in Appendix D.2) Time complexity of Algorithm 2 is
$O(n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}*n_{b})$.

######  Proposition 4.

(Proof in Appendix D.2) Memory complexity of Algorithm 2 is
$O(n_{r}*n_{b}^{2})$.

##  6 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 1 to greedily find a dense submatrix around $K$ strategically picked
matrix elements performing equally well in practice.

###  6.1 AnoGraph

AnoGraph, as described in Algorithm 3, 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. AnoGraph-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
$\mathcal{M}$. The current dense submatrix is initialised as matrix
$\mathcal{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 $S_{cur}$ and $T_{cur}$ are empty (line 12). The density of the current
submatrix is computed at each iteration of the submatrix expansion process and
the maximum over all densities is returned (line 19).

Algorithm 3 is a special case of finding the densest subgraph in a directed
graph problem [49] 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.

######  Theorem 2.

(Proof in Appendix E.1) Algorithm 3 achieves a 2-approximation guarantee for
the densest submatrix problem.

1

Input: Stream $\mathscr{G}$ of edges over time

Output: Anomaly score per graph

2

1 Procedure  _AnoGraph(_$\mathscr{G}$_)_

Initialize H-CMS matrix $\mathcal{M}$ for graph edges count

// H-CMS data structure

2 while  _new graph $G\in\mathscr{G}$ is received_ do

Reset H-CMS matrix $\mathcal{M}$ for graph $G$

// reset count

3 for  _edge $e=(u,v,w,t)\in G$_ do

Update H-CMS matrix $\mathcal{M}$ for edge $(u,v)$ with value $w$

// update count

4

output $score(G)\leftarrow$ AnoGraph-Density($\mathcal{M}$)

// anomaly score

5

6

7

8Procedure  _AnoGraph-Density(_$\mathcal{M}$_)_

$S_{cur}\leftarrow[n];\enspace T_{cur}\leftarrow[n]$

// initialize to size of $\mathcal{M}$

9 $d_{max}\leftarrow\mathcal{D}(\mathcal{M},S_{cur},T_{cur})$

10 while  _$S_{cur}\neq\emptyset\enspace\vee\enspace T_{cur}\neq\emptyset$_ do

$u_{p}\leftarrow\operatorname*{argmin}_{s_{p}\in
S_{cur}}\mathcal{R}(\mathcal{M},s_{p},T_{cur})$

// submatrix min row-sum index

$v_{p}\leftarrow\operatorname*{argmin}_{t_{p}\in
T_{cur}}\mathcal{C}(\mathcal{M},S_{cur},t_{p})$

// submatrix min column-sum index

11 if  _$\mathcal{R}(\mathcal{M},u_{p},T_{cur})
<\mathcal{C}(\mathcal{M},S_{cur},v_{p})$_ then

$S_{cur}\leftarrow S_{cur}/\\{u_{p}\\}$

// remove row

12

13 else

$T_{cur}\leftarrow T_{cur}/\\{v_{p}\\}$

// remove column

14

15 $d_{max}\leftarrow max(d_{max},\mathcal{D}(\mathcal{M},S_{cur},T_{cur}))$

16

return $d_{max}$

// dense submatrix density

17

Algorithm 3 AnoGraph: Streaming Anomaly Graph Scoring

######  Proposition 5.

(Proof in Appendix E.1) Time complexity of Algorithm 3 is
$O(|\mathscr{G}|*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$.

######  Proposition 6.

(Proof in Appendix E.1) Memory complexity of Algorithm 3 is
$O(n_{r}*n_{b}^{2})$.

###  6.2 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 4.

AnoGraph-K-Density computes the density of a dense submatrix of matrix
$\mathcal{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 $K$ largest elements of the matrix $\mathcal{M}$ and
calls Edge-Submatrix-Density from Algorithm 1 to get the dense submatrix
around each of those elements (line 14). The maximum density over the
considered $K$ dense submatrices is returned.

1

Input: Stream $\mathscr{G}$ of edges over time

Output: Anomaly score per graph

2

1 Procedure  _AnoGraph-K(_$\mathscr{G},K$_)_

Initialize H-CMS matrix $\mathcal{M}$ for graph edges count

// H-CMS data structure

2 while  _new graph $G\in\mathscr{G}$ is received_ do

Reset H-CMS matrix $\mathcal{M}$ for graph $G$

// reset count

3 for  _edge $e=(u,v,w,t)\in G$_ do

Update H-CMS matrix $\mathcal{M}$ for edge $(u,v)$ with value $w$

// update count

4

output $score(G)\leftarrow$ AnoGraph-K-Density($\mathcal{M},K$)

// anomaly score

5

6

7

8Procedure  _AnoGraph -K-Density(_$\mathcal{M}$ , $K$_)_

$B\leftarrow[n]\times[n]$

// set of all indices

9 $d_{max}\leftarrow 0$

10 for  _$j\leftarrow 1$ … $K$_ do

$u_{p},v_{p}\leftarrow\operatorname*{argmax}_{(s_{p},t_{p})\in
B}\mathcal{M}[s_{p}][t_{p}]$

// pick the max element

11 $d_{max}\leftarrow max(d_{max},\textsc{Edge-Submatrix-
Density}({\mathcal{M},u_{p},v_{p}}))$

$B\leftarrow B/\\{(u_{p},v_{p})\\}$

// remove max element index

12

return $d_{max}$

// dense submatrix density

13

Algorithm 4 AnoGraph-K: Streaming Anomaly Graph Scoring

######  Proposition 7.

(Proof in Appendix E.2) Time complexity of Algorithm 4 is
$O(|\mathscr{G}|*K*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$.

######  Proposition 8.

(Proof in Appendix E.2) Memory complexity of Algorithm 4 is
$O(n_{r}*n_{b}^{2})$.

##  7 Experiments

In this section, we evaluate the performance of our approaches as compared to
all baselines discussed in Table 1. We use four real-world datasets: _DARPA_
[50] and _ISCX-IDS2012_ [51] are popular datasets for graph anomaly detection;
[52] surveys more than $30$ datasets and recommends to use the newer _CIC-
IDS2018_ and _CIC-DDoS2019_ datasets [53, 54]. Dataset details are discussed
in Appendix B. Hyperparameters for the baselines are provided in Appendix H.
Appendix F describes the experimental setup and results with some additional
parameters are shown in Appendix G. 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:

  1. Q1.

Edge Anomalies: How accurately do AnoEdge-G and AnoEdge-L detect edge
anomalies compared to baselines? Are they fast and scalable?

  2. Q2.

Graph Anomalies: How accurately do AnoGraph and AnoGraph-K detect graph
anomalies i.e. anomalous graph snapshots? Are they fast and scalable?

###  7.1 Edge Anomalies

#### Accuracy:

Table 3 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.

Table 3: AUC and Running Time when detecting edge anomalies. Averaged over $5$
runs.

Dataset | DenseStream | SedanSpot | MIDAS-R | PENminer | F-FADE | AnoEdge-G | AnoEdge-L
---|---|---|---|---|---|---|---
DARPA | $0.532$ | $0.647\pm 0.006$ | $0.953\pm 0.002$ | 0.872 | $0.919\pm 0.005$ | $\bf 0.970\pm 0.001$ | $0.964\pm 0.001$
57.7s | 129.1s | 1.4s | 5.21 hrs | 317.8s | 28.7s | 6.1s
ISCX-IDS2012 | $0.551$ | $0.581\pm 0.001$ | $0.820\pm 0.050$ | 0.530 | $0.533\pm 0.020$ | $0.954\pm 0.000$ | $\bf 0.957\pm 0.003$
138.6s | 19.5s | 5.3s | 1.3 hrs | 137.4s | 7.8s | 0.7s
CIC-IDS2018 | $0.756$ | $0.325\pm 0.037$ | $0.919\pm 0.019$ | 0.821 | $0.607\pm 0.001$ | $\bf 0.963\pm 0.014$ | $0.927\pm 0.035$
3.3 hours | 209.6s | 1.1s | 10 hrs | 279.7s | 58.4s | 10.2s
CIC-DDoS2019 | $0.263$ | $0.567\pm 0.004$ | $0.983\pm 0.003$ | — | $0.717\pm 0.041$ | $0.997\pm 0.001$ | $\bf 0.998\pm 0.001$
265.6s | 697.6s | 2.2s | > 24 hrs | 18.7s | 123.3s | 17.8s

#### Running Time:

Table 3 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 the
fastest.

#### AUC vs Running Time:

Figure 3(a) plots accuracy (AUC) vs. running time (log scale, in seconds,
excluding I/O) on the _ISCX-IDS2012_ dataset. AnoEdge-G and AnoEdge-L achieve
much higher accuracy compared to all baselines, while also running
significantly fast.

Figure 3: On _ISCX-IDS2012_ , (a) AUC vs running time when detecting edge
anomalies. (b) Linear scalability with number of hash functions. (c) Linear
scalability with number of edges.

#### 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.

###  7.2 Graph Anomalies

#### Accuracy:

Table 4 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 AnoGraph-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, Appendix G.

Table 4: AUC and Running Time when detecting graph anomalies. Averaged over
$5$ runs.

Dataset | DenseAlert | SpotLight | AnomRank | AnoGraph | AnoGraph-K
---|---|---|---|---|---
DARPA | $0.833$ | $0.728\pm 0.016$ | $0.754$ | $0.835\pm 0.002$ | $\bf 0.839\pm 0.002$
49.3s | 88.5s | 3.7s | 0.3s | 0.3s
ISCX-IDS2012 | $0.906$ | $0.872\pm 0.019$ | $0.194$ | $\bf 0.950\pm 0.001$ | $\bf 0.950\pm 0.001$
6.4s | 21.1s | 5.2s | 0.5s | 0.5s
CIC-IDS2018 | $0.950$ | $0.835\pm 0.022$ | $0.783$ | $\bf 0.957\pm 0.000$ | $\bf 0.957\pm 0.000$
67.9s | 149.0s | 7.0s | 0.2s | 0.3s
CIC-DDoS2019 | $0.764$ | $0.468\pm 0.048$ | $0.241$ | $0.946\pm 0.002$ | $\bf 0.948\pm 0.002$
1065.0s | 289.7s | 0.2s | 0.4s | 0.4s

#### Running Time:

Table 4 shows the running time (excluding I/O). DenseAlert has
$O(|\mathscr{E}|)$ 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.

Figure 4: On _CIC-DDoS2019_ , (a) AUC vs running time when detecting graph
anomalies. (b) AnoGraph-K scales linearly with factor $K$. (c) Linear
scalability with number of hash functions. (d) Linear scalability with number
of edges.

#### Scalability:

Figures 4(b), 4(c), and 4(d) plot the running time with increasing factor $K$
(used for top-$K$ in Algorithm 4), number of hash functions and number of
edges respectively, on the _CIC-DDoS2019_ dataset. This demonstrates the
scalability of AnoGraph and AnoGraph-K.

##  8 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 sketch-based 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 node and edge
representations, and more general types of data, including tensors.

## References

  * Shin et al. [2017] Kijung Shin, Bryan Hooi, Jisu Kim, and Christos Faloutsos.  Densealert: Incremental dense-subtensor detection in tensor streams.  _KDD_ , 2017.
  * Eswaran et al. [2018] Dhivya Eswaran, Christos Faloutsos, Sudipto Guha, and Nina Mishra.  Spotlight: Detecting anomalies in streaming graphs.  In _KDD_ , 2018.
  * Bhatia et al. [2020] Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, and Christos Faloutsos.  Midas: Microcluster-based detector of anomalies in edge streams.  In _AAAI_ , 2020.
  * Akoglu et al. [2010] Leman Akoglu, Mary McGlohon, and Christos Faloutsos.  Oddball: Spotting anomalies in weighted graphs.  In _PAKDD_ , 2010.
  * Chakrabarti [2004] Deepayan Chakrabarti.  Autopart: Parameter-free graph partitioning and outlier detection.  In _PKDD_ , 2004.
  * Hooi et al. [2017] Bryan Hooi, Kijung Shin, Hyun Ah Song, Alex Beutel, Neil Shah, and Christos Faloutsos.  Graph-based fraud detection in the face of camouflage.  _TKDD_ , 2017.
  * Jiang et al. [2016] Meng Jiang, Peng Cui, Alex Beutel, Christos Faloutsos, and Shiqiang Yang.  Catching synchronized behaviors in large networks: A graph mining approach.  _TKDD_ , 2016.
  * Kleinberg [1999] Jon M Kleinberg.  Authoritative sources in a hyperlinked environment.  _JACM_ , 1999.
  * Shin et al. [2018] Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos.  Patterns and anomalies in k-cores of real-world graphs with applications.  _KAIS_ , 2018.
  * Tong and Lin [2011] Hanghang Tong and Ching-Yung Lin.  Non-negative residual matrix factorization with application to graph anomaly detection.  In _SDM_ , 2011.
  * Eswaran and Faloutsos [2018] Dhivya Eswaran and Christos Faloutsos.  Sedanspot: Detecting anomalies in edge streams.  In _ICDM_ , 2018.
  * Belth et al. [2020] C Belth, X Zheng, and D Koutra.  Mining persistent activity in continually evolving networks.  In _KDD_ , 2020.
  * Chang et al. [2021] Yen-Yu Chang, Pan Li, Rok Sosic, MH Afifi, Marco Schweighauser, and Jure Leskovec.  F-fade: Frequency factorization for anomaly detection in edge streams.  In _WSDM_ , 2021.
  * Yoon et al. [2019] Minji Yoon, Bryan Hooi, Kijung Shin, and Christos Faloutsos.  Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach.  In _KDD_ , 2019.
  * Cormode and Muthukrishnan [2005] Graham Cormode and Shan Muthukrishnan.  An improved data stream summary: the count-min sketch and its applications.  _Journal of Algorithms_ , 2005.
  * Zhang et al. [2019] Jiabao Zhang, Shenghua Liu, Wenjian Yu, Wenjie Feng, and Xueqi Cheng.  Eigenpulse: Detecting surges in large streaming graphs with row augmentation.  In _PAKDD_ , 2019.
  * Bogdanov et al. [2013] Petko Bogdanov, Christos Faloutsos, Misael Mongiovì, Evangelos E Papalexakis, Razvan Ranca, and Ambuj K Singh.  Netspot: Spotting significant anomalous regions on dynamic networks.  In _SDM_ , 2013.
  * Shah et al. [2016] Neil Shah, Alex Beutel, Bryan Hooi, Leman Akoglu, Stephan Gunnemann, Disha Makhija, Mohit Kumar, and Christos Faloutsos.  Edgecentric: Anomaly detection in edge-attributed networks.  In _ICDMW_ , 2016.
  * Perozzi and Akoglu [2018] Bryan Perozzi and Leman Akoglu.  Discovering communities and anomalies in attributed graphs: Interactive visual exploration and summarization.  _TKDD_ , 2018.
  * Bonchi et al. [2019] Francesco Bonchi, Ilaria Bordino, Francesco Gullo, and Giovanni Stilo.  The importance of unexpectedness: Discovering buzzing stories in anomalous temporal graphs.  _Web Intelligence_ , 2019.
  * Bonchi et al. [2016] Francesco Bonchi, Ilaria Bordino, Francesco Gullo, and Giovanni Stilo.  Identifying buzzing stories via anomalous temporal subgraph discovery.  In _WI_ , 2016.
  * Bojchevski and Günnemann [2018] Aleksandar Bojchevski and Stephan Günnemann.  Bayesian robust attributed graph clustering: Joint learning of partial anomalies and group structure.  In _AAAI_ , 2018.
  * Yu et al. [2018] Wenchao Yu, Wei Cheng, C Aggarwal, K Zhang, H Chen, and Wei Wang.  Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks.  _KDD_ , 2018.
  * Na et al. [2018] Gyoung S Na, Donghyun Kim, and Hwanjo Yu.  Dilof: Effective and memory efficient local outlier detection in data streams.  In _KDD_ , 2018.
  * Manzoor et al. [2018] Emaad A Manzoor, Hemank Lamba, and Leman Akoglu.  xstream: Outlier detection in feature-evolving data streams.  In _KDD_ , 2018.
  * Tan et al. [2011] Swee Chuan Tan, Kai Ming Ting, and Tony Fei Liu.  Fast anomaly detection for streaming data.  In _IJCAI_ , 2011.
  * Jankov et al. [2017] Dimitrije Jankov, Sourav Sikdar, Rohan Mukherjee, Kia Teymourian, and Chris Jermaine.  Real-time high performance anomaly detection over data streams: Grand challenge.  _DEBS_ , 2017.
  * Zou et al. [2017] Shaofeng Zou, Yingbin Liang, H Vincent Poor, and Xinghua Shi.  Nonparametric detection of anomalous data streams.  _IEEE Transactions on Signal Processing_ , 2017.
  * Moshtaghi et al. [2015] Masud Moshtaghi, James C Bezdek, Christopher Leckie, Shanika Karunasekera, and Marimuthu Palaniswami.  Evolving fuzzy rules for anomaly detection in data streams.  _IEEE Transactions on Fuzzy Systems_ , 2015.
  * Siffer et al. [2017] Alban Siffer, Pierre-Alain Fouque, Alexandre Termier, Christine Largouet, and C Largouët.  Anomaly detection in streams with extreme value theory.  _KDD_ , 2017.
  * Togbe et al. [2020] Maurras Ulbricht Togbe, Mariam Barry, Aliou Boly, Yousra Chabchoub, Raja Chiky, Jacob Montiel, and Vinh-Thuy Tran.  Anomaly detection for data streams based on isolation forest using scikit-multiflow.  In _ICCSA_ , 2020.
  * Zhang et al. [2021] Jiabao Zhang, Shenghua Liu, Wenting Hou, Siddharth Bhatia, Hua-Wei Shen, Wenjian Yu, and Xueqi Cheng.  Augsplicing: Synchronized behavior detection in streaming tensors.  _AAAI_ , 2021.
  * Pan et al. [2013] Shirui Pan, Xingquan Zhu, Chengqi Zhang, and S Yu Philip.  Graph stream classification using labeled and unlabeled graphs.  In _ICDE_ , 2013.
  * Wang et al. [2008] Wei Wang, Xiaohong Guan, and Xiangliang Zhang.  Processing of massive audit data streams for real-time anomaly intrusion detection.  _Computer communications_ , 2008.
  * Menon et al. [2007] Aditya Krishna Menon, Gia Vinh Anh Pham, Sanjay Chawla, and Anastasios Viglas.  An incremental data-stream sketch using sparse random projections.  In _SDM_ , 2007.
  * Zhao et al. [2011] Peixiang Zhao, Charu C Aggarwal, and Min Wang.  gsketch: On query estimation in graph streams.  _VLDB_ , 2011.
  * Shi and Anandkumar [2020] Yang Shi and Animashree Anandkumar.  Higher-order count sketch: Dimensionality reduction that retains efficient tensor operations.  _DCC_ , 2020.
  * Chalapathy and Chawla [2019] Raghavendra Chalapathy and Sanjay Chawla.  Deep learning for anomaly detection: A survey.  _ArXiv_ , abs/1901.03407, 2019.
  * Pang et al. [2020] Guansong Pang, Chunhua Shen, Longbing Cao, and Anton van den Hengel.  Deep learning for anomaly detection: A review.  _arXiv preprint arXiv:2007.02500_ , 2020.
  * Akoglu et al. [2015] Leman Akoglu, Hanghang Tong, and Danai Koutra.  Graph based anomaly detection and description: A survey.  _Data mining and knowledge discovery_ , 2015.
  * Yu et al. [2013] Weiren Yu, Charu C Aggarwal, Shuai Ma, and Haixun Wang.  On anomalous hotspot discovery in graph streams.  In _ICDM_ , 2013.
  * Ranshous et al. [2016] Stephen Ranshous, Steve Harenberg, Kshitij Sharma, and Nagiza F Samatova.  A scalable approach for outlier detection in edge streams using sketch-based approximations.  In _SDM_ , 2016.
  * Sricharan and Das [2014] Kumar Sricharan and Kamalika Das.  Localizing anomalous changes in time-evolving graphs.  In _SIGMOD_ , 2014.
  * Sun et al. [2006] Jimeng Sun, Dacheng Tao, and Christos Faloutsos.  Beyond streams and graphs: dynamic tensor analysis.  In _KDD_ , 2006.
  * Beutel et al. [2013] Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos.  Copycatch: stopping group attacks by spotting lockstep behavior in social networks.  In _WWW_ , 2013.
  * Abdelhamid et al. [2017] Ehab Abdelhamid, Mustafa Canim, M. Sadoghi, B. Bhattacharjee, Yuan-Chi Chang, and Panos Kalnis.  Incremental frequent subgraph mining on large evolving graphs.  _TKDE_ , 2017.
  * Page et al. [1999] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd.  The pagerank citation ranking : Bringing order to the web.  In _WWW_ , 1999.
  * Mcgregor [2014] Andrew Mcgregor.  Graph stream algorithms: a survey.  _SIGMOD Record_ , 2014.
  * Khuller and Saha [2009] Samir Khuller and Barna Saha.  On finding dense subgraphs.  In _ICALP_ , 2009.
  * Lippmann et al. [1999] Richard Lippmann, Robert K Cunningham, David J Fried, Isaac Graf, Kris R Kendall, Seth E Webster, and Marc A Zissman.  Results of the darpa 1998 offline intrusion detection evaluation.  In _Recent advances in intrusion detection_ , 1999.
  * Shiravi et al. [2012] Ali Shiravi, Hadi Shiravi, Mahbod Tavallaee, and Ali A Ghorbani.  Toward developing a systematic approach to generate benchmark datasets for intrusion detection.  _computers & security_, 2012.
  * Ring et al. [2019] Markus Ring, Sarah Wunderlich, Deniz Scheuring, Dieter Landes, and Andreas Hotho.  A survey of network-based intrusion detection data sets.  _Computers & Security_, 2019.
  * Sharafaldin et al. [2018] Iman Sharafaldin, Arash Habibi Lashkari, and Ali A Ghorbani.  Toward generating a new intrusion detection dataset and intrusion traffic characterization.  In _ICISSP_ , 2018.
  * Sharafaldin et al. [2019] Iman Sharafaldin, Arash Habibi Lashkari, Saqib Hakak, and Ali A Ghorbani.  Developing realistic distributed denial of service (ddos) attack dataset and taxonomy.  In _ICCST_ , 2019.
  * Forest [2021] Random Cut Forest.  https://github.com/aws/random-cut-forest-by-aws, 2021.
  * Carter and Wegman [1979] J Lawrence Carter and Mark N Wegman.  Universal classes of hash functions.  _Journal of computer and system sciences_ , 1979.

## Appendix

##  Appendix A H-CMS

Algorithm 5 shows the H-CMS operations.

1

1 Procedure  _INITIALIZE H-CMS(_$n_{r}$ , $n_{b}$_)_

2 for  _$r\leftarrow 1$ … $n_{r}$_ do

$h_{r}:\mathcal{V}\rightarrow[0,n_{b})$

// hash vertex

3 $M_{r}\rightarrow[0]_{n_{b}\times n_{b}}$

4

1 Procedure  _RESET H-CMS(_$n_{r}$ , $n_{b}$_)_

2 for  _$r\leftarrow 1$ … $n_{r}$_ do

$\mathcal{M}_{r}\leftarrow[0]_{n_{b}\times n_{b}}$

// reset to zero matrix

3

4

1 Procedure  _UPDATE H-CMS(_$u,v,w$_)_

2 for  _$r\leftarrow 1$ … $n_{r}$_ do

3
$\mathcal{M}_{r}[h_{r}(u)][h_{r}(v)]\leftarrow\mathcal{M}_{r}[h_{r}(u)][h_{r}(v)]+w$

4

1 Procedure  _DECAY H-CMS(_$\delta$_)_

2 for  _$r\leftarrow 1$ … $n_{r}$_ do

$\mathcal{M}_{r}\leftarrow\delta*\mathcal{M}_{r}$

// decay factor: $\delta$

3

4

5

Algorithm 5 H-CMS Operations

##  Appendix B Datasets

Table 5 shows the statistical summary of the datasets. $|E|$ corresponds to
the total number of edge records, $|V|$ and $|T|$ are the number of unique
nodes and unique timestamps, respectively.

Table 5: Statistics of the datasets. Dataset | $|V|$ | $|E|$ | $|T|$ | Edge Anomalies | Graph Anomalies
---|---|---|---|---|---
DARPA | 25,525 | 4,554,344 | 46,567 | $60.1\%$ | $26.5\%$
ISCX-IDS2012 | 30,917 | 1,097,070 | 165,043 | $4.23\%$ | $3.38\%$
CIC-IDS2018 | 33,176 | 7,948,748 | 38,478 | $7.26\%$ | $11.0\%$
CIC-DDoS2019 | 1,290 | 20,364,525 | 12,224 | $99.7\%$ | $51.4\%$

_DARPA_ [50] and _ISCX-IDS2012_ [51] are popular anomaly detection datasets
used by baseline papers to evaluate their algorithms. [52] surveys more than
$30$ datasets and recommends to use the newer _CIC-IDS2018_ [53] and _CIC-
DDoS2019_ [54] containing modern attack scenarios.

##  Appendix C Higher-Order Sketch Proof

######  Theorem 1.

H-CMS has the same estimate guarantees as the original CMS.

###### Proof.

Consider a 3-dimensional H-CMS, with depth $n_{r}$, where an entity
$a\in[1,N]$ is mapped to index $(i,j)$ with two independent hash functions
$h^{\prime}:[1,N]\rightarrow[0,b)$ and
$h^{\prime\prime}:[1,N]\rightarrow[0,b)$, i.e., $i=h^{\prime}(a)$ and
$j=h^{\prime\prime}(a)$. Without loss of generality, the 3-dimensional H-CMS
can be converted to a CMS data structure by combining $h^{\prime}$ and
$h^{\prime\prime}$ in the following way:
$h(a)=n_{b}*h^{\prime}(a)+h^{\prime\prime}(a)$, i.e., $h(a)=n_{b}*i+j$ where
$b*i\in[0,n_{b}^{2}-n_{b})$ and $j\in[0,n_{b}]$. Hence, $h(a)\in[0,b^{2})$,
and $h:[1,N]\rightarrow[0,b^{2})$ can be a hash function for a CMS data
structure with width $n_{b}^{2}$ and depth $n_{r}$. Therefore, the CMS
estimate guarantee holds for a 3-dimensional H-CMS data structure. A higher
dimensional H-CMS can be reduced to a CMS data structure in a similar manner.
∎

##  Appendix D Edge Anomalies Proofs

###  D.1 Proofs: AnoEdge-G

######  Proposition 1.

Time complexity of Algorithm 1 is $O(|\mathscr{E}|*n_{r}*n_{b}^{2})$.

###### Proof.

Procedure Edge-Submatrix-Density removes rows (or columns) iteratively, and
the total number of rows and columns that can be removed is $n_{b}+n_{b}-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 column-
sum; (c) calculate density. We keep $n_{b}$-sized arrays for flagging removed
rows (or columns), and for maintaining row-sums (or column-sums). Operations
(a) and (b) take maximum $n_{b}$ 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 $n_{b}$ steps. Time complexity of
(a) and (b) is therefore $O(n_{b})$. 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 $O(1)$. Total time complexity of procedure Edge-Submatrix-
Density is $O((n_{b}+n_{b}-2)*(n_{b}+n_{b}+1))=O(n_{b}^{2})$.

Time complexity to initialize and decay the H-CMS data structure is
$O(n_{r}*n_{b}^{2})$. Temporal decay operation is applied whenever the
timestamp changes, and not for every received edge. Update counts operation
updates a matrix element value ($O(1)$ operation) for $n_{r}$ matrices, and
the time complexity of this step is $O(n_{r})$. Anomaly score for each edge is
based on the submatrix density computation procedure which is $O(n_{b}^{2})$;
the time complexity of $n_{r}$ matrices becomes $O(n_{r}*n_{b}^{2})$.
Therefore, the total time complexity of Algorithm 1 is
$O(|\mathscr{E}|*(n_{r}+n_{r}*n_{b}^{2}))=O(|\mathscr{E}|*n_{r}*n_{b}^{2})$. ∎

######  Proposition 2.

Memory complexity of Algorithm 1 is $O(n_{r}*n_{b}^{2})$.

###### Proof.

For procedure Edge-Submatrix-Density, we keep an $n_{b}$-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 $O(4*n_{b})=O(n_{b})$.

Memory complexity of H-CMS data structure is $O(n_{r}*n_{b}^{2})$. Dense
submatrix search and density computation procedure require $O(n_{b})$ memory.
For $n_{r}$ matrices, this becomes $O(n_{r}*n_{b})$. Therefore, the total
memory complexity of Algorithm 1 is
$O(n_{r}*n_{b}^{2}+n_{r}*n_{b})=O(n_{r}*n_{b}^{2})$. ∎

###  D.2 Proofs: AnoEdge-L

######  Proposition 3.

Time complexity of Algorithm 2 is
$O(n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}*n_{b})$.

###### Proof.

As shown in Proposition 1, the time complexity of H-CMS is
$O(n_{r}*n_{b}^{2})$ and update operation is $O(n_{r})$. Current submatrix
$(S_{cur},T_{cur})$ is updated based on _expand_ and _condense_ submatrix
operations. (a) We keep an $n_{b}$-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 $h(u)$ and column $h(v)$,
and the density is calculated by considering these elements, thus requiring
maximum $n_{b}$ steps. Upon addition of the row (or column), the dependent
column-sums (or row-sums) are also updated taking maximum $n_{b}$ steps. Time
complexity of expand operation is therefore $O(n_{b})$. (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 $O(n_{b})$ time. Removed row (or column) affects the dependent column-
sums (or row-sums) and are updated in $O(n_{b})$ time. Time complexity of a
row (or column) removal is therefore $O(n_{b})$. Condense submatrix removes
rows (or columns) that were once added by the expand submatrix operation which
in worse case is $O|\mathscr{E}|$.

Expand and condense submatrix operations are performed for $n_{r}$ matrices.
Likelihood score calculation depends on elements from row $h(u)$ and column
$h(v)$, and takes $O(n_{r}*n_{b})$ time for $n_{r}$ matrices. Therefore, the
total time complexity of Algorithm 2 is
$O(n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}+|\mathscr{E}|*n_{r}*n_{b}+|\mathscr{E}|*n_{r}*n_{b}+|\mathscr{E}|*n_{r}*n_{b})=O(n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}*n_{b})$.
∎

######  Proposition 4.

Memory complexity of Algorithm 2 is $O(n_{r}*n_{b}^{2})$.

###### Proof.

Memory complexity of the H-CMS data structure is $O(n_{r}*n_{b}^{2})$. To keep
current submatrix information, we utilize $n_{b}$-sized arrays similar to
Proposition 2. For $n_{r}$ matrices, submatrix information requires
$O(n_{r}*n_{b})$ memory. Hence, total memory complexity of Algorithm 2 is
$O(n_{r}*n_{b}^{2}+n_{r}*n_{b})=O(n_{r}*n_{b}^{2})$. ∎

##  Appendix E Graph Anomalies-Proofs

###  E.1 Proofs: AnoGraph

######  Lemma 1.

Let $S^{*}$ and $T^{*}$ be the optimum densest sub-matrix solution of
$\mathcal{M}$ with density $\mathcal{D}(\mathcal{M},S^{*},T^{*})=d_{opt}$.
Then $\forall u\in S^{*}$ and $\forall v\in T^{*}$,

$\mathcal{R}(\mathcal{M},u,T^{*})\geq\tau_{S^{*}};\quad\mathcal{C}(\mathcal{M},S^{*},v)\geq\tau_{T^{*}}$
(3)

where:  $\tau_{S^{*}}$ =
$\mathcal{E}(\mathcal{M},S^{*},T^{*})\left(1-\sqrt{1-\frac{1}{|S^{*}|}}\right)$,
$\tau_{T^{*}}$ =
$\mathcal{E}(\mathcal{M},S^{*},T^{*})\left(1-\sqrt{1-\frac{1}{|T^{*}|}}\right)$

###### Proof.

Leveraging the proof from [49], let’s assume that $\exists u\in S^{*}$ with
$\mathcal{R}(\mathcal{M},u,T^{*})<\tau_{S^{*}}$. Density of submatrix after
removing
$u=\frac{\mathcal{E}(\mathcal{M},S^{*},T^{*})-\mathcal{R}(\mathcal{M},u,T^{*})}{\sqrt{(|S^{*}-1|)|T^{*}|}}$
which is greater than
$\frac{\mathcal{E}(\mathcal{M},S^{*},T^{*})-\tau_{S^{*}}}{\sqrt{(|S^{*}-1|)|T^{*}|}}=d_{opt}$,
and that is not possible. Hence,
$\mathcal{R}(\mathcal{M},u,T^{*})\geq\tau_{S^{*}}$.
$\mathcal{C}(\mathcal{M},S^{*},v)\geq\tau_{T^{*}}$ can be proved in a similar
manner. ∎

######  Theorem 2.

Algorithm 3 achieves a 2-approximation guarantee for the densest submatrix
problem.

###### Proof.

Leveraging the proof from [49], we greedily remove the row (or column) with
minimum row-sum (or column-sum). At some iteration of the greedy process,
$\;\forall u\in S_{cur};\forall v\in T_{cur}$,
$\;\mathcal{R}(\mathcal{M},u,T_{cur})\geq\tau_{S^{*}}$ and
$\mathcal{C}(\mathcal{M},S_{cur},v)\geq\tau_{T^{*}}$. Therefore,
$\mathcal{E}(\mathcal{M},S_{cur},T_{cur})\geq|S_{cur}|\tau_{S^{*}}$ and
$\mathcal{E}(\mathcal{M},S_{cur},T_{cur})\geq|T_{cur}|\tau_{T^{*}}$. This
implies that the density
$\mathcal{D}(\mathcal{M},S_{cur},T_{cur})\geq\sqrt{\frac{|S_{cur}|\tau_{S^{*}}|T_{cur}|\tau_{T^{*}}}{|S_{cur}||T_{cur}|}}=\sqrt{\tau_{S^{*}}\tau_{T^{*}}}$.
Putting values of $\tau_{S^{*}}$ and $\tau_{T^{*}}$ from Lemma 1, and setting
$|S^{*}|=\frac{1}{\sin^{2}\alpha}$, $|T^{*}|=\frac{1}{\sin^{2}\beta}$, we get
$\mathcal{D}(\mathcal{M},S_{cur},T_{cur})\geq\frac{\mathcal{E}(\mathcal{M,S^{*},T^{*}})}{\sqrt{|S^{*}||T^{*}|}}\frac{\sqrt{(1-\cos\alpha)(1-\cos\beta)}}{\sin\alpha\sin\beta}\geq\frac{d_{opt}}{2\cos\frac{\alpha}{2}\cos\frac{\beta}{2}}\geq\frac{d_{opt}}{2}$.
∎

######  Proposition 5.

Time complexity of Algorithm 3 is
$O(|\mathscr{G}|*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$.

###### 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 $n_{b}+n_{b}-2$. We keep $n_{b}$-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 column-sum) takes
$O(n_{b})$ time, and updating the dependent row-sums (or column-sums) also
$O(n_{b})$ time. Density is calculated in $O(n_{b})$ time based on the current
submatrix row-sum and column-sum. Each iteration takes
$O(n_{b}+n_{b}+n_{b})=O(n_{b})$ time. Hence, the total time complexity of
AnoGraph-Density procedure is $O((n_{b}+n_{b}-2)*n_{b})=O(n_{b}^{2})$.

Initializing the H-CMS data structure takes $O(n_{r}*n_{b}^{2})$ time. When a
graph arrives, AnoGraph: (a) resets counts that take $O(n_{r}*n_{b}^{2})$
time; (b) updates counts taking $O(1)$ time for every edge update; (c)
computes submatrix density that follows from procedure AnoGraph-Density and
takes $O(n_{b}^{2})$ time. Each of these operations is applied for $n_{r}$
matrices. Therefore, the total time complexity of Algorithm 3 is
$O(n_{r}*n_{b}^{2}+|\mathscr{G}|*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}+|\mathscr{G}|*n_{r}*n_{b}^{2})=O(|\mathscr{G}|*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$,
where $|\mathscr{E}|$ is the total number of edges over graphs $\mathscr{G}$.
∎

######  Proposition 6.

Memory complexity of Algorithm 3 is $O(n_{r}*n_{b}^{2})$.

###### Proof.

For procedure AnoGraph-Density, we keep $n_{b}$-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
$O(4*n_{b})=O(n_{b})$.

H-CMS data structure requires $O(n_{r}*n_{b}^{2})$ memory. Density computation
relies on AnoGraph-Density procedure, and takes $O(n_{b})$ memory. Therefore,
the total memory complexity of Algorithm 3 is $O(n_{r}*n_{b}^{2})$. ∎

###  E.2 Proofs: AnoGraph-K

######  Proposition 7.

Time complexity of Algorithm 4 is
$O(|\mathscr{G}|*K*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$.

###### Proof.

Relevant operations in Procedure AnoGraph-K-Density directly follow from Edge-
Submatrix-Density procedure, which has $O(n_{b}^{2})$ time complexity. Edge-
Submatrix-Density procedure is called $K$ times, therefore, the total time
complexity of AnoGraph-K-Density procedure is $O(K*n_{b}^{2})$.

For Algorithm 4, we initialize an H-CMS data structure that takes
$O(n_{r}*n_{b}^{2})$ time. When a graph arrives, AnoGraph-K: (a) resets counts
that take $O(n_{r}*n_{b}^{2})$ time; (b) updates counts taking $O(1)$ time for
every edge update; (c) computes submatrix density that follows from procedure
AnoGraph-K-Density and takes $O(K*n_{b}^{2})$ time. Each of these operations
is applied for $n_{r}$ matrices. Therefore, the total time complexity of
Algorithm 4 is
$O(n_{r}*n_{b}^{2}+|\mathscr{G}|*K*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r}+|\mathscr{G}|*n_{r}*n_{b}^{2})=O(|\mathscr{G}|*K*n_{r}*n_{b}^{2}+|\mathscr{E}|*n_{r})$,
where $|\mathscr{E}|$ is the total number of edges over graphs $\mathscr{G}$.
∎

######  Proposition 8.

Memory complexity of Algorithm 4 is $O(n_{r}*n_{b}^{2})$.

###### Proof.

The density of $K$ submatrices is computed independently, and the memory
complexity of Algorithm procedure AnoGraph-K-Density is the same as the memory
complexity of Edge-Submatrix-Density procedure i.e. $O(n_{b})$.

Maintaining the H-CMS data structure requires $O(n_{r}*n_{b}^{2})$ memory.
Density computation relies on AnoGraph-K-Density procedure, and it requires
$O(n_{b})$ memory. Therefore, the total memory complexity of Algorithm 4 is
$O(n_{r}*n_{b}^{2})$. ∎

##  Appendix F Experimental Setup

All experiments are carried out on a $2.4GHz$ Intel Core $i9$ processor,
$32GB$ RAM, running OS $X$ $10.15.3$. For our approach, we keep $n_{r}=2$ and
temporal decay factor $\delta=0.9$. $n_{b}=32$ to have a fair comparison to
MIDAS which uses ${n_{b}}^{2}=1024$ buckets. We keep $K=5$ for Algorithm 4.
AUC for graph anomalies is shown with edge thresholds as $50$ for _DARPA_ and
$100$ for other datasets. Time window is taken as $30$ minutes for _DARPA_ and
$60$ minutes for other datasets.

##  Appendix G Additional Results

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 have performance similar to that in Table 4.

Table 6: AUC when detecting graph anomalies. Dataset | Time | Edge | AnoGraph | AnoGraph-K
---|---|---|---|---
| Window | Threshold |  |
DARPA | $15$ | $25$ | $0.835\pm 0.001$ | $0.838\pm 0.001$
$30$ | $50$ | $0.835\pm 0.002$ | $0.839\pm 0.002$
$60$ | $50$ | $0.747\pm 0.002$ | $0.748\pm 0.001$
$60$ | $100$ | $0.823\pm 0.000$ | $0.825\pm 0.001$
ISCX-IDS2012 | $15$ | $25$ | $0.945\pm 0.001$ | $0.945\pm 0.000$
$30$ | $50$ | $0.949\pm 0.001$ | $0.948\pm 0.000$
$60$ | $50$ | $0.935\pm 0.002$ | $0.933\pm 0.002$
$60$ | $100$ | $0.950\pm 0.001$ | $0.950\pm 0.001$
CIC-IDS2018 | $15$ | $25$ | $0.945\pm 0.004$ | $0.947\pm 0.006$
$30$ | $50$ | $0.959\pm 0.000$ | $0.959\pm 0.001$
$60$ | $50$ | $0.920\pm 0.001$ | $0.920\pm 0.001$
$60$ | $100$ | $0.957\pm 0.000$ | $0.957\pm 0.000$
CIC-DDoS2019 | $15$ | $25$ | $0.864\pm 0.002$ | $0.863\pm 0.003$
$30$ | $50$ | $0.861\pm 0.003$ | $0.861\pm 0.003$
$60$ | $50$ | $0.824\pm 0.004$ | $0.825\pm 0.005$
$60$ | $100$ | $0.946\pm 0.002$ | $0.948\pm 0.002$

##  Appendix H Baselines

We use open-source implementations of DenseStream [1] (Java), SedanSpot [11]
(C++), MIDAS-R [3] (C++), PENminer [12] (Python), F-FADE [13] (Python),
DenseAlert [1] (Java), and AnomRank [14] (C++) provided by the authors,
following parameter settings as suggested in the original paper. For SpotLight
[2], we used open-sourced implementations of Random Cut Forest [55] and Carter
Wegman hashing [56].

###  H.1 Edge Anomalies

  1. 1.

SedanSpot:

     * •

sample_size $=10000$

     * •

num_walk $=50$

     * •

restart_prob $0.15$

  2. 2.

MIDAS: The size of CMSs is 2 rows by 1024 columns for all the tests. For
MIDAS-R, the decay factor $\alpha=0.6$.

  3. 3.

PENminer:

     * •

ws $=1$

     * •

ms $=1$

     * •

view = id

     * •

alpha $=1$

     * •

beta $=1$

     * •

gamma $=1$

  4. 4.

DenseStream: We keep default parameters, i.e., order $=3$.

  5. 5.

F-FADE:

     * •

embedding_size $=200$

     * •

W_upd $=720$

     * •

T_th $=120$

     * •

alpha $=0.999$

     * •

M $=100$

For t_setup, we always use the timestamp value at the $10^{th}$ percentile of
the dataset.

###  H.2 Graph Anomalies

  1. 1.

SpotLight:

     * •

K $=50$

     * •

p $=0.2$

     * •

q $=0.2$

  2. 2.

DenseAlert: We keep default parameters, i.e., order $=3$ and window=$60$.

  3. 3.

AnomRank: We keep default parameters, i.e., damping factor c $=0.5$, and L1
changes of node score vectors threshold epsilon $=10^{-3}$. We keep
${1/4}^{th}$ number of graphs for initializing mean/variance as mentioned in
the respective paper.


# A New Aspect of Chebyshev’s Bias for Elliptic Curves over Function Fields

Ikuya Kaneko  The Division of Physics, Mathematics and Astronomy, California
Institute of Technology, 1200 E. California Blvd., Pasadena, CA 91125, USA
<EMAIL_ADDRESS>https://sites.google.com/view/ikuyakaneko/ and  Shin-ya
Koyama  Department of Biomedical Engineering, Toyo University, 2100 Kujirai,
Kawagoe, Saitama, 350-8585, Japan<EMAIL_ADDRESS>http://www1.tmtv.ne.jp/
koyama/

###### Abstract.

This work considers the prime number races for non-constant elliptic curves
$E$ over function fields. We prove that if $\mathrm{rank}(E)>0$, then there
exist Chebyshev biases towards being negative, and otherwise there exist
Chebyshev biases towards being positive. The main innovation entails the
convergence of the partial Euler product at the centre that follows from the
Deep Riemann Hypothesis over function fields.

###### Key words and phrases:

Deep Riemann Hypothesis, Grand Riemann Hypothesis, Birch–Swinnerton-Dyer
conjecture, $L$-functions, elliptic curves, function fields, Chebyshev’s bias

###### 2020 Mathematics Subject Classification:

Primary: 11G40; Secondary: 11M38

##  1\. Introduction

In 1853, Chebyshev noticed in a letter to Fuss that primes congruent to $3$
modulo $4$ seem to predominate over those congruent to $1$ modulo $4$. If
$\pi(x;q,a)$ signifies the number of primes $p\leq x$ such that $p\equiv
a{\@displayfalse\,(\mathrm{mod}{\,q})}$, then the inequality
$\pi(x;4,3)\geq\pi(x;4,1)$ holds for more than 97 % of $x<10^{11}$. On the
other hand, were we to leverage Dirichlet’s theorem on primes in arithmetic
progressions, then it is expected that the number of the primes of the form
$4k+1$ and $4k+3$ should be asymptotically equal. Therefore, the Chebyshev
bias indicates that the primes of the form $4k+3$ appear earlier than those of
the form $4k+1$. Classical triumphs include the work of Littlewood [12] who
established that $\pi(x;4,3)-\pi(x;4,1)$ changes its sign infinitely often.
Knapowski–Turán [9] conjectured that the density of the numbers $x$ for which
$\pi(x;4,3)\geq\pi(x;4,1)$ holds is $1$. Nonetheless, the work of Kaczorowski
[7] shows the falsity of their conjecture conditionally on the Generalised
Riemann Hypothesis. Note that they have a logarithmic density via work of
Rubinstein–Sarnak [14], which is approximately $0.9959\cdots$.

In this fundamental scenario, the next layer of methodological depth came with
the introduction of a weighted counting function that allows one to scrutinise
the above phenomenon. The work of Aoki–Koyama [2] introduces the counting
function

$\pi_{s}(x;q,a)\coloneqq\sum_{\begin{subarray}{c}p\leq x\\\ p\equiv
a{\@displayfalse\,(\mathrm{mod}{\,q})}\end{subarray}}\frac{1}{p^{s}},\qquad
s\geq 0,$ (1.1)

extending $\pi(x;q,a)=\pi_{0}(x;q,a)$, where the smaller prime $p$ permits a
higher contribution to $\pi_{s}(x;q,a)$ as long as we fix $s>0$. The function
$\pi_{s}(x;q,a)$ ought to be more appropriate than $\pi(x;q,a)$ to represent
the phenomenon, since it reflects the size of the primes that $\pi(x;q,a)$
ignores. Although the natural density of the set
$\\{x>0\mid\pi_{s}(x;4,3)-\pi_{s}(x;4,1)>0\\}$ does not exist when $s=0$ under
the Generalised Riemann Hypothesis (see the article [7]), they have shown
under the Deep Riemann Hypothesis (DRH) that it would be equal to $1$ when
$s=1/2$. More precisely, the Chebyshev bias could be realised in terms of the
asymptotic formula

$\pi_{\frac{1}{2}}(x;4,3)-\pi_{\frac{1}{2}}(x;4,1)=\frac{1}{2}\log\log
x+c+o(1)$ (1.2)

as $x\to\infty$, where $c$ is a constant.

The Chebyshev biases for prime ideals $\mathfrak{p}$ of a global field $K$ are
formulated as follows.

######  Definition 1.1 (Aoki–Koyama [2]).

Let $c(\mathfrak{p})\in\mathbb{R}$ be a sequence over primes $\mathfrak{p}$ of
$K$ such that

$\lim_{x\to\infty}\frac{\\#\\{\mathfrak{p}\mid
c(\mathfrak{p})>0,\mathrm{N}(\mathfrak{p})\leq x\\}}{\\#\\{\mathfrak{p}\mid
c(\mathfrak{p})<0,\mathrm{N}(\mathfrak{p})\leq x\\}}=1.$

We say that $c(\mathfrak{p})$ has a Chebyshev bias towards being positive if
there exists a constant $C>0$ such that

$\sum_{\mathrm{N}(\mathfrak{p})\leq
x}\frac{c(\mathfrak{p})}{\sqrt{\mathrm{N}(\mathfrak{p})}}\sim C\log\log x,$

where $\mathfrak{p}$ ranges over primes of $K$. On the other hand, we say that
$c(\mathfrak{p})$ is unbiased if

$\sum_{\mathrm{N}(\mathfrak{p})\leq
x}\frac{c(\mathfrak{p})}{\sqrt{\mathrm{N}(\mathfrak{p})}}=O(1).$

######  Definition 1.2 (Aoki–Koyama [2]).

Assume that the set of all primes $\mathfrak{p}$ of $K$ with
$\mathrm{N}(\mathfrak{p})\leq x$ is expressed as a disjoint union
$P_{1}(x)\cup P_{2}(x)$ and that their proportion converges to

$\delta=\lim_{x\to\infty}\frac{|P_{1}(x)|}{|P_{2}(x)|}.$

We say that there exists a Chebyshev bias towards $P_{1}$ or a Chebyshev bias
against $P_{2}$ if

$\sum_{p\in
P_{1}(x)}\frac{1}{\sqrt{\mathrm{N}(\mathfrak{p})}}-\delta\sum_{p\in
P_{2}(x)}\frac{1}{\sqrt{\mathrm{N}(\mathfrak{p})}}\sim C\log\log x$

for some $C>0$. On the other hand, we say that there exist no biases between
$P_{1}$ and $P_{2}$ if

$\sum_{p\in
P_{1}(x)}\frac{1}{\sqrt{\mathrm{N}(\mathfrak{p})}}-\delta\sum_{p\in
P_{2}(x)}\frac{1}{\sqrt{\mathrm{N}(\mathfrak{p})}}=O(1).$

Definitions 1.1 and 1.2 differ from those in [1, 6, 14] and formulate an
asymptotic formula for the size of the discrepancy caused by Chebyshev’s bias
disregarded in the conventional definitions of the length of the interval in
terms of the limiting distributions. Definitions 1.1 and 1.2 involve little
information on the density distributions and both types of formulations appear
not to have any logical connections. They shed some light on Chebyshev’s bias
from different directions.

It is shown in [2, Corollary 3.2] that the Chebyshev bias (1.2) against the
quadratic residue $1{\@displayfalse\,(\mathrm{mod}{\,4})}$ is equivalent to
the convergence of the Euler product at the centre $s=1/2$ for the Dirichlet
$L$-function $L(s,\chi_{-4})$ with $\chi_{-4}$ denoting the nontrivial
character modulo $4$. This is related to DRH proposed by Kurokawa [8, 11] in
2012.

Aoki–Koyama [2] have observed various instances of Chebyshev biases that
certain prime ideals in Galois extensions of global fields have over others,
with an emphasis on the biases against splitting primes and principal prime
ideals. Koyama–Kurokawa [10] have obtained an analogue of this phenomenon for
Ramanujan’s $\tau$-function $\tau(p)$ and shown that DRH for the automorphic
$L$-function $L(s+11/2,\Delta)$ implies the bias of $\tau(p)/p^{11/2}$ towards
positive values.

In this work, we delve into such phenomena on the prime number races that
elliptic curves over function fields give rise to. Let $E$ be an elliptic
curve over $K$ and let $E_{v}$ be the reduction of $E$ on the residue field
$k_{v}$ at a finite place $v$ of $K$. If $E$ has good reduction at $v$, we
define

$a_{v}=a_{v}(E)\coloneqq q_{v}+1-\\#E_{v}(k_{v}),$

where $q_{v}=\\#k_{v}$ and $\\#E_{v}(k_{v})$ is the number of $k_{v}$-rational
points on $E_{v}$. The symbol $a_{v}$ can be extended to all other finite
places $v$ as follows:

$a_{v}\coloneqq\begin{cases}1&\text{if $E$ has split multiplicative reduction
at $v$},\\\ -1&\text{if $E$ has nonsplit multiplicative reduction at $v$},\\\
0&\text{if $E$ has additive reduction at $v$}.\end{cases}$

This work aims to prove the following asymptotic corresponding to the case of
$s=1/2$ in (1.1).

######  Theorem 1.3.

Assume $\mathrm{char}(K)>0$ and that $E$ is a non-constant elliptic curve over
$K$ in the terminology of Ulmer [17, Definitions 1.1.4]. If
$\mathrm{rank}(E)>0$, then the sequence $a_{v}/\sqrt{q_{v}}$ has a Chebyshev
bias towards being negative. To be more precise, we have that

$\sum_{q_{v}\leq
x}\frac{a_{v}}{q_{v}}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\frac{1}{2}-\mathrm{rank}(E)\right)}\log\log
x+O(1).$ (1.3)

The proof uses the convergence of the Euler product at the centre, which
follows from DRH over function fields due to Conrad [5] and
Kaneko–Koyama–Kurokawa [8]; see §2 for details.

## Acknowledgements

The authors would like to thank Nobushige Kurokawa for instructive
discussions. The first author acknowledges the support of the Masason
Foundation and the Spirit of Ramanujan STEM Talent Initiative. The second
author was partially supported by the INOUE ENRYO Memorial Grant 2022, TOYO
University.

##  2\. Deep Riemann Hypothesis

Let $K$ be a one-dimensional global field that is either a number field or a
function field in one variable over a finite field. For a place $v$ of $K$,
let $M(v)$ denote a unitary matrix of degree $r_{v}\in\mathbb{N}$. We consider
an $L$-function expressed as the Euler product

$L(s,M)=\prod_{v<\infty}\det(1-M(v)q_{v}^{-s})^{-1},$ (2.1)

where $q_{v}$ is the cardinal of the residue field $k_{v}$ at $v$. The product
(2.1) is absolutely convergent in $\mathrm{Re}(s)>1$. In this article, we
assume that $L(s,M)$ has an analytic continuation as an entire function on
$\mathbb{C}$ and a functional equation relating values at $s$ and $1-s$.
Moreover, we set

$\delta(M)=-\mathop{\mathrm{ord}}_{s=1}L(s,M^{2}),$

where $\mathop{\mathrm{ord}}_{s=1}$ signifies the order of the zero at $s=1$.
We here do not presuppose that $M$ is a representation. The square $M^{2}$ is
interpreted as an Adams operation. Note that since

$L(s,M^{2})=\prod_{v<\infty}\det(1-M(v)^{2}q_{v}^{-s})^{-1}=\frac{L(s,\mathrm{Sym}^{2}M)}{L(s,\wedge^{2}M)},$

we derive the expression

$\delta(M)=-\mathop{\mathrm{ord}}_{s=1}L(s,\mathrm{Sym}^{2}M)+\mathop{\mathrm{ord}}_{s=1}L(s,\wedge^{2}M),$
(2.2)

where $\mathrm{Sym}^{2}$ and $\wedge^{2}$ denote the symmetric and the
exterior squares, respectively. If we assume that $M$ is an Artin
representation

$\rho\colon\mathrm{Gal}(K^{\mathrm{sep}}/K)\to\mathrm{Aut}_{\mathbb{C}}(V),\qquad\rho\neq\mathbbm{1}$

with a representation space $V$, then

$\delta(M)=\mathrm{mult}(\mathbbm{1},\mathrm{Sym}^{2}\rho)-\mathrm{mult}(\mathbbm{1},\wedge^{2}\rho),$

where $\mathrm{mult}(\mathbbm{1},\sigma)$ is the multiplicity of the trivial
representation $\mathbbm{1}$ in $\sigma$.

We are now in a position to formulate DRH due to Kurokawa [8, 11] in a general
context.

######  Conjecture 2.1 (Deep Riemann Hypothesis).

Keep the assumptions and notation as above. Let
$m=\mathop{\mathrm{ord}}_{s=1/2}L(s,M)$. Then the limit

$\lim_{x\to\infty}\left((\log x)^{m}\prod_{q_{v}\leq
x}\det\left(1-M(v)q_{v}^{-\frac{1}{2}}\right)^{-1}\right)$ (2.3)

satisfies the following conditions:

DRH (A):

The limit (2.3) exists and is nonzero.

DRH (B):

The limit (2.3) satisfies

$\lim_{x\to\infty}\left((\log x)^{m}\prod_{q_{v}\leq
x}\det\left(1-M(v)q_{v}^{-\frac{1}{2}}\right)^{-1}\right)=\frac{\sqrt{2}^{\delta(M)}}{e^{m\gamma}m!}\cdot
L^{(m)}\left(\frac{1}{2},M\right).$

It is obvious that DRH (B) indicates DRH (A). Nonetheless, DRH (A) is still
meaningful since it is essentially equivalent to the Chebyshev biases. The
following instances clarify this situation; we refer the reader to the work of
Aoki–Koyama [2] for more interesting examples.

######  Example 2.2 (Aoki–Koyama [2]).

If $K=\mathbb{Q}$, we denote a prime number by $v=p$. If $r_{p}=1$ for any $p$
and $M$ is the nontrivial Dirichlet character modulo 4, namely
$M(p)=\chi_{-4}(p)$, then we have that $L(s,M)=L(s,\chi_{-4})$ and
$\delta(M)=1$. It is shown in their work [2] that DRH (A) for $L(s,\chi_{-4})$
is equivalent to the original form of the Chebyshev bias (1.2).

######  Example 2.3 (Koyama–Kurokawa [10]).

Let $K=\mathbb{Q}$ and $r_{p}=2$ for any $p$, and let $\tau(p)\in\mathbb{Z}$
be Ramanujan’s $\tau$-function defined for $q=e^{2\pi iz}$ with
$\mathrm{Im}(z)>0$ by

$\Delta(z)=q\prod_{k=1}^{\infty}(1-q^{k})^{24}=\sum_{n=1}^{\infty}\tau(n)q^{n}.$

We introduce $M(p)=\begin{pmatrix}e^{i\theta_{p}}&0\\\
0&e^{-i\theta_{p}}\end{pmatrix}$, where the Satake parameter
$\theta_{p}\in[0,\pi]\cong\mathrm{Conj}(\mathrm{SU}(2))$ is defined by
$\tau(p)=2p^{11/2}\cos(\theta_{p})$. It then follows that the associated
$L$-function

$L(s,M)=\prod_{p}(1-2\cos(\theta_{p})p^{-s}+p^{-2s})^{-1}$

satisfies a functional equation for $s\leftrightarrow 1-s$. Using the
conventional notation of Ramanujan’s $L$-function

$L(s,\Delta)=\sum_{n=1}^{\infty}\frac{\tau(n)}{n^{s}},$

which satisfies a functional equation for $s\leftrightarrow 12-s$, we have
that $L(s,M)=L(s+11/2,\Delta)$ and $\delta(M)=-1$. It is shown in [10] that
DRH (A) for $L(s,M)=L(s+11/2,\Delta)$ implies that there exists a Chebyshev
bias for the sequence $\tau(p)/p^{11/2}$ towards being positive.

Conjecture 2.1 is known to hold when the characteristic is positive. The proof
was given by Conrad [5, Theorems 8.1 and 8.2] under the second moment
hypothesis, and the full proof was offered by Kaneko–Koyama–Kurokawa [8,
Theorem 5.5]. We record their result as follows.

######  Theorem 2.4 (Kaneko–Koyama–Kurokawa [8]).

Conjecture 2.1 is valid for $\mathrm{char}(K)>0$.

##  3\. Proof of Theorem 1.3

Let $E$ be an elliptic curve over a global field $K$ and let $a_{v}$ be the
same as in the introduction. We define the parameter
$\theta_{v}\in[0,\pi]\cong\mathrm{Conj}(\mathrm{SU}(2))$ by
$a_{v}=2\sqrt{q_{v}}\cos(\theta_{v})$. If one writes

$r_{v}=\begin{cases}2&\text{if $v$ is good},\\\ 1&\text{if $v$ is
bad},\end{cases}$

and

$M(v)=M_{E}(v)=\begin{cases}\begin{pmatrix}e^{i\theta_{v}}&0\\\
0&e^{-i\theta_{v}}\end{pmatrix}&\text{if $v$ is good},\\\ a_{v}&\text{if $v$
is bad},\end{cases}$

then the $L$-function (2.1) is equal to

$L(s,M)=L(s,M_{E})=\prod_{v\colon\text{good}}(1-2\cos(\theta_{v})q_{v}^{-s}+q_{v}^{-2s})^{-1}\prod_{v\colon\text{bad}}(1-a_{v}q_{v}^{-s})^{-1}.$

This Euler product is absolutely convergent in $\mathrm{Re}(s)>1$ and has an
meromorphic continuation to the whole complex plane $\mathbb{C}$ along with a
functional equation for $s\leftrightarrow 1-s$.

The $L$-function $L(s,M_{E})$ is expressed in terms of an Artin-type
$L$-function in the following manner. Fixing $\ell$ and $K$ with
$\ell\neq\mathrm{char}(K)$, we obtain the representation

$\rho_{E}\colon\mathrm{Gal}(K^{\mathrm{sep}}/K)\to\mathrm{Aut}(T_{\ell}(E)\otimes\mathbb{Q}_{\ell}),$
(3.1)

where $T_{\ell}(E)=\varprojlim\limits_{n}E[\ell^{n}]$ is the $\ell$-adic Tate
module of $E/K$. The Artin $L$-function associated to the Galois
representation $\rho_{E}$ is defined by the Euler product

$L(s,\rho_{E})=\prod_{v<\infty}\det(1-q_{v}^{-s}\rho_{E}(\mathrm{Frob}_{v}|V^{I_{v}}))^{-1}.$

The Euler factors of $L(s,M_{E})$ are in accordance with those of
$L(s+1/2,\rho_{E})$ for all places $v$ at which $E$ has good reduction. In
other words, the $L$-function $L(s,M_{E})$ equals $L(s+1/2,\rho_{E})$ up to
finite factors stemming from bad places.

Conjecture 2.1 originates from the Birch–Swinnerton-Dyer conjecture in the
following form.

######  Conjecture 3.1 (Birch–Swinnerton-Dyer [3, Page 79 (A)]).

Let $E$ be an elliptic curve $E$ over $K$. Then there exists a constant $A>0$
dependent on $E$ such that

$\prod_{\begin{subarray}{c}q_{v}\leq x\\\
v\colon\text{good}\end{subarray}}\frac{\\#E(k_{v})}{q_{v}}\sim A(\log x)^{r},$
(3.2)

where $r=\mathrm{rank}(E)$. Moreover, $r$ is equal to the order of vanishing
of $L(s,M_{E})$ at $s=1/2$.

Since the left-hand side of (3.2) coincides with the Euler product over good
places of the $L$-function $L(s,M_{E})$ at $s=1/2$, Conjecture 3.1 is
indicative of DRH (A) for $L(s,M_{E})$.

######  Theorem 3.2.

Keep the notation as above. The following conditions are equivalent.

  1. (i)

DRH (A) holds for $L(s,M)$.

  2. (ii)

There exists a constant $c$ such that

$\sum_{q_{v}\leq
x}\frac{\mathrm{tr}(M(v))}{\sqrt{q_{v}}}=-\left(\frac{\delta(M)}{2}+m\right){\log\log
x}+c+o(1),$

where $m=\mathop{\mathrm{ord}}_{s=1/2}L(s,M)$.

###### Proof.

We introduce

$\displaystyle\text{I}(x)$ $\displaystyle=\sum_{q_{v}\leq
x}\frac{\mathrm{tr}(M(v))}{\sqrt{q_{v}}},$ $\displaystyle\text{II}(x)$
$\displaystyle=\frac{1}{2}\sum_{q_{v}\leq
x}\frac{\mathrm{tr}(M(v)^{2})}{q_{v}},$ $\displaystyle\text{III}(x)$
$\displaystyle=\sum_{k=3}^{\infty}\frac{1}{k}\sum_{q_{v}\leq
x}\frac{\mathrm{tr}(M(v)^{k})}{q_{v}^{k/2}}.$

Since one has

$\text{I}(x)+\text{II}(x)+\text{III}(x)=\log\left(\prod_{q_{v}\leq
x}\det\left(1-M(v)q_{v}^{-\frac{1}{2}}\right)^{-1}\right),$

the condition (i) is equivalent to the claim that there exists a constant $L$
such that

$m\log\log x+\text{I}(x)+\text{II}(x)+\text{III}(x)=L+o(1).$ (3.3)

The generalised Mertens theorem (see [13, Theorem 5] and [8, Lemma 5.3]) gives

$\text{II}(x)=\frac{\delta(M)}{2}\log\log x+C_{1}+o(1)$ (3.4)

for some constant $C_{1}$. Additionally, it is straightforward to see that
there exists a constant $C_{2}$ such that

$\text{III}(x)=C_{2}+o(1).$ (3.5)

Therefore, the estimates (3.3)–(3.5) yield

$\text{I}(x)=-\left(\frac{\delta(M)}{2}+m\right)\log\log
x+L-C_{1}-C_{2}+o(1).$

If we assume (i), then the condition (ii) is valid with $c=L-C_{1}-C_{2}$.
Conversely, if we assume (ii), then (3.3) is valid with $L=c+C_{1}+C_{2}$.
This finishes the proof of Theorem 3.2. ∎

In order to examine the asymptotic behavior of a sum over $v$ with $q_{v}\leq
x$ as $x\to\infty$, it suffices to restrict ourselves to places $v$ at which
$E$ has good reduction. When $v$ is good, the $n$-th symmetric power matrix
$\mathrm{Sym}^{n}M$ of size $n+1$ is given by

$(\mathrm{Sym}^{n}M)(v)=\mathrm{diag}(e^{in\theta_{v}},e^{i(n-2)\theta_{v}},\cdots,e^{-i(n-2)\theta_{v}},e^{-in\theta_{v}}).$

We calculate

$\mathrm{tr}(\mathrm{Sym}^{n}M)(v)=\frac{\sin((n+1)\theta_{v})}{\sin\theta_{v}}.$

Extending the definition of $(\mathrm{Sym}^{n}M)(v)$ to all places $v$ by
setting $(\mathrm{Sym}^{n}M)(v)=a_{v}^{n}$ for bad places $v$, one defines the
$n$-th symmetric power $L$-function $L(s,\mathrm{Sym}^{n}M)$. With the
standard notation for the Galois representation $\rho=\rho_{E}$ in (3.1), we
have the following normalisation:

$L(s,\mathrm{Sym}^{n}M)=L\left(s+\frac{n}{2},\mathrm{Sym}^{n}\rho\right).$
(3.6)

If $E$ is a non-constant elliptic curve in the terminology of Ulmer [17,
Definitions 1.1.4], it is known that $L(s,\mathrm{Sym}^{n}M)$ is a polynomial
in $q^{-n/2-s}$ (see [4, 16]) and the absolute values of its roots are equal
to $q^{-(n+1)/2}$ with the normalisation (3.6) taken into account. Therefore,
all zeroes of (3.6) lie on the critical line $\mathrm{Re}(s)=1/2$ and there
holds

$\mathop{\mathrm{ord}}_{s=1}L(s,\mathrm{Sym}^{n}M)=0,\qquad n\in\mathbb{N}.$
(3.7)

######  Lemma 3.3.

If $\mathrm{char}(K)>0$ and $E$ is a non-constant elliptic curve over $K$,
then we have for $M=M_{E}$ that $\delta(M)=-1.$

###### Proof.

Since $M$ is a unitary matrix of size 2, the exterior square matrix
$\wedge^{2}M$ is trivial. Thus
$\mathop{\mathrm{ord}}_{s=1}L(s,\wedge^{2}M)=-1$. The claim follows from (2.2)
and (3.7). ∎

In what follows, we use the shorthand
$m_{n}=\mathop{\mathrm{ord}}_{s=1/2}L(s,\mathrm{Sym}^{n}M)$.

######  Theorem 3.4.

If $\mathrm{char}(K)>0$ and $E$ is a non-constant elliptic curve over $K$,
then we have that

$\sum_{q_{v}\leq
x}\frac{a_{v}}{q_{v}}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(\frac{1}{2}-m_{1}\right)}\log\log
x+O(1).$ (3.8)

In particular, if $\mathrm{rank}(E)>0$, the sequence $a_{v}/\sqrt{q_{v}}$ has
a Chebyshev bias towards being negative.

###### Proof.

In [16, §3.1.7] and [17, Theorem 9.3], Ulmer proves that $L(s,M_{E})$ is a
polynomial in $q^{-s}$ for any non-constant elliptic curve $E$ and hence it is
entire and satisfies the assumption of Conjecture 2.1. By Theorem 2.4, DRH
holds for $L(s,M_{E})$. By Theorem 3.2 and Lemma 3.3, we are able to prove
(3.8). In order to justify the second assertion, we appeal to the work of
Ulmer [17, Theorem 12.1 (1)], which says that $\mathrm{rank}(E)\leq m_{1}$.
Using this inequality, we have $m_{1}\geq 1$ and thereby $C<0$. This completes
the proof of Theorem 3.4. ∎

Theorem 3.4 is in accordance with the prediction of Sarnak [15, page 5] that
$\mathrm{rank}(E)>0$ implies the existence of a bias towards being negative,
although he considers the sequence $a_{v}$ instead of $a_{v}/\sqrt{q_{v}}$. He
also states that $\mathrm{rank}(E)=0$ implies the existence of a bias towards
being positive. We ascertain this phenomenon under the Birch–Swinnerton-Dyer
conjecture.

######  Corollary 3.5.

Assume that $L(1,M_{E})\neq 0$. If $\mathrm{char}(K)>0$ and $E$ is a non-
constant elliptic curve over $K$ such that $\mathrm{rank}(E)=0$, then we have
that

$\sum_{q_{v}\leq x}\frac{a_{v}}{q_{v}}=\frac{1}{2}\log\log x+O(1).$ (3.9)

In other words, the sequence $a_{v}/\sqrt{q_{v}}$ has a Chebyshev bias towards
being positive.

###### Proof.

The Birch–Swinnerton-Dyer conjecture asserts that $m_{1}=\mathrm{rank}(E)$,
which implies that $m_{1}=0$. Hence the asymptotic formula (3.8) gives the
desired result. ∎

######  Remark 1.

Cha–Fiorilli–Jouve [4, Theorem 1.7] have shown that there exist infinitely
many elliptic curves $E/\mathbb{F}_{q}(T)$ such that the sequence $a_{v}$ is
unbiased in the following sense:

$\lim_{X\to\infty}\frac{1}{X}\sum_{\begin{subarray}{c}x\leq X\\\
T_{E}(x)>0\end{subarray}}1=\frac{1}{2}$

with

$T_{E}(x)=-\frac{x}{q^{x/2}}\sum_{\begin{subarray}{c}\deg(v)\leq x\\\
v\colon\text{good}\end{subarray}}2\cos\theta_{v}=-\frac{x}{q^{x/2}}\sum_{\begin{subarray}{c}\deg(v)\leq
x\\\ v\colon\text{good}\end{subarray}}\frac{a_{v}}{q^{\deg(v)/2}}.$

Despite their work discussing the Chebyshev bias for the sequence $a_{v}$,
which is different from the sequence $a_{v}/\sqrt{q_{v}}$ dealt with in
Theorem 3.4, we strongly believe that these are constant elliptic curves whose
$L$-functions have a pole at $s=1$ and do not satisfy DRH.

We obtain other types of biases on the Satake parameters $\theta_{v}$ by
considering the symmetric square $L$-function.

######  Theorem 3.6.

If $\mathrm{char}(K)>0$ and $E$ is a non-constant elliptic curve over $K$,
then we have that

$\sum_{q_{v}\leq
x}\frac{(2\cos\theta_{v}-1)(\cos\theta_{v}+1)}{\sqrt{q_{v}}}=(1-m_{1}-m_{2})\log\log
x+O(1).$ (3.10)

In particular, if both $L(1/2,M)\neq 0$ and $L(1/2,\mathrm{Sym}^{2}M)\neq 0$
are true, the sequence $(2\cos\theta_{v}-1)(\cos\theta_{v}+1)$ has a Chebyshev
bias towards being positive.

###### Proof.

Applying Theorem 3.2 to $L(s,M)$ and $L(s,\mathrm{Sym}^{2}M)$, we deduce

$\sum_{q_{v}\leq
x}\frac{2\cos\theta_{v}}{\sqrt{q_{v}}}=\left(\frac{1}{2}-m_{1}\right){\log\log
x}+O(1)$ (3.11)

and

$\sum_{q_{v}\leq x}\frac{2\cos
2\theta_{v}}{\sqrt{q_{v}}}=\left(\frac{1}{2}-m_{2}\right){\log\log x}+O(1).$
(3.12)

It follows that $\eqref{n=2}+\eqref{n=1}$ equals

$\sum_{q_{v}\leq x}\frac{2(\cos\theta_{v}+\cos
2\theta_{v})}{\sqrt{q_{v}}}=\sum_{q_{v}\leq
x}\frac{2(2\cos\theta_{v}-1)(\cos\theta_{v}+1)}{\sqrt{q_{v}}}=(1-m_{1}-m_{2})\log\log
x+O(1).$

This concludes the proof of Theorem 3.6. ∎

We give an example of unbiased sequences constructed from the Satake
parameters $\theta_{v}$.

######  Theorem 3.7.

If $\mathrm{char}(K)>0$ and $E$ is a non-constant elliptic curve over $K$,
then we have that

$\sum_{q_{v}\leq
x}\frac{2(2\cos\theta_{v}+1)(\cos\theta_{v}-1)}{\sqrt{q_{v}}}=(m_{1}-m_{2})\log\log
x+O(1).$ (3.13)

In particular, if $m_{1}=m_{2}$, the sequence
$(2\cos\theta_{v}+1)(\cos\theta_{v}-1)$ is unbiased.

###### Proof.

It follows that $\eqref{n=2}-\eqref{n=1}$ equals

$\sum_{q_{v}\leq x}\frac{2(\cos
2\theta_{v}-\cos\theta_{v})}{\sqrt{q_{v}}}=\sum_{q_{v}\leq
x}\frac{2(2\cos\theta_{v}+1)(\cos\theta_{v}-1)}{\sqrt{q_{v}}}=(m_{1}-m_{2})\log\log
x+O(1).$

This concludes the proof of Theorem 3.7. ∎

## References

  * [1] A. Akbary, N. Ng, and M. Shahabi.  Limiting distributions of the classical error terms of prime number theory.  Q. J. Math., 65(3):743–780, 2014.
  * [2] M. Aoki and S. Koyama.  Chebyshev’s bias against splitting and principal primes in global fields.  to appear in J. Number Theory, 35 pages, 2023.  https://doi.org/10.1016/j.jnt.2022.10.005.
  * [3] B. J. Birch and H. P. F. Swinnerton-Dyer.  Notes on elliptic curves. II.  J. Reine Angew. Math., 218:79–108, 1965.
  * [4] B. Cha, D. Fiorilli, and F. Jouve.  Prime number races for elliptic curves over function fields.  Ann. Sci. École Norm. Sup. (4), 49(5):1239–1277, 2016.
  * [5] K. Conrad.  Partial Euler products on the critical line.  Canad. J. Math., 57(2):267–297, 2005.
  * [6] L. Devin.  Chebyshev’s bias for analytic $L$-functions.  Math. Proc. Cambridge Philos. Soc., 169(1):103–140, 2020.
  * [7] J. Kaczorowski.  On the distribution of primes (mod $4$).  Analysis, 15(2):159–171, 1995.
  * [8] I. Kaneko, S. Koyama, and N. Kurokawa.  Towards the Deep Riemann Hypothesis for $\mathrm{GL}_{n}$.  arXiv e-prints, 17 pages, 2022.  https://arxiv.org/abs/2206.02612.
  * [9] S. Knapowski and P. Turán.  Comparative prime-number theory. I. Introduction.  Acta Math. Acad. Sci. Hungar., 13:299–314, 1962.
  * [10] S. Koyama and N. Kurokawa.  Chebyshev’s bias for Ramanujan’s $\tau$-function via the Deep Riemann Hypothesis.  Proc. Japan Acad. Ser. A Math. Sci., 98(6):35–39, 2022.
  * [11] N. Kurokawa.  The pursuit of the Riemann Hypothesis (in Japanese).  Gijutsu Hyouron-sha, Tokyo, 2012.
  * [12] J. E. Littlewood.  Sur la distribution des nombres premiers.  C. R. Acad. Sci. Paris, 158:1869–1872, 1914.
  * [13] M. I. Rosen.  A generalization of Mertens’ theorem.  J. Ramanujan Math. Soc., 14:1–19, 1999.
  * [14] M. Rubinstein and P. Sarnak.  Chebyshev’s bias.  Experiment. Math., 3(3):173–197, 1994.
  * [15] P. Sarnak.  Letter to: Barry Mazur on “Chebyshev’s bias” for $\tau(p)$, 2007\.  https://publications.ias.edu/sites/default/files/MazurLtrMay08.PDF.
  * [16] D. Ulmer.  Geometric non-vanishing.  Invent. Math., 159(1):133–186, 2005.
  * [17] D. Ulmer.  Elliptic curves over function fields.  In C. Popescu, K. Rubin, and A. Silverberg, editors, Arithmetic of $L$-Functions, volume 18 of IAS/Park City Mathematics Series, pages 211–280. Amer. Math. Soc., Providence, RI, 2011.