DINE: A Framework for Deep Incomplete Network Embedding

Ke Hou, Jiaying Liu, Yin Peng, Bo Xu, Ivan Lee, Feng Xia

Abstract

Network representation learning (NRL) plays a vital role in a variety of tasks such as node classification and link prediction. It aims to learn low-dimensional vector representations for nodes based on network structures or node attributes. While embedding techniques on complete networks have been intensively studied, in real-world applications, it is still a challenging task to collect complete networks. To bridge the gap, in this paper, we propose a Deep Incomplete Network Embedding method, namely DINE. Specifically, we first complete the missing part including both nodes and edges in a partially observable network by using the expectation-maximization framework. To improve the embedding performance, we consider both network structures and node attributes to learn node representations. Empirically, we evaluate DINE over three networks on multi-label classification and link prediction tasks. The results demonstrate the superiority of our proposed approach compared against state-of-the-art baselines.

Introduction

Network Representation Learning (NRL) has become a cornerstone for downstream tasks like node classification and link prediction. However, most existing NRL algorithms, such as Node2vec or DeepWalk, operate under the assumption that the input network is "complete." In practice, networks are rarely complete; academic citation networks may miss papers (missing nodes), and biological datasets often lack undiscovered protein interactions (missing edges).

Analyzing these "incomplete" networks leads to biased statistics and poor embedding quality. While some research has addressed missing links, this paper tackles the more complex problem of incomplete networks where both nodes and edges are missing. DINE addresses this by combining generative network completion with a multi-view deep autoencoder.

The DINE Framework

The DINE framework is structured into two pivotal stages: network recovery and recovered network embedding.

The DINE framework overview: from incomplete network to node representation.

1. Network Recovery Phase

To handle missing components, DINE utilizes the Kronecker graphs model within an Expectation-Maximization (EM) framework, specifically the KronEM algorithm. This phase iteratively samples the missing parts of the network and node permutations (E-step) and optimizes model parameters to maximize the likelihood of the observed and sampled data (M-step). This generative process produces a "recovered" network that approximates the connectivity patterns of the original, unobserved graph.

2. Multi-View Embedding (MVC-DNER)

Once the network is recovered, DINE employs a specialized deep autoencoder called MVC-DNER (Multi-View Deep Network Embedding for Recovered networks). This model processes two distinct inputs: the network structure (adjacency matrix) and node attributes.

Architecture of the MVC-DNER model showing cross-view reconstruction.

A key innovation in MVC-DNER is the cross-view reconstruction mechanism. Unlike standard autoencoders that reconstruct their own input, this model uses the latent representation of the structural view to help reconstruct the attribute view, and vice versa. This ensures the final embedding captures the deep correlation between a node's connectivity and its intrinsic attributes, making the representation more robust to noise introduced during the recovery phase.

Experimental Evaluation

The authors evaluated DINE on three benchmark datasets: Citeseer, DBLP, and BlogCatalog. Incompleteness was simulated by removing 5% to 30% of the nodes and their associated edges.

Key Results

  • Multi-label Classification: On the Citeseer dataset with 5% missing nodes, DINE achieved a Macro-F1 score of 0.642, significantly outperforming Node2vec (0.431).
  • Link Prediction: DINE showed superior AUC (Area Under Curve) across all datasets. Notably, DINE's performance remained relatively stable even as the fraction of missing nodes increased to 30%, whereas traditional methods saw sharp declines.
  • Robustness: The results indicate that integrating node attributes with structure is critical when the network topology is unreliable or incomplete.

Conclusion and Future Work

DINE demonstrates that missing nodes are a fundamental challenge because their absence alters the global topology. By using generative models as a pre-processor and employing cross-view fusion, DINE provides a stable foundation for embedding incomplete data.

Future research directions include extending the framework to heterogeneous networks (containing multiple types of nodes and edges) and optimizing the computational complexity of the EM-based recovery to scale for massive, billion-node graphs.

Summary updated

Abstract

Network representation learning (NRL) plays a vital role in a variety of tasks such as node classification and link prediction. It aims to learn low-dimensional vector representations for nodes based on network structures or node attributes. While embedding techniques on complete networks have been intensively studied, in real-world applications, it is still a challenging task to collect complete networks. To bridge the gap, in this paper, we propose a Deep Incomplete Network Embedding method, namely DINE. Specifically, we first complete the missing part including both nodes and edges in a partially observable network by using the expectation-maximization framework. To improve the embedding performance, we consider both network structures and node attributes to learn node representations. Empirically, we evaluate DINE over three networks on multi-label classification and link prediction tasks. The results demonstrate the superiority of our proposed approach compared against state-of-the-art baselines.
BibTeX
@inproceedings{hou2019dine,
  author = {Ke Hou and Jiaying Liu and Yin Peng and Bo Xu and Ivan Lee and Feng Xia},
  title = {{DINE: A Framework for Deep Incomplete Network Embedding}},
  booktitle = {Australasian Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=enMRZuFibQ},
}
Figure