Watch Your Step: Learning Node Embeddings via Graph Attention
Graph embedding methods represent nodes in a continuous vector space, preserving different types of relational information from the graph. There are many hyperparameters to these methods (e.g. the length of a random walk) which have to be manually tuned for every graph. In this paper, we replace previously fixed hyperparameters with trainable ones that we automatically learn via backpropagation. In particular, we propose a novel attention model on the power series of the transition matrix, which guides the random walk to optimize an upstream objective. Unlike previous approaches to attention models, the method that we propose utilizes attention parameters exclusively on the data itself (e.g. on the random walk), and are not used by the model for inference. We experiment on link prediction tasks, as we aim to produce embeddings that best-preserve the graph structure, generalizing to unseen information. We improve state-of-the-art results on a comprehensive suite of real-world graph datasets including social, collaboration, and biological networks, where we observe that our graph attention model can reduce the error by up to 20%-40%. We show that our automatically-learned attention parameters can vary significantly per graph, and correspond to the optimal choice of hyperparameter if we manually tune existing methods.
The paper proposes a new algorithm for learning node embedding, by bringing together the attention model and the graph likelihood objective function suggested in a recent work [2]. By learning the context distribution determining the coefficients of powers of the transition matrix, it leads to a more flexible representation learning model.  Quality:  Although the technical content of the paper seems to be correct, I would like to point out some issues in the paper: - In Line 121, the sentence "In practice, random walk methods based on Deepwalk do not use $C$ as a hard limit" is not generally correct because many methods (such as Node2vec) perform fixed length walks.  - Although the proposed method is described  using the random walk concept, it computes the expected value of the number of node pair occurrences in a length $c \sim \mathcal{U}(1,C)$ by applying matrix multiplication. On the other hand, Deepwalk or Node2vec implicitly approximate it, by performing only a limited number of random walks. Therefore, I think it could be also better to see its performance against the methods such as HOPE.  - In classification, only two datasets have been used. I would strongly recommend  to examine the performance of the method over different training and test sizes.  - In the Table b of Figure 1, the figures for ca-AstroPh and ca-HepTh are not depicted. Those results are important to better understand the behavior of the proposed method: in Table 1, Graph Attention uses windows size of $C=10$ but node2vec uses $C=2$ or $C=5$.  - Although experimental results are given with standard deviation for the Graph Attention method, in Table 1 only mean scores are shown for the other methods.  - Is the proposed method scalable for large networks? This is a very important question, since the proposed algorithm performs matrix factorization.  Clarity: I think the paper is well-organized and quite readable. In the beginning, the authors shortly mention two previous works on "Attention Models" and "Graph Likelihood", and then they introduce the proposed method by incorporating ideas from the above two methodologies. However, I would like to make some suggestions for the notation used in the paper:  - Between lines 29-30, the symbol $C$ is used to indicate the length of the walk and the italic $\mathcal{C}$ is also used to denote the context distribution but it can be confused with the other notation $C$.  - In Line 63, the expression "$|E|$ non-zero entries" is not correct. For example the adjacency matrix of a simple graph have $2|E|$ non-zero entries due to symmetry.  - In line 72, if $E[v_i]$ are the outgoing edges from $v_i$ then $sample(E[v_i])$ returns an edge and not a node -- so it could be better to define $E[v_i]$ as the neighbourhood of vertex $v_i$.  - In line 121, the sentence "In practice, random walk methods based on Deepwalk do not use $C$ as a hard limit" is not generally correct because many methods such as Node2vec perform fixed length walks.  Originality: The authors extend a previous work on the “graph likelihood objective” [2] with the Attention Model, and the proposed method outperforms the state-of-the-art baselines for the link prediction task.  Significance: This work incorporates the attention model with the "graph likelihood" objective function proposed by a recent work [2], in such a way that it enables to learn context distribution which is used in the paper to compute the expected value of the number of co-occurrences of nodes. Although the context distribution corresponds to the coefficients of the powers of the transition matrix, I believe that the same idea can be applied for different models. The experiments for node classification appear to be insufficient to evaluate the model, but the suggested method shows significant improvements for the link prediction task.