Higher-order graphical models for classification in social and affiliation networks

In this work we explore the application of higher-order Markov Random Fields(MRF) to classification in social and affiliation networks. We consider both friend-
ship links and group membership for inferring hidden attributes in a collective
inference framework. We explore different ways of using the social groups as ei-
ther node features or to construct the graphical model structure. The bottleneck in
applying higher-order MRFs to a domain with many overlapping large cliques is
the complexity of inference which is exponential in the size of the largest clique.
To circumvent the slow inference problem, we borrow recent advancements in
the computer vision community to achieve fast approximate inference results. We
provide preliminary results using a dataset from facebook which suggest that our
higher-order MRF models are capturing the structural dependencies in the net-
works and they yield higher accuracy than linear classifiers.