Graph Structure Learning

Ask about this topic

Overview

Graph structure learning studies how to infer or refine edges, weights, and higher-order connections when the network is unknown, noisy, changing, or poorly matched to a task. Methods range from sparse precision-matrix and Laplacian estimation and score-based directed acyclic graph learning to similarity-based construction, attention-driven rewiring, and task-aware bilevel optimization. Learned structures support tasks such as node classification, link prediction, time-series forecasting, recommendation, and biomedical analysis, including settings with scarce labels, multimodal features, or evolving relationships. A central tension is whether a graph should faithfully recover underlying dependencies or maximize downstream performance: task-driven rewiring can help prediction but may overfit, weaken interpretability, or fail to transfer across datasets.

Latest papers

CardsList

139 papers14 papers in the last four weeks, up 8% on the four weeks before. 0.1% of all new papers.

Mar 17, 2026

RaDAR: Relation-aware Diffusion-Asymmetric Graph Contrastive Learning for Recommendation

Collaborative filtering (CF) recommendation has been significantly advanced by integrating Graph Neural Networks (GNNs) and Graph Contrastive Learning (GCL). However, (i) random edge perturbations often distort critical structural signals and degrade semantic consistency across augmented views, and (ii) data sparsity hampers the propagation of collaborative signals, limiting generalization. To tackle these challenges, we propose RaDAR (Relation-aware Diffusion-Asymmetric Graph Contrastive Learning Framework for Recommendation Systems), a novel framework that combines two complementary view generation mechanisms: a graph generative model to capture global structure and a relation-aware denoising model to refine noisy edges. RaDAR introduces three key innovations: (1) asymmetric contrastive learning with global negative sampling to maintain semantic alignment while suppressing noise; (2) diffusion-guided augmentation, which employs progressive noise injection and denoising for enhanced robustness; and (3) relation-aware edge refinement, dynamically adjusting edge weights based on latent node semantics. Extensive experiments on three public benchmarks demonstrate that RaDAR consistently outperforms state-of-the-art methods, particularly under noisy and sparse conditions.

Yixuan Huang, Jiawei Chen, Shengfan Zhang +1

National University of Defense Technology, Changsha, China · Ant Group, Chongqing, China · Tsinghua University, Beijing, China

Graph Contrastive LearningCollaborative FilteringGraph Structure Learning
AskPDF
Mar 13, 2026

Exploring Subnetwork Interactions in Heterogeneous Brain Network via Prior-Informed Graph Learning

Modeling the complex interactions among functional subnetworks is crucial for the diagnosis of mental disorders and the identification of functional pathways. However, learning the interactions of the underlying subnetworks remains a significant challenge for existing Transformer-based methods due to the limited number of training samples. To address these challenges, we propose KD-Brain, a Prior-Informed Graph Learning framework for explicitly encoding prior knowledge to guide the learning process. Specifically, we design a Semantic-Conditioned Interaction mechanism that injects semantic priors into the attention query, explicitly navigating the subnetwork interactions based on their functional identities. Furthermore, we introduce a Pathology-Consistent Constraint, which regularizes the model optimization by aligning the learned interaction distributions with clinical priors. Additionally, KD-Brain leads to state-of-the-art performance on a wide range of disorder diagnosis tasks and identifies interpretable biomarkers consistent with psychiatric pathophysiology. Our code is available at https://anonymous.4open.science/r/KDBrain.

Siyu Liu, Guangqi Wen, Peng Cao +4

Computer Science and Engineering, Northeastern University, Shenyang, China · Key Laboratory of Intelligent Computing in Medical Image of Ministry of Education, Northeastern University, Shenyang, China · School of Computer Science and Artificial Intelligence, Shandong Normal University, Jinan, China +5

Brain Network AnalysisFunctional ConnectivityMedical DiagnosisGraph Structure Learning
AskPDF
Mar 10, 2026

Learning Bayesian and Markov Networks with an Unreliable Oracle

We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable.

Juha Harviainen, Pekka Parviainen, Vidya Sagar Sharma

University of Helsinki, Finland · University of Bergen, Norway · Indian Institute of Technology Madras, India

Graph Structure LearningBayesian Network Structure LearningProbabilistic Graphical ModelsBayesian NetworksMarkov Random Fields
AskPDF
Mar 6, 2026

Polarized Direct Cross-Attention Message Passing in GNNs for Machinery Fault Diagnosis

The reliability of safety-critical industrial systems hinges on accurate and robust fault diagnosis in rotating machinery. Conventional graph neural networks (GNNs) for machinery fault diagnosis face limitations in modeling complex dynamic interactions due to their reliance on predefined static graph structures and homogeneous aggregation schemes. To overcome these challenges, this paper introduces polarized direct cross-attention (PolaDCA), a novel relational learning framework that enables adaptive message passing through data-driven graph construction. Our approach builds upon a direct cross-attention (DCA) mechanism that dynamically infers attention weights from three semantically distinct node features (such as individual characteristics, neighborhood consensus, and neighborhood diversity) without requiring fixed adjacency matrices. Theoretical analysis establishes PolaDCA's superior noise robustness over conventional GNNs. Extensive experiments on industrial datasets (i.e., XJTUSuprgear, CWRUBearing and Three-Phase Flow Facility datasets) demonstrate state-of-the-art diagnostic accuracy and enhanced generalization under varying noise conditions, outperforming seven competitive baseline methods. The proposed framework provides an effective solution for safety-critical industrial applications.

Zongyu Shi, Laibin Zhang, Maoyin Chen

Department of Automation, College of Artificial Intelligence, China University of Petroleum (Beijing), Beijing 102299, China · Department of Safety Engineering, College of Safety and Ocean Engineering, China University of Petroleum (Beijing), Beijing 102299, China

Graph Neural NetworksFault DiagnosisDynamic Graph LearningGraph Structure LearningNeural Network Robustness
AskPDF
Mar 3, 2026

Beyond One-Size-Fits-All: Adaptive Subgraph Denoising for Zero-Shot Graph Learning with Large Language Models

Graph-based tasks in the zero-shot setting remain a significant challenge due to data scarcity and the inability of traditional Graph Neural Networks (GNNs) to generalize to unseen domains or label spaces. While recent advancements have transitioned toward leveraging Large Language Models (LLMs) as predictors to enhance GNNs, these methods often suffer from cross-modal alignment issues. A recent paradigm (i.e., Graph-R1) overcomes the aforementioned architectural dependencies by adopting a purely text-based format and utilizing LLM-based graph reasoning, showing improved zero-shot generalization. However, it employs a task-agnostic, one-size-fits-all subgraph extraction strategy, which inevitably introduces significant structural noise--irrelevant neighbors and edges--that distorts the LLMs' receptive field and leads to suboptimal predictions. To address this limitation, we introduce GraphSSR, a novel framework designed for adaptive subgraph extraction and denoising in zero-shot LLM-based graph reasoning. Specifically, we propose the SSR pipeline, which dynamically tailors subgraph extraction to specific contexts through a "Sample-Select-Reason" process, enabling the model to autonomously filter out task-irrelevant neighbors and overcome the one-size-fits-all issue. To internalize this capability, we develop SSR-SFT, a data synthesis strategy that generates high-quality SSR-style graph reasoning traces for supervised fine-tuning of LLMs. Furthermore, we propose SSR-RL, a two-stage reinforcement learning framework that explicitly regulates sampling and selection operations within the proposed SSR pipeline designed for adaptive subgraph denoising. By incorporating Authenticity-Reinforced and Denoising-Reinforced RL, we guide the model to achieve accurate predictions using parsimonious, denoised subgraphs for reasoning.

Fengzhi Li, Liang Zhang, Yuan Zuo +5

JIUTIAN Research, Beijing, China · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China · MIIT Key Laboratory of Data and Decision Intelligence, Beihang University, Beijing, China +1

LLM Reasoning with GraphsZero-Shot LearningGraph Structure LearningGraph Representation LearningRL for Language Model Reasoning
AskPDF
Mar 2, 2026

Learning graph topology from metapopulation epidemic encoder-decoder

Metapopulation epidemic models are a valuable tool for studying large-scale outbreaks. With the limited availability of epidemic tracing data, it is challenging to infer the essential constituents of these models, namely, the epidemic parameters and the relevant mobility network between subpopulations. Either one of these constituents can be estimated while assuming the other; however, the problem of their joint inference has not yet been solved. Here, we propose two encoder-decoder deep learning architectures that infer metapopulation mobility graphs from time-series data, with and without the assumption of epidemic model parameters. Evaluation across diverse random and empirical mobility networks shows that the proposed approach outperforms the state-of-the-art topology inference. Further, we show that topology inference improves dramatically with data on additional pathogens. Our study establishes a robust framework for simultaneously inferring epidemic parameters and topology, addressing a persistent gap in modeling disease propagation.

Xin Li, Jonathan Cohen, Shai Pilosof +1

Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Be’er Sheva, South District, Israel · Department of Life Sciences, Ben-Gurion University of the Negev, Be’er Sheva, South District, Israel · The Goldman Sonnenfeldt School of Sustainability and Climate Change, Ben-Gurion University of the Negev, Be’er Sheva, South District, Israel

Graph Structure LearningSpatial Epidemic ModelingParameter Estimation
AskPDF
Feb 26, 2026

Learning Disease-Sensitive Latent Interaction Graphs From Noisy Cardiac Flow Measurements

Cardiac blood flow patterns contain rich information about disease severity and clinical interventions, yet current imaging and computational methods fail to capture underlying relational structures of coherent flow features. We propose a physics-informed, latent relational framework to model cardiac vortices as interacting nodes in a graph. Our model combines a neural relational inference architecture with physics-inspired interaction energy and birth-death dynamics, yielding a latent graph sensitive to disease severity and intervention level. We first develop the method using computational fluid dynamics simulations of aortic coarctation, where learned interaction graphs reveal increasingly structured vortex interactions as vessel narrowing progresses. The resulting graph entropy exhibits a strong monotonic relationship with coarctation severity (R2=0.78R^2=0.78, Spearman ∣ρ∣=0.96|ρ|=0.96). We then evaluate the framework on fluid-structure interaction simulations of intracranial aneurysms using multiple geometric severity descriptors. Among these, aneurysm volume produces the most informative latent representation, with non-interaction graph entropy demonstrating a strong monotonic relationship with severity (Spearman ∣ρ∣=0.91|ρ| = 0.91) and generalising to several alternative morphological measures. Finally, we apply the approach to ultrasound-derived flow fields of a left ventricle under varying levels of left ventricular assist device support, where the latent graph captures the progressive loss of coherent vortex interactions under mechanical assistance, demonstrating cross-modal generalisation to imaging data. Across all datasets, latent interaction graphs and graph entropy provide interpretable markers of disease severity and intervention, linking haemodynamic organisation to clinically relevant physiological changes.

Viraj Patel, Marko Grujic, Philipp Aigner +4

Department of Computer Science, University of Bath, Bath, UK · Christian Doppler Laboratory for Mechanical Circulatory Support, Department of Cardiac and Thoracic Aortic Surgery, Medical University of Vienna, Vienna, Austria · Department of Mechanical Engineering, University of Bath, Bath, UK

Graph Structure LearningPhysics-Informed GNNsDynamic Graph Learning
AskPDF
Feb 25, 2026

RABot: Reinforcement-Guided Graph Augmentation for Imbalanced and Noisy Social Bot Detection

Social bot detection is pivotal for safeguarding the integrity of online information ecosystems. Although recent graph neural network (GNN) solutions achieve strong results, they remain hindered by two practical challenges: (i) severe class imbalance arising from the high cost of generating bots, and (ii) topological noise introduced by bots that skillfully mimic human behavior and forge deceptive links. We propose the Reinforcement-guided graph Augmentation social Bot detector (RABot), a multi-granularity graph-augmentation framework that addresses both issues in a unified manner. RABot employs a neighborhood-aware oversampling strategy that linearly interpolates minority-class embeddings within local subgraphs, thereby stabilizing the decision boundary under low-resource regimes. Concurrently, a reinforcement-learning-driven edge-filtering module combines similarity-based edge features with adaptive threshold optimization to excise spurious interactions during message passing, yielding a cleaner topology. Extensive experiments on three real-world benchmarks and four GNN backbones demonstrate that RABot consistently surpasses state-of-the-art baselines. In addition, since its augmentation and filtering modules are orthogonal to the underlying architecture, RABot can be seamlessly integrated into existing GNN pipelines to boost performance with minimal overhead.

Longlong Zhang, Xi Wang, Haotong Du +3

School of Artificial Intelligence, Optics and Electronics (iOPEN), Northwestern Polytechnical University · Shenzhen Research Institute, Northwestern Polytechnical University · School of Automation Science and Engineering, Xi’an Jiaotong University +1

Social Bot DetectionGraph Data AugmentationData AugmentationClass-Imbalanced LearningGraph Neural NetworksGraph Structure Learning
AskPDF
Feb 20, 2026

Causal Neighbourhood Learning for Invariant Graph Representations

Graph data often contain noisy and spurious correlations that mask the true causal relationships, which are essential for enabling graph models to make predictions based on the underlying causal structure of the data. Dependence on spurious connections makes it challenging for traditional Graph Neural Networks (GNNs) to generalize effectively across different graphs. Furthermore, traditional aggregation methods tend to amplify these spurious patterns, limiting model robustness under distribution shifts. To address these issues, we propose Causal Neighbourhood Learning with Graph Neural Networks (CNL-GNN), a novel framework that performs causal interventions on graph structure. CNL-GNN effectively identifies and preserves causally relevant connections and reduces spurious influences through the generation of counterfactual neighbourhoods and adaptive edge perturbation guided by learnable importance masking and an attention-based mechanism. In addition, by combining structural-level interventions with the disentanglement of causal features from confounding factors, the model learns invariant node representations that are robust and generalize well across different graph structures. Our approach improves causal graph learning beyond traditional feature-based methods, resulting in a robust classification model. Extensive experiments on four publicly available datasets, including multiple domain variants of one dataset, demonstrate that CNL-GNN outperforms state-of-the-art GNN models.

Simi Job, Xiaohui Tao, Taotao Cai +2

School of Science, Engineering and Digital Technologies, University of Southern Queensland, Australia. · School of Data Science, Lingnan University, Hong Kong.

Graph Representation LearningCausal Representation LearningOOD GeneralizationGraph Structure LearningCausal Inference
AskPDF
Feb 19, 2026

AdvSynGNN: Structure-Adaptive Graph Neural Nets via Adversarial Synthesis and Self-Corrective Propagation

Graph neural networks frequently encounter significant performance degradation when confronted with structural noise or non-homophilous topologies. To address these systemic vulnerabilities, we present AdvSynGNN, a comprehensive architecture designed for resilient node-level representation learning. The proposed framework orchestrates multi-resolution structural synthesis alongside contrastive objectives to establish geometry-sensitive initializations. We develop a transformer backbone that adaptively accommodates heterophily by modulating attention mechanisms through learned topological signals. Central to our contribution is an integrated adversarial propagation engine, where a generative component identifies potential connectivity alterations while a discriminator enforces global coherence. Furthermore, label refinement is achieved through a residual correction scheme guided by per-node confidence metrics, which facilitates precise control over iterative stability. Empirical evaluations demonstrate that this synergistic approach effectively optimizes predictive accuracy across diverse graph distributions while maintaining computational efficiency. The study concludes with practical implementation protocols to ensure the robust deployment of the AdvSynGNN system in large-scale environments.

Rong Fu, Chunlei Meng, Shuo Yin +2

Independent Researcher

Graph Neural NetworksGraph Structure LearningGraph Transformer
AskPDF
Feb 17, 2026

Including Node Textual Metadata in Laplacian-constrained Gaussian Graphical Models

This paper addresses graph learning in Gaussian Graphical Models (GGMs). In this context, data matrices often come with auxiliary metadata (e.g., textual descriptions associated with each node) that is usually ignored in traditional graph estimation processes. To fill this gap, we propose a graph learning approach based on Laplacian-constrained GGMs that jointly leverages the node signals and such metadata. The resulting formulation yields an optimization problem, for which we develop an efficient majorization-minimization (MM) algorithm with closed-form updates at each iteration. Experimental results on a real-world financial dataset demonstrate that the proposed method significantly improves graph clustering performance compared to state-of-the-art approaches that use either signals or metadata alone, thus illustrating the interest of fusing both sources of information.

Jianhua Wang, Killian Cressant, Pedro Braconnot Velloso +1

Université Paris-Nanterre, LEME, IUT Ville d’Avray, Ville d’Avray, France · Conservatoire National des Arts et Métiers, CNAM, Paris, France

Graph Structure LearningProbabilistic Graphical ModelsText-Attributed Graph Learning
AskPDF
Nov 21, 2025

A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs

We study the problem of learning an unknown graph via group queries on node subsets, where each query reports whether at least one edge is present among the queried nodes. In general, learning arbitrary graphs with nn nodes and kk edges is hard in the non-adaptive setting, requiring Ω(min⁡{k2log⁡n, n2})Ω\big(\min\{k^2\log n,\,n^2\}\big) tests even when a small error probability is allowed. We focus on learning Erdős--Rényi (ER) graphs G∼ER(n,q)G\sim\mathrm{ER}(n,q) in the non-adaptive setting, where the expected number of edges is kˉ=q(n2)\bar{k}=q\binom{n}{2}, and we aim to design an efficient testing--decoding scheme, namely, a non-adaptive test design together with a decoding algorithm, achieving asymptotically vanishing error probability. Prior work (Li--Fresacher--Scarlett, NeurIPS 2019) presents a testing--decoding scheme that attains an order-optimal number of tests O(kˉlog⁡n)O(\bar{k}\log n) but incurs Ω(n2)Ω(n^2) decoding time, whereas their proposed sublinear-time algorithm incurs an extra (log⁡kˉ)(log⁡n)(\log \bar{k})(\log n) factor in the number of tests. We extend the binary splitting approach, recently developed for non-adaptive group testing, to the ER graph learning setting, and prove that the edge set can be recovered with high probability using O(kˉlog⁡n)O(\bar{k}\log n) tests while attaining decoding time O(kˉ1+δlog⁡n)O(\bar{k}^{1+δ}\log n) for any fixed δ>0δ>0.

Hoang Ta, Jonathan Scarlett

Department of Computer Science, School of Computing, National University of Singapore (NUS), Singapore 117417 · Department of Computer Science, Hanoi University of Science and Technology, Vietnam · Department of Computer Science, Department of Mathematics, and Institute of Data Science, NUS, Singapore 117417

Graph Structure Learning
AskPDF
Sep 2, 2025

Design of Experiment for Discovering Directed Mixed Graph

We study the design of interventions for causal discovery in simple structural causal models whose causal graphs are directed mixed graphs (DMGs) that may contain directed cycles and bidirected edges representing latent confounding. In such case, observational conditional-independence (CI) information may not identify even the graph skeleton, while CI alone cannot generally detect a bidirected edge coexisting with a directed edge. To this end, we propose a stage-wise framework based on tailored separating systems. Separating-system interventions first recover descendant relations and strongly connected components (SCCs). The SCCs are then ordered by ancestry, and an SCC-Anc separating system recovers the directed subgraph. Given this subgraph, further systems use CI tests interpreted through dd- or σσ-separation to recover non-adjacent bidirected edges, whose endpoints share no directed edge, and do-see comparisons to recover those coexisting with exactly one directed edge. Under our assumptions, the framework recovers the directed subgraph and every bidirected edge except double-adjacent ones, whose endpoints are connected by a directed edge in each direction. We develop algorithms for unrestricted and MM-bounded settings, with each experiment targeting at most MM variables in the latter. For recovering the directed subgraph and non-adjacent bidirected edges, our upper bounds on the number and maximum size of experiments match corresponding worst-case lower bounds up to logarithmic factors.

Haijie Xu, Chen Zhang

Department of Industrial Engineering Tsinghua University

Graph Structure LearningCausal DiscoveryCausal InterventionCausal Discovery with Latent Confounding
AskPDF
Aug 20, 2025

Graph Structure Learning with Temporal Graph Information Bottleneck for Inductive Representation Learning

Temporal graph learning is crucial for dynamic networks where nodes and edges evolve over time and new nodes continuously join the system. Inductive representation learning in such settings faces two major challenges: effectively representing unseen nodes and mitigating noisy or redundant graph information. We propose GTGIB, a versatile framework that integrates Graph Structure Learning (GSL) with Temporal Graph Information Bottleneck (TGIB). We design a novel two-step GSL-based structural enhancer to enrich and optimize node neighborhoods and demonstrate its effectiveness and efficiency through theoretical proofs and experiments. The TGIB refines the optimized graph by extending the information bottleneck principle to temporal graphs, regularizing both edges and features based on our derived tractable TGIB objective function via variational approximation, enabling stable and efficient optimization. GTGIB-based models are evaluated to predict links on four real-world datasets; they outperform existing methods in all datasets under the inductive setting, with significant and consistent improvement in the transductive setting.

Jiafeng Xiong, Rizos Sakellariou

Department of Computer Science, University of Manchester, UK

Graph Structure LearningTemporal GNNsGraph Representation LearningTemporal Link PredictionDynamic Graph Learning
AskPDF
Jul 27, 2025

Learning Latent Graph Geometry via Fixed-Point Schrödinger-Type Activation: A Theoretical Study

We study neural architectures in which each hidden layer is defined by the stationary state of a dissipative Schrödinger-type dynamics on a learned latent graph. On stable branches, the local stationary problem defines a differentiable implicit graph layer. To learn the graph itself, we optimize over the stratified moduli space of weighted graphs and equip each stratum with a non-degenerate Kähler-Hessian metric that keeps natural-gradient descent and face crossing well posed. We then show that a multilayer stationary network is equivalent to an exact global stationary problem on a supra-graph, and that it admits a penalized global relaxation whose stationary states converge to the exact one as the penalty parameter tends to infinity. Reverse-mode differentiation is recovered as the adjoint of the exact global system, and the penalized adjoint converges to it in the same limit. Finally, under finite-dimensional strong-monotonicity and admissible-lift assumptions, the corresponding represented hypothesis classes coincide among resolvent feed-forward networks, graph-stationary networks, supra-graph stationary systems, and sheaf-based architectures with unitary connection. The resulting structural identifications yield complexity bounds controlled by sparse graph or supra-graph geometry rather than dense ambient connectivity.

Dmitry Pasechnyuk-Vilensky, Martin Takáč

MBZUAI, UAE

Graph Structure LearningGraph Neural NetworksGraph Representation LearningSheaf Neural NetworksNeural Network Approximation Theory
AskPDF
Jun 2, 2025

Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming

Signed graphs are equipped with both positive and negative edge weights, encoding pairwise correlations as well as anti-correlations in data. A balanced signed graph is a signed graph with no cycles containing an odd number of negative edges. Laplacian of a balanced signed graph has eigenvectors that map via a simple linear transform to ones in a corresponding positive graph Laplacian, thus enabling reuse of spectral filtering tools designed for positive graphs. We propose an efficient computation method to learn a balanced signed graph Laplacian directly from data. Specifically, extending a previous linear programming (LP) based sparse inverse covariance estimation method called CLIME, we formulate a new LP problem for each Laplacian column ii, where the linear constraints restrict weight signs of edges stemming from node ii, so that nodes of same / different polarities are connected by positive / negative edges. We derive a feasible CLIME parameter ρiρ_i for each sign-constrained column problem. We solve the LP problem efficiently by tailoring a sparse LP method based on ADMM. We theoretically prove that the row / column updates produce a non-increasing objective sequence, and show that the iterations are terminated in a finite number of steps. Extensive experimental results on synthetic and real-world datasets show that our balanced graph learning method outperforms competing methods and enables reuse of spectral filters, wavelets, and graph neural nets (GNN) constructed for positive graphs.

Haruki Yokota, Hiroshi Higashi, Yuichi Tanaka +1

Graph Structure LearningGraph Representation LearningAlternating Direction Method of MultipliersLinear Programming
AskPDF
Mar 27, 2025

LLaTA: Unlocking Graph Structure Learning with Tree-Guided Large Language Models

The emergence of large language models (LLMs) has popularized text-attributed graphs (TAGs), creating an urgent need for graph structure learning (GSL) methods that effectively leverage textual information. However, existing GSL approaches are designed for traditional graphs without text, and adapting them to LLMs faces two challenges: defining a suitable optimization objective given LLMs' massive parameters, and designing an efficient architecture without costly fine-tuning. To address these, we propose LLaTA (Large Language and Tree Assistant), which reformulates GSL as a tree optimization framework---shifting from training edge predictors to designing a language-aware tree sampler. LLaTA constructs structural encoding trees via entropy minimization to capture topology, then leverages tree-guided LLM in-context learning to integrate textual semantics without fine-tuning. Extensive experiments on 11 datasets demonstrate LLaTA's flexibility with any backbone, superior scalability over LLM-based GSL methods, and state-of-the-art effectiveness across diverse domains.

Zhihan Zhang, Xunkai Li, Hongchao Qin +2

Beijing Institute of Technology

Graph Structure LearningText-Attributed Graph LearningLLMs for Graph Learning
AskPDF
Dec 11, 2024

GLL: A Differentiable Graph Learning Layer for Neural Networks

Standard deep learning architectures used for classification generate label predictions with a projection head and softmax activation function. Although successful, these methods fail to leverage the relational information between samples for generating label predictions. In recent works, graph-based learning techniques, namely Laplace learning, have been heuristically combined with neural networks for both supervised and semi-supervised learning (SSL) tasks. However, prior works approximate the gradient of the loss function with respect to the graph learning algorithm or decouple the processes; end-to-end integration with neural networks is not achieved. In this work, we derive backpropagation equations, via the adjoint method, for inclusion of a general family of graph learning layers into a neural network. The resulting method, distinct from graph neural networks, allows us to precisely integrate similarity graph construction and graph Laplacian-based label propagation into a neural network layer, replacing a projection head and softmax activation function for general classification task. Our experimental results demonstrate smooth label transitions across data, improved generalization and robustness to adversarial attacks, and improved training dynamics compared to a standard softmax-based approach.

Jason Brown, Bohan Chen, Harris Hardiman-Mostow +2

Department of Mathematics University of California, Los Angeles Los Angeles, CA 90095, USA · Computing + Mathematical Sciences (CMS) Department California Institute of Technology Pasadena, CA 91125, USA · School of Mathematics University of Minnesota Minneapolis, MN 55455, USA

Graph-Based Label PropagationGraph-Based Semi-Supervised LearningGraph Structure Learning
AskPDF
Jan 10, 2020

Time-Varying Graph Learning with Constraints on Graph Temporal Variation

We propose a novel framework for learning time-varying graphs from spatiotemporal measurements. Given an appropriate prior on the temporal behavior of signals, our proposed method can estimate time-varying graphs from a small number of available measurements. To achieve this, we introduce three regularization terms in convex optimization problems that constrain the sparseness of temporal variations of the time-varying networks. Moreover, a computationally scalable algorithm is introduced to solve the optimization problem efficiently. The experimental results with synthetic and real datasets (point cloud, temperature, and EEG data) demonstrate that our proposed method outperforms state-of-the-art methods.

Haruki Yokota, Koki Yamada, Yuichi Tanaka +1

Graduate School of Engineering, The University of Osaka, Osaka 565-0871, Japan · Graduate School of Engineering, Tokyo University of Agriculture and Technology, Tokyo 184-8588, Japan · Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, CA 90089 USA

Graph Signal ProcessingGraph Structure LearningGraph Representation LearningDynamic Graph Learning
AskPDF