PaperlayerView exact revision on arXiv

Source-linked AI summary

Relational Pooling for Graph Representations

Ryan L. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, Bruno Ribeiro

arXiv:1903.02541v2cs.LGstat.ML

TL;DR

Graph representation methods lack provably most-powerful representations for distinguishing nonisomorphic graphs. The paper introduces Relational Pooling, an ideal but intractable representation with tractable approximations that can strengthen existing architectures and WL-GNNs. Experiments show improvements across datasets and state-of-the-art methods, while some sampling approximations sacrifice unbiasedness.

  • Problem

    Existing graph representation schemes cannot provably distinguish all distinct graphs up to graph isomorphism.

  • Method

    Relational Pooling defines an ideal most-powerful graph representation, approximates it tractably, and combines it with neural architectures including WL-GNNs.

  • Results

    RP improves graph representations across multiple datasets and can make WL-GNNs more expressive than the WL test.

  • Takeaways & Limitations

    RP extends graph representation learning to architectures such as RNNs and CNNs while improving properties of state-of-the-art methods.

  • Takeaways & Limitations

    Combining π-SGD with k-ary RP can speed up GNNs but does not provide unbiased estimates of the full-graph loss.

Abstract

from arXiv · show

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.

1. Introduction

Graph representation learning still lacks a provably most-powerful representation that distinguishes all nonisomorphic graphs, motivating a broader framework. Relational Pooling provides such an ideal and tractable approximations that can strengthen existing GNNs.

  • Current graph representation schemes cannot provably distinguish all distinct graphs up to graph isomorphism.
  • A most-powerful graph representation framework would be a key development as GNNs address increasingly challenging problems.
  • Relational Pooling specifies an ideal representation that can distinguish nonisomorphic graphs when the WL isomorphism test fails.
  • RP produces graph representations invariant to adjacency-matrix permutations for finite, arbitrary-sized graphs with vertex or edge features.
  • RP combines with existing architectures, increases WL-GNN representation power, and uses tractable approximations for graph classification.The framework also supports architectures such as RNNs and yields strong empirical performance.

2. Relational Pooling

Relational Pooling (RP) creates permutation-invariant graph representations by aggregating outputs over vertex permutations, achieving maximal expressive power under suitable assumptions. RP also supports tractable approximations and can enhance GNNs, including WL-GNNs, beyond the original WL test.

  • Graph encoding and invariance: RP encodes graphs with an adjacency-and-edge-feature tensor and a vertex-feature matrix, while requiring representations to remain invariant to arbitrary vertex relabelings.The adjacency tensor has shape |V| × |V| × (1 + de), and vertex features have shape |V| × dv.
  • Joint Relational Pooling: Averaging an arbitrary graph function over all vertex permutations yields a permutation-invariant representation, and composing it with an outer function can capture additional graph signal.The resulting representation is maximally expressive but generally intractable to compute exactly.
  • Expressive power: For finite node and edge attribute sets, RP is most expressive when its underlying function is sufficiently expressive, distinguishing graphs exactly up to isomorphism and features.A universal approximator is given as an example of a sufficiently expressive function.
  • Neural architectures: RP can combine with RNNs, MLPs, and CNNs, allowing permutation-sensitive functions inside the pooling framework while preserving permutation invariance overall.CNNs operate on permuted adjacency tensors, with 2D or 3D convolutions depending on whether edge features are present.
  • RP-GNN and WL-GNNs: RP-GNN is strictly more expressive than the original WL-GNN and, with GIN and discrete attributes, is more powerful than the WL test.The paper uses circulant skip-link graphs as an example that WL-GNNs cannot distinguish but RP-GNN can represent differently.
  • Tractable approximations: π-SGD provides an unbiased estimator for the RP representation, while combining k-ary RP with π-SGD speeds up GNNs but loses unbiasedness for the full-graph loss.The paper also notes that k-ary RP combined with π-SGD does not provide unbiased estimates of the loss calculated with the entire graph.
  • Tractable approximations: k-ary RP improves tractability by pooling over k-node induced subgraphs, with expressiveness increasing strictly as k increases.The k-ary construction operates on k × k × (de + 1) tensor patches and k rows of vertex features.

3. Related Work

Prior graph methods include WL-based GNNs, graph kernels, CNNs, and invariant-function frameworks, while RP targets permutation-invariant representations beyond WL limitations.

  • WL-GNNs are at most as powerful as the standard Weisfeiler-Lehman algorithm and can fail to distinguish some nonisomorphic graphs.
  • Higher-order WL[k] methods operate on vertex tuples, increasing graph-distinguishing capacity as k increases.
  • Graph kernels and CNN-based approaches provide alternative graph representations, including CNNs applied to single canonical orderings.
  • RP provides stochastic optimization over all or poly-canonical orderings for permutation-invariant graph functions.
  • Exchangeability-based invariant-function theory and hand-picked canonical orientations offer related approaches but may fail in some cases or lack task-wide guarantees.

4. Experiments

Experiments test RP-GNN against WL-GNNs on graph classification and evaluate RP variants on molecular property prediction, including tractability and alternative neural architectures.

  • 4.1. Testing RP-GNN vs WL-GNN: The CSL experiment assesses whether RP can distinguish graph isomorphism classes that WL-GNNs represent identically.The study uses approximate RP through π-SGD and does not claim to solve graph isomorphism.
  • 4.1. Testing RP-GNN vs WL-GNN: RP-GNN substantially outperforms GIN on the 10-class skip-length task, whereas GIN achieves 10% random-guessing accuracy.GIN produces the same representation for all validation graphs in each fold.
  • 4.2. Predicting Molecular Properties: RP-Duvenaud is more powerful than the molecular baseline on HIV and similar in performance on the other evaluated tasks.The authors note that variability estimates may be over-confident.
  • 4.2. Predicting Molecular Properties: The molecular experiments use π-SGD with 20 inference-time samples and five random train/validation/test splits for k-ary models.
  • 4.2. Predicting Molecular Properties: 25% faster with mean AUC 0.687 (0.005 sd) at k = 10, while k = 20 is 10% faster with AUC 0.755 (0.003 sd) on Tox21.Results level off around k = 30; other datasets show no significant variation with k.
  • 4.2. Predicting Molecular Properties: The RNN performs reasonably on Tox21 but underperforms on other tasks, while the CNN underperforms on all tasks.The authors identify task suitability for these architectures as future work.

5. Conclusions

The paper presents RP as a theoretically and empirically supported framework for more expressive graph classification and regression, with tractable approximations and unresolved computational tradeoffs.

  • RP provides ideal most-powerful graph representations and tractable approximations that can make WL-GNNs more expressive than the WL test.
  • Experiments evaluate RP across datasets and show improvements to properties of state-of-the-art methods.
  • RP also permits RNNs and CNNs for graph problems, while future theory should clarify representation-power versus computational-cost tradeoffs.

Supplementary Material of Relational Pooling

The supplementary material explains how graphs are vectorized, how RP handles identifiers and permutations, and how these representations preserve isomorphism invariance.

  • A graph with edge attributes is represented by an adjacency tensor, while vertex attributes are stored separately.The example uses a 3 × 3 × 2 adjacency tensor.
  • The vec operation lists edge attributes and indicators for each vertex, then appends vertex attributes before continuing through the graph.k-ary models apply vec to induced subgraphs of size k.
  • Standard GNN aggregation can be permutation-invariant, but adding unique node IDs makes the resulting representation permutation-sensitive.The example shows different aggregated vectors after permuting adjacency rows and columns.
  • RP applies pooling over permutations to GNNs with unique IDs, preserving permutation invariance while using identifiers to distinguish vertices.
  • The alternative RP-GNN formulation permutes identifier matrices instead of adjacency and feature matrices, with reduced identifiers still applicable.Identifiers can use m-bit one-hot encodings for m ≤ |V|.

Proof of Theorem 2.1

The proof establishes maximal representation power by constructing a permutation-invariant fingerprint that uniquely identifies each graph up to isomorphism, then mapping that fingerprint to its target.

  • The proof considers the most general classification task, assigning equal targets exactly to isomorphic graphs with matching attributes.
  • A sufficiently expressive neural network approximates the required permutation-sensitive function on vectorized graph inputs.
  • Averaging the function over all vertex-label permutations produces a permutation-invariant representation.
  • The resulting representation is a unique fingerprint of each graph’s isomorphism class.
  • A downstream function can map each fingerprint to its unique target, proving maximal representation power.

Proof of Theorem 2.2

The proof shows that RP-GNN preserves isomorphism invariance, retains every distinction made by WL-GNNs, and can separate some nonisomorphic graphs that maximally powerful WL-GNNs cannot.

  • RP-GNN augments node features with one-hot identifiers determined by positions under graph permutations.
  • The proof targets three properties: isomorphic graphs coincide, WL-distinguishable graphs remain distinct, and some WL-indistinguishable graphs become separable.
  • Permutation averaging ensures that isomorphic graphs are mapped to the same representation.
  • RP-GNN can preserve distinctions between nonisomorphic graphs that a WL-GNN successfully distinguishes.
  • For circulant skip-link graphs G1 and G2, WL-GNNs cannot distinguish the pair, whereas RP-GNN can assign different representations.
  • π-SGD converges to a fixed point with probability one when the stated gradient and variance assumptions hold.

Proof of Proposition 2.2

The proof reduces RP computation by summing over k-node induced subgraphs rather than all vertex permutations when k is smaller than the graph size.

  • The k-ary RP formulation sums over all k-node induced subgraphs of the graph.
  • When k < |V|, the number of summed terms decreases from |V|! to |V|! (|V|−k)!.
  • For each selected subgraph, the method accounts for its k! node orderings.

Proof of Proposition 2.3

The proof shows that increasing RP’s dependency order strictly increases expressiveness: k-ary RP can represent every (k−1)-ary function and some additional functions.

  • For every k, the class Fk−1 of functions representable with (k−1)-ary dependencies is a proper subset of Fk.
  • The construction implies that k-ary RP expresses a function unavailable to (k−1)-ary RP.
  • The separating construction uses circulant skip-link graphs Gk and Gk+1 with the same number of vertices but different skip lengths.
  • A permutation-sensitive function that counts nonzero entries in properly oriented submatrices can therefore distinguish the two graphs.
  • At size k, Gk contains an induced subgraph with more edges than the corresponding subgraph in Gk+1.
  • Their induced subgraphs of size k−1 are isomorphic in matched multisets, preventing a lower-order RP function from distinguishing them.

C.1. Relational Pooling and Graph Structure Representation on CSL Graphs

The CSL experiment compares GIN with RP-GIN under controlled training and cross-validation settings, using random permutation-based IDs for RP-GIN. Figure 3 reports the resulting comparison on a challenging 10-class task.

  • Experimental setup: RP-GIN assigns one-hot encodings of i mod 10 rather than completely unique vertex IDs to facilitate learning.The experiment uses vertices i ∈ {1, 2, . . . , |V| = 41}.
  • Experimental setup: Both models are trained for 1000 epochs using ADAM for optimization.
  • Results: Figure 3 presents RP-GNN as more powerful than WL-GNN on a challenging 10-class classification task.
  • Experimental setup: Five random initializations are used at each cross-validation fold, with balanced classes in training and validation.
  • Experimental setup: Training runs on CPUs using PyTorch’s inherent multithreading on machines with multiple CPUs.

C.2. Predicting Molecular Properties

The molecular experiments evaluate RP-based graph models across chemical property-prediction tasks, including graph-convolution, RNN, and CNN variants. The CNN underperforms across all tasks, while the experiments also report training-time and performance comparisons for k-ary models.

  • Evaluation setup: Graph-convolution models use DeepChem-based architectures trained for 100 epochs with mini-batches of 96, Adagrad, and a learning rate of 0.003.Training uses 48 CPUs with DeepChem’s inherent multithreading.
  • Evaluation setup: RP-Duvenaud uses random splits and ROC-AUC for every selected dataset to simplify comparisons across the three datasets.The choice was made before training, while MoleculeNet reports ROC-AUC scores on all three datasets.
  • Relational Pooling models: The RP-Duvenaud implementation appends one-hot atom IDs whose length equals the largest molecule’s atom count to each molecule’s vertex attributes.This makes the ID representation depend on the maximum molecule size observed during model building.
  • RNN and CNN models: The CNN constructs a 20 × 20 × 14 adjacency subtensor from a random DFS start, applies convolution, ReLU, and max-pooling, then combines the result with vertex attributes.The combined graph representation is passed through an MLP to predict the class.
  • Results and limitations: The CNN underperforms on all tasks, whereas the RNN achieves reasonable performance on Tox21 and underperforms on the other tasks.The authors state that future work is needed to determine which tasks suit these approaches better.
  • Training time and performance: Figure 4 reports Tox21 test-set AUC means and standard deviations across five random splits together with k-ary training speedup factors.Training time is compared with full-graph training on 48 CPUs.
  • Training time and performance: Figures 5 and 6 present training-time and model-performance comparisons for k-ary models on HIV and MUV, respectively.
Loading 1903.02541v2…