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

EdgeReMIND: A Scalable, Top-Ranked Memorization Baseline for Temporal Multi-Relational Link Prediction
Sep 15, 2026Bryant PollardLink Prediction Temporal Link Prediction
Clemson University
Hyperbolic Graph Embedders for Link Prediction and Topology Reconstruction
Aug 7, 2026Robert Jankowski, Maksim Kitsak, Dorota Celińska-KopczyńskaLink Prediction Unsupervised Representation Learning
TU Delft · Indiana University · Institute of Informatics, University of Warsaw
GravityGraphSAGE: Link Prediction in Directed Attributed Graphs
May 10, 2026Riccardo Porcedda, Francesca Chiaromonte, Fabrizio Lillo +1Graph Neural Networks Graph Representation Learning
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

Sep 15, 2026J/K move · Enter open · S save

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

Bryant Pollard

Clemson University

Link Prediction Temporal Link Prediction Temporal KGs

Open paper AskPDF arXiv

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.

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