Robust Semi-Supervised Classification for Multi-Relational Graphs
This work addresses the challenge of handling multiple noisy graphs in semi-supervised learning, which is important for applications like social network analysis or bioinformatics, but it is incremental as it builds on existing graph-regularized methods.
The paper tackles the problem of multi-relational graph classification where noisy or irrelevant relations can degrade performance, proposing a robust method that infers graph weights and filters out uninformative graphs, achieving superior results compared to baselines and state-of-the-art approaches under various noise conditions.
Graph-regularized semi-supervised learning has been used effectively for classification when (i) instances are connected through a graph, and (ii) labeled data is scarce. If available, using multiple relations (or graphs) between the instances can improve the prediction performance. On the other hand, when these relations have varying levels of veracity and exhibit varying relevance for the task, very noisy and/or irrelevant relations may deteriorate the performance. As a result, an effective weighing scheme needs to be put in place. In this work, we propose a robust and scalable approach for multi-relational graph-regularized semi-supervised classification. Under a convex optimization scheme, we simultaneously infer weights for the multiple graphs as well as a solution. We provide a careful analysis of the inferred weights, based on which we devise an algorithm that filters out irrelevant and noisy graphs and produces weights proportional to the informativeness of the remaining graphs. Moreover, the proposed method is linearly scalable w.r.t. the number of edges in the union of the multiple graphs. Through extensive experiments we show that our method yields superior results under different noise models, and under increasing number of noisy graphs and intensity of noise, as compared to a list of baselines and state-of-the-art approaches.