In this work we propose a novel approach for learning graph representation of the data using gradients obtained via backpropagation. Next we build a neural network architecture compatible with our optimization approach and motivated by graph filtering in the vertex domain. We demonstrate that the learned graph has richer structure than often used nearest neighbors graphs constructed based on features similarity. Our experiments demonstrate that we can improve prediction quality for several convolution on graphs architectures, while others appeared to be insensitive to the input graph. Recently we have seen a rise in deep learning models, which can account for non-linearities and fit a wide range of functions. Multilayer perceptron (MLP), a general purpose neural network, is a powerful predictor, but requires too many parameters to be estimated and often faces the problem of over-fitting, i.e. learns to almost exactly match training data and unable to generalize when it comes to testing.While MLPs treat all features equally, which partially is the cause of excessive number of parameters, Convolutional Neural Networks (CNNs) have significantly fewer parameters and demonstrate groundbreaking results when it comes to object recognition in images BID11 . The parameter reduction is due to utilizing convolutional operation: a window is sliding through the image and applying same linear transformation of the pixels. The number of parameters then is proportional to the size of the window rather than polynomial of the number of data features as in the case of the MLPs.Indeed images posses a specific structure, which can be encoded as a lattice graph, that makes the sliding window procedure meaningful, but inapplicable outside of the image domain. In recent years there have been multiple works (cf. Bronstein et al. (2017) for an overview) on generalizing convolution operation to a general domain, where graph is not a lattice. Citing BID3 -"classification performance critically depends on the quality of the graph", nonetheless the problem of learning the graph useful for prediction has not been addressed so far and the graph was either known or pre-estimated only based on feature similarity in all of the prior work.There are two major challenges when estimating the graph inside the neural network architecture. First is the architecture itself -majority of the neural networks rely on gradient optimization methods, but the graph is often used in such ways that it is not possible to obtain its gradient. In Section 3 we define a novel neural network architecture which is differentiable with respect to the graph adjacency matrix and built upon graph filtering in the vertex domain, extending the linear polynomial filters of BID20 . Second problem is the series of constraints that are often imposed on the graph and therefore its adjacency. In Section 2 we show how the three common graph properties, undirected sparse edges with positive weights, can be enforced by only utilizing the gradient obtained through backpropagation, therefore allowing us to utilize any of the modern deep learning libraries for graph estimation. In Section 4 we discuss other graph based neural networks and evaluate them from the perspective of graph estimation. In Section 5 we analyze graph estimation and interpretation for text categorization and time series forecasting. We conclude with a discussion in Section 6 2 GRAPH OPTIMIZATION BASED ON BACKPROPAGATION In this section we provide an optimization procedure for learning adjacency matrix of a graph with various properties of interest, assuming that we can obtain its derivative via backpropagation. In a subsequent section we will present novel neural network architecture that will allow us to get the derivative and utilize the graph in meaningful way.Let data X ∈ R N ×D with N observation, D features and response Y ∈ R (or Y ∈ N for classification). Graph G among data features can be encoded as its adjacency matrix A ∈ R D×D . Our goal is to estimate functionŶ := f W (X, A), where W are weight parameters, that minimize some loss L := L(Ŷ , Y ). We assume that we are able to evaluate partial derivative ∂L ∂A . In the most general case, when edges of G can be directed, have negative weights and G can be fully connected, we perform the update A := A − γG ∂L ∂A , where G(·) depends on the optimizer (e.g., identity function for vanilla gradient descent) and γ is the step size. Nonetheless, in the majority of the applications, G is desired to have some (or all) of the following properties:• Undirected graph, in which case A is restricted to be symmetric.• Have Positive edge weights, in which case A ∈ R D×D + .• Be Sparsely connected, in which case A should contain small proportion of non-zero entries.First two properties are necessary for the existence of the graph Laplacian, crucial for the vast amount of neural networks on graphs architectures (e.g., BID2 ; BID8 ; BID3 ). Third property greatly reduces computational complexity, helps to avoid overfitting and improves interpretability of the learned graph. We proceed to present the Undirected Positive Sparse UPS optimizer, that can deliver each of the three properties and can be easily implemented as part of modern deep learning libraries.Remark When node classification is of interest, our approach can be applied to graph between observations (e.g. social networks), then A ∈ R N ×N .
Graph Optimization with signal filtering in the vertex domain. The paper investigates learning adjacency matrix of a graph with sparsely connected undirected graph with nonnegative edge weights uses a projected sub-gradient descent algorithm. Develops a novel scheme for backpropogating on the adjacency matrix of a neural network graph