Source-linked AI summary
Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction
Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, Hyunwoo J. Kim
TL;DR
Link prediction remains challenging because GNNs often rely on smoothed node features while structural signals such as neighborhood overlap are important, and heuristics have their own limitations. Neo-GNNs learn structural features from adjacency matrices, model overlapped neighborhoods, and combine structural and feature-based scores. Across OGB datasets, they consistently achieve state-of-the-art link-prediction performance.
Problem
GNNs can underuse structural information important for link prediction, while heuristic methods require manually designed features and cannot use node features.
Method
Neo-GNNs learn structural features from adjacency matrices, estimate overlapped neighborhoods, generalize overlap-based heuristics, and combine structural and feature-based scores.
Results
Neo-GNNs consistently achieve state-of-the-art link-prediction performance across four OGB datasets.
Takeaways & Limitations
Neo-GNNs provide a unified approach that uses learned structural information, supports overlapped multi-hop neighborhoods, and incorporates input node features.
Takeaways & Limitations
Heuristic methods require manually selected structural features, while structure-only methods cannot utilize node features for link prediction.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) have been widely applied to various fields for learning over graph-structured data. They have shown significant improvements over traditional heuristic methods in various tasks such as node classification and graph classification. However, since GNNs heavily rely on smoothed node features rather than graph structure, they often show poor performance than simple heuristic methods in link prediction where the structural information, e.g., overlapped neighborhoods, degrees, and shortest paths, is crucial. To address this limitation, we propose Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs) that learn useful structural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction. Our Neo-GNNs generalize neighborhood overlap-based heuristic methods and handle overlapped multi-hop neighborhoods. Our extensive experiments on Open Graph Benchmark datasets (OGB) demonstrate that Neo-GNNs consistently achieve state-of-the-art performance in link prediction. Our code is publicly available at https://github.com/seongjunyun/Neo_GNNs.
1 Introduction
Link prediction exposes a gap between feature-smoothing GNNs and structure-dependent heuristic methods. Neo-GNNs address this gap by learning structural features from adjacency information and combining them with feature-based GNNs.
- Motivation: Structural information such as overlapped neighborhoods, degrees, and shortest paths is crucial for link prediction, where heuristics can outperform GNNs.GNNs often rely on smoothed node features rather than graph structure.
- Approach: Neo-GNNs learn useful structural features from an adjacency matrix and estimate overlapped neighborhoods for link prediction.The model is designed to incorporate key link-related structure without manual processing.
- Approach: Neo-GNNs use neighborhood overlap-aware aggregation and adaptively combine structural and input-node-feature scores end to end.This combines the structural focus of Neo-GNNs with feature-based GNN representations.
- Contribution: Neo-GNNs generalize neighborhood-overlap heuristics and handle overlapped multi-hop neighborhoods.The contribution extends manually designed overlap-based structural scoring.
- Results: Neo-GNNs consistently achieve state-of-the-art link-prediction performance on four Open Graph Benchmark datasets.The reported evaluation covers OGB datasets and compares against GNN and heuristic methods.
2 Related Works
Prior work combines message passing over graph topology with heuristic link-prediction scores based on structural relationships. These approaches motivate adaptively incorporating structural information into GNNs for link prediction.
- Graph Neural Networks: GNNs learn node representations through neural message passing over graph topology, including information from multi-hop neighbors.The passage describes message passing as common in GCN, GraphSAGE, and GAT.
- Research Focus: The paper focuses on adaptively incorporating structural information into GNNs for link prediction.This focus connects topology-aware representation learning with structure-based link scoring.
- Link Prediction: Heuristic link-prediction methods score node pairs using structural information such as overlapped neighbors and shortest paths.Common neighbors and preferential attachment use one-hop neighborhoods, while other heuristics extend beyond one hop.
3 Methods
Neo-GNNs combine learned structural features from adjacency matrices with neighborhood-overlap aggregation, while adaptively integrating conventional feature-based GNN representations. The framework generalizes heuristic link-prediction methods, supports multi-hop overlap, and addresses their inability to use node features.
- Motivation and scope: Conventional heuristic methods use manually selected structural features and cannot incorporate node features, whereas Neo-GNNs learn structural features and combine them with feature-based GNNs.These limitations motivate an end-to-end model that uses both graph structure and input node features.
- Structural feature generator: Neo-GNNs learn structural features from an adjacency matrix instead of relying only on manually designed heuristic features.The structural feature generator uses learnable node- and edge-level functions; specific choices can reproduce features used by methods such as Adamic–Adar.
- Neighborhood overlap-aware aggregation: The model computes similarity from structural features of overlapped neighborhoods using unnormalized adjacency aggregation.This preserves individually represented neighboring-node features so inner products capture overlap-specific structural similarity.
- Multi-hop aggregation: Neo-GNNs extend neighborhood-overlap aggregation to multi-hop neighborhoods by combining powers of the adjacency matrix.The coefficient β controls the relative weighting of close and distant neighbors.
- Adaptive combination: The framework combines structural and feature-based representations by computing both similarity scores and taking their trainable convex combination.The structural representation Z and feature-based GNN representation H are combined using the learnable parameter α.
- Training: Neo-GNNs jointly train the proposed components and individual models using weighted binary cross-entropy losses.The loss formulation uses binary cross entropy with weighting coefficients λ_i.
4 Experiments
Experiments evaluate Neo-GNNs on four OGB link-prediction datasets, compare them with heuristic, embedding, and GNN baselines, and analyze structural, feature-combination, multi-hop, and heuristic-learning behavior.
- Experiment Settings: The evaluation ranks positive test edges against negative candidates using Hits@K on three datasets and MRR on OGB-Citation2.Each reported performance is averaged over 10 random initializations.
- Results on Link Prediction: Neo-GNNs achieve state-of-the-art performance across OGB-PPA, OGB-Collab, OGB-DDI, and OGB-Citation2.On OGB-Collab and OGB-DDI, improvements over the best baseline are 5.4% and 9.6%, respectively.
- Ablation Studies: Neo-GNNs without GCN retain state-of-the-art performance except on OGB-DDI while using only graph structures, unlike competing GNNs that also use input features.This supports the importance of overlapped-neighborhood structure for link prediction.
- Ablation Studies: Combining Neo-GNN and GCN scores with trainable α consistently outperforms either individual model, with OGB-DDI showing 42% and 80% improvements over the separate models.The learned α varies by dataset, adapting the balance between structural information and input features.
- Ablation Studies: Multi-hop overlapped neighborhoods improve performance over one-hop neighborhoods, while smaller β slows convergence but eventually yields similar performance.The analysis varies maximum hop L and decaying factor β on OGB-Collab.
- Analysis on learning neighborhood overlap-based heuristic methods: On OGB-PPA, Neo-GNNs learn neighborhood-overlap heuristics and align most closely with Resource Allocation, whose correlation is 0.9627 and performance is 49.33.Correlations with Adamic Adar and Common Neighbors are 0.9277 and 0.8982, matching their lower reported performances of 32.45 and 27.65.
5 Conclusion
The paper concludes that Neo-GNNs learn structural information from adjacency matrices, estimate overlapped neighborhoods, and combine structural and feature-based signals for link prediction. Across four OGB datasets, they achieve state-of-the-art performance while generalizing heuristic methods and handling multi-hop neighborhoods.
- Conclusion: Neo-GNNs learn structural features from adjacency matrices and estimate overlapped neighborhoods for link prediction.The model is designed to use structural information as a key element of link prediction.
- Conclusion: Neo-GNNs adaptively combine structural and input node features through integration with feature-based GNNs.This combines the two information sources in an end-to-end model.
- Conclusion: Neo-GNNs generalize neighborhood-overlap heuristics, handle overlapped multi-hop neighborhoods, and achieve state-of-the-art performance on four OGB link-prediction datasets.The conclusion reports this outcome across OGB-PPA, OGB-Collab, OGB-DDI, and OGB-Citation2.
A Comparison to heuristic methods for link prediction
The experiments compare Neo-GNNs with popular heuristic methods across seven traditional link-prediction datasets. Neo-GNN generally performs best among the evaluated methods, including on Power, where overlap-based heuristics perform poorly.
- Evaluation setup: Table 4 reports link-prediction performance averaged over 10 random initializations, with underlining denoting the best result and bold denoting the second best.The table compares Neo-GNNs with heuristic methods on traditional link-prediction datasets.
- Evaluation setup: Seven traditional link-prediction datasets are evaluated alongside Jaccard, preferential attachment, Katz, PageRank, and SimRank.The datasets are USAir, Power, Router, E.coli, PB, Yeast, and C.ele.
- Results: Neo-GNN consistently outperforms overlap-based heuristic methods across the traditional link-prediction datasets.The reported comparison also finds Neo-GNN generally better than other heuristic methods.
- Results: PageRank performs better than Neo-GNN on two datasets, making it the stated exception to Neo-GNN's overall advantage over other heuristics.
- Results: Neo-GNN achieves the best performance against all heuristic methods on Power, despite overlap-based heuristics performing worse there.
B Analysis on the correlation between adjacency matrices and multi-hop adjacency matrices
Neo-GNN improvements are more significant when the original and multi-hop adjacency matrices are highly correlated. This correlation indicates how informative overlapped neighborhoods are for predicting links.
- Multi-hop adjacency: A multi-hop adjacency entry A′_ij = 1 indicates at least one path between two nodes within K hops and overlapping neighbors within K/2 hops.
- Correlation analysis: The correlation between adjacency matrices is computed as corr(A, A′) = ρ(vec(A), vec(A′)), using the Pearson correlation of their vectorizations.
- Correlation analysis: High correlation implies that existing links tend to coincide with overlapped neighbors, whereas correlation near 0 makes overlap less useful for link prediction.
- Dataset comparison: The reported training-set correlations are 0.0038 for DDI and 0.8727 for Collab, indicating Neo-GNN should be more effective on Collab.
- Dataset comparison: The experiments in Table 3 are consistent with this correlation-based analysis.
C Broader Impact
Neo-GNNs use graph structure to support link prediction when node features are unavailable or sensitive. The paper highlights potential applications in recommendation and biology while cautioning about social-network privacy.
- Structure-only prediction: Neo-GNNs learn structural features from graph structures alone, rather than relying on conventional GNNs' smoothed node features.
- Potential applications: The structure-only approach may help recommendation systems avoid exploiting sensitive user features.The paper presents this as a potential benefit when privacy and anonymity matter.
- Potential applications: Neo-GNNs may support biological relationship discovery when drug or protein features are unavailable because feature engineering is expensive.
- Beyond link prediction: The Structural Feature Generator is described as a model-agnostic module that could benefit graph-related tasks beyond link prediction.
- Caveat: Neo-GNNs need careful use in social networks where privacy and anonymity are important.
D License of the assets
The implementation uses permissively licensed software components and reports the licenses governing the code and frameworks used in the experiments.
- Software licenses: The source code is implemented in PyTorch under the BSD License.
- Software licenses: The GNN baselines use PyTorch Geometric, which is licensed under MIT.
- Software licenses: SEAL is implemented from its official GitHub repository under the MIT License.
- Redistribution: The paper states that both BSD and MIT licenses permit use or redistribution under stipulated conditions.