Benchmarking and Analyzing Unsupervised Network Representation Learning and the Illusion of Progress
Authors: Saket Gurukar
Priyesh Vijayan
srinivasan parthasarathy
Balaraman Ravindran
Aakash Srinivasan
Goonmeet Bajaj
Chen Cai
Moniba Keymanesh
Saravana Kumar
Pranav Maneriker
Anasua Mitra
Vedang Patel
Venue: Accepted by TMLR ()

Abstract: A number of methods have been developed for unsupervised network representation learning -- ranging from classical methods based on the graph spectra to recent random walk based methods and from deep learning based methods to matrix factorization based methods. Each new study inevitably seeks to establish the relative superiority of the proposed method over others. The lack of a standard assessment protocol and benchmark suite often leave practitioners wondering if a new idea represents a significant scientific advance. In this work, we articulate a clear and pressing need to systematically and rigorously benchmark such methods. Our overall assessment -- a result of a careful benchmarking of 15 methods for unsupervised network representation learning on 16 non-attributed graphs (several with different characteristics) - is that many recently proposed improvements are somewhat of an illusion when  assessed through the lens of downstream tasks such as link prediction and node classification. Specifically, we find that several proposed improvements are marginal at best and that aspects of many of these datasets often render such small differences insignificant, especially when viewed from a rigorous statistical lens. A more detailed analysis of our results identify several new insights: first, we find that classical methods, often dismissed or not considered by recent efforts, can compete on certain types of datasets if they are tuned appropriately; second, we find that from a qualitative standpoint, a couple of methods based on matrix factorization offer a small but not always consistent advantage over alternative methods; third, no single method completely outperforms other embedding methods on both node classification and link prediction tasks. Finally, we also present several analysis that reveals settings under which certain algorithms perform well (e.g., the role of neighborhood context and dataset properties that impact performance). An important outcome of this study is the benchmark and evaluation protocol, which practitioners may find useful for future research in this area. 

Published in Transactions on Machine Learning Research (06/2022)
Benchmarking and Analyzing Unsupervised Network Repre- sentation Learning and the Illusion of Progress
Saket Gurukar' The Ohio State University
gurukar. Gosu.
Priyesh Vijayan"
priyess.vviogymmmmmilmmmmm
McGill University and Mila
Srinivasan Parthasarathy The Ohio State University
srint@cce.ohio--fe edu
Balaraman Ravindran
ravi@cse. wwtpi/sseeimmm...m oc in
Indian Institute of Technology, Madrus; Robert Bosch Centre for Data Science and AT
Aakash Srinivasan
s.oakash3331 @gmaiil com
University of California, Los Angeles
Goonmeet Bajaj
bujaj.32@osu. edu
The Ohio State University
Chen Cai
cicai@ucsd. edu
University of California, San Diego
Moniba Keymanesh, Saravana Kumar, Pranav Maneriker
keymanesh. @8osuesshh.@sseee.e
savkumar90@gmmiilccomo com, maneriker. &osu. edu Ohio State University
Anasua Mitra
omasuamittr220055@@maaaa.cc com
Indian Institute of Technology, Guwahati
Vedang Patel
patel.1140@oss edu
The Ohio State University
Reviewed on OpenReview: https: opwnrevveee. net/ forum? id= GuFFkt9tXX
Abstract
number methods have been developed for unsupervised network representation learning ranging from classical methods based on the graph spectra to recent random walk based methods and from deep learning based methods to matrix factorization based methods. Each new study inevitably seeks to establish the relative superiority of the proposed method over others. The lack of a standard assessment protocol and benchmark suite often leave practitioners wondering a new idea represents significant scientific advance. In this work, we articulate a clear and pressing need to systematically and rigorously benchmark such mothods. Our overall assessment a result of a careful benchmarking of 15 methods for unsupervised network representation learning different characteristics). is that many recently proposed improvements somewhat of an illusion when assessed through the lens of downstream tasks such link prediction and node classification. Specifically, we find that several proposed improvements are marginal at best and that aspects of many of these datasets often render such small differences insignificant,
16 non-attributed graphs (several with
Fiirst authors contributed equally this work.

---

Published in Transactions on Machine Learning Research (06/2022)
especially when viewed from rigorous statistical lens. A more detailed analysis of our results identify several new insights: first, we find that classical methods, often dismissed or not considered by recent efforts, can compete on certain types of datasets if they are tuned appropriately; second, we find that from a qualitative standpoint, a couple of methods based on matrix factorization offer a small but not. always consistent advantage over alternative methods; third, no single method completely outperforms other embedding methods on both node classification and link prediction tasks. Finally, we also present several analysis that reveals settings under which certain algorithms perform well (e.g., the role of neighborhood context and dataset properties that impact performance). An important outcome of this study is the benchmark and evaluation protocol, which practitioners may find useful for future research in this area.
1 Introduction
Graphs are effective in multiple disparate domains to model, query, and mine relational data. Examples abound, ranging from the use of nearest neighbor graphs in machine learning (Bhatlacharyya & Kalita
2013
Nickel et al. 2016) and database systems (Epsttein et al. 1997 Zhao & Saligrama 2009) to the
analysis of biological networks [ensoo et al.] 2016 Yue et al. 2019) and from social network analysis (Gu
jet al. 2017 Zhang et al. 2017) to the analysis of transportation networks (Cetinkaya et al.) 2015). Graph
or network representation learning seeks to realize a vector representation of each node the graph (or the
graph as a whole) for use in downstream applications such as graph-based recommendation systems (Ying
et al.] 2018a; Waan al. 2018), learning molecular fingerprints for drug discovery and cheminformatics
(Duvenaud et al.) 2015 Lusci et a...
2013).
knowledge graphs (Wang et al. 2014 Zhang et al. 2019
anomaly detection (Zhao & Saligrama, 2009 Liang et al. 2018b) and entity resolution (Cohen & Richman
2002 Geloor & Machanavajjhala, 2012)) 2). Fundamental to such applications is the use of classilication or
predictive methodology based on the underlying representation.
Given the potential applications, a plethora of new network representation learning methods have been proposed recently (See Cai et al. (2018); Hamilton et al. (2017b) for a comprehensive survey). Given the number of such methods, it is difficult for a practitioner to determine or understand which of these methods they should consider adopting for particular task on particular dataset. The lack of a standard assessment methodology, makes it difficult to also understand if newer methods truly reflect a scientific advance or if it is simply an illusion of progress (Hand) 2006). Developing a good assessment methodology is both important and daunting.
Lack of a Standard Evaluation Protocol: First, the efficacy among embedding methods is often eval- uated based on downstream machine learning tasks such as node classification and link prediction. There is no standard evaluation protocol involving common set of datasets to evaluate the performance on such lasks, which can lead to inconsistent and inconclusive reporting of results. For example, logistic regression is commonly used to evaluate node embeddings" quality for classification, but grid-search over logistic re- gression parameters is rarely conducted or reported. In our experiments on Blogcatalog, we find that with a train-test split of 50:50 the Laplacian Eigenmaps method (Belkin & Niyogi, 2003) without Grid-Search achieves a Macro-f1 score of 3.9% (similar to what was reported in (Goyal & Ferrara 2018 Grover & Leskoved 2016)). However, by tuning the sypee-parameters.. we find that the Laplacian Eigenmaps method achieves Macro-F1 of 29.2% (also reported elsewhere (Tang & Liu 2011)). Similar examples hold for other tasks (e.g. link prediction). Our task setup, preprocessing of dalasets and evaluation details are described in Section G
Careful Tuning Of Comparative Methods: Second, a new method almost always compares its perfor- mance against other methods on a subset of lasks and datasets previously evaluated. In many cases, while great care is taken to tune the new method (via careful ssper-parameter tuning) the same care is often not taken when evaluating basclines. For example, the parameters of Deepwalk, such as the number of walks, walk length, and window size are often set to default or fixed values (Grover & Leskovee, 2016 Cao et al.
2015 Qiu et al. 2018 Tang et al. 2015 Tsitsulin et al. 2018 Wang et al. 2016a Kipf & Welling 2016), and
2

---

Published in Transactions on Machine Learning Research (06/2022)
grid search is rarely reported over those Deepwalk parameters (Tang & Liu 2011 Additionally, reported results are rarely averaged over multiple shuffles to ameliorate bias effects ! In short, lack of consistency in evaluation inhibits our understanding of the scientific advances in this arena.
Evaluation on Task-Specific Baselines: Third, for many lasks such node classification and link prediction, there is rich pre-existing literature (Bhagat et al,, 2011 Lü & Zhou 2011) focused on such tasks (that do not explicitly rely on node embedding methodology of the prior art in network representation learning consider such baselines often, such methods compare performance on downstream machine learning tasks against other graph embedding methods.
preprocessing step). Few, if any,
Contributions: To summarize, there is clear and pressing need for comprehensive and careful bench- marking of such methods, which is the focus of this study. We perform experimental study of 15 promising network embeddings methods on 16 diverse non-attributed graphs to address the aforementioned issues in the network embedding literature. The selected embedding methods are unsupervised techniques (many of which have been widely cited) to generate the node embeddings of a graph. Our goal is to perform a uniform, principled comparison of these methods on various datasets and across the two most commonly evaluated tasks link prediction and node classification.
1. Our most important observation is that progress in this area is somewhat of an illusion (viewed from a rigorous statistical lens), especially since the advent DeepWalk (Perozzi et al., 2014). Specifi- cally, on the node classification task, not a single method surveyed offers statistically significant advantage over Deep Walk. We find that couple of methods offer a slight but statistically significant improvement for the link prediction task. In contrast, none of the other methods surveyed offers an advantage over DeepWate Walk.
2. The task-specific baselines we create are simple and efficient. On the link prediction task, these baselines are competitive with many recent methods (outperformed only by MNMF (Wang et al. 2017) and WYS (Abu-El-Haija et al.) 2018)). The task-specific baseline for node classification is competitive on certain types of datasets (datasets with few labels). Other recent methods perform worse on both the lasks than these baselines on a few datasets, suggesting that future researchers on these tasks should consider these task-specific baselines.
3. We present several drill-down analyses that reveal settings under which specific algorithms perform well (e.g,, the role of neighborhood context on performance; dataset characteristics that influence performance). We also examine two common ways in which link prediction strategies are evaluated (explicitly through classifier, or implicitly through vector dot-product ranking). We find that the former is always preferred.
An important outcome of this study is the benchmark and evaluation protocol, which practitioners
may find useful for future research in this area.
2 Notation & Problem Definition
We denote the input graph as = (V, where V and E denote the set of nodes and edges of the graph, G. The notations used in this work are listed in Table [ In this study, consider both directed as well as undirected graphs along with weighted as well as unweighted graphs. We evaluate the embedding methods on non-attributed, homogeneous graphs.
Network Embedding: Given a Graph, 9 = EV,E) and an embedding dimension, where d < |/V,, the goal of network embedding method to Iearn a d-dimensional representation of each vertex (V) of the graph, & such that similarity between vertices in graph space approximates to closeness between them in d-dimensional space.
3

---

Published in Transactions on Machine Learning Research (06/2022)
Symbol
Description
A, D,
Adjaceney, Degree and Identity Matrix Node, Window size, Context window Node and Context embedding of node Node and context embedding matrix Label, neighbor and number of neighbors of node Indicator function
Vn w,T
((u), (u)
U,
lus No. [Nul
I
(ol(G)
Sum of weights of all edges
b A
Number of negative samples
Graph Similarity matrix
(x)
Sigmoid function
H
Binary community membership matrix
C
Latent representations of communities
B
Modularity matrix
P
D
Laplacian ==
List, L2nd
Loss functions to preserve first-order and sccond-order proximitics Graph Convolutional Network
GCN
X
Node features
q
Attention parameter vector
E[
Expectation of the random walk matrix
NS
Negative Sampling Distribution.
N, M
Number of nodes and negative samples, respectively Alternate graph as defined in DGI Velickovic et. al. (019 Features of Graph A and Alternate Graph A
X, X
s
Summary vector of Graph.
h; h4
Hidden representation the node in original and alternate graph
Table 1: The notations table.
3 Network Embedding methods
The methods considered in our study are shown in Table 2 These represent a broad spectrum of classic, popular and recent methods. Due to space limitation, we only present the objective functions of the methods.
The notations present in the objective function are defined in Table [ Interested readers are encouraged
refer (Belkin & Niyogi 2003 Perozzi al. 2014
Grover Leskovec 2016 Cao et al.
2015
Qiu et al. 2018
Wang et al. 2017 Ou et al.
2016
Tang al. 2015 Tsitsulin al.] 2018 Wang et al. 201 (6a
Kipl Welling,
2016 Abu-El-Haija et al. 2018 Hamilton et al. 2017a Velickovic et al 2019 Huang et al.) 2021), for the
details about the embedding methods. In the experimental comparison of embedding methods, it becomes critical to reproduce the experimental results. A short summary of the embedding methods are shared in
the appendix Section B To facilitate reproducibility we note the grid search parameters for each method and provide the source code of our evaluation scripts at httpp///////tto.oo//////////////
A common parameter for all the embedding methods is the embedding dimension. In this study, we vary the embedding dimensions [64, 128, 256] and report the best result for the downstream task. On datasets with <300 nodes, limit the embedding dimensions to 64 and 128. The method-specific parameter values for grid-search are shared in the Table
There are several interesting network embedding methods that utilize node features (Hassani & Khasahmadi 2020 Peng et al. 2020 Mo et al. 2022 Liu et al. 2022). survey of such methods including the use of self- supervised learning presented (Lu al. 2022). However, note that unsupervised network representation methods often operate on non-attributed graphs [Lekkovec) 2022 Hamilton 2020) and therefore the methods in Liu et al. LLu et al. 2022 falls out of the scope of evaluation. Similarly, other interesting network
Ihis is observation based evaluation scripts publically shared by multiple authors.
4

---

Published in Transactions on Machine Learning Research (06/2022)
Method
Objective function
Reproducibility Notes
Manifold- method
minimize 0
trace(U**LU)
Taplarian Rigemaps
the datasets with 2-M nodes, Laplacian Rigenmaps did not seale embedding dimen- sion 128, 256.
subject to U DU =I
Belkin Niyogi
2003
Random walk based methods
DeepWalk
minimisce log Pr((e--n Ve ((va))
Walk length [5. 20, 40). Number of walks = [20, 40, 80/, Window size = [2, 4, 10). In the case directed graphe, we treat directed graphs as undirected for DeepWalk for im- proved performance.
Perozzi et sl. 2014
Vede2Vec
minimizeg - loo Pr((te-wi Re " ((r)))
Walk length = [5, 20, 40). Number walks 80. Window Size = 10, and q = (0.25, 1, 2. 4J. case directed graphs, we treat directed gruphs as undirected for Node2Vec improved performance.
Griver Leskowee 2016
Matrix factorization based methods
()( = log or (+)() (()))
GraRep
Σ A A. logo(----ii ++e"))
à from to On the datasets with >2M edges, due to scalability issue, we searched for & from to 2 and Embedding dimension = [64, 128).
Cao et al.
2015
NetMF
log vol( ( D-1) logb
[1, 10), Negative samples [], 3). Rank for large context window [128, 256, 512]
Qiu al.
0 min
15 Vt
+ + | UC* 1
MNMF
0.1. 1.0, 10.0), $ [0.1, 1.0, 10.0)
-Btr(II BTT) -||III1 11/
Wang et al. 2017
HOPE YOu et sl.
2016
man 5 0'
The decay parameter Ø = 0.5/a. a is sot to the spectral radius the graph. We use the weighted Katz as the similarity messure.
Edge reconstruction based method
ménimize
Σ
Aua log ((
(W
LINE (Tang et al.
2015
Σ (N.))R
Aua log Evera (u)
eap ((p(
Number of samples = 10 billion. In the case of directed graphs, as suggested by the authors of LINE, we evaluate only second-order prox- imity.
Node similarity based method Evey (L(simale, )Il simp(e.))
Verse
PageRank damping factor [0.7, 0.85, 0.9). Negative samples
[3, 10).
Tsitsulin et al. 2018
Deep neural network based methods
SDNE
Loontt aLis Land ufeeg
[1e005 05, 0.2), Penalty coefficient. [5, 10]
Wang
2016a.
VAG
A 0 o (C
Hidden layens size
[128, 256]
Kipf & Welling 2016
min R.S
f1111 E.D: g) (U
Watch Your Step
Number Hops
1/1 = 0| log(1 a(U . V'
Abu-Ci-Hlafja et al. 2018
Table continued on the next page...
5

---

Published in Transactions on Machine Learning Research (06/2022)
Method
Objective function
Reproducibility Notes
Table continued from the previous page...
Unsupervisad--Crpllie
[ogl o(v)) X. Fiu NS logla(-o(u)" o(w))
Walk length 15, 20, 40,, Number walks [20, 40, 80]
(Unsup_ GS) Hamilton al.
7a
Bix,A Bog s(h,,s)]
N + M
DGI Velickovic et al. 2019
Number layers- 2. 3), Hidden layer size (64,2[6 and with and without freezing gradient flow for I/p embedding and GCN for the negutive notwork
(x Bog (1 D(b,,
RW franework Humnng et al. 2021
Factorization or Sampling
Markov tine = [3, 50, 100] Similarity = l'au- tocovriiance' 'PMI") Algurithm = ['Gactor ixation", "sampling"]
log edd(w.))
L(() Σ
EV'NN c doaeet
Polncaré Huang et al. 2021
(w.))E
Number of negatives = [10, 30, 50, 70, 90), Manifolds= [Poincare, Loreuta), Mod- els [Distance, Energy)
11 d(u. v) arccosh (1 (11 1|ul 1P13)
The embedding methods evaluated in our study, See Table 1 for objective function notation key. The following code bases were in Python: Laplacian Eigenmaps, Deep GraRep, NetMF, MNMF, HOPE, SDNE, VAG, WYS, Unsupervised GraphSage, DGI and RW-framework. The following code bases were in C or C++: Node2Vec, Verse, LINE. All are widely used code bases typically from the original authors. For methods that leverage a learning rate parameter, we varied across following rates 0.1, 0.5, 1.0]. For methods that lever epochs parameter, we varied across following number of epoch values [50, 100).
Table 2:
embedding methods (Hassani & Khasahmadi] 2020 Peng et al. 2020; Mo et al. 2022 that require node
attributes are not considered in our evaluation.
Alternatively there are some interesting network embedding methods that focuses on imposing constraints on the embedding space (Nickel & Kicla 2017: 2018) and do not require node attributes. For instance, Nickel et al. NNckel & Kiela, 2017 2018) propose learning the node embeddings in the hyperbolic space instead of euclidean space. We evaluate and include such methods in our empirical analysis.
Other machine learning downstream tasks such as learning fair node embeddings (Agarwal et al. 2021 or performing graph classification Togninalli et. al. (2019); Ying el al. (2018b) have recently received significant attention. For instance, Agarwal et. al (Agarwal et al. 2021 learns node embeddings in an efficient and fair manner. However such methods require sensitive attributes to both be present and pre-identified and is therefore not applicable to our setting. Other works Togninalli et al. (2019) : Ying et al. (2018b) focus on learning the graph representations for tasks such as graph classification. However, in this work, we mainly focus on two downstream tasks: node classification and link prediction tasks. The generic prepossessing of adjacency matrix has also boen explored (Klicpera et al.J 2019). GCC (Kliepora et al.] 2019) introduces a generic two-step pre-processing that recommends the usage of a sparsified higher-order transition matrix (Page rank and Heat diffusion) instead of the original adjacency matrix. Such methods rely substituting simple transition matrix with a higher-order transition matrix for graph convolutions in GNNs. We do not include GCC method in our evaluation as it is not standalone embedding method and focuses on preprocessing the adjacency matrix.
4 Related Work & Feedback
Related Work: Network representational learning has attracted lot of attention in the past few years. Recent surveys (Cai et al. 2018 Hamilton et al. 2017b; Zhang et al.) 2018a) attempt to categorize or laxonomize these efforts along various axes but they do not ofler an empirical analysis of the embedding methods. Slightly prior to our study, we were aware of one other excellent empirical study of network embedding methods (Goyal & Ferrara 2018). However, there are significant differences between this effort and ours. First, our systematic study encompasses over 375,000 individual experiments, on a larger set of embedding methods, including several more recent ideas and on many more datasets (16 7) than the
6

---

Published in Transactions on Machine Learning Research (06/2022)
previous study. Specifically, we evaluate 15 embedding methods + 2 efficient heuristics on 16 datasets. Second, we carefully tune all hyperparameters of each method as well as the logistic classifier (and include this information in our reproducibility notes). As a concrete example of where such careful tuning can make a difference consider that on Blogcatalog with a train-test split of 50:50, Goyal et al. (Goyal & Ferrara, 2018), achieve a Macro-Il score of 3.9% while with tuning the hyper-parameterss of logistic regression we achieve a Macro-fl score of 29.2%. Third, our analysis reveals several important insights on the role of context, the role of different link prediction evaluation strategies (dot product vs classifier), the impact of non-linear classifiers, and many others. All of these provide useful insights for end-users as well as guidance for future research and evaluation in network representational learning and downstream applications. Fourth, we also provide a comparison against simple but effective task-specific baseline heuristics which will serve as useful strawman methods for future work. Finally and perhaps most distinctively, we carefully analyze comparative performance through a careful grid search and rigorous statistical lens, pointing out that many recent advances are perhaps somewhat of an illusion this not a conclusion drawn from the previous effort.
Subsequent to our initial work, we also learned of another effort by Khosla el al. (Khosla et al. 2019) who conducted empirical bake-off of unsupervised network embedding methods and found that no single method always outperformed other methods a consistent message with both our work and that of Goyal et al. Gooaa & Ferrara 2018). The differences between our work and this work can be similarly outlined as above (comparative scale of experiments on a wider range of methods and datasets, detailed hyper-parameter tuning and comparison with task-specific heuristics). Again and perhaps most distinctively, the authors do not analyze comparative performance through a rigorous statistical lens or attempt to examine if recent research represents true advance or an illusion of progress. Both sets of authors also do not: i) study the impact of lincar non-linear classifier node classification task; ii) the difference between dot-product and classifier for link prediction lask; and iii) the impact of embedding mnmeesioon/mmeedddigg normalization on both node classification and link prediction tasks.
Community Feedback: After our initial work, we socialized and sought feedback within the database, data science and machine learning communities. We received several useful feedback on this work as follows.
It was suggested that we should include an unsupervised variant of Deep Graph Infomax (Velickovic et al.] 2019 in our study. We have added the experiments with DGI.
It was suggested that we should compare with some Graph Neural Network methods (Kipf & Welling, 2017). We note that Graph Neural Networks typically fall under the "semiisupervised learning' paradigm. However, we do perform experiments on unsupervised variants of Graph Convolutional Network proposed by Kipf & Welling (2016) and Velickovic et al. (019).
Finally we received several suggestions for additional experiments (see main results and appendix), evaluation on new datascts (c.g. Reddit), and positioning that has helped shape both the analysis and eventual presentation of results.
5 Datasets
Table 3 describes empirical properties of the datasets in our study, The datasets support both standard multi-class classification (each node is associated a single class label from among multiple class labels) as well as multi-label classification (a node can be associated with multiple class labels). Directed as well as undirected datasets are considered in order to evaluate the embedding methods on the link-prediction task efficiently. Further, datasets with and without edge weights are also included. The datasets exhibit varying levels of homogencity where homogeneity of a node (say u) is computed using the Jaccard function as HG( = ΣieN, (Jaccard((,, (4, 4)), where No represents the neighborhood set of u. Note this formulation naturally handles both multi-clase and multi-label datasets. The homogeneity value of a dataset is represented by the average homogeneily value of nodes in the dalaset. Note that for the publicly available Tube dataset [Zffarani & Liu 2009). we have node classes for only 2.7% nodes; hence we do not report
For the multi-class setting this is equivalent HG(u) EVEN. 1(uu == ==:===4,, Na) used elsewhere Ma et al.
2021

---

Published in Transactions on Machine Learning Research (06/2022)
Dataset
#N
#E
#L
(C/L)
D
W
CC
HI
SP
WebKB (Texas)
Craven et al.
1998
186
464
4
C
F
T
0.195
0.405
2.70E-02
WebKB (ornell)
Craven
1998
195
478
5
C
0.157
0.436
2.53E-02
WobKB (Wahiintonn)
Craven ot a
1998
230
596
5
C
0.197
0.470
2.26E-02
WebKB Wisconsin)
raven ct a..
098
265
724
5
C
0.208
0.437
2.07E-02
PPI (Breitkeeutz et ai. 2007
3,890
38,739
50
I.
F
F
0.242
0.109
5.12F-03
Wikipedia MMlhooeyy
2011
4,777
92,517
40
L
F
T
0.569
0.116
8.11K-03
Blogeatalog Zalarani Lim. 2009
10,312
333,983
39
L
0.463
0.145
6.28F-03
DBLP (Co-Authar Tang et al.
2008
18,721
122,245
3
C
0.833
0.453
6.98F-04
CoCit (Microsoft) Tsitsulin et
2018
44,034
195,361
15
C
F
F
0.142
0.423
2.02F-04
Wiki- Vote [Lekkvvec al. 2010
7,115
103,689
T
0.141
4. 40100-03
Pubmed Naamaa al. 2012
19,717
44,338
C
0.060
0.792
2.28F-04
p2p- Gnutella [Ripeanu Foster
2002
62,586
147,892
0.005
7.55E-05
Flickr (Zfaranii & Liu
2009
80,513
5,899,882
195
L
F
F
0.165
0.146
L82E-03
Epinions Richardson al.
2003
75,879
508,837
T
0.137
1.77E-04
YouTube Zalarani Liu
2009
1,134,890
.2987,624
C
0.081
4.64E-06
Reddit Hamillin el al.
2017a
231,443
11,606,919
41
C
0.169
0.818
4.33E-04
Table 3: Dataset Properties. Notations: Nodes(N), EEges(E), Labels (L), Multi-Class (C) Multi-Label (L),
Directed (D) and Weighted (W). Clustering coefficient (CC), Homogeneity (HG), and Sparsity (SP)
its homogeneity score in Table 3 For each dataset we also report its clustering coefficient commonly used measure of local (eeatty(Newann 2010). We also report sparsity for each dataset, defined as fraction of actual edges over number of maximum possible edges. The datasets span varions domains: Web (WebKB), Medical (PPI), Natural Language (Wikipedia), Social (Blogcatalog, Flickr, YouTube, Epinions), Citation (DBLP, CoCit, and Pubmed), Digital (p2p-Gnutell) and Voting (Wiki-vote). The datasets Wiki-vote, p2p- Gnutella, and Epinions do not contain node labels. Hence, on those datasets, we evaluate the embeddings methods only the link prediction task.
We next present the list of datasets and their prior use in evaluating unsupervised network representation learning methods: WebKB datasets (Wang et al.)
2017
2018 Jin et al. 2018 Mitra et al., 2020 Li et al.
Adhíkari et al.] 2018 Al-Sayouri et al. 2020 Wang et al.
2016bb. PPI
Grover & Leskovee, 2016 Qiu ct al.
2018 Abu-El El- Haija et al. |2188/ Alsentzer et al. [2200] Mitra et al.
2020
Epasto & Perozzi
2019). Wikipedia
Grover & Leskovee 2016 Qiu et al.] 2018 Tang et al.]
2015
Al-Sayouri et al. 20200 Mitra et al. 2020:
Cavallari al.
2017): Blogcatalog (Perozzi et al.] 2014
Grover Leskovec 2016 Cao al.
2015
Qiu al.
2018
Tang et al.
2015| Tsitsulin et al. 2018 Wang et al.
2016a Mitra et al.
2020 Qiu et al.
2018
Cavallari
et al.
2017 Li et
al. 2017), DBLP (Tsissulin et al.
2018 8
Cao et al. 201 Mitra et al.] 2020
Cavallan et al.
2017
Li et al. 2017 7) Microsoft Tsitsulin et al.]
2018
Mitra ct al.
2020
Wang et al.
2020
Spitz et al.
2018
1, Wiki (Abu-El-Haija et al.] 2018 Agrawal
et. al. 2013
Heidari
et al. 2015
Epasto & Perozzi
2019
Sun et al. 2019), Pubmed (Kipf & Welling 2016
Velickovic et al.
2019
Mitra et al.
2020
Wang et al.
2020
Flickr (Perozzi et al. 2014
2018: Cavallari | Grover & Leskovec
2016
Qiu ct al.
2018
Tang et al.
2015
Wang al.
6a
Li et al.]
al.] 2017 Li al.,
2017
P2P-Cnutella
(Tu et al.
2019b
Kim el al.
2018
Zhao al.
2013 Moon et al. 2020), Epinions
RRiharrsonn et al.
2003
Agrawal et al.
2013 Epasto
& Perozzi 2019 Li et al.
2017). Reddit (Hamilton et al.)
2017a]] /a| Chiang et al.
2019 Zhang et al. 2020 Liu
ct al.
2020 Velickovic et al. 2019) and YouTube (Perozzi et al.
2014 Tang et al. 2015 Tsitsulin et al.
2018
Wang et. al.) 2016a). While each dataset has been evaluated on several methods, there is not a single dataset common to all those efforts making it difficult to compare different network embedding methods meaningfully. Note that the focus of the the unsupervised network representation learning methods has primarily been on preserving the structure. Hence, these methods often operate on non-attributed graphs
[eskovee 2022 Hamilton 2020
6 Experimental setup
In this section, we claborate on the experimental setup for link prediction and node classification tasks employed to evaluate the quality of embeddings generated by different. methods. Additionally, also
8

---

Published in Transactions on Machine Learning Research (06/2022)
present two heuristics based basclines for both the tasks and define the metrics used for comparing the embedding methods.
6.1 Link Prediction
Prediction of ties is an essential task in multiple domains where the relational information is costlier to obtain such as drug-target interactions (Crichton et al. 2018). protein-protein interactions (Airoldi et al., 2006). or when the environment is partially observable. "Link prediction,
consists of inferring the existence
of new relationships or still unknown interactions between pairs of entities based on their properties and the currently observed links" (Martínez et al., 2016). In this work, we focus on the prediction of unknown interactions (links) between two nodes. The problem of predicting a tie/link between two nodes i and j is often evaluated in one of two ways. The first is to treat the problem as a binary classification problem. The second is to use the dot product on the embedding space as a scoring function to evaluate the tie's strength.
The edge features for binary classification consists node embeddings of nodes and j, where two node embeddings are aggregated with a binary function. In our study, we experimented with three binary functions on node embeddings: Concatenation, Hadamard and L2 distance. Node2vec (Grover & Leskovee 2016) also levered the binary functions Hadamard, and L.2 distance. We use Logistic Regression (LR) our base classifier for the task of link prediction. The parameters of the logistic regression are tuned using a grid search with 5-fold cross-validation. We evaluate the link prediction performance with metries: Area Under the Receiver Operating Characteristics (AUROC). An alternative evaluation strategy is to predict the presence of link (i.j) based on the dot product value of node embeddings of nodes i and j. We study the impact of both the evaluation strategies in Section 7.1
Construction of the train and test sets: The method of construction of train and test sets for link prediction task is crucial for comparing embedding methods. The train and test split consists of 80% and 20% of the edges, respectively, and are constructed in the following order:
1. Self-loops are removed.
2. We randomly select 20% of all edges as positive test edges and add them in the test set.
3. Positive lest edges are removed from the graph. We find the largest weakly connected component formed with the non-removed edges. The edges of the connected component form positive train edges.
We sample negative edges from the largest weakly connected component (C) and add the sampled negative edges to both the training and test sets where a negative edge is defined as (i,j) g C. The number of negative edges is equal to the number of positive edges in both training and test sets.
5. For directed graphs, we form "directed negative test edges" which satisfy the following constraint: (j,)) & C but (1,5) E C. where C' refers to edges in the largest weakly connected component. We add the directed negative test edges (j.)) edges to our test set. The number of "directed negative lest edges" is a parameter and in our experiments we set it to 10% of negative test edges in the test set.
Nodes present in the test set, but not present in the training set, are deleted from the test set. For learning the binary classifier, all the edges in the training set are considered positive train edges. We sample equal number of negative train edges from the training set. Edges from the training set as positive train edges and add an equal number of negative train edges
In the case of large datasets (>5M edges), we reduce our training set. We consider 10% of both randomly selected positive and negative train edges for learning the binary classifier. The learned model is evaluated on the test set. The above steps are repeated for 5 train:test splits of 80:20, and we report the average AUROC across 5 splits. The additional details about the folds are shared in appendix Section
As stated previously, our focus is on "unsupervised" network representation learning methods. We perform the grid scarch over the method parameters and get a score on the test split for all possible parameters in the grid. We report the best score from this search for each method. We note that such a strategy has been previously employed by others (see (Abu-al-Haaja et al. 2018 Huang et al.
Hyperparameter tuning:
9

---

Published in Transactions on Machine Learning Research (06/2022)
2021 Ou et al. 2016 Wang et al., 2017 The hyperparameters of the method are shared in Table 2 under
column "Reproduciblity Notes'.
The preprocessing procedure is visually described in the appendix C and the statistics of train:test splits of dataset shared in Table 4 and Table []] In brief, we consider five train:test splits of 80:20 rather than a single split and report the average performance over the five splits. Like all approaches in the literature we require the training graph to be connected. Specifically, following the approach of Gfyaa & Ferrara 2018)) we compute weakly connected component for identifying the connected training graph Goyal & Ferrara (0118). As an alternative, other methods remove set of edges from the original graph, while ensuring that the training graph remains connected Huang ct al. (2021).
Preprocessing procedure:
6.2 Node classification
In the network embedding literature, node classification the most popular way of comparing the quality of embeddings generated by different embedding methods. The generated node embeddings are treated node features, and node labels are considered as ground truth. The classification tasks performed in our experiments are either multi-label multi-class classification. The details on the classification task performed on each dataset are provided in Table 3 We select Logistic Regression as our classifier. We split the dataset with 50:50 train-test splits. In the case of large datasets (Flicckr and YouTuube), we split the dataset with 5:95 train-test splits based on labeled nodes. The learned model is evaluated on the test set, and we report the results averaged over 10 shuffles train-lest sets.
We noted that most of the efforts in the literature do not tune the ayper-parameters of Logistic Regression. Default parem-parameters with the LR classifier's default hyper-parameters, the Macro-f1 performance of Laplacian eigenmaps on the Blogcatalog dataset is 3.9% for the train-test split of 50:50. However, tuning the syper-parameters results in significant improvement of the Macro-fl score to 29.2%. In our experiments, we perform five-fold cross- validation with the following parameters of logistic regression: "inverse of regularization strength' C=|0.001, 0.01, 0.1, 1, 10, 100) and "norm used in the conalization"=111 and 'T.2"). We lever the logistic regression implementation provided by scikit-learn (Pedregosa al.) 2011]. We also explored Bayesian optimization for ident ifying the best Logistic Regression or EigenPro parameters with the help of auto-sklearn (Feurer et al. 2020). However, even given time budget of two days, the auto-sklearn results were rarely able to even match (never beat) the results computed with the grid-scarch suggesting that our grid search was comprehensive.
not always the best hyper-parameters for Logistic Regression. For instance,
The choice of a "linear" classifier to evaluate the quality of embeddings is not a hard constraint in the node classification task. In this work, we also test the idca of leveraging a "non-lincar" classifier for the node classification (ask and compare its performance to that of linear classifier We use the EigenPro (Ma & Belkin 2017) classifier as our non-linear classifier. EigenPro (Ma & Belkin 2017) provides significant performance boost over the state-of-the-art kernel methods with faster convergence rates on large datasets. In our experiments, we see up to 15% improvement in Micro-fl scores with non-linear classifiers compared to the linear classifier. (See Section 7.2 for details).
6.3 Task-Specific Baselines
Next, we present new baselines for both link prediction and node classification tasks. The purpose of defining such bascline is to assess the difficulty of different tasks on different datasct and compare the performance of sophisticated network embedding methods over simple heuristics.
6.3.1 Link Prediction Heuristic
In the link prediction literature, there exist multiple similarity-based metrics Lü & Zhou 2011 which can predict a score for link formation between two nodes. Examples of such metrics include Jaccard Index [Jaccard] 1901 Wang et al., 2007), Adamic Adar (Adamic & Adar 2003). These similarity-baser metrics often base their predictions on the neighborhood overlap between the nodes. We combine the similarity- based metrics to form curated feature vector of each edge (Sinha et al. 2018). The binary classifier in the link
10

---

Published in Transactions on Machine Learning Research (06/2022)
Heuristics
77.7
81.5
75.3
79.4
90.9
91.6
95.2
95.6
87.7
866.3
W-Texas
Laptig
83.5
89.6
W-Comell
DeepWalk
79.7
79.2
75.3
80.7
89.
90.9
97.4
94.3
96.0
89.1
871.6
W WaWshington
Node2Vec
83.0
82.0
75.0
78.0
88.3
90.9
97.6
95.0
95.4
89.3
874.6
VERSE
81.7
87.0
82.2
88 2
89.6
91.3
94.9 9
97.3
97.9
96.6
906.5
W-Wisconein
LINE
78.2
77.5
72.9
72.5
67.6
91.2
96.6
95.2
94.3
92.7
859.0
PPI
Gra
78.7
84.4
78.1
84.3
90.0
92.3
88.4
96.2
97
77.7
867.2
Wikipedia
HОPE
78.7
79.9
72.8
75.5
88.4
90.4
97.8
95.3
90.1
858.5
82.4
91.3
88.9
868.0
Wiki-Vote
NetMFF
BlogCatalog
MNMF
97.5
98.9
92.2
954.2
VAG
78.5
74.8
73.9
73.9
87.4
89.5
94.3
94.8
94 1
93.6
855.0
DBLP
WYS
83.0
64.4
79.2
84.5
91.5
92.3
98.2
96.0
96.8
97.0
903.0
Pubmed
Unsup_GS
78.4
80.4
75.0
82.3
87.1
89.0
92.1
93.5
95.9
85.8
859.5
DGI
73.8
63.4
70.3
6/.4
63.1
88.5
60
68.6
60
63.8
680.3
RW_framework
89.4
879.9
Poincare
(a) Smaller dalasets: All methods complete execution.
Heuristics
552.7
L
Microsoft
LapElg
95.6
69.9
93.0
90.9
96.0
96.1
541.4
P2P
DeepWalk
97.6
88.2
95.8
93.3
93.6
98.1
566.6
Flickr
Node2Vec
97.3 3
88.3
94.7
93.4
91.4
96.5
561.7
VERSE
83.7 7
77.6
91 g
97.6
99.3
522.8
Epinions
LINE
97.2
91.2
95.2
91.6
96.5
98.6
570.3
Youtube
GraRep
97.9
71.8
95.5
93.7
91.4
98.0
548.2
Reddit
HOPE
96.5
SDNE
83.9
93.0
361.5
NetMF
96.9
87.5
97.2
92.8
374.4
MNMF
96.6
92.3
188.8
VAG
96.2
96.2
WYS
0.0
Unsup_ce
95.7
76.4
86.0
88.5
92.9
96.5
536.0
DGI
0
56.0
111.0
RW_framework
97.5
93.5
549.7
Poincare
83.8
69.1
82,5
75.0
86.0
396.4
(b) Larger datasets: Not all methods complete execution.
Figure 1: Link Prediction performance measured with AUROC. The AUROC score is multiplied by 100 for better readability. Not all mothods are scalable on the datasets shown in Figure 16b
prediction task is then trained on these generated edge features. Our selected similarity- metrics are Common Neighbors (CN), Adamic Adar (AA) (Adamic & Adar 2003), Jaccard Index (JA) (Jaccard) 1901). Resource Allocation Index (RA) (Zhou et al. 2009) and Preferential Attachment Index (PA) (Barabási & Albert 1999). The similarity-bases basod motrics CN, JA, and PA, capture first-order proximity between nodes, while the metrics AA and R.A capture second-order proximity between nodes. We found this neuristic-basse model to be highly competitive when compared to the embedding methods multiple datasets.
6.3.2 Node Classification Heuristic
Nodes in the graph can be characterized (represented) by their properties. We combine the node properties form a feature vector (embedding) node. The classifier in the node classification task then trained on this node embedding. The node properties capture information such as nodes' neighborhood, influence on other nodes and their structural properties. We select. following node properties: Degree, PageRank (Page
11

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
Node2Vec
VERSE
Embeddiing methods
SONE
NetMF
GraRep
MNMF
VAG
WYS
Unsup
DG
RW wwwmmrewoork
Poincare
-0.25
0.25
AUROC score difference
Figure 2: Illusion of Progress I: Link Prediction: Box-plot represents the distribution of differences between AUROC of the embodding method and AUROC Deepwalk.
LapEig
Node2Vec
VERSE
Embedding methods
SONE
GraRep
HOPE
MNMF
WYS
Unsup GS
RW framework
Paincare
-0.4
-0.2
0.0
0.2
AUROC score difference
Figure 3: Illusion of Progress I: Link Prediction (dot product). Bax-plot represents the distribution of dif- ferences between AUROC of the embedding method and AUROC of Deepwalk.
ct al. 1999). Clustering Coefficient, Hub and Authority scores (Kleinberg) 1999), Average Neighbors' Degree, and Eccentricity (Newman 2010). We treat the graph as undirected while computing the node properties. As each node property's 's magnitude varies with another, we perform column- miimn-wisee wise normalization with Ro- bustScaler available from Seikit-learn. We show in the experiments Section 7.2 that the node classification heuristics baseline is competitive with several recent embedding methods on datasets with few (up to five) labels.
7 Experimental Results
This section reports the performance of net embedding methods on link prediction and node classification tasks. We tune both the parameters embedding methods and classifiers' parameters in link prediction and node classification tasks. Whenever possible, we rely on the authors' code implementation of the embedding method. All methods that do not finish for large datasets are executed on modern machine with 500 GB RAM and 28 cores. All the evaluation scripts executed in the virtual python environment.
12

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWak
NodeZVec
VERSE
Embeddinng methods
LINE
SONE
NetMF
GraRep-
HOPE
MNMF
VAG
Unsup_ GS
RW -f-fraeeorrk-
Poincare
0.0
0.2
0.3
AUROC score difference
Figure 4: Default vs Tuned Parameters: Link Prediction. Box-plot represents the distribution of differences between AUROC of the embedding method with default parameters vs tuned paramcters.
7.1 Link Prediction
The link prediction performance of 15 embedding methods measured in terms of AUROC on 16 dalasets is shown in Figure | The Overall (or aggregate) performance of an embedding method on all the datasets is also shown at the end of the horizontal bar of each method in Figure [ We represent Overall score as the sum of scores (AUROC) of the method on all the datasets. As mentioned in Section B we tune the hyper-parameters of each embedding method and report the best average AUROC scores across train:test splits. We perform the link prediction task with both normalized and unnormalized embeddings and report the best performance. We make the following observations:
We begin by noting that the current emphasis and interest in network rep- resentation learning can partially be attributed to the Deepwalk's Perozzi et al. (2014) simplicity. In this analysis, we seek to understand if more recent advances offer a real advancement (or if it is an illusion) over Deepwalk on the link prediction task. The distribution of these differences with respect to each embedding method versus Deepwalk is shown as box-plot. in Figure 2 A positive difference implies that the embedding method's performance is better than Deepwalk in terms AUROC. The improvement over Deepwalk is statistically significant by paired t-test only for MNMF and WYS (marginal) with a significance level of 0.05. We observe that except for MNMF and WYS the performance of Deepwalk is comparable or superior to the others. We also observe that the median of the box-plot for link prediction heuristic is also close to that of Deepwalk. WYS provides marginally better link prediction performance over Deepwalk and the cauristic-based model on the smaller datasets. MNMF is the only method that seems to offer a small but consistent advancement over the state-of-the-art suggesting it is the only counterexample to the assertion that recent advances are largely an illusion at least as it relates to the downstream task of link prediction when evaluated on non-attributed graphs. Similar to the results shown Figure P with classifier, we observe that with dot-product too, the improvement over Deepwalk is statistically significant by paired t-test for only MNMF and WYS with significance level of 0.05.
A. Illusion of Progress:
Efficacy of Deepwalk on Link Prediction task: We observe that the link prediction performance of Deepwalk and other random-wal walk based methods improves significantly through the use of classifier (see scction D.. Morcover, Deepwalk is able to effectively capture the local neighborhood of node in the embedding through multiple random walks and the captured neighborhood information appears sufficiently expressive for the link prediction task.
B. Effectiveness of Link Prediction Heuristic: The hcuristic bascline- described section 03 is
very effective while being simple compute and efficient (not shown as this study focuses entirely on quality). On the largest dataset YouTube, the heuristic achieves an AUROC of 96.2%, close to the best performing
13

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWalk
NodeZVec
VERSE
Embedding methods
LINE
SONE
NetMF
GraRep
HOPE
MNMF
VAG
Unsup_ _5
RW -W-framworrk
Poincare
-0.1
0.3
0.4
AUROC score difference
Figure The box-plot represents distribution of the differences between AUROC score with dot product and AUROC score with classifier on all the datascts.
N2V
Embedeing methods
LINE
NetMF
GraR
HOPE
MNMF
WYS
-0.05
0.00
0.05
0.10
AUROC score difference
Figure 6: The box-plot represents the distribution of the differences between AUROC score with node + context embeddings and AUROC score with only node embeddings on directed datasets.
Verse model with an AUROC of 97.6%. When compared the most compotitive bascline MNMF, the link prediction heuristic outperforms MNMF Wikipedia and Blogeatalog datasets. We also observe that the task-specific baseline's performance is competitive against several other methods on the directed datasets despite using undirocted similarity- based metrics. The core components of the link prediction heuristic capture important first- and second-order local topological proximity information which are essential for link prediction and may help explain its impressive performance.
C. Effectiveness of MNME for Link Prediction: We observe that MNMF achieves the highest overall link prediction performance in terms of best average AUROC. We also observe that MNMF does not always outperform other methods all the datasets. For instance, on the Wiki-Vote and Pubmed dataset, WYS achieves the best average AUROC scores while the Microsoft dataset, GraRep achieves the best average modern machine
AUROC score. Note that MNMF did not scale for the datascts with 5M edges with 500 GB RAM and 28 cores. However, the scalability issue of non-negative matrix factorization based methods can be addressed by adopting recent ideas Moon et al. (2019): Liang et al. (2018a) (outside the scope of this study). We note that community structure an important topological property of the network and can play significant role predicting links within a network. MNMF by construction, explicitly imposes higher level of constraint on the node representation, and tries to ensure that the vector representation of
14

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWak
NodeZVec
VERSE
Embeddiing methods
LINE
SONE
NetMF
GraRep-
HOPE
MNMF
VAG
Unsup_ GS
RW -ffamaeeoork
Poincare
0.00
0.02
0.04
0.06
AUROC stá err
Figure The box-plot represents the distribution of the standard error of AUROC scores computed for each method on each dataset across five splits.
nodes within community are more similar than nodes across different communities. This may explain its improved performance over peer methods on the link prediction task.
D. Impact of Evaluation Strategy: As described in section 6.1 the presence of a link between two nodes can be predicted with either the Logistic Regression classifier (treating the embeddings as features) or the dot product between the node embeddings. The latter is the widely used approach in the literature Ou et al. (2016); Kipf & Welling (016)); Abu-Fl-Haaia et al. (2018); Wang et al. (2016ab; Goyal & Ferrara [2018). Here, compare both the evaluation strategies' performance
each embedding method across all datasets using the average AUROC scores' differences. The results are presented as box-plot in Figure 5 A positive difference implies that the classifier's performance is better than the dot product score in terms of AUROC. The paired t-test suggests the positive difference is statistically significant for all mothods, except for Verse, VAG and WYS, with a significance level of 0.05. For Verse and WYS, both strategies resulted in near-identical performance (almost no change). In summary, we find that using a classifier over dot product provides significant predictive performance gain on the link prediction task and probably should be the evaluation strategy of choice moving forward for this task. Note that, irrespective of the evaluation strategy (classifier or dot-product), we observe that only two methods (MNMF and WYS) outperform Deepwalk in a statistical significant manner. Result for link prediction task with dot product is not shown here due paucity of space.
E. Impact of context embeddings: We study context embeddings' impact on directed datasets for the link prediction task. We consider only those embedding methods which generate both node and context embeddings for this study. We compare the impact of using node context embeddings over using only node embeddings with the help of differences in AUROC scores. The '+' symbol refers to the concatenation operation. The results are detailed in Figure 6 A positive difference implies that node + context embed- dings' performance is better than just node embeddings in terms of AUROC. The difference is statistically significant (paired t-test) with a significance level 0.05 for LINE and WYS for which using context infor- mation helps. In contrast, for GraRep and MNMF, hurts the performance. Context also appears to help HOPE, but it not statistically significant. We see that levering node + context embeddings improve the link prediction performance of LINE, HOPE, and WYS. For MNMF, context embeddings do not improve the link prediction performance because, in MNMF, the community information crucial for link prediction is already incorporated in the node embeddings. In the case of GraRep, we find that the node embeddings encapsulate high-order information and, hence, levering context does not help improve the performance.
F. Stability and Robustness: For link prediction, we thus far report the average AUROC score of an embedding method over 5 splits of a selected dataset. The computed average AUROC standard error corresponds to measure of the robustness (or stability) of that embedding method the selected dataset
15

---

Published in Transactions on Machine Learning Research (06/2022)
Texas
Corell
Washington
Wisconsin
DBLP (Co-Author)
Pubmed
Wikipedia
Blogeatalog
CoCkt (mlcrosoft)
Filekr
Youtube
Reddlt
Heuristics
61.8
42.1
65.0
37.3
10.84119
17.25
471.51
LapEig
43.3
41.5
37.1
81.7
2248
46.3
43.0
569.55
DeepWalk
55.1
40.5
56.0
52.3
35.9
81.5
2104
50.0
41.5
46.3
35.6
40
94.0
650.53
Node2Vec
57.2
34.3
58.4
45.6
35.6
81.1
21.0
51.4
41.7
46.7
35.
40.3
93
641.78
VERSE
54.5
35.4
51.5
41.7
37.2
63.0
1907
43.8
37.2
46.0
33
38.5
93.7
595.26
LINE
52.9
654.63
GraRep
40.9
46.7
50.8
35.7
79.1
20.4
56.8
46.6
10
931
618.13
HОPE
59.1
41.9
62.8
51.5
36.0
74.7
18.8
57.9
34.4
14.6
28.7
38
549.15
SONE
56.0
48.5
60.5
51.3
37.4
67.7
17.4
52.4
29.5
38
491.60
NetMF
80.0
58.4
43.5
548.50
MNMF
58.0
36.1
60.4
53.9
36.2
77.1
18.6
48.1
2016
44.7
454.70
VAG
54.8
40.3
59.0
48
36.2
63.5
1332
41.1
17.51
43.5
422.80
41.8
65.3
73.6
44.4
400.44
Unsup_GS
37.8
50.3
43.9
37.5
79.1
1.0
40.7
25.5
44.9
25.6
35.0
907
588.94
DGI
56.0
39.0
47.0
37.0
37.4
39.9
(1:39.1
19966.5
333.77
RW_framework
$7.0
44.0
59.0
51.0
37.5
44.6
2283
$3.1
41.3
46.3
33
40.8
93.9
624.18
Poincare
9999
34.71
Figure 8: The node classification performance measured with Micro-fl train-test split of 50:50 with Logistic Regression, For each method, the number at the end of bar represent the summation of the Micro- fl values across the datascts. The Micro-fl score is multiplied by 100 for better readability.
Texax
W Cornell
W Washington
W Wisconsin
DBLP (Co-Author)
Pubmed
PPI
Wikipedia
Blogeatalog
CoCit (microsoft)
Flickr
YouTube
Reddit
Heuristics
55.9
42.9
66.1
51.9
36.9
57.1
10.7/40.6
16X28
471.6
LapEig
51.5
36.8
46.7
46.2
37.3
81.3
23.8
47.1
43.8
43.6
300
92.8
$85.0
DeepWalk
58.0
56.7
36.8
83.0
23.0
50.5
43.6
672.4
Node2Vec
43.2
61.2
37.0
82.5
23.5
49.2
41.8
48.2
43.0
93.3
669.7
VERSE
54.3
40.8
57.0
5355
37.1
78.0
212
44.3
13.9
47.6
13285
42.5
93.6
638.1
LINE
68.1
4207
61.3
51
37.0
77.9
20.0
54.1
38.8
47.1
42.6
94
669.2
GraRop
58.7
36.4
53.0
52.9
36.5
80.8
203
58.7
44.0
47.5
16.0
4010
98.
641.8
HОPE
$6.5
39.8
59.6
56.4
79.3
210
56.4
3733
44.1
41.0
563.6
46.1
53.8
71.5
39.7
NetMIF
63.0
48.9
59.1
62.9
37.1
81.1
230
57.5
43.9
44.6
3730
558.9
MNMF
56.9
42.6
62.0
58.2
36.8
78.6
2255
47.4
2002
46.1
474.0
VAG
57.7
41.7
56.5
49.9
36.1
68.1
1213
40.1
19K1
45.6
437.4
WYS
58.8
43.6
63.9
96.0
79.7
22.8
44.7
41.2
410.7
Unsup_GS
51.0
37.5
79.1
42.7
29.8
610.3
DGI
50.0
36.0
46.0
42.0
34.
37.333334.6111
61.613
309.8
RW. framew
56.0
4280
56.0
51.0
37.3
44.9
23.0
53.7
44.0
48.2
34.5
628.5 43.0
93.9
Poincare
58.3
48.6
48.4
49.4
6,237.9
24.7
34.6
58.0
43.0
184
41.7
469.2
Figure 9: The node classification performance measured with Micro-fl on train-test split of 50:50 with non- linear classifier. The Micro-f1 score multiplied by 100 for better readability.
larger values of standard error corresponds to large variance in AUROC scores across splits. In Figure we report the distribution of average AUROC standard error of each embedding method over all datasets. We observe that most of the methods' median of box-plots is close to zero, suggesting that all methods are reasonably stable with MNMF and DeepWalk seemingly being the most robust. across different splits and datasets.
G. Dataset specific analysis: There is strong negative correlation between the sparsity of the dataset and the average link prediction performance across methods on said dataset (Pearson correlation (-0.82)). Clustering coefficient plays a secondary factor on aggregate link prediction performance - methods achieve poor link prediction performance on low clustering coefficient datascts such as p2p-Gmutella and Pubmed (an exception is MNMF which is explained by the fact that explicitly accounts for community structure). On the other hand, on datasets with high CC (e.g. DBLP) all methods perform well (above 90%).
16

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
Node2Vec
VERSE
Embeddiing methods
SONE
NetMF
GpaRep
MNMF
VAG
WYS
Unsup_
DGI
RW framework
Poincare
-0.4
-0.2
0.0
Micro-f1 difference
Figure 10: Musion of Progress II: Node Classification: The Box-plot represents the distribution of differences between Micro-fl of the embedding method and Deepwalk.
Node + Context embedding
Node embedding
0.80
0.60
Micro-F1
0.40
0.20
0.00
LINE (2nd)
NetMF GraRep HOPE
MNMF
WYS
Figure 11: Node Classification on Directed Dataset (PubMed) with/without concatenation of Node embed- dings and Context Embeddings (128 dimensions).
Next, we analyze the performance of embedding method HOPE on directed datasets. HOPE learns node embeddings by preserving asymmetric transitivity and hence is expected to perform well on link prediction tasks for the directed datasets. We observe that the HOPE method achieves competitive performance on two directed datasets (Wiki-vote and Epinions). However, HOPE achieves relatively low link prediction performance on other two directed datasots (Pubmed and P2P-Gmutella) with low clustcring cocfficient suggesting preserving asymmetric transitivity might not be "sufficient" for better link prediction performance on directed datasets with low clustering coefficient.
H. Default Tuned Parameters: In Figure we show the impact of tuning the parameters of network embedding method the link prediction performance. A positive difference implies the tuned parameters result in better performance than default parameters. Not surprisingly we see that for most methods tuning its parameters results in improved performance (the exceptions being NetMF and LINE for which default parameters work very well). The tuning of parameters for methods such as SDNE, MNMF, VAG, and WYS lead to significant boost the average AUROC score. This analysis underscores the importance of parametric tuning on downstream performance which is often ignored by authors when comparing with strawman methods and is not considered even in some benchmarking studies Khosla al. 2019)
17

---

Published in Transactions on Machine Learning Research (06/2022)
7.2 Node Classification
The node classification performance of 15 embedding methods measured in terms of Micro-f1 scores on 16 datasets with train-test split of 50:50 is reported in Figure [ and Figure g We tune the of cach embedding method- - mentioned in Section - and report the best Micro-fl score. We perform the node classification with both normalized and unnormalized embedkiings and report the best performance. We make the following observations.
A. Illusion of Progress II: Here we compare and contrast the performance of recently proposed algorithms for network representation learning with Deepwalk on the node classification lask in Figure TO A positive difference here implies that the embedding method's performance is better than Deepwalk in Micro-fl, The improvement over Deepwalk is statistically significant (paired t-test) for none of the methods at significance level 0.05 when evaluated on non-attributed graphs. Somewhat startlingly, we observe that not a single method offers consistent, statistically significant improvement over Deepwalk on this task. The closest one to being significant is NetMF, with a p-value of 0.07.
Efficacy of Deepwalk on Node Classification task: The efficacy of Deepwalk on node classification task can be attributed i. tuning of Deepwalk's s parameters and ii. tuning of logistic regression parameters. The default vs tuned parameters of Deepwalk method result in vast performance differences. For instance, with Logistic regression and train:test split of 50:50, we observe that the default tuned parameters result in following Micro-fl scores: 0.19 0.21 (PPT), 0.47 vs 0.50 (Wikipedia), 0.34 vs 0.36 (Flickr). This experiment highlights the importance of careful tuning of comparative methods.
B. Analysis of the methods for node classification: Although not better than Deepwalk (w.r.t statis- tical significance), NetMF achieves the highest overall performance for node classification with both linear and non-lineat classifiers. LINE, WeepWalk, and Node2Vec are also competitive baselines for the task of node classification as their overall performance is closest to that of NetMF. The performance of GraRep on datasets with more labels is comparable with other methods (except on the Flickr dalaset). The results for GraRep the Flickr dataset are with an embedding dimensionality of 64 increasing the dimensionality to 128 and 256 resulted in Out-Of-Memond error modern machine with 500GB RAM and 28 cores. Note that the methods NetMF, MNMF, SDNE, VAG, and WYS did not finish exccution on YouTube and Reddit. While scalability is currently outside our study's scope, the scalability of such methods is under active development (we refer the interested reader elsewhere Qiu et al. (0019 Liang et al. (2018)))
C. Laplacian Eigenmaps Performance: We observe that Laplaciann Eigenmaps achieves competitive Micro-fl scores on several datasets. For instance, on the Blogcatalog dataset with 39 labels, Laplacian Eigennaps achieves the best Micro-fl score of 42.1% while on the Pubmed dataset, it outperforms all other embedding methods. With non-linear classifier, Laplacian Eigenmaps achieves the second-best performance the PPI dataset with 23.8% Micro-f1. The observed results for Laplacian Eigenmaps on evaluated datasets are better than those reported elsewhere Goyal & Ferrara (2018) : Grover & Leskoved (2016) for both node classification and link prediction tasks. This improvement is due in part to the careful hyperparameter tuning of parameters of the corresponding classifier.
D. Context embeddings can improve performance: We find that levering both node and context embeddings of Skip-gram based models results in significant. improvement (up to 25%) for most of the methods (see Figure| []]. On the Pubmed dataset, we observe that the node classification performance of embedding methods, LINE (2nd order), HOPE, and WYS, is significantly lower than those of other methods. We found that the Pubmed dataset consists of around 80% sink nodes. As a result, when the Skip gram based embedding methods generate node embeddings, the sink nodes appear most times as "context' nodes and rarely appear as "source" nodes. Hence, the node embeddings of sink nodes are of lower quality.
E. Impact of non-linear classifier: We study the impact of using a non-linear classifier (as opposed to a linear classifier) on node classification performance. The results are shown with a box plot in Figure 12 The box plot represents the distribution of differences of Micro-fl scores computed with the non-lincar (EigenPro Ma & Belkin| (2017)) and linear classifiers (Logistic Regression). A positive difference implics that the non-linear classifier results are better than that of the linear classifier. For Verse, we see 1 15% absolute
18

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWalk
Node2Vec
VERSE
Embeddiing methods
LINE
SONE
NetMF
GraRep-
HOPE
MNMF
VAG
WY5
Unsup GS
DGI-
RW fromework
Poincare
0.0
Micro-f1 difference
Box-plot represents the distribution of differences between Micro-fl of the non-linear classifier and Micro-fl of linear classifier on all the datascts.
Figure 12:
increase when using a non-linear classifier on the PubMed dataset. The positive difference statistically significant (with paired t-test) for methods WeepWalk, Verse, SDNE, GraRep, MNMF, and Unsupervised GraphSage with significance level 0.05. It worth pointing out that this gain less evident on the smaller datasets while on the larger datasets (more training data), the benefits of using non-linear classifier are much clearer.
F. Classifier Robustness: We also note that the non-linear classifier appears to be more stable to the impact of normalization (of the embedding), as shown in Figure 13 A positive difference implies the normalization of embeddings improves performance.
G. Dataset specific analysis First, we observe that datascts with fewer classes (up to five), the node classification heuristic is competitive its performance is betler than several other embedding melhods such Laplacian Eigenmaps, Node2vec, Verse, GraRep, VAG, WYS and Unsupervised GraphSage. However, as the number of classes in the datasets increases, we observe that the relative performance of the heuristic decreases drastically. The reduction in overall performance reflects that the node features that currently make up the baseline lack the discriminative power to classify multiple labels. Second, We observe that network embedding methods generally achieve poor node classification performance reflected with low absolute values of Micro-fl scores datasets with low homophily (see PPI and Flickr). On the contrary, datasets with high homophily (Reddit and Pubmed), the network embedding methods achieve better node classification performance (with Micro-fl scores above >80%). The Pearson correlation cocfficient between average node classification performance on a dataset and its homogeneity is 0.86. Third, for multi- label datasets, clustering coefficient plays an important role along with homophily for overall high node classification performance (for example while both Wikipedia and PPI exhibit low homophily Wikipedia has much higher clustering coefficient suggesting that local density plays role improved overall performance).
H. Default Tumed Parameters: In Figure 14 we again examine the impact of tuning parameters node classification performance. Not surprisingly once again observe that tuning the method's parameters results in a better Micro-fl score for most methods (exeeptions here are HOPE and GraRep). Tuning the parameters results in a huge gain in the Miero-f1 score of Laplacian Figenmaps, VERSE, SDNE, NetMF, MNMF, VAG, WYS, and Unsupervised GraphSage. We reiterate the points we made in Section 7.1.H.
8 Discussion & Concluding Remarks
To conclude, among the methods we analyzed, we found that matrix factorization based approaches offer a small advantage over other methods on both link prediction and node classification. However, for the link prediction task, outside of MNMF and WYS, other method offers statistically significant improvement
19

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWalk
NodeZVec
VERSE
Embedding methods
LINE
SONE
NetMF
HOPE
MNMF
VAG
Unsup_Gr GS
RW framework
Poincare
-0.05
0.00
0.05
0.10
Micro-f1 difference
(a) Linear classifier
Logistic Regression
LapElg-
DeepWalk-
Node2Vec-
VERSE-
Embeddiing methods
SONE
NetiF
GraRep
VAG
WY5
Unsup_Gr GS
RW fromework
Poincare
0.0
Micro-fl difference
(b) Noulinear classifier : EigenPro
Figure 13: Classifer Robustness: Box-plot represents the distribution of differences between Micro-fl achieved with normalized embedding and Micro-fl achieved with unnormalized embedding on all the datasets.
DeepWalk either task. Regarding task-specific basclines, the link prediction heuristic is simple, efficient to compute, and offers competitive performance, while the node-classificttion heuristic is effective only on datasets with fewer labels. Moving forward, this study suggests that the field of graph representation learning needs renewed bearing and that careful benchmarking is essential for understanding true scientific advances. Said benchmarking should include more algorithms (existing and new ideas), non-trivial heuristics and methods for end-to-end lasks, as well as more evaluation datasets ideally examined through a statistical lens, on a common platform (our study relics on authors' original code various programming environments in part because wished to be true the original implementations).
Usability of our Study: Network embedding methods has seen applications in multiple domains including drug-discase association prediction (Zhang ct al. 2018b), drug-drug interaction prediction (Zhu et al. 2013
protein function prediction (Leiserson el al. 2017 for relation extraction in natural language processing Jall
et al. 2018). neural machine translation (Battings et al. 2017). for outlier analysis (Zhao & Saligrama 2009
Liang et al. 2018b), and entity resolution (Cohen & Richman 2002 Getoor & Machanavajjhala 2012)
Our benchmarking study examines the performance of a range of methods on datasets drawn from many
of these application domains. Moreover our study provides useful insights researchers with respect to
20

---

Published in Transactions on Machine Learning Research (06/2022)
LapElg
DeepWak-
NodeZVec
VERSE
Embeddiing methods
LINE
SONE
NetMF
epaRep
HOPE
MNMF
VAG
Unsup_ GS
RW -f--mamwwork
Poincare
0.1
0.2
Micro-fl score difference
Figure 14: Default vs Tuned: Node Classification: The Box-plot represents the distribution of differences between Micro-fl of the embedding method with default paramcters tuned parameters.
which baseline methods and hyper-parameter settings to consider in these domains for downstream machine learning tasks such as link prediction and node classification.
Future directions: Scaling several of these methods is also useful direction to pursuc as this could open up benchmarking on larger more meaningful and practical datasets and end applications (Qiu et al. 2019 Liang al.) 2018a). Accounting for model complexity in this context becomes important. Note that Deepwalk is one of the simpler models (and easy to parallelize) and in competitive manner with respect to more complex models. Finally, we believe that the experimental data (375K runs) from this study can also serve as useful training data for improving tuning techniques (Tu et al. 2019a).. In our initial analysis, we find that such techniques rarely match the best performance revealed by our comprehensive grid search for each method on each dataset.
demonstrate can still perform
References
Sami Abu-El-Haijy Bryan Perozzi, Rami Al-Rfou, and Alex Alemi. Watch your step: Learning node embeddings via graph attention. In Neurips, 2018
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 2003.
Bijaya Adhikari, Yao Zhang, Naren Ramakrishnan, and B Aditya Prakash. Sub2vec: Feature learning for subgraphs. In PAKDD, 2018
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards a unified framework for fair and stable graph representation learning. In Uncerlainly in Arlificial Intelligence, pp. 2114 -124. PMLR, 2021.
Priyanka Agrawal, Vikas K Garg, and Ramasuri Narayanam. Link label prediction in signed social networks. In Twenty-thing third international joint conference on artificial intelligence, 2013.
Edoardo M. Airoldi et al. Mixed membership stochastic block models for relational data with application to protein-protein interactions. In International Biometrics Society Annual Meeting, 2006.
Saba Al-Sayouri, Ekta Gujral, Danai Koutra, Evangelos E Papalexakis, and Sarah S Lam. t-pine: Tensor- based predictable and interpretable node embeddings. Social Network Analysis and Mining, 10(1):1-11, 2020.
Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. Subgraph neural networks. Advances in Neural Information Processing Systems, 33, 2020.
Albert-T.ás266 Barabási and Réka Albert. Emergence of scaling in random networks. science, 1999.
21

---

Published in Transactions on Machine Learning Research (06/2022)
Joost Bastings et al. Graph convolutional encoders for syntax-aware neural machine translation. anXiv preprint Xiv: 1Xx::170440400 774404675, 2017.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Newral computation, 2003.
Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 2016.
Smriti Bhagat, Graham Cormode, and S Muthukrishnan. Node classification in social networks. In Social network dala analylics. 2011.
Dhruba Kumar Bhattacharyya and Jugal Kumar Kalita, Network anomaly detection: A machine learning perspective. 2013.
Bobby-Joe Breitkreutz et al. The biogrid interaction database. Nucleic acids research, 2007.
Hongyun Cai et al. A comprehensive survey of graph embedding: Problems, techniques, and applications. TKDE, 2018.
Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM, 2015.
Sandro Cavallari, Vincent W Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. Learning community embedding with community detection and node embedding on graphs. In CIKM, 2017.
Egemen Cetinkaya et al. Multilevel resilience analysis of transportation and communication networks. Telesommunication Systems, 2015.
Wei-Tin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Dala Mining, pp. 257 337-266, 2019.
William W Cohen and Jacob Richman. Learning to match and cluster large high-dimensional data sets for data integration. In KDD, 2002.
Mark Craven et al. Learning to extract symbolic knowledge from the world wide web. Technical report, 1998.
Gamal Crichton et al. Neural networks for link prediction in realistic biomedical graphs: a multi-dimennsonall evaluation of graph embedding-basee based approaches. BMC Bioinformatics, 2018.
David K Duvenaud et al. Convolutional networks graphs for learning molecular fingerprints. In NeurIPS, 2015.
Alessandro Epasto and Bryan Perozzi. Is a single embedding enough? learning node representations that capture multiple social contexts. In The World Wide Web Conference, pp. 394-404, 2019.
David Eppstein, Michael S Paterson, and F Frances Yao. On nearest-neighhor graphs. Discrete & Compu- tational Geometry, 1997.
Matthias Feurer et al. Auto-sklearn 2.0: The next generation. orXiv preprint arXiv:2007.04074 2020.
Lise Getoor and Ashwin Machanavajjhala. Entity resolution: theory, practice & open challenges. VLDB, 2012.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge- Based Systems, 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Tn KDD, 2016.
22

---

Published in Transactions on Machine Learning Research (06/2022)
Yupeng Gu, Yizhou Sun, and Jianxi Gao. The co-evolution model for social network evolving and opinion migration. In KDD, 2017.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for un- normalized statistical models. In AISTATS, 2010.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Newrips, 2017a.
William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-155) 159, 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. TEEE Data Engineering Bulletin, 2017b.
David J Hand. Classifier technology and the illusion of progress. Statistical science, 2006.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. Tn International Conference on Machine Learning, pp. 4116 4126. PMLR, 2020.
Mchdi Heidari, Masoud Asadpour, and Hesham Faili. Smg: Fast scalable greedy algorithm for influence maximization in social networks. Physica A: Statistical Mechanics and its Applications, 420:124-133,
2015.
Zexi Huang, Arlei Silva, and Ambuj Singh. A broader picture of random-was based graph embedding. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 685-695, 2021.
Paul Jaccard. Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull Soc Vandoise Sci Nal, 1901.
Sharmistha Jat et al. Improving distantly supervised relation extraction using word and entily based atten- tion. EMNLP, 2018
Glen Jeh and Jennifer Widom. Simrank: measure of structural-contett similarity. In KDD, 2002.
Di Jin et al. Integrative network embedding via deep joint reconstruction. In IJCAI, 2018
Megha Khosla, Vinay Setty, and Avishek Anand. A comparative study for unsupervised network represen- tation learning. TKDE, 2019.
Jungeun Kim, Sungsu Lim, Jac-Gil Lee, and Byung Suk Lee. Linkblackhole*: Robust overlapping community detection using link embedding. IEEE Transactions Knowledge and Data Engineering, (1())):2138 2150, 2018.
Thomas Kipf and Max Welling. Variational graph auto-encoders NIPS Workshop on Boyesion Deep Learning, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Jon Kleinberg, Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 1999.
Johannos Klicpera, Stefan Weifenbbegerr, and Stephan Günnemann. Diffusion improves graph learning. arXiv preprint arX:o:1911.05455, 2019.
Mark Leiserson el al. A multi-species functional embedding integrating sequence and network structure. bioRriv, 2017.
Jure Leskovec. Node embeddings. URL:
cs2.///22222/// (odindeee// 2022.
23

---

Published in Transactions on Machine Learning Research (06/2022)
Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. Signed networks in social media. In SIGCHI, 2010.
Jundong Li, Harsh Dani, Xia Hu, Jiliang Tang, Yi Chang, and Huan Liu. Attributed network embedding for learning in a dynamic environment. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, pp. 387-396, 2017.
Ye Ti, Chaofeng Sha, Xin Huang, and Yanchun Zhang. Community detection in attributed graphs: An embedding approach. In AAAI, 2018.
Jiongqian Liang, Saket, Gurukar, and Srinivasan Parthasarathy. Mile: A multi-level framework for scalable graph embedding. arXiv preprint orXiv:1822.066 2018a.
Jiongqian Liang, Peter Jacobs, Jiankai Sun, and Srinivasan Parthasarathy. Semi-supervised embedding in attributed networks with outliers. In SDM, 2018b.
Weile Liu, Zhihao Tang, Lei Wang, and Min Li. Debgen: An algorithm with high memory and computational efficiency for training deep graph convolutional network. In 2020 3rd International Conference on Advanced Electronic Materials, Computers and Software Engineering (AEMCSE), pp. 16 21. IEEE, 2020.
Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip Yu. Graph self-supervised learning: A survey. IEEE Transactions on Knowledge and Data Engineering, 2022.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey, Physica A: statistical mechanics and its applications, 2011.
Alessandro Lusci et al. Deep architoctures and deep learning in chemoinformatics: the prediction of aqucous solubility for drug-like molecules. Journal of chemical informalion and modeling, 2013.
Siyuan Ma and Mikhail Belkin. Diving into the shallows: a computational perspective on largo-scale shallow learning. In Neurips, 2017.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang, Is homophily necessity for graph neural networks? arXiv preprint arXin:2106..0 06134, 2021.
Matt Mahoney, Large text compression benchmark. URL: http://www. mattmahoney, net/text/tent /tert. html, 2011.
Victor Martinez, Fernando Berzal, and Juan Maan-Caloss Cubero. survey of link prediction in complex networks. ACM computing surveys (CSUR), 2016.
Tomas Mikolov, Tya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. NeurIPS'13, 2013.
Anasua Mitra, Priyesh Vijayan, Srinivasan Parthasarathy, and Balaraman Ravindran. A unified non-negative matrix factorization framework for semi supervised learning on graphs. In SDM, 2020.
Andriy Muih and Geoffrey E Hinton. A scalable hierarchical distributed language model. In NewrIPS, 2009.
Yujie Mo, Liang Peng, Jie Xu, Xiaoshuang Shi, and Xiaofeng Zhu. Simple unsupervised graph represcntation lcarning. AAAI, 2022.
Gordon E Moon, Aravind BakumarannRajam, Srinivasan Parthasarathy, and P Sadayappan. Pl-nmf: Parallel locality-optimized non-negative matrix factorization. arXiv preprint arXiv:1904, 07935, 2019.
Gordon E Moon, Austin Ellis, Aravind Sukumaran-Rajam Srinivasan Parthasarathy, and P Sadayappan. Alo-nmf: Accelerated locality-optimized non-negative matrix factorization. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1758 1767, 2020.
Galileo Namata et al. Query-driven active surveying for collective classification. In MLG, KDD, 2012.
Mark Newman. Networks: an introduction. 2010.
24

---

Published in Transactions on Machine Learning Research (06/2022)
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 2016.
Maximillann Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representations. Ad- vonces in neural information processing systems, 30, 2017.
Maximillian Nickel and Douwe Kiela. Learning continuous hierarchies in the lorentz model of hyperbolic geometry, In International Conference on Machine Learning, pp. 3779 3788. PMLR, 2018.
Mingdong Ou, Pong Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity prescrving graph embedding. In KDD, 2016.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Christopher C Paige and Michael A Saunders. Towards generalized singular value decomposition. SIAM Journal on Numerical Analysis, 1981.
F. Pedregosa et al. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 2011.
Zhen Peng, Wenbing Huang, Minnan Luo, Qinghua Zheng, Yu Rong, Tingyang Xu, and Junzhou Huang, Graph representation learning via graphical mutual information maximization. In Proceedings of The Web Conference 2020, pp. 259 270, 2020.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In KDD, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding matrix factorization: Unifying deepwalk, line, ptc, and node2vec. In WSDM, 2018.
Jiezhong Qiu al. Netsmf: Large-scale network embedding as sparse matrix factorization. The Web, 2019.
Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. Trust management for the semantic web. In International semantic Web conference, 2003.
Matei Ripeanu and lan Foster. Mapping the gnutella network: Macroscopic properties of large-scale peer- to-peer systems. In international workshop on peer-to-peet systems, 2002.
Aakash Sinha et al. Systematic biases in link prediction: comparing heuristic and graph embedding based methods. In Complex Networks, 2018.
Andreas Spitz, Diego Costa, Kai Chen, Jan Greulich, Johanna Geiß, Stefan Wiesberg, and Michael Gertz. Heterogeneous subgraph features for information networks. In Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Dala Analylics (NDA), pp. 1 9, 2018.
Jiankai Sun, Bortik Bandyopadhyay, Armin Bashizade, Jiongqian Liang, P Sadayappan, and Srinivasan Parthasarathy. Atp: Directed graph embedding with asymmetric transitivity preservation. Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 265 272, 2019.
Jian Tang et al. Line: Large-scale information network embedding. In Web, 2015.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In KDD, 2008.
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery, 2011.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares- Llóez, Bastian Rieck, and Karsten Borgwardt. Wasser- stein weisseiler-lehman graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
25

---

Published in Transactions on Machine Learning Research (06/2022)
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embed- dings from similarity measures. In Web, 2018.
Ke Tu, Jianxin Ma, Peng Cui, Jian Pei, and Wenwu Zhu, Autone: Hyperparameter optimization for massive network embedding. Tn KDD, 2019a.
Kun Tu, Jian Li, Don Towsley, Dave Braines, and Liam D Turner gl2vec: Learning feature representation using graphlets for directed networks. In Proceedings of the 2019 IEEE/ACM International Conference on Advonces in Social Networks Analysis and Mining, pp. 216 221, 2019b.
Petar Velickovic, William Fedus, William L Hamilton, Pictro Liò, Yoshua Bengio, and R. Devon Hjelm. Decp graph infomax. In ICLR, 2019.
Chao Wang, Venu Satuluri, and Srinivasan Parthasarathy. Local probabilistic models for link prodiction. In ICDM, ICDM '0, 2007. ISBN 0-7695-3018-4.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In KDD, 2016a.
Jizhe Wang, Pipei Huang, Huan Zhao, Zhibo Zhang, Binqiang Zhao, and Dik Lun Lee. Billion-scale com- modity embedding for e-commerce recommendation alibaba. In KDD, 2018.
Xiao Wang, Di Jin, Xiaochun Cao, Liang Yang, and Weixiong Zhang. Semantic community identification in large attribute networks In AAAI, pp. 265-271. Citeseer, 2016b.
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Communily preserving network embedding. In AAAI, 2017.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi- supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD Inter- national Conference on Knowledge Discovery & Data Mining, pp. 207-217, 2020.
Zhen Wang, Jianwen Zhang, Jianlin Feng, and Zheng Chen. Knowledge graph embedding by translating on hyperplancs. In Twenty-Eights AAAI conference on artificial intelligence, 2014.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchi- cal graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018b.
Xiang Yue et al. Graph embedding on biomedical networks: Methods, applications, and evaluations. Bioin- formatics, 2019.
Reza Zafarani and Huan Liu. Social computing data repository at asu, 2009.
Bingyi Zhang, Hanqing Zeng, and Viktor Prasanna. Hardware acceleration of large scale gen inference. In 2020 IEEE 31st International Conference on Applecation-specsfee Systems, Archstectures and Processors (ASAP), pp. 61 68. IEEE, 2020.
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Network representation learning: A survey. IEEE transactions on Big Data, 2018a.
Fan Zhang, Wenjie Zhang, Ying Zhang, Lu Qin, and Xuemin Lin. Olak: an efficient algorithm to prevent unraveling in social networks. VLDB, 2017.
Wen Zhang, Xiang Yue, Weiran Lin, Wenjian Wu, Ruoqi Liu, Feng Huang, and Feng Liu. Predicting drug- disease associations by using similarity constrained matrix factorivation. BMC bioinformmllic,, 2018b.
Wen Zhang et al. Iteratively learning embeddings and rules for knowledge graph reasoning. In The Web, 2019.
26

---

Published in Transactions on Machine Learning Research (06/2022)
Manqi Zhao and Venkatesh Saligrama. Anomaly detection with score functions based nearest neighbor graphs. In NewrIPS, 2009.
Xiaohan Zhao, Adelbert Chang, Atish Das Sarma, Haitao Zheng, and Ben Y Zhao. On the embeddability of random walk distances. Proceedings of the VLDB Endoument, 6(14):1600-170; 1701, 2013.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 2009.
Lin Zhu et al. Increasing the reliability of protein protein interaction networks via non-convex semantic embedding. Neurocomputing. 2013.
A Appendix
A.1
Additional experiments and analysis
In our study, in addition to Micro-F1 scores, we have computed Macro-Fl scores for all experimental settings (trends are similar to the reported results for Micro-F1). For node classification, we variod train: test splits from 10:90 to 90:10 (the trends are similar to what we have reported for the 50:50 split in that no method outperforms Welp with significance level of 0.05). We also studied the impact of embedding normalization the link prediction task (the impact of normalization classifier, unlike what we observed for the node classification task). Additionally, we analyzed the impact of embedding dimension on both the tasks. We also study the impact of binary function on the link prediction task. These additional results and analysis will be available in a technical report.
negligible with the logistic
B Summary of the methods
In this section, we give summary of the network embedding methods evaluated in our work. Herein, for each models along with their description.
Laplacian Eigenmaps Belkin & Niyogi (2003): Laplacian Figenmaps generates a d-dimensional em- bedding of the graph using the smallest d eigenvectors of Laplacian matrix =
minimize
lrace(U LU)
subject to DU =1
U generated embedding matrix RVdd The above equation can be reduced to simple minimization of L2 distance for adjacent nodes Ex - 12 Laplacian Eigenmaps levers the first order information for generating the embeddings.
Deep Walk Perozzi et al. (2014): DeepWalk is random walk based network embedding method which uses truncated random walks and levers local information from these generated walks to learn similar latent representations. DeepWall draws inspiration from Skip-gram model in Word2vec Mikolov et al. (013 by treating random walks as sequences and optimizing following objective function:
Welk
mánimizes - log Pr(fe: Ce ((;)))
(1)
where is target node while (u- Uu+ } \u the context nodes. d(v)) denotes the embedding of the node v. Since the objective function is expensive to compute for large graphs, it is approximated using Hierarchical SoftmaxMiih & Hinton 2009).
Node2Vec Grover & Leskovec (2016): Node2Vec is biased random walk based network embedding method which allows the random walk be more flexible exploring the graph neighborhoods. The flexibility of the random walk achieved by interpolating between Breadth-first traversal and Depth-fires first traversal. The objective function is again based on Skip-gram model -based Word2vee Mikolov et al.
27

---

Published in Transactions on Machine Learning Research (06/2022)
2013), and since the objective function is expensive to compute for large graphs, it is approximated by negative sampling Mikolov et al. (2013).
GraRep Cao et al. (2015): GraRep is a matrix factorization based network embedding method which captures the global structural information of the graph while learning node embeddings. The authors observe that the existing Skip-gram based models project all the k-step relational information into common subspace and then, argue the importance of preserving different k-step relational information in separate subspaces. The loss function to preserve the k-step relationship between node and is proposed
Lu(u, v) =A -log ( $(0))
Σ d'EV'''E
A A oogo(-1 (-g) $(v'))
(2)
V
where v' refers to the negative node at k-th step for node u (see Table 1 for additional notation, c.g. A). The above loss function in closed form results in log-transformet probabilistic adjacency matrix which is factorized with SVD for generating each k-step representation. The final node representation is generated by concatenation of all the k-stop representations.
NetMF Qiu et al. (2018): : NetMF is matrix factorization based network embedding method. NetMF presents theoretical proofs for their claim that Skip-gram models with negative sampling are implicitly approximating and factorizing appropriate matrices constructed with the help of graph Laplacians. The objective matrix based for NetMF on small context window T is given by (see Table 1 for notation):
| \E' ) )
log GC)
log
where vol(G) refers to sum of all edge weights and b corresponds to number of negative samples in skip-gram model. NetMF factorizes the above closed form DeepWalk matrix with SVD in order to generate node embedding and provides two algorithms for small context window and large context window.
M-NMF Wang et al. 2017): M-NMF a matrix factorization based network embedding method which generates node embeddings that preserves the microscopic information in form of first-order and second- order proximities among nodes and the generated embeddings also preserve mesoscopic information in form of community structure. The objective function for M-NMF is given
0 = min U.VC,H20
||S - VU +a I| UC
(4)
- -BIr(H+TB), + CHHHH - -||
where H the binary community membership matrix, C is the latent representations of communities and B is the modularity matrix obtained from the adjacency matrix, A (see Table | for rest of the notations). Overall, M-NMF discovers communities through modularity constraints. The node embeddings generated with the help of microscopic information and community embeddings then, jointly optimized by assuming consensus relationship between both node and community embeddings.
HOPE Ou et al. (2016): HOPE is a matrix factorization based network embedding method which gen- erates node embeddings that preserve asymmetric transitivity of nodes in directed graphs. If there exists a directed edge from node u w and w v, then due to asymmetric transitivity property - an edge from to more likely to form than edge from v u. The objective function of HOPE is given as follows
min || - 1
where U and U are the source and target embeddings. In order to preserve asymmetric transitivity of nodes, the proximity matrix S constructed using similarity metric which respects the directionality of odges. The node embeddings are generated by factorizing the proximity matrix with generalized SVD Paige
& Saunders 1981
28

---

Published in Transactions on Machine Learning Research (06/2022)
LINE Tang et al. (2015) LINE is optimization-base network embedding method which optimizes objective function that preserves both first and second order proximity among nodes in the embedding space. The objective function for first-order proximity is given as:
0, --
Σ (,,D)E
An, log o (((())((e))
(6)
The objective function to preserve the second order proximity is given
cxp(+(u).e((e)
O2 - Σ
Au,o log Evevio exp ((p(((()))) (T(((())((()))
(7)
(u,D)EB
where (b)) represents context embedding of node (see Table 1 for rest of the notations). The first-order proximity corresponds to local proximity between nodes based on the presence of edges in the graph while the second-order proximity corresponds to global proximity between nodes based on shared neighborhoods of those nodes in the graph. Since the objective function expensive to compute for large graphs, is approximated by negative sampling Mikolov al. (2013).
Verse Tsitsulin et al. (2018): Verse is an optimization based network embedding method which opti- mizes an objective function that minimizes the Kullback-Leibhe Leibler (KT.) divergence from the given similarity distribution in graph space to similarity distribution in embedding space (E). The objective function is given as follows:
KL(sima(e, (eleiimc(e.))lsmmegeee ()sssmg((e.)
(8)
The similarity distribution in graph space could be constructed with help of Personalized PageRank Page et al. (1999), SinRankJeh & Widom (2002), or Adjacency matrix Taitsulii et al. (2018). Since the objective function is expensive to compute for large graphs, it is approximated by Noise Constrastive Estimation Gutmann & Hyvärinen (010))
SDNE Wang et al. (2016a): SDNE is a deep autoencoder based network embedding method which optimizes an objective function that preserves both first and second order proximity among nodes in the embedding space. The objective function of SDNE given below
Ljoint aList + Land + v uLreg
(9)
where List and L2nd are loss functions to preserve first-order and second-order proximities respectively, while Creg is the regularizer term The authors propose a semi-supervised deep model to minimize the mentioned objective function. The deep model consists of two components: supervised and unsupervised. The supervised component attempts to preserve the first-order proximity while the unsupervised component attempts to preserve the second-order proximity by minimizing reconstruction loss of nodes.
VAG Kipf & Welling (2016): VAG is a graph autoencoder based network embedding method which minimizes the reconstruction loss of the adjacency matrix. The reconstruction matrix is generated as Á = (ZZ") where is node embeddings generated with Graph Convolutional Networks (GCN) Kipf & Welling
(2117) as = GCN(X, A) with X as node features (see Table for additional notalion). In the case of unattributed graphs, the node feature matrix is the identity matrix.
Watch Your Step Abu-El-Haijpe et al. (2018): Watch Your Step (WYS) addresses the sensitivity issuc of lyper-parameters in the random walk based embedding methods. WYS solves the sensitivity issue with the attention mechanism on the expected random walk matrix. The attention mechanism guides the random walk to focus on short or long term dependencies pertinent to the input graph. The objective function of WYS given as
B11a11 [[E[D; d) log(o(L * RR))
min L.R.q
(10)
- 1|A = 0] log(1 - a(L * R²T) )l1
where g is attention parameter vector, and R are node embeddings, E|D;q] is expectation on the random walk matrix (see Table i1 for rest of the notations).
29

---

Published in Transactions on Machine Learning Research (06/2022)
Hamilton et al. (2017a): Graphsage is vressage-passingg based graph neural method that learns to aggregale feature information from node's local neighborhood. The neighborhood of the node u is defined through parameter & and the nodes that are k hops from u are considered as its neighbors. Due to this definition of node neighborhood, one can train GraphSage in a minibatch sctting. The objective iunction of Unsuperrvised-CrapphSSee is shown below
- (o 20)) Q Q.Ex--P((jlog((((-2 =x))
(11)
where Zu is the node representation of node u, is the number of negative samples and (o()) is negative sampling distribution.
DGL Velickovic et al. (011)) Deep Graph Infomax (DGI) Velickovie el al. 2019 is a recent and highly popular unsupervised node representation learning approach that has achieved excellent performance for graphs with node attributes. DGI uses an InfoMax based objective that aims to maximize the mutual information between a node's imput features based patch-level representation and its corresponding graph- level representation. This enforces the message passing based patch encoder to prefer similarity information shared across patches. The objective function of DGI is given as
M
(x,)) (Log D(h,, 8)] +
Σ
E (x,A) [log (1 - D(hj,,)])
(12)
N+ M
where N and M the number of nodes and number of negative samples respectively. X, A and X, Å are features and adjaceny matrix of original and alternate graph, respectively. is summary vector of the graph. h; and hi is the hidden representation of the node i in original and alternate graph, respectively.
Huang et al. (2021): Huang et al. proposed an analytical framework for categorizing and proposing novel random-walk based node embedding methods. The framework consists of three components -)alddomwwalk process, ii) similarity function, and iii) embedding algorithm. The authors utilize standard random- walk process for undirected graphs and Pagerank process for directed graphs. For similarity function, the framework relies Pointwise Mutual Information and autocovariance metrics. The embedding methods in the framework are matrix factorization and sampling.
BeeelooWall-FFaammeee
Poincaré Nickel & Kiela (2017): Nickel et al. Nickel & Kiela 2017)) propose that the embeddings learned in the hyperbolic space can better reflect the semantic similarity of symbolic data than the embeddings learned in cuclidean space, especially when the data has hicrarchical structure. The loss function of Poincaró is described as
ddu,w)
[(0)
Σ log EVEN, e dlure) (u
(13)
where d(u, v) arccosh (1+ 2 optimization mothods.
1 (1- 11110-P0011111111 |P. ). The equation 13 is optimized via stochastic Riemannian
C
Link Prediction Dataset Statistics
The statistics of the five folds of link prediction datasct is shown in Table and Table 5 The link prediction folds are formed by following the procedure specified in section 6.1 The train graph has around 80% edges while the test graph has 20% edges. graph, we delete that test edge as we cannot learn the node embodding of node during training. The flowchart for graph construction is shared in Figure 15a while the ftowchart for creation of train and test sets for Link prediction classifier is shared in Figure 15b
the test edge contains node (say t) that is not present in training
30

---

Published in Transactions on Machine Learning Research (06/2022)
Dataset
Fold
Num Nodes
Num Edges
Train Graph Nodes
Train Graph Edges
Test Graph Nodes
Test Graph Edges
texas
186
464
159
224
39
28
texas
186
464
162
216
48
texas
164
168
217
53
texas
164
157
216
40
texas
464
156
211
44
cornell
478
222
45
cornell
478
216
53
cornell
478
160
217
43
cornell
195
478
155
215
44
cornell
195
478
160
213
51
washington
230
596
203
291
79
61
washington
230
596
191
285
74
52
washington
230
596
187
276
71
60
washington
230
596
180
272
63
46
washington
230
596
196
287
69
56
wisconsin
265
724
232
365
85
65
wisconsin
265
724
222
344
89
70
wisconsin
265
724
220
355
76
57
wisconsin
265
724
225
348
98
73
wisconsin
265
724
239
375
82
ppi
3,890
38,739
30260
2771
7492
ppi
3,890
38,739
3744
30367
2733
7351
ppi
3,890
38,739
3768
30367
2738
7364
ppi
3,800
38,739
3753
30179
2755
75-17
ppi
3,890
38,739
3758
30170
2763
7556
wikipedia
4,777
92,517
4777
73959
4563
18336
wikipedia
4777
92,517
73702
4568
18593
wikipedia
4777
92,517
4777
73846
4558
18-119
rikipedia
4777
92,517
4777
73666
4554
8629
vikipedia
4777
92,517
4777
73748
4552
18547
wikivote
7,115
103,689
G611
81239
3840
1 19955
wikivote
7,115
103,689
6596
81151
38-15
20011
w
wikivote
7,115
103,089
6572
81154
3854
200
wikivote
7,115
103,689
6558
81113
3854
20006
wikivote
7,115
103,689
6573
80993
3894
20100
blogeatalog
10,312
333,983
10242
267094
8958
66795
blogcatalog
10,312
333,983
10247
260883
8973
67013
blogratalog
10,312
333,983
10227
267134
8952
66746
blogeatalog
10,312
333,983
10237
267025
8936
66862
blogratalog
10,312
333,983
10252
206687
8955
67215
co-author
18,721
122,245
17691
82506
12349
19996
co-author
18,721
122,245
17609
82076
12550
20386
co-anthor
18,721
122,245
17697
82298
12513
2017 72
author
122,245
82183
12539
20309
co-author
122,245
82205
12482
pubmed
19,717
44,338
17551
35347
6086
66-13
pubmed
19,717
44,338
17541
35250
6100
6698
pubmed
19.717
44,338
17592
35321
6107
6692
pubmed
19.717
44,338
17531
35384
6028
65-49
pubmed
19,717
44,338
17561
35417
6121
65
microsoft.
44,031
195,361
40423
155124
25118
369-19
mierosoft
44.034
195,361
40464
155046
25228
37048
microsoft
41.031
195,361
40344
155070
25112
36872
microsoft.
44,034
195,361
40315
155133
25078
36806
microsoft
44,031
195,361
403G5
155146
25123
30875
p2p gautella31
62,586
147, 147,892 892
56322
118298
22077
22869
p2p-guutella31
62, 22,586
147, 892
56235
118089
22092
22985
p2p-gnatella31
62, 588
147,892
56506
118524
21957
22828
p2p-gmutella31
62, 588
147 897 892
56295
118244
22079
22911
p2p-gnatella31
62,586
147,892
56326
118207
22067
22980
flickr
80,513
8,890,882
4718007
74083
1181588
flickr
80,513
5,899,882
80382
4720230
73991
1179368
flickr
80.513
5,899,885
4720613
73966
1178954
flickr
80,513
5,899,85
80358
4718527
73984
1181007
flickr
80,513
5,899,882
80358
4718527
73984
1181007
Table 4: Link Prediction Folds Statistics
31

---

Published in Transactions on Machine Learning Research (06/2022)
Remove Self Loops
Sample 20% edges and treat them as test edges
Graph
Compute the weakly connected component (WCC) from the rest 80% edges and treat WCC as Train Graph (say TrainG)
Form Test Graph (say TestG) from test edges
Delete node from test graph that not present in training graph
(a) Visual illustration for the graph construction.
1. If edge(iij) belong in TrainG, then that training instance's features embeddings of node and j and label +1
Form Training set for Classifier
2. Sample negative edges (edge(j,kk does not belong TrainG), then that training instance's features are embedding of node and k and its label is 0.
Link Prediction Classifier Evaluation
1. If Tedge(ij) belong in TestG, then that test instance's features are embeddings of node i and and label is +1
Form Test set for Classifier
2. Sample negative edges (edgeli,k) does not belong in TrainG), then that test instance's features embeddings of node and and its label is O.
Once Train and Test Set are formed and node embeddings are learned, train Logistic Regression classifier on Training and Evaluate on Test
(b) Visual illustration for training and test set creation for Link Prediction classifier.
D Link Prediction: Ranking
We rank the methods based on the average AUROC score and compare the ranking of the methods based on evaluation strategy - dot vs. classifier. The results are presented in Table ( the average AUROC between the two methods is within 0.5 (x 100) points, then they share the same ranks. We observe that in case of the random-walk based methods such Deepwalk, Node2vee, RW framework as well the family of methods covered by NetMF Qiu et al. (2018) (LINE, Deepwalk, Node2vee), the of classifier improves the link prediction performance. Moreover, even though the rank for VAG increase, the overall average AUROC of VAG still improves. For the rest of the methods, the ranking is similar (rank difference S 4) with respect to the evaluation strategy.
E
Link Prediction: Mean Average Precision
The link prodiction performance of 13 embodding methods measured in terms of mean average precision on datasets is shown in Figure I6 We observe that the claim of illusion of progress for the link prediction task holds with mean average precision score.
32

---

Published in Transactions on Machine Learning Research (06/2022)
Dataset
Fold
Num Nodes
Num Edges
Train Graph Nodes
Train Graph Edges
'ees Graph Nodes
'esst Graph Edges
epinions
75,879
508,837
67900
340192
28079
90340
epinions
75,879
508,837
68049
340091
28036
epinions
2
75.879
508,837
67887
340079
27923
90277
epinions
3
75.879
508,837
68104
340273
27949
90156
epinions
4
75,879
508,837
67928
340088
27913
90288
youtube
1,131,890 0
2,987,622 624
966732
2362025
260866
446980
youlube
1
1,134,890
2,987 624
966749
2363358
260352
445760
youtube
2
1,134,890
2,987,624
967081
2362951
260846
446739
youtube
3
1,134,890
.2987,624
966025
2362875
260048
445527
youtube
1,134,890
2,987,62 624
967130
23641336
260061
445068
reddit
231,433
11,606,919
230562
9282990
221639
2322903
reddit
231,443
11,606,919
230607
9285995
221643
2319955
reddit
231,443
11,606,919
230576
9282918
221573
2322994
reddit
3
231,443
11,606,919
230583
9286122
221524
2319805
reddit
4
231,443
11,606,919
230503
9284390
221609
2321546
Table 5: Link Prediction Folds Statistics
Avg. AUROC: Dot Product
Avg. AUROC: Classifier Dot-product Ranking
Classifier Ranking
LmplacianEmb
70.65
83.33
14
13
Deepwalk
82.10
89.89
3
Node2vec
84.23
89.77
Grarep
77.89
88.44
11
9
NetMF
76.08
89.23
12
MNMF
88.7 71
95.25
LINE
80.36
89.33
3
Verse
88.01
89.33
VAG
81.51
86.53
12
WYS
89.98
90.45
2
SDNE
74.17
81.99
HОPE
83.71
88.21
9
Unsup GS
81.50
87.2
11
RW framework
80.40
89.35
3
Poincaré
59.93
76.61
15
15
Table 6: Ranking of the method based on the average AUROC score. AUROC score is multipliod by 100 for better readability. If the average AUROC between the two methods is within 0.5 (x 100) points, then they share the same ranks.
33

---

Published in Transactions on Machine Learning Research (06/2022)
Heuristics
82.09
81.45
80.58
82.64
91.40
93.05
87.94
95,09
96.76
85.26
876.27
W-Texas
LapElg
79.37
W-Comell
W-Washington
Node2Vec
82.00
79.00
B9.53
92.35
97.23
94.76
82.27
877.28
VERSE
85.32
85.05
86.65
90.80
90.71
92.80
94.85
97.88
98. 16
96.79
922.00
W-Wisconsin
LINE
82.43
77:15
75.79
76.62
88
92.77
95.29
95.10
95 58
90.32
869 26
SDNE
85.66
79.99
81.69
80.83
90.23
50.00
96.31
95.46
50
00
30.52
800.68
Wikipedia
85.18
87.91
96,70
86.07
883.11
GraRep
97
74.15
Wiki-Vote
HОPE
15
80.19
77.45
99
89.16
91.78
06.77
95.03
00 01
91.37
874.79
BlogCatalog
MNMF
05.47
97.90
97.74
96.49
96.49
89.95
67 56
93.62
99 16
90.31
947.20
VAG
82
79:45
79.56
79.87
68.32
92.91
95.78
94.95
94.82
95.67
883.65
DBLP
83.58
92.15
93.52
97
96.07
96.89
916.04
Pubmed
Unsup_68 GS
80.82
78.46
76.17
80.50
87.65
90.95
87 64
93.21
96
79.26
851.08
iW_.famewark
$1.39
81
80.02
88
05
89.71
91.79
95 35
93 87
96
82
88.13
886.39
Poincare
75.35
75.24
72.86
76 92
62.89
81
24
B2 27
59.97
85 66
81.57
754.90
(a) Smaller datasets: All methods complete execution.
79.51
92.52
Microsoft
LapÉlg 97.87
95.00
540.62
DeepWalk
84.28
96.12
91.68
95.03
97.80
562.78
Flickr
Node2Vec
97.53
84.47
94.96
91.86
93.04
96.28
148
VERSE
76.37
68.35
70.94
88 63
98.23
99:16
501.67
Epinions
LINE
07.70
88.5
95.47
566.08
Youtube
350,96
NetMF
97:08
97.57
11.89
370.53
Reddit
GraRep
97.95
71.30
95.72
92.99
20
97:40
547.55
HОPE
05.33
85.84
96.73
91.46
94.03
463.39
MNMF
94.51
89.55
184.07
0.00
DGI
55.09
55.27
110.36
Unsup GS
94.64
73.06
67.08
78.54
92.96
95.86
522.14
RW_ffamework
97.77
82.93
82.82
89.57
94.82
98.15
546.06
Poincare
83.72
75,00
82 10
82
82.29
404.94
(b) Larger datasets: Not all methods complete execution.
Figure 16: Link Prediction performance mcasured with Mean Average Precision (MAP). The MAP score is multiplied by 100 for better readability. Not all methods are scalable on the datasets shown in Figure 16b
F Default Parameters
Figure 7 shows the parameters considered be default in our experiments in Section 4 and Section
34

---

Published in Transactions on Machine Learning Research (06/2022)
Methods
Default Parameters
LapEig
d=128
Deepwalk
d=128, walk 1ength-40, number of walks-80, window size=10
Node2vec
d=128, walk length=40, number of walks=80, window size=10, p-4.0, q=1.0
GraRep
d=128, k=4
NetMF
d=128, T=10, X=3, H=128
MNMF
d=128, alpha=0.1, beta=10
Line
d=128, samples=10 10 billion
Verse
d=128, alpha=0.85, nogs=3
VAG
d=128, h-128
WYS
d=128, hops=5
SDNE
d=128, alpha=0.2, beta=5
Hope
d=128, alpha= spectral radius
Unsup GS
1=128, walk length=40, number of walks=80,
RW framework
d= algoritmm-factorizztion, markov-time=100 similarity=PPM
Poincaré
d=128, manifold-poincare, negative 5implee--5,.mooellddiiseeee
Table 7: The parameters considered to be default on our experiments in Section and Section
35


Reviews:
[{"review_id": "pQmUvUEYGU", "reviewer": "Reviewer_V52y", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n- Paper is written very clearly and is a pleasure to read. \n- Valuable benchmarking and evaluation contributions .\n- Consideration of task-specific baselines and heuristics and showing they too can be competitive with various DL methods. \n- Providing evidence for what has been an open secret in the GRL community -- that most methods don't offer any significant advantage -- if all the baselines are tuned carefully. \n- Some dataset level analysis to understand poor performance in some and good performance in others. \n\nWeaknesses:\nI could suggest a bunch of more recent baselines and also to evaluate heterogeneous methods such as metapath2vec. However, I am quite happy with the paper's contribution (and the methods considered) in its current state, so I would resist that temptation (except for one case -- see below). ", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an extensive benchmarking effort comparing popular unsupervised graph representation learning methods, and concludes that much of the reported progress is illusory. Much work in the area (as also noted by the authors) seems to be motivated by the extreme simplicity of DeepWalk, which seems to tantalizingly suggest that development of methods that can improve up on it should be easy. As a consequence, many new methods have been proposed. However, as might be somewhat frustratingly clear to many practitioners working in the area, it has never been quite clear if any of these methods offer any significant benefit despite the reported results in papers. In many of these papers, context-specific/task specific baselines are rarely considered, and unfortunately the baselines are also set to default parameters and rarely tuned. This situation necessitates a careful benchmarking of these methods, a gap which this paper fills. Empirical work of a similar flavour was done by Goyal and Ferrera (2018) and Khosla et. al (2019), but the current paper could be considered more current and rigorous (amounting to a total of 375,000 experiments). \n\nSome of the main contributions + findings of the paper include: \n- Providing a standard evaluation protocol to allow fair comparison of such methods, including for the careful tuning of all the methods and the baselines considered. \n- Benchmarking many task-specific baselines that have been proposed by the network community (and rarely considered in the DL literature), along with adding context specific information. \n- When compared rigorously, most of the methods perform similarly to DeepWalk, with the exception of MNMF and WYS, which offer a slight advantage. \n- Task-specific baselines can often be competitive with all the methods considered.  \n- Careful tuning of various baselines can lead to somewhat surprising gains (compared to reported in many papers), even for methods such as EigenMaps of Belkin and Niyogi. \n- Adding context specific embeddings generally helps performance for methods such as LINE and WYS, while it hurts performance for the factorization methods. \n\nSome secondary findings include: \n- Datasets with high sparsity tend to have poor link prediction performance across the methods considered. Similarly, link prediction performance seems to be poor on datasets with a low clustering coefficient. \n- Several node classification heuristics offer competitive performance to many recent methods when the number of classes are low. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I would prefer to see some more analysis of Deep Graph Infomax. It seems to perform poorly compared to DeepWalk, however the discussion has been relegated to the appendix and is carried out for a couple of cases. Preferably it should be treated as a first class citizen in the paper wherever possible and added along with other methods.  This is because it is indeed quite popular (and also does not quite give good performance). A brief discussion in the appendix (pointed at by \"community feedback\" in the main article) comes across as a little off. ", "broader_impact_concerns": "No impact concerns. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "LORMXP22tJ", "reviewer": "Reviewer_X49W", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general I am evaluating this submission's claims based on the following questions:\n- Are the methods studied recent/state-of-the-art?\n- Are they evaluated objectively/thoroughly?\n- Do the empirical findings support claims of underperformance?\n\nThe paper is strongest on the last question, i.e. insightful conclusions follow from the empirical results. However, the first 2 can be improved significantly\n\n### Strengths\n- Good example of a survey paper including extensive empirical study to confirm/deny/unify previous findings\n- Includes simple baselines based on neighborhood overlap and classical node features\n- Source code is publicly available\n- Well written and organized\n\n### Weaknesses\n- Methods are not recent\n    - All methods considered are from 2018 or earlier, which hurts the claim that they are recent and/or state-of-the-art. The most recent [1] appears only in the Appendix, and is 3 years old at the time of this review. Even some important circa-2018 lines of work such as hyperbolic embeddings [2,3] are missing. An updated version of the paper would include more recent work, for example [4-6] and references therein\n- Concerns about evaluation/methodology\n    - How standard is the construction of train and test sets? For example, \"Nodes present in the test set, but not present in the training set, are deleted from the test set.\" How many nodes does this remove? Another approach would be to learn representations for these nodes during training using negative edges. This could contribute to why so many methods often perform very similarly in experiments. Therefore, it deserves a more detailed justification and/or comparison of multiple approaches.\n    - The hyperparameter search [0.1, 0.5, 1.0] learning rate $\\times$ [50, 100] epochs could be quite limiting, and could be improved with learning rate decay and/or early stopping\n- Additional evaluation\n    - Following [2-3], it may be beneficial to evaluate link prediction score with mean average precision in addition to AUC. Precision of positive edges emphasizes the representation's local structure\n    - Euclidean distance is another common ranking score which could produce different performance than dot product ranking\n    - Many experiments evaluate the impact of a system parameter by comparing the average AUC or F1-score improvement for each algorithm. These insights are usually consistent with intuition, for example nonlinear classifiers are more expressive and should perform better than linear classifiers. Additionally, the authors could show how the relative ranking of methods changes with evaluation strategy, context embeddings, etc.. Do the best methods get better, or do weaker methods overtake stronger ones?\n    - Link prediction and node classification are important downstream tasks for graph representations. The paper would be strengthened by considering additional tasks such as graph classification (e.g. [7]), or by explaining why this is out of scope\n- Presentation\n    - Box plots are helpful but could be improved by adding vertical gridlines and the statistical significance discussed in the text\n\n[1] Veličković et al., Deep Graph Infomax, ICLR 2019. https://arxiv.org/abs/1809.10341\n\n[2] Nickel and Kiewla, Poincaré Embeddings for Learning Hierarchical Representations, NeurIPS 2017. https://arxiv.org/abs/1705.08039\n\n[3] Nickel and Kiewla, Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry, ICML 2018. https://arxiv.org/abs/1806.03417\n\n[4] Gasteiger et al., Diffusion Improves Graph Learning. NeurIPS 2019. https://arxiv.org/abs/1911.05485\n\n[5] Agarwal et al., Towards a Unified Framework for Fair and Stable Graph Representation Learning, UAI 2021. https://arxiv.org/abs/2102.13186\n\n[6] Liu et al., Graph Self-Supervised Learning: A Survey. https://arxiv.org/abs/2103.00111\n\n[7] Togninalli et al., Wasserstein Weisfeiler-Lehman Graph Kernels. NeurIPS 2019. https://arxiv.org/abs/1906.01277", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper surveys several recent methods for graph representation learning. The main contribution is a detailed set of experiments and analyses to evaluate whether progress has been made on the standard downstream tasks of edge prediction and node classification. This includes proposing a large collection of standard datasets and several simple baselines. The authors conclude that fairly little progress has been made in recent years, with classical baselines performing well and with little statistically significant improvements over DeepWalk (2014).", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "### Critical\n- Include more recent related work on network representations ([2-6] for a non-exhaustive sampling)\n- Improve methodology for constructing train/test sets and tuning hyperparameters (see above)\n- Merge discussion/results of [1] from the Appendix into the rest of the paper\n- Show the impact of evaluation strategy, context embeddings, etc. on the ranking of representation methods for each task (see above)\n\n### Non-critical\n- Evaluation\n    - Include Euclidean distance and mean average precision for link prediction\n- Presentation\n    - Include p-values in box plot figures (see above)\n    - Dataset Specific Analysis subsections 7.1.G and 7.2.G could be summarized in a table of dataset property $\\times$ Pearson correlation for each task\n- Misc. Questions\n    - Is the assumption $d << |V|$ fundamental, or is this due to computational limitations?\n    - How is concatenation a \"binary function on node embeddings\"?\n- Typos\n    - \"several drill down analysis\" should be \"analyses\"\n    - \"lever a learning rate parameter\" should be \"leverage\"\n", "broader_impact_concerns": "This paper's findings are agnostic to whether graph representations satisfy broader impact considerations such as fairness and interpretability. The authors should state this or perform additional experiments to strengthen their contributions. Analyzing the per-class error rates of node classifiers (or other more rigorous fairness metrics) in addition to micro/macro F1 would help determine whether any progress has been made in this direction.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "nBSc7TugAG", "reviewer": "Reviewer_tvky", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n* The performed experiments for benchmarking unsupervised graph representation methods are extensive.\n* The authors faithfully tune the hyperparameters for every model, to accurately evaluate different methods.\n\n---\n\n# Weaknesses\nOverall, there should be more empirical results and analyses to benchmark different methods.\n* The performance for two downstream tasks (i.e., node and link prediction) is not enough to evaluate various methods. The authors should also provide more in-depth analyses about the representation space. For example, does the learned representation space accurately reflect the important node property, such as degree, page rank, clustering coefficient, to name a few?\n* The authors use the test dataset to tune the hyperparameters. Hyperparameter tuning should be done with validation sets.\n* A lack of analyses on efficiencies. In particular, the performance gains from the method should be evaluated along with its time and memory complexity. Does the complex the model, the higher the performance?\n* A lack of recent large-scale benchmark datasets, namely Open Graph Benchmark [1].\n* There should be more recent unsupervised graph embedding methods to benchmark [2, 3, 4]. All the compared models outlined in Table 2 are the works before 2019.\n\n---\n\n[1] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS 2020.\n\n[2] Hassani et al. Contrastive Multi-View Representation Learning on Graphs. ICML 2020.\n\n[3] Peng et al. Graph Representation Learning via Graphical Mutual Information Maximization. WWW 2020.\n\n[4] Mo et al. SimpleUnsupervisedGraphRepresentationLearning. AAAI 2022.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper provides extensive benchmark studies of various unsupervised graph representation learning methods across many different datasets. The main focus of this study is to identify whether the advanced methods can outperform the simple DeepWalk baseline, and the authors conclude that most of the recent methods cannot do so, especially on the link prediction task. Also, the suggested simple network properties-based methods show decent performances on node classification and link prediction tasks, thus the authors suggest the community use such simpler models as baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "# Suggestions \n**that critically affect my recommendation**\n* The authors should evaluate the embedding space of compared methods. Does the embedding space reflect the heuristic properties of nodes and edges, for example, node degrees or centralities? Performances alone are not enough to benchmark several models. Also, it is recommended to analyze the embedding space with spectrum analysis to identify the important signals.\n* The authors should re-evaluate different methods: tuning the hyperparameters with validation sets and then reporting the final performances with test sets, not equally using test sets for both.\n* The authors should include the results on more recent OGB datasets [1] and more recent unsupervised learning methods [2, 3, 4]. \n* The authors should include the discussions on efficiencies of different models, to see the performance gains with models' complexities.\n\n---\n\n# Suggestions \n**that would strengthen the work in my point of view**\n* It is better to change the title. The main focus of this work is the benchmark study of different unsupervised network representation methods, and I think there should be the word benchmark in the title. When I first saw the title, for me, it is hard to understand this paper is relevant to the benchmark study.\n* The description of every method in Table 2 is not enough. This paper is not self-contained, as the readers who are not familiar with the compared methods in Table 2 must jump to the original paper to understand the methods.\n* The authors provide only the ranges of the candidate hyperparameters. It is better to provide also the searched hyperparameters that perform the best.\n* It is better to visually illustrate the dataset preprocessing procedures in the \"Construction of the train and test sets\" paragraph of Section 6.1 Link prediction.\n\n---\n\n# Questions\n**that should be also additionally clarified in the paper**\n* Does the authors use the hyperparameters from the original paper, or arbitrarily search for the hyperparameters without including the original ones?\n* What is the meaning of default parameters in H. Default vs Tuned Parameters?", "broader_impact_concerns": "While there are no explicit sections for a broader impact statement in this paper, I think there are no concerns about the ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper examines a number of existing approaches for unsupervised network representation learning and identifies under what conditions each method performs well. Using several different datasets, the paper shows that several recently proposed improvements provide marginal gains over strong baselines and points to the need for more rigorous tuning for baselines. The paper also analyzes the role of various factors of the task (e.g. neighborhood context) on the relative performance of the different algorithms. 

The reviewers find the paper to be well-written, the study to be extensive in testing the findings of prior work and providing sufficient insights that will be of interest to the community, but also note some areas for improvement. Hence, I am recommending acceptance subject to the following revisions:
1. The authors should tone down the claims to make them more accurately reflect the empirical studies performed, including the scope of datasets, methods, preprocessing, downstream tasks (node classification, link prediction) investigated. This will entail some rewriting to parts of the paper and the addition of these caveats at places like the abstract, introduction and results.
2. Related to the above, the paper should provide more justification/discussion on why a method like DeepWalk serves as a good baseline and why some of the more recent methods mentioned by the reviewers are not considered. The authors mention some of this in their response, but this should be incorporated into the paper.
3. The paper should also clearly state the procedure for hyperparameter tuning, including the range of hyperparameters tried out, cross-validation method, etc. Also, clarify the preprocessing procedure and discuss how it compares to preprocessing in prior work. And for both these areas, discuss any limitations/caveats in the choices that may apply to the reader’s interpretation of the results.
4. Finish incorporating the promised results for the Poincare method which is currently in progress.

While not a required revision, I also highly encourage the authors to add some fine-grained analysis (e.g. error analysis) to shed some more light on why DeepWalk remains a strong baseline and to provide actionable insights for future work to improve these methods, which I believe will further strengthen this paper. The authors are in especially a good position to do this due to their extensive empirical study across several datasets that rules out some confounding factors usually arising in smaller-scale experimentation.
Decision: Accept (poster)