DINE: A Framework for Deep Incomplete Network Embedding

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

TL;DR

DINE is a novel framework designed to learn high-quality node representations from "partially observable" networks where both nodes and edges are missing. By combining a generative network completion step (using Expectation-Maximization) with a multi-view deep autoencoder that fuses topology and node attributes, DINE significantly outperforms traditional embedding methods on incomplete data.

What Problem Does This Paper Address?

Network Representation Learning (NRL) has become a cornerstone for tasks like node classification and link prediction. However, most existing NRL algorithms (like Node2vec or DeepWalk) assume the input network is "complete."

In the real world, networks are rarely complete. Academic search engines might miss papers (missing nodes), and biological datasets often have 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 much harder problem of incomplete networks with both missing nodes and missing edges.

Methods

The DINE framework consists of two pivotal stages:

  1. Network Recovery (The "Completion" Phase): The authors use the Kronecker graphs model within an Expectation-Maximization (EM) framework (specifically an algorithm called KronEM).

  2. E-step: Samples the missing part of the network and node permutations based on the observed graph and current model parameters.

  3. M-step: Optimizes the model parameters to maximize the likelihood of the observed and sampled data. This iterative process generates a "recovered" network that mimics the connectivity patterns of the original, partially observed graph.

  4. Recovered Network Embedding (The "MVC-DNER" Phase): Once the network is recovered, DINE uses a specialized deep autoencoder called MVC-DNER (Multi-View Deep Network Embedding for Recovered networks).

  5. Two Views: It processes two distinct inputs: the network structure (adjacency matrix) and node attributes.

  6. Cross-View Reconstruction: Unlike standard autoencoders, this model uses a "cross-view" approach where the latent representation of the structure view helps reconstruct the attribute view, and vice versa. This ensures the final embedding captures the deep correlation between how a node connects and what a node contains.

Datasets

The authors evaluated DINE on three widely used benchmarks, simulating incompleteness by removing 5% to 30% of the nodes and their associated edges:

  • Citeseer: A citation network (3,312 papers, 6 classes) with 3,703-dimensional attribute vectors.
  • DBLP: A larger citation dataset (8,192 papers, 10 domains) with 9,662-dimensional attribute vectors.
  • BlogCatalog: A social network (4,096 nodes, 39 groups) where node attributes represent blogger interests.

Key Insights and Ideas

  • Nodes Matter More Than Edges: Most prior work focuses on link prediction. DINE highlights that missing nodes are a fundamental challenge because their absence fundamentally alters the network's global topology.
  • Generative Models as a Pre-processor: By using a generative model (Kronecker graphs) to "fill in the blanks" before embedding, the model provides a more stable foundation for deep learning than simply treating missing values as zeros.
  • The Power of Multi-View Fusion: The "aha moment" here is the cross-view reconstruction. By forcing the structural embedding to predict attributes (and vice versa), the model learns a joint space that is more robust to the noise introduced during the recovery phase.

Key Results

DINE was compared against state-of-the-art baselines including GF, HOPE, Node2vec, and SDNE.

  • Multi-label Classification: On the Citeseer dataset with 5% missing nodes, DINE achieved a Macro-F1 score of 0.642, vastly outperforming the next best baseline, Node2vec (0.431).
  • Link Prediction: DINE showed significant improvements in AUC (Area Under Curve) across all datasets. Even as the fraction of missing nodes increased to 30%, DINE's performance remained relatively stable compared to the sharp declines seen in traditional methods.
  • Robustness: The results demonstrate that considering node attributes alongside structure is critical when the structure itself is unreliable or incomplete.

Limitations and Future Work

  • Known Missing Count: The current framework assumes the number of missing nodes is known beforehand. While the authors suggest statistical methods to estimate this, it remains a dependency.
  • Homogeneous Networks: DINE is currently designed for networks with a single type of node and edge. The authors explicitly mention that extending the framework to heterogeneous networks (e.g., networks with different types of entities like authors, papers, and venues) is a primary direction for future research.
  • Computational Complexity: The EM-based recovery and deep autoencoder training are computationally intensive, which might pose challenges for scaling to 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},
}

Loading related content...

Figure