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 is a cornerstone of graph analytics, typically handled in a transductive setting where all nodes are present during training. However, real-world scenarios—such as a recommender system greeting a new user—often present an inductive challenge: predicting links for new, "unseen" nodes that possess attribute data but lack any initial structural connections.
Existing solutions like GraphSage still require some initial edges to function, while others rely too heavily on attributes and fail to capture the underlying graph structure effectively. The gap is clear: how do we build a model that understands the relationship between what a node is (attributes) and where it belongs (structure)?
The DEAL Framework
To address this, the authors introduce DEAL (Dual-Encoder graph embedding with ALignment). The core philosophy is to learn a mapping from the attribute space to the structural space.
- Dual Encoders: DEAL employs two distinct encoders. The Structure-oriented Encoder ($H_s$) learns representations based purely on graph topology using node IDs. The Attribute-oriented Encoder ($H_a$) uses a Multilayer Perceptron (MLP) to map raw attributes into an embedding space.
- Alignment Mechanism: The innovation lies in aligning these two spaces. By forcing the attribute-based embeddings to approximate the structural embeddings, the model enables the attribute encoder to "predict" where a node belongs in the graph even if its structural context is missing.
- Loose Alignment (L-align): Rather than a strict one-to-one mapping, DEAL utilizes a "loose" alignment strategy. It maximizes the similarity between a node's attribute embedding and the structural embeddings of its neighbors, providing better generalization than "tight" alignment.
The model is trained using a ranking-motivated loss function that includes a specialized weight function. This function gives more importance to "hard" negative samples—nodes that are close in the graph but not actually connected—forcing the model to learn finer distinctions.
Experimental Evaluation
The model was evaluated on seven diverse, real-world datasets, including citation networks (Cora, CiteSeer, PubMed), co-authorship graphs (CS), and co-purchase graphs (Amazon Computers and Photo).
Key Results
DEAL demonstrates superior performance in both inductive and transductive settings. In inductive tasks, it significantly outperforms baselines like G2G and MLP. On the "Computers" dataset, it improved the Average Precision (AP) score by nearly 18% over the next best baseline.
Interestingly, the authors found that simple MLPs often outperform GCNs for the attribute encoder in inductive settings. GCNs rely on neighbor aggregation, which can lead to "over-smoothing" and a loss of the fine-grained attribute signals necessary for distinguishing new nodes at inference time.
Conclusion
DEAL provides a robust solution for the cold-start problem in link prediction. By aligning attribute and structural embeddings, it effectively transfers structural knowledge to an attribute-only encoder. Its versatility across inductive and transductive tasks, combined with its ability to outperform state-of-the-art models like SEAL and GAE, makes it a powerful tool for modern graph-based applications. Future work will focus on scaling the model to billion-node graphs and adapting it for dynamic, evolving structures.
Summary updated