Source-linked AI summary
Gravity-Inspired Graph Autoencoders for Directed Link Prediction
Guillaume Salha, Stratis Limnios, Romain Hennequin, Viet Anh Tran, Michalis Vazirgiannis
TL;DR
Graph AE/VAE methods for link prediction treat links as undirected, limiting their fit to applications with asymmetric relations. This paper extends these frameworks with a gravity-inspired decoder for directed graphs, and reports competitive performance across directed link-prediction tasks and real-world graphs.
Problem
Graph AE/VAE predict links symmetrically, although many applications contain directed relations.
Source: §1 · p. 1Method
Results
Across three directed link-prediction tasks, the models outperform standard graph AE/VAE and achieve competitive results against popular baselines on three real-world graphs.
Source: §1 · p. 2, §4.3 · p. 7Takeaways & Limitations
The experiments support gravity-inspired graph AE/VAE as effective approaches for directed link prediction, including tasks where directionality learning is crucial.
Source: §4.3 · p. 7, §5 · p. 9Experiments focused on featureless graphs; evaluating node features and alternative graph neural network encoders remains future work.
Source: §4.4.3 · p. 9
Abstract
from arXiv · showhide
Graph autoencoders (AE) and variational autoencoders (VAE) recently emerged as powerful node embedding methods. In particular, graph AE and VAE were successfully leveraged to tackle the challenging link prediction problem, aiming at figuring out whether some pairs of nodes from a graph are connected by unobserved edges. However, these models focus on undirected graphs and therefore ignore the potential direction of the link, which is limiting for numerous real-life applications. In this paper, we extend the graph AE and VAE frameworks to address link prediction in directed graphs. We present a new gravity-inspired decoder scheme that can effectively reconstruct directed graphs from a node embedding. We empirically evaluate our method on three different directed link prediction tasks, for which standard graph AE and VAE perform poorly. We achieve competitive results on three real-world graphs, outperforming several popular baselines.
1 INTRODUCTION
Graph link prediction infers unobserved edges, and graph AE/VAE embedding methods have become state-of-the-art for undirected prediction. This paper addresses their inability to model asymmetric links by extending them to directed graphs with a gravity-inspired decoder.
1 INTRODUCTION
- Link prediction infers unobserved edges; graph AE/VAE are state-of-the-art embedding approaches, following earlier graph-mining similarity heuristics.Embedding methods represent nodes as low-dimensional vectors and can use proximity, such as inner products, to predict links.Source: §1 · p. 1
- Undirected graph AE/VAE predict a connection from node i to node j with the same probability as the reverse, limiting their fit to applications with nonreciprocal links.Examples include web hyperlinks, Twitter follows, and artist-similarity recommendations.Source: §1 · p. 1
- Existing graph AE/VAE methods focus on undirected graphs, leaving open how to reconstruct directed graphs from vector representations and extend their promising performance to directed prediction.Earlier work had considered asymmetric measures and asymmetric proximity in embeddings, but effective reconstruction from vector representations remained unresolved.Source: §1 · pp. 1–2
- The paper introduces graph AE/VAE models for directed graphs, using a gravity-inspired decoder to reconstruct asymmetric relations from node embeddings.The authors also report evaluating the approach on three directed link-prediction tasks and three real-world datasets.Source: §1 · p. 2
2 PRELIMINARIES
The preliminaries establish graph AE/VAE as embedding-based link-prediction models, then identify their symmetric decoding as a mismatch for directed links. They frame the paper’s approach against existing directed-embedding methods that use separate source and target vectors.
2.1 Graph Autoencoders
- Graph AE encode nodes as low-dimensional vectors and decode those vectors to reconstruct the adjacency matrix, using inner products and a sigmoid in the standard formulation.The latent vectors are intended to preserve graph structure when reconstruction is close; training can minimize Frobenius reconstruction loss or weighted cross-entropy.Source: §2.1 · p. 2
2.2 Graph Convolutional Networks
- GCNs propagate transformed node features through normalized adjacency across layers; the paper uses them for consistency, prior success, and efficiency, while allowing alternative encoders.Each layer has edge-linear evaluation complexity, and the method is not limited to GCN encoders.Source: §2.2 · p. 2
2.3 Variational Graph Autoencoders
- Graph VAEs infer distributions over node vectors with GCN-produced means and log standard deviations, then decode latent-vector inner products and optimize a variational lower bound.The latent vectors are sampled from the learned distributions, and the ELBO includes a KL-divergence term.Source: §2.3 · pp. 2–3
2.4 Graph AE and VAE for Undirected Link Prediction
- For undirected link prediction, graph AE/VAE are trained with removed edges and sampled non-edges, then evaluated by ranking true links, often outperforming popular embedding baselines.The cited evaluation uses AUC or Average Precision; many prior experiments covered medium-size graphs because the inner-product decoder has O(dn^2) complexity, though scalable approaches were also reported.Source: §2.4 · p. 3
2.5 Why do these models fail to perform Directed Link Prediction?
- The symmetric inner-product decoder assigns the same probability to both edge directions, making standard graph AE/VAE unsuitable when directed relations are not reciprocal.Other symmetric decoders share this constraint; prior D-VAE work addressed small DAGs, leaving general directed graphs as an open extension for graph AE/VAE.Source: §2.5 · p. 3
2.6 On the Source/Target Vectors Paradigm
- Existing directed-embedding approaches such as HOPE and APP represent each node with separate source and target vectors to model asymmetric links.The paper’s source/target graph AE/VAE variant splits an encoded vector into those two representations, but the authors instead favor one latent vector per node and report that this approach outperforms the split-vector variant on directed tasks.Source: §2.6 · pp. 3–4
3 A GRAVITY-INSPIRED MODEL FOR DIRECTED GRAPH AE AND VAE
The model uses Newtonian gravity to address the challenge of reconstructing asymmetric relations from unique node vectors, whose inner products and distances are symmetric.
3 A GRAVITY-INSPIRED MODEL FOR DIRECTED GRAPH AE AND VAE
- The model addresses directed graph AE and VAE by reconstructing asymmetric relations from unique latent node vectors.The challenge is that inner products and distances between these vectors are symmetric.Source: §3 · p. 4
- A gravity-inspired decoder assigns node embeddings mass and uses acceleration to produce asymmetric relations.The paper draws an analogy between node embeddings and celestial objects: although distance is symmetric, acceleration can differ by direction when masses differ.Source: §3 · p. 4
3.1 Newton’s Theory of Universal Gravitation
Newton’s law relates gravitational force to two masses and the squared distance between them; unequal masses yield unequal accelerations toward one another. The paper uses the acceleration formulation as inspiration for its autoencoder models.
3.1 Newton’s Theory of Universal Gravitation
- Gravitational force is proportional to the product of two positive masses and inversely proportional to the squared distance between their centers.The passage denotes the masses m1 and m2, distance r, and force F.Source: §3.1 · p. 4
- When two masses differ, their accelerations toward each other differ, with the less massive object accelerating more toward the more massive one.The passage states this relationship for m1 and m2.Source: §3.1 · p. 4
- The paper draws on Newtonian acceleration to build its autoencoder models, noting that the theory approximates gravity when fields are not extreme.Newtonian gravity has been used in prior graph visualization and in graph-mining measures for symmetric node similarity.Source: §3.1 · p. 4
3.2 From Physics to Node Representations
The proposed analogy treats each node as having an embedding and a learned mass, then uses directed acceleration as an edge-likelihood indicator. A log transform and sigmoid support reconstruction of unweighted edges.
3.2 From Physics to Node Representations
- A node’s mass represents its propensity to attract neighboring nodes to point toward it through directed edges.The model assumes each node has a latent vector and a positive mass parameter.Source: §3.2 · p. 4
- The acceleration of node i toward node j serves as an indicator of the likelihood of directed edge (i, j), depending on j’s mass and the squared embedding distance.The passage gives r^2 = ||z_i - z_j||^2 as the squared distance.Source: §3.2 · p. 4
- The log-acceleration decoder uses a sigmoid to reconstruct unweighted adjacency entries.The log transform limits large values toward central nodes and can be negative, which is convenient for sigmoid reconstruction.Source: §3.2 · pp. 4–5
3.3 Gravity-Inspired Directed Graph AE
The directed graph AE learns node embeddings and log-mass estimates with a GCN encoder, then reconstructs adjacency with a gravity-inspired decoder. Its directed normalization aggregates features from outgoing neighbors, and its decoder can produce asymmetric predictions.
3.3 Gravity-Inspired Directed Graph AE
- The directed graph AE extends node embeddings with learned mass parameters to support directed link prediction.The subsection introduces how the graph autoencoder framework derives these parameters.Source: §3.3 · p. 5
3.3.1 Encoder.
- The GCN encoder outputs a d-dimensional latent vector and a log-mass estimate for each node.It processes the adjacency matrix and potentially node features; the mass output is log Gm_i.Source: §3.3.1 · p. 5
- The encoder replaces symmetric adjacency normalization with out-degree normalization, averaging features from nodes each node points to along with its own features.The layer combines these features with a ReLU activation.Source: §3.3.1 · p. 5
3.3.2 Decoder.
- The gravity-inspired decoder reconstructs adjacency with sigmoid-activated log acceleration, allowing predicted edge probabilities to differ by direction.Training minimizes weighted cross-entropy reconstruction loss by gradient descent.Source: §3.3.2 · p. 5
3.4 Gravity-Inspired Directed Graph VAE
The graph VAE extends the gravity-inspired model by inferring node embeddings together with mass parameters, then decoding sampled vectors to reconstruct the adjacency matrix. It is trained by maximizing the likelihood ELBO with gradient descent and a Gaussian prior.
3.4.1 Encoder.
- Each node’s VAE latent vector concatenates a d-dimensional embedding with a mass parameter, and two GCNs learn Gaussian distribution parameters using out-degree normalization.The model extends [25] and uses Gaussian hypotheses for the distributions.Source: §3.4.1 · p. 5
3.4.2 Decoder.
- The decoder uses vectors sampled from the learned distributions in the gravity-inspired scheme to reconstruct the adjacency matrix A.Source: §3.4.2 · p. 5
- Training maximizes the model likelihood’s ELBO with gradient descent and a Gaussian prior over the latent embeddings and mass parameters.The paper notes that its Gaussian assumptions are discussed in the experimental section.Source: §3.4.2 · p. 5
3.5 Generalization of the Decoder
An additional positive parameter λ generalizes the decoder by balancing embedding distance against mass attraction; λ = 1 recovers the earlier decoders.
3.5 Generalization of the Decoder
- The positive parameter λ balances node-distance importance against mass attraction, with λ = 1 as the special case used by the earlier decoders.It is tuned by cross-validation; physically, it replaces the squared distance in Newton’s formula with distance raised to 2λ.Source: §3.5 · p. 5
3.6 On Complexity and Scalability
The approach has linear space complexity in graph size under the stated sparse-adjacency assumptions, but its pairwise distance calculations give it quadratic time complexity. The experiments therefore focus on medium-sized graphs, while degeneracy-based scaling is proposed for future work.
3.6 On Complexity and Scalability
- For featureless nodes and sparse A with m nonzeros, space use is O(m + n(d + 1)); with n × f node features, it is O(m + n(f + d + 1)).The paper notes d ≪ n and f ≪ n in practice, and says space complexity grows linearly with graph size.Source: §3.6 · p. 5
- Pairwise L2 distances make decoding O(dn^2) in time, so experiments use graphs with thousands of nodes and edges; degeneracy-based methods are proposed for scaling to millions.A deeper investigation of scalability is left to future work.Source: §3.6 · pp. 5–6
4 EXPERIMENTAL ANALYSIS
The experiments compare gravity-inspired and standard graph autoencoders across three directed link-prediction tasks on three real-world graphs. Gravity-inspired models are competitive overall and perform best when evaluation requires distinguishing link direction or bidirectionality.
4.1.1 Task 1: General Directed Link Prediction.
- Task 1 removes 15% of edges with direction-aware masking, then classifies removed edges against an equal number of sampled unconnected pairs using AUC and AP.The authors expect directionality to have limited impact here because reverse pairs are unlikely to appear among negative samples, motivating two additional tasks.Source: §4.1.1 · p. 6
4.1.2 Task 2: Biased Negative Samples (BNS.) Link Prediction.
- Task 2 removes unidirectional edges and includes both directions of each validation and test pair, testing whether models reconstruct an edge and its absent reverse direction.Standard graph AE and VAE return symmetric predictions and are expected to fail this setting.Source: §4.1.2 · p. 6
4.1.3 Task 3: Bidirectionality Prediction.
- Task 3 removes one direction of each bidirectional training edge and tests whether models distinguish reciprocal links from reverse directions of true unidirectional edges.The task is designed to rely strongly on directionality learning.Source: §4.1.3 · p. 6
4.2.1 Datasets.
- The evaluation uses Cora2 and Citeseer2 citation graphs and the Google web graph; Google is denser and has a higher proportion of bidirectional edges.All graphs are unweighted and featureless.Source: §4.2.1 · p. 6
4.2.2 Standard and Gravity-Inspired Autoencoders.
- All four main AE/VAE models use two-layer GCN encoders with 64 hidden units, 32-dimensional latent vectors, and 200 training epochs; λ varies by task and graph.The task-specific λ settings were tuned using task 1 AUC.Source: §4.2.2 · p. 6
4.3 Results for Directed Link Prediction
- On task 2, gravity-inspired models lead with 76.19% AUC on Citeseer, 11+ points above the best baseline, and they also outperform alternatives on task 3.On task 2, direction-ignoring models reach 50.00% AUC and AP on all graphs; task 3 reaches 85.82% AUC for gravity-inspired graph AE on Google.Source: Table 2 · p. 7, §4.3 · p. 7
4.2.3 Baselines.
- The comparisons include source/target graph AE and VAE, HOPE, APP, and node2vec; experiments find no significant performance gap between AE models and their variational counterparts.AE/VAE training takes roughly 7 seconds on Cora, 8 seconds on Citeseer, and 5 minutes on Google; the cited baselines train faster on Google.Source: §4.2.3 · p. 7, §4.3 · pp. 7–8
4.3 Results for Directed Link Prediction
- On task 1, gravity-inspired models significantly outperform standard graph AE and VAE; on Cora, graph VAE rises from 82.79% AUC to 91.92% AUC.APP is best among the directed baselines on all three datasets, alongside source/target graph AE on Google.Source: §4.3 · p. 7
4.4 Discussion
The discussion examines what the learned node masses capture, how the decoder’s proximity–mass balance affects results across tasks and graphs, and the study’s scope and possible extensions.
4.4 Discussion
- Nodes with smaller learned masses tend to connect to larger-mass neighbors, while the masses correlate with centralities without precisely matching any one measure.The reported centralities are lower for Google, which the authors suggest may relate to that graph’s structure and density.Source: §4.4 · pp. 8–9
4.4.2 Impact of the parameter
- For tasks 1 and 3, λ=1 is optimal on Cora and Citeseer, while Google performs better at higher λ; for task 2, λ=0.05 is optimal on all three graphs.Higher λ emphasizes symmetric node proximity over learned mass; the authors relate Google’s higher optimal λ to its greater density and proportion of symmetric relations, and task 2’s lower λ to the greater importance of directionality.Source: Figure 2 · p. 9, §4.4.2 · p. 9
4.4 Discussion
- Learned masses are positively correlated with most centrality measures, but negatively or nearly uncorrelated with out-degree; replacing them with fixed centralities underperforms.On Cora, betweenness-based masses reach 89.05% AUC, below the learned-mass VAE’s 91.92%; centrality-based initialization did not significantly improve performance.Source: §4.4 · p. 9, Table 3 · p. 9
4.4.3 Extensions and openings.
- Experiments use featureless graphs for fair comparison, although the method could also use node features and alternative graph neural network encoders.Future work is proposed on those extensions, better-suited VAE priors, scalability to directed graphs, and directed node clustering.Source: §4.4.3 · p. 9
5 CONCLUSION
The paper presents a Newtonian-gravity-inspired method for learning node embeddings with graph AE and VAE models on directed graphs, addressing directed link prediction.
5 CONCLUSION
- The proposed Newtonian-gravity-inspired method learns node embeddings from directed graphs using graph AE and VAE models.The conclusion says the models effectively address challenging directed link prediction problems and points to future research directions for improvement.Source: §5 · p. 9