Cited By
View all- Li LChu YLiu GWu X(2019)Multi-Objective Optimization-Based Networked Multi-Label Active LearningJournal of Database Management10.4018/JDM.201904010130:2(1-26)Online publication date: 1-Apr-2019
Leveraging Neighbor Attributes for Classification in Sparsely Labeled Networks
Article No.: 2, Pages 1 - 37
Abstract
Many analysis tasks involve linked nodes, such as people connected by friendship links. Research on link-based classification (LBC) has studied how to leverage these connections to improve classification accuracy. Most such prior research has assumed the provision of a densely labeled training network. Instead, this article studies the common and challenging case when LBC must use a single sparsely labeled network for both learning and inference, a case where existing methods often yield poor accuracy. To address this challenge, we introduce a novel method that enables prediction via “neighbor attributes,” which were briefly considered by early LBC work but then abandoned due to perceived problems. We then explain, using both extensive experiments and loss decomposition analysis, how using neighbor attributes often significantly improves accuracy. We further show that using appropriate semi-supervised learning (SSL) is essential to obtaining the best accuracy in this domain and that the gains of neighbor attributes remain across a range of SSL choices and data conditions. Finally, given the challenges of label sparsity for LBC and the impact of neighbor attributes, we show that multiple previous studies must be re-considered, including studies regarding the best model features, the impact of noisy attributes, and strategies for active learning.
Supplementary Material
Supplemental movie, appendix, image and software files for, Leveraging Neighbor Attributes for Classification in Sparsely Labeled Networks
- Download
- 942.66 KB
References
[1]
B. Ahmadi, K. Kersting, M. Mladenov, and S. Natarajan. 2013. Exploiting symmetries for scaling loopy belief propagation and relational training. Mach. Learn. 92, 1 (2013), 91--132.
[2]
S. H. Bach, B. Huang, and L. Getoor. 2015. Unifying local consistency and MAX SAT relaxations for scalable inference with rounding guarantees. In Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS). 46--55.
[3]
S. H. Bach, B. Huang, B. London, and L. Getoor. 2013. Hinge-loss Markov random fields: Convex inference for structured prediction. In Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI). 32--41.
[4]
M. Belkin, P. Niyogi, and V. Sindhwani. 2006. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7 (2006), 2399--2434.
[5]
J. Besag. 1975. Statistical analysis of non-lattice data. The Statistician 24, 3 (1975), 179--195.
[6]
J. Besag. 1986. On the statistical analysis of dirty pictures. J. R. Stat. Soc. 48, 3 (1986), 259--302.
[7]
M. Bilgic and L. Getoor. 2008. Effective label acquisition for collective classification. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 43--51.
[8]
M. Bilgic, L. Mihalkova, and L. Getoor. 2010. Active learning for networked data. In Proceedings of International Conference on Machine Learning (ICML). 79--86.
[9]
B. Bollobás, C. Borgs, J. Chayes, and O. Riordan. 2003. Directed scale-free graphs. In Proceedings of Symposium on Discrete Algorithms (SODA). 132--139.
[10]
S. Chakrabarti, B. Dom, and P. Indyk. 1998. Enhanced hypertext categorization using hyperlinks. In Proceedings of SIGMOD. 307--318.
[11]
O. Chapelle, B. Schölkopf, and A. Zien. 2006. Semi-Supervised Learning. MIT Press, Cambridge.
[12]
R. Crane and L. McDowell. 2012. Investigating Markov logic networks for collective classification. In Proceedings of International Conference on Agents and Artificial Intelligence (ICAART). 5--15.
[13]
A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc., Ser. B 39, 1 (1977), 1--38.
[14]
A. Dhurandhar and J. Wang. 2013. Single network relational transductive learning. J. Artif. Intell. Res. 48 (2013), 813--839.
[15]
P. Domingos, S. Kok, D. Lowd, H. Poon, M. Richardson, and P. Singla. 2008. Probabilistic Inductive Logic Programming: Theory and Applications. Springer, Berlin.
[16]
P. Domingos and D. Lowd. 2009. Markov logic: An interface layer for artificial intelligence. Synth. Lect. Artif. Intell. Mach. Learn. 3, 1 (2009), 1--155.
[17]
A. Fleming, L. K. McDowell, and Z. Markel. 2014. A hidden treasure? Evaluating and extending latent methods for link-based classification. In Proceedings of International Conference on Information Reuse and Integration (IRI). 669--676.
[18]
B. Gallagher, H. Tong, T. Eliassi-Rad, and C. Faloutsos. 2008. Using ghost edges for classification in sparsely labeled networks. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 256--264.
[19]
B. Geng, D. Tao, C. Xu, L. Yang, and X.-S. Hua. 2012. Ensemble manifold regularization. IEEE Trans. Pattern Anal. Mach. Intell. 34, 6 (2012), 1227--1233.
[20]
S. Gould and X. He. 2014. Scene understanding by labeling pixels. Commun. ACM 57, 11 (2014), 68--77.
[21]
D. J. Hand and R. J. Till. 2001. A simple generalisation of the area under the ROC curve for multiple class classification problems. Mach. Learn. 45, 2 (2001), 171--186.
[22]
P. Hoff. 2009. Multiplicative latent factor models for description and prediction of social networks. Comput. Math. Organ. Theory 15, 4 (2009), 261--272.
[23]
T. N. Huynh and R. J. Mooney. 2008. Discriminative structure and parameter learning for Markov logic networks. In Proceedings of International Conference on Machine Learning (ICML). ACM, 416--423.
[24]
Y. Jacob, L. Denoyer, and P. Gallinari. 2014. Learning latent representations of nodes for classifying in heterogeneous social networks. In Proceedings of Conference on Web Search and Data Mining (WSDM). 373--382.
[25]
D. Jensen and J. Neville. 2002. Linkage and autocorrelation cause feature selection bias in relational learning. In Proceedings of International Conference on Machine Learning (ICML). 259--266.
[26]
D. Jensen, J. Neville, and B. Gallagher. 2004. Why collective inference improves relational classification. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 593--598.
[27]
A. Kimmig, L. Mihalkova, and L. Getoor. 2015. Lifted graphical models: A survey. Mach. Learn. 99, 1 (2015), 1--45.
[28]
S. Kok and P. Domingos. 2005. Learning the structure of Markov logic networks. In Proceedings of International Conference on Machine Learning (ICML). ACM, 441--448.
[29]
X. Kong, P. S. Yu, Y. Ding, and D. J. Wild. 2012. Meta path-based collective classification in heterogeneous information networks. In Proceedings of Conference on Information and Knowledge Management (CIKM). 1567--1571.
[30]
A. Kuwadekar and J. Neville. 2010. Combining semi-supervised learning and relational resampling for active learning in network domains. In Proceedings of the Budgeted Learning Workshop at International Conference on Machine Learning (ICML-2010).
[31]
A. Kuwadekar and J. Neville. 2011. Relational active learning for joint collective classification models. In Proceedings of International Conference on Machine Learning (ICML). 385--392.
[32]
J. Leskovec, D. Huttenlocher, and J. Kleinberg. 2010. Predicting positive and negative links in online social networks. In Proceedings of Conference on World Wide Web (WWW). 641--650.
[33]
D. Liben-Nowell and J. Kleinberg. 2007. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 7 (2007), 1019--1031.
[34]
F. Lin and W. W. Cohen. 2010. Semi-supervised classification of network data using very few labels. In Proceedings of Advances in Social Networks Analysis and Mining (ASONAM). 192--199.
[35]
Q. Lu and L. Getoor. 2003a. Link-based classification. In Proceedings of International Conference on Machine Learning (ICML). 496--503.
[36]
Q. Lu and L. Getoor. 2003b. Link-based classification using labeled and unlabeled data. In Proceedings of the International Conference on Machine Learning (ICML) Workshop on the Continuum from Labeled to Unlabeled Data.
[37]
S. Macskassy and F. Provost. 2007. Classification in networked data: A toolkit and a univariate case study. J. Mach. Learn. Res. 8 (May 2007), 935--983.
[38]
L. K. McDowell. 2015. Relational active learning for link-based classification. In Proceedings of Data Science and Advanced Analytics (DSAA). 1--10.
[39]
L. K. McDowell and D. W. Aha. 2012. Semi-supervised collective classification via hybrid label regularization. In Proceedings of International Conference on Machine Learning (ICML). 975--982.
[40]
L. K. McDowell and D. W. Aha. 2013. Labels or attributes? Rethinking the neighbors for collective classification in sparsely-labeled networks. In Proceedings of International Conference on Information and Knowledge Management (CIKM). 847--852.
[41]
L. K. McDowell, A. Fleming, and Z. Markel. 2015. Evaluating and extending latent methods for link-based classification. In Proceedings of the Advances in Intelligent Systems and Computing, Vol. 346. Springer International Publishing, 227--256.
[42]
L. K. McDowell, K. M. Gupta, and D. W. Aha. 2009. Cautious collective classification. J. Mach. Learn. Res. 10 (Dec. 2009), 2777--2836.
[43]
A. Menon and C. Elkan. 2010. Predicting labels for dyadic data. Data Min. Knowl. Discov. 21, 2 (2010), 327--343.
[44]
A. Menon and C. Elkan. 2011. Link prediction via matrix factorization. Proc. of ECML PKDD. 437--452.
[45]
K. Miller, T. Griffiths, and M. Jordan. 2009. Nonparametric latent feature models for link prediction. In Proceedings of the Advances in Neural Information Processing Systems (NIPS). 1276--1284.
[46]
G. Namata, S. Kok, and L. Getoor. 2011. Collective graph identification. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 87--95.
[47]
G. M. Namata, B. London, L. Getoor, and B. Huang. 2012. Query-driven active surveying for collective classification. In Proceedings of the 10th International Workshop on Mining and Learning with Graphs (MLG-2010).
[48]
M. Neumann, R. Garnett, and K. Kersting. 2013. Coinciding walk kernels: Parallel absorbing random walks for learning with graphs and few labels. In Proceedings of ACML. 357--372.
[49]
J. Neville and D. Jensen. 2000. Iterative classification in relational data. In Proceedings of the Workshop on Learning Statistical Models from Relational Data at Conference on Artificial Intelligence (AAAI-2000). 13--20.
[50]
J. Neville and D. Jensen. 2005. Leveraging relational autocorrelation with latent group models. In Proceedings of International Conference on Data Mining (ICDM). 170--177.
[51]
J. Neville and D. Jensen. 2007. Relational dependency networks. J. Mach. Learn. Res. 8 (March 2007), 653--692.
[52]
J. Neville and D. Jensen. 2008. A bias/variance decomposition for models using collective inference. Mach. Learn. J. 73, 1 (2008), 87--106.
[53]
J. Neville, D. Jensen, L. Friedland, and M. Hay. 2003b. Learning relational probability trees. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 625--630.
[54]
J. Neville, D. Jensen, and B. Gallagher. 2003a. Simple estimators for relational Bayesian classifiers. In Proceedings of International Conference on Data Mining Series (ICDM). 609--612.
[55]
J. J. Pfeiffer III, J. Neville, and P. N. Bennett. 2014a. Active exploration in networks: Using probabilistic relationships for learning and inference. In Proceedings of Conference on Information and Knowledge Management (CIKM). 639--648.
[56]
J. J. Pfeiffer III, J. Neville, and P. N. Bennett. 2014b. Composite likelihood data augmentation for within-network statistical relational learning. In Proceedings of International Conference on Data Mining (ICDM). 490--499.
[57]
J. J. Pfeiffer III, J. Neville, and P. N. Bennett. 2015. Overcoming relational learning biases to accurately predict preferences in large scale networks. In Proceedings of International Conference on World Wide Web (WWW). 853--863.
[58]
M. J. Rattigan, M. Maier, D. Jensen, B. Wu, X. Pei, J. Tan, and Y. Wang. 2007. Exploiting network structure for active inference in collective classification. In Proceedings of the Workshop on Mining Graphs and Complex Structures at International Conference on Data Mining (ICDM-2007). 429--434.
[59]
M. Richardson and P. Domingos. 2006. Markov logic networks. Mach. Learn. 62, 1--2 (2006), 107--136.
[60]
R. A. Rossi, L. K. McDowell, D. W. Aha, and J. Neville. 2012. Transforming graph data for statistical relational learning. J. Artif. Intell. Res. 45 (2012), 363--441.
[61]
T. Saha, H. Rangwala, and C. Domeniconi. 2014. FLIP: Active learning for relational network classification. In Proceedings of European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 1--18.
[62]
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi-Rad. 2008. Collective classification in network data. AI Mag. 29, 3 (2008), 93--106.
[63]
X. Shi, Y. Li, and P. Yu. 2011. Collective prediction with latent graphs. In Proceedings of Conference on Information and Knowledge Management (CIKM). 1127--1136.
[64]
P. Singla, A. Nath, and P. Domingos. 2014. Approximate lifting techniques for belief propagation. In Proceedings of Conference on Artificial Intelligence (AAAI). 2497--2504.
[65]
J. Tang and H. Liu. 2012. Unsupervised feature selection for linked social media data. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 904--912.
[66]
L. Tang and H. Liu. 2009. Relational learning via latent social dimensions. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 817--826.
[67]
L. Tang and H. Liu. 2011. Leveraging social media networks for classification. Data Min. Knowl. Discov. 23, 3 (2011), 447--478.
[68]
L. Tang, X. Wang, and H. Liu. 2011. Scalable learning of collective behavior. IEEE Trans. Knowl. Data Eng. 24, 6 (2011), 1080--1091.
[69]
B. Taskar, P. Abbeel, and D. Koller. 2002. Discriminative probalistic models for relational data. In Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI). 485--492.
[70]
B. Taskar, E. Segal, and D. Koller. 2001. Probabilistic classification and clustering in relational data. In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 870--878.
[71]
M. Torkamani and D. Lowd. 2013. Convex adversarial collective classification. In Proceedings of the 30th International Conference on Machine Learning (ICML). 642--650.
[72]
V. N. Vapnik. 1998. Statistical Learning Theory. Wiley, New York, NY.
[73]
F. Wang and C. Zhang. 2008. Label propagation through linear neighborhoods. IEEE Trans. Knowl. Data Eng. 20, 1 (2008), 55--67.
[74]
T. Wang, J. Neville, B. Gallagher, and T. Eliassi-Rad. 2011. Correcting bias in statistical tests for network classifier evaluation. In Proceedings of European Conference on Machine Learning (ECML). 506--521.
[75]
X. Wang and G. Sukthankar. 2013. Multi-label relational neighbor classification using social context features. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 464--472.
[76]
R. Xiang and J. Neville. 2008. Pseudolikelihood EM for within-network relational learning. In Proceedings of International Conference on Data Mining Series (ICDM). 1103--1108.
[77]
R. Xiang and J. Neville. 2011. Understanding propagation error and its effect on collective classification. In Proceedings of International Conference on Data Mining Series (ICDM). 834--843.
[78]
D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf. 2004. Learning with local and global consistency. In Proceedings of the Advances in Neural Information Processing Systems (NIPS). 321--328.
[79]
S. Zhu, K. Yu, Y. Chi, and Y. Gong. 2007. Combining content and link for classification using matrix factorization. In Proceedings of SIGIR. 487--494.
[80]
X. Zhu and Z. Ghahramani. 2002. Learning from Labeled and Unlabeled Data with Label Propagation. Technical Report CMU-CALD-02-107. Cargenie Mellon University.
[81]
X. Zhu, Z. Ghahramani, and J. D. Lafferty. 2003. Semi-supervised learning using Gaussian fields and harmonic functions. In Proceedings of International Conference on Machine Learning (ICML). 912--919.
[82]
Y. Zhu, X. Yan, L. Getoor, and C. Moore. 2013. Scalable text and link analysis with mixed-topic link models. In Proceedings of Conference on Knowledge Discovery and Data Mining (KDD). 473--481.
Index Terms
- Leveraging Neighbor Attributes for Classification in Sparsely Labeled Networks
Recommendations
Labels or attributes?: rethinking the neighbors for collective classification in sparsely-labeled networks
CIKM '13: Proceedings of the 22nd ACM international conference on Information & Knowledge ManagementMany classification tasks involve linked nodes, such as people connected by friendship links. For such networks, accuracy might be increased by including, for each node, the (a) labels or (b) attributes of neighboring nodes as model features. Recent ...
Leveraging label-independent features for classification in sparsely labeled networks: an empirical study
SNAKDD'08: Proceedings of the Second international conference on Advances in social network mining and analysisWe address the problem of within-network classification in sparsely labeled networks. Recent work has demonstrated success with statistical relational learning (SRL) and semi-supervised learning (SSL) on such problems. However, both approaches rely on ...
Using ghost edges for classification in sparsely labeled networks
KDD '08: Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data miningWe address the problem of classification in partially labeled networks (a.k.a. within-network classification) where observed class labels are sparse. Techniques for statistical relational learning have been shown to perform well on network ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2017
288 pages
Copyright © 2016 Public Domain.
This paper is authored by an employee(s) of the United States Government and is in the public domain. Non-exclusive copying or redistribution is allowed, provided that the article citation is given and the authors and agency are clearly identified as its source.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 20 July 2016
Accepted: 01 February 2016
Revised: 01 January 2016
Received: 01 November 2015
Published in TKDD Volume 11, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- ONR
- NSF
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 569Total Downloads
- Downloads (Last 12 months)41
- Downloads (Last 6 weeks)7
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
Cited By
View all- Li LChu YLiu GWu X(2019)Multi-Objective Optimization-Based Networked Multi-Label Active LearningJournal of Database Management10.4018/JDM.201904010130:2(1-26)Online publication date: 1-Apr-2019
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in