  Digital presence in the world of online social media entails significant
privacy risks. In this work we consider a privacy threat to a social network in
which an attacker has access to a subset of random walk-based node
similarities, such as effective resistances (i.e., commute times) or
personalized PageRank scores. Using these similarities, the attacker's goal is
to infer as much information as possible about the underlying network,
including any remaining unknown pairwise node similarities and edges.
  For the effective resistance metric, we show that with just a small subset of
measurements, the attacker can learn a large fraction of edges in a social
network, even when the measurements are noisy. We also show that it is possible
to learn a graph which accurately matches the underlying network on all other
effective resistances. This second observation is interesting from a data
mining perspective, since it can be expensive to accurately compute all
effective resistances. As an alternative, our graphs learned from just a subset
of approximate effective resistances can be used as surrogates in a wide range
of applications that use effective resistances to probe graph structure,
including for graph clustering, node centrality evaluation, and anomaly
detection.
  We obtain our results by formalizing the graph learning objective
mathematically, using two optimization problems. One formulation is convex and
can be solved provably in polynomial time. The other is not, but we solve it
efficiently with projected gradient and coordinate descent. We demonstrate the
effectiveness of these methods on a number of social networks obtained from
Facebook. We also discuss how our methods can be generalized to other random
walk-based similarities, such as personalized PageRank. Our code is available
at https://github.com/cnmusco/graph-similarity-learning.
