Fast streaming small graph canonization Pedro Paredes and Pedro Ribeiro 2018

Abstract

In this paper we introduce the streaming graph canonization problem. Its goal is finding a canonical representation of a sequence of graphs in a stream. Our model of a stream fixes the graph’s vertices and allows for fully dynamic edge changes, meaning it permits both addition and removal of edges. Our focus is on small graphs, since small graph isomorphism is an important primitive of many subgraph based metrics, like motif analysis or frequent subgraph mining. We present an efficient data-structure to approach this problem, namely a graph isomorphism discrete finite automaton and showcase its efficiency when compared to a non-streaming-aware method that simply recomputes the isomorphism information from scratch in each iteration.

Keywords

Graph Canonization; Streaming; Temporal Graphs

Digital Object Identifier (DOI)

doi 10.1007/978-3-319-73198-8_3

Publication in PDF format

pdf Download PDF

Software

software Streaming Small Graph Canonization

Journal/Conference/Book

9th Conference on Complex Networks

Reference (text)

Pedro Paredes and Pedro Ribeiro. Fast streaming small graph canonization. Proceedings of the 9th Conference on Complex Networks (CompleNet), pp. 27-40, Springer, Boston, USA, March, 2018.

Bibtex

@inproceedings{ribeiro-COMPLENET2018,
  author = {Pedro Paredes and Pedro Ribeiro},
  title = {Fast streaming small graph canonization},
  doi = {10.1007/978-3-319-73198-8_3},
  booktitle = {9th Conference on Complex Networks},
  pages = {27-40},
  publisher = {Springer},
  month = {March},
  year = {2018}
}