Title: HEBBIAN GRAPH EMBEDDINGS

Abstract: Representation learning has recently been successfully used to create vector representations of entities in language learning, recommender systems and in similarity learning. Graph embeddings exploit the locality structure of a graph and generate embeddings for nodes which could be words in a language, products of a retail website; and the nodes are connected based on a context window. In this paper, we consider graph embeddings with an error-free associative learning update rule, which models the embedding vector of node as a non-convex Gaussian mixture of the embeddings of the nodes in its immediate vicinity with some constant variance that is reduced as iterations progress. It is very easy to parallelize our algorithm without any form of shared memory, which makes it possible to use it on very large graphs with a much higher dimensionality of the embeddings. We study the efficacy of proposed method on several benchmark data sets in Goyal & Ferrara (2018b) and favourably compare with state of the art methods. Further, proposed method is applied to generate relevant recommendations for a large retailer.

1. INTRODUCTION:

Graph embeddings learn vector representations of nodes in a graph. [Cai et al. (2018) ] and [Goyal & Ferrara (2018b) ] give a comprehensive survey of graph embedding methods like node2vec [Grover & Leskovec (2016) ] and also deep convolutional embeddings. The advantage of learning low dimensional embeddings is that they induce an order on the nodes of a graph which could be authors in a citation network, products in a recommender system, or words in an text corpus. The order could be established using an inner product or using another machine learning algorithm like a neural network or a random forest.

Our method uses error-free associative learning to learn the embeddings on graphs. The algorithm is quite simple, but very effective. We apply the learnt embeddings to the task of recommending items to users and to the task of link prediction and reconstruction.

Label propagation and message passing have been applied to many tasks like feature propagation [Heaukulani & Ghahramani (2013) ], interest propagation, propagation of information in a population [Rapoport (1953) ] and other network models of behavior like PageRank [Page et al. (1999) ] and models of text like TextRank [Mihalcea & Tarau (2004) ]. Instead of propagating a single unit of information, we propagate entire embeddings across the network. By propagating information on a graph iteratively, long distance similarities can also be learnt.

For link prediction and reconstruction, our results are directly comparable to [Goyal & Ferrara (2018b) ]. We compare our results from the state of the art results in [Goyal & Ferrara (2018b) ] in tables 1,5,6,7 and find that our result has significantly better results as compared to the techniques implemented in [Goyal & Ferrara (2018b) ] and [Zhang & Chen (2018) ] like SEAL, VGAE [Kipf & Welling (2016) ], node2vec [Grover & Leskovec (2016) ], GF (graph factorization) [Ahmed et al. (2013) ], SDNE [Wang et al. (2016) ], HOPE [Ou et al. (2016) ], and LE [Belkin & Niyogi (2002) ]. Our method is similar to LLE [Roweis & Saul (2000) ] (we compare with algorithms that were developed after LLE) and our algorithm takes inspiration from simulated annealing which is theoretically sound and it iteratively reduces the global variance, and thus is able to outperform all of these algorithms. Note that LLE uses a loss function while our method is an instance of errorless learning which, as the results show, is more effective and embarrassingly parallelizable.

Annealing is a process that takes steel in a furnace from a very high temperature to gradu-ally cooling to lower temperatures. This creates a self-organizing process that improves the ductility properties of steel. A high temperature implies higher variance. We take inspiration from this process in this paper in which initially, the variance is very high and is gradually reduced with the goal that the network gains more structure and finds a stable state after the iterations complete [Kirkpatrick et al. (1983) ].

2. HEBBIAN GRAPH EMBEDDINGS:

Hebbian learning is the simplest form of learning invented by Donald Hebb in 1949 in his book The organization of behavior [Hebb (1949) ]. It is inspired by dynamics of biological systems. A synapse between two neurons is strengthened when the neurons on either side of the synapse (input and output) have highly correlated outputs. In essence, when an input neuron fires, if it frequently leads to the firing of the output neuron, the synapse is strengthened. In simple terms: "neurons that fire together wire together" [Hebb (1949) ]. Recently, there's renewed interest in Hebbian learning. [Keysers & Gazzola (2014) ] postulates that Hebbian learning predicts mirror-like neurons for sensations and emotions. [Treur (2016) ] applies Hebbian learning in modelling of temporal-causal network.

Hebbian learning consists of a parameter update rule which is based on the strength of connection between two nodes, as applied to neural networks (based on firing tendencies of neurons on the opposite ends of a synapse). We extend the idea to graphs. Based on a pre-computed transition probability between two nodes, we update the parameters (the embeddings of a node) iteratively based on an error-free associative learning rule (nodes that are contextually connected should have similar embeddings, like word2vec for words [Mikolov et al. (2013)] ). For a discussion on errorless learning, please see [McClelland (2006) ].

We first initialize all embeddings to a multivariate normal distribution with mean 0 and variance σ 2 .

EQUATION

We model the embedding at a node as a non-convex Gaussian mixture of the embeddings of the connected nodes. If there is an edge from node i to node j, the embedding of node j is modeled as follows:

EQUATION

The variance σ 2 starts off at a value of 10 and is divided by 1.1 every iteration in the spirit of simulated annealing [Kirkpatrick et al. (1983) ]. The embedding of node j is updated as follows:

EQUATION

EQUATION

w j = w j + δ j (5)

The δ j are then simply added to the embedding at node j (where there is an edge from node i to node j). p ij is the transition probability and η is the learning rate. The graph is weighted, asymmetric and undirected. Also, a random negative edge is selected at each node and the negative of the embeddings is propagated to both selected nodes with a fixed transition probability (we use 0.5). This iterative procedure learns the embeddings of all nodes in the graph and is able to generate very effective embeddings, as the next section shows. As shown in figure 1 , the embeddings get propagated across the Gaussian graph iteratively. for each node j in Adj(i) do wi ∼ N(w i , σ 2 I) (6)

p ij = (#(i - → j))/(#i)

EQUATION

end for 13:

end for σ 2 ← σ 2 /τ (8) 14:

end for 15: end procedure

3. EXPERIMENTS AND RESULTS:

We run our algorithm on three of the data sets used in [Goyal & Ferrara (2018b) ] namely AstroPh, BlogCatalog and HepTh for both link prediction and reconstruction. Our algorithm outperforms several other algorithms that are implemented in [Goyal & Ferrara (2018b) ] and [Goyal & Ferrara (2018a) ]. We also compare our algorithm for link prediction using average precision and run-time with SEAL [Zhang & Chen (2018) ] and VGAE [Kipf & Welling (2016) ] in table 6 and table 7.

We start with an initial variance σ 2 of 10 and use the variance reduction factor τ of 1.1. We run the algorithm for 10 iterations. The algorithm is shown in Algorithm 1.

Link Prediction is the task of trying to predict a link between two nodes that were not part of the training data. Reconstruction tries to reconstruct the entire graph which is used entirely in the training set (i.e. there is no train/test separation). We also run our algorithm on our recommender system and find that it is able to achieve a very high hit rate. Future work will focus more on the recommender system.

3.1. RESULTS ON RECONSTRUCTION:

We ran our algorithm for reconstruction on publicly available data sets. Reconstruction tries to reconstruct the entire original graph (without splitting into train/test). As in [Goyal & Ferrara (2018b) ], we sample 1024 nodes for calculation of the MAP. We run the algorithm for 10 iterations with a learning rate 1.0. The results in table 1, table 2 and figure 2 show that our algorithm is able to achieve good results on reconstruction when the dimensionality is large. As benchmarks, we use three data sets that [Goyal & Ferrara (2018b) ] uses for reconstruction. Our results are favorably comparable on those three data sets. The other data sets are not used by [Goyal & Ferrara (2018b) ] but the supporting code base as in [Goyal & Ferrara (2018a) ] can be used to compare.

3.2. RESULTS ON THE RECOMMENDER SYSTEM OF A LARGE RETAILER:

Also, in the recommender system at a large retailer, we used a sample of 200 thousand items as our population for training and measurement. 10% of the users are held out as the test set. The number of nodes in the graph is 200,000 and the number of edges is about 13.1 billion (note that the weight of an incoming edge might be different from an outgoing edge between any two nodes).

We measure the performance of our algorithm on the hit rate. Top 10 recommendations are generated per item based on the nearest neighbors of the generated embeddings based on an inner product (using all 200,000 items). Then, one random item from the users entire interaction history is chosen.

Recommendations for this random item are computed. If any of the top 10 recommended items (other than the seed item) also occurs in the users interaction history, it is considered a hit. Otherwise a fail. The average hit rate is then the number of successes divided by the number of users in the test set. Results are shown in table 4. We use 10 iterations and a learning rate of 1.0.

The edges are determined using the induced graph from the consumer-product bipartite graph based on the co-viewing of the products. So, if two products were viewed by the same consumer, then we create an edge between them based on the same p ij weight between them (as described in section 2). 

3.3. RESULTS ON LINK PREDICTION:

For link prediction, we use some of the data sets used in [Nickel & Kiela (2017) ] and [Goyal & Ferrara (2018b) ]. As in [Goyal & Ferrara (2018b) ], we sample 1024 nodes for calculation of the MAP. We keep 10% of the edges as a held out test set. We run the algorithm for 10 iterations with a learning rate 1.0. The results in table 8, table 9 and figure 3 show that our algorithm is able to achieve good results on link prediction when the dimensionality is large. As benchmarks, we use three data sets that [Goyal & Ferrara (2018b) ] uses for link prediction. Our results are favorably comparable on those three data sets for link prediction. [Goyal & Ferrara (2018b) ] also has a supporting code base [Goyal & Ferrara (2018a) ] which can be used to compare on other data sets.

We also compare our algorithm with SEAL and VGAE and find that our algorithm outperforms VGAE on all four data-sets and outperforms SEAL on one of the four data-sets. Note that since our algorithm is an Apache Spark application, there is some initial time spent on initialization and allocation of resources. The larger the graph, the more noticeable is the difference in the run-time. For instance, it might be infeasible to run SEAL or VGAE on our recommender system data-set with 200,000 nodes and 13.1 billion edges.

It is quite easy to parallelize the algorithm, and we implement it on Apache Spark. We run the algorithm for 10 iterations (which takes about 3 hours on the parallel implementation on recommender system data and from 5 minutes to 2 hours (depending on the dimensionality) on the publicly available data). We found that the learning rate does not affect the results in any significant way (we use 1.0).

4. CONCLUSION:

In this paper, we described a simple, but very effective algorithm to learn the embeddings on a graph. The results show that the algorithm, as applied to the tasks of link prediction and reconstruction, is able to perform well when the dimensionality of the embeddings is large. This shows the effectiveness of learning on graphs using iterative methods. Its a useful experiment of error-free (errorless) learning on graphs. Our method can learn long distance similarities because of the iterative nature of the algorithm which percolates the embeddings on the weighted graph.

A distinctive advantage of our approach is that it is very easy to parallelize the algorithm without any need for shared memory. It is quite easy to implement the algorithm on platforms like Apache Spark, which makes the algorithm amenable to very large graphs which cannot be processed on one machine.

Our recommender system work was tested live and it did very well. But because our item graph has a very large number of nodes and edges, we omit the implementation of [Nickel & Kiela (2017) ] and [Goyal & Ferrara (2018b) ] for our recommender system.

Other algorithms like in [Vinh et al. (2018) ] and [Chamberlain et al. (2019) ] could be compared with our work. There is still an opportunity to improve the algorithm through hyperparameter tuning. It might be interesting to measure the algorithm with a much higher dimensionality of the embeddings. 

:



Figures and Tables:

Figure 1: Propagation of Embeddings Across a Graph

MAP Comparison with State of the Art for Reconstruction (see[Goyal & Ferrara (2018b)])

Table content: <table><tr><td>Algorithm</td><td colspan="2">Dimensionality AstroPh</td><td>BlogCatalog</td><td>HepTh</td></tr><tr><td colspan="2">Hebbian Graph Embeddings 200</td><td>0.573</td><td>0.499</td><td>0.619</td></tr><tr><td>node2vec</td><td>256</td><td>0.56</td><td>0.24</td><td>0.42</td></tr><tr><td>GF</td><td>256</td><td>0.29</td><td>0.09</td><td>0.39</td></tr><tr><td>SDNE</td><td>256</td><td>0.46</td><td>0.33</td><td>0.5</td></tr><tr><td>HOPE</td><td>256</td><td>0.33</td><td>0.45</td><td>0.32</td></tr><tr><td>LE</td><td>256</td><td>0.26</td><td>0.09</td><td>0.4</td></tr></table>

Mean Average Precision (MAP) results for network embeddings for Reconstruction of the entire graph

Table content: <table><tr><td>DataSet</td><td>Nodes</td><td>Edges</td><td/><td colspan="5">Reconstruction Results of Varying Dimensionality</td></tr><tr><td/><td/><td/><td>10</td><td>20</td><td>50</td><td>100</td><td>200</td><td>300</td><td>400</td><td>500</td></tr><tr><td>CondMat</td><td>23,133</td><td>93,497</td><td colspan="6">0.192 0.304 0.495 0.649 0.778 0.838 0.873 0.895</td></tr><tr><td>GrQc</td><td>5,242</td><td>14,496</td><td colspan="6">0.245 0.407 0.625 0.763 0.860 0.894 0.910 0.918</td></tr><tr><td>HepPh</td><td>12,008</td><td colspan="7">118,521 0.196 0.293 0.455 0.586 0.698 0.755 0.789 0.814</td></tr><tr><td>AstroPh</td><td>18,772</td><td colspan="7">198,110 0.181 0.245 0.362 0.461 0.573 0.635 0.675 0.707</td></tr><tr><td>HepTh</td><td>27,770</td><td colspan="7">352,807 0.188 0.261 0.402 0.509 0.619 0.679 0.709 0.732</td></tr><tr><td colspan="2">BlogCatalog 10,312</td><td colspan="7">333,983 0.432 0.432 0.458 0.491 0.499 0.507 0.508 0.496</td></tr></table>

Random Mean Average Precision (MAP) results (no training) for network embeddings for

Table content: <table><tr><td>Reconstruction</td><td/><td/><td/></tr><tr><td>DataSet</td><td>Nodes</td><td>Edges</td><td>Random (no training)</td></tr><tr><td/><td/><td/><td>500 (Dimension)</td></tr><tr><td>CondMat</td><td>23,133</td><td>93,497</td><td>0.0139</td></tr><tr><td>GrQc</td><td>5,242</td><td>14,496</td><td>0.0126</td></tr><tr><td>HepPh</td><td>12,008</td><td colspan="2">118,521 0.0233</td></tr><tr><td>AstroPh</td><td>18,772</td><td colspan="2">198,110 0.0255</td></tr><tr><td>HepTh</td><td>27,770</td><td colspan="2">352,807 0.0292</td></tr><tr><td colspan="2">BlogCatalog 10,312</td><td colspan="2">333,983 0.0364</td></tr></table>

Results on a very large graph for recommender systems at a large retailer

Table content: <table><tr><td>Dimensionality</td><td>HitRate@10</td></tr><tr><td>100</td><td>24.2%</td></tr><tr><td>200</td><td>30.1%</td></tr><tr><td>250</td><td>31.1%</td></tr></table>

MAP Comparison with State of the Art for Link Prediction (see[Goyal & Ferrara (2018b)])

Table content: <table><tr><td>Algorithm</td><td colspan="2">Dimensionality AstroPh</td><td>BlogCatalog</td><td>HepTh</td></tr><tr><td colspan="2">Hebbian Graph Embeddings 200</td><td>0.317</td><td>0.202</td><td>0.339</td></tr><tr><td>node2vec</td><td>256</td><td>0.025</td><td>0.17</td><td>0.04</td></tr><tr><td>GF</td><td>256</td><td>0.15</td><td>0.02</td><td>0.17</td></tr><tr><td>SDNE</td><td>256</td><td>0.24</td><td>0.19</td><td>0.16</td></tr><tr><td>HOPE</td><td>256</td><td>0.25</td><td>0.07</td><td>0.17</td></tr><tr><td>LE</td><td>256</td><td>0.21</td><td>0.04</td><td>0.23</td></tr></table>

Comparison of Average Precision with other State of the Art algorithms for Link Prediction (see[Zhang & Chen (2018)] for more details), randomly chosen 10% of edges held out as the test set

Table content: <table><tr><td>Algorithm</td><td>Power</td><td>PB</td><td>USAir</td><td>C.Ele</td></tr><tr><td colspan="2">Hebbian Graph Embeddings 93.11</td><td>93</td><td>95.92</td><td>84.99</td></tr><tr><td>SEAL</td><td>86.69</td><td>94.55</td><td>97.13</td><td>88.81</td></tr><tr><td>VGAE</td><td>75.91</td><td>90.38</td><td>89.27</td><td>78.32</td></tr></table>

Comparison of Run-Time (seconds) for Link Prediction (see[Zhang & Chen (2018)] for more details)

Table content: <table><tr><td>Algorithm</td><td>Power</td><td>PB</td><td>USAir</td><td>C.Ele</td></tr><tr><td colspan="2">Hebbian Graph Embeddings 287</td><td>233</td><td>237</td><td>172</td></tr><tr><td>SEAL</td><td>1640</td><td>146</td><td>31</td><td>16</td></tr><tr><td colspan="5">Benjamin Paul Chamberlain, Stephen R Hardwick, David R Wardrope, Fabon Dzogang, Fabio</td></tr><tr><td>Daolio, and Saúl Vargas.</td><td colspan="3">Scalable hyperbolic recommender systems.</td><td>arXiv preprint</td></tr><tr><td>arXiv:1902.08648, 2019.</td><td/><td/><td/><td/></tr></table>

Mean Average Precision (MAP) results for network embeddings for Link Prediction (10% randomly chosen edges are held out as the test set)

Table content: <table><tr><td>DataSet</td><td>Nodes</td><td>Edges</td><td/><td colspan="5">Link Prediction Results for Varying Dimensionality</td></tr><tr><td/><td/><td/><td>10</td><td>20</td><td>50</td><td>100</td><td>200</td><td>300</td><td>400</td><td>500</td></tr><tr><td>CondMat</td><td>23,133</td><td>93,497</td><td colspan="6">0.070 0.130 0.251 0.350 0.450 0.507 0.531 0.544</td></tr><tr><td>GrQc</td><td>5,242</td><td>14,496</td><td colspan="6">0.064 0.129 0.233 0.292 0.332 0.348 0.363 0.383</td></tr><tr><td>HepPh</td><td>12,008</td><td colspan="7">118,521 0.065 0.121 0.213 0.289 0.346 0.384 0.401 0.424</td></tr><tr><td>AstroPh</td><td>18,772</td><td colspan="7">198,110 0.060 0.092 0.179 0.235 0.317 0.357 0.388 0.409</td></tr><tr><td>HepTh</td><td>27,770</td><td colspan="7">352,807 0.070 0.120 0.203 0.259 0.339 0.370 0.383 0.407</td></tr><tr><td colspan="2">BlogCatalog 10,312</td><td colspan="7">333,983 0.183 0.182 0.198 0.198 0.202 0.217 0.210 0.212</td></tr></table>

Random Mean Average Precision (MAP) results (no training) for network embeddings for

Table content: <table><tr><td>Link Prediction</td><td/><td/><td/></tr><tr><td>DataSet</td><td>Nodes</td><td>Edges</td><td>Random (no training)</td></tr><tr><td/><td/><td/><td>500 (Dimension)</td></tr><tr><td>CondMat</td><td>23,133</td><td>93,497</td><td>0.007</td></tr><tr><td>GrQc</td><td>5,242</td><td>14,496</td><td>0.007</td></tr><tr><td>HepPh</td><td>12,008</td><td colspan="2">118,521 0.010</td></tr><tr><td>AstroPh</td><td>18,772</td><td colspan="2">198,110 0.009</td></tr><tr><td>HepTh</td><td>27,770</td><td colspan="2">352,807 0.009</td></tr><tr><td colspan="2">BlogCatalog 10,312</td><td colspan="2">333,983 0.014</td></tr></table>

Peer review (iclr2020):
[Summary] This paper proposes an error-free rule update method for graph embedding. The authors employ the Hebbian learning concept iteratively using the pre-calculated transition probability. They evaluate their model on six benchmark datasets. [Pros] - Very simple and fast by using an error-free update rule. [Cons] - The introduction is not organized. What are the motivation, related work, and contribution? - No comparison with conventional methods such as PageRank and NN-based models such as SEAL [1] and VGAE [2]. Even if this method is not learning-based, the proposed model should be compared. - The authors claimed they applied their model to real recommendation systems. But there is no specific information. At least, the author describes what is recommended, the data size, how large performance is improved, etc. - It is required to be evaluated on conventional datasets. - Ablation on sigma [1] M. Zhang and Y Chen, Link Prediction Based on Graph Neural Networks, NIPS 2018. [2] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.