Toward Effective and Efficient Graph Neural Networks with Implicit Layers
Abstract:
Graph-structured data are ubiquitous in the real world, such as social networks, e-commerce recommendation, financial transaction networks, and molecular interaction networks. For modelling graph data, Graph neural networks (GNNs) are widely used in numerous applications. However, existing GNNs are not satisfactory in terms of effectiveness in different scenarios and applications. Meanwhile, they can also be inefficient regarding memory usage. In this thesis, we aim to propose new GNN models for improving effectiveness and efficiency.
Typical GNNs usually have a number of aggregation layers defined explicitly (i.e., explicit layers). However, with their inherently finite aggregation layers, these GNN models may not be able to effectively capture long-range dependencies in the underlying graphs. Additionally, existing GNNs require storing all hidden states at each layer, which demands a lot of GPU memory when the number of layers increases for capturing long-range dependencies. It leads to memory inefficiency. Motivated by these limitations regarding effectiveness and memory efficiency, we propose a GNN model with infinite depth, which we call Efficient Infinite-Depth Graph Neural Networks (EIGNN), to efficiently capture very long-range dependencies. EIGNN can be viewed as a GNN model with infinite layers defined implicitly (i.e., implicit layers). We theoretically derive a closed-form solution of EIGNN which makes training an infinite-depth GNN model tractable. We then further show that we can achieve more efficient computation for training EIGNN by using eigendecomposition. The empirical results of comprehensive experiments on synthetic and real-world datasets show that EIGNN is more effective than recent baselines (i.e., has a better ability to capture long-range dependencies), and consistently achieves state-of-the-art performance. Furthermore, we show that our model is also more robust against both noise and adversarial perturbations on node features.
In the second work, we introduce two limitations of EIGNN and previous implicit GNNs: the constrained expressiveness due to their limited effective range for capturing long-range dependencies, and their lack of ability to capture multiscale information on graphs at multiple resolutions. To show the limited effective range of previous implicit GNNs, we first provide a theoretical analysis and point out the intrinsic relationship between the effective range and the convergence of iterative equations used in these models. To mitigate the mentioned limitations and further improve the effectiveness, we propose a multiscale graph neural network with implicit layers (MGNNI) which is able to model multiscale structures on graphs and has an expanded effective range for capturing long-range dependencies. We conduct comprehensive experiments for node and graph classification to show that MGNNI outperforms representative baselines and is more effective with a better ability for multiscale modeling and capturing long-range dependencies.
Lastly, we focus on making implicit GNNs able to be trained on large graphs. Despite the advantages of memory efficiency and the better ability to capture long-range dependencies, existing implicit GNNs still have some limitations such as scalability and training efficiency issues on large graphs. Specifically, previous implicit GNNs usually rely on full-batch training and require a large number of iterations to get the equilibrium, which makes them unfeasible to work on large graphs. Motivated by these limitations, in our third work, we propose a new implicit GNN with minibatch training and an unbiased solver to enable efficient training on large graphs. The experiments show that our model outperforms representative baselines with less training time, compared to other implicit GNNs.