Venue: ICLR 2018 conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors propose a method for learning node representations which, like previous work (e.g. node2vec, DeepWalk), is based on the skip-gram model. However, unlike previous work, they use the concept of shared neighborhood to define context rather than applying random walks on the graph.

The paper is well-written and it is quite easy to follow along with the discussion. This work is most similar, in my opinion, to node2vec. In particular, when node2vec has its restart probability set pretty high, the random walks tend to stay within the local neighborhood (near the starting node). The main difference is in the sentence construction strategy. Whereas node2vec may sample walks that have context windows containing the same node, the proposed method does not as it uses a random permutation of a node's neighbors. This is the main difference between the proposed method and node2vec/DeepWalk.

Pros:

Outperforms node2vec and DeepWalk on 5 of the 6 tested datasets and achieves comparable results on the last one.
Proposes a simple yet effective way to sample walks from large graphs.


Cons:

The description on the experimental setup seems to lack some important details. See more detailed comments in the paragraph below. While LINE or SDNE, which the authors cite, may not run on some of the larger datasets they can be tested on the smaller datasets. It would be helpful if the authors tested against these methods as well. 

 For instance, on page 5 footnote 4 the authors state that DeepWalk and node2vec are tested under similar conditions but do not elaborate. In NBDE, when k=5 a node u's neighbors are randomly permuted and these are divided into subsets of five and concatenated with u to form sentences. Random walks in node2vec and DeepWalk can be longer, instead they use a sliding context window. For instance a sentence of length 10 with context window 5 gives 6 contexts. Do the authors account for this to ensure that skip-gram for all compared methods are tested using the same amount of information. Also, what exactly does the speedup in time mean. The discussion on this needs to be expounded.
review_title: Good work

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper demonstrates good experiment results on several tasks. There are some pros and comes as below:

Pros
The proposed model provides a new view to generate training examples for random-walk-based embedding models.
Experiments are conducted on several datasets (6 datasets for link prediction and 3 datsets for classification).
Various experiments are provided to support the analysis of time complexity of the proposed model.
Additional experiments are provided in appendix, though the details of experimental setups are not provided.

Cons:
1. The novelty is limited. The main contribution is the idea of substituting random-walk by neighbors of a node. The rest of the model can be viewed as DeepWalk which requires walk length be the same as window size.
2. The experiment setup is not fair to the competitors. It seems that the proposed model is turned by validation, and the competitors adopt the parameters proposed in Node2Vec. A fair experiment shall require every model to turn their parameters by the validation dataset. 
3. Furthermore, since embedding training is unsupervised, in reality no validation data can be used to select the parameters. Therefore a fair experiments it to find a universal set of parameters and use them across different datasets. 

4. In section 4.1 (Link Prediction), is there negative sampling during training and testing? Otherwise the training and testing instances are all positive. Also, what is the ratio of positive instances over negative ones?
5. In section 5.1 (Number of Permutations), why is “test accuracy” adopted but not “AUC” (which is the evaluation metric in section 4.1)?
6. In section 5.1 (Number of Permutations), table 4 should contain only the results of the same task (either Link Prediction or Classification but not both).
7. Didn't compare with the state-of-the-art node embedding models.
review_title: The authors propose a node embedding model NBNE, which preserves both first and second order proximity. NBNE is similar to random-walk-based methods (DeepWalk, Node2Vec) while having a different definition of “walk”. It defines “neighbors of a node” to be the “walk”. It also proposes that the “sentence length” should be the same as “window size”. It outperforms baseline models (DeepWalk and Node2Vec) in link prediction and classification tasks and also significantly reduces training time.

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper includes the terms first-order proximity ("the concept that connected nodes in a graph should have similar properties") and second-order proximity ("the concept that nodes with similar neighborhoods should have common characteristics"). These are called homophily in social network analysis. It is also known as assortativity in network science literature. The paper states on Page 4: "A trade-off between first and second order proximity can be achieved by changing the parameter k, which simultaneously controls both the sizes of sentences generated and the size of the wind used in the SkipGram algorithm." It is not readily clear why this statement should hold. Also the paper does not include a discussion on how the amount of homophily in the graph affects the results. There are various ways of measuring the level of homophily in a graph. There is simple local consistency, which is % of edges connecting nodes that have the same characteristics at each endpoint. Neville & Jensen's JMLR 2007 paper describes relational auto-correlation, which is Pearson contingency coefficient on the characteristics of endpoints of edges. Park & Barabasi's PNAS 2007 paper describes dyadicity and heterophilicity, which measures connections of nodes with the same characteristics compared to a random model and the connections of nodes with different characteristics compared to a random model. 

k ("which simultaneously controls both the sizes of sentences generated and the size of the wind used in the SkipGram algorithm") is a free-parameter in the proposed algorithm. The paper needs an in-depth discussion of the role of k in the results. Currently, no discussion is provided on k except that it was set to 5 for the experiments.  From a network science perspective, it makes sense to have k vary per node.

It is also not clear why d = 128 was chosen as the size of the embedding.

From the description of the experimental setup for link prediction, it is not clear if a stratified sample of the entries of the adjacency matrix (i.e., both 0 and 1 entries) where selected.

For the node classification experiments, information on class distribution and homophily levels would be helpful. 

In Section 5.1, the paper states: "For highly connected graphs, larger numbers of permutations should be chosen (n in [10, 1000]) to better represent distributions, while for sparser graphs, smaller values can be used (n in [1, 10])." How high is highly connected graphs? How spare is a sparser graph? In general, the paper lacks an in-depth analysis of when the approach works and when it does not.  I recommend running experiments on synthetic graphs (such as Barabasi-Albert, Watts-Strogatz, Forest Fire, Kronecker, and/or BTER graphs), systematically changing various characteristics of the graph, and reporting the results.

The faster runtime is interesting but not surprising given the ego-centric nature of the approach.


review_title: The papers presents approach to embed nodes based on their 1-hop (i.e, immediate) neighbors.  It is not clear on what types of graphs the approach will perform well.  The space of graphs is not exhausted by the six chosen data sets.

Meta-review: The authors addressed the reviewers concerns but the scores remain somewhat low.
The method is not super novel, but it is an incremental improvement over existing approaches.
Decision: Invite to Workshop Track