Joint Learning of the Graph and the Data Representation for Graph-Based Semi-Supervised Learning (2020)

Abstract: Graph-based semi-supervised learning is appealing when labels are scarce but large amounts of unlabeled data are available. These methods typically use a heuristic strategy to construct the graph based on some fixed data representation, independently of the available labels. In this pa- per, we propose to jointly learn a data representation and a graph from both labeled and unlabeled data such that (i) the learned representation indirectly encodes the label information injected into the graph, and (ii) the graph provides a smooth topology with respect to the transformed data. Plugging the resulting graph and representation into existing graph-based semi-supervised learn- ing algorithms like label spreading and graph convolutional networks, we show that our approach outperforms standard graph construction methods on both synthetic data and real datasets.

## introduction an important bottleneck for the development of accurate natural language processing (nlp) tools for many applications and languages is the lack of annotated data. a natural remedy to this issue lies in semi-supervised learning (ssl) methods, which are able to leverage smaller labeled datasets in combination with large amounts of unannotated text data (which are often more easily available). in particular, graph-based ssl algorithms @xcite , among which variants of label propagation @xcite @xcite and more recently graph convolutional networks @xcite @xcite , have attracted a lot of attention due to their interesting theoretical properties and good empirical performance. they have successfully been applied to several nlp problems, such as sentiment analysis @xcite , word sense disambiguation @xcite ), text categorization @xcite , pos tagging @xcite , semantic parsing @xcite , machine translation @xcite , or lexicon induction @xcite . as their name suggests, graph-based ssl methods represent all data points (that is, labeled and unlabeled) as nodes in a graph with weighted edges encoding the similarity between pairs of points. this graph is then used as a propagation operator to transfer labels from labeled to unlabeled points. despite differences in the way this propagation is achieved, graph-based ssl approaches all rely on two assumptions: (i) the graph representing the data provides a faithful approximation of the manifold on which the data actually live, and (ii) the underlying labels are smooth with respect to this manifold. in many nlp problems, there is often no a priori-known graph, which raises the question of how to best construct this graph over the dataset given some data representation. most existing work rely on classic graph construction heuristics such as k-nn graphs, -graphs or radial kernel graphs @xcite , which may poorly adapt to the intrinsic structure of the data manifold and hence violate assumption (i). more recently, in the machine learning and signal processing communities, some algorithms were proposed to learn more flexible graphs by enforcing the topology to be smooth with respect to the input data @xcite @xcite . all these approaches this work is licensed under a creative commons attribution 4.0 international license. license details: http:// creativecommons.org/licenses/by/4.0/ . in this paper, we propose an original semi-supervised algorithm for graph construction that adapts to both the data and the predictive task. specifically, our approach leverages the labeled and unlabeled data to jointly learn a graph and a data representation. on the one hand, the graph is learned to provide a smooth topology with respect to the learned representation. on the other hand, the representation should bring closer (labeled and unlabeled) points that are neighbors in the graph as well as similarly labeled points, while pulling away points of different labels. a key feature of our approach is that the learned representation indirectly encodes and injects label information into the graph beyond the labeled points alone. we formulate our problem as a joint optimization problem over the representation and the graph weights, with a hyperparameter to easily control the sparsity of the resulting graph and thereby obtain a good approximation of the underlying manifold. we discuss some appropriate parameterizations for learning the representation, which revolve around adapting pre-trained embeddings so as to avoid overfitting. we then propose to solve our joint problem by alternating optimization on the representation and the graph. we validate our approach through several graph-based ssl experiments using label spreading @xcite and graph convolutional networks (gcn) (kipf and welling, 2017), both on synthetic and real text classification datasets. incidentally, note that our approach is generic and could in principle be used in combination with any existing graph-based ssl framework. the results show that our approach outperforms previous methods which rely on heuristic graphs, generally by a considerable margin. interestingly, we also observe that our approach effectively bridges the accuracy gap between a simple method like label spreading and a richer neural-based approach like gcn. the rest of this paper is organized as follows. we introduce some notations and discuss the related work in section 2. we then describe our approach and algorithm in section 3. our experimental results are presented in section 4, and we conclude with future work directions in section 5. ## notations and related work our work lies in the intersection of two topics: graph-based semi-supervised learning and graph learning. in this section, we start by introducing some useful notations. we then briefly review some related work in both areas. ## proposed model our approach learns a graph and a data representation for use in downstream graph-based ssl algorithms. in this section, we start by introducing our formulation as a joint optimization problem over the representation and the graph. we then discuss some relevant choices for the parameterization of the learned representation, and finally present our alternating optimization scheme. ## experiments in this section, we study the practical behavior of our method by comparing the accuracy of downstream graph-based ssl algorithms when the graph (along with the underlying representation) is learned with our approach ( ours) rather than constructed with the following baseline strategies: in all cases the graph is constructed over the union of labeled (train set) and unlabeled data (validation and test sets). for experiments with our method, the learned representation is a linear transformation of the initial features as explained in section 3.2. we perform experiments with two graph-based ssl approaches: label spreading (ls) @xcite and the graph convolutional network (gcn) method of @xcite . we used the scikit-learn @xcite implementation of ls. for gcn, we used the tensorflow implementation provided by the authors 2 and follow the recommended architecture: to illustrate the behavior of our approach, we first present some experiments on synthetic data. we then show some results on real text classification datasets. ## discussion and future work we presented a novel method bringing together graph learning, representation learning and ssl by jointly inferring the graph and the representation from semi-supervised data. the output of our approach can then be plugged into any graph-based ssl algorithm in place of using common graph constructions. our experimental results suggest that the gains are especially significant for graph-based ssl algorithms that are unable to adapt the data representation (like label spreading and its variants), although we observe some gains also for gcn. to further improve the performance with richer models like gcns, a promising direction is to extend our approach to learn the graph, the representation and the classifier in an end-toend manner. we note that there has been very recent attempts in this general direction @xcite , though specific to gcn and with completely different modeling and assumptions. the ideas underlying our approach could also be useful to tackle transfer learning settings and in particular domain adaptation @xcite . the latter can be seen as a ssl problem where the distribution of the target (unlabeled) data follows a different distribution that the source (training) data. our objective function could be modified to encourage the learned representation and graph to serve as a "bridge" between the source and target distributions.