Graph-based Text Classification: Learn from Your Neighbors

Abstract

Automatic classification of data items, based on training samples, \ncan be boosted by considering the neighborhood of data items in \na graph structure (e.g., neighboring documents in a hyperlink environment \nor co-authors and their publications for bibliographic data entries). \nThis paper presents a new method for graph-based classification, \nwith particular emphasis on hyperlinked text documents but broader \napplicability. Our approach is based on iterative relaxation labeling and can \nbe \ncombined with either Bayesian or SVM classifiers on the feature spaces \nof the given data items. The graph neighborhood is taken into consideration \nto exploit locality patterns while at the same time avoiding overfitting. \nIn contrast to prior work along these lines, our approach employs a number \nof novel techniques: dynamically inferring the link/class pattern in the graph\nin the run of the iterative relaxation labeling, \njudicious pruning of edges from the neighborhood graph \nbased on node dissimilarities and node degrees, weighting the influence of \nedges based on \na distance metric between the classification labels of interest \nand weighting edges by content similarity measures. Our techniques considerably \nimprove the robustness and accuracy of the classification outcome, as shown in \nsystematic experimental comparisons with previously published methods on three \ndifferent real-world datasets.