Empirical Comparison of “Hard” and “Soft” Label Propagation for Relational Classification
Lecture notes in computer sciencePublished 1 January 2008
Aram Galstyan, Paul R. Cohen
Citations17
SJR quartileQ2
SJR score0.35
SNIP0.55
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
A comparative empirical study of hard and soft label propagation for classification of relational (networked) data is presented, and it is indicated that while neither approach dominates the other over the entire range of input data parameters, there are some interesting and non-trivial tradeoffs between them.
Abstract
In this paper we differentiate between hard and soft label propagation for classification of relational (networked) data. The latter method assigns probabilities or class-membership scores to data instances, then propagates these scores throughout the networked data, whereas the former works by explicitly propagating class labels at each iteration. We present a comparative empirical study of these methods applied to a relational binary classification task, and evaluate two approaches on both synthetic and real–world relational data. Our results indicate that while neither approach dominates the other over the entire range of input data parameters, there are some interesting and non–trivial tradeoffs between them.
Keywords
Computer Science
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.
Learning from Labeled and Unlabeled Data with Label Propagation
1,568 Citations2002Xiongjie Zhu, Zoubin Ghahramani
A simple iterative algorithm, label propagation, to propagate labels through the dataset along high density areas defined by unlabeled data is proposed and its solution is analyzed, and its connection to several other algorithms is analyzed.
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.
Elsevier eBooksCombating Web Spam with TrustRank
1,025 Citations2004Zoltán Gyöngyi, Héctor García-Molina +1 more
This paper proposes techniques to semi-automatically separate reputable, good pages from spam, and shows that they can effectively filter out spam from a significant fraction of the web, based on a good seed set of less than 200 sites.
Learning Probabilistic Relational Models
941 Citations2001Lise Getoor, Nir Friedman +2 more
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.
Partially labeled classification with Markov random walks
563 Citations2001Martin Szummer, Tommi Jaakkola
This work combines a limited number of labeled examples with a Markov random walk representation over the unlabeled examples and develops and compares several estimation criteria/algorithms suited to this representation.
Document clustering using word clusters via the information bottleneck method
476 Citations2000Noam Slonim, Naftali Tishby
A novel implementation of the recently introduced information bottleneck method for unsupervised document clustering that first finds word-clusters that capture most of the mutual information about to set of documents, and then finds document clusters that preserve the information about the word clusters.
Journal of Machine Learning ResearchClassification in Networked Data: A Toolkit and a Univariate Case Study
447 Citations2007Sofus A. Macskassy, Foster Provost
The results demonstrate that very simple network-classification models perform quite well---well enough that they should be used regularly as baseline classifiers for studies of learning with networked 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.
Data Clustering by Markovian Relaxation and the Information Bottleneck Method
134 Citations2000Naftali Tishby, Noam Slonim
This method combines a pairwise based approach with a vector-quantization method which provide a meaningful interpretation to the resulting clusters and can cluster data with no geometric or other bias and makes no assumption about the underlying distribution.
A study of relevance propagation for web search
99 Citations2005Tao Qin, Tie‐Yan Liu +3 more
Drawing many conclusions that are useful for selecting a propagation model in real-world search applications are come to, including 1) sitemap-based propagation models outperform hyperlink-based models in sense of both effectiveness and efficiency, and 2) sitEMap- based term propagation is easier to be integrated into real- world search engines because of its parallel offline implementation and acceptable complexity.
Text REtrieval ConferenceRelevance Propagation for Topic Distillation UIUC TREC 2003 Web Track Experiments.
52 Citations2003Azadeh Shakery, ChengXiang Zhai
The experiment results show that combining link and content information generally performs better than using only content information, though the amount of improvement is sensitive to the document collection and tuning of parameters.
Suspicion scoring of networked entities based on guilt-by-association, collective inference, and focused data access 1
31 Citations2005Sofus A. Macskassy, Foster Provost
A guilt-by-association system that can be used to rank networked entities by their suspiciousness is described and demonstrated on a suite of data sets generated by a terrorist-world simulator developed to support a DoD program.
Classificaiton in Networked Data: A Toolkit and a Univariate Case Study
10 Citations2005Softus A. Macskassy, Foster Provost
NetKit-SRL: A Toolkit for Network Learning and Inference
9 Citations2005Sofus A. Macskassy, Foster Provost
International Joint Conference on Artificial IntelligenceInferring useful heuristics from the dynamics of iterative relational classifiers
6 Citations2005Aram Galstyan, Paul R. Cohen
It is speculated that for a class of algorithms that use label-propagation the iterative procedure can lead to nontrivial dynamics in the number of newly classified instances, and suggested that this phenomenon can be used for establishing a self-consistent classification threshold and a criterion for stopping iteration.
Relational Classification Through Three¿State Epidemic Dynamics
3 Citations2006Aram Galstyan, Paul R. Cohen
This paper introduces a new, intermediate state that corresponds to "susceptible" data instances that allows to control the rates of epidemic spreading, hence making the algorithm more flexible and improving significantly the performance of the algorithm.