From Latent Graph to Latent Topology Inference: Differentiable Cell Complex Module

Weaknesses

1. In our paper, DGM refers to the original Differentiable Graph Module of Kazi et al. (2022). Section 3.1 introduces $\alpha$-DGM, which is our prosed variation of DGM that exploits the entmax function instead of Gumbel-Softmax to sample a potentially irregular graph topology. $\alpha$-DGM is the variant we use in our Differentiable Cell Module (DCM), as shown e.g. in Figure 3. This is also reflected in the experiments, where we use DGM only as a baseline model to refer to the original variant of Kazi et al. (2022). We clarified this point in the revised version of the paper.

2. We modified the Section based on the reviewers’ suggestions (please also see our other answers). The organization is as follows: we provide a general overview of the method (Fig. 2), before describing each component in turn, (i) the graph sampling procedure (Section 3.1), the lifting procedure (Section 3.2), our novel polygon sampling method (Section 3.3, Fig. 3), and the final downlifting procedure (Section 3.4). Reviewer XizW suggested this to be the most natural exposition, however, we would be glad to do additional rewriting or reorganization if the reviewer has further suggestions.

3. We added a reproducibility statement immediately after the references and before Appendix A. Please note that we provide a link to an anonymous repository with code allowing to reproduce our experiments.

Questions

1. See Weaknesses 1-2.

2. At the graph level, this operation is applied to a matrix containing row-wise the probability vectors $\mathbf{p}_i$. Each row is normalized based on its empirically computed mean and variance. Hence, this is equivalent to LN as generically used for sequences or sets in transformers. This is also matched in the code (see our previous answer), where we applied the default LN implementation from PyTorch.

3. We set it to $0$ because a similar effect to modifying the threshold can be obtained in the $\alpha$-DGM module by varying the $\alpha$ parameter, which is optimized by gradient descent and does not require manual fine-tuning (which may be time-consuming and dataset-dependent). Nevertheless, we tested two additional values for the threshold (0.1 and 0.01) on a subset of the datasets obtaining similar results, as shown in the following Table.

4. We describe the meaning and the usage of $\alpha$ below Eq. (5). In the revised paper, we made it clear that the Tsallis $\alpha$-entropy is formally a class of functions parametrized by a parameter $\alpha \geq 1$.

5. The boundary of an edge $i$ is simply made by its endpoints node $j$ and $v$. We clarified it below Eq. (5) in the revised paper.

6. The coboundary of a node $i$ is simply made by all the edges for which node $i$ is an endpoint. We clarified it below Eq. (9) in the revised paper.

7. Table 2 is about heterophilic datasets. We expect the DCM to achieve better performance when the graph is not provided. This is because, in the heterophilic setting, the input graph and data structure are in contradiction with the homophily assumption on which most of the well-known Graph and Topological NNs hinge, i.e. connected nodes have similar labels. Indeed, our method achieves top performance without an input graph for the heterophilic datasets and with an input graph for the homophilic datasets, as one could expect. However, even 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 homophilic case while being less sensitive to the "wrong'' ones in the heterophilic case.

8. Implementing Latent Topology Inference for directed complexes is one of the future directions we are definitely most interested in. However, it is not trivial, because fundamental literature about how to theoretically characterize directed regular cell complexes is missing. Few works analyzed directed simplicial complexes (very loosely speaking, a particular case of cell complexes), however, they could be pretty limited as objects to leverage in the context of Latent Topology Inference.

Weaknesses

1. (Includes also the reply to Question 2.) Eq. (6) can be used for polygons of arbitrary size $k$. We initially presented it for the triangle case ($k=3$) just to provide a simple example. We made the choice to decompose the “$k$-th order” similarity as a sum of pairwise similarities to enhance the scalability of our method (trivially, a sum can be parallelized). However, it can be arbitrarily designed, as long as it is a similarity measure, i.e. it is higher if the involved edge features are similar. We rewrote Eq. (6) in its general form for a polygon of arbitrary size $k$ and included the above considerations in the revised paper.

2. The reviewer is right, indeed we conducted extensive ablation studies on the maximum inferrable polygon size $K_{max}$ (Tables 8 and 9 in the Appendix of the revised paper). We performed experiments using values for $K_{max} > 5$ but did not observe improvements. We also observed that very few times the inferred 1-skeletons presented cycles of lengths greater than 4 or 5. Although it has been shown that MP at the polygon level mitigates the GNNs’ limitation in handling long-range interactions (see e.g. Bodnar et al., Giusti et al.), we agree that future research on Latent Topology Inference could explicitly focus on this issue, given the promising results of this work.

3. It is true that, on the homophilic datasets, the results of the DCM with input graph are slightly worse than the other well-known baselines. We argue this is an expected behavior, because those models inherently rely on the homophily assumption. Our results are also consistent with previous literature on LGI (e.g. DGM). On the other hand, DCM consistently shows superior performance in the heterophilic settings when the graph is provided, whereas the performance of the other “homophily-based” methods tends to drop. When the input graph is not provided, the performance of the DCM is consistently superior across all the tested datasets. Finally, please note that DCM is a general framework allowing to employ other more complex GNNs and TopologicalNNs as backbones at the node and edge levels instead of the simpler GCN and CCCN we used in our paper for the sake of simplicity. This feature represents an exciting future direction.

Questions

1. In Table 3 of Appendix B of the revised paper (reported also in the reply to Reviewer ims6), we show a breakdown of the 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 complexity analysis we report in Appendix B, the lifting operation (computing the cycles and lifting the node embeddings) and cell sampling (computing the similarities among edge embeddings and applying the $\alpha$-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 do not perform LTI (CWN or GCN+CCCN) can mitigate this problem (only) on transductive tasks by computing the cycles offline. Additional solutions w.r.t. the ones presented in point (b) of Appendix B could be accumulating the gradients and inferring the graph/cell-complexes once every $t$ 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 are currently working on this and we will soon update our repo, hopefully before the end of the rebuttal period.

2. Please see Weakness 1.

3. About the "why", as explained in detail above, we expect the results of DCM to be comparable to the other baselines on the homophilic datasets. About the “when”, several works tried to give a technical answer. To name a few, some works showed that working on these spaces enhances the expressivity and the handling of long-range interactions (Bodnar et al., Giusti et al.), while some other works leveraged a Signal Processing perspective (Barbarossa et al., Yang et al., Calmon et al.) to prove that working on these spaces provides more versatile and sophisticated frequency-based tools. In general, as it often happens with DL, there is no unique answer. As long as multiway (group, high order, beyond pairwise) interactions play a crucial role in the adopted data, then higher topology will significantly help.

4. The “sim” function is any (pseudo-)similarity measure. Cosine similarity could be employed as well. In our experiments, we use minus the square distance among the embeddings. We clarified this in the revised paper.

Weaknesses

1. It is true that, on the homophilic datasets, the results of the DCM with provided graph are slightly worse than the presented well-known graph-based and complex-based architectures. We argue this is an expected behavior, because those architectures inherently rely on the homophily assumption, i.e. they employ diffusion/message-passing schemes that work better when connected nodes have similar labels. Our results are also consistent with previous literature on latent graph inference (e.g. DGM). On the other hand, DCM consistently shows superior performance in the heterophilic settings when the graph is provided, whereas the performance of the other “homophily-based” methods tends to drop. When the input graph is not provided, the performance of the DCM is consistently superior across all the tested datasets. To conclude, we want to stress that one should not consider DCM only as a novel effective GNN architecture. The main novelty of DCM is in it being (to our knowledge) the first model capable of Latent Topology Inference, i.e. learning of higher-order latent interactions modeled as combinatorial topological spaces (regular cell complexes, in our case). DCM is able to overcome many of the Latent Graph Inference's (and Topological Deep Learning's) limitations and achieve SOTA or near-SOTA results across multiple datasets. In addition, please note that DCM is a general framework allowing to employ other more complex GraphNN and TopologicalNN architectures as backbones at the node and edge levels instead of the simpler GCN and CCCN we used in our paper for the sake of simplicity (Remark 5). This feature represents an exciting direction for future work.

Questions

1. In Table 3 of Appendix B of the revised paper, reported below, we show a breakdown of the inference execution times (in seconds) 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 complexity analysis we report in Appendix B, the lifting operation (computing the cycles and lifting the node embeddings) and cell sampling (computing the similarities among edge embeddings and applying the $\alpha$-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 do not perform LTI (CWN or GCN+CCCN) can mitigate this problem (only) on transductive tasks by computing the cycles offline. Additional solutions w.r.t. the ones presented in point (b) of Appendix B could be accumulating the gradients and inferring the graph/cell-complexes once every $t$ 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 are currently working on this and we will soon update our repo, hopefully before the end of the rebuttal period.