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

## Abstract

Abstract The Euler Characteristic Transform (ECT) is an efficiently-computable
geometrical-topological invariant that characterizes the global shape of data.
In this paper, we introduce the Local Euler Characteristic Transform ( ℓ − ECT ℓ ECT \operatorname{\ell-ECT} ), a novel extension of the ECT particularly designed to enhance expressivity and interpretability in graph representation learning.
Unlike traditional Graph Neural Networks (GNNs), which may lose critical local details through aggregation, the ℓ − ECT ℓ ECT \operatorname{\ell-ECT} provides a lossless representation of local neighborhoods.
This approach addresses key limitations in GNNs by preserving nuanced local structures while maintaining global interpretability.
Moreover, we construct a rotation-invariant metric based on ℓ − ECT ℓ ECT \operatorname{\ell-ECT} s for spatial alignment of data spaces.
Our method exhibits superior performance than standard GNNs on a variety of node classification tasks, particularly in graphs with high heterophily.

## 1 Introduction

While traditional GNNs often rely on message-passing schemes that aggregate node features, they may lose crucial local information, particularly in the case of graphs with high heterophily. These methods can obscure structural nuances that are key to understanding the relationships between nodes. The Euler Characteristic Transform (ECT), a technique from Topological Data Analysis (TDA), offers a solution as it provides a representation of the given data space.
The ECT captures topological features through sublevel set filtrations across various directions. Notably, it is invertible for so-called constructible sets, ensuring that the original data can be reconstructed from its transform. This invertibility, coupled with efficient computability, positions the $\operatorname{ECT}$ as a powerful tool for representation learning.
In this paper, we extend the ECT to local neighborhoods, presenting the Local Euler Characteristic Transform ($\operatorname{\ell-ECT}$), a method designed to preserve local structural details while retaining global interpretability. The $\operatorname{\ell-ECT}$ captures both structural and spatial information around each data point, making it particularly advantageous for graph-based data.
Our approach specifically addresses the challenge of neighborhood aggregation in featured graphs, ensuring lossless representation of local neighborhoods of nodes.
As it turns out, $\operatorname{\ell-ECT}$s maintain critical local details, and therefore offer a more nuanced representation that can be used for various downstream tasks such as node classification.
Our method is particularly effective for tasks where node feature aggregation may obscure essential differences, such as in graphs with high heterophily. Additionally, the $\operatorname{\ell-ECT}$ framework’s natural vector representation makes it compatible with a wide range of machine learning models, facilitating both performance and interpretability.

As our main contributions, we
(i) construct $\operatorname{\ell-ECT}$s in the context of embedded simplicial complexes and theoretically investigate their expressivity in the special case of featured graphs,
(ii) empirically show that this expressivity positions $\operatorname{\ell-ECT}$s as a powerful tool for interpretable node classification, often superior to standard GNNs, and
(iii) introduce an efficiently computable rotation-invariant metric based on $\operatorname{\ell-ECT}$s which facilitates spatial alignment of geometric graphs.

## 2 Background

##### Simplicial Complexes

A simplicial complex $K$ is a combinatorial structure that generalizes the notion of a graph by including higher-dimensional simplices. Formally, an (abstract) simplicial complex is a finite collection of (abstract) simplices such that every face of a simplex in the collection is also in the collection, and the intersection of any two simplices is either empty or a common face. An (abstract) $k$-simplex is given by a tuple $(v_{0},\dots,v_{k})$ of $k+1$ points, and its faces are given by $(v_{0},\dots\hat{v_{i}},\dots,v_{k})$, where $\hat{v_{i}}$ means that $v_{i}$ is omitted.

##### Euler Characteristic

The Euler characteristic $\chi$ is a fundamental topological invariant that applies to a broad class of topological spaces, including simplicial complexes. For a simplicial complex $K$, the Euler characteristic is defined as

$$ $\chi(K)=\sum_{k=0}^{d}(-1)^{k}\sigma_{k}(K),$ (1) $$

where $\sigma_{k}(K)$ denotes the number of $k$-dimensional simplices in the simplicial complex $K$.
Alternatively, the Euler characteristic can be computed by:

$$ $\chi(K)=\sum_{n=0}^{\infty}(-1)^{n}\text{rank}(H_{n}(K)),$ (2) $$

where $H_{n}(K)$ is the $n$-th homology group of $K$.
The Euler characteristic is therefore invariant under homeomorphisms and plays a key role in classifying topological spaces, with applications ranging from algebraic topology to the analysis of high-dimensional data.

##### Graph Neural Networks and Message Passing

Graph Neural Networks (GNNs) are a class of neural networks designed to operate on graph-structured data. The core mechanism of GNNs is message passing, which iteratively propagates information across the graph. Formally, for a graph $G=(V,E)$ with node features $\mathbf{x}_{v}$ for each node $v\in V$, the message passing framework updates the embedding $\mathbf{h}_{v}^{(t)}$ of each node at layer $t$ by aggregating messages from its neighbors, i.e.,

$$ $\mathbf{h}_{v}^{(t+1)}=\text{UPDATE}\left(\mathbf{h}_{v}^{(t)},\text{AGGREGATE}\left(\{\mathbf{h}_{u}^{(t)}:u\in\mathcal{N}(v)\}\right)\right),$ (3) $$

where $\mathcal{N}(v)$ denotes the neighbors of node $v$, and AGGREGATE and UPDATE are typically learnable functions.

## 3 Related Work

Graph Neural Networks (GNNs) have revolutionized the field of graph representation learning by enabling end-to-end learning of node embeddings through message passing (Kipf & Welling, ). However, traditional GNNs face theoretical limitations that are fundamental obstructions in learning expressive representations of graph data (Xu et al., ). Related to the latter phenomenon, GNNs are known to suffer from issues like oversmoothing (Zhang et al., ; Rusch et al., ) and oversquashing (Di Giovanni et al., ).
Hamilton et al. () and Velickovic et al. () have addressed these issues by incorporating sampling and attention mechanisms into the message-passing paradigm. However, even these advancements often show limited performance, particularly in graphs with high heterophily.
Recent work in graph machine learning started incorporating additional geometric information into architectures, leading to *geometric convolutional networks* (Pei et al., ), as well as *geometric graph neural networks* (Joshi et al., ).
Moreover, the analysis of the theoretical capacity or *expressivity* of an architecture remains an ongoing avenue of research (Morris et al., ), with some works providing additional “topology-aware” inductive biases (Horn et al., ; Verma et al., ) to improve overall GNN expressivity.

The *Euler Characteristic Transform* (ECT) has recently become a popular tool in topological data analysis (Turner et al., ; Ghrist et al., ). Röell & Rieck () have expanded on these ideas, applying them to modern machine learning problems, including shape classification. In Curry et al. (); Marsh et al. (), transformation invariance properties of ECTs are studied. All aforementioned contributions build on global Euler Characteristic Transforms, local aspects, which are necessary for our approach, are not discussed therein.
The use of the ECT is just one example of increasing interest in methods for dealing with higher-order information.
In this context, simplicial complexes provide a richer structure than simple graphs (Yang et al., ; Ebli et al., ), with *message passing* over high-order domains gaining much attention (Bodnar et al., ), and a recent position paper outlining the benefits of methods being capable of working with such domains (Papamarkou et al., ).

## 4 Methods

##### Euler Characteristic Transform (ECT)

The Euler Characteristic Transform (ECT) of an (abstract) simplicial complex $X\subset\mathbb{R}^{n}$ is a function $\operatorname{ECT}(X):S^{n-1}\times\mathbb{R}\to\mathbb{Z}$, given by

$$ $\displaystyle\operatorname{ECT}(X)(v,t)=\chi(\{x\in X|x\cdot v\leq t\}),$ (4) $$

where $\chi$ denotes the Euler characteristic. The interpretation of $\operatorname{ECT}(X)$ is therefore that it scans the ambient space of $X$ in every direction and records the Euler characteristic of the sublevel sets.
In Ghrist et al. (), it is proven that $\operatorname{ECT}(X)$ is invertible, meaning that $X$ can be recovered from $\operatorname{ECT}(X)$, as long as $X$ is a so-called constructible set. The main focus of this work are compact simplicial complexes which are constructible, and therefore the invertibility theorem applies in our setting.

In practice, we approximate $\operatorname{ECT}(X)$ via $\overline{\operatorname{ECT}}(X)_{(m,l)}:=\operatorname{ECT}(X)_{|\{v_{1},\dots,v_{m}\}\times\{t_{1},\dots,t_{l}\}}$
for uniformly distributed directions $v_{1},\dots,v_{m}\in S^{n-1}$ and filtration steps $t_{1},\dots,t_{l}\in\mathbb{R}$. Since $X$ is compact, $t_{1},\dots,t_{l}$ can be chosen to lie in a compact interval $[a,b]$ with $t_{1}=a$ and $t_{l}=b$, and so that the sequence $\{t_{i}\}_{i}$ forms a uniform partition of $[a,b]$. We note that this approximation is efficiently computable and has a natural representation as a vector of dimension $m\cdot l$.
Regarding the choice of the magnitudes of $m,l$ we have the following result.

###### Theorem 1 .

In the above setting, the worst case convergence of
$\overline{\operatorname{ECT}}(X)_{(m,l)}$ to the true quantity $\operatorname{ECT}(X)$ is $\mathcal{O}((\frac{\log m}{m})^{1/(n-1)}\frac{1}{l})$.

Curry et al. () prove that the aforementioned approximation actually determines the true quantity, under mild conditions and for $m,l$ large enough.
We notice that both translations and scalings of $X$ in the ambient space lead to a reparametrization of $\operatorname{ECT}(X)$, and therefore $\operatorname{ECT}(X)$ essentially (up to a parameter change) remains unaltered under these two types of transformations.

###### Theorem 1 .

##### Local ECT ( ℓ − ECT ℓ ECT \operatorname{\ell-ECT} )

Given a simplicial complex $X\subset\mathbb{R}^{n}$ and a vertex $x\in X$, we define the *local ECT* of x with respect to $k\geq 0$ as

$$ $\displaystyle\operatorname{\ell-ECT}_{k}(x;X):=\operatorname{ECT}(N_{k}(x;X)),$ (5) $$

where $N_{k}(x;X)$ denotes an appropriate local neighborhood of $x$ in $X$, whose locality scale is controlled by a parameter $k$. Usually, $N_{k}(x;X)$ will be either the full subcomplex of $X$ which is spanned by the $k$-hop neighbors of $x$, or the full subcomplex of $X$, which is spanned by the $k$-nearest vertices of $x$. The first important special case arises when $X$ is a 0 0-dimensional simplicial complex, which is just a point cloud. In this case, the full subcomplex of $X$, which is spanned by the $k$-nearest vertices of $x$, $N_{k}(x;X)$, is simply given by the $k$-nearest neighbors of $x$.
In light of the invertibility theorem, we note that $\operatorname{\ell-ECT}(x;X)$ can be interpreted as a fingerprint of a local neighborhood of $x$ in $X$. The upshot is that this fingerprint can be well approximated in practice, making it possible to obtain local representations of combinatorial data embedded in Euclidean space. This approximation works by sampling $v_{1},\dots,v_{m}\in S^{n-1}$ and $t_{1},\dots,t_{l}\in\mathbb{R}$, and considering
$\overline{\operatorname{ECT}}(N_{k}(x;X))_{(m,l)}$, instead of $\operatorname{\ell-ECT}_{k}(x;X)$. The latter quantity is well-computable in practice, and the approximation error can be controlled by the sample sizes $m$ and $l$, as we discussed before.
Again, this approximation has a natural representation as a vector of dimension $m\cdot l$, enabling us to encode local structural information of point neighborhoods in an approximate lossless way that can readily be used by machine learning algorithms for downstream tasks.

##### ℓ − ECT ℓ ECT \operatorname{\ell-ECT} in representation learning

Our formulation of $\operatorname{\ell-ECT}$s provides a natural representation of local neighborhoods of embedded simplicial complexes. One important special case is that of featured graphs, meaning graphs in which every node admits a feature vector. The latter data structure forms the basis of many modern graph learning tasks, such as node classification, graph classification, or graph regression. The predominant class of methods to deal with these graph learning problems are message-passing graph neural networks. We develop an alternative procedure for dealing with featured graph data, built on $\operatorname{\ell-ECT}$s and we show that $\operatorname{\ell-ECT}$s provide sufficient information to perform message passing, which we explain in the following.

###### Definition 1 .

A *featured graph* is a (non-directed) graph $\mathcal{G}$ such that every node $v\in\mathcal{G}$ admits a feature vector $x(v)\in\mathbb{R}^{n}$. We denote the set of nodes of $\mathcal{G}$ by $V(\mathcal{G})$, and the set of edges by $E(\mathcal{G})$.

We notice that a featured graph $\mathcal{G}$ can naturally be interpreted as a graph embedded in $\mathbb{R}^{n}$, by representing each node feature vector as a point in $\mathbb{R}^{n}$, and by drawing an edge between two embedded points if and only if there is an edge between the underlying nodes in $\mathcal{G}$. This construction yields a graph isomorphism between $\mathcal{G}$ and the embedded graph if and only if for any pair of nodes $v,w\in\mathcal{G}$ with $v\neq w$ we have $x(v)\neq x(w)$ for their associated feature vectors. In practice, the latter assumption can always be achieved by adding an arbitrarily small portion of Gaussian noise to each feature vector, and we therefore may restrict ourselves to featured graphs that yield an isomorphism on their Euclidean embeddings. We now show that $\operatorname{\ell-ECT}$s are in fact expressive representations in the context of graph learning.

###### Theorem 2 .

Let $\mathcal{G}$ be a featured graph and let $\{\operatorname{\ell-ECT}_{1}(x;\mathcal{G})\}_{x}$ be the collection of local $\operatorname{ECT}$s with respect to the $1$-hop neighborhoods in $\mathcal{G}$. Then the collection $\{\operatorname{\ell-ECT}_{1}(x;\mathcal{G})\}_{x}$ provides the necessary (non-learnable) information for performing a single message-passing step on $\mathcal{G}$.

Thm. [2](#Thmtheorem2) tells us that for a featured graph $\mathcal{G}$ the collection $\{\operatorname{\ell-ECT}_{1}(x;\mathcal{G})\}_{x}$ already contains sufficient information to perform a message passing step.
The advantage of using $\operatorname{\ell-ECT}$s instead of message passing to represent featured graph data lies in the possibility to additionally use $\{\operatorname{\ell-ECT}_{k}(x;\mathcal{G})\}_{x}$ for $k\geq 2$, which contain both structural and feature vector information of larger neighborhoods of nodes in the graph. This type of information is typically *not* explicitly available through message passing since passing messages to non-direct neighbors depends on prior message passing steps, which solely produce an aggregation of neighboring feature vectors.

###### Definition 1 .

###### Theorem 2 .

##### Subgraph counting

Chen et al. () investigate the power of message-passing neural networks with respect to subgraph counting. Specifically, it is proven that message-passing neural networks *cannot* perform induced-subgraph-count of any connected substructure consisting of 3 or more nodes. By contrast, we will now show that $\operatorname{ECT}$s for featured graphs and their local variants can indeed be used to perform subgraph counting. We start with the definitions of the necessary concepts.

###### Definition 2 .

Two featured graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are isomorphic if there is a bijection $\pi:V(\mathcal{G}_{1})\to V(\mathcal{G}_{2})$, such that $(v,w)\in E(\mathcal{G}_{1})$ if and only if $(\pi(v),\pi(w))\in E(\mathcal{G}_{2})$ and so that for all $v\in\mathcal{G}_{1}$ one has $x(v)=x(\pi(v))$ for the respective feature vectors.

A featured graph $\mathcal{G}_{S}$ is called a subgraph of $\mathcal{G}$ if $V(\mathcal{G}_{S})\subset V(\mathcal{G})$ and $E(\mathcal{G}_{S})\subset E(\mathcal{G})$, and such that the respective node features remain unaltered under the induced embedding.
A featured graph $\mathcal{G}_{S}$ is called an induced subgraph of $\mathcal{G}$, if $\mathcal{G}_{S}$ is a subgraph of $\mathcal{G}$, and if $E(\mathcal{G}_{S})=E(\mathcal{G})\cap\mathcal{G}_{S}$.
For two featured graphs $\mathcal{G}$ and $\mathcal{G}_{S}$, we define $C_{Sub}(\mathcal{G};\mathcal{G}_{S})$ to be the number of subgraphs in $\mathcal{G}$ that are isomorphic to $\mathcal{G}_{S}$. Similarly, we define $C_{Ind}(\mathcal{G};\mathcal{G}_{S})$ to be the number of induced subgraphs in $\mathcal{G}$ which are isomorphic to $\mathcal{G}_{S}$.

###### Theorem 3 .

Two featured graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are isomorphic if and only if $\operatorname{ECT}(\mathcal{G}_{1})=\operatorname{ECT}(\mathcal{G}_{2})$.

An immediate consequence of the previous Theorem is the following:

###### Corollary 1 .

$\operatorname{ECT}$s can perform subgraph counting.

As previously stated, GNNs can generally not be used to perform (induced) subgraph counting, and we therefore conclude that $\operatorname{ECT}$-based methods for graph representation learning can be more powerful than message-passing-based approaches.

###### Definition 2 .

###### Theorem 3 .

###### Corollary 1 .

##### Rotation-invariant metric based on local ECTs

The aforementioned invariance properties of $\operatorname{ECT}$s with respect to translations and scalings
naturally raise the question if $\operatorname{\ell-ECT}$s may be used to compare the local neighborhoods of two distinct points.
Unfortunately, the $\operatorname{ECT}$ is sensitive to rotations since rotating the underlying simplicial complex leads to a misalignment of the respective directions in $S^{n-1}$. Since a local comparison should not depend on the choice of a coordinate system, this property is a fundamental obstruction of using $\operatorname{\ell-ECT}$ as a local similarity measure. We therefore construct a rotation-invariant metric as follows.
Let $X,Y\subset\mathbb{R}^{n}$ be two finite simplicial complexes. Since $X,Y$ are finite, $\operatorname{ECT}(X)$ and $\operatorname{ECT}(Y)$ only take finitely many values, and we can therefore define a similarity measure $d_{\operatorname{ECT}}$ between $X$ and $Y$ as

$$ $\displaystyle d_{\operatorname{ECT}}(X,Y):=\inf_{\rho\in SO(n)}\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho Y))\right\rVert_{\infty}$ (6) $$

We first prove that this similarity measure satisfies the definitions of a metric.

###### Theorem 4 .

$d_{\operatorname{ECT}}$ is a metric on the collection of rotation classes of finite simplicial complexes embedded in $\mathbb{R}^{n}$.

Thm. [4](#Thmtheorem4) ensures that we may use $d_{\operatorname{ECT}}$ as a metric that measures the similarity between embedded simplicial complexes up to rotation. In particular, for a simplicial complex $X\subset\mathbb{R}^{n}$ and $x,y\in X$, we have a rotation-invariant measure to compare local neighborhoods of $x$ and $y$ by setting

$$ $\displaystyle d_{\operatorname{ECT}}^{k}(x,y;X):=\inf_{\rho\in SO(n)}\left\lVert\operatorname{\ell-ECT}_{k}(x;X)-\operatorname{\ell-ECT}_{k}(y;\rho X)\right\rVert_{\infty}$ (7) $$

In practice, we approximate $d_{\operatorname{ECT}}$ by

$$ $\displaystyle d_{\operatorname{ECT}}(X,Y)\approx\inf_{\rho\in SO(n)}\left\lVert\overline{\operatorname{ECT}}(X)_{(m,l)}-\overline{\operatorname{ECT}}(\rho Y)_{(m,l)}\right\rVert_{\infty}$ (8) $$

for a choice of samples $v_{1},\dots,v_{m}\in S^{n-1}$ and $t_{1},\dots,t_{l}\in\mathbb{R}$ (and in an analogous manner for the local version $d_{\operatorname{ECT}}^{k}(x,y;X)$). As we pointed out before, the approximations of the $\operatorname{ECT}$s used in Eq. [8](#S4.E8) have a natural vector representation, so that the $\left\lVert\bullet\right\rVert_{\infty}$ in Eq. [8](#S4.E8) is in fact the maximum of the entry-wise absolute differences between the two respective representation vectors.
Therefore, the approximation shown in Eq. [8](#S4.E8) is efficiently computable for a large class of data spaces, however for our experiments in Sec. [5](#S5) we use the Euclidean metric instead for differentiability reasons.

###### Theorem 4 .

##### Limitations

While $\operatorname{\ell-ECT}$s present clear advantages in preserving *local* details, there are some trade-offs to consider. In certain cases, message-passing GNNs, which aggregate information across neighbors, may be preferable for tasks where global context is more important than local details. Furthermore, while our method is computationally feasible on medium-sized datasets (as demonstrated in our experiments), the complexity of “naïvely” calculating $\operatorname{\ell-ECT}$s increases for larger $k$ and with the size and density of the graph, suggesting a need for improved methods.

## 5 Experiments

In this section, we present experiments to empirically evaluate the performance of the
$\operatorname{\ell-ECT}$-based approach in graph representation learning, focusing on node classification tasks. We aim to demonstrate how
$\operatorname{\ell-ECT}$ representations can capture structural information more effectively than traditional message-passing mechanisms, especially in scenarios with high heterophily. Our experiments compare the performance of
$\operatorname{\ell-ECT}$-based models against the standard GNN models graph attention networks (GATs) and graph convolutional networks (GCNs). Furthermore, we showcase how the rotation-invariant metric from Sec. [4](#S4) may be used for spatial alignment of graph data through experiments.

### 5.1 ℓ − ECT ℓ ECT \operatorname{\ell-ECT} s in graph representation learning

The link between message passing and $\operatorname{\ell-ECT}$s, which we stated in Thm. [2](#Thmtheorem2), encourages us to empirically validate the expressivity of $\operatorname{\ell-ECT}$s in the context of node classification. For a featured graph $\mathcal{G}$ and fixed $k\geq 0$, we assign $\operatorname{\ell-ECT}_{k}(x;\mathcal{G})$ to every node $v\in\mathcal{G}$. The $\operatorname{\ell-ECT}$ corresponding to a node together with the respective node feature vector is subsequently used as the input of a simple model for the underlying node classification task. In our experiments, this classifier is given by XGBoost, as we found it to outperform other, more complex models like neural networks, but we emphasize that the choice of the model can be controlled by the user. Notice that we do *not* claim to have found a new state-of-the-art for benchmarking graph datasets, but we rather showcase that an approach based on $\operatorname{\ell-ECT}$ lets us obtain results that are *on a par with and often superior* to common graph-learning techniques based on message passing, like graph attention networks (GATs) and graph convolutional networks (GCNs).

We find that $\operatorname{\ell-ECT}$s work particularly well in situations where aggregating neighboring information is inappropriate, as for graphs that exhibit a high degree of heterophily, for example. In these situations our approach may outperform message-passing-based methods by far. The upshot of our method is that local graph information can be incorporated without the architectural necessity to diffuse information along the graph structure, as it is the case for message-passing-based models. While this discrete diffusion process induced by message passing is useful for a plethora of graph learning tasks, it can also be an obstruction in learning the right representation for tasks where node features of neighbors in the graph should not be aggregated. In this sense, $\operatorname{\ell-ECT}$s naturally overcome a fundamental limitation, which (by design) is induced by message passing.
The second advantage of $\operatorname{\ell-ECT}$s is that they are agnostic to the choice of the downstream model. This allows using models that are easy to tune, enabling practitioners to make use of their graph data without necessarily having specialized knowledge in GNN training and tuning. Moreover, it permits using models that are *interpretable*, making our method well-suited for domains where regulatory demands often ask for levels of interpretability that cannot readily be achieved by (graph) neural networks.
In fact, by using feature importance values (which are directly available for tree-based algorithms like XGBoost) and since the entries of the $\operatorname{\ell-ECT}$ vectors that are used as the input for the model can be linked to the directions in the calculation of the $\operatorname{\ell-ECT}$s, one obtains a deeper spatial understanding of how the model arrives at predictions. A further discussion on interpretability and an ablation on the directions used for the $\operatorname{\ell-ECT}$s is contained in the appendix. Finally, we notice that our method enables practitioners to make use of models that do not necessitate a validation split in the dataset, making a larger portion of the data accessible for training and testing.

##### Implementation details

For our experiments, we assume that we are given a featured graph $\mathcal{G}$ such that there is an assignment $V(\mathcal{G})\to\mathcal{Y}$, with $V(\mathcal{G})$ being the node set of $\mathcal{G}$ and $\mathcal{Y}$ being the space of classes w.r.t. the underlying node classification task. For a fixed $k\geq 0$, $x\in V(\mathcal{G})$ and $N_{k}(x;\mathcal{G})$ being the $k$-hop neighborhood of $x$ in $\mathcal{G}$, we then approximate $\operatorname{\ell-ECT}_{k}(x;\mathcal{G})$ via $\overline{\operatorname{ECT}}(N_{k}(x;\mathcal{G}))_{(m,l)}$ for sampled directions and filtration steps, as explained in Sec.[4](#S4). In our setup we use $m=l=64$, but the number of samples can be seen as hyperparameters and may be tuned in practice(^1^11Thm.[1](#Thmtheorem1) provides an order of magnitude for a reasonable choice of $m$ and $l$.). The resulting $m\cdot l$-dimensional vector(s) $\overline{\operatorname{ECT}}(N_{k}(x;\mathcal{G}))_{(m,l)}$ together with the feature vector of $x$ then serve as additional input information for the classifier, corresponding to node $x$. As the classifying model we use a simple XGBoost classifier without tuning the hyperparameters, which should showcase how well our method performs out of the box.
The architecture of our baseline models is mostly inspired by Platonov et al. (). In particular, we add a two-layer MLP after every graph neighborhood aggregation
layer and further augment the models with skip connections (He et al., ) and layer normalization (Ba et al., ). For each run, the respective model is trained for $1000$ epochs, and we report the test accuracy corresponding to the state of the model that admits the maximum validation accuracy during training. The performance of our baseline models are comparable with the results stated in Platonov et al. ().

We start our observations with the WebKB datasets, first introduced in Pei et al. (). For all three datasets Cornell, Wisconsin and Texas our $\operatorname{\ell-ECT}$-based approach outperforms the baseline GNNs, by far. While the combination of both $\operatorname{\ell-ECT}_{1}$ and $\operatorname{\ell-ECT}_{2}$ performs best for Cornell and Texas, using solely $\operatorname{\ell-ECT}_{1}$ leads to best performance for Wisconsin. However, also for the two aforementioned datasets the combination of $\operatorname{\ell-ECT}_{1}$ and $\operatorname{\ell-ECT}_{2}$ only slightly improves the performance in comparison to $\operatorname{\ell-ECT}_{1}$, suggesting that $1$-hop neighboring information is already very informative for these tasks. The results are summarized in Tab. [1](#S5.T1).

**Table 1: Performance (in accuracy) of different graph learning models across multiple datasets, for $5$ training runs each. The results for the $\operatorname{\ell-ECT}$s are with respect to a simple XGBoost classifier.**
| Model | Cornell | Wisconsin | Texas |
| --- | --- | --- | --- |
| GCN | 45.0 $\pm$ 2.2 % | 44.2 $\pm$ 2.6 % | 47.3 $\pm$ 1.5 % |
| GAT | 44.7 $\pm$ 2.9 % | 48.2 $\pm$ 2.0 % | 51.7 $\pm$ 3.2 % |
| $\operatorname{\ell-ECT}_{1}$ | 66.8 $\pm$ 4.2 % | 81.2 $\pm$ 2.9 % | 74.6 $\pm$ 0.5 % |
| $\operatorname{\ell-ECT}_{2}$ | 67.0 $\pm$ 4.9 % | 76.1 $\pm$ 2.8 % | 73.8 $\pm$ 2.6 % |
| $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ | 67.1 $\pm$ 4.1 % | 78.5 $\pm$ 2.6 % | 74.8 $\pm$ 3.1 % |

The heterophilous graph datasets introduced in Platonov et al. () contain the two multiclass graph datasets Roman Empire and Amazon Ratings on which we validate our method. Again, $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ performs best on both datasets, and outperforms both GCN and GAT (see Tab. [2](#S5.T2)). However, $\operatorname{\ell-ECT}_{1}$ outperforms $\operatorname{\ell-ECT}_{2}$ on Roman Empire, while $\operatorname{\ell-ECT}_{2}$ outperforms $\operatorname{\ell-ECT}_{1}$ on Amazon Ratings. Our interpretation of this finding is that the $1$-hop neighborhoods are particularly informative for Roman Empire, while the $2$-hop neighborhoods are more informative for the Amazon Ratings dataset.

**Table 2: Performance (in accuracy) of different graph learning models across multiple datasets, for $5$ training runs each. The results for the $\operatorname{\ell-ECT}$s are with respect to a simple XGBoost classifier.**
| Model | Roman Empire | Amazon Ratings |
| --- | --- | --- |
| GCN | 73.3 $\pm$ 0.8 % | 42.3 $\pm$ 0.7 % |
| GAT | 76.4 $\pm$ 1.2 % | 44.6 $\pm$ 0.9 % |
| $\operatorname{\ell-ECT}_{1}$ | 80.4 $\pm$ 0.4 % | 48.4 $\pm$ 0.3 % |
| $\operatorname{\ell-ECT}_{2}$ | 78.0 $\pm$ 0.3 % | 49.6 $\pm$ 0.3 % |
| $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ | 81.1 $\pm$ 0.4 % | 49.8 $\pm$ 0.3 % |

The Amazon dataset was first introduced in Shchur et al. () and consists of the two datasets Computers and Photo. While GAT outperforms on Computers, the combination of $\operatorname{\ell-ECT}_{1}$ and $\operatorname{\ell-ECT}_{2}$ outperforms on Photo, see Tab.[3](#S5.T3). However, both of the aforementioned models lead to very similar performance on these two datasets.

**Table 3: Performance (in accuracy) of different graph learning models across multiple datasets, for $5$ training runs each. The results for the $\operatorname{\ell-ECT}$s are with respect to a simple XGBoost classifier.**
| Model | Computers | Photo |
| --- | --- | --- |
| GCN | 91.6 $\pm$ 1.6 % | 93.6 $\pm$ 1.7 % |
| GAT | 92.4 $\pm$ 1.3 % | 94.8 $\pm$ 1.1 % |
| $\operatorname{\ell-ECT}_{1}$ | 89.6 $\pm$ 0.3 % | 94.1 $\pm$ 0.3 % |
| $\operatorname{\ell-ECT}_{2}$ | 90.1 $\pm$ 0.5 % | 94.4 $\pm$ 0.7 % |
| $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ | 92.2 $\pm$ 0.6 % | 94.9 $\pm$ 0.6 % |

For the Actor dataset (Pei et al., ), the $\operatorname{\ell-ECT}_{1}$ model achieves the highest accuracy, outperforming both GCN and GAT. The combination $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ performs slightly worse. $\operatorname{\ell-ECT}_{2}$ performs the lowest on this dataset, indicating that $\operatorname{\ell-ECT}_{1}$ captures more relevant features for the Actor dataset.
The WikipediaNetwork dataset from Rozemberczki et al. () consists of the two node classification tasks Squirrel and Chameleon.
On the Squirrel dataset, both $\operatorname{\ell-ECT}_{1}$ and $\operatorname{\ell-ECT}_{2}$ deliver the best performance. This indicates that the $\operatorname{\ell-ECT}$-based are particularly effective for this dataset, outperforming both GAT and GCN by a significant margin. The combination model $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ also performs well, only slightly lower than the individual $\operatorname{\ell-ECT}$ models.
On the Chameleon dataset, GAT achieves the highest accuracy, outperforming the other models. $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ comes next, followed by $\operatorname{\ell-ECT}_{1}$. The standard GCN model performs the lowest, though the gap between GCN and the $\operatorname{\ell-ECT}$ models is relatively small.

**Table 4: Performance (in accuracy) of different graph learning models across multiple datasets, for $5$ training runs each. The results for the $\operatorname{\ell-ECT}$s are with respect to a simple XGBoost classifier. The Actor dataset is separated visually to indicate it belongs to a different dataset. The maximum accuracy for each dataset is highlighted in bold.**
| Model | Actor | Squirrel | Chameleon |
| --- | --- | --- | --- |
| GCN | 30.7 $\pm$ 2.1 % | 28.9 $\pm$ 1.4 % | 42.8 $\pm$ 1.8 % |
| GAT | 31.1 $\pm$ 1.8 % | 31.8 $\pm$ 1.3 % | 47.3 $\pm$ 1.3 % |
| $\operatorname{\ell-ECT}_{1}$ | 31.4 $\pm$ 1.9 % | 35.6 $\pm$ 0.7 % | 43.46 $\pm$ 1.7 % |
| $\operatorname{\ell-ECT}_{2}$ | 30.1 $\pm$ 1.3 % | 35.6 $\pm$ 0.8 % | 40.44 $\pm$ 1.5 % |
| $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ | 30.9 $\pm$ 0.7 % | 35.3 $\pm$ 1.5 % | 43.90 $\pm$ 0.7 % |

### 5.2 Learning spatial alignment

In the following, we use the approach described in Sec. [4](#S4) in order to learn the spatial alignment of two data spaces by re-rotating one into the other. We start by showing that synthetic data which only differs up to a rotation can be re-aligned using the given method. Moreover, we show that this alignment is stable with respect to noise, making it a robust measure for the comparison of local neighborhoods in data.
In comparison to other spatial alignment methods like the iterative closest point algorithm, ours does *not* necessitate the computation of all pairwise distances between points in the respective spaces. The latter is often a computational bottleneck, especially for large datasets, thus positioning our method for spatial alignment as a computationally more efficient method in practice.
We observe that this approach is also capable of aligning embedded graph data, making it particularly useful for dealing with *geometric graphs*, constituting a highly-efficient alternative to more involved machine-learning models such as geometric GNNs (Joshi et al., ).
For a discussion of spatial alignment in the context of high-dimensional point cloud data, please refer to App. [A.2.2](#A1.SS2.SSS2).

For the subsequent learning problem, let us assume that we are given two point clouds $X,Y\subset\mathbb{R}^{n}$.
In light of Sec. [4](#S4), the metric properties of $d_{\operatorname{ECT}}$ ensure that $d_{\operatorname{ECT}}(X,Y)=0$ if $X$ and $Y$ only differ up to a rotation. We therefore approximate $d_{\operatorname{ECT}}(X,Y)$ via the learning problem

$$ $\displaystyle\min_{\rho\in SO(n)}\left\lVert\overline{\operatorname{ECT}}(X)_{(m,l)}-\overline{\operatorname{ECT}}(\rho Y)_{(m,l)}\right\rVert_{2}^{2}$ (9) $$

for a choice of directions $v_{1},\dots,v_{m}\in S^{n-1}$ and filtration steps $t_{1},\dots,t_{l}\in\mathbb{R}$.
As explained in Sec. [4](#S4), the $\operatorname{ECT}$ approximations are given by vectors, making it feasible to approach the above learning problem by a general-purpose gradient-based learning algorithm. The advantage of this formulation is that it yields both the rotation-invariant loss and the rotation that leads to this minimum loss, where the latter is given by the parameters of the learner.

##### Low-dimensional data

We now approximate the optimization problem in Eq. [9](#S5.E9) to show that we can learn a spatial alignment of two given data spaces, while the distance between $\operatorname{ECT}$s of non-aligned spaces that only differ up to a rotation will in fact generally be high. Our first example is given by a wedged sphere, meaning two $2$-dimensional spheres which are concatenated at a gluing point (see Fig. [3](#A1.F3)). We begin by sampling $2000$ points from such a wedged sphere, and compare the squared L2 loss between the $\operatorname{ECT}$s of this sample and a rotation of the same data space. We repeat this procedure $500$ times, where at each step both the sample of the wedged sphere and the rotation matrix which yields the rotated version of the same space are randomly sampled.
We notice that the L2 losses between the non-aligned spaces are high (with a median of around $19$), whereas the L2 losses of the non-aligned spaces are significantly lower, with a median loss close to zero (see Fig. [7](#A1.F7) in the appendix for more details). Moreover, we see that the $\operatorname{ECT}$ of the same space significantly changes when the coordinate system is changed, which undermines the necessity of a rotation-invariant metric for a comparison of $\operatorname{ECT}$s that we introduced in Sec. [4](#S4).
We conclude that an alignment of the $\operatorname{ECT}$s of the two underlying data spaces in fact leads to an alignment of the data spaces itself, as promised by the theoretical results in Sec. [4](#S4).

##### Robustness with respect to outliers and noise

Fig. [4](#A1.F4) and Fig. [5](#A1.F5) in the appendix show that the spatial alignment of wedged spheres still works in the presence of outliers and noise.
This property is an important feature when dealing with real-world data, which is often noisy, and enables us to align spaces that only approximately differ up to a rotation.
By contrast, the Hausdorff distance which is a widely used metric between point clouds is (by definition) highly sensitive to outliers. We therefore conclude that the proposed metric based on $\operatorname{ECT}$s is a robust metric to compare point clouds of potentially different cardinalities.

Figure: Figure 1: A comparison of the Hausdorff distances of aligned graphs. The black dots represents the Hausdorff distance between the original graph and a randomly rotated version of itself.
Refer to caption: /html/2410.02622/assets/Data/Images/rotated_graphs.png

##### Geometric graphs

As a final example of the utility of our method, we face the problem of graph re-alignment. Recall that a $k$-star graph is given by a tree with one internal node and $k$ leaves (see Fig. [1](#S5.F1) for examples of different $k$-star graphs). In order to obtain an embedded graph, we assign a 2D vector to every node in the graph in such a way that the assigned node vectors are equidistant to each other. Subsequently, the embedded graph is perturbed by a random 2D rotation, and finally the rotation matrix is learned by using the $\operatorname{ECT}$-based metric defined in Sec. [4](#S4). We measure the similarity via the Hausdorff distance between the original graph and its re-rotated version. We repeated the learning procedure for $200$ times with the same initialization of both the graph and the respective rotation matrix. The results are shown in Fig. [1](#S5.F1). We see that the realignment leads to small Hausdorff distances with medians close to zero, whereas the Hausdorff distance between the original graph and its random perturbation is significantly higher.

## 6 Discussion

In this work, we introduced the Local Euler Characteristic Transform ($\operatorname{\ell-ECT}$), providing a novel approach to graph representation learning that preserves local structural information without relying on aggregation. Our method addresses fundamental limitations in message-passing neural networks, particularly in tasks where aggregating neighboring information is suboptimal, such as in graphs with heterophily. By retaining critical local details, $\operatorname{\ell-ECT}$s enable more nuanced and expressive representations, offering significant advantages in node classification tasks and beyond.

One key strength of our approach is its model-agnostic nature, allowing it to be paired with interpretable machine learning models. This is particularly useful in domains such as healthcare, finance, and legal applications, where regulatory frameworks demand high levels of transparency and interpretability that are often difficult to achieve with black-box neural networks. By leveraging $\operatorname{\ell-ECT}$s, we can fulfill these regulatory requirements while maintaining the expressiveness needed for accurate representation learning.

Beyond graph representation learning, the framework of $\operatorname{\ell-ECT}$s opens the door for applications in other areas where local structure is critical, such as in point clouds, 3D shape analysis, and biological networks. Additionally, the ability to generalize $\operatorname{\ell-ECT}$s to higher-dimensional simplicial complexes suggests future extensions of this work into the realm of simplicial learning, providing a powerful tool for analyzing higher-order data in a computationally feasible way.
Future work could explore more efficient algorithms for computing $\operatorname{\ell-ECT}$s at scale, as well
as hybrid approaches that balance local and global information more effectively. In particular, the
investigation of sampling methods appears to be a promising direction for this purpose.

## Appendix A Appendix

### A.1 Proofs

##### Proof of Theorem 1 :

In the setting of Sec.[4](#S4),
the worst case convergence of
$\overline{\operatorname{ECT}}(X)_{(m,l)}$ to the true quantity $\operatorname{ECT}(X)$ is $\mathcal{O}((\frac{\log m}{m})^{1/(n-1)}\frac{1}{l})$.

###### Proof.

The total surface area of $S^{n-1}$ is given by $A(S^{n-1})=\frac{2\pi^{n/2}}{\Gamma(n/2)}$.
A spherical cap on $S^{n-1}$ is the set of points on the sphere that lie within an angular distance $\delta$ from a given point, and the area of such a spherical cap can for large $m$ be approximated as $A_{\text{cap}}\approx c_{n}\delta^{n-1}$ with $c_{n}$ being a constant. What we would like to achieve is $A_{\text{cap}}\approx\frac{A(S^{n-1})}{m}$, leading to $\delta\approx c_{n}^{\prime}(\frac{1}{m})^{1/(n-1)}$ for a constant $c_{n}^{\prime}$. However, the discrepancy in the uniform sampling on the sphere introduces another logarithmic term, leading to $\delta\approx c_{n}^{\prime\prime}(\frac{logm}{m})^{1/(n-1)}$, see Beck (). The convergence speed with respect to the Euclidean direction is $\mathcal{O}(\frac{1}{l})$ since no sampling is involved here. Together, this proves the statement.
∎

###### Proof.

##### Proof of Theorem 2 :

Let $\mathcal{G}$ be a featured graph and let $\{\operatorname{\ell-ECT}_{1}(x;\mathcal{G})\}_{x}$ be the collection of local $\operatorname{ECT}$s with respect to the $1$-hop neighborhoods in $\mathcal{G}$. Then the collection $\{\operatorname{\ell-ECT}_{1}(x;\mathcal{G})\}_{x}$ provides the necessary information for performing a single message-passing step on $\mathcal{G}$.

###### Proof.

By the remark before, we may assume that the natural embedding of $\mathcal{G}$ into $\mathbb{R}^{n}$ is a graph isomorphism.
Then by the invertibility theorem, the $1$-hop neighborhood of a point $x$ in the embedding of $\mathcal{G}$ can be reconstructed from $\operatorname{\ell-ECT}_{1}(x;\mathcal{G})$. Therefore, the feature vectors of $x$ and its $1$-hop neighbors can be deduced from $\operatorname{\ell-ECT}_{1}(x;\mathcal{G})$, which is the only non-learnable information one needs to perform a message passing step.
∎

###### Proof.

##### Proof of Theorem 3 :

Two featured graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are isomorphic if and only if $\operatorname{ECT}(\mathcal{G}_{1})=\operatorname{ECT}(\mathcal{G}_{2})$.

###### Proof.

When two featured graphs are isomorphic in the sense of Def.[2](#Thmdefinition2), their respective Euclidean embeddings produce equal $\operatorname{ECT}$s, by construction. On the other hand, let us assume that $\operatorname{ECT}(\mathcal{G}_{1})=\operatorname{ECT}(\mathcal{G}_{2})$. Then by the invertibility theorem, the Euclidean embeddings of $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are equal. Therefore, the only information that may tell apart the two graphs are their node labels, but this means that $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are isomorphic.
∎

###### Proof.

##### Proof of Theorem 4 :

$d_{\operatorname{ECT}}$ is a metric on the collection of rotation classes of finite simplicial complexes embedded in $\mathbb{R}^{n}$.

###### Proof.

$d_{\operatorname{ECT}}(X,X)=0$ holds for $\rho$ being the identity. Now assume that $d_{\operatorname{ECT}}(X,Y)=0$. Then there exists $\rho\in SO(n)$ with $\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho Y))\right\rVert_{\infty}=0$. As $\left\lVert\bullet\right\rVert_{\infty}$ is a norm, it follows that $\operatorname{ECT}(X)=\operatorname{ECT}(\rho Y)$, and by the invertibility theorem we obtain $X=\rho Y$. This shows the first property of a metric (note that positivity follows from $\left\lVert\bullet\right\rVert_{\infty}$). For symmetry, note that $\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho Y))\right\rVert_{\infty}=\left\lVert(\operatorname{ECT}(\rho^{-1}X)-\operatorname{ECT}(Y))\right\rVert_{\infty}$,
since rotations are invertible.
For the triangle inequality, let $Z$ be another finite simplicial complex. We then have

$$ $\displaystyle d_{\operatorname{ECT}}(X,Z)$ $\displaystyle=\inf_{\rho\in SO(n)}\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho Z))\right\rVert_{\infty}$ $\displaystyle\leq\inf_{\rho,\rho^{\prime}\in SO(n)}\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho^{\prime}Y))\right\rVert_{\infty}+\left\lVert(\operatorname{ECT}(\rho^{\prime}Y)-\operatorname{ECT}(\rho Z))\right\rVert_{\infty}$ $\displaystyle=\inf_{\rho,\rho^{\prime}\in SO(n)}\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho^{\prime}Y))\right\rVert_{\infty}+\left\lVert(\operatorname{ECT}(Y)-\operatorname{ECT}((\rho^{\prime})^{-1}\rho Z))\right\rVert_{\infty}$ $\displaystyle=\inf_{\rho\in SO(n)}\left\lVert(\operatorname{ECT}(X)-\operatorname{ECT}(\rho Y))\right\rVert_{\infty}+\inf_{\rho\in SO(n)}\left\lVert(\operatorname{ECT}(Y)-\operatorname{ECT}(\rho Z))\right\rVert_{\infty}$ $\displaystyle=d_{\operatorname{ECT}}(X,Y)+d_{\operatorname{ECT}}(Y,Z)$ $$

∎

###### Proof.

### A.2 Additional results

As another node classification task, we provide results for the well-known Planetoid datasets from Yang et al. () which consists of Cora, CiteSeer and PubMed. We trained all models using a random 75/25 split of the data. The results are shown in Tab.[5](#A1.T5). Although GCN and GAT performs slightly better for Cora and CiteSeer, the gap is surprisingly small. In the case of PubMed the $\operatorname{\ell-ECT}$-based models even outperform both GCN and GAT. The findings suggest that the expressivity of $\operatorname{\ell-ECT}$s which we formally established in Sec. [4](#S4) is also of practical use, giving rise to an alternative way of dealing with graph data that is not restricted by the underlying model architecture and therefore allows for interpretability.

**Table 5: Performance (in accuracy) of different graph learning models across multiple datasets, for $5$ training runs each. The results for the $\operatorname{\ell-ECT}$s are with respect to a simple XGBoost classifier.**
| Model | Cora | CiteSeer | PubMed |
| --- | --- | --- | --- |
| GCN | 88.1 $\pm$ 1.2 % | 74.6 $\pm$ 1.5 % | 85.3 $\pm$ 4.7 % |
| GAT | 88.3 $\pm$ 1.1 % | 75.3 $\pm$ 1.5 % | 85.7 $\pm$ 4.2 % |
| $\operatorname{\ell-ECT}_{1}$ | 87.6 $\pm$ 0.6 % | 72.1 $\pm$ 0.6 % | 90.2 $\pm$ 0.5 % |
| $\operatorname{\ell-ECT}_{2}$ | 87.2 $\pm$ 0.7 % | 72.3 $\pm$ 0.8 % | 90.3 $\pm$ 0.5 % |
| $\operatorname{\ell-ECT}_{1}+\operatorname{\ell-ECT}_{2}$ | 87.8 $\pm$ 0.6 % | 72.5 $\pm$ 0.7 % | 90.3 $\pm$ 0.5 % |

#### A.2.1 Ablation on directions and interpretability

Coming back to our approximation of $\operatorname{ECT}(X)$ via $\overline{\operatorname{ECT}}(X)_{(m,l)}:=\operatorname{ECT}(X)_{|\{v_{1},\dots,v_{m}\}\times\{t_{1},\dots,t_{l}\}}$
for uniformly distributed directions $v_{1},\dots,v_{m}\in S^{n-1}$ and filtration steps $t_{1},\dots,t_{l}\in\mathbb{R}$, we notice that the $(l\cdot(j-1)+1)$-th till $(l\cdot j)$-th entries of $\overline{\operatorname{ECT}}(X)_{(m,l)}$ correspond to the direction $v_{j}$.
The latter gives us the opportunity to get a deeper spatial understanding of how the model predicts its outcome, by analysing its feature importances (which are available for tree-based algorithms like e.g. XGBoost).
Therefore, our approach enables us to analyse which features (i.e. directions) of the underlying ECT vector are most important.
In practice, we often observe that a small number of features admits high feature imoprtance with respect to the corresponding model, see Fig.[2](#A1.F2). This raises the question if we may use only a smaller random collection of features and still get reasonable results. We therefore ran experiments for a collection of datasets for a varying number of randomly sampled entries of the $\operatorname{\ell-ECT}_{1}$ vector see Tab.[6](#A1.T6) for the results. Here, 4096 corresponds to the whole vector. We observe that for certain tasks like e.g. Coauthor CS, Coauthor Physics and Amazon Ratings the performance of the model only slightly changes when using only a small portion of the $\operatorname{\ell-ECT}_{1}$ vector. In light of the results in Curry et al. (), this observation is not entirely surprising: one main claim therein is that the $\operatorname{ECT}$ can be determined using only a small number of directions.

Figure: Figure 2: Feature importances of an XGBoost model for the Coauthor Phyiscs dataset (using $\operatorname{\ell-ECT}_{1}$). Only a small number of features admit high importance scores.
Refer to caption: /html/2410.02622/assets/Data/Images/feature_importances.png

**Table 6: Mean accuracy results (5 runs each) for different node classification tasks, and a varying number of randomly sampled entries of the respective $\operatorname{\ell-ECT}_{1}$ vectors.**
| Dataset | 50 | 100 | 500 | 1000 | 4096 |
| --- | --- | --- | --- | --- | --- |
| WikiCS | 69.2% | 70.5% | 71.3% | 72.7% | 74.6% |
| Coauthor CS | 92.3% | 92.4% | 92.5% | 92.6% | 92.6% |
| Coauthor Physics | 95.6% | 95.6% | 95.8% | 95.9% | 96.1% |
| Roman Empire | 73.7% | 75.8% | 78.3% | 79.7% | 80.4% |
| Amazon Ratings | 47.9% | 48.2% | 48.4% | 48.2% | 48.4% |

Figure: Figure 3: A comparison of two wedged spheres with one being rotated around the wedge point and the points being perturbed by Gaussian noise (left) and the learned re-rotated sphere that is aligned with the original data (right).
Refer to caption: /html/2410.02622/assets/x1.png

Figure: Figure 4: A comparison of two wedged spheres with one being rotated around the wedge point and added $200$ outliers (left) and the learned re-rotated sphere that is aligned with the original data (right).
Refer to caption: /html/2410.02622/assets/x3.png

Figure: Figure 5: A comparison of two wedged spheres with one being rotated around the wedge point and the points being perturbed by Gaussian noise (left) and the learned re-rotated sphere that is aligned with the original data (right).
Refer to caption: /html/2410.02622/assets/x5.png

#### A.2.2 Spatial Alignment of High-Dimensional Data

Following our previous observations that $d_{\operatorname{ECT}}$ enables us to align two spaces, we now use it to investigate its effect on high-dimensional data. We start this discussion with the well-known MNIST benchmark dataset. We first represent each (gray-scale) image in the dataset as a $784$-dimensional vector, by flattening the image. In this way, we obtain a high-dimensional point cloud corresponding to the dataset. Subsequently, we sample $300$ points of digits of ‘$1$’ and calculate the pairwise distances of their respective $\operatorname{\ell-ECT}$ (with respect to the whole point cloud), for $k=10$. Finally, we calculate the pairwise distances of the respective aligned $\operatorname{\ell-ECT}$s (by using the approach of Eq. [9](#S5.E9) and for $k=10$). The results are shown in Fig. [6](#A1.F6). We see that the aligned $\operatorname{\ell-ECT}$s have a significantly lower squared L2 distance (with a median of $\approx 112$) than the non-aligned ones (with a median of $\approx 224$), showcasing that rotations cause dissimilarity between small neighborhoods of points, in many cases.

Figure: Figure 6: A comparison of the squared L2 distances of $\operatorname{\ell-ECT}$s of aligned and non-aligned MNIST digits of ‘1’, respectively.

#### A.2.3 Spatial alignment of wedged spheres

Figure: Figure 7: A comparison of the squared L2 distances of the respective $\operatorname{ECT}$s of aligned and non-aligned wedged spheres, respectively.

Fig.[7](#A1.F7) shows that the L2 losses between the non-aligned spaces are high (with a median of around $19$), whereas the L2 losses of the non-aligned spaces are significantly lower, with a median loss close to zero. We therefore see that the $\operatorname{ECT}$ of the same space significantly changes when the coordinate system is changed, which undermines the necessity of a rotation-invariant metric for a comparison of $\operatorname{ECT}$s that we introduced in Sec. [4](#S4).

##### Disclaimer

Certain aspects of this work have been improved with the help of OpenAI ().

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: Would it be possible to include experimental results for the other datasets offered in “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?” by Platonov et. al. or an argument as to why this is done?
soundness: 3
strengths: The paper presents the Local Euler Characteristic Transform (L-ECT) as an extension of the traditional Euler Characteristic Transform, enabling a lossless representation of local graph structures and addressing key limitations of Graph Neural Networks (GNNs) such as oversmoothing and loss of local detail in high heterophily graphs. This novel transformation preserves intricate topological information, allowing for more nuanced node representations by capturing both structural and spatial data and offering an alternative to GNN message-passing frameworks. Additionally, the authors introduce a rotation-invariant metric that enables robust spatial alignment of data in Euclidean space, enhancing the method’s applicability in graph-structured data and increasing resilience to coordinate transformations. Empirical results underscore L-ECT’s effectiveness, showing superior performance over standard GNNs in high-heterophily datasets like WebKB, Roman Empire, and Amazon Ratings. Furthermore, L-ECT’s model-agnostic nature facilitates integration with interpretable machine learning models, such as XGBoost, making it ideal for use in regulated fields like healthcare and finance where transparency is paramount. Beyond graph representation, L-ECT extends to point clouds and other high-dimensional data, proving robust to noise and outliers and enabling efficient spatial alignment without the need for exhaustive pairwise distance computations.

The methods section is detailed yet readable, presenting L-ECT’s mathematical foundation and integrating a rotation-invariant metric for spatial alignment, which adds to the paper’s originality. While the experiments section is robust and results are well-presented through tables and figures, additional visual aids could further clarify data characteristics and enhance accessibility.

the discussion on the limitations of the approaches proposed in the paper is appreciated
summary: The paper introduces the Local Euler Characteristic Transform (L-ECT), an extension of the Euler Characteristic Transform (ECT) designed for graph representation learning. Unlike traditional Graph Neural Networks (GNNs), which can obscure local details through node aggregation, the L-ECT maintains local structural data, thus enhancing interpretability and performance, especially in heterogeneous (high heterophily) graphs. By capturing spatial and structural characteristics of local neighborhoods, the L-ECT provides a rotation-invariant metric for data alignment, showcasing improved performance over GNNs in node classification tasks. The method’s compatibility with machine learning models enables use cases beyond standard GNN architectures, offering more accessible and interpretable models, such as tree-based classifiers. Empirical results demonstrate that L-ECT outperforms GNNs in heterogeneous datasets and facilitates robust spatial alignment in both synthetic and high-dimensional data. This research suggests future exploration into scaling L-ECT and integrating global and local information in complex graph structures.
weaknesses: 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 

Including a more robust and explicit comparison to related works, which also addresses the novelty of the work being proposed, would be appreciated.

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. 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. 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. The approach’s scalability is further limited by sampling trade-offs, as its accuracy depends on carefully chosen parameters, such as direction and filtration steps, which challenge fidelity and computational efficiency at scale. 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.

The authors should include comparison other works which construct topological representations of graphs and graphs neighborhoods and include reference to those related methods such as “graph filtration learning” by Hofer et. al. and other approaches as discussed in survey works such as  “A Survey of Topological Machine Learning Methods” by Hensel et. al.

The authors provide comparative experimental analysis to a number of datasets. It may be misleading, however, to not include other models as discussed in “A critical look at the evaluation of GNNs under heterophily: Are we really making progress?” by Platonov et. al.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: See weaknesses.
soundness: 3
strengths: 1. Innovative Use of Euler Characteristic Transform: Employing the ECT to enhance graph representation learning, especially in settings with heterophily, is a novel and interesting approach.

2. Solid Theoretical Foundation: The work is thorough, with strong theoretical results that effectively support the proposed method.
summary: This paper introduces the Local Euler Characteristic Transform ($l$-ECT), an extension of the Euler Characteristic Transform (ECT) designed to enhance expressivity and interpretability in graph representation learning. It provides a lossless representation of local neighborhoods and addresses key limitations in GNNs by preserving nuanced local structures while maintaining global interpretability. Their method demonstrates superior performance over standard GNNs on node classification tasks, particularly in graphs with heterophily.
weaknesses: Missing Important Related Works & Limited Experimental Comparisons: The quantitative experiments focus mainly on node classification tasks in heterophilic graphs but compare the proposed method only with basic models like GCN and GAT. While the authors acknowledge related works on GNNs designed for heterophily in Section 3, the coverage is still limited. It is suggested that the authors include more related works such as [1-5] and select appropriate GNNs for experimental comparison to strengthen the validation of their method.

[1] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

[2] Graph Neural Networks with Heterophily

[3] Predicting Global Label Relationship Matrix for Graph Neural Networks under Heterophily

[4] ES-GNN: Generalizing Graph Neural Networks Beyond Homophily With Edge Splitting

[5] GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily

---

confidence: 5
contribution: 2
initial_rating: 5
presentation: 4
questions: See weaknesess.
soundness: 3
strengths: 1. **Novel l-ECT Framework**: Extending the Euler Characteristic Transform to capture local graph details in embedded simplicial complexes is impactful, with theoretical insights enhancing its expressivity, especially for featured graphs.

2. **Extracting  Key Information from Node Neighborhoods from Attribute Space**: The l-ECT enables to obtain node neighborhood information by effectively utilizing the information from attribute space.

3. **Experimental Validation**: The l-ECT consistently outperforms traditional GNNs in node classification tasks, particularly in high-heterophily settings, highlighting its interpretability and effectiveness.

4. **Presentation:** The presentation is very good.
summary: The authors introduce a new topological feature extraction methods, Local Euler Characteristic Transform (l-ECT), extending the Euler Characteristic Transform (ECT) to provide a lossless, interpretable representation of local graph neighborhoods, addressing limitations in traditional Graph Neural Networks (GNNs). This novel approach improves performance in node classification tasks, especially in heterophilous graphs, by preserving both local and global structural details.
weaknesses: 1. **Limited Applicability:** The proposed approach is constrained to graphs with node feature vectors in $\mathbb{R}^n$, limiting its applicability to datasets that fit this specific structure.

2. **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.

3. **Feasibility in High Dimensions:** As the dimension $n$ of the feature space increases, the number $m$ of representative vectors on $S^{n-1}$ must grow nearly exponentially. Furthermore, the feature vector range impacts the number of intervals {$t_i$} 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.

4. **Theoretical Contributions vs. Practical Applications:** While the rotation-invariant metric is mathematically appealing, it may lack practical relevance since it relies on the infimum over all rotations. Also, the discussion of graph isomorphism seems tangential, as Definition 2 is highly restrictive, applicable only to isomorphic graphs with identical feature vectors.

5. **Experimental Results:** The presented results are uninformative and potentially misleading. The models used, GCN and GAT, are older and are known to perform poorly in heterophilic settings. The authors should consider comparing their approach with newer GNN models that perform well on heterophilic datasets and include more homophilic datasets (other than Computers and Photo) to provide a comprehensive performance assessment. Also, exploring the integration of $l$-ECT vectors with a more recent GNN model may yield interesting insights into performance enhancement.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: See weaknesses.
soundness: 1
strengths: Using local Euler characteristic transform for graph representation is novel to me.
summary: The paper proposes a local Euler characteristic transform for enhancing feature representation for graph learning. This approach addresses key limitations in GNNs by preserving nuanced local structures while maintaining global interpretability.
weaknesses: 1. 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. 
2. Related to 1. The author should be more specific on ``embedding'', whether it is metrical embedding, differential embedding, or topological embedding (or something else?). 
3. 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. 
4. 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. 
5. The compared benchmarks are very limited (only GCN and GAT). From my own experience, the results are not very impressive, e.g., for the Actor, Squirrel, and Chameleon datasets, there are more recent benchmarks (e.g., ACM-GCN) whose performance is at least 5%-10% higher than those reported by the authors. 
6. Ablation study is missing. It is hard to assess whether l-ECTs play an important role in the reults shown.

Meta-review: The paper introduces the Local Euler Characteristic Transform (l-ECT), an extension of the Euler Characteristic Transform (ECT) aimed at enhancing expressivity and interpretability in graph representation learning. Unlike traditional GNNs, which may lose important local details during aggregation, l-ECT provides a lossless representation of local neighborhoods, preserving nuanced structures while maintaining global interpretability. Additionally, the authors propose a rotation-invariant metric based on l-ECT for spatial alignment of data. Experimental results show that l-ECT outperforms standard GNNs, particularly in high-heterophily node classification tasks.

### Strengths:

1. The use of the ECT to enhance graph representation learning, especially in high-heterophily settings, is both novel and compelling. The authors provide solid theoretical backing to support the proposed method.

2. The l-ECT consistently outperforms traditional GNNs in node classification tasks, particularly in high-heterophily environments, demonstrating its interpretability and effectiveness.

### Weaknesses:

1. The technical sections, including the proofs, are poorly presented, making it difficult to assess the correctness of the results.

2. The numerical results are not particularly striking, and the experimental design could be strengthened to more convincingly demonstrate that the approach advances the state of the art.

### Overall:

This paper presents an interesting and novel idea by applying l-ECT to graph learning. However, the clarity of the technical sections is insufficient, which hampers the ability to evaluate the correctness of the method. Additionally, the experimental results are not compelling enough to clearly show the method’s superiority. As a result, I recommend borderline rejection, but strongly encourage the authors to address the reviewers' suggestions and revise the paper accordingly.

Decision: Reject