Diss-l-ECT: Dissecting Graph Data with local Euler Characteristic Transforms

Dear Reviewer,

Thank you for taking your time in reviewing our paper and for acknowledging that our approach addresses key limitations in GNNs by preserving nuanced local structures while maintaining global interpretability.

Regarding your concerns:

To compute ECT or l-ECT, one needs to embed a simplicial complex in a Euclidean space. The authors propose to embed using node features. However, I don't think this is a genuine embedding. For example, if the feature space is $\mathbb{R}^2$, then even if the nodes are embedded to the place in a 1-1 fashion, the edges may cross each other. Therefore, only talking about vertex embedding is insufficient as a graph or a simplicial complex has additional structures.

Indeed, embedding only the vertices of the graph/simplicial complex is insufficient as you point out. However, we embed the whole object (as is described in l.162-164) in a way that the additional structure of the object is respected. In the case of graph (on which we focus in the experiments), this means that we embed the graph in a way that we obtain a graph isomorphism on the image of this embedding. Although edge crossings may happen, the invertibility theorem for Euler Characteristic Transforms still ensures that both the feature vector information and the graph structure can be deduced from the respective ECT (note that the crossing point is not a node!).

Related to 1. The author should be more specific on ``embedding'', whether it is metrical embedding, differential embedding, or topological embedding (or something else?).

By embedding, we mean that we embed the vertices of the simplicial complex using their spatial data (i.e. the feature vectors) and draw edges between embedded nodes in a way that we obtain an isomorphism of simplicial complexes between the original and the embedded complex. In the special case of graphs, this notion of isomorphism is given by graph isomorphism. We apologize for the confusion and will clarify this is our revision.

The proofs are poorly written. The statements are vague and imprecise. Many details are missing. It is hard to assess the correctness of the results.

Thanks for your feedback, we are happy to provide more details on the proofs and revise them accordingly! Could you please pinpoint us to the specific parts which are unclear to you?

It seems to me that the proposed l-ECTs capture local structural information. They are used as node features, but not used to guide feature aggregation. I fail to get the intuition of why they can be useful for the node classification task. However, on the other hand, they might be useful for the graph classification task.

The l-ECT of a given node can be interpreted as a fingerprint of the ego graph of the respective node. Therefore, l-ECTs capture both feature vector information and the structural information of the local graph neighborhood which is sufficient to restore this neighborhood in a lossless way. In this sense, l-ECTs in fact allow for guiding feature aggregation since feature vectors of neighboring nodes are implicitly contained in the respective l-ECT. The intuition is that l-ECTs provide a way to represent local (featured) graph neighborhoods in a lossless way, combining both the structural and spatial information.

Thank you for the response to my comments. However, I am not convinced to change my score for the following reasons (hope the remarks can help the authors improve the quality of the paper).

1. The issue regarding embedding remains. The authors replied with the following: "we embed the vertices of the simplicial complex using their spatial data (i.e. the feature vectors) and draw edges between embedded nodes in a way that we obtain an isomorphism of simplicial complexes between the original and the embedded complex." However, in general, I believe such "an embedding" will not be a graph isomorphism or a homeomorphism, and likely not even a homotopy equivalence. Hence, many topological properties (e.g., Euler characteristic) may be changed during the process.
2. Regarding the proofs, I think it is the responsibility of the authors to make them readable, precise, and rigorous. For example, in the proof of Theorem 1, there are many vague phrasing such as "$\approx$" (how to quantify this?), and the meaning of "since no sampling is involved" is unclear. In the statement of Theorem 2, the statement "provides the necessary information for performing a single message-passing step" is imprecise and not acceptable as a theoretical result. Such issues are all over the place in Appendix A.1.
3. Regarding using I-ECT to generate features, I am not convinced that the local structures of nodes are important in distinguishing node classes. There can be nodes with the same label but completely different neighborhood structures. However, the local topological structures might be useful for the graph classification task.
4. Numerical studies are insufficient as I have pointed out in the review, and they are not fully addressed in the rebuttal.

Dear Reviewer,

thank you very much for carefully reviewing our paper. We are happy to hear that you acknowledge the novelty, utility and very good presentation of our results!

Regarding your concerns:

Limited Applicability: The proposed approach is constrained to graphs with node feature vectors in Rn, limiting its applicability to datasets that fit this specific structure.

Although this might look like a restriction at first, the assumption that node feature vectors lie in a (possibly high-dimensional) Euclidean space is a common one and applies to every node classification task the authors are aware of. Please let us know otherwise, we are happy to generalize our method accordingly!

Effectiveness of Approach: While the concept of embedding the graph into an attribute space using node attribute vectors is promising, the subsequent steps for extracting meaningful information appear less effective. The method could be enhanced by exploring simpler and more efficient ways to utilize the geometry (rather than topology) of ego networks induced within the attribute space.

Although the approach of using local versions of Euler Characteristic Transforms is topological by nature, the resulting representation is in fact a lossless representation of the local graph neighborhood, containing both spatial information (of the respective feature vectors in the neighborhood) and structural information (of the graph structure of the neighborhood). Therefore, l-ECTs should not be seen as capturing pure topological information, but rather providing a fingerprint of ego graphs. We will clarify this aspect in our revision. However, we are happy to consider concrete suggestions which simplify our approach!

Feasibility in High Dimensions: As the dimension n of the feature space increases, the number m of representative vectors on Sn−1 must grow nearly exponentially. Furthermore, the feature vector range impacts the number of intervals {ti} needed. For high-dimensional and wide-range data, this results in a very high-dimensional l-ECT vector, making the approach impractical for real-world applications. Dimension reduction could help by reducing feature dimensionality to three (as two dimensions may be insufficient for graph embedding) and normalizing feature vectors (e.g. total diameter of feature vector space to 2), allowing for "end-to-end" a fixed-size feature extraction for nodes. Without this, selecting vectors and thresholds can be challenging, particularly for new users.

You are correct in the sense that the number of representative vectors on the sphere grows exponentially in order to exceed a certain density threshold. However, it is known that only a fraction of representative directions suffices to obtain a lossless representation of the underlying graph (or simplicial complex) by using (l)-ECTs (see Justin Curry, Sayan Mukherjee, and Katharine Turner. How many directions determine a shape and other sufficiency results for two topological transforms. Transactions of the American Mathematical Society, Series B, 9(32):1006–1043, 2022.). The number of intervals is not affected by the range of the vectors since our l-ECT implementation ensures that we only start tracking information when the maximum (resp. minimum) value in the range is reached via a respective filtration parameter ti. In our experiments, we fixed both hyperparameters which determine the number of directions and interval steps to 60, which worked well even in situations with high-dimensional (several hundreds of dimensions) feature vectors. Moreover, an ablation study on the number of directions used is contained in the appendix and shows that often a very small number of directions suffices for reasonable results.

1. Thank you for clarifying the focus of your model. However, the concern about its applicability remains. Many benchmark datasets, such as citation networks, use binary node features https://ogb.stanford.edu/docs/nodeprop/. Since your model only works with continuous feature spaces in R^n, it is less useful for datasets with binary features. It would strengthen your work to address this limitation or explain how the model could be extended.

2. The embedding of ego networks in feature space is a promising approach for extracting meaningful node information. However, using the l-ECT on ego network embeddings may not provide the most useful features. The topology output often does not change with size or continuous shape changes, which might miss finer details. Geometric measures, such as the diameter or convex hull volume in R^n, could provide more meaningful information, especially with proper normalization in the feature space.

3. I understand the time constraints during the rebuttal period. However, it was expected that you would include experiments with newer GNN models. These would show how your method compares to more recent approaches and make the results more convincing. Without these updates, this part of the work feels incomplete.

Finally, as a reviewer, I find the use of exclamation marks in your responses inappropriate. I am providing feedback on your paper based on my expertise, and I would appreciate a more professional and respectful tone in your responses.

Dear Reviewer,

Thank you for your feedback! Our method is designed as a general-purpose approach to graph learning that inherently works well for heterophilic graphs due to its mechanistic design. Specifically, by leveraging l-ECTs, we introduce an alternative paradigm that moves beyond the fundamental limitations of message-passing approaches. Unlike specialized architectures tailored for heterophilic graphs, our method does not rely on task-specific adaptations or additional mechanisms, which underscores its versatility and applicability across various graph settings.

Given this general-purpose nature, we believe that the most meaningful comparisons are with other general-purpose GNNs, such as GCN or GAT, which are not specifically designed for heterophily but are widely used as baselines across a range of tasks. While we understand the interest in comparing against architectures designed specifically for heterophilic graphs, we argue that such comparisons might not be entirely fair, as these models include domain-specific mechanisms that directly target heterophily. By contrast, our method's strength lies in its ability to perform well on heterophilic graphs without such explicit tailoring. Nevertheless, in the spirit of thoroughness and to address your concern, we are happy to include results comparing our method against one specialized architecture like H2GCN as suggested by you, in addition to the general-purpose GNNs. Moreover, we will add results for one other general-purpose architecture, such as GIN.

Finally, we will incorporate a discussion on how our findings relate to the insights provided in "A critical look at the evaluation of GNNs under heterophily: Are we really making progress?" to situate our contributions within the broader discourse on heterophilic graph learning. We hope this approach demonstrates the unique advantages of our method and emphasizes its general-purpose design while maintaining a balanced perspective on its evaluation.

In the meantime, please feel free to reach out if you have any additional questions. If our responses have sufficiently addressed your concerns, we would be grateful if you could consider re-evaluating your overall rating. Once again, we thank you for the support of our work!

Best regards,

the Authors

Dear Reviewer,

thank you for your thoughtful review and for recognizing the strengths of our paper, particularly the l-ECT’s capacity to enhance interpretability and performance in heterophilic graphs and its model-agnostic design.

Regarding your concerns:

The paper would benefit, both in making more persuasive the novelty of the work with respect to contemporary literature as well as clarity of the work itself, with a more robust background and related works section

Thank you for this suggestion! We will extend the Background and Related Work sections, and sharpen the novelty of our work, in our revision. To our knowledge, there is indeed no other work making use of local variants of the ECT at this point.

The L-ECT approach, while innovative, faces several limitations and lacks certain aspects of novelty. Its computational complexity scales with graph size and density, making it less efficient for very large or dense graphs and primarily feasible for medium-sized datasets.

We are aware of this limitation (see l.234-240) and work on extensions of the proposed method for future work, so that it is also applicable for large and dense graphs. We will clarify this fact better in a revision.

Although L-ECT emphasizes local information preservation, similar topology-aware or geometric GNN approaches also capture neighborhood-specific details, reducing the uniqueness of this feature.

To the best of our knowledge, such topology-aware and geometric GNN approaches are usually based on message passing. Our approach overcomes the fundamental limitation induced by message passing, introducing a novel and interpretable paradigm that allows for graph neighborhood representation without the need of aggregating neighboring feature vector information. Given the recent insights into the fundamental limitations of architectures based on message passing (https://arxiv.org/abs/2408.05486), we believe that our work outlines new research avenues to pursue.

Additionally, traditional GNNs perform comparably well on low-heterophily datasets, indicating that L-ECT may not consistently outperform them across all types of graph data.

Indeed, we do not claim to have found a new state-of-the art method for benchmarking graph datasets (see l.259-263), but we rather propose a fundamentally different approach for graph learning that overcomes fundamental limitations introduced by message passing. As the main advantage of our method, we see its model-agnosticism, interpretability and the different mechanistic design which does not necessitate on node feature vector aggregation.

Moreover, despite its model-agnostic design, L-ECT’s interpretability hinges on pre-defined features, potentially restricting its flexibility for complex, dynamic graphs. Finally, L-ECT does not support end-to-end learning as GNNs do; instead, it relies on external classifiers (e.g., XGBoost), which may limit its integration into more comprehensive, end-to-end pipelines.

Making our method end-to-end learnable is also a direction which we leave for future work. However, we do not see any fundamental obstruction in doing so since the model agnosticism of the method allows for using neural networks for classification. However, the focus of this work was to introduce an approach to graph learning which is both interpretable and applicable to data-scarce scenarios.