  Performing signal processing over graphs requires knowledge of the underlying
fixed topology. However, graphs often grow in size with new nodes appearing
over time, whose connectivity is typically unknown; hence, making more
challenging the downstream tasks in applications like cold start
recommendation. We address such a challenge for signal interpolation at the
incoming nodes blind to the topological connectivity of the specific node.
Specifically, we propose a stochastic attachment model for incoming nodes
parameterized by the attachment probabilities and edge weights. We estimate
these parameters in a data-driven fashion by relying only on the attachment
behaviour of earlier incoming nodes with the goal of interpolating the signal
value. We study the non-convexity of the problem at hand, derive conditions
when it can be marginally convexified, and propose an alternating projected
descent approach between estimating the attachment probabilities and the edge
weights. Numerical experiments with synthetic and real data dealing in cold
start collaborative filtering corroborate our findings.
