Beyond symmetrization: effective adjacency matrices and renormalization for (un)singed directed graphs

• URL: http://arxiv.org/abs/2406.01517v1
• Date: Mon, 3 Jun 2024 16:48:25 GMT
• Title: Beyond symmetrization: effective adjacency matrices and renormalization for (un)singed directed graphs
• Abstract summary: We define the concept of effective adjacency matrices that arise from the definition of deformed Laplacian operators. These effective matrices allow mapping generic graphs to a family of unsigned, undirected graphs. We show how the Hodge-Helmholtz decomposition can assist us in navigating this complexity.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To address the peculiarities of directed and/or signed graphs, new Laplacian operators have emerged. For instance, in the case of directionality, we encounter the magnetic operator, dilation (which is underexplored), operators based on random walks, and so forth. The definition of these new operators leads to the need for new studies and concepts, and consequently, the development of new computational tools. But is this really necessary? In this work, we define the concept of effective adjacency matrices that arise from the definition of deformed Laplacian operators such as magnetic, dilation, and signal. These effective matrices allow mapping generic graphs to a family of unsigned, undirected graphs, enabling the application of the well-explored toolkit of measures, machine learning methods, and renormalization groups of undirected graphs. To explore the interplay between deformed operators and effective matrices, we show how the Hodge-Helmholtz decomposition can assist us in navigating this complexity.

Related papers

• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• Function graph transformers universally approximate operators between function spaces [14.886643480836817]
  We study the approximation of nonlinear operators between function spaces by transformers.<n>Our approach is to lift functions to measures supported on their graphs and leverage a recently introduced measure-theoretic view of transformers.<n>We show that this framework models discretization refinement via convergence measures and provides a natural setting for operator learning.
  arXiv  Detail & Related papers  (2026-05-18T07:25:14Z)
• Topology Identification and Inference over Graphs [61.06365536861156]
  Topology identification and inference of processes evolving over graphs arise in timely applications involving brain, transportation, financial, power, as well as social and information networks.<n>This chapter provides an overview of graph topology identification and statistical inference methods for multidimensional data.
  arXiv  Detail & Related papers  (2025-12-11T00:47:09Z)
• Taxonomy of reduction matrices for Graph Coarsening [14.662574002430794]
  Graph coarsening aims to diminish the size of a graph to lighten its memory footprint.<n>Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrix.<n>We show that, for a fixed coarsening represented by a fixed lifting matrix, the RSA can be further reduced simply by modifying the reduction matrix.
  arXiv  Detail & Related papers  (2025-06-13T12:55:03Z)
• Position: Curvature Matrices Should Be Democratized via Linear Operators [6.946287154076936]
  Linear operators provide a general, scalable, and user-friendly abstraction to handle curvature matrices. $textitcurvlinops$ is a library that provides curvature matrices through a unified linear operator interface. We demonstrate with $textitcurvlinops$ how this interface can hide complexity, simplify applications, be interoperable with other libraries, and scale to large NNs.
  arXiv  Detail & Related papers  (2025-01-31T14:46:30Z)
• Learning signals defined on graphs with optimal transport and Gaussian process regression [1.1062090350704616]
  In computational physics, machine learning has emerged as a powerful complementary tool to explore efficiently candidate designs in engineering studies. We propose an innovative strategy for Gaussian process regression where inputs are large and sparse graphs with continuous node attributes and outputs are signals defined on the nodes of the associated inputs. In addition to enabling signal prediction, the main point of our proposal is to come with confidence intervals on node values, which is crucial for uncertainty and active learning.
  arXiv  Detail & Related papers  (2024-10-21T07:39:44Z)
• Representing Edge Flows on Graphs via Sparse Cell Complexes [6.74438532801556]
  We introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells. We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution.
  arXiv  Detail & Related papers  (2023-09-04T14:30:20Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Transfer operators on graphs: Spectral clustering and beyond [1.147633309847809]
  We show that spectral clustering of undirected graphs can be interpreted in terms of eigenfunctions of the Koopman operator. We propose novel clustering algorithms for directed graphs based on generalized transfer operators.
  arXiv  Detail & Related papers  (2023-05-19T15:52:08Z)
• Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Prior [1.2891210250935143]
  We derive an analytically tractable Bayesian method that uses repeated interactions and a topological prior to infer transition matrices data-efficiently. We show that it recovers the transition probabilities with higher accuracy and that it is robust even in cases when the knowledge of the topological constraint is partial.
  arXiv  Detail & Related papers  (2022-10-27T13:17:47Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Graph Kernel Neural Networks [53.91024360329517]
  We propose to use graph kernels, i.e. kernel functions that compute an inner product on graphs, to extend the standard convolution operator to the graph domain. This allows us to define an entirely structural model that does not require computing the embedding of the input graph. Our architecture allows to plug-in any type of graph kernels and has the added benefit of providing some interpretability.
  arXiv  Detail & Related papers  (2021-12-14T14:48:08Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, and graph visualization tasks.
  arXiv  Detail & Related papers  (2020-03-10T02:33:14Z)
• Supervised Quantile Normalization for Low-rank Matrix Approximation [50.445371939523305]
  We learn the parameters of quantile normalization operators that can operate row-wise on the values of $X$ and/or of its factorization $UV$ to improve the quality of the low-rank representation of $X$ itself. We demonstrate the applicability of these techniques on synthetic and genomics datasets.
  arXiv  Detail & Related papers  (2020-02-08T21:06:02Z)
• Graph Representation Learning via Graphical Mutual Information Maximization [86.32278001019854]
  We propose a novel concept, Graphical Mutual Information (GMI), to measure the correlation between input graphs and high-level hidden representations. We develop an unsupervised learning model trained by maximizing GMI between the input and output of a graph neural encoder.
  arXiv  Detail & Related papers  (2020-02-04T08:33:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.