A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks
We propose a scalable approach for making inference about latent spaces of large networks. With a succinct representation of networks as a bag of triangular motifs, a parsimonious statistical model, and an efficient stochastic variational inference algorithm, we are able to analyze real networks with over a million vertices and hundreds of latent roles on a single machine in a matter of hours, a setting that is out of reach for many existing methods. When compared to the state-of-the-art probabilistic approaches, our method is several orders of magnitude faster, with competitive or improved accuracy for latent space recovery and link prediction.
This paper proposes parsimonious triangular model 
      (PTM), which constrains the O(K^3) parameter space of mixed-membership 
      triangular model (MMTM) to O(K) for faster inference. Authors develop a 
      stochastic variational inference algorithm for PTM and additional 
      approximation tricks to make it further scalable. It is shown from 
      synthetic dataset that the reduction of the number of variables may lead 
      to stronger statistical power, and from real-world datasets that the 
      proposed method is competitive with existing methods in terms of accuracy. 
      Quality: PTM seems to be an interesting specialization of 
      MMTM, but it is questionable what is the practical advantage of achieving 
      good scalability in terms of K (the number of possible roles). To 
      empirically evaluate the value of such a method, it is critical for us to 
      answer "how does it help if we can learn MMTM with large K?" Since MMSB 
      and MMTM are mixed-membership models, using small K may not be as 
      troublesome as it is in single-membership models! For real network 
      experiments, what would be really interesting is to see the performance of 
      both MMTM and PTM as a function of K: if we can really see that PTM with 
      large K outperforms MMTM with small K, it will show the power of PTM. 
      Unfortunately such experiments were not done. Actually I could not find 
      good description about how K's were chosen in real data experiments for 
      both PTM and its competitor MMSB; the method of model selection could've 
      biased experimental results. Authors are also a bit reticent on 
      what are the impact of simplifying assumptions they make. It is clear that 
      we can achieve good scalability by constraining the parameter space, but 
      it would be also nice to hear about when would such model fail. If there 
      really are O(K^3) distinct values in the parameter matrix B (following 
      authors' notation) of MMSB and MMTM, PTM should perform poorly, right? In 
      this regard, it is unsatisfactory that the choice of true B in synthetic 
      data experiments were not clearly described; authors' should've 
      experimented with various B's which some are in favor of PTM and some are 
      against the model. It would be more beneficial for readers to know when 
      would PTM succeed and when would it fail, than to know only when it would 
      succeed. On the other hand, authors introduce a number of tricks 
      to make PTM scale; while I find them to be very interesting and effective, 
      this paper does a poor job in describing and analyzing the impact of such 
      an approximation. 1) What is the impact of choosing the threshold \delta? 
      On real-world and synthetic data experiments, does it help to choose 
      larger or smaller \delta? How much can we lower \delta to improve 
      scalability while not sacrificing much of accuracy? 2) Authors claim that 
      a-MMSB does not work since downsampling compromises accuracy; why would 
      PTM free of such problem? MMTM and PTM are actually ignoring triplets with 
      only one edge. Why can't we ignore non-edges in MMSB while we can in PTM? 
      3) What is the impact of O(K) approximation to local update (in page 5)? 
      What happens if we sample 2K, 4K, or 100K of triples? Would the quality of 
      approximation suffer when K gets larger? To sum up, I am not 
      convinced experimental setup was fair to competitors, and the description 
      of potential weakness of the algorithm/model is poor. Clarity: the 
      paper is very clearly written and well-organized. Originality: In 
      terms of modeling it is a bit incremental, but achieving scalability via 
      constraining parameters is an interesting and original direction to 
      pursue, as recently in this topic a lot of work has been focused on 
      generalizing existing models. Significance: Provided simplifying 
      assumptions in the model and the inference algorithm do hold in practice, 
      it would have a good impact on the practice of latent-space models on 
      networks, as not many of them actually scale to large data. 
      Additional Comments: Personally I think the title is too broad. 
      There are other scalable approaches to other latent space models, and 
      authors propose a scalable algorithm to _a_ latent space model- PTM. 
      Also, I am not sure that PTM is really a probabilistic method. 
      Authors argue in the last paragraph of Section 3 that this is same in 
      spirit to bag-of-words assumption, but I am not convinced. When LDA 
      generates a bag-of-words, there always exists a document corresponding to 
      it; so it has proper likelihood function, no matter how unrealistically 
      simple it might be. On the other hand, with very high probability there 
      does not exist any network corresponding to a bag-of-triples generated by 
      MMTM and PTM. Therefore MMTM/PTM is not really a generative model for 
      networks, and majority of posterior probability mass is placed on modeling 
      non-networks! It might be dangerous to abandon basic principles of 
      likelihood in "probabilistic" methods (what does probability mean in 
      PTM?)... I am curious what authors and other reviewers 
      think.