Link Prediction in Relational Data
Published 9 December 2003
Ben Taskar, Ming-fai Wong, Pieter Abbeel, Daphne Koller
Citations442
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the collective classification approach of RMNs, and the introduction of subgraph patterns over link labels, provide significant improvements in accuracy over flat classification, which attempts to predict each link in isolation.
Abstract
Many real-world domains are relational in nature, consisting of a set of objects related to each other in complex ways. This paper focuses on predicting the existence and the type of links between entities in such domains. We apply the relational Markov network framework of Taskar et al. to define a joint probabilistic model over the entire link graph --- entity attributes and links. The application of the RMN algorithm to this task requires the definition of probabilistic patterns over subgraph structures. We apply this method to two new relational datasets, one involving university webpages, and the other a social network. We show that the collective classification approach of RMNs, and the introduction of subgraph patterns over link labels, provide significant improvements in accuracy over flat classification, which attempts to predict each link in isolation.
Keywords
Computer SciencePhysics and Astronomy
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
16,927 Citations1988Judea Pearl
The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.
The PageRank Citation Ranking : Bringing Order to the Web
12,645 Citations1999Lawrence M. Page, Sergey Brin +2 more
This paper describes PageRank, a mathod for rating Web pages objectively and mechanically, effectively measuring the human interest and attention devoted to them, and shows how to efficiently compute PageRank for large numbers of pages.
Journal of the ACMAuthoritative sources in a hyperlinked environment
9,060 Citations1999Jon Kleinberg
This work proposes and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure, and has connections to the eigenvectors of certain matrices associated with the link graph.
PsychometrikaLogit Models and Logistic Regressions for Social Networks: I. An Introduction to Markov Graphs and <i>p</i>
1,264 Citations1996Stanley Wasserman, Philippa Pattison
A large class of models, including several generalizations of stochastic block models, as well as models parameterizing global tendencies towards clustering and centralization, and individual differences in such tendencies are described and extended.
IEEE Transactions on Pattern Analysis and Machine IntelligenceInducing features of random fields
1,044 Citations1997S. Della Pietra, V. Della Pietra +1 more
The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated.
Generalized Belief Propagation
906 Citations2000Jonathan S. Yedidia, William T. Freeman +1 more
It is shown that BP can only converge to a stationary point of an approximate free energy, known as the Bethe free energy in statistical physics, and generalized belief propagation (GBP) versions of these Kikuchi approximations are derived.
Inductive Logic Programming: Techniques and Applications
767 Citations1993Nada Lavrač, Sašo Džeroski
Applications of inductive logic programming: learning rules for early diagnosis of rheumatic diseases finite element mesh design an overview of selected ILP applications.
Information Processing & ManagementAn introduction to informetrics
756 Citations1992Jean Tague‐Sutcliffe
The scope and significance of the field of informetrics is defined and related to the earlier fields of bibliometrics and scientometrics; the phenomena studied by informetricians are identified.
Learning to extract symbolic knowledge from the World Wide Web
675 Citations1998Mark Craven, Dan DiPasquo +5 more
The goal of the research described here is to automatically create a computer understandable world wide knowledge base whose content mirrors that of the World Wide Web, and several machine learning algorithms for this task are described.
Discriminative probabilistic models for relational data
637 Citations2002Ben Taskar, Pieter Abbeel +1 more
Iterative Classification in Relational Data
306 Citations2000Jennifer Neville, David Jensen
An iterative classification approach that uses simple Bayesian classifiers in an iterative fashion, dynamically upd ating the attributes of some objects as inferences are made about related ob jects.
Probabilistic frame-based systems
269 Citations1998Daphne Koller, Avi Pfeffer
This paper provides a language that cleanly integrates frame-based representation systems and Bayesian networks, and describes an implemented system that allows most of the main frame systems in existence today to annotate their knowledge bases with Probabilistic information, and to use that information in answering probabilistic queries.
First MondayA social network caught in the Web
268 Citations2003Lada A. Adamic, Orkut Buyukkokten +1 more
Using the rich profile data provided by the users, the analysis of Club Nexus was able to deduce the attributes contributing to the formation of friendships, and to determine how the similarity of users decays as the distance between them in the network increases.
Probabilistic classification and clustering in relational data
230 Citations2001Ben Taskar, Eran Segal +1 more
This work proposes a general class of models for classification and clustering in relational domains that capture probabilistic dependencies between related instances, and shows how to learn such models efficiently from data.
Learning Probabilistic Models of Relational Structure
217 Citations2001Lise Getoor, Nir Friedman +2 more
Probabilistic Models of Text and Link Structure for Hypertext Classification
77 Citations2001Lise Getoor, Eran Segal +2 more
This work proposes a unified probabilistic model for both the textual content and the link structure of a document collection based on the recently introduced framework of Probabilistic Relational Models (PRMs), which allows us to capture correlations between linked documents.
Hypertext Categorization using Hyperlink Patterns and Meta Data
66 Citations2001Rayid Ghani, Seán Slattery +1 more
This investigation suggests that meta data which is often available, or can be acquired using Information Extraction techniques, can be extremely useful for improving classi cation accuracy.