  Tracking a targeted subset of nodes in an evolving graph is important for
many real-world applications. Existing methods typically focus on identifying
anomalous edges or finding anomaly graph snapshots in a stream way. However,
edge-oriented methods cannot quantify how individual nodes change over time
while others need to maintain representations of the whole graph all time, thus
computationally inefficient.
  This paper proposes \textsc{DynAnom}, an efficient framework to quantify the
changes and localize per-node anomalies over large dynamic weighted-graphs.
Thanks to recent advances in dynamic representation learning based on
Personalized PageRank, \textsc{DynAnom} is 1) \textit{efficient}: the time
complexity is linear to the number of edge events and independent on node size
of the input graph; 2) \textit{effective}: \textsc{DynAnom} can successfully
track topological changes reflecting real-world anomaly; 3) \textit{flexible}:
different type of anomaly score functions can be defined for various
applications. Experiments demonstrate these properties on both benchmark graph
datasets and a new large real-world dynamic graph. Specifically, an
instantiation method based on \textsc{DynAnom} achieves the accuracy of 0.5425
compared with 0.2790, the best baseline, on the task of node-level anomaly
localization while running 2.3 times faster than the baseline. We present a
real-world case study and further demonstrate the usability of \textsc{DynAnom}
for anomaly discovery over large-scale graphs.
