Link-based Classification
Advanced information and knowledge processingPublished 1 January 2006
Qing Lu
Citations627
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.
Abstract
Over the past few years, a number of approximate inference algorithms for networked data have been put forth. We empirically compare the performance of three of the popular algorithms: loopy belief propagation, mean field relaxation labeling and iterative classification. We rate each algorithm in terms of its robustness to noise, both in attribute values and correlations across links. We also compare them across varying types of correlations across links.
Keywords
Computer ScienceBiochemistry, Genetics and Molecular BiologyPhysics and Astronomy
ScholarlyCommons (University of Pennsylvania)Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
12,978 Citations2001John Lafferty, Andrew McCallum +1 more
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
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.
Lecture notes in computer scienceText categorization with Support Vector Machines: Learning with many relevant features
7,925 Citations1998Thorsten Joachims
SVMs achieve substantial improvements over the currently best performing methods and behave robustly over a variety of di-erent learning tasks, eliminating the need for manual parameter tuning.
Combining labeled and unlabeled data with co-training
5,604 Citations1998Avrim Blum, Tom M. Mitchell
A comparison of event models for naive bayes text classification
3,224 Citations1998Andrew McCallum, Kamal Nigam
It is found that the multi-variate Bernoulli performs well with small vocabulary sizes, but that the multinomial performs usually performs even better at larger vocabulary sizes--providing on average a 27% reduction in error over the multi -variateBernoulli model at any vocabulary size.
Machine LearningText Classification from Labeled and Unlabeled Documents using EM
2,749 Citations2000Kamal Nigam, Andrew Kachites McCallum +2 more
This paper shows that the accuracy of learned text classifiers can be improved by augmenting a small number of labeled training documents with a large pool of unlabeled documents, and presents two extensions to the algorithm that improve classification accuracy under these conditions.
Transductive Inference for Text Classification using Support Vector Machines
2,717 Citations1999Thorsten Joachims
An analysis of why TSVMs are well suited for text classi(cid:12)cation is presented, and an algorithm for training TSVMs e(cid:14)-ciently, handling 10,000 examples and more is proposed.
On Discriminative vs. Generative Classifiers: A comparison of logistic regression and naive Bayes
1,887 Citations2001Andrew Y. Ng, Michael I. Jordan
It is shown, contrary to a widely-held belief that discriminative classifiers are almost always to be preferred, that there can often be two distinct regimes of performance as the training set size is increased, one in which each algorithm does better.
IEEE Transactions on Information TheoryConstructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
1,627 Citations2005Jonathan S. Yedidia, William T. Freeman +1 more
This work explains how to obtain region-based free energy approximations that improve the Bethe approximation, and corresponding generalized belief propagation (GBP) algorithms, and describes empirical results showing that GBP can significantly outperform BP.
arXiv (Cornell University)Loopy Belief Propagation for Approximate Inference: An Empirical Study
1,468 Citations2013Kevin P. Murphy, Yair Weiss +1 more
IEEE Transactions on Systems Man and CyberneticsScene Labeling by Relaxation Operations
1,401 Citations1976Azriel Rosenfeld, Robert A. Hummel +1 more
This paper formulates the ambiguity-reduction process in terms of iterated parallel operations (i.e., relaxation operations) performed on an array of object, identification data.
Information RetrievalAutomating the Construction of Internet Portals with Machine Learning
1,265 Citations2000Andrew Kachites McCallum, Kamal Nigam +2 more
New research in reinforcement learning, information extraction and text classification that enables efficient spidering, the identification of informative text segments, and the population of topic hierarchies are described.
Max-Margin Markov Networks
1,251 Citations2003Ben Taskar, Carlos Guestrin +1 more
Maximum margin Markov (M3) networks incorporate both kernels, which efficiently deal with high-dimensional features, and the ability to capture correlations in structured data, and a new theoretical bound for generalization in structured domains is provided.
CiteSeer
1,031 Citations1998C. Lee Giles, Kurt Bollacker +1 more
CiteSeer has many advantages over traditional citation indexes, including the ability to create more up-to-date databases which are not limited to a preselected set of journals or restricted by journal publication delays, completely autonomous operation with a corresponding reduction in cost, and powerful interactive browsing of the literature using the context of citations.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)Learning from Labeled and Unlabeled Data using Graph Mincuts
947 Citations2018Avrim Blum, Shuchi Chawla
An algorithm based on finding minimum cuts in graphs, that uses pairwise relationships among the examples in order to learn from both labeled and unlabeled data is considered.
Learning Probabilistic Relational Models
941 Citations2001Lise Getoor, Nir Friedman +2 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn the Foundations of Relaxation Labeling Processes
891 Citations1983Robert A. Hummel, Steven W. Zucker
It is shown that the problem of finding consistent labelings is equivalent to solving a variational inequality, and a procedure nearly identical to the relaxation operator derived under restricted circum-stances serves in the more general setting.
Enhanced hypertext categorization using hyperlinks
775 Citations1998Soumen Chakrabarti, Byron Dom +1 more
This work has developed a text classifier that misclassified only 13% of the documents in the well-known Reuters benchmark; this was comparable to the best results ever obtained and its technique also adapts gracefully to the fraction of neighboring documents having known topics.
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
Lecture notes in computer scienceFOIL: A midterm report
513 Citations1993J. R. Quinlan, R. M. Cameron-Jones
This paper summarises the development of FOIL from 1989 up to early 1993 and evaluates its effectiveness on a non-trivial sequence of learning tasks taken from a Prolog programming text.
Computer NetworksFinding related pages in the World Wide Web
491 Citations1999Jay B. Dean, Monika Henzinger
This paper discusses a different approach to Web searching where the input to the search process is not a set of query terms, but instead is the URL of a page, and the output is aSet of related Web pages.
Link Prediction in Relational Data
442 Citations2003Ben Taskar, Ming-fai Wong +2 more
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.
The Missing Link - A Probabilistic Model of Document Content and Hypertext Connectivity
439 Citations2000David Cohn, Thomas Hofmann
A joint probabilistic model for modeling the contents and inter-connectivity of document collections such as sets of web pages or research paper archives is described, based on a Probabilistic factor decomposition.
IEEE Intelligent Systems and their ApplicationsGraph-based data mining
411 Citations2000Diane J. Cook, Lawrence B. Holder
Using databases represented as graphs, the Subdue system performs two key data mining techniques: unsupervised pattern discovery and supervised concept learning from examples.
Information RetrievalText Categorization Based on Regularized Linear Classification Methods
378 Citations2001Tong Zhang, Frank J. Oles
A number of known linear classification methods as well as some variants in the framework of regularized linear systems are compared to discuss the statistical and numerical properties of these algorithms, with a focus on text categorization.
Symposium on Discrete AlgorithmsDirected scale-free graphs
325 Citations2003Béla Bollobás, Christian Borgs +2 more
A model for directed scale-free graphs that grow with preferential attachment depending in a natural way on the in- and out-degrees is introduced, reproducing observed properties of the worldwide web.
Journal of Intelligent Information SystemsA Study of Approaches to Hypertext Categorization
309 Citations2002Yiming Yang, Seán Slattery +1 more
This paper examines five hypertext regularities which may (or may not) hold in a particular application domain, and whose presence (or absence) may significantly influence the optimal design of a classifier.
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.
Propositionalization Approaches to Relational Data Mining
271 Citations2001Stefan Krämer, Nada Lavrač +1 more
An extension to the LINUS propositionalization method that overcomes the system's earlier inability to deal with non-determinate local variables is described, and it is shown that in many relational data mining applications this can be done without loss of predictive performance.
Academic Press eBooksMarkov random fields : theory and application
265 Citations1993Rama Chellappa, Anil K. Jain
Image modeling during the 1980s - a brief overview, A Rosenfeld compound Gauss-Markov random fields for parallel image processing, J.W. Woods, et al stochastic algorithms for restricted image spaces and experiments in deblurring, and a continuation method for image estimation using the A-diabatic approximation.
Why collective inference improves relational classification
256 Citations2004David Jensen, Jennifer Neville +1 more
This work describes the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data, and characterizes different types of statistical models used for making inference in relational data.
A Simple Relational Classifier
246 Citations2003Sofus A. Macskassy, Foster Provost
It is argued that a simple relational predictive model the predicts only based on class labels of related neighbors, using no learning and no inherent attributes should be used as a baseline to assess the performance of relational learners.
Learning probabilistic models of link structure
239 Citations2003Lisa Getoor, Nir Friedman +2 more
This paper proposes two mechanisms for representing a probabilistic distribution over link structures: reference uncertainty and existence uncertainty, and describes the appropriate conditions for using each model and present learning algorithms for each.
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 associative Markov networks
176 Citations2004Ben Taskar, Vassil Chatalbashev +1 more
This paper exploits a linear programming relaxation for the task of finding the best joint assignment in associative Markov networks, which provides an approximate quadratic program (QP) for the problem of learning a margin-maximizing Markov network.
The Role of Unlabeled Data in Supervised Learning
150 Citations2004Tom M. Mitchell
It is argued that models of human and animal learning should consider more strongly the potential role of unlabeled data, and that many natural learning problems fit the problem class identified in this paper.
A practical hypertext catergorization method using links and incrementally available class information
148 Citations2000Hyo-Jung Oh, Sung Hyon Myaeng +1 more
This paper proposes a practical method for enhancing both the speed and the quality of hypertext categorization using hyperlinks, and achieves up to 18.5% of improvement in effectiveness while reducing the processing time dramatically.
ePrints Soton (University of Southampton)Composite Kernels for Hypertext Categorisation
145 Citations2001Thorsten Joachims, Nello Cristianini +1 more
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Using unlabeled data to improve text classification
129 Citations2001Kanal Paul Nigam, Tom M. Mitchell
This dissertation demonstrates that supervised learning algorithms that use a small number of labeled examples and many inexpensive unlabeled examples can create high-accuracy text classifiers.
Lecture notes in computer scienceCombining statistical and relational methods for learning in hypertext domains
78 Citations1998Seán Slattery, Mark Craven
This work presents a new approach to learning hypertext classifiers that combines a statistical text-learning method with a relational rule learner and demonstrates that this new approach is able to learn more accurate classifiers than either of its constituent methods alone.
Stochastic link and group detection
72 Citations2002Jeremy Kubica, Andrew Moore +2 more
A probabilistic model of link generation based on membership in groups is proposed that considers both observed link evidence and demographic information about the entities and shows several heuristics that make the search tractable.
Combining labeled and unlabeled data for text classification with a large number of categories
63 Citations2002Rayid Ghani
This work develops a framework to incorporate unlabeled data in the error-correcting output coding (ECOC) setup by decomposing multiclass problems into multiple binary problems and then using co-training to learn the individual binary classification problems.
Statistical challenges to inductive inference in linked data.
37 Citations1999David Jensen
This paper examines three such challenges: 1) statistical dependence caused by linked instances; 2) bias introduced by sampling density; and 3) multiple comparisons intensified by feature combinatorics.
ScholarlyCommons (University of Pennsylvania)Towards Structural Logistic Regression: Combining Relational and Statistical Learning
26 Citations2002Alexandrin Popescul, Lyle Ungar +2 more
A new approach is proposed which integrates structure navigation from ILP with regression modeling, and propositionalizes the first-order rules at each step of ILP's relational structure search, generating features for potential inclusion in a regression model.
The role of feature construction in inductive rule learning
26 Citations2000Peter Flach, Raedt Luc De +2 more
It is argued that feature construction is a crucial notion in explaining the relations between attribute-value rule learning and inductive logic programming (ILP) and a general method for transforming ILP problems to attributevalue form is demonstrated, which overcomes some of the traditional limitations of propositionalisation approaches.