Relational Pooling for Graph Representations

By Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, Bruno Ribeiro. 2019

285 citations recorded by the source corpus.

This work generalizes graph neural networks (GNNs) beyond those based on the Weisfeiler-Lehman (WL) algorithm, graph Laplacians, and diffusions. Our approach, denoted Relational Pooling (RP), draws from the theory of finite partial exchangeability to provide a framework with maximal representation power for graphs. RP can work with existing graph representation models and, somewhat counterintuitively, can make them even more powerful than the original WL isomorphism test. Additionally, RP allows architectures like Recurrent Neural Networks and Convolutional Neural Networks to be used in a theoretically sound approach for graph classification. We demonstrate improved performance of RP-based graph representations over state-of-the-art methods on a number of tasks.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Provably Powerful Graph Networks (2019, background): “In another line of work, Murphy et al. (2019) suggest expressive invariant graph models deﬁned using averaging over all permutations of an arbitrary base neural network.”
Weisfeiler and Lehman Go Cellular: CW Networks (2021, methodology): “Unsolvable by the WL test and message passing approaches [14, 57], we use it to validate the expressive power of CWNs.”
Can graph neural networks count substructures? (2020, methodology): “For choices of f that are sufficiently expressive, such fRP’s are shown to be an universal approximator of permutation-invariant functions [45].”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “This inspired a large body of research on stronger variants of GNNs [20, 91, 85, 86, 92, 93, 94] which provably overcome these limitations.”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, background): “[86] Ryan L.”
Identity-aware Graph Neural Networks (2021, methodology): “Recently, many neural networks have been proposed with expressive power beyond the 1-WL test, including (Chen et al. 2019; Maron et al. 2019a; Murphy et al. 2019; You, Ying, and Leskovec 2019; Li et al. 2020).”
Graph Information Bottleneck (2020, unknown): “Recently, many works have been focusing on developing more powerful GNNs [8–13], in a sense that they can fit more complex graph-structured data.”
Efficient Graph Generation with Graph Recurrent Attention Networks (2019, background): “Similar strategy has been exploited for learning relational pooling function in [25].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “Extensive experiments 3 are conducted to evaluate our DE-GNN and DEA-GNN over three levels of tasks involving target node sets with sizes 1, 2 and 3 respectively: roles of nodes classiﬁcation (Task 1), link prediction (Task 2), and triangle prediction (Task 3).”
Principal Neighbourhood Aggregation for Graph Nets (2020, background): “Only recently there have been significant studies on the expressive power of various GNN models [6, 7, 8, 9, 10].”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, unknown): “In a CSL graph-pair [43], we want to be able to distinguish the two non-isomorphic graphs.”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, methodology): “[20] proposes relational pooling (RP), an approach that combines permutation-sensitive functions under all permutations to obtain a permutation-invariant function.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “A possible workaround is proposed in [49], where the authors take into account all possible vertex permutations.”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “Given the recent theoretical results on the importance of informative graph PE for expressive GNNs (Murphy et al., 2019; Srinivasan & Ribeiro, 2019; Loukas, 2020), we are interested in a generic framework that can enable GNNs to separate positional and structural representations to increase their ex”
Design Space for Graph Neural Networks (2020, methodology): “There are alternative designs of graph learning models [18–20, Transferable Architecture Search .”
A Generalization of Transformer Networks to Graphs (2020, background): “For graphs, the design of unique node positions is challenging as there are symmetries which prevent canonical node positional information (Murphy et al. 2019).”
Benchmarking Graph Neural Networks (2023, methodology): “We perform a 5-fold cross validation split, following [67], which gives 5 sets of train, validation and test data indices in the ratio 3 : 1 : 1.”