From Latent Graph to Latent Topology Inference: Differentiable Cell Complex Module
Authors: Claudio Battiloro
Indro Spinelli
Lev Telyatnikov
Michael M. Bronstein
Simone Scardapane
Paolo Di Lorenzo
Venue: ICLR 2024 poster (2024)
Keywords: Topological Deep Learning
Geometric Deep Learning
Latent Topology Inference
Latent Graph Inference
Cell Complexes
Primary area: learning on graphs and other geometries & topologies
TL;DR: We study Latent Topology Inference (LTI) for learning higher-order cell complexes (with sparse and not regular topology) describing multi-way interactions between data points.

Abstract: Latent Graph Inference (LGI) relaxed the reliance of Graph Neural Networks (GNNs) on a given graph topology by dynamically learning it. However, most of LGI methods assume to have a (noisy, incomplete, improvable, ...) input graph to rewire and can solely learn regular graph topologies. In the wake of the success of  Topological Deep Learning (TDL), we study Latent Topology Inference (LTI) for learning higher-order cell complexes (with sparse and not regular topology) describing multi-way interactions between data points. To this aim, we introduce the Differentiable Cell Complex Module (DCM), a novel learnable function that computes cell probabilities in the complex to improve the downstream task. We show how to integrate DCM with cell complex message-passing networks layers and train it in an end-to-end fashion, thanks to a two-step inference procedure that avoids an exhaustive search across all possible cells in the input, thus maintaining scalability. Our model is tested on several homophilic and heterophilic graph datasets and it is shown to outperform other state-of-the-art techniques, offering significant improvements especially in cases where an input graph is not provided.

FROM LATENT GRAPH TO LATENT TOPOLOGY INFER- ENCE: DIFFERENTIABLE CELL COMPLEX MODULE
Claudio Battiloro*.h +1 Michael Bronstein
Indro Spinelli*:1.
Lev Telyatnikov Paolo Di Lorenzo 1:.
Simone Scardapane
ABSTRACT
Latent Graph Inference (LGI) relaxed the reliance of Graph Neural Networks (GNNs) on a given graph topology by dynamically learning it. However, most of LGI methods assume to have a (noisy, incomplete, improvable, ...) input graph to rewire and can solely learn regular graph topologies. In the wake of the success of Topoological Deep Learning (TDL), we study Latent Topology Inference (LTI) for learning higher-order cell complexes (with sparse and not regular topology) describing way interactions between data points. To this aim, we introduce the Differentiable Cell Complex Module (DCM), a novel learnable function that computes cell probabilities in the complex to improve the downstream task. We show how to integrate DCM with cell complex message message-passing networks layers and train it in end-to-end fashion, thanks to two-step inference procedure that avoids an exhaustive search across all possible cells in the input, thus maintaining scalability. Our model is tested several homophilic and heterophilic graph datasets and it is shown to outperform other state-of-the-ar techniques, offering significant improvements especially in cases where an input graph not provided.
INTRODUCTION
Graph Neural Networks (GNNs) are a versatile tool exploited in a wide range of fields, such as computational chemistry (Gilmer et al. 2017a), physies simulations (Shlomi et al. 2020). and social networks (Xia et al., (021). just to name a few. GNNs have shown remarkable performance in learning tasks where data represented over graph domain, due their ability to combine the flexibility of neural networks with prior knowledge about data relationships, expressed in terms of the underlying graph topology. The literature on GNNs is extensive and encompasses various techniques, typically categorized into spectral (Bruna et al. 2014) and non-spectral (Gori et al. (005) methods. The basic idea behind GNNs is to learn node (and/or) edge attributes representations using local aggregation based on the graph topology, i.e. pessage-passingg networks in their most general form (Gilmer al. 20176). By leveraging this feature, GNNs have achieved outstanding results several tasks, including node and graph classification (Kipf & Welling (017a)). link prediction (Zhang & Chen 2018). and more specialized tasks such as protein folding (Jumper et al. 2021) and neural algorithmic reasoning Veličkovié & Blundell 2021
The majority of GNNs assume the graph topology to be fixed (and optimal) for the task at hand, therefore the focus is usually on designing more sophisticated architectures with the aim of improving the message-passing process. Very recently, a series works (Kazi et al. 2022 de Ocáriz Borde et al., 2023 Topping et al. 2022) started to investigate techniques for Latent Graph Inference (LGI), where the intuition is that data can have some underlying but unknown (latent) graph structure, mainly in cases where only point cloud of data is available but also when the given graph is suboptimal for the downstream task. LGI is of particular interest on a variety of applications. such as disease prediction (Cosmo et al., [2020] Song et al. (021), brain network modeling from MRI/MMI scans (Kan et al.) 2022; Qiao et al. [2018), building networks of patients for automatic and personalized diagnosis (Cosmo al.) 2020; Kazi et al. 2019), recommender systems (Zhang et al. 2023), computer vision
(Bahl et al. 2022, Raboh et al. 2019), and missing data imputation (elyatnikov & Scardapane) 2023 Spinelli et al.] 2020 You et al. 2020). At the same time, the field of Topological Deep Learning
(TDL) (Barbarossa & Sardellitii 2020 Hajij et al. 2023) started to gain interest, motivated by the fact that many systems are characterized by higher-order interactions that cannot be captured by the
'Equal contribution, corresponding authors: (claudio.batiin battiloro, indro.spinelli @ @uniromal.it .it. Supported by: PNRR MUR project PE0000013-FAIR PNRR MUR project 11000001-RESTARRTT Sapienza grant Horizon SNS JU project 6G-GOALS grant Agreement No 101 139232.
RM12218 11B28110006226DSS5SS0 Sapienza University of Rome, Harvard University, 3 Oxford University.

---

DCM
GNN
Q-DGM
CONN
The proposed two-step procedure for Latent Topology Inference (LTI) via regular cell complexes. The Differentiable Cell Complex Module (DCM) is a function that first learns a graph describing the pairwise interactions among data points via the o- o--Differentiabee Graph Module (a-DGM), and then it leverages the graph as the 1-skeleton of a regular cell complex whose 2- cells (polygons), describing multi-way interactions among data points, are learned via the Polygon Inference Module (PIM). The inferred topology is then used in two message-passing networks, at node (Graph Neural Network, GNN) and edge (Cell Complex Neural Network, CCNN) levels to solve the downstream task. The whole architecture is trained in an end-to-end fashion.
Figure 1:
intrinsically pairwise structure of graphs. Topological Neural Networks (TNNs) exploit tools and objects from (algebraic) topology to encode these multi-way relationships. c.g. simplicial (Bodnar et al. 20216: Giusti et al. [2022] Battiloro et al.) (202c)), cell (Bodnar et al. a0).a). or combinatorial complexes (Hajij et al. 2023). However, TDL techniques usually incorporate graphs higher-order complexes by means of deterministic lifting maps, assigning higher-orde order cells to cliques or induced cycles of the graph, thus implicitly assuming that these (task-agnostic, deterministic) complexes are optimal for the downstream task. In addition, whenever input graph is not available, these strategies scale poorly in the size of the input set by requiring an exhaustive (combinatorial) search over all possible cells, making them unfeasible for even medium-sized sets of data points.
Contribution. In this paper, we introduce the concept of Latent Topology Inference (LTI) by generalizing LGI to higher-order complexes. The goal of LTI is not (only) learning a graph structure describing pairwise interactions but rather learning a higher-order complex describing multi-way interactions among data points. As a first instance of LTI, we introduce the Differentiable Cell Complex Module (DCM), a novel deep learning architecture that dynamically learns a cell complex improve the downstream task. The DCM implements two-step inference procedure alleviate the computational burden: first, learning the 1-skeleton of the complex (i.e., a graph) via novel improved version of the Differentiable Graph Module (DGM) (Kazi al.] 2022). and then learning which higher-order cells (polygons) should be included in the complex. Both steps leverage peessage-asssigg (at node and edge levels) and a sparse sampling technique based on the a-entmax class of functions, which allows overcoming the limitation of the original DGM, capable of learning only regular graph topologies. We generalize the training procedure the DGM (Kazi et al. 2022) to train the DCM in an end-to-end fashion. The DCM is tested several homophilic and heterophilic datasets and it is shown to outperform other state-of-the -fethe-rr techniques, offering significant improvements both when the input graph is provided not. In particular, accuracy gains on heterophilic benchmarks with provided input graphs indicate that the DCM leads to robust performance even when the input graph does not fit the data well.
1.1 RELATED WORKS
Latent graph inference (also referred to as graph structure learning) is a problem arising in many applications of graph neural networks and geometric deep learning (Bronstein et al. 202T). Existing LGI approaches belong to two broad classes. Known input graph. These approaches assume the input graph is provided but imperfect in some sense, and attempt to modify it improve the message- passing. Various graph rewiring approaches fall in this category (Topping et al., 2022; Sun et al.) 2022, Chen et al. 2020b Jin al.) [020 Zhao al. 2023). Unknown input graph. Methods in this class learn the graph structure in a dynamic fashion, without necessarily assuming a fixed graph at the beginning of training. Some approaches assume the latent graph be fully connected (complete),
e.g., Transformers (Vaswani et al.) (017) and attentional multi-agent predictive models (Hoshen
2017). whereas other approaches perform sparse latent graph inference, offering computational and learning advantages. Notable sparse LGI techniques are LDDS-GN) (Franceschi et al. 2019). Dynamic GCNNs [Wang et al. 2019), and variants of DGM (Kazi et al. 2022] de Ocáriz Borde et al. 2023). A related but difterent problem is Neural Relational Inference (Kipf et al. 2018), also aiming to infer latent graphs, but usually in an unsupervised fashion, with a focus on physical systems and their time dynamics.
2

---

Topological deep learning TDL stems from the pioneering works on Topological Signal Processing (TSP) (Barbarossa & Sardellitti] 2020] Schaub et al. 2021 Roddenberry et al. [022] Sardellitti et al.
2021 that showed the benefits of considering higher-order (multiwway) re relationships among data
points. Generalizations of the renowned Weisfeiler-Lehmaal graph isomorphism test to simplicial
(SC) (Bodnar al., 2021b) and cell (CW) (Bodnar et al. (02Ta) complexes have been proposed,
along with SC and CW message-pasee paassing architectures. Convolutional SC and CW architectures
2020 Yang al. 2022] Hajij et al. 2020 Yang & Isufi] 2023 Roddenberry et al., 2021; Hajij et al. 2022). Attentional SC and CW architectures have been
have been previously studied in (Ebli et al.
presented in (Battiloro al.j 2023c Giusti et al., 2022 Goh et al.,
2022;
Giusti et al.) 2023). A
notable unifying framework for TDL was proposed in (Hajij et al. 2023). where the concept of
combinatorial complex (CC) generalizing SCs, CWs, and hypergraphs, was introduced along with a general class of messagg-passing CC neural networks. An excellent survey on TDL. can be found in (Papillon et al. 2023). Finally, message passing or diffusion on cellular sheaves (Hansen & Ghrist 2019) built upon graphs were proposed in (Hansen & Gebhart 2020 Bodnar et 22.22 Battiloro et al.
2023a d Barbero et al. 2022) and shown to be effective in heterophilic settings.
Our paper is related to both classes of works and helps to overcome their limitations via mutual synergy: we significantly improve and generalize DGM to enable, for the first time, latent topology inference and learning of non-regular topologies via the machinery of Topological Deep Learning.
2 BACKGROUND
Regular cell complexes. We start with the fundamentals of regular cell complexes, topological spaces that provide an effective way to represent complex interaction systems of various orders. Regular cell complexes generalize both graphs and simplicial complexes.
Definition (Regular cell complex) (Hansen & Ghrist, 2019 Bodnar et al. 2021a). regular cell complex (CW) is topological space C together with partition JoEP of subspaces X, of C called cells, where Pe is the indexing set of C. s.t.
1. For each E C, every sufficient small neighborhood of e intersects finitely many Xo;
2. For all n,a we have that X n Xx, * iff X, S X.. where X, is the closure of the cell;
3. Every Xx is homeomorphic to To.h for some k;;
4. For every a E 'e there is homeomorphism ái of a closed ball in Ii* to X' such that the restriction of Φ to the interior of the ball is homeomorphism onto X,.
From Condition 2, Pe has a poset structure, given by S a iff X, C Xr. and we say that 7 bounds a. This is known as the face poset of C. From Condition 4, all of the topological information about C is encoded in the poset structure of Pec Then, a regular cell complex can be identified with its face poset. From now on we will indicate the cell X, with its corresponding face poset element a. The dimension or order dim(a) ) of a cell a is k, we call it a k-cell and denote it with of to make this explicit when necessary. Regular cell complexes can be described via an incidence relation (boundary relation) with reflexive and transitive closure that is consistent with the partial order introduced in Definition Please see Appendix for combinatorial and algebraic description.
Definition 2 (Boundary Relation). We have the boundary relation < iff dim(a) S dim(r) and there is no cell 8 such that a I T.
In other words, Definition 2 states that the boundary of cell o² of dimension i is the set of all cells of dimension less than & bounding o²_ The dimension or order a cell complex is the largest dimension of any of its cells. A graph G is particular case of cell complex of order 1, containing only cells of order (nodes) and (edges). We can use the previous definitions to introduce the four types of (local) adjacencies present in regular cell complexes:
Definition 3 (Cell Complex Adjacencies) (Bodnar et al. 2021a). For a cell complex and a cell Pe. define:
The boundary adjacent cells B(o) = {T T < o., are the dower-dimensional cells on the boundary of a. For instance, the boundary cells of an edge are its endpoint nodes.
The co-boundary adjacent cell (B(() = (r σ < r), are the nigher-dimensione cells with o on their boundary. E.g., the co-boundary cells of node the edges having that node as endpoint.
3

---

The lower adjacent cells Na(o)) {r 38 such that 8 < and 8 r) are the cells of the same dimension as a that share a lower dimensional cell on their boundary. The line graph adjacencies between the edges a typical example of this.
The upper adjacent cells N,, (o) {r 36 such that o < 8 and r < 6}. These are the cells of the same dimension as a that are on the boundary of the same higher-dimensional cell.
Definition 4 (k-skeleton). A k-skeleton of a regular cell complex C is the subeomplex of C' consisting of cells of dimension at most k.
From Definition 1 and Definition 5, it is clear that the O-skeleton of cell complex is a set of vertices and the 1- I-skeleton is a set of vertices and edges, thus a graph. For this reason, given graph = EV, it is possible to build a regular cell complex "on top of it", i.e. cell complex Cg whose 1-skeleton is isomorphic to G.
Remark We remark that the term "regular" is ambiguous in this context, because a regular cell complex is object as in Definition 1, while regular graph is graph whose neighborhoods' cardinalities are all the same. For this reason, in the following, we will refer to regular cell complex(es) simply as "cell complex(es)," reserving the term "regular" only for graphs.
In this work, we attach order 2 cells to an inferred (learned) subset of induced cycles of the graph G up to length mazz refer to them polygons, and denote the resulting order-2 cell complex with Cg = {V. E, P), where P is the polygons set, with [V] = N, |E| = E, and |P] = P. This procedure is formally a graph into a cell complex can be found in (Bodnar et al. (021a).
lifting map; detailed discussion about the lifting of
Signals over Cell Complexes A k-cell signal is defined mapping from the set D2 of all k-cells contained in the complex, with [Dx] = N₁. to real numbers (Sardellitti et al. 2021):
3kk Dx R
Therefore, for an order-2 complex Cg, the k-cell signals are defined as the following mappings:
Fo TR I1 : R,
22 P IR
(2)
representing node, edge, and polygon signals, respectively, with Ng = N, Ni = E, and N₂ = F celll signals are available, we collect them in feature matrix X2,in = (x (1) E R. where the i-th row 0n (i) = [ [ (o.)...., zx. E R collects the features, i.c. the signals values, the i-th c-clll o. The definition of k-llll signal in (T is sufficient and rigorous for the scope of this paper, however more formal topological characterizations in terms of chain and cochain
spaces can be given (Sardellitti et al. 2021 Bodnar et al. 202 la Hajij et al. 2023).
3 A DIFFERENTIABLE LAYER FOR LATENT TOPOLOGY INFERENCE
We propose a novel layer, depicted at high level in Figure | and in detail in Figure 2 comprising of a series of modules among which the most important one the Differentiable Cell Complex Module (DCM), the first fully differentiable module that performs LTI, i.e. learns a cell complex describing the hidden higher-order interactions among input data points. The DCM equipped with novel sampling algorithm that, at the best of our knowledge, is the first graph/complex sampling technique that allows to generate topologies whose neighborhoods cardinality not fixed priori but can be freely learned in an end-to-end fashion.
The proposed layer takes as input the node feature matrix X E Nx.., and gives as output the updated node feature matrix Xo,out E Nx and the inferred latent cell complex Cg..e- Optionally, the layer can take as input also a graph Gin- To make the layer self-consistent in multi-layer setting, the output can be reduced to the updated node feature matrix Xo,out and the 1-skeleton (graph) Gout of Cg....
We employ a two-step inference procedure to keep the computational complexity tractable, i.e. the DCM module first samples the I-skeleton of the latent cell complex (possibly in sparse way, i.e. E <<< N2), and then it samples the polygons among the induced cycles generated by the sampled edges. The first step is implemented via the novel a- D-Dfferremtiall Graph Module (a-DGM), while
the second step is implemented via the novel Polygon Inference Module (PIM). Directly sampling among all the possible polygons, thus trivially generalizing the DGM framework (Kazi et al. 2022
4

---

DCM
Gin (Oplimal)
Gost
Graph-level
cr- D-DGM
PIM
Complex-level
Gout
Xiaosz Loux
Ca.e
Xa.in
Edge-level MP & Downlift
Uplift
X
Xasior f
Ca.a
X
Node-level MP
Xexnn
Figure 2: The DCM and the proposed architecture.
would have led to intractable complexity, e.g. even at triangles level the sampling would have had a complexity of the order of (VVE3) (,N)), being all edges candidate to be sampled. In the following, describe in detail each module of the proposed layer.
3.1 THE C--DIFFEENTIABLE GRAPH MODULE
The a-DGM a novel variation the DGM and is responsible for inferring the I-skeleton (graph) of the latent cell complex. One of the main limitations of the DGM (Kazi et al. (022) the constraint
of inferring only regular graphs; we solve this problem by proposing a novel sampling procedure
based the a-entmax class of functions (Peters al. 2019), recently introduced in the NLP community to obtain sparse alignments and zero output probabilities. With fixed a > and input E Rdd the a- en-mnaxx function O CENT Rd - A is defined
CENT = arg max (u, s) + (u) 4
(3)
where A = {u F /|||| 1} is the d-dimensional probability simplex and Ha is the family of Tsallis a-entropies parametrized by a parameter a 2 1 (Peters et al.) 2019). For a = equation (3) recovers the standard softmax, while for >> 1 solutions be sparse with degree depending on a. In practice, a can be initialized at a reasonable value (e.g., 1.5) and adapted via gradient descent (Correia et al. 2019).
In a- D--GMM, we first compute auxiliary node features Xo vo (Xo.in) E R Nxdg where vn(-) is MLP otherwise. At this function sim(-) is chosen, the similarities among node embeddings are computed and collected in the vectors z, (sim(xo, (i), Xo, aue (j))}, E R. i.j I....,N.
learnable function, e.g. a GNN if an initial graph Gin is provided point,
Valid examples of sim(-) are cosine similarity, inverse or minus Euclidean square distance.
The (sparse) edge probabilities are then obtained node-wise via a-entmax, i.e. the vectors p; CENT (ENT(C((e) E ER,, 1 1,..., N are computed; layer normalization LN is employed to have better control on the similarities statistics and, consequently, more stability in the training procedure. The (i,j) edge is included in the inferred graph if p.(j) > 0. This procedure leads to directed graph that would be incompatible with the cell complex structure introduced in Section whose 1-skeleton is an undirected graph; the inferred directed graph is converted to the closest undirected graph Sout = {N, E), i.c. each inferred edge is considered as a bidirectional edge to obtain We want further stress the fact that computing edge probabilities via the q-entmax leads sparse and non-regular graphs whose sparsity level can be controlled (or learned) tuning the parameter a. A detailed pictorial description of the a-DGM is shown in Figure 3 (left).
Remark The choice of applying the a-entmax in a node-wise fashion and not directly on a vector containing all the possible similarities (that would have naturally led to undirected graph) is due to the fact that, in the latter case, we empirically observed that the o-entmax consistently leads to heavily disconnected graphs with few hub nodes (therefore, also leading performance drops).
At this point, the intermediate node features Xo.ina E 1R x are computed with one or more usual messagg-passing (MP) rounds over the inferred graph:
Xo, Xn. (i) = = Xo, (i),
(x0, (00,,(()))x0.
(4)
JEN.. (o.)
where (o(-)) and of (+) are learnable functions and + is any aggregation operator.

---

Dueuez
Laus
Gin
Q- e-DGM
PIM
Caml
Zi
Uplift
sim
a
CN
sim
LN
onol
Figure 3: The a-Differentiable Graph Module (left) and the Polygon Inference Module (right).
3.2
UPLIFT MODULE
To fully exploit the potential of cell complexes, it is not sufficient to work at the node level. For this reason, intermediate edge features are learned (or computed) with a MP round of the form:
X X1 (2) = 4/1
+
of (x)x.nnnii)
(5)
jEB(o!)
where (-) is (possibly) learnable function. The boundary B(oa)) of edge is composed by its endpoints nodes of and o. Therefore, the intermediate features X1, (i) of edge i are learned (or computed) as a function of the intermediate node features Xp,ina (i) and Xo,
3.3 THE POLYGON INFERENCE MODULE
The Polygon Inference Module (PIM) is a novel module responsible of inferring the polygons of the latent cell complex by sampling subset of the induced cycles of the inferred 1-skeleton Gout.
To this aim, auxiliary edge features are computed from the auxiliary node features with a MP round as in 5). which we denote in this context with Xı,auz 1n2 (Xo,auz) R Exdi for notation consistency.
At this point, we need a similarity function for the edge embeddings belonging to the same induced cycle. We decide to use the of the pairwise similarities, e.g. for generic cycle of length & made by the edges whose indices are collected in index set I, the similarity is computed (with slight abuse of notation) as:
xim(fx1,uua (i))ez)
= E Σ SET JEI
sim(X1,auz (i), X1
The similarity in (6) for an induced cycle of length k S Kmax contains 21-2 ever, Kmaz is usually very small integer and the sim(fxi,aw)) (i) Jizz) doesn't need to be the sum of pairwise similarities. It can be arbitrarily de- signed, long it similarity measure, i.e. it is higher if the involved embeddings are similar.
terms, how- be trivially distributed. In general,
&1
The similarities are collected in a vector z E R.P.. where is the number of induced cycles, and the polygons probabilities are computed as (CN(((((())) R We set Cg... = & P). where P are the induced eycles with positive probabilities and [P|
P (possibly <<< P).
The updated edge features X1,out E IR Ex are computed with one or more MP rounds as:
X1,mut (i) 71
Xi, (i),
Ne (i) (x1n XI.sne(i))
NLE (eA)
where X is a neighborhoods aggregation operator Hajij et al. 2023 (-).). No (+), and of (-) are learnable functions. A detailed pictorial deseription of the PIM shown Figure (right).
Remark 3. The message- -aaiggggepaiiggggggo rounds in (7) and in (5) (as special case) are instances of message- passing neural networks over cell complexes. Several MP schemes can be defined for cell (simplicial, combinatorial) complexes, please refer to (Bodnar et al. 202 Hajij al.) 2023) for more details. We employ the schemes in (5 7 for two reasons: the first one is that using more sophisticated MP rounds (e.g. moving to cells of higher order than polygons or designing more intensive messages exchange among different cell orders) would have lead to computational intractability; the second one is that moving higher order cells also introduces series of tricky theoretical issues (in terms of the structure of the complex) that are not trivial to tackle (Hansen Ghrist. 2019). We plan to investigate these directions in future works.

---

3.4 DOWNLIFT MODULE AND OUTPUT COMPUTATION
At this point, the output node features oo, E X are learned (or computed) from the updated edge features X1, E TR. Fout and the intermediate node features Xo,int E TR. x Fine as:
out (1)
in (i)
Xu,down (t)
(8)
where the Xo E IR N. X Four are obtained with a MP round of the form:
Xo.down (1) 40
CB 90
(xL,ou(())
(9)
jECB(aP)
with (-)(.) being a (possibly) learnable function. The coboundary CB(a)) of node is composed by all the edges for which node is an endpoint. Therefore, the output features (i) of node i are learned (or computed) the concatenation of its intermediate features and features obtained downlifiting the updated features of the edges for which i is an endpoint.
We present comparison in terms of computational complexity between the DCM and the DGM (Kazi et al. 2022) in Appendix B
3.5
TRAINING OF THE DIFFERENTIABLE CELL COMPLEX MODULE
The proposed sampling scheme based on the a-entmax does not allow the gradient of the downstream task loss to flow both through the graph and polygons inference branches of the DCM, due to the fact that they involve only auxiliary features and the entmax outputs are substantially just a way of indexing the edges and the polygons present in the inferred complex. To enable a task-oriented end-
to-end training of the DCM, we generalize the approach of DGM (Kazi et al. 2022 de Ocáriz Borde ctt al., 2023) and design an additional loss term that rewards edges and polygons involved in a correct classification (in classification tasks) or in "good" predictions (in regression tasks), and penalizes edges and polygons that lead to misclassification or high error predictions. Refer to Appendix Aor
the details.
EXPERIMENTAL RESULTS
In this Section, we evaluate the effectiveness of the proposed framework on several heterophilic and homophilic graph benchmarks. Graph homophily is the principle that nodes with similar labels are more likely to be connected. Traditional Graph/Cell Complex Convolutional Neural Networks (GCNs
and CCCNs) implicitly rely on the homophily assumption, and performance drops are typically observed in heterophilic settings (Bodnar et al. 2022 Spinelli et al. 2022 2023).
Our main goal is show that latent topology inference via the differentiable cell complex module (DCM) allows learning higher-order relationships among data points that lead to significant improve- ments w.r.t. latent graph inference. Since DCM is a generalization of the differentiable graph module (DGM), we use as a comparison the original (discrete) DGM (Kazi et al. 2022) (denoted DGM-E) and its recently introduced Moreover, we also report the results of a simplified variant of our model (denoted as DCM (a = 1)). in which the graph is explicitly learned and all the polygons are taken, i.e. a in the PIM: in this (lower complexity) case, the a a-DGM guides both the edges (explicitly) and the polygons (implicitly) inference steps. We also test a variant, denoted with GCN-CCCN, where the complex is not imputed at all, i.e. the input graph is used in GCN and all the polygons are used in CCCN, and variant, denoted with KCM, where the graph is imputed using a KNN after embedding the node features using an MLP/GCN, and all the polygons & Welling 2017b), GCN2 (Chen et al. 2020aa), GAT /Veličković et al. 2018). and (convolutional) CWN (Bodnar et al.) 2021a) as further baselines and comparisons. In all the experiments, we utilize GCNs at the graph level and CCCNs at the edge level; the details about the architectures employed to obtain the results are given in Appendix The first and the second best results are highlighted.
Euclidean version (de Ocáriz Borde et al. 2023) (denoted DGM-M).
used. Finally, we report the vanilla MLP and GCN (Kipf)
We follow the same core experimental setup of (de Ocáriz Borde et al., 2023 on transductive classification tasks; in particular, we first focus on standard graph datasets such Cora, CiteSeer
7

---

Table Hiomophilic-grappe node classification benchmarks. Test accuracy in % avg.ed over 10 splits.
Cora
CiteSeer
PabMedd
Physacs 0.91
CS
ModaDHom, level
0.81
0.74
0.30
0.20
85.75
1.02
0.28
wio graph
KCM
78.47
2.09
75,20
2.41
86.56
0.91
95.61 4: 0.18
95.14
0.32
DGM-E
62.48
3.24
62.47
3.20
83.89
0.70
94.03
+ 0.45
76.05
6.89
DGM-M
68.86
DCM
78.50 1.31
76.47
2:15
87.38 0.91
96.45 0.12
95.40
0.10
DCM (o 1)
78,73 4: 1.99
76.33
2.75
87.47 0.77
96.22 4: 0.27
95.35 0.37
GON
83.11 2.229
85.75
87.28
GCN2
87.85
1.41
78.53
2.66
89.60 0.70
97.41 0.344
95.05
0.38
GAT
89,81 1.77
78.18
2.31
88.53 0.61
98.87 0.30
94.42 0.70
grapp
KCM
78.43 2.11
75.23
2.45
86.61 0.95
96.16 0.17
95.46 0.36
75.53
87.97
0.24
GUN&COUN
86.19 1.82
78.36
3.33
88.59 0.67
96.91 + 0.300
95.31 0.49
DGM-E
82.11 4:2.4
72.35
1.92
87.69 0.67
95.96 0.40
87.17 3.82
DCM
85.78 1.71
78.72
2.84
$3.49 0.62
96.99 1: 0.44
95.79 0.45
DCM (o- 1)
85.97
1.86
78.60
3.16
88.61
0.69
96.69 0.46
95.78
0.49
Table 2: Heterophilic- -grpii node classification benchmarks. Test accuracy in % avg.ed over 10 splits.
Texas
Wisconsin
Squirrel
Chameleon
Model/Hom. level
0.11
0.21
0.22
0.23
10.24
85.33
2.55
40.35 3.37
MÑo grapts
KCM
84.12 + 11.37
87.10
5.15
35.15 + 1.38
52.12 +: 2.02
DGM-E DGM-M
80.00 +:00:::0 8:31
88,00
5.65
34.35 + 2.34
48.90 +: 3.61
81.67
89.33
1.89
35.00
2.35
48.90 3.61
DCM
85.71 : 7.87
$7.40 3.34
35335 2.24
53.63 3:07
DCM (a D
$4,96 +: 10.24
86.72
6.02
35.25 +: 2.22
53.67 1: 3.19
GUN
41.66 11.72
47,20 9.76
24.19 2.56
32.56 3.53
GCN2
75.50 7.81
74.57 5.38
33.09 +: 1.76
49.50 1: 3.02
GAT
66.72 :: 11.22
60.52 9.23
35.07 +: 2.13
50.73 +: 3.12
V groppt
KCM
83,92 1: 11.15
$4.92 5.21
34.47 +: 1.49
53,12 1: 2.02
65.87
64.57 7.12
2.75
GUN-COON
84,43 9.111
84.03 + 5.42
00M
0OM
DGM-E
60.56 8.03
70.67 10.49
29.87 1: 2.16
41.19 1: 3.85
DGM-M
62.78
76.00 3.26
2.38
2.66
DCM
$4.87 1: 10.04
86.33 5.14
34,95 1: 2.59
$3.05 J. 3.00
DCM
1)
84.96
5.60
85.36
5.05
38.13 + 2.27
53.76 + 3.72
YYang et al. 2016). PubMed, Physics and CS (Shchur et al. 2019). which have high homophily levels ranging from 0.74 to 0.93. We then test our method on several challenging heterophilic datasets, Texas, Wisconsin. Squirrel. and Chameleon (Rozemberczki et al. (022), which have low homophily levels ranging between 0. and 0.23. The results for the homophilic and heterophilic datasets are presented in Tables original graph is available (marked w graph in Tables [nd and more challenging case in which the input graph is assumed to be unavailable (w/o graph).
[ [and 2 respectively. All the models were tested in two settings: assuming the
From Tables Daales[[mme and 2 it evident that the DCM exhibits consistently superior performance compared to alternative methods across both homophilic and heterophilic datasets, both with and without provided input graphs. As expected, our method achieves top performance without an input graph for the heterophilic datasets and with an input graph for the homophilic datasets. We achieve remarkable results considering the input graph for heterophilic datasets. Despite exposing the model to the "wrong" input graphs (in the sense that the topology does not match the structure of the node features), the overall performance of the DCM remains stable, yielding remarkable improvements exceeding 20% for Texas and approximately 10% for Wisconsin compared DGM-M (de Ocáriz Borde et al. 2023). Therefore, observing the results across both homophilic and heterophilic datasets when the input graph is provided, we can appreciate how DCM exploits the available "good" graphs in the first case while being less sensitive to the "wrong" ones in the latter. Our performance on the heterophilic datasets suggests that the learned latent complex has a homophilic 1-skeleton (graph) that enables the involved GCNs and CCCNs to reach higher accuracies. To corroborate this hypothesis, in Figure i we show the evolution of the latent topology during the training for the Texas dataset along with the nodes degree distribution, the percentage of sampled polygons %p. and the homophily level h that we note reaching 0.99 on the final inferred graph from the initial 0. 11. Moreover, the fact that most of the inferred polygons belong to the same class and the pretty high spread of the degree distribution further confirm the effectiveness of the proposed architecture. In Appendix(Eland we report ablation studies, plots, and interpretability hints the inferred complexes.
8

---

Agna
Degaoe
Dagan
Input, %pp 100, 0.11
(b) Epoch %p 90, 0.40
(c) Epoch 180, %p 20, h 0.99
Figure 4: Evolution of the latent complex for the Texas dataset, along with homophily level and nodes degree distribution. Edges in orange, triangles in lilac, squares in purple (K = 4)
CONCLUSIONS
We introduced the paradigm of latent topology inference, aiming to not (only) learn a latent graph structure but rather higher-order topological structures describing multi-way way interactions among data points. We made LTI implementable by introducing the Differentiable Cell Complex Module, a novel learnable function that dynamically learns regular cell complex improve the downstream task in an end-to-end fashion and in a computationally tractable way. via to two-step inference procedure that avoids an exhaustive search across all possible cells the input. We showed the effectiveness of the DCM on a series of homophilic and heterophilic graph benchmarks datasets, comparing its performance against state-of-the- ofrthe-art latent graph inference methods, and showing its competitive performance both when the input graph is provided or not.
LIMITATIONS AND FUTURE DIRECTIONS
To our knowledge, DCM is the first differentiable approach for latent topology inference. The promising results open several avenues for future work.
Methodological. Although cell complexes are very flexible topological objects, other instances of LTI could leverage hypergraphs or combinatorial complexes (CCs) (Hajij et al. 2022). which are able to handle both hierarchical and set-type higher-
nigher-order order interactions. Second, remaining within cell complexes, different MP schemes (Hajij et al. 2023). lifting maps (Bodnar et al., 2021a), or
model spaces (de Ocáriz Borde et al., 2023)
of interest for future work. Third, extending
framework to weighted (Battiloro et al. 2023b) or directed complexes (Courtney & Bianconi 2018)
could give further insights. Finally, one potentially interesting direction is merging LTI and Sheaf Neural Networks in order to learn cellular sheaves defined on latent higher-order complexes.
Computational. While most of experimental validation of the DCM focused on transductive tasks, we could also tackle inductive ones (de Ocáriz Borde et al. 2023). Future works could tailor the DCM to fit challenging specific applications the ones presented in the introduction for LGL. Moreover, though computationally tractable thanks to the proposed two-step inference procedure, DCM may benefit from further improvements to effectively scale on very large datasets. The main bottlenecks are MP operations and the search for the induced cycles of the learned graph. A possible solution for the former could be neighbor samplers (de Ocáriz Borde et al., (023), while the latter could be tackled by leveraging stochastic search methods moving to more flexible topological spaces, e.g. CCs. Finally, our sampling strategy implicitly assumes that there are no specific edges and polygons distribution requirements, e.g. a sampling budget is given particular correlation structure needs to be imposed on the cells. these cases, incorporating more sophisticated sampling methods like IMLE (Li & Malik 2018 Serra & Niepert 2022) could be beneficial.

---

REFERENCES
Gaetan Bahl, Mehdi Bahri, and Florent Lafarge. Single-shot end-to-end road graph extraction. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). pp. 141121111, 2022. doi: 10.1 N0.109/CVPRW5637.22222.000
S. Barbarossa and S. Sardellitti. Topological signal processing simplicial complexes. IEEE Transactions on Signal Processing, 2020.
Federico Barbero, Cristian Bodnar, Haitz Sáez de Ocáriz Borde, Michael Bronstein, Petar Veličković, and Pietro Liò. Sheaf neural networks with connection laplacians, 2022.
C. Batttllroo Z. Wang, H. Riess, Lorenzo, and A. Ribeiro. Tangent bundle filters and neural networks: From manifolds to cellular sheaves and back. In ICASSP 2023 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp- 1-5, 2023a.
Claudio Battiloro, Stefania Sardellitti, Sergio Barbarossa, and Paolo Di Lorenzo. Topological signal processing over weighted simplicial complexes. In ICASSP 2023 2023 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1-5, 2023b.
Claudio Battiloro, Lucia Testa, Lorenzo Giusti, Stefania Sardellitti, Paolo Di Lorenzo, and Sergio Barbarossa. Generalized simplicial attention neural networks. arXiv preprint arXiv:2309.02336
2023c.
Claudio Battiloro, Zhiyang Wang, Hans Riess, Paolo Di Lorenzo, and Alejandro Ribeiro. Tangent bundle convolutional learning: from manifolds to cellular sheaves and back, 2023d.
Claudio Battiloro et al. Generalized simplicial attention neural networks. arXiv:2309.02/38, 2023e.
arXiv preprint
Mathicu Blondel, Andre Martins, and Vlad Niculae. Learning classifiers with fenchel-young losses: Generalized entropies, margins, and algorithms. In AISTATS, pp. 606-615. PMLR, 2019.
C. Bodnar, Frasca, N. Otter, Wang, P. Liò, G. Montufar, and M. Bronstein. Weisfeiler and lehman cellular: Cw networks. In Advances in Neural Information Processing Systems, 2021a.
C. Bodnar, F. Frasca, Y. Wang, N. Otter, G.F. Montufar, P. Liò, and M. Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. International Conference on Machine Learning, 2021b.
Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Advances in Neural Information Processing Systems, 2022.
M.M. Bronstein, J. Bruna, Cohen, and P. Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arXiv:2104. 13478, 2021.
J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, Banff, Canada, 2014.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International conference on machine learning, pp. 1725-1735. PMLR, 2020a.
Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings, 2020h.
Gonçalo M. Correia, Vlad Niculae, and André F. T. Martins, Adaptively sparse transformers. In EMNLI--JCNIPP. pp- 2174-2184. Association for Computational Linguistics, November 2019.
Luca Cosmo, Anees Kazi, Seyed- Aored-Ahmmdd Ahmadi, Nassir Navab, and Michael Bronstein. Latent- graph learning for disease prediction. In Medical Image Computing and Computer Assisted Intervention-MIe MICCAI 2020: 23rd International Conference, Lima, Peru, October 4-8, 2020, Proceedings, Part Il 23, pp. 643-653. Springer, 2020.
10

---

Owen T. Courtney and Ginestra Bianconi. Dense power-law networks and simplicial complexes. Phys. Rev. E, 97:052303, May 2018. doi: 10.1105Phhyyee2.997023333.
Haitz Sáez de Ocáriz Borde, Anees Kazi, Federico Barbero, and Pietro Lio. Latent graph inference using product manifolds. In The Eleventh International Conference Learning Representations, 2023.
Xiaowen Dong, Dorina Thanou, Laura Toni, Michael Bronstein, and Pascal Frossard. Graph signal processing for machine learning: A review and new perspectives. IEEE Signal processing magazine, 17 2020.
S. Ebli, M. Defferrard, and G. Spreemann. Simplicial neural networks. In Advances in Neural Information Processing Systems Workshop on Topological Data Analysis and Beyond, 2020.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 1972-1982, PMLR, 09-15 Jun 2019.
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In International Conference Machine learning. 2017a.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, ICML' pp. 1263-1272. JMI..org, 2017b.
L. Giusti, C. Battiloro, P. Lorenzo, Sardellitti, and S. Barbarossa. Simplicial attention neural networks, 2022.
Lorenzo Giusti, Claudio Battiloro, al. Cell attention networks. In 2023 International Joint Conference on Neural Networks (IJCNN, pp. 1-8. IEEE, 2023.
C. Wei Jin Goh, C. Bodnar, and P. Lio. Simplicial attention networks. In International Conference on Learning Representations Workshop on Geometrical and Topological Representation Learning. 2022.
T. E. Goldberg. Combinatorial Laplacians of simplicial complexes. Senior Thesis, Bard College, 2002.
M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In IEEE International Joint Conference on Neural Networks, 2005.
J. Grady and R. Polimeni. Discrete calculus: Applied analysis on graphs for computational science. Springer, 2010.
M. Hajij, G. Zamzmi, T. Papamarkou, N. Miolane, A. Sézmán-Sáenz, and K. N. Ramamurthy. Higher-order attention networks, 2022.
Mustafa Hajij. Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. In Advances in Neural Information Processing Systems Workshop on TDA & Beyond, 2020.
Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz. Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K. Dey, Soham Mukherjee, Shreyas N. Samaga, Neal Livesay, Robin Walters, Paul Rosen, and Michael T. Schaub. Topological deep learning: Going beyond graph data, 2023.
Hansen and R. Ghrist. Toward a spectral theory of cellular sheaves. Journal of Applied and Computational Topology, 2019.
Jakob Hansen and Thomas Gebhart. Sheaf neural networks, 2020.
Yedid Hoshen. Vain: Attentional multi-agen predictive modeling. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.). Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
11

---

Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang. Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD '20, pp. 66-74, New York, NY, USA, 2020. Association for Computing Machinery.
J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. Zídek, A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 2021.
Xuan Kan, Wei Dai, Hejie Cui, Zilong Zhang. Ying Guo, and Carl Yang. Brain network transformer. Advances in Neural Information Processing Systems, 11-25586-25599 2022.
Anees Kazi, S.Arvind krishna, Shayan Shekarforoush, Karsten Kortuem, Shadi Albargouni, and Nassir Navab. Self-attention equipped graph convolutions for disease prediction. In 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019), pp. 1896-1899, 2019. doi: 10.1
Ances Kazi, Luca Cosmo, Seyed-Ahmad Ahmadi, Nassir Navab, and Michael Bronstein. Differ- entiable graph module (dgm) for graph convolutional networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-1, 2022. doi: 10. 10.1099//
T. N. Kipf and M. Welling. Semi-SSuprrvsed Classification with Graph Convolutional Networks, In International Conference on Learning Representations, 2017a
Thomas Kipf, Ethan Fetaya, Kuan-Chich Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International conference on machine learning, pp. 2688-2697.
PMLR, R, 2018.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017b.
John M. Lee. Introduction to Topological Manifolds, volume 202. 2000.
Ke Li and Jitendra Malik. Implicit maximum likelihood estimation, 2018.
L. Lim. Hodge Laplacians on graphs. Siam Review, 2020.
Mathilde Papillon, Sophia Sanborn, Mustafa Hajij. and Nina Miolane. Architectures of topological deep learning: A survey on topological neural networks, 2023.
Ben Peters, Vlad Niculae, and André F. T. Martins. Sparse
models, 2019.
Lishan Qiao, Limei Zhang, Songcan Chen, and Dinggang Shen. Data-driven graph construction and graph learning: review. Neurocomputing. 312:336-355 2018.
Moshiko Raboh, Roei Herzig, Gal Chechik, Jonathan Berant, and Amir Globerson. Learning latent scene-graph representations for referring relationships. ArXiv e-prints, 3, 2019.
T. M. Roddenberry, N. Glaze, and S. Segarra. Principled simplicial neural networks for trajectory prediction. In International Conference on Machine Learning, 2021.
Signal processing on cell complexes. In ICASSP 2022 2022 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1852-8856, 2022. doi: 10. 11009//AAAS4492222222299999
Mitchell Roddenberry, Michael T. Schaub, and Mustafa Hajij.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale attributed node embedding. Journal of Complex Networks, 9(2), 05 2021. ISSN 2051-1329. doi: 10. 00.1093/commeetcnaa00444 cnab014.
S. Sardellitti. S. Barbarossa, and L. Testa. Topological signal processing over cell complexes. In Asilomar Conference on Signals, Systems, and Computers, 2021.
Amab Sarker, Natalie Northrup, and Ali Jadbabaie, Generalizing homophily to simplicial complexes. In Hocine Cherifi, Rosario Nunzio Mantegna, Luis M. Rocha, Chantal Cherifi, and Salvatore Micciche (eds.), Complex Networks and Their Applications XI, pp. 311-323. Springer International Publishing. 2023.
12

---

M. T. Schaub, Y. Zhu, J.B. Seby, M. Roddenberry, and S. Segarra. Signal processing higher-order networks: Livin' on the edge... and beyond. Signal Processing, 2021.
Giuseppe Serra and Mathias Niepert. Learning to explain graph neural networks, 2022.
Oleksandr Shehur. Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation, 2019.
Jonathan Shlomi, Peter Battaglia, and Machine Learning: Science and Technology, 2(2):021001 dec 2020. doi: (0.1088/233-2255)) abbf9a.
Vlimant. Graph neural networks in particle physics.
Xiaofan Song, Mingyi Mao, and Xiaohua Qian. Auto-metric graph neural network based on a mecta-eerning strategy for the diagnosis of alzheimer's disease. IEEE Journal of Biomedical and Health Informatics, 25(8):31411 3411-315, 2021. doi: 10.1 202///H..221.3000
Indro Spinelli, Simone Scardapane, and Aurelio Uncini Missing data imputation with adversarially- trained graph convolutional networks. Neural Networks, 129:249-260, 2020. ISSN 0893-6080.
doi: https://doi.org// 10160.............. w0w...........e..220000 wewnet.2020.06.000
Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial
Intelligence, 3(3):344-354, 2022. doi: 10. 10.1109/TA1.20211133311
Indro Spinelli, Riccardo Bianchini, and Simone Scardapane. Drop edges and adapt: A fairness enforcing fine-tuning for graph neural networks. Neural Networks, 167:159-167, 2023. ISSN 0893-6080. doi: https://doi.org// 10. 101610066....... mwt.::..numeet.233..0. .0.0......
Qingyun Sun, Jianxin Li, Beining Yang, Xingcheng Fu, Hao Peng, and Philip S. Yu. Self-organization preserved graph structure learning with principle of relevant information, 2022.
Lev Telyatnikov and Simone Scardapane. Ege-gae: scalable graph neural networks for tabular data imputation. Francisco Ruiz, Jennifer Dy, and Jan- an-Willem van de Meent (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 2661-2676. PMLR, 25-27 Apr 2023.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention all you need. Advances in Neural Information Processing Systems, 2017.
Veličković and C. Blundell. Neural algorithmic reasoning. Patterns, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. accepted as poster.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph for learning on point clouds, ACM Trans. Graph., 38(5), oct 2019. ISSN 0730-0301. doi: 10. 145/332636..
Wenwen Xia, Yuchen Li, Jun Wu, and Shenghong Li. Deepis: Susceptibility estimation on social networks. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, WSDM '21, pp. 761-769, New York, NY, USA, 2021. Association for Computing Machinery.
Maosheng Yang and Elvin Isufi. Convolutional learning on simplicial complexes, 2023.
Ruochen Yang, Frederic Sala, and Paul Bogdan. Efficient representation learning for higher- -odher-order data with simplicial complexes. In Bastian Rieck and Razvan Pascanu (eds.), Proceedings the First Learning on Graphs Conference, volume 198 of Proceedings of Machine Learning Research, pp. 13:1-13:21. PMLR, 09-12 Dec 2022.
13

---

Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting supervise learning with graph embeddings. In Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 40-48, New York, New York, USA, 20-22 Jun 2016. PMLR.
Jiaxuan You, Xiaobai Ma, Yi Ding, Mykel J Kochenderfer, and Jure Leskovec. Handling missing data with graph representation learning. Advances in Neural Information Processing Systems, 33: 19075-19087, 2020.
Jinghao Zhang, Yanqiao Zhu, Qiang Liu, Mengqi Zhang, Shu Wu, and Liang Wang. Latent structure mining with contrastive modality fusion for multimedia recommendation. IEEE Transactions Knowledge and Data Engineering, 35(9):155-91177 2023. doi: 10.1 109/TKDE.2022..2221111
M. Zhang and Y. Chen. Link prediction based graph neural networks. Advances in Neural Information Processing Systems, 2018.
Yusheng Zhao, Xiao Luo, Wei Ju. Chong Chen, Xian-Sheng Hua, and Ming Zhang. Dynamic hypergraph structure learning for traffic flow forecasting. In 2023 IEEE 39th International Conference Data Engineering (ICDE), pp. 2303-2316, 2023.
REPRODUCIBILITY STATEMENT
We include all the details about our experimental setting, including the choice of hyperparameters and the specifications of our machine, in Appendix [F] We provide all the code, data splits, and virtual environment needed to replicate the experiments at the following anonymized repository: http://///gthuub..o//ssssnioooo
cww.-eellleoooee comoompllee ex Tee_llxx____eeeeeeeeeeeeeeeeeeee
A TRAINING PROCEDURE
Here we discuss the key concepts about the training of the DCM. We detail how to back propagate through the entmax-based discrete sampling the 1-cell (edge) level (in the aDDGM) and the 2-cell (polygon) level (in the PIM). We follow the approach proposed by(Kazi et al. 2022) and introduce a supplementary loss that rewards edges and polygons involved in correct classification and penalizes the ones which result in misclassification. We define the reward function:
(Ui, ú:) = E (a:) a::
(10)
as the difference between the average accuracy of the i-th sample and the current prediction accuracy, where yi and it are the predicted and true labels, and a; if yt ÿt otherwise. We then define the loss associated to the edge sampling as follows:
LGL =
8 ( Ds) Ep:())
(11)
We estimate E (a:) with exponential moving average the accuracy during the training process
E (a,) = μl (a:) (t) + (1 (1-1)):
(1+1)
(12)
with μ = 0.9 in all our experiments and E (a.) #
classes
Similarly, the loss associated with the polygon sampling is defined as follows:
Lpt. Σ
8 (v). Σ p())
(13)
JEP.
where P, is the set of indices of the polygons for which node is vertex. Following (de Ocáriz Borde ct al. 2023), the accuracy can be replaced with the R2 score in the case of regression tasks. In every experiment, set the initial value of to 1.5.
14

---

Table 3: Execution times expressed in Seconds.
Graph MP
Graph Sampling
Litting
Cell Sampling
Cell MP
GCN
5e
Cora
GCN+CCCN
2
2-
DGM
6e
4e
DCM
le-6
5e-
le
2e-²
5e
GCN
2e-5
Texas
GCN+CCCN
le-2
2
DGM
3e-b
9e
DCM
le-5
9e-4
3e-
7e-2
4e
B COMPUTATIONAL COMPLEXITY
We carry out a complexity analysis of the proposed architecture with a particular focus on the differences with respect to the DGM (Kazi al. 2022). which are:
(a) the introduction of a-entmax to sample cells compared to the Gumbel-Sofiie sampler;
(b) the need to search for all cycles up length Kmaz the skeleton Gouti
(c) the sampling operation over the cycles;
(d) the cell complex neural network;
For (a), the solution to 3) cannot be expressed in closed form except for specific values of a (Correia et al. 2019), but e-approximate solution can be obtained in O(1/ log E) time with bisection algorithm (Blondel et al. 2019).
For (b), leverage the algorithm in (Bodnar et al. 2021a). which has complexity O(EE NP)polylog(N)), where N is the number of vertices, E. the number of sampled edges, and P the number of cycles induced by the skeleton up to length Kmaz. Note that in our implementation the cell complex is recomputed for each iteration, but this computation can be amortized across epochs, approximated with stochastic search algorithms, or leveraging more flexible topological spaces, e.g. Combinatorial Complexes.
For (c), the complexity is the same as (a), which is approximately linear in the number P of cycles. is also approximately linear in the size of the cell complex.
For (d), the complexity of due to the fact that we consider cells of constant maximum dimension and boundary size (Bodnar al. a02
As further empirical analysis, in Table 3 we break down the actual inference execution times on two reference datasets, Cora and Texas, for GCN, GCN+CCCN, DGM, and DCM, based on the (macro-) )operations they require. As we can see from this empirical analysis and as we could expect from the above complexity analysis, the lifting operation (computing the cycles and lifting the node embeddings) and cell sampling (computing the similarities among edge embeddings and applying a-entmax) are the main computational bottlenecks. The lifting operation needs to be performed in every complex-based architecture (we show DCM and GCN+CCCN, but for CWN would be the same). Architectures that not perform LTI (CWN or GCN+CCCN) can mitigate this problem (only) transductive tasks by computing the cycles offline. In our setting, additional solutions w.r.t. the ones presented in (b) could be accumulating the gradients and inferring the every & iteration rather than after every optimization step. The cell sampling bottleneck, unlike the lifting, is not given by any technical requirement, but it is just related to our actual implementation. To keep the code readable and reproducible for (mainly) academic purposes, we use basic data structures and functions, e.g. we store the cells in lists that we parse. However, the bottleneck could be mitigated by optimizing the code. We will soon update our repo
C ADDITIONAL RESULTS
We present series of additional experiments and ablation studies to further validate the effectiveness of the DCM. In particular, in Section C.I we investigate the advantages of employing the a-entmax sampling strategy w.r.t. the Gumbel Top-k trick used in the DGM (de Ocáriz Borde al. 2023
15

---

Table 4: Comparison among sampling strategies on homophilic graph node classification benchmarks. Test accuracy in % avg.ed over 10 splits.
Cora
CiteSeer
PuhMed
Physics
CS
DCM
78.80 = 1.84
76.47 +: 2.45
87.38 = 0.91
96.45 1 0.12
95.40 + 0.40
w/ graph
DCM (a = 1)
78.73 = 1.99
76.32 - 2.75
87.47 = 0.77
96.2 - 0.27
95.35 + 0.37
Top-k DCM
76.16 = 3.71
73.21 2.73
87.13 = 1.22
96,31 0.49
95.25 + 0.08
Top-k DCM All
76.24 = 2.84
73.45 3.12
87.38 = 1.04
96.49 : 0.64
95.17 + 0.07
DCM
85.78 1.71
78.72
88.49 = 0.62
96.99 0.44
95.79 0.48
w graph
DCM (a
85.97 1.86
78.60
3.16
88.61 + 0.69
96.69
0.46
94.81
0.49
Top-k DCM
76.96 3.46
75.50 2.15
86.76 + 0.89
96.19 0.33
94.74 0.28
Top-k DCM All
77.55 = 3.18
75.66
2.67
86.64 = 0.74
96.21 + 0.34
94.79 0.37
Table 5: Comparison among sampling strategies on heterophilic graph node classification benchmarks.
Test accuracy in % avg.ed over 10 splits.
Texas
Wisconsin
Squirre
Chameleon
DCM
85.71 + 7.87
87.49 + 5,94
35.55 = 2.24
53.63 + 3.07 53.67 + 3.19
w graph wo graph
DCM (a 1)
84.96 + 10.24
86.72 + 6.02
35.25
2.22
Top-k DCM
84.21 8.21
84.10 1 6.60
33.90
1.38
52.88 + 4.24
Top-k DCM All
82.71 + 11.25
85.18 + 6.89
33.80
1.47
53.23 +: 3.86
DCM
84.87 + 10.04
86.33 + 5.14
34.95 + 2.59
$3.05 + 3.00
DCM (a = 1)
84,96 + 5.60
85.36 + 5.05
35.13 + 2.27
53.76 + 3.72
Top-k DCM
84.61 + 8.47
82.87 + 7.59
33.77 = 0.91
52.84 + 4.24
Top-k DCM All
84,66 + 9.33
82.10 + 6.64
33.52 + 1.08
51.61 + 4.07
we study the impact of the number of MP layers in (7 (implemented, as explained in Section of the body and Appendix [F], with GCNs and we investigate the usage of different values for the maximum cycle
Kazi et al.
2022). Additionally, in Section C.2
CCCNs). Finally, in Section C.3
size Kmaz-
C.I SAMPLING STRATEGIES
In this section, we assess the impact of employing the a-entmax as sampling strategy, compared to the Top-k sampler utilized in (Kazi et al. [022]] de Ocáriz Borde al. (023). for both homophilic (Table 4 and heterophilic datasets (Table 5). with and without input graph. We compare the two variants of the DCM (again denoted with DCM and DCM (a = 1)) against
same architecture but with Gumbel Top-k sampler in place of the a eeemmax both when explicit sampling is performed edge and polygons level (denoted with Top-k DCM) and when only the edge are sampled and all the polygons are taken (the counterpart of DCM (a = 1), denoted with Top-K DCM All). Our investigation reveals that the capability of o-entmax of generating non-regular topologies leads to significant performance gains on almost all the tested datasets.
C.2 NUMBER OF MESSAGE- LAYERS
In this section, we assess the impact of the number of MP layers on the performance of our model. In Table (for homophilic datasets) and Table (for heterophilic datasets), we show the accuracy as a function of the number of MP layers, i.e. GCNs and CCCNs layers at node and edge levels, respectively. We notice that the determination of an optimal number of message-pant saasaaggpassing layers is not governed by a universal rule but rather depends on the characteristics of the dataset under consideration. However, we observe that employing a single message-passingg yields favorable performance across most of the datasets, further confirming that integrating higher- order information is beneficial. Moreover, the 1-layer configuration maintains a comparable number of trainable parameters w.r.t. the DGM-M (de Ocáriz Borde et al.) 2023) settings, whose results are reported as a comparison. In particular, DGM-M employs 3-layer GCNs while we employ 1-layer GCNs and 1 lllayer CCCNs (having 3 times the number of parameters of single GCN layer), see Appendix F for details. For this reason, despite the fact that some results in Table 6 and in Table are better than the ones reported in the body of the paper, decided to show the that correspond
layer consistently
16

---

Table 6: Results varying the number of MP layers on homophilic graph node classification bench- marks. Test accuracy in % avg.ed ed over 10 splits.
MP layers
Cora
CiteSeer
PubMed
Physics
CS
w graph wo graph
78.80 = 1.84
76.47 + 2.45
87.38 + 0.91
96.45 - 0.12
95.40 1 0.40
2
76,90 2.81
75.86 + 2.35
87.77 + 0.53
97.10 0.15
94.81 + 0.40
3
74.98 = 4.20
74.59
+ 2.35
88.10 = 0.45
97.09 0.11
94.15 + 0.63
69.74 = 3.95
71.41
+: 2.47
87.79 = 0.36
96.80 + 0.08
93.54 + 0.72
85.78 1.71
78.72 + 2.84
88.49 0.62
96.99
0.44
95.79 + 0.48
88.89 1.63
78.42
2.63
88.27 0.54
97.03
0.23
94.50 0.55
88.07 2.26
76.95
2.84
88,97 0.61
97.01
0.12
94.47 + 0.54
86.00 2.21
76.62
+ 2.86
88.62 + 0.76
96.86 0.19
93.66 + 0.51
to architectures whose number of trainable parameters are as similar as possible to the reported
competitors.
C.3 MAXIMUM CYCLE SIZE
In this section, we conduct an ablation study on the maximum length Kmaa of induced cycles taken in consideration to sample the polygons of the latent cell complex. In Table 8 and in Table 9 we show the accuracy even the optimal K maz varies based on the specific dataset, however with top performance obtained in most cases when Kmar=
function of Kmaz. respectively. As for the choice of the number of MP layers.
D ALGEBRAIC DESCRIPTION OF REGULAR CELL COMPLEXES
is possible to give a combinatorial description along with rich algebraic representation regular cell complexes. To do so, it essential introduce an orientation of the cells. Orienting cells mathematically trivial but, in the end, it is only a "bookkeeping matter" (Roddenberry et al. (022). One of the possible ways of orienting cells (Sardellitti al. 2021) via simplicial decomposition of the complex, i.c. subdividing the cell into a set of internal k-simplices (Lec 2000 Barbarossa & Sardellitti 2020), so that i) two simplices share exactly one (k simpplicaa boundary element, which is not the boundary of any other k-cell in the complex; and ii) two k-simplices induce an opposite orientation on the shared (k: 1) -boundary. Therefore, by orienting a single internal simplex, the orientation propagates on the entire cell.
Given an orientation, the structure of an oriented regular cell complex of order then fully captured by the set of its incidence (or boundary) matrices B, E 1 k 1, ..... K, with (or 1)), if o is face of of
entries (t.j) = 0 if - is not face of a². and (i, and its orientation is coherent (or not) with the orientation of of. From the incidence information, we build the Hodge (or combinatorial) Laplacian matrices of order k = O..... K as (Goldberg 2002):
Lg B,B
(14)
L B
B
B
= K
(15)
L (4)
LK = B BR Table 7: Results varying the number of MP layers on heterophilic graph node classification bench- marks. Test accuracy in % avg.ed over 10 splits.
(16)
MP layers
Texas
Wisconsin
Squirrel
Chameleon
w graph w/o graph
85.71 + 7.87
87.49 i 5,94
35.55 : 2.24
53.63 +: 3,07
2
87.89 + 10.24
84.80
+ 4,81
33.30 + 1.67
52.22 +: 4.22
3
82.02 + 8.97
83.64
+ 4.87
33.61 + 2.55
51.34 + 3.25
4
80.75 + 10.80
79.49 + 7.45
31.96 + 2.56
47.82 4.12
84.87 + 10.04
86.33 + 5.14
44.9522.559
53.05
3.00
77.34 - 8.64
76.31
+ 4.92
33.53
52.61 2.73
3
77.34 + 8.09
80.95
+ 6.52
33.18 1.88
51.47 2.80
4
74.76 + 12.01
76.13 4 7.43
33.45 + 2.59
43.65 3.00
17

---

Table 8: Results varying Kman on homophilic graph node classification benchmarks. Test accuracy in % avg.ed over 10 splits.
Kmuz
Cora
CiteSeer
PubMed
Physics
CS
w2rpp wib groph
3
78,38
2.50
75.56 + 1.45
87.44 1 0.91
96.32 = 0.28
95.41 1 0.60
4
78.80
1.84
76.47 + 2.45
87.38 + 0.91
96.45 + 0.12
95.40 + 0.40
78.60
2.60
75.62 +: 1.26
87.54 + 0.98
96.20
95.39 + 0,60
85.54
2.40
78.38 + 1.56
88.50 1:000:::000 0.78
97.01
0.28
95.68 + 0.63
85.78
1.71
78.72 + 2.84
88.49
0.62
96,99
0.44
95.79 + 0.48
85.54
2.43
78.32
+ 1.47
85.75
1.02
97.07 0.40
95.68 + 0.56
Table 9: Results varying Kmaz on heterophilic graph node classification benchmarks. Test accuracy in % avg.ed ed over 10 splits.
Kmax
Texas
Wisconsin
Squirrel
Chameleon
graph with gran
3
85.53 + 9.85
84.80 + 6.29
35.15 + 1.76
53.41 + 3,30
4
85.71 7.87
87.49 5.94
35.55 + 2.24
53.63 3.07
5
80.22 11.54
85.57
7.19
34.98 + 2.15
53.01 = 3.73
85,49 7.89
80.95
7.36
33.11 2.58
52.70
84.87 10.04
86.33 5.14
34,95 + 2.59
53.05 3.00
84.21 + 9.15
81.71
6.33
33.88 + 1.49
52.92 3.30
All Laplacian matrices of intermediate orders, i.e., k I,..., K 1, contain two terms: The first term L also known lower Laplacian, encodes the lower adjaceney among k-order cells, i.c. L (d) (i, - 0 if of & Na(of);; the second term ig also known as upper Laplacian, encodes the upper adjacency among k-order cells, i.e. L (i, = 0 if o & N..(o.) Lo is the usual graph Laplacian. Hodge Laplacians admit the following Hodge decomposition (Lim 2020).
Proposition (Hodge Decomposition) The k-topological signal space F. N. can be decomposed as (Grady & Polimeni 2010):
R im [ + im (B θ ker(Lz))
(17)
where θ is the direct sum of vector spaces, and ker(-) and im(-) are the kernel and image spaces of matrix, respectively.
Let us denote the i-th column of any feature matrix X E N i.e. the vector collecting the i-th signal values all the cells, with [ "e.. RRN, where Tyys is defined in (I.
k-cell signals can be represented over the basis of the eigenvectors of the corresponding Hodge Laplacian matrix Lg. We denote the eigendecoopposition of Lg L U where Ux and Ae diag ( Ae,N, collect the eigenvector and the eigenvalues of L;. respectively. The Cell Complex Fourier Transform (CFT) of order is defined the projection of k-cell signal [x.
onto the eigenvectors of La (Sardellitti et al. 2021):
[
U xx].
(18)
We refer to the eigenvalue domain of the CFT as the frequency domain (or spectrum). A consequence of the Hodge decomposition in is that the eigenvectors belonging im im( are orthogonal to those belonging to im (T) for all 1,..., K
E ADDITIONAL PROPERTIES AND PLOTS OF THE INFERRED COMPLEXES
In this appendix, we analyze properties and show additional plots of the inferred latent cell complexes for the Wisconsin and Cora datasets. The plots shown Figure for the Wisconsin dataset, as the ones shown in Figure 4 are obtained by training the architecture without providing the input graph. The plots in Figure 6 for the Cora dataset show the input and the final inferred latent complexes both when the input graph is provided
not to the DCM. Overall, Figure 5 5nd Figure 6 further show the ability of the DCM to learn a latent complex with a high level homophily. Moreover, in Tables [I and 12 we show the average homophily level of the learned graphs for all the tested datasets, again both when the input graph is provided or not. It is worth noticing that the homophily levels of the learned graphs are always greater than the input graph, on the homophilic datasets.
18

---

Cheik
(a) Input, %/ = 100, h (b) Epoch 0.19
10, %p
= (c, Epoch 50, %. = 51,
h 0.70
h = 0.89
Bagne
(d) Epoch 100, Rp 55 (e) Epoch 150. %y 36. (f) Epoch 200, %pp 18, 0.96
0.98
h
Figure 5: Evolution of the latent complex for the Wisconsin dataset, along with homophily level and nodes degree distribution. Edges orange, triangles in lilac, squares in purple (Kmaz 4)
To give some quantitative hints of the interpretability of the inferred cell complexes, we now present several graph and complex-based metrics for the Cora and Wisconsin datasets, which illustrate how inferred cell complexes align with amenable properties that would be intuitively expected. In particular, assess the properties of the complexes at various levels.
Topological properties. To assess the latent topology w.r.t. the input graphs of the considered datasets, evaluate the normalized total spectral gap between the input graph and the inferred graph, i.e. the sum of differences between the eigenvalues of the input and inferred graph Laplacians divided by the number of nodes. Two graphs
be considered topologically similar if the spectral gap is small (Dong et al. (2020). i.e. if they have similar frequencies, in the sense of Appendix first orient the input complex Cg,, (i.e. the complex having the input graph
D In particular, Iin as I-skeleton and all of its cycles as polygons) and the inferred latent complex Cgous using the procedure presented in Appendix of the input Gin and inferred Gout graphs, respectively. We compute their eigenvalues (Ao.i.n h: and (oo hi and we evaluate their normalized total spectral gap N SGG Pout), defined as:
this point, we compute the graph Laplacians L0,in and Lo,
N
SSG Gout) =
(Ao,s,an Ao.i.out)
(19)
N
19

---

(a) Input graph
(b) Cs... w input graph, h = 0.89 (c) Co.u. w/o input graph, = 0.93
Figure 6: Input graph (a), inferred latent complex if the input graph is provided (b), and inferred latent complex if the input graph is provided (c) for the Cora dataset, along with homophily level. Edges in orange, triangles in lilac, squares in purple (Kaas 4).
In Table 10 we show this metric when the imput graph is provided or not. As the reviewer can notice, the spectral gap on the Cora dataset is in both cases an order of magnitude smaller than the spectral gap on the Wisconsin dataset. This result allows us to state that, if the input graph is provided, our model is able to significantly discard information about it in case it is "bad" graph (Wisconsin, heterophilic), while it is able to retain its main topological properties and sufficiently rewire it to improve the downstream task if it is a "good" graph (Cora, homophilic). On the other hand, if the input graph is not provided, our model able to infer topologically similar graph to the (unseen) input graph if the imput graph is "good" (Cora), while infers a topologically different graph if the input graph is "bad" (Wisconsin).
Homophily properties. To assess the latent topology w.r.t. the node labels y RN of the considered datasets, we employ the Polygon Homophily, which quantifies the fraction homogeneous polygons that connect nodes having the same label, respectively. In particular, the Polygon Homophily is designed by us by generalizing the simplicial homophily from (Sarker et al. (023). and for a regular cell complex Cg the ones we consider, it is computed as:
Hy Co) |Pal IPAl
(20)
|P|-1P|
where P is the set of polygons of the complex Cg. P is the set of induced cycles of the 1-skeleton (graph) G. Ps. is the subset homogeneous polygons, i.e. polygons whose vertices have the same label, and Pr is the subset of homogeneous induced cycles. The polygon homophily reduces to the usual (graph) homophily if edges are considered in place of polygons. With these definitions, a complex exhibits high polygon homophily if Hy, Cc) 2 1. In Table 10 we show the polygon homophily Hy, Cg...) of the inferred complex Co.ur when the input graph is provided not. As the reader can notice combining Table 11. Table 12 and Table 10 the inferred complexes show both graph and polygon homophily.
Feature-dependent properties. To evaluate how the latent topology evolves w.r.t. node features on the considered datasets, we use the notion of total variation (TV) of features defined over nodes and edges (Sardellitti et al.) (02T). In particular, the total variation TV, at the node level is measure of the smoothness of node features, i.e. node features of nodes linked by an edge are similar, the node TV will be small; the total variation TVVi at the edge level is measure of the smoothness of edge features, i.e. if edge features edges belonging to the same polygon are similar, the edge TV will be small. Given orientated cell complex Cg. its order 0 (graph) Lo and order L1 Laplacians. node and edge feature matrices X, and X,, respectively, then the total variation at node and edge level can be computed as:
TVo CG) = Trace { x.. Xo
(21)
TV, (X,, CG) = Trace XX'1,, X1).
(22)
In other words, TV, is the sum of the squared variations of the node signals along the edge of the complex, while TV, is the sum of the squared variations (curls) of the edge signals along the polygons
20

---

of the complex. In Table 10. show the TV (Vo(Xo,in:C.. of the initial node features the imput graph, the TV T (V Cg..) of the initial node features over the inferred graph, the the input graph, the TV TV TV Co.. of
TV (V C...) ) of the final node features the final node features over the inferred graph, the TV (X1 Co... ) of the final edge features the input complex (obtained again considering all the induced cycles polygons), and the TV (XVi(XX,ou Cg...) of the final edge features over the inferred complex. As the reader can notice, the DCM always able to learn embeddings that are smooth over the inferred complex, both at node and edge level, when the input graph is provided or not. Interestingly, not only the learned embeddings are smooth, but also the input features are smoother on the 1-skeleton (graph) of the inferred complex than on the input graph.
The above quantitative analysis, along with the qualitative information given by the various plots, show that the DCM is able to learn complexes that jointly align with data features and data labels, while at the same time being able to extract or retain topological information similar the input graph if it is useful for downstream task. These facts could be particularly useful in more involved and tailored applications, and we plan to investigate this direction in future (more) applied works.
F MODEL ARCHITECTURE
In this appendix, we present a detailed description of the architectures employed to obtain the results in Table [ and Table 2
To ensure uniformity and show the performance gain without intensive ad-hoc hyperparameters tuning (as the ones performed for the DGM (Kazi et al., 2022) and the DGM-M (de Ocáriz Borde et al. 2023)), ), we maintained constant configuration for the number of layers, hidden dimensions, activation functions, Kmar (4), (pseudo-)similarity functions (minus the euclidean distances among embeddings), dropout rates (0.5), and learning rates (0.01) across all datasets. The architecture details are shown in Tables 13 and [4] We conducted training for total of 200 epochs for the homophilic datasets, with the exception of the physics dataset, which underwent 100 epochs like the heterophilic datasets. Our experiments were performed using a single NVIDIA RTX A6000 with 48 GB of GDDR6 memory. As mentioned in Section 4 in every experiment we employ Graph Convolutional Neural Networks (GCNs) and Cell Complex Convolutional Neural Network (CCCNs) as specific MP architectures at node and edge levels, respectively. We give a brief description of GCNs and CCCNs in the following.
Remark 5. The DCM has not to be considered a novel GNN architecture that aims to achieve SOTA performance graph benchmarks. To the best of our knowledge, DCM is the first model that permits learning of higher-order latent interactions while overcoming many of the LGI's (and TDL's) limitations and achieving and matching SOTA results across multiple datasets. In addition, please note that the majority of GNN and TNN architectures could be integrated into DCM as backbones at the node and edge levels as instead of the employed GCN and CCCN.
F.1 GRAPH AND CELL COMPLEX CONVOLUTIONAL NEURAL NETWORKS
Graph Convolutional Neural Networks (GCNs) one of the most famous and simple GNNs architectures. In GCNs, the output features of a node are computed as a weighted sum of linearly transformed features of its neighboring nodes. Therefore, the MP round in (4) implemented as:
Xu,int (i) = Yr
Σ (E.
Oi 0n. (i)
(23)
where W are learnable parameters and the (normalized) weights ony are set as 0zy / dd,
with
d, and d, being the degrees of node and node j, respectively (Kipf & Welling 2017a). Table 10: LTI metrics.
VV(XKaa.Co... $7.55
Ta Co.,)
TV:: Cr... 21kl (o,)
21i (a..
TV: TV5(X Co.,!
Mly.Co... Co..Co...
N. Bae)
Gmgph
$796
811
34-100
Graphs
$756
.9
1.8-10-1
Groph
1201
1883
1007
.35
5.5-10-1
Graph
1201
1763
1289
94
7:2-10
21

---

Table 11: Homophily level of the latent graph on homophilic graph node classification benchmarks.
Cora
CiteSeer
PubMed
Physics
CS
graph
0.93
0.96
0.84
0.98
0.99
graph
0.89
0.78
0.82
0.96
0.92
input
0.81
0.74
0.80
0.93
0.80
Table 12: Homophily level of the latent graph on heterophilic graph node classification benchmarks.
Texas
Wisconsin
Squirrel
Chameleon
w/o graph
0.99
0.99
0.30
0.64
w graph
0.80
0.70
0.29
0.62
input
0.11
0.21
Cell Complex Convolutional Neural Networks (CCCNs) generalize GCNs to cell complexes using the adjacencies introduced in Definition 1. our case, the output features of edge are computed as weighted sum of linearly transformed features of its neighboring edges, over the upper and lower adjacencies. Therefore, this paper, we implement the MP round as:
X1.out (1) 7/1
Gu,i ()) + (E,)
Σ
Σ jENa(o!)
an Wa x1 ())
(24)
where W a. Wd. and W learnable parameters. The weights are normalized with the same approach of GCNs, with upper (for the du,i.5 and lower (for the ad.i,j degrees. The skip connection Xi,int(j) W is as usual beneficial, and the case of CCCNs it has further theoretical justification in terms of Hodge Decomposition and signal filtering, see (Roddenberry et al. 2022; Sardellitti et al.
2021 for further details.
Table 13: Model Architecture.
No. Layer param.
Activation
LayerType
(no. input features, 32)
ReLU
Linear
DCM
(32, 32)
ReLU
Graph Conv
(32, 32)
ReLU
Cell Conv
(64, no. classes)
Softmax
Linear
Table 14: DCM Architecture.
DCM
DCM
No. Layer param.
Activation
Layer type
(32, 32)
ReL.U
Linear
Graph Conv
(32, 32)
ReLU
Lineur
Graph Conv
(32, 32)
None
Lineur
Graph Conv
22


Reviews:
[{"review_id": "m5nqCSO4Ui", "reviewer": "Reviewer_ims6", "summary": "This paper deals with the learning of high-order cell complexes with sparse and not regular graph topology.\n\nThe key is to introduce a learnable function that computes cell probabilities in the complex and integrate with cell complex message-passing network layers in a scalable way. The model achieved improve test accuracy in both homophilic and heterophilic graph node classification benchmarks. However, the improvements seem incremental.", "questions": "What is the time efficiency of DCM, comparing with the baselines?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The key is to introduce a learnable function that computes cell probabilities in the complex and integrate with cell complex message-passing network layers in a scalable way. The model achieved improve test accuracy in both homophilic and heterophilic graph node classification benchmarks.", "weaknesses": "In empirical studies, the improvements on accuracy seem incremental.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t2NhhNjcX2", "reviewer": "Reviewer_XizW", "summary": "This paper proposes a method to learn \"latent topology\" in ML tasks, extending Latent Graph Inference. The idea is to learn a cell complex during training. Their method extends the Differentiable Graph Module (DGM) (Kazi 2022) to Diff. Cell Module (DCM). They also use $\\alpha$-maxent instead of gumball softmax. As I understand it, the procedure involves: \n1. Get auxiliary node features $x_{0,aux}= \\nu (x_{0,in})$ from inputs $x_{0,in}$, (via GNN, if a graph is given, or MLP otherwise).\n2. Use $\\alpha$-maxent to infer a graph (1-simplex). \n3. Build higher order cells (e.g. faces, volumes etc) using message passing (MP) on the inferred lower-order cells (e.g. edges) \n4. Do MP for inference using cell complex conv nets (CCCN). \n\nIn the paper, they mostly only discuss up to 2-simplexes, with the Polygon Inference Module (PIM), and not higher simplexes.  \n\nThey conduct a set of experiments on the usual graph benchmarks and show superior performance against a few baselines, including DGM. Most notably, they point out that most graph based methods (if the graph is similarity based) do not perform well on heterophilic datasets. They find that their method (using 2-simplexes) usually outperforms other methods.", "questions": "1. How efficient is PIM in practice? How does the training time compare with DGM or other baselines? I know you discuss the time complexity in App B, but I'm curious about the wall-clock time. \n2. For eq (6), is there a reasoning saying higher order correlations would be weaker, e.g. randomness of $x_{1,int}$? In principle, you could also consider any contraction, including products of all three $ x(i),x(j),x(v)$. \n3. Table 1, with graph, in about half of the cases GCN outperforms all higher order methods. Any intuition on why? When should we expect higher topology to matter?   \n4. Is the \"sim\" function cosine similarity?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The idea of inferring cell complexes is a nice and natural extension of learning graphs. \n2. Although the number of higher-order cells can grow and quickly become intractable, they seem to use methods that makes this inference manageable (Appendix B and sec. 3.3). \n3. It outperforms others on heterophilic datasets (Table 2)\n4. Extensive tests and ablation studies.  \n5. Well-written with detailed appendix and discussion of limitations", "weaknesses": "1. In PIM, eq (6) restricts the types of polygons that can be inferred (see questions)\n2. Limiting PIM to small polygons may fail to capture long-range dependencies\n3. When a graph is given, the experiments are inconclusive. I appreciate reporting the negative results. But a discussion of the failure cases would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "7ylg8ZyQ99", "reviewer": "Reviewer_EucF", "summary": "The authors introduce a novel Latent Topology Inference (LTI) method that enables the learning of non-regular topologies based on their novel Differentiable Cell Complex Module (DCM). DCM is designed to compute cell probabilities within the complex, thus enhancing downstream tasks. They show how to integrate DCM with cell complex message-passing network layers and train it in an end-to-end fashion, offering significant improvements, especially in cases where an input graph is not provided. The paper demonstrates the effectiveness of the proposed approach on both homophilic and heterophilic graph datasets.", "questions": "- Same as I stated in the section of weakness, on of my major concerns it the organization of Section 3. More efforts are needed in this part. The following few questions might help the authors to refine the section.\n- In the paragraph above 'Remark 2', the layer normalization $\\mathcal{LN}$ is employed. If I understand correctly, $\\mathcal{LN}$ actually works on vectors of similarities. Thus is it really precise to call it as layer normalization?\n- In the same paragraph, the threshold of assigning an edge is set as $0$. Is there any ablation study on the selection of this threshold?\n- In the same paragraph, what is 'parameter $\\alpha$'? Is it mentioned before?\n- In Eqn. (5), how to get $\\mathcal{B}(\\sigma_i^1)$?\n- Similarly, in Eqn. (9),  how to get $\\mathcal{CB}(\\sigma_i^0)$?\n- As shown in Table 2, the performance of DCM is higher without an initial graph than with an initial graph. What could be the possible reason behind this observation?\n- How to modify the proposed method to make it work for directed complexes?\n\nI will raise my score if my concerns are correctly addressed.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The novel $\\alpha$-DGM demonstrates remarkable efficacy in characterizing the 1-skeleton of the latent cell complex.\n- The paper substantiates its claims with extensive experimental results, both in the main body and the appendix, providing a thorough evaluation of the proposed method.\n- The \"Limitations\" section is thoughtfully composed, addressing potential constraints and challenges of the approach.", "weaknesses": "- Section 3.1 initially introduces the $\\alpha$-DGM; however, the subsequent description within this section appears to be inconsistent with the concept of $\\alpha$-DGM.\n- Section 3 would benefit from a reorganization to enhance clarity and coherence. Its current form significantly hinders the understanding of the proposed method. Please reorganize it for readers to follow the description.\n- Notably, there is no dedicated \"Reproducibility Statement\" section in the paper, which hinders providing clear instructions for reproducing the results. The inclusion of such a section would enhance the paper's accessibility and reproducibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)