Characterizing and Identifying Separable Graphical Models

• URL: http://arxiv.org/abs/2607.01057v1
• Date: Wed, 01 Jul 2026 15:22:03 GMT
• Title: Characterizing and Identifying Separable Graphical Models
• Abstract summary: We introduce separable graphs, in which each missing edge implies the existence of a separating set for its endpoints.<n>We show that these models include many existing graph families used to define graphical models.<n>We develop an algorithm that identifies the equivalence class of any essentially separable graph.
• Score: 3.3065613256340427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a broad class of graphical models whose independencies correspond to vertex separation in mixed graphs with directed, undirected, and bidirected edges, that are capable of encoding independence structures arising from feedback, latent and selection mechanisms. In particular, we introduce separable graphs, in which each missing edge implies the existence of a separating set for its endpoints, and essentially separable graphs, those graphs separation equivalent to a separable graph. We show that these models include many existing graph families used to define graphical models an provide several characterizations of separable graphs and essentially separable graphs. We also provide multiple characterizations of separation equivalence for separable graphs. One is a graphical characterization in terms of ordinary graph properties, extending earlier results for specific subfamilies Another is a separational characterization depending only on graph separation properties. Finally, we provide a canonical representation for the equivalence classes of essentially separable graphs and develop an algorithm that, under suitable assumptions, identifies the equivalence class of any essentially separable graph.

Related papers

• Diversity Curves for Graph Representation Learning [21.35846278198515]
  We show how to track the structural diversity of a graph across coarsening levels.<n>The resulting graph embeddings are interpretable by construction, efficient, and directly comparable.<n>We demonstrate their utility over a range of baseline methods in practice.
  arXiv  Detail & Related papers  (2026-05-07T15:55:20Z)
• Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra [6.164863213336097]
  We present a novel evolutionary approach to evolve graphs based on the Laplacian graph spectra descriptor.<n>Our experimental results show that our approach is successful for different classes of graphs and a wide range of Laplacian graph spectra.
  arXiv  Detail & Related papers  (2026-03-30T08:14:53Z)
• Graph Pattern-based Association Rules Evaluated Under No-repeated-anything Semantics in the Graph Transactional Setting [0.6599344783327054]
  We introduce graph pattern-based association rules (GPARs) for directed labeled multigraphs such as RDF graphs.<n>GPARs support both generative tasks, where a graph is extended, and evaluative tasks, where the plausibility of a graph is assessed.
  arXiv  Detail & Related papers  (2025-12-17T10:52:15Z)
• Graph-Dictionary Signal Model for Sparse Representations of Multivariate Data [49.77103348208835]
  We define a novel Graph-Dictionary signal model, where a finite set of graphs characterizes relationships in data distribution through a weighted sum of their Laplacians. We propose a framework to infer the graph dictionary representation from observed data, along with a bilinear generalization of the primal-dual splitting algorithm to solve the learning problem. We exploit graph-dictionary representations in a motor imagery decoding task on brain activity data, where we classify imagined motion better than standard methods.
  arXiv  Detail & Related papers  (2024-11-08T17:40:43Z)
• Renormalized Graph Representations for Node Classification [21.589472270424405]
  We analyze the effect of using different coarse-grained graph resolutions on node classification tasks.<n>We specifically experiment using representations at the characteristic scale of the graph's mesoscopic structures.<n>Our results showed that models with access to both the original graph and the characteristic scale graph can achieve statistically significant improvements in test accuracy.
  arXiv  Detail & Related papers  (2023-06-01T14:16:43Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Curvature Filtrations for Graph Generative Model Evaluation [11.55292147747249]
  Graph generative model evaluation requires understanding differences between graphs on the distributional level. Curvature constitutes one such property that has recently proved its utility in characterising graphs. We combine graph curvature descriptors with emerging methods from topological data analysis to obtain robust, expressive descriptors for evaluating graph generative models.
  arXiv  Detail & Related papers  (2023-01-30T14:10:30Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs [72.51835626235368]
  We argue that when comparing two graphs, the distribution of node structural features is more informative than global graph statistics. We present GraphDCA - a framework for evaluating similarity between graphs based on the alignment of their respective node representation sets.
  arXiv  Detail & Related papers  (2022-02-08T14:19:19Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Group Contrastive Self-Supervised Learning on Graphs [101.45974132613293]
  We study self-supervised learning on graphs using contrastive methods. We argue that contrasting graphs in multiple subspaces enables graph encoders to capture more abundant characteristics.
  arXiv  Detail & Related papers  (2021-07-20T22:09:21Z)

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.