Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper proposes to represent nodes in graphs by time series. This is an interesting idea but the results presented in the paper are very preliminary.
Experiments are only conducted on synthetic data with very small sizes.
In Section 5.1, I did not understand the construction of the graph. What means 'all the vertices are disjoint'? Then I do not understand why the vertices of G_i form the optimum.
review_title: The motivation for this paper is unclear. The writing is problematic and evaluations are not sufficient.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes GRAPH2SEQ that represents graphs as infinite time-series of vectors, one for
each vertex of the graph and in an invertible representation of a graph.  By not having the restriction of representation to a fixed dimension, the authors claims their proposed method is much more scalable. They also define a formal computational model, called LOCAL-Gather that includes GRAPH2SEQ and other classes of GCNN representations, and show that GRAPH2SEQ is capable of computing certain graph functions that fixed-depth GCNNs cannot. They experiment on graphs of size at most 800 nodes to discover minimum vertex cover and show that their method perform much better than GCNNs but is comparable with greedy heuristics for minimum vertex cover.

I find the experiments to be hugely disappointing. Claiming that this particular representation helps in scalability and then doing experiment on graphs of extremely small size does not reflect well. It would have been much more desirable if the authors had conducted experiments on large graphs and compare the results with greedy heuristics. Also, the authors need to consider other functions, not only minimum vertex cover. In general, lack of substantial experiments makes it difficult to appreciate the novelty of the work. I am not at all sure, if this representation is indeed useful for graph optimization problems practically.





review_title: Unclear motivation and experiments

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 


review_title: Interesting idea but limited validation. Also sample complexity may be exponential in graph degree.

Meta-review: The reviewers agree that the problem being studied is important and relevant but express serious concerns. I recommend the authors to carefully go through the reviews and significantly scale up their experiments.
Decision: Reject