Inferring networks from random walk-based node similarities

Jeremy G. Hoskins, Cameron Musco, Christopher Musco, Charalampos E. Tsourakakis

    Research output: Contribution to journalConference articlepeer-review


    Digital presence in the world of online social media entails significant privacy risks [31, 56]. 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 seeks to infer as much information as possible about the network, including unknown pairwise node similarities and edges. For the effective resistance metric, we show that with just a small subset of measurements, one can learn a large fraction of edges in a social network. 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 compute all effective resistances or other random walk-based similarities. As an alternative, our graphs learned from just a subset of effective resistances can be used as surrogates in a 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 scores. Our code is available at

    Original languageEnglish (US)
    Pages (from-to)3704-3715
    Number of pages12
    JournalAdvances in Neural Information Processing Systems
    StatePublished - 2018
    Event32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada
    Duration: Dec 2 2018Dec 8 2018

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Information Systems
    • Signal Processing


    Dive into the research topics of 'Inferring networks from random walk-based node similarities'. Together they form a unique fingerprint.

    Cite this