Existing network embedding approaches tackle the problem of learning low-dimensional node representations. However, networks can also be seen in the light of edges interlinking pairs of nodes. The broad goal of this paper is to introduce edge-centric network embeddings. We present an approach called ECNE, which instead of computing node embeddings directly, computes edge embeddings by relying on the notion of line graph coupled with an edge weighting mechanism to preserve the dynamic of the original graph in the line graph. We also present a link prediction framework called ECNE-LP, which given a target link $(u,v)$ first collects paths between nodes $u$ and $v$, then directly embeds the edges in these paths, and finally aggregates them toward predicting the existence of a link. We show that both ECNE and ECNE-LP bring benefit wrt the state-of-the-art.

§ INTRODUCTION

The problem of learning network representations, in the form of low-dimensional embeddings, has been extensively studied in the last years [4, 24]. In particular, a variety of approaches has been proposed to learn node embeddings such that nodes that are (structurally) similar have embeddings that are close together. Early work like Deepwalk [17] and node2vec [9] to define node similarity leverage the notion of context, which mimics on graphs the reasoning behind the SkipGram model used to learn word embeddings from text [14].
Here, random walks in a graph (i.e., sequences of neighborhood nodes) play the same role as text sentences (i.e., sequences of words).  Struc2vec [19] is a more recent approach also based on random walks. LINE [20] guides the generation of random walks by using 1-hop and 2-hop neighborhoods. On the other hand, SDNE [22] uses autoencoders to preserve structural similarity. A very recent piece of work is NetMF [18], which bridges the worlds of matrix factorization and random-walk-based approaches.

Other categories of node embedding techniques include Graph Neural Networks (GNNs) that refine the notion of node neighborhood; for instance, GraphSage [10] incorporates fixed-size neighborhood information of nodes when computing their embeddings. Graph Convolutions Networks (GCN) [11] port the convolutions operations on graphs while Graph Attention Networks (GAT) introduce mechanisms to weight the importance of all neighbors [21]. Despite the variety of existing approaches, we observe that all of them have focused on learning node embeddings only, although networks can also be seen in the lights of their edges.

§.§ Motivation

Edge-centric views of networks have shown their usefulness in a variety of tasks. Evans and Lambiotte [7] studied how to define communities as a partition of the links rather than the nodes of a network. It has been shown that link communities naturally incorporate overlap while revealing hierarchical organization and that a link-based approach is superior to existing node-based approaches  [2] especially when one needs to find overlapping communities. Edge-centric network analysis is very important in biology and spans from the analysis of reaction networks [15] to the human connectome [5], that is, the network resulting from neural interactions.

We observe that embeddings gained popularity much later than the above-mentioned pieces of work [14]. Therefore, we believe that rethinking edge-centric tasks on the light of edge embeddings can provide a refreshing perspective. We will provide an extensive evaluation on the task of edge-centric community detection (<ref>). Furthermore, a number of recent applications making usage of node embeddings can be also rethought of in the light of edge embeddings. As an example, we show how recent approaches for link prediction that leverage paths between a pair of nodes to establish the plausibility of a link between them (e.g., [1]), can benefit from edge embeddings. With our approach, instead of vectorizing paths as sequences of node embeddings, we can vectorize them as sequences of edge embeddings able to better capture the peculiarity of each link in a path (<ref>).

§.§ Contributions and Outline

We set two main goals in this paper. The first is to present a framework to directly learn edge embeddings instead of node embeddings. The second is to show the usefulness of edge embeddings in the task of link prediction (see [13] for a survey), which is usually tackled by leveraging node embeddings.

To tackle the first goal, we introduce the Edge Centric Network Embedding () technique, which relies on the notion of line graph of a graph [23].  The line graph $\lkg$  of a graph $G$ is such that its nodes are edges of the original graph and an edge is inserted between adjacent nodes (i.e., edges sharing a node).

Once the line graph is available, our approach could benefit from any existing node embedding technique (e.g., node2vec, Deepwalk, sdne, GraphSage) as learning node embeddings of $\lkg$ leads, by construction, to learn the embeddings of the edges of $G$. However, directly working with $\lkg$, leads to low-quality embeddings because edges in the $\lkg$ are added based on adjacency; basically, nodes having a high-degree in $G$ get over-represented in $\lkg$, which does not correctly reflect the dynamics of $G$ in  $\lkg$. To overcome this problem,  introduces an edge weighting strategy for $\lkg$ based on the centrality of nodes of $G$.  However, the size of the line graph is usually much larger than that of the original graph. To overcome this issue, in the implementation of  we make usage of a recent graph coarsening strategy [12].  The idea is to repeatedly coarsen the (line) graph into smaller ones, apply any embedding method on the coarsest graph and refine the embeddings to the original graph through a graph convolution neural network. We show that 's direct edge embedding approach can scale to large graphs and brings an improvement as compared to the indirect way based on the aggregation of edges endpoints' embeddings (<ref>).

To tackle the second goal, we present a learning model called , which starts by collecting paths between the nodes $u$ and $v$ for which the existence of a link has to be estimated. Then, it embeds the edges in these paths via , and finally aggregates them, according to different strategies, toward providing a verdict for the $(u,v)$ link.

The main contributions of this paper are as follows:

* A direct way to compute edge embeddings based on the notion of line graph;

* an edge-weighting mechanism for the line graph, which preserves the dynamics of the; original graph in the line graph;

* an approach for link prediction based on path embeddings;

* an extensive experimental evaluation and comparison with related work.

The remainder of the paper is organized as follows. We provide some definitions (<ref>). Then, introduce  (<ref>) and the  link prediction approach (<ref>). We report on an experimental evaluation (<ref>), draw some conclusions and sketch future work (<ref>).

§ PRELIMINARIES

works on a given graph $\kgDef$, where $V_G$ is the sets of node and $E_G$$\subseteq V_G \times V_G$ is the set of edges. An edge can be directed or undirected, weighted or unweighted, and signed or unsigned. A path $\pi$ of length $l$ between the pair of nodes $(u,v)$ consists of a sequence of the from $\pi$=($u_0$,$u_1$),...,($u_k$,$u_l$), with $u_0$=$u$ and $u_l$=$v$.
We denote by $\Pi^l_{(u,v)}=\{\pi_1^l,\pi_2^l,...\pi_n^l\}$ the set of paths of length $l$ between $u$ and $v$.

§.§ Line Graph

The main intuition behind  is to find a way to turn edges of the original graph into nodes and then apply existing node-embeddings methods. The notion of line graph [23] is crucial toward this goal.

Given a graph $\kgDef$, its line graph $\lkg=(V_L,E_L)$ is such that: (i) each node of $\lkg$ represents an edge of $\kg$; (ii) two vertices of $\lkg$ are adjacent if, and only if, their corresponding edges in $\kg$ have a node in common.

Starting from $\kg=(V_G,E_G)$ it is possible to compute the number of nodes and edges of $\lkg=(V_L,E_L)$ as follows: (i) the number of nodes of $\lkg$ is equals to the number of edges of $\kg$, i.e., $|V_L|=|E_G|$; (ii) the number of edges is $|E_L| \propto \frac{1}{2} \sum_{v\in V_G} d_v^2 -|E_G|$, where $d_{v}$ denotes the degree of the node $v\in V_G$.
The concept of line graph has been extended to other types of graphs, including multigraphs and directed graphs.

§.§ Node Embeddings

Given a graph $\kgDef$ and a predefined dimensionality $d$ ($d$$<<$$|V_G|$), the problem of graph embedding is to learn a $d$-dimension vector representation for each node in $\kg$ that best preserve the properties of $G$. If we see a graph as an adjacency matrix, an embedding is essentially a function  $f_n$: R$^{|V_G|\times|V_G|}$ $\to$ R$^{|V_G|\times d}$, which maps the adjacency matrix to a lower dimension matrix. Motivated by the fact that existing graph embedding methods focus on the embeddings of nodes, our goal is to define a direct way for computing edge embeddings. In other words, given a graph $\kgDef$, devise an edge embedding function $f_e$: R$^{|E_G|\times|E_G|}$ $\to$ R$^{|E_G|\times d}$, this time considering edge-adjacency.

§ : EDGE-CENTRIC NETWORK EMBEDDINGS

We now outline th edge-centric network embedding approach. The idea is to leverage the line graph of a graph where edges of the original network become nodes. With this in mind, once the line graph of a graph has been constructed, any existing node embedding approach can be used in principle. However, we show that directly working on the line graph is not enough and present a strategy to learn more precise edge embeddings (<ref>).

§.§ Weighted Line Graph

The structure of the line graph $\lkg$ is such that high-degree nodes in the original graph $G$ are over-represented in the line graph; a node of $G$ having degree $k$ creates $k(k-1)/2$ edges in $\lkg$. While the Whitney graph isomorphism [23] does guarantee that the line graph preserves the topology of the original graph, it does not offer the same guarantee when it comes to the dynamics. This can be better understood in terms of how a random walker walks in $G$ and $\lkg$.

In general, a random walk on each node of $G$ will pass along a generic edge $e$ with a certain frequency $f^e$. As this edge is mapped to node $v_e$ in $\lkg$, the same random walk on $\lkg$ the frequency of visiting $v_e$ can be completely different from $f^{v_e}$. Concretely, if we were to apply approaches like Deepwalk or node2vec to $\lkg$ as it is, we would obtain low-quality embeddings as also confirmed by experiments on several networks in an early-version of .

To overcome this issue, one can think of a weighting mechanism. [6] (page 7), proposed a weighted line graph where edges are scaled by a factor $O(1/k)$. In this work, we consider an edge weighting mechanism based on current-flow betweenness [3], which considers the importance of each node in a graph in terms of the number of times it lies on a path between two other nodes (note that it extends the notion of betweenness centrality which focuses on shortest paths only). This allows to better differentiate the edges in $\lkg$ assigning a value that does not only depend on the degree of a node of $G$.

In particular, the edge from $n_p$=$(i,j)$ to $n_q$=$(j,k)$ in $\lkg $ (representing a path from $i$ to $k$ passing through $j$ in $\kg$) is assigned a weight as follows:

$$w(n_p, n_q)= 1/cb(i) + 1/cb(j) + 1/cb(k)$$

with $cb(x)$ being the current-flow centrality of the node $x$ in $G$, with $x \in \{i,j,k\}$. We leave the investigation of other weighing mechanisms as future work.

§.§ Computing Edge Embeddings

Once the (weighted)  line graph is available,  can learn the final edge embeddings by using a variety of existing techniques (e.g., Deepwalk [17], node2vec [9], SDNE [22]). In the current implementation  uses a language model approach based on a set of truncated random walks $\mathcal{W}$. The embedding  learns is a function $f_e:\mathcal{V}_L\rightarrow {R}^d$, which projects nodes of the weighted line graph $\lkg$ into a low dimensional vector space, where $d \ll |\mathcal{V}_L|$, so that neighboring nodes are close in the vector space.
For every node $u \in \mathcal{V}_L$, $N(u)\subset \mathcal{V}_L$ is the set of neighbors and the co-occurrence probability of two nodes $v_i$ and $v_{i+1}$ in a set of walks $\mathcal{W}$ is given by:

\begin{equation}\label{eq:nextnode}
p((e_{v_i},e_{v_{i+1}})\in \mathcal{W}) =\sigma(e_{v_i}^Te_{v_{i+1}})
\end{equation}

where $\sigma$ is the softmax function and $e_{v_i}^Te_{v_{i+1}}$ is the dot product of the vectors $e_{v_i}$ and $e_{v_{i+1}}$
As the computation of (<ref>) is demanding [9], we use negative sampling to training the Skip-gram model [14]. Negative sampling randomly selects nodes that do not appear together in a walk as negative examples, instead of considering all nodes in a graph.

§ PATH EMBEDDING FOR LINK PREDICTION

We now focus our attention on the link prediction task (see [8] for a survey) and present an approach called , which leverages edge embeddings. As the goal of this paper is not to specifically tackle link prediction, but to show the potential usage of edge embeddings in a downstream application, we consider the state-of-the-art LEAP system [1] and adapt it to use edge embeddings instead of node embeddings.

The problem we face can be stated as follows: given a pair of nodes $(u, v)$ assess whether a link between them should hold. The idea is to leverage paths between $u$ and $v$ to collect structural information that can help in assessing the plausibility of a link between $u$ and $v$.  is outlined in Fig. <ref>. It includes three main modules: (i) path extractor; (ii) path embedder; (iii) path aggregator, (iv) link predictor. We will outline each of them in the following.

Overview of . Paths are grouped and processed for each length $l$ and then embedded (Path Embedder). An overall path representation is learned (Path Aggregator), which is used to train a binary classifier (Link Predictor).

§.§ Path Finder

This module is responsible for finding a set of paths between nodes $u$ and $v$ that will help in assessing the plausibility of the link $(u, v)$. Due to the potential large number of paths, to make this step practically feasible in all networks considered in the experiments (<ref>), we use the efficient graph-tool library[<https://graph-tool.skewed.de/>] to obtain paths. We note that also LEAP starts from a set of paths between the nodes $u$ and $v$. However, what makes  is the way these paths are embedded  for link prediction.

§.§ Path Embedder

To be processed by the link prediction learning model, paths found by the Path Finder are given a numerical representation. While state-the-art approaches for link prediction, including our direct competitor LEAP [1], consider paths as sequences of node embeddings,  considers them as sequences of edge embeddings. Consider the paths $\pi_1$=$n_0$-$n_7$-$n_1$ and $\pi_2$=$n_2$-$n_1$-$n_4$-$n_0$. While approaches based on node embeddings will consider in these paths the same embeddings $\emb{n_0}$ and  $\emb{n_1}$ for the nodes $n_0$ and $n_1$,  will consider the specific edge embeddings $\embE{n_0,n_7}$, $\embE{n_4,n_0}$, $\embE{n_7,n_1}$, and $\embE{n_2,n_1}$ for the edges involving these nodes. This will help the learning model to better represent and differentiate paths.
The  function $\cdot$ used to vectorize each edge in a path  can use either a direct or indirect approach.  The direct  approach is to use  where a path $\pi$={$e^1,e^2,\ldots e^l$} of length $l$ including $l$ edges is encoded as a sequence $\pi_E$=[$e_E^1,e_E^2,\ldots,e_E^l$], where $e_E^i$=($e^i$).

As for the indirect way, one can start with node embeddings found by any existing mechanism (e.g., node2vec  [9], Deepwalk [17], etc) and consider a generic function $\cdot$, which given a node, returns its corresponding vector embedding. Hence, to compute the embedding of an edge $e$=$(u,v)$, we can perform some operation $op$ (e.g., concatenation) on its constituents vectors, that is, $e$=$op(\emb{u},\emb{v})$. As an example, Grover and Leskovec [9] considered some operators (e.g., average, Hadamard product) over the embeddings of individual node found via node2vec for link prediction.

§.§ Path Aggregator

Paths converted into their vector form are given an aggregate representation. We see aggregation as a black-box learning module, which takes the vectorized paths and provides an overall vector representation for them. Aggregation has been extensively considered in the literature (e.g., [10]). In this paper, as our direct competitor is LEAP, we use the  three aggregation strategies used by LEAP.

§.§.§ Average Pool

This kind of aggregator combines the different representations of paths by concatenating the vector representations of the edges in a path. Then on the set of paths obtained, the aggregator performs a 1D average pooling operation. The final combined path representation is a single vector obtained by averaging the paths between $u$ and $v$ of length $l$. The whole operation can be summarized as follows:

\begin{equation}
\mathcal{P}_V^l={AvgPool([\oplus(\pi_i^l), \forall \pi_i^l \in \mathcal{P}^l])}
\end{equation}

where $AvgPool$ is the one-dimensional average pooling operation, and $\oplus(\cdot)$ is the vector concatenation operation, which concatenating multiple vectors together. This representation relies on the embeddings of the edges in each path.

§.§.§ Max Pool

This kind of aggregator shares with the AvgPool the fact representation obtained, even in this case, by concatenating edge vectors; what changes is the final vector of the path. Instead of being the average, it is now computed by using a dense neural network layer. The resulting activations are then passed through a max-pooling operation which helps to derive a single vector representation for the paths of length $l$. The whole operation can be summarized as follows:

\begin{equation}
\mathcal{P}_V^l={MaxPool([ \sigma(W_l\cdot\oplus(\pi_i^l)+b_l), \forall \pi_i^l \in \mathcal{P}^l])}
\end{equation}

where $MaxPool$ is the one-dimension max pool operation (which selects bit-wise the maximum value from multiple vectors to derive a single final vector.), $W_l$ are the weights to be learned, $b_l$ the bias, and $\sigma$ the activation function.

§.§.§ LSTM Max Pool

We now outline the most sophisticated aggregator we considered. The idea is to treat a (vectorized) path as a sequence an employ an LSTM network to cater for sequential dependencies between edges in a path. With this reasoning, each edge in a path represents a point of a sequence. Fig. <ref> provides an overview of the architecture of the LSTM Max Pool aggregator. At each step $l-1$,  the  LSTM layer outputs a hidden state vector $h_{l-1}$, consuming sub-sequence of embedded edges $[f_1,..., f_{l-1}]$. In other words, $x_{l-1}$=$f_{l-1}$. The input $x_{l-1}$ and the hidden state $h_{l-1}$ are used to learn the hidden state of the next path step $l$.

As our final goal is to leverage the representations of all paths, after processing all of them via the LSTM, the aggregator employs another LSTM followed by a max pool operation (see Fig. <ref>) to produce the combined path representation $\mathcal{P}_V$.

An overview of the LSTM Max Pool Aggregator.

Summary of the datasets used for evaluation.

Task                              Name     Nodes     Edges
2*                          Karate Club       34                 78
Power Grid        4,941              6,594
Classif & Clustering     Facebook          4,039              88,234
3*                          Erdos             6,100              9,939
Astrophysics      17,900             197,000
ArXiv             18,772             198,110
USAir             332                2,126
NS                1,589              2,742
Link Prediction                   PB                1,222              16,714
C. Ele            297                2,148
E. coli           1,805              14,660
ArXiv             18,772             198,110
DBLP           123,456          651,756

§.§ Link Predictor

As paths are grouped according to their different lengths, the aggregation mechanism processes each set of paths separately. Finally, the path representations for each length are concatenated together to give the final length-specific path representation $\mathcal{P}_V$ (see Fig. <ref>).

The last step consists of providing the final prediction about a link. This is done by the link predictor module, which takes as input the output of the Path Aggregator (i.e., the vector representation $\mathcal{P}_V$) and feeds it into a classifier. We treat the link prediction problem as a binary classification problem, where an existing link and non-existing link are assigned 1 and 0 as target values, respectively. The final goal is to optimize the negative log-likelihood objective function, which defined  as follows:

\begin{equation}
\mathcal{L}=- \sum_{f^+  \in \mathcal{F}^+}   log \ \hat{y}_{f^+} + \sum_{f^-  \in \mathcal{F}^-}log(1- \ \hat{y}_{f^-})
\end{equation}

where $\mathcal{F}^+$={$f^+\mid y_{f^+}=1$} and $\mathcal{F}^-$={$f^+\mid y_{f^-}=0$} are the true and false links, respectively. Given a target link $({u}, {v})$, the link predictor outputs a plausibility score $\eta \in [0,1]$.

§ EVALUATION

The goal of the experimental evaluation was twofold. First, to show that directly computing edge embeddings leads to better performance as compared to indirect edge embeddings obtained from edges' endpoints. Second, to show that edge embeddings are useful in applications where paths between nodes in a network can be exploited. The framework has been implemented in Python using Keras[<http://keras.io>].

Moreover, to make the computation of (edge) embeddings feasible on the line graph, which usually contains a larger number of nodes, the implementation of  leverages the MILE framework [12]. It uses MILE[<http://jiongqianliang.com/MILE/>] to repeatedly coarsen the weighted line graph into smaller ones, apply the embedding method described above on the coarsest graph and refine the embeddings to the original graph via graph convolution. We make available the code of [The code is available upon request.]

§.§ Datasets and Experimental Setting

We performed experiments to investigate the above-mentioned goals on the real-world datasets summarized in Table <ref>. The datasets for edge classification and clustering are popular networks[We downloaded them from <http://snap.stanford.edu>] used in the context of community detection [9].
As for link prediction, we considered the datasets used to evaluate the state-of-the-art LEAP systems [1], which is our direct competitor[<https://github.com/rakshit-agrawal/LEAP>].

[legend columns=8,legend style=align=left,draw=none,column sep=0ex,legend entries=,,NetMF,node2vec, Deepwalk, struct2vec, sdne, GraphSage]
color=violet!90!black, mark=triangle*, mark size=4pt
color=violet!70!black, mark=triangle, mark size=4pt
color=blue, mark=diamond*, mark size=4pt
color=black, mark=square*, mark size=4pt
color=brown, mark=star, mark size=4pt

color=red!90!black, mark=triangle, mark size=4pt
color=green, mark=star, mark size=4pt
color=blue!90!black, mark=square, mark size=4pt

xlabel=% Labeled nodes from $\lkg$,
title=Karate Club,
file[x index=0, y index=0.2] evaluation/karate/karate_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_graphsage_micro.txt;

xlabel=% Labeled nodes from $\lkg$,
title=Karate Club
file[x index=0, y index=0.2] evaluation/karate/karate_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/karate/karate_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/karate/karate_graphsage_macro.txt;

xlabel=% Labeled nodes from $\lkg$,

title=USA Power Grid,
legend style=at=(-0.6,-0.3),anchor=west,
file[x index=0, y index=0.2] evaluation/power/power_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/power/power_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/power/power_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/power/power_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/power/power_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/power/power_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/power/power_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/power/power_graphsage_micro.txt;

xlabel=% Labeled nodes from $\lkg$,
title=USA Power Grid
file[x index=0, y index=0.2] evaluation/power/power_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/power/power_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/power/power_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/power/power_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/power/power_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/power/power_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/power/power_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/power/power_graphsage_macro.txt;

xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/facebook/facebook_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_graphsage_micro.txt;

legend style=at=(-0.3,-0.3),anchor=west,
legend columns=-1,
xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/facebook/facebook_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/facebook/facebook_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/facebook/facebook_graphsage_macro.txt;

xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/erdos/erdos_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_graphsage_micro.txt;

legend style=at=(-0.3,-0.3),anchor=west,
legend columns=-1,
xlabel=% Labeled nodes from $\lkg$,
file[x index=0, y index=0.2] evaluation/erdos/erdos_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/erdos/erdos_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/erdos/erdos_graphsage_macro.txt;

xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/astro/astro_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_graphsage_micro.txt;

legend style=at=(-0.3,-0.3),anchor=west,
legend columns=-1,
xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/astro/astro_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/astro/astro_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/astro/astro_graphsage_macro.txt;

xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_ecne_micro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_ecned_micro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_NetMF_micro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_node2vec_micro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_deepWalk_micro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_struct2vec_micro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_sdne_micro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_graphsage_micro.txt;

legend style=at=(-0.3,-0.3),anchor=west,
legend columns=-1,
xlabel=% Labeled nodes from $\lkg$,

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_ecne_macro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_ecned_macro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_NetMF_macro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_node2vec_macro.txt;
file[x index=0, y index=0.2] evaluation/arxiv/arxiv_deepWalk_macro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_struct2vec_macro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_sdne_macro.txt;

file[x index=0, y index=0.2] evaluation/arxiv/arxiv_graphsage_macro.txt;

Edge classification on varying the amount of labeled data used for training (average of 5 runs).

[legend columns=8,legend style=align=left,draw=none,column sep=0ex,legend entries=, , NetMF, node2vec, Deepwalk, struct2vec, sdne, GraphSage]
color=violet!90!black, fill=violet!90!black,mark=square*,  only marks, mark size=4pt
color=pink, fill=pink,mark=square*,  only marks, mark size=4pt
color=blue, fill=blue,mark=square*,  only marks, mark size=4pt
color=black, fill=black,mark=square*,  only marks, mark size=4pt
color=brown, fill=brown,mark=square*,  only marks, mark size=4pt

color=red, fill=red,mark=square*,  only marks, mark size=4pt
color=green!90!black, fill=green!90!black,mark=square*,  only marks, mark size=4pt
color=yellow, fill=yellow,mark=square*,  only marks, mark size=4pt

width  = 0.5*,
height = 4.2cm,
xlabel = Karate Club,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,
scaled y ticks = false,
enlarge x limits=1,
legend pos=outer north east]
coordinates (T,1.0) +- (0.0, 0.5);
coordinates (T1,1.0);
coordinates (N,0.98834);
coordinates (D,0.89556);
coordinates (E,0.895356);

coordinates (S,0.901373);
coordinates (ST,0.89214);
coordinates (GS,0.93456);

width  = 0.5*,
height = 4.2cm,
xlabel = Erdos,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,

scaled y ticks = false,
enlarge x limits=1,

legend pos=outer north east]

coordinates (T,.955);
coordinates (T1,.9612);
coordinates (N,0.93234);
coordinates (D,0.9056);
coordinates (E,0.89374);

coordinates (S,0.901234);
coordinates (ST,0.912323);
coordinates (GS,0.92151);

width  = 0.5*,
height = 4.2cm,
xlabel = Facebook,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,

scaled y ticks = false,
enlarge x limits=1,
y tick label style=
/pgf/number format/fixed

legend cell align=left,
legend style=
anchor=north,legend columns=-1,
column sep=1ex

coordinates (T,0.95);
coordinates (T1,.937);
coordinates (N,0.8934);
coordinates (D,0.8836);
coordinates (E,0.88126);

coordinates (S,0.934);
coordinates (ST,0.8734);
coordinates (GS,0.8421);

width  = 0.5*,
height = 4.2cm,
xlabel = Power Grid,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,

scaled y ticks = false,
enlarge x limits=1,

legend pos=outer north east]

coordinates (T,.932);
coordinates (T1,.9427);
coordinates (N,0.934);
coordinates (D,0.8734);
coordinates (E,0.8421);

coordinates (S,0.88325);
coordinates (ST,0.897334);
coordinates (GS,0.9013);

width  = 0.5*,
height = 4.2cm,
xlabel = Astrophysics,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,

scaled y ticks = false,
enlarge x limits=1,

legend pos=outer north east]

coordinates (T,0.86463);
coordinates (T1,.85621);
coordinates (N,0.8218);
coordinates (D,0.8012);
coordinates (E,0.7936);

coordinates (S,0.8341);
coordinates (ST,0.84134);
coordinates (GS,0.8618);

width  = 0.5*,
height = 4.2cm,
xlabel = ArXiv,

bar width=10pt,
ymajorgrids = true,

symbolic x coords=T,T1,N,D,E,S,ST,GS,

scaled y ticks = false,
enlarge x limits=1,

legend pos=outer north east]

coordinates (T,0.784545);
coordinates (T1,.7781);
coordinates (N,0.745253);
coordinates (D,0.732424);
coordinates (E,0.72343);

coordinates (S,0.76564);
coordinates (ST,0.77212);
coordinates (GS,0.78216);

Clustering results (average of 5 runs).

We are not aware of any approach that focuses on directly learning edge embeddings. Therefore, we adapt a sample of the most popular and well-performing node embedding systems to construct edge embeddings as done by Grover and Leskovec [9]. Given an edge $e=(u,v)$, its embedding is obtained as $e$=$u$ $\circ$$v$, where $\circ$ is the average, Hadamard product, Weighted-L or Weighted-L2 operator. We considered the following competitors:

* DeepWalk learns node embeddings via random walks  and the Skip-gram model.

* node2vec improves upon DeepWalk in both the way random walks are generated (by balancing the breadth-first search and depth-first search strategies).

* NetMF [18] is a very recent piece of work, which shows that Deepwalk, LINE, and node2vec with negative sampling can be unified into the matrix factorization framework with closed forms[https://github.com/xptree/NetMF].

* struct2vec [19] is a recent approach also based on random walks, which imposes similar embeddings to nodes that are structurally similar[https://github.com/leoribeiro/struc2vec].

* SDNE [22] uses autoencoders to preserve structural similarity[https://github.com/suanrong/SDNE].

* GraphSage [10] aggregates fixed-size neighborhood information of nodes[https://github.com/williamleif/GraphSAGE].

We used the values of the parameters $n$ (number of walks per node), $L$ (max. walk length), $w$ (window size for the Skipgram model), and negative samples ($\Gamma$) in line with values used by the competitors as reported in their respective paper. Ditto for specific parameters  (e.g., $p$ and $q$ for node2vec). We set $n$=$10$, $L$=100 $w$=10, and $\Gamma$=100 for all systems in all experiments.

§.§ Setting the embedding dimension

A different strategy is adopted for the dimension of the embeddings $d$. On one hand, we note that the number of node embeddings found by the competitors corresponds to the number of nodes of the networks. In this case, we used  $d$=128 for all datasets, which is in line with values used by recent competitors (e.g., NetMF [18]).

On the other hand, we observe that for  the number of nodes (of the weighted line graph) to embed corresponds to the number of edges of the original graph, which is usually larger. This inherently makes the number of parameters for  larger. Therefore, for , we performed experiments in two different settings. The first assumes $d$=128 in all datasets,
while in the second we adapted the embedding dimensionality for each dataset in order for  to use the same number of parameters as the competitors.

We refer to this variant of  as .  For instance, for the Erdos dataset including 6100 nodes, the number of parameters used by the competitors was 6100*128=780800. In order for  to use (roughly) the same number of parameters we have to consider $d=80$ as the number of edges 9939 multiplied by 80 gives 795120.

§.§ Community Detection via Edge Embeddings

We start by presenting experiments in the task of community detection via edge clustering. While Evans and Lambiotte [7] treated the problem from a modularity-optimization perspective, our goal is to tackle this problem from an edge-embedding perspective and show its usefulness. To conduct experiments, we proceeded as follows. For each considered network in Table <ref>, we first found communities by using a modularity-based algorithm [16]. Then, for each community, intended as a set of nodes, we identified the set of intra-community edges and labeled each of such edges with the id of the community it belongs to. To evaluate  and competitors we computed the edge embeddings for each network; while for  (and ) edge embeddings are directly computed, for the other approaches we used the bootstrapping approach previously described (<ref>). After obtaining edge embeddings for all approaches, we trained a one-vs-rest Logistic regression model giving as input the edge embeddings and the labels (the community they belong to) and computed the Micro and Macro F1 scores.

Results when varying the amount of labeled data used for training are reported in Fig. <ref>. We point out that for the competitors the figure reports the best edge embeddings obtained over all the operators on node embeddings considered (<ref>). In particular, we observed that for node2vec and Deepwalk in most of the cases (e.g., on Astrophysics and ArXiv) the average of the node embeddings gave the best results while for NetFM, struct2vec, SDNE, and GraphSage in some cases (e.g., on ArXiv) the Weighted-L2 performed better.

Fig. <ref> shows that  performs better than the competitors in almost all cases. We recall that this variant of , instead of considering a fixed embedding size (i.e., $d$=128) adapts the dimension to the number of edges in the network (<ref>). It seems that for networks of moderate size ($\sim$10K edges), the size of embeddings equal to 128 leads to slightly inferior results. However, when the size of the network (in terms of edges) increases (i.e., on Astrophysics and ArXiv) we note that  performs slightly better. This may be explained by the fact that the valu of $d$ automatically set may not be enough to correctly separate edge embeddings. As an example, to obtain the same number of parameters as the competitors on ArXiv,  used $d$=20 instead of $d$=128. We also observe that when moving to larger networks the difference wrt the competitors of both  variants becomes clearer.

§.§ Experiments on edge clustering

We also completed experiments in an edge clustering task. We considered the K-means algorithm to which we gave as input both the edge embeddings obtained by  (in its two variant) and competitors and the number of clusters. In particular, the number of clusters considered coincided with the number of communities previously found. To evaluate the performance of the systems, we compute the Normalized Mutual Information (NMI), which is used to estimate the clustering quality. Results are reported in Fig. <ref>. We observe that  and  perform equally or better than the competitors in all networks.

We observe that also in this case the improvement wrt the competitors becomes clearer as the network size increases. Note that we only report the best performance for the competitors in terms of the aggregation mechanism on node embeddings that, even in this case, in most cases was the average. On the contrary, neither  nor  require aggregation as they directly learns edge embeddings.
As observed in the previous experiments, even in this case we note that  performs slightly better than  for moderately large networks. As the number of  edges of the network increases, the difference in performance is no more tangible.

We mention that the main goal of this paper neither is to specifically devise a community detection algorithm nor a clustering one. The goal is to introduce the novel task of edge-centric network embeddings and show its usefulness in concrete downstream applications. This leaves room for further investigations related to edge-driven community detection and clustering. Examples are alternative weighing mechanisms for the line graph or a different way of computing embeddings from the line graph (e.g., using SDNE instead of the Skip-graph model).

(st. dev.)                      USAir
NS        PB
EColi         ArX     DBLP    8*

(r)1-8  -LSTM        1c.964

1c .981     1c.831
1c.924       1c.995      .978

1c .011     1c.088
1c.071       1c.003             1c.013

(r)1-8-Max        1c.921

1c .967     1c.803
1c.912             1c.967     .979

1c .028     1c.039
1c.071       1c.021         .014

(r)1-8-Avg        1c.912

1c .965     1c.812
1c.911       1c.957         .948

1c .019     1c.071
1c.080       1c.042        .021

(r)1-8  -LP-LSTM        1c.971

1c .983     1c.836
1c.928       1c.993        .976

1c .016     1c.068
1c.066       1c.002           .022

(r)1-8-LP-Max        1c.922

1c .967     1c.804
1c.913             1c.968         .965

1c .026     1c.069
1c.027       1c.021         .032

(r)1-8-LP-Avg        1c.913

1c .966     1c.838
1c.912       1c.960             .951

1c .028     1c.068
1c.076       1c.028         .031

(r)1-8 LEAP-LSTM       1c.962

1c .982     1c.814
1c.926          1c.994     .976

1c .011     1c.072
1c.063       1c.001        .002

(r)1-8 LEAP-Max       1c.949

1c .942     1c.804
1c.913          1c.974          .966

1c .035     1c.069
1c.072       1c.021      .011

(r)1-8 LEAP-Avg       1c.933

1c .962     1c.798
1c.903          1c.964      .948

1c .071     1c.078
1c.078       1c.021         .014

(r)1-8NetMF       1c.887

1c .856     1c.797
1c.907         1c.947       .938

1c .102     1c.128
1c.022       1c.026        .081

(r)1-9node2vec       1c.865

1c .824     1c.767
1c.887       1c.921             .876

1c .111     1c.182
1c.109       1c.031       .103

(r)1-8Deepwalk       1c.847

1c .813     1c.772
1c.869           1c.902          .931

1c .080     1c.121
1c.115       1c.063        .012

(r)1-8struct2vec       1c.818

1c .807     1c.711
1c.901           1c.931       .897

1c .132     1c.021
1c.079       1c.042        .067

(r)1-8sdne       1c.852

1c .857     1c.802
1c.912           1c.961       .911

1c .089     1c.041
1c.084       1c.029       .037

(r)1-8GraphSage       1c.872

1c .859     1c.793
1c.907           1c.961      .911

1c .111     1c.143
1c.087       1c.012         .041

Area under the ROC curve (AUC) and standard deviation.

§.§ Link Prediction

In this set of experiments, the goal was as follows: given a graph $\kgDef$ and a pair of nodes $(u, v)$, what is the probability of the existence of the link between $u$ and $v$? To set-up the learning model described in Section <ref>, we can consider each existing edge  $(x, y) \in V_G$ as a positive example while negative examples can be sampled such that the edge $(\overline{x}, \overline{y}) \notin V_G$. With this reasoning, we assign as a label 1 to positive pairs and 0 to negative pairs.

To evaluate our proposal and compare it with competitors, we sampled a variable number of both positive and negative edges and further split them into train and test examples according to the state-of-the-art [1]. In particular, for small datasets, we leverage 90% of edges for train and the remaining for test also considering an equal number of negative edges. For datasets with more than 4K nodes, we adopt a 50% split. For our approach and LEAP (the other competitor using paths) we considered as path lengths $l=3$ and $l=4$ and used up to 100 paths for each such lengths randomly selected. To train the model, we used the Adam optimizer (and learning rate of 0.001) with binary cross-entropy for a maximum of 50 epochs with early-stop enabled. For the other competitors, we used the best configuration reported in their respective papers [1].

The competitors considered are node2vec, Deepwalk, NetFM that do not make usage of multi-hop information. We also considered SDNE and struct2vec that learn node embeddings to preserve structural similarity and GraphSage, which incorporates neighborhood information via aggregation. However, our direct competitor is the state-of-the-art LEAP [1] system, which uses embeddings on nodes in a path along with path aggregation but does not consider edge embeddings.  We have also considered variants of  that instead of considering edge embeddings computed via  (or ), compute them as done by the other competitors. In particular, we considered the average of node embeddings and the LSTM-based path aggregator. However, we found that in all cases results were inferior to the case in which embeddings were computed via  or . Therefore, for sake of space we omit these results.

Results. Table <ref> reports the results. We observe that approaches based on paths that leverage multi-hop information (rows 1-10) perform better on the task of link prediction. This comes as no surprise as the presence/absence of a link can be better understood by looking at the overall connectivity between a pair of candidate nodes for the link. We also note that computing edges with -LP gives better results for moderately large networks. On the two larger networks, , which sets the embedding dimensions to 128 performs better. This is in line with results obtained on edge-based community detection and edge clustering. We also observe that the aggregation strategy considering paths as sequences of edges (all  variants) gives better performance than when considering them as sequences of nodes (all LEAP variants) in almost all the cases.

§ CONCLUDING REMARKS AND FUTURE WORK

We introduced the task of edge-centric network embeddings. The main intuition of our approach is to directly compute edge embeddings by transforming the original network into an edge-centric network via the line graph. We discussed how directly operating on this construction leads to poor results and introduced an edge weighting mechanism for the line graph that preserves the dynamics of random walks. What also makes our approach useful is a combination of two aspects. First, it allows to revisit edge-centric tasks like community detection, that were introduced a decade ago, in the light of edge embeddings that were not consolidated at that time. Second, our approach also results useful in more recent downstream applications like path-based link prediction.

We showed that embeddings paths as sequences of edges instead of sequences of nodes brings an immediate benefit. We also considered some potential limitations of our approach and proposed effective solutions. To face the fact that the line graph is much larger (in terms of nodes) than the original graph, we adopted a graph coarsening approach in the implementation.

To deal with the potential larger number of parameters that results from the higher number of nodes in the line graph, we devised a strategy that automatically adapts the embedding dimension on the basis of the number of nodes of the original graph (the  variant). There is room for several improvements. Considering alternative edge weighting mechanisms for  and path aggregation strategies for  is in our research agenda.

[1]
Rakshit Agrawal and Luca de Alfaro.
Learning edge properties in graphs from path aggregations.
In The World Wide Web Conference, pages 15–25. ACM, 2019.

[2]
Yong-Yeol Ahn, James P Bagrow, and Sune Lehmann.
Link communities reveal multiscale complexity in networks.
nature, 466(7307):761, 2010.

[3]
U. Brandes and D. Fleischer.
Centrality measures based on current flow.
In STACS, pages 533–544, 2005.

[4]
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang.
A comprehensive survey of graph embedding: Problems, techniques, and
IEEE Transactions on Knowledge and Data Engineering,
30(9):1616–1637, 2018.

[5]
Marcel A de Reus, Victor M Saenger, René S Kahn, and Martijn P van den
An edge-centric perspective on the human connectome: link communities
in the brain.
Philosophical Transactions of the Royal Society B: Biological
Sciences, 369(1653):20130527, 2014.

[6]
T Evans and R Lambiotte.
Overlapping communities, link partitions and line graphs.
In Proc. of the European Conference on Complex Systems,
volume 9, 2009.

[7]
TS Evans and Renaud Lambiotte.
Line graphs, link partitions, and overlapping communities.
Physical Review E, 80(1):016105, 2009.

[8]
Palash Goyal and Emilio Ferrara.
Graph embedding techniques, applications, and performance: A survey.
Knowledge-Based Systems, 151:78–94, 2018.

[9]
A. Grover and J. Leskovec.
node2vec: Scalable feature learning for networks.
In KDD, pages 855–864, 2016.

[10]
Will Hamilton, Zhitao Ying, and Jure Leskovec.
Inductive representation learning on large graphs.
In Advances in Neural Information Processing Systems, pages
1024–1034, 2017.

[11]
Thomas N Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
In ICLR, 2017.

[12]
Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy.
Mile: A multi-level framework for scalable graph embedding.
arXiv:1802.09612, 2018.

[13]
Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero.
A survey of link prediction in complex networks.
ACM Computing Surveys (CSUR), 49(4):69, 2017.

[14]
T. Mikolov, I. Sutskever, K. Chen, G. S Corrado, and J. Dean.
Distributed representations of words and phrases and their
In NIPS, pages 3111–3119, 2013.

[15]
Jose C Nacher, Nobuhisa Ueda, Takuji Yamada, Minoru Kanehisa, and Tatsuya
Clustering under the line graph transformation: application to
reaction network.
BMC bioinformatics, 5(1):207, 2004.

[16]
M. EJ Newman.
Modularity and community structure in networks.
Proceedings of the national academy of sciences,
103(23):8577–8582, 2006.

[17]
B. Perozzi, R. Al-Rfou, and S. Skiena.
Deepwalk: Online learning of social representations.
In KDD, pages 701–710, 2014.

[18]
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang.
Network embedding as matrix factorization: Unifying deepwalk, line,
pte, and node2vec.
In Proceedings of the Eleventh ACM International Conference on
Web Search and Data Mining, pages 459–467. ACM, 2018.

[19]
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo.
struc2vec: Learning node representations from structural identity.
In Proceedings of the 23rd ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, pages 385–394. ACM, 2017.

[20]
J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei.
Line: Large-scale information network embedding.
In WWW, pages 1067–1077, 2015.

[21]
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero,
Pietro Lio, and Yoshua Bengio.
Graph attention networks.
In ICLR, 2018.

[22]
Daixin Wang, Peng Cui, and Wenwu Zhu.
Structural deep network embedding.
In Proceedings of the 22nd ACM SIGKDD international conference
on Knowledge discovery and data mining, pages 1225–1234. ACM, 2016.

[23]
Hassler Whitney.
Congruent graphs and the connectivity of graphs.
In Hassler Whitney Collected Papers, pages 61–79. Springer,

[24]
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S
A comprehensive survey on graph neural networks.
arXiv preprint arXiv:1901.00596, 2019.