Abstract. We consider the problem of link prediction, 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. The performance of the model is analysed in a highdimensional regime under a structural assumption. The minimax rate for the Frobenius-norm risk is established and a combinatorial estimator based on the penalised maximum likelihood approach is shown to achieve it. Furthermore, it is shown that this rate cannot be attained by any (randomised) algorithm computable in polynomial time under a computational complexity assumption. Primary 62J02, 62C20; secondary 68Q17. Key words and phrases: Link prediction, Logistic regression, Computational lower bounds, Planted clique. In the field of network analysis, the task of link prediction consists in predicting the presence or absence of edges in a large graph, based on the observations of some of its edges, and on side information. Network analysis has become a growing inspiration for statistical problems. Indeed, one of the main characteristics of datasets in the modern scientific landscape is not only their growing size, but also their increasing complexity. Most phenomena now studied in the natural and social sciences concern not only isolated and independent variables, but also their interactions and connections. The fundamental problem of link prediction is therefore naturally linked with statistical estimation: the objective is to understand, through a generative model, why different vertices are connected or not, and to generalise these observations to the rest of the graph. Most statistical problems based on graphs are unsupervised: the graph itself is the sole data, there is no side information, and the objective is to recover an unknown structure in the generative model. Examples include the planted clique problem Kučera, 1995), the stochastic block model (Holland et al., 1983)-see Abbe (2017) for a recent survey of a very active line of work (Abbe and Sandon, 2015; Banks et al., 2016; Decelle et al., 2011 Massoulié, 2014; Mossel et al., 2013 Mossel et al., , 2015 , the Ising blockmodel , random geometric graphs -see Penrose (2003) for an introduction and (Bubeck et al., 2014; Devroye et al., 2011) for recent developments in statistics, or metric-based learning (Bellet et al., 2014; Chen et al., 2009 ) and ordinal embedings (Jain et al., 2016). In supervised regression problems on the other hand, the focus is on understanding a fundamental mechanism, formalized as the link between two variables. The objective is to learn how an explanatory variable X allows to predict a response Y , i.e. to find the unknown function f that best approximates the relationship Y ≈ f (X). This statistical framework is often applied to the observation of a phenomenon measured by Y (e.g. of a natural or social nature), given known information X: the principle is to understand said phenomenon, to explain the relationship between the variables by estimating the function f (Hoff et al., 2002; Holland and Leinhardt, 1981). We follow this approach here: our goal is to learn how known characteristics of each agent (represented by a node) in the network induce a greater or smaller chance of connection, to understand the mechanism of formation of the graph. We propose a model for supervised link prediction, using the principle of regression for inference on graphs. For each vertex, we are given side information, a vector of observations X ∈ R d . Given observations X i , X j about nodes i and j of a network, we aim to understand how these two explanatory variables are related to the probability of connection between the two corresponding vertices, such that P(Y (i,j) = 1) = f (X i , X j ), by estimating f within a high-dimensional class based on logistic regression. Besides this high-dimensional parametric modelling, various fully non-parametric statistical frameworks were exploited in the literature, see, for example, Gao et al. Link prediction can be useful in any application where data can be gathered about the nodes of a network. One of the most obvious motivations is in social networks, in order to model social interactions. With access to side information about each member of a social network, the objective is to understand the mechanisms of connection between members: shared interests, differences in artistic tastes or political opinion (Wasserman and Faust, 1994) . This can also be applied to citation networks, or in the natural sciences to biological networks of interactions between molecules or proteins (Madeira and Oliveira, 2004; Yu et al., 2008) . The key assumption in this model is that the network is a consequence of the information, but not necessarily based on similarity: it is possible to model more complex interactions, e.g. where opposites attract. The focus on a high-dimensional setting is another aspect of this work that is also motivated by modern applications of statistics: data is often collected without discernment and the ambient dimension d can be much larger than the sample size. This setting is common in regression problems: the underlying model is often actually very simple, to reflect the fact that only a small number of measured parameters are relevant to the problem at hand, and that the intrinsic dimension is much smaller. This is usually handled through an assumption on the rank, sparsity, or regularity of a parameter. Here this needs to be adapted to a model with two covariates (explanatory variables) and a structural assumption is made OPTIMAL LINK PREDICTION WITH MATRIX LOGISTIC REGRESSION 3 in order to reflect this nature of our problem. We therefore decide to tackle link prediction by modelling it as matrix logistic regression. We study a generative model for which P(Y (i,j) = 1) = σ(X ⊤ i Θ ⋆ X j ), where σ is the sigmoid function, and Θ ⋆ is the unknown matrix to estimate. It is a simple way to model how the variables interact, by a quadratic affinity function and a sigmoid function. In order to model realistic situations with partial observations, we assume that Y (i,j) is only observed for a subset of all the couples (i, j), denoted by Ω. To convey the general idea of a simple dependency on X i and X j , we make structural assumptions on the rank and sparsity of Θ ⋆ . This reflects that the affinity X ⊤ i Θ ⋆ X j is a function of the projections u ⊤ ℓ X for the vectors X i and X j , for a small number of orthogonal vectors, that have themselves a small number of non-zero coefficients (sparsity assumption). In order to impose that the inverse problem is well-posed, we also make a restricted conditioning assumption on Θ ⋆ , inspired by the restricted isometry property (RIP). These conditions are discussed in Section 1. We talk of link prediction as this is the legacy name but we focus almost entirely on the problem of estimating Θ ⋆ . The classical techniques of likelihood maximization can lead to computationally intractable optimization problems. We show that in this problem as well as others this is a fundamental difficulty, not a weakness of one particular estimation technique; statistical and computational complexities are intertwined. Our contribution: This work is organized in the following manner: We give a formal description of the problem in Section 1, as well as a discussion of our assumptions and links with related work. Section 2 collects our main statistical results. We propose an estimatorΘ based on the penalised maximum likelihood approach and analyse its performance in Section 2.1 in terms of non-asymptotic rate of estimation. We show that it attains the minimax rate of estimation over simultaneously block-sparse and low-rank matrices Θ ⋆ , but is not computationally tractable. In Section 2.2, we provide a convex relaxation of the problem which is in essence the Lasso estimator applied to a vectorised version of the problem. The link prediction task is covered in Section 2.3. A matching minimax lower bound for the rate of estimation is given in Section 2.4. Furthermore, we show in Section 3 that the minimax rate cannot be attained by a (randomised) polynomial-time algorithm, and we identify a corresponding computational lower bound. The proof of this bound is based on a reduction scheme from the so-called dense subgraph detection problem. Technical proofs are deferred to the appendix. Our findings are depicted in Figure 1 . Notation: For any positive integer n, we denote by [n] the set {1, . . . , n} and by [[n]] the set of couples of [n], of cardinality n 2 . We denote by R the set of real numbers and by S d the set of real symmetric matrices of size d. For a matrix A ∈ S d , we denote by A F its Frobenius norm, defined by We extend this definition for B ∈ S n and any subset Ω ⊆ [[n]] to its semi-norm
In the related setting of the inductive link prediction in graphs REF the minimax optimal rates in sparse and low-rank regime are obtained and the tradeoffs between the statistical rates and the computational complexity are uncovered.
Optimal link prediction with matrix logistic regression
arXiv: Statistics Theory
Mathematics