Which way?
Direction-Aware Attributed Graph Embedding?
Zekarias T. Kefato1 , Nasrullah Sheikh2 , and Alberto Montresor2
1

Royal Institute of Technology, Stockholm, Sweden
zekarias@kth.se2
University of Trento{nasrullah.sheikh,alberto.montresor}@unitn.it

Abstract. Graph embedding algorithms are used to efficiently represent (encode) a graph in a low-dimensional continuous vector space that preserves themost important properties of the graph. One aspect that is often overlooked iswhether the graph is directed or not. Most studies ignore the directionality, so
as to learn high-quality representations optimized for node classification. On theother hand, studies that capture directionality are usually effective on link prediction but do not perform well on other tasks.
This preliminary study presents a novel text-enriched, direction-aware algorithm
called D IAGRAM, based on a carefully designed multi-objective model to learn
embeddings that preserve the direction of edges, textual features and graph context of nodes. As a result, our algorithm does not have to trade one property
for another and jointly learns high-quality representations for multiple network
analysis tasks. We empirically show that D IAGRAM significantly outperforms six
state-of-the-art baselines, both direction-aware and oblivious ones, on link prediction and network reconstruction experiments using two popular datasets. It alsoachieves a comparable performance on node classification experiments against
these baselines using the same datasets.

1

Introduction

Recently, we have seen a tremendous progress in graph embedding algorithms that arecapable to learn high-quality vector space embeddings of graphs. Most of them arebased on different kinds of neural networks, such as the standard multi-layer perceptron(MLP) or convolutional neural networks (CNN). Regardless of the architecture, mostof them are optimized to learn embeddings for effective node classification.
Even though they have been shown to be useful for link prediction, they are only
capable to predict if two nodes are connected; they are not able to identify the directionof the edge. For example, in social networks like Twitter, it is very likely for “organic
users” (such as u in Fig. 1) to follow popular users like SkyFootball, based on their interest on the provided content, while the follow-back is very unlikely. Consequently, transitivity from u to SkySport is usually asymmetric as empirically demonstrated by [1].
For this reason, a good embedding algorithm over directed graphs should not be oblivious to directionality.
?

The source code is provided in the following github repo: https://github.com/zekariastilahun/diagram

2

Z. T. Kefato et al.

u

SkyFootball

SkySport

Fig. 1. An example follower graph between a random football enthusiast Twitter user and two
popular football and sport news channels Twitter accounts.

Another pressing issue in graph embedding research is the need for preserving similarity (homophily) between nodes. For example, the similarity between u and SkyFootball is usually dependent on the undirected neighborhood and the content produced/consumed by them [2, 3]. Thus, it is more important to examine the content andthe entire neighborhood of nodes to measure their similarity.
Existing studies usually trade-off between preserving directionality versus similarity [1, 3–12, 2, 13, 14]. Hence, they either learn high-quality embeddings for classification at the expense of asymmetric link prediction, or vice versa.
In this study, we argue that we do not have to choose between these aspects andwe propose a novel algorithm called D IAGRAM (Direction-Aware Attributed Graph
Embedding) that seeks to learn embeddings that balance the two aspects: D IAGRAM
preserves directionality and hence asymmetric transitivity, while at the same time striving to preserve similarity. We achieve this by designing a multi-objective loss functionthat seeks to optimize with respect to (1) direction of edges (2) content of nodes (Binary
or TF-IDF features) and (3) undirected graph context.
First we propose a variant of D IAGRAM called D IAGRAMnode ; after investigating
its limits, we propose an extension called D IAGRAMedge to address them.
The paper is structured as follows. In Section 2 we give a description of the proposedmodel and report the empirical evaluation in Section 3. In Section 4 we discuss related
work. Section 5 concludes the paper.

2

Model

Let G = (N, E, M, D) be a directed graph, where N is a set of n nodes and E is a set ofm edges. M ∈ Rn×n is an adjacency matrix, binary or real, and D ∈ Rn×d is a featurematrix, for instance constructed from a document corpus D = {D1 , . . . , Dn }, where
Du is a document associated to node u ∈ N . Each word w ∈ Du is a sample from a
vocabulary V of d words. Matrix D can be a simple binary matrix, where Du,i = 1
means that the word, the i-th word of V , appears in document Du of user u. It can also
be a TF-IDF weight that captures the importance of word w to node u.
For every node u ∈ N , our objective is to identify three embedding vectors, eu ={zu , ou , iu }. A recent study [15] has shown the power of learning multiple embedding
vectors of each node that capture different social contexts (communities). In our study,
however, each embedding vector is designed to meet the three goals that we set out toachieve in the introduction, which are:

Which way? Direction-Aware Attributed Graph Embedding˜˜
Au ⊕ Du˜
Mureconstruct

reconstructdecodedecode
iu

zu

embed

T

˜
Mu

reconstructdecode
ou

3

embed

embed

encodeencodeT

Mu

Mu

Fig. 2. The D IAGRAM architecture. Dotted and solid arrows indicate an MLP and SLP, respectively

1. Undirected neighborhood and content similarity-preserving embedding – zu ∈Rk , k  n – based on Mu |MT
u and D, where | is a bitwise or.
2. Outgoing neighborhood-preserving embedding – ou ∈ Rk – based on Mu
3. Incoming neighborhood-preserving embedding – iu ∈ Rk – based on MTu
To motivate our work, suppose we want to estimate the proximity between u andv. If (u, v) ∈ E is a reciprocal edge, then the estimated proximity should be equallyhigh for both (u, v) and (v, u), otherwise it should be high for (u, v) and very small for(v, u).
To this end, we adopt the technique proposed by [1] for estimating the asymmetricproximity between u and v as the dot product between ou ∈ Rk and iv ∈ Rk as:prx(u, v) ∝ dot(ou , iv )which are the learned embeddings of node u and v that capture their outgoing andincoming neighborhood, respectively.
Remark 1. To satisfy the above condition, if there is an unreciprocated directed edge(u, v) ∈ E we consider that as a high non-symmetric proximity, and hence ou and iv
should be embedded close to each other.
Thus, our goal is to jointly learn three embeddings eu = {zu , ou , iu } of each nodeu ∈ N using a single shared autoencoder model as follows.
2.1

Node Model

The first variant of D IAGRAM is D IAGRAMnode (Fig. 2); for each node u, its inputs
are Mu and MT
u . It has four components, which are encode, embed, decode, andreconstruct. The encode and decode components are formulated as a multilayer perceptron (MLP), with Lenc , and Ldec layers, respectively, and the output ofeach layer l is specified as:
hl = tanh(Wl · hl−1 + bl )

4

Z. T. Kefato et al.

where the weight matrix at the lth layer, Wl , is shared in the process of learning, eu :u ∈ N.
On the other hand, embed and reconstruct are a single-layer perceptron (SLP)
defined as:
embed = tanh(Wemb · hLenc + bemb )reconstruct = tanh(Wrec · hLdec + brec )where Wemb and Wrec are the weight matrices for the embedding and reconstruction
layers, respectively, which are also shared while learning the parameters eu : u ∈N . hLenc and hLdec are the activations of the last layers of the encoder and decoder,respectively. bl , bemb and brec are the biases for the lth -layer, embedding layer andreconstruction layer, in their respective order.
Optimization The model parameters are trained by minimizing the reconstruction errors on the weight and feature matrices M and D, respectively as follows:
LC u = ||(Au − Ãu )s + (Du − D˜u )LO u = ||(Mu − M̃u )

s||22

s||22

LI u = ||(Mu T − M̃Tu ) s||22X
L = minLC u + LO u + LI uΘu∈N

where is an element-wise multiplication, A = M|MT is the undirected adjacency
matrix, Θ denotes the set of all learnable model parameters, and s is a simple weighting
trick adopted from [4] to avoid the trivial solution of reconstructing the zeros for sparse
matrices. That is, for the j th entry, sj = µ > 1 if Au,j ≥ 1 otherwise sj = 1 . In all theexperiments we use µ = 10.
Therefore, LC enables us to preserve the combined neighborhood, in and out, andthe content similarity between nodes. LO and LI enables us to preserve the outgoingand incoming neighborhood of nodes, respectively.
2.2

Edge Model

The limit of D IAGRAMnode is that it does not satisfy the constraint that we specify
in Remark 1. To solve this, we propose D IAGRAMedge that has the same architecture
depicted in Fig. 2, but iterates over the edges. For each directed edge (u, v) ∈ E, we
execute D IAGRAM on both u and v; we use however a simple trick by adjusting LI foru as:
LI u = ||(Mv T − M̃u ) s||22
In other words, the reconstructions of u’s out-neighborhood, M̃u , is ensured to be consistent with v’s actual incoming neighborhood, Mv T , consequently reducing the distance ou − iv between u’s outgoing and v’s incoming embedding, and hence projecting
them close to each other.

Which way? Direction-Aware Attributed Graph Embedding

5

Although iterating over the edges in large networks might be expensive, we employ
transfer learning and use the trained parameters of the node model as a starting point. In
our experiments, transfer learning ensures convergence in one or two epochs, otherwise
D IAGRAMedge requires at least 30 epochs.
For both D IAGRAMnode and D IAGRAMedge we use dropout regularization as ourdatasets are extremely sparse.

3

Experimental Evaluation

We have evaluated the performance of our algorithm against two popular citation network datasets summarized in Table 1, comparing it against the following state-of-the-art
baselines.
3.1

Baselines

We include six baselines that preserve both symmetric and asymmetric neighborhoods,
as well as content similarity.
1. HOPE [1] is a direction-aware algorithm that uses a generalized variant of Singular
Value Decomposition.
2. D EEPWALK [6] and N ODE 2V EC [7] are algorithms that learn a symmetric neighborhood of nodes using S KIP G RAM [16] by leveraging sampled random walks.
3. DANE [3], ANRL [5] and VGAE [17] preserve both neighborhood and content similarity of nodes, yet only in a symmetric manner. DANE and ANRL use different
architectures of autoencoders, whereas VGAE uses a variational autoencoder.
We use three kinds of common network analysis tasks, which are network reconstruction, link prediction, and node classification in order to evaluate the performanceof the embedding algorithms.
3.2

Settings

The parameters of D IAGRAM are tuned using random search, while for the baselines
we use the source code provided by the authors and the optimal values reported in thecorresponding papers. For both datasets, D IAGRAM’s variants have the same configuration. The encoder layer configuration is [|V |, 512, 256], and the embedding size k is128. The decoder layer configuration is [128, 256, 512], and for reconstruction layer theconfiguration is [512, |V | + |F |]. Dropout rate is equal to 0.2 (Cora) and 0.1 (Citeseer);
the learning rate is 0.0001 for both.
Dataset |N | |E| d = |V | #Labels
Cora
2,708 5,278 3,703
7
Citeseer 3,312 4,660 1,433
6
Table 1. Dataset Summary6

Z. T. Kefato et al.
P@K(%)
K=2500 K=5000 K=7500 K=10000
D IAGRAMedge 57
44
37
31
D IAGRAMnode 46
36
29
25
DANE
3
11
13
12
ANRL
3
2
2
2
Citeseer
VGAE
16
13
12
11
HOPE
46
38
30
24
D EEPWALK
5544N ODE 2V EC 191616
12
D IAGRAMedge 59
49
42
36
D IAGRAMnode 46
38
31
30
DANE
10
10
9
0
ANRL
3
3
2
2
Cora
VGAE
21
18
15
14
HOPE
48
42
36
30
D EEPWALK
9998N ODE 2V EC 66
7
10
Dataset Algorithms

Table 2. P@K results of the network reconstruction experiment

3.3

Network Reconstruction

A good embedding algorithm should be able to preserve the structure of the network,and the goodness is usually verified by evaluating its performance in reconstructing the
network. Following the practice of related studies, we quantify the performance using
the precision-at-k (P@K) metric.
To this end, we first compute the pairwise proximity between all nodes. For every pair of nodes u and v, a direction-aware algorithm computes proximity prx(u, v)
between u and v as1
prx(u, v) =1 + e−dot(ou ,iv )and for direction-oblivious algorithms we simply have a single embedding zu and zv
for u and v, respectively, and hence prx is computed as:prx(u, v) =1
1 + e−dot(zu ,zv )Finally, node pairs are ranked according to their proximity score, and P@K is simply
the precision measured with respect to the ground truth edges at cut-off K.
The results of the network reconstruction experiments are reported in Table 2; ouralgorithms–D IAGRAMedge in particular–outperforms all the baselines with a significant
margin. In addition, as a consequence of satisfying Remark 1, D IAGRAMedge performs
much better than D IAGRAMnode .
The Cora dataset for instance has ≈ 5000 edges, and we see that for K = 5000, outof the ≈ 7, 000, 000 possible pairs D IAGRAMedge correctly filters out almost half of theground truth edges. These results are 7% and 11% better than HOPE and D IAGRAMnode ,respectively, and they are in stark contrast to the direction-oblivious baselines.

Which way? Direction-Aware Attributed Graph Embedding
Citeseer

7

Cora

AUC Score

0.75

0.50

0.25

0.00
Average Hadamard

Algorithms

W−L1

W−L2

Diagramedge
Diagramnode

Average Hadamard

Node2vec
Deepwalk

HOPE
DANE

W−L1

W−L2

ANRL
VGAE

Fig. 3. AUC results for link prediction, and p = 10.

3.4

Link Prediction

One of the most common real-world applications of graph embedding algorithms is link
prediction. In this experiment, similar to [7, 4, 18] we first sample p percent of the edges
from the graph. We refer to these edges as true samples and remove them from the graphby ensuring that the residual graph remains connected. We also sample p percent of pairof nodes that are not connected by an edge, referred to as false samples.
To show how robust our approach is, we train the variants of D IAGRAM on theresidual graph, while the baselines are trained on the complete graph. Then we use thelearned embeddings of the algorithms to predict edges as follows.
For all the sampled edges, true and false, we construct edge features using the techniques proposed by [7], which are the average, element wise multiplication, weightedL1, and weighted-L2 (Average, Hadamard, W-L1, W-L2, respectively) of the embeddings of the source and target nodes of each edge. For direction-aware algorithms(D IAGRAM and HOPE), edge features are asymmetric, o and i are used, while the otherbaselines are symmetric, only z is used. Then, for each sample, we assign the label ‘1’
if it comes from the true ones, ‘0’ otherwise.
We finally train a binary classifier using a 3-fold cross validation and we report themean of the area under the curve (AUC) score in Fig. 3, along with the error margin.
Although D IAGRAM’s variants have been trained on the residual graph, yet we see thatthey significantly outperform all the baselines across all feature construction techniques.

8

Z. T. Kefato et al.
DatasetCora
Citeseer
Micro-F1(%) Macro-f1(%) Micro-F1(%) Macro-F1(%)
D IAGRAMedge 75
73
60
56
D IAGRAMnode 74
72
60
56
DANE
77
75
61
57
ANRL
74
72
66
62
VGAE
75
72
58
52
HOPE
63
61
41
37
D EEPWALK
70
68
48
45
N ODE 2V EC 73
72
51
47
D IAGRAMedge 80
79
68
64
D IAGRAMnode 79
78
68
63
DANE
79
77
66
62
ANRL
77
75
71
67
VGAE
77
74
60
53
HOPE
73
71
49
45
D EEPWALK
77
76
55
51
N ODE 2V EC 79
78
58
54
D IAGRAMedge 82
80
70
65
D IAGRAMnode 81
79
69
64
DANE
81
79
70
65
ANRL
78
76
73
68
VGAE
78
75
60
53
HOPE
76
75
50
46
D EEPWALK
80
79
56
52
N ODE 2V EC 81
80
60
55

Training Ratio Algorithm

10%

30%

50%

Table 3. F1-Micro and F1-Macro results for node classification experiments on Cora and Citeseer
datasets. Each experiment is carried out using a fraction (10, 30, and 50 percent) of the data as
training set and the rest as test set.

This is due to the fact that D IAGRAM uses direction-aware embeddings. Even though
HOPE uses such kind of embeddings as well, its linear model is not powerful enough tocapture the highly non-linear structure of real graphs [4]. Furthermore, D IAGRAMedge
performs better than D IAGRAMnode , mostly with smaller variance, with exception of
W-L1.
3.5

Node Classification

Following the most common practices in these kinds of experiments, we train a multiclass one-vs-rest classifier using logistic regression. We use learned embeddings as
node features to predict the corresponding label. Yet again, we perform a 10-fold crossvalidation experiment; Table 3 reports the average Micro-F1 and Macro-F1 metrics.
For Cora, in most cases D IAGRAM performs better than DANE, ANRL, and VGAE,
methods known for their superior performance in node classification. For Citeseer, however, D IAGRAM performs worst than ANRL, comparable to DANE and better than VGAE.

Which way? Direction-Aware Attributed Graph Embedding

9Note that D IAGRAM is significantly better than HOPE, the direction-aware baseline.
This is due to the fact that D IAGRAM attempts to balance both direction and content byincorporating textual features and the undirected neighborhood.

4

Related WorkClassical graph embedding techniques rely on matrix factorization techniques. Fairly
recently, however, several studies have been proposed based on shallow and deep neural networks [2–7, 9, 18]. The earlier ones, such as D EEPWALK [6] and N ODE 2V EC [7],are techniques based on sampled random walks that are intended to capture the local
neighborhood of nodes. Virtually all methods based on random walks rely on the S KIP G RAM model [16], whose objective is to maximize the probability of a certain neighbornode v ∈ N of an anchor node u ∈ N , given the current embedding zu of u. One of
the main drawbacks of random walk based methods is their sampling complexity.
To address this limitation, several follow up studies, e.g. [3–5], have been proposed
based on deep-feed forward neural networks, such as Deep Autoencoders. However,
all these methods are inherently applicable for undirected networks, as they do not
explicitly care for directionality.
A method called Hope [1] has been proposed for preserving important properties
in directed networks. However, it relies on matrix factorization, and do not effectively
capture the highly non-linear structure of the network [4].
Our algorithm addresses the aforementioned limitations, however the results of thenode-classification experiment are not satisfactory and we intend to carefully investigate
the problem and design a better algorithm in the complete version of this paper.

5Conclusion

In this study we propose an ongoing, yet novel direction-aware, text-enhanced graphembedding algorithm called D IAGRAM. Unlike most existing studies that trade-off between learning high-quality embeddings for either link prediction or node classification,
D IAGRAM is capable to balance both.
We have empirically shown D IAGRAM’s superior performance in asymmetric link
prediction and network reconstruction and comparable performance in node classification over the state-of-the-art. However, we are still investigating directions to improve
D IAGRAM so as to improve its performance on node classification as well and we alsoseek to incorporate more datasets. We shall cover all of these aspects in a future versionof this study.

10

Z. T. Kefato et al.

References
1. M. Ou, P. Cui, J. Pei, Z. Zhang, and W. Zhu, “Asymmetric transitivity preserving
graph embedding,” in Proceedings of the 22Nd ACM SIGKDD International Conference on
Knowledge Discovery and Data Mining, ser. KDD ’16. New York, NY, USA: ACM, 2016,
pp. 1105–1114. [Online]. Available: http://doi.acm.org/10.1145/2939672.2939751
2. S. Pan, J. Wu, X. Zhu, C. Zhang, and Y. Wang, “Tri-party deep network representation,”in Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence,ser. IJCAI’16. AAAI Press, 2016, pp. 1895–1901. [Online]. Available: http://dl.acm.org/
citation.cfm?id=3060832.3060886
3. H. Gao and H. Huang, “Deep attributed network embedding,” in Proceedings of theTwenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, 7 2018,
pp. 3364–3370. [Online]. Available: https://doi.org/10.24963/ijcai.2018/467
4. D. Wang, P. Cui, and W. Zhu, “Structural deep network embedding,” in Proceedings of the
22Nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,ser. KDD ’16. New York, NY, USA: ACM, 2016, pp. 1225–1234. [Online]. Available:
http://doi.acm.org/10.1145/2939672.2939753
5. Z. Zhang, H. Yang, J. Bu, S. Zhou, P. Yu, J. Zhang, M. Ester, and C. Wang, “Anrl:
Attributed network representation learning via deep neural networks,” in Proceedings of theTwenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, 7 2018,
pp. 3155–3161. [Online]. Available: https://doi.org/10.24963/ijcai.2018/438
6. B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, ser. KDD ’14. ACM, 2014, pp. 701–710.
7. A. Grover and J. Leskovec, “Node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data
Mining, ser. KDD ’16. ACM, 2016, pp. 855–864.
8. J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “LINE: large-scale
information network embedding,” CoRR, vol. abs/1503.03578, 2015. [Online]. Available:
http://arxiv.org/abs/1503.03578
9. C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Y. Chang, “Network representation learning withrich text information,” in Proc. of the 24th Int. Conf. on Artificial Intelligence, ser. IJCAI’15.
AAAI Press, 2015, pp. 2111–2117. [Online]. Available: http://dl.acm.org/citation.cfm?id=
2832415.2832542
10. D. Yang, S. Wang, C. Li, X. Zhang, and Z. Li, “From properties to links: Deep network
embedding on incomplete graphs,” in Proc. of the 2017 ACM on Conf. on Information andKnowledge Management, ser. CIKM ’17. ACM, 2017, pp. 367–376. [Online]. Available:
http://doi.acm.org/10.1145/3132847.3132975
11. W. L. Hamilton, R. Ying, and J. Leskovec, “Inductive representation learning on large
graphs,” CoRR, vol. abs/1706.02216, 2017. [Online]. Available: http://arxiv.org/abs/1706.
02216
12. T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional
networks,” CoRR, vol. abs/1609.02907, 2016. [Online]. Available: http://arxiv.org/abs/1609.
02907
13. P. Velikovi, G. Cucurull, A. Casanova, A. Romero, P. Li, and Y. Bengio, “Graph attention
networks,” in International Conference on Learning Representations, 2018. [Online].
Available: https://openreview.net/forum?id=rJXMpikCZ
14. R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec,“Graph convolutional neural networks for web-scale recommender systems,” CoRR, vol.
abs/1806.01973, 2018. [Online]. Available: http://arxiv.org/abs/1806.01973

Which way? Direction-Aware Attributed Graph Embedding

11

15. A. Epasto and B. Perozzi, “Is a single embedding enough? learning node representations
that capture multiple social contexts,” in The World Wide Web Conference, ser. WWW’19. New York, NY, USA: ACM, 2019, pp. 394–404. [Online]. Available: http://doi.acm.org/10.1145/3308558.3313660
16. T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, “Distributed representationsof words and phrases and their compositionality,” in Proceedings of the 26th International
Conference on Neural Information Processing Systems - Volume 2, ser. NIPS’13. USA:
Curran Associates Inc., 2013, pp. 3111–3119. [Online]. Available: http://dl.acm.org/citation.
cfm?id=2999792.2999959
17. T. N. Kipf and M. Welling, “Variational graph auto-encoders,” NIPS Workshop on Bayesian
Deep Learning, 2016.
18. N. Sheikh, Z. Kefato, and A. Montresor, “GAT2VEC: Representation learning for attributedgraphs,” Computing, 2018.