Phase transitions and optimal algorithms for semi-supervised classifications on graphs: from belief propagation to graph convolution network

Published on Nov 1, 2019in arXiv: Statistical Mechanics
· DOI :10.1103/PHYSREVRESEARCH.2.033325
Pengfei Zhou1
Estimated H-index: 1
,
Tianyi Li1
Estimated H-index: 1
,
Pan Zhang17
Estimated H-index: 17
(CAS: Chinese Academy of Sciences)
Sources
Abstract
We perform theoretical and algorithmic studies for the problem of clustering and semi-supervised classification on graphs with both pairwise relational information and single-point feature information, upon a joint stochastic block model for generating synthetic graphs with both edges and node features. Asymptotically exact analysis based on the Bayesian inference of the underlying model are conducted, using the cavity method in statistical physics. Theoretically, we identify a phase transition of the generative model, which puts fundamental limits on the ability of all possible algorithms in the clustering task of the underlying model. Algorithmically, we propose a belief propagation algorithm that is asymptotically optimal on the generative model, and can be further extended to a belief propagation graph convolution neural network (BPGCN) for semi-supervised classification on graphs. For the first time, well-controlled benchmark datasets with asymptotially exact properties and optimal solutions could be produced for the evaluation of graph convolution neural networks, and for the theoretical understanding of their strengths and weaknesses. In particular, on these synthetic benchmark networks we observe that existing graph convolution neural networks are subject to an sparsity issue and an ovefitting issue in practice, both of which are successfully overcome by our BPGCN. Moreover, when combined with classic neural network methods, BPGCN yields extraordinary classification performances on some real-world datasets that have never been achieved before.
📖 Papers frequently viewed together
26 Citations
2019AAAI: National Conference on Artificial Intelligence
61 Citations
9 Citations
References42
Newest
We introduce PyTorch Geometric, a library for deep learning on irregularly structured input data such as graphs, point clouds and manifolds, built upon PyTorch. In addition to general graph data structures and processing methods, it contains a variety of recently published methods from the domains of relational learning and 3D data processing. PyTorch Geometric achieves high data throughput by leveraging sparse GPU acceleration, by providing dedicated CUDA kernels and by introducing efficient mi...
833 Citations
Feb 19, 2019 in ICML (International Conference on Machine Learning)
#2Tianyi Zhang (Cornell University)H-Index: 8
319 Citations
#1Johannes KlicperaH-Index: 10
Last. Stephan GünnemannH-Index: 38
view all 3 authors...
Neural message passing algorithms for semi-supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construc...
25 Citations
#1Peter W. BattagliaH-Index: 36
#2Jessica B. HamrickH-Index: 16
Last. Razvan PascanuH-Index: 63
view all 27 authors...
Artificial intelligence (AI) has undergone a renaissance recently, making major progress in key domains such as vision, language, control, and decision-making. This has been due, in part, to cheap data and cheap compute resources, which have fit the natural strengths of deep learning. However, many defining characteristics of human intelligence, which developed under much different pressures, remain out of reach for current approaches. In particular, generalizing beyond one's experiences--a hall...
1,075 Citations
Feb 15, 2018 in ICLR (International Conference on Learning Representations)
#1Petar Veličković (University of Cambridge)H-Index: 15
#2Guillem Cucurull (Autonomous University of Barcelona)H-Index: 11
Last. Yoshua Bengio (UdeM: Université de Montréal)H-Index: 192
view all 6 authors...
We present graph attention networks (GATs), novel neural network architectures that operate on graph-structured data, leveraging masked self-attentional layers to address the shortcomings of prior methods based on graph convolutions or their approximations. By stacking layers in which nodes are able to attend over their neighborhoods' features, we enable (implicitly) specifying different weights to different nodes in a neighborhood, without requiring any kind of costly matrix operation (such as ...
3,093 CitationsSource
Last. Vladimir V. Mazalov (RAS: Russian Academy of Sciences)H-Index: 13
view all 3 authors...
The paper is devoted to game-theoretic methods for community detection in networks. The traditional methods for detecting community structure are based on selecting denser subgraphs inside the network. Here we propose to use the methods of cooperative game theory that highlight not only the link density but also the mechanisms of cluster formation. Specifically, we suggest two approaches from cooperative game theory: the first approach is based on the Myerson value, whereas the second approach i...
1,148 CitationsSource
Jun 12, 2017 in NeurIPS (Neural Information Processing Systems)
#1Ashish Vaswani (Google)H-Index: 28
#2Noam Shazeer (Google)H-Index: 30
Last. Illia Polosukhin (Google)H-Index: 8
view all 8 authors...
The dominant sequence transduction models are based on complex recurrent or convolutional neural networks that include an encoder and a decoder. The best performing models also connect the encoder and decoder through an attention mechanism. We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely. Experiments on two machine translation tasks show these models to be superior in quality while being mor...
19.2k Citations
Apr 4, 2017 in ICML (International Conference on Machine Learning)
#1Justin Gilmer (Google)H-Index: 24
#2Samuel S. Schoenholz (Google)H-Index: 30
Last. George E. Dahl (Google)H-Index: 32
view all 5 authors...
Supervised learning on molecules has incredible potential to be useful in chemistry, drug discovery, and materials science. Luckily, several promising and closely related neural network models invariant to molecular symmetries have already been described in the literature. These models learn a message passing algorithm and aggregation procedure to compute a function of their entire input graph. At this point, the next step is to find a particularly effective variant of this general approach and ...
1,166 Citations
#1Darko Hric (Aalto University)H-Index: 4
#2Tiago P. Peixoto (University of Bath)H-Index: 23
Last. Santo Fortunato (Aalto University)H-Index: 57
view all 3 authors...
The empirical validation of community detection methods is often based on available annotations on the nodes that serve as putative indicators of the large-scale network structure. Most often, the suitability of the annotations as topological descriptors itself is not assessed, and without this it is not possible to ultimately distinguish between actual shortcomings of the community detection algorithms, on one hand, and the incompleteness, inaccuracy, or structured nature of the data annotation...
54 CitationsSource
Jun 19, 2016 in ICML (International Conference on Machine Learning)
#1Zhilin Yang (CMU: Carnegie Mellon University)H-Index: 30
#2William W. Cohen (CMU: Carnegie Mellon University)H-Index: 86
Last. Ruslan Salakhutdinov (CMU: Carnegie Mellon University)H-Index: 96
view all 3 authors...
We present a semi-supervised learning framework based on graph embeddings. Given a graph between instances, we train an embedding for each instance to jointly predict the class label and the neighborhood context in the graph. We develop both transductive and inductive variants of our method. In the transductive variant of our method, the class labels are determined by both the learned embeddings and input feature vectors, while in the inductive variant, the embeddings are defined as a parametric...
587 Citations
Cited By0
Newest
Based on the SEIR model and the modeling of urban transportation networks, a general-purpose simulator for the spread of epidemics in Chinese cities is built. The Chinese public transportation system between over 340 prefectural-level cities is modeled as a multi-layer bi-partite network, with layers representing different means of transportation (airlines, railways, sail routes and buses), and nodes divided into two categories (central cities, peripheral cities). At each city, an open-system SE...
7 CitationsSource