Graph-to-Graph Transfer in Geometric Deep Learning

ABOUT THE PROJECT

At a glance

The term “geometric deep learning” [1] has been coined to describe deep neural networks that operate on data from non-Euclidean, non-grid domains such as general graphs. One recognized problem in graph neural network learning has been the generalization of learning “across domains” [1] - that is, applying deep learners trained with data on one graph to (qualitatively similar) data from a different graph. Our proposed project represents, to the best of our knowledge, the first study focusing on quantifying the ability of geometric deep learning to learn across graph domains, as well as the first application of graph-to-graph transfer in transportation networks. 

The graph-to-graph transfer problem is particularly relevant when dealing with road networks – since traffic data are generated by car-to-car and car-to-infrastructure (i.e., stoplights) interactions, we should expect that traffic data should be roughly similar for two different network topologies if they share the same rules of the road. Geometric deep learning has proven to be applicable to traffic data, with graph-specific neural network architectures outperforming naive “dense” architectures with similar amounts of parameters (e.g., [7]). Put another way, the cross-graph generalization problem acts as a major barrier towards unlocking the full potential of deep learning with cross-network “big” data in transportation settings. 

Beyond traffic data, geometric deep learning on graphs has been applied to obtain state-of-the-art results in the contexts of social network analysis [4], document/citation networks [8], and protein-protein interaction prediction [9].

Our proposed project is a quantitative and qualitative study of graph-to-graph transfer in geometric deep learning in traffic data and code and methodologies for performing these studies. Traffic data’s known cross-graph consistency provides a useful setting to study this problem. Understanding the usefulness of cross-graph learning has immediate applicability in the transportation domain for tasks that depend on the state of the road network like traffic state estimation and prediction, as well as fleet coordination. Cross-graph transfer is, of course, applicable to data in many fields where some graph structure is apparent, such as the aforementioned social and documentation network and biological applications. 

In the following section, we review some of the mathematical background, and describe some of the knowledge gaps we propose to address. We request $100K of funding to support one graduate student for the next academic year. This proposal falls under the following categories: “advanced machine learning for autonomous driving” and “functionality and applications for automated driving.”

Mathematical Background and Related Work
A recent literature review in graph neural network learning [9] proposed a breakdown of graph neural network approaches into two classes: spectral-based and non-spectral-based. Spectral approaches ([2, 3, 5], etc.) define the graph neural network layer in the graph Fourier domain, which uses an eigendecomposition of the graph Laplacian. The learned featurizations in the neural network are then functions of the graph’s spectral structure. These learned features are usually regularized to operate in small neighborhoods around each node, but still assume a consistent eigenbasis of all datapoints, which mean that learned information cannot be directly applied between graphs.

Non-spectral approaches (e.g., [4, 9], and our own current work) operate in the node-and-edge basis explicitly (this is more similar to the approach of most traditional CNNs, which perform their convolution operations in the pixel basis rather than a transform basis). These approaches learn node-local embeddings as functions of each node’s input features, and those of the nodes in its neighborhood.

In [9], their proposed (non-spectral) methodology achieved state-of-the-art performance on an inductive learning task, where protein-protein interactions graphs are predicted, but the test dataset is made of graphs that were completely unobserved during training time. To our knowledge, though, questions relating to deeper quantitative understanding of the mechanisms of graph-to-graph transfer (how many training graphs are needed to achieve transfer; how poorly do transferred learners perform compared to learners trained on the test domain; etc.), have not been studied. As mentioned, this sort of knowledge is crucial to designing best practices for cross-graph deep learning.

Research Questions
We propose two guiding research questions:
1. What are the quantified gains from cross-graph learning in a transportation setting (and more generally)? As mentioned above, we see the use of graph-to-graph transfer in transportation networks as key to unlocking the potential of “big data” learning in transportation networks. We hypothesize that knowledge gained from observing local spatiotemporal features in one road network should be transferable to other road networks. As such, we will perform experiments that use the aforementioned non-spectral graph approaches to aggregate data from multiple graphs, and quantify their performance on new data or new graphs entirely. We will begin with supervised-learning-based experiments (e.g., predicting and estimating unobserved queues from observed speed measurements as in our current work), and foresee the extension into reinforcement-learning-based settings with traffic light and/or autonomous vehicle control. To our knowledge, no prior graph-based transfer applications have been studied for reinforcement learning.
2. Can localized learned spectral representations be transferred? As mentioned in the previous section, spectral graph neural network approaches make assumptions on the eigenbasis of the underlying graph. However, in practice, these approaches only approximate the eigenbasis and learned filters, and enforce a spatial locality (as is done explicitly in the non-spectral approaches). Despite this, potential cross-graph application of these localized spectral features has, to the best of our knowledge, not been studied. There is an intuition to believe that these localized spectral approaches may still integrate information across an entire graph through use of the eigenbasis (in other words, aggregation is done in the “forward pass” of computing the (approximate) Fourier transform of the data, in addition to the “backward pass” of batch-averaging the gradient direction). We will study potential methods for transfer here to boost or accelerate learning.

Research Approach
We will make use of the open-source traffic simulator SUMO (Simulation of Urban MObility)[6]. SUMO is a “microscopic” traffic simulator that models individual vehicles’ driving behavior on a specified road network, and is widely-used by researchers in transportation science, for network control applications, and for deep learning research. It also serves as the core component in a (MIT-licensed) multiagent reinforcement learning framework for study of coordinated autonomous vehicles recently developed by Professor Bayen’s lab [10].

Our current project has resulting in methodologies and code for (non-spectral) graph learning (with novel RNNextensions to sequence data) as compatible with popular deep learning frameworks (namely via Keras), as well as code for integration of SUMO as a data source. The proposed project will result in continuing development of this code base, with extensions towards the graph-to-graph transfer problem. For study of reinforcement-learning graph-based transfer, we foresee writing code integrating with the aforementioned Bayen lab framework [10].