Given a labeled graph, the frequent-subgraph mining (FSM) problem asks to
find all the $k$-vertex subgraphs that appear with frequency greater than a
given threshold. FSM has numerous applications ranging from biology to network
science, as it provides a compact summary of the characteristics of the graph.
However, the task is challenging, even more so for evolving graphs due to the
streaming nature of the input and the exponential time complexity of the
problem.
In this paper, we initiate the study of the approximate FSM problem in both
incremental and fully-dynamic streaming settings, where arbitrary edges can be
added or removed from the graph. For each streaming setting, we propose
algorithms that can extract a high-quality approximation of the frequent
$k$-vertex subgraphs for a given threshold, at any given time instance, with
high probability. In contrast to the existing state-of-the-art solutions that
require iterating over the entire set of subgraphs for any update, our
algorithms operate by maintaining a uniform sample of $k$-vertex subgraphs with
optimized neighborhood-exploration procedures local to the updates. We provide
theoretical analysis of the proposed algorithms and empirically demonstrate
that the proposed algorithms generate high-quality results compared to
baselines.

本文研究了具有标签的图中的频繁子图挖掘问题，提出了适用于增量和完全动态流设置的算法，以提取给定阈值下的高质量近似频繁 $k$- 顶点子图，通过保持一个均匀采样 $k$- 顶点子图组，并优化围绕更新的邻域探索过程，以及理论分析的支持，我们证明了所提出的算法相对于现有的最先进的解决方案可以产生高质量的结果。

挖掘演化图中的频繁模式

Mining Frequent Patterns in Evolving Graphs

We develop a streaming (one-pass, bounded-memory) word embedding algorithm
based on the canonical skip-gram with negative sampling algorithm implemented
in word2vec. We compare our streaming algorithm to word2vec empirically by
measuring the cosine similarity between word pairs under each algorithm and by
applying each algorithm in the downstream task of hashtag prediction on a
two-month interval of the Twitter sample stream. We then discuss the results of
these experiments, concluding they provide partial validation of our approach
as a streaming replacement for word2vec. Finally, we discuss potential failure
modes and suggest directions for future work.

本文使用流式数据处理技术，开发了一个基于 skip-gram 和负采样实现的词嵌入算法，并在 Twitter 数据流中进行了实验，发现其可以部分替代 word2vec。

用 Space-Saving 算法流式生成词向量

Streaming Word Embeddings with the Space-Saving Algorithm

Given a stream of heterogeneous graphs containing different types of nodes
and edges, how can we spot anomalous ones in real-time while consuming bounded
memory? This problem is motivated by and generalizes from its application in
security to host-level advanced persistent threat (APT) detection. We propose
StreamSpot, a clustering based anomaly detection approach that addresses
challenges in two key fronts: (1) heterogeneity, and (2) streaming nature. We
introduce a new similarity function for heterogeneous graphs that compares two
graphs based on their relative frequency of local substructures, represented as
short strings. This function lends itself to a vector representation of a
graph, which is (a) fast to compute, and (b) amenable to a sketched version
with bounded size that preserves similarity. StreamSpot exhibits desirable
properties that a streaming application requires---it is (i) fully-streaming;
processing the stream one edge at a time as it arrives, (ii) memory-efficient;
requiring constant space for the sketches and the clustering, (iii) fast;
taking constant time to update the graph sketches and the cluster summaries
that can process over 100K edges per second, and (iv) online; scoring and
flagging anomalies in real time. Experiments on datasets containing simulated
system-call flow graphs from normal browser activity and various attack
scenarios (ground truth) show that our proposed StreamSpot is high-performance;
achieving above 95% detection accuracy with small delay, as well as competitive
time and memory usage.

StreamSpot 是一种基于聚类的异常检测方法，可以在消耗有限的内存的同时，实时对包含不同节点和边的杂乱图形流进行检测，并可处理超过每秒 100K 条边的数据流。该方法具有良好的性能，并且可以处理从正常浏览器活动到各种攻击情况的各种情况。

流式异构图快速内存高效异常检测

Fast Memory-efficient Anomaly Detection in Streaming Heterogeneous  Graphs

We consider streaming, one-pass principal component analysis (PCA), in the
high-dimensional regime, with limited memory. Here, $p$-dimensional samples are
presented sequentially, and the goal is to produce the $k$-dimensional subspace
that best approximates these points. Standard algorithms require $O(p^2)$
memory; meanwhile no algorithm can do better than $O(kp)$ memory, since this is
what the output itself requires. Memory (or storage) complexity is most
meaningful when understood in the context of computational and sample
complexity. Sample complexity for high-dimensional PCA is typically studied in
the setting of the {\em spiked covariance model}, where $p$-dimensional points
are generated from a population covariance equal to the identity (white noise)
plus a low-dimensional perturbation (the spike) which is the signal to be
recovered. It is now well-understood that the spike can be recovered when the
number of samples, $n$, scales proportionally with the dimension, $p$. Yet, all
algorithms that provably achieve this, have memory complexity $O(p^2)$.
Meanwhile, algorithms with memory-complexity $O(kp)$ do not have provable
bounds on sample complexity comparable to $p$. We present an algorithm that
achieves both: it uses $O(kp)$ memory (meaning storage of any kind) and is able
to compute the $k$-dimensional spike with $O(p \log p)$ sample-complexity --
the first algorithm of its kind. While our theoretical analysis focuses on the
spiked covariance model, our simulations show that our algorithm is successful
on much more general models for the data.

本研究提出了一种基于流处理的、使用有限内存的主成分分析算法，它可以在高维情况下有效地运行，并且在样本复杂度上比相关算法更好。