The key challenge in semi-supervised learning is how to effectively leverage unlabeled data to improve learning performance. The classical label propagation method, despite its popularity, has limited modeling capability in that it only exploits graph information for making predictions. In this paper, we consider label propagation from a graph signal processing perspective and decompose it into three components: signal, filter, and classifier. By extending the three components, we propose a simple generalized label propagation (GLP) framework for semi-supervised learning. GLP naturally integrates graph and data feature information, and offers the flexibility of selecting appropriate filters and domain-specific classifiers for different applications. Interestingly, GLP also provides new insight into the popular graph convolutional network and elucidates its working mechanisms. Extensive experiments on three citation networks, one knowledge graph, and one image dataset demonstrate the efficiency and effectiveness of GLP. The success of deep learning and neural networks comes at the cost of large amount of training data and long training time. Semi-supervised learning BID37 BID8 ) is interesting and important as it can leverage ample available unlabeled data to aid supervised learning, thus greatly saving the cost, trouble, and time for human labeling. Many researches have shown that when used properly, unlabeled data can significantly improve learning performance BID38 BID16 . The key challenge for semi-supervised learning is how to effectively leverage the information of unlabeled data, such as graph structures and data features.Label propagation BID39 BID36 BID2 is arguably the most popular method for graph-based semi-supervised learning. As a simple and effective tool, it has been widely used in many scientific research fields and has found numerous industrial applications. Given a non-oriented graph G = (V, W, X) with n = |V| vertices, a nonnegative symmetric affinity matrix W ∈ R n×n + encoding edge weights, and a feature matrix X ∈ R n×m which contains an mdimensional feature vector of each vertex. For semi-supervised classification, only a small subset of vertices are labeled, and the goal is to predict the labels of other vertices. Denote by Y ∈ {0, 1} n×l the labeling matrix 1 with l being the number of classes. The objective of of label propagation (LP) is to find a prediction (embedding) matrix Z ∈ R n×l which agrees with Y while being smooth on the graph such that nearby vertices have similar embeddings: DISPLAYFORM0 where α is a balancing parameter, L = D − W is the graph Laplacian 2 and D is the degree matrix. The term enforcing smoothness is called graph Laplacian regularization or Tikhonov regularization. Solving the quadratic regularization framework gives the prediction of LP.As LP makes predictions only based on graph information (W ), its performance depends on whether the underlying graph structure can well represent the class information of data -vertices in the same 1 If the label of vertex vi is known, then Y (i, :) is a one-hot embedding of vi with yij = 1 if vi belongs to the j-th class and yij = 0 otherwise. If the label of vertex vi is not given, then Y (i, :) is a vector of all zeros.2 Other variants such as the normalized Laplacian matrices are also applicable.cluster tend to have same labels. For some applications such as social network analysis, data exhibits a natural graph structure. For some other applications such as image or text classification, data may come in a vector form, and a graph is usually constructed using data features. Nevertheless, in many cases, graphs only partially encode data information. Take document classification in a citation network as an example, the citation links between documents form a graph which represents their citation relation, and each document is represented as a bag-of-words feature vector which describes its content. To correctly classify a document, both the citation relations (W ) and the content information (X) need to be taken into account, as they contain different aspects of document information. However, in this case, LP can only exploit the graph information to make predictions without using any of the feature information, thus resulting in poor performance.To go beyond the limit of LP and jointly model graph and feature information, a common approach is to train a supervised learner to classify data features while regularizing the classifier using graph information. Manifold regularization BID1 trains a support vector machine with a graph Laplacian regularizer. Deep semi-supervised embedding BID32 and Planetoid BID34 ) train a neural network with an embedding-based regularizer. The recently proposed graph convolutional neural networks BID16 ) adopts a different approach by integrating graph and feature information in each of its convolutional layer, which is coupled with a projection layer for classification.In this paper, we extends the modeling capability of LP in the context of graph signal processing. Casted in the spectral domain, LP can be interpreted as low-pass graph filtering BID10 BID11 . In light of this, we decompose LP into three components: graph signal, graph filter, and classifier. By naturally extending the three components, we propose a generalized label propagation (GLP) framework for semi-supervised learning. In GLP, a low-pass graph filter is applied on vertex features to produce smooth features, which are then fed to a supervised learner for classification. After filtering, the data features within each class are more similar and representative, making it possible to train a good classifier with few labeled examples.GLP not only extends LP to incorporate vertex features in a simple way, but also offers the flexibility of designing appropriate graph filters and adopting domain-specific classifiers for different semisupervised applications. The popular graph convolutional networks (GCN) BID16 is closely related to GLP. In fact, GCN without internal ReLUs is a special case of GLP with a certain graph filter and a multilayer perceptron classifier. When revisited under the GLP framework, it makes clear the working mechanisms of GCN including its design of convolutional filter and model parameter setting. Extensive experiments on citation networks, knowledge graphs, and image datasets show substantial improvement of GLP over GCN and other baselines for semi-supervised classification, confirming the effectiveness of this simple and flexible framework.The rest of the paper is organized as follows. Section 2 interprets LP in the context of graph signal processing. Section 3 presents the proposed GLP framework. Section 4 revisits GCN under GLP. Section 5 discusses the design of graph filters for GLP. Section 6 presents experimental results. Section 7 discusses related works. Finally, section 8 concludes the paper. In this paper, we have proposed a simple, flexible, and efficient framework GLP for semi-supervised learning, and demonstrated its effectiveness theoretically and empirically. GLP offers new insights into existing methods and opens up possible avenues for new methods. An important direction for future research is the design and selection of graph filters for GLP in different application scenarios.Other directions include making GLP readily applicable to inductive problems, developing faster algorithms for GLP, and applying GLP to solve large-scale real-world problems.
We extend the classical label propation methods to jointly model graph and feature information from a graph filtering perspective, and show connections to the graph convlutional networks.
{"src": "scitldr-AIC_train", "paper_id": "SygjB3AcYX"}