Breaking the Limits of Message Passing Graph Neural Networks, ICML2021
Since the Message Passing (Graph) Neural Networks (MPNNs) have a linear complexity with respect to the number of nodes when applied to sparse graphs, they have been widely implemented and still raise a lot of interest even though their theoretical expressive power is limited to the first order Weisfeiler-Lehman test (1-WL). In this paper, we show that if the graph convolution supports are designed in spectral-domain by a non-linear custom function of eigenvalues and masked with an arbitrary large receptive field, the MPNN is theoretically more powerful than the 1-WL test and experimentally as powerful as a 3-WL existing models, while remaining spatially localized. Moreover, by designing custom filter functions, outputs can have various frequency components that allow the convolution process to learn different relationships between a given input graph signal and its associated properties. So far, the best 3-WL equivalent graph neural networks have a computational complexity in O(n3) with memory usage in O(n2), consider non-local update mechanism and do not provide the spectral richness of output profile. The proposed method overcomes all these aforementioned problems and reaches state-of-the-art results in many downstream tasks. https://github.com/balcilar/gnn-matlang https://slideslive.com/38958778 |
|
Analyzing the Expressive Power of Graph Neural Networks in a Spectral Perspective, ICLR2021
In the recent literature of Graph Neural Networks (GNN), the expressive power of models has been studied through their capability to distinguish if two given graphs are isomorphic or not. Since the graph isomorphism problem is NP-intermediate, and Weisfeiler-Lehman (WL) test can give sufficient but not enough evidence in polynomial time, the theoretical power of GNNs is usually evaluated by the equivalence of WL-test order, followed by an empirical analysis of the models on some reference inductive and transductive datasets. However, such analysis does not account the signal processing pipeline, whose capability is generally evaluated in the spectral domain. In this paper, we argue that a spectral analysis of GNNs behavior can provide a complementary point of view to go one step further in the understanding of GNNs. By bridging the gap between the spectral and spatial design of graph convolutions, we theoretically demonstrate some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. Using this connection, we managed to re-formulate most of the state-of-the-art graph neural networks into one common framework. This general framework allows to lead a spectral analysis of the most popular GNNs, explaining their performance and showing their limits according to spectral point of view. Our theoretical spectral analysis is confirmed by experiments on various graph databases. Furthermore, we demonstrate the necessity of high and/or band-pass filters on a graph dataset, while the majority of GNN is limited to only low-pass and inevitably it fails. https://github.com/balcilar/gnn-spectral-expressive-power https://slideslive.com/38954202/analyzing-the-expressive-power-of-graph-neural-networks-in-a-spectral-perspective?ref=speaker-36840 |
|
R-SLAM : Resilient Localization and Mapping in Challenging Environments
Accurate pose estimation plays an important role in solution of simultaneous localization and mapping (SLAM) problem, required for many robotic applications. This project presents a new approach called R-SLAM, primarily to overcome systematic and non-systematic odometry errors which are generally caused by uneven floors, unexpected objects on the floor or wheel-slippage due to skidding or fast turn. The hybrid approach presented here combines the strengths of feature based and grid based methods to produce globally consistent high resolution maps within various types of environments. The proposed R-SLAM algorithm improves the pose estimation by positioning some of the particles relative to the features existing in the environment. So instead of assuming unimodal Gaussian distribution of particles, as it is in GMapping method, R-SLAM handles the odometry errors better without increasing the number of particles. R-SLAM approach does not necessitate any pre-defined landmarks, yet makes use of them whenever they exist in the environment. Restricted use of the features keeps the computational complexity suitable for real time applications in large scaled environments. Balcılar, M, S Yavuz, MF Amasyalı, E Uslu, et F Çakmak. "R-SLAM: Resilient localization and mapping in challenging environments." Robotics and Autonomous Systems, Vol. 87, pp 66-80, (2017). |
|