Differentiable M AX SAT Message Passing

Francesco Alesiani * 1 Cristóbal Corvalá * 1 Markus Zopf 1

Abstract

traditional neural network that fails to reason over discretevariables or combinatorial problems (Pogančić et al., 2019;
Cappart et al., 2021).

The message-passing principle is used in the mostpopular neural networks for graph-structured data.
However, current message-passing approaches
use black-box neural models that transform features over continuous domain, thus limiting thedescription capability of GNNs.

In this work, we explore an alternative to standard message passing. We propose to learn logic rules (which could
model for example binary arithmetics) end-to-end with adifferentiable satisfiability solver to encode how messages
are distributed within the graph. By modeling the node features as logical variables, we describe the relationship of
those features over the neighbor nodes using one or morelogical sentences. A feature is propagated over neighbornodes only if correct according to the graph logic rules.

In this work, we explore a novel type of message passing based on a differentiable satisfiability solver. Our model learns logical rules that
encode which and how messages are passed from
one node to another node. The rules are learned
in a relaxed continuous space, which renders thetraining process end-to-end differentiable and thus
enables standard gradient-based training. In our
experiments we show that M AX SAT-MP learns
arithmetic operations and that is on par with stateof-the-art GNNs on graph structured data.

Our approach M AX SAT-MP is a continuous-discrete approach and thus enjoys several benefits such as data efficiency and interpretability. For example in the arithmetic
experiments (subsection 4.1) the number of clauses is limited. Moreover, our experiments show (section 4) that ourapproach exceeds or is comparable accuracy of standard
message passing approaches.

1. Introduction

2. Background

Graph-structured data can be found in many domains such as
biology, chemistry, and computer science (Bronstein et al.,2021; Scarselli et al., 2008). Consequently, machine learning for graph-structured data is gaining more interest fromthe machine learning community.

2.1. Notation
An undirected graph is a pair G = (VG , EG ), where
VG = {v1 , . . . , vN } is finite set of vertices (nodes), andEG ⊆ {{u, v} : u, v ∈ VG , u ̸= v} is a symmetric, irreflexive, binary relation on VG , while e ∈ EG is called edge.
N (v) = {u : {v, u}, u ∈ V, {v, u} ∈ EG } is the set ofneighborhood of v and |·| denotes the size of a set. For acolumn vector h, hT is its transpose, and 1x is the indicatorfunction.

A key component of neural networks for graph-structured
data, so-called graph neural networks, is the message passing principle (Gilmer et al., 2017). The key idea of message
passing is to exchange messages between nodes in a graphsuch that representations for nodes or the graph can belearned. The obtained representations are used to address
tasks such as node classification (Kipf and Welling, 2016),
graph classification (Niepert et al., 2016), and missing nodefeature prediction (Rossi et al., 2021).

2.2. SAT and MaxSAT Problems
Satisfiability problems (SAT) consists of a set of boolean
variables (literals) that are related by a logical rules (clauses).
The rules that govern the relationship among the variable
are represented in conjunctive normal form (CNF), which
consists of a series of clauses joined by AND operators.
CNF represents any propositional logic (sec.7.5 of (Russell,2010)) Each of the clauses contains some of the variables, ortheir negation, as for example (s11 x1 ∨ . . . ∨ s1n xn ) ∧ . . . ∧(sm1 x1 ∨ . . . ∨ smn xn ), where sji determines whether the

GNNs provide limited graph reasoning capabilities they use*

Equal contribution 1 NEC Laboratories Europe, Heidelberg, Germany.
Correspondence to: Francesco Alesiani<Francesco.Alesiani@neclab.eu>.
Published at the Differentiable Almost Everything Workshop of the
40 th International Conference on Machine Learning, Honolulu,
Hawaii, USA. July 2023. Copyright 2023 by the author(s).

1Differentiable M AX SAT Message Passingx̄i ∈ S k−1 are mapped back to a probabilistic value using
Equation 2.

variable xi ∈ {⊥, ⊤}1 is present and/or negated in clausej , for example if s11 = 1 then x1 participates in the firstclause, while if s11 = −1 then x1 is negated into ¬x1 , while
if s11 = 0 then x1 is not present. The objective of the SAT
problem is to find the truth values of the variables so that the
CNF statement is fulfilled, while a Maximum Satisfiability
problems (MaxSAT)’s goal is to find the values of variables
that satisfies the maximum number of clauses.

To improve convergence, the vectors x̄i are generated fromthe logical values as x̄i = − cos(πxi )x̄0 +sin(πxi )P⊤ x̄rand
i ,where Pi = IK − x̄i x̄Ti is the projection matrix on theis a random unit vector. The soluvector x̄i , while x̄randition of Equation 3 is given as the fix point equation (Wanget al., 2019) x̄i = − ∥ggii ∥ , with gi = X̄S T si − ∥si ∥2 x̄i =X̄S T si − vi sTi si . SATNet (Wang et al., 2019) provides anefficient way to back-propagate the gradients with respect
to S. The complexity of solving Equation 3 (Wang et al.,2019), for both forward and backward steps, is O(knmT ),with T being the maximum number of iterations. Additional
information is provided in the Appendix H.

2.3. SATNet
The SATNet (Wang et al., 2019) is a satisfiability solver thatmaps the variables and parameters of the MaxSAT problem
into a continuous high-dimensional space. In this relaxation, the MaxSAT problem is defined as Semi-Definite
Programming (SDP) problem, which allows the algorithm
to be integrated as a layer in machine learning systems.

In the following, we will use y = M AX SATN
M (x) to denotea M AX SAT problem with N logic variables and M clauses,
where the input variable x ∈ [0, 1]dx and output variablesy ∈ [0, 1]dy have a combined size of dx + dy = N . Whenever multiple inputs x1 , x2 , . . . are presented to M AX SAT,
these are concatenated in a single input x.

Given a M AX SAT problem with n variables m clauses,
we denote the variables of the SAT as xi ∈ {−1, 1} fori ∈ {1, . . . n}, where xi represent the i-th variable truth
value. Let sji ∈ {−1, 0, 1} denote the parameters of the
SAT for i ∈ {1, . . . n} and j ∈ {1, . . . m} . The valueof sji represents thus the sign (if present) of variable xi
in clause j. The MaxSAT problem consists of finding thevalues of xi so thatmax nx∈{−1,1}nm _X

1sji xi >0 ,2.4. Message Passing
Message passing (Gilmer et al., 2017) consists of threesteps. First, for each pair of connected nodes u, v, a messagem(v, u) is computed. Second, for each node v, all messagesm(v, u) with u ∈ N (v) are aggregated. Third, the node
representation hv of v is updated based on the aggregatedmessages.

(1)

j=1 i=1

The SAT variables xi are given a probabilistic interpretation
and are relaxed by a map into the k-dimensional sphere:
P (xi = 1) ∈ [0, 1] → x̄i ∈ S k−1 ⊂Rk , with ∥x̄i ∥ = 1 andS k−1 = {x̄ ∈ Rk : ∥x̄∥ = 1}. The probability of xi beingtrue is set to
P (xi = 1) = cos−1 (−x̄Ti x̄0 )/π,

3. MaxSAT-based Message Passing
We propose a message aggregation procedure where neighboring nodes’ features, associated with a central node,
are logically related to the updated central node’s feature
through an unknown MaxSAT (see Figure 4 in Annex), i.e.
a set of logic rules. Our motivation lies in the intuition thatthe information carried across graph edges and the updated
nodes can be represented as a set of truth variables. The
logic rule that fulfills the MaxSAT related to them can inprinciple be learned and computed from the neighbor nodes
and is inherent to the nature of information represented in
the graph.

(2)

given the truth direction x̄0 . The coefficients sji are also
mapped into the real numbers s̄ji ∈ R, with s̄j0 = −1. The
Semi-Definite Programming (SDP) of the MaxSAT of Eq.1
ismin⟨S T S, X̄ T X̄⟩, such that ∥x̄i ∥ = 1 ∀i

(3)

X̄

In the proposed model, we use a differentiable rule learning approach to learn the MaxSAT behind the aggregation.
Node features and aggregated messages will therefore acquire a probabilistic nature according to the relaxation process discussed in the previous section.

where X̄ ∈ Rk×(n+1) and S ∈ Rm×(n+1) are thep matrices
formed by the column vectors x̄i and si = s̄i / 4∥s̄i ∥ respectively. Given a set of known parameters S, the MaxSAT
as in Equation 3 is solved via a block coordinate descentmethod that converges to the optimal global point of the SDP(Wang et al., 2017). The solutions of the relaxed MaxSAT

3.1. Recursive MAXSAT Message Passing

1⊥ is the logic false value, and ⊤ is the logic true value. In thefollowing, the true value will be mapped to +1, while the false
value into −1.

The aggregation function over the neighbors of a node is
implemented recursively similar to Recurrent Networks
2

Differentiable M AX SAT Message Passing

3.3. Logic attention bit
An attention bit is used to help the solver to decide if
the message should be processed or not. We call RAM AX SAT-MP, the model that uses the attention bit. The
attention bit is computed between the center node andl lleach of its neighbors alji = σ(hlT
j W hi − b ) and themessage update includes the additional information mki =3dl +1
M AX SATM(mik−1 , alji , hlj ), ∀j ∈ N (i) where σ is the
non-linear Sigmoid function, W l ∈ Rdl ×dl , bl ∈ Rdl aretrained parameters and mki is the memory of the aggregation
related to node i at step k, and dl is the feature dimensionl l
ath l-layer. Self-attention bit alj = σ(hlT
j W hj ) is used
when the central node feature is missing, and the attention
would provide self-filtering information for the SAT.

Figure 1. M AX SAT variables: Visualization of the Message Passing aggregation using a MaxSAT problem at the l-layer of the network. mki , mk−1
are the messages when considering the i-nodeiof the graph, while hlj is the feature of the j-neighbout node. The
attention bit alji , described in subsection 3.3, helps the MaxSAT toselect the relevant features.

(Hochreiter and Schmidhuber, 1997), where the aggregation
step uses a MaxSAT solver. We call it R-M AX SAT-MP,
i.e. Recursive MaxSAT Message Passing.
Using node i and the set of its neighbor features hli , hlj ∈[0, 1]dl , j ∈ N (i), where dl is the dimension of the featuresat the l-layer, and the logic value is represented as a probability (Equation 2), the R-M AX SAT-MP applies a logic ruleto all of those elements in a recursive manner, see Figure 1.
It starts operating on two of them and the output is used as
memory for the next operation with the next element until
the whole set takes part in the aggregation. The memory isa key element of our aggregation since it contains the important information from all neighbor nodes to help to computea logic-related output. Let {hlj : j ∈ N (i)} be the set offeatures entering the node vi , where j is the neighbor nodeindex. With reference to Figure 1, we proposed aggregationof the following form:k−1lmki = M AX SAT3d, hlj )M (mi|N (i)|

hl+1
= mi
i

, m0i = hli∀j ∈ N (i)Figure 2. Visualization of the batch version of the M AX SAT (BM AX SAT-MP), where multiple nodes’ features are considered atonce.

3.4. Batch aggregation
Batch M AX SAT-MP (B-M AX SAT-MP) (see Figure 2)
computes outputs over K neighboring nodes’ features atonce in a single forward pass, where K is fixed to the maximum node degree of the network by concatenating theordered node features

(4)
(5)

(n+2)dlhl+1= M AX SATM
iwhere mki is the message/memory that aggregates the information from the neighboring nodes for the ego-node, whosefeature, hli , can be used as the initial state.

(φ(hli , hlj1 , . . . , hljn )),(6)

where φ refers to an ordering function, j ∈ N (I), and n =|N (i)|. This model only requires one evaluation and does
not require hidden states, thus improving training stability.
For larger graphs, K-neighbors sampling is used to reduce
the size of the MaxSAT problem.

3.2. Canonical ordering
In Equation 4, the nodes do not have a predefined order,
thus, to implement an equivariant or invariant Message Passing method for graph data (Bronstein et al., 2021), i.e. tothe group of permutations over the nodes, we propose toorder the features before they are processed sequentially(Niepert et al., 2016). This ordering consists of mapping
the binary representation encoded in the features to thereal numbers and sorting the neighbors in decreasing order.
Whenever two or more nodes have the same feature’s values, the relative order is not relevant for the permutation
invariant property, since the result of the node’s features
aggregation of Equation 4 is independent of the permutationof these nodes.

4. Experiments
Baselines To evaluate M AX SAT-MP, we consider tworecursive networks, LSTM (Hochreiter and Schmidhuber,
1997) and GRU (Cho et al., 2014), that use a hidden state
to propagation of information over consecutive inputs. For
message passing on graph structures, we consider the standard graph GCN convolution (Kipf and Welling, 2016),
the GAT convolution which contains an attention mechanism to assign weights to edge messages (Veličković et al.,2017) and the Graph Isomorphism Network (GIN) (Xu et al.,2018), which improves GNN’s expressive power. Tran3

Differentiable M AX SAT Message Passing
Method / task
Trained/ tested on

2→2Addition
3→3

4→4

2→2

Multiplication
3→3
4→4

R-M AX SAT-MP
B-M AX SAT-MP

1.0000(000)-0.9284(532)0.9958(008)0.8196(493)0.9859(105)0.9633(055)-

0.9554(42)0.9586(3)0.9030(2)0.9758(018)

LSTM
GRU
GCN
GAT
GIN

0.8254(267)0.8894(280)
0.5753(158)
0.7946(247)
1.0000(000)0.4787(310)0.7779(600)0.6427(56)0.7713(24)0.9999(001)0.7109(47)0.7670(30)0.6735(21)0.7690(78)0.9990(011)0.8000(286)0.8196(54)0.6291(51)0.7917(204)0.8070(106)0.8392(64)0.8509(54)0.7171(40)0.8313(35)0.8321(15)0.8859(58)0.8848(19)0.7907(2)0.8709(31)0.8433(17)Table 1. In this table we report the performance in terms of accuracy for the Addition of 5-bit numbers and Multiplication with modulo of
5-bit numbers. The best and second-best results (if overlaps statistically) are reported, where the top results are also underlined. The
error, expressed as standard deviation, is reported in parenthesis and represents the last relevant digits. For example 1.234 ± 0.050 isrepresented as 1.234(50). The dash represents that B-M AX SAT-MP is equivalent to R-M AX SAT-MP.

4.2. Graph Classification

former based model have been adapter to work with graphdata, for example the Graph Transformer of the Unified
Message Passaging Model (UniMP) (Shi et al., 2021).

For graph classification, we consider three datasets fromthe graph learning benchmarks (Morris et al., 2020a): MUTAG, Mutagenicity, and PROTEINS, and the ZINC dataset(Sterling and Irwin, 2015; Gómez-Bombarelli et al., 2018).
The first two contain graphs with one-hot encoded features.
The PROTEINS dataset consists of an integer number plus
a one-hot encoded three-class features. All continuous variable of the datasets have been converted into 5-bits integers. Use use uniform architectures composed of 2 layers.
For M AX SAT-MP we used as message aggregation RAM AX SAT-MP, and B-M AX SAT-MP, followed by a max
pooling and a final dense linear layer. We train our models
using Adam (Kingma and Ba, 2014) optimizer and the binary cross entropy loss (Zhang and Sabuncu, 2018) over a
80/20 split. The results in Table 2, show that in complex
tasks such as graph classification where multiple aggregations are involved, the MaxSAT-based models are capableof performing similarly to the baselines.

4.1. Learning arithmetic operations
Basic arithmetic over integer numbers are implemented,
even in modern computer architectures, using logic rules,
we thus test the ability of the M AX SAT-MP in learning
arithmetic operations. Therefore design two experiments:
1) Addition of 2, 3, and 4 numbers; 2) Multiplication withmodulo of 2, 3, and 4 numbers. The synthetic datasets
consist of numbers in binary representation with a length offive bits (i.e. integer numbers from 0 to 31). For the addition
over 2, 3, 4 elements, we take all possible pairs, triplets, andquadruplets whose sum does not exceed 31 bits, while formultiplication we used modulo 32 operations. A proper stargraph dataset is build to test graph neural network. From
the results on addition and multiplication in Table 1, we
notice M AX SAT-MP learns better arithmetic operations
than recurrent networks such as GRU and LSTM. Comparedwith graph-based convolutions (GCN and GAT) we discoverthat M AX SAT-MP have more power to aggregate messages
on a logic-based setting. GIN shows better performance inthe addition, but underperforms in the multiplication dataset.

5. Conclusions
In this work, we propose to model the properties of graphstructure data using logic rules that can be learned throughend-to-end training. We exploit the structure of message
passing and proposed an invariant-equivariant architecture
based on an ordering function and a flexible attention
mechanism. Experiments that M AX SAT-MP learns rules
for arithmetic operations, while on molecular datasets isequal capable in classifying graphs. Limitations of thiswork: while M AX SAT solution computation is efficient(O(knmT ) complexity), it has higher cost then regular neural networks.

Graph Classification
MUTAG

Mutagenicity

PROTEINSZINC

B-M AX SAT-MP
RA-M AX SAT-MP

0.9211(456)0.9035(152)0.7949(123)0.8078(130)0.7227(262)0.8690 (0.0206)

GCN
GAT
GIN
Graph Transformer

0.7632(912)
0.7979(405)0.8502(402)-

0.7919(131)0.7905(87)0.8150(149)-

0.7047(324)0.6811(419)0.6922(475)-0.9025 (0.0035)
0.9028 (0.0055)
0.9114 (0.0036)
0.9012 (0.0023)

Table 2. Standard deviation is reported with the last n position.
The best and second-best results (if it overlaps statistically) are
reported, where the top results are also underlined. The accuracy
is reported as in Table 1.

4

Differentiable M AX SAT Message Passing

R EFERENCES

Wouter Kool, Herke Van Hoof, and Max Welling. Attention,
learn to solve routing problems! ICLR, 2019.

Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar
Veličković. Geometric Deep Learning: Grids, Groups,
Graphs, Geodesics, and Gauges, May 2021. URL http://arxiv.org/abs/2104.13478.

Juho Lee, Yoonho Lee, Jungtaek Kim, Adam R. Kosiorek,
Seungjin Choi, and Yee Whye Teh. Set transformer:
A framework for attention-based permutation-invariant
neural networks, 2019.

Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi,
Christopher Morris, and Petar Veličković. Combinatorial
optimization and reasoning with graph neural networks.
arXiv preprint arXiv:2102.09544, 2021.

Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The
concrete distribution: A continuous relaxation of discreterandom variables. arXiv:1611.00712, 2016.

Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau,
and Yoshua Bengio. On the properties of neural machinetranslation: Encoder-decoder approaches. arXiv preprint
arXiv:1409.1259, 2014.

Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron
Lipman. Invariant and equivariant graph networks. In
International Conference on Learning Representations,2018.

Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro
Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets, 2020.

Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, andYaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32,
2019.

Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol
Vinyals, and George E. Dahl. Neural Message Passing for
Quantum Chemistry, June 2017. URL http://arxiv.
org/abs/1704.01212.

Christopher Morris and Petra Mutzel. Towards a practicalk-dimensional weisfeiler-leman algorithm. arXiv preprint
arXiv:1904.01543, 2019.

Rafael Gómez-Bombarelli, Jennifer N. Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamı́n SánchezLengeling, Dennis Sheberla, Jorge Aguilera-Iparraguirre,
Timothy D. Hirzel, Ryan P. Adams, and Alán AspuruGuzik. Automatic chemical design using a data-driven
continuous representation of molecules. ACS Central
Science, 4(2):268–276, Feb 2018. ISSN 2374-7943. doi:
10.1021/acscentsci.7b00572.

Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learningwith graphs. arXiv preprint arXiv:2007.08663, 2020a.

Sepp Hochreiter and Jürgen Schmidhuber. Long ShortTerm Memory. Neural Computation, 9(8):1735–1780,
11 1997. ISSN 0899-7667. doi: 10.1162/neco.1997.9.
8.1735. URL https://doi.org/10.1162/neco.
1997.9.8.1735.

Mathias Niepert, Mohamed Ahmed, and Konstantin
Kutzkov. Learning convolutional neural networks forgraphs. In International conference on machine learning,
pages 2014–2023. PMLR, 2016.

Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv:1611.01144,
2016.

Gábor Pataki. On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of operations research, 23(2):339–358,
1998.

Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson.
An efficient graph convolutional network technique forthe travelling salesman problem. arXiv:1906.01227,
2019.

Max B Paulus, Chris J Maddison, and Andreas Krause.
Rao-blackwellizing the straight-through gumbel-softmax
gradient estimator. page 11, 2021.

Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-ordergraph embeddings. Advances in Neural Information Processing Systems, 33:21824–21840, 2020b.

Giovanni Pellegrini, Alessandro Tibo, Paolo Frasconi, Andrea Passerini, and Manfred Jaeger. Learning aggregation
functions, 2021.

Diederik P Kingma and Jimmy Ba. Adam: A method forstochastic optimization. arXiv preprint arXiv:1412.6980,
2014.

Marin Vlastelica Pogančić, Anselm Paulus, Vit Musil,
Georg Martius, and Michal Rolinek. Differentiation of
blackbox combinatorial solvers. In International Conference on Learning Representations, 2019.

Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2016. URL
https://arxiv.org/abs/1609.02907.
5

Differentiable M AX SAT Message Passing

Haiquan Qiu, Yongqi Zhang, Yong Li, and Quanming
Yao. Logical expressiveness of graph neural network
for knowledge graph reasoning, 2023.

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.
How powerful are graph neural networks?, 2018. URL
https://arxiv.org/abs/1810.00826.

Meng Qu, Junkun Chen, Louis-Pascal Xhonneux, Yoshua
Bengio, and Jian Tang. RNNLogic: Learning Logic Rules
for Reasoning on Knowledge Graphs. In International
Conference on Learning Representations, 2021.

Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy,
Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic
reasoning with graph neural networks. arXiv preprint
arXiv:2001.11850, 2020.

Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and MichaelBronstein. On the unreasonable effectiveness of feature
propagation in learning on graphs with missing node features. arXiv preprint arXiv:2111.12128, 2021.

Zhilu Zhang and Mert Sabuncu. Generalized cross entropy
loss for training deep neural networks with noisy labels.
Advances in neural information processing systems, 31,
2018.

Stuart J Russell. Artificial intelligence a modern approach.
Pearson Education, Inc., 2010.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neuralnetwork model. IEEE transactions on neural networks,
20(1):61–80, 2008.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong,Wenjin Wang, and Yu Sun. Masked label prediction:
Unified message passing model for semi-supervised classification, 2021.
Alessandro Sperduti and Antonina Starita. Supervised neural networks for the classification of structures. IEEE
Transactions on Neural Networks, 8(3):714–735, 1997.
Teague Sterling and John J. Irwin. Zinc 15 – ligand discovery for everyone. Journal of Chemical Information andModeling, 55(11):2324–2337, Nov 2015. ISSN 15499596. doi: 10.1021/acs.jcim.5b00559.
Petar Veličković, Guillem Cucurull, Arantxa Casanova,
Adriana Romero, Pietro Liò, and Yoshua Bengio. Graphattention networks, 2017. URL https://arxiv.
org/abs/1710.10903.
Po-Wei Wang and J Zico Kolter. Low-rank semidefinite programming for the max2sat problem. In Proceedings of the
AAAI Conference on Artificial Intelligence, volume 33,
pages 1641–1649, 2019.
Po-Wei Wang, Wei-Cheng Chang, and J. Zico Kolter. The
mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints, 2017. URL
https://arxiv.org/abs/1706.00476.
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter.
Satnet: Bridging deep learning and logical reasoning
using a differentiable satisfiability solver. In International Conference on Machine Learning, pages 6545–
6554. PMLR, 2019.
6

Differentiable M AX SAT Message Passing

Supplementary Materials

Neural Combinatorial Optimization (NCO) The combinatorial problem can be solved using heuristics, NCO methods use deep neural networks to learn adaptable heuristics
either using supervised learning or reinforcement learning(Joshi et al., 2019; Kool et al., 2019). These approaches
could be alternatives to the one proposed in this work.

A. Related Work
Deep learning on graphs and in particular graph neural networks (GNNs) has been extensively studied in the last few
years (Sperduti and Starita, 1997; Scarselli et al., 2008;
Kipf and Welling, 2016; Gilmer et al., 2017). The predominant paradigm is message passing (Gilmer et al., 2017),
which propagates information using a learnable non-linear
function on the graph. Among the most popular architecture is GCN (Kipf and Welling, 2016), where the graphis represented using the normalized adjacent matrix, GAT(Veličković et al., 2017), where the weights of multiple
heads on the node are mixed with learnable functions, andGraph Isomorphism Network (GIN) (Xu et al., 2018), which
achieves the same discriminative power level of WeisfeilerLehman (WL) isomorphism test. RNNLogic (Qu et al.,2021) uses an EM-based algorithm to learn a set of rules forreasoning on knowledge graphs. Contrary to our approach,the model is not differentiable. In (Niepert et al., 2016)
the authors consider a fixed canonical ordering, while we
use a fixed function, which depends on the current node’s
feature. To overcome the limited expressive power of GNN,
recently alternative approaches have been proposed as in(Maron et al., 2019; 2018; Morris et al., 2020b; Morris andMutzel, 2019), where WL-k (k ≥ 1) networks are described,
whose complexity, however, increases exponentially withthe expressive level k.

B. Limitations of the proposed approach
We recognize some limitations of the proposed approach.
First, the dataset’s input features are considered discreteand the dataset is generated at least partially according tosome logic rules. If the input data is described with continuous variables and quantization of the input values does not
introduce high distortion, then the model can be used. In
some situations, we can employ an initial nonlinear layer toencode the features either into discrete features (for example
using (Jang et al., 2016; Maddison et al., 2016; Paulus et al.,2021)) or into continuous value in [0, 1]. Otherwise, otherapproaches are more appropriate. Training of the model
is longer because of the recursive nature of the model andproportional to the number of neighbors of the nodes, but
the number of variables is similar to alternative methods.
With the batch architecture, the computational time and convergence are comparable with the classical forward neuralnetwork.

C. Example Application
For example in Figure 3, the variable describing if themolecule is Alanine or Glycine is set based on the number of hydrogen atoms around the carbon atom and thepresence of three or two carbon atoms. We thus assume
that a collection of logical rules can be collected at the levelof the single atom and then verified by pooling the logicalvariables at the level of the whole graph.

Learning Aggregation Function and Learning on Sets
An alternative line of work addresses the improvement in
the aggregation function in current graph neural netwok andmessage passing architectures. (Corso et al., 2020),(Pellegrini et al., 2021). Another alternative direction is discard
the graph straucture and directly learn over sets (Lee et al.,2019). These works do not attempt to model the learning
process using logic clauses.

CH3
H3 N+

Reasoning in Knoledge Graphs Reasoning over categorical data is a critical task in Knowledge Graphs (Zhang et al.,2020),(Qiu et al., 2023). In this application the informationin organized in triplet and infgerence of new relationships
or links an important task.

C

H

C

O−

H3 N+

H
O
Alanine

C

C

O−

H
O
GlycineFigure 3. Alanine and Glycine Molecules; the difference is in thepresence of a specific sub-structure or the abundance of specificatoms.

Discrete latent variables An alternative way to model
reasoning is to use discrete latent variables. To integrate discrete variables into traditional differentiable architectures,various gradient estimations have been proposed (Jang et al.,2016; Maddison et al., 2016; Paulus et al., 2021). Unfortunately, these models only mimic the discrete nature of
the variables but do not capture the underlying reasoning
mechanism.

D. Message Passing Visualization
E. Additional Experiments
E.1. Learn arithmetic: addition and multiplication
To support our motivation that logical reasoning can befound in common machine learning problems, we com7

Differentiable M AX SAT Message Passing

aggregate messages on a logic-based setting, which is notbased only on a sum aggregation such as the GCN’s and
GAT’s. Taking a look at the specific results, in addition, we
find out that M AX SAT-MP give satisfactory results in thistask. When training on pairs of numbers the R-M AX SATMP achieves a perfect score together with the GIN.
We notice also that adding elements to the recursion makes
the performance of the R-M AX SAT-MP drop by 7.2% and18.0%. GIN maintains its almost perfect score when training
on quadruplets. The B-M AX SAT-MP is still capable tocapture the addition operation maintaining its performanceover 98, 5% when it is trained on quadruplets.

Figure 4. M AX SAT Message passing: Visualization of the Message Passing aggregation using a MaxSAT problem. We use theMethane molecule from Figure 3, where the carbon atom is thecurrent node. The neighbor nodes are visualized according to theadopted notation. The neighbor nodes N (v) are first ordered (subsection 3.2) and then aggregated using Equation 4.

We conclude from this that the R-M AX SAT-MP is sensible
to lose information as explained in subsection 3.4 when
the input has more elements. This idea is supported whenlooking at the uncertainty of the results. B-M AX SAT-MP
has more stable results while the recursive version did only
sometimes achieve similar scores (and could not learn inthe others). For the multiplication task, R-M AX SAT-MP
achieves the best accuracy score when training with pairs.
As before, B-M AX SAT-MP has the peculiarity that theirresults stay similar, over 95.8%, with the three datasets.

pare the learning capability of arithmetic operations of both
M AX SAT and existing approaches. Basic arithmetics overinterger numbers are implmented, even in modern computerarchitectures, using logic rules, we test the ability of the
M AX SAT-MP in learning those rules. Therefore we take
into account two experiments: 1) Addition of 2, 3, and 4
numbers; 2) Multiplication with modulo of 2, 3, and 4 numbers. The synthetic datasets consist of numbers in binary
representation with a length of five bits (i.e. integer numbers
from 0 to 31). For the addition, we take all possible pairs,
triplets, and quadruplets whose sum does not exceed 31.
For multiplication, we consider all possible pairs, triplets,and quadruplets. The labels are set to be the result of addition/multiplication with modulo 32 of those numbers. The
recurrent networks and the M AX SAT-MP are tested by asimple forward pass on the set of numbers. To test thosesets on our graph-based benchmarks, we construct a stargraph dataset (from the previous sets) with an unlabeled
center node whose neighbors correspond to the numbers to
be operated. The output after a message aggregation should
give us an insight into their ability to learn the arithmetic
operation we are studying.

E.1.2. G ENERALIZATION OF A RITHMETIC L EARNEDO PERATIONS
We explore if our models can generalize the arithmetic operation on a different aggregation size, by testing them withthe other datasets that were not used for training. (For example, the M AX SAT-MP that was trained with pairs of
numbers tested on triplets and quadruplets). We report theseresults on Table 3 and Table 4. For the addition, we observein general that the R-M AX SAT-MP is able to generalize
when it was trained on pairs, but in the other experiments,
they are not, showing decreases in performance over 12%.
On the other hand, B-M AX SAT-MP proves to be more
successful in this task, maintaining their ability to learn
pair multiplication at 99.4% and 93.7% in the triplet andquadruplet experiments respectively. Unfortunately, thisachievement is obscured by the fact the GIN is able to generalize in all cases with scores over 99%.
We report a similar generalization behavior on the multiplication task with M AX SAT-MP. In contrast to its recursive
version, the accuracy of B-M AX SAT-MP does not decrease
more than 3% for the pairs and triplet experiments and it
decreases slightly more, by 5.4%, when it is trained on four
numbers and tested on two.

E.1.1. R ESULTS OF L EARNING ARITHMETIC
The results of learning arithmetic are summarized in Table 1
for addition and for multiplication. We report the mean
accuracy per bit of the binary rounded results given by themodels. In general, we notice that our model learns muchbetter arithmetic operations than recurrent networks such as
GRU and LSTM. This is evidence of that the M AX SAT-MP
are more capable of encoding logic functions and carrying
them across a memory state. Also, if we take a general viewof the results of the graph-based convolutions (GCN and
GAT) we discover that M AX SAT-MP have more power toE.2. Node Missing Data
As a second step, knowing that the R-M AX SAT-MP is capable to learn an arithmetic operation on binary numbers,
we move on to real datasets whose features are represented8Differentiable M AX SAT Message Passing
Training on 2, 3, 4 number set (addition, out-domain evaluation)
Tested on
R-M AX SAT-MP
B-M AX SAT-MP
LSTM
GRU
GCN
GAT
GIN

2→3

2→4

3→2

3→4

4→2

4→3

1.0000(000)-0.9990(015)-0.8010(1783)
0.9938(059)

0.7875(1379)-

0.6508(1529)
0.9379(578)0.6438(1927)
0.9709(247)0.6027(1481)
0.6903(233)
0.6387(61)0.6075(91)0.9199(44)0.5337(1268)
0.6034(261)
0.6727(36)0.5440(150)0.8228(82)0.5870(526)0.5957(1301)
0.5918(258)0.6421(189)1.0000(000)0.4787(310)
0.5332(1624)
0.6736(16)0.6654(76)0.9679(039)

0.5886(40)0.5577(519)
0.6013(340)
0.7038(147)
0.9987(022)0.6393(73)0.6304(167)
0.6384(39)0.6688(79)0.9999(002)

Table 3. In this table we show the accuracy results for the Addition of 5-bit numbers, where we test the generalization (out-distribution),where the models are trained on 2, 3, 4 number-sets. The best and second-best results (if overlaps statistically) are reported, where the top
results are also underlined. The accuracy is reported as in Table 1. The dash represents when B-M AX SAT-MP can not be used since thenumber of operations is larger than K.
Training on 2, 3, 4 number sets (multiplication, out-distribution)
2→3

2→4

3→2

3→4

4→2

4→3

R-M AX SAT-MP
B-M AX SAT-MP

0.9445(048)-0.9409(066)-0.7221(1060)
0.9306(016)

0.9013(543)-0.7884(39)0.9218(036)0.8544(1)0,9541(014)

LSTM
GRU
GCN
GAT
GIN

0.7654(334)0.7539(288)0.7160(16)0.7426(174)0.5290(59)0.7462(367)0.7707(489)0.7909(4)0.7226(440)0.4970(68)0.6514(134)0.7672(178)0.6116(127)0.7122(78)0.5945(256)0.8001(171)0.8699(167)
0.7903(7)0.8499(33)0.6138(45)0.6556(313)0.7063(568)0.6128(73)0.6963(183)0.6278(43)0.7676(443)0.8037(230)
0.7121(28)0.7891(45)0.7165(25)Tested on

Table 4. In this table we show the accuracy results for the Multiplication with modulo of 5 bit numbers, where we test the generalization(out-distribution), and where the models are trained on 2, 3, 4 number-sets. The best and second best results (if overlaps statistically) are
reported, where the top results are also underlined. The accuracy is reported as in Table 1.

in binary or one-hot encoding. We follow the assumption,that there is some logical operation, similar to an arithmetic
operation, that can be performed on messages toward a specific node. This operation would help to discern newer or
missing node representations on a graph, for instance, tofind node labels when data is not available, from the neighborhood information. Missing node data prediction consists
in predicting node features based on the information thatcan be gathered from their neighborhood. It is a useful task
when the dataset is incomplete, but there is still information
enough to capture the missing data.

applying a soft-max layer to the output.
E.2.1. R ESULTS OF N ODE M ISSING FEATURE TASKAs shown in Table 5, the ability of the M AX SAT-MP to findthe correct label based on closest neighbor message passing
is similar to or slightly better that the other models.
On the MUTAG dataset, the Satnet achieves an accuracyof 93.7% which is somewhat better than the results of thebaselines which reach 91.3%. This difference is more remarkable in the case of the Mutagenicity dataset where thedifference is over 7% with respect to the best of the GNN
networks. The results achieved on the ENZYMES dataset
do not exhibit a particular improvement over the baselines.

We set up our experiment on three datasets from the benchmarks for graph learning TUDataset (Morris et al., 2020a)
MUTAG, Mutagenicity, and ENZYMES. For training, we
set 20% of all the nodes to be test nodes: their features are
set to zero, meaning that they are unknown. The rest of thenodes are the training nodes. During each training iteration(mini-batch), 10% of the training nodes are set to zero, andtheir features are inferred at training time. We use a similararchitecture as in the previous experiment, composed of
one layer of message aggregation with our three models
and the baselines to gather neighborhood information; andone linear layer for non-probabilistic outputs. The labelsof the nodes are one-hot encoded features. Therefore we
optimize the cross entropy loss for multiclass classificationand evaluate performance using classification accuracy afterE.3. Graph Classification
We further investigate the performance of the proposed
method for the task of graph classification. We consider
three datasets from the same graph learning benchmarks(Morris et al., 2020a): MUTAG, Mutagenicity, and PROTEINS. We additionally tested on the ZINC dataset (Sterling and Irwin, 2015; Gómez-Bombarelli et al., 2018). The
first two contain graphs with one-hot encoded features. The
PROTEINS dataset consists of an integer number plus a onehot encoded three-class features. That integer number was”clamped” between the values 0 and 31, the interval where9Differentiable M AX SAT Message Passing
Graph Classification

Node Missing Data
MUTAG

Mutagenicity

MUTAG

Mutagenicity

PROTEINSZINC

B-M AX SAT-MP
RA-M AX SAT-MP

0.9211(456)0.9035(152)0.7949(123)0.8078(130)0.7227(262)0.8690 (0.0206)

GCN
GAT
GIN
Graph Transformer

0.7632(912)
0.7979(405)0.8502(402)-

0.7919(131)0.7905(87)0.8150(149)-

0.7047(324)0.6811(419)0.6922(475)-0.9025 (0.0035)
0.9028 (0.0055)
0.9114 (0.0036)
0.9012 (0.0023)

ENZYMESR-M AX SAT-MP*B-M AX SAT-MP
RA-M AX SAT-MP

0.9372(031)
0.9201(22)0.9365(002)0.8968(009)
0.8221(18)0.8962(010)

0.7123(178)0.7266(045)0.7269(046)

GCN
GAT
GIN

0.9165(17)0.9086(40)0.9134(109)0.7637(92)0.8182(1)0.8263(8)0.7164(36)0.7202(43)0.7152(41)Table 6. Standard deviation is reported with the last n position.
The best and second-best results (if it overlaps statistically) are
reported, where the top results are also underlined. The accuracy
is reported as in Table 1.

Table 5. The accuracy performance in recovering the missing nodefeatures on the molecular datasets. The best and second best results(if overlaps statistically) are reported, where the top results are also
underlined. The accuracy is reported as in Table 1.

F. Logic expressive power
We model the relationship of nodes’ (or edges’ ) featuresin the neighborhood of a node of a graph. When we use
multiple layers, we can extend the scope of the learned rules
to a larger number of features. While we model extended
logic rules over the features of a graph, we do know if wecover all possible logic rules. This is left for future work.

most of the values lie, and subsequently was converted intoa binary 5-bit vector and was eventually concatenated to therest of the features.
All those datasets have a global graph label with two different classes. For training and metric evaluation, we split theminto a training set (80%) and a test set (20%) respectively.

G. Experimental details

The architecture for our MaxSAT-based message passing
consisted of 2 layers of message aggregation with RAM AX SAT-MP, and B-M AX SAT-MP. A global poolingusing the max function, which should resemble an OR gate.
One linear dense layer followed by a Sigmoid function, forprobabilistic outputs. The baselines (GCN, GAT, and GIN)
use the same architecture. We train our models using Adam
(Kingma and Ba, 2014) optimizer and the binary cross entropy loss (Zhang and Sabuncu, 2018). For the Zinc dataset
we additional compared with the Graph Transformer. We
also evaluate our results using the accuracy metric.

For the addition experiments, we set the number of bits
to 5, thus the total number of variables is n = 15, where
two numbers are used as input and one variable is the output. We set the number of auxiliary variables (Wang et al.,2019) to aux = 12, while the number of clauses m = 40.
The number of applications of the M AX SAT depends onthe experiment N = 1, 2, 3. The same network is appliedrecursively. With the B-M AX SAT-MP, the missing input
variables are set to zero.

E.3.1. R ESULTS OF GRAPH CLASSIFICATION TASKFor the multiplication experiments, we set the number ofbits to 5, thus the total number of variables is n = 15,
where two numbers are used as input and one variable isthe output. We set the number of auxiliary variables (Wanget al., 2019) to aux = 16, while the number of clauses m =88. The number of applications of the M AX SAT depends
on the experiment N = 1, 2, 3. The same network is appliedrecursively. With the B-M AX SAT-MP, the missing input
variables are set to zero, while aux = 100, m = 100, andn = 5 + 5N .

G.1. Addition

G.2. Multiplication

In complex tasks such as graph classification where multiple
aggregations are involved, the MaxSAT-based models arecapable of performing similarly to the baselines. The results
are shown in Table 2. We report the performance of BM AX SAT-MP, although they are not an adequate model for
performing aggregation, especially for datasets such as PROTEINS, where the maximum graph degree is considerablylarger than the other datasets. While for the ZINC dataset,
our MaxSAT model shows lower performance, we see that
our models outperform on average the other baselines on
the MUTAG dataset reaching 92.1% in accuracy, while in
the others the results overlap. This demonstrates that graphclassification can be modeled with SAT solvers where aninternal logical representation of the nodes is capable ofclassifying the graphs.

G.3. Graph Classification
For the Graph Classification experiments the total numberof variables is n, the number of auxiliary variables (Wanget al., 2019) aux, and the number of clauses m, the number
of applications of the M AX SAT depends on the dataset,10Differentiable M AX SAT Message Passing

for Mutagenicity N = 5, aux = 20, m = 20, n = 42, for
PROTEINS N = 26, aux = 12, m = [12, 20], n = 24 andfor MUTAG N = 28, aux = 12, m = [24, 24], n = 27.
The same network is applied recursively as an aggregation
function, while we use 2 layers in the experiments. With
the B-M AX SAT-MP, the missing input variables are set
to zero. GCN has a similar architecture with two layers
and 64 channels, while GAT has 16 channels, and GIN
has 7 channels. An additional network generates the graphclassification from the node features. For training, we use
ADAM (Kingma and Ba, 2014) gradient update and lr =1e−3 , while the training loss function is the binary crossentropy loss (Zhang and Sabuncu, 2018).

H.2. SAT-Net: differentiable MAX-SAT relaxation via
Semi-definitive programming (SDP)The problem in Equation 7 can be relaxed into a SemiDefinitive Programming (SDP) problem (?Wang and Kolter,
2019; Wang et al., 2017)min

V ∈Rk×(n+1)(8)
where for each input variable xi is associated with uniKtary
√ vector vi ∈ R of dimension k, with some k >2n (Pataki, 1998), with k is the size of the embedded space, while n is the number of variables. The
variable v⊤ is used as a reference and is associatedwith true logic value. pThe normalized matrix S =[s⊤ , s1 , . . . , sn ]/ diag(1/ 4|sj |) ∈ Rm×(n+1) encodes
the clauses, while the unitary matrix V ∈ RK×(k+1) encodes the variables.

G.4. Node missing features
As for the Graph Classification experiments, also for theNode missing features experiments the total number of variables is n, the number of auxiliary variables (Wang et al.,2019) aux, the number of clauses m, the number of application of the M AX SAT depends on the dataset, for Mutagenicity N = 5, aux = 20, m = 20, n = 42, for PROTEINS
N = 26, aux = 12, m = [12, 20], n = 24 and for MUTAG
N = 28, aux = 12, m = [24, 24], n = 27. The same network is applied recursively as an aggregation function, while
we use 2 layers in the experiments. With the B-M AX SATMP, the missing input variables are set to zero. GCN has asimilar architecture with two layers and 64 channels, while
GAT has 16 channels, and GIN has 7 channels. For training,
we use ADAM (Kingma and Ba, 2014) gradient update andlr = 1e−3 , while the training loss function is the binary
cross entropy loss. The difference with respect to the graphclassification is that we do not have a graph pooling function, but we predict the node features for the missing nodefeatures directly.

Reading the logic variables Once we solve the relaxed
problem, we need to compute the logic variables from thevectors that minimize Equation 8.
P (xi = 1) =Transforming the logic variables to the relaxed vectors
We generate the vectors from the logical values as vi =− cos(πxi )v⊤ + sin(πxi )P⊤ virand , where Pi = IK − vi viT
is the projection matrix on the vector vi , while virand is arandom unit vector.

H.1. MAX-SAT Problem
In Maximal Satisfiability Problems (MAX-SAT), we areinterested to find the assignment of n binary variables xi ∈{−1, 1}, i = 1, . . . , n concerning m given clauses, ormax nx∈{−1,1}j∈[m]∨i∈[n] 1sji xi >01
arccos (−viT v⊤ )π

The probability measures the angle between the vector associated with the true value and the vector associated with thei variable, indeed viT v⊤ = cos(πxi ). If we want to recover
the discrete value, we compute the sign of the probability,
i.e. xi = sign(P (xi = 1)).

H. Differentiable Satisfiability NetworkX⟨S T S, V T V ⟩ s.t. ∥vi ∥ = 1, ∀i ∈ {⊤, 1, . . . , n},Solving the SDP relaxation The solution of Equation 8
is given as the fix point (Wang et al., 2019)vi = −

(7)

gi
∥gi ∥

(9)

where gi = V S T si − ∥si ∥2 vi = V S T si − vi sTi si .

where sji ∈ {−1, 0, +1} are the clauses of the MAX-SAT
problem. If sji = 0 the variable i is ignored in the j clause,
while xi = +1 is associated with a true value and xi = −1
to a false value, thus sji = −1 negates the variable xi .
MAX-SAT is one of the extensions of the Satisfiability(SAT) problem, where all the clauses need to be true. Relaxing the SAT is useful when we want to find the closest
solution that satisfies most of the clauses.

Auxiliary variables As noted in (Wang et al., 2019), additional variables (aux) are necessary to help the SDP relaxation to converge to the minimal point. These variables
do not have a specific meaning, but we notice that they areakin to reformation using additional variables of the original
problem, this reformulation, while not changing the original
truth table, helps the underlying minimization procedure toconverge.
11Differentiable M AX SAT Message Passing

Algorithm 1 Forward pass algorithm: coordinate descent
Input: VI , where I is the set of input variables
Output: VO , where O is the set of output variables
1: G = V S T
2: while not converged do
3:
for i ∈ O do
4:
gi = V S T si − ∥si ∥2 vi
5:vi = − ∥ggii ∥ {As described in section subsection H.2}
6:
G = G + (vi − viprev )sTi
7:
end for
8: end while(a)Computational complexity of solving SDP relaxation
The complexity of the algorithm depends on the solution of
Equation 8. As shown in (Wang et al., 2019) the solutionof the SDP relaxation can be computed using coordinate
descent and the integration as differentiable is implemented
using two separated, but similar algorithms Alg.1 and Alg.2
for the forward and backward passes.

(b)

Figure 5. Graph (a) and graph (b) are not distinguishable for astandard GNN or 1-WL test.

Since the algorithms require only rank-one updates, theoverall complexity of the two algorithms is O(T kmn), withk the expanded dimension, n the number of variables andm the number of clauses. At the same time, T represents
the number of iterations of the algorithm. During the experiments, T is set to a small number, e.g. T = 40.

I. Motivational Example: 1-WL Isomorphism
Test
In Figure 5, we show two graphs that can not be distinguished according to the 1-WL isomorphism test and, consequently, by a standard GNN. Indeed the neighborhood of
the red and green nodes in both graphs is the same, so theaggregation function will return the same result. If we areable to propagate the multi-hop distance in binary format,
then we can reason on the relative distance of nodes. In a
simplified example, consider the adjacent matrix A of thetwo networks, we then thus use the one-hop and two-hop
adjacent matrices Aa , A2a of the first graph (Equation 10)
and Ab , A2b of the second graph (Equation 11). We can use
the rows of the two-hop adjacent matrix to reason on thenode contribution. For example, the node 1 (as highlighted
in Equation 10) has one entry equal to 2 and three equal to1, while in the second graph (as highlighted in Equation 11),
two entries equal to 2 and one equal to 1. We can thus
use this information to classify the node or the graph. A
standard GNN would not be able to count the entries.

Computational complexity of solving SDP relaxation ongraphs When solving M AX SAT-MP, we need to solvea M AX SAT problem for each node and for all the neighbours. The computational complexity of in this scenario isO(T kmnN M L), where N is the number of nodes, M is
the number of edges, and L number of layers. The batch
version of M AX SAT-MP has the same time complexity,
but it is more stable during training since the M AX SAT
modules are not connected in series but in parallel.

Algorithm 2 Backward pass algorithm: coordinate descent
Input: ∇O L, where O is the set of output variables
Output: ∇I L, where I is the set of input variables
T
1: UO = 0, F = UO SO=0
2: while not converged do
3:
for i ∈ O do
4:
∇gi = F si − ∥si ∥2 ui − ∂L/∂vi
5:ui = −Pi ∇gi /∥gi ∥T
6:
F = F + (ui − uprevi )si
7:
end for
8: end while

0
 0

1
Aa = 
 0

 1
0


0
0
0
1
0
1

1
0
0
1
1
0

0
1
1
0
0
1

1
0
1
0
0
0



0
2
 0
1 


0  2
1
, Aa = 
 1
1 


 1
0 
0
0

0
2
1
1
0
1

1
1
3
0
1
1

1
1
0
3
1
1

1
0
1
1
2
0

(10)
12


0
1 

1 
1 

0 
2

Differentiable M AX SAT Message Passing
0
 1

1
Ab = 
 0

 0
0


1
0
0
1
0
0

1
0
0
1
1
0

0
1
1
0
0
1

0
0
1
0
0
1

0
2
 0
0 


0  2
0
, Ab = 
 2
1 


 1
1 
0
0




0
2
2
0
0
1

0
2
3
0
0
2

2
0
0
3
2
0

1
0
0
2
2
0


0
1 

2 
0 

0 
2

(11)

J. Zinc Experiments
We propose also experiments with the Zinc dataset, where
we model the regression tasks as a classification into 5classes representing different intervals defined by the intervals of probabilities [0.7, 0.3, 0.1, .01] and train on thefirst 12′ 000 samples. We additional compared with a graphtransformer model (Shi et al., 2021). For this dataset, theGIN network provides higher accuracy.
Graph Classification
ZINC
B-M AX SAT-MP

0.8690(0206)

Graph Transformer
GCN
GAT
GIN

0.9012(0023)
0.9025(0035)
0.9028(0055)
0.9114(0036)

Table 7. Standard deviation is reported with the last n position.
The best and second-best results (if it overlaps statistically) are
reported, where the top results are also underlined. The accuracy
is reported as in Table 1.

13