PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Common Neighbor with Completion for Link Prediction

Xiyuan Wang, Haotong Yang, Muhan Zhang

arXiv:2302.00890v4cs.LGcs.AIcs.SI

TL;DR

Link prediction relies on graph structure, but unobserved links can reduce common neighbors and shift their distribution. The paper proposes NCN, which combines MPNN with structural features, and NCNC, which uses link prediction to complete common-neighbor structure. NCNC outperforms state-of-the-art models across standard link prediction benchmarks.

  • Problem

    Graph incompleteness can reduce common neighbors and shift their training-test distribution, affecting common-neighbor-based link prediction.

    Source: §1 · p. 2

  • Method

    NCN uses structural features to guide pooling of MPNN representations, while NCNC completes common-neighbor structure with a link prediction model before applying NCN.

    Source: §1 · p. 2

  • Results

    NCNC outperforms state-of-the-art baselines across various datasets in both speed and prediction performance.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    Completing common-neighbor structure before applying NCN significantly improves NCN performance.

    Source: §1 · p. 2

    The paper analyzes incompleteness only for common-neighbor structures and presents NCN and its variants as implementations of the MPNN-then-SF framework.

    Source: §8 · p. 10

Abstract

from arXiv · show

In this work, we propose a novel link prediction model and further boost it by studying graph incompleteness. First, we introduce MPNN-then-SF, an innovative architecture leveraging structural feature (SF) to guide MPNN's representation pooling, with its implementation, namely Neural Common Neighbor (NCN). NCN exhibits superior expressiveness and scalability compared with existing models, which can be classified into two categories: SF-then-MPNN, augmenting MPNN's input with SF, and SF-and-MPNN, decoupling SF and MPNN. Second, we investigate the impact of graph incompleteness -- the phenomenon that some links are unobserved in the input graph -- on SF, like the common neighbor. Through dataset visualization, we observe that incompleteness reduces common neighbors and induces distribution shifts, significantly affecting model performance. To address this issue, we propose to use a link prediction model to complete the common neighbor structure. Combining this method with NCN, we propose Neural Common Neighbor with Completion (NCNC). NCN and NCNC outperform recent strong baselines by large margins, and NCNC further surpasses state-of-the-art models in standard link prediction benchmarks. Our code is available at https://github.com/GraphPKU/NeuralCommonNeighbor.

1 INTRODUCTION

MPNN-based link prediction can miss pairwise structural differences, while existing ways of combining structural features (SF) and MPNN trade expressivity against scalability. The paper introduces MPNN-then-SF and NCN, then addresses incompleteness in common-neighbor structure with NCNC.

1 INTRODUCTION

  • GAE can give the same prediction to links with different pairwise relations when symmetry gives their target nodes identical MPNN representations.For example, one target pair shares a common neighbor and the other does not.Source: §1 · p. 1
  • SF-then-MPNN can capture common-neighbor node representations but requires a separate MPNN run per target link, whereas SF-and-MPNN runs once but may only count common neighbors.SEAL exemplifies SF-then-MPNN; BUDDY exemplifies SF-and-MPNN.Source: §1 · p. 2
  • MPNN-then-SF first applies MPNN to the original graph, then uses structural features to guide pooling, combining common-neighbor node features with one MPNN run for all target links.The paper introduces Neural Common Neighbor (NCN) as this architecture's implementation and reports superior performance and scalability to existing models.Source: §1 · p. 2
  • Graph incompleteness reduces common neighbors and shifts their training-test distribution; the proposed NCNC approach uses NCN to complete the structure before applying NCN again.The paper reports that this method significantly improves NCN performance.Source: §1 · p. 2

2 PRELIMINARY

The preliminary section defines the graph and neighborhood notation used for link prediction. It also introduces MPNN as neighbor-based node-representation updating.

2 PRELIMINARY

  • The graph is undirected, with an edge set, node-feature matrix, and symmetric adjacency matrix whose entries indicate whether a node pair is connected.The degree counts adjacent nodes, and a node's neighborhood is the set of nodes connected to it.Source: §2 · p. 2
  • High-order adjacency entries count walks of a given length, while shortest-path neighborhoods identify nodes at a specified distance.The notation also permits neighborhoods defined by shortest-path distance in a high-order graph.Source: §2 · pp. 2–3
  • An MPNN layer updates a node representation by aggregating messages from its neighbors and combining them with the node's prior representation.The functions may be MLPs, and aggregation may use sum or max.Source: §2 · p. 3

3 RELATED WORK

Related work includes node-embedding, heuristic, and GNN link predictors, with GNN approaches combining node representations and structural features in different ways. The section also situates the paper's focus on how graph incompleteness affects common-neighbor features.

3 RELATED WORK

  • GAE predicts a link from the inner product of its target nodes' MPNN representations, while SEAL pools representations from an MPNN run on a target-link subgraph.Neo-GNN and BUDDY instead combine original-graph MPNN representations with structural features such as common-neighbor counts.Source: §3 · p. 3
  • Common Neighbor, Resource Allocation, and Adamic-Adar are heuristics based on first-order common neighbors.Neo-GNN extends neighborhood-overlap features to higher-order neighborhoods, and BUDDY also uses higher-order neighborhood differences.Source: §3 · pp. 3–4
  • The section presents a framework for summarizing pairwise structural features using neighborhood overlap or difference, node-degree functions, and high-order adjacency weights.Table 1 summarizes existing models using that framework.Source: Table 1 · p. 3, §3 · p. 4
  • Prior work examined unobserved links' effects on evaluation or target-link presence, while this paper focuses on incompleteness effects on common-neighbor features and model design.Other cited work added predicted edges for node classification, with the stated goal of enhancing same-class edges and diminishing others.Source: §3 · p. 4

4 NEURAL COMMON NEIGHBOR

The paper introduces MPNN-then-SF, which uses structural features to guide pooling of MPNN representations, and instantiates it as NCN. The architecture aims to combine expressivity with scalability, while NCN uses target nodes and their common neighbors.

4.1 NEW ARCHITECTURE COMBINING MPNN AND SF

  • MPNN-then-SF runs MPNN on the original graph once, then uses structural features to guide pooling of node representations for each target link.This combines feature-aware pooling with a single MPNN run across target links.Source: §4.1 · p. 5
  • Equation 7 and Equation 8 together are strictly more expressive than GAE, CN, RA, AA, Neo-GNN, and BUDDY.The theorem compares them with MPNN-only, SF-only, and MPNN-and-SF models.Source: §4.1 · p. 5
  • Coupling MPNN with structural features lets NCN distinguish equal-count common-neighbor pairs when their common neighbors have different node features.SF-and-MPNN models typically count common neighbors but cannot distinguish those pairs by common-neighbor features.Source: Figure 3 · p. 4, §4.1 · p. 5

4.2 NEURAL COMMON NEIGHBOR

  • NCN pools representations of target nodes and their first-order common neighbors, whose MPNN representations implicitly capture higher-order information.The authors chose this node set for scalability after observing marginal gains from explicitly considering higher-order neighbors once MPNN was included.Source: §4.2 · p. 5
  • NCN is strictly more expressive than GAE, CN, RA, and AA, while Neo-GNN and BUDDY are not more expressive than NCN.In scenarios where common-neighbor properties matter, NCN can exceed both Neo-GNN and BUDDY in expressiveness.Source: §4.2 · p. 5

5 NEURAL COMMON NEIGHBOR WITH COMPLETION

The paper examines how unobserved edges alter common-neighbor information and affect link prediction, then proposes common-neighbor completion (CNC). Applying NCN to the completed structure yields NCNC, which retains a single MPNN run across target links.

5.1 INCOMPLETENESS VISUALIZATION

  • In the incomplete graph, common neighbors are lost, and on ogbl-collab this creates a train–test distribution shift that disappears in the complete graph.For randomly split Cora, training and test edges lose a similar ratio of common neighbors and do not exhibit this shift.Source: §5.1 · pp. 6–7
  • CN test performance declines on incomplete graphs when the common-neighbor distribution changes, while ogbl-collab training performance remains similar across complete and incomplete graphs.The passage reports similar test and training score declines on incomplete Cora graphs when their common-neighbor distributions change.Source: §5.1 · p. 7

5.2 COMMON NEIGHBOR COMPLETION

  • CNC softly completes common-neighbor links with predicted probabilities instead of completing every edge in the graph.If one of the two links connecting a candidate neighbor to the target nodes is unobserved, NCN predicts its probability; if both are unobserved, the probability is set to zero.Source: §5.2 · p. 7
  • NCNC reapplies NCN to the graph completed with soft common-neighbor weights, while its MPNN still takes the original graph as input and runs once for all target links.The authors use NCN for completion in practice because weaker link prediction models may not accurately recover unobserved common-neighbor structure.Source: §5.2 · p. 7
  • NCNC addresses NCN’s degeneration to GAE when target pairs lack observed common neighbors, degenerating only when both target nodes are isolated.In that case, no structural features are available, so the model relies on target-node representations.Source: §5.2 · p. 7

6 EXPERIMENT

Experiments evaluate NCN and NCNC on seven real-world benchmarks, with NCNC achieving the strongest overall results. Ablations assess structural features, the MPNN-then-SF design, and neighborhood variants, while scalability tests compare inference time and GPU memory.

6 EXPERIMENT

  • The evaluation uses seven benchmarks: Cora, Citeseer, Pubmed, ogbl-collab, ogbl-ppa, ogbl-citation2, and ogbl-ddi.Baselines include heuristics, GAE models, SF-then-MPNN models, and SF-and-MPNN models.Source: §6 · p. 8, §6.1 · p. 8

6.1 EVALUATION ON REAL-WORLD DATASETS

  • NCNC is top-performing on all seven datasets, while NCN surpasses all baselines on five and improves average score by 5% over BUDDY.On ogbl-ppa, NCNC achieves 61.42% HR@100, over 10% above BUDDY.Source: §6.1 · p. 8

6.2 SCALABILITY

  • NCN and NCNC have computation overhead similar to GAE because each runs MPNN only once; Figure 5 reports inference time and GPU memory on ogbl-collab.The measurement includes preprocessing and prediction of one test-link batch; SEAL has an out-of-memory problem and uses only small batch sizes.Source: §6.2 · p. 9, Figure 5 · p. 9

6.3 ABLATION ANALYSIS

  • On OGB datasets, GAE+CN outperforms GAE by 70%, and NCN improves scores by 5.5% over GAE+CN.GAE+CN adds common neighbors as pairwise features; the comparison highlights the MPNN-then-SF design against MPNN-and-SF.Source: §6.3 · p. 9
  • NCN, NCN-diff, and NCN2 perform similarly on most datasets, suggesting first-order neighborhood overlap may suffice; NCN-diff scores lower on DDI, possibly due to noisy differences at high node degree.NCN-diff adds neighborhood differences, while NCN2 adds high-order neighborhood overlap.Source: §6.3 · p. 9

7 CONCLUSION

The conclusion presents NCN as a scalable link-prediction model and NCNC as its completion-based extension. It reports that NCNC outperforms state-of-the-art baselines across datasets in speed and prediction performance.

7 CONCLUSION

  • NCNC outperforms state-of-the-art baselines across various datasets in both speed and prediction performance.It combines Common Neighbor Completion with NCN to address incompleteness-related common-neighbor loss and distribution shifts.Source: §7 · p. 9
  • NCN is presented as a scalable, robust link-prediction model using learnable pairwise features.The paper identifies NCN as an implementation of the MPNN-then-SF architecture.Source: §7 · p. 9
  • The conclusion identifies common-neighbor loss and distribution shifts as effects of graph incompleteness that the paper investigates and visualizes.Common Neighbor Completion is proposed to mitigate these problems.Source: §7 · p. 9

8 LIMITATIONS

The authors limit their MPNN-then-SF exploration to NCN and two variants, and focus their incompleteness analysis on common-neighbor structures. The appendix describes a pooling construction weighted by high-order adjacency edge weights.

8 LIMITATIONS

  • The paper does not exhaust the MPNN-then-SF design space, proposing only NCN and the NCN2 and NCN-diff variants.The authors also note that incompleteness may affect structural features beyond common neighbors, and that completion could potentially generalize to them.Source: §8 · p. 10

A.1 DERIVATION OF EQUATION 8

  • For set Sab, the derivation uses sum pooling weighted by g(a)g(b), where g takes high-order adjacency edge weights as input.The construction sums weighted MPNN representations.Source: §A.1 · p. 12

A.2 PROOF OF THEOREM 1 AND 2

The appendix argues that NCN is more expressive than several link-prediction approaches, proving this by simulation and a constructed example. The example distinguishes links that GAE and several structural methods cannot distinguish.

A.2 PROOF OF THEOREM 1 AND 2

  • NCN can express GAE because Equation 7 is part of NCN and summing Equation 7 yields GAE's link prediction.GAE predicts link scores using the inner product of the target nodes' MPNN representations.Source: §A.2 · p. 12
  • The proof states that NCN is more expressive than CN, RA, and AA, and that combining Equations 7 and 8 is more expressive than BUDDY and Neo-GNN.The paper defines strict expressivity by requiring that one algorithm distinguish every link pair another can, plus at least one additional pair.Source: §A.2 · p. 12
  • NCN distinguishes two links with different common-neighbor features even when GAE, CN, RA, AA, Neo-GNN, and BUDDY cannot distinguish them.The constructed graph makes the target nodes symmetric for the compared methods, while their common neighbors have different features.Source: §A.2 · p. 12

B DATASET STATISTICS

The section points to dataset statistics and specifies the random edge split used in evaluation, with a distinct input-edge rule for collab.

B DATASET STATISTICS

C MODEL ARCHITECTURE

NCN builds link representations from endpoint and common-neighbor embeddings after message passing, while NCNC adds predicted links to complete common-neighbor structure. The section also describes their evaluation settings, computational costs, scalability, and comparisons across models and metrics.

C MODEL ARCHITECTURE

  • NCN uses one MPNN pass and combines endpoint and common-neighbor representations; NCNC uses predicted links to complete common neighbors before prediction.Training target links are removed from the input graph, while validation and test target links are unobserved.Source: C MODEL ARCHITECTURE · pp. 12–14, Figure 6 · p. 13

E TIME AND SPACE COMPLEXITY

D EXPERIMENTAL SETTINGS

  • The experiments use Optuna random searches selected by validation score, run the models with 10 random seeds, and require 280 GPU hours to reproduce the main results.Experiments ran on an Nvidia 4090 GPU using PyTorch Geometric and PyTorch.Source: D EXPERIMENTAL SETTINGS · p. 14

F SCALABILITY COMPARISON ON DATASETS

  • NCN has computation overhead similar to GAE, NCNC usually scales better than Neo-GNN, and SEAL has the worst scalability.On ogbl-citation2, SEAL uses the least GPU memory with small batches because it runs MPNN on sampled subgraphs rather than the large whole graph.Source: F SCALABILITY COMPARISON ON DATASETS · p. 15

G COMPARISON WITH OTHER LINK PREDICTION MODELS

  • NCN and NCNC outperform node-embedding methods on all ogb datasets; NCN gains 89% on ogbl-ppa and 20% on average over PLNLP.The comparison with GIDN is incomplete because it reports experiments on only ogbl-collab.Source: Table 7 · p. 16, G COMPARISON WITH OTHER LINK… · p. 16

H CNC EXAMPLE

  • The Cora example shows NCNC completing a missing common neighbor and assigning target link (0, 1) higher existence probability than NCN.The illustration plots completions only above probability 0.5, and one displayed completed neighbor is absent even from the graph containing all train, validation, and test edges.Source: Figure 8 · p. 16

I ABLATION OF MPNN

  • NCN’s performance varies with the MPNN choice, but it improves over GAE with every tested GNN.The tested variants include GIN, GraphSage, max aggregation, GCN, and GAT.Source: Table 8 · p. 17, I ABLATION OF MPNN · p. 17

J CHOICE OF METRICS

  • Across the reported metrics, NCN achieves 11 best scores and NCNC 22, compared with 9 for the strongest baseline, BUDDY.Table 9 notes that blank entries represent experiments unfinished because of time constraints.Source: Table 9 · p. 17, J CHOICE OF METRICS · p. 17

Related papers

Loading 2302.00890v4…