Learning Graph Representations with Embedding Propagation
We propose Embedding Propagation (EP), an unsupervised learning framework for graph-structured data. EP learns vector representations of graphs by passing two types of messages between neighboring nodes. Forward messages consist of label representations such as representations of words and other attributes associated with the nodes. Backward messages consist of gradients that result from aggregating the label representations and applying a reconstruction loss. Node representations are finally computed from the representation of their labels. With significantly fewer parameters and hyperparameters an instance of EP is competitive with and often outperforms state of the art unsupervised and semi-supervised learning methods on a range of benchmark data sets.
Despite its conceptual simplicity, we show that EP generalizes several existing machine learning methods for graph-structured data. Since EP learns embeddings by incorporating different label types (representing, for instance, text and images) it is a framework for learning with multi-modal data [31].
The authors introduce embedding propagation (EP), a new message-passing method for learning representations of attributed vertices in graphs.   EP computes vector representations of nodes from the 'labels' (sparse features) associated with nodes and their neighborhood.  The learning of these representations is facilitated by two different types of messages sent along edges: a 'forward' message that sends the current representation of the node, and a 'backward' message that passes back the gradients of some differentiable reconstruction loss.  The authors report results that are competitive with or outperform baseline representation learning methods such as deepwalk and node2vec.
Quality:
The quality of the paper is high.  The experimental technique is clearly described, appears sound, and the authors report results that are competitive with strong baseline methods.  In addition, the authors provide clear theoretical analysis of the worst-case complexity of their method.  
Clarity:
The paper is generally clearly written and well-organized.  The proposed model is clearly delineated.
Originality:
The work is moderately original - the authors draw inspiration from message-passing inference algorithms to improve on existing graph embedding methods.
Significance:
On the positive side, the proposed technique is creative and likely to be of interest to the NIPS community. Furthermore, the authors report results that are competitive or better when compared with strong baseline methods, and the computational complexity of the technique is low (linear in both the maximum degree of the graph and the number of nodes).  However, while the results are competitive, it is unclear which method (if any) is offering the best performance.  This is a little troubling because EP is constructing the representations using both node features and graph structure while the baselines only consider graph structure itself, and this raises the question of whether EP is adequately capturing the node features when learning the node representation.
Overall, I believe that the paper is significant enough to warrant publication at NIPS.  
Some questions and suggestions for improvement for the authors:
 - It seems like this method could be implemented in a distributed asynchronous manner like standard belief propagation.  If so, the scalability properties are nice - linear computational complexity and a low memory footprint due to the sparse feature input and low-dimensional dense representations.  This could be a good area to explore.
 - It seems like there are really two representations being learned: a representation for a node's labels, and an overall representation for the node that takes the label representation of the node and the representations of the neighboring nodes into account.  How necessary is it to learn a representation for the node labels as a part of the pipeline?  Would it be possible to just use the raw sparse features (node labels)?  If so, how would that affect performance?
 - Is it possible to learn this representation in a semi-supervised manner?
 - Learning curves would be nice.  If the method is using fewer parameters, perhaps it's less inclined to overfit in a data-poor training regime?
 
Overall impression:
A good paper that proposes an interesting technique that gives solid (although not spectacular) results.  An interesting idea for others to build on.  Accept.