Research map / Label-efficient and robust learning / Recognition and long-tail
OCN: Effectively Utilizing Higher-Order Common Neighbors for Better Link Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Orthogonal Common Neighbor (OCN) and its polynomial-filter variant OCNP, which orthogonalize higher-order common-neighbor features and normalize them by walk counts to improve GNN link prediction.
Problem
Higher-order common neighbors for link prediction are redundant across orders and suffer over-smoothing as order grows, limiting their usefulness in state-of-the-art pairwise link prediction models.
Approach
Gram-Schmidt-style orthogonalization (approximated by a running moving average and by orthonormal polynomial filters) removes linear dependence between different-order CN coefficients, and path-based normalization divides each node's coefficient by the number of walks it participates in, generalizing Resource Allocation; combined with an MPNN-then-structural-feature pipeline.
Key results
- OCN improves on the strongest baselines by an average of 7.7% across the five datasets where it beats NCNC (ogbl-ppa reaches 69.79 HR@100 vs 61.42 for NCNC).
- OCN achieves 97.42 HR@20 on ogbl-ddi versus 84.11 for NCNC; OCNP reaches 74.87 HR@100 on ogbl-ppa.
- OCN is 0.6% behind NCNC on Citeseer and Citation2, and OCN's average ranking is 1.57 versus 2.71 for NCNC.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add orthogonalization to normalizedCN-weighted common neighbors (ablation) | OCN · PPA | HR@100: 59.94$\pm$ 2.65 -> 69.79$\pm$0.85 | Helped |
| Add normalizedCN weighting to orthogonalized common neighbors (ablation) | OCN · PPA | HR@100: 18.39$\pm$5.94 -> 69.79$\pm$0.85 | Helped |
| Add normalizedCN weighting to polynomial-filtered common neighbors (ablation) | OCNP · PPA | HR@100: 30.86$\pm$1.03 -> 74.87$\pm$0.94 | Helped |
| Sum rather than concatenate structural and MPNN terms (ablation) | OCN · PPA | HR@100: 34.30$\pm$ 6.55 -> 69.79$\pm$0.85 | Helped |
| Sum rather than concatenate structural and MPNN terms (ablation) | OCNP · PPA | HR@100: 28.11$\pm$2.01 -> 74.87$\pm$0.94 | Helped |
| Retain nonlinear layers (ablation) | OCN · PPA | HR@100: 6.91$\pm$3.34 -> 69.79$\pm$0.85 | Helped |
| Retain nonlinear layers (ablation) | OCNP · PPA | HR@100: 12.82$\pm$1.37 -> 74.87$\pm$0.94 | Helped |
| Use MPNN-then-SF instead of SF-and-MPNN (ablation) | OCN · PPA | HR@100: 59.30$\pm$0.54 -> 69.79$\pm$0.85 | Helped |
| Use MPNN-then-SF instead of SF-and-MPNN (ablation) | OCNP · PPA | HR@100: 57.45$\pm$0.89 -> 74.87$\pm$0.94 | Helped |
| Limit common-neighbor orders to 1-hop and 2-hop rather than adding 3-hop CNs (ablation) | OCN · Pubmed | HR@100: 69.56$\pm$4.66 -> 83.96$\pm$0.51 | Helped |
| Limit common-neighbor orders to 1-hop and 2-hop rather than adding 3-hop CNs (ablation) | OCNP · Collab | HR@50: 59.31$\pm$0.57 -> 67.74$\pm$0.16 | Helped |
| Use walk-based higher-order common neighbors rather than SPD-based neighbors (ablation) | OCN · PPA | HR@100: 44.37$\pm$2.19 -> 69.79$\pm$0.85 | Helped |
Surprising findings
- Removing the nonlinear layers (OCN-Linear) causes little drop on most datasets but collapses performance on ogbl-ppa (6.91 HR@100).
- Adding 3-hop common neighbors (OCN-3) did not improve performance and made training unstable, with OOM on ogbl-ppa.
Limitations
- Gains on smaller graphs (Cora, Citeseer, Pubmed) are modest and higher-order CNs may add uninformative information there.
- Three-hop CNs cause instability and high cost, so the method is restricted to orders 1 and 2.
- OCN uses more GPU memory than NCN on some datasets.
Experimental setup
Datasets: Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-citation2 ogbl-ddi
Benchmarks: Cora Citeseer Pubmed ogbl-collab ogbl-ppa ogbl-citation2 ogbl-ddi
Metrics: HR@100 HR@50 HR@20 MRR
Baselines: CN AA RA GCN SAGE SEAL NBFNet Neo-GNN BUDDY NCN NCNC PLNLP
Builds on: NCN Resource Allocation Batch Normalization BUDDY Neo-GNN
Closest papers by meaning
- Pure Message Passing Can Estimate Common Neighbor for Link Prediction (NeurIPS 2024 · similarity 0.89)
- Neural Common Neighbor with Completion for Link Prediction (ICLR 2024 · similarity 0.88)
- Revisiting Link Prediction: a data perspective (ICLR 2024 · similarity 0.85)
- Mixture of Link Predictors on Graphs (NeurIPS 2024 · similarity 0.84)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.84)
- GNNs Meet Sequence Models Along the Shortest-Path: an Expressive Method for Link Prediction (NeurIPS 2026 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.