Most existing neural networks for learning graphs deal with the issue of 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 some standard graph learning benchmarks. Learning on graphs has a long history in the kernels literature, including approaches based on random walks BID14 BID1 BID11 , counting subgraphs BID35 , spectral ideas BID41 , label propagation schemes with hashing BID36 Neumann et al., 2016) , and even algebraic ideas BID21 . Many of these papers address moderate size problems in chemo-and bioinformatics, and the way they represent graphs is essentially fixed.Recently, with the advent of deep learning and much larger datasets, a sequence of neural network based approaches have appeared to address the same problem, starting with BID33 . In contrast to the kernels framework, neural networks effectively integrate the classification or regression problem at hand with learning the graph representation itself, in a single, end-to-end system. In the last few years, there has been a veritable explosion in research activity in this area. Some of the proposed graph learning architectures BID8 BID18 BID29 directly seek inspiration from the type of classical CNNs that are used for image recognition BID25 Krizhevsky et al., 2012) . These methods involve first fixing a vertex ordering, then moving a filter across vertices while doing some computation as a function of the local neighborhood to generate a representation. This process is then repeated multiple times like in classical CNNs to build a deep graph representation. Other notable works on graph neural networks include BID26 BID34 BID0 BID20 . Very recently, BID15 showed that many of these approaches can be seen to be specific instances of a general message passing formalism, and coined the term message passing neural networks (MPNNs) to refer to them collectively.While MPNNs have been very successful in applications and are an active field of research, they differ from classical CNNs in a fundamental way: the internal feature representations in CNNs are equivariant to such transformations of the inputs as translation and rotations BID4 , the internal representations in MPNNs are fully invariant. This is a direct result of the fact that MPNNs deal with the permutation invariance issue in graphs simply by summing the messages coming from each neighbor. In this paper we argue that this is a serious limitation that restricts the representation power of MPNNs.MPNNs are ultimately compositional (part-based) models, that build up the representation of the graph from the representations of a hierarchy of subgraphs. To address the covariance issue, we study the covariance behavior of such networks in general, introducing a new general class of neural network architectures, which we call compositional networks (comp-nets). One advantage of this generalization is that instead of focusing attention on the mechanics of how information propagates from node to node, it emphasizes the connection to convolutional networks, in particular, it shows that what is missing from MPNNs is essentially the analog of steerability.Steerability implies that the activations (feature vectors) at a given neuron must transform according to a specific representation (in the algebraic sense) of the symmetry group of its receptive field, in our case, the group of permutations, S m . In this paper we only consider the defining representation and its tensor products, leading to first, second, third etc. order tensor activations. We derive the general form of covariant tensor propagation in comp-nets, and find that each "channel" in the network corresponds to a specific way of contracting a higher order tensor to a lower order one. Note that here by tensor activations we mean not just that each activation is expressed as a multidimensional array of numbers (as the word is usually used in the neural networks literature), but also that it transforms in a specific way under permutations, which is a more stringent criterion. The parameters of our covariant comp-nets are the entries of the mixing matrix that prescribe how these channels communicate with each other at each node. Our experiments show that this new architecture can beat scalar message passing neural networks on several standard datasets. On the subsampled HCEP dataset, CCN outperforms all other methods by a very large margin. For the graph kernels datasets, SVM with the Weisfeiler-Lehman kernels achieve the highest accuracy on NCI1 and NCI109, while CCN wins on MUTAG and PTC. Perhaps this poor performance is to be expected, since the datasets are small and neural network approaches usually require tens of thousands of training examples at minimum to be effective. Indeed, neural graph fingerprints and PSCN also perform poorly compared to the Weisfeiler-Lehman kernels.In the QM9 experiments, CCN beats the three other algorithms in both mean absolute error and root mean squared error. It should be noted that BID15 obtained stronger results on QM9, but we cannot properly compare our results with theirs because our experiments only use the adjacency matrices and atom labels of each node, while theirs includes comprehensive chemical features that better inform the target quantum properties. We have presented a general framework called covariant compositional networks (CCNs) for constructing covariant graph neural networks, which encompasses other message passing approaches as special cases, but takes a more general and principled approach to ensuring covariance with respect to permutations. Experimental results on several benchmark datasets show that CCNs can outperform other state-of-the-art algorithms. clearly true, since f a = f a = ξ(a ) . Now assume that it is true for all nodes with height up to h * . For any node n a with h(a) = h * + 1, f a = Φ(f c1 , f c2 , . . . , f c k ), where each of the children c 1 , . . . , c k are of height at most h * , therefore f a = Φ(f c1 , f c2 , . . . , f c k ) = Φ(f c1 , f c2 , . . . , f c k ) = f a .Thus , f a = f a for every node in G. The proposition follows by φ(G) = f r = f r = φ(G ).Proof of Proposition 3. Let G , G , N and N be as in Definition 5. As in Definition 6, for each node (neuron) n i in N there is a node n j in N such that their receptive fields are equivalent up to permutation. That is, if |P i | = m, then |P j | = m, and there is a permutation π ∈ S m , such that if P i = (e p1 , . . . , e pm ) and P j = (e q1 , . . . , e qm ), then e q π(a) = e pa . By covariance , then f j = R π (f i ).Now let G be a third equivalent object, and N the corresponding comp-net. N must also have a node, n k , that corresponds to n i and n j . In particular , letting its receptive field be P k = (e r1 , . . . , e rm ), there is a permutation σ ∈ S m for which e r σ(b) = e q b . Therefore, f k = R σ (f j ).At the same time , n k is also in correspondence with n i . In particular, letting τ = σπ (which corresponds to first applying the permutation π, then applying σ), e r τ (a) = e pa , and therefore f k = R τ (f i ). Hence, the {R π } maps must satisfy Case 4. Follows directly from 3.Case 5. Finally, if A 1 , ..., A u are k'th order P -tensors and C = j α j A j then DISPLAYFORM0 so C is a k'th order P -tensor.Proof of Proposition 5. Under the action of a permutation π ∈ S m on P b , χ (dropping the a→b superscipt) transforms to χ , where χ i,j = χ π −1 (i),j . However, this can also be written as DISPLAYFORM1 Therefore, F i1,...,i k transforms to DISPLAYFORM2 so F is a P -tensor.Proof of Proposition 6. By Proposition 5, under the action of any permutation π, each of the F pj slices of F transforms as DISPLAYFORM3 At the same time, π also permutes the slices amongst each other according to DISPLAYFORM4 so F is a k + 1'th order P -tensor.Proof of Proposition 7. Under any permutation π ∈ S m of P i , A↓ P i transforms to A↓ P i , where [A↓ P i ] π(a),π(b) = [A↓ Pi ] a,b . Therefore, A↓ Pi is a second order P -tensor. By the first case of Proposition 4, F ⊗ A↓ Pi is then a k + 2'th order P -tensor.
A general framework for creating covariant graph neural networks
{"src": "scitldr-AIC_train", "paper_id": "S1TgE7WR-"}