Recent advances in neural networks have solved common graph problems such as, link prediction, node classification, node clustering and node recommendation by developing embeddings of entities and relations into vector spaces. Graph embeddings encode the structural information present in a graph. The encoded embeddings then can be used to predict the missing links in a graph. However, obtaining the optimal embeddings for a graph can be a computationally challenging task specially in an embedded system. Two techniques which we focus on in this work are 1) node embeddings from random walk based methods and 2) knowledge graph embeddings. Random walk based embeddings are computationally inexpensive to obtain but are sub-optimal whereas knowledge graph embeddings perform better but are computationally expensive. In this work, we investigate a transformation model which converts node embeddings obtained from random walk based methods to embeddings obtained from knowledge graph methods directly without an increase in the computational cost. Extensive experimentation shows that the proposed transformation model can be used for solving link prediction in real-time.
With the advancement in internet technology, online social networks have become part of people’s everyday life. Their analysis can be used for targeted advertising, crime detection, detection of epidemics, behavioural analysis etc. Consequently, a lot of research has been devoted to computational analysis of these networks as they represent interactions between a group of people or community and it is of great interest to understand these underlying interactions. Generally, these networks are modeled as graphs where a node represents a person or an entity and an edge represent interactions, relationships or communication between two of them. For example, in a social network such as Facebook and Twitter, people are represented by nodes and the existence of an edge between two nodes would represent their friendship. Other examples would include a network of products purchased together on an E-commerce website https://architparnami.github.io/ (A. Parnami); https://webpages.charlotte.edu/mlee173/ (M. Lee)
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). like Amazon, a network of scientists publishing in a conference where an edge would represent their collaboration or a network of employees in a company working on a common project.
Inherent nature of social networks is that they are dynamic, i.e., over time new edges are added
as a network grows. Therefore, understanding the likelihood of future association between two
nodes is a fundamental problem and is commonly known as link prediction [
Over the years, a large number of link prediction methods have been proposed [
Similar to these node embedding methods, recent years have also witnessed a rapid growth
in knowledge graph embedding methods. A knowledge graph (KG) is a graph with entities of
diferent types of nodes and various relations among them as edges. Link prediction in such a
graph is known as knowledge graph completion. It is similar to link prediction in social network
analysis, but more challenging because of the presence of multiple types of nodes and edges.
For knowledge graph completion, we not only determine whether there is a link between two
entities or not, but also predict the specific type of the link. For this reason, the traditional
approaches of link prediction are not capable of knowledge graph completion. Therefore, to
tackle this issue, a new research direction known as knowledge graph embedding has been
proposed [
Our experiments show that neither of these two approaches, however, can generate “optimal” embeddings “quickly” for real-time link prediction on new graphs. Random walk based node embedding methods are computationally eficient but give poor results whereas KG-based methods produce optimal results but are computationally expensive. Thus, in this work, we mainly focus on embedding learning methods (i.e., Walk based node embedding methods and knowledge graph completion methods) which are capable of finding optimal embeddings quickly enough to meet real-time constraints for practical applications. To bridge the gap between computational time and performance of embeddings on link prediction, we propose the following contributions in this work: • We compare the embedding’s performance and computational cost of both Random walk based node embedding and KG-based embedding methods and empirically determine that Random walk based node embedding methods are faster but give sub-optimal results on link prediction whereas KG based embedding methods are computationally expensive but perform better on link prediction. • We propose a transformation model that takes node embeddings from Random walk based node embedding methods and output near optimal embeddings without an increase in computational cost. • We demonstrate the results of transformation through extensive experimentation on various social network datasets of diferent graph sizes and diferent combinations of node embeddings and KG embedding methods.
Let ℎ = ⟨ , , ⟩ be an unweighted, undirected homogeneous graph where is the set of vertices, is the set of observed links, i.e., ⊂ × and is the adjacency matrix respectively. The graph represents the topological structure of the social network in which an edge = ⟨, ⟩ ∈ represents an interaction that took place between and . Let denote the universal set containing all (| | × (| | − 1))/2 possible edges. Then, the set of non-existent links is − . Our assumption is that there are some missing links (edges that will appear in future) in the set − . Then the link prediction task is given the current network ℎ , find out these missing edges.
Similarly, let = ⟨ , , ⟩ be a Knowledge Graph (KG). A KG is a directed graph whose
nodes are entities and edges are subject-property-object triple facts. Each edge of the form (head
entity, relation, tail entity) (denoted as ⟨ℎ, , ⟩ ) indicates a relationship from entity ℎ to entity
. For example, ⟨, , ⟩ and ⟨, , ⟩ . Note that the entities and
relations in a KG are usually of diferent types. Link prediction in KGs aims to predict the
missing h or t for a relation fact triple ⟨ℎ, , ⟩ , used in [
We then formulate the problem of link prediction on graph such that ≡ ℎ ≡ , i.e., KG with only one type of entity and relation. Link prediction is then to predict the missing ℎ or for a relation fact triple ⟨ℎ, , ⟩ where both ℎ and are of the same kind. For example ⟨, , ?⟩ or ⟨, , ?⟩ .
Graph embedding aims to represent a graph in a low dimensional space which preserves as much
graph property information as possible. The diferences between diferent graph embedding
algorithms lie in how they define the graph property to be preserved. Diferent algorithms
have diferent insights of the node (/edge/substructure/whole-graph) similarities and how to
preserve them in the embedded space. Formally, given a graph = ⟨ , , ⟩ , a node embedding
is a mapping 1 ∶ → yi ∈ ℝ ∀ ∈ [] where is the dimension of the embeddings, the
number of vertices and the function preserves some proximity measure defined on graph
. If there are multiple types of links/relations in the graph then similar to node embeddings,
relation embeddings can be obtained as ∶ → yj ∈ ℝ
of relations.
2.2.1. Node Embeddings using Random Walks
where the number of types
Random walks have been used to approximate many properties in the graph including node
centrality [22] and similarity [23]. Their key innovation is optimizing the node embeddings so
that nodes have similar embeddings if they tend to co-occur on short random walks over the
graph. Thus, instead of using a deterministic measure of graph proximity [24], these random
walk methods employ a flexible, stochastic measure of graph proximity, which has led to superior
performance in a number of settings [25]. Two well known examples of random walk based
methods are node2vec [
A Transformation model (Fig. 1) is suggested to expedite the fine-tuning process with KGembedding methods. Let ,
be a graph with vertices and edges. Given the node embeddings of the graph , we would want to transform them to optimal node embeddings.
The input graph ,
is fed into one of the random walk based graph embeddings methods
(node2vec [
where ∈ × and
we can initialize with higher quality.
Instead of using randomly initialized embeddings to obtain target embeddings ∈ × are fine tuned output embeddings. This idea of better initialization has also been explored previously in [29, 30] where it has been shown to result in embeddings of parameters .
be the initial node embeddings, In a KG-based embedding algorithm (such as TransE), the input is a graph and the initial embeddings are randomly initialized. The algorithm uses a scoring function and optimizes the initial embeddings to output the trained embeddings for the given graph. Since we are working with homogeneous graph with only one type of relation, we don’t need to learn the embeddings for the relation, hence they are kept constant and only node embeddings are learnt. Let be the trained embeddings and the KG method with ∈ × .
= (
, in Eq. (1) as ; ) (2) 3.3. Transformation Model with Self-Attention
Using the node embeddings from Eq. (1) and fine-tuned KG embeddings from Eq. (3), we train a transformation model which can learn to transform the node embeddings from a node-based method to KG embeddings. We adopt self-attention [31] on graph adjacency matrix as explained in Algorithm 1: ∈ × are the transformed embeddings and are the parameters of the The loss on batch X of graphs is measured as:
= 1/ ∑ || − 2 || . (
X) = 1/ ∑ =1 2 3 4 5 6 7 8 9 = afine(E, d) = afine(E, d) × × × = afine(E, d)
× return Output × = matmul(Q, transpose(K)) ×
= Logits + A = matmul(AttendedLogits, V) (4) (5) (6) where X = {(
, from facts/triplets which are obtained from the adjacency matrix of the graph, a self-attention model reinforced with information of the adjacency matrix when applied to node-embeddings is able to learn the transformation function as observed in our experiments (Fig. 3). The proposed algorithm is summarized in Algorithm 2.
)} and is the batch size. Since KG embeddings are trained Algorithm 1: Self-attention on graph adjacency matrix 1 Function SelfAttention( , , × )
× = Adjacency Matrix of ,
The error between the fine-tuned and transformed embeddings is calculated using squared
Yang, et. al [32] introduced social network datasets with ground-truth communities. Each dataset is a network having a total of nodes, edges and a set of communities (Table 1).
Algorithm 2: Training the transformation model
Input: Dataset of Graphs
= { 1, 2, ..., } 2 5 8 9 10 11 12 13 14 end
YouTube1, Orkut1 and LiveJournal1 are friendship networks where each community is a userdefined group. Nodes in the community represent users, and edges represent their friendship.
DBLP1 is a co-authorship network where two authors are connected if they publish at least one paper together. A community is represented by a publication venue, e.g., journal or conference. Authors who published to a certain journal or conference form a community.
Amazon1 co-purchasing network is based on Customers Who Bought This Item Also Bought feature of the Amazon website. If a product is frequently co-purchased with product , the graph contains an undirected edge from to . Each connected component in a product category defined by Amazon acts as a community where nodes represent products in the same category and edges indicate that we were purchased together.
1http://snap.stanford.edu/data/index.html#communities
We consider each community in a dataset as an individual graph , with vertices representing the entity in the community and edges representing the relationship. For training the transformation model, we select communities of particular size range which acts as dataset of graphs (Table 2). We randomly disable 20% of the links (edges) in each graph to act as missing links for link prediction. In all the experiments, the embedding dimension is set to 32, which works best in our pilot test. We used OpenNE2 for generating node2vec and DeepWalk embeddings and OpenKE [33] for generating KG embeddings. The dataset of graphs is split into train, 2https://github.com/thunlp/OpenNE validation and test split of 64%, 16%, and 20% respectively.
For evaluation, we use MRR and Precision@K. The algorithm predicts a list of ranked candidates for the incoming query. To remove pre-existing triples in the knowledge graph, filtering operation cleans them up from the list. MRR computes the mean of the reciprocal rank of the correct candidate in the list, and Precision@K evaluates the rate of correct candidates appearing in the top K candidates predicted. Due to space constraints, we only present the results for MRR. Results of Precision@K can be found at our GitHub3.
From the results depicted in Fig. 3, we observe that the target KG embeddings (TransE, TransH, etc.) almost always outperforms random-walk based source embeddings (node2vec and DeepWalk) except in case of SimplE and DistMult where both the methods perform poorly. This can also be observed in Fig. 4.
Finetuned KG embeddings achieved better or equivalent performance as compared to target KG embeddings. This can be confirmed by ANOVA test in Fig. 4 where there is no significant diference between the MRRs obtained from finetuned and target KG embeddings in most cases. Specifically, translational based methods such as TransE, TransH, and TransD have equivalent performance for finetuned and target embeddings whereas SimplE, RESCAL, and DistMult have better finetuned embeddings than target embeddings as the graph size grows.
Transformed embeddings consistently outperform source embeddings and have similar performance to finetuned embeddings at least for graphs of sizes up to 65. The performance drop starts from graph size 71-75 in the transformation to TransD from DeepWalk whereas 81-85 in the transformation to TransE from node2vec. For RESCAL, the transformation works for larger sized graphs in node2vec and till 121-125 in DeepWalk.
As the graph size increases (top to bottom), the overall MRR scores decrease for all the embeddings as expected. In Fig. 5, we compare computation time and MRR performance of transformed embeddings and finetuned embeddings where source method is node2vec and target method is TransE. It can be seen that the transformed embeddings give similar performance as ifnetuned embeddings (without any significant increase in computational cost) up to graphs of size 71-75. Thereafter the transformed embeddings perform poorly, we attribute this to poor ifnetuned embeddings on which the transformation model was trained.
In this work, we have demonstrated that random-walk based node embedding (source) methods are computationally eficient but give sub-optmial results on link prediction in social networks whereas KG based embedding (target & finetuned) methods perform better but are computationally expensive. For our requirement of generating optimal embeddings quickly for real-time link prediction we proposed a self-attention based transformation model to convert walk-based embeddings to optimal KG embeddings. The proposed model works well for smaller graphs but as the complexity of the graph increases, the transformation performance decreases. For future work, our goal is to explore better transformation models for bigger graphs. 3167–3175. [18] A. Bordes, X. Glorot, J. Weston, Y. Bengio, A semantic matching energy function for learning with multi-relational data, Machine Learning 94 (2014) 233–259. [19] R. Socher, D. Chen, C. D. Manning, A. Ng, Reasoning with neural tensor networks for knowledge base completion, in: Advances in neural information processing systems, 2013, pp. 926–934. [20] A. Bordes, J. Weston, R. Collobert, Y. Bengio, Learning structured embeddings of knowledge bases, in: Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011. [21] A. Bordes, X. Glorot, J. Weston, Y. Bengio, Joint learning of words and meaning representations for open-text semantic parsing, in: Artificial Intelligence and Statistics, 2012, pp. 127–135. [22] M. E. Newman, A measure of betweenness centrality based on random walks, Social networks 27 (2005) 39–54. [23] A. Pirotte, J.-M. Renders, M. Saerens, et al., Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation, IEEE Transactions on Knowledge & Data Engineering (2007) 355–369. [24] M. Belkin, P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, in: Advances in neural information processing systems, 2002, pp. 585–591. [25] P. Goyal, E. Ferrara, Graph embedding techniques, applications, and performance: A survey, Knowledge-Based Systems 151 (2018) 78–94. [26] Q. Wang, Z. Mao, B. Wang, L. Guo, Knowledge graph embedding: A survey of approaches and applications, IEEE Transactions on Knowledge and Data Engineering 29 (2017) 2724–2743. [27] B. Yang, W.-t. Yih, X. He, J. Gao, L. Deng, Embedding entities and relations for learning and inference in knowledge bases, arXiv preprint arXiv:1412.6575 (2014). [28] S. M. Kazemi, D. Poole, Simple embedding for link prediction in knowledge graphs, in:
Advances in Neural Information Processing Systems, 2018, pp. 4284–4295. [29] Y. Luo, Q. Wang, B. Wang, L. Guo, Context-dependent knowledge graph embedding, in: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, 2015, pp. 1656–1661. [30] H. Chen, B. Perozzi, Y. Hu, S. Skiena, Harp: Hierarchical representation learning for networks, in: Thirty-Second AAAI Conference on Artificial Intelligence, 2018. [31] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, I. Polosukhin, Attention is all you need, in: Advances in neural information processing systems, 2017, pp. 5998–6008. [32] J. Yang, J. Leskovec, Defining and evaluating network communities based on ground-truth,
Knowledge and Information Systems 42 (2015) 181–213. [33] X. Han, S. Cao, X. Lv, Y. Lin, Z. Liu, M. Sun, J. Li, Openke: An open toolkit for knowledge embedding, in: Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, 2018, pp. 139–144.