Graph Structure Learning

Follow this topic Ask about this topic

Momentum

9 papers in the last four weeks, up 50% on the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 95

Oct 7, 2026cs.LG

Edge Accuracy Is Not Enough: Why Dynamics-Learned Structure Fails to Transfer to Inverse Problems

A natural strategy for inverse problems with scarce labelled data is to transfer relational structure learned from abundant forward-simulation data. We show this strategy fails systematically, even when it satisfies the standard theoretical justification for why structure should help. We prove that approximate structure provides estimation-error benefits whenever the edge error satisfies

Δ< n^2 - kn

, reducing sample complexity from

O(n^2)

to

O(kn+Δ)

. Structure learned via Neural Relational Inference (NRI) from dynamics prediction satisfies this condition, yet on a source-localisation task across 180 CFD-simulated hydrogen-leak scenarios and 180 acoustic scenarios, it degrades performance by 116% and 201% relative to a flexible, task-optimised attention baseline, while a physics-based prior (Green's function) degrades by only 69-72%. Four independent lines of evidence show this is not a tuning failure: NRI improves only 0.5% when given 18x more training data (versus 16.6% for the task-optimised baseline,

p<0.001

); performance is insensitive to the NRI edge threshold across a wide range; the dynamics-learned graph overlaps the task-optimal graph on only 6% of edges; and two further dynamics-derived structure estimators (correlation- and mutual-information-based) show no measurable benefit over a structure-free baseline, with the correlation-based estimator performing markedly worse. We formalise this gap as a statement about approximation error that the edge-accuracy condition cannot control, and we provide a lightweight transferability test (Jaccard similarity against a partially-observed target-task graph) that separates successful from failed transfer in all four domain/structure pairs we evaluate, using under an hour of computation and 15-20% of target-domain data; we present this as a heuristic calibrated on few cases, not a validated general threshold.

Nicholas Tan Jerome, Fangnian Wang

Institute for Data Processing and Electronics (IPE) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany · Institute for Thermal Energy Technology and Safety (ITES) Karlsruhe Institute of Technology (KIT) Karlsruhe, Germany

Inverse Problems Graph Structure Learning Task Transferability Estimation

Oct 6, 2026cs.AI

LFHE: Local-First Heuristic Evolution for Bounded Local Topology Search in Decentralized Learning with Non-IID Data

Decentralized learning is highly sensitive to communication topology under non-IID data. Adaptive peer-selection methods can exploit local model information, but broader peer discovery may require increasingly large control state, whereas direct spectral optimization typically relies on graph-wide information. We study the intermediate setting of bounded local topology search and propose Local-First Heuristic Evolution (LFHE), a representation-driven rewiring framework whose candidate discovery and scoring use only ego-neighborhood and friend-of-a-friend (FoF) information. The structural score admits an exact interpretation through graph Dirichlet energy: its sum across clients equals twice the representation Dirichlet energy, which under standard linear consensus dynamics governs the instantaneous dissipation of representation disagreement. LFHE combines this state-dependent structural signal with early exploration and degree control, while algebraic connectivity remains an offline graph diagnostic. Under bounded sparse degree, its FoF candidate state remains local rather than expanding toward population-wide peer tracking. Across four image, speech, and text benchmarks, LFHE achieves competitive decentralized learning performance. Matched-protocol controls identify the structural term as the principal empirical topology-selection signal, while comparison with broader peer discovery exposes a trade-off between predictive performance and discovery-state locality. Together, these results motivate state-aware bounded local topology search between pairwise peer selection and globally informed topology optimization.

Yin-Kuan Liang, Yan Gao, Yang Long

Durham University · University of Cambridge

Graph Structure Learning Decentralized Learning Decentralized Optimization

Oct 5, 2026cs.LG

Joint Precision Neural Networks: Task-Aware Dependency and Predictive Learning

Exploiting meaningful latent structures from data to solve downstream tasks is a fundamental challenge in signal processing and machine learning. While Principal Component Analysis (PCA) and coVariance Neural Networks (VNNs) successfully leverage the covariance matrix to process data, they inherently capture both direct and indirect correlations. The precision matrix (inverse covariance) overcomes this by explicitly encoding conditional independencies, making it largely studied in graphical lasso and graph topology identification. However, finite-sample precision estimates are notoriously unstable, and regularized estimators remain task-agnostic. In this work, our principal contribution is tackling the challenging problem of task-aware graph inference. We propose Precision Neural Networks-Joint (PNN-Joint), a framework that jointly estimates a sparse, statistically grounded precision matrix alongside graph neural network weights via an alternating optimization scheme. As a foundational framework to support this, we introduce Precision Neural Networks (PNNs), a broader class of graph convolutional networks operating on precision estimators, and establish their spectral connections to PCA and VNNs alongside their stability to finite-sample errors. Extensive empirical evaluations on synthetic data, as well as real-world neuroimaging and motion sensor datasets, demonstrate that PNN-Joint yields highly interpretable task-aware graphs, exhibits remarkable robustness in low-data regimes, and consistently achieves the best or second-best performance among competitors on real-world tasks.

Andrea Cavallo, Samuel Rey, Antonio G. Marques +1

INSY Department, Delft University of Technology · Department of Signal Theory and Communications, King Juan Carlos University

Graph Structure Learning Graph Neural Networks Covariance Estimation

Sep 30, 2026cs.LG

World-as-Graph: Relational World Modeling Through Latent Space Graphs

World models aim to learn representations of real-world environments and predict their future evolution. Recent object-centric world models have made expressive progress by representing visual scenes as sets of object-level latent states, but object-object relations are often captured only implicitly, which limits explicit relational and temporal structure modeling and object-centric dynamic memory modeling. To address such challenges, we propose World-As-Graph (WAG), a graph-based object-centric world model that introduces relational inductive bias into JEPA-style predictive representation learning. The proposed WAG contains two main modules: (1) Relation-aware structure induction, which constructs time-varying latent graphs from object-centric slots and designs relation-aware object masking policies to guide relational object representation learning in latent space; (2) Object-centric memory transition, which maintains and updates object-level dynamic states by combining relational information from neighboring objects with historical memory, enabling effective autoregressive future prediction. Extensive experiments on both visual reasoning and robotic manipulation tasks could demonstrate the superior performance of our proposed WAG.

Yaqi Yang, Shuo Huang, Yujin Huang +3

School of Computing Technologies, RMIT University, Australia · Faculty of Information Technology, Monash University, Australia · KStelrix Star Dynamics Lab, KStelrix, China +1

Graph Structure Learning World Model Learning World Models Object-Centric World Models Object-Centric Representation Learning Predictive Representation Learning

Sep 29, 2026cs.LG

GARDiff: Graph-Aligned Residual Diffusion for Probabilistic Multivariate Time-Series Forecasting

Diffusion models have recently shown strong potential for probabilistic multivariate time-series forecasting by modeling complex conditional distributions. Recent decoupled diffusion frameworks further separate forecasting into deterministic prediction and stochastic residual generation, making it natural to derive dependency graphs from deterministic representations and use them to guide residual diffusion. However, we show that this direct structural transfer is unreliable. Although deterministic-derived graphs encode useful global dependency priors, they exhibit substantial edge-level misalignment with residual dependency structures, introducing inaccurate or redundant conditions during residual generation. This reveals a previously overlooked deterministic-to-residual structural alignment problem in decoupled diffusion forecasting. To address this problem, we propose GARDiff, a Graph-Aligned Residual Diffusion framework for probabilistic multivariate time-series forecasting. Instead of treating deterministic-derived graphs as fixed diffusion conditions, GARDiff progressively adapts them to residual generation. Specifically, GARDiff estimates residual uncertainty to distinguish high- and low-uncertainty regions, enabling uncertainty-aware structural refinement, and further performs timestep-aware edge sparsification during reverse diffusion to evolve graph conditions from broad dependency aggregation to localized residual refinement. Extensive experiments on six real-world benchmarks demonstrate that GARDiff consistently improves probabilistic forecasting performance and uncertainty calibration over strong baselines.

Rui Han, Min Yang, Xu Zhang +3

Shandong University, Jinan, China · Macquarie University, Sydney, Australia · China University of Petroleum (East China), Qingdao, China +1

Multivariate Time Series Forecasting Graph Structure Learning Time Series Forecasting Probabilistic Time Series Forecasting Diffusion Models

Sep 27, 2026cs.IT

Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting

Graph learning from edge-detecting queries concerns the reconstruction of an unknown edge set on a known vertex set. Each query reports whether a specified vertex subset contains at least one edge. We study non-adaptive schemes, in which all queries are fixed before any outcomes are observed, with the goal of achieving exact recovery using few queries and fast decoding. For general graphs on

n

vertices with at most

k

edges, non-adaptive recovery requires

Ω(\min\{k^2\log n,n^2\})

queries in the worst case, even when a small error probability is allowed. In this paper, we consider Erdős--Rényi (

\mathrm{ER}

) graphs

G\sim \mathrm{ER}(n,q)

, with expected edge count

\bar{k}=q\binom{n}{2}

. Our scheme uses

O(\bar{k}\log n)

queries and achieves exact recovery in

O(\bar{k}\log n)

decoding time with probability tending to one throughout the regime

\bar{k}\to\infty

and

\bar{k}=o(n^2)

. This improves the previous

O(\bar{k}^{1+δ}\log n)

decoding guarantee for any fixed

δ>0

, while maintaining the same query order. The guarantee also extends beyond the previously studied regime

\bar{k}=Θ(n^{2θ})

with fixed

θ\in(0,1)

. Our approach builds on the binary splitting method used in prior work, which organizes vertices into a hierarchy of successively smaller groups. We introduce three main changes: (i) we use random affine hash functions over a finite field to process each candidate pair in constant time; (ii) we apply the splitting procedure directly to the full graph, avoiding the need to combine solutions to multiple smaller graph-learning subproblems; and (iii) we bound the total decoding workload directly rather than deriving separate high-probability bounds on candidate counts at each level.

Hoang Ta

Department of Computer Science, Hanoi University of Science and Technology, Vietnam

Graph Structure Learning Sparse Recovery

Sep 23, 2026cs.LG

Graph Learning with Spectral Connectivity Priors for Scarce Data

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix

\mathbf{W}

with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize

\mathbf{W}

. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou +3

Tsinghua University, China · York University, Canada

Graph Signal Processing Graph Structure Learning Spectral Regularization

Sep 20, 2026eess.SP

Fast Graph Laplacian Estimation using Effective Resistance

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.

Christoffer Kjellson, Claudio Altafini, Emma Tegling

Department of Automatic Control, Lund University · ELLIIT Strategic Research Area · Division of Automatic Control, Department of Electrical Engineering, Linköping University

Graph Structure Learning Probabilistic Graphical Models

Sep 14, 2026cs.LG

GSLAD: Prototype-Regularized Graph Structure Learning for Multivariate Time Series Anomaly Detection

Unsupervised multivariate time series anomaly detection methods typically identify anomalies through forecasting, reconstruction, or representation discrepancies. However, industrial faults may first alter inter-variable structural patterns while individual trajectories remain close to normal, resulting in weak anomaly signals. In this paper, we propose GSLAD, a prototype-regularized graph structure learning framework that uses structural deviations for anomaly scoring. GSLAD adopts a two-phase training strategy. First, a condition-aware graph learner and a graph-based forecaster are optimized with predictive supervision. The inferred normal graphs are then clustered into multiple structural prototypes representing different normal operating regimes, with edge-wise variability characterizing structural uncertainty. Deviations from these prototypes regularize the graph learner in the second phase, encouraging stable and regime-specific structural patterns. During inference, uncertainty-normalized structural deviation is combined with predictive deviation for anomaly scoring. Experiments on four industrial benchmarks demonstrate strong overall performance of GSLAD and confirm the effectiveness of structural deviation for anomaly detection and diagnosis.

Zepeng Zhang, Fuad Khuri, Keivan Faghih Niresi +1

Intelligent Maintenance and Operations Systems (IMOS) Lab École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

Graph Structure Learning Industrial Anomaly Detection Unsupervised Anomaly Detection Time-Series Anomaly Detection

Sep 14, 2026cs.CL

ABSOL: Aggregated Bayesian Subsampling Orchestrated with LLMs

Large language models are increasingly used as natural-language interfaces to structured data, yet they remain unreliable when answers require consistent evidence conditioning, dependency-aware reasoning, and uncertainty estimation. Bayesian networks provide an explicit probabilistic reasoning layer, but learning useful structures from data remains costly and fragile at scale. We introduce ABSOL, a hybrid LLM-guided Bayesian network structure-learning framework that uses LLMs as bounded semantic guides. Across five discrete BN benchmarks spanning 27 to 1041 nodes, ABSOL is the only evaluated method to produce a viable graph on every benchmark, and achieves the highest Edge F_1 on every benchmark larger than 27 nodes with GPT-5.4. The four LLM augmentations, which contribute complementary semantic evidence to the statistical backbone, improve Edge F_1 over the non-LLM aggregation backbone by +0.23 on average. Complementary post-hoc refinement experiments suggest that these gains depend in part on limiting the LLM's authority over the final structure. Together, these results show that language-derived semantic knowledge can substantially improve scalable probabilistic structure learning when used as bounded guidance within a statistically grounded reasoning pipeline. The code for ABSOL is available at github.com/megagonlabs/absol-bn.

Jackson Hassell, Chen Shen, Estevam Hruschka

Megagon Labs

Graph Structure Learning Bayesian Networks Probabilistic Graphical Models LLMs for Graph Learning

Sep 8, 2026stat.ML

Tensor Network Moral Graph Recovery of Discrete Probability Distributions

We present a method for recovering the moral graph of a causal DAG from a probability distribution over discrete variables, using fully connected tensor networks (FCTNs) with nuclear-norm-regularized bond corrections. Each bond matrix is parameterized as a baseline all-ones matrix plus a low-rank correction

C_{ij} = U_{ij}V_{ij}^\top

, and the nuclear norm of the correction implemented via the variational Frobenius norm penalty on the factors drives unnecessary bonds to zero. We prove that under faithfulness, positivity, and a no-implicit-rerouting assumption on the local tensor architecture, \textbf{every} optimal FCTN with zero reconstruction error

\varepsilon = 0

has effective graph exactly equal to the moral graph. For the approximate regime (

\varepsilon > 0

), we provide explicit recovery bounds using the Fannes-Audenaert continuity of conditional mutual information, and derive a sufficient condition on the regularization parameter

β

. The effective graph is read directly from the optimized bond matrices.

Á. Troyano Olivas, Chi-Hang Fred Fung, Hans H. Brunner +2

Heisenberg Research Center (Munich), Huawei Technologies Duesseldorf GmbH, Germany · Center for Computational Simulation, Universidad Politécnica de Madrid, Madrid, Spain

Tensor Networks Graph Structure Learning Bayesian Networks Causal Structure Learning

Sep 7, 2026stat.ME

Bayesian Matrix-Valued Graphs for Context-Dependent Multivariate Relationships

Many scientific graphs attach several variables to each node, so a single scalar edge weight cannot describe direction-dependent interactions. We model each edge by a symmetric positive-definite (SPD) matrix and infer a posterior over matrix-valued graph geometries, which we call the Bayesian matrix-valued graph (BMVG). We ask how these interactions reconfigure across contexts: how large the change is and which multivariate directions strengthen or weaken. The geodesic distance induced by the affine-invariant Riemannian metric (AIRM) quantifies deformation magnitude and generalized eigenvalues resolve its signed directions.Against fused graphical lasso, Bayesian multiple-GGM, and common principal components, BMVG is competitive on global precision recovery while retaining identifiable matrix-valued edge structure and accurately recovering edge-level deformation directions. In controlled known-truth experiments, it resolves structural change with increasing sample size, including orientation changes that leave ordinary eigenvalues unchanged. In one year of Bay Area weather data, the geometry of 12-hour change reconfigures spatial coupling about as much as whole seasons differ. In TCGA-BRCA, estrogen-receptor (ER)-associated reconfiguration concentrates on specific gene-module pairs and persists under graph-scaffold sparsification and removal of subgroup mean differences. These results establish posterior matrix-valued edge geometry as a unified framework for quantifying and interpreting context-dependent multivariate reconfiguration.

Papri Dey

Graph Structure Learning Bayesian Inference

Sep 3, 2026cs.LG

Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

Kernelized graph methods - spectral clustering, diffusion maps, and sparse kernel -regression graphs - that use Gaussian kernels depend on the choice of Gaussian bandwidth sigma, which governs the spectral character of the local kernel operator. When sigma is too small, the kernel overestimates local complexity and treats each sample as an independent direction; when sigma is too large, the kernel collapses multiple directions together, the condition number diverges, and all geometric discrimination is lost. We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold. We propose a per-node bandwidth criterion that operationalizes this principle by jointly matching the kernel's effective rank to the local intrinsic dimension estimated via minimum spanning tree, anchoring the search in the manifold-consistent log-log scaling regime. We evaluate SSL embeddings from six encoders on CIFAR-100, showing that adaptive bandwidth consistently improves leave-one-out (LOO) classification and label propagation (LP) accuracy over fixed-bandwidth methods and competing adaptive methods.

Ecem Bozkurt, Antonio Ortega

Department of Electrical and Computer Engineering University of Southern California, Los Angeles, CA, USA

Graph Structure Learning Graph-Based Semi-Supervised Learning Kernel Methods Spectral Methods

Sep 2, 2026stat.ML

From topology learning to graph generation: A unifying perspective

Learning graph structures from data is a fundamental problem that spans a wide range of signal processing and machine learning tasks. While significant effort has been made to tackle the problem, existing research has largely evolved along two parallel directions. The first seeks to infer the topology of an individual graph from observations supported on it, whereas the second seeks to learn a generative distribution from observed graph instances, enabling the sampling of new graphs. This review presents a unified framework that connects these formulations by viewing them as inverse problems of a common generation process for graph data. We review the major methodologies within this framework, highlight their relationships, strengths, and limitations, and identify opportunities for integrating ideas across paradigms. By bridging graph topology learning and graph generation, this review provides a broader cross-disciplinary perspective on the field and outlines promising directions for future research.

Xiaowen Dong, Hoi-To Wai, Siheng Chen +2

University of Oxford · The Chinese University of Hong Kong · Shanghai Jiao Tong University +2

Graph Structure Learning Graph Generation

Sep 1, 2026cs.LG

Import What You Need: Learning When and How to Augment EHR Graphs with External Knowledge

Longitudinal prediction from electronic health records (EHRs) is limited by the sparsity and irregularity in patient trajectories, and knowledge augmentation with external knowledge graphs (KGs) offers a promising way to alleviate these issues. However, most existing methods perform fixed, context-agnostic topology augmentation by adding the same KG nodes and edges regardless of a patient's evolving state. We propose ReTA, a Reinforcement learning-based dynamic Topology Augmentation framework that casts KG import as a per-visit, budget-aware policy. ReTA first constructs an offline refined pool of KG-grounded templates, then learns a policy to select one augment action per visit from three options: Soft Import, which enriches node features without modifying graph topology, Hard Import, which grafts a compact KG subgraph onto the visit graph to create message-passing shortcuts, and Skip, which leaves the visit unaugmented when the base encoder is already confident. To stabilize learning, ReTA employs a decoupled encoder that processes semantic and structural signals in separate channels and fuses them via adaptive gating. Experiments on MIMIC-III and MIMIC-IV across diagnosis prediction, mortality, and readmission show that ReTA consistently outperforms strong baselines while remaining efficient, transfers across datasets and knowledge graphs, and yields interpretable augmentation patterns. The robust gains under sparse supervision highlight the advantage of ReTA's dynamic decision to import knowledge, boosting accuracy while curbing costs.

Chen Chen, Mohsen Nayebi Kerdabadi, Dongjie Wang +2

Electrical Engineering and Computer Science, University of Kansas, USA · Health Outcomes and Biomedical Informatics, University of Florida, USA

Graph Structure Learning Longitudinal EHR Modeling Knowledge Graphs

Aug 27, 2026cs.LG

Decentralized Multitask Learning over Learned Task Graphs

This paper investigates decentralized multitask learning over networks when the underlying task relationships are unknown. While existing graph-regularized multitask frameworks typically assume a known structure, practical settings often require learning inter-task dependencies directly from distributed data. We propose a decentralized two-phase strategy that first estimates a generalized graph Laplacian from noisy non-cooperative stochastic gradient iterates, and subsequently exploits the learned graph to enable cooperative multitask diffusion learning. This framework is motivated by a Gaussian Markov random field prior, which gives rise to a decentralized maximum likelihood estimator for the graph Laplacian. The analysis quantifies the Laplacian estimation error and its propagation to the steady-state performance of the multitask diffusion recursion, and introduces a topology sensitivity index to capture the effect of network heterogeneity. Simulation results corroborate the theoretical findings and demonstrate that cooperation enabled by the learned task graph significantly improves performance over non-cooperative learning, while approaching the true-graph baseline when the estimation stepsize is sufficiently small.

Zirui Wan, Stefan Vlaski

Department of Electrical and Electronic Engineering, Imperial College London, UK

Graph Structure Learning Multi-Task Learning Decentralized Learning Multi-Task Optimization

Aug 13, 2026cs.LG

EGRL: Edge generation-guided relation-aware learning for RNA-protein interaction prediction

RNA-Protein Interactions (RPIs) are critical for regulating cellular functions. While traditional wet-lab experiments for RPI detection are costly and time-consuming, Deep Learning (DL) methods provide an efficient computational alternative for RPI Prediction (RPIP). In particular, Graph Neural Networks (GNNs) are promising, as they naturally model RPI networks. However, existing GNN-based methods often rely on homogeneous graphs or predefined meta-paths, which limit their ability to handle data sparsity and to generalize to cold-start scenarios involving unknown molecules. To address these limitations, we propose Edge Generation-guided Relation-aware Learning (EGRL), a novel framework with several key components: implicit meta-path learning to capture relational semantics without handcrafted paths; a multi-relation-aware attention mechanism for adaptive fusion of interaction patterns; a graph generator that predicts potential ("soft") edges to support cold-start nodes; and a multi-feature fusion predictor for final interaction scoring. EGRL is jointly trained with a primary task loss and an auxiliary generator loss. Comprehensive evaluations on four benchmark datasets demonstrate that EGRL achieves competitive overall performance. More importantly, it exhibits superior generalization in cold-start settings, achieving an Area Under the Receiver Operating Characteristic curve (AUROC) of 0.867 and an Area Under the Precision-Recall curve (AUPR) of 0.861 on unknown molecules, corresponding to improvements of 8.6% in AUROC and 5.0% in AUPR over prior state-of-the-art methods. The code will be released soon.

Danyu Li, Ling Zhou, Rubing Huang +3

School of Computer Science and Engineering, Macau University of Science and Technology, Macao SAR, 999078, China · Macau University of Science and Technology Zhuhai Research Institute, Zhuhai, Guangdong, 519099, China · Hubei Key Laboratory of Transportation Internet of Things, School of Computer Science and Artificial Intelligence, Wuhan University of Technology, Wuhan, Hubei, 430070, China +2

Graph Structure Learning Heterogeneous GNNs Relational Deep Learning

Aug 11, 2026cs.LG

AutoGrable: What Is a Good Graph for a Table?

Graph learning presupposes a graph, and tables and relational databases do not come with one. Applying a GNN to them requires deciding which entities become nodes, which of them to connect, and through which relations---a decision made by hand, by schema heuristics, or by training a model on every candidate graph and keeping the best. We give a criterion that requires no trained graph model. In the minimal table-to-graph abstraction each row is a node, so a message-passing GNN, bounded by 1-WL, sees a construction only as a partition of the rows into colour-refinement classes: a construction is good for a task when that partition separates rows with different labels and does not split rows that share one. AutoGrable turns this criterion into a construction procedure. For incidence constructions the partition is fixed by the selected columns, so building a graph reduces to choosing them, and we score a candidate subset by a label-alignment risk: the held-out risk of the best predictor constant on its blocks, penalised by an occupancy term measuring how thinly the blocks are populated. The score materialises no graph and trains no GNN, so AutoGrable can search the space of subsets greedily and cheaply, and returns the resulting grable for single tables and for foreign-key schemas alike. Our experiments show that over a space of candidate graphs the score discards a large fraction while retaining the best; that AutoGrable recovers the columns that generate the label on controlled tasks and outperforms fixed, random, and task-aware constructors on real tasks under a fixed predictor; and that it is the only method compared that can decline to build a graph when none helps.

Tamara Cucumides, Floris Geerts

University of Antwerp

Graph Structure Learning Tabular Prediction

Aug 9, 2026cs.LG

Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering

We study exact Kullback--Leibler (KL) projection for low-rank factorizations whose two nonnegative factors have prescribed row marginals and a shared, learned column marginal. For arbitrary positive row marginals of equal total mass, the joint KL projection reduces exactly to a strictly convex gauge-fixed dual with only

r-1

effective variables; its Hessian is a sum of categorical covariance terms and admits

O((n+m)r)

matrix-free Hessian--vector products. The projection theorem is objective-independent. We then specialize this geometry to doubly stochastic (DS) graph learning through

W=U\operatorname{Diag}(g)^{-1}V^\top

, where row-simplex factors with a common column mass induce an exactly DS graph without materializing an

n\times n

optimization variable. Combined with observed-edge sparse fitting, a stochastic anchor-reduced manifold regularizer, and Bregman backtracking, the resulting mirror-descent method preserves exact feasibility at every accepted step. Under a nonvanishing latent-mass condition, it satisfies sufficient decrease and an

O(1/N)

mirror-stationarity bound, while strictly positive accumulation points are KKT stationary. Matched clustering experiments show competitive accuracy, feasibility residuals near numerical precision, and favorable anytime behavior without a dense learned graph.

Enliang Hu

Graph Structure Learning Low-Rank Matrix Decomposition Clustering Matrix Optimization Matrix Factorization

Aug 7, 2026eess.SY

Topology Inference for Immune System Networks by Using Cell Amount Data

Recent years have witnessed the advanced development of topology inference research, which helps elucidate the interaction relationships of components in many biological networks. This paper focuses on inferring the topology of a group of immune cells, based on the collected data from cell-depletion based experiments. The problem is very challenging due to i) the lack of standard analytical models for the cell interactions, and ii) the restrictive data availability determined by the huge experiment and time costs. To address these issues, we first leverage certain common knowledge and observations on the experiments to characterize three properties on the cell amounts during the interaction process: state non-negativity, ratio-based convergence, and triple signs of topology weights. Then, we construct a new model with simple structure and analytical convenience, and obtain sufficient conditions for the model to accommodate all three properties. Finally, based on the constructed model, we propose a constrained quadratic programming method to infer the topology from limited number of data pairs. Validation on experiment data demonstrate the effectiveness of the proposed method.

Yushan Li, Rikard Forlin, Dimos V. Dimarogonas +1

Department of Decision and Control Systems, KTH Royal Institute of Technology, Sweden · Department of Women’s and Children’s Health, Karolinska Institutet, Sweden

Graph Structure Learning

Aug 7, 2026cs.LG

Graph Machine: Exploring Edge Mechanisms as an Inductive Bias

Transformers provide a powerful architecture for global content-based matching, but reasoning problems may benefit from a stronger inductive bias toward iterative traversal of latent relations. We introduce Graph Machine, an architecture with two explicit edge-based mechanisms: Edge-augmented attention, in which edges modulate attention between nodes, and edge-centric referral, in which nodes exchange addresses to update their edges. Conceptually, this enables the model to dynamically and differentiably construct and revise relational graphs across layers. We study this inductive bias using Sudoku under controlled settings and find that Graph Machine outperforms Transformer baselines, with ablation studies and mechanistic analysis attributing the gains to the edge mechanisms. Surprisingly, we found that the model discovers a compact edge-based construction for Sudoku geometry. Our results support explicit edge mechanisms as a promising architectural design, motivating broader evaluation.

Lintai Hou

Iter Labs

Graph Structure Learning Neural Algorithmic Reasoning Edge ML Graph Transformer Algorithmic Reasoning

Aug 6, 2026q-fin.PM

Beyond Co-Movement: Locality by Exposures Enables a Joint Factor-Graph Framework for Portfolio Diversification

Current portfolio construction methods are either agnostic to the effects of idiosyncratic shocks (standard factor models) or to the latent data structure driving systematic returns (recent graph-based approaches). This presents an opportunity to combine the complementary market aspects captured by the factor and graph domains, allowing asset allocations to operate directly on the underlying market structure, rather than on its observed co-movement or its finite-sample artefacts. In this work, we introduce the Mutually-INformed Graph-Locality and Exposures framework (MINGLE), which mutually regularises the factor and graph domains by redefining graph locality through systematic factor exposure profiles, rather than via observed co-movements. This is formalised through a unified Alternating Direction Method of Multipliers (ADMM) framework that jointly learns a latent factor representation and its induced graph topology directly from market returns. The resulting exposure-similarity graph aligns more closely with established economic sectors than conventional correlation-based graphs. Portfolios constructed from this representation are shown to consistently outperform their correlation-based counterparts across a range of volatility regimes and transaction cost levels. For rigour, paired statistical testing confirms that these gains stem from the reconciliation of the graph and factor domains.

Sara Chehab, Giorgos Iacovides, Parisa Yazdanparast +1

Imperial College London London, UK

Graph Structure Learning Quantitative Finance Portfolio Optimization Finance

Aug 5, 2026cs.LG

Towards Trustworthy Hypergraph Neural Networks under Label Noise

Hypergraph neural networks (HGNNs) have demonstrated remarkable capabilities in processing complex higher-order relationships. However, their performance is highly dependent on labeled data, making them vulnerable to label noise. Despite advances in learning with label noise (LLN) and graph learning with label noise (GLN), noisy-label learning on hypergraphs remains underexplored. In this paper, we present a systematic study of hypergraph node classification under label noise. First, we adapt representative LLN and GLN methods to hypergraphs and evaluate them under a unified benchmark, revealing the limitations of existing robust learning strategies for hypergraphs. Building on this, we propose a new hypergraph robust framework, HyperTrust, which first estimates hyperedge trustworthiness through a pretraining-based, entropy-aware strategy, and then incorporates the HyperedgeBoost module to enhance reliable supervision by connecting unlabeled nodes to trustworthy hyperedges, as well as the HyperedgePrune module to suppress noisy propagation by removing untrustworthy node-hyperedge incidences. Finally, two modules work collaboratively to adjust the hypergraph structure and generate final predictions. Extensive experiments and theoretical analysis demonstrate the effectiveness and robustness of HyperTrust on multiple hypergraph datasets under various noisy settings. Our work provides a unified benchmark and an effective solution for hypergraph learning with label noise and lays a foundation for future research in this direction.

Mengyao Zhou, Zhiheng Zhou, Xiao Han +1

Academy of Mathematics and Systems Science, Chinese Academy of Sciences and also with the University of Chinese Academy of Sciences, Beijing 100190, China · School of Mathematics and Statistics, Shandong University, Weihai, Shandong 264209, China · School of Artificial Intelligence, Beihang University, Beijing 100191,China

Graph Structure Learning Hypergraph Neural Networks Learning with Noisy Labels Hypergraph Learning

Aug 2, 2026cs.LG

Differentiable Lifting for Topological Neural Networks

Topological neural networks (TNNs) enable leveraging high-order structures on graphs (e.g., cycles and cliques) to boost the expressive power of message-passing neural networks. In turn, however, these structures are typically identified a priori through an unsupervised graph lifting operation. Notwithstanding, this choice is crucial and may have a drastic impact on a TNN's performance on downstream tasks. To circumvent this issue, we propose

\partial

lift (DiffLift), a general framework for learning graph liftings to hypergraphs and cellular- and simplicial complexes in an end-to-end fashion. In particular, our approach leverages learned vertex-level latent representations to identify and parameterize distributions over candidate higher-order cells for inclusion. This results in a scalable model which can be readily integrated into any TNN. Our experiments show that

\partial

lift outperforms existing lifting methods on multiple benchmarks for graph and node classification across different TNN architectures. Notably, our approach leads to gains of up to 45% over static liftings, including both connectivity- and feature-based ones.

Jorge Luiz Franco, Gabriel Duarte, Alexander Nikitin +3

University of São Paulo, Instituto Curvelo · Federal Institute of Ceará · Aalto University +3

Graph Structure Learning Graph Representation Learning Topological Representation Learning

Jul 20, 2026stat.ML

Mixing-Free and Signal-Optimal Learning of Gaussian Graphical Models from Glauber Dynamics

Gaussian graphical model selection is usually studied under independent sampling, but in many applications the data arise as a single trajectory of a dependent stochastic process. We study exact recovery of the graph from one trajectory of random-scan Gaussian Glauber dynamics. Existing techniques for this problem either inherit the mixing time of the chain, which can be super-polynomial in the dimension

p

without strong assumptions, or are suboptimal in the minimum normalized edge strength

κ

. We propose two algorithms that are mixing-free and attain the

κ^{-2}

dependence of the information-theoretic lower bounds. Both instantiate a shared dueling-neighborhood search meta-algorithm with a local statistic built directly from the update sequence. For every fixed precision matrix and deterministic initialization, the first algorithm fits a least-squares regression at the updates of each node and has pointwise recovery horizon

\widetilde O(pd^{2}/κ^{2})

, where

d

is the maximum degree. Its horizon depends logarithmically on a local conditioning quantity and on the initialization potential. The second algorithm is based on counting occurences of a specific update pattern and requires

\widetilde O(pd^{4}/κ^{2})

updates, with no dependence on any condition number. The central technical challenge is that both statistics are built from dependent, non-stationary observations. Our analysis tackles this by demonstrating how to extract fresh Gaussian innovations from the update sequence, which yields mixing-free control of appropriate quantities. Neither the algorithms nor their analyses invoke stationarity, a spectral gap, or mixing conditions.

Vignesh Tirukkonda, Gautam Dasarathy

Arizona State University

Graph Structure Learning Probabilistic Graphical Models

Jul 17, 2026cs.LG

Knowledge-Assisted Multi-Graph Dependency Learning for Multivariate Time Series Anomaly Detection in Multi-Stage Industrial Processes

Industrial processes often generate complex, interdependent time-series data from multiple sensors across multiple stages, forming complex dependencies among variables and process stages. Effective monitoring and timely anomaly detection of these time series through multivariate time series anomaly detection (MTAD) is crucial for preventing failures and ensuring the reliability of automated systems. Graph neural networks (GNNs) have advanced MTAD by leveraging data-driven graphs to model complex dependencies among variables, effectively capturing relational structures within multivariate time series to enhance anomaly detection performance. However, existing GNN-based approaches often overlook critical process knowledge, and even when this knowledge is considered, seamlessly incorporating it into existing models remains inherently challenging, leading to suboptimal performance. To address this limitation, we propose a knowledge-assisted multi-graph framework for modeling sensor dependencies in multi-stage industrial processes for MTAD, which explicitly incorporates process knowledge into graph learning to enhance dependency modeling and improve anomaly detection performance. Our method constructs three complementary graphs: one purely data-driven and two refined by integrating structural constraints derived from process knowledge. To effectively leverage these graphs for anomaly detection, we employ a multi-graph attention network, enabling a more accurate and robust representation of complex dependencies. Comprehensive experiments on two real-world, multi-stage industrial datasets demonstrate that incorporating process knowledge substantially enhances anomaly detection performance.

Jaeyeong Lee, Taeseong Yoon, Wonmo Koo +1

Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea

Graph Structure Learning Graph Representation Learning Industrial Anomaly Detection Time-Series Anomaly Detection

Jul 16, 2026cs.CV

DAPGNet: Dynamic Adaptive Physics-Guided Graph Diffusion Network for Hyperspectral Image Classification

Hyperspectral image (HSI) classification requires reliable pixel-relation modeling under spectral variability, mixed pixels, and heterogeneous boundaries. Existing graph-based HSI classifiers usually construct graph topology from spatial proximity, superpixel connectivity, or learned feature affinity. However, the spectral physical prior carried by contiguous bands has limited influence on topology estimation and message propagation. This paper presents DAPGNet, a dynamic adaptive physics-guided graph diffusion network that injects a structure-constrained physical prior into relation-level graph learning. DAPGNet first encodes contiguous spectral responses into node-wise multiscale physical-prior representations. A two-stage graph constructor then combines spectral-spatial affinity, physical-prior consistency, and spatial distance to form a physical-prior-aware sparse topology. During graph diffusion, learned edge weights are transformed into additive attention biases, while a physical gate performs node-wise and feature-wise interpolation between graph-aggregated features and projected physical-prior features. Cross-scale fusion integrates node states from different diffusion depths, and the network is optimized with main classification, auxiliary supervision, and second-order spectral smoothness regularization. Experiments on Indian Pines, WHU-Hi-LongKou, Houston2013, and Houston2018 show that DAPGNet achieves the best OA, AA, and Kappa among representative CNN-, Transformer-, Mamba-, and graph-based baselines. It improves AA over the strongest competing method by 3.64 to 7.31 percentage points across the four datasets. Ablation and sensitivity analyses further support the complementary effects of physical-prior extraction, prior-aware topology construction, physics-gated propagation, and spectral smoothness regularization.

Pengkun Wang, Weijia Cao, Ning Wang +1

National Engineering Laboratory for Satellite Remote Sensing Applications, Aerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100094, China · Aerospace Information Research Institute, Chinese Academy of Sciences, Beijing 100094, China · Guangzhou University, Guangzhou 510006, China

Graph Structure Learning Hyperspectral Imaging Physics-Informed ML Hyperspectral Image Classification Graph Diffusion

Jul 15, 2026cs.LG

NeuroGRIP: Retrieval-Augmented Graph Refinement for Knowledge-Grounded EEG Seizure Diagnosis

Seizure diagnosis from EEG signals is a critical yet persistently challenging task, due to the complicated neural dynamics and the spurious connections in inter-channel modeling. While spatial-temporal graph neural networks (STGNNs) have advanced EEG brain network representation learning, the resulting graph structures suffer from low clinical plausibility and limited interpretability due to their purely data-driven nature. To this end, we introduce NeuroGRIP, a retrieval-augmented graph refinement framework that incorporates external medical knowledge to calibrate noisy EEG graphs. We first construct a large-scale, domain-specific knowledge base derived from authoritative clinical guidelines. Leveraging large language models, we extract structured biomedical entities and relations to form a textual knowledge graph (KG), which serves as external knowledge source of clinical priors. Our framework performs alignment-aware query construction by projecting STGNN-generated EEG node embeddings into the semantic space of KG. Semantic queries are then executed via FAISS-based similarity search over knowledge triplets to retrieve relation evidence. Each predicted edge is assigned a confidence score based on retrieved similarity, relation type, and source reliability, enabling us to prune medically implausible edges from the originally predicted graph. Extensive experiments on TUSZ and CHB-MIT demonstrate that NeuroGRIP not only improves seizure detection accuracy but also enhances interpretability by grounding each prediction in clinically validated knowledge. This work provides the first unified framework that tightly couples brain dynamics with external medical expertise via retrieval-augmented reasoning, paving the way for knowledge-enhanced, explainable clinical diagnosis. The code is available at: https://github.com/LincanLi-X/NeuroGRIP.

Lincan Li, Zheng Chen, Yushun Dong

Department of Computer Science, Florida State University, Tallahassee, United States · SANKEN, The University of Osaka, Japan.

Graph Structure Learning Electroencephalography EEG Seizure Detection Spatiotemporal GNNs

Jul 9, 2026cs.AI

Drift-Aware Temporal Graph Rewiring (DATGR) for Adaptive Semantic Modeling in Biomedical Text

Biomedical language evolves rapidly as new discoveries emerge, causing traditional text models to lose semantic fidelity over time. Static embeddings and co-occurrence graphs cannot capture such evolution, leading to performance degradation in retrieval and knowledge discovery tasks. This paper introduces a Drift-Aware Temporal Graph Rewiring (DATGR) framework that models concept evolution by dynamically updating co-occurrence edges based on estimated semantic drift. Instead of retraining embeddings for each time slice, DATGR performs lightweight, feedback-driven rewiring using a logistic update rule applied to edge weights. Evaluated on the Biomedical Multi-Relation Corpus (BIOMRC), the method achieved a mean Area Under the Receiver Operating Characteristic (AUROC) improvement of approximately 0.066 absolute difference (0.699 vs. 0.633) over a static baseline. Area Under the Precision-Recall Curve (AUPRC) remained comparable (0.738 vs. 0.744), showing that drift-aware adaptation enhances link-prediction recall without a loss in precision. These results demonstrate that edge-level adaptation effectively captures temporal semantic change in evolving biomedical text while remaining computationally efficient and interpretable.

Bharathwaj Vijayakumar, Sahana K. Varadaraju

Institutional Data and Analytics, Rowan University, NJ, USA · Information Resources & Technology, Rowan University, NJ, USA

Graph Structure Learning Temporal Link Prediction Dynamic Graph Learning Semantic Change Detection

Jul 7, 2026cs.CV

Visual graphs for image classification: does the structure affect performance?

Deep learning models have emerged in machine learning and related fields, demonstrating astonishing performance in various visual tasks. Despite their great success, however, these models are unable to fully encode intrinsic visual structures, and often ignore the spatial, topological, and semantic information contained within an image. Graph neural networks offer a good framework to face this aspect, but their effective use for visual tasks has been only partly explored and mainly starting from a limited perspective. This work aims to address this gap by conducting a systematic comparison of current graph construction techniques within the context of a fixed three-layer GCN architecture. Through an empirical study, it demonstrates in particular how the network structure affects performance and provides an important methodological contribution regarding the computational stages preceding graph utilization, which will be strongly influenced by the structure itself.

Alessandra Ibba

University of Sassari - Department of Engineering, Sassari, Italy

Graph Structure Learning Graph Neural Networks Image Classification