SaNN: Simple Yet Powerful Simplicial-aware Neural Networks

We appreciate your feedback and agree that the lack of formal definitions for oriented features and missing to mention the use of unoriented incidence matrices for unoriented features might have caused confusion. We have now clarified these points and expect this to improve the understanding of the theorems and properties related to orientations.

Regarding simplicial awareness, this property requires a model's output to be dependent on all incidence operators. All baseline methods in our paper rely on the powers of lower-adjacent matrices, upper-adjacent matrices, or Hodge Laplacian matrices. As none of these powers approach zero, all baselines inherently exhibit simplicial awareness. However, excluding MPSN, the other baselines do not match the expressivity of the SWL test, as they do not account for feature aggregation from boundary and coboundary simplices, while the SWL test does. Furthermore, since the baselines other than MPSN do not consider aggregation from coboundary simplices, the node embeddings from these models cannot be shown to be more expressive than those from the WL test.

We will supplement Appendix A with the following text for further clarification: "All baseline methods, including `MPSN, \SCNN, \SCoNe, and \S2CNN, exhibit simplicial awareness as they utilize the powers of lower-adjacent matrices, upper-adjacent matrices, or Hodge Laplacian matrices, none of which approach zero. However, except for \MPSN, these baselines do not match the SWL test in terms of expressivity, as they do not account for feature aggregation from boundary and coboundary simplices, which is considered by the SWL test. Furthermore, since the baselines other than MPSN do not consider aggregation from coboundary simplices, the node embeddings from these models cannot be shown to be more expressive than those from the WL test. We summarize the properties of \SaNN` and the existing SNN models as follows:

We appreciate your feedback regarding Section 4.1. In Section 4.1, we consider unoriented simplices. The details are as follows.

In Section 4.1, we explore example functions that adhere to the conditions in Theorem 4.2, demonstrating that SaNN is as powerful as the SWL test. It is important to note that the SWL test differentiates non-isomorphic simplicial complexes based on structure, not the features they carry as in the commonly used WL test. Consequently, it assumes uniform initial features (colors) across all simplices, which are then updated iteratively [Please refer to Section 3 in Bodnar et al., 2021].

Our goal in showing equivalence to the SWL test is to demonstrate that SaNN assigns distinct embeddings to two non-isomorphic simplicial complexes, irrespective of their features, if the SWL test assigns different colors to their structures. In this context, we consider unoriented uniform features across all simplices, thus dealing with unoriented simplicial complexes.

However, SaNN is also capable of handling oriented features in practice. For instance, in trajectory prediction where flow has orientation, we consider oriented simplicial complexes. In such scenarios, we can also establish orientation equivariance as detailed in the paper, hence validating Property 1. In sum, the two settings are different as highlighted by the reviewer and we have clarified this in the paper. To enhance clarity, we have slightly revised the introductory text of Section 4.1 as follows:

"In this section, we discuss example functions that fulfill the conditions outlined in Theorem 4 and demonstrate that SaNN is as powerful as the SWL test. The SWL test [cf. Appendix C] distinguishes non-isomorphic simplicial complexes based on structure, assuming uniform initial features (colors) across all simplices. To establish equivalence with the SWL test, we consider simplicial complexes with a uniform scalar feature $a$ on all simplices, without attributing any orientation to the features or the simplices. However, it is worth noting that SaNN can also process oriented features in practice, and in such cases, we work with oriented simplicial complexes (or incidence matrices) as defined in Section 2."

It is indeed correct that SaNN demonstrates comparable, and occasionally superior, performance to the baselines on some datasets. However, the real strength of SaNN lies in its significant training time improvements. This means that while maintaining competitive accuracy, SaNN offers substantial computational gains, which is a crucial factor in practical applications. Table 2 illustrates that existing SNN models often encounter out of memory errors when handling very large datasets. In contrast, our proposed SaNN model not only significantly reduces computational time, but also delivers performance that is consistently competitive with, and at times surpasses, that of the existing SNN models.

We agree that citing the Universal Approximation Theorem to propose that $g_k$ can be injectively approximated may seem like a strong assumption. This assumption is primarily used for theoretical justification, and we understand its potential limitations in practical applications. However, it is important to note that we have only used multilayer perceptrons (MLPs) as one possible example of the many functions that $g_k$ could be. It is possible to choose any suitable learnable injective function. Our choice of MLPs is simply an example, and it has indeed performed well in our numerical experiments. Therefore, while the injectivity assumption offers theoretical support, it does not diminish the practical effectiveness of our proposed method.

We agree that SaNN does not consistently outperform other models in terms of prediction accuracy for certain datasets. However, the true strength of SaNN lies in its substantial runtime improvements and theoretical characterization while maintaining competitive accuracy. This computational efficiency is crucial for practical applications. The reduced training time that SaNN offers enables more frequent model retraining, which is particularly beneficial for real-time applications. It also ensures scalability for larger datasets. As shown in Table 2, traditional SNN models struggle with large datasets, while SaNN excels, especially with datasets in simplicial closure prediction where existing SNNs face memory constraints.

In Table 3, although SaNN is not the leader in average accuracies for most datasets, the high standard deviations suggest significant overlap in accuracy results, rendering the differences between the top-performing models statistically insignificant. While SPIN is the fastest for graph classification, it is important to note that it is not applicable to applications involving simplicial complexes such as simplicial closure prediction and trajectory prediction.

While accuracy is indeed a priority in many applications, the balance between accuracy and computational efficiency is an equally critical factor in real-world scenarios. SaNN offers a valuable trade-off in this context, making it a viable option, particularly for large-scale applications.

The predictive models, which are used to learn task-specific embeddings from the embeddings of all simplices (as calculated using Equation 8), are detailed in Appendix H.

To use the edge embeddings learnt using SaNN to perform trajectory prediction, we map the embeddings from the vector space of edge embeddings to the vector space of node embeddings by multiplying them by the incidence matrix $\mathbf{B}_1^T$. We consider the node embeddings of only those nodes that have a possibility of being the next in the trajectory, which are the neighboring nodes of the last node in a trajectory. For a trajectory t, which ends at node i, we use a masking function to extract the embeddings corresponding to the neighboring nodes of the node i. We do this for node embeddings from different depths and concatenate them. We then give the combined node embeddings as input to a decoder MLP which maps the node embeddings to a vector space of dimension same as the maximum number of neighboring nodes of the last node in any trajectory in the dataset. The last layer of the decoder is a softmax activation function, the output of which for a trajectory is a vector containing the probabilities with which the neighboring nodes of the trajectory’s last node become the successor node of that trajectory. For all the datasets, we train SaNN in a supervised manner using the cross-entropy loss function.

To perform simplicial closure prediction for triangles, we concatenate the embeddings of the constituent nodes and edges in the open triangles in the training set. The concatenated embeddings are given as input to a decoder MLP with a sigmoid activation function in the last layer, the output of which is the probability of the open triangles forming a simplex. For all the datasets, we train SaNN in a supervised manner using the binary cross-entropy loss function. Since the datasets are heavily skewed with many negative examples (open triangles that never get closed) than positive examples (open triangles that get closed), we perform oversampling of the positive examples in each training batch and use a weight for positive examples in the binary cross-entropy loss function.

To perform graph classification using the embeddings learnt using SaNN, we combine embeddings of the constituent simplices of all orders in the clique-lifted graphs. Since the number of k-simplices in a training example (a clique-lifted graph) is large concatenating embeddings of all the k-simplices in a training example will result in very high-dimensional embeddings. Therefore, we use summation as the readout function at $k$-simplices level. We, finally, use concatenation as the global-level readout function. Specifically, we take a summation of all the node embeddings, edge embeddings, and triangle embeddings in a graph and concatenate the nodelevel, edge-level, and triangle-level embeddings of the simplicial complex to get one global representation for the simplicial complex. The global embeddings of graphs are given as input to a decoder MLP with either a sigmoid activation function or a softmax activation function as the final layer depending on whether the dataset has two or more classes. For all the datasets, we train SaNN in a supervised manner using the cross-entropy loss function, which takes the output of the decoder and the true graph labels as the input.

The hyperparameters used in SaNN to implement the different tasks are summarized in Tables 5, 7, and 9. We have maintained consistency in our experiments by using the same hyperparameters, such as depth ($T$), order ($K$), and hidden dimensions, across all baseline SNN models. This was done to ensure a fair computational comparison. The predictive models for the three tasks are also the same for all the neural network-based models. Due to space constraints, we provided all these details in the Appendix.

To provide further clarity about the hyperparameters used for benchmarks, we have added the following line to Appendix H: "For a fair computational comparison, the same predictive models, and hyperparameters, namely depth ($T$), order ($K$), and hidden dimensions, were utilized for all the baseline SNN models.

I checked appendix H which indeed gives sufficient details on the experiments. I also appreciate the given responses to my questions. Although the mentioned minor changes to the paper should be easy to incorporate, I would appreciate seeing an updated pdf on openreview. Is it possible to do this?

Thank you!