Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: ### Summary

The authors propose a "meta-algorithm" for approximating various graph representation learning schemes: generate batches of random trees with fixed fanout (and possibly biased probabilities of selecting different edges), and use them to accumulate information to approximate operations on the graph.  The idea is beautifully simple, and generalizes running independent random walkers, an approach that is used in deriving many related algorithms.  The biasing and accumulation functions are user provided, and the authors show how different choices of these functions can be used to approximate a number of graph representation learning schemes.  The authors also provide a software framework, though it was inaccessible at review due to anonymization.  Experiments show the approach is much more scalable than competing approaches (though, to be fair, some of the competition was not targeting scalability).

### Minor points

- The "CompactAdj" format seems equivalent to compressed sparse row (or compressed sparse column) storage for the adjacency.  Is there any difference?
- It might be worth commenting (possibly in appendices) on the data structures used for accumulation in the different concrete instances that are presented.  For example, the sparse matrix data structure used in 3.3.1 is presumably a neighbor list or equivalent, and not the CompactAdj format (since rebuilding the latter at every step seems needlessly expensive).
- The claim at the end of section 4.1 that "although naive calculation of $T^k$ is cubic, GTTF can estimate it in time complexity independent of the number of nodes" is imprecise to the point of being misleading.  One can exactly compute a single row of $T^k$ for arbitrary $T$ via repeated sparse matrix-vector products time time proportional to the graph size times $k$, and one can do an approximate  computation of a row of $T^k$ even more cheaply using the method sketched here.  One can also get efficient estimates of various properties of matrix powers.  But actually getting estimates of all elements of the matrix $T^k$ in general is going to depend on the size of the graph, particularly when $k$ gets to the order of the graph diameter.

### Typos

- In the related work section, the table lists "DGI" -- I believe this is referring to DGL.
- For the paper, I recommend writing out "without loss of generality" rather than using the abbreviation at the start of section 3 (unless it leads to going over space)
- Add "the" before "node embedding WYS" at the start of 4.3.

### Update

Thanks to the authors for their clarifications (and to the other reviewers).  I am more comfortable with my accept recommendation now, and have updated my confidence accordingly.
review_title: Approximating graph representation learning schemes via sampling random trees

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a new graph traversal method by introducing a compact adjacency matrix and applying stochastic methods to sample nodes.  The proposed graph traversal can be applied in conjunction with graph neural networks such as GCN, Deepwalk,..etc, and ideas proposed in the paper would interest and influence other researchers in the community. An advantage is that the proposed method shows improvements in speed and memory usage. Overall, The paper is well written with both theoretical and experimental evaluations. 

Pros:
a.) The proposed method well-developed and supported with theoretical analysis 

b.) The proposed sampling method can be combined with other existing methods. The authors discuss the applicability of the proposed method with existing methods.

Cons:
a.) One limitation is that experiments are not very convincing since there are only a few baseline methods that are compared with the proposed method.  For instance, It would be better to show performances of methods like GraphSAGE, cluster GCN, and other methods (at least method in the table in Section 2) applied to all datasets. Showing different selections of baseline methods make it hard to understand the true performances of the proposed method. Can the authors provide more detailed comparisons with different baseline methods?  

b.) The performances (e.g. semisupervised node-classification) shown are not as competitive as performances achieved by other recent methods (e.g. GCNII). Can the authors add more experimental results to the paper?

I raise my rating based on the additional experimental results given.
review_title: Good contribution but experiments are not convincing 

final_score: rating: 7: Good paper, accept
review_content: # Quality

This paper, as far as I can tell, is technically solid.
The authors present an algorithm, show how it can be specialized to a variety of other methods, then prove the conditions under which it estimates loss functions, gradients, and powers of transition matrices without bias.
They then demonstrate how their method can be used to approximate graph representation learning techniques over a variety of datasets, as well as enabling the application of non-scalable techniques to large graphs.

# Clarity

This paper is mostly well-written, with a few issues throughout.

One issue I took was with the authors' use of the term "tensor:" they claim that their method allows for efficient implementation via standard tensor operations.
This was deceiving when first reading the paper: I expected this approach to involve tensors in the sense of a multilinear operator, and for operations to be understood in terms of that operator.
The approach in this paper doesn't resemble tensor methods in that way: it would be better described as graph representation learning with sparse edge lists.

There is also some ambiguity in Algorithm 1: it is unclear what AccumulateFn *does*.
Without thoroughly looking at the specific applications, it is not easy to tell what effect line 10 in Algorithm 1 has.
It would significantly improve readability to be specific about side-effects, return values, etc. of AccumulateFn in general.

# Originality

This paper is somewhat original.
The authors do not formulate anything particularly new: rather, they unify a variety of algorithms for graph representation learning under a common approach, parameterized by two functions (Accumulate and Bias).
The algorithm in this paper takes very similar form to that written in the most popular GRL papers, so I would not evaluate it as being a particularly novel contribution.

However, there is novel value in the analysis of the meta-algorithm as an unbiased estimator of loss functions dependent on powers of a transition matrix.
This is similar in spirit to the cited paper [Qui et al., 2018], where a link is made between these methods and matrix factorization techniques.
Here, the authors have made a link between many methods and a general framework, from which they can form computationally efficient approximations.

# Significance

One contribution of this work to the community is a "unified look" at a wide array of node embedding methods.
The authors have identified common features of approaches such as node2vec, DeepWalk, GCN, etc., and formulated a stochastic approach that is flexible enough to reflect each of these algorithms.
I wouldn't characterize this formulation as inherently significant, since the form of all of these algorithms is written in a similar way.

A more concrete contribution of this work is the analysis of this formulation as a computationally efficient (Propositions 6 and 7) approximator for powers of a transition matrix (Propositions 1 and 2), which has applications in many representation learning tasks.
It is established that using the proposed estimator of the transition matrix yields unbiased estimates and gradients for a class of loss functions (Propositions 3, 4, and 5).

This yields the most significant contribution of this paper: if a practitioner can write the loss function in the form provided in Proposition 3, the formulation of the authors can be justified as a good, computationally efficient approximant for their case.
This impact is demonstrated in the experiments using WYS, where the authors' form is shown to perform similarly to WYS on graphs of small scale, and then shown to be feasible on graphs of large scale, while the original form of WYS does not scale.
That is, the proposed framework appears to be a reasonable way to approximate methods that are not scalable, showing potential in bridging theory and practice.

Beyond the special case where a method's loss function can be written in terms of a transition matrix raised to some power, though, this paper falls short.
It would be useful to understand the behavior of this approach when used to approximate methods that cannot be written in the form of Proposition 3.
Because of this, the scope of analysis in this paper is somewhat limited: the authors should more directly discuss cases where this is not true, beyond the brief mention of node2vec in the appendix.

# Overall review

This paper takes a broad view of graph representation learning problems, proposing a generic algorithm that they show can recover many popular approaches.
Although there are a few missing pieces, the proposed approach is useful in scaling approaches that were previously not scalable, and thus warrants being accepted into ICLR 2021.
review_title: A nice paper with wide range, suffering from a few problems

final_score: rating: 7: Good paper, accept
review_content: Pros:
1)	The graph traversal via tensor functionals is proposed with stochastic graph traversal algorithm based on tensor optimization that inherits benefits of vectorized computation and libraries. 
2)	It can be specialized for many existing models and make them scalable for large graph.
3)	Authors proved the learning is unbiased, with controllable variance.
4)	Experimental results on both node classification and link prediction verify the efficiency and effectiveness of the proposed unified meta-algorithm framework. 

Cons:
1)	As shown in the experiments, the implementation of existing methods under GTTE can be more efficient and less memory requirement. It might be better to conduct complexity analysis on the proposed meta-algorithm to show these advantages.
2)	The algorithmic comparisons between the existing stochastic sampling methods and GTTE can be helpful to understand the differences and their pros and cons.  

review_title: Authors proposed graph traversal via tensor functionals (GTTE) for easing the implementation of diverse graph algorithms and enabling transparent and efficient scaling to large graphs. It can be specialized to obtain various existing graph representation learning models. 

Meta-review: Summary: The authors propose to approximate operations on graphs, roughly
speaking by approximating the graph locally around a collection of
vertices by a collection of trees. The method is presented as a
meta-algorithm that can be applied to a range of problems in the
context of learning graph representations.

Discussion: The reviews are overall positive, though they point out a
number of weaknesses. One was unconvincing experimental
validation. Another, more conceptual one was that this is a 'unifying
framework' rather than a novel method. Additionally, there were a number of
minor points that were not clear. However, the authors have provided
additional experiments that the reviewers consider convincing, and
were able to provide sufficient clarification.

Recommendation:
The reviewer's verdict post-discussion favors publication, and I
agree. The authors have convincingly addressed the main concerns in discussion, and novelty is not a necessity: Unifying frameworks often seem an end in themselves, but this one is
potentially useful and compellingly simple.

Decision: Accept (Poster)