The general idea (using word frequencies in context) is Firth's distributional hypothesis [0]. Related to this is the idea of a distributional representation which is covered by Gardenfors in his book on conceptual spaces.
For word2vec and such, several papers in this year's TACL explain why these methods should work [1,2].
There are good reasons other than `it models the data well' to use a logit. Of course, the perspective that much like least-squares, logit regression does best when your data is generated from a logistic GLM is true, but not the only story.
The papers cited in the article pretty cleanly explain why the logit and other surrogate losses are the 'natural choice' for classification. This also explains why other non-generative models like the SVM perform similarly well to the logit in practice.
The last sentence of your post is known as 'link-prediction' in the networks literature. [1] is a pretty comprehensive survey from the networks perspective. In many cases this reduces to learning pairwise distances between vertices.
The network translation view is interesting, though one caution would be that you can have two graphs constructed on identical points, but with a different graph construction technique (say k-nearest neighbor vs fixed eps ball graph) and it is unclear if you should say the two graphs are the same (since they share the same latent coordinates) or if they are different since the graphs differ.
The generative model approach seems like a pretty nice way to go since it lets you evaluate against simulation and ground truth. The only problem in my view is that network models may be quite limited since the relevant network models for these problems rely on exchangability of some type.
We've a paper in review on the link prediction problem via random walk hitting times as a similarity measure. We don't have a preprint on Arxiv since that would de-anonymize us, but I'd be happy to send a copy if this is relevant to your work.
The connection between the random walk and embeddings has been characterized in [1] (disclosure: I am an author).
It turns out embedding in this setting is exactly smarter page rank as you suggested, since PageRank recovers the underlying density structure of an embedding.
I'm not hopeful that this is much more powerful than a matrix representation, since if [2] is true, it's a matrix factorization of the random-walk marginal. It's probably more scalable than the linear algebra approach, but not more powerful theoretically or representationally.
One interesting connection that is unexplored in the paper is that of kernel PCA with diffusion kernels and this approach. Once again if [2] is true, then this procedure should behave like kernel PCA under a diffusion kernel in the large-data limit.
For word2vec and such, several papers in this year's TACL explain why these methods should work [1,2].
[0] https://www.aclweb.org/aclwiki/index.php?title=Distributiona... [1] https://transacl.org/ojs/index.php/tacl/article/viewFile/742... [2]https://transacl.org/ojs/index.php/tacl/article/viewFile/809...