$σ$-Maximal Ancestral Graphs

• URL: http://arxiv.org/abs/2507.00093v1
• Date: Mon, 30 Jun 2025 10:08:21 GMT
• Title: $σ$-Maximal Ancestral Graphs
• Abstract summary: We introduce and study a class of graphical objects that we coin ''$sigma$-Maximal Ancestral Graphs'' (''$sigma$-MAGs'')<n>These graphical objects encode information about ancestral relations and d-separations of Directed Acyclic Graphs (DAGs)<n>We show how these graphs provide an abstract representation of Directed Graphs with latent (selection) variables, analogous to how MAGs represent DAGs.
• Score: 1.6574413179773764
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximal Ancestral Graphs (MAGs) provide an abstract representation of Directed Acyclic Graphs (DAGs) with latent (selection) variables. These graphical objects encode information about ancestral relations and d-separations of the DAGs they represent. This abstract representation has been used amongst others to prove the soundness and completeness of the FCI algorithm for causal discovery, and to derive a do-calculus for its output. One significant inherent limitation of MAGs is that they rule out the possibility of cyclic causal relationships. In this work, we address that limitation. We introduce and study a class of graphical objects that we coin ''$\sigma$-Maximal Ancestral Graphs'' (''$\sigma$-MAGs''). We show how these graphs provide an abstract representation of (possibly cyclic) Directed Graphs (DGs) with latent (selection) variables, analogously to how MAGs represent DAGs. We study the properties of these objects and provide a characterization of their Markov equivalence classes.

Related papers

• DiPhon: Diffusion on Graphons for Scalable Graph Generation [100.75398811422308]
  Diffusion models represent a leading paradigm for graph generation, with notable impact in domains such as molecular design.<n>We propose DiPhon, a discretized graph-level process that mimics these dynamics on finite graphs.<n>We prove that DiPhon matches exactly the first moment of the marginal distributions induced by the continuous graphon process, and approximates the second moment up to a closed-form discrepancy.
  arXiv  Detail & Related papers  (2026-07-08T10:15:17Z)
• SWING: Unlocking Implicit Graph Representations for Graph Random Features [57.956136773668476]
  We propose SWING: Space Walks for Implicit Network Graphs, a new class of algorithms for computations involving Graph Random Features on graphs.<n>We provide detailed analysis of SWING and complement it with thorough experiments on different classes of i-graphs.
  arXiv  Detail & Related papers  (2026-02-13T08:12:38Z)
• On Approximate MMS Allocations on Restricted Graph Classes [0.31457219084519]
  We study the problem of fair division of a set of indivisible goods with connectivity constraints.<n>It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist.<n>We show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
  arXiv  Detail & Related papers  (2025-08-08T14:17:44Z)
• What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs [69.48708136448694]
  Large language models (LLMs) are reorganizing in the AI community for their expected reasoning and inference abilities.<n>We believe this kind of parametric representation of graphs, graph laws, can be a solution for making LLMs understand graph data as the input.
  arXiv  Detail & Related papers  (2024-10-16T00:01:31Z)
• Probing Graph Representations [77.7361299039905]
  We use a probing framework to quantify the amount of meaningful information captured in graph representations. Our findings on molecular datasets show the potential of probing for understanding the inductive biases of graph-based models. We advocate for probing as a useful diagnostic tool for evaluating graph-based models.
  arXiv  Detail & Related papers  (2023-03-07T14:58:18Z)
• Variational Graph Generator for Multi-View Graph Clustering [51.89092260088973]
  We propose Variational Graph Generator for Multi-View Graph Clustering (VGMGC)<n>This generator infers a reliable variational consensus graph based on a priori assumption over multiple graphs.<n>It embeds the inferred view-common graph and view-specific graphs together with features.
  arXiv  Detail & Related papers  (2022-10-13T13:19:51Z)
• A Prufer-Sequence Based Representation of Large Graphs for Structural Encoding of Logic Networks [0.30458514384586405]
  In this paper, we are primarily concerned with the inference that the structure of the graph influences the property of the real life system it represents. A model of such structural influence would be useful in inferencing useful properties of complex and large systems, like VLSI circuits.
  arXiv  Detail & Related papers  (2022-09-04T11:24:19Z)
• A Graph Convolution for Signed Directed Graphs [0.0]
  Graph convolutions for signed directed graphs have not been delivered much yet. We propose a novel complex Hermitian adjacency matrix that encodes graph information via complex numbers. To the best of our knowledge, it is the first spectral convolution for graphs with signs.
  arXiv  Detail & Related papers  (2022-08-23T01:58:35Z)
• Graph Filtration Kernels [3.325932244741268]
  We propose a family of graph kernels that incorporate existence intervals of features. We show that using Weisfeiler-Lehman labels over certain filtrations strictly increases the expressive power over the ordinary Weisfeiler-Lehman procedure.
  arXiv  Detail & Related papers  (2021-10-22T15:51:10Z)
• Topology-aware Tensor Decomposition for Meta-graph Learning [33.70569156426479]
  A common approach for extracting useful information from heterogeneous graphs is to use meta-graphs. We propose a new viewpoint from tensor on learning meta-graphs. We also propose a topology-aware tensor decomposition, called TENSUS, that reflects the structure of DAGs.
  arXiv  Detail & Related papers  (2021-01-04T16:38:00Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• Inverse Graph Identification: Can We Identify Node Labels Given Graph Labels? [89.13567439679709]
  Graph Identification (GI) has long been researched in graph learning and is essential in certain applications. This paper defines a novel problem dubbed Inverse Graph Identification (IGI) We propose a simple yet effective method that makes the node-level message passing process using Graph Attention Network (GAT) under the protocol of GI.
  arXiv  Detail & Related papers  (2020-07-12T12:06:17Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  Graph convolutional networks (GCNs) are a widely used method for graph representation learning. We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
  arXiv  Detail & Related papers  (2020-02-13T17:58:42Z)

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.