Scaling Up Markov Logic Probabilistic Inference for Social Graphs

Haiquan Chen, Wei Shinn Ku, Haixun Wang, Liang Tang, Min Te Sun

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Link prediction is a fundamental problem in social network analysis. Although the link prediction problem is not new, the challenge of how to exploit various existing network information, such as network structure data and node attribute data, to enable AI-style knowledge inference for large social networks still remains unsolved. In this paper, we design and implement a scalable framework that treats link prediction as knowledge reasoning using Markov Logic Networks (MLNs). Differing from other probabilistic graphical models, MLNs allow undirected relationships with cycles and long-range (non-adjacent) dependency, which are essential and abound in social networks. In our framework, the prior knowledge is captured as the structure dependency (such as friendship) and the attribute dependency (such as social communities) in terms of inference rules, associated with uncertainty represented as probabilities. Next, we employ the random walk to discover the inference subgraph, on which probabilistic inference is performed, so that the required computation and storage cost can be significantly reduced without much sacrifice of the inference accuracy. Our extensive experiments with real-world datasets verify the superiority of our proposed approaches over two baseline methods and show that our approaches are able to provide a tunable tradeoff between inference accuracy and efficiency.

Original languageEnglish
Article number7736107
Pages (from-to)433-445
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume29
Issue number2
DOIs
StatePublished - 1 Feb 2017

Keywords

  • Markov logic network
  • Social network analysis
  • graph pruning
  • probabilistic graphical models

Fingerprint

Dive into the research topics of 'Scaling Up Markov Logic Probabilistic Inference for Social Graphs'. Together they form a unique fingerprint.

Cite this