Methods that learn representations of nodes in a graph play a critical role in network analysis since they enable many downstream learning tasks. We propose Graph2Gauss - an approach that can efficiently learn versatile node embeddings on large scale (attributed) graphs that show strong performance on tasks such as link prediction and node classification. Unlike most approaches that represent nodes as point vectors in a low-dimensional continuous space, we embed each node as a Gaussian distribution, allowing us to capture uncertainty about the representation. Furthermore, we propose an unsupervised method that handles inductive learning scenarios and is applicable to different types of graphs: plain/attributed, directed/undirected. By leveraging both the network structure and the associated node attributes, we are able to generalize to unseen nodes without additional training. To learn the embeddings we adopt a personalized ranking formulation w.r.t. the node distances that exploits the natural ordering of the nodes imposed by the network structure. Experiments on real world networks demonstrate the high performance of our approach, outperforming state-of-the-art network embedding methods on several different tasks. Additionally, we demonstrate the benefits of modeling uncertainty - by analyzing it we can estimate neighborhood diversity and detect the intrinsic latent dimensionality of a graph. Graphs are a natural representation for a wide variety of real-life data, from social and rating networks (Facebook, Amazon), to gene interactions and citation networks (BioGRID, arXiv) . Node embeddings are a powerful and increasingly popular approach to analyze such data BID0 . By operating in the embedding space, one can employ proved learning techniques and bypass the difficulty of incorporating the complex node interactions. Tasks such as link prediction, node classification, community detection, and visualization all greatly benefit from these latent node representations. Furthermore, for attributed graphs by leveraging both sources of information (network structure and attributes) one is able to learn more useful representations compared to approaches that only consider the graph BID33 BID24 BID5 .All existing (attributed) graph embedding approaches represent each node by a single point in a low-dimensional continuous vector space. Representing the nodes simply as points, however, has a crucial limitation: we do not have information about the uncertainty of that representation. Yet uncertainty is inherent when describing a node in a complex graph by a single point only. Imagine a node for which the different sources of information are conflicting with each other, e.g. pointing to different communities or even revealing contradicting underlying patterns. Such discrepancy should be reflected in the uncertainty of its embedding. As a solution to this problem, we introduce a novel embedding approach that represents nodes as Gaussian distributions: each node becomes a full distribution rather than a single point. Thereby, we capture uncertainty about its representation.To effectively capture the non-i.i.d. nature of the data arising from the complex interactions between the nodes, we further propose a novel unsupervised personalized ranking formulation to learn the embeddings. Intuitively, from the point of view of a single node, we want nodes in its immediate neighborhood to be closest in the embedding space, while nodes multiple hops away should become increasingly more distant. This ordering between the nodes imposed by the network structure w.r.t the distances between their embeddings naturally leads to our ranking formulation. Taking into account this natural ranking from each node's point of view, we learn more powerful embeddings since we incorporate information about the network structure beyond first and second order proximity.Furthermore, when node attributes (e.g. text) are available our method is able to leverage them to easily generate embeddings for previously unseen nodes without additional training. In other words, Graph2Gauss is inductive, which is a significant benefit over existing methods that are inherently transductive and do not naturally generalize to unseen nodes. This desirable inductive property comes from the fact that we are learning an encoder that maps the nodes' attributes to embeddings.The main contributions of our approach are summarized as follows: a) We embed nodes as Gaussian distributions allowing us to capture uncertainty. b) Our unsupervised personalized ranking formulation exploits the natural ordering of the nodes capturing the network structure at multiple scales.c) We propose an inductive method that generalizes to unseen nodes and is applicable to different types of graphs: plain/attributed, directed/undirected. Inductive learning. While during learning we need both the network structure (to evaluate the ranking loss) and the attributes, once the learning concludes, the embedding for a node can be obtained solely based on its attributes. This enables our method to easily handle the issue of obtaining representations for new nodes that were not part of the network during training. To do so we simply pass the attributes of the new node through our learned deep encoder. Most approaches cannot handle this issue at all, with a notable exception being SDNE and GraphSAGE . However, both approaches require the edges of the new node to get the node's representation, and cannot handle nodes that have no existing connections. In contrast, our method can handle even such nodes, since after the model is learned we rely only on the attribute information.Plain graph embedding. Even though attributed graphs are often found in the real-world, sometimes it is desirable to analyze plain graphs. As already discussed, our method easily handles plain graphs, when the attributes are not available, by using one-hot encoding of the nodes instead. As we later show in the experiments we are able to learn useful representations in this scenario, even outperforming some attributed approaches. Naturally, in this case we lose the inductive ability to handle unseen nodes. We compare the one-hot encoding version, termed G2G oh, with our full method G2G that utilizes the attributes, as well as all remaining competitors.Encoder architecture. Depending on the type of the node attributes (e.g. images, text) we could in principle use CNNs/RNNs to process them. We could also easily incorporate any of the proposed graph convolutional layers inheriting their benefits. However, we observe that in practice using simple feed-forward architecture with rectifier units is sufficient, while being much faster and easier to train. Better yet, we observed that Graph2Gauss is not sensitive to the choice of hyperparameters such as number and size of hidden layers. We provide more detailed information and sensible defaults in the appendix.Complexity. The time complexity for computing the original loss is O(N 3 ) where N is the number of nodes. Using our node-anchored sampling strategy, the complexity of the stochastic version is O(K 2 N ) where K is the maximum distance considered. Since a small value of K ≤ 2 consistently showed good performance, K 2 becomes negligible and thus the complexity is O(N ), meaning linear in the number of nodes. This coupled with the small number of epochs T needed for convergence (T ≤ 2000 for all shown experiments, see e.g. FIG2 ) and an efficient GPU implementation also made our method faster than most competitors in terms of wall-clock time. We proposed Graph2Gauss -the first unsupervised approach that represents nodes in attributed graphs as Gaussian distributions and is therefore able to capture uncertainty. Analyzing the uncertainty reveals the latent dimensionality of a graph and gives insight into the neighborhood diversity of a node. Since we exploit the attribute information of the nodes we can effortlessly generalize to unseen nodes, enabling inductive reasoning. Graph2Gauss leverages the natural ordering of the nodes w.r.t. their neighborhoods via a personalized ranking formulation. The strength of the learned embeddings has been demonstrated on several tasks -specifically achieving high link prediction performance even in the case of low dimensional embeddings. As future work we aim to study personalized rankings beyond the ones imposed by the shortest path distance.
 We embed nodes in a graph as Gaussian distributions allowing us to capture uncertainty about their representation.
{"src": "scitldr-AIC_train", "paper_id": "r1ZdKJ-0W"}