We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “Chordal Skeleton”
We consider the problem of learning causal networks with interventions, when each intervention is limited in size under Pearl's Structural Equation Model with independent errors (SEM-IE). The objective is to minimize the number of experiments to discover the causal directions of all the edges in a causal graph. Previou…
Develops a method to efficiently learn causal DAGs using directed clique trees.
problem Efficiently learning causal DAGs in the presence of large cliques.
method Decomposes DAGs into independently orientable components using directed clique trees and designs a two-phase intervention algorithm.
result Proves that the number of single-node interventions necessary to orient any DAG in an EC is at least the sum of half the size of the largest cliques in each chain component of the essential graph.
We prove several results about chordal graphs and weighted chordal graphs by focusing on exposed edges. These are edges that are properly contained in a single maximal complete subgraph. This leads to a characterization of chordal graphs via deletions of a sequence of exposed edges from a complete graph. Most interesti…
Chordal graphs can be used to encode dependency models that are representable by both directed acyclic and undirected graphs. This paper discusses a very simple and efficient algorithm to learn the chordal structure of a probabilistic model from data. The algorithm is a greedy hill-climbing search algorithm that uses t…
A new invariant captures geometric features of circle embeddings.
problem Capturing geometric features of circle embeddings invariantly.
method Chordal distance transform and persistent homology.
result Persistent homology of chordal distance transform is invariant.
A highly influential ingredient of many techniques designed to exploit sparsity in numerical optimization is the so-called chordal extension of a graph representation of the optimization problem. The definitive relation between chordal extension and the performance of the optimization algorithm that uses the extension …
Geodesic rays and chordal distances link algebraic and geometric properties of positive metrics.
problem Understanding the geometry of the space of positive metrics at infinity.
method Using Monge-Ampère equations and test configurations, algebraic descriptions of geodesic rays and chordal distances are derived.
result The Mabuchi chordal distance between geodesic rays associated with ample test configurations equals the spectral distance between their filtrations.
We study the class N of graphs, the right-angled Artin groups defined on which do not contain surface subgroups. We prove that a presumably smaller class N' is closed under amalgamating along complete subgraphs, and also under adding bisimplicial edges. It follows that chordal graphs and chordal bipartite graphs belong…
New algorithms bound graph structure sampling and learning high-dimensional graphical models.
problem Learning high-dimensional graphical models and efficient graph structure sampling.
method Online learning framework with exponentially weighted average (EWA) or randomized weighted majority (RWM) forecasters using log loss function.
result New sample complexity bounds and efficient algorithms for learning Bayes nets, including trees and chordal skeletons.
New metric spaces for geodesic rays in cohomology classes.
problem Constructing geodesic rays in cohomology classes with finite energy.
method Introduced a chordal metric and proved geodesic properties.
result Found a characterization of geodesic rays in terms of test curves.
In this paper, we consider the Graphical Lasso (GL), a popular optimization problem for learning the sparse representations of high-dimensional datasets, which is well-known to be computationally expensive for large-scale problems. Recently, we have shown that the sparsity pattern of the optimal solution of GL is equiv…
In this paper we characterize compact extended Ptolemy metric spaces with many circles up to Möbius equivalence. This characterization yields a Möbius characterization of the -dimensional spheres and hemispheres when endowed with their chordal metrics. In particular, we show that every compact extended…
New algorithm computes flag mean and median on flag manifolds.
problem Computing first order flag statistics on flag manifolds.
method Transformed problem to Stiefel manifold for optimization.
result Proved convergence and effectiveness of the flag-mean computation.
SPOT improves differentiable causal discovery by estimating skeleton posterior for latent confounders.
problem Scalable and accurate estimation of causal skeletons in the presence of latent confounders.
method SPOT (Skeleton Posterior-guided OpTimization) framework that estimates skeleton posterior and integrates it with differentiable causal discovery.
result SPOT enhances differentiable causal discovery by reducing the search space and improving accuracy.
The study examines the topology of complements of polytopal skeletons.
problem Characterizing topological properties of polytopal complexes and their skeletons.
method Constructing a long exact sequence relating homologies of skeleton complements and links of faces.
result Characterizations of Cohen-Macaulay and Leray complexes, stacked balls, and neighbourly spheres in terms of skeleton complements.
New method simplifies causal inference with tiered background knowledge.
problem Large equivalence classes of DAGs limit causal information.
method Integrates tiered background knowledge to create 'tiered MPDAGs' with simplified structure.
result Tiered MPDAGs are chain graphs with chordal components, simplifying causal effect estimation.
Criterion for manifold skeletons embeddability in Euclidean space.
problem Embeddability of manifold skeletons in Euclidean space.
method Criterion based on the complement of a submanifold.
result Embeddability of -skeleton of a triangulation of an -bundle over into .
Completing correlation matricesq-fin.MF
A method to complete incomplete correlation matrices using maximum entropy.
problem Incomplete correlation matrices in financial applications.
method Maximizing entropy of the distribution described by the matrix, constructing a chordal graph.
result A proper correlation matrix can be constructed for large models involving multiple currencies.
Skeleton is a new notion designed for constructing space-filling curves of self-similar sets. It is shown in [Dai, Rao and Zhang, Space-filling curves of self-similar sets (II): Edge-to-trail substitution rule,https://doi.org/10.1088/1361-6544/ab1275] that for a connected self-similar set, space-filling curves can be c…
We have completely rewritten the paper, and corrected the proofs. We construct an exponential map at any point in the (n-1)-skeleton minus the (n-2)-skeleton of an n-dimensional Riemannian polyhedron. We have added allover the extra-assumption that the exponential map is totally geodesic at points in the (n-1)-skeleton…
The extension functors between categories of Cartan geometries can be used to define different categories of Cartan geometries with additional morphisms. The Cartan geometries modeled on skeletons can be used for the description of such categories of Cartan geometries and therefore we develop the theory of Cartan geome…
Undirected graphical models known as Markov networks are popular for a wide variety of applications ranging from statistical physics to computational biology. Traditionally, learning of the network structure has been done under the assumption of chordality which ensures that efficient scoring methods can be used. In ge…
Fixed point sets of certain group actions are contractible.
problem Fixed point sets of group actions on specific types of complexes.
method Analyzing group actions on diagrammatically reducible complexes with fine 1-skeleton.
result Fixed point sets are contractible under certain conditions.
We prove that for all a shellable -dimensional simplicial complex with at most vertices is extendably shellable. The proof involves considering the structure of `exposed' edges in chordal graphs as well as a connection to linear quotients of quadratic monomial ideals.
Skeleton clustering detects clusters in high-dimensional data without needing prototypes.
problem Detecting clusters in high-dimensional data with irregular shapes.
method Skeleton clustering combines prototype methods, density-based clustering, and hierarchical clustering using surrogate density measures.
result Skeleton clustering reliably detects clusters in multivariate and high-dimensional data.
A new method scores contextual Markov networks without assuming chordality.
problem Learning structure in contextual Markov networks is hard due to many possible structures.
method Marginal pseudo-likelihood as a consistent structure estimator.
result Marginal pseudo-likelihood yields a consistent structure estimator.
Tensor-based method simplifies causal skeleton discovery.
problem Discover causal relationships between variables.
method Express associations as tensors to reduce dimensionality.
result Causal skeleton can be determined using pair-wise tensors.
Efficiently learns polytrees with known skeleton in polynomial time and sample complexity.
problem Learning polytrees with known skeleton structure.
method Proposes an efficient algorithm for learning -polytrees in polynomial time and sample complexity when the skeleton is known.
result Establishes finite-sample guarantees for efficient learning of -polytrees.
New theorem shows embedding restrictions for manifold skeletons.
problem Embedding restrictions for triangulated manifolds.
method Proves van Kampen-Flores theorem for manifolds with specific Stiefel-Whitney classes.
result Triangulated manifolds with non-trivial Stiefel-Whitney classes cannot embed into .
The Bezier simplex fitting is a novel data modeling technique which exploits geometric structures of data to approximate the Pareto front of multi-objective optimization problems. There are two fitting methods based on different sampling strategies. The inductive skeleton fitting employs a stratified subsampling from e…
Node-link diagrams are a popular method for representing graphs that capture relationships between individuals, businesses, proteins, and telecommunication endpoints. However, node-link diagrams may fail to convey insights regarding graph structures, even for moderately sized data of a few hundred nodes, due to visual …
Our main theorem identifies a class of totally geodesic subgraphs of the 1-skeleton of the pants complex, each isomorphic to the product of two Farey graphs. We deduce the existence of many convex planes in the 1-skeleton of the pants complex.
We are enveloped by stories of visual interpretations in our everyday lives. The way we narrate a story often comprises of two stages, which are, forming a central mind map of entities and then weaving a story around them. A contributing factor to coherence is not just basing the story on these entities but also, refer…
New method certifies risks of LLM outputs, improving accuracy and reliability.
problem Uncertain and incorrect outputs from large language models.
method Information-lift certificates using PAC-Bayes bounds and skeleton design.
result Achieves 77.0% coverage at 2% risk, outperforming baselines.
The present paper is devoted to the joint motion of two immiscible incompressible liquids in porous media. The liquids have different densities and initially separated by a surface of strong discontinuity (free boundary). We discuss the results of numerical simulations for exact free boundary problems on the microscopi…
Proposes a neural network for recognizing 3D skeleton-based interactions.
problem Recognizing two-person interactions from 3D skeleton sequences.
method Uses Gaussian distributions and Riemannian geometry of SPD matrices and matrix groups.
result Achieves competitive results on three benchmarks for 3D human activity understanding.
The paper finds and visualizes unique geometric polyhedra and tori with few vertices.
problem Finding and visualizing geometric polyhedra and tori with specific vertex configurations.
method Using Schlegel diagrams and geometric realization in 3D and 4D space.
result Identifies and visualizes 12 triangulations of the 2-torus and 12 triangulations of the 2D projective plane.
We create a 3-skeleton for a symmetric group's classifying space.
problem Classifying space construction for symmetric groups.
method Combining rewriting systems and combinatorial methods.
result Correctness of the constructed 3-skeleton.
A new graph-based approach for estimating complex data with manifold structure.
problem Regression of large-scale, complex data with underlying geometric structure and noises.
method Constructing a skeleton graph to capture geometric structure, defining metrics, and applying nonparametric regression.
result Statistical guarantees and effectiveness demonstrated through simulations and real data examples.
A method for learning skeleton of Bayesian networks robust to outliers and corruption.
problem Learning the exact skeleton of discrete Bayesian networks from corrupted data.
method Distributionally robust optimization and regression approach, optimizing worst-case risk over distributions within bounded Wasserstein distance or KL divergence.
result Logarithmic sample complexities for successful structure learning of bounded-degree graphs.
We show that closed arithmetic hyperbolic n-dimensional orbifolds with larger and larger volumes give rise to triangulations of the underlying spaces whose 1-skeletons are harder and harder to embed nicely in Euclidean space. To show this we generalize an inequality of Gromov and Guth to hyperbolic n-orbifolds and find…
Every cubic graph is a bridge trisection's 1-skeleton for a knotted surface.
problem Understanding cubic graphs and their relation to bridge trisections.
method Proving every Tait-colored cubic graph is a 1-skeleton of a bridge trisection.
result Every Tait-colored cubic graph corresponds to a bridge trisection of a knotted surface.
On a Weinstein manifold, we define a constructible co/sheaf of categories on the skeleton. The construction works with arbitrary coefficients, and depends only on the homotopy class of a section of the Lagrangian Grassmannian of the stable symplectic normal bundle. The definition is as follows. Take any, possibly high …
The one-skeleton of a G-manifold M is the set of points p in M where ; and M is a GKM manifold if the dimension of this one-skeleton is 2. Goresky, Kottwitz and MacPherson show that for such a manifold this one-skeleton has the structure of a ``labeled" graph, , and that the equivariant…
Finite simplicial complexes dominate certain manifolds with a bounded number of simplices.
problem Understanding the finite domination of manifolds by simplicial complexes.
method Proving that a manifold can be dominated by the -skeleton of a finite simplicial complex with a bounded number of simplices.
result The total number of simplices in the -skeleton is bounded above by a constant depending only on and the embolic volume of the manifold.
We present a constructive proof that there exists a decomposition of the 2-skeleton of the k-dimensional cross polytope into closed surfaces of genus , each with a transitive automorphism group given by the vertex transitive -action on . Furthermore we show that for each $k \equiv …
Learning properties of large graphs from samples has been an important problem in statistical network analysis since the early work of Goodman \cite{Goodman1949} and Frank \cite{Frank1978}. We revisit a problem formulated by Frank \cite{Frank1978} of estimating the number of connected components in a large graph based …