Source-linked AI summary
Covariant Compositional Networks For Learning Graphs
Risi Kondor, Hy Truong Son, Horace Pan, Brandon Anderson, Shubhendu Trivedi
TL;DR
Message-passing graph networks achieve permutation handling through fully invariant internal features, which the paper argues limits representation power. CCNs instead use covariant tensor representations within compositional architectures, and experiments report stronger performance than competing methods on several benchmarks, subject to stated framework assumptions.
Problem
MPNNs obtain permutation invariance by summing neighbor messages, leaving internal representations fully invariant and potentially restricting representation power.
Method
CCNs represent hierarchical graph parts with activations transforming according to tensor representations of the permutation group and derive corresponding covariant propagation rules.
Results
CCNs outperform other state-of-the-art algorithms on several benchmark datasets, including all three compared algorithms on QM9’s mean absolute error and root mean squared error.
Takeaways & Limitations
CCNs provide a general, principled framework for permutation-covariant graph neural networks that encompasses other message-passing approaches as special cases.
Takeaways & Limitations
The framework assumes linear permutation representations and does not discuss its natural generalizations to non-symmetric graphs or graphs with self-loops.
Abstract
from arXiv · showhide
Most existing neural networks for learning graphs address permutation invariance by conceiving of the network as a message passing scheme, where each node sums the feature vectors coming from its neighbors. We argue that this imposes a limitation on their representation power, and instead propose a new general architecture for representing objects consisting of a hierarchy of parts, which we call Covariant Compositional Networks (CCNs). Here, covariance means that the activation of each neuron must transform in a specific way under permutations, similarly to steerability in CNNs. We achieve covariance by making each activation transform according to a tensor representation of the permutation group, and derive the corresponding tensor aggregation rules that each neuron must implement. Experiments show that CCNs can outperform competing methods on standard graph learning benchmarks.
1. INTRODUCTION
Graph learning has moved from fixed kernel representations toward end-to-end neural models, but message-passing networks enforce fully invariant internal features. The paper introduces compositional networks that restore transformation-aware internal representations by treating steerability as the missing analogue from CNNs.
- Neural graph models learn representations jointly with classification or regression in an end-to-end system.
- MPNNs handle graph permutations by summing neighbor messages, making their internal feature representations fully invariant.
- The paper argues that fully invariant internal representations restrict MPNNs’ representation power.
- Compositional networks represent graphs through a hierarchy of subgraphs and connect graph representation learning to convolutional networks.
- CCNs use permutation-group tensor representations for activations and derive covariant tensor propagation through contraction channels.
2. LEARNING GRAPHS
Graph learning seeks predictions from graph-structured inputs while capturing structure across multiple scales and remaining unchanged by vertex renumbering. The section formalizes this permutation-invariance requirement and notes simplifying assumptions used in the framework.
- Graph learning maps graph inputs to class labels, real-valued quantities, or more general combinatorial outputs.
- The framework assumes graphs are symmetric, have no self-loops, and may include weighted edges and vertex feature vectors.
- Useful graph representations should capture structure ranging from individual atoms and functional groups to protein subunits and overall shape.
- The framework does not discuss its natural generalizations to non-symmetric graphs or graphs with self-loops.
- Permuting vertex names changes the adjacency matrix and labels while preserving the represented graph, so predictions and training outcomes should remain unchanged.
- Permutation invariance is formulated through a feature map whose output is unchanged across vertex permutations.
3. COMPOSITIONAL NETWORKS
Compositional networks represent hierarchical objects as DAGs of parts whose nodes carry activations computed from child features. For graphs, permutation-invariant composition schemes and invariant aggregation yield invariant representations, while the framework also connects graph neural networks to message passing and CNN-like compositional architectures.
- Compositional networks: Comp-nets represent complex objects by composing parts in a DAG, with leaves as atoms, a root for the whole object, and feature vectors attached to nodes.Each non-leaf activation is computed by aggregating the feature vectors of its children.
- Graph constructions: Graph comp-nets can combine information across scales because their parts correspond to vertex clusters or neighborhoods of different radii.This construction also provides a natural route to satisfying permutation invariance.
- Permutation invariance: If the composition scheme and child aggregation function are permutation invariant, the resulting comp-net representation is invariant to permutations of graph vertices.The root feature vector serves as the graph representation.
- Permutation invariance: A composition scheme is permutation invariant when relabeling atoms produces an isomorphic DAG with corresponding parts.This preserves the structural organization of the object under atom permutations.
- Connection to CNNs: The framework relates graph comp-nets to CNNs because both use hierarchical receptive fields, while graph atoms are vertices and CNN atoms are pixels.The analogy motivates aggregation functions that combine child activations in structured ways.
- Graph constructions: Layered graph composition schemes connect each vertex to neighboring nodes at the previous level, then aggregate the final layer into a root representing the entire graph.The construction depends only on graph topology, so it is permutation invariant and can be interpreted as label propagation.
- Message passing neural networks: Message passing neural networks are special cases of comp-nets: invariant aggregation makes their representations permutation invariant, but the paper argues this invariant scheme limits representation power.The framework emphasizes compositional structure rather than only node-to-node information propagation.
4. COVARIANT COMPOSITIONAL NETWORKS
The paper argues that invariant message passing loses information about the internal organization of receptive fields, and introduces covariant compositional networks whose activations transform predictably under permutations. Tensor representations of permutation groups provide the transformation rules for first-, second-, and higher-order activations.
- CNN analogy: CNNs motivate covariance: translations shift activations, while rotations also change receptive-field orientation and can exchange feature responses.Steerability makes these activation changes predictable through a fixed invertible transformation.
- Motivation: Invariant message passing can restrict graph representations because symmetric aggregation loses which receptive-field vertices contributed which information.With overlapping receptive fields, upstream aggregation cannot distinguish shared vertices from nonshared ones.
- Covariance: Covariant comp-nets replace unordered receptive fields with ordered sets and require activations to transform through a function Rπ associated with each aligning permutation.Under a permutation π, the corresponding activation is transformed according to Rπ.
- Representations: Assuming linear transformation maps makes the matrices Rπ form a representation of the symmetric group.This connects covariance to steerable representations and supplies algebraic transformation rules for activations.
- Tensor activations: First-order covariance uses permutation matrices, requiring each activation to be a |Pi|-dimensional vector whose components relate to specific receptive-field atoms.Higher-order covariance uses tensor-product representations, so second-order activations are |Pi|^2-dimensional and encode constituent relationships.
5. TENSOR AGGREGATION RULES
Tensor aggregation preserves permutation covariance by combining tensor operations that raise, contract, and mix activation orders. The resulting scheme generalizes conventional message passing through multiple contraction patterns and channels.
- General tensor operations: Tensor arithmetic provides the framework for deriving aggregation operations that preserve permutation behavior.Tensor products, elementwise products, projections, contractions, and linear combinations can be combined within the aggregation function.
- Promotion and stacking: Child activations are promoted to the parent receptive field before being stacked into a higher-order tensor.Promotion uses indicator matrices associated with the child and parent receptive fields to guarantee covariance.
- General aggregation algorithm: The general aggregation algorithm stacks promoted activations, optionally incorporates the restricted adjacency matrix, contracts dimensions, and mixes the resulting tensors.This sequence increases tensor order before contractions reduce it to a manageable set of output channels.
- Scalar aggregation: Constraining inputs and outputs to scalars and omitting adjacency multiplication reduces aggregation to summation, recovering simple message passing when multiple channels are allowed.The scalar case also connects to the aggregation used by the Weisfeiler–Lehman isomorphism test.
- Higher-order aggregation: First-order aggregation offers two contraction choices, including summing contributions from children individually, while higher-order aggregation provides more projection patterns.For second-order aggregation, a third-order tensor can be contracted along each of its three dimensions.
6. EXPERIMENTS
The experiments evaluate second-order CCNs on molecular regression and graph-classification benchmarks. CCNs show strong performance on the subsampled HCEP and QM9 tasks, while results on small kernel datasets vary by dataset.
- Datasets: The evaluation compares second-order CCNs with standard graph-learning algorithms on molecular datasets spanning regression and classification.The datasets include HCEP, QM9, and four graph-kernel classification benchmarks.
- Datasets: The HCEP regression experiment uses a random subset of 50,000 molecules from a 2.3-million-compound dataset.The target is Power Conversion Efficiency for candidate solar-cell compounds.
- Datasets: QM9 contains 133k organic molecules and 13 target properties, but the experiments use only chemical graphs and atom labels.Spatial information about atomic configurations is not used.
- Results: On subsampled HCEP, CCN outperforms all other methods by a very large margin.On the kernel datasets, CCN wins on MUTAG and PTC, whereas Weisfeiler–Lehman kernels achieve the highest accuracy on NCI1 and NCI109.
- Results: On QM9, CCN beats the three other algorithms in both mean absolute error and root mean squared error.The comparison is limited because the experiments use adjacency matrices and atom labels, whereas another reported study used richer chemical features.
7. CONCLUSIONS
The paper presents CCNs as a general framework for covariant graph neural networks that includes message-passing approaches as special cases. Experiments on benchmark datasets show that CCNs can outperform other state-of-the-art algorithms.
- Conclusion: CCNs provide a general framework for constructing graph neural networks that are covariant to permutations.The framework encompasses other message-passing approaches as special cases.
- Conclusion: The framework takes a more general and principled approach to ensuring covariance with respect to permutations.This conclusion follows from treating activations according to tensor representations and deriving corresponding aggregation rules.
- Conclusion: Experimental results on several benchmark datasets show that CCNs can outperform other state-of-the-art algorithms.The reported experiments include graph-classification benchmarks with accuracy results and QM9 regression results.
APPENDIX A. MATHEMATICAL BACKGROUND
The appendix introduces groups and their representations as mathematical background for the paper's symmetry-based construction. Groups are defined by closure, associativity, identity, and inverses, while representations map group elements to matrices preserving multiplication.
- Groups: A group is a set with a binary operation satisfying closure, associativity, identity, and inverse axioms.The operation need not be commutative, and groups may be finite or infinite.
- Representations: A representation maps each group element to a matrix such that multiplying representation matrices corresponds to the group operation.The paper generally uses complex-valued representations and allows real-valued representations for symmetric groups.
APPENDIX B. PROOFS
The appendix proves that covariant compositional networks preserve the required transformation behavior under permutations. It establishes this through induction over network height, permutation representations, and closure of tensor operations.
- Permutation covariance of compositional networks: Induction over node height shows that corresponding activations in equivalent permuted objects transform consistently, including the final network output.The base case uses equivalent leaf features, while the inductive step applies the compositional map to corresponding child activations.
- Permutation covariance of compositional networks: Equivalent receptive fields are related by permutations, allowing corresponding neurons in the two compositional networks to be matched.The proof identifies corresponding nodes whose receptive fields have equal size and differ only by a permutation.
- Permutation representations: The permutation maps satisfy Rσπ = Rσ ◦Rπ and, in the linear case, form a group representation of Sm.This composition law is the algebraic basis for representing how activations transform under successive permutations.
- Closure of tensor operations: Feature slices and contractions remain P–tensors, and adding a permuted slice increases the tensor order by one.The proofs show both the transformation of individual slices and their permutation among one another.