Neural networks are increasingly used as a general purpose approach to learning algorithms over graph structured data. However, techniques for representing graphs as real-valued vectors are still in their infancy. Recent works have proposed several approaches (e.g., graph convolutional networks), but as we show in this paper, these methods have difficulty generalizing to large graphs. In this paper we propose GRAPH2SEQ, an embedding framework that represents graphs as an infinite time-series. By not limiting the representation to a fixed dimension, GRAPH2SEQ naturally scales to graphs of arbitrary size. Moreover, through analysis of a formal computational model we show that an unbounded sequence is necessary for scalability. GRAPH2SEQ is also reversible, allowing full recovery of the graph structure from the sequence. Experimental evaluations of GRAPH2SEQ on a variety of combinatorial optimization problems show strong generalization and strict improvement over state of the art.
This paper proposes a novel way of embedding graph structure into a sequence that can have an unbounded length. 
There has been a significant amount of prior work (e.g. d graph convolutional neural networks) for signals supported on a specific graph. This paper on the contrary tries to encode the topology of a graph using a dynamical system created by the graph and randomization. 
The main theorem is that the created dynamical system can be used to reverse engineer the graph topology for any digraph. 
As far as I understood, the authors are doing essentially reverse directed graphical model learning. In classical learning of directed graphical models (or causal DAGs) one wants to learn the structure of a graph from observed data created by this graph inducing conditional independencies on data. This procedure is creating a dynamical system that (following very closely previous work) estimates conditional directed information for every pair of vertices u,v and can find if an edge is present from the observed trajectory. 
The recovery algorithm is essentially previous work (but the application to graph recovery is new).
The authors state:
``Estimating conditional directed information efficiently from samples is itself an active area of research Quinn et al. (2011), but simple plug-in estimators with a standard kernel density estimator will be consistent.''
One thing that is missing here is that the number of samples needed could be exponential in the degrees of the graph. Therefore, it is not clear at all that high-dimensional densities or directed information can be estimated from a number of samples that is polynomial in the dimension (e.g. graph degree).
This is related to the second limitation, that there is no sample complexity bounds presented only an asymptotic statement. 
One remark is that there are many ways to represent a finite graph with a sequence that can be decoded back to the graph (and of course if there is no bound on the graph size, there will be no bound on the size of the sequence). For example, one could take the adjacency matrix and sequentially write down one row after the other (perhaps using a special symbol to indicate 'next row'). Many other simple methods can be obtained also, with a size of sequence being polynomial (in fact linear) in the size of the graph. I understand that such trivial representations might not work well with RNNs but they would satisfy stronger versions of Theorem 1 with optimal size. 
On the contrary it was not clear how the proposed sequence will scale in the graph size. 
Another remark is that it seems that GCNN and this paper solve different problems. 
GCNNs want to represent graph-supported signals (on a fixed graph) while this paper tries to represent the topology of a graph, which seems different. 
The experimental evaluation was somewhat limited and that is the biggest problem from a practical standpoint. It is not clear why one would want to use these sequences for solving MVC. There are several graph classification tasks that try to use the graph structure (as well as possibly other features) see eg the bioinformatics 
and other applications. Literature includes for example:
Graph Kernels by S.V.N. Vishwanathan et al. 
Deep graph kernels (Yanardag & Vishwanathan and graph invariant kernels (Orsini et al.),
which use counts of small substructures as features. 
The are many benchmarks of graph classification tasks where the proposed representation could be useful but significantly more validation work would be needed to make that case.