Inductive Link Prediction for Nodes Having Only Attribute Information

Yu Hao, Xin Cao, Yixiang Fang, Xike Xie, Sibo Wang

Abstract

Predicting the link between two nodes is a fundamental problem for graph data analytics. In attributed graphs, both the structure and attribute information can be utilized for link prediction. Most existing studies focus on transductive link prediction where both nodes are already in the graph. However, many real-world applications require inductive prediction for new nodes having only attribute information. It is more challenging since the new nodes do not have structure information and cannot be seen during the model training. To solve this problem, we propose a model called DEAL, which consists of three components: two node embedding encoders and one alignment mechanism. The two encoders aim to output the attribute-oriented node embedding and the structure-oriented node embedding, and the alignment mechanism aligns the two types of embeddings to build the connections between the attributes and links. Our model DEAL is versatile in the sense that it works for both inductive and transductive link prediction. Extensive experiments on several benchmark datasets show that our proposed model significantly outperforms existing inductive link prediction methods, and also outperforms the state-of-the-art methods on transductive link prediction.

Introduction: The Challenge of Unseen Nodes

Link prediction—the task of estimating the likelihood of a connection between two nodes—is a cornerstone of modern graph analytics, powering recommendation engines, social network suggestions, and biological network analysis. Traditionally, this problem is approached in a transductive setting, where all nodes are present in the graph during training.

However, real-world scenarios often demand inductive capabilities. Consider a new user joining a social network: they have profile attributes (interests, location) but no existing connections. Predicting their likely friends is difficult because standard graph models rely heavily on existing structural topology. Most current inductive methods still require a few "starter" edges to function. The DEAL framework addresses the most restrictive and challenging case: predicting links for "unseen" nodes that possess only attribute information.

Illustration of transductive vs. inductive link prediction. Inductive prediction involves "unseen" nodes (red) that lack initial structural connections.

The DEAL Framework

To bridge the gap between raw attributes and graph structure, the researchers developed DEAL (Dual-Encoder graph embedding with ALignment). The architecture is built on three pillars:

1. Dual Encoders

DEAL utilizes two distinct encoders to capture different facets of the graph:

  • Attribute-oriented Encoder ($H_a$): A multilayer perceptron (MLP) that maps node attributes into an embedding space. Unlike Graph Convolutional Networks (GCNs), which can "over-smooth" data by aggregating neighbor information, the MLP preserves the unique signature of a node's attributes.
  • Structure-oriented Encoder ($H_s$): A linear model that learns embeddings based purely on the graph's topology using node identifiers.

2. Alignment Mechanism

The core innovation of DEAL is the alignment of these two encoders. During training, the model forces the embeddings from $H_a$ and $H_s$ to converge. This process essentially "teaches" the attribute encoder how to translate specific attribute patterns into their corresponding structural positions. The authors found that Loose Alignment—matching embeddings for linked pairs—provided the best balance of flexibility and predictive power.

3. Ranking-Motivated Loss

Rather than treating link prediction as a simple binary classification, DEAL employs a generalized logistic loss with a specialized weight function. This function prioritizes "hard" negative samples—nodes that are structurally close but not connected—forcing the model to learn the fine-grained boundaries of the network topology.

The DEAL framework overview, showing the dual-encoder architecture and the alignment process between attribute and structure embeddings.

Experimental Results

DEAL was evaluated against seven real-world datasets, including citation networks (Cora, PubMed) and co-purchase graphs (Amazon Computers/Photo).

  • Inductive Performance: DEAL significantly outperformed existing inductive baselines like G2G. On the "Computers" dataset, it achieved an 18% improvement in Average Precision (AP) over the next best method.
  • Transductive Versatility: Despite its inductive focus, DEAL also surpassed state-of-the-art transductive models (e.g., SEAL, GAE), demonstrating its robustness as a general-purpose link prediction tool.
  • Attribute Sparsity: The model remained effective even on datasets like PPI, where attributes are sparse, proving the strength of the alignment mechanism in extracting structural signals from limited data.

Conclusion

DEAL represents a significant step forward in graph representation learning by effectively using graph structure as a "teacher" for attribute-based embeddings. By aligning these two information sources, DEAL enables accurate link prediction for entirely new nodes, a critical requirement for dynamic, real-world networks. Future work will focus on scaling these mechanisms to massive graphs with billions of nodes.

Summary updated

Abstract

Predicting the link between two nodes is a fundamental problem for graph data analytics. In attributed graphs, both the structure and attribute information can be utilized for link prediction. Most existing studies focus on transductive link prediction where both nodes are already in the graph. However, many real-world applications require inductive prediction for new nodes having only attribute information. It is more challenging since the new nodes do not have structure information and cannot be seen during the model training. To solve this problem, we propose a model called DEAL, which consists of three components: two node embedding encoders and one alignment mechanism. The two encoders aim to output the attribute-oriented node embedding and the structure-oriented node embedding, and the alignment mechanism aligns the two types of embeddings to build the connections between the attributes and links. Our model DEAL is versatile in the sense that it works for both inductive and transductive link prediction. Extensive experiments on several benchmark datasets show that our proposed model significantly outperforms existing inductive link prediction methods, and also outperforms the state-of-the-art methods on transductive link prediction.
BibTeX
@inproceedings{hao2020inductive,
  author = {Yu Hao and Xin Cao and Yixiang Fang and Xike Xie and Sibo Wang},
  title = {{Inductive Link Prediction for Nodes Having Only Attribute Information}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=CoKscvVmgm},
}
Figure