PaperlayerView exact revision on arXiv

Source-linked AI summary

Building powerful and equivariant graph neural networks with structural message-passing

Clement Vignac, Andreas Loukas, Pascal Frossard

arXiv:2006.15107v3cs.LGstat.ML

TL;DR

Message-passing networks have limited ability to represent graph topology despite their equivariance and local-learning bias. This paper introduces SMP, which propagates node identifiers in local context matrices using equivariant functions. It reports improved performance on structural tasks and state-of-the-art ZINC results among methods without expert features.

  • Problem

    Equivariant message-passing networks have limited expressive power for basic graph properties such as connectivity and cycle detection.

    Source: §1 · p. 1

  • Method

    SMP propagates one-hot node identifiers and features in local context matrices, using equivariant message and update functions.

    Source: §1 · p. 2, §3.2 · p. 5

  • Results

    SMP significantly outperforms previous models on graph topological properties and achieves state-of-the-art ZINC performance among methods that do not use expert features.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    SMP retains message-passing's inductive bias and ability to process node features while improving learning of graph topology.

    Source: §6 · p. 9

    Practical parameterizations that make SMP a universal approximator remain an open question.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

Message-passing has proved to be an effective way to design graph neural networks, as it is able to leverage both permutation equivariance and an inductive bias towards learning local structures in order to achieve good generalization. However, current message-passing architectures have a limited representation power and fail to learn basic topological properties of graphs. We address this problem and propose a powerful and equivariant message-passing framework based on two ideas: first, we propagate a one-hot encoding of the nodes, in addition to the features, in order to learn a local context matrix around each node. This matrix contains rich local information about both features and topology and can eventually be pooled to build node representations. Second, we propose methods for the parametrization of the message and update functions that ensure permutation equivariance. Having a representation that is independent of the specific choice of the one-hot encoding permits inductive reasoning and leads to better generalization properties. Experimentally, our model can predict various graph topological properties on synthetic data more accurately than previous methods and achieves state-of-the-art results on molecular graph regression on the ZINC dataset.

1 Introduction

Message-passing networks combine local structural learning with permutation equivariance, but have limited expressive power for graph topology. The paper introduces structural message-passing (SMP), which propagates node identifiers in local context matrices, and reports gains on structural tasks and ZINC molecular regression.

1 Introduction

  • MPNNs are permutation equivariant, encoding that node ordering is arbitrary and supporting better generalization than networks that must learn this invariance.MPNNs also exploit graph sparsity and favor learning relationships between nearby nodes.Source: §1 · p. 1
  • Despite these strengths, equivariant MPNNs cannot learn some basic properties, including connectivity, local clustering coefficients, and whether a graph contains a cycle.The paper identifies molecular-property prediction and combinatorial optimization as settings where graph structure matters.Source: §1 · p. 1
  • SMP is a graph network strictly more powerful than MPNNs that retains message-passing's inductive bias and is designed to generalize to unseen data.Its framework is computationally universal over equivariant functions when built from powerful layers.Source: §1 · p. 2
  • SMP compares favorably on structural tasks, solving cycle detection in all evaluated configurations where other powerful networks struggle on larger graphs and MPNNs do not solve it completely.The paper also evaluates connectivity, diameter, and shortest-path computation.Source: §1 · p. 2
  • SMP achieves state-of-the-art ZINC performance among methods that do not use expert features.The authors state that SMP learns from both features and topological information.Source: §1 · p. 2

2 Related work

Prior work strengthens graph networks through higher-order representations, equivariant building blocks, or node identifiers, but each route has practical or generalization trade-offs. SMP is positioned as a way to gain structural power while retaining equivariance.

2.1 Permutation equivariant graph neural networks

  • MPNNs without special node attributes are at most as powerful as the Weisfeiler-Lehman test, while higher-order k-WL networks are costly because they update tuples using all nodes.SMP learns richer node embeddings rather than one embedding per k-tuple, and its analysis uses distributed algorithms.Source: §2.1 · p. 2
  • More powerful equivariant networks can use hand-crafted topological features or combine equivariant functions and operators, but handcrafted features require task-specific expertise.The cited building blocks include equivariant linear functions, element-wise functions, and equivariance-preserving operators.Source: §2.1 · pp. 2–3
  • Higher-order tensor networks can use k-tuples to increase expressive power, but their memory requirements grow exponentially with tensor order.PPGN and Ring-GNN use matrix multiplication to improve expressivity at a given tensor order; SMP instead retains sparse message passing.Source: §2.1 · p. 3

2.2 Non-equivariant graph neural networks

  • MPNNs without identifiers can fail to reconstruct graph structure because nodes cannot distinguish whether incoming messages came from unique neighbors.This limitation motivates equipping nodes with identifiers.Source: §2.2 · p. 3
  • Identifiers can make message-passing networks Turing universal with sufficiently expressive functions, but randomly chosen identifiers compromise permutation equivariance and can harm sample efficiency and generalization.The cited work reports that larger datasets or augmentation can overcome identifier dependence, though overfitting and optimization issues can occur.Source: §2.2 · p. 3

3 Structural message-passing

SMP generalizes message passing by maintaining a local context matrix at each node and propagating it equivariantly. The analysis characterizes conditions for equivariance and increased expressive power, while noting that practical universal parameterizations remain unresolved.

3.1 Method

  • Each SMP node maintains a local context matrix whose rows represent the node's views of all graph nodes, rather than a single feature vector.Reordering nodes permutes the context rows without changing their content.Source: §3.1 · pp. 3–4
  • SMP initializes each local context with one-hot node identifiers and appends node features to the corresponding row; the identifier ordering is irrelevant to the output under the proper parametrization.The layer updates contexts using edge messages aggregated symmetrically, then the node's previous context.Source: §3.1 · pp. 3–4
  • Propagating identifiers from a one-hot encoding lets SMP iteratively compute powers of the adjacency matrix, which encode walk counts and can expose spectral properties.The paper says even simple parametrizations can manipulate polynomials in the adjacency matrix that MPNNs cannot detect.Source: §3.1 · p. 4

3.2 Analysis

  • SMP is permutation equivariant when its message, aggregation, and update functions are equivariant; set-equivariant networks can parameterize these functions.Equivariant set networks also permit training across graph sizes and inductive use on unseen sizes.Source: §3.2 · p. 5
  • For node classification, nodes with isomorphic k-hop neighborhoods receive the same output from a k-layer SMP.The paper contrasts this property with positional embeddings that do not have it.Source: §3.2 · p. 5
  • With powerful layers, SMP can recover graph structure from local contexts and represent any equivariant function for graphs under the stated depth and width conditions.The formal result concerns graphs bounded by diameter and maximum degree; the proofs are nonconstructive, leaving practical universal parameterizations open.Source: §3.2 · pp. 5–6
  • SMP is strictly more powerful than MPNNs: it can simulate any MPNN with the same depth, while MPNNs cannot simulate all SMPs.The paper also states that universal approximation requires symmetry-breaking during message passing and powerful message, aggregation, and update functions; practical universal parameterizations remain open.Source: §3.2 · p. 6

4 Implementation

The implementation combines equivariant set functions with message passing and offers default and faster variants. SMP can exploit graph sparsity relative to global-update architectures, though its local contexts require more memory than MPNNs.

4 Implementation

  • The proposed implementations first update each node's local context with a set neural network, then apply standard message passing separately to each context row.The first step uses a subset of linear equivariant functions.Source: §4 · p. 6
  • Default SMP uses two-layer perceptrons for message and update functions and normalizes a sum aggregator by the graph's average degree.The stated purpose is to retain sum aggregation's properties while avoiding exploding norms.Source: §4 · p. 6
  • Fast SMP is proposed for graphs without edge features; its message function uses pointwise multiplication and its update is a residual connection.Because its summed arguments depend only on each node's local context, it computes one message per node rather than per edge.Source: §4 · p. 6
  • SMP is more efficient than PPGN because message passing can exploit adjacency sparsity, and the authors report that it learns topological information more easily.Fast SMP can be approximated by a 2k-block PPGN, though it is not more powerful.Source: §4 · p. 6
  • SMP stores information for node pairs rather than all node triplets, and its sparse message passing can yield more favorable time complexity than global updates.Table 1 compares forward-pass time and space complexity in terms of node count, edge count, color count, and width.Source: §4 · p. 7, Table 1 · p. 7
  • SMP requires more memory than MPNNs, but greedy coloring can reuse identifiers for sufficiently distant nodes and reduce local-context size.The number of colors needed can grow rapidly with network depth.Source: §4 · p. 7

5 Experiments

Across cycle detection, multi-task graph-property prediction, and ZINC solubility regression, SMP compares favorably with prior methods. Results also distinguish standard and fast SMP on traversal-heavy tasks and report strong ZINC performance without expert features.

5.1 Cycle detection

  • Cycle models share an architecture and are retrained for each cycle length and graph size on balanced training samples.The experiments use 10,000 training and 10,000 evaluation samples; the compared methods differ in their convolution definition.Source: §5.1 · p. 7
  • SMP solves cycle detection almost perfectly across graph and cycle sizes, while PPGN and RING-GNN fail as graphs grow.SMP is also the only powerful network evaluated that generalizes well across graph sizes, and it requires much less training data in the reduced-data setting.Source: §5.1 · p. 8, Table 2 · p. 8

5.2 Multi-task detection of graph properties

  • Both SMP variants outperform their corresponding MPNNs and other methods on multi-task graph-property prediction.Standard SMP tends to do better than fast SMP on shortest paths, eccentricity, and connectivity tasks.Source: §5.2 · p. 9, Table 3 · p. 9

5.3 Constrained solubility regression on ZINC

  • SMP achieves state-of-the-art ZINC performance with and without edge features, without expert features.The comparison uses a subset of 10,000 molecules; an MPNN with edge features and expert features is reported to reach 0.108 MAE.Source: §5.3 · p. 9, Table 4 · p. 9

6 Conclusion

The conclusion presents SMP as a powerful, permutation-equivariant architecture that improves learning of graph topology while retaining MPNN-like feature processing and locality bias.

6 Conclusion

  • SMP is both powerful and permutation equivariant, addressing a major weakness of previous message-passing networks.The conclusion identifies this as the architecture's central contribution.Source: §6 · p. 9
  • SMP significantly outperforms previous models in learning graph topological properties.The conclusion frames this as an empirical finding.Source: §6 · p. 9
  • SMP retains MPNNs' inductive bias toward locality and their ability to process node features.The conclusion points to applications in chemistry, computational biology, and neural algorithmic reasoning.Source: §6 · p. 9

Broader Impact

The paper describes broad application prospects for its graph neural network while noting that its eventual uses and associated ethical problems are difficult to foresee.

Broader Impact

  • Because graph neural networks apply across many domains, the authors say their method's uses and associated ethical problems are difficult to predict.The method is presented as a general graph-neural-network methodology rather than one designed for a single application.Source: Broader Impact · p. 10
  • The authors expect early use in fields where graph topology is considered important, including quantum chemistry and drug discovery.They cite SMP's ZINC performance as an encouraging sign of potential in those fields.Source: Broader Impact · p. 10
  • Other proposed application areas include materials science, computational biology, combinatorial optimization, and code generation.These are described as possible applications, not demonstrated outcomes in this passage.Source: Broader Impact · p. 10

A Proof of Theorem 1

The proof applies a node permutation to the inputs and shows that the resulting SMP layer output matches the required equivariant transformation.

A Proof of Theorem 1

  • An SMP layer maps its inputs to a per-node output by applying an update to the node context and an aggregation of messages from neighbors.The message function takes node contexts and edge attributes; the aggregation is passed through φ before the update.Source: A Proof of Theorem 1 · p. 14
  • The proof defines permuted adjacency and context entries by reindexing their node indices with the inverse permutation.The action on the inputs applies the same permutation to U, Y, and A.Source: A Proof of Theorem 1 · p. 14
  • Under the theorem's conditions, the transformed layer expression matches the definition of equivariance.The proof writes the permuted-input output using the permuted node and neighbor indices, then identifies the match.Source: A Proof of Theorem 1 · p. 14

B Proof of Theorem 2

The proof constructs permutation-equivariant SMP networks that recover graph structure from local contexts, with bounds on depth and width under graph-diameter and degree constraints. It extends the construction to node and edge attributes and notes that its exact-function assumption is impractical.

B Proof of Theorem 2

  • For simple graphs with n nodes, diameter at most ∆, degree at most dmax, cX node attributes, and cY edge attributes, there exists a permutation-equivariant SMP of depth at most ∆ + 1 and width at most 2dmax + cX + n cY.Source: B Proof of Theorem 2 · p. 14

B.1 Warm up: nodes manipulate n x n matrices

  • In the warm-up, nodes propagate n × n matrices encoding their receptive fields, enabling each node to recover the full adjacency matrix after a number of layers equal to the graph diameter.The result is stated for connected graphs.Source: §B.1 · p. 15

B.2 SMP: nodes manipulate node embeddings

  • SMP replaces the n × n state with embeddings of width 2dmax, constructed equivariantly, and can injectively map adjacency matrices to local contexts once depth reaches the diameter.The resulting contexts distinguish non-isomorphic graphs even up to permutations.Source: §B.2 · pp. 15–16

B.3 Extension for attributed graphs

  • For connected graphs, node attributes can be progressively propagated into local contexts, while edge attributes require a separate equivariant embedding because node embeddings and edge-feature matrices transform differently under permutations.The square-root construction for edge features does not compress their representation; each edge-feature channel requires n additional channels.Source: §B.3 · pp. 16–17

B.4 Conclusion

  • The proof establishes layers that manipulate n × n matrices internally to produce embeddings of size n × (2dmax + cX + n cY), but assumes aggregation and update functions can compute any input function exactly, which is impossible in practice.A practical approximation argument would require a suitable universal approximator for equivariant functions on n × n × c tensors; known options have large memory requirements.Source: §B.4 · p. 17

C Proof of Corollary 1

The corollary uses local contexts that can reconstruct the adjacency matrix to compute equivariant graph functions. Invariant graph functions can then be obtained by replicating their value across nodes and averaging.

C Proof of Corollary 1

  • Because local contexts can reconstruct the adjacency matrix, nodes can use a universal network for sets to compute an equivariant function on the graph.The contexts are supplied under the conditions of Theorem 3.Source: C Proof of Corollary 1 · p. 17
  • An invariant graph function can be represented by repeating its value at every node in an equivariant output and averaging those node outputs.Source: C Proof of Corollary 1 · p. 18

D Proof of Proposition 1

The proof establishes that SMP can simulate MPNNs and distinguish some regular graphs that MPNNs cannot. It also gives a graph-coloring strategy for reducing identifier memory while avoiding conflicts in local neighborhoods.

D Proof of Proposition 1

  • Any MPNN can be simulated by an SMP, so SMPs are at least as powerful as MPNNs.The proof maintains MPNN features on the diagonal of each local context through initialization and an inductive update.Source: D Proof of Proposition 1 · p. 18
  • For the two regular graphs, an SMP distinguishes them with tr(A^3) values of 2 and 0, while MPNNs view them as isomorphic.Figure 3 illustrates the pair that SMPs distinguish but MPNNs cannot.Source: D Proof of Proposition 1 · pp. 18–19, Figure 3 · p. 18

E A more compact representation with graph coloring

  • When graph diameter is large relative to L, greedy coloring of the 2L-neighborhood graph reuses identifiers without conflicts in any L-hop neighborhood.The coloring may not use the optimal number of colors.Source: E A more compact representation with… · p. 19
  • The coloring-based initialization updates context rows by node color and is useful only when graph diameter exceeds 2L.The passage notes this condition is often met in geometric graphs such as meshes, but often not in scale-free networks.Source: E A more compact representation with… · p. 19

F Proof of Proposition 2

The comparison reports that PPGN is harder to optimize than SMP, while Ring-GNN could not be trained on the largest graphs. The proof shows that Fast SMP layers can be approximated by PPGN blocks, bounding Fast SMP's expressive power by PPGN's.

F Proof of Proposition 2

  • Each Fast SMP layer can be approximated by two PPGN blocks, implying that Fast SMP's expressive power is bounded by PPGN's.The proof constructs the first block to obtain an intermediate representation and the second to produce the Fast SMP layer output.Source: F Proof of Proposition 2 · pp. 19–20
  • The construction assumes PPGN layers retain access to adjacency, all-ones, and identity matrices, and that entry-wise multiplication can be approximated.The proof notes that entry-wise multiplication is not available in the original model.Source: F Proof of Proposition 2 · p. 19

G Comparison between SMP, Provably powerful graph networks and Ring-GNN

  • PPGN is harder to optimize than SMP; Ring-GNN works on small graphs but was not trained on 66- or 72-node graphs and is between two and three times slower per epoch.PPGN and SMP training time per epoch is approximately the same.Source: Figure 4 · p. 21
Loading 2006.15107v3…