Laplacian Encoding for Causal Structure in Transformer Architectures

Actian AI Lab · Internal Research Note · January 2026. A theory post: the math is real, the architecture is specified, the validation criteria are written down and pre-registered. None of the experiments have been run yet. That’s what the status field says and that’s what it means.

Abstract

Positional encoding in transformer architectures assumes sequential structure: tokens occupy positions in a queue, and proximity in that queue implies relevance. This assumption fails for directed acyclic graphs (DAGs), where relevance is determined by causal ancestry rather than sequential adjacency. We demonstrate that sinusoidal positional encoding is a special case of spectral graph encoding applied to path graphs, and propose the Laplacian Encoder as a principled generalization for arbitrary DAG topologies. The encoding preserves causal proximity in embedding space, enabling attention mechanisms to natively query ancestry relationships. We provide mathematical foundations, computational considerations, and validation criteria.

1. Introduction

Dupin, Poe’s detective, solved crimes through what he called ratiocination: the systematic reasoning from observed effects to hidden causes [Poe, 1841]. The corpse is here; the murderer was there. The method requires traversing causal structure backward — from consequence to antecedent.

Modern transformer architectures are Dupin’s inverse. Trained on sequential prediction, they reason forward: given tokens 1 through n, predict token n+1. The positional encoding reflects this assumption, marking each token’s location in a queue where causality flows with index order.

But not all structures are queues. Data lineage graphs, dependency trees, version control histories, and causal networks are directed acyclic graphs (DAGs) where “position” is not a scalar index but a location in a partially-ordered ancestry structure. When we flatten these DAGs into sequences and apply sequential positional encoding, we discard the information Dupin would need.

This paper argues that:

1. Sinusoidal positional encoding is spectral encoding on a path graph
2. Spectral encoding generalizes naturally to arbitrary graph topologies
3. For DAG-structured inputs, Laplacian eigenvector encoding preserves causal proximity
4. This enables attention mechanisms to perform ancestry queries natively

2. Background

2.1 Positional Encoding in Transformers

Vaswani et al. (2017) introduced sinusoidal positional encoding to inject sequence order into the permutation-invariant self-attention mechanism:

$$PE_{(pos, 2i)} = \sin\left(\frac{pos}{10000^{2i/d}}\right)$$

$$PE_{(pos, 2i+1)} = \cos\left(\frac{pos}{10000^{2i/d}}\right)$$

where $pos$ is the sequence position and $i$ is the dimension index. The authors note that this encoding allows the model to “attend by relative positions” since $PE_{pos+k}$ can be represented as a linear function of $PE_{pos}$.

2.2 The Path Graph Assumption

The sinusoidal encoding implicitly assumes the input is a path graph $P_n$: a graph where node $i$ connects only to nodes $i-1$ and $i+1$.

$$1 - 2 - 3 - 4 - \cdots - n$$

This is appropriate for natural language (tokens produced and consumed sequentially) but inappropriate for structures with branching, merging, or partial ordering.

2.3 Spectral Graph Theory

The graph Laplacian $L$ is defined as:

$$L = D - A$$

where $A$ is the adjacency matrix and $D = \mathrm{diag}(d_1, \ldots, d_n)$ is the degree matrix with $d_i = \sum_j A_{ij}$.

The normalized symmetric Laplacian is:

$$\mathcal{L} = I - D^{-1/2} A D^{-1/2}$$

Both are symmetric positive semi-definite, admitting eigendecomposition:

$$L = V \Lambda V^\top$$

where $\Lambda = \mathrm{diag}(\lambda_1, \ldots, \lambda_n)$ with $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ and $V = [v_1 | v_2 | \cdots | v_n]$ contains the corresponding eigenvectors.

2.4 Key Insight: Laplacian Eigenvectors as Graph Fourier Basis

The eigenvectors of the graph Laplacian form an orthonormal basis analogous to the Fourier basis for regular domains [Belkin & Niyogi, 2003; Shuman et al., 2013]. Specifically:

• For the path graph $P_n$, the Laplacian eigenvectors are exactly the discrete cosine transform (DCT) basis vectors
• For the cycle graph $C_n$, they are the discrete Fourier transform (DFT) basis vectors
• For arbitrary graphs, they generalize these to the graph’s specific topology

Proposition 1. Sinusoidal positional encoding is equivalent to spectral encoding using Laplacian eigenvectors of the path graph, up to scaling and phase.

Proof sketch. The unnormalized Laplacian of path graph $P_n$ is tridiagonal:

$$L_{P_n} = \begin{pmatrix} 1 & -1 & & \ -1 & 2 & -1 & \ & \ddots & \ddots & \ddots \ & & -1 & 1 \end{pmatrix}$$

The eigenvectors are $v_k(j) = \cos\left(\frac{\pi k (j - 1/2)}{n}\right)$, which matches the DCT-II basis and is equivalent to sinusoidal encoding under appropriate parameterization. $\square$

3. The Laplacian Encoder

3.1 Definition

Given a DAG with adjacency matrix $A \in {0,1}^{n \times n}$ and desired embedding dimension $k$, the Laplacian Encoder produces positional embeddings $P \in \mathbb{R}^{n \times k}$:

Step 1: Symmetrization (for directed graphs)

$$A_{sym} = A + A^\top$$

Step 2: Normalized Laplacian

$$\mathcal{L} = I - D^{-1/2} A_{sym} D^{-1/2}$$

with $D_{ii} = \sum_j (A_{sym})_{ij}$ and the convention $0/0 = 0$ for isolated nodes.

Step 3: Eigendecomposition

Compute the $k+1$ smallest eigenvalues and corresponding eigenvectors:

$$\mathcal{L} v_i = \lambda_i v_i, \quad i = 1, \ldots, k+1$$

Step 4: Positional Encoding

$$P = [v_2 | v_3 | \cdots | v_{k+1}]$$

where we discard $v_1$ (the constant eigenvector corresponding to $\lambda_1 = 0$).

3.2 Spectral Interpretation

The eigenvalues $\lambda_i$ correspond to frequency on the graph:

Eigenvalue	Frequency	Captures
$\lambda_1 = 0$	DC	Connectedness (uninformative)
$\lambda_2, \ldots, \lambda_j$	Low	Global structure, distant ancestry
$\lambda_j, \ldots, \lambda_m$	Mid	Community structure, subtrees
$\lambda_m, \ldots, \lambda_n$	High	Local structure, immediate neighbors

The Fiedler vector $v_2$ (corresponding to $\lambda_2$, the algebraic connectivity) is particularly informative, encoding the primary partition of the graph [Fiedler, 1973].

3.3 Causal Proximity Preservation

Theorem 1. For a tree-structured DAG, the Euclidean distance between Laplacian encodings is monotonically related to path distance.

Proof. In trees, the effective resistance between nodes $i$ and $j$ equals the path distance $d(i,j)$. The effective resistance can be computed from Laplacian eigenvectors [Klein & Randić, 1993]:

$$R_{eff}(i,j) = \sum_{k=2}^{n} \frac{1}{\lambda_k}(v_k(i) - v_k(j))^2$$

For truncated encodings, this becomes an approximation weighted toward low-frequency (global) structure. $\square$

Corollary 1. Nodes with shared ancestry have similar low-frequency components.

This follows from the smoothness of low-frequency eigenvectors: $v_k$ for small $k$ varies slowly across the graph, so nodes in the same region of the DAG receive similar values.

3.4 Sign Ambiguity

Eigenvectors are defined only up to sign: if $v$ is an eigenvector, so is $-v$. This creates inconsistency across different graph instances or decomposition algorithms.

Resolution strategies:

1. Sign-invariant networks [Lim et al., 2022]: Design downstream architecture to be invariant to per-eigenvector sign flips
2. Canonical sign: Set $\mathrm{sign}(v_k) = \mathrm{sign}(\sum_i v_k(i))$
3. Data augmentation: Randomly flip signs during training

4. Integration with Transformer Architecture

4.1 Additive Encoding

The standard approach, following Vaswani et al. (2017):

$$X’ = X + W_p P$$

where $W_p \in \mathbb{R}^{k \times d}$ projects the $k$-dimensional Laplacian encoding to model dimension $d$.

4.2 Attention Bias

Incorporate graph structure directly into attention scores [Dwivedi & Bresson, 2020]:

$$\mathrm{Attention}(Q, K, V) = \mathrm{softmax}\left(\frac{QK^\top}{\sqrt{d}} + B\right) V$$

where the bias $B_{ij}$ encodes the structural relationship between nodes $i$ and $j$:

$$B_{ij} = -\alpha |P_i - P_j|^2$$

This biases attention toward spectrally-close (causally-related) nodes.

4.3 Concatenation

For explicit access to positional information:

$$X’ = [X | P]$$

This increases dimensionality but allows the model to learn separate functions of content and position.

5. Computational Considerations

5.1 Complexity

Operation	Complexity	Notes
Laplacian construction	$O(	E
Full eigendecomposition	$O(n^3)$	Prohibitive for large graphs
Truncated (Lanczos)	$O(	E
Per-node lookup	$O(k)$	After precomputation

For data lineage graphs with $n \sim 10^6$ nodes, $|E| \sim 10^7$ edges, and $k = 64$, the truncated decomposition is feasible (seconds to minutes) and amortized over all queries.

5.2 Sparse Implementation

The Laplacian is sparse with $O(|E|)$ nonzeros. Lanczos/ARPACK algorithms require only matrix-vector products $\mathcal{L}v$, which are $O(|E|)$ each:

1. Compute $Av$ via sparse matrix-vector multiply — $O(|E|)$
2. Compute $D^{-1/2} v$ elementwise — $O(n)$
3. Return $v - D^{-1/2} A D^{-1/2} v$ — $O(n)$

5.3 Dynamic Graphs

When edges are added or removed, full recomputation is wasteful. Incremental approaches include:

• Low-rank updates [Brand, 2006]: For rank-$r$ changes to $A$, update eigendecomposition in $O(n \cdot r \cdot k)$
• Local recomputation: If change is localized, recompute only affected subgraph
• Periodic refresh: Batch updates, recompute on schedule

6. Directed Acyclic Graphs: Special Considerations

6.1 Directed Laplacian

The symmetrization in Section 3.1 discards edge direction. For causal DAGs where direction encodes causality, alternatives include:

Random-walk Laplacian:

$$\mathcal{L}{rw} = I - D{out}^{-1} A$$

where $D_{out}$ is the out-degree matrix. This is not symmetric, so eigenvectors may be complex.

Magnetic Laplacian [Zhang et al., 2021]: Encodes direction via complex phases:

$$\mathcal{L}^{(q)}{ij} = \begin{cases} 1 & i = j \ -\frac{1}{\sqrt{d_i d_j}} e^{i q \cdot \mathrm{sign}(A{ij} - A_{ji})} & (i,j) \in E \ 0 & \text{otherwise} \end{cases}$$

This preserves some directional information while maintaining Hermitian structure.

6.2 Ancestor-Aware Encoding

For explicit ancestry encoding, augment spectral features with:

• Topological depth: Distance from root(s)
• Reachability hash: Bloom filter of ancestor set
• Path encoding: Sequence of edge types from root to node

These can be concatenated with Laplacian encoding for hybrid representations.

7. Application: Laplacian Autoencoder for Data Lineage

The preceding sections establish Laplacian encoding as a theoretically grounded positional encoding for DAG-structured data. We now describe a concrete architecture for data lineage root cause analysis that requires no labeled anomalies and no explicit graph traversal at inference time.

7.1 Motivation

Data lineage graphs encode the causal provenance of data assets: tables derive from other tables, dashboards aggregate reports, reports query views. When an anomaly appears at a downstream node (e.g., a dashboard showing incorrect figures), the root cause lies somewhere upstream in the lineage DAG.

Traditional approaches require explicit graph traversal at query time, which is $O(|V| + |E|)$ per query and requires the graph to be loaded in memory. We propose instead to bake the causal structure into a learned embedding space, enabling root cause retrieval via vector similarity search.

7.2 Architecture

Training Phase:

[node_features x_i] + [laplacian_PE P_i]
            |
            v
    +---------------+
    |    Encoder    |  (Transformer with LE-biased attention)
    +---------------+
            |
            v
        z_i in R^d    <-- bottleneck embedding
            |
            v
    +---------------+
    |    Decoder    |
    +---------------+
            |
            v
[x_i_hat, P_i_hat]   (reconstruct features AND position)

The encoder is a transformer where attention scores incorporate Laplacian encoding distance as a bias term (Section 4.2). The bottleneck embedding $z_i$ is constrained to be low-dimensional ($d = 64$–$256$), forcing compression that preserves only the most salient information.

Critically, the decoder reconstructs both the input features $x_i$ and the Laplacian positional encoding $P_i$. This dual reconstruction objective forces the bottleneck to encode causal position, not just content.

7.3 Training Objective

The loss function combines three terms:

$$\mathcal{L} = \lambda_1 \mathcal{L}{feat} + \lambda_2 \mathcal{L}{pos} + \lambda_3 \mathcal{L}_{contrast}$$

Feature reconstruction ensures the embedding captures node semantics:

$$\mathcal{L}{feat} = \frac{1}{n} \sum{i=1}^{n} | x_i - \hat{x}_i |^2$$

Position reconstruction ensures the embedding captures graph structure:

$$\mathcal{L}{pos} = \frac{1}{n} \sum{i=1}^{n} | P_i - \hat{P}_i |^2$$

Contrastive regularization (optional) explicitly organizes the latent space by ancestry:

$$\mathcal{L}{contrast} = \sum{(i,j) \in \mathrm{Ancestors}} | z_i - z_j |^2 - \sum_{(i,k) \notin \mathrm{Ancestors}} \max(0, m - | z_i - z_k |)^2$$

where $m$ is a margin hyperparameter. This pulls ancestors together and pushes non-ancestors apart, subject to the margin.

7.4 Self-Supervised Learning from Topology

A key insight: no labeled anomalies are required. The graph topology itself provides supervision.

The Laplacian encoding $P_i$ is computed deterministically from the adjacency matrix. By training the autoencoder to reconstruct $P_i$, we force the model to learn representations that respect causal structure. The graph teaches the model what “nearby” means in lineage space.

This is analogous to how word2vec learns semantic similarity from co-occurrence statistics without labeled synonyms. Here, we learn causal similarity from graph structure without labeled root causes.

7.5 Inference: Root Cause Retrieval

At inference time, the lineage graph is not traversed. Instead:

1. Offline indexing: Compute $z_i$ for all nodes in the lineage graph. Index these embeddings in a vector database (e.g., FAISS, NEBULA).

2. Anomaly detection: When node $j$ exhibits anomalous behavior (detected by reconstruction error $| x_j - \hat{x}_j |$ exceeding a threshold, or by external monitoring), it becomes a query.

3. Similarity search: Retrieve the $k$ nearest neighbors of $z_j$ in the indexed embedding space.

4. Ancestry filter: Optionally filter results to only include nodes that are ancestors of $j$ in the DAG (a sparse matrix lookup, $O(1)$ with precomputed reachability).

5. Ranking: Return candidates ranked by embedding similarity. High similarity indicates shared causal context; these are probable root causes.

Complexity: After offline indexing, each root cause query is $O(\log n)$ for approximate nearest neighbor search, compared to $O(|V| + |E|)$ for graph traversal. For lineage graphs with millions of nodes, this is the difference between milliseconds and seconds.

7.6 Why This Works

The architecture exploits three properties of Laplacian encoding:

1. Ancestors share low-frequency components (Corollary 1). Nodes with common ancestry have similar $P_i$, so the encoder sees them as positionally close.

2. Reconstruction pressure preserves structure. To reconstruct $P_i$, the bottleneck must encode where the node sits in the causal hierarchy.

3. Attention bias reinforces locality. The LE-biased attention (Section 4.2) ensures that during encoding, each node attends primarily to its causal neighbors, not arbitrary distant nodes.

The result is a latent space where Euclidean distance approximates causal distance. Root cause retrieval becomes cosine similarity — a problem for which we have decades of optimized infrastructure.

7.7 Predictive Lineage Inference

The most compelling application extends beyond retrieval to prediction: inferring lineage relationships that are not explicitly documented.

Enterprise data catalogs suffer from incomplete lineage metadata. Manual documentation is expensive, automated parsers miss dynamic SQL and ad-hoc transformations, and legacy systems predate lineage tracking entirely. The result is a lineage graph with missing edges — known unknowns and unknown unknowns.

The Laplacian Autoencoder addresses this directly:

Lineage Completion. Given two nodes $i$ and $j$ with no documented relationship, compute $\mathrm{sim}(z_i, z_j)$. High similarity suggests a causal relationship exists but is undocumented. This generates candidate edges for human review or automated validation.

Ancestor Prediction. Given a node $j$ with incomplete ancestry, retrieve its $k$ nearest neighbors in embedding space. These are predicted ancestors, ranked by confidence. The model has learned what “upstream” looks like from the training graph; it can generalize to nodes with missing metadata.

Anomaly Explanation. When an anomaly appears at node $j$, but $j$’s documented lineage is incomplete, the model can still identify probable root causes. It reasons from learned causal structure, not from explicit edges. This is precisely the scenario where traditional graph traversal fails.

Transfer Across Subgraphs. A model trained on well-documented portions of the lineage graph can make predictions about poorly-documented portions, provided the node features are comparable. The spectral encoding captures patterns of causal relationship that transfer across graph regions.

The implication: the Laplacian Autoencoder is not merely a faster way to traverse known lineage. It is a predictive model that infers likely causal relationships from learned structure. The lineage graph becomes a training signal, not a runtime dependency.

7.8 Relation to Pull-Based Execution

This architecture mirrors the “pull-based” execution model increasingly common in modern data systems. In pull-based systems, a downstream consumer requests data, and the system traces backward through the DAG to find the upstream producers that can satisfy the request.

The Laplacian Autoencoder performs pull-based reasoning implicitly:

• The downstream anomaly is the “request”
• The embedding similarity search “pulls” on the latent space
• The retrieved neighbors are the upstream “producers” of the anomaly

The difference is that traditional pull-based systems traverse explicit edges; the Laplacian Autoencoder traverses implicit causal structure encoded in continuous vector space. The graph has been compiled into geometry — and geometry, unlike graphs, supports approximate queries, interpolation, and prediction.

8. Validation Methodology

8.1 Synthetic Benchmark

Construct DAGs with known causal structure:

        A
       / \
      B   C
     /|   |\
    D E   F G

Test 1: Ancestry Recovery

Query: Given node $D$, rank all other nodes by cosine similarity of Laplacian encoding.

Success criterion: Ancestors ${A, B}$ rank above non-ancestors ${C, E, F, G}$.

Metric: Mean Average Precision (MAP) over ancestor retrieval.

Test 2: Sibling Detection

Nodes $D, E$ share parent $B$. Nodes $D, F$ share grandparent $A$ only.

Success criterion: $\mathrm{sim}(P_D, P_E) > \mathrm{sim}(P_D, P_F)$

Metric: Accuracy of sibling-vs-cousin discrimination.

Test 3: Spectral-Geodesic Correlation

Compute Pearson correlation between:

• Pairwise spectral distance: $|P_i - P_j|$
• Pairwise shortest path distance: $d_G(i, j)$

Expected: Strong positive correlation ($r > 0.8$) for tree structures.

8.2 Baseline Comparisons

Method	Expected Performance
Random encoding	Chance
BFS-order sinusoidal	Poor (order-dependent)
DFS-order sinusoidal	Poor (order-dependent)
Topological-order sinusoidal	Moderate (respects direction)
Node2Vec [Grover & Leskovec, 2016]	Moderate (content-biased)
Laplacian Encoder	Best (structure-native)

8.3 Downstream Task: Root Cause Retrieval

Given a data lineage graph and an anomalous node, retrieve probable root causes.

Ground truth: Inject faults at known nodes, propagate effects, measure retrieval of injected fault locations.

Metric: Mean Reciprocal Rank (MRR) of true root cause in similarity-ranked results.

9. Related Work

Graph Neural Networks. GCN [Kipf & Welling, 2017] uses the Laplacian for message passing but not positional encoding. GraphSAGE [Hamilton et al., 2017] and GAT [Veličković et al., 2018] aggregate neighbor information without explicit positional encoding.

Graph Transformers. Dwivedi & Bresson (2020) benchmark Laplacian eigenvector positional encoding for graph classification. Kreuzer et al. (2021) propose spectral attention networks. Ying et al. (2021) introduce Graphormer with spatial and edge encodings.

Spectral Methods. Belkin & Niyogi (2003) establish Laplacian eigenmaps for dimensionality reduction. Coifman & Lafon (2006) develop diffusion maps with similar spectral foundations.

Causal Discovery. Pearl (2009) formalizes causal DAGs and do-calculus. Recent work explores LLMs for causal discovery [Kıcıman et al., 2023], but focuses on graph generation rather than graph encoding.

10. Conclusion

The sequential assumption in positional encoding is a special case, not a universal truth. For structures where relevance is determined by causal ancestry rather than sequential proximity, the Laplacian Encoder provides a principled alternative grounded in spectral graph theory.

The Laplacian Autoencoder architecture demonstrates a concrete application: data lineage root cause analysis without graph traversal, without labeled anomalies, and without LLMs in the inference path. More significantly, it enables predictive lineage inference — discovering undocumented causal relationships from learned structure, not just traversing known ones.

The graph topology provides its own supervision; the spectral encoding compiles causal structure into geometry; and vector similarity search — a solved problem with mature infrastructure — replaces expensive graph algorithms.

Dupin’s method was to observe that everyone searched for the purloined letter in hidden places, when it sat in plain sight on the mantelpiece. The same insight applies here: positional information was never missing from our DAGs. We were simply encoding the wrong structure — imposing sequences where ancestry was the natural order.

The position was never hidden. We just forgot to ask the graph.

Appendix A: Laplacian Eigenvectors of Common Graphs

Path graph $P_n$:

$$\lambda_k = 2 - 2\cos\left(\frac{\pi (k-1)}{n}\right), \quad v_k(j) = \sqrt{\frac{2}{n}} \cos\left(\frac{\pi (k-1)(j - 1/2)}{n}\right)$$

Complete graph $K_n$: $\lambda_1 = 0$, $\lambda_2 = \cdots = \lambda_n = n$. All non-trivial eigenvectors have eigenvalue $n$; no structural information beyond connectedness.

Star graph $S_n$ (1 center, $n-1$ leaves): $\lambda_1 = 0$, $\lambda_2 = \cdots = \lambda_{n-1} = 1$, $\lambda_n = n$. The Fiedler vector separates center from leaves.

Binary tree $T_h$ (height $h$): No closed form, but low-frequency eigenvectors encode depth (distance from root), and mid-frequency eigenvectors encode subtree membership.

Appendix B: Implementation Reference

import numpy as np
from scipy.sparse import csr_matrix, diags
from scipy.sparse.linalg import eigsh

def laplacian_encoder(adjacency: csr_matrix, k: int = 64) -> np.ndarray:
    """Compute k-dimensional Laplacian positional encoding.

    Args:
        adjacency: Sparse adjacency matrix (directed OK, will be symmetrized)
        k: Number of spectral components

    Returns:
        P: [n, k] positional encoding matrix
    """
    n = adjacency.shape[0]

    # Symmetrize for directed graphs
    A_sym = adjacency + adjacency.T
    A_sym.data = np.clip(A_sym.data, 0, 1)  # Binary

    # Degree matrix
    degrees = np.array(A_sym.sum(axis=1)).flatten()
    degrees = np.maximum(degrees, 1e-12)  # Avoid division by zero

    # Normalized Laplacian: L = I - D^{-1/2} A D^{-1/2}
    D_inv_sqrt = diags(1.0 / np.sqrt(degrees))
    L_norm = diags(np.ones(n)) - D_inv_sqrt @ A_sym @ D_inv_sqrt

    # Compute k+1 smallest eigenvectors (skip first)
    k_compute = min(k + 1, n - 1)
    eigenvalues, eigenvectors = eigsh(L_norm, k=k_compute, which='SM')

    # Sort by eigenvalue and skip trivial eigenvector
    idx = np.argsort(eigenvalues)
    P = eigenvectors[:, idx[1:k+1]]  # Skip lambda_0 = 0

    # Canonical sign: make sum positive
    for i in range(P.shape[1]):
        if P[:, i].sum() < 0:
            P[:, i] *= -1

    return P.astype(np.float32)

References

1. Poe, E. A. (1841). The Murders in the Rue Morgue. Graham’s Magazine.
2. Vaswani, A., et al. (2017). Attention Is All You Need. NeurIPS, 30.
3. Belkin, M., & Niyogi, P. (2003). Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6):1373–1396.
4. Shuman, D. I., et al. (2013). The Emerging Field of Signal Processing on Graphs. IEEE Signal Processing Magazine, 30(3):83–98.
5. Fiedler, M. (1973). Algebraic Connectivity of Graphs. Czechoslovak Mathematical Journal, 23(2):298–305.
6. Klein, D. J., & Randić, M. (1993). Resistance Distance. Journal of Mathematical Chemistry, 12(1):81–95.
7. Lim, D., et al. (2022). Sign and Basis Invariant Networks for Spectral Graph Representation Learning. ICLR.
8. Dwivedi, V. P., & Bresson, X. (2020). A Generalization of Transformer Networks to Graphs. AAAI Workshop on Deep Learning on Graphs.
9. Brand, M. (2006). Fast Low-Rank Modifications of the Thin Singular Value Decomposition. Linear Algebra and its Applications, 415(1):20–30.
10. Zhang, X., et al. (2021). MagNet: A Neural Network for Directed Graphs. NeurIPS, 34.
11. Grover, A., & Leskovec, J. (2016). node2vec: Scalable Feature Learning for Networks. KDD.
12. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
13. Hamilton, W. L., Ying, R., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. NeurIPS, 30.
14. Veličković, P., et al. (2018). Graph Attention Networks. ICLR.
15. Kreuzer, D., et al. (2021). Rethinking Graph Transformers with Spectral Attention. NeurIPS, 34.
16. Ying, C., et al. (2021). Do Transformers Really Perform Bad for Graph Representation? NeurIPS, 34.
17. Coifman, R. R., & Lafon, S. (2006). Diffusion Maps. Applied and Computational Harmonic Analysis, 21(1):5–30.
18. Pearl, J. (2009). Causality: Models, Reasoning, and Inference, 2nd ed. Cambridge University Press.
19. Kıcıman, E., Ness, R., Sharma, A., & Tan, C. (2023). Causal Reasoning and Large Language Models. arXiv:2305.00050.