Concorde improves link prediction in sparse and complex graphs
Concorde: Geometry-Aware Link Prediction via Decoupled Energy Minimization
Machine LearningArtificial Intelligence
Summary
Link prediction helps guess which connections might form in networks, but this is hard when there isn’t much data or the network structure is complex. The authors introduce Concorde, a new approach that breaks down the problem into three simpler parts using geometry and graph properties to better predict links. One part looks at stable patterns in the network, another learns complex curved spaces to capture structure, and the last aligns distant connections. Tested on various datasets, Concorde shows much better precision especially in sparse networks.
What this means in practice
- •For social network engineers: Improve recommendations of new connections or friends in sparse and complex social graphs with greater accuracy.
- •For cybersecurity analysts: Detect potential hidden or emerging relationships in sparse network traffic to better identify threats or anomalies.
Authors
Ege Demirci, Ambuj Singh
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.