Semi-Supervised Classification of Network Data Using Very Few Labels
Abstract
The goal of semi-supervised learning (SSL) methods is to reduce the amount of labeled training data required by learning from both labeled and unlabeled instances. Macskassy and Provost (2007) proposed the weighted-vote relational neighbor classifier (wvRN) as a simple yet effective baseline for semi-supervised learning on network data. It is similar to many recent graph-based SSL methods and is shown to be essentially the same as the Gaussian-field harmonic functions classifier proposed by Zhu et al. (2003) and proves to be very effective on some benchmark network datasets. We describe another simple and intuitive semi-supervised learning method based on random graph walk that outperforms wvRN by a large margin on several benchmark datasets when very few labels are available. Additionally, we show that using authoritative instances as training seeds --- instances that arguably cost much less to label --- dramatically reduces the amount of labeled data required to achieve the same classification accuracy. For some existing state-of-the-art semi-supervised learning methods the labeled data needed is reduced by a factor of 50.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Cites
Normalized cuts and image segmentation
Shi, J., & Malik, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.868688 · Cited by 15,842 · see citing works
(1999) · Cited by 12,854 · see citing works
On Spectral Clustering: Analysis and an algorithm
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2001) · Cited by 8,159 · see citing works
Learning with Local and Global Consistency
Zhou, D., Bousquet, O., Lal, T. N., Weston, J., & Schölkopf, B. (2003) · MPG.PuRe (Max Planck Society) · Cited by 3,856 · see citing works
Semi-Supervised Learning Literature Survey
Zhu, X. (2005) · Cited by 3,828 · see citing works
Semi-supervised learning using Gaussian fields and harmonic functions
Zhu, X., Zoubin Ghahramani, A., & Lafferty, J. (2003) · Cited by 3,509 · see citing works
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619 · see citing works
Fast Random Walk with Restart and Its Applications
Tong, H., Faloutsos, C., & Pan, J.-Y. (2006) · Proceedings · doi:10.1109/icdm.2006.70 · Cited by 1,218 · see citing works
Selective Sampling Using the Query by Committee Algorithm
Freund, Y., Seung, H. S., Shamir, E., & Tishby, N. (1997) · Machine Learning · doi:10.1023/a:1007330508534 · Cited by 1,098 · see citing works
Getoor, L. C. (2006) · Springer eBooks · doi:10.1007/1-84628-284-5_7 · Cited by 688 · see citing works
Partially labeled classification with Markov Random Walks
Szummer, M., & Jaakkola, T. (2001) · Cited by 557 · see citing works
Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions
Zhu, X., Lafferty, J., & Ghahramani, Z. (2003) · Cited by 469 · see citing works
Learning to construct knowledge bases from the World Wide Web
Craven, M. W., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T. M., Nigam, K., & Slattery, S. (2000) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00004-7 · Cited by 462 · see citing works
Classification in Networked Data: A Toolkit and a Univariate Case Study
(2007) · Journal of Machine Learning Research · doi:10.5555/1248659.1248693 · Cited by 452 · see citing works
Video suggestion and discovery for youtube
Baluja, S., Seth, R., Sivakumar, D., Jing, Y., Yagnik, J., Kumar, S., Ravichandran, D., & Aly, M. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367618 · Cited by 447 · see citing works
An Analytical Comparison of Approaches to Personalizing PageRank
Haveliwala, T. H., Kamvar, S. D., & Jeh, G. (2003) · Cited by 181 · see citing works
Using ghost edges for classification in sparsely labeled networks
Gallagher, B. J., Tong, H., Eliassi‐Rad, T., & Faloutsos, C. (2008) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1401890.1401925 · Cited by 149 · see citing works
Weakly-supervised acquisition of labeled class instances using graph random walks
Talukdar, P. P., Reisinger, J., PAŞCA, M. A., et al. (2008) · Conference on Empirical Methods in Natural Language Processing (EMNLP) · doi:10.3115/1613715.1613787 · Cited by 131 · see citing works
Modeling Trust and Influence on Blogosphere using Link Polarity
Kale, A. (2007) · doi:10.13016/m28h3f · Cited by 73 · see citing works
Stacked Graphical Models for Efficient Inference in Markov Random Fields
Kou, Z., & Cohen, W. W. (2007) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972771.57 · Cited by 66 · see citing works
Self-citation(2010) · Encyclopedia of Machine Learning · doi:10.1007/978-0-387-30164-8_482 · Cited by 53 · see citing works
Graph-Based Semi-Supervised Learning as a Generative Model
He, J., Carbonell, J., & Liu, Y. (2018) · Figshare · doi:10.1184/r1/6605996 · Cited by 46 · see citing works
Improving learning in networked data by combining explicit and mined links
Macskassy, S. A. (2007) · National Conference on Artificial Intelligence · Cited by 45 · see citing works
Improving a Page Classifier with Anchor Extraction and Link Analysis
Cohen, W. W. (2002) · Cited by 34 · see citing works
Self-citationWeb Content Categorization Using Link Information
Gyöngyi, Z., García-Molina, H., & Pedersen, J. (2006) · Cited by 25 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · see citing works
- Authors
- Lin, F., & Cohen, W. W.
- Affiliations
- Carnegie Mellon University (US)
- Venue
- 2010 International Conference on Advances in Social Networks Analysis and Mining
- Publisher
- IEEE
- Published
- 2010-08
- Pages
- 192-199
- OpenAlex
- W2148534792
- Cited by
- 96
- References
- 25
- Citations by year
- 2025: 3 · 2024: 4 · 2023: 5 · 2022: 3 · 2021: 8 · 2020: 6 · 2019: 7 · 2018: 13 · 2017: 7 · 2016: 8 · 2015: 9 · 2014: 5 · 2013: 8 · 2012: 6
- FWCI
- 4.65
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (publishedVersion)
- Funders
- National Science Foundation
- National Institutes of Health
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Physics and Astronomy › Statistical and Nonlinear Physics › Complex Network Analysis Techniques
- Keywords
- semi-supervised classification, network data, graph learning, random walks
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
