# Computing Graph Descriptors on Edge Streams

arXiv: https://arxiv.org/abs/2109.01494 · HTML: https://mlsanity.com/paper/2109.01494/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 75 references that are in the map.
- First posted on arXiv 2 Sep 2021.

## Builds on (most cited first, 30 of 34)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [A Large-Scale Database for Graph Representation Learning](https://mlsanity.com/paper/2011.07682/) (2020)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Learning Graph Representations with Embedding Propagation](https://mlsanity.com/paper/1710.03059/) (2017)
- [The Multiscale Laplacian Graph Kernel](https://mlsanity.com/paper/1603.06186/) (2016)
- [Efficient Approximation Algorithms for String Kernel Based Sequence Classification](https://mlsanity.com/paper/1712.04264/) (2017)
- [Graph Isomorphism in Quasipolynomial Time](https://mlsanity.com/paper/1512.03547/) (2015)
- [DELTACON: A Principled Massive-Graph Similarity Function](https://mlsanity.com/paper/1304.4657/) (2013)
- [A Simple Baseline Algorithm for Graph Classification](https://mlsanity.com/paper/1810.09155/) (2018)
- [Predicting Attributes of Nodes Using Network Structure](https://mlsanity.com/paper/1912.12264/) (2019)
- [TRI`EST: Counting Local and Global Triangles in Fully-dynamic Streams with Fixed Memory Size](https://mlsanity.com/paper/1602.07424/) (2016)
- [Detecting DDoS Attack on SDN Due to Vulnerabilities in OpenFlow](https://mlsanity.com/paper/1912.12221/) (2019)
- [Effect of Analysis Window and Feature Selection on Classification of Hand Movements Using EMG Signal](https://mlsanity.com/paper/2002.00461/) (2020)
- [Short-Term Load Forecasting Using AMI Data](https://mlsanity.com/paper/1912.12479/) (2019)
- [Combinatorial Trace Method for Network Immunization](https://mlsanity.com/paper/1912.12070/) (2019)
- [A Multi-cascaded Model with Data Augmentation for Enhanced Paraphrase Detection in Short Texts](https://mlsanity.com/paper/1912.12068/) (2019)
- [Language Independent Sentiment Analysis](https://mlsanity.com/paper/1912.11973/) (2019)
- [Stochastic Graphlet Embedding](https://mlsanity.com/paper/1702.00156/) (2017)
- [Spectral Methods for Immunization of Large Networks](https://mlsanity.com/paper/1711.00791/) (2017)
- [Scalable Approximation Algorithm for Network Immunization](https://mlsanity.com/paper/1711.00784/) (2017)
- [Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications](https://mlsanity.com/paper/1805.11769/) (2018)
- [A Multi-cascaded Deep Model for Bilingual SMS Classification](https://mlsanity.com/paper/1911.13066/) (2019)
- [Estimating Descriptors for Large Graphs](https://mlsanity.com/paper/2001.10301/) (2020)
- [Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs](https://mlsanity.com/paper/2003.01282/) (2020)

## Built on by (most cited first, 4 of 4)

- [Spike2Vec: An Efficient and Scalable Embedding Approach for COVID-19 Spike Sequences](https://mlsanity.com/paper/2109.05019/) (2021)
- [Robust Representation and Efficient Feature Selection Allows for Effective Clustering of SARS-CoV-2 Variants](https://mlsanity.com/paper/2110.09622/) (2021)
- [Characterizing SARS-CoV-2 Spike Sequences Based on Geographical Location](https://mlsanity.com/paper/2110.00809/) (2021)
- [Information We Can Extract About a User From 'One Minute Mobile Application Usage'](https://mlsanity.com/paper/2207.13222/) (2022)

## Abstract (arXiv)

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.