Feature extraction is an essential task in graph analytics. These feature
vectors, called graph descriptors, are used in downstream vector-space-based
graph analysis models. This idea has proved fruitful in the past, with
spectral-based graph descriptors providing state-of-the-art classification
accuracy. However, known algorithms to compute meaningful descriptors do not
scale to large graphs since: (1) they require storing the entire graph in
memory, and (2) the end-user has no control over the algorithm's runtime. In
this paper, we present streaming algorithms to approximately compute three
different graph descriptors capturing the essential structure of graphs.
Operating on edge streams allows us to avoid storing the entire graph in
memory, and controlling the sample size enables us to keep the runtime of our
algorithms within desired bounds. We demonstrate the efficacy of the proposed
descriptors by analyzing the approximation error and classification accuracy.
Our scalable algorithms compute descriptors of graphs with millions of edges
within minutes. Moreover, these descriptors yield predictive accuracy
comparable to the state-of-the-art methods but can be computed using only 25%
as much memory.

通过使用流算法近似计算三种不同的图表述，避免将整个图存储在内存中，并控制样本大小，使我们能够将算法运行时间保持在所需的范围内，并通过分析逼近误差和分类准确度证明所提出的描述符的功效。