FastMap-D embeds directed graphs using potential fields.
problem Embedding directed graphs in Euclidean space.
method Generalization of FastMap to handle directed graphs using a potential field and machine learning.
result FastMap-D outperforms other approaches in embedding directed graphs.
Study of Betti numbers in prodsimplicial complexes for directed graphs, focusing on DNA recombination.
problem Analyzing Betti numbers in directed graphs for DNA recombination.
method Custom prodsimplicial complexes for acyclic directed graphs, investigating Betti numbers.
result Investigated Betti numbers and cycles in prodsimplicial complexes for DNA recombination.
Novel Haar-Laplacian for directed graphs enhances spectral graph applications.
problem Lack of suitable Laplacian for directed graphs in spectral graph theory.
method Inspired by Haar-like transformation, introduces a Hermitian matrix preserving direction and weight.
result HaarNet outperforms in weight prediction and denoising on directed graphs.
New method clusters directed graphs using Koopman operators.
problem Challenges in clustering directed graphs, especially complex eigenvalues and lack of cluster definition.
method Relate graph Laplacians to transfer operators and metastable sets in stochastic systems, derive clustering algorithms for directed and time-evolving graphs.
result Clusters can be interpreted as coherent sets, useful for analyzing transport and mixing processes.
Graph convolutional networks(GCNs) have become the most popular approaches for graph data in these days because of their powerful ability to extract features from graph. GCNs approaches are divided into two categories, spectral-based and spatial-based. As the earliest convolutional networks for graph data, spectral-bas…
Directed graphs occur throughout statistical modeling of networks, and exchangeability is a natural assumption when the ordering of vertices does not matter. There is a deep structural theory for exchangeable undirected graphs, which extends to the directed case via measurable objects known as digraphons. Using digraph…
Extends GCNs to directed graphs for better performance.
problem Limited application of GCNs to undirected graphs.
method Uses first- and second-order proximity to extend GCNs to directed graphs.
result DGCN outperforms state-of-the-art methods on citation and co-purchase datasets.
Proposes a new model for traffic flow on directed graphs.
problem Modeling advection on directed graphs for traffic flow.
method Reformulates graph advection operator as finite difference scheme; proposes DGAMGP model.
result Effective modeling of traffic flow and uncertainty as an advective process.
In this paper, we define the curvature dimension inequalities CD(m, K) on finite directed graphs modifying the case of undirected graphs. As a main result, we evaluate m and K on finite directed graphs.
New matrix reveals cluster info in sparse directed graphs.
problem Analyzing cluster information in directed graphs.
method Proposed complex non-backtracking matrix integrating Hermitian adjacency matrix and non-backtracking matrix properties.
result The complex non-backtracking matrix holds cluster information, especially for sparse directed graphs.
Spectral clustering for directed graphs using likelihood estimation.
problem Clustering directed graphs with edge directions.
method Maximum likelihood estimation on stochastic block models.
result Significant performance gains over existing methods.
This paper considers the problem of embedding directed graphs in Euclidean space while retaining directional information. We model a directed graph as a finite set of observations from a diffusion on a manifold endowed with a vector field. This is the first generative model of its kind for directed graphs. We introduce…
Graph autoencoders (AE) and variational autoencoders (VAE) recently emerged as powerful node embedding methods. In particular, graph AE and VAE were successfully leveraged to tackle the challenging link prediction problem, aiming at figuring out whether some pairs of nodes from a graph are connected by unobserved edges…
We introduce a novel harmonic analysis for functions defined on the vertices of a strongly connected directed graph of which the random walk operator is the cornerstone. As a first step, we consider the set of eigenvectors of the random walk operator as a non-orthogonal Fourier-type basis for functions over directed gr…
PyTorch Geometric Signed Directed fills the gap for GNNs on signed and directed graphs.
problem Lack of unified software packages for GNNs on signed and directed networks.
method Developed a software package with GNN models, synthetic and real-world data, and evaluation metrics.
result Demonstrates the effectiveness of the implemented methods through experiments.
New method clusters directed and undirected graphs without losing directional information.
problem Clustering directed graphs due to asymmetry in edge connectivity.
method Generalized Dirichlet Energy (GDE) and generalized spectral clustering (GSC).
result GSC outperforms existing methods in clustering accuracy and robustness.
Graph Lie algebras have infinite prolongation if they have a vertex of degree one.
problem Determining when the prolongation of a graph Lie algebra is infinite-dimensional.
method Analyzing labeled direct graphs and their associated Lie algebras.
result Graph Lie algebras are infinite-dimensional if and only if they have a vertex of degree one.
Proposes a novel approach using vector cross product to preserve directional edges in directed graphs.
problem Preserving directional edges in directed graphs for tasks like link prediction and node recommendation.
method Integrates the non-commutative property of vector cross product into a Siamese neural network to learn N-dimensional embeddings.
result Low-dimensional embeddings effectively preserve directional properties and outperform state-of-the-art methods.
Develops neural network for directed hypergraphs for node classification.
problem Irregular data structure, particularly directed graphs.
method Directed hypergraph neural network and semi-supervised learning method.
result Novel directed hypergraph neural network achieves highest accuracies on node classification tasks.
New method for testing directed graphs using surrogate data.
problem No established method for statistical testing on directed graphs.
method Define directed graph wide-sense stationary signals, generate surrogates preserving covariance, construct null distributions.
result Feasibility and superiority of new approach over existing methods.
The paper presents a new method to represent directed graphs using pseudo-Riemannian manifolds.
problem Representing directed graphs in a compact and meaningful way.
method Combines pseudo-Riemannian metric structure, non-trivial global topology, and a unique likelihood function.
result Low-dimensional cylindrical Minkowski and anti-de Sitter spacetimes produce equal or better graph representations than curved Riemannian manifolds.
The ability of a graph neural network (GNN) to leverage both the graph topology and graph labels is fundamental to building discriminative node and graph embeddings. Building on previous work, we theoretically show that edGNN, our model for directed labeled graphs, is as powerful as the Weisfeiler-Lehman algorithm for …
We consider intrinsic linking and knotting in the context of directed graphs. We construct an example of a directed graph that contains a consistently oriented knotted cycle in every embedding. We also construct examples of intrinsically 3-linked and 4-linked directed graphs. We introduce two operations, consistent edg…
Novel GNN for signed and directed networks using magnetic signed Laplacian.
problem Efficiently modeling signed and directed networks for tasks like clustering and link prediction.
method Introduced a magnetic signed Laplacian for directed signed graphs, used it to construct a spectral GNN.
result Demonstrated effective performance on tasks involving signed and directional information.
Constructs Lie algebras from labeled directed graphs and identifies properties of these algebras.
problem Constructing and analyzing Lie algebras from labeled directed graphs.
method Using labeled directed simple graphs to construct 2-step nilpotent Lie algebras, identifying ideals and subalgebras through special subgraphs, and proving isomorphisms based on label occurrences.
result Lie algebras depend only on the underlying undirected graph if all edges are labeled uniquely.
New Ricci flow method for directed graphs with balancing factor.
problem Analyzing asymmetry in directed networks.
method Rigorous formulation of Ricci flow on directed weighted graphs with balancing factor.
result Existence and uniqueness of discrete Ricci flow solutions.
We propose a novel approach for learning node representations in directed graphs, which maintains separate views or embedding spaces for the two distinct node roles induced by the directionality of the edges. We argue that the previous approaches either fail to encode the edge directionality or their encodings cannot b…
The study characterizes heat flow and concentration on directed graphs with a lower Ricci curvature bound.
problem Understanding heat flow and concentration on directed graphs with a specific curvature bound.
method Characterization via gradient estimate and transportation inequality for the heat semigroup.
result Concentration of measure inequality for directed graphs with positive Ricci curvature.
Paper studies metric ribbon graphs and provides a recursion for their volumes.
problem Calculating volumes of combinatorial moduli spaces of directed metric ribbon graphs.
method Decomposes directed ribbon graphs into simpler graphs with one vertex, proving a canonical recursion scheme for volumes.
result Explicit recursion for volumes of four-valent metric ribbon graphs provided.
Summarizing large-scaled directed graphs into small-scale representations is a useful but less studied problem setting. Conventional clustering approaches, which based on "Min-Cut"-style criteria, compress both the vertices and edges of the graph into the communities, that lead to a loss of directed edge information. O…
Maximal diameter theorem for graphs with positive Ricci curvature.
problem Diameter comparison in directed graphs with positive Ricci curvature.
method Introduced a Lin-Lu-Yau type Ricci curvature for directed graphs and investigated rigidity properties for the equality case.
result Concluded a maximal diameter theorem of Cheng type.
DIGRAC clusters directed graphs using flow imbalance, outperforming existing methods.
problem Clustering directed networks without label supervision.
method DIGRAC uses a graph neural network with a novel imbalance loss for directed flow imbalance.
result DIGRAC outperforms 10 state-of-the-art methods on directed graph clustering.
In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality…
We analyze directed, unweighted graphs obtained from xi∈Rd by connecting vertex i to j iff ∣xi−xj∣<ε(xi). Examples of such graphs include k-nearest neighbor graphs, where ε(xi) varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whethe…
We propose a novel node embedding of directed graphs to statistical manifolds, which is based on a global minimization of pairwise relative entropy and graph geodesics in a non-linear way. Each node is encoded with a probability density function over a measurable space. Furthermore, we analyze the connection between th…
AB-SAGA optimizes distributed optimization over directed graphs using variance reduction and stochastic weights.
problem Optimizing distributed stochastic optimization over directed graphs with stochastic weights.
method AB-SAGA combines variance reduction and network-level gradient tracking, using both row and column stochastic weights.
result AB-SAGA converges linearly to the global optimal with a constant step-size and achieves a linear speed-up over centralized methods.
TSAM predicts directed temporal links using GCN and self-attention.
problem Predicting links in directed temporal networks.
method GCN, self-attention mechanism, autoencoder architecture, graph attentional layers, graph convolutional layers, graph recurrent unit layer.
result TSAM outperforms benchmarks on four realistic networks.
For undirected graphs, the Ricci curvature introduced by Lin-Lu-Yau has been widely studied from various perspectives, especially geometric analysis. In the present paper, we discuss generalization problem of their Ricci curvature for directed graphs. We introduce a new generalization by using the mean transition proba…
New representations defined for groups and graphs, with applications to stable representations.
problem Defining and constructing new types of representations for groups and graphs.
method Introducing (R,Λ)-directed Anosov representations and using Fock-Goncharov positivity to construct them. result Constructs large families of primitive stable representations from F2 to PGL(V), including non-discrete and non-faithful examples. ParPIC clusters directed graphs using random walks and diffusion operators.
problem Challenges in vertex-level clustering for directed graphs due to edge directionality.
method Parametrized Power-Iteration Clustering (ParPIC) based on reversible random walks and diffusion operators.
result ParPIC achieves competitive clustering accuracy with improved scalability compared to spectral and teleportation-based methods.
We present a method to generate directed acyclic graphs (DAGs) using deep reinforcement learning, specifically deep Q-learning. Generating graphs with specified structures is an important and challenging task in various application fields, however most current graph generation methods produce graphs with undirected edg…
Quantum spheres' groupoid structure revealed.
problem Identifying the groupoid structure of quantum spheres.
method Comparing path groupoids of quantum spheres with Sheu's groupoid.
result Path groupoid of quantum spheres is isomorphic to Sheu's groupoid.
A new metric based on hitting probabilities for directed graphs and Markov chains.
problem Lack of metrics specifically adapted to asymmetric structure of directed graphs and Markov chains.
method Metric based on hitting probabilities, insensitive to shortest and average walk distances.
result New structural theory of directed graphs and utility for various applications.
Graph embedding algorithms are used to efficiently represent (encode) a graph in a low-dimensional continuous vector space that preserves the most important properties of the graph. One aspect that is often overlooked is whether the graph is directed or not. Most studies ignore the directionality, so as to learn high-q…
GG-SAGE predicts links in directed graphs with attributes, outperforming existing methods.
problem Predicting links in directed graphs with node attributes.
method Gravity-GraphSAGE, a modified GraphSAGE model with a gravity-inspired decoder.
result GG-SAGE outperforms state-of-the-art GDL link prediction techniques.
Generalizes k-means to graphs using PageRank.
problem Clustering nodes in directed and undirected graphs.
method Utilizes PageRank to compute node centrality in graphs.
result Robustly computes centrality in graphs and metric spaces.
Many signals on Cartesian product graphs appear in the real world, such as digital images, sensor observation time series, and movie ratings on Netflix. These signals are "multi-dimensional" and have directional characteristics along each factor graph. However, the existing graph Fourier transform does not distinguish …
Online CPD for weighted and directed graphs using RDPG model.
problem Monitoring and detecting changes in weighted and directed graph data.
method Spectral embeddings of RDPG models for online updates and error-rate control.
result A lightweight online CPD algorithm with improved detection resolution and delay.