# Anomaly detection in the dynamics of web and social networks

Volodymyr Miz, Benjamin Ricaud, Kirell Benzi, and Pierre Vandergheynst  Ecole
Polytechnique Fédérale de LausanneLausanneSwitzerland<EMAIL_ADDRESS>
(2018)

###### Abstract.

In this work, we propose a new, fast and scalable method for anomaly detection
in large time-evolving graphs. It may be a static graph with dynamic node
attributes (e.g. time-series), or a graph evolving in time, such as a temporal
network. We define an anomaly as a localized increase in temporal activity in
a cluster of nodes. The algorithm is unsupervised. It is able to detect and
track anomalous activity in a dynamic network despite the noise from multiple
interfering sources.

We use the Hopfield network model of memory to combine the graph and time
information. We show that anomalies can be spotted with a good precision using
a memory network. The presented approach is scalable and we provide a
distributed implementation of the algorithm.

To demonstrate its efficiency, we apply it to two datasets: Enron Email
dataset and Wikipedia page views. We show that the anomalous spikes are
triggered by the real-world events that impact the network dynamics. Besides,
the structure of the clusters and the analysis of the time evolution
associated with the detected events reveals interesting facts on how humans
interact, exchange and search for information, opening the door to new
quantitative studies on collective and social behavior on large and dynamic
datasets.

Anomaly Detection, Dynamic Network, Graph Algorithm, Hopfield Network,
Wikipedia, Web Logs Analysis

††copyright: acmcopyright††doi: 10.475/123_4††isbn:
123-4567-24-567/08/06††conference: May 13-17; San-Francisco; USA††journalyear:
2019††ccs: Computing methodologies Anomaly detection††ccs: Information systems
Wrappers (data mining)††ccs: Information systems Web log analysis††ccs: Theory
of computation Dynamic graph algorithms††ccs: Theory of computation
Unsupervised learning and clustering

##  1\. Introduction

In recent years, the Web has significantly affected the way people learn,
interact in social groups, store and share information. Apart from being an
essential part of modern life, social networks, online services, and knowledge
bases generate a massive amount of logs containing traces of global online
activity on the Web. Most of this data is related to the standard activity of
the users. However, the larger these logs become, the harder it is to detect
deviations from normal behavior in the network. Localization of these
anomalies becomes even more difficult because of the continuous expansion and
dynamic nature of these networks. Hence, in recent years, anomaly detection
has become an important field of research focusing on this problem (Chandola
et al., 2009), (Ranshous et al., 2015).

In this paper, we present a scalable anomaly detection approach for spatio-
temporal datasets such as user activity logs of web and social networks. The
approach focuses on anomaly detection in the collective behavior of users in
such networks. Our approach introduces the following novelties that
distinguish it from the state-of-the-art.

1) The method bridges the gap between graph anomaly detection (Ranshous et
al., 2015; Akoglu et al., 2015; Aggarwal and Subbian, 2014) and spatio-
temporal data mining (Atluri et al., 2018). It uses the formalism of anomaly
detection and extends it to spatio-temporal event analysis. Here, the _spatial
component_ is a graph of interconnected entities (e.g. web pages, users or
documents), and the _temporal component_ is the activity logs of these
entities. A spatio-temporal event is a set of nodes that have an abnormal
behavior during a period of time. Importantly, the nodes may not undergo a
change at the same time. There can be a complex interaction between the nodes
during an event when a change in one node can trigger changes in others. This
complex spatio-temporal evolution is not covered in anomaly detection
literature.

2) For each event or anomaly detected using our method, the model produces a
rich set of spatio-temporal indicators rather than a single label or a
probability of being an anomaly. In this sense, it is closer to the spatio-
temporal data mining (Atluri et al., 2018), where the purpose is to extract
the anomalous events and keep as much information about them as possible for
the sake of interpretability. Providing the description of detected anomalies
to domain experts is a powerful feature of our data mining process. Our
approach provides insights on the collective behavior in web and social
networks, how the visitor activity evolves and propagates over the network. We
illustrate that in the Experiment section and reveal new insights on the
collective behavior of Wikipedia visitors.

3) We define the concept of _potential anomaly_ that introduces a prior on the
presence of an anomaly and enhances the scalability of the method. Indeed, in
many anomaly detection applications and thanks to expert knowledge, the data
can be separated into 2 parts; one part contains potential anomalies, while
the other contains non-anomalous samples. Our concept defines the separation
in a rigorous manner and allows discarding non-anomalous samples. This step
significantly reduces the amount of data to process. The concept of _potential
anomaly_ is general and can be used for other methods and applications.

Our approach can be applied to the data that has a structure depicted in Fig.
1. It consists in an attributed graph where the attributes of the nodes are
time-series signals. It leverages the network structure of the given data to
detect dynamic events or anomalies in collective behavior.

In the experiments, we use two spatio-temporal datasets. First, we build a
network of Wikipedia articles and use visitor activity of each article, i.e.
the number of visits per article per hour, as a node attribute. The static
underlying network is the Wikipedia hyperlinks network. Two pages are
connected if there is at least one hyperlink reference between them. Second,
we transform the Enron email dataset into a temporal network where nodes
correspond to email addresses of employees and edges reflect an email exchange
between a couple of employees. The temporal activity attributes of the nodes
is the number of emails sent per day by an employee.

In the results of our experiments, we demonstrate that we can extract
anomalous patterns in collective behavior of users in web and social networks.
The anomalies correspond to subgraphs containing nodes whose behavior deviates
from the norm. For the Enron email dataset, these subgraphs are groups of
employees having an increase in their email exchange during a short period of
time corresponding to major events in the corporation. For the Wikipedia data,
the subgraphs contain linked pages closely related to an event that triggered
a sudden increase of visits during a short period of time. These clusters of
anomalous nodes can then be used for more detailed investigation, as shown in
Section 5.

The strength of our approach is that it provides a comprehensive description
of detected anomalies. As a result, we are able to perform a thorough
qualitative evaluation of our results. Although, it turns into a difficulty
when a quantitative evaluation of the method is needed. It is not as
straightforward as computing the accuracy of a classification. Therefore, we
use alternative methods for validating of the results. First, we use Google
Trends as a ground truth indicator of the anomalous activity of the visitors
on the Web. We verify the detected anomalous events using the trending topics
extracted from Google Trends. In the second case, the Enron email dataset
contains ground truth, hence we use it to validate the detected anomalies.

##  2\. Related work

Anomaly detection. A recent review of the emerging field of spatio-temporal
data mining highlights the importance of anomaly detection techniques for the
dynamic networks domain (Atluri et al., 2018). Due to the complex nature of
the data, most existing approaches treat spatial and temporal components of
the data independently (Wu et al., 2010; Lu et al., 2007; Faghmous et al.,
2013). There are several application-specific approaches for anomaly detection
in video streams that use spatial and temporal information jointly (Li et al.,
2014; Kratz and Nishino, 2009). Lappas et al. (Lappas et al., 2013) presented
an approach for bursts identification in Twitter using spatial and temporal
aspects of the data, although did not use the formalism of anomaly detection.

When dealing with the data from social networks, event detection is closely
related to anomaly detection, therefore there exists a number of approaches
that use spatio-temporal features of these datasets for collective behavior
analysis. The category of Event detection in (Ranshous et al., 2015, Type 4)
covers the case where all nodes of a subgraph contribute to the creation of an
event at the same time. This is also the case in (Akoglu et al., 2015, Def.
4), where the authors defined it as a problem of the dynamic-graph anomaly
detection. In addition, these reviews as well as (Aggarwal and Subbian, 2014),
focus on dynamic graphs, where the graph structure evolves over time, whereas
in our case, the structure of the graph is static.

Our method is developed for static graphs with a dynamic evolution of node
attributes (time-series). Our definition of an anomaly is more general since
we track a heterogeneous spatio-temporal pattern that can emerge in situations
when the anomaly spread or propagate over the network. It can not be captured
by a single subgraph. Within our framework, an anomaly is described by two
components. First, _a graph pattern_ that involves multiple nodes, possibly
anomalous at different time steps. Second, _a temporal pattern_ , a set of
time-series, that reflects the anomaly evolution on each node. Tracking these
types of patterns has a number of applications (Atluri et al., 2018; Benzi et
al., 2016; Griffa et al., 2017), although they have not yet been linked to the
field of anomaly detection.

Enron email dataset. Several studies have investigated the Enron email dataset
using different approaches. While many of them focus on email contents and
perform analysis using natural language processing techniques, others focus on
the network structure and anomaly detection. In (Diesner et al., 2005), the
authors explore the email communication network of the corporation. Wang et
al. (Wang et al., 2014) adopt an anomaly detection framework to spot
remarkable events. We compare our results to this latter reference to validate
the accuracy of our detection.

Wikipedia dataset. There is a large number of studies on mining the visitor or
editor activity on Wikipedia that are aimed at getting better insights on
collective behavior and social interactions (Tinati et al., 2016), (García-
Gavilanes et al., 2017), (Kanhabua et al., 2014). However, due to a large
amount of data, the aforementioned studies are restricted to particular topics
of interest and subsets of selected Wikipedia articles. For instance, only
traumatic events such as attacks and bombings have been investigated in
(Ferron and Massa, 2011), (Ferron, 2012) based on the Wikipedia edit activity
data. Analyzing Wikipedia daily page views, Kanhabua et al. (Kanhabua et al.,
2014) investigated 5500 events from 11 categories such as aviation accidents,
earthquakes, hurricanes, or terrorist attacks. Wikipedia hourly visits on the
pages of celebrities were used to investigate the fame levels of tennis
players (Yucesoy and Barabási, 2016). These studies point out the high
interest in this dataset and the increasing need for more systematic detection
methods.

Mongiovi et al. (Mongiovi et al., 2013b; Mongiovi et al., 2013a) provided the
first investigation from an anomaly detection point of view, where the
Wikipedia page counts data are combined with the graph of hyperlinks. However,
they apply their method to a pre-selected subset of Wikipedia.

Due to the introduced concept of potential anomaly and the distributed
implementation, our method can handle the full Wikipedia network and long-term
visitor activity records.

Figure 1.  Spatio-temporal data structure combining a graph topology and time-
series. a) Graph topology. Edges highlighted in red depict the spatial
component of an anomalous spatio-temporal pattern. b) Time-series signals
residing on the vertices of the graph. Signals associated to nodes B, C and D
are correlated: an anomalous process is propagating from node D to B through
C. This is an abstract illustration of a dynamic anomaly detected by our
method.

##  3\. Method

Anomaly detection in dynamic networks generally contains two stages (Ranshous
et al., 2015). The first stage is usually responsible for feature extraction
from the domain-specific data. The second stage applies the anomaly detection
algorithm to the extracted features and reports the detected anomalies.

We build our method upon this scheme in the following way. Firstly, we add to
the Stage 1 a filtering step that keeps only potentially anomalous signals. It
allows reducing the amount of data that is processed in Stage 2 by discarding
obviously non-anomalous cases. Secondly, in Stage 2, our model contains a
learning step that enhances the interpretability of the detected anomalies. It
provides a complete and detailed spatio-temporal description of the detected
anomaly, rather than the classification _anomalous/non-anomalous_ commonly
seen in anomaly detection. This description is a group of interconnected nodes
(spatial information), where every node has a time-series attribute (temporal
information) that indicates the time when the anomaly occurred.

The learning step is inspired by the model of a memory neural network, the
Hopfield network with the Hebbian learning rule. In our model, we adapt the
learning rule to fit our spatio-temporal data structure in the following way.
An edge weight is reinforced when two neighbors are active together during the
same time slice. This particular network design shares similarities with the
Hotspot anomaly detection for graph streams (Yu et al., 2013), however, the
authors use it for feature engineering (Stage 1 of the processing), while in
our approach this update is a part of Stage 2, the learning and classification
stage.

The Hopfield network approach learns a memory network, where the nodes
correspond to the ones of the initial graph. During the learning process,
edges between the nodes will be either strengthened or removed depending on
the temporal behavior of each node. As a result of learning, nodes with
similar behavior are connected by strong links and clustered together in the
memory network. These clusters contain groups of nodes with common abnormal
behavior.

Stage 1: Feature extraction and filtering. This stage highlights anomalies and
extracts features from the raw data. We introduce a notion of _potential
anomaly_ and we filter out the nodes that are not potentially anomalous. Let
$V$ be the set of vertices of graph $G$ and $x_{i}[t]\in\mathbb{R}$ be the
value associated to vertex $v_{i}\in V$ at the time $t\in[0,T-1]$. The time-
series have a length of $T$ samples.

###### Definition 3.1 (Single vertex potential anomaly).

Given a score function $f_{i}:\mathbb{R}\to\mathbb{R}$ for each vertex $v_{i}$
and a threshold value $c_{0}\geq 0$, a vertex $v_{i}\in V$ is said to have a
potential anomaly at time $t$ when its time series value is such that
$|f_{i}(x_{i}[t])|>c_{0}$.

Note that the potential anomaly is local on the graph, i.e. it depends only on
the time-series attribute of a considered vertex. If the score function is
such that $f_{i}=f-\hat{f}(v_{i})$, for some function $f$ and $\hat{f}(v_{i})$
a summary statistics of the scores $f(v_{i}[t])$, our definition corresponds
to the definition of the anomaly in (Ranshous et al., 2015). A basic example
of a potential anomaly is the time-series values exceeding a fixed threshold
$c_{0}$. In that case, $f_{i}$ is the identity.

In this work, potential anomalies have to satisfy the following requirement. A
potentially anomalous node must have a sufficient number of bursts in their
time-series attribute. Unless this requirement holds, we discard the node. To
define a burst of activity we compute the mean $\mu_{i}$ and the standard
deviation $\sigma_{i}$ of $x_{i}$ over time. We normalize the time-series by
defining the score function
$f_{i}^{b}(x_{i}[t])=(x_{i}[t]-\mu_{i})/\sigma_{i}$. We select values that are
above $c_{0}^{b}$, the activity rate parameter ($c_{0}^{b}=5$ for Wikipedia,
$c_{0}^{b}=3$ for Enron). The _burstiness_ $b_{i}$ of a signal $x_{i}$ of a
node $i$ is

(1) $b_{i}=\sum_{t=0}^{T-1}k_{i}[t],\qquad k_{i}[t]=\begin{cases}1,&\text{if
$|f_{i}^{b}(x_{i}[t])|>c_{0}^{b}$},\\\ 0,&\text{otherwise}.\end{cases}$

The minimal number of bursts (potential anomalies) per vertex in Wikipedia is
$b_{i}=5$ while in the email dataset it is $b_{i}=2$.

The general definition of the potential anomaly allows for other score
functions, such as a moving average or ARMA filter prior to the thresholding,
a short time Fourier transform or a wavelet transform. This depends on the
dataset and should be chosen carefully to make a compromise between efficiency
and scalability.

Applying $f_{i}$ to the time-series gives us 1) features reflecting an anomaly
and 2) an initial indication of anomalous behavior. In practice, removing
nodes with no potential anomaly reduces the amount of data by an order of
magnitude without losing relevant information that is required for the anomaly
detection.

Stage 2: Hopfield network learning. The presented anomaly detection approach
is aimed at detecting groups of vertices that have a similar, abnormal
behavior. The learning stage is intended to make this coherent behavior
apparent in the memory network.

Our approach is based on the Hopfield model of artificial memory (Hopfield,
1982). It is an unsupervised learning method. To implement it, we use a
synaptic-plasticity-inspired computational model, the Hebbian learning rule
(Hebb, 2005). The main idea of this model of brain memory is that a co-
activation of two neurons results in the reinforcement of a connection
(synapse) between them. Although, contrary to the original learning rule, in
our model, we do not take causality of activations into account.

In our case, the Hopfield network has $N$ nodes. These nodes correspond to the
ones given in the dataset, after the reduction performed at Stage 1 (only the
nodes containing potential anomalies).

The learning process is as follows. We use the initial structure of the given
network. For two initially connected nodes $i$ and $j$ of the Hopfield
network, at time $t$, we update the weight of an edge $e_{ij}$ between them
according to the similarity measure ${{\rm Sim}\\{i,j,t\\}}$. Note that we
only perform this step for the nodes that are initially connected and do not
compare every possible pair of nodes. This is crucial for the tractability of
the method in cases when we deal with large networks. For each time step $t$,
the edge weight $w_{ij}$ between $i$ and $j$ is updated as follows:

(2) $\Delta w_{ij}=\begin{cases}+Sim\\{i,j\\},&\text{if $Sim\\{i,j\\}$ $>$
$\lambda$},\\\ -\alpha Sim\\{i,j\\},&\text{otherwise},\end{cases}$

where $\lambda\geq 0$ is the _sparsity parameter_. Similarly to firing
neurons, nodes expressing similar behavior have their connection weight
increased. When $\alpha>0$, the weight decreases allowing older events to be
forgotten in order to keep only the latest anomalies. In our experiments, we
set $\alpha=0$, as we want to keep all the anomalies. We also fix
$\lambda=0.5$. The value of $\lambda$ influences the sparsity of the final
network. Increasing $\lambda$ reduces the number of edges in the resulting
memory network. One should increase the value of $\lambda$, when looking for
the most outstanding anomalies and decrease it, when a higher sensitivity is
required.

Before describing the similarity function, let us introduce the activity
function $y_{i}$ at a node $v_{i}$:

(3) $y_{i}[t]=x_{i}[t]\times k_{i}[t].$

Note that the activity function can also be defined from the features
calculated at Stage 1, $y_{i}[t]=f_{i}(x_{i}[t])\times k_{i}[t]$. In the
present work, we use the definition (3).

Different similarity measures can be defined. A first example is the
following:

(4) ${\rm Sim}\\{i,j,t\\}=y_{i}[t]y_{j}[t].$

When $y_{i}$ and $y_{j}$ are normalized, this measure gives the Pearson
correlation between the nodes (if $\lambda=0$ and $\alpha=1$). The $L^{2}$
distance with a Gaussian kernel ${\rm
Sim}\\{i,j,t\\}=\exp(-|y_{i}[t]-y_{j}[t]|^{2})$ can also be a good candidate.
Another measure, restricted to the interval $[0,1]$ and that worked well in
our applications, is defined as follows: ${{\rm Sim}\\{i,j,t\\}}=0$ if
$y_{i}[t]=y_{j}[t]=0$ and otherwise,

(5) ${\rm
Sim}\\{i,j,t\\}=\frac{\min(y_{i}[t],y_{j}[t])}{\max(y_{i}[t],y_{j}[t])}\in[0,1].$

Recalling process. Starting from an initial partial memory pattern
$P_{0}\in\mathbb{R}^{N\times T}$, the recall of a learned pattern is done by
the following iterative computation:

(6) $P_{j+1}=h_{\theta}(WP_{j}),$

where $W\in\mathbb{R}^{N\times N}$ is the weight matrix of the Hopfield
network. The function $h_{\theta}:\mathbb{R}^{N\times T}\to\mathbb{R}^{N\times
T}$ is a nonlinear thresholding function (step function giving values
$\\{-1,1\\}$) that binarize the vector entries. The value $\theta$ is the
threshold (same for all entries). In our case, we build a network per month so
$W$ is associated to a particular month. For each $j\geq 0$, $P_{j}$ is a
matrix of binarized time-series where each row is associated to a node of the
network and each column corresponds to a time step of the month considered. We
stop the iteration when the iterative process has converged to a stable
solution ($\|P_{j+1}-P_{j}\|\leq\varepsilon$, where $\varepsilon$ is small,
the norm is the Frobenius norm). The initial pattern $P_{0}$ is a binary
matrix, where the rows have all values set to $-1$ (inactivity) except the
ones associated to the partial memory pattern obtained from the time-series
using the expression of $k_{i}$ defined in Eq. (1). The computation of the
iterative process is efficient as the matrices are sparse and in practice, it
converges after a reasonable number of steps.

Graph visualization and community detection. Since the connections between
nodes with similar activity are reinforced during the learning process, after
we prune low-weight edges, each Hopfield network transforms into a modular
graph structure with strongly connected clusters of nodes having a similar
activity. These groups can be either isolated connected components or
communities within the largest connected component. The analysis of the
Hopfield networks and their communities provides a good way to spot, analyze,
and interpret the anomalies in the dynamics as we will see in the next
section. To find communities, we use the Louvain method (Blondel et al., 2008)
and to represent the graph in 2D space for visualization, we use a force-
directed layout (Jacomy et al., 2014). Additional and more interactive
visualizations are available online (Miz, 2017b).

Storing memories of detected anomalies. The number of anomalies that can be
memorized by a single network is limited (McEliece et al., 1987). Indeed,
without the forgetting parameter $\alpha$, the clusters of nodes will
accumulate inside the graph, eventually overlapping and forming larger
clusters of unrelated anomalies. To avoid this but still keep track of older
events, we create snapshots of memories by slicing the time-series into time-
windows of the finite duration. The time-window size depends on the
application. For example, in the analysis of Wikipedia data, we use time-
windows of one-month length.

Complexity. The computations are tractable because 1) they are local on the
graph, i.e. weight updates depend on a node and its one-hop neighbors, 2)
weight updates are iterative, and 3) a weight update occurs only between
initially connected nodes and not among all possible combinations of nodes.
These three facts allow us to build a distributed model to speed up
computations. For this purpose, we use a graph-parallel Pregel-like
abstraction, implemented in the GraphX framework (Gonzalez et al., 2014), (Xin
et al., 2013).

Stage 1 has complexity $\mathcal{O}(NT)$ where $N$ is the number of nodes and
$T$ the number of time steps. Stage 2 has a complexity of $\mathcal{O}(ET)$,
where $E$ is the number of edges. The recall process involves a multiplication
by a sparse matrix with $2E$ non-zero entries, hence the complexity is
$\mathcal{O}(ET)$. It is important to point out that the number of nodes and
edges in the computations are not necessarily the numbers found in the
dataset: Stage 1 may discard a large number of inactive nodes (containing no
potential anomaly), Stage 2 sparsifies the time series as Eq. (3) may set to
zero a large number of values.

##  4\. Datasets

Wikipedia dataset. We use the dataset described in (Benzi, 2017). This dataset
is based on two Wikipedia SQL dumps: English language articles and user visit
counts per page per hour. The original datasets are publicly available on the
Wikimedia website (Foundation, 2016).

The Wikipedia network of pages is first constructed using the data from
article dumps that contain information about the references (edges) between
the pages (nodes)111Note that Wikipedia is continuously updating. Some links
that existed at the moment we made the dump may have been removed from current
versions of the pages. To check consistency with past versions, one can use
the dedicated search tool at http://wikipedia.ramselehof.de/wikiblame.php..
Time-series are then associated to each node (Fig. 1), corresponding to the
visits history from 02:00, 23 September 2014 to 23:00, 30 April 2015. The
time-series have a length of $T=5278$ hours.

Enron dataset. We use Enron email
dataset222https://www.kaggle.com/wcukierski/enron-email-dataset. It contains
614586 emails sent over the period from 6 January 1998 until 4 February 2004.
We remove the periods of low activity and keep the emails from 1 January 1999
until 31 July 2002 which is 1448 days of email records in total. We remove
inactive email addresses that sent less than three emails over that period. In
total, the Enron email network contains 6 600 nodes and 50 897 edges.

##  5\. Experiments and results

In this section, we present our results of the anomaly detection experiments.
We apply the proposed algorithm to the two datasets. The results obtained from
the Enron one serve mainly to validate the method so we do not describe the
analysis of the data. We dedicate more space to the detailed inspection of the
Wikipedia dataset, which is a larger and more informative dataset allowing us
to demonstrate the scalability of our method and to provide the detailed
interpretation of the results.

Figure 2. Anomaly detection in Enron email network. Red areas highlight the
month periods previously reported as anomalies (ground truth supported by the
real world events). Blue lines reflect the normalized (scale 0-100) overall
activity level in the network computed by the proposed algorithm. We can see
that the algorithm detects anomalies in all reported cases.

Enron email dataset. In order to apply our anomaly detection algorithm to this
dataset, we represent the data as a time-series graph data structure, which is
depicted in Fig. 1. The static graph is the network of email communications:
the nodes are email addresses and they are connected if they have exchanged at
least one email over the 5 years. It is an undirected, unweighted graph. Time-
series associated to the nodes are captured from the email activity; each
temporal value is the number of emails sent from the associated address during
one day. Here, the connection between email addresses is reinforced if a
similar amount of emails have been sent by both of them over the same hour.
Note that the graph and time-series design could have been more complex with
directed edges or time-series associated to the edges. However, in order to
stay as general as possible, we decided to strictly follow the steps described
in Sec. 3.

In this case, an anomaly is a sudden increase in email communications among a
group of employees of the corporation. After learning a Hopfield network for
every month, we investigate their structure. We select four months where the
results can be compared to the literature. The authors of (Wang et al., 2014)
observe four anomalous periods and relate them to the specific news reports
involving Enron. We use these events as a ground truth. These are the months
of December 1999, April, May and August 2001. For each month, we select the
largest connected component of the learned graph. We sum up the activity of
its nodes to get a single time-series representative of the group activity. We
show this normalized activity on Figure 2. We define an anomaly to be a spike
of overall activity in a cluster of email addresses that we detect after
learning. All the four curves have a larger activity during the chosen month
than in the rest of the time span. For April and May 2001, it is more than
twice the maximal activity for the rest of the months, showing the evidence of
an anomaly. December 1999 and August 2001 increases in activity have a longer
trace after the main anomaly has been detected but still, the high activity
does not spread for more than one year. Concerning the monthly components of
active nodes for the 4 chosen months, it involves 29, 25, 126, 28 nodes
respectively for December 1999, April, May and August 2001. Almost all of them
correspond to addresses of Enron employees. Except for the May event, the
activity involves less than 30 persons. In May, it involves 100 employees out
of the 158, showing an event that impacted the whole company.

The application of our method to the Enron dataset allows detecting all the
anomalies presented in the state-of-the-art literature. It reveals the days of
the peak activities, the duration of the events, and the persons involved,
which makes more detailed investigation possible in the future. Besides, our
approach can detect periodic or recurrent anomalies due to associative nature
of the Hopfield network. This feature will be demonstrated in the following
experiments on the Wikipedia data.

Wikipedia dataset. We conduct more detailed experiments on the Wikipedia web
network and use Google Trends data as a ground truth to verify the accuracy of
our findings. An anomaly, in this case, is a sudden increase in visitor
activity in a small, local part of the web network. We start by analyzing the
initial graph of Wikipedia web pages connected with hyperlinks. In this
experiment, the time-series attributes of the nodes correspond to the
viewership statistics of the associated web pages, described in Section 4.

To learn the global anomalies that occurred in the long-term dynamics of the
Wikipedia web network, we build the Hopfield network of the 7-month period.
After the learning, only 275 498 edges have strictly positive weights (4.2% of
the initial graph). We remove the disconnected nodes and preserve only the
largest connected component of the graph. The number of remaining nodes is 35
839 (31% of the initial number).

The analysis of the static underlying graphs shows that both (the initial and
learned) Wikipedia graphs have statistically heterogeneous connectivity (Fig.
3). However, the initial Wikipedia graph is dominated by large hubs that
attract most of the connections to numerous low-degree neighbors. These hubs
correspond to general topics in the Wikipedia network. They often link broad
topics such as, for instance, the “United States” page, with a large number of
hyperlinks pointing to it from highly diverse subjects. If we look at the
viewership statistics, the activity of the visitors in these large clusters is
uniform and does not expose any anomalies over time. We aim at extracting
smaller communities that correspond to localized anomalies in the dynamics of
the network. This is why we need the learned graph.

The visualizations of the initial and learned graphs using a force layout
algorithm show striking differences (Fig. 4). The initial Wikipedia graph is
dense and cluttered with a significant number of unused references, while the
learned graph reveals smaller and more separated communities. This is also
confirmed by the numerical measures such as the community size and degree
distributions of the graphs (Fig. 3, right). The number of communities and
their size change after learning. Initially, the small number of large
communities dominate the graph (blue), while after the learning (red) we see a
five times increase in the number of communities. Moreover, as a result of the
learning, the size of the communities decreases by one order of magnitude. The
modularity of the learned graph is 25% higher, strengthening the evidence of
the creation of associative structures. These measures indicate that as a
result of learning, we obtain a graph structure with small strongly connected
clusters that correspond to a summary of anomalies in the network dynamics. We
provide detailed examples of such anomalies in the following experiments.

The analysis of each community of nodes in the learned graph gives a glimpse
of the events that occurred during the 7-month period and caused the anomalous
behavior of visitors during that period of time. Each cluster is a group of
pages related to a common topic such as a championship, a tournament, an
awards ceremony, a world-level contest, an attack, an incident, or popular
festive events such as Halloween or Christmas.

Figure 3. Left. Weighted degree distribution in log-log scale for the
Wikipedia graph and Hopfield network learned over the entire 7 months time
span. Linearity in log-log scale corresponds to power-law behavior $P(k)\sim
k^{-\gamma}$. The learned graph preserves a similar scale-free behavior, but
is less connected and has fewer hubs than the initial graph. Right. Community
size distribution of the initial Wikipedia graph of hyperlinks (blue) and the
learned Hopfield network (red). The total number of communities: 32 for the
initial graph, 172 for the learned one.

Before going deeper into the clusters analysis and the corresponding anomalies
in the network dynamics, we investigate the evolution of the graph structure
over time with an emblematic example.

|
---|---
(a) Initial | (b) Learned
Figure 4. Wikipedia graph of hyperlinks (left) and learned Hopfield network
(right). Colors correspond to the detected communities. The learned graph is
much more modular than the initial one, with a larger number of smaller
communities. The layout is force-directed.

Monthly networks. As stated in Sec. 3, we split the dataset into one-month
periods. These periods are longer than the duration of an average event
attracting the attention of Wikipedia users, that usually lasts no longer than
two weeks. This means that we are going to detect multiple anomalies at once.
Monthly graphs are smaller, compared to the 7-months graph, and contain 10 000
nodes on average. However, the properties and distributions of monthly graphs
are similar to the 7-months one, described above.

Figure 5. Evolution of the National Football League 2014-2015 championship
cluster and visits on its articles. We show 30 NFL teams from the main
cluster. Top: the 7 monthly learned graphs in gray, with the NFL cluster
highlighted in red. The month is displayed on the bottom of the figure. Middle
table: visitors activity per hour on the NFL teams’ Wikipedia pages in
greyscale (the more visits, the darker). Bottom: the red and blue curves are
the total number of visits in the articles of the clusters over time
(normalized) and the Google Trends curve for the keyword ”Super Bowl”,
respectively.

To give an example of a detected event and the associated anomalous behavior
of the Wikipedia users, we discuss the cluster of the USA National Football
League championship, spotted in and extracted from the Hopfield network during
several months between 2014 and 2015 (Fig. 5).

NFL is one of the most popular sports leagues in the USA and it triggers a lot
of interest to the related articles on Wikipedia. Due to the high number of
visits on this topic we were able to localize a cluster related to the NFL on
each of the monthly graphs. Figure 5 shows the detailed information about the
NFL clusters. The top part of the figure contains the learned graphs for each
month, where the NFL cluster is highlighted in red.

The final game of the 2014 season, Super Bowl XLIX, had been played on
February 1, 2015. This explains the continuous expansion of the cluster until
February where its size reaches the maximum. The activity collapses right
after this event and the cluster disappears.

For the sake of figure interpretability, we extracted 30 NFL team pages from
the original cluster (485 pages) to show the details of the evolution in time
as a table on Fig. 5. This fraction of the nodes reflects overall dynamics in
the entire cluster. Each row describes the hourly activity of a page, while
the columns split the plot into months. The sum of visits for the selected
pages is plotted as a red line in the bottom.

The dynamics of the detected cluster reflects the real timeline of the NFL
championship. The spiking nature of the overall activity corresponds to
weekends when most of the games were played. Closer to the end of the
championship, the peaks become stronger, following the increasing interest of
fans. We see the highest splash of the activity on 1 February, when the final
game was played.

We want to emphasize that this cluster, as well as all the others, was
obtained in a completely unsupervised manner. The football teams pages were
automatically connected together in a cluster having “Super Bowl” as a common
topic. Moreover, the cluster is not formed by one Wikipedia page and its
direct neighbors, it involves many pages with distances of several hops in the
graph.

The NFL championship case is an example of a periodic (yearly) event. The
interest increases over the months until the expected final event, which
causes an anomaly in the network dynamics. Accidents and incidents are the
events of a different nature as they appear suddenly, without prior activity.
The proposed learning method allows detecting this kind of events and the
related anomalies as well. We provide examples of three accidents to
demonstrate the ability of our method to detect anomalous behavior in the
network in case of an unexpected event.

We pick three core events among 172 detected and discuss them to show the
details of our anomaly detection approach. Figure 6 shows the extracted
clusters from the learned graph (top) and the overall timeline of the
clusters’ activity (bottom). We evaluate the accuracy of the anomaly detection
using Google Trends history records.

|  |
---|---|---
|  |
(a) Germanwings 9525 crash | (b) Ferguson unrest | (c) Charlie Hebdo attack
Figure 6. Graphs and activity timelines of the 3 events that triggered
anomalies in the network dynamics. Top: Clusters of pages grouped after
learning in the Hopfield network. Bottom: A normalized sum of all visits of
the articles of each cluster over time (in red). The Google Trends curve for
the keywords ”Germanwings 9525 crash” (a), ”Ferguson unrest” (b) and ”Charlie
Hebdo attack” (c) is displayed in blue.

Charlie Hebdo shooting. 7 January 2015. This terrorist attack is an example of
an unexpected event. The cluster emerged over a period of 72 hours, following
the attack. All pages in the cluster are related to the core event.
Strikingly, a look at the title of the pages is sufficient to get a precise
summary of what the event is about. There is a sharp peak of activity on the
first day of the attack, slowly decaying over the following week.

Germanwings flight 9525 crash. 24 March 2015. This cluster not only involves
pages describing the crash or providing more information about it, but also
the pages of similar events that happened in the past. It includes, for
example, a page enumerating airlane crashes and the page of a previous crash
that happened in December 2014, the Indonesia AirAsia Flight 8501 crash. As a
result, the time activity of the event is connected to the one of the Flight
8501 crash, that is why we can see an increase in visits in December. This is
an example where our approach captures two relevant events and groups them
together in one cluster allowing to detect a secondary anomaly that is only
implicitly related to the main one.

Ferguson unrest. Second wave. November 24, 2014 – December 2, 2014. This is an
example of an event that has the official beginning and end dates. A sharp
increase in the activity at the beginning of protests highlights the main
event. This moment triggers the core cluster emergence. We also see that the
cluster becomes active once again at the end of the unrest allowing to record
the two related anomalies in the visitor activity.

Finally, in Table 1, we summarize our exploration of the clusters of the
learned graphs by providing a list of handpicked page titles inside each
cluster that refer to previous events and related subjects. The connected
events occurred outside of the 7-months period we analyze. This illustrates
the associative property of our the anomalies we detect. Firstly, pages are
grouped by events with the help of visitors activity. Secondly, the events
themselves are connected together by this activity. An anomaly is
characterized by a group of connected concepts and these groups are in turn
connected together through concepts they share. This feature makes it easy to
interpret the cause of the detected anomaly.

Google Trends Evaluation. For each of the events presented before, we have
compared the total number of visits in the clusters with Google Trends curves
reflecting anomalous search activity of internet users. There is a striking
correspondence between the detected anomalies and Google Trends, as we can see
in Fig. 5 and 6. In all 4 examples, the anomalous activity and Google Trends
curves reach their maximum at the same time and have a very similar shape. The
differences that appear during the months prior to the Super Bowl date are
explained by the fact that our ”Super Bowl” cluster contains articles about
Football teams and other topics related to the Super Bowl. Due to the
associative nature of the detected anomalies, this example has a higher
accuracy of detection than Google Trends.

As discussed previously, the periodic spikes in the visitor activity take
place during the weekends when football matches are played. We observe the
same phenomenon in the case of the Germanwings crash, where we observe a small
peak of activity in December. This peak is the result of the prior activity on
the pages related to another airplane crash that happened in December 2014.
Again, this demonstrates the richness of the obtained clusters: they describe
a group of events that caused an anomaly in visitor activity, as confirmed by
Google Trends but represent more than a single keyword since the detected
anomaly is a result of multiple real-world events.

Table 1. Examples of Wikipedia article titles contained in the clusters
associated to the events presented.

Charlie Hebdo attack | Germanwings 9525 crash | Ferguson unrest
---|---|---
Porte de Vincennes hostage crisis | Inex-Adria Aviopromet Flight 1308 | Shooting of Tamir Rice
Al-Qaeda | Pacific Southwest Airlines Flight 1771 | Shooting of Amadou Diallo
Islamic terrorism | SilkAir Flight 185 | Sean Bell Shooting Incident
Hezbollah | Suicide by pilot | Shooting of Oscar Grant
2005 London bombings | Aviation safety | 1992 Los Angeles riots
Anders Behring Breivik | Air France Flight 296 | O.J. Simpson murder case
Jihadism | Air France Flight 447 | Shooting of Trayvon Martin
2015 Baga massacre | Airbus | Attack on Reginald Denny

---
Figure 7. Recall of an event from a partial pattern (Charlie Hebdo attack).
The red vertical lines define the start of the event and its most active part,
ending 72 hours from the start. Left: full activity over time of the pages in
the cluster. Middle: pattern with 20% of nodes set inactive (top lines).
Right: the result of the recall using the Hopfield network model. In light red
are shown the difference with the original pattern (the forgotten activity).

Recalling memories. In this last experiment, our goal is to test the
hypothesis that the proposed method, as a memory, allows recalling or
recovering events from partial information. We emulate recall processes using
the Hopfield network approach, described in Section 3. We show that the
learned graph structure can recover a full event (cluster of pages and its
activations) from an incomplete input.

We create incomplete patterns for the Hopfield network by selecting randomly a
few pages contained in a chosen cluster. We built the input matrix $P_{0}$
setting to $(-1)$ (inactive state) all the time-series except for the few
pages selected. We then apply iteratively Eq. (6).

We present only one example of the recall, to demonstrate the recall ability
of the network but also to illustrate its complexity, on Fig. 7. From the
cluster associated to the Charlie Hebdo Attack and we choose a subset of the
list of articles, here $80\%$. We apply the learned graph for the month of
January when the memory was detected. After the recall, we can remark two
important facts. First, if we focus on the short time span when the event
occurs (within the red vertical lines), most of the cluster is recovered.
Second, the model forgets a part of the activity, plotted in light red,
outside of the event bounds. This missing part is made of pages that are
active outside of the time of the event, giving the evidence that they are not
directly related (or weakly related) to the event.

The results of this experiments show that our method can be used to recover
the signals related to the detected anomalies given a noisy or incomplete
input. For instance, this feature can be helpful in cases when the data
required for anomaly interpretation is destroyed by some intruders that are
interested in hiding traces after an attack on the network.

##  6\. Conclusions and future work

In this paper, we presented a new unsupervised graph algorithm that allows
detecting anomalies in large datasets with dynamic activity records. We showed
that this approach allows analyzing the root causes of detected anomalies.
Beyond the presentation of the method, we also provided new insights on
collective behavior of Wikipedia users.

This approach is promising. We noted experimentally a high robustness of the
method to the tuning of the parameters. We also plan to go deeper into the
analysis of the recalling process.

This work opens new avenues for dynamic graph-structured data analysis. For
example, the proposed approach could be used in a framework for automated
event detection, monitoring, and recording. However, to cover these use cases,
the method should be able to process streams of data as they are recorded. An
online version of the method is not straightforward and will be the object of
future work.

The artificial memory model used in the method suggests an interesting
connection between the detection of anomalies and the functioning of the
memory. This insight is more apparent in the experiments related to Wikipedia.
Events and abnormal activity in the data trigger the recording process of the
collective associative memory. The Hopfield network trained on Wikipedia
articles transforms into a set of interconnected concepts or topics that have
interested people at some point in the past. It resembles an artificial
collective memory. This is fascinating and deserves further research in this
direction related to social sciences.

##  7\. Tools, implementation, code and online visualizations

All learned Wikipedia graphs (overall September-April, monthly activity, and
localized events) are available online (Miz, 2017b) to foster further
exploration and analysis. For graph visualization we used the open source
software package Gephi (Bastian et al., 2009) and layout ForceAtlas2 (Jacomy
et al., 2014). We used Apache Spark GraphX (Xin et al., 2013), (Gonzalez et
al., 2014) for graph learning implementation and graph analysis. The presented
results can be reproduced using the code, written in Scala and Python (Miz,
2017a), (Miz, 2018). Both datasets are available on Zenodo (Kirell et al.,
2017), (Miz et al., 2018).

###### Acknowledgements.

We would like to thank Michaël Defferrard and Andreas Loukas for fruitful
discussions and useful suggestions. Also, we would like to thank anonymous
reviewers for their constructive criticism and recommendations that helped
improve this paper. The research leading to these results has received funding
from the European Union’s H2020 Framework Programme (H2020-MSCA-ITN-2014)
under grant agreement no 642685 MacSeNet.

## References

  * (1)
  * Aggarwal and Subbian (2014) Charu Aggarwal and Karthik Subbian. 2014.  Evolutionary network analysis: A survey.  ACM Computing Surveys (CSUR) 47, 1 (2014), 10\.
  * Akoglu et al. (2015) Leman Akoglu, Hanghang Tong, and Danai Koutra. 2015\.  Graph based anomaly detection and description: a survey.  Data mining and knowledge discovery 29, 3 (2015), 626–688.
  * Atluri et al. (2018) Gowtham Atluri, Anuj Karpatne, and Vipin Kumar. 2018\.  Spatio-temporal data mining: A survey of problems and methods.  ACM Computing Surveys (CSUR) 51, 4 (2018), 83\.
  * Bastian et al. (2009) Mathieu Bastian, Sebastien Heymann, Mathieu Jacomy, et al. 2009\.  Gephi: an open source software for exploring and manipulating networks.  Icwsm 8 (2009), 361–362.
  * Benzi et al. (2016) Kirell Benzi, Benjamin Ricaud, and Pierre Vandergheynst. 2016\.  Principal Patterns on Graphs: Discovering Coherent Structures in Datasets.  IEEE Trans. Signal and Information Processing over Networks 2, 2 (2016), 160–173.
  * Benzi (2017) Kirell Maël Benzi. 2017\.  From recommender systems to spatio-temporal dynamics with network science.  EPFL, Chapter 5, 97–98.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast unfolding of communities in large networks.  Journal of statistical mechanics: theory and experiment 2008, 10 (2008), P10008.
  * Chandola et al. (2009) Varun Chandola, Arindam Banerjee, and Vipin Kumar. 2009\.  Anomaly detection: A survey.  ACM computing surveys (CSUR) 41, 3 (2009), 15\.
  * Diesner et al. (2005) Jana Diesner, Terrill L Frantz, and Kathleen M Carley. 2005\.  Communication networks from the Enron email corpus “It’s always about the people. Enron is no different”.  Computational & Mathematical Organization Theory 11, 3 (2005), 201–228.
  * Faghmous et al. (2013) James H Faghmous, Muhammed Uluyol, Luke Styles, Matthew Le, Varun Mithal, Shyam Boriah, and Vipin Kumar. 2013.  Multiple Hypothesis Object Tracking For Unsupervised Self-Learning: An Ocean Eddy Tracking Application.. In AAAI.
  * Ferron (2012) Michela Ferron. 2012\.  Collective memories in Wikipedia.  Ph.D. Dissertation. University of Trento.
  * Ferron and Massa (2011) Michela Ferron and Paolo Massa. 2011.  Studying collective memories in Wikipedia.  Journal of Social Theory 3, 4 (2011), 449–466.
  * Foundation (2016) Wikimedia Foundation. 2016\.  Wikimedia Downloads: Database tables as sql.gz and content as XML files.  (May 2016).  https://dumps.wikimedia.org/other/ Accessed: 2016-May-16.
  * García-Gavilanes et al. (2017) Ruth García-Gavilanes, Anders Mollgaard, Milena Tsvetkova, and Taha Yasseri. 2017.  The memory remains: Understanding collective memory in the digital age.  Science Advances 3, 4 (2017), e1602368.
  * Gonzalez et al. (2014) Joseph E Gonzalez, Reynold S Xin, Ankur Dave, Daniel Crankshaw, Michael J Franklin, and Ion Stoica. 2014.  GraphX: Graph Processing in a Distributed Dataflow Framework.. In OSDI, Vol. 14. 599–613.
  * Griffa et al. (2017) Alessandra Griffa, Benjamin Ricaud, Kirell Benzi, Xavier Bresson, Alessandro Daducci, Pierre Vandergheynst, Jean-Philippe Thiran, and Patric Hagmann. 2017\.  Transient networks of spatio-temporal connectivity map communication pathways in brain functional systems.  NeuroImage 155 (2017), 490–502.
  * Hebb (2005) Donald Olding Hebb. 2005\.  The organization of behavior: A neuropsychological theory.  Psychology Press.
  * Hopfield (1982) John J Hopfield. 1982\.  Neural networks and physical systems with emergent collective computational abilities.  Proceedings of the national academy of sciences 79, 8 (1982), 2554–2558.
  * Jacomy et al. (2014) Mathieu Jacomy, Tommaso Venturini, Sebastien Heymann, and Mathieu Bastian. 2014.  ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software.  PloS one 9, 6 (2014), e98679.
  * Kanhabua et al. (2014) Nattiya Kanhabua, Tu Ngoc Nguyen, and Claudia Niederée. 2014\.  What triggers human remembering of events? A large-scale analysis of catalysts for collective memory in Wikipedia. In Digital Libraries (JCDL), 2014 IEEE/ACM Joint Conference on. IEEE, 341–350.
  * Kirell et al. (2017) Benzi Kirell, Miz Volodymyr, Ricaud Benjamin, and Vandergheynst Pierre. 2017.  Wikipedia time-series graph.  (Sept. 2017).  https://doi.org/10.5281/zenodo.886484
  * Kratz and Nishino (2009) Louis Kratz and Ko Nishino. 2009.  Anomaly detection in extremely crowded scenes using spatio-temporal motion pattern models.  (2009).
  * Lappas et al. (2013) Theodoros Lappas, Marcos R Vieira, Dimitrios Gunopulos, and Vassilis J Tsotras. 2013.  STEM: A spatio-temporal miner for bursty activity. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. ACM, 1021–1024.
  * Li et al. (2014) Miao Li, Shuying Zang, Bing Zhang, Shanshan Li, and Changshan Wu. 2014.  A review of remote sensing image classification techniques: The role of spatio-contextual information.  European Journal of Remote Sensing 47, 1 (2014), 389–411.
  * Lu et al. (2007) Chang-Tien Lu, Yufeng Kou, Jiang Zhao, and Li Chen. 2007\.  Detecting and tracking regional outliers in meteorological data.  Information Sciences 177, 7 (2007), 1609–1632.
  * McEliece et al. (1987) ROBERTJ McEliece, EDWARDC Posner, EUGENER Rodemich, and SANTOSHS Venkatesh. 1987.  The capacity of the Hopfield associative memory.  IEEE transactions on Information Theory 33, 4 (1987), 461–482.
  * Miz (2017a) V. Miz. 2017a.  Wikipedia graph mining. GraphX implementation.  https://github.com/mizvol/WikiBrain. (2017).
  * Miz (2017b) V. Miz. 2017b.  Wikipedia graph mining. Visualization.  (2017).  https://goo.gl/Xgb7QG
  * Miz (2018) V. Miz. 2018.  Anomaly Detection in the Enron Email Graph. GraphX Implementation.  https://github.com/mizvol/enron-email-network-analysis. (2018).
  * Miz et al. (2018) Volodymyr Miz, Benjamin Ricaud, and Pierre Vandergheynst. 2018\.  Enron Email Time-Series Network.  (Aug. 2018).  https://doi.org/10.5281/zenodo.1342353
  * Mongiovi et al. (2013b) Misael Mongiovi, Petko Bogdanov, Razvan Ranca, Evangelos E Papalexakis, Christos Faloutsos, and Ambuj K Singh. 2013b.  Netspot: Spotting significant anomalous regions on dynamic networks. In Proceedings of the 2013 SIAM International Conference on Data Mining. SIAM, 28–36.
  * Mongiovi et al. (2013a) Misael Mongiovi, Petko Bogdanov, and Ambuj K Singh. 2013a.  Mining evolving network processes. In Data Mining (ICDM), 2013 IEEE 13th International Conference on. IEEE, 537–546.
  * Ranshous et al. (2015) Stephen Ranshous, Shitian Shen, Danai Koutra, Steve Harenberg, Christos Faloutsos, and Nagiza F Samatova. 2015.  Anomaly detection in dynamic networks: a survey.  Wiley Interdisciplinary Reviews: Computational Statistics 7, 3 (2015), 223–247.
  * Tinati et al. (2016) Ramine Tinati, Markus Luczak-Roesch, and Wendy Hall. 2016\.  Finding Structure in Wikipedia Edit Activity: An Information Cascade Approach. In Proceedings of the 25th International Conference Companion on World Wide Web. International World Wide Web Conferences Steering Committee, 1007–1012.
  * Wang et al. (2014) Heng Wang, Minh Tang, Youngser Park, and Carey E Priebe. 2014\.  Locality statistics for anomaly detection in time series of graphs.  IEEE Transactions on Signal Processing 62, 3 (2014), 703–717.
  * Wu et al. (2010) Elizabeth Wu, Wei Liu, and Sanjay Chawla. 2010.  Spatio-temporal outlier detection in precipitation data.  In Knowledge discovery from sensor data. Springer, 115–133.
  * Xin et al. (2013) Reynold S Xin, Joseph E Gonzalez, Michael J Franklin, and Ion Stoica. 2013.  Graphx: A resilient distributed graph system on spark. In First International Workshop on Graph Data Management Experiences and Systems. ACM, 2.
  * Yu et al. (2013) Weiren Yu, Charu C Aggarwal, Shuai Ma, and Haixun Wang. 2013\.  On anomalous hotspot discovery in graph streams. In Data Mining (ICDM), 2013 IEEE 13th International Conference on. IEEE, 1271–1276.
  * Yucesoy and Barabási (2016) Burcu Yucesoy and Albert-László Barabási. 2016\.  Untangling performance from success.  EPJ Data Science 5, 1 (2016), 17.


chamber along the $z$ direction. The resultant Čerenkov radiation envelope
projected onto the mirror surfaces in the x-y plane at 7 GeV/c is shown in
Fig. 6.2b. Note that the Čerenkov angle $\theta_{C}$ at 7 GeV/c is 2.84∘, so
the Čerenkov radiation distribution is taller and wider than of the charged
particles which generate it. Most of the photons are projected in a 90
cm$\times$80 cm region in the $x$-$y$ plane; the four black squared brackets
indicate the approximate mirror boundaries. Thus, this leaves at least 5 cm
clearance along the mirror edges for the mirror mounting scheme onto the
detector. Fig. 6.2c shows the distribution of reflected photons which are then
focused onto the active region of the PMTs, which is indicated as the inner
circle in Fig. 6.3. Note that PMT efficiencies are switched off in the
simulation. Thus, photons which are missed due to the PMT inefficiency are not
included in this plot, only those due to the imperfect optics. Fig. 6.2d shows
the reflected photons which are not focused onto the active region of the
PMTs. From the plotted distribution, the mis-focused photons are mainly
distributed at the interleaved mirror corners near the detector center. This
will lead to a localized region of lower efficiency near the center.

###  6.4 PMT Optimization

(a) PMT #1 $x$-$y$ Focused Spot Size (b) PMT #2 $x$-$y$ Focused Spot Size

(c) PMT #3 $x$-$y$ Focused Spot Size (d) PMT #4 $x$-$y$ Focused Spot Size

Figure 6.3: The $x$-$y$ plane projection of the photon hit position at the PMT
cathode plane for 7 GeV/c $\pi^{+}$. The inner circle indicates the PMT active
area which has radius of 6cm; the outer circle gives the boundary of the
quartz window which has radius of 8cm. Notice that the $x$ axis is vertical
and $y$ axis is horizontal in HGC coordinate. However, the mean and RMS x, y
values refer to the plotting program convention of x = horizontal (HGC $y$
axis) and y = vertical (HGC $x$ axis). (Original In Color).

(a) PMT #1 x-z Photon Path Distribution (b) PMT #2 x-z Photon Path
Distribution

(c) PMT #3 x-z Photon Path Distribution (d) PMT #4 x-z Photon Path
Distribution

Figure 6.4: The reconstructed photon path through 7 tracking planes in the x-z
plane. The black line indicates the position of the cathode plane. (Original
In Color).

Efficiencies $\eta_{\gamma}$ and $\eta_{pe}$ are defined in Equation (6.1) and
(6.2). The quantities $\eta_{\gamma}$ and $\eta_{pe}$ are very closely
related: $\eta_{\gamma}$ is for the PMT-off mode and $\eta_{pe}$ is for the
PMT-on mode. In the PMT-on mode, focused photons have a certain probability to
be converted into photo electrons, and this probability is dictated by the
various of efficiencies of the PMT assembly. The simulation takes into account
efficiencies such as the quartz window and adaptor transmissivity, reflection
at the front face of the quartz window and PMT quantum and positional
efficiency. For PMT-on mode, a $\pi^{+}$ at 7 GeV/c central momentum has
$\eta_{pe}$=15.78%. In the PMT-off mode, the PMT assembly efficiencies are
assumed to be 100%, which means all photons are focused onto the active area
of the PMT are converted into photo electrons, where the missing photons are
due to the imperfect optics. For PMT-off mode, $\pi^{+}$ at 7 GeV/c central
momentum has $\eta_{\gamma}$=96.8%. The PMT optimization studies in this
chapter were using the PMT-off mode.

Fig. 6.3 shows the $x$-$y$ projection of the photon hits at the PMT cathode
plane. The inner black circle indicates the boundary of the PMT active area
(12 cm in diameter); the outer black circle is the boundary of the quartz
window. From the plotted distribution, most of the photons are focused onto
the center of the PMT active area, and form a donut shaped spot. The missing
photons are distributed in the large purple tail which extends outside of the
PMT active region. To maximize the number of detected photons, ideally one
needs to adjust the mirror angle to bring the purple tail into the PMT active
region without losing too much light from the donut spot. Note also that at 3
GeV/c the donut shaped spot will be more compact, due to the smaller Čerenkov
cone angle.

Fig. 6.4 shows the reconstructed Čerenkov photon trajectories in the $x$-$z$
plane using the position information from the 7 tracking planes. The black
line is the cathode plane. The tracking planes are tilted by 42∘ with respect
to the x-axis. From the graphs, we can conclude that the PMT optical
performance is insensitive to small changes in the PMT tilt angle (1∘ or 2∘),
and most of the photons pass through the cathode plane in the compacted
central region. This is the justification for all PMTs to have the same tilt
angle, but the mirrors have the different tilt angles with respect to the $x$
axis.

Fig. 6.5 shows the Root Mean Square (RMS) area of the spot size at each
tracking plane for each PMT. The RMS area is computed using the RMS x and y
values inside of the PMT active region as shown in Fig. 6.3. Since the focused
spots are similar to elliptical shapes, therefore the area can be calculated
as

$\textrm{RMS Area}=\frac{\textrm{RMS y}}{\sin 42^{\circ}}\times\textrm{RMS
x}\times\pi\,,$ (6.4)

where the first term is corrected for the PMT tilt angle. The RMS x and RMS y
in Equation (6.4) correspond to the RMS values for the x and y axes on the
plot, not according to the HGC coordinate. A smaller RMS area would suggest
the photons are more compactly distributed on the plane, thus easier to focus
onto the active area of the PMT.

The PMT cathode plane is labeled #50 among all tracking planes. Planes #53,
#52, #51 are in front and #49, #48, #47 are behind the cathode plane, planes
are separated by 2 cm along the $z$ axis. Fig. 6.5b shows that PMTs #3 and #4
have the smallest RMS spot size at plane #50. However, PMTs #1 and #2 have the
smallest RMS spot size between plane #50 and #49; this suggests that PMT #1
and #2 are 1 cm too close to the mirror. This small imperfection is due to the
recent angle change for PMT #1 and #2 from 45∘ to 42∘ for the manufacture
convenience, since Fig. 6.4 shows the small PMT angle change results in little
difference in performance. Further efforts will be committed to re-optimize
the optics arrangement as well as other new studies following the release of
on updated SHMS particle distribution from Hall C.

(a) PMT 1 & 2

(b) PMT 3 & 4

Figure 6.5: Focused spot root mean square size vs. plane number. (Original In
Color).

###  6.5 Projected Performance

The particle identification efficiency, $\eta_{particle}$, is defined in
Equation (6.3); it describes the overall performance of the detector. It is
only studied using the PMT-on mode. The particle identification efficiency was
studied with 3 and 7 GeV/c central momentum $\pi^{+}$, $K^{+}$ and proton.
Based on the previous HMS experiments, the $\pi^{+}$-$K$-proton ratio is
estimated to be 5:2:2 at 3 GeV and 5:3:2 at 7 GeV momentum in the simulation.
The $\pi^{+}$ sample size for 3 and 7 GeV simulations were 250000. The
simulated photo-electrons spectra were analyzed in the same manner that actual
HGC data will be analyzed in SHMS experiments. The particle identification
efficiency is highly dependent upon the signal threshold, which is applied in
the analysis to reduce the noise signal. The optimization of the threshold
signal level is one of the major goals of our study.

(a) 3 GeV/c

(b) 7 GeV/c

Figure 6.6: The $\pi^{+}$ Čerenkov photon production and detected photon
electron distribution at 3 and 7 GeV/c central momentum. The red curve is
generated Čerenkov photons per event distribution, while the blue curve is
photo-electrons emitted by the PMT photo-cathode per event distribution.
(Original In Color).

####  6.5.1 Čerenkov Photon Detection for $\pi^{+}$ Events

Fig. 6.6 shows the total generated Čerenkov photons and photo-electrons per
event by all four PMTs at 3 and 7 GeV/c central momentum $\pi^{+}$. The total
generated photon curve for 3 GeV/c $\pi^{+}$ has wide double peaks, which is
due to the momentum difference of the particles entering different parts the
detectors along the x direction. For example, the particles travel through
$+x$ mirror (#1 and #2) regions have higher momentum than those travel through
$-x$ mirror (#3 and #4) regions; the particles with higher central momentum
can generate more Čerenkov photons. The range for the SHMS momentum acceptance
is created by the magnetic focusing elements (both dipole and quadrupole) in
front of the detector stack, and it generates a larger range in velocities for
lower central momentum $\pi^{+}$, which results a wider total photon
distribution at 3 GeV/c than at 7 GeV/c central momentum. The total Čerenkov
photon production for 7 GeV/c $\pi^{+}$ has a Gaussian distribution with the
mean 291.8 and standard deviation 31.6. The photo-electron (blue)
distributions have sharp peaks, and the mean are 16.0 and 46.8 for 3 GeV/c and
7 GeV/c $\pi^{+}$. This concludes that at same refractive index (pressure) the
particle with higher momentum generates more Čerenkov photon. The photo-
electron distribution is summed over all four PMTs. This is easy to do in the
simulation. However, in the actual experimental analysis, care will have to be
taken to properly match the PMT signal spectra, so they can be correctly added
together.

####  6.5.2 Signal Threshold

Positrons ($e^{+}$) have a Čerenkov refractive index threshold that is lower
than the detector refractive index, so they are capable of generating Čerenkov
photons in the HGC detector. The detected $e^{+}$ events can be rejected by
other particle identification detectors like the lead-glass detector or the
Noble Gas Čerenkov detector at high central momenta. When $K^{+}$ or protons
pass through the HGC detector, they can knock electrons free from the C4F8O
gas particles; these secondary $e^{-}s$ at sufficiently high momenta can
generate Čerenkov radiation. This process is known as delta radiation and it
is one of the primary sources for background signals in the HGC. The delta
radiation can also be modeled by the Geant4 simulation. An effective way to
reduce this background is to introduce a signal threshold, however, the
threshold should not exclude too many real $\pi^{+}$ events.

Fig. 6.7 shows the number of events vs. the detected number of photo-electrons
per event, and Fig. 6.8 shows the particle detection efficiency vs. the number
of photo-electrons. Results are shown for both 3 and 7 GeV/c central momenta
for $\pi^{+}$, $K^{+}$ and proton. In Fig. 6.7 it can be seen that the
detected pion events generate many more photo-electrons (on average) than
delta radiation from $K^{+}$ and proton at 7 GeV/c momentum. However, the
generated photo-electron difference is much smaller at 3 GeV/c. Thus,
different signal thresholds were used for the different particle central
momenta to ensure $\eta_{particle}>$ 98% for $\pi^{+}$. At 3 GeV/c, the
analysis threshold was set for 2 photo-electrons, giving $\eta_{particle}$ =
98.4%; at 7 GeV/c, the threshold is set for 10 photo-electrons where
$\eta_{particle}$ = 98.4%. 1.1% and 0.88% of $K^{+}$ delta radiation events at
3 and 7 GeV/c central momentum pass the applied threshold. However, these
$K^{+}$ events will have high probability to be identified by the Aerogel
Čerenkov Detector and so we are confident that our goal of 1000:1
$\pi^{+}$/$K^{+}$ separation ratio needed for SHMS experiments will ultimately
be achieved.

(a) 3 GeV/c

(b) 7 GeV/c

Figure 6.7: Particle events vs. the detected photo-electron per event plots at
3 and 7 GeV/c central momentum. $K^{+}$ distribution is in blue, proton
distribution is in magenta, $\pi^{+}$ distribution is shaded in red and total
distribution is shaded in cyan. $K^{+}$ and proton events are plotted against
the left y axis in black; $\pi^{+}$ and total events are plotted against the
right y axis in red. Note that the $\pi^{+}$ and total events distribution are
overlapping. The red solid lines indicate the signal threshold. (Original In
Color).

(a) 3 GeV/c

(b) 7 GeV/c

Figure 6.8: Particle detection efficiency vs. the threshold photo-electron
plot at 3 and 7 GeV/c. The red solid lines indicate the signal threshold. Note
the different x axis scales for plot (a) and (b). (Original In Color).

###  6.6 Oblate Ellipsoid Versus Spherical Mirrors

All simulation results presented in this chapter are with the oblate mirrors.
The performances for both oblate and spherical mirrors were studied and
compared. Fortunately, both mirrors have the same photon detection efficiency
at PMT-on mode $\eta_{pe}$=15.78%, however, the pion identification efficiency
for PMT-on mode for spherical mirrors is $\eta_{particle}=98.90$%, which is
0.5% higher than the oblate mirror efficiencies at 7 GeV/c momentum with the
threshold set for 10 photo-electrons. This is due to the better focusing
ability of spherical mirror, it is able to include larger area of the purple
tail into the PMT active area, see Fig. 6.3.

###  6.7 Remarks and Outlook

The Hall C collaboration has recently decided to shift the super-conducting
dipole towards the $-x$ direction by 5 cm after some further optimization of
the SHMS optics. Based on our preliminary simulation results using the new
particle distribution corresponding to the changed SHMS optics, the detector
and mirror positions need to be re-optimized to accommodate the new Čerenkov
radiation envelope. Since the PMT positions and angles have been fixed by the
finalized detector vessel construction drawings, all adjustments have to be
made on the mirrors. Further effort is needed to optimize the detector
performance for the new beam and Čerenkov envelope. We expect only small
adjustments will be needed.

In principle, the current estimated photon detection efficiency could be
lowered by as much as 30%, due to reflection losses at each of the optical
interfaces between the quartz window and the PMT. The current simulation model
counts the survival photons after the quartz window, which does not include
the photon loss from the quartz window to the quartz adaptor and from the
quartz adaptor to the PMT cathode. As it was explained in the Section 3.5,
silica optical gel will be used between the quartz window and the quartz
adaptor; RTV compound will be used to make a UV transparent cookie between
quartz adaptor and the PMT head. These precautions will hopefully reduce the
photon loss to a minimum. The Čerenkov photon loss rate will be determined
experimentally with our cosmic ray measurement setup and then implemented in
the simulation model.

##  Chapter 7 Summary and Future Remarks

We are constructing a Heavy Gas Čerenkov Detector for the Super High Momentum
Spectrometer as part of the Hall C 12 GeV upgrade project at Jefferson Lab.
The purpose of the HGC detector is to provide reliable $\pi/K$ separation
between 3-11 GeV/c central momenta. The detector pressure is 0.95 atm between
3-7 GeV/c, and gradually reducing at higher momenta. The HGC consists of four
sets of curved mirrors and PMTs, where each mirror focuses the Čerenkov
photons onto the active area of the corresponding PMT. The detector is
designed to be a vacuum vessel which can with stand $10^{-6}$ atm pressure.

The HGC mirrors have dimension of 60 cm $\times$ 55 cm with radius of
curvature of 110 cm. Based on our detailed mirror quality study, we conclude
that all manufactured HGC mirrors have oblate elliptical curvature: $\kappa>$
0, and their fitted radius of curvature are slightly larger than desired: R$>$
110 cm. We were able to select four best mirrors with 0 $<\kappa<$ 1 and
radius of curvature around 112 cm, where $\delta\kappa$=$\pm$0.15 and $\delta
R$=$\pm$2 cm. The Geant4 simulation results suggest the difference in terms of
optical performance between oblate and spherical mirrors is acceptably small.

The Čerenkov radiation generated when a high momentum charged particle passes
through the HGC detector has wavelength in the upper visible to ultraviolet
region. Thus, the mirror reflecting surfaces need to be coated with aluminum
grain to reflect the UV photons. HGC Mirrors #2 and #8 were sent to Evaporated
Coating Inc. (ECI) for a test aluminization. Based upon our reflectivity
results obtained from the permanent reflectivity measurement setup at
Jefferson Lab, we confirm that our reflectivity results are consistent within
2% with the ECI witness sample reflectivity results between 200-400 nm. We
believe the ECI aluminization quality meets our performance specifications and
is sufficient for the aluminization of mirrors to be actually used in the HGC.
Six more HGC mirrors were aluminized by ECI and have been recently sent to
Jefferson Lab, further reflectivity tests will be carried out in Dec, 2012.

A Geant4 Monte-Carlo simulation was constructed according to the HGC design,
to study the detector performances such as photon detection and particle
identification efficiency. At 7 GeV/c, the HGC optics focuses 96.9% of the
generated Čerenkov photons onto the PMTs active area. At 3 and 7 GeV/c central
momenta, the signal threshold is set for two and ten photon electrons, and a
pion identification efficiency $\eta>$ 98% is predicted. The Hall C
collabration has recently made further optimization on the SHMS vertical
bending dipole elevation, so some modifications are required to our Geant4
model. The optical alignment will be re-optimized according to the new
changes, and detector performances will be fine tuned.

The main vessel construction contract has been awarded to HAI Precision
Waterjets Inc. [47], their estimated delivery time is November 2012. The HGC
construction group will have a six month to assemble the detector before it is
shipped to Jefferson Lab in the summer of 2013. We are confident that the HGC
detector will function successfully along other particle identification
detectors of Hall C for the next 10-20 years.

## References

  * [1]
  * [2] Jefferson Lab website: www.jlab.org
  * [3] M. Fowler. _CAD Model Rendering_ , Hall C Document 667-v1, 2010.
  * [4] H. Fenker. _Overview of the SHMS System_ , Hall C Document 554-v1, 2009.
  * [5] D. Gaskell, G. Huber. _Measurement of the Charged Pion Form Factor to High Q2_ , Hall C Experiment E12-06-101.
  * [6] D. Dutta, R. Ent. _The Search for Color Transparency at 12 GeV_ , Hall C Experiment E12-06-107.
  * [7] C. Keppel, S. Malace, M. I. Niculescu. _Precision measurements of the $F_{2}$ structure function at large x in the resonance region and beyond_, Hall C Experiment E12-10-002.
  * [8] B. Anderson, J. Arrington, S. Kowalski, R. Madey, B. Plaster, A. Semenov. _The Neutron Electric Form Factor at $Q^{2}$ up to 7 (GeV/c)2 from the Reaction ${}^{2}H\,(\vec{e},\,e^{\prime}\vec{n})\,^{1}H$ via Recoil Polarimetry_, Hall C Experiment E12-11-009.
  * [9] E. Brash, C. Perdrisat. _GEp/GMp with an 11 GeV electron beam_ , Hall C Proposal C12-11-009.
  * [10] SHMS engineering drawings from Bert Metzger<EMAIL_ADDRESS>
  * [11] Urzhumov, Yaroslav A. _Sub-wavelength Electromagnetic Phenomena in Plasmonic and Polaritonic Nanostructures: from Optical Magnetism to Super-resolution_ , The University of Texas at Austin Press, 2007.
  * [12] L. Sichello, G, Huber. _Heavy Gas Cerenkov Optimization_ , Hall C Document 681-v1, 2010.
  * [13] Jefferson Lab Hall C Website: www.jlab.org/Hall-C
  * [14] Jackson, John D. _Classical Electrodynamics_ , 3rd ed. John Wiley & Sons, Inc. 1998.
  * [15] D. J. Griffiths. _Introduction to Electrodynamics_ , 3rd ed. Prentice Hall, Inc. 1999.
  * [16] Sinclair Glass, Inc. 105 N Wabash Ave, P.O. Box 527, Hartford City, IN 47348-2366. Website: http://www.sinclairglass.com
  * [17] Plots from Garth Huber<EMAIL_ADDRESS>
  * [18] Detector blueprints made by Chris Ng, University of Alberta, Center for Research in Particle Physics<EMAIL_ADDRESS>  * [19] M. Artuso, et. al, _Performance of a C 4F8O gas radiator ring imaging Cherenkov detector using multi-anode photomuliplier tubes_, Nuclear Instruments and Methods in Physics Research A 588 (2006) 373-387.
  * [20] HAMAMATSU Photonics K.K. [IR] 325-6, Sunayama-cho, Naka-ku, Hamamatsu City, Shizuoka Pref., 430-8587, Japan. Website: www.hamamatsu.com
  * [21] Corning Incorporated, One Riverfront Plaza, Corning, NY 14831 USA. Website: www.corning.com/index.aspx
  * [22] Hardin Optical Company, PO Box 219, Bandon, OR 97411. Website: www.hardinoptical.com
  * [23] Momentive, 180 East Broad Street, Columbus, OH 43215. Website: www.momentive.com/home.aspx
  * [24] E. Hecht, _Optics, Fourth Edition_. Pearson Higher Education. 18 March 2003.
  * [25] Jochen Volmer, _The Pion Charged Form Factor via Pion Electroproduction on the Proton_ , PhD Thesis, 2000, Vrijie Universiteit.
  * [26] https://twiki.cern.ch/twiki/bin/view/LHCb/C4F10
  * [27] G. Huber, W. Li, L. Sichello, _Progress Report on Heavy Gas C̆erenkov Detector Construction_ , Jan 13, 2011, HallC-doc-686-v1.
  * [28] T.Skwarnicki, et, al, _Beam Test of a C 4F8O MAPMT RICH Prototype_, Nuclear Instruments and Method in Phyiscs Resreach, A 553 (2005) 339-344.
  * [29] Detector drawing from Lee Sichello, University of Regina Undergraduate Research Assistant<EMAIL_ADDRESS>
  * [30] Dumur Industries, No.2 Ramm Avenue, Box 338, Station Main, White City, SK, S4L 5B1. Website: http://www.dumurindustries.com
  * [31] FARO Swiss Holding GmbH, Wiesengasse 20, 8222 Beringen, Switzerland. Website: http://www.faro.com
  * [32] Telescope Optics Website: http://www.telescope-optics.net/conics_and_aberrations.htm.
  * [33] Evaporated Coatings, Inc. 2365 Maryland Road, Willow Grove, PA 19090. Website: http://www.evaporatedcoatings.com
  * [34] W. Li, G. Huber, M. Denissenya, D. Gervais, L. Sichello, K. Wolbaum, _Mirror Testing Result_ , Hall C Document 716-v1, 2011.
  * [35] GIMP (GNU Image Manipulation Program): an image retouching and editing tool. http://www.gimp.org
  * [36] International Radiation Detectors, Inc. Opto Diode Corp. 750 Mitchel Road, Newbury Park, CA 91320. Website: www.ird-inc.com
  * [37] CVI Melles Griot - Albuquerque, 200 Dorado Place SE, Albuquerque, NM 87123, USA. Website: http://www.cvimellesgriot.com
  * [38] McPherson, Inc. - 7A Stuart Road, Chelmsford, MA 01824 USA
  * [39] http://www.ird-inc.com/text/SXUV%20RESPONSIVITY%20MASTER.txt
  * [40] SR530 Lock-in Amplifier User Manual.
Website: mrl.illinois.edu/sites/default/files/pdfs/SR530m.pdf

  * [41] http://www.emcgrath.com/catalog/lab/instruments.html
  * [42] CAD Drawing provided by Chris Gould<EMAIL_ADDRESS>
  * [43] S. Agostinelli, et. al, _Geant4 - a simulation toolkit_ , Nuclear Instruments and Methods in Physics Research, A 506 (2003), 250-303.
  * [44] J. Allison, et. al, _Geant4 developments and applications_ , IEEE Transactions on Nuclear Science, 53 No. 1 (2006), 270-278.
  * [45] Mark Jones, Jefferson Lab Hall C<EMAIL_ADDRESS>  * [46] Hamamatsu Catalog, http://sales.hamamatsu.com/en/products/electron-tube-division/detectors/photomultiplier-modules/part-h6528.php
  * [47] HAI Precision Waterjets Inc. 160 Stanley Street, Trenton, ON, Canada, K8V 4W1.

##  Appendix A Reflectivity Data

###  A.1 AXUV-100G Detector Response Curve

Figure A.1: IRD AXUV-100G photo-diode detector response curve [39].

The graph above shows the signal response curve for the IRD AXUV-100G detector
between 100-800nm. The numerical data are provided by the IRD company.

###  A.2 Typical Melles Griots DUV Mirror Reflectivity Curve

Figure A.2: Melles Griots DUV flipper mirror Theo critical reflectivity curve
provided by the manufacturer [37].

The graph above shows the typical Melles Griots DUV mirror reflectivity
between 185-250nm wavelength.

###  A.3 ECI Testing Sample Reflectivity Measurements

The ECI data sheets are attached in the following three pages, the actual
placement of the witness samples with respect to the real mirror are shown in
Fig. 5.4a. The first page of the data sheet contains the theoretical
reflectivity performance; 2nd and 3rd page record the reflectivity measurement
of the witness samples.

Figure A.3: ECI theoretical reflectivity curve [33]. Figure A.4: ECI witness
sample reflectivity measurements between 200-600 nm [33]. (Original In Color).
Figure A.5: ECI witness sample reflectivity measurements between 200-250 nm
[33]. (Original In Color).

##  Appendix B Efficiency Documentation

###  B.1 Corning 7980 Quartz Transmissivity

Figure B.1: Corning 7980 quartz wavelength dependent transmissivity [21].

Fig. B.1 shows the Corning 7980 quartz wavelength dependent transmissivity.
The plot data were converted into the absorption length using absorption
equation

$\frac{I}{I_{0}}=P=e^{-x/\alpha}\\\ $ (B.1)

where $I_{0}$ is the initial beam intensity, $I$ is the beam intensity at
depth $x$ and $P$ is the transmissivity. The absorption length $\lambda$ can
be written as

$\alpha=-x/\ln{P}\,.$ (B.2)

The absorption lengths were embedded into the Geant4 simulation and quartz
material depth $x$ is set for 1 cm. Table B.1 shows the absorption length and
transmissivity at different wavelength.

Table B.1: Corning 7980 quartz absorption length and transmissivity at different wavelength. $\lambda$ | Transmissivity | Absorption Length $\alpha$
---|---|---
(nm) | (%) | (m)
100 | 00.00 | 0.00005
160 | 00.00 | 0.00005
165 | 52.00 | 0.01530
170 | 68.00 | 0.02600
180 | 85.00 | 0.06200
200 | 98.00 | 0.49500
225 | 99.00 | 0.99500
250 | 99.57 | 2.32000
300 | 99.80 | 4.99500
350 | 99.93 | 14.2800
400 | 100.0 | 100.000
450 | 99.97 | 33.3280
500 | 99.96 | 24.9950
600 | 99.95 | 19.9950
700 | 99.92 | 12.4950
800 | 99.90 | 9.99500

###  B.2 PMT Radial Dependent Efficiency

Figure B.2: PMT Radial Dependent Efficiency [20].

Fig B.2 shows the radial dependent efficiency of Hamamatsu R1584 PMT. The data
points are the average over 4 set of radial efficiency measurements provided
by Hamamastu. A 6th degree polynomial function is used to fit the data and the
efficiency can be written as

$\eta=P_{0}+P_{1}x+P_{2}x^{2}+P_{3}x^{3}+P_{4}x^{4}+P_{5}x^{5}+P_{6}x^{6}$
(B.3)

where $x$ is the radial distance from the center of the PMT. The fitted
parameter values are as given:

$P_{0}$ | = | 0.699858
---|---|---
$P_{1}$ | = | 0.000199
$P_{2}$ | = | -4.8$\times 10^{-5}$
$P_{3}$ | = | 2.5$\times 10^{-6}$
$P_{4}$ | = | 3.4$\times 10^{-8}$
$P_{5}$ | = | 1.1$\times 10^{-9}$
$P_{6}$ | = | -3.8$\times 10^{-11}$

(B.3) is embedded into the HGC Geant4 simulation to provide the PMT radial
efficiency.

###  B.3 PMT Quantum Efficiency

Figure B.3: Hamamatsu R1584 PMT quantum efficiency [46].

The Hamamatsu R1584 PMT wavelength quantum efficiency from the catalog is
shown in the figure above. We interpret this curve as the result of both
quantum and position dependence in the PMT central region. Since we separately
count for the position dependence and the PMT central region has position
efficiency of 70% as shown in Fig. B.3, the quantum efficiency curve is
corrected up by 43%. The corrected efficiency curve was included in our Geant4
simulation.


T}{T}\cdot\frac{1}{\lambda_{j}^{2}}\cdot\left(1-2\lambda_{j}\sum_{i=\ell}^{\log
T-1}\sum_{k=i\cdot\frac{T}{\log T}+1}^{(i+1)\cdot\frac{T}{\log
T}}\frac{\eta_{1}}{2^{i}}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{256}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}\cdot\left(1-2\lambda_{j}\sum_{i=\ell}^{\log
T-1}\frac{T}{\log T}\cdot\frac{\eta_{1}}{2^{i}}\right)$ $\displaystyle\geq$
$\displaystyle\frac{1}{256}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}\cdot\left(1-2\lambda_{j}\cdot\frac{T}{\log
T}\cdot\frac{\eta_{1}}{2^{\ell-1}}\right)$
$\displaystyle\overset{\eqref{eq:steplower_first_interval_1}}{\geq}$
$\displaystyle\frac{1}{256}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}\cdot\left(1-4\lambda_{j}\cdot\frac{T}{\log
T}\cdot\frac{\eta_{1}}{\lambda_{j}\eta_{1}\cdot\frac{8T}{\log T}}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{256}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}\cdot\frac{1}{2}$ $\displaystyle=$
$\displaystyle\frac{1}{512}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}$

Here the first inequality is obtained by focusing variance generated in
interval $\ell$ only. The second inequality utilizes $\tau\geq\ell\cdot T/\log
T$. The fourth inequality is entailed by
$(1-a_{1})(1-a_{2})=1-a_{1}-a_{2}+a_{1}a_{2}\geq 1-a_{1}-a_{2}$ for $\forall
a_{1},a_{2}\in[0,1]$, where by mathematical induction, we can extend this
inequality for more terms $\prod_{i=1}^{n}(1-a_{i})\geq 1-\sum_{i=1}^{n}a_{i}$
as long as $\sum_{i=1}^{n}a_{i}\leq 1$. The fifth inequality comes from
$\sum_{i=\ell}^{\log
T-1}1/2^{i}\leq\sum_{i=\ell}^{\infty}1/2^{i}=1/2^{\ell-1}$.

b) For $\forall j\in\mathcal{B}$:

Step decay’s bottleneck will occur in the bias term. Since $j\in\mathcal{B}$,
it follows from the definition of $\mathcal{B}$ in Eqn.(G.22),

$\displaystyle\lambda_{j}\leq\frac{\log
T}{8\eta_{1}T}\quad\Longrightarrow\quad\eta_{1}\lambda_{j}\leq\frac{\log
T}{8T},$

we have

$\displaystyle b_{j}=$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\prod_{k=0}^{T}(1-\eta_{k}\lambda_{j})^{2}$
$\displaystyle\geq$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-\sum_{k=0}^{T}2\eta_{k}\lambda_{j}\right)=\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-\sum_{k=1}^{T}2\eta_{k}\lambda_{j}\right)$
$\displaystyle=$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-\sum_{i=0}^{\log
T-1}\sum_{k=i\cdot\frac{T}{\log T}+1}^{(i+1)\cdot\frac{T}{\log
T}}2\eta_{k}\lambda_{j}\right)$ $\displaystyle=$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-\sum_{i=0}^{\log
T-1}\sum_{k=i\cdot\frac{T}{\log T}+1}^{(i+1)\cdot\frac{T}{\log
T}}\frac{\eta_{1}\lambda_{j}}{2^{i-1}}\right)$ $\displaystyle=$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-\eta_{1}\lambda_{j}\sum_{i=0}^{\log
T-1}\frac{T}{\log T}\cdot\frac{1}{2^{i-1}}\right)$ $\displaystyle\geq$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-4\eta_{1}\lambda_{j}\cdot\frac{T}{\log
T}\right)$ $\displaystyle\geq$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\left(1-4\cdot\frac{\log
T}{8T}\cdot\frac{T}{\log T}\right)$ $\displaystyle=$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\frac{1}{2},$

where the first inequality is caused by
$(1-a_{1})(1-a_{2})=1-a_{1}-a_{2}+a_{1}a_{2}\geq 1-a_{1}-a_{2}$ for $\forall
a_{1},a_{2}\in[0,1]$ and applying mathematical induction for $\\{a_{n}\\}$ to
obtain $\prod_{i=1}^{n}(1-a_{i})\geq 1-\sum_{i=1}^{n}a_{i}$ as long as
$\sum_{i=1}^{n}a_{i}\leq 1$. The second equality is because $\eta_{0}=0$. The
second inequality comes from $\sum_{i=0}^{\log
T-1}1/2^{i-1}\leq\sum_{i=0}^{\infty}1/2^{i-1}=4$. The last inequality follows
$\eta_{1}\lambda_{j}\leq\log T/(8T)$.

From assumption (3), we know $\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}>0$.
Furthermore, as we require

$\displaystyle\frac{T}{\log
T}\geq\frac{1}{256}\cdot\frac{\sigma^{2}}{\min_{j}\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}}$

in Eqn. (G.19),

$\displaystyle b_{j}\geq$
$\displaystyle\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\frac{1}{2}\geq\min_{j}\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\cdot\frac{1}{2}\geq\frac{1}{512}\cdot\frac{\sigma^{2}}{T}\cdot\log
T.$

In sum, we have obtained

$\displaystyle\forall j\in\mathcal{A},\quad$ $\displaystyle
v_{j}\geq\frac{1}{512}\cdot\frac{\log T}{T}\cdot\frac{1}{\lambda_{j}^{2}}$
$\displaystyle\forall j\in\mathcal{B},\quad$ $\displaystyle
b_{j}\geq\frac{1}{512}\cdot\frac{\sigma^{2}}{T}\cdot\log T$

By combining with Eqn. (G.21), we have

$\displaystyle\mathbb{E}\left[f(w_{T+1}-f(w_{*})\right]=$
$\displaystyle\frac{1}{2}\left[\left(\sum_{j=1}^{d}b_{j}\right)+\left(\sigma^{2}\sum_{j=1}^{d}\lambda_{j}^{2}v_{j}\right)\right]$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\left[\left(\sum_{j\in\mathcal{B}}b_{j}\right)+\left(\sigma^{2}\sum_{j\in\mathcal{A}}\lambda_{j}^{2}v_{j}\right)\right]$
$\displaystyle\geq$
$\displaystyle|\mathcal{B}|\cdot\left(\frac{1}{1024}\cdot\frac{\sigma^{2}}{T}\cdot\log
T\right)+\sum_{j\in\mathcal{A}}\sigma^{2}\cdot\lambda_{j}^{2}\cdot\frac{1}{1024}\cdot\frac{\log
T}{T}\cdot\frac{1}{\lambda_{j}^{2}}$ $\displaystyle=$
$\displaystyle|\mathcal{B}|\cdot\left(\frac{1}{1024}\cdot\frac{\sigma^{2}}{T}\cdot\log
T\right)+|\mathcal{A}|\cdot\left(\frac{1}{1024}\cdot\frac{\sigma^{2}}{T}\cdot\log
T\right)$ $\displaystyle=$
$\displaystyle\left(|\mathcal{A}|+|\mathcal{B}|\right)\cdot\left(\frac{1}{1024}\cdot\frac{\sigma^{2}}{T}\cdot\log
T\right)$ $\displaystyle=$ $\displaystyle
d\cdot\frac{1}{1024}\cdot\frac{\sigma^{2}}{T}\cdot\log T$ $\displaystyle=$
$\displaystyle\Omega\left(\frac{d\sigma^{2}}{T}\cdot\log T\right),$

where the first inequality is because both the bias and variance terms are
non-negative, given
$b_{j}=\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\prod_{k=0}^{T}(1-\eta_{k}\lambda_{j})^{2}\geq
0$ and
$v_{j}=\sum_{\tau=0}^{T}\eta_{\tau}^{2}\prod_{k=\tau+1}^{T}(1-\eta_{k}\lambda_{j})^{2}\geq
0$.

∎

######  Remark 3.

The requirement $T/\log T\geq
1/256\cdot\sigma^{2}/\left(\min_{j}\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\right)$
and assumption $\lambda_{j}\left(w_{0,j}-w_{*,j}\right)^{2}\neq 0$ for
$\forall j=1,2,\dots,d$ can be replaced with $T/\log T>1/(8\eta_{1}\mu)$,
since in that case $j\in\mathcal{A}$ holds for $\forall j=1,2,\dots,d$ and
$\mathcal{B}=\emptyset$. In particular, if $\eta_{1}=1/L$, this requirement on
$T$ becomes $T/\log T\geq\kappa/8$.

###  G.5 The Reason of Using Assumption (1.7)

In all of our analysis, we employ assumption (1.7)

$\displaystyle\mathbb{E}_{\xi}\left[n_{t}n_{t}^{\top}\right]\preceq\sigma^{2}H\quad\mbox{
where }n_{t}=Hw_{t}-b-\left(H(\xi)w_{t}-b(\xi)\right)$

which is the same as the one in Appendix C, Theorem 13 of Ge et al. (2019).
This key theorem is the major difference between our work and Ge et al.
(2019), which directly entails its main theorem by instantiating $\sigma$ with
specific values in its assumptions.

On the other hand, it is possible to use the assumptions in Ge et al. (2019);
Bach & Moulines (2013); Jain et al. (2016) instead of our assumption (1.7) for
least square regression:

$\displaystyle\min_{w}f(w)\quad\mbox{ where
}f(w)\triangleq\frac{1}{2}\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[(y-w^{\top}x)^{2}\right]$
(G.25) $\displaystyle y=w_{*}^{\top}x+\epsilon\mbox{ with $\epsilon$
satisfying
}\mathbb{E}_{(x,y)\sim\mathcal{D}}\left[\epsilon^{2}xx^{\top}\right]\preceq\sigma^{2}H\mbox{
for }\forall(x,y)\sim\mathcal{D}$ (G.26)
$\displaystyle\mathbb{E}\left[||x||^{2}xx^{\top}\right]\preceq R^{2}H$ (G.27)

By combining our Lemma 1 and assumption (1.7) with Lemma 5, Lemma 8 and Lemma
9 in Ge et al. (2019), one can obtain similar results in this paper with their
assumptions. For simplicity, we just use assumption (1.7) here.

##  Appendix H Relationship with (Stochastic) Newton’s Method

Our motivation in Proposition 1 shares a similar idea with (stochastic)
Newton’s method on quadratic objectives

$\displaystyle w_{t+1}=$ $\displaystyle w_{t}-\eta_{t}H^{-1}\nabla
f(w_{t},\xi),$

where the parameters are also updated coordinately in the “rotated space”,
i.e. given $H=U\Lambda U^{\top}$ and $w^{\prime}=U^{\top}w$. In particular,
when the Hessian $H$ is diagonal and $\eta_{t}=1/(t+1)$, the update formula is
exactly the same as the one for Proposition 1.

Despite of this similarity, our method differ from Newton method’s and its
practical variants in several aspects. First of all, our method focuses on
learning rate schedulers and is a first-order method. This property is
especially salient when we consider eigencurve’s derivatives in Section 4.3:
only hyperparameter search is needed, just like other common learning rate
schedulers. In addition, most second-order methods, e.g. Schraudolph (2002);
Erdogdu & Montanari (2015); Grosse & Martens (2016); Byrd et al. (2016); Botev
et al. (2017); Huang et al. (2020); Yang et al. (2021), approximates the
Hessian matrix or the Hessian inverse and exploits the curvature information,
while eigencurve only utilizes the rough estimation of the Hessian spectrum.
On top of that, this estimation is only an one-time effect and can be even
further removed for similar models. These key differences highlight
eigencurve’s advantages over most second-order methods in practice.