New method learns graph structure with hidden causes from observational data.
problem Learning the structure of linear non-Gaussian models with hidden causes.
method Augments hidden variable structure by learning multidirected edges and uses higher order cumulants.
result Correct structure recovery for bow-free acyclic mixed graphs with multi-directed edges.
Paper addresses hidden faces in configuration space integrals for embeddings.
problem Understanding hidden faces in configuration space integrals for long embeddings.
method Modified configuration space integrals incorporating acyclic bar complex of a dg algebra.
result Cochain map from new graph complex to de Rham complex of embeddings modulo immersions.
Graph Ricci flow reveals hidden hierarchies in stock market correlations.
problem Detecting hidden structures in the complex stock market graph.
method Using graph Ricci curvature and flow techniques to analyze the NASDAQ 100 index.
result Algorithm detects hidden hierarchies, community behavior, and clustering in financial markets.
The paper studies recovering hidden nearest neighbor graphs in large networks.
problem Discovering strong ties in social networks and assembling genome subsequences.
method Maximum likelihood estimator for recovering hidden 2k-nearest neighbor graphs. result The maximum likelihood estimator achieves asymptotic recovery guarantees under specific conditions.
Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.
The study finds conditions for compressing the hidden dimension of Graph Transformers for transductive learning.
problem The challenge of efficiently analyzing and training Graph Transformers for transductive learning.
method Theoretical bounds on hidden dimension compression for Graph Transformers, considering both sparse and dense variants.
result Theoretical findings on how and under what conditions the hidden dimension of Graph Transformers can be compressed.
CoulGAT interprets GAT models by analyzing node interactions.
problem Understanding and interpreting the complex interactions within graph attention networks.
method Developed a CoulGAT framework to analyze and interpret GAT model layers and datasets.
result Extracted node-node and node-feature interactions to define a standard model for graph structure.
Polynomial delay algorithm tests causal models with hidden variables.
problem Testing causal models with hidden variables in polynomial delay.
method c-component local Markov property (C-LMP) and polynomial delay algorithm.
result First algorithm for poly-delay testing of CIs in causal graphs with hidden variables.
FEALM learns features for better nonlinear DR of hidden patterns.
problem DR misses important patterns on distorted manifolds.
method FEALM generates optimized projections using an optimization algorithm and neighbor-shape dissimilarity.
result FEALM captures important patterns on hidden manifolds.
This work presents entropic constraints from DAGs with hidden variables.
problem Characterizing causal relations in systems with hidden variables.
method Entropic inequality constraints derived from e-separation relations. result These constraints can learn about true causal models from observed data.
This paper extends stable blanket theory to models with hidden variables and causal cycles.
problem Identifying stable predictors in models with hidden variables and causal cycles.
method Use acyclic directed mixed graphs (ADMGs) and directed graphs (DGs) with m-separation and σ-separation to characterize and construct intervention-stable predictor sets. result Graphical characterizations of Markov blankets, stable frontiers, and stable blankets in models with hidden variables and cycles.
Study optimal adjustment sets for causal policies with hidden variables.
problem Estimating dynamic treatment regimes with hidden variables.
method Developed criteria for graphs without hidden variables to compare estimators, extended to dynamic policies and hidden variables.
result Existence and computation of optimal minimal and globally optimal adjustment sets.
We propose a framework to model the distribution of sequential data coming from a set of entities connected in a graph with a known topology. The method is based on a mixture of shared hidden Markov models (HMMs), which are jointly trained in order to exploit the knowledge of the graph structure and in such a way that …
Improved graph embedding through refined linear transformation and community recovery.
problem Identifying meaningful latent communities in graph data.
method Refined graph encoder embedding via linear transformation, self-training, and latent community recovery.
result Improved vertex embedding and better decision boundaries for vertex classification.
While neural networks are powerful approximators used to classify or embed data into lower dimensional spaces, they are often regarded as black boxes with uninterpretable features. Here we propose Graph Spectral Regularization for making hidden layers more interpretable without significantly impacting performance on th…
The paper analyzes GNNs with one hidden layer, proving their generalizability and convergence rate.
problem Theoretical guarantee on generalizability of GNNs with one hidden layer.
method Tensor initialization and accelerated gradient descent.
result The proposed learning algorithm converges to the ground-truth GNN model for regression and to a model close to the ground-truth for binary classification.
Bayesian networks with hidden variables help identify causal relationships obscured by confounding.
problem Identifying causal relationships obscured by unobserved confounders.
method Use finite k-mixtures of Bayesian networks with hidden variables to recover the joint probability distribution and identify causal relationships. result First algorithm to learn mixtures of non-empty DAGs, recovering identifiable causal relationships.
New method detects corporate fraud in noisy financial networks.
problem Detecting corporate fraud in rich yet noisy financial networks.
method Knowledge-enhanced GCN with Robust Two-stage Learning (KeGCN_R)
result KeGCN_R outperforms baselines in fraud detection effectiveness and robustness.
VACA models graph data for causal inference without hidden confounders.
problem Causal inference in observational data with hidden confounders.
method Variational graph autoencoders for structural causal models.
result Accurately approximates interventional and counterfactual distributions.
CgNN uses network structure as IVs to estimate causal effects in networks.
problem Hidden confounders complicate causal effect estimation in network data.
method CgNN combines GNNs and attention mechanisms to leverage network structure as IVs.
result CgNN effectively mitigates hidden confounder bias and improves causal effect estimation.
Paper introduces HGSL for heterogeneous graphs, improving edge type and weight recovery.
problem Learning structure in heterogeneous graphs with multiple node and edge types.
method Proposes H2MN model for DGPs and derives alternating optimization method.
result Demonstrates superior performance on synthetic and real-world datasets.
Consider a finite connected graph possibly with multiple edges and loops. In discrete geometric analysis, Kotani and Sunada constructed the crystal associated to the graph as a standard realization of the maximal abelian covering of the graph. As an application of what the author showed in an earlier paper with Seshadr…
Ancestral graph models, introduced by Richardson and Spirtes (2002), generalize both Markov random fields and Bayesian networks to a class of graphs with a global Markov property that is closed under conditioning and marginalization. By design, ancestral graphs encode precisely the conditional independence structures t…
Study on detecting and recovering hidden dense cycles in random graphs.
problem Detecting and recovering hidden dense cycles in random graphs.
method Information-theoretic analysis of thresholds for detection and recovery.
result Characterization of information-theoretic thresholds for detection and recovery.
A colored graph is a directed graph in which nodes or edges have been assigned colors that are not necessarily unique. Observability problems in such graphs consider whether an agent observing the colors of edges or nodes traversed on a path in the graph can determine which node they are at currently or which nodes wer…
This paper sets thresholds for recovering vertex correspondences in partially correlated graphs.
problem Recovering hidden vertex correspondences in partially correlated graphs.
method Proposed partially correlated Erdős-Rényi graphs model; information-theoretic thresholds; correlated functional digraphs.
result Optimal rates for partial and exact recovery of vertex correspondences.
AEGCN uses autoencoder constraints to improve graph node classification.
problem Node classification on graph domains with reduced information loss.
method Autoencoder-constrained graph convolutional network (AEGCN).
result Adding autoencoder constraints significantly improves graph convolutional network performance.
Automatic methods for generating state-of-the-art neural network architectures without human experts have generated significant attention recently. This is because of the potential to remove human experts from the design loop which can reduce costs and decrease time to model deployment. Neural architecture search (NAS)…
We provide a classification of graphical models according to their representation as subfamilies of exponential families. Undirected graphical models with no hidden variables are linear exponential families (LEFs), directed acyclic graphical models and chain graphs with no hidden variables, including Bayesian networks …
Universal MLPs with a single hidden layer can learn any function.
problem Learning on various data structures like sequences, images, sets, and graphs.
method Using group theory, the paper proves the universality of a broad class of equivariant MLPs with a single hidden layer.
result Having a hidden layer on which the group acts regularly is sufficient for universal equivariance (invariance).
LP-SparseMAP relaxes SparseMAP for more complex structures.
problem SparseMAP's tractable MAP inference oracle limits its applicability.
method Local polytope relaxation for factor graphs.
result LP-SparseMAP outperforms SparseMAP and Structured SVM in structured prediction tasks.
We present a scalable approach for semi-supervised learning on graph-structured data that is based on an efficient variant of convolutional neural networks which operate directly on graphs. We motivate the choice of our convolutional architecture via a localized first-order approximation of spectral graph convolutions.…
Identifying causal direction in location-scale noise models with hidden variables
problem Causal discovery in location-scale noise models with hidden variables
method ADMGs satisfying a bow-free condition
result First identifiability result for causally insufficient models beyond noise additivity
The graph braid group of a complete bipartite graph is the fundamental group of a configuration space of points on the graph, which is a CAT(0) cube complex. We combine an analysis of the topology of links of vertices in this complex, the description of a hidden symmetry among the parameters, and known results from the…
Amortized Causal Discovery learns to infer causal graphs from time-series data, improving performance.
problem Inference of causal graphs from time-series data is inefficient due to fitting new models for each sample.
method Proposes Amortized Causal Discovery, a variational model that leverages shared dynamics across samples with different causal graphs.
result Significant improvements in causal discovery performance demonstrated experimentally.
We consider the problem where an agent wants to find a hidden object that is randomly located in some vertex of a directed acyclic graph (DAG) according to a fixed but possibly unknown distribution. The agent can only examine vertices whose in-neighbors have already been examined. In this paper, we address a learning s…
New framework for dynamic causal graph modeling and effect estimation.
problem Dynamic changes in causal relationships over time.
method Score-based causal discovery with autoregressive model structure.
result Dynamic causal graph with time-varying causal relations.
The paper bounds the complexity of GCNs using Rademacher complexity.
problem Understanding the sample complexity of GCNs.
method Derived tight upper and lower bounds of Rademacher complexity for GCN models.
result The derived bounds depend on the largest eigenvalue of the graph filter and the degree distribution.
New method identifies latent causal graphs without parametric assumptions.
problem Identifying latent causal graphs without parametric assumptions.
method Constructive proofs with new graphical concepts.
result Conditions for nonparametric identification of latent causal graphs.
New results on inferring hidden states in trackable weak models.
problem Inferring hidden states in trackable weak models.
method Analyzing strongly-connected trackable weak models and reconstructing branch choices.
result The number of hypotheses in strongly-connected trackable models is bounded by a constant.
Graph neural controlled differential equations learn graph dynamics from vertex observations.
problem Predicting future states of dynamical systems on graphs with limited vertex data.
method Incorporates graph topology information into NCDE to predict graph dynamics.
result Informed NCDE requires fewer parameters and lower MAE compared to previous methods.
New methods for estimating causal effects in hidden variable DAGs.
problem Estimating causal effects in models with hidden variables.
method Influence function based estimators for causal effects in hidden variable DAGs.
result Achieves semiparametric efficiency bounds for identifiable effects.
In this paper we investigate the geometry of the likelihood of the unknown parameters in a simple class of Bayesian directed graphs with hidden variables. This enables us, before any numerical algorithms are employed, to obtain certain insights in the nature of the unidentifiability inherent in such models, the way pos…
Machine learning provides algorithms that can learn from data and make inferences or predictions on data. Bayesian networks are a class of graphical models that allow to represent a collection of random variables and their condititional dependencies by directed acyclic graphs. In this paper, an inference algorithm for …
Ring-reservoir networks simplify graph embeddings efficiently.
problem Efficient graph embeddings using deep neural networks.
method Progressive simplification of Reservoir Computing models to ring topology.
result Ring-reservoir networks show consistent advantages in predictive performance.
Paper shows graphs can be embedded in lower dimensions than expected.
problem Choosing the right embedding dimension for graph analysis.
method Utilizes hidden manifold structure to predict lower-dimensional embedding.
result Graphs can be embedded in much lower dimensions than previously thought.
New model handles complex non-linear relationships with hidden graph structures.
problem Modeling non-linear relationships with hidden graph-structured interactions.
method Block-diagonal localized mixture of polynomial experts (BLoMPE) regression model with penalized maximum likelihood selection criterion.
result Strong theoretical guarantee for finite-sample oracle inequality.
GLFA improves latent factor analysis by incorporating graph structures for HiDS matrices.
problem Accurate representation learning on high-dimensional and sparse matrices.
method GLFA incorporates a graph to identify hidden high-order interactions and uses a recurrent LFA structure to improve representation learning.
result GLFA outperforms state-of-the-art models in predicting missing data of HiDS matrices.