  Semi-supervised learning on graph structured data has received significant
attention with the recent introduction of Graph Convolution Networks (GCN).
While traditional methods have focused on optimizing a loss augmented with
Laplacian regularization framework, GCNs perform an implicit Laplacian type
regularization to capture local graph structure. In this work, we propose
Lovasz Convolutional Network (LCNs) which are capable of incorporating global
graph properties. LCNs achieve this by utilizing Lovasz's orthonormal
embeddings of the nodes. We analyse local and global properties of graphs and
demonstrate settings where LCNs tend to work better than GCNs. We validate the
proposed method on standard random graph models such as stochastic block models
(SBM) and certain community structure based graphs where LCNs outperform GCNs
and learn more intuitive embeddings. We also perform extensive binary and
multi-class classification experiments on real world datasets to demonstrate
LCN's effectiveness. In addition to simple graphs, we also demonstrate the use
of LCNs on hyper-graphs by identifying settings where they are expected to work
better than GCNs.
