Interpretable Graph Networks Formulate Universal Algebra Conjectures
Authors: Francesco Giannini
Stefano Fioravanti
Oguzhan Keskin
Alisia Maria Lupidi
Lucie Charlotte Magister
Pietro Lio
Pietro Barbiero
Venue: NeurIPS 2023 poster (2023)
Keywords: universal algebra
interpretability
graph neural networks
concept-based models
TL;DR: We propose the first-ever use of AI to investigate Universal Algebra's conjectures using interpretable graph neural networks

Abstract: The rise of Artificial Intelligence (AI) recently empowered researchers to investigate hard mathematical problems which eluded traditional approaches for decades. Yet, the use of AI in Universal Algebra (UA)---one of the fields laying the foundations of modern mathematics---is still completely unexplored. 
This work proposes the first use of AI to investigate UA's conjectures with an equivalent equational and topological characterization. While topological representations would enable the analysis of such properties using graph neural networks, the limited transparency and brittle explainability of these models hinder their straightforward use to empirically validate existing conjectures or to formulate new ones. 
To bridge these gaps, we propose a general algorithm generating AI-ready datasets based on UA's conjectures, and introduce a novel neural layer to build fully interpretable graph networks. The results of our experiments demonstrate that interpretable graph networks: (i) enhance interpretability without sacrificing task accuracy, (ii) strongly generalize when predicting universal algebra's properties, (iii) generate simple explanations that empirically validate existing conjectures, and (iv) identify subgraphs suggesting the formulation of novel conjectures.

Interpretable Graph Networks Formulate Universal Algebra Conjectures
Francesco Giannini' CINI, Italy
Stefano Fioravanti Università di Siena, Italy, JKU Linz, Austria Italy stefano. fioravantiinniii.........
francesco, giannini@unisi.
Oguzhan Keskin
Alisia Maria Lupidi
Lucie Charlotte Magister
University of Cambridge, UK ok3138cam. ac. uk
University of Cambridge, UK
University of Cambridge, UK
am12018cam.. ac. uk
1cm670cam ac uk
Pictro Lió University of Cambridge, UK p1219@cam. ac. uk
Pietro Barbiero"
Università della Svizzera Italiana, CH University Cambridge, UK barbiplusi.ch
Abstract
The rise of Artificial Intelligence (AI) recently empowered researchers to investi- gate hard mathematical problems which eluded traditional approaches for decades. Yet, the use of AI in Universal Algebra (UA)-one of the fields laying the founda- tions modern mathematics-is is still completely unexplored. This work proposes the first use of AI to investigate UA's conjectures with an equivalent equational and topological characterization. While topological representations would enable the analysis of such properties using graph neural networks, the limited trans- parency and brittle explainability these models hinder their straightforward use empirically validate existing conjectures or to formulate new ones. To bridge these gaps, we propose a general algorithm generating Al-ready datasets based on UA's conjectures, and introduce novel neural layer build fully interpretable graph networks. The results of our experiments demonstrate that interpretable graph networks: (i) enhance interpretability without sacrificing task accuracy, (ii) strongly generalize when predicting universal algebra's properties, (iii) generate simple explanations that empirically validate existing conjectures, and (iv) identify subgraphs suggesting the formulation of novel conjectures.
GENERATE DATA SET
FRAME CONJECTURE
1+1=
Introduction
Universal Algebra (UA, (6) is one the foundational fields of modern Mathematics with possible deep impact in all mathematical disciplines, but the complexity of studying abstract algebraic structures hinders scientific progress and discourages many academics. Recently, the emergence of powerful AI technologies empowered researchers inves- tigate intricate mathematical problems which eluded tradi- tional approaches for decades, leading the solution of open problems (e.g., (24)) and discovery of new conjectures (e.g., 7)). Yet, universal algebra currently remains un- investigated realm for AI, primarily for two reasons (i) first
The mocila
not modular
iGNN Cutt modutar
EXTRACT EXPLANATIONS
TRAIN AI MODEL
Figure I: Interpretable graph networks support universal algebra research.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

UA deals with infinite objects or even classes of abstract objects, which pose unique challenges for conventional AI techniques, (ii) secondly the field commonly relies on deterministic algorithms. utilized to construct finite models or serve as deterministic theorem provers, such as "mace4" and "prover9" [ In this sense, we hope that our paper could represent guidance to further explore the study of UA's problems with AI, e.g. by integrating existing systems, like these mentioned theorem provers, with our methodology. which may suggest novel conjectures, in a unique scheme.
Universal algebra studies algebraic structures from an abstract perspective, Interestingly, several UA conjectures equivalently characterize algebraic properties using equations or graphs (T6). In theory, studying UA properties as graphs would enable the use of powerful AI techniques, such as Graph Neural Networks (GNN, (39), which excel on currently limit scientific progress. First, the absence of benchmark datasets suitable for machine learning prevents widespread application of AI to UA. Second, GNNs' opaque reasoning obstructs human understanding of their decision process (38). Compounding the issue of GNNs' limited transparency. GNN explainability methods mostly rely on brittle and untrustworthy local/post-hor
data. However, two factors
methods (14 27 28 38 45) or pre-defined subgraphs for explanations (2) 42). which are often
unknown in UA
Contributions. In this work, we investigate universal algebra's conjectures through AI (Figure D Our work includes three significant contributions. First, we propose novel algorithm that generates a dataset suitable for training AI models based on an UA equational conjecture. Second, we generate and release the first-ever universal algebra's dataset compatible with AI, which contains more than 29, 000 lattices and the labels of 5 key properties i.e., modularity, distributivity, semi-distributiving join eemi-distributivityy and meet cini-isttriuttivity. And third, we introduce a novel neural layer that makes GNNs fully interpretable, according to Rudin's 's (38) notion of interpretability. The results of our experiments demonstrate that interpretable GNNs (iGNNs): (i) enhance GNN interpretability without sacrificing task accuracy, (ii) strongly generalize when trained to predict universal algebra's 's properties, (iii) generate simple concept-based explanations that empirically validate existing conjectures, and (iv) identify subgraphs which could be relevant for the formulation of novel conjectures. As consequence, our findings demonstrate the potentiality of Al methods for investigating UA problems.
2 Background
Universal Algebra is branch of mathematics studying general and abstract algebraic structures. Algebraic structures are typically represented as ordered pairs A = (A, consisting of non non-empty set A and collection of operations F defined on the set. UA aims to identify algebraic properties (often in equational form) shared by various mathematical systems. In particular, varieties are classes of algebraic structures sharing common set of identities, which enable the study of algebraic systems based on their common properties. Prominent instances of varieties that have been extensively studied across various academic fields encompass Groups, Rings, Boolean Algebras, Fields, and many others. A particularly relevant variety of algebras are Lattices (details in Appendix A.3). which are often studied for their connection with logical structures.
Definition 2.1. A lattice L is an algebraic structure composed by non-empty set L. and two binary operations V and A, satisfying the commutativity, associativity, idempotency, and absorption axioms.
Equivalently a lattice can be characterized as partially ordered set in which every pair of elements has a supremum (V) and an infinum (A)
M3
N
(cf. Appendix A.3). Lattices also have formal representations as graphs via Hasse diagrams (L, E)) (e.g.. Figure 2). where each node x E L is lattice element, and directed edges (x. y) E E C L x L represent the ordering relation, such that if (a. y) E then x Sr. y in the ordering of the lattice. A sublattice L' of a lattice L is a lattice such that L,' C L and L' preserves the original order (the "essential structure") of T,, i.e. for all x. E T.' then x. Su. y and only if J: Sr. y. The foundational work by Birkhoff (5). Dedekind (9) and Jónsson (18) played significant role in discovering that some significant varieties of lattices can be characterized through the omission of one or more lattices. Specifically, variety V of lattices is said to omit lattice L if the latter cannot be identified as a sublattice of any lattice in V. A parallel line of work in UA
Figure 2: Hasse diagrams.
hattpa://wwe cs. unm. laa..edud''ma /ttb//nccume//pover//
The orientation of Hasse diagrams is always to be meant bottom-up, hence will omit arrows for simplicity.
2

---

characterizes lattices in terms of equational ("term; 2 term2") ") and quasi-equational ("if equation holds then equation, holds") properties, such as distributivity and modularity.
Definition 2.2. Let L be lattice. L is modular if it satisfies x S y + (2) distributive if it satisfies x V (y A =) R (x v) A (x V z).
We notice that each distributive lattice is also modular (see Appendix A.3) Figure represents M3, (modular with 3 atoms) and N₂ (non-modular with 5 atoms), the smallest instances of lattices which exhibit failures of distributivity and modularity, respectively. For example, N; neither modular nor distributive, considering the substitution x a, y C, = b. The same substitution shows that M3 is not distributive. The classes of distributive and modular lattices show classical examples of varieties that can equívalently be characterized using equations and lattice omissions, as illustrated by the following theorems.
Theorem 2.3 (Dedekind )). A lattice variety modular if and only V omits N
Theorem 2.4 (Birkhoff ( A lattice variety V is distributive if and only if omits N₂ and M3.
Starting from these classic results, the investigation of lattice omissions and the structural charac- terizations of classes of lattices has evolved into a rich and extensively studied field (T6), but it was never approached with Al methodologies before.
3 Methods
The problem of characterizing lattice varieties through lattice omission is very challenging as requires the analysis of large (potentially infinite) lattices 9 To address this task, we propose the first Al-assisted framework supporting mathematicians in finding empirical evidences to validate existing conjectures and to suggest novel theorems. To this end, propose general algorithm (Section 3 allowing researchers in universal algebra to define a property of interest and generate dataset suitable to train Al models. We then introduce interpretable graph networks (Section (.2) which can suggest candidate lattices whose omission is responsible for the satisfaction of the given algebraic property.
3.1 A Tool to Generate Datasets of Lattice Varieties
We propose a general methodology to investi- gate any algebraic property whose validity can be verified on a finite lattice. In this work, we focus on properties that can be characterized via equations and quasi-cquations. To train AI mod- els. we propose a general dataset generator for lattice varieties. Intuitively, the generator takes as input the number of nodes n in the lattices and a function to check whether lattice satisfies a given property. We generate 2nxn matrices of size n. containing all binary functions definable on (1..... n)²,, and filter only binary matrices representing partial orders. Then, we verify that the partial ordered set L is lattice, by checking that any pair of nodes always has unique infimum and supremum. This directly verifies that A and VL satisfy Definition [. Finally, we not, and append it and the property label
Algorithm 1: Generate dataset of lattice varieties.
Input: hasPropemetss)))
cardinality
Dolonet =
AllFanes e- (onchiiFancr())) for L AllFwscs do if infortialOneer(( then istanice then for s. 3. S n do
binary functionss as v. x i mutrices It L). = 1 meaning i S check of S. rofl. antirmm and trans. dheeek yf lutiie
bbb + sup.st far St. s St. f} Vulbi +- inf us 18 St. wand St. #)
hasPhoppetyy Ar, Vy.)
#f A properies
Dunanet append[[ liue))
else Datavet appendi( (L, False')
check whether the lattice satisfies the target property to our dataset. We remark that checking the validity of a single ternary equation on a medium-size lattice is not computationally prohibitive (i.e., it "only" requires checking n² identities), but the number of existing lattices increases exponentially as n increases. For instance, it is known that there at least 2,000,000 non-isomoiphic lattices with n 10 elements (4). Therefore, we only sample a fixed number of lattices per cardinality starting from a certain node cardinality. While this may seem strong bias, we notice that known and relevant lattice omissions often rely on lattices with few nodes (5) 9). To empirically verify that this is not a significant limitation, in our experiments we deliberately investigate the generalization capacity of GNNs when trained on small-size lattices and tested on larger ones. This way we can use GNNs to predict the satisfiability of equational properties
Thhe dataset generator and the datasets are available htthttss///gthhhh com./Erraggaamminn/AAA4.
3

---

CONCERT
Ci
Node-level concepts. An interpretable concept space is the first step towards interpretabilliyy unit of MESSAGE PASSING
M3
INTERPRETABLE ABGREGATION
f WWW.OAAANTNNOOOO..OO
y = NON DISTRIBUTIVE
INTERPRETABLE CLASSIFIER
HARD
GUMBEL SOFTMMX
N5
CONCEPT
"2hnodo Heig Soomood
Figure 3: An interpretable graph layer (1) aggregates node features with message passing, (ii) generates node-level concept space with hard Gumbel-Softtm activation θ, (iii) generates graph-level concept space with an interpretable permutation invariant pooling function E on node-level concepts, and (iv) predicts a task label with interpretable classifier using graph-level concepts.
on large graph structures without explicitly checking them. Using Algorithm [ we generated the first large-scale Al-compatible datasets of lattices containing more than 29, 000 graphs and the labels of 5 key properties of lattice (quasi-Jvarieties i.e., modularity, distributivity, semi-distributivity, join semi-distributivity, and meet semi-distributivity, whose definitions can be found in Appendix A
Scalability and Complexity. The scalability of the dataset generation process is related to two main points: (i) dealing with the exponential growth of the number of lattices, (ii) how to feasibly generate a lattice of a finite amount of elements. (i) Since the number of lattices definable on a set L = (O....n 1} increases exponentially with n, it is not feasible to realize a dataset containing all the lattices of n elements. However, this is also unnecessary for the scope of this work, which aims automatically identifying (small) topological patterns responsible for the failure of certain algebraic properties. In addition. the majority of the graphs generated are isomorphic, thus not particularly informative for our task. Because of this, we only generate a portion of all the lattices up to certain value M > 0, and then take a fixed number of samples n, up to N (we take M = 8, n, = 20, N 50 in the paper). (ii) The construction of lattice with n elements is briefly sketched in Algorithm 1
We refer to Appendix B for the technical details on the design of the used functions.
3.2 Interpretable Graph Networks (iGNNs)
In this section, we design an interpretable graph network (iGNN, Figure 3) that satisfies the notion of "interpretability"" introduced by Rudin (38). According to this definition, a machine learning (ML) system interpretable if and only if (1) its inputs are semantically meaningful, and (2) its model inference is simple for humans to understand (c.g., sparse and/or symbolic). This definition covers ML systems that take tabular datasets or sets of concepts as inputs, and (piece-wise) linear models such as logistic regression or decision trees. To achieve this goal in GNNs, we introduce an interpretable graph layer that learns semantically meaningful concepts and uses them as inputs for a simple linear classification layer. We then show how this layer can be included into existing architectures or into hierarchical iGNNs, which consist of a sequence of interpretable graph layers. We notice that in devising our approach, we preferred to rely on linear classifiers as they are fully differentiable, hence allowing us to realize a fully interpretable and differentiable model from the input to the classification head. However,in practice any interpretable and differentiable classifier could be used in place of this linear layer.
3.2.1 Interpretable Graph Layer
The interpretable graph layer (Figure 3) serves three main functions: message passing, concept generation, and task predictions. The first step of the interpretable graph layer involves a standard message passing operation (Eq. right), which aggregates information from node neighbors. This operation enables to share and process relational information across nodes and it represents the basis of any GNN layer.
Following Ghorbani et al. (10), relevant concept is "high-level

---

information" shared by input samples and thus identifiable with clustering techniques. Message passing algorithms do cluster node embeddings based on the structure of node neighborhoods, as observed by Magister et al. (28). However, the real-valued large embedding representations h, E TRy, E N generated by message passing can be challenging for humans interpret. To address this, we use a hard Gumbel-Softmax activation θ IR9 + {0, 13,, following Azzolin et al. (
C; = (h:)
h = # X (xx x3))
JEN,
where & a learnable function ignoring or assuming constant input features and & is a learnable function aggregating information from a node neighborhood N₂, and @ is permutation invariant aggregation function (such as sum or mean). During the forward pass, the Gumbel-Softmas activation @ produces one-hot encoded representation of each node embedding. Since nodes sharing the same neighborhood have similar embeddings h, due to message passing, they will also have the same one-hot vector due to the Gumbel-Softmal and vice versa we can then interpret nodes having the same one-hot concept c, as nodes having similar embeddings h, and thus sharing a similar neighborhood. More formally, we can assign semantic meaning to reference concept ? E {0, 1 by visualizing concept prototypes corresponding to the inverse images of a node concept vector. In practice, we can consider a subset of the input lattices I' corresponding to the node's (p-hop) neighborhood covered by message passing:
(() = [ (in))
(2)
where D is the set of all training lattices, and ((tp)) is the graph corresponding to the p-hop neighbor- hood (p E (I,....1I.] (Z.1) of the node i E I., as suggested by Ghorbani et al. (10); Magister et al. (28). This way, by visualizing concept prototypes as subgraph neighborhoods, the meaning of the concept representation becomes easily interpretable to humans (Figure 3), aiding in the understanding of the reasoning process of the network.
Example 3.1 (Interpreting node-level concepts). Consider the problem of classifying distributive
lattices with simplified dataset including N₂ & and M3 x only, and where each node has a constant feature x; = 1, As these two lattices only have nodes with 2 or 3 neighbours, one layer of message passing will then generate only two types of node embeddings e.g., h1 = [0.2. 100-00.. 0.4, 0.3]
for nodes with 2-nodes neighborhood (e.g., S and 1 = 0.6, -0.1] for nodes with 3-nodes neighborhood (e.g., 4). As a consequence, the Gumbel-Softmax will only generate two possible concept vectors e.g., C₁r = [0, 0, 1] and C₁1 = [1, 0, 0j. Hence, for instance the concept belongs to CΙI, while belongs to C/II-
Graph-level concept embeddings. To generate a graph-level concept space in the interpretable graph layer, we can utilize the node-level concept space produced by the Gunbel-Softmax. Normally, graph-level embeddings are generated by applying a permutation invariant aggregation function on node embeddings. However, in iGNNs we restrict the options to (piece-wise) linear permutation invariant functions in order to follow our interpretability requirements dictated by Rudin (38). This restriction still includes common options such as max sum pooling. Max pooling can easily be interpreted by taking the component-wist max over the one-hot hot encoded concept vectors c, After max pooling, the graph-level concept vector has value of 1 at the k-th index if and only if at least one node activates the k-th concept i.e., 3i E L, Cak = 1. Similarly, we can interpret the output of a sum pooling: a graph-level concept vector takes value E N the k-th index after sum pooling if and only there are exactly v nodes activating the k-th concept i.e., Rio.... ... E L,, C.k- 1.
Example 3.2 (Interpreting graph-level concepts). Following Example 3.1 let us use sum pooling to generate graph-level concepts. For an N₂ graph, we have 5 nodes with exactly the same 2-node neighborhood. Therefore, sum pooling generates a graph-level embedding [0, 0, 5]. which certifies
that we have nodes of the same type e.g., For an M3 graph, the top and bottom nodes have a
3-node neighborhood e.g., while the middle nodes have a 2-node neighborhood e.g.. 4. This means that sum pooling generates graph-level embedding [2, 0, 3), certifying that we have 2 nodes of type & and 3 nodes of type +
5

---

Interpretable classifier. To prioritize the identification of relevant concepts, we use a classifier to predict the task labels using the concept representations. A black-box classifier like a multi-layer perceptron (36) would not be ideal as it could compromise the interpretabilityy of our model, so instead we use an interpretable linear classifier such as a single-layer network (20). This allows for completely interpretable and differentiable model from the input to the classification head, as the input representations of the classifier are interpretable concepts and the classifier is a simple linear model which is intrinsically interpretable discussed by Rudin (38). In fact, the weights of the perceptron can be used to identify which concepts are most relevant for the classification task. Hence, the resulting model can be used not only for classification, but also to interpret and understand the problem at hand.
3.2.2 Interpretable architectures
The interpretable graph layer can be used to instantiate different types of iGNNs. One approach is to plug this layer as the last message passing layer of a standard GNN architecture:
ÿ f BKEK
(o(p)k)
h
(K-1)
J (h) (K-1) hn ((K-1)))
(3)
JEN:
h = 600) hh (1-1)
(h!
11 nb. )) 1 1= I=.,,,, K
(4)
JEN;
where I' is an interpretable classifier (e-g. single-layer network), ER is an interpretable piece-wise linear and crmmutation-ivaaiiii function (such as max or sum), θ is Gumbel-Softmax hard activation function, and hς = X, In this way, we can interpret the first part of the network as a feature extractor generating well-clustered latent representations from which concepts can be extracted. This approach is useful when we only care about the most complex neighbortooddsconcepts Another approach is to generate hierarchical transparent architecture where each GNN layer is interpretable:
g0= = :0=s(EE))) ((BEK (o(n))))
I= K
(5)
In this case, we can interpret every single layer of our model with concepts of increasing complexity. The concepts extracted from the first layer represent subgraphs corresponding to the 1-hop neighbor- hood of node, those extracted at the second layer will correspond to 2-hop neighhorhoods, and so on. These hierarchical iGNNs can be useful get insights into concepts with different granularities. By analyzing the concepts extracted at each layer, we gain a better understanding of the GNN inference and of the importance of different (sub)graph structures for the classification task.
3.2.3 Training
For the classification layer, the choice of the activation and loss functions for iGNNs depends on the nature of the task at hand and does not affect their interpretability. For classification tasks, we use standard activation functions such softmax or sigmoid, along with standard loss functions like cross-entropy. For hierarchical iGNNs (HiGNNs), we apply the same loss function at each layer of the concept hierarchy, as their layered architecture enables intermediate supervisions. This ensures that each layer is doing its best to extract the most relevant concepts to solve the task. Internal losses can also be weighted differently to prioritize the formation of optimal concepts of specific size, allowing the HiGNN to learn in a progressive and efficient way.
4 Experimental Analysis
4.1 Research questions
In this section we analyze the following research questions:
Generalization Can GNNs generalize when trained to predict universal algebra's proper- ties? Can interpretable GNNs generalize as well?
Interpretability- Do interpretable GNNs concepts empirically validate universal algebra's conjectures? How can concept-based based explanations suggest novel conjectures?

---

4.2 Setup
Baselines. For our comparative study, we evaluate the performance of iGNNs and their hierarchical version against equivalent GNN models (i.e., having the same hyperparameters such as number layers, training epochs, and learning rate). For vanilla GNNs we resort to common practice replacing the Gumbel-Softnal with a standard leaky ReL.U activation. We exclude from our main baselines prototype or concept-basee GNNs pre-defining graph structures for explanations, as for most datasets these structures are unknown. Appendix [[oveers implementation details. We show more extensive results including local and post-hoe explanations in Appendix G
Evaluation. We employ three quantitative metrics assess model's generalization and inter- pretability. We use the Area Under the Receiver Operating Characteristic (AUC ROC) curve to assess task generalization. We evaluate generalization under two different conditions: with independently and identically distributed train/test splits, and out-of-distribution by training on graphs up to eight nodes, while testing on graphs with more than eight nodes ("strong generalization" (41)). We further assess generalization under binary and multilabel settings (classifying 5 properties of a lattice at the same time). To evaluate interpretability, fidelity (37). Completenes assesses the quality of the concept space on a global scale using an interpretable model to map concepts to tasks, while fidelity measures the difference in predictions obtained with an interpretable surrogate model and the original model. Finally, we evaluate the mean- ingfulness of our concept-basee based explanations by visualizing and comparing the generated concepts with ground truth lattices like e.g. M3 and N;, whose omission is known to be significant for modular and distributive properties. All metrics in our evaluation, across all experiments, are computed on test sets using 5 random seeds, and reported using the mean and 95% confidence interval.
standard metrics such as completeness (44) and
5
Key Findings
5.1 Generalization
Our experimental evaluation reveals that interpretable GNNs are able to strike a balance between completeness and fidelity, two crucial metrics that are used to assess pnteraliizaioonnneepreabblllll trade-offs (37). We observe that the multilabel classification scenario, which requires models to learn a more varied and diverse set of concepts, is the most challenging and results in the lowest completeness scores on average. We also notice that the more challenging cuttof-distribution scenario results in the lowest completeness and fidelity scores across all datasets. More importantly, our findings indicate that iGNNs achieve optimal fidelity scores, as their classification layer consists of a simple linear function of the learnt concepts which is intrinsically interpretable (38). On the contrary, interpretable surrogate models of black- box GNNs exhibit, as expected, lower fidelity scores, confirming analogous observations in the explainable AI literature 3733) In practice, this discrepancy between the original black-box predictions and the predictions obtained with an interpretable surrogate model questions the actual usefulness of black-boxes when interpretable alternatives achieve similar results in solving the problem at hand, as extensively discussed by Rudin (38). Overall, these results demonstrate how concept spaces are highly informative to solve universal algebra's 's tasks and how the interpretable graph layer may improve GNNs' interpretability without sacrificing task accuracy. We refer the reader to Appendix F for detailed discussion on quantitative analysis of concept space obtained by iGNNs under different generalization settings with comparisons to their black-box counterparts.
iGNNs improve interpretability without sacrificing task accuracy (Figure 4.
GNNs strongly generalize on universal algebra's 's tasks (Figure(5.. Our experimental findings demonstrate the strong generalization capabilities of GNNs across the universal algebra tasks we designed. Indeed, we stress GNNs test generalization abilities by training the models on graphs of size up to (with n ranging from 5 to 8), and evaluating their performance much larger graphs of size up to 50. We designed this challenging experiment in order to understand the limits and robustness of interpretable GNNs when facing significant data distribution shift from training to test data. Remarkably, iGNNs exhibit robust generalization abilities (similar to their black-box counterparts) when trained on graphs up size 8 and tested on larger graphs. This evidence confirms the hypothesis that interpretable models can deliver reliable and interpretable predictions, as suggested by Rudin
We assess the recall of the completeness the datasets are very unbalanced towards the negative label.
7

---

multilabel
Distributive
Modular
MeetSemiDiitributie
Sem Distibbbii
100
FIDELTYYS
COMPI FTENESS
COMPI ETENESS %
COMMI ETENESS %
CÖMPLETENESS %
COMPI ETENESS
COMPLETENESS %
GSAT
Black Box GCExplainer
HIGNN
IGNN
GSAT (strong)
Black.Box
GCExplainer (strong)
HiGNN (strong)
IGNN (strong)
Figure 4: Accuracy-interpaee interpretability trade-off in terms of concept completeness (accuracy) and model fidelity (interpretability). iGNNs attain optimal fidelity as model inference is inherently interpretable, outmatching equivalent black-box GNNs. All models attain similar results in terms of completeness.
(38). However, we observe that black-box GNNs slightly outperform iGNNs when trained on even smaller lattices. We hypothesize that this is due to the more constrained architecture of iGNNs, which imposes tighter bounds on their expressiveness when compared to standard black-box GNNs. Notably, training with graphs of size up to 5 or significantly diminishes
Distributive
Modular
Multiabe
GNNs generalization in
Text AUCROC
the tasks we designed.
28
70
We hypothesize that this
68
due to the scarcity
of non-distributive and non-modular lattices during training. but it may also suggest that some patterns of size 7 and 8 might be quite relevant to generalize to larger graphs. Unfortunately, running generalization experiments with S 4 was not possible since all such lattices trivially omitted N₂ and M3. is worth mentioning that GNNs performed well even in the challenging multilabel case, where they had to learn wider and more diverse set of concepts and tasks. In all experiments. we observe a plateau of the AUC ROC scores for n = 8, thus suggesting that training including graphs of this size might be sufficient learn the relevant patterns allowing the generalization to larger lattice varieties. For detailed numerical results across all tasks, we refer the reader Table in Appendix D Overall, these results emphasize the potential of GNNs in addressing complex problems in universal algebra, providing an effective tool to handle lattices that are difficult to analyze manually with pen and paper.
Maximum Number of Nodes Training
Black
IGNN
HGGN
Figure 5: Strong generalization performance with respect to the maxi- mum number of nodes used in training.
5.2 Interpretability
explanations empirically validate universal algebra's conjec- 6). We present empirical evidence support the validity of theo- rems 2.3 and 2.4 by examining the concepts generated for modular and distribu- leverage the interpretable structure of iGNNs.
Concept-based
tures (Figure
tive tasks. For this investigation
Similarly to Ribeiro et al. (37).
visualize in Figure 6 the weights of our trained linear clas- sifeer representing the relevance of each concept. We remark that the visualization is limited to the (top-5) most negative weights, as we are interested in those con- cepts that negatively affect the prediction of property. the same plot, we also show the prototype of each concept rep- resented by the 2-hop neighbor-
Concept ID [istributivee i5
Concept [Modllar]
Omizzion Relesance
Omizsion Relevance
-02
Figure Ranking of relevant clusters of lattices (x-axis) accord- ing to the interpretable GNN linear classifier weights (y-axis, the lower the more relevant the cluster). N₂ is always the most impor- tant sub-lattice to omit for modularity, while both Mg and N₂ relevant for distributivity, thus validating theorems and

---

hood of node activating the concept, following similar procedure as Ghorbani et al. (IO); Magister al. (28); Azzolin al. (2). Using this visualization, we investigate the presence of certain concepts when classifying modular and distributive lattices. For the modularity task, our results show that the lattice N; appears among non- non-modular concepts, but is never found in modular lattices, while the lattice M3 appears among both modular and non-modular concepts, which is consistent with Theorem 2.3 In the case of distributivity, we observe that both M3 and N;, are present among non-distributive concepts, and are never found in distributive lattices, which is also in line with Theorem 2.4 These findings provide a large-scale empirical evidence for the validity of theorems 2.3 and 2.4 and further demonstrate the effectiveness of graph neural networks in learning and analyzing lattice properties. Overall, these results highlight how interpretable GNNs can not only learn the properties of universal algebra but also identify structures that are unique to one type of lattice (e.g., non non-modular) and absent from another (e.g., modular), thus providing human-interpretablee explanations for what the models learn.
Contrastive explanations highlight topological differences between properties of lattice rieties (Figure 7). We leverage interpretable GNNs to analyze the key topological differences of classical lattice properties such join and meet cumi-distribuitivity characterized by relevant quasi-equations (cf. Appendix [A.5). To this end, we visualize specific concept prototypes corre- sponding to lattices that not meet semi-distributive against lattices that are meet semi-distributive. We observe N₂ but not M3 among the concepts of meet semi -ini-distributive lattices, while we observe both N₂ and M3 only in concepts that are not meet disiidiitributive. This observa- tion suggests that N₂ is not key lattice for meet semi-distributive lattices, unlike distributive lattices. Furthermore, we find that the lattice pattern V is relevant for non meet semidistributivity, while its dual A is relevant for non join semidistributivity, thus empirically confirming the hypotheses of Jónsson and Rival (19). These findings are significant because they demonstrate how analyzing concepts in interpretable GNNs can provide universal algebraists with a powerful and automatic tool to formulate new conjectures based identifying simple lattices that play a role in specific properties. By leveraging the power of interpretable GNNs, we may uncover previously unknown connections between different properties and identify new patterns and structures that could lead to the development of new conjectures and theorems in universal algebra, providing exciting opportunities for future research in universal algebra.
Distributive Lattice Varieties
Semi- Distributie Varieties
Figure 7: Contrastive explanations showing lattice varieties with a a pair of discording labels to highlight the key difference between join and meet semi cemi-distributivity.
Discussion
Relations with Graph Neural Network explainability. Graph Neural Networks (GNNs, process relational data generating node representations by combining the information of a node with that of its neighbors, thanks to general learning paradigm known as message passing (1.. A number of post-hoc explainability techniques have been proposed to explain the reasoning of GNNs. Inspired by vision approaches (40 37 I0), early explainability techniques focused on feature importance (35), or global explanations using conceptual subgraphs by clustering the activation space (28 46 29 22). However, all these techniques either rely on pre-defined subgraphs for explanations (which are often unknown in UA) or provide post-hoc explanations which may be brittle and unfaithful as extensively demonstrated by Rudin (38). On the contrary, our experiments show that iGNNs generate interpretable predictions according to Rudin (38) notion of interpretability via linear classifiers applied on sparse suman-understandable concept representations.
while subsequent works aimed to extract local explanations (45 27 42)
Limitations. The approach proposed in this paper focuses on universal algebra conjectures charac- terized both algebraically and topologically. Our methodology limited to finite lattices, which may not capture all relevant information about infinite algebraic structures. However, the insights gained from finite-lattice explanations can still provide valuable information regarding given problem (albeit with potentially limited generalization). Moreover, our approach is restricted to topological

---

properties on graphs, while non-structural properties may require the adoption of other kinds of (interpretable) models.
Broader impact and perspectives. AI techniques are becoming increasingly popular for solv- ing previously intractable mathematical problems and proposing new conjectures (23 26
However, the use of modern Al methods in universal algebra was a novel and unexplored field until the development of the approach presented in this paper. To this end, our method uses inter- pretable graph networks to suggest graph structures that characterize relevant algebraic properties of lattices. With our approach, we empirically validated Dedekind (9) and Birkhoff (5) theorems on distributive and modular lattices, by recovering relevant lattices. This approach can be readily extended -bennd equational properties determined by the omission of sublattice in a variety (45) to any structural property of lattices, including the characterization of congruence lattices of algebraic varieties 21 31 43), Our methodology can also be applied (beyond universal algebra) to investi- gate (almost) any mathematical property that can be topologically characterized graph, such as the classes of graphs/diagraphs with fixed set of polymorphisms (25 32)
Conclusion. This paper presents the first-ever Al-assisted approach to investigate equational and topological conjectures in the field of universal algebra. To this end, we present novel algorithm to generate datasets suitable for AI models to study equational properties of lattice varieties. While topo- logical representations would enable the use graph neural networks, the limited transparency and brittle explainability of these models hinder their use in validating existing conjectures proposing new ones. For this reason, we introduce a novel neural layer to build fully interpretable graph net- works to analyze the generated datasets. The results of our experiments demonstrate that interpretable graph networks: enhance interpretability without sacrificing task accuracy, strongly generalize when predicting universal algebra's 's properties, generate simple explanations that empirically validate existing conjectures, and identify subgraphs suggesting the formulation of novel conjectures. These promising results demonstrate the potential of methodology, opening the doors of universal algebra to Al with far-reaching impact across all mathematical disciplines.
Acknowledgments and Disclosure of Funding
This paper was supported by TAILOR and by HumanE--Al-eet projects funded by EU Horizon 2020 research and innovation programme under GA No 952215 and No 952026, respectively. This paper has been also supported by the Austrian Science Fund FWF project P33878 "Equations in Universal Algebra" and the European Union's Horizon 2020 research and innovation programme under grant agreement No 848077. This project has also received funding from the European Union's Horizon-MSCA-202) research and innovation program under grant agreement No 101073307.
References
[1] Paolo Agliand, Stefano Bartali, and Stefano Fioravanti. On Freese's technique. International Journal of Algebra and Computation, 2023. doi: http://...0rr1111111112/11111111
URL https: arxii..ivvv...i.//a.//aaaaa .org/ abs/ 2tt.:2222...11 11452
[2] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. Global ex- plainability of gnns via logic combination of learned concepts. arXiv preprint arXiv:2210.07147, 2022.
[3] Libor Barto, Marcin Kozik, and Todd Niven. The csp dichotomy holds for digraphs with no sources and sinks (a positive answer conjecture of bang-jensen and hell). SIAM Journal on Computing, 38(5):1782-1802. 2009.
[4] Joel Berman and Pawel Idziak. Counting finite algebras in the post varieties. International Journal of Algebra and Computation, 10(03):323-33) 337, 2000.
[5] Garrett Birkhoff. On the structure of abstract algebras. In Mathematical proceedings of the Cambridge philosophical society, volume 31, pages 433-454. Cambridge University Press, 1935.
[6] Stanley Burris and H. P. Sankappanavar. A Course in Universal Algebra. Springer, 1981.
10

---

[7] Alex Davies, Petar Veličković, Lars Buesing, Sam Blackwell, Daniel Zheng, Nenad Tomašev, Richard Tanbur, Peter Battaglia, Charles Blundell, András Juhász, Mare Lackenby, Geordie Williamson, Demis Hassabis, and Pushmeet Kohli. Advancing mathematics by guiding human intuition with Al. Nature, 60007888):70-74, December 2021. doi: 10.1038/ s41586-021 021--008-0 URL https:://oi.orgg:
[8] Alan Day. characterization of modularity for congruence lattices of algebras*. Canadian Mathematical Bulletin,
1969. doi: 10.4153/CMB- 199-00666999--1166
[9] Richard Dedekind. Über die drei Moduln erzeugte Dualgruppe. Math. Ann., 1900.
[10] Amirata Ghorbani, James Wexler, James Zou, and Been Kim. Towards automatic concept- based explanations. Advances in Neural Information Processing Systems, 32, 2019.
[11] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning. pages 2663-127. PMLR, 2017.
[12] Yang- He. Machine-leaming mathematical structures. International Journal of Data Science in the Mathematical Sciences, pages 1-25, 2022.
[13] Jobst Heitzig and Jürgen Reinhold. Counting finite lattices. Algebra universalis, 48(1):43-53, 2002.
[14] Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions on Knowledge and Data Engineering. 2022.
[15] Martin Hyland and John Power. The category theoretic understanding of universal alge- bra: Lawvere theories and monads. Electronic Notes in Theoretical Computer Science, 172:437-458, 2007. ISSN 1571-0661. doi: https://dii.org/// 101 URL https::///// //ww: sci enciiienedt....... com/ http:///iaiancccttttt.ee//////// Computation, Meaning, and Logic: Articles dedicated to Gordon Plotkin.
[16] Peter Jipsen and Henry Rose. Varieties of Lattices. Springer Berlin, 1992.
[17] Bjarni Jonnson. Algebras whose congruence lattices are distributive. MATHEMATICA SCANDINAVICA, 21:110-121, Dec. 1967. doi: (0.7146/math.scannaa-0000 URL https
www.msccand dk/ cb/aarticceevvie/100550
[18] Bjamn Jónsson. On the representation of lattices. Mathematica Scandinavica, 1953.
[19] Bjarni Jónsson and Ivan Rival. Lattice varieties covering the smallest non-modular lattice variety. Pucific J. Math., Volume 82, 1978.
[20] Samandarov Erkaboy Karimboyevich and Abdurakhmonov Olim Nematullayevich. Single layer artificial neural network: Perceptron. European Multidisciplinary Journal of Modern Science, 5:230-238, Apr. 2022. URL https:///mjmmeee academi cijeemiccoornaa ii -oo /i////iddxxx////// phpp emjms/
article/view/ 255
[21] Keith Kearnes and Emil Kiss. The shape of congruence lattices. Memoirs of the American Math. Soc., 2013.
[22] Oguzhan Keskin, Alisia Maria Lupidi, Stefano Fioravanti, Lucie Charlotte Magister, Pietro Barbiero, Pietro Lio, and Francesco Giannini. Bridging equational properties and patterns on graphs: an ai-based approach. In Topological, Algebraic and Geometric Learning Workshops 2023, pages 156-168. PMLR, 2023.
[23] Guillaume Lample and François Charton. Deep learning for symbolic mathematics. In Interna- tional Conference Learning Representations.
[24] Guillaume Lample and François Charton. Deep learning for symbolic mathematics. arXiv preprint 1rXiv:1112.01442 2019.

---

[25] Barto Libor and Kozik Marcin. Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem. Logical Methods in Computer Science, Volume 8, Issue 1, 2012.
[26] Donald W Loveland. Automated theorem proving: A logical basis, Elsevier, 2016.
[27]
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33: 19319900019311, 2020.
(28) Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Lid. Gcexplainer: Human-in-the-loop concept-based explanations for graph neural networks. arXiv preprint arXiv:2107.11889, 2021.
(29] Lucie Charlotte Magister, Pietro Barbiero, Dmitry Kazhdan, Federico Siciliano, Gabriele Ciravegna, Fabrizio Silvestri, Mateja Jamnik, and Pietro Lio. Encoding concepts in graph neural networks. arXiv preprint arXiv:2207. 13586, 2022.
[30] Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pages 15524-15543. PMLR, 2022.
[31] J. B. Nation. Varieties whose congruences satisfy certain lattice identities. Algebra Universalis, 1974.
[32] Miroslav Olšák. The local loop lemma. Algebra universalis, 2020.
[33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv: 1912:0992.00.733. 2019.
[34] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2832 2011.
[35] Phillip Pope, Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoff- mann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 10772-10781, 2019.
[36] Marius-Constantie Popescu, Valentina Balas, Liliana Perescu-Popeseee and Nikos Mastorakis. Multilayer perceptron and neural networks. WSEAS Transactions on Circuits and Systems, 8, 07 2009.
[37] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. " why should trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1 1135-11444 1144, 2016.
[38] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206-215. 2019.
[39] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
[40] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprini arXiv:/3/2.600) 2013.
[41] Petar Veličković, Rex Ying, Matilde Padovano, Raia Hadsell, and Charles Blundell. Neural execution of graph algorithms. In International Conference on Learning Representations, 2019.
[42] Minh Vu and My T Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks. Advances in neural information processing systems, 33:1 12255-2225, 2020.
[43] Philip M Whitman. Free lattices. Annals of Mathematics, pages 325-330, 1941.
12

---

[44] Chih-Kuan Yeh, Been Kim, Sercan Arik, Chun-Liang Li, Tomas Pfister, and Pradeep Ravikumar. On completeness-awee aware concept-bacd based explanations in deep neural networks. Advances in 2020.
Neural Information Processing Systems,
[45] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks, 2019.
[46] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self-explaining graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9127-9135, 2022.
13

---

A Algebra definitions
A.1 Formal defintions for Universal Algebra
Universal algebra is the field of mathematics that studies algebraic structures, which are defined as a set A along with its collection of operations. In this section, recall some basic definitions and theorems from Burris and Sankappanavar (6); Day algebra and lattice theory.
( Jonnson (17). about elements of universal
Definition A.I. N-ary function For non-empty set A and non-negative integer we define A {0} and, for n > 0, A" the set of n-tuples elements from A. An n-ary operation on is any function f from A to A; n is the arity of f. An operation f on A is called n-ary operation if its arity is n.
Definition A.2. Algebraic Structure algebra is pair (A, F) where A a non-empty set called universe and F is a set of finitary operations on A.
Apart from the operations on A, an algebra is further defined by axioms, that in the particular case of universal algebras in the form of identities. Definition A.3. A lattice operations V and A satisfying the following axioms and their duals obtained exchanging V and A: (commutativity)
an algebraic structure composed by a non non-empty set and two binary
x V Nyygy yVr
V VV)
(associativityy
VV 2 R
(idempotency)
Ay)
(absorption)
Theorem A.4 (66). partially ordered set L is a lattice if and only if for every a, E both supremum and intiruum of {a, b) exist (in L) with V being the supremum and A the infimum. Definition A.5. Let L be a lattice. Then modular (distributive, disti-diittibuutive, A-semi- distributive) if it satisfies the following:
S y + x V (y A R ( V y A 2) 2 | A (z)2)
(modularity)
(distributivity)
V y 2 s V x ( RVVY
(V-semi-distributtiitt))
(y R Furthermore a lattice semi-distributive both V-semi-distributiee and A-semi-distributive
Ay R x A
(A-semiidisstributtittt))
N
Mg
e
Figure 8: N₂. a non modular non-distributive and Mg. a modular non non-distributive lattice.
Theorem A.6. If lattice L is distributive, then L also modular.
Proof. By assuming S y, we have x V y. Hence, from the distributive property we get: x ( ()
y
14

---

Definition A.7. Congruence Lattice
An equivalence relation on set A is binary relation that satisfies three properties: reflexivity, symmetry, and transitivity.
Reflexivity: For every element a in A, a related to itself, denoted as a a;
Symmetry: For any elements a and b A, if a then a;
Transitivity: For any elements a, b, and c in A, if and b c, then a c.c.
In other words, an equivalence relation partitions the set A into subsets, called equivalence classes, such that elements within the same class are equivalent to each other under the relation ~.
Let A be an algebra. A congruence A of A is a equivalent relation on A, that is compatible with the operations of A. Formally, for every n-ary operation f of A: if (a1, 61), (22,b)).... (on, b,)) O, then (f(a), .2..... an), fbb,, be.... ..).).))))))....... ) 0. For every algebra A on the set A. the identity relation on A, and A A are trivial congruences. An algebra with no other congruences is called simple. Let Con (A) be the set of congruences on the algebra A. Since congruences are closed under intersection, we can define a meet operation: A : Con A) X Con - Con by simply taking the intersection of the congruences E1 A E2 = E1 n Eg. Congruences are not closed under union, however we can define the following closure operator of binary relation E, with respect to a fixed algebra A, such that its image is congruence: (F)) = N(F E Con ) F. C F). Note that the closure of a binary relation is a congruence and thus depends on the operations in A, not just on the base set. Now define V Con(A) x Con(A) > Con( A) as E1 V Eg {E) U E2) A- For every algebra A, (Con(A), A, V) with the two operations defined above forms a lattice, called the congruence lattice of A.
type F is defined as a set of operation symbols along with their respective arities. Each operation symbol represents a specific operation that can be performed on the elements of the algebraic system. To refer to the specific operation performed by a given symbol f on an algebra of type F, we denote it as fa. This notation allows us differentiate and access the particular operation carried out by I within the context of A.
Definition A.S. Subalgebra Let and B be two algebras of the same type. Then B is a subalgebra of A if B C A and every fundamental operation of B is the restriction of the corresponding operation of A, i.e., for each function symbol f. f f restricted B.
Definition A.9. Homomorphic image Suppose A and B two algebras of the same type F, i.e. for each operation of A, there exists a corresponding operation B with the same arity, and vice versa. mapping + B is called homomorphiism from A B if
a (a.......... an) f (aa1..... ..a,))
for each n-ary in F and each sequence a....., an from A. If. in addition, the mapping is onto then B is said to be a homomorphic image of A.
Definition A.10. Direct product Let A and A₂ be two algebras of the same type F. We define the direct product A x A, to be the algebra whose universe is the set A₁ x A2, and such that for and a, E A1, a' E A2, < is
jAiXAs ((a), of), ..., (an a²,)) = (fAi(a), (a),.... an), fA (a .d.....,,da ,,,)))
The collection of algebraic structures defined by equational laws are called varieties. (5
Definition A.11. Variety A nonempty class K of algebras of type F is called variety if it is closed
under subalgebras, homomorphic images, and direct products.
B Algorithm I details
In the following, we report some technical details on how the dataset generator sketched in Algorithm is actually implemented. First, notice that a brute-force approach is infeasible for large lattices, as
given a set of n nodes, the number of binary relations on this set is 2n To cope with this issue, first
15

---

for each candidate lattice L we consider a squared x n matrix Sz representing its order that has 1 value in a position (i, if and only if the element i is less or equal to the element j in L (i.e. Sr. j) and O otherwise. Then we constraint each matrix to have I in the diagonal (reflexivity), O in each (i,5) with j < i, where "<" denotes denotes the order on N (this choice both prunes the majority of isomorphic lattices and yields anti-symmetricity) All the other pairs of elements (f, can either be such that S j or incomparable (i.e. i ÉL j and j Σr, 1), and we consider all these possible cases. Finally, we apply matrix multiplications to get transitive closure of the order relation (convergence guaranteed at most n - steps) and hence St represents a partial order. To assure that the order represents lattice, have check that each pair of elements (i. admits (unique!) infimum and supremum. This step and checking lattice equational properties are implemented tensorially to leverage GPU quicker computations, hence being particularly advantageous when the dimensions of the lattices is such that the computational cost of Algorithm | surpasses the overhead of GPU communication. Finally, we notice that even avoiding the isomorphic lattices, for = 18 there around 165Bn non-isomorphic different lattices (13). This is why we sampled a fixed number of lattices as n increases, e.g. 20 samples for cardinality after certain threshold, instead of keeping generating all the possible lattices for each value of n, which is not particularly relevant for our task. Whereas it allows us to study the strong generalization capability of GNNs trained on e-g. up to n 8 nodes and then evaluated on lattices of higher dimensions, e.g. n 50 nodes (see Figure 5 Notice that checking e.g. the distributivity for 50 is deterministic but requires checking 50 identities.
Rumning time. The running time of the algorithm increases polynomially in the size of the given lattice (it is ((n²) for checking each of the equational properties, e.g. distributivity/moduuarii and Onn²) to check if candidate binary relation is actually a lattice). In a machine with a single quad-core CPU, it requires 20 minutes to generate all the lattices up to N = 8 and sampling n., 20 lattices for n E [9, 50] (the dataset we used in the paper).
C Baselines' details
In practice, we train all models using eight message passing layers and different embedding sizes ranging from 16 to 64. We train all models for 200 epochs with a learning rate of 0.001. For interpretable models, we set the Humbel-Softmar temperature to the default value of and the activation behavior to "hard," which generates one-hot encoded embeddings in the forward pass, but computes the gradients using the soft scores. For the hierarchical model, we set the internal loss weight to 0.1 (to score it roughly 10% less w.r.t. the main loss). Overall, our selection of baselines aims at embracing a wide set of training setups and architectures to assess the effectiveness and versatility of GNNs for analyzing lattice properties in universal algebra. To demonstrate the robustness of our approach, we implemented different types of message passing layers, including graph convolution and GIN.
D Generalization results details
Here we report the raw numbers for the weak and strong generalization results reported as a figure in the main paper. The results obtained by setting maximum lattice size to 8 in training and using lattices of size 9 or larger during evaluation. All models provide near perfect performance for binary classification and perform slightly worse but still very competitively for multi-label classification. This demonstrates the strong generalization capability of GNNs for universal algebra tasks, and may be an ideal starting point finding new relevant patterns in UA properties.
In Table D we also include a quantitative comparison with GSAT (30). and observe that GSAT and iGNNs obtain comparable results in terms of task generalization and concept completeness (cf. Table when trained on the proposed UA's tasks.
E
Concept completeness and purity
Our experimental results (Tables 2 demonstrate that interpretable GNNs produce concepts with high completeness and low purity, which are standard quantitative metrics used to evaluate the quality of concept-based approaches. Completeness score is the accuracy of classifier, such as decision
16

---

Table 1: Generalization performance of different graph neural models in solving universal algebra's tasks. Values represents the mean and the standard error of the mean of the area under the receiver operating curve (AUCROC, %)
weak generalization
strong generalization
GCExplainer
GSAT
iGNN
HGGNN
GCExplainer
GSAT
IGNN
HIGNN
Distributive
593.80 1 0.04
96.73 0.11
96.56 1.12
59.45
0.36
99.51 1 1.20
97.26
17.20:10 0,30
99.311 0.05
99.32
0.04
Join Semi Distributive
99.00 1: 0.02
0..33:10.06
18.31
98.
0.04
08.77 1 0.15
07.76
0.07
07.50
1 0.14
97.18
0.14
Meet Semi Distribetive
0.04
08.36
06.19-00.06
98.25
0.03
07.18
96.80
Modular
0.02
99:18+0.11
90.35-
99.32 0:22
96.35
0.31
00:21
90.11
Semal Distrihutive
90.86 + 0.03
00002
-0.5000006
99.19
0.04
98.14
97.28 + 0.48
96.89 0.47
Multi Label
99.80 +: 0.02
0
96.32
96.98 = 0.30
98.02
+ 0.43
94.45 à: 0.35
95.29 à: 0.55
95.27 + 0.32
tree, which takes concepts as inputs and predicts a label. Purity score is the number of graph edits, such as node/edge additionneliminationn necessary to match two graphs in a cluster. A concept space is said to be pure if the purity score is zero.
We employ decision tree as the classifier, but compute recall instead of accuracy calculate com- pleteness score since the datasets are heavily unbalanced towards the negative labels. We compute purity scores for each cluster and report the average of those scores the final purity score. Our approach achieves at least 73% and up to 87% recall, which shows that our interpretable models consistently avoid false negatives in the abundance of negative labels. We obtain around 3-4 purity scores, which suggests that our interpretable models extract relatively pure concept spaces in the presence of large lattices.
Furthermore, the hicrarchical structure of interpretable GNNs enables us to evaluate the quality of intermediate concepts layer by layer. This hierarchy provides insights into why we may need more layers, and it can be used as a valuable tool to find the optimal setup and tune the size of the architecture. Additionally, it can also be used to compare the quality of concepts at different layers of the network. To that end, we compare the purity scores of the concept spaces obtained by the second layer and the final layer of HiGNN. As shown in Table deeper layers may produce higher quality concepts for distributivity and join semi-distrbuutiiity whereas earlier layers may result in more reliable concepts for the remaining properties. Overall, these results quantitatively assess and validate the high quality of the concepts learned by the interpretable GNNs, highlighting the effectiveness of this approach for learning and analyzing complex algebraic structures.
Table 2: Concept purity scores of graph neural models in solving universal algebra's 's tasks. Lower is better.
WEAK PURITY
STRONG PURITY
GCExplainer
IGNN
HIGNN
GCExplainer
IGNN
HIGNN
Distributive
3.30 + 0.36
3.64 + 0.30
3.09 - 0.56
3.20 + 0.38
4.00 + 0.77
4.15+ 0.67
Join Semi Distributive
2.38 +: 0.37
3:96
4: 0.51
3.74 = 0.62
3.45 à: 0.34
3.98 # 0.68
4.29 2: 0.61
Meet Semi Disteibutive
3:50
0.62
3.30 0.30
3.36 0.32
4.25
4.97
Modular Semi Distributive
3.10 0.35
3.50
0.46
1.41 0.56
3.14::.2
3.19::1.01
1.25 0.69
2.84 à: 0.51
3.70
4: 0.54
4.11 a 0.46
3.70 4: 0.55
3.92 4: 0.28
4.08 à: 0.85
Table 3: Concept purity scores of different layers of HiGNN. Lower is better.
WEAK PURITY
STRONG PURITY
2nd Layer
Last Layer
2nd Layer
Last Layer
Distributive
3.26 + 0.43
3.09 : 0.56
4.66 + 0.98
4.15 + 0.67
Join Semi Distributive
4.25 + 0.69
3.74 0.62
4.30 0.39
4.29 + 0.61
Meet Semi Distributive
3.64 +.64
+.299
4.41 + 0.27
4.97 + 0.44
Modular Semi Distributive
3.89 + 0.63
4.44 0.56
4.19 + 0.56
4.25
+ 0.69
3.55 1 0.58
4.11 + 0.46
3.16 1 0.59
4.08 1 0.85
Table 4: Concept completeness scores of graph neural models in solving universal algebra's tasks.
Higher is better.
WEAK COMPLETENESS
STRONG COMPLLEVENESS
GCEspluiner
IGNN
GSAT
HRGNN
GCExplainer
IGNN
GSAT
HIGNN
Distribative
96.53 0.72
98.54 0.13
68.36
5.22
93.42
0.09
95.61 0.76
99.45 D.16
66.30 -1.1
523.46
0.06
Bemi-Distibuuive
96.64
98.45 0.25
63.72=
4.82
0.11
93.98
97.50
90.57
97.51
Meet Semi- Distributvv
96.00
0.11
98.17 0.111
78.78
1.45
98.30
0.03
95.18 a 0.41
97.20
2: 0.14
85.46
2.68
96.36
0.13
Modular
96.28
1..6
99.08 1 0.03
61.62
- 1.24
99.80
0.12
91.
1.08
99.10 1: 0.20
66.83
1663_22 2.60
99.33
0.07
Suttiittibativee
97.47 0.04
08.62 0.08
83.58
= 77
98.57
0.00
96.31
0.02
97.07
1: 0.81
-2233 65.68
97.00
0.75
Multilahel
95.79
3.65
87.16 0.31
96
17

---

Gruzh Coreagt 0
Grast Corcapt
Conrept [a..0a355.000 (o0d
Conceppe |.000035660001 1199
Goot Caroaee
Goohh Goroapt
Corcapt kbst [00000888000110]]
Concept bbct (p00000660000110
Concege
lustt [80000а8800011100
label p.000000000101100
Gruah Corcapt
Great Corcapt
Concapt lubt [000000001001101]
Concept last [0000033c1110000]
Groph Corcopt
Grash Corcapt
Cancept bbat [000005504111000]
Cancept labak [e000033C10001.0
Concept
Grash
Concept (0000898611000))
Concept (10.08006.1...
Geaph Conregt 12
Graph Connept 13
Concept bist (00000@611110000)
Concegt bbet [00000311000000)
Concapt 14
Grah Concept
Concept ibbet (0000900144110000
Concept labet [000000100110000]
Graph Coccept
Grsph Conoept Concept [000000111111000]]
Concapt [000000101000000]
Figure 9: Examples of graph concepts.
F Concept visualization
Figure 9 visualizes 18 randomly sampled graph concepts (out of the 7896 graph concepts represented by different graph encodings) following the visualization procedure introduced by (28). The figure shows for each concept an example of four (randomly sampled) graphs having the same concept label in the 7-th layer of the hierarchical iGNN trained on the multilabel dataset. Graphs belonging to the same concept show a coherency in their structure and similar patterns. These patterns represent the knowledge extracted and discovered the hierarchical iGNN.
18

---

G Explanations of post-hoc explainers
We compared our Explainable Hierarchical GNN against standard explainer (namely GNNExplainer (45) to further support our results. GNNExplainer is the first general, model-agnostic approach for providing interpretable explanations for predictions of any GNN-based model on any graph-bau machine learning task and it is widely used in the scientific community as one of the staple explainers GNN's XAI. In this particular setting, GNNExplainer was configured as follows: model-wise explanation on multiclass-node level classification task, with HiGNN the model of choice, and GNNExplainer as the desired algorithm, trained for 200 epochs. The explainer takes as imput single graph in the dataset and outputs and explanation for its classification. GNNExplainer will enforce classification based on the presence or omission of M3 and/or N₂ and is possible to visualize the subgraph that lead to this classification by leveraging the visual i _gaapph function. By doing this, we retrieve the following visualizations:
0
0
1
1
2
7
2
5
3
3
6
4
4
Figure 10: Visualizations obtained with GNNExplainer on weak distributive generalization (on the left) and strong multiclass generalization (on the right)
On the right, the substructure identified as N5 by CNNExplainer which lead to the classification of said graph as non modular and non distributive. On the right, in green M3. Our hierarchical model arrive to the same conclusions as the standard explainer but can also be augmented with a standard explainer.
H Code, Licences, Resources
Libraries For experiments, implemented all baselines and methods in Python 3.7 and relied upon open-source libraries such as PyTorch 1.11 (33) (BSD license) and Scikit-learn (34) (BSD license). To produce the plots seen in this paper, made of Matplotlib 3.5 (BSD license). We will release all of the code required to recreate our experiments in an MIT-licensed public repository.
Resources All of experiments 5218 CPUs (2.30GHz), 64GB of RAM, and 2 Quadro RTX 8000 Nvidia GPUs. We estimate that approximately 100-GPU hours were required to complete all of our experiments.
private machine with Intel(R) Xeon(R) Gold
19


Reviews:
[{"review_id": "eLNGCJ6Bly", "reviewer": "Reviewer_AeQ9", "summary": "A general methodology is introduced that allows a researcher interested in problems regarding lattices, in the mathematical field of Universal Algebra, to investigate any algebraic property whose validity can be verified on a finite lattice.\nThe paper indicates how a dataset can automatically be generated . Then a new GNN variant is devised, adapted from previous works (e.g. [1]), that is interpretable. This model is compared to the performance of a vanilla, black-box GNN, with all the other model parameters kept identical. \n\n[1] Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. Global ex-\nplainability of gnns via logic combination of learned concepts", "questions": "- Is there a reason you chose to use linear classifiers instead of decision trees, as the interpretable model of choice?\n\n- consider line 150 (\"To address this, we use a hard Gumbel-Softmax activation\") vs. line 219 (\"The choice of the activation and loss functions to train iGNNs depends on the nature of the task at hand and does not affect their interpretability\"). Does that mean that you use different activation functions at different parts of the GNN? ", "limitations": "The problem that is solved is quite narrow, though the authors go out of their way to make sure that this is not emphasized. \n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper discusses how a field that has hitherto not seen a large number of AI applications be treated. Two new GNN variants are proposed, called iGNN and HiGNN.\nI also like the fact that the well-known lattices N_5 and M_3 where used throughout the text as examples of how the learning algorithms works (Example 3.1 and 3.2).", "weaknesses": "__I. Various hyperbolizing adjectives are used throughout the text, that do not provide information:__\n\n- line 18: \"Universal Algebra (UA, (6)) is one of the foundational fields of modern mathematics\" The importance of Universal Algebra is somewhat overstated. While it indeed is a foundational field, it is usually not part of a typical university curriculum.\n\n- line 43 onwards: \"First, we propose a novel algorithm that generates a dataset suitable for training AI models based on an UA equational conjecture. Second, we generate and release the first-ever universal algebra’s dataset compatible with AI [...] Our findings\ndemonstrate the potential of our methodology and open the doors of universal algebra to AI.\"\nThe relevance of the contribution is hyperbolized and overstated, for the following reasons:\n1) Indeed, this may be the first application of AI to universal algebra (although experience has shown that in machine learning often new results are introduced, that under a different name were already known previously -- --, so unless an extremely thorough literature review would have been made, I would not feel confident making this assertion). \n2) It is known that AI is very well suitable to a particular type of mathematics, where the involved objects are discrete (see [1]), so it is not surprising that this approach works well in this setting too.\n3) I am not convinced paper does not \"open doors of universal algebra to AI\" (see also the claim repeated on line 408), since the method is not tied to the field of Universal Algebra, but rather to the objects of study. Universal Algebra has strong connections to model theory, for example (see [2], chapter 5, which is a reference that is cited in the paper), and exploring these using machine-learning is definitely not covered under the current approach.\n\nline 90: \"advanced AI methods\" (what exactly makes an AI method \"advanced\" is debatable)\n\nline 396: \"However, as universal algebra is a foundational branch of modern mathematics, any contribution to this field can already have significant implications in various mathematical disciplines.\"\n\nI feel like these hyped-up claims obscure the actual strong points of the paper: A well-executed experiment with a suitable neural model (GNN) (and other strong points outlined in the Strength section). \n\n__II. Other observations__\n\n- while not a weakness, but a curiosity: it is noteworthy that the lattice examples from Figure 2, page 2, are identical to those from the Wikipedia article on lattices, see Pic 10 and Pic 10 [3]. In Wikipedia, it is mentioned that these are the smallest lattices of their type, but the paper does not mention this (tangential) fact.\n\n- in the appendix, a number of definitions from Universal Algebra are taken from well-knowns, e.g., Definition A.3 corresponds ad literam to Definition 9.3 from [2]. I feel it could be emphasized more strongly that many of the definitions are directly copied from existing sources, rather than merely stating \" More formally (6; 8; 16):\", where their reference 6 is my reference [2] below.\nMore precisely, at the beginning of the appendix, it is stated: \"An n-ary operation on A is a function that takes n elements of A and returns a single element from the set. More formally (6; 8; 16):\" which implies that only the first ensuing definition of arity is taken from references rather than all ensuing definitions.\nIt would be helpful, to either explicitly state that all theorems/definitions are taken from books (and ideally, like in Theorem A.5, show from where the theorem comes).\n\n- on table from the appendix is missing (below line 582): \"Note: ADD TABLE WITH CONCEPT PURITY\". This should be fixed, if the paper is accepted, but doesn't make a difference for acceptance/rejection decision.\n\n[1] A.Z. Wagner, Constructions in combinatorics via neural networks, https://arxiv.org/abs/2104.14516\n[2] Burris S., Sankappanavar H.P., A Course in Universal Algebra, Springer Millenium Edition\n[3] https://en.wikipedia.org/wiki/Lattice_(order)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our appreciation to the Reviewer for demonstrating a comprehensive grasp of the fundamental aspects of our paper. We comment on the points of the review in the following text.\n\n*“I. Various hyperbolizing adjectives are used throughout the text, that do not provide information: /line 18/line 43/The problem that is solved is quite narrow”*\n\nWe thank the Reviewer for the meaningful suggestions. We agree with the reviewer and in the revised version of the paper, we will rephrase the mentioned statements in a more moderate fashion, while contextualizing the novelties introduced by our paper with respect to the specific contributions within the field of UA.\n\nWe acknowledge that Universal Algebra (UA) and abstract algebra in general are usually not covered in standard university programs as they constitute topics requiring a strong comprehension of deep mathematical concepts in a broad view. However, we notice that this can be similarly observed for other fields in Mathematics, like Category Theory and axiomatic Set Theory, which are  widely recognized as foundational branches of Mathematics.\n\nWe also would like to note that, to the best of our knowledge, UA problems remain largely unexplored by AI methodologies for two main reasons. Firstly, UA primarily deals with infinite objects or even classes of abstract objects, which pose unique challenges for conventional AI techniques. Secondly, the field commonly relies on deterministic algorithms, utilized to construct finite models or serve as deterministic theorem provers, such as \"mace4\" and \"prover9\" [1]. In this sense, we hope that our paper could represent a guidance to further explore the study of UA’s problems with AI.\n\n*“while not a weakness, but a curiosity: (...)”*  \nWe thank the Reviewer for the remark. We will clarify this point in the revised paper when referring to Figure 2 as follows: “Figure 2 represents M3 and N5 that are the smallest instances of lattices which exhibit failures of distributivity and modularity, respectively”.  \nNotably, it is not surprising that the depiction of these lattices in our paper aligns with their representation found in Wikipedia since it is the usual way to represent them, following the lattice order.\n\n*“in the appendix, a number of definitions from Universal Algebra (...)”*  \nIn the revised version, we will make explicit mention which definitions are directly drawn from [11]. Nevertheless, we deemed it necessary to include them in our paper to ensure self-containedness, particularly for an AI audience that may be unfamiliar with the domain of UA.\n\n*“on table from the appendix is missing (...)”*  \nThe main pdf contains a preliminary version of the appendix, while the finalized version of the appendix can be found in the supplementary material of the submission.\n\n*“Is there a reason you chose to use linear classifiers instead of decision trees (...)” ?*  \nDecision trees represent a suitable choice as interpretable models and we have also used them through our investigation, e.g. in the evaluation of the completeness score of non-interpretable models in Figure 4. In devising our approach, we preferred to rely on linear classifiers as they are fully differentiable, hence allowing us to realize a fully interpretable and differentiable model from the input to the classification head. However, in practice any interpretable and differentiable classifier could be used in place of this linear layer.\n\n*“consider line 150 (\"To address this, we use a hard Gumbel-Softmax activation\") vs. line 219 (\"The choice of the activation and loss functions to train iGNNs depends on the nature of the task at hand and does not affect their interpretability\"). Does that mean that you use different activation functions at different parts of the GNN?”*  \nLine 150 refers to the activation function generating concept encodings (always a Gumbel softmax in our approach, invariant w.r.t. the task at hand), while Line 219 refers to the activation and loss function of the classification layer (usually softmax/sigmoid + cross entropy/MSE, depending on the task at hand).\n"}, {"review_id": "b7cNvn5sS3", "reviewer": "Reviewer_LfMh", "summary": "This paper aims to use AI as a tool to help solve problems in mathematics. In particular, this paper focuses on universal algebra, which studies algebraic structures and can be considered as learning properties of graphs. \n\nThe contributions are two folds:\n- This work proposes a method for generating a benchmark for universal algebra, and releases a dataset of 29000 lattices (partial orderings, which can be represented as graphs) of different sizes and 5 properties.\n  - Generation: filter binary matrices (each lattice on a set of size n can be represented by a nxn matrix) that admits a partial ordering.\n- This work proposes an interpretable neural layer (iGNN) that can be used to solve tasks in the benchmark dataset.\n\nEmpirical results show that the model is able to generalize across lattice sizes while being interpretable.", "questions": "- Sec 3.2.1, node level features: the \"vice versa\" part is unclear: we only have the converse direction if we assume that the mapping has some reverse Lipschitz condition (e.g. if the neighborhoods are distinct, then the corresponding $h_i$'s are different), which is not guaranteed in the current setup?\n- top of page 5: where do the values of $h_{II}$ come from? Are the values made up as examples?\n- Sec 3.2.3: what are examples of intermediate loss functions? How to obtain the signals/labels for the loss?\n- Sec 5.2: what does a \"concept\" mean? How are the weights computed? Is there a set of \"concepts\" (small graphs?) to search over?\n\nWriting related:\n- A notational question: why $\\approx$ rather than =?\n- The background can be defined more clearly in the main text (or please consider adding pointers to the appendix):\n    - explain that $\\vee, \\wedge$ correspond respectively to join (least upper bound) and meet (greatest lower bound).\n    - explain $M_3$ and $N_5$ are named for \"Modular\" and \"Nonmodular\".\n    - line 77: is there a typo?\n    - to help understand the properties, it might be helpful to point out that not modular implies not distributive.\n- Sec 3.1: are $n,L$ the same thing?\n- Fig 6: where's $M_3$?", "limitations": "The paper discusses limitations that the proposed methods are constrained to finite-size graph and only work with structural properties.\n\nThere is no direct societal impact.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The paper provides the required background and is self-contained.\n- The proposed benchmark dataset is the first dataset for universal algebra which is valuable to the field.\n- The proposed interpretable layer achieves good empirical performance.\n  - Experiments in Section 5.1 show that on UA tasks, the proposed iGNN scores higher in terms of interpretability metrics, while preserving the performance of black-box GNNs.\n  - The interpretability results in Section 5.2 are interesting: the appearance of substructures corresponding to N5 and M3 is consistent with the theoretical understanding.", "weaknesses": "- The dataset generation process is relatively straightforward (i.e. filtering to get valid lattices, and sampling since it's computationally infeasible to enumerate all configurations).\n  - Update post-rebuttal: this is no longer a concern: the author responses have discussed more details and considerations on scalability. \n- The proposed neural layer is interpretable due to constraining the function classes, which may limit the representational power of the network.\n  - For the pooling layer, the paper chooses max or sum pooling, which reflects the existence or number of 1s in the pooled inputs; this seems to provide only a limited level of interpretability and I wonder if other aspects can be used.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback on the paper. In the following paragraphs we address the raised comments, in the hope of shedding light on the significance of our research. .\n\n*“The dataset generation process is relatively straightforward.”*  \nWe disagree on considering a straightforward data generation process as a weakness. This dataset is the first benchmark for studying UA lattices with AI, thus constituting a scientific contribution by definition. It follows a detailed explanation of why we think the data generation process is also not as straightforward as it may seem at first sight.\nFirst, notice that a brute-force approach is infeasible for large lattices, as given a set of n nodes, the number of binary relations on this set is $2^{n^2}$.  To cope with this issue, first for each candidate lattice **L** we consider a squared $n\\times n$ matrix representing its order $\\leq_L$ having a 1 in each position $(i,j)$ if and only if the element $i$ is less or equal to the element $j$ in **L** (i.e. $i\\leq_L j$) and 0 otherwise. Then we constraint each matrix to have 1 in the diagonal (reflexivity), 0 in each $(i,j)$ with $j<i$ , where $<$ denotes the order on $\\mathbb{N}$ (this both prunes the majority of isomorphic lattices and yields anti-symmetricity). All the other pairs of elements $(i,j)$ can either be s.t.  $i\\leq_L j$ or incomparable (i.e. $i\\nleq_L j$ and $j\\nleq_L i$), and we consider all these possible cases. Finally, we apply matrix multiplications to get a transitive closure of the order relation (converge guaranteed in at most n-2 steps) and  $\\leq_L$ represents a partial order. \nTo assure the order represents a lattice, we have to check that each pair of elements $(i,j)$ admits a (unique!) inf and sup. This step and checking lattice equational properties are implemented tensorially to leverage GPU quicker computations, hence being particularly advantageous when the dimensions of the lattices is s.t. the computational cost of Alg 1 surpasses the overhead of GPU communication. \nLastly, even removing all isomorphic lattices, for $n=18$ there are around 165Bn non-isomorphic different lattices [2]. This is why we sampled a fixed number of lattices as $n$ increases, e.g. 20 samples for cardinality after a certain threshold, instead of keeping generating all the possible lattices for each value of $n$, which is not particularly relevant for our task. Whereas it allows us to study the strong generalization capability of GNNs trained on e.g. up to $n=8$ nodes and then evaluated on lattices of higher dimensions, e.g. $n=50$ nodes (see Fig. 5 of the main paper). Notice that checking e.g. distributivity for $n=50$ is deterministic but requires verifying $50^3$ identities checking.  \nFor completeness we will include these considerations in the Appendix.\n\n*“The proposed neural layer is interpretable due to constraining the function classes, which may limit the representational power of the network.”*  \nInterpretable models constrain the representation power by definition (see Rudin [3], or CBMs [4] vs DNNs, or Decision Trees vs XGBoost). The problem therefore is how much these constraints affect the classification accuracy. Our results empirically demonstrate that these constraints do not deteriorate the task accuracy (see Figs 4-5).\n\n*“Sec 3.2.1, node level features: the \"vice versa\" part is unclear (...)”*  \nWe notice that for the UA’s properties investigated, only the pure graph structure is relevant while (input) node features do not play any role. In this context, relational models may not consider node features at all (e.g., KGEs) or generate constant input features to allow message passing. Hence, we get similar embeddings $h_i\\approx h_j$ after message passing if and only if i and j have the same neighbors. We clarified it as mentioned in the list of changes.\n\n*“top of page 5: are h_II values made up as examples?”*  \nYes. \n\n*“Sec 3.2.3: what are examples of intermediate loss functions?\"*  \nThe intermediate supervisions on HiGNNs mentioned in Sec 3.2.3 are applied on the task predictions $\\hat{y}^{(l)}$ and obtained via Eq. 5 at each layer for $l=1,...,K$ (where $\\hat{y}^{(K)} = \\hat{y}$). The task labels (i.e., $y$) and the loss function (e.g., cross-entropy in our experiments) are always the same and can be used to supervise any layer.\n\n*“Sec 5.2: what does a \"concept\" mean?”  \nThe notion of “concept” in general follows Ghorbani et al. [5] (lines 146-7), while in the context of GNNs, we follow Magister et al. [6], where a concept is represented by a subgraph.\n\n*“A notational question: why \\approx rather than =?”*  \n“$\\approx$” distinguishes from “$=$” as it denotes equations on variables instead of elements.\n\n*“background can be defined more clearly in the main text”*  \nWe revised the background section addressing all the suggestions.\n\n*“Sec 3.1: are n, L the same thing?”*  \nL is the set of elements of a lattice, while $n=|L|$. We replaced the typo $L=10$ to $n=10$ in Sec 3.1.\n\n*“Fig 6: where's M_3?”*  \nIn Fig 6, M3 is a sublattice of lattices number 2,4,5 (left) and of 2,3,5 (right). We will add the prefix “(sub-)” in front of “lattice” in the caption of Fig 6. "}, {"review_id": "CKTYm3jxiE", "reviewer": "Reviewer_3uvy", "summary": "In this paper, the authors explored the use of AI in mathematical problems Universal Algebra. They propose an algorithm for generating datasets of lattice varieties and derive an interpretable graph neural networks for predicting universal algebra’s properties. Experiment results show the effectiveness of the proposed method. Overall, the motivation is clear and the paper is well written.", "questions": "What is the running time for generating the datasets used in the experiments? How is the time increased with n?\n\nCan the authors include recent general graph explanation methods for comparison?\n", "limitations": "It is recommended that the authors can provide results in a table to be more readable.\n", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The problem the paper is investigating is of interest and importance. The authors propose a relatively complete pipeline consisting of both datasets generation and a graph neural network for interpretable prediction.\n\nThe paper is well written and the problem definition is clear. In addition, the authors provide examples to emphasize how the Gumbel softmax works which makes it more readable. \n\nExperiment results seem reasonable. It is good that the authors verify their method on datasets with different settings and use qualitative metrics for interprebility.\n", "weaknesses": "One concern is from the dataset generation. As the authors mentioned that the number of existing lattices increases exponentially as n increases, I am curious whether the algorithm is really scalable. In addition, it seems that the algorithm is unable to control label distribution generated.\n\nUsing Gumbel softmax instead of regular activation functions seems novel. However, one concern is whether the semantic concept acquired via the one-hot embedding is really meaningful. Because two embeddings may not necessarily have correlation when they have the maximum value in the same indice. \n\nThe authors mainly compare their method with black-box GNNs and show better results. However, no recent works are included for comparison. Though the authors discussed the difference between the proposed method with existing general graph explanation methods. There are actually some ad-hoc explanation methods that do not rely on subgraph patterns, e.g. GSAT. \n\nRef:\nMiao S, Liu M, Li P. Interpretable and generalizable graph learning via stochastic attention \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the positive comments.\n\n*“Concerning the number of lattices and algorithm scalability”*  \nThe scalability of the dataset generation process is related to two main points: (i) dealing with the exponential growth of the number of lattices, (ii) how we may feasibly generate a lattice on a finite set of elements.  \n(i) Since the number of lattices definable on a set L={0,...n-1} increases exponentially with n, it is not feasible to realize a dataset containing all lattices of n elements. However, this is also unnecessary for the scope of this work, which aims at automatically identifying (small) topological patterns responsible for the failure of certain algebraic properties. In addition, the majority of the graphs generated are isomorphic, thus not particularly informative for our task. Because of this, we only generate a portion of all (see point (ii)) lattices up to a certain value $M$, and then take a fixed number of samples $n_s$ up to $N$ ($M=8, n_s = 20, N=50$ in the paper).  \n(ii) Given a set of nodes L={0,...,n-1}, each “candidate” lattice is stored as a $n\\times n$ matrix with a 1 in each position $(i,j)$ meaning that  $i\\leq Lj$, and 0 otherwise, where $\\leq_L$ represents a binary relation on $L$.Then we constraint each matrix to have 1 in the diagonal (for reflexivity), and 0 in each position $(i,j)$ with $j<i$, where $<$ is the order of integers (this allows for the strong pruning of isomorphic lattices per cardinality, see (i), without losing any lattice configuration and while ensuring anti-symmetry). All the remaining pairs of elements $(i,j)$ can be either such that  $i\\leq_L j$ or incomparable (i.e. $i \\nleq_L j$ and $j\\nleq_L i$). Since, the obtained matrix not always represent a transitive relation, we apply (truncated) matrix multiplications of each matrix with itself, to get the transitive closure of the order relation (this step converges in at most $n-2$ iterations), hence, assuring that the relation $L$ represents a partial order. \nFollowing Theorem A.5, we then check if each pair of elements $(i,j)$ admits a (unique!) infimum and supremum (check lattice property) - please refer to lattice.py in the supplementary material for implementation details. The lattice checking and all the lattice operations are translated to standard optimized tensors operations to leverage GPU quicker computations, which becomes particularly advantageous when dealing with lattices’ dimensions for which the computational cost of Algorithm 1 surpasses the overhead of GPU communication. For more details on the complexity of these operations please see the answer to question #1.  \nFinally, the complexity of checking an equational property on a lattice depends on the number of variables and on the lattice terms involved in the equation, e.g. is $n^3$ for the distributive property.\nWe will include these considerations in the Appendix.\n\n*“Control label distribution generated.”*  \nIn our experiments we control the label distribution of train and test splits using sub-sampling. However, this process can be implemented directly in the lattice generation algorithm by filtering the lattices that fulfill the desired properties after applying the \"isLattice\" function within Algorithm 1.\n\n*“Using Gumbel softmax (...) seems novel (...) whether the semantic concept acquired via the one-hot embedding is really meaningful. ”*  \nIn our setting, the nodes’ features are ignored, hence the message-passing algorithm guarantees that similar embedding representations h_i will correspond to nodes with the same neighborhood. Nevertheless, the concepts we want to identify correspond to subgraphs whose nodes’ neighborhood may differ. However, even in this case nodes activating the same concept encoding all share a common pattern i.e., the max value of the node embedding. As an example, we can simply consider the differences in the neighborhood between the top and an intermediate node in an $M_3$ lattice, even if they participate in the same concept.\n\n*\"Missing comparisons, e.g. GSAT”*\nThe  submitted paper already compares iGNNs with GNNExplainer (Fig 10, examples of subgraph explanations) and GCExplainer (Fig 4 for fidelity and completeness, note that: GCExplainer should replace the label “Black-box GNN” in the legend)In the revised version we also include a quantitative comparison with GSAT (see tables in the PDF attached to the main rebuttal), and  observe that GSAT and iGNNs obtain comparable results in terms of task generalization and concept completeness when trained on the proposed UA’s tasks. We thank the reviewer for bringing this method to our attention as it allowed us to strengthen the experimental results.\n\n*“What is the running time (...)?”*  \nThe running time increases polynomially in the size n of the given lattice (it is O(n3) for checking each of the equational properties, e.g. distributivity/modularity, and O(n4) to check if a candidate binary relation is actually a lattice). In a machine with a single quad-core CPU, it requires 20 minutes to generate all the lattices up to n = 8 and sampling 20 lattices for n  [9, 50] (the dataset we used in the paper).  \nWe will integrate the details on the running time in a new section of the appendix and the complexity of the algorithm in its description in Section 3.1.\n\n*“Can the authors include (...) comparison?”*  \nSee the uploaded new tables in the common rebuttal answer.\n\n*“It is recommended (...) provide results in a table…”*  \nSome details of the main key findings were already summarized in the tables 1 and 4 present in appendices C, and D. We will update these two tables and Figure 4 of the main text including the comparison with GSAT.\n"}, {"review_id": "nWthOMstsM", "reviewer": "Reviewer_swnT", "summary": "This paper introduces the novel application of Artificial Intelligence (AI) in the field of Universal Algebra (UA), which has remained unexplored until now. The authors propose a methodology that combines equational and topological characterizations with graph neural networks to investigate UA conjectures. To address the limitations of transparency and explainability in graph neural networks, they develop an algorithm for generating AI-ready datasets based on UA conjectures and introduce a new interpretable graph network layer. Experimental results demonstrate that interpretable graph networks offer enhanced interpretability without compromising task accuracy, successfully validate existing conjectures, and identify subgraphs that suggest the formulation of new conjectures. Overall, this paper presents a pioneering approach that integrates AI with UA, enabling empirical validation and formulation of conjectures in this foundational field of mathematics.", "questions": "na", "limitations": "Limited to finite lattices: The methodology is restricted to finite lattices, which may not capture all the relevant information about infinite algebraic structures. While insights gained from finite-lattice explanations can still provide valuable information, the generalization to infinite structures may be limited.\n\nRestriction to topological properties: The approach focuses on topological properties on graphs, and it may not be applicable to non-structural properties that require the use of other interpretable models. While the method is effective in characterizing equational and topological conjectures, it may not cover a broader range of mathematical properties that are not solely determined by the graph structure.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper propose to use GNN to study the UA subject in the modern mathematics. \n\nThe paper claims to have generated the first UA dataset, which is a previously untouched area.\n\nThis paper also proposed the iGNN which improves model interperability and identifies the relevant subgraphs.", "weaknesses": "As the authors pointed out, the method only applies to finite number of lattices.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We express our sincere appreciation to the reviewer for demonstrating a comprehensive grasp of the fundamental aspects of our paper and for the positive comments about the importance of the problem we investigate, as well as the quality of the presentation and the experimental evaluation.\n \n*“As the authors pointed out, the method only applies to finite number of lattices.”*  \nThe methodology at hand is restricted to the analysis of a finite number of lattices, which is an inevitable consequence of the finite nature of datasets. However, the conjectures derived through the application of our methodology have the potential to encompass infinitely many lattices (as well as infinitely-sized lattices). This is evidenced by the experiments illustrating the Dedekind and Birkhoff theorems 2.3 and 2.4 in the paper, which are known to hold for the entirety of the modular and distributive lattice classes, respectively. In addition, we observe that known and relevant lattice omissions often rely on lattices with few nodes [8,9,10], hence dealing with (small) finite lattices does not seem to significantly affect our approach."}]

Author rebuttal:
We thank all the reviewers for their comments and useful suggestions. In the following, we address the main concerns and questions reviewer-by-reviewer. We also describe minor changes we made based on these suggestions in the reviewed version of the paper, however, the core of our work’s contribution remains unchanged. We earnestly hope that our responses to the reviewers' requests have been sufficiently satisfactory. However, we remain committed to address any additional concerns or queries that may arise during the discussion period, with the ultimate aim of further refining and enhancing the quality and impact of our research work.

**List of changes in the revised version of the paper:**

- Comparison with GSAT added in Table 1 and Table 4 of appendix C and in Figure 4 of the main text (see PDF attached to this comment).
- In line 18 and 19  we rephrase the mentioned statements to contextualize the novelties introduced by our paper with respect to the specific contributions within the field of UA.
- At line 152, we replace the sentence “(...) where \psi and \phi are (...)” with the sentence “(...) where \psi is a learnable function ignoring or assuming constant input features and \phi is (...)”.
We change the sentence at line 67  “(...) every pair of elements has a supremum and an infimum (...)” with the sentence “(...) every pair of elements has a supremum (∨) and an infimum (∧) (...)”.
- Line 77 “it” to “the latter”.
- At line 82 when referring to Figure 2 we modify the sentence to “For instance, Figure 2 represents M3 (modular with 3 atoms) and N5 (non-modular with 5 elements), the smallest instances of lattices which exhibit failures of distributivity and modularity, respectively”.
- We will add the sentence: “Furthermore, we notice that each distributive lattice is also modular, see Appendix A.” after the previous one and we will add the half-line proof of this fact in the appendix.
- Line 119  “L=10” to “n=10”.
- We add the prefix “(sub-)” in front of the word “lattice” in the caption of Figure 6.
- We make explicit mention to which definitions of the appendix A are directly drawn from [11].
- Further considerations about Algorithm 1’s complexity, strategy used for the filtering process, and explanation of the tensorial optimization are now added to a new appendix section.

We notice that the main pdf contains a preliminary version of the appendix, while the finalized version of the appendix can be found in the supplementary material of the submission.

Throughout all the rebuttals, we will use the following common reference numbers.

References:  
[1] https://www.cs.unm.edu/~mccune/prover9/  
[2] Heitzig, Jobst, and Jürgen Reinhold. "Counting finite lattices." Algebra universalis 48.1 (2002): 43-53.  
[3] Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature machine intelligence, 1(5):206–215, 2019.  
[4] Koh, Pang Wei, et al. "Concept bottleneck models." International conference on machine learning. PMLR, 2020.  
[5] Amirata Ghorbani, James Wexler, James Y Zou, and Been Kim. Towards automatic concept- based explanations. Advances in Neural Information Processing Systems, 32, 2019.  
[6] Lucie Charlotte Magister, Dmitry Kazhdan, Vikash Singh, and Pietro Liò. GCExplainer: Human-in-the-loop concept-based explanations for graph neural networks. arXiv preprint arXiv:2107.11889, 2021.  
[7] Heitzig, Jobst, and Jürgen Reinhold. "Counting finite lattices." Algebra universalis 48.1 (2002): 43-53.  
[8] Garrett Birkhoff. On the structure of abstract algebras. In Mathematical proceedings of the Cambridge philosophical society, volume 31, pages 433–454. Cambridge University Press, 1935.  
[9] Richard Dedekind. Über die von drei Moduln erzeugte Dualgruppe. Math. Ann., 1900.  
[10] Bjarni Jónsson and Ivan Rival, Lattice varieties covering the smallest non-modular lattice variety, Pacific J. Math, 1978.  
[11] Stanley Burris and H. P. Sankappanavar. A Course in Universal Algebra. Springer, 1981.

Meta-review: ### Summary

This paper presents an application of graph neural networks (GNNs) in Universal Algebra (UA), which was an uncharted territory until now. UA serves as the foundation of modern mathematics, and this work pioneers the use of AI to investigate UA conjectures with equational and topological characterisations. While traditional approaches have struggled with these problems for decades, the authors propose a new methodology that leverages graph neural networks for analysis.
The authors introduce an algorithm for generating AI-ready datasets based on UA conjectures to overcome the transparency and explainability issues associated with standard neural networks. Furthermore, they developed an interpretable graph network layer, iGNN, designed to enhance interpretability without sacrificing task accuracy.
The paper's contributions include the generation of a benchmark dataset comprising 29,000 lattices of varying sizes and five different properties, along with the introducing of the interpretable neural layer (iGNN) to address UA-related tasks. Empirical results demonstrate that the proposed method successfully generalises across lattice sizes while maintaining interpretability.
In summary, this paper, AFAIK, marks the first introduction of AI into UA, offering a methodology that integrates equational and topological characterisations with interpretable graph neural networks. It validates existing UA conjectures and suggests the formulation of new conjectures, ultimately paving the way for AI-assisted mathematical exploration in this foundational field of mathematics.

## Decision

I was on the fence for this paper as the reviews were mostly positive but borderline. I recommend this paper acceptance due to:

1. It is addressing and exploring a very interesting problem.
2. The paper is well-written and clear.
3. The authors have done a great job answering and addressing the issues raised by the reviewers.

Thus I think this paper would be of interest for the general NeurIPS community.
Decision: Accept (poster)