Are there any probabilistic models for graph-based recommender systems? All I can find now is somehow based on random walks or graph kernels, which is nice, but I want to have a more or less solid probabilistic foundation for my recommender system for bounds and estimations and stuff which usually comes with probabilistic models. 
I probably should clarify: I have a graph and want to build recommender engine what recommends certain vertexes based on the ones selected by user.  
 A: There is the very-well known approach based on restricted BOltzmann machines (RBM), which won the Netflix competition. For more details you may have a look at the Wikipedia site, and the references therein.
Restricted Boltzmann machines are a particular instance of Markov Random Fields, with some properties that makes particularly attractive. Here a couple of points are made.
The approach is described in detail in this paper. The idea is that there is a RBM per user. Each RBM has as many hidden units as items rated by the user. The main insight is weight sharing: the weight referring to a corresponding item is shared by all users, i.e. it is the same parameter. So when many users give a good rating to an item, the corresponding weight becomes stronger for all users. And viceversa. Here is where collaboration takes place.
Now, in order to see what items to recommend to a given user, one clamp the visible units to the observed ratings, and evaluates the probability of obtaining a given rating for each user. You may have a look at these slides, where it is graphically explained in more detail.
As I understand, selecting a vertex would be equivalent to selecting one of the items. The RBM would give you back how likely will the user rate the item as k, where k is each of the possible ratings.
A: There is another good paper on this for unrestricted Boltzmann machines. You might also look at sum/max product networks. 
It may be that what you really want to do is compute marginal distributions rather than a real recommendation systems. In that case consider Markov Random Fields or perhaps log-linear models. 
