Methods › Graphs › Graph Models › CT-Layer

Commute Times Layer

CT-Layer

1 paper tagged archive 2025-07-28

Introduced by Adrian Arnaiz-Rodriguez et al. in DiffWire: Inductive Graph Rewiring via the Lovász Bound

archive 2025-07-28 Description, source and code snippet are the archive's method entry.

TL;DR: CT-Layer is a GNN Layer which is able to rewire a graph in an inductive an parameter-free way according to the commute times distance (or effective resistance). We address it learning a differentiable way to compute the CT-embedding of the graph.

Summary

CT-Layer is able to Learn the Commute Times distance between nodes (i.e. effective resistance distance) in a differentiable way, instead of the common spectral version, and in a parameter free manner, which is not the cased of the heat kernel. This approach allow to solve it as an optimization problem inside a GNN, leading to have a new layer which is able to learn how rewire a given graph in an optimal, and inductive way.

In addition, CT-Layer also is able to learn Commute Times embeddings, and then calculate it for any graph in an inductive way. The Commute Times embedding is also related with the eigenvalues and eigenvectors of the Laplacian of the graph, because CT embedding is just the eigenvectors scaled. Therefore, CT-Layer is also able to learn hot to calculate the spectrum of the Laplacian in a differentiable way. Therefore, this embedding must satisfy orthogonality and normality.

Finally, recent connections has been found between commute times distance and curvature (which is non-differentiable), establishing equivalences between them. Therefore, CT-Layer can also be seen as the differentiable version of the curvature rewiring.

**We are going through a quick overview of the layer, but I suggest go to the paper for a detailed explanation. **

Spectral CT- Embedding downsides

CT-embedding Z is computed spectrally in the literature (until the proposal of this method) or it is approximated using the heat kernel (very dependent on hyperparameter t). This fact does not allow us to propose differentiable methods using that measure: Z=√(vol(G))Λ¹2Fᵀ given L=FΛFᵀ

Then, CT-distance is given by the Euclidean distances between the embeddings CTᵤᵥ = ||zᵤ-zᵥ||². The spectral form is:

CTᵤᵥ/(vol(G)) = ∑ᵢ₌₂ⁿ 1/λᵢ (f(u)-f(v))² being f the eigenvectors of the graph Laplacian.

This embedding and distances gives us desirable properties of the graph, such an understanding of the structure, or an embedding based on the spectrum which minimizes Dirichlet energies. However, the spectral computation is not differentiable.

CT-Layer as an optimization problem: Differentiable, learnable and inductive CT-Layer

Giving that Z minimizes Dirichlet energies s.t. being orthogonal and normalized, we can formulate this problem as constraining neighboring nodes to have a similar embeddings s.t. ZZᵀ=I.

Z = argmin_(ZᵀZ=I) (∑_(u,v) ||zᵤ-zᵥ||²Aᵤᵥ)/(∑_(u,v) Z²ᵤᵥ dᵤ)=(Tr[ZᵀLZ])/(Tr[ZᵀDZ])

With the above elements we have a definition of CT-Layer, our rewiring layer: Given the matrix X_(n×F) encoding the features of the nodes after any message passing (MP) layer, Z_(n×O(n))=tanh(MLP(X)) learns the association X→Z while Z is optimized according to the loss L_(CT) = (Tr[ZᵀLZ])/(Tr[ZᵀDZ]) + ‖ZᵀZ/(‖ZᵀZ‖_F) - Iₙ‖_F This results in the following resistance diffusion T^(CT) = R(S)⊙A (Hadamard product between the resistance distance and the adjacency) which provides as input to the subsequent MP layer a learnt convolution matrix.

As explained before, Z is the commute times embedding matrix and the pairwise euclidian distance of that learned embeddings are the commute times distances or resistance distances. Therefore, once trained this layer, it will be able to calculate the commute times embedding for a new graph, and rewire that new and unseen graph in a principled way based on the commute times distance.

Preservation of Structure

Does this rewiring preserve the original structure? Let G′ = Sparsify(G, q) be a sampling algorithm of graph G = (V, E), where edges e ∈E are sampled with probability q∝Rₑ (proportional to the effective resistance, i.e. commute times). Then, for n = |V| sufficiently large and 1/√(n)< ϵ≤1, we need O(n\log n/ε^2)$ samples to satisfy:

∀x∈ℝⁿ: (1-ϵ)xᵀL_Gx≤xᵀL_(G′)x≤(1+ϵ)xᵀL_Gx

The intuitions behind is that Dirichlet energies in G′ are bounded in (1±ϵ) of the Dirichlet energies of the original graph G.

PaperSourceSee Code · anonymous.4open.science/r/DiffWireNeurIPS22/CT_layer.py

In Syntology name not resolved (unknown_name). The lookup matched no method, paper or venue by this name; that asserts nothing about whether code exists.

Syntology's have check for this name (free, it answers coverage only), read 2026-10-05; ask it again live. A level is the served verification level of that one answer; nothing here is summed across methods.

Papers archive 2025-07-28

archive papers tagged: 1 · with a code link: 1 · where Syntology ran a sample: 0 (0 with a run with no instrument failure, 0 where every run was a failure of Syntology's instrument) Syntology

Show: all tagged papersonly where code ran: none of the 1 tagged papers has a Syntology run on record

Page 1 of 1: paper 1 of 1, newest first by the archive's date (ties by slug), in archive order.

Repository counts are the archive's code-links table. A Syntology line states what Syntology ran from that paper's harvested code, as “N ran (of which C constructed an object rather than computing a result; K with no instrument failure: H honoured, V violated, P with no contract checked; I where Syntology's instrument failed) · U unverified”; the instrument figure counts failures of Syntology's instrument, not of the code. It is per sample and not a correctness claim. When the archive marks a repository official for the paper, the line starts with that repository's state (the archive's flag, not a verdict on who wrote the code; “community repositories only” when every sample that ran came from a community repository, “official: no sample here; runs from other or unrecorded repositories” when some came from a repository the paper names or has in its text, or from none recorded); hover it for the repositories the samples that ran came from.

Tasks archive 2025-07-28

2 tasks the archive attaches to papers tagged with this method, by distinct papers. A task without a page in the catalog is plain text.

TaskPapers
Graph Classification1
Node Classification1

Usage over time archive 2025-07-28

Papers per year tagged with CT-Layer: 2022 to 2022, peak 1 1 0 2022: 1 paper 2022
Papers per year the archive tags with this method, by the paper's archive date (1 dated). Bars are counts, not a trend claim.

Components: the archive holds no method-to-method composition, so PwC's Components table cannot be rebuilt; the Papers list carries no Results column for the same reason (the archive does not join its leaderboard rows to method tags).

Categories archive 2025-07-28

Graph ModelsGraph Embeddings

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections