Signal Processing and Learning on Directed Graphs

14 concepts14 papers1 proposal

Classical signal processing was built for the grid—pixels in an image or samples in a time series. As data became more complex, researchers developed Graph Signal Processing (GSP) to handle irregular domains like social networks or brain connectivity. As Shuman et al. explain, this framework generalizes tools like the Fourier transform by leveraging the Graph Laplacian.

However, a significant limitation persists: most foundational GSP tools assume that relationships between data points are symmetric. In the real world, influence is rarely a two-way street. Traffic flows in specific directions, citations link papers to their predecessors, and causal influences move from cause to effect. Modeling these systems requires moving beyond undirected graphs to directed graphs (digraphs), a transition that breaks many of the mathematical assumptions the field relies on.

The Symmetry Constraint

In standard GSP, the Graph Laplacian—a matrix representing the network structure—is symmetric. This symmetry is mathematically convenient because it guarantees a set of real eigenvalues and orthogonal eigenvectors, which serve as the "frequencies" and "Fourier basis" for the graph.

When edges are directed, this symmetry vanishes. As Shuman et al. and Isufi et al. note, the lack of a symmetric Laplacian makes it difficult to define what "frequency" even means on a directed network. Without a clear spectral decomposition, standard operations like filtering, denoising, and smoothing become theoretically unstable. Kyng et al. point out that even regression techniques like Lipschitz learning encounter practical hurdles when applied to directed structures, often requiring complex physical analogies that do not naturally fit the data.

Why Directionality Matters

The push toward directed graph modeling is driven by the need to capture asymmetric dependencies. In many systems, the relationship between node A and node B is fundamentally different from the relationship between B and A:

  • Causality and Flow: Mateos et al. and Buciulea et al. argue that undirected graphs fail to capture the one-way causal influences inherent in biological or financial processes.
  • Non-reciprocal Similarity: In semi-supervised learning, Rustamov et al. observe that treating label propagation as a symmetric process ignores cases where one data point might strongly suggest the label of another, but not vice versa.
  • Physical Constraints: In 3D point cloud analysis, Hu et al. suggest that directed edges could better capture complex geometric dependencies that symmetric metrics miss.

Redefining the Toolkit for Digraphs

To bridge this gap, researchers are developing new mathematical frameworks that do not rely on symmetry.

One approach involves rethinking the Fourier transform itself. Shafipour et al. proposed a Directed Graph Fourier Transform (DGFT) based on a new measure called "directed variation." Instead of relying on the Laplacian's eigenvectors, they use optimization to construct an orthonormal basis that spreads frequency components evenly, allowing for effective denoising on digraphs.

In the realm of topology inference—where the goal is to learn the graph structure from the data itself—the challenge is even greater. Standard methods like the Graphical Lasso often assume symmetry to ensure a valid precision matrix. To counter this, Mayiami et al. developed Bayesian frameworks that incorporate distinct mathematical constraints specifically for directed edges. Similarly, Mateos and Wasserman have introduced software toolkits like pyGSL to help researchers infer these asymmetric causal or flow-based dependencies at scale.

Even non-linear analysis is evolving. Najman and Cousty have explored how mathematical morphology—traditionally used for image processing—can be generalized to graphs. They highlight that creating consistent morphological operators for directed graphs remains one of the most significant open challenges in extending signal processing to asymmetric domains.

The Path Forward

The transition from undirected to directed graph modeling represents a shift from simple connectivity to complex influence. Whether through quantum-based walks proposed by Zhang et al. or the kernel-based reconstruction methods of Romero, the goal is the same: to create a signal processing framework that respects the inherent "one-way" nature of the real world. As Chen et al. suggest, adapting these models is not just a theoretical exercise, but a necessity for representing the asymmetric influence and causal flows that define modern complex systems.

Key Foundational Work

A graph-based mathematical morphology reader (2014) — contributed 2 concept elements to this direction.
The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_asymmetric_relationship_modeling_directe_cddc2095,
  title = {asymmetric relationship modeling (directed graph signal processing)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-relationship-modeling-directed-graph-signal-processing/rdr_cddc2095435c47b6b462c37cbd07c257},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_asymmetric_relationship_modeling_directe_cddc2095_v1,
  title = {asymmetric relationship modeling (directed graph signal processing)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-relationship-modeling-directed-graph-signal-processing/rdr_cddc2095435c47b6b462c37cbd07c257/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake