Source-linked AI summary
Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking
Aleksandar Bojchevski, Stephan Günnemann
TL;DR
Graph node embeddings support many network-analysis tasks, but point representations do not capture uncertainty and many methods do not generalize naturally to unseen nodes. Graph2Gauss embeds nodes as Gaussian distributions and learns them with personalized network-structure rankings, using attributes for inductive inference. It reports strong performance across several tasks, while uncertainty analysis reveals neighborhood diversity and latent graph dimensionality.
Problem
Point-vector node embeddings do not capture representation uncertainty, while existing methods do not naturally support unsupervised inductive inference across the stated graph types.
Method
Graph2Gauss represents nodes as Gaussian distributions and learns them with an unsupervised personalized ranking formulation that uses attributes and network structure.
Results
Graph2Gauss achieves high link prediction performance across several tasks and supports uncertainty analysis for neighborhood diversity and latent dimensionality.
Takeaways & Limitations
Uncertainty analysis provides insight into neighborhood diversity and the latent dimensionality of a graph, while attribute-based encoding enables inductive reasoning for unseen nodes.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Graph2Gauss addresses uncertainty and inductive generalization in node embeddings by representing nodes as Gaussian distributions and learning network-aware rankings. It applies across graph types and uses attributes to embed unseen nodes without additional training.
- Motivation and representation: Node embeddings support downstream tasks including link prediction, node classification, community detection, and visualization.The paper motivates embeddings as a way to analyze complex node interactions in a learned latent space.
- Motivation and representation: Point-vector embeddings omit uncertainty, whereas Graph2Gauss represents each node as a Gaussian distribution to capture uncertainty.The distributional representation is intended to reflect conflicting information about a node’s communities or underlying patterns.
- Network-aware learning: Graph2Gauss learns embeddings with an unsupervised personalized ranking formulation that orders immediate neighbors closer than nodes multiple hops away.This ranking incorporates network structure beyond first- and second-order proximity.
- Inductive generalization: The method leverages node attributes through an encoder to generate embeddings for previously unseen nodes without additional training.This gives Graph2Gauss an inductive property that existing inherently transductive methods do not naturally provide.
- Scope: The approach is designed for plain or attributed graphs and for directed or undirected graphs.Its stated contributions combine inductive learning with applicability across these graph settings.
2 RELATED WORK
Prior work learns node embeddings from random walks, proximity, attributes, graph convolutions, or distributions, but these approaches differ in graph assumptions and supervision. The paper positions Graph2Gauss among distributional methods while targeting unsupervised attributed-graph embedding.
- Plain-graph and proximity methods: DeepWalk and node2vec learn embeddings for plain graphs from random walks using extensions of the Skip-Gram architecture.LINE instead uses first- and second-order proximity with negative sampling.
- Attributed and heterogeneous graphs: Attributed-graph methods incorporate text, node attributes, labels, or augmented networks through approaches such as TRIDNR, CENE, and TADW.These methods vary in whether they treat attributes as nodes, factorize matrices, or combine structure with labels.
- Graph convolutional methods: Graph convolutional networks adapt convolutional architectures to graphs by using graph Laplacians and neighbor aggregation.They can be viewed as implicitly learning embeddings from the output of a final layer.
- Distributional embeddings: Few approaches represent embeddings as distributions, and existing distributional methods cited here target word, knowledge-graph, or supervised heterogeneous-graph settings.The paper states that these methods do not directly apply to unsupervised learning of attributed graphs and do not consider node attributes in the relevant settings.
3 DEEP GAUSSIAN EMBEDDING
Graph2Gauss embeds nodes as Gaussian distributions produced by an attribute encoder and learns them with an unsupervised ranking loss based on network distances. The method supports multiple graph types, inductive inference, multiscale structure, and scalable stochastic optimization.
- Gaussian node embeddings: Graph2Gauss maps node attributes through a deep encoder to Gaussian embedding parameters and compares distributions using asymmetric KL divergence.The encoder produces the mean and covariance of each node’s Gaussian representation; asymmetric divergence also supports directed graphs.
- Network structure representation via personalized ranking: Personalized ranking orders nodes by hop distance so nearer neighborhoods receive smaller embedding dissimilarities than more distant neighborhoods.The ranking uses pairwise constraints between k-hop neighborhoods, extending structural modeling beyond first- and second-order proximity.
- Learning via energy-based loss: The energy-based loss penalizes ranking errors between positive and negative node pairs, while node-anchored stochastic sampling addresses intractability and preserves unbiased gradient estimates.The original loss has O(N^3) complexity, whereas the stochastic version has O(K^2N), becoming O(N) when K ≤ 2.
- Inductive learning: The shared encoder enables embeddings for previously unseen nodes using only their attributes after training, including nodes without existing connections.During training, both attributes and network structure are used; inference for new nodes requires only the learned attribute-to-embedding mapping.
- Plain graph embedding: Without attributes, Graph2Gauss uses one-hot node encodings for plain graphs but loses the ability to represent unseen nodes inductively.The one-hot variant is termed G2G oh, while the attribute-based method is termed G2G.
4 EMBEDDING EVALUATION
Graph2Gauss is evaluated across link prediction, node classification, sampling efficiency, uncertainty analysis, and inductive generalization. It performs strongly across real-world settings, while uncertainty supports analyses of neighborhood diversity and latent dimensionality.
- Link prediction: Graph2Gauss significantly outperforms competing methods on link prediction across real-world datasets, while G2G oh also surpasses competitors on some datasets.GAE achieves comparable performance on some datasets but does not scale efficiently to graphs beyond 15K nodes.
- Sensitivity analysis: Even with embedding size L = 2, G2G outperforms competitors using much higher embedding sizes.The L = 2 representation uses one-dimensional Gaussian distributions for the mean and sigma.
- Sensitivity analysis: Graph2Gauss strongly outperforms competitors when the percentage of training edges is small.Performance below the threshold guaranteeing every node appears in training indicates behavior in the inductive setting, where structure-only methods cannot compute meaningful unseen-node embeddings.
- Node classification: Graph2Gauss clearly outperforms competitors in node classification and remains stable across different percentages of labeled nodes.The evaluation uses unsupervised embeddings followed by logistic regression trained on varying percentages of labeled nodes.
- Sampling strategy: Node-anchored sampling reaches full-loss performance after seeing fewer than 4.2% of pairs, with lower loss and gradient variance than naive sampling.Lower gradient-update variance contributes to faster convergence.
- Embedding uncertainty: Learned uncertainty correlates with neighborhood diversity: nodes whose neighbors span more classes have higher variance.This relationship appears on Cora for a three-hop neighborhood and also holds on the other datasets.
- Embedding uncertainty: Removing dimensions identified as highly uncertain causes little performance change until the true latent dimensions are removed.The uncertainty-based procedure is used to detect the graph’s intrinsic latent dimensionality.
- Inductive learning: Using node attributes, Graph2Gauss achieves strong link-prediction performance for unseen nodes even when 25% of nodes are withheld.Embeddings for unseen nodes are obtained from attributes alone after training, unlike SDNE and GraphSAGE in this setting.
5 CONCLUSION
Graph2Gauss represents attributed-graph nodes as Gaussian distributions, capturing uncertainty while supporting inductive reasoning and neighborhood-based ranking. Its embeddings perform strongly on link prediction, including with low-dimensional representations.
- Graph2Gauss represents nodes in attributed graphs as Gaussian distributions, enabling uncertainty modeling.Analyzing uncertainty reveals graph latent dimensionality and neighborhood diversity.
- The method leverages node attributes to generate embeddings for unseen nodes without additional training.This encoder-based property enables inductive reasoning.
- Graph2Gauss uses a personalized ranking formulation based on the natural ordering of nodes relative to their neighborhoods.The ranking formulation incorporates network structure beyond first- and second-order proximity.
- Graph2Gauss achieves high link prediction performance even with low-dimensional embeddings.The paper reports strong performance across several tasks.
A PROOF OF THEOREM 1
The proof shows that the sampled loss equals the original loss in expectation, so its sample-based gradient is an unbiased estimate of the full-loss gradient. The derivation expands pairwise terms, marginalizes irrelevant variables, and uses uniform sampling probabilities.
- The proof reduces Theorem 1 to showing equality in expectation between the sampled loss Ls and the original loss L.Because both losses sum over nodes, it suffices to establish equality for one node i.
- The sampled gradient ∇Ls is an unbiased estimate of ∇L when computed from a set of samples.This follows directly from the expected equality of Ls and L.
- The derivation expands the sum over k < l into independent terms and marginalizes variables absent from each expression.Marginalization removes variables that do not affect a given pairwise term.
- Expanding the expectation and substituting p(jp) with 1/|N_ijp| yields the pairwise loss expression under uniform sampling.The substitution uses the uniform distribution over each sampled neighborhood.
B IMPLEMENTATION DETAILS
Graph2Gauss uses a simple encoder configuration, produces Gaussian parameters from node attributes, and is relatively insensitive to architecture and embedding-size choices. Its inductive design also removes the need for every node to appear in the training edge set.
- Architecture and hyperparameters: Graph2Gauss is not sensitive to the number or size of hidden layers or to the embedding size L.A relatively large embedding size can be selected and pruned later if required.
- Architecture and hyperparameters: The recommended default is an encoder with one hidden layer of size s1 = 512.The encoder maps node attributes into the embedding parameters.
- Architecture and hyperparameters: The encoder computes Gaussian means and positive scale parameters from node attributes using ReLU and ELU transformations.Softplus also works for ensuring positive scale parameters and a positive-definite covariance matrix.
- Optimization: The method does not explicitly regularize mean norms or clip covariance matrices because the KL divergence is self-regularizing.The authors report that experiments confirmed this was unnecessary.
- Edge cover: Unlike competing transductive methods, Graph2Gauss does not require every node to appear in the training edge set.The competing methods require an edge cover so every node is incident to at least one training edge.