Fast streaming small graph canonization

Pedro Paredes, Pedro Ribeiro

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSpringer Proceedings in Complexity
EditorsSean Cornelius, Kate Coronges, Bruno Goncalves, Roberta Sinatra, Alessandro Vespignani
PublisherSpringer Science and Business Media B.V.
Number of pages14
ISBN (Print)9783319731971
StatePublished - 2018
Externally publishedYes
Event9th International Conference on Complex Networks, CompleNet 2018 - Boston, United States
Duration: Mar 5 2018Mar 8 2018

Publication series

NameSpringer Proceedings in Complexity
ISSN (Print)2213-8684
ISSN (Electronic)2213-8692


Conference9th International Conference on Complex Networks, CompleNet 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'Fast streaming small graph canonization'. Together they form a unique fingerprint.

Cite this