PaperlayerView exact revision on arXiv

Source-linked AI summary

Link Prediction Based on Graph Neural Networks

Muhan Zhang, Yixin Chen

arXiv:1802.09691v3cs.LGstat.ML

TL;DR

Heuristic link prediction is limited by manually chosen assumptions that may fail across networks. The paper proves that γ-decaying heuristics can be approximated from local subgraphs and introduces SEAL, a GNN framework that learns graph structure, embeddings, and attributes. SEAL achieves strong performance against heuristic, latent-feature, and embedding methods across experiments.

  • Problem

    Existing link-prediction heuristics rely on assumptions about when links form, and those assumptions can fail in some networks.

  • Method

    The paper develops γ-decaying theory and uses it to motivate SEAL, which learns from local enclosing subgraphs with GNNs while incorporating embeddings and attributes.

  • Results

    SEAL achieved unprecedentedly strong performance compared with heuristics, latent-feature methods, and network-embedding algorithms.

  • Takeaways & Limitations

    Local enclosing subgraphs can support learning network-specific link-prediction heuristics rather than relying only on predefined heuristics.

  • Takeaways & Limitations

    The theory assumes properties including exponentially decaying heuristic contributions and local calculability conditions.

Abstract

from arXiv · show

Link prediction is a key problem for network-structured data. Link prediction heuristics use some score functions, such as common neighbors and Katz index, to measure the likelihood of links. They have obtained wide practical uses due to their simplicity, interpretability, and for some of them, scalability. However, every heuristic has a strong assumption on when two nodes are likely to link, which limits their effectiveness on networks where these assumptions fail. In this regard, a more reasonable way should be learning a suitable heuristic from a given network instead of using predefined ones. By extracting a local subgraph around each target link, we aim to learn a function mapping the subgraph patterns to link existence, thus automatically learning a `heuristic' that suits the current network. In this paper, we study this heuristic learning paradigm for link prediction. First, we develop a novel $γ$-decaying heuristic theory. The theory unifies a wide range of heuristics in a single framework, and proves that all these heuristics can be well approximated from local subgraphs. Our results show that local subgraphs reserve rich information related to link existence. Second, based on the $γ$-decaying theory, we propose a new algorithm to learn heuristics from local subgraphs using a graph neural network (GNN). Its experimental results show unprecedented performance, working consistently well on a wide range of problems.

1 Introduction

Heuristic link-prediction methods are simple and effective but rely on assumptions that can fail across networks. The paper addresses this by theoretically justifying local-subgraph learning and proposing SEAL, a GNN framework for learning network-specific graph features.

  • Heuristic methods score node similarity to estimate link likelihood, ranging from one-hop common neighbors and preferential attachment to high-order Katz, rooted PageRank, and SimRank.
  • Common neighbors can work in social networks but fail in protein-protein interaction networks, where many shared neighbors indicate lower interaction likelihood.
  • Local enclosing subgraphs provide training data for learning link-prediction heuristics, and contain enough structure to calculate first-order heuristics such as common neighbors.
  • High-order heuristics may outperform low-order ones, but learning them from whole-network enclosing subgraphs would impose unaffordable time and memory costs.
  • Under mild conditions, γ-decaying heuristics can be approximated from h-hop enclosing subgraphs with error decreasing at least exponentially as h grows.
  • SEAL uses a GNN to learn general graph structure features from local enclosing subgraphs, while also incorporating latent and explicit node features.
  • SEAL reportedly outperforms heuristic, latent-feature, network-embedding, and WLNM baselines by large margins.

2 Preliminaries

The preliminaries define graph, neighborhood, and walk notation and position graph learning alongside latent-feature and GNN approaches. They also describe prior supervised heuristic-learning methods and their limitations.

  • The network is modeled as an undirected graph G=(V,E), with adjacency matrix A indicating observed links.
  • A walk is a node sequence connected by edges, and its length is the number of traversed edges.
  • Latent-feature methods factorize network-derived matrices to learn low-dimensional node embeddings, emphasizing global properties and long-range effects.
  • GNNs commonly combine graph-convolution layers for local substructure features with aggregation into graph-level representations.
  • WLNM learns from local subgraphs but uses fixed-size adjacency tensors, potentially losing structure, and cannot incorporate latent or explicit features.

3 A theory for unifying link prediction heuristics

The section defines enclosing subgraphs and a γ-decaying theory that explains why high-order heuristics can be approximated from local neighborhoods. It then establishes this framework for Katz, rooted PageRank, and SimRank.

  • An h-hop enclosing subgraph contains nodes within h hops of either target node and accurately calculates any h-order heuristic.
  • A γ-decaying heuristic weights length-l contributions by a decaying factor γ^l and uses a nonnegative network-dependent function f.
  • Under two properties on f, the heuristic is approximable from an h-hop enclosing subgraph, with approximation error decreasing at least exponentially with h.
  • Any walk between the target nodes of length at most 2h + 1 is included in their h-hop enclosing subgraph, supporting local calculation of walk-based heuristics.
  • Katz satisfies the theory when d < 1/β; its small damping factor can therefore make local approximation effective.
  • Rooted PageRank and SimRank are also shown to be γ-decaying heuristics satisfying the theorem’s properties.
  • The discussion concludes that many path-counting and random-walk heuristics can be approximated from small enclosing subgraphs because distant structures receive exponentially smaller weight.

4 SEAL: An implemetation of the theory using GNN

SEAL learns general graph-structure features from local enclosing subgraphs with a GNN, combining structural labels with optional latent and explicit node features. Its node-information design encodes each node’s role relative to the target pair.

  • SEAL extracts enclosing subgraphs, constructs node-information matrices, and applies GNN learning to estimate link likelihood.
  • The node-information matrix includes structural labels, while embeddings and attributes can be concatenated to support joint feature learning.
  • DRNL assigns target nodes label 1 and groups other nodes by their distances to both target nodes, reflecting relative position and structural importance.
  • DRNL orders nodes first by the sum of their two distances and then by the product when those sums are equal.
  • A closed-form DRNL hash enables fast label computation, while nodes disconnected from either target receive a null label.
  • Embeddings must avoid recording training-link existence, because a GNN could optimize by fitting that information rather than broader link-prediction patterns.

5 Experimental results

SEAL is evaluated across eight networks against heuristic, heuristic-learning, latent-feature, and network-embedding methods. It generally outperforms these baselines, with local enclosing subgraphs providing strong link-prediction information.

  • Experimental setup: SEAL is evaluated using AUC and average precision across eight network datasets, with results averaged over 10 runs.The experiments randomly hold out existing and nonexistent links for testing and use the remainder for training.
  • Comparison to heuristic methods: SEAL is compared with eight heuristics, an ensemble classifier, WLK, and WLNM using only graph-structure features.The comparison includes both predefined scores and methods that learn from enclosing subgraphs.
  • Comparison to heuristic methods: The experiments select h from {1, 2}, because performance typically does not increase for h ≥3 while larger enclosing subgraphs can become expensive.The selection rule uses validation performance between AA and CN to choose h = 1 or h = 2.
  • Comparison to heuristic methods: Methods learning from enclosing subgraphs generally outperform predefined heuristics, and SEAL performs best among the learning-based methods.The results attribute this pattern to learned heuristics capturing network properties more effectively and to GNN-based graph feature learning.
  • Comparison to latent feature methods: SEAL shows significant improvement over latent feature methods, while combining SEAL with node2vec does not always improve performance over SEAL without embeddings.SEAL with node2vec embeddings outperforms pure node2vec by large margins.

6 Conclusions

The paper justifies learning link-prediction heuristics from local enclosing subgraphs and introduces SEAL, a GNN framework that combines structural and feature information. Experiments report strong performance against heuristic, latent-feature, and network-embedding methods.

  • Conclusions: The paper presents a γ-decaying theory that unifies many high-order heuristics and proves their approximation from local enclosing subgraphs.The theory provides the theoretical justification for learning link-prediction heuristics locally.
  • Conclusions: SEAL uses graph neural networks to learn simultaneously from local enclosing subgraphs, embeddings, and node attributes.The framework is motivated by the theoretical results on local approximation.
  • Conclusions: Experiments report unprecedentedly strong SEAL performance against heuristics, latent feature methods, and network embedding algorithms.The conclusion frames these comparisons as empirical support for the framework.
  • Conclusions: The authors suggest that SEAL may inspire link-prediction research and other relational machine-learning problems such as knowledge-graph completion and recommender systems.

A More about the three types of features for link prediction

The paper distinguishes graph structure, latent, and explicit features by where their information comes from and how it is learned. These feature types are described as largely orthogonal and potentially complementary.

  • Graph structure features: Graph structure features are computed directly from observed nodes and edges, and link-prediction heuristics are predefined examples.Other examples include centrality scores, graphlets, and network motifs.
  • Graph structure features: Graph structure features are inductive and transferable to new nodes and networks because they are not tied to particular identities.Common-neighbor scores use the same structural rule for any node pair.
  • Latent features: Latent features are low-dimensional node representations learned by factorizing network-derived matrices, emphasizing global properties and long-range effects.Network embedding methods can be viewed as learning expressive latent features through matrix factorization.
  • Explicit features: Explicit features consist of continuous or discrete node attributes or other network side information unrelated to structure.Examples include word distributions in citation networks and user profiles in social networks.
  • Feature types: Graph structure, latent, and explicit features are largely orthogonal, motivating methods that combine them to improve single-feature approaches.

B More discussion about node labeling

SEAL’s double-radius node labeling distinguishes target nodes and encodes each node’s relative position within an enclosing subgraph. Label magnitudes additionally preserve distance information useful for GNN input.

  • Labeling criteria: Node labels distinguish the target nodes and encode other nodes’ relative positions using their distance pair (d(i, x), d(i, y)).This structural information facilitates GNN training on enclosing subgraphs.
  • Double-Radius Node Labeling: DRNL assigns label 1 to the target nodes and progressively larger labels to nodes grouped by increasing double-radius combinations.Examples include (1, 1) → 2, (1, 2)/(2, 1) → 3, and (2, 2) → 5.
  • Double-Radius Node Labeling: DRNL orders labels first by the sum of distances to the target nodes and then by the product when sums are equal.Thus, smaller arithmetic and geometric mean distances correspond to smaller labels.
  • Label information: Unlike one-hot encoding, DRNL retains magnitude information about a node’s distance to the enclosing-subgraph center.The labels are encoded into node information matrices for machine-learning models.
  • Distance computation: When computing a node’s distance to one target, DRNL temporarily removes the other target to avoid obscuring the pure distance.Otherwise, the distance can be bounded by a path through the other target.
  • Comparison with WLNM: DRNL differs from WLNM labeling because SEAL uses labels to indicate structural roles, whereas WLNM uses them to define adjacency-matrix node order.

C Dataset details

The experiments use several network datasets, including airline, collaboration, political-blog, and yeast protein-protein interaction networks, with reported sizes and average degrees.

  • USAir contains 332 nodes and 2,126 edges, with an average node degree of 12.81.
  • NS contains 1,589 nodes and 2,742 edges, with an average node degree of 3.45.
  • PB contains 1,222 nodes and 16,714 edges, with an average node degree of 27.36.
  • Yeast contains 2,375 nodes and 11,693 edges, with an average node degree of 9.85.

D Additional details about baselines

The additional baseline details describe WLNM, graph-kernel comparisons, and SEAL’s DGCNN-based architecture and training setup, including removal of the target edge from positive training subgraphs.

  • WLNM baseline: WLNM extracts enclosing subgraphs, encodes node order with the Weisfeiler-Lehman algorithm, truncates them to size K, and feeds adjacency matrices to a fully connected network.
  • Graph-kernel baseline: WLK compares graphs by counting common rooted subtrees and uses the same enclosing subgraphs as SEAL.
  • SEAL architecture: SEAL uses DGCNN as its default GNN engine, combining propagation-based graph convolution with SortPooling for graph-level representation.
  • SEAL architecture: DGCNN stacks graph convolution layers and concatenates layer states to extract multi-hop node features before graph aggregation.
  • Training protocol: Positive training subgraphs remove the target-node edge because testing subgraphs do not contain link-existence information through that edge.

F Additional results

Additional experiments report SEAL’s performance across average precision, AUC, sparsity, scalability, and embedding comparisons. SEAL generally outperforms the evaluated baselines, including under incomplete-network settings.

  • 90%–10% split: SEAL shows great performance improvement over heuristic and latent-feature baselines in both AUC and AP under the 90%–10% split.
  • Scalability: SEAL’s single-GPU inference handles over 1E7 potential links in less than an hour.
  • 50%–50% split: Under the sparser setting, VGAE achieves the best AUC on 3 out of 8 datasets and becomes a strong baseline.
  • Embedding comparison: On five networks evaluated under the node2vec setting, SEAL consistently outperforms all embedding methods and WLNM.
Loading 1802.09691v3…