Paper proposes learnable topological features for efficient phylogenetic inference.
problem Finding appropriate topological structures for phylogenetic inference tasks requires significant design effort and domain expertise.
method Combines raw node features with graph neural networks to automatically adapt to different tasks.
result Demonstrates effectiveness and efficiency on simulated and real data phylogenetic inference tasks.
This chapter covers methods for identifying and inferring graph topologies.
problem Identifying and inferring graph topologies from multidimensional relational data.
method Overview of methods including correlation metrics, covariance selection, kernels, structural equations, and vector autoregressions.
result Supports both batch and online learning with convergence guarantees and leverages high-order statistical information.
Proposes a method to infer complex network topologies from multiple graphs.
problem Learning multiple graph Laplacian matrices from heterogeneous graph signals with intricate topological patterns.
method Structured fusion regularization and ADMM algorithm for efficient computation.
result Establishes a non-asymptotic bound of the estimation error and reflects the effect of key factors on convergence rate.
Bayesian method infers transition matrices from incomplete graph data with topological constraints.
problem Inference of transition matrices from incomplete graph data with topological constraints.
method Bayesian approach using repeated interactions and a topological prior.
result Higher accuracy in inferring transition probabilities, improving downstream tasks.
Researchers create benchmarks to compare graph inference methods.
problem Comparing graph inference methods is difficult due to varying downstream tasks.
method Developed benchmarks for various graph tasks.
result Contrasted prominent graph inference techniques.
Estimates network topologies from shared graphon models across different networks.
problem Estimating the topology of multiple networks from nodal observations.
method Combining maximum likelihood penalty with graphon estimation schemes.
result Validated performance against competing methods in synthetic and real-world datasets.
This paper proposes a new method for learning covers of geometric datasets to improve topological inference and visualization.
problem Improving topological inference and visualization of large-scale geometric datasets.
method Proposes a method for learning topologically-faithful covers of geometric datasets using optimization.
result Simplicial complexes obtained from learned covers outperform standard methods in terms of size and representation of large-scale topology.
ARTree uses deep learning to infer tree topologies efficiently.
problem Efficient phylogenetic inference from tree topologies.
method Deep autoregressive model based on graph neural networks (GNNs).
result ARTree provides a flexible family of distributions over tree topologies.
Novel TRI-GNN framework improves graph classification robustness.
problem Graph neural networks suffer from over-smoothing and vulnerability to graph perturbations.
method Integrates higher-order graph information via persistent homology and local graph structure learning.
result TRI-GNN outperforms state-of-the-art baselines on node classification tasks.
Network science provides valuable insights across numerous disciplines including sociology, biology, neuroscience and engineering. A task of major practical importance in these application domains is inferring the network structure from noisy observations at a subset of nodes. Available methods for topology inference t…
In this work, we formalize the problem of causal inference over graph-based relational time-series data where each node in the graph has one or more time-series associated to it. We propose causal inference models for this problem that leverage both the graph topology and time-series to accurately estimate local causal…
In this work, we address semi-supervised classification of graph data, where the categories of those unlabeled nodes are inferred from labeled nodes as well as graph structures. Recent works often solve this problem via advanced graph convolution in a conventionally supervised manner, but the performance could degrade …
Estimates multiple networks using graphons for non-aligned graphs.
problem Estimating topology of multiple networks from nodal observations.
method Combining maximum likelihood penalty with graphon estimation schemes.
result Validated performance against competing methods in synthetic and real-world datasets.
Attack graphs provide compact representations of the attack paths that an attacker can follow to compromise network resources by analysing network vulnerabilities and topology. These representations are a powerful tool for security risk assessment. Bayesian inference on attack graphs enables the estimation of the risk …
The construction of a meaningful graph topology plays a crucial role in the effective representation, processing, analysis and visualization of structured data. When a natural choice of the graph is not readily available from the data sets, it is thus desirable to infer or learn a graph topology from the data. In this …
Identifies directed graphs from node measurements using polynomial filters.
problem Inferring directed network topology from nodal measurements.
method System identification of graph convolutional filter followed by topology inference.
result Effective recovery of directed graphs from measurements.
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.
A distributed algorithm for training graph convolutional networks.
problem Training graph convolutional networks with sparse network topology and distributed agents.
method Formulate inference and optimization in a distributed scenario, propose a gradient descent procedure, and design communication topology.
result Convergence to stationary solutions of the GCN training problem under mild conditions.
In this study, we present and analyze a framework for geometric and topological estimation for mapping of unknown environments. We consider agents mimicking motion behaviors of cyborg insects, known as biobots, and exploit coordinate-free local interactions among them to infer geometric and topological information abou…
Improved phylogenetic inference using VBPI-Mixtures for tree topology and branch length.
problem Multimodality of tree-topology posterior distributions in phylogenetic inference.
method VBPI-Mixtures algorithm that uses mixture learning within the BBVI framework.
result VBPI-Mixtures captures tree-topology distributions better than VBPI.
HLTF generates chemically valid 3D molecules with improved topology control.
problem Generating chemically valid 3D molecules is challenging due to bond topology errors.
method HLTF uses a latent multi-scale plan for global context and a constraint-aware sampler to suppress topology-driven failures.
result HLTF achieves high validity and uniqueness on QM9 and GEOM-DRUGS datasets.
Graph convolutional neural networks (GCNN) have numerous applications in different graph based learning tasks. Although the techniques obtain impressive results, they often fall short in accounting for the uncertainty associated with the underlying graph structure. In the recently proposed Bayesian GCNN (BGCN) framewor…
Proposes a graph dynamics prior for more accurate relational inference.
problem Identifying interactions in dynamical systems from observed dynamics.
method Graph Dynamics Prior (GDP) that uses error amplification in non-local polynomial filters.
result Reconstructs graphs more accurately than previous methods, robust to under-sampling.
The ability of a graph neural network (GNN) to leverage both the graph topology and graph labels is fundamental to building discriminative node and graph embeddings. Building on previous work, we theoretically show that edGNN, our model for directed labeled graphs, is as powerful as the Weisfeiler-Lehman algorithm for …
Paper tackles uncertainty in GNNs for graph data.
problem Uncertainty in GNNs' predictions for graph data.
method CF-T2NN, tensor decomposition, topological learning.
result CF-T2NN improves reliability and interpretability of GNN outcomes.
Inferring air quality from a limited number of observations is an essential task for monitoring and controlling air pollution. Existing inference methods typically use low spatial resolution data collected by fixed monitoring stations and infer the concentration of air pollutants using additional types of data, e.g., m…
Recent papers have formulated the problem of learning graphs from data as an inverse covariance estimation with graph Laplacian constraints. While such problems are convex, existing methods cannot guarantee that solutions will have specific graph topology properties (e.g., being k-partite), which are desirable for so…
The construction of a meaningful graph plays a crucial role in the success of many graph-based representations and algorithms for handling structured data, especially in the emerging field of graph signal processing. However, a meaningful graph is not always readily available from the data, nor easy to define depending…
Unified framework infers time-varying graphs from incomplete signals.
problem Jointly inferring time-varying network topologies and imputing missing data from partial observations.
method Unified non-convex optimization framework with Proximal Alternating Direction Method of Multipliers (PADMM) algorithm.
result Superior robustness in high missing-data regimes, demonstrated through extensive numerical experiments.
Proposes an approach to ensure acyclic graphs in Bayesian structure learning.
problem Ensuring acyclic graphs in Bayesian structure learning.
method Integration of knowledge from topological orderings to constrain acyclicty.
result Outperforms related Bayesian score-based approaches in experiments.
PHLP uses persistent homology to interpret graph link prediction.
problem Interpreting why graph neural network models perform well in link prediction.
method Employing persistent homology to analyze graph topology and extract features.
result PHLP outperforms state-of-the-art models on most benchmark datasets.
Attack graphs are a powerful tool for security risk assessment by analysing network vulnerabilities and the paths attackers can use to compromise network resources. The uncertainty about the attacker's behaviour makes Bayesian networks suitable to model attack graphs to perform static and dynamic analysis. Previous app…
The paper tackles partial inference in structured prediction using a convex optimization approach.
problem Maximizing a score function with unary and pairwise potentials in graph label spaces.
method Generative model approach with two-stage convex optimization for label recovery.
result Conditions for recovering a majority of labels with provable guarantees.
We call an Ising model tractable when it is possible to compute its partition function value (statistical inference) in polynomial time. The tractability also implies an ability to sample configurations of this model in polynomial time. The notion of tractability extends the basic case of planar zero-field Ising models…
Paper learns Cartesian product graphs with Laplacian constraints.
problem Learning Cartesian product graphs from Laplacian constraints.
method Penalized maximum likelihood estimation (MLE) and efficient algorithm.
result Statistical consistency for Cartesian product Laplacian estimation.
Bayesian inference of discrete component states in civil infrastructures using PGMs and GNNs.
problem Inferring discrete states of civil infrastructure components from measurable responses is an ill-posed inverse problem.
method The study proposes a novel Bayesian inversion paradigm based on Probabilistic Graphical Models (PGMs) and Graph Neural Networks (GNNs). PGMs are used to model the problem, with parameters learned from data and structural topology prior. Inference is accomplished by GNNs, and a graph property-based training strategy is developed.
result The proposed framework effectively solves the challenges of inferring the posterior PDF for discrete variables in high-dimensional problems.
A new model encodes distances and topology in latent variables.
problem Modeling dissimilarity data with latent variables and invariances.
method Isometric Gaussian Process Latent Variable Model using Riemannian geometry and variational inference.
result The model can encode invariances in learned manifolds.
Many optimization, inference and learning tasks can be accomplished efficiently by means of decentralized processing algorithms where the network topology (i.e., the graph) plays a critical role in enabling the interactions among neighboring nodes. There is a large body of literature examining the effect of the graph s…
This paper finds efficient algorithms for approximating Markov networks with k-tree topologies.
problem Efficiently approximating Markov networks with complex topologies.
method Developed O(n^{k+1})-time algorithms for finding maximum spanning k-trees (MSkT) that retain certain subgraphs.
result Optimal approximation of Markov networks with k-tree topology is achieved in polynomial time.
SGRNN models evolving graph data for better property prediction.
problem Modeling evolving graph data for property prediction.
method SGRNN uses stochastic latent variables to capture both node attribute and topology evolution, with semi-implicit variational inference and KL-divergence simplification.
result SGRNN improves property prediction on real-world datasets.
Method interprets deep learning models using topological data analysis.
problem Lack of interpretability in deep learning models, especially in high-risk applications.
method Topological and geometric data analysis to infer features and decision-making mechanisms of DL models.
result Extracted subgraphs reveal relevant features for model decisions, demonstrating model's reliance on pertinent data.
TGAT learns node embeddings for evolving graphs, capturing both static and temporal features.
problem Learning node embeddings for dynamic graphs with evolving topological structures and temporal patterns.
method Temporal Graph Attention (TGAT) layer using self-attention and functional time encoding.
result TGAT model can inductively infer node embeddings for new and observed nodes as the graph evolves.
Directed networks are pervasive both in nature and engineered systems, often underlying the complex behavior observed in biological systems, microblogs and social interactions over the web, as well as global financial markets. Since their structures are often unobservable, in order to facilitate network analytics, one …
Study of digital topology concepts like hyperspaces and function graphs.
problem Adapting classical topology concepts to digital topology.
method Define digital hyperspaces and function graphs, study their properties.
result Some relationships and graphical properties of digital hyperspaces and function graphs.
We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a significantly lower number of constraints compared to popular MIP models based on cycle elimination constraint…
The paper introduces a quantum state system to count perfect matchings in graphs.
problem Counting perfect matchings in graphs using quantum state systems.
method Topological quantum field theory (TQFT) and spectral sequences.
result The filtered n-color vertex homology for n=2 is generated by perfect matchings. Estimates parameters in max-linear Bayesian networks with noise.
problem Causal inference in extreme-value settings with noise parameters.
method Max-plus algebra and logarithm transformation, normal distribution estimation, EM algorithm and quadratic optimization.
result An estimator of a parameter for each edge in a DAG is normally distributed.
New methods compare neural network models using geometric and topological summaries.
problem Comparing deep representations of complex networks in models and brains.
method Develops inference methods based on topological data analysis (TDA) and graph-based techniques.
result New statistical methods enable better model comparison and inference.