Consistent Nonparametric Methods for Network Assisted Covariate Estimation

Xueyu Mao, Deepayan Chakrabarti, Purnamrita SarkarICML 2021

Overview

This paper introduces CN-VEC (Common Neighbor - Vectorized Estimation of Covariates), a novel local algorithm designed to predict missing node features (covariates) in a network by analyzing two-hop neighborhoods. It stands out as the first local method to provide provable consistency guarantees for sparse networks. Furthermore, it operates 10x to 100x faster than popular embedding-based methods like node2vec, all while maintaining superior or comparable predictive accuracy.

The Challenge of Missing Covariates in Sparse Networks

In many real-world networks—such as social media platforms, e-commerce sites, or citation graphs—we often know the "covariates" (e.g., interests, demographics, or topic preferences) for a subset of nodes, but lack this information for others. The objective is to leverage the network's underlying structure to infer these missing values.

The primary hurdle is sparsity. In a sparse network, two users with identical latent interests might not be directly connected, nor might they even share a single common neighbor. Simple heuristics, like averaging the features of a node's immediate neighbors, frequently fail because those neighbors might not actually be the most similar nodes in the latent space. While global methods (like graph embeddings) can capture broader structures, they often lack theoretical "consistency" guarantees—meaning there is no mathematical proof that predictions will converge to the true values as the network grows. Additionally, these global methods are computationally expensive.

Proposed Methods

The authors propose two primary algorithms to tackle this problem:

  1. CN-VEC (Common Neighbor - Vectorized Estimation of Covariates): This is a model-agnostic, local algorithm. Its core innovation is a new similarity statistic ($K_{ij}$) that compares the 2-hop neighborhoods of two nodes. Unlike a simple count of common neighbors, this formula includes specific correction terms that allow the measure to "concentrate" (become statistically stable) even in very sparse graphs. Once similarities are calculated, the algorithm performs $k$-nearest neighbor regression to predict missing values.
  2. SVD-RBF: A global method designed for "low-rank" latent variable models (like the Stochastic Blockmodel). It uses Singular Value Decomposition (SVD) to estimate the latent positions of nodes and then applies a Radial Basis Function (RBF) kernel for non-parametric regression.

The Theoretical Breakthrough: Most previous similarity measures only provide consistency guarantees for dense networks (where the average degree grows very quickly). CN-VEC is provably consistent even when the average degree grows as slowly as $n^{1/3}$ (where $n$ is the number of nodes).

Key Insights

  • Local Signal is Powerful: You don't necessarily need to process the entire graph to make accurate predictions. By carefully constructing a similarity measure based on 2-hop neighborhoods, CN-VEC captures enough signal to match or beat global embedding methods.
  • The Concentration Trick: The mathematical "aha moment" is the construction of the $K_{ij}$ statistic. In sparse graphs, the number of common neighbors between two nodes is often zero or one, which is too noisy for prediction. By looking at the patterns of common neighbors across the entire network and applying specific subtractions, the authors created a metric that accurately reflects latent distances even when edges are rare.
  • Efficiency vs. Complexity: While node embeddings (like node2vec) are popular, they are often computationally heavy "black boxes" without convergence guarantees. CN-VEC provides a mathematically grounded alternative that is significantly lighter on computational resources.

Experimental Results

The researchers evaluated their methods using both synthetic models (Latent Space Model, Stochastic Blockmodel, etc.) and real-world datasets (Cora, CiteSeer, and a Weibo-derived social network called Sinanet).

Superior Speed

CN-VEC is exceptionally fast, running 10x to 100x faster than baseline embedding methods like node2vec and NOBE. This efficiency makes it highly scalable and feasible for massive real-world networks.

Running time comparison showing CN-VEC's superior speed

Robust Accuracy

In both simulations and real-world applications, CN-VEC consistently achieved the lowest Root Mean Square Error (RMSE) for recovering hidden topic distributions. It outperformed almost all other local and global methods across various graph models and missing data fractions.

RMSE comparison across different fractions of unknown covariates

Limitations and Future Work

  • Sparsity Floor: While the method works well for sparse graphs, it still requires the average degree to grow at a certain rate ($n^{1/3}$). It may struggle in "ultra-sparse" graphs where the degree remains constant regardless of network size.
  • Hyperparameter Tuning: The algorithm requires choosing $k$ (the number of neighbors for regression). While the authors suggest $k = O(\log n)$ and demonstrate a "sweet spot" in their experiments, practical application still requires cross-validation.
  • Undirected Assumption: The current similarity measure is formulated for undirected graphs. Developing a dedicated version for directed or weighted graphs represents a valuable future extension.

Summary updated

BibTeX
@inproceedings{mao2021consistent,
  author = {Xueyu Mao and Deepayan Chakrabarti and Purnamrita Sarkar},
  title = {{Consistent Nonparametric Methods for Network Assisted Covariate Estimation}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
}
Figure