LEAP: Local ECT-Based Learnable Positional Encodings for Graphs

This paper introduces LEAP, a novel end-to-end trainable local structural positional encoding for graphs that leverages differentiable approximations of the Euler Characteristic Transform to overcome the limitations of standard message-passing neural networks by effectively capturing topological features.

The Gist

Imagine you are trying to teach a computer how to understand a social network. In this network, people are nodes, and friendships are lines connecting them.

For a long time, computers have tried to understand these networks using a method called "Message Passing." Think of this like a game of Telephone. A person (node) listens to their immediate friends, summarizes what they heard, and passes that summary to their own friends. The problem? If the network is huge or complex, the message gets garbled, or the computer gets confused about who is who. It's like trying to understand a whole city just by asking one person what their neighbor is doing; you miss the big picture and the unique details.

To fix this, researchers usually give the computer a "map" or a "name tag" (called a Positional Encoding) so it knows where each person sits in the network. But most existing maps are either too simple (just counting neighbors) or too rigid (based on fixed mathematical rules that can't learn).

Enter LEAP: The "Topological Detective"

The paper introduces a new tool called LEAP (Local ECT-based Learnable Positional Encodings). Here is how it works, using a simple analogy:

1. The Problem with Standard Maps

Imagine you are looking at a group of friends.

• Standard Maps (like LaPE or RWPE): These might just tell you, "This person is 3 steps away from the center" or "This person has 5 friends." It's useful, but it doesn't capture the shape of the group. Is the group a tight circle? A long line? A star?
• The Limitation: If two groups look different but have the same number of friends, standard maps might think they are identical.

2. The LEAP Solution: Scanning with a "Flashlight"

LEAP uses a concept from mathematics called the Euler Characteristic Transform (ECT). Imagine you have a flashlight that can shine from any angle.

• The Old Way: You shine the light on the group of friends and count how many people are visible.
• The LEAP Way: You shine the light from many different angles (directions). As you rotate the light, you watch how the "shadow" or the "silhouette" of the group changes.
  • If the group is a circle, the shadow changes smoothly.
  • If the group is a star, the shadow changes in sharp, jagged ways.
  • If the group has a hole in the middle, the shadow behaves differently than if it's solid.

By recording these changes from all angles, LEAP creates a unique "fingerprint" for the local neighborhood of every single person in the network. This fingerprint captures the shape and structure of the group, not just the number of people.

3. "Learnable" Means It Gets Smarter

The "L" in LEAP stands for Learnable.

• Old Methods: The flashlight angles were fixed. The computer had to use the same angles for every problem, even if some angles were useless.
• LEAP: The computer is allowed to learn which angles are best. During training, it figures out, "Hey, shining the light from the left and top gives us the most useful information for this specific task, so let's focus on those." It adapts its "flashlight strategy" to the specific problem it's solving.

Why is this a big deal?

The researchers tested LEAP on a few scenarios:

1. The "Shape-Only" Test: They created a fake world where the "people" had no personalities (no data), only their connections mattered. Standard computers failed miserably here because they relied on the personalities. LEAP, however, looked at the shape of the connections and got 100% accuracy. It proved that LEAP can understand structure even when there is no other information to go on.
2. Real-World Tests: They tested it on real datasets (like chemical molecules or social networks). In almost every case, adding LEAP to existing computer models made them smarter and more accurate.

The Bottom Line

Think of LEAP as giving a graph neural network a pair of 3D glasses and a smart camera.

• Instead of just seeing a flat list of connections, the network can now "see" the 3D shape and topology of the data.
• It learns to take photos from the best angles to understand the structure.
• It helps the computer distinguish between a "crowded party" and a "long line of people," even if both have the same number of people.

This allows AI to solve complex problems involving networks (like drug discovery or social analysis) much more effectively than before, by understanding not just who is connected, but how they are connected in space.

Technical Summary

1. Problem Statement

Graph Neural Networks (GNNs), particularly Message Passing Neural Networks (MPNNs), face significant theoretical and practical limitations:

• Signal Loss: MPNNs struggle with graphs of high diameter, leading to signal dilution (oversquashing).
• Limited Expressivity: They often fail to distinguish non-isomorphic graphs or capture complex substructures (e.g., subgraph counting).
• Lack of Structural Awareness: Standard MPNNs rely heavily on node features and may fail when node features are uninformative or non-existent (non-attributed graphs).
• Limitations of Existing PEs: Current Positional Encodings (PEs) like Random Walk PE (RWPE) or Laplacian PE (LaPE) are often static, non-learnable, or rely solely on either geometric or topological aspects, limiting their expressivity.

The paper aims to bridge the gap between geometry and topology by introducing a learnable, local structural positional encoding that can be trained end-to-end within deep learning pipelines.

2. Methodology: LEAP

The authors propose LEAP (Local ECT-based Learnable Positional Encodings), a novel PE that leverages the Euler Characteristic Transform (ECT).

Core Concepts

• Euler Characteristic Transform (ECT): A topological invariant that characterizes shapes by tracking the Euler characteristic (nodes minus edges) across a sequence of subgraphs generated by projecting the graph onto different directions ($\theta$).
• Differentiable ECT (DECT): Since the standard ECT involves non-differentiable indicator functions, the authors use a sigmoid approximation to make it differentiable, allowing for gradient-based optimization.
• Local ECT ($\ell$-ECT): Instead of computing the ECT for the entire graph (global), LEAP computes it on the $m$-hop neighborhood of each node $v$. This provides a local structural signature.

LEAP Algorithm

For a given node $v$ in a featured graph $(G, x)$:

1. Subgraph Extraction: Select the $m$-hop neighborhood $N_m(v, G)$.
2. Feature Normalization: Mean-center the node features within the neighborhood and normalize them to the unit sphere ($S^{d-1}$). This ensures invariance to scaling.
3. ECT Computation: Compute the Differentiable ECT matrix $M \in \mathbb{R}^{|\Theta| \times |T|}$, where $\Theta$ is a set of direction vectors and $T$ is a set of thresholds. The entry $(i, j)$ represents the DECT value at direction $\theta_i$ and threshold $t_j$.
4. Projection: A learnable projection function $\phi$ maps the matrix $M$ to a $k$-dimensional vector $PE(v)$.

Projection Strategies

The paper evaluates five strategies to project the ECT matrix into a vector:

1. Linear Projection: Flattening the matrix and applying a linear layer (not permutation invariant).
2. 1D Convolutions: Treating the ECT as a time series across thresholds.
3. DeepSets: Aggregating ECCs (Euler Characteristic Curves) from different directions using a permutation-invariant set function.
4. Attention: Using a Transformer encoder with a single head to process the set of ECCs.
5. Attention with PE: Concatenating direction vectors with ECCs before attention to incorporate directional information.

Key Innovation: Unlike previous static uses of $\ell$-ECT, LEAP allows the direction vectors ($\Theta$) to be randomly initialized and learned during training, optimizing the transform specifically for the task at hand.

3. Key Contributions

1. Novel Learnable PE: Introduction of LEAP, the first end-to-end trainable local structural PE based on the $\ell$-ECT, combining geometric and topological information.
2. Feature Independence: Demonstration that LEAP can capture structural differences even when node features are non-informative or random, enabling learning on non-attributed graphs.
3. Learnable Directions: The proposal to optimize the direction vectors $\Theta$ during training, which empirically outperforms fixed-direction approaches.
4. Theoretical Grounding: Leveraging the injectivity of the ECT on geometric graphs to argue that LEAP captures more structural information than standard MPNNs.

4. Experimental Results

The authors evaluated LEAP on synthetic and real-world datasets (TU Benchmark, Alchemy, HIV).

• Synthetic Structural Task: On a dataset of 40,000 graphs where classification depended only on edge count (with random node features), LEAP achieved 100% accuracy. Standard GCN and GAT models failed (approx. 70%), proving LEAP's ability to extract pure topological features.
• Real-World Classification (TU Benchmark):
  • LEAP consistently achieved the best or second-best performance across various architectures (GCN, GAT, GIN, and a non-MPNN "NoMP" transformer).
  • On the Letter-H, Letter-M, and Letter-L datasets, LEAP provided massive gains (e.g., +96.2% improvement over the worst baseline on Letter-H).
  • Learned vs. Fixed: In most cases (especially with GCN and NoMP), learning the directions (LEAP-L) outperformed fixed directions (LEAP-F).
• Large-Scale Datasets:
  • Alchemy: LEAP with learned directions significantly outperformed all baselines in regression tasks ($R^2$ score).
  • HIV: While LaPE (global) performed best individually, the concatenation of LaPE and LEAP yielded the best overall results, suggesting that local (LEAP) and global (LaPE) encodings are complementary.
• Ablation Studies:
  • Locality: 1-hop neighborhoods were sufficient; increasing to 2-hop did not improve performance and sometimes degraded it.
  • Dimension: LEAP remained robust across embedding dimensions (2, 5, 10, 20).
  • Hyperparameters: The method was robust to variations in the number of directions and smoothing parameters.

5. Significance and Future Work

• Topological Deep Learning: LEAP advances the field of topological deep learning by making a powerful topological invariant (ECT) differentiable and trainable within standard GNNs.
• Complementarity: The results suggest that LEAP is particularly effective for architectures relying on global attention (like Transformers) where local structural information is missing. It complements global PEs like LaPE.
• Limitations:
  • Requires node features (though these can be learned).
  • Relies on a differentiable approximation of the ECT, meaning theoretical guarantees of exact ECT injectivity may not fully hold.
  • Introduces more hyperparameters (directions, thresholds, smoothing) compared to standard PEs.
• Future Directions: Formalizing theoretical expressivity, making the ECT step fully differentiable (learning thresholds), and extending LEAP to higher-order structures like simplicial complexes.

In conclusion, LEAP represents a significant step forward in graph representation learning by successfully integrating learnable topological invariants into deep learning pipelines, offering superior performance in capturing structural nuances that traditional message-passing networks miss.