Semi-supervisedly Co-embedding Attributed Networks

Zaiqiao Meng, Shangsong Liang, Jinyuan Fang, Teng Xiao

Introduction

The SCAN (Semi-supervised Co-embedding Attributed Network) model bridges the gap between network structure and node attributes by embedding both into a shared semantic space. By extending Variational Auto-encoders (VAEs) to handle heterogeneous data and partial labels, SCAN captures not only how nodes relate to each other, but also how they relate to their specific features—all while accounting for representation uncertainty.

The Challenge with Attributed Networks

Most real-world networks are "attributed." This means nodes aren't just dots on a map; they come with rich, unstructured information. For example, a social media user has specific interests, and a research paper has keywords. However, traditional network embedding methods often face three major hurdles when dealing with this data:

  1. Node-Centric Bias: Traditional models typically only learn representations for nodes. This makes it difficult to directly measure the affinity between a node and an attribute (e.g., answering "How likely is this user to be interested in 'Machine Learning'?").
  2. Label Scarcity: In the real world, only a tiny fraction of nodes are labeled. Existing models often struggle to generalize effectively from these small labeled sets to the vast unlabeled majority.
  3. Overconfidence: Most models represent a node as a single, fixed point in space. This ignores the inherent uncertainty of the data; we might be very sure about a highly active user's interests but very unsure about a "lurker."

Methods: The SCAN Framework

To address these limitations, the authors introduce SCAN, a framework built on a generalized Semi-supervised Variational Auto-encoder (SVAE).

Architecture of the SCAN model showing inference and generative networks across five reconstruction cases.

Key technical highlights of the SCAN architecture include:

  • Heterogeneous Co-embedding: Unlike standard VAEs that handle one type of data, SCAN is designed for triples (entities, relationships, and labels). It maps both nodes and attributes into the same low-dimensional space as Gaussian distributions (parameterized by mean and variance).
  • Five-Case ELBO: To handle partially labeled data, the authors decompose the network's Evidence Lower Bound (ELBO) into five atomic cases. As shown in the architecture diagram, these cover every possible interaction: edges between two labeled nodes, two unlabeled nodes, or a mix, as well as attribute associations for both labeled and unlabeled nodes.
  • The Gumbel-Softmax Trick: For unlabeled nodes, the model must "guess" a label. Since standard sampling from a categorical distribution isn't differentiable (preventing backpropagation through a random choice), SCAN uses the Gumbel-Softmax trick to create a continuous, differentiable approximation.
  • Joint Optimization: The model simultaneously trains an inference network (to find embeddings), a generative network (to reconstruct the network), and a discriminative network (to predict labels).

Key Insights and Ideas

  • Shared Semantic Space: By forcing nodes and attributes into the same space, the model allows for "zero-shot" style reasoning. You can calculate the cosine similarity between a node vector and an attribute vector to perform user profiling or tag recommendation directly.
  • Uncertainty as Information: By representing embeddings as Gaussian distributions, the variance acts as a measure of "confidence." Nodes with sparse connections or few attributes naturally exhibit higher variance, preventing the model from making overconfident, incorrect predictions.
  • Collaborative Regularization: The semi-supervised labels don't just help classify nodes; they act as a guide for the entire embedding space, ensuring that the latent representations of attributes also align with the underlying class structures.

Key Results

The model was evaluated on three widely used real-world attributed networks: Pubmed (citation network), Flickr (social image network), and BlogCatalog (social blog directory). SCAN consistently outperformed state-of-the-art baselines like Graph Convolutional Networks (GCN) and SEANO across multiple tasks:

  • Node Classification: On the BlogCatalog dataset, SCAN achieved a Macro-F1 score of 0.829, significantly higher than GCN's 0.509. This highlights SCAN's superior ability to handle networks where the relationship between structure and attributes is complex.
  • Attribute Inference: SCAN showed a marked improvement in predicting missing attributes. In Pubmed, it achieved an AUC of 0.713, compared to the next best model (CAN) at 0.670.
  • Visualization: Using t-SNE to project the 64-dimensional embeddings into 2D, the authors demonstrated that SCAN produces much tighter, more distinct clusters of nodes compared to other methods. This proves that the learned space is semantically meaningful.
t-SNE visualization comparing node embeddings of GCN, SEANO, Planetoid-T, and SCAN.

Limitations and Future Work

While SCAN is a powerful framework, the authors note a few areas for future growth:

  • Computational Complexity: Marginalizing over all possible classes for unlabeled data can be computationally expensive if the number of classes is very large, though the Gumbel-Softmax trick helps mitigate this.
  • Static Nature: The current model is designed for static networks. Extending SCAN to dynamic attributed networks—where connections and attributes change over time—is a promising future direction.
  • Entity Diversity: The model currently focuses on two entity types (nodes and attributes). Expanding this to more complex "knowledge graph" architectures with many different entity and relation types would be a logical next step.

Summary updated

Abstract

Deep generative models (DGMs) have achieved remarkable advances. Semi-supervised variational auto-encoders (SVAE) as a classical DGM offers a principled framework to effective generalize from small labelled data to large unlabelled ones, but it is difficult to incorporate rich unstructured relationships within the multiple heterogeneous entities. In this paper, to deal with the problem, we present a semi-supervised co-embedding model for attributed networks (SCAN) based on the generalized SVAE for the heterogeneous data, which collaboratively learns low- dimensional vector representations of both nodes and attributes for partially labelled attributed networks semi-supervisedly. The node and attribute embeddings obtained in a unified manner by our SCAN can benefit not only for capturing the proximities between nodes but also the affinities between nodes and attributes. Moreover, our model also trains a discriminative network to learn the label predictive distribution of nodes. Experimental results on real-world networks demonstrate that our model yields excellent performance in a number of applications such as attribute inference, user profiling and node classification compared to the state-of-the-art baselines.
BibTeX
@inproceedings{meng2019semi,
  author = {Zaiqiao Meng and Shangsong Liang and Jinyuan Fang and Teng Xiao},
  title = {{Semi-supervisedly Co-embedding Attributed Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=8PAC_Wa-nr},
}
Figure