Classification using link prediction

doi:10.1016/j.neucom.2019.06.026

Return

Classification using link prediction

2019-09-01

Seyed Amin Fadaee

Maryam Amir Haeri *

DOI：10.1016/j.neucom.2019.06.026

Original

Save

View PDF

Abstract

En 中文

Link prediction in a graph is the problem of detecting the missing links or the ones that would be formed in the near future. Using a graph representation of the data, we can convert the problem of classification to the problem of link prediction which aims at finding the missing links between the unlabeled data (unlabeled nodes) and their classes. To our knowledge, despite the fact that numerous algorithms use the graph representation of the data for classification, none are using link prediction as the heart of their classifying procedure. In this work, we propose a novel algorithm called CULP (Classification Using Link Prediction) which uses a new structure namely Label Embedded Graph or LEG and a link predictor to find the class of the unlabeled data. Different link predictors along with Compatibility Score - a new link predictor we proposed that is designed specifically for our settings - has been used and showed promising results for classifying different datasets. This paper further improved CULP by designing an extension called CULM which uses a majority vote (hence the M in the acronym) procedure with weights proportional to the prediction's confidences to use the predictive power of multiple link predictors and also exploits the low level features of the data. Extensive experimental evaluations shows that both CULP and CULM are highly accurate and competitive with the cutting edge graph classifiers and general classifiers. (C) 2019 Elsevier B.V. All rights reserved.

Keywords:

Classification

Link prediction

Graph representation

Local similarity measure

Similarity-based techniques

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.