# Graph Reasoning Networks
**Authors**: Markus Zopf, Francesco Alesiani
## Abstract
Graph neural networks (GNNs) are the predominant approach for graph-based machine learning. While neural networks have shown great performance at learning useful representations, they are often criticized for their limited high-level reasoning abilities. In this work, we present Graph Reasoning Networks (GRNs), a novel approach to combine the strengths of fixed and learned graph representations and a reasoning module based on a differentiable satisfiability solver. While results on real-world datasets show comparable performance to GNN, experiments on synthetic datasets demonstrate the potential of the newly proposed method.
footnotetext: Equal contribution footnotetext: Presented at the workshop on graphs and more complex structures for learning and reasoning at AAAI 2022
## 1 Introduction
Graph-structured data can be found in a wide range of domains such as computer science (e.g. scientific citation graphs and social networks), chemistry (e.g. molecules), and biology (e.g. proteins). Consequently, graph-based machine learning (Scarselli et al. 2009; Bronstein et al. 2021) has received increasing attention from the machine learning community.
Today, the most popular approaches for graph-based machine learning are different variants of the message-passing approach such as Graph Neural Networks (GNNs) (Scarselli et al. 2009), Graph Convolutional Networks (GCNs) (Kipf et al. 2018), and Graph Attention Networks (GATs) (Veličković et al. 2018). While these approaches have demonstrated good performance in a wide range of application domains, they are often criticized for their limited high-level reasoning abilities and interpretability (Cingillioglu and Russo 2018; d’Avila Garcez and Lamb 2020; Marcus 2020; Chen et al. 2020; Loukas 2019; Bodnar et al. 2021; Dwivedi et al. 2021). These shortcomings motivate research to combine the abstraction abilities of continuous neural networks and approaches with better high-level reasoning capabilities. A major challenge in doing so is the fact that many reasoning approaches are not differentiable, which renders an efficient joint training of continuous neural networks reasoning approaches impossible.
In this work, we present Graph Reasoning Networks (GRNs), a novel combination of continuous graph-based machine learning and a logical reasoning approach that can be trained with standard gradient-based optimization methods. GRNs consist of a graph encoding module that maps graphs into a $d$ -dimensional feature vector in $[0,1]^{d}$ and a differentiable satisfiability solver Wang et al. (2019) that learns logical rules based on the obtained representation. We propose a semi-learnable encoder that consists of a fixed and a learnable component to combine the strength of previously observed usefulness of fixed encodings with the adaptiveness of learned representations.
Our experiments demonstrate the potential of the newly proposed method as it can learn challenging synthetic datasets that standard GNNs cannot learn without a reasoning module. Furthermore, the proposed approach performs on par on real-world datasets with and without using node features.
## 2 Related Work
GNN and Beyond GNN
GCN (Kipf and Welling 2016), GAT (Veličković et al. 2017) or in general neural message passing (Gilmer et al. 2017) are among various commonly used methods to process features over graphs. PPGN (Provably Powerful Graph Network) (Maron et al. 2019) is a class of Neural Networks that improves the expressiveness of GNN. (Morris et al. 2019) extends message passing to include higher-order node tuples. However, these methods remain highly limited regarding memory and computational complexity.
Learning Rules over Knowledge Graphs
Learning rules over Knowledge Graphs (KGs) (Qu et al. 2020) extracts rules from triplets head - relationship - tail (i.e. $(h,r,t)$ ), to predict the relationship ( $r$ ) not observed or to predict elements ( $h$ or $t$ ) missing in the KG. These methods do not extend to graph classification.
Differentiable SAT
Differentiable SAT methods (Wang et al. 2019; Wang and Kolter 2019; Wang, Chang, and Kolter 2017) compute gradients on the rules and on the input and output variables to propagate gradients, thus enabling SAT model to be integrated into machine learning systems. Alternative approaches (Cingillioglu and Russo 2018; Evans and Grefenstette 2018), restrict the class of rules to predefined templates. These methods do not consider graph classification.
## 3 Graph Reasoning Networks
In the following, we describe our novel approach to combine graph-based machine learning with a reasoning module to mitigate the limited reasoning capabilities of graph neural networks. On a high-level view, the proposed method consists of two submodules: an $\mathsf{encoder}$ and a $\mathsf{reasoner}$ . The encoder is a module that takes a graph $g$ as input and generates a $d$ -dimensional intermediate vector representation $r$ of the graph. The intermediate vector representation $r$ contains binary values (i.e. $r_{i}\in\{0,1\}$ ) and/or probabilistic values (i.e. $r_{i}\in[0,1]$ ). In contrast to previous approaches, we propose an encoder that consists of both learnable and not learnable features to empower the reasoner to learn even better rules (hence, a semi-learnable encoder). The reasoner is a module that learns logical rules based on the semi-learned $d$ -dimensional intermediate representation $r$ and generates a task-specific prediction $o$ for the input graph as an output. Both encoder and reasoner can be trained end-to-end with gradient-based optimization thanks to the differentiable MAX-SAT relaxation proposed in (Wang, Chang, and Kolter 2017), which is a crucial property of the proposed method. Note that different to most neural networks, the output of the reasoner is not a probability distribution over all possible classes, but a discrete output representing the corresponding class. Hence, for a binary classification problem, we obtain $o\in\{0,1\}$ and a corresponding encoding for multi-class prediction problems.
Based on the two submodules, Graph Reasoning Networks can be defined as a combination of both functions according to
| | $\displaystyle r$ | $\displaystyle=\mathsf{encoder}(g),$ | $\displaystyle y$ | $\displaystyle=\mathsf{reasoner}(r)$ | |
| --- | --- | --- | --- | --- | --- |
In the following, we discuss both encoder and reasoner in detail.
### 3.1 Semi-learnable encoder
To combine the strengths of fixed features and learnable representations, we propose a semi-learnable encoder that maps input graphs into a vector representation, which will be used by the subsequent reasoner to predict a classification output.
#### Fixed features.
The first set of functions consists of fixed, predefined features that encode information about the topology of the graph and the node features (if present). A simple approach to encode the topology as a vector is to flatten the corresponding adjacency matrix $A$ into an adjacency string $S$ . To this end, $A\in\operatorname{\{0,1\}}^{n\times n}$ is converted into $S\in\operatorname{\{0,1\}}^{n^{2}}$ according to $S_{i+n\cdot(j-1)}=A_{i,j}$ for $i,j\in\{1,\dots,n\}$ . The size of the adjacency matrix increases quadratically with the number of nodes in the graph, which is also true for the adjacency string $S$ . However, in many datasets such as NCI1 and PROTEINS, the number of nodes in the graphs is rather small and thus allows an application of this approach. Furthermore, in undirected graphs, only a part of the adjacency matrix needs to be encoded since it already contains all information about the graph topology. Moreover, the elements $A_{i,i}$ do not have to be encoded in $S$ if the graphs do not contain self-loops. Hence, the size of the adjacency string $S$ can be reduced to $l=\frac{(n-1)n}{2}$ .
A problem with this approach is that isomorphic graphs with different adjacency matrices $A$ and $A^{\prime}$ are mapped to different adjacency strings. Two graphs are called isomorphic if there exists an isomorphism (i.e. a bijection map) between their vertex sets that preserves the graph topology. Graph canonical labelling (McKay and Piperno 2014a) is the process where a graph is relabelled such that isomorphic graphs are identical after relabelling. While the complexity of graph canonical labelling is $e^{O(\sqrt{n\log n})}$ (Babai, Kantor, and Luks 1983), there exist fast implementations such as Trace or nauty (McKay and Piperno 2014b).
Besides encoding information about the topology, information about the node features can be encoded in a vector representation, for instance by simply concatenating all node features. However, this approach can lead to a large representation, depending on the number of node features.
A problem with the previously described approach is that the rules learned by Wang et al. (2019) are not invariant to permutations of the bit string. Hence, each rule is only able to consider a specific sub-structure of a graph or a specific set of node features, which may limit the generalizability of the approach. Furthermore, the representation is fixed and cannot be automatically adapted by a machine learning model based on the concrete problem at hand.
#### Learned representation
Encoding the topology with fixed representations such as a topology string or a Weisfeiler-Leman-based representation (Weisfeiler and Leman 1968) have been shown to be strong features (Shervashidze et al. 2011). However, there are also problems as discussed above. A potential solution is to learn a fixed-sized permutation invariant encoding of the graph. To this end, permutation invariant graph neural networks (GNN) such as GCN (Kipf and Welling 2016) or GAT (Veličković et al. 2017) can be used. Since the approach proposed by Wang et al. (2019) provides gradients not only for the rules but also for the input, the GNN can be trained jointly with the differentiable satisfiability solver such that it learns to generate a useful intermediate representation.
<details>
<summary>extracted/5716995/figures/GraphSAT3.png Details</summary>
### Visual Description
\n
## Diagram: Graph Neural Network Representation
### Overview
The image presents two diagrams illustrating the representation of graph neural networks. Each diagram consists of a graph structure, an adjacency matrix (A), a feature matrix (X), and equations defining topological features (X<sub>topo</sub>) and learned features (X<sub>features</sub>). The diagrams demonstrate how graph structures can be represented mathematically for use in neural networks.
### Components/Axes
Each diagram contains the following components:
* **Graph Structure:** A visual representation of a graph with nodes and edges. Nodes are colored with a pattern of orange, blue, and grey.
* **Adjacency Matrix (A):** A 3x3 matrix representing the connections between nodes in the graph.
* **Feature Matrix (X):** A 4x3 matrix representing the features associated with each node.
* **Equations:** Two equations defining X<sub>topo</sub> and X<sub>features</sub>.
* X<sub>topo</sub> = \[1 1 0 1 0 1]
* X<sub>features</sub> = σ(Kσ(KXW<sup>0</sup>)W<sup>1</sup>)
* Where σ is the sigmoid function, K is a kernel, and W<sup>0</sup> and W<sup>1</sup> are weight matrices.
### Detailed Analysis or Content Details
**Diagram 1 (Top)**
* **Graph Structure:** The graph has 4 nodes labeled 1, 2, 3, and 4. Node 1 is connected to nodes 2 and 3. Node 2 is connected to node 3. Node 3 is connected to node 4.
* **Adjacency Matrix (A):**
```
[ 1 1 0 ]
[ 1 0 1 ]
[ 0 1 1 ]
```
* **Feature Matrix (X):**
```
[ Blue Orange Grey ]
[ Grey Blue Orange ]
[ Orange Grey Blue ]
[ Blue Grey Orange ]
```
* **X<sub>topo</sub>:** \[1 1 0 1 0 1]
* **X<sub>features</sub>:** σ(Kσ(KXW<sup>0</sup>)W<sup>1</sup>)
**Diagram 2 (Bottom)**
* **Graph Structure:** The graph has 4 nodes labeled 1, 2, 3, and 4. Node 1 is connected to node 3. Node 2 is connected to node 4. Node 3 is connected to node 4.
* **Adjacency Matrix (A):**
```
[ 1 0 1 ]
[ 0 1 1 ]
[ 1 1 0 ]
```
* **Feature Matrix (X):**
```
[ Grey Blue Orange ]
[ Orange Grey Blue ]
[ Blue Orange Grey ]
[ Grey Blue Orange ]
```
* **X<sub>topo</sub>:** \[1 1 0 0 1 1]
* **X<sub>features</sub>:** σ(Kσ(KXW<sup>0</sup>)W<sup>1</sup>)
### Key Observations
* The adjacency matrices represent the connectivity of the graphs. A '1' indicates a connection between two nodes, while a '0' indicates no connection.
* The feature matrices represent the features associated with each node. The colors in the matrix correspond to the colors of the nodes in the graph.
* The X<sub>topo</sub> vector appears to be a flattened representation of the graph's structure, potentially indicating node presence or absence in specific contexts.
* The X<sub>features</sub> equation suggests a non-linear transformation of node features using a kernel function (K) and weight matrices (W<sup>0</sup>, W<sup>1</sup>), followed by a sigmoid activation function (σ).
### Interpretation
These diagrams illustrate a method for representing graphs in a format suitable for processing by neural networks. The adjacency matrix and feature matrix provide a numerical representation of the graph's structure and node attributes. The equations for X<sub>topo</sub> and X<sub>features</sub> suggest a process for extracting topological features and learning node representations through a neural network architecture. The use of a kernel function and sigmoid activation function indicates a non-linear transformation of the node features, allowing the network to learn complex relationships between nodes. The two diagrams demonstrate how different graph structures can be represented and processed using this approach. The differences in the adjacency matrices and feature matrices reflect the unique connectivity and attributes of each graph.
</details>
Figure 1: Combining topological and learned node features
#### Combining static and learned encoders
A third option leverages both of the two previously proposed ideas by combining a fixed graph representation with a learned graph representation (see Figure 1). To this end, the fixed graph representation can simply be concatenated with the learn graph representation. While we do not backpropagate gradients to the fixed graph representation, we can still backpropagate gradients to the GNN to train it.
### 3.2 Reasoning module
The reasoning module takes the previously generated vector representation as input and generates a binary classification as output. The reasoning module is based on a differentiable satisfiability solver proposed by (Wang, Chang, and Kolter 2017) and is explained in detail below.
#### Background: Differentiable Satisfiability
#### MAX-SAT
In Maximal Satisfiability Problems (MAX-SAT), we are interested in finding the assignment of $m$ binary variables $x_{i}\in\{-1,1\},i=1,\dots,m$ for some given rules, or
$$
\displaystyle\max_{x\in\{-1,1\}^{m}} \displaystyle\sum_{j\in[n]}\langle s_{j},x\rangle \tag{1}
$$
where $s_{ji}\in\{-1,0,+1\}$ are the rules of the MAX-SAT problem and $\langle s_{j},x\rangle=\lor_{i\in[m]}1_{s_{ji}x_{i}>0}$ . MAX-SAT is the relaxation of the Satisfiability (SAT) problem, where all the rules need to be true. The relaxation is useful, when the set of rules may generate an infeasible set of solutions and we are interested in knowing the solution that maximal satisfies the given rules.
#### SatNet: Differentiable MAX-SAT relaxation via Semi-definitive programming (SDP)
Here we consider the relaxation of the MAX-SAT problem as a SDP, (Wang et al. 2019; Wang and Kolter 2019; Wang, Chang, and Kolter 2017) , where the MAX-SAT problem defined in Eq.( 1) is relaxed by
$$
\displaystyle\min_{V\in\mathbb{R}^{K\times(k+1)}} \displaystyle\langle S^{T}S,V^{T}V\rangle \displaystyle\|v_{i}\|=1,\forall i\in\{\top,1,\dots,k\} \tag{2}
$$
where for each input variable $x_{i}$ we have an associated unitary vector $v_{i}\in\mathbb{R}^{K}$ , with some $K>\sqrt{2k}$ (Pataki 1998). $K$ is the size of the embedded space, while $k$ is the number of variables. The special variable $v_{\top}$ represents the true logic value and is used to retrieve the logic value of the solution. $S=[s_{\top},s_{1},\dots,s_{k}]/\operatorname{diag}(1/\sqrt{4|s_{j}|})\in \mathbb{R}^{m\times(k+1)}$ is the matrix representing the rules, while $V\in\mathbb{R}^{K\times(k+1)}$ is the matrix of the unitary vectors.
#### Mapping from the vector to the logic variable
The logic value is recovered by its probability defined as $P\{x_{i}\}=\frac{1}{\pi}\arccos{(-v_{i}^{T}v_{\top})}$ . The probability measures the radiant angle between the true vector and the variable vector, i.e. $v_{i}^{T}v_{\top}=\cos(\pi x_{i})$ . We can recover the discrete value by evaluating the sign, i.e. $x_{i}=\operatorname{sign}(P\{x_{i}\})$ .
#### Mapping from the logic variable to the vector
To generate the vectors from the logical values, we could use the following mapping $v_{i}=-\cos(\pi x_{i})v_{\top}+\sin(\pi x_{i})P_{\top}v_{i}^{\text{rand}}$ , where $P_{i}=I_{K}-v_{i}v_{i}^{T}$ is the projection matrix on the vector $v_{i}$ and $v_{i}^{\text{rand}}$ is a random unit vector.
#### Solution to the SDP relaxation
The solution of Eq.(2) is given by the fix point (Wang et al. 2019) $v_{i}=-\nicefrac{{g_{i}}}{{\|g_{i}\|}}$ , where $g_{i}=VS^{T}s_{i}-\|s_{i}\|^{2}v_{i}=VS^{T}s_{i}-v_{i}s_{i}^{T}s_{i}$ .
## 4 Experiments
To evaluate our proposed method, we perform graph classification experiments on synthetic without node features and real-world datasets with and without node features. For the graph classification tasks, we compute the mean prediction accuracy across all graphs in an unseen test set. In all experiments, we report the average result of three runs with three different random seeds to obtain more stable results. To better understand the robustness of the models, we also report the standard deviation (indicated by the $\pm$ symbol). Since we want to evaluate the potential benefits of encoding the topology into a fixed-sized bit string as described above, we filter graphs with a size larger than 15 and 20 nodes. As a consequence, our results are not directly comparable to prior works. Dataset details can be found in Table 1.
### 4.1 Architectures
Similar to prior works (Zhang et al. 2019), we use a graph neural network with 2 convolutional layers with an optional dropout layer after each convolution. A mean pooling layer is used after the convolutional layers to aggregate the obtained node features into a single vector that represents the entire graph. The pooling is followed by an additional layer to map the obtained intermediate representation to the final output. In contrast to our approach, which outputs only a single binary label, the GNN generates two outputs As typically done for graph classification, one output for each class: $\{0,1\}$ . for a binary classification task that indicates the probability of each class.
We implement three different versions of the proposed approach based on the previously presented fixed and learned graph representations. The first version, GRN ASC (adjacency string canonicalized) uses only the canonicalized adjacency string as graph representation. Second, we use a version that jointly learns the GRN and the GNN, which we denote as GRN GNN. Third, the architecture that uses a combination of both representations is denoted by GRN ASC+GNN. To obtain a meaningful comparison with the reference model, we use the same GNN architecture as described above. Instead of using an additional layer to make the class predictions, we use the reasoning module.
### 4.2 Hyperparameter optimization
To perform a hyperparameter optimization, we split the datasets into training, validation, and test splits with sizes of 80%, 10%, and 10% of the dataset, respectively, and report the result of the configuration with the best validation result for each run. For the GNN, we consider a hidden size in $\operatorname{Set}(32,64)$ , a learning rate in $\operatorname{Set}(0.01,0.001)$ , and test a dropout probability in $\operatorname{Set}(0.0,0.3)$ , where a dropout probability of $0.0$ means that no dropout is used. For the Satnet, we consider a learning rate in $\operatorname{Set}(0.1,0.01)$ and a number of rules $m$ and auxiliary variables $aux$ in $\operatorname{Set}(32,64)$ . To limit the search space, we only consider configurations with $m=aux$ . Adam optimizer is used to train all models.
| NCI1 | 240 | 26 | up to 15 |
| --- | --- | --- | --- |
| PROTEINS | 360 | 40 | up to 20 |
| IMDB-BIN | 400 | 40 | up to 15 |
Table 1: Dataset statistics
| GNN GNN GRN ASC | constant node degree - | ${\bf 0.87}\pm 0.02$ $0.86\pm 0.02$ ${\bf 0.87}\pm 0.11$ | $0.63\pm 0.05$ $0.60\pm 0.07$ ${\bf 0.67}\pm 0.10$ | $0.54\pm 0.09$ $0.64\pm 0.05$ $0.61\pm 0.07$ |
| --- | --- | --- | --- | --- |
| GRN GNN | constant | ${\bf 0.87}\pm 0.02$ | $0.61\pm 0.05$ | $0.48\pm 0.00$ |
| GRN GNN | node degree | $0.83\pm 0.02$ | $0.61\pm 0.03$ | ${\bf 0.67}\pm 0.05$ |
| GRN ASC+GNN | constant | $0.83\pm 0.09$ | $0.63\pm 0.13$ | $0.63\pm 0.06$ |
| GRN ASC+GNN | node degree | $0.80\pm 0.07$ | $0.62\pm 0.08$ | $0.62\pm 0.05$ |
Table 2: Prediction accuracy and standard deviation of three runs for real-world graphs without node features. Column ’Node Feature’ indicates which alternative feature has been used as input for the message-passing algorithm. Since GRN ASC only uses the topology string, it does not need alternative node features.
## 5 Results
In the following, we report the results on three different types of datasets. We report results on synthetic datasets to illustrate the benefits of the proposed method in challenging problems that cannot be solved by standard GNNs alone. We also report results on real-world datasets with and without node features.
### 5.1 Synthetic datasets
To compare the expressiveness of GRN versus GNN, we generated synthetic graph datasets. We randomly generated graphs with $n$ nodes. We used regular random graphs of fix degree $d$ ( $d$ -regular) and Erdos-Renyi with edge probability $p$ (Bollobás and Béla 2001). As prediction tasks we considered detecting the connectivity of the graph ( ), detecting the presence of motifs: triangles ( ), squares ( ) and $5$ -edges $4$ -nodes motif ( ). For $3$ -regular graphs we used $$ , while we used $$ . As expected (see Table 3), GNN is not able to detect with accuracy the presence of specific motifs in the graph. The GNN shows a more reasonable performance on the connectivity test, probably exploiting other correlated information. On the other hand, GRN exhibits superior performance, thus confirming that the use of topological information is necessary if the prediction task involves information related to the topology of the graph.
| GNN GRN ASC | 0.70 0.98 | 0.51 0.81 | 0.53 0.85 | 0.57 0.87 | 0.63 1.00 | 0.59 1.00 |
| --- | --- | --- | --- | --- | --- | --- |
Table 3: Results for synthetic graphs with Random Graphs (RG). Prediction tasks: for connectivity, for square motif counting, for $5$ edges motif counting and for triangle counting.
| GNN GRN GNN GRN ASC+GNN | ${\bf 0.88}\pm 0.04$ $0.87\pm 0.06$ $0.86\pm 0.04$ | ${\bf 0.83}\pm 0.06$ $0.82\pm 0.02$ $0.79\pm 0.06$ | $0.60\pm 0.04$ $0.62\pm 0.06$ ${\bf 0.65}\pm 0.11$ |
| --- | --- | --- | --- |
Table 4: Results for real-world graphs with node features.
### 5.2 Real-world datasets without node features
Next, we perform experiments on real-world datasets without node features. To this end, we use the NCI1 and the PROTEINS datasets without node features. Furthermore, we use the IMDB-BIN dataset. Since message-passing neural networks such as the GCN rely on node features for message passing, we use two different node feature alternatives. In the first version, we initialize all nodes with the same, constant value. In the second version, we initialize the feature vector of all nodes with their node degree in a one-hot encoding. Using a one-hot representation of the node degree is a strong, hand-crafted feature for GNNs in many datasets. The results of this experiment can be found in Table 2.
The results show that the GRN ASC and GRN GNN are able to outperform the baseline approaches in the PROTEINS and the IMDB-BIN datasets. Interestingly, GRN ASC that does not use the node degree as a feature performs best in PROTEINS, which suggests that the topology is highly informative in this dataset. In NCI1, several methods show a similar performance and GRN ASC+GNN does not perform well.
### 5.3 Real-world datasets with node features
In the last experiment, we evaluate the performance of different approaches in the NCI1, NCI109, and PROTEINS datasets with their original node features. The results in Table 4 show that the baseline GNN performs best in the NCI1 and NCI109 datasets, closely followed by GRN GNN. Additionally using the topology in the GRN ASC+GNN seems not to be beneficial in these two datasets. However, GRN ASC+GNN performs best in the PROTEINS dataset, which suggests that the model can leverage the information contained in the topology string. This observation confirms the result from Table 2, which also showed that the topology seems to be important in the PROTEINS dataset.
## 6 Conclusions
In this work, we present an approach to applying Satnet to graphs. Our experiments on synthetic datasets show that the approach can learn meaningful rules. Moreover, we find that rather simple GRN ASC outperforms the GNN baseline. Experiments on real-world datasets with and without node features are less conclusive.
In future work, other fixed representations can be used instead of the adjacency string, which limits the applicability of the approach to small and medium-sized graphs, or as an additional feature of the graph size is not too large. A promising idea is a representation based on the 1-WL graph isomorphism test. Furthermore, we noticed that jointly training the GCN and the SatNet can be difficult in practice because both networks require a different learning rate. Hence, it will be important to develop a robust training schedule to improve the training of the joint model. Inspiration for this can be gained from training procedures that have been developed for GANs that also consist of two modules that depend on each other.
## References
- Babai, Kantor, and Luks (1983) Babai, L.; Kantor, W. M.; and Luks, E. M. 1983. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science (Sfcs 1983), 162–171. IEEE.
- Bodnar et al. (2021) Bodnar, C.; Frasca, F.; Otter, N.; Wang, Y. G.; Liò, P.; Montufar, G. F.; and Bronstein, M. 2021. Weisfeiler and lehman go cellular: Cw networks. Advances in Neural Information Processing Systems, 34.
- Bollobás and Béla (2001) Bollobás, B.; and Béla, B. 2001. Random graphs. 73. Cambridge university press.
- Bronstein et al. (2021) Bronstein, M. M.; Bruna, J.; Cohen, T.; and Veličković, P. 2021. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104.13478.
- Chen et al. (2020) Chen, Z.; Chen, L.; Villar, S.; and Bruna, J. 2020. Can graph neural networks count substructures? arXiv preprint arXiv:2002.04025.
- Cingillioglu and Russo (2018) Cingillioglu, N.; and Russo, A. 2018. Deeplogic: Towards end-to-end differentiable logical reasoning. arXiv preprint arXiv:1805.07433.
- d’Avila Garcez and Lamb (2020) d’Avila Garcez, A.; and Lamb, L. C. 2020. Neurosymbolic AI: The 3rd Wave. arXiv:2012.05876.
- Dwivedi et al. (2021) Dwivedi, V. P.; Luu, A. T.; Laurent, T.; Bengio, Y.; and Bresson, X. 2021. Graph Neural Networks with Learnable Structural and Positional Representations. arXiv preprint arXiv:2110.07875.
- Evans and Grefenstette (2018) Evans, R.; and Grefenstette, E. 2018. Learning explanatory rules from noisy data. Journal of Artificial Intelligence Research, 61: 1–64.
- Gilmer et al. (2017) Gilmer, J.; Schoenholz, S. S.; Riley, P. F.; Vinyals, O.; and Dahl, G. E. 2017. Neural message passing for quantum chemistry. In International conference on machine learning, 1263–1272. PMLR.
- Kipf et al. (2018) Kipf, T.; Fetaya, E.; Wang, K. C.; Welling, M.; and Zemel, R. 2018. Neural Relational Inference for Interacting Systems. In Proceedings of the 35th International Conference on Machine Learning.
- Kipf and Welling (2016) Kipf, T. N.; and Welling, M. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
- Loukas (2019) Loukas, A. 2019. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199.
- Marcus (2020) Marcus, G. 2020. The Next Decade in AI: Four Steps Towards Robust Artificial Intelligence. arXiv:2002.06177.
- Maron et al. (2019) Maron, H.; Ben-Hamu, H.; Serviansky, H.; and Lipman, Y. 2019. Provably powerful graph networks. arXiv preprint arXiv:1905.11136.
- McKay and Piperno (2014a) McKay, B. D.; and Piperno, A. 2014a. Practical graph isomorphism, II. Journal of symbolic computation, 60: 94–112.
- McKay and Piperno (2014b) McKay, B. D.; and Piperno, A. 2014b. Practical graph isomorphism, II. Journal of Symbolic Computation, 60: 94–112.
- Morris et al. (2019) Morris, C.; Ritzert, M.; Fey, M.; Hamilton, W. L.; Lenssen, J. E.; Rattan, G.; and Grohe, M. 2019. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 4602–4609.
- Pataki (1998) Pataki, G. 1998. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of operations research, 23(2): 339–358.
- Qu et al. (2020) Qu, M.; Chen, J.; Xhonneux, L.-P.; Bengio, Y.; and Tang, J. 2020. Rnnlogic: Learning logic rules for reasoning on knowledge graphs. arXiv preprint arXiv:2010.04029.
- Scarselli et al. (2009) Scarselli, F.; Gori, M.; Tsoi, A. C.; Hagenbuchner, M.; and Monfardini, G. 2009. The Graph Neural Network Model. IEEE Transactions on Neural Networks, 20(1): 61–80.
- Shervashidze et al. (2011) Shervashidze, N.; Schweitzer, P.; Van Leeuwen, E. J.; Mehlhorn, K.; and Borgwardt, K. M. 2011. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12: 2539–2561.
- Veličković et al. (2017) Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Lio, P.; and Bengio, Y. 2017. Graph attention networks. arXiv preprint arXiv:1710.10903.
- Veličković et al. (2018) Veličković, P.; Cucurull, G.; Casanova, A.; Romero, A.; Liò, P.; and Bengio, Y. 2018. Graph Attention Networks. In Proceeding of the 6th International Conference on Learning Representations, 1–12.
- Wang, Chang, and Kolter (2017) Wang, P.-W.; Chang, W.-C.; and Kolter, J. Z. 2017. The mixing method: coordinate descent for low-rank semidefinite programming.
- Wang et al. (2019) Wang, P.-W.; Donti, P.; Wilder, B.; and Kolter, Z. 2019. Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver. In International Conference on Machine Learning, 6545–6554. PMLR.
- Wang and Kolter (2019) Wang, P.-W.; and Kolter, J. Z. 2019. Low-rank semidefinite programming for the MAX2SAT problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, 1641–1649.
- Weisfeiler and Leman (1968) Weisfeiler, B. Y.; and Leman, A. A. 1968. The Reduction of a Graph To Canonical Form and the Algebra which Appears Therein. 1–11.
- Zhang et al. (2019) Zhang, Z.; Bu, J.; Ester, M.; Zhang, J.; Yao, C.; Yu, Z.; and Wang, C. 2019. Hierarchical Graph Pooling with Structure Learning.