Estimating latent feature-feature interactions in large feature-rich
  graphs
  Real-world complex networks describe connections between objects; in reality,
those objects are often endowed with some kind of features. How does the
presence or absence of such features interplay with the network link structure?
Although the situation here described is truly ubiquitous, there is a limited
body of research dealing with large graphs of this kind. Many previous works
considered homophily as the only possible transmission mechanism translating
node features into links. Other authors, instead, developed more sophisticated
models, that are able to handle complex feature interactions, but are unfit to
scale to very large networks. We expand on the MGJ model, where interactions
between pairs of features can foster or discourage link formation. In this
work, we will investigate how to estimate the latent feature-feature
interactions in this model. We shall propose two solutions: the first one
assumes feature independence and it is essentially based on Naive Bayes; the
second one, which relaxes the independence assumption assumption, is based on
perceptrons. In fact, we show it is possible to cast the model equation in
order to see it as the prediction rule of a perceptron. We analyze how
classical results for the perceptrons can be interpreted in this context; then,
we define a fast and simple perceptron-like algorithm for this task, which can
process $10^8$ links in minutes. We then compare these two techniques, first
with synthetic datasets that follows our model, gaining evidence that the Naive
independence assumptions are detrimental in practice. Secondly, we consider a
real, large-scale citation network where each node (i.e., paper) can be
described by different types of characteristics; there, our algorithm can
assess how well each set of features can explain the links, and thus finding
meaningful latent feature-feature interactions.
