Statistical and Computational Rates in Graph Logistic Regression

Quentin Berthet, Nicolai BaldinAISTATS 2020 · OpenReview

Abstract

We consider the problem of graph logistic regression, based on partial observation of a large network, and on side information associated to its vertices. The generative model is formulated as a matrix logistic regression where the probability of an edge depends on node features and an unknown parameter matrix. We analyze the statistical and computational trade-offs in estimating this matrix under sparsity and low-rank constraints.

Introduction

In network analysis, link prediction typically involves predicting connections based on existing graph structure. However, real-world networks often provide "side information"—features like user interests or protein properties. This paper investigates supervised link prediction, where node features $X_i$ and $X_j$ are used to estimate the underlying mechanism of connection. The authors model this as a high-dimensional matrix logistic regression. Given that the number of features $d$ often exceeds the number of observed edges $N$, estimation requires structural assumptions like sparsity and low-rankness. A critical question arises: can the optimal estimator be computed efficiently?

Model and Methods

The problem is formulated as a Matrix Logistic Regression. The probability of an edge between nodes $i$ and $j$ is modeled using the sigmoid of a quadratic form:

$$P(Y_{(i,j)} = 1) = \sigma(X_i^\top \Theta X_j)$$

where $\Theta$ is the unknown parameter matrix. The authors assume $\Theta$ is $k$-sparse and low-rank.

Structure of the parameter matrix $\Theta$ with sparsity $k$ and dimension $d$.

Two primary approaches are analyzed:

  1. Penalized Maximum Likelihood Estimator (MLE): A theoretically optimal but computationally intractable (NP-hard) estimator that searches for the best sparse, low-rank matrix.
  2. Convex Relaxation (Lasso): A computationally efficient approach using an $\ell_1$ penalty to encourage sparsity, which is shown to be statistically sub-optimal.

The authors introduce the Block Isometry Property (BIP), a variant of the Restricted Isometry Property (RIP) for matrices, ensuring that node features are sufficiently well-behaved to allow recovery of $\Theta$.

Statistical vs. Computational Rates

The core contribution of this work is identifying a fundamental "computational gap" in error rates. This gap represents a region where estimation is theoretically possible but computationally hard for any polynomial-time algorithm.

The computational gap between the minimax rate, the computational lower bound, and the Lasso rate.
  • Statistical Minimax Rate: The theoretical lower bound on error is $O\left(\frac{kr}{N} + \frac{k}{N} \log(\frac{de}{k})\right)$. This is the "gold standard" for accuracy if computation time were infinite.
  • Computational Lower Bound: Using a reduction to the Dense Subgraph Detection problem, the authors prove that any polynomial-time algorithm must accept an error rate of at least $O(k^2/N)$.
  • Lasso Performance: The standard Lasso achieves $O(\frac{k^2}{N} \log d)$, which is near the computational limit but significantly worse than the minimax rate when the rank $r$ is small.

Conclusion

This paper demonstrates that while low-rank structures are theoretically powerful, they are computationally hard to exploit in the context of graph logistic regression with side information. The gap between what is statistically possible and what is computationally feasible suggests that practitioners using standard tools like the Lasso are inherently limited by this trade-off. Future work may explore whether more complex convex relaxations can bridge this gap for higher-rank matrices.

Summary updated

Abstract

We consider the problem of graph logistic regression, based on partial observation of a large network, and on side information associated to its vertices. The generative model is formulated as a ma...
BibTeX
@inproceedings{berthet2020statistical,
  author = {Quentin Berthet and Nicolai Baldin},
  title = {{Statistical and Computational Rates in Graph Logistic Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=3knVdlTP3A4},
}
Figure