Hebbian Graph Embeddings
Authors: Shalin Shah
Venkataramana Kini
Venue:  (2020)
Keywords: graph embeddings
hebbian learning
simulated annealing

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 on 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 favorably compare with state of the art methods. Further, proposed method is applied to generate relevant recommendations for a large retailer.

Under review as a conference paper at ICLR 2020
HEBBIAN GRAPH EMBEDDINGS
Anonymous authors Paper under double-blind review
ABSTRACT
Representation learning has recently been successfully used to create vector repre- sentations 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 language, products of 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 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 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.
INTRODUCTION
Graph embeddings learn vector representations of nodes in a graph. [Cai al. [2018) and [Goyal & Ferrara [2018b)] give a comprehensive survey of graph embedding methods like node2vec [rrover & Leskovee (2016) and also deep convolutional embeddings. The advantage of learning low di- mensional embeddings is that they induce an order on the nodes of a graph which could be authors in a citation network, products
recommender system, or words in an text corpus. The order could be established using an inner product or using another machine learning algorithm like 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 popula- tion |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 single unit of information, we propagate entire embeddings across the network. By propagating information on graph iteratively, long distance similarities can also be learnt.
For link prediction and reconstruction, our results are directly comparable to [Goyal & Ferrara [. We compare our results from the state of the 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 [Goyal& & Ferrara (2018b) and [Zhang & Chen [0118] like SEAL, VGAE (Kipf & Welling (2016) node2vec [Grover& & Leskovec (2016)). GF (graph factorization) [Ahmed al. (2013). SINE [Wang et al. (2016). HOPE [Ou al. (2016)). and LE [Belkin & Niyogi (2002) J. 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, the results show, is more effective and embarrassingly parallelizable.
Annealing is process that takes steel in furnace from very high temperature to gradu-

---

Under review as a conference paper at ICLR 2020
ally cooling to lower temperatures. This creates 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 al. [1883)]
HEBBIAN GRAPH EMBEDDINGS
Hebbian learning is the simplest form of learning invented by Donald Hebb in 1949 in his book inspired by dynamics of biological systems. A
The organization of behavior [Hebb] [.49)]. 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, frequently leads to the firing of the output neuron, the synapse is strengthened. In simple terms: "neurons that fire together wire together" [Hebb] [1.49]]. Recently, there's renewed interest in Hebbian learn- ing. [Keysers & Gazzola [2014 postulates that Hebbian learning predicts mirror-like neurons for sensations and emotions. network.
(1949)
(Treur (2016) applies Hebbian learning in modelling of temporal-causal
Hebbian learning consists of a parameter update rule which is based on the strength of connection between two nodes, as applied neural networks (based on firing tendencies of neurons the opposite ends of a synapse). We extend the idea to graphs. Based on pre-computed transition probability between two nodes, we update the parameters (the embeddings of 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 discussion on errorless learning, please see [McClelland (2006)]
We first initialize all embeddings to multivariate normal distribution with mean and variance a².
wy ~ 020
(1)
We model the embedding node as non-convex Gaussian mixture of the embeddings of the connected nodes. If there an edge from node to node j. the embedding of node j is modeled as follows:
Wi N(w;, 021)
(2)
The variance 2² starts off value of 10 and is divided by 1.1 every iteration in the spirit of simulated annealing (Kirkpatrick et al. al. (1983)] The embedding of node j is updated as follows:
W. N(w;, o
(3)
8, Σ Wi * Pij *
(4)
Wy = wi + 63
(5)
The 8, are then simply added to the embedding at node j (where there is an edge from node i to node j). Pij is the transition probability and r) is the learning rate. The graph 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 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.
Piy (# (++)
2

---

Under review as a conference paper at ICLR 2020
A
N(C,
N(C,a
D
N(A,0*1)
N(D.of1
C
F
N(E,o*I)
N(B.o*I)
N(C.o*1
N(E.o*I)
N(F,o*
B
E
N(B.o*I)
Figure 1: Propagation of Embeddings Across Graph
Algorithm Hebbian Graph Embeddings
procedure FINDEMBEDDINGSICC)
2: Inputs: Weighted, asymmetric and undirected graph with nodes as nodes (1,2.... P) and
edge weights as transition probabilities between nodes Pij
3: Hyper-parameters:
4: o² Variance normal distribution (initial value = 10)
5:
N Number of iterations of Hebbian learning
6: K Dimensionality node representation
7:
Variance reduction factor (value 1.1)
8: Initialization: Initialize the nodes representation wy by sampling from a zero mean multi- variate normal distribution ((0, a² for each integer m in N do for each node in P do for each node j in (dj do
of dimensionality K
9:
11:
W. N(W,, I²I)
(6)
Wj - Wj + m/WiPi
(7)
12:
end for end for
13:
0² + 02/T
(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 (20185) and [Goyal & Ferrara [2018a]]. We also compare our algorithm for link prediction using average precision and run-time with SEAL Zhhagg & Chen (2018) and VGAE Kipp & Welling (2016) in table 6 and table 7.
We start with an initial variance o² of 10 and use the variance reduction factor of 1.1. We run algorithm for 10 iterations. The algorithm is shown Algorithm
Link Prediction is the task of trying to predict a link between two nodes that were not part of the training data. Reconstruction tries reconstruct the entire graph which is used entirely in the training set (i.c. there is no train/test separation).

---

Under review as a conference paper at ICLR 2020
Table 1: MAP Comparison with State of the Art for Reconstruction (see [Goyal & Ferrara (2088b 8b]]
Algorithm
Dimensionality AstroPh
BlogCatalog
HepT
Hebbian Graph Embeddings
200
0,573
0.499
0.619
node2vec
256
0.56
0.24
0.42
GF
256
0.29
0.09
0.39
SDNE HOPE
256
0,46
0.33
0.5
256
0.33
0,45
0.32
LE
256
0.26
0.09
0.4
Table 2: Mean Average Precision (MAP) results for network embeddings for Reconstruction of the entire graph
DataSet
Nodes
Edges
Reconstruction Results of Varying Dimensionality
10
20
50
100
200
300
400
500
MondMat
23,133
93,497
0.192
0.304
0.495
0.649
0.778
0.838
0.873
0.895
GrQe
5,242
14,496
0.245
0.407
0.625
0.763
0.860
0.894
0.910
0.918
HepPh 12,008
118,521
0.196
0.293
0,455
0.586
0.698
0.755
0.789
0.814
AstroPh
18,772
198,110
0.181
0.245
0.362
0.461
0.573
0.635
0.675
0.707
HepTh 27,770
352,807
0.188
0.261
0,402
0.509
0.619
0.679
0.709
0.732
BlogCatalog
10,312
333,983
0,432
0.432
0.458
0.491
0.499
0.507
0.508
0.496
We also run our algorithm on our recommender system and find that is able to achieve very high hit rate. Future work will focus more the recommender system.
3.1 RESULTS ON RECONSTRUCTION
We ran our algorithm for reconstruction on publicly available data sets. Reconstruction tries to re- construct 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 itcrations with learning rate 1.0. The results in table 1, table 2 and figure 2 show that algorithm is able to achieve good results on reconstruction when the dimensionality is large. As benchmarks, we use three data sets that [Goyal & Ferraral (2018b)] uses for reconstruction. Our results are favorably comparable on those three data sets. The other data sets are not used by [Goyal & Ferrara (0018)) but the supporting code base in [Goyal & Ferrara [208abb can be used to compare.
3.2 RESULTS ON THE RECOMMENDER SYSTEM OF LARGE RETAILER
Also, in the recommender system at large retailer, we used a sample of 200 thousand items as our population for training and measurement. 10% of the users held out as the test 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
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 hit. Otherwise a fail. The average hit rate is then the number successes divided by the number users in the test set. Results are shown in table 4. We use 10 iterations and learning rate of 1.0.
The edges are determined using the induced graph from the consumer- on the co-viewing of the products. So, if two products were viewed by the same consumer, then create an edge between them based on the same Pij weight between them (as described in section 2).
consumer-product product bipartite graph based

---

Under review as a conference paper at ICLR 2020
Table 3: Random Mean Average Precision (MAP) results (no training) for network embeddings for Reconstruction
DataSet
Nodes
Edges
Random (no training)
500 (Dimension)
CondMat
23,133
93,497
0.0139
GrQc
5,242
14,496
0.0126
HepPh
12,008
118,521
0.0233
AstroPh
18.772
198,110
0.0255
HepTh
27,770
352,807
0.0292
BlogCatalog
10,312
333,983
0.0364
MAP vs Dimensionalitt for Reconstruction
0.9
0.8
Average Precision
0.6
0.3
CondMat
GrQc
HepPh
AstroPh
HepTh
BlogCatmlog
0.1
50
100
150
200
250
300
350
400
450
500
Dimensionality
Figure 2: Mean Average Precision for Reconstruction with Varying Dimensionality.
3.3 RESULTS ON LINK PREDICTION
For link prediction, we use some the data sets used [Nickel & Kiela (2017)) and [Goyal & Ferrara (2018))] As in [Goyal & Ferrara (2018b)), sample 1024 nodes for calculation of the MAP. We keep 10% of the edges as held out test set. We run the algorithm for 10 iterations with learning rate 1.0. The results in table table 9 and figure 3 show that 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 [2018)) uses for link prediction. Our results are favorably comparable on those three data sets for link prediction. [Goyal & Ferrara (2018b)] also has supporting code base [Goyal Ferrara [018a)] which can be used to compare on other data sets.
We also compare our algorithm with SEAL and VGAE and find that our algorithm outper- of the four data-sets. Note that
forms VGAE all four data-sets and outperforms SEAL 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, might be infeasible to run SEAL or VGAE on our recommender system data-set with 200,000 nodes and 13.1 billion edges.
is quite easy to parallelize the algorithm, and we implement on Apache Spark. We run the algo- rithm for 10 iterations (which takes about 3 hours the parallel implementation recommender
5

---

Under review as a conference paper at ICLR 2020
Table 4: Results very large graph for recommender systems large retailer
Dimensionality
HitRate
100
24.2%
200
30.1%
250
31.1% 1%
Table 5: MAP Comparison with State of the Art for Link Prediction (see |Goyal & Ferrara (2018b
Algorithm
Dimensionality
AstroPh
BlogCatalog
HepTh
Hebbian Graph Embeddings
200
0.317
0.202
0.339
node2vec
256
0,025
0.17
0.04
256
0.15
0.02
0.17
SDNE
256
0.24
0.19
0.16
НОРЕ
256
0.25
0.07
0.17
LE
256
0.21
0.04
0.23
system data and from 5 minutes hours (depending the dimensionality) the publicly avail- able 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, described a simple, but very effective algorithm 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 ness of learning 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.
the embeddings is large. This shows the effective- graphs using iterative methods. Its useful experiment of error-free (errorless)
distinctive advantage our approach is that it is very easy to parallelize the algorithm without any need for shared memory. It is quite easy implement the algorithm 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 very large number of nodes and edges, omit the implementation of (Nickel & Kiela (207))
and [Goyal & Ferrara [2018)]] for our recommender system.
Other algorithms like in Vinh al. 2018)] and [Chamberlain al. 20] could be compared with our work. There is still an opportunity to improve the algorithm through hyperparameter tuning. might be interesting to measure the algorithm with a much higher dimensionality the embeddings.
REFERENCES
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd inter- national conference on World Wide Web, pp. 37-48. ACM, 2013.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chhan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering, 3069):611-1133, 2018

---

Under review as a conference paper at ICLR 2020
Table 6: Comparison of Average Precision with other State of the Art algorithms for Link Prediction (see [Zhang & Chen (018)] for more details), randomly chosen 10% of edges held out as the test
Algorithm
Power
PB
USAir
C.Ele
Hebbian Graph Embeddings
93.11
93
95.92
84.99
SEAL
86.69
94.55 90.38
97.13 89.27
88.81
VGAE
75.91
78.32
Table 7: Comparison of Run-Time (seconds) for Link Prediction (see more details)
(Zhagg & Chen (0188) for
Algorithm
Power
PB
USAir
C.Ele
Hebbian Graph Embeddings
287
233
237
172
SEAL
1640
146
31
16
Benjamin Paul Chamberlain, Stephen R Hardwick, David Wardrope, Fabon Dzogang, Fabio Daolio, and Saúl Vargas. Scalable hyperbolic recommender systems. arXiv preprint 1rXiv:1902.08648, 2019.
Palash Goyal and Emilio Ferrara. Gem: A python package for graph embedding methods. Open Source Software, 3729):876, 2018a.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Bort Based Systems, 151:78-94, 2018b.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864. ACM, 2016.
Creighton Heaukulani and Zoubin Ghahramani. Dynamic probabilistic models for latent feature propagation in social networks. In International Conference on Machine Learning, pp. 275-283, 2013.
Donald Olding Hebb. The Organization of Behavior. Wiley Sons, 1949.
Christian Keysers and Valeria Gazzola. Hebbian learning and predictive mirror neurons for actions, sensations and emotions. Philosophical Transactions of the Royal Society B: Biological Sciences, 369(1644::201307555 2014.
Thomas N Kipf and Max Welling. arXiv:1611.07308 2016.
Variational
graph auto-encoders.
arXiv preprint
Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. science, 220(459))671-669,, 1983.
James L McClelland. How far can you go with hebbian learning, and when does it lead you astray? Processes of change in brain and cognitive development: Attention and performance xxi, 21: 33 23-69,20 2006.
Rada Mihalcea and Paul Tarau. Textrank: Bringing order into text. In Proceedings of the 2004 conference on empirical methods in natural language processing, pp. 401411, 2004.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word represen- tations in vector space. arXiv preprint arXiv: 1301.378... 2013.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in neural information processing systems, pp. 6338-6347, 2017.
7

---

Under review as a conference paper at ICLR 2020
Table 8: Mean Average Precision (MAP) results for network emheddings for Link Prediction (10%
randomly chosen edges are held out as the test set)
DataSet
Nodes
Edges
Link Prediction Results for Varying Dimensionality
100
200
300
400
500
MondMat
23,133
93,497
0.070
0.130
0.251
0.350
0.450
0.507
0.531
0.544
GrQe
5,242
14,496
0.064
0.129
0.233
0.292
0.332
0.348
0.363
0.383
HepPh 12,008
118,521
0.065
0.121
0,213
0.289
0.346
0.384
0.401
0.424
AstroPh
18,772
198,110
0.060
0.092
0.179
0.235
0.317
0.357
0.388
0,409
HepTh 27,770
352,807
0.070
0.120
0,203
0.259
0.339
0.370
0.383
0.407
BlogCatalog
10,312
333,983
0.183
0.182
0.198
0.198
0.202
0.217
0.210
0.212
Table 9: Random Mean Average Precision (MAP) results (no training) for network embeddings for Link Prediction
DataSet
Nodes
Edges
Random (no training)
500 (Dimension)
CondMat
23,133
93,497
0.007
GrQc
5,242
14,496
0.007
HepPh
12,008
118,521
0.010
AstroPh
18,772
198,110
0.009
HepTh 27,770
352,807
0.009
BlogCatalog
10,312
333,983
0.014
Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserv- ing graph embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1105 1105-11144 1114. ACM, 2016.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Anatol Rapoport, Spread of information through population with socio-structural bias: I. assump- tion of transitivity. The bulletin of mathematical biophysics, 15(4):523-533, 1953.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embed- ding. science, 290(5500):2323- 23222236...2222 2000.
Jan Treur. Network-oriented modeling. Springer, 2016.
Tran Dang Quang Vinh, Yi Tay, Shuai Zhang, Gao Cong, and Xiao-Li Li. Hyperbolic recommender systems. arXiv preprint arXiv: /00.::/03000000.33. 2018.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 1225-1234. ACM, 2016.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
8

---

Under review as a conference paper at ICLR 2020
MAP vs Dimensionality for Link Prediction
0.5
0.45
Average Precision
0.35
0.25
0.2
CondMat
GrQc
HepPh
HepTh
BlogCammog
0.05
50
100
150
200
250
300
350
400
450
500
Dimensionaliit
Figure 3: Mean Average Precision for Link Prediction with Varying Dimensionality.


Reviews:
[{"review_id": "rJeTak3J5r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Thanks to the authors for their response. There are still significant issues with motivation, writing, and baseline comparisons (the latter noted by R3). I would encourage the authors to continue to polish and investigate their method and submit to a future conference. \n\n=====\n\nThis paper proposes an approach to learning embeddings associated with nodes in a graph. Inspired by Hebbian learning, the representations of a node are iteratively updated to be similar to representations of its neighbors. The update is performed by adding a scaled vector sampled from a Gaussian centered on a neighbor's representation to the current node's vector. After learning, the embeddings may be used for tasks such as graph reconstruction, link prediction, or product recommendation.\n\nContributions include:\n* Proposal of an approach to learn embeddings of nodes in a graph in which representations of a node are updated by scaled and Gaussian-perturbed versions of its neighbors' representations.\n* Experiments demonstrating reconstruction and link prediction performance of the proposed approach on several datasets, as well as product recommendation perfomance on a large retail dataset.\n  \nThere are several significant concerns with the paper as it currently stands. The three most pressing issues are as follows:\n1. The proposed algorithm is not situated relative to related work.\n2. The paper does not provide the reader with enough details or precision to be able to replicate the work.\n3. Experiments do not compare to any baselines other than random embeddings.\n  \nThe paper suggests that the proposed algorithm is a form of Hebbian learning because the representation of nearby nodes in the graph are encouraged to be similar. However, this idea has long been used for learning node embeddings (for example, LLE encourages representations of a node to be predicted as a linear combination of neighboring nodes). The connection seems loose other than a superficial similarity in the update rule and naming the algorithm after Hebbian learning is somewhat misleading.\n\nThe algorithm is reminiscent of message-passing inference in a continuous Markov random field with pairwise potentials encouraging nearby nodes to have similar representations. I am not an expert in graph embedding approaches, but I would be surprised if the approach could not be easily related to classical approaches such as MDS or LLE.\n\nThere are several notational/clarity issues:\n* j is used for both the node index and the embedding of the node itself (equation 1-2). Replacing the j on the left hand side with w_j would resolve ambiguity and bring the equations in line with Algorithm 1.\n* Equation 2 is inconsistent with equation 1 because they both specify different distributions over the same embedding. Framing equation 1 as an initialization and equation 2 as providing the conditional distribution p(w_j | w_i) may make the situation clearer.\n* Equation 3 is a mixture of Gaussian distributions, yet \\delta_j is a vector added to the current node embedding. Instead, first write \\tilde{w}_i as a sample from the Gaussian and then let \\delta_j be the weighted sum of the samples.\n* Equation 3 is not consistent with equations 4-5. Equation 3 suggests that a node is updated by summing over neighbors and then applying the update. But Algorithm 1 suggests that nodes are updated based on only a single neighbor at a time.\n* What does it mean when the negative embedding is propagated with a small transition probability? This should be described mathematically.\n* It is misleading to call the graph a Gaussian hierarchy, since a hierarchy implies that certain nodes are higher than others.\n* How are the \"transition probabilities\" set for an unweighted graph? Specifically, the GrQc dataset doesn't appear to have edge weights.\n* What values of the variance and \\tau hyperparameters were used?\n* How are reconstructions and link predictions computed?\n  \nExperimentally, the proposed approach is not compared to any baselines other than random embeddings. The claim made in the paper that the method compares favorably is thus not backed up by results. The results in section 3.2 should be described in greater detail. If the items are nodes, then how are edges and weights determined?\n\n Other specific comments:\n* What is the connection between the current work and hyperbolic geometry of Nickel & Kiela (2017)? The proposed algorithm does not rely on hyperbolic geometry so this seems like a non sequitur.\n* Algorithm 1: Rather than describing the algorithm in terms of the intended application (products), it would be useful to describe it in general terms and then use retail products as specific application.\n* Figures 2 and 3 are not particularly useful. The most important information for the reader or practitioner is how various methods compare on the same dataset, not how a single method performs across different datasets.\n  \nQuestions for the authors:\n* How is the proposed algorithm similar/different to related approaches for learning node embeddings?\n* What are baseline results for related algorithms on the datasets experimented upon?\n* What is the role of the variance scaling? How do the results change if the variance is reduced to 0 immediately after random initialization?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJg_uTZ15B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nThis 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.\n\n[Pros]\n- Very simple and fast by using an error-free update rule.\n\n[Cons]\n- The introduction is not organized. What are the motivation, related work, and contribution?\n- 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.\n- 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.\n- It is required to be evaluated on conventional datasets.\n- Ablation on sigma\n\n[1] M. Zhang and Y Chen, Link Prediction Based on Graph Neural Networks, NIPS 2018.\n[2] Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv:1611.07308, 2016.\n\n ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "B1eMMi63FB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors proposed a simple but effective node embedding method for large-scale graphs. \nThe proposed method is based on Hebbian learning, enhancing the connections between neighbor nodes iteratively. \nThe idea is very straightforward and suitable for large-scale applications. \nThe authors tested the proposed method on multiple real-world datasets under different configurations.\n\nThe strategy of the work makes sense to me, but the work itself is incomplete. \nAs mentioned in the conclusion, there are some potential competitors of the proposed method, which should be considered as baselines in the experiments. \nAdditionally, for conceptual proof, the authors can consider a synthetic/real-world dataset with relatively small size and compare their method with state-of-the-art methods.\n\nAdditionally, the notations in Eqs. (1-3) are inconsistent with those in Algorithm 1. Especially Eq.(3), delta_j should be an incremental vector of node j’s embedding, while N(I, sigma^2 I) is a distribution. The authors should write Eqs. (1-3) as Eqs. (4-6).", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper learns an embedding on the nodes of the graph, iteratively aligning the vector associated to a node with that of its neighbor nodes (based on the Hebbian rule). 

The reviews state that the approach is interesting though very natural/straightforward, and that it might go too far to call it "Hebbian" (Rev#2) - you might want also to see it as a Self-Organizing Map for graphs. 

A main criticism was about the comparison with the state of the art (all reviewers). The authors did add empirical comparisons with the suggested VGAE and SEAL, and phrase it nicely as "our algorithm outperforms SEAL on one out of four data sets". Looking at the revised paper, this is true: the approach is outperformed by SEAL on 3 out of 4 datasets.

Another criticism regards the insufficient analysis of the results (e.g. through visualization, studying the clusters obtained along different runs, etc). 
This aspect is not addressed in the revised version.

An excellent point is the scalability of the approach, which is worth emphasizing.

I thus encourage the authors to rewrite and polish the paper, improving the positioning of the proposed approach w.r.t. the state of the art, and providing a more thorough analysis of the results.


Decision: Reject