Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks

2020/10/26 by Hao Tang, Zhiao Huang, Tang, Hao +7
Computer Science · #Advanced Graph Neural Networks #Advanced Neural Network Applications #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2010.13547

openalex publication_date 2020/10/26 · openalex created_date 2020/10/29 · openalex updated_date 2026/07/28

Abstract

Current graph neural networks (GNNs) lack generalizability with respect to scales (graph sizes, graph diameters, edge weights, etc..) when solving many graph analysis problems. Taking the perspective of synthesizing graph theory programs, we propose several extensions to address the issue. First, inspired by the dependency of the iteration number of common graph theory algorithms on graph size, we learn to terminate the message passing process in GNNs adaptively according to the computation progress. Second, inspired by the fact that many graph theory algorithms are homogeneous with respect to graph weights, we introduce homogeneous transformation layers that are universal homogeneous function approximators, to convert ordinary GNNs to be homogeneous. Experimentally, we show that our GNN can be trained from small-scale graphs but generalize well to large-scale graphs for a number of basic graph theory problems. It also shows generalizability for applications of multi-body physical simulation and image-based navigation problems.

Citations

• The quickhull algorithm for convex hulls
• A note on two problems in connexion with graphs
• Adaptive Computation Time for Recurrent Neural Networks
• Attentional Pooling for Action Recognition
• Learning a SAT Solver from Single-Bit Supervision
• Graph networks as learnable physics engines for inference and control
• Graph Neural Networks: A Review of Methods and Applications
• LanczosNet: Multi-Scale Deep Graph Convolutional Networks
• Relational Pooling for Graph Representations
• Graph Neural Networks for Social Recommendation
• Graph Neural Ordinary Differential Equations
• Variational Inference: A Review for Statisticians
• A Comprehensive Survey on Graph Neural Networks

Related

• Scale Invariance of Graph Neural Networks
• Local-to-global Perspectives on Graph Neural Networks
• Introduction to Graph Neural Networks: A Starting Point for Machine Learning Engineers
• Transferability Properties of Graph Neural Networks
• Deep Iterative and Adaptive Learning for Graph Neural Networks