Learning Graph from Smooth Signals under Partial Observation: A Robustness Analysis

• URL: http://arxiv.org/abs/2509.14887v1
• Date: Thu, 18 Sep 2025 12:09:40 GMT
• Title: Learning Graph from Smooth Signals under Partial Observation: A Robustness Analysis
• Authors: Hoang-Son Nguyen, Hoi-To Wai,
• Abstract summary: We show that vanilla graph topology learning methods are implicitly robust to partial observations of low-pass filtered graph signals.<n>We show that smoothness-based graph learning formulation can recover the ground truth graph topology corresponding to the observed nodes.
• Score: 22.116133023519676
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning the graph underlying a networked system from nodal signals is crucial to downstream tasks in graph signal processing and machine learning. The presence of hidden nodes whose signals are not observable might corrupt the estimated graph. While existing works proposed various robustifications of vanilla graph learning objectives by explicitly accounting for the presence of these hidden nodes, a robustness analysis of "naive", hidden-node agnostic approaches is still underexplored. This work demonstrates that vanilla graph topology learning methods are implicitly robust to partial observations of low-pass filtered graph signals. We achieve this theoretical result through extending the restricted isometry property (RIP) to the Dirichlet energy function used in graph learning objectives. We show that smoothness-based graph learning formulation (e.g., the GL-SigRep method) on partial observations can recover the ground truth graph topology corresponding to the observed nodes. Synthetic and real data experiments corroborate our findings.

Related papers

• Knowledge Probing for Graph Representation Learning [12.960185655357495]
  We propose a novel graph probing framework (GraphProbe) to investigate and interpret whether the family of graph learning methods has encoded different levels of knowledge in graph representation learning. Based on the intrinsic properties of graphs, we design three probes to systematically investigate the graph representation learning process from different perspectives. We construct a thorough evaluation benchmark with nine representative graph learning methods from random walk based approaches, basic graph neural networks and self-supervised graph methods, and probe them on six benchmark datasets for node classification, link prediction and graph classification.
  arXiv  Detail & Related papers  (2024-08-07T16:27:45Z)
• Learning Latent Graph Structures and their Uncertainty [63.95971478893842]
  We show that minimizing point-prediction losses does not guarantee proper learning of latent relational information.<n>We propose a sampling-based method that solves this joint learning task.
  arXiv  Detail & Related papers  (2024-05-30T10:49:22Z)
• Bures-Wasserstein Means of Graphs [60.42414991820453]
  We propose a novel framework for defining a graph mean via embeddings in the space of smooth graph signal distributions. By finding a mean in this embedding space, we can recover a mean graph that preserves structural information. We establish the existence and uniqueness of the novel graph mean, and provide an iterative algorithm for computing it.
  arXiv  Detail & Related papers  (2023-05-31T11:04:53Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
  We propose a joint graph learning method that takes into account the presence of hidden (latent) variables. We exploit the structure resulting from the previous considerations to propose a convex optimization problem. We compare the proposed algorithm with different baselines and evaluate its performance over synthetic and real-world graphs.
  arXiv  Detail & Related papers  (2022-12-04T13:03:41Z)
• Learning Robust Representation through Graph Adversarial Contrastive Learning [6.332560610460623]
  Existing studies show that node representations generated by graph neural networks (GNNs) are vulnerable to adversarial attacks. We propose a novel Graph Adversarial Contrastive Learning framework (GraphACL) by introducing adversarial augmentations into graph self-supervised learning.
  arXiv  Detail & Related papers  (2022-01-31T07:07:51Z)
• Graph Structure Learning with Variational Information Bottleneck [70.62851953251253]
  We propose a novel Variational Information Bottleneck guided Graph Structure Learning framework, namely VIB-GSL. VIB-GSL learns an informative and compressive graph structure to distill the actionable information for specific downstream tasks.
  arXiv  Detail & Related papers  (2021-12-16T14:22:13Z)
• Kernel-based Graph Learning from Smooth Signals: A Functional Viewpoint [15.577175610442351]
  We propose a novel graph learning framework that incorporates the node-side and observation-side information. We use graph signals as functions in the reproducing kernel Hilbert space associated with a Kronecker product kernel. We develop a novel graph-based regularisation method which, when combined with the Kronecker product kernel, enables our model to capture both the dependency explained by the graph and the dependency due to graph signals.
  arXiv  Detail & Related papers  (2020-08-23T16:04:23Z)
• GraphOpt: Learning Optimization Models of Graph Formation [72.75384705298303]
  We propose an end-to-end framework that learns an implicit model of graph structure formation and discovers an underlying optimization mechanism. The learned objective can serve as an explanation for the observed graph properties, thereby lending itself to transfer across different graphs within a domain. GraphOpt poses link formation in graphs as a sequential decision-making process and solves it using maximum entropy inverse reinforcement learning algorithm.
  arXiv  Detail & Related papers  (2020-07-07T16:51:39Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.