Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization

Ege Demirci; Ambuj Singh

cs.LGOct 26, 2026

Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization

Authors: Ege Demirci, Ambuj Singh

Organizations: Department of Computer Science, UC Santa Barbara Santa Barbara, CA 93106, USA

Abstract

Link prediction remains difficult in sparse graphs, where diffusion heuristics lack connectivity and geometric methods suffer spectral instability when coupling learned representations with diffusion operators. We introduce Concorde, an energy-based framework that resolves this by decomposing link likelihood into three structurally decoupled branches: (i) a parameter-free spectral anchor that establishes permutation-invariant topological stability; (ii) a mixed-curvature residual on a learnable $\mathbb{H}^{d_h}_{c_h} \times \mathbb{S}^{d_s}_{c_s}$ product manifold, regularized by a feature-aware Ollivier-Ricci curvature proxy; and (iii) a continuous vector field on the tangent bundle of hyperbolic space for non-local structural alignment across topological gaps. The branches are fused via learned gating and trained with an N-pair ranking loss aligned with retrieval-style evaluation. Across five benchmarks spanning sparse, dense, featureless, and attributed regimes, Concorde establishes state-of-the-art early retrieval precision, nearly doubling P@10% over leading baselines in sparse settings.

Figures & tables

Panel of Figure 1 — Figure 1: Overview of Concorde. Link likelihood is decomposed into three structurally decoupled energy branches: a parameter-free spectral anchor on the unperturbed adjacency (global, $\mathrm{Aut}(G)$ -invariant), a mixed-curvature residual on $\mathbb{H}\times\mathbb{S}$ with a feature-aware Ollivier–Ricci guardrail (local symmetry-breaking), and a non-local geodesic steering field on $\mathcal{T}\mathbb{H}_{c}^{d}$ (bridging topological gaps). Learned scalar gates fuse the branches, and the model is trained with an $N$ -pair ranking loss aligned with early-retrieval evaluation.

Metric	Model	Cora	CiteSeer	PubMed	OGBL-DDI	Power
P@10	SEAL	6.52 $\pm$ 1.08	5.35 $\pm$ 1.12	∗∗	37.45 $\pm$ 1.15	11.34 $\pm$ 1.28
	HGCN	6.53 $\pm$ 1.11	7.25 $\pm$ 1.23	11.10 $\pm$ 1.25	27.32 $\pm$ 1.93	18.28 $\pm$ 1.19
	Neo-GNN	6.05 $\pm$ 0.32	6.23 $\pm$ 0.85	12.32 $\pm$ 0.74	25.80*	10.74 $\pm$ 0.39
	BUDDY	7.23 $\pm$ 0.45	7.93 $\pm$ 0.80	OOM	22.59 $\pm$ 2.02	12.53 $\pm$ 0.45
	NCN	10.12 $\pm$ 1.08	10.36 $\pm$ 0.32	3.23 $\pm$ 1.09	45.30 $\pm$ 0.15	14.77 $\pm$ 0.61
	NCNC	8.78 $\pm$ 0.58	10.84 $\pm$ 0.34	14.56 $\pm$ 0.89	45.22 $\pm$ 0.11	13.42 $\pm$ 0.31

Table 1: Link prediction performance comparison across five benchmark datasets. We report Early Precision (

P@10\%

P@20\%

) and Average Precision (AP) using an unbiased evaluation protocol. Results show mean

\pm

standard deviation over 10 runs, except where noted. ( ∗ ) Run only once due to runtime

>24

hrs; OOM: Out-of-memory; ( ∗∗ ) Each run takes

>1000

hrs [ 25 ]

Architecture Configuration				Average Precision (AP)
$S_{\text{anchor}}$	$S_{\text{res}}$	$S_{\text{field}}$	Description	Cora	CiteSeer	PubMed	OGBL-DDI	Power
✓	✓	✓	Concorde	4.50 $\pm$ 0.03	5.05 $\pm$ 0.18	2.83 $\pm$ 0.02	42.32 $\pm$ 0.14	6.39 $\pm$ 0.28
✓	×	×	The Invariant Anchor Only	2.45 $\pm$ 0.00	2.37 $\pm$ 0.00	2.30 $\pm$ 0.00	28.70 $\pm$ 0.00	3.88 $\pm$ 0.00
✓	✓	×	w/o Geodesic Steering	3.02 $\pm$ 0.27	4.70 $\pm$ 0.12	2.58 $\pm$ 0.15	38.38 $\pm$ 0.30	4.17 $\pm$ 0.59
✓	×	✓	w/o Mixed Curvature Residual	2.87 $\pm$ 0.08	2.59 $\pm$ 0.67	1.45 $\pm$ 0.28	38.22 $\pm$ 0.46	2.72 $\pm$ 0.45
×	×	×	Autocovariance	2.47 $\pm$ 0.00	2.65 $\pm$ 0.00	2.50 $\pm$ 0.00	29.73 $\pm$ 0.00	4.12 $\pm$ 0.00

Table 2: Macro-Ablation: Impact of the Tri-Branch Superposition. We report Average Precision (AP) to demonstrate how each structural operator contributes to hard-negative discrimination.

Configuration	Cora	CiteSeer	PubMed	OGBL-DDI	Power
Vanilla Autocovariance	2.47	2.65	2.50	29.73	4.12
Same-loss learned reweight(no geometry)	4.16	4.52	2.47	38.15	4.52
Full Concorde	4.50	5.05	2.83	42.32	6.39

Table 3: Same-loss learned reweighting without geometry, versus vanilla Autocovariance and full Concorde (AP). All three use the identical

N

-pair loss and evaluation protocol; only the geometric inputs differ.

Configuration	Cora	CiteSeer	PubMed	OGBL-DDI	Power
Concorde	4.50 $\pm$ 0.03	5.05 $\pm$ 0.18	2.83 $\pm$ 0.02	42.32 $\pm$ 0.14	6.39 $\pm$ 0.28
w/o Hyperbolic Geometry ( $\mathbb{H}$ )	4.38 $\pm$ 0.05	4.72 $\pm$ 0.05	2.75 $\pm$ 0.03	39.30 $\pm$ 0.14	5.78 $\pm$ 0.30
w/o Spherical Geometry ( $\mathbb{S}$ )	4.34 $\pm$ 0.07	5.01 $\pm$ 0.08	2.73 $\pm$ 0.04	38.32 $\pm$ 0.20	6.28 $\pm$ 0.20
w/o Mixed Curvature (Euclidean Only)	4.30 $\pm$ 0.03	4.70 $\pm$ 0.03	2.67 $\pm$ 0.03	38.52 $\pm$ 0.17	5.85 $\pm$ 0.32
w/o Feature-Aware ORC ( $\kappa$ )	4.37 $\pm$ 0.03	4.80 $\pm$ 0.04	2.74 $\pm$ 0.04	39.22 $\pm$ 0.20	6.27 $\pm$ 0.30
w/o Local Neighborhood Geometry	4.29 $\pm$ 0.07	4.56 $\pm$ 0.70	2.55 $\pm$ 0.05	39.01 $\pm$ 0.44	4.85 $\pm$ 0.18

Table 4: Micro-Ablation: Components of the Local Geometric Energy (

S_{\text{res}}

). We isolate the impact of manifold choice and intrinsic structural guardrails on ranking quality. We report Average Precision (AP).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Single-matrix AP	Full AP	$\Delta$	Spectral drift
Power	4.54	6.39	$\mathbf{-1.85}$	$\mathbf{0.27}$
OGBL-DDI	39.80	42.32	$-2.52$	0.03
CiteSeer	4.63	5.05	$-0.42$	0.10
Cora	4.27	4.50	$-0.23$	0.12
PubMed	2.72	2.83	$-0.11$	0.06

Appendix

Table 5: Coupled single-matrix model versus full decoupled Concorde (AP), with the relative spectral drift of the coupled learned matrix. The coupled model underperforms on all five datasets, most on sparse featureless Power and least on feature-rich Cora, matching the prediction of Proposition 1 that node features partially relax the structural impossibility.

Dataset	Enrichment (Br. II)	Enrichment (Br. III)	Dominant Branch
Cora	$1.05\times$	$0.95\times$	Branch II
CiteSeer	$1.08\times$	$0.92\times$	Branch II
PubMed	$1.45\times$	$0.55\times$	Branch II
OGBL-DDI	$1.69\times$	$0.31\times$	Branch II
Power	$0.90\times$	$1.10\times$	Branch III

Appendix

Table 6: Branch enrichment in globally top-

10\%

ranked predictions. Enrichment

>1

indicates over-representation of that branch’s candidate edges at the top of the ranked list. All results significant at

p<10^{-4}

(Fisher exact test).

Dataset	ORC Precomputation (s)	Time per Epoch (s)
Cora	3.2	2.4
CiteSeer	4.7	3.2
PubMed	32.4	54.1
Power	12.2	5.8
OGBL-DDI	75.9	7.2

Appendix

Table 7: Wall-clock runtime for ORC proxy precomputation and average per-epoch training time for Concorde.

s/epoch	Concorde	NCNC	OCNP	BUDDY	Gelato
Cora	2.4	4.8	3.2	0.6	3.3
CiteSeer	3.2	8.3	4.8	485	2.9
PubMed	54.1	6.2	4.4	OOM	49.8
OGBL-DDI	7.2	36.2	28.1	342	1.4
Power	5.8	7.6	6.9	498	7.2

Appendix

Table 8: Per-epoch training time (s) across methods, identical hardware and full-negative protocol.

peak GB	Concorde	NCNC	OCNP	BUDDY	Gelato
Cora	2.45	1.85	1.23	1.62	1.83
CiteSeer	2.14	2.93	1.32	12.84	1.18
PubMed	12.84	4.15	3.77	OOM	18.12
OGBL-DDI	13.89	6.82	5.56	55.39	7.49
Power	3.05	2.84	1.42	37.28	3.08

Appendix

Table 9: Peak GPU memory (GB) across methods, identical hardware and full-negative protocol.

Dataset	$d_{h}{=}d_{s}$	Hidden	LR	WD	$k$	Scale	Self-loops	Epochs
Cora	16	64	$10^{-3}$	$5{\times}10^{-4}$	3	3	✓	100
CiteSeer	16	64	$10^{-4}$	$5{\times}10^{-4}$	3	3	✓	100
PubMed	32	128	$10^{-3}$	0	3	–	×	100
OGBL-DDI	32	512	$10^{-3}$	$5{\times}10^{-5}$	1	3	✓	250
Power	32	256	$10^{-3}$	$10^{-5}$	1	1	✓	250

Appendix

Table 10: Dataset-specific hyperparameter configurations for Concorde.

Dataset	Mean degree	$\lambda_{\text{anchor}}$	$\lambda_{\text{field}}$
OGBL-DDI	dense	0.62	0.10
CiteSeer	2.33	0.48	0.13
Cora	3.32	0.44	0.28
PubMed	${\sim}4.5$	0.47	0.33
Power	2.27	0.47	0.63

Appendix

Table 11: Learned gate values by dataset, ordered by mean degree. Both gates are initialised at

(\lambda_{\text{anchor}},\lambda_{\text{field}})=(0.50,0.12)

Dataset	Learned	Tuned fixed	Equal ( $\lambda{=}1$ )	Learned $-$ Equal
OGBL-DDI	42.32	40.18	30.45	$\mathbf{+11.87}$
Power	6.39	6.18	4.20	$+2.19$
PubMed	2.83	2.73	2.32	$+0.51$
CiteSeer	5.05	4.92	4.78	$+0.27$
Cora	4.50	4.40	4.24	$+0.26$

Appendix

Table 12: Gating-policy ablation (AP, mean over 3 runs). Learned gating versus a per-dataset oracle-tuned fixed gate and equal weighting (

\lambda=1

LPE dim $k$	16	32	64	128
Power	4.55	6.36	6.12	6.47
OGBL-DDI	38.33	40.47	42.10	43.28

Appendix

Table 13: LPE dimension sweep (AP) on the featureless graphs.

LPE source	Power AP	OGBL-DDI AP
Full graph (as reported)	6.36	43.28
Training-only graph	6.12	42.84

Appendix

Table 14: LPE leakage check (AP): encodings computed on the full graph (as reported) versus the training-only graph.

Link Prediction

Link prediction estimates missing or future relationships in graphs, from social ties and knowledge-graph facts to biological interactions.

See all 46 papers

Sep 15, 2026

EdgeReMIND: A Scalable, Top-Ranked Memorization Baseline for Temporal Multi-Relational Link Prediction

Temporal link prediction on the Temporal Graph Benchmark 2.0 (TGB 2.0) faces a scalability ceiling: on the benchmark's three largest datasets, every existing embedding method runs out of memory or exceeds the time budget. These large-scale graphs are the ones nearest real deployment scale, so failing on them is a real production limitation. EdgeReMIND sets the highest reported test mean reciprocal rank (MRR) on six of eight TGB 2.0 datasets and is the only relation-aware method that runs on all of them. This linear memorization model, with learned per-relation weights over data-calibrated features, is therefore not merely a fallback where embeddings fail but a practical state-of-the-art baseline across the benchmark.

Bryant Pollard

Clemson University

Link Prediction Temporal Link Prediction Temporal KGs

Ask PDF

Aug 7, 2026

Hyperbolic Graph Embedders for Link Prediction and Topology Reconstruction

Hyperbolic embeddings provide compact geometric representations of complex networks in hyperbolic spaces, but systematic comparisons of methods developed in machine learning, network science, and algorithmics remain rare. We benchmark 13 unsupervised hyperbolic graph embedders under a unified protocol for link prediction and topology reconstruction on synthetic and empirical networks. The protocol captures both missing-link recovery and the preservation of local and global network structure. Maximum-likelihood and representation-learning-based approaches, including hybrid variants, achieve the strongest overall performance, although no method dominates across all tasks and structural regimes. Performance is more strongly associated with embedding paradigm than with disciplinary origin. We identify the network regimes in which different paradigms succeed or fail and provide practical guidance for method selection in downstream applications.

Robert Jankowski, Maksim Kitsak, Dorota Celińska-Kopczyńska

TU Delft · Indiana University · Institute of Informatics, University of Warsaw

Link Prediction Unsupervised Representation Learning Hyperbolic Representation Learning

Ask PDF

May 10, 2026

GravityGraphSAGE: Link Prediction in Directed Attributed Graphs

Link prediction (inferring missing or future connections between nodes in a graph) is a fundamental problem in network science with widespread applications in, e.g., biological systems, recommender systems, finance and cybersecurity. The ability to accurately predict links has significant real-world applications, such as detecting fraudulent financial transactions or identifying drug-target interactions in biomedicine. Despite a rich literature, link prediction is still challenging, especially for graphs enriched with information on edges (direction) and nodes (attributes). In fact, research on link prediction, especially the one based on Graph Deep Learning (GDL), has mostly focused on undirected graphs, without fully leveraging node attributes. Here, we fill this gap by proposing Gravity-GraphSAGE (GG-SAGE), a modified version of GraphSAGE, a GDL model for node embeddings, composed of a gravity-inspired decoder. This implementation is the first example in the literature of a GraphSAGE backbone adopted for directed link prediction. Using the benchmark datasets Cora, Citeseer, PubMed and 16 real-world graphs from the online Netzschleuder repository, we show that our proposed model outperforms state-of-the-art GDL link prediction techniques. Using further experimental evidence, we relate the quality of the output of our model with various characteristics of the graph, suggesting that our framework scales well when applied to data of increasing complexity.

Riccardo Porcedda, Francesca Chiaromonte, Fabrizio Lillo +1

Department of Excellence L’EMbeDS, Sant’Anna School of Advanced Studies, Pisa, Italy · Department of Statistics and Huck Institutes of the Life Sciences, The Pennsylvania State University, USA · Class of Science, Scuola Normale Superiore, Pisa, Italy +1

Graph Neural Networks Graph Representation Learning Link Prediction Graph Embedding

Ask PDF

Abstract

Link Prediction

Explore similar work

EdgeReMIND: A Scalable, Top-Ranked Memorization Baseline for Temporal Multi-Relational Link Prediction

Hyperbolic Graph Embedders for Link Prediction and Topology Reconstruction

GravityGraphSAGE: Link Prediction in Directed Attributed Graphs