Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization

Ege Demirci, Ambuj SingharXiv 2026 · arXiv

TL;DR

Concorde is a new energy-based framework for link prediction that solves the "sparsity bottleneck" by decomposing link likelihood into three structurally decoupled branches: a stable spectral anchor, a mixed-curvature local residual, and a non-local hyperbolic steering field. This approach nearly doubles early retrieval precision (P@10%) on sparse graphs compared to previous state-of-the-art methods.

What Problem Does This Paper Address?

Link prediction—the task of identifying missing edges in a network—is a cornerstone of graph machine learning. However, current methods struggle with two major issues:

  1. The Sparsity Bottleneck: In sparse graphs, traditional "local" heuristics (like counting common neighbors) fail because nodes simply don't have enough shared neighbors. While "global" diffusion methods help, they often lack the fine-grained detail needed to distinguish between structurally similar nodes.
  2. Spectral Instability: Geometric deep learning (using hyperbolic or spherical spaces) offers a way to capture complex graph motifs like hierarchies and cliques. However, when researchers try to combine these learned geometric representations with traditional graph diffusion, the resulting models often become "spectrally brittle," meaning small changes in learned parameters can lead to wild, unstable fluctuations in the graph's global structure.

The authors propose the Spectral Decoupling Hypothesis: a single learned adjacency matrix cannot simultaneously preserve the graph's global spectrum (stability) and break local symmetries (precision). Concorde is designed to bypass this impossibility by separating these concerns into distinct, "decoupled" branches.

Methods

Concorde treats link prediction as an energy minimization problem, where the total energy $E(u, v)$ between two nodes is the sum of three specialized branches, fused by learned gates:

Overview of the Concorde architecture showing the three decoupled branches: Invariant Anchor, Mixed-Curvature Residual, and Non-Local Geodesic Field.
  1. Branch I: Invariant Anchor (Global Stability): This is a parameter-free branch based on multi-step diffusion. it captures the "macroscopic" topology of the graph. Because it is fixed and doesn't learn, it provides a stable foundation that preserves the graph's global spectrum.
  2. Branch II: Mixed-Curvature Residual (Local Detail): This branch operates on a product manifold ($\mathbb{H} \times \mathbb{S}$), combining hyperbolic space (good for tree-like structures) and spherical space (good for cliques). It uses a feature-aware Ollivier–Ricci curvature (ORC) proxy to reweight edges, allowing the model to "break symmetry" and distinguish between nodes that look identical to the global anchor.
  3. Branch III: Non-Local Geodesic Field (Bridging Gaps): To handle extreme sparsity, this branch learns a continuous vector field on the tangent bundle of hyperbolic space. It "steers" a query node toward its most likely partner across the manifold, allowing it to predict links even between nodes that are entirely disconnected in the current graph.

The model is trained using an $N$-pair ranking loss, which specifically penalizes the model if a true missing edge is ranked below any non-edge, directly optimizing for retrieval performance.

Datasets

The authors evaluated Concorde across five benchmarks representing different structural regimes:

  • Cora, CiteSeer, PubMed: Standard citation networks with rich node features.
  • OGBL-DDI: A dense, featureless drug-drug interaction network where local overlap is king.
  • Power: An electrical grid topology that is extremely sparse and featureless, representing the "hard mode" for link prediction.

Key Insights and Ideas

  • Geometry Follows Data: Instead of forcing a graph into a single manifold, Concorde uses a product space and learnable curvatures. This allows the model to adapt to the specific "shape" of the dataset—whether it's more hierarchical (hyperbolic) or community-dense (spherical).
  • Decoupling is Necessary: The "Spectral Decoupling Hypothesis" is the paper's theoretical heart. By proving that stability and detail are mathematically at odds in a single matrix, the authors justify why a multi-branch architecture is more than just an engineering trick—it's a structural requirement.
  • Early Precision Matters: Most link prediction papers report Average Precision (AP) or Hits@K. Concorde focuses on Early Precision (P@10%), arguing that in real-world retrieval (like recommending a friend or a drug interaction), only the very top of the ranked list matters.

Key Results

Concorde sets a new state-of-the-art in early retrieval precision across all tested regimes.

  • Sparse Graphs: On the "Power" dataset, Concorde achieved 27.58% P@10%, nearly doubling the performance of strong baselines like NCN (14.77%).
  • Attributed Graphs: On Cora and CiteSeer, it improved early precision by up to 91% over the strongest baselines.
  • Ablation Studies: As shown in Table 2, removing any single branch leads to a significant performance drop, confirming that the "division of labor" between the anchor, the residual, and the steering field is effective.
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 ± 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]

Limitations and Future Work

  • Computational Overhead: The Ollivier–Ricci curvature proxy requires Sinkhorn iterations. While precomputed and parallelizable, it adds a layer of complexity that might be difficult to scale to truly massive, billion-node graphs without further optimization.
  • Global Gating: Currently, the branches are fused using global scalar gates. The authors suggest that per-subgraph adaptive gating could further improve performance in graphs with high structural heterogeneity (e.g., a graph that is "tree-like" in one area but "clique-heavy" in another).
  • Calibration: Because the $N$-pair loss focuses on ranking, the model's raw probability scores might not be perfectly calibrated. Future work could involve adding a calibration head for applications requiring precise probability estimates.

Summary updated

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.
BibTeX
@misc{demirci2026concorde,
  author = {Ege Demirci and Ambuj Singh},
  title = {{Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization}},
  year = {2026},
  eprint = {2610.36204},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.36204},
}
Figure