Learning Kronecker-Structured Graphs from Smooth Signals

• URL: http://arxiv.org/abs/2505.09822v1
• Date: Wed, 14 May 2025 21:53:37 GMT
• Title: Learning Kronecker-Structured Graphs from Smooth Signals
• Authors: Changhao Shi, Gal Mishne,
• Abstract summary: Graph learning, or network inference, is a prominent problem in graph signal processing (GSP)<n>We propose an alternating non-structured problem Cartesian product scheme to tackle this graph learning problem.<n>We conduct experiments and demonstrate our approach's efficacy and superior performance compared to existing methods.
• Score: 8.594140167290098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph learning, or network inference, is a prominent problem in graph signal processing (GSP). GSP generalizes the Fourier transform to non-Euclidean domains, and graph learning is pivotal to applying GSP when these domains are unknown. With the recent prevalence of multi-way data, there has been growing interest in product graphs that naturally factorize dependencies across different ways. However, the types of graph products that can be learned are still limited for modeling diverse dependency structures. In this paper, we study the problem of learning a Kronecker-structured product graph from smooth signals. Unlike the more commonly used Cartesian product, the Kronecker product models dependencies in a more intricate, non-separable way, but posits harder constraints on the graph learning problem. To tackle this non-convex problem, we propose an alternating scheme to optimize each factor graph and provide theoretical guarantees for its asymptotic convergence. The proposed algorithm is also modified to learn factor graphs of the strong product. We conduct experiments on synthetic and real-world graphs and demonstrate our approach's efficacy and superior performance compared to existing methods.

Related papers

• Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals [18.45931641798935]
  This paper introduces Polynomial Graphical Lasso (PGL), a new approach to learning graph structures from nodal signals. Our key contribution lies in the signals as Gaussian and stationary on the graph, enabling the development of a graph-learning lasso.
  arXiv  Detail & Related papers  (2024-04-03T10:19:53Z)
• GraphEdit: Large Language Models for Graph Structure Learning [14.16155596597421]
  Graph Structure Learning (GSL) focuses on capturing intrinsic dependencies and interactions among nodes in graph-structured data.<n>Existing GSL methods heavily depend on explicit graph structural information as supervision signals.<n>We propose GraphEdit, an approach that leverages large language models (LLMs) to learn complex node relationships in graph-structured data.
  arXiv  Detail & Related papers  (2024-02-23T08:29:42Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  We study the problem of learning Cartesian product graphs under Laplacian constraints. We establish statistical consistency for the penalized maximum likelihood estimation. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values.
  arXiv  Detail & Related papers  (2024-02-12T22:48:30Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• Graph Laplacian Learning with Exponential Family Noise [8.594140167290098]
  We propose a versatile graph inference framework for learning from graph signals corrupted by exponential family noise. Our framework generalizes previous methods from continuous smooth graph signals to various data types.
  arXiv  Detail & Related papers  (2023-06-14T02:09:52Z)
• 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)
• Learning Product Graphs from Spectral Templates [3.04585143845864]
  Graph Learning (GL) is at the core of inference and analysis of connections in data mining and machine learning (ML) We propose learning product (high dimensional) graphs from product spectral templates with significantly reduced complexity. In contrast to the rare current approaches, our approach can learn all types of product graphs without knowing the type of graph products.
  arXiv  Detail & Related papers  (2022-11-05T12:28:11Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  We propose a graph convolutional relationship between the observed and latent graphs, and formulate the graph learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN) GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive.
  arXiv  Detail & Related papers  (2022-05-19T14:08:15Z)
• Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
  We propose an unsupervised graph structure learning paradigm, where the learned graph topology is optimized by data itself without any external guidance. Specifically, we generate a learning target from the original data as an "anchor graph", and use a contrastive loss to maximize the agreement between the anchor graph and the learned graph.
  arXiv  Detail & Related papers  (2022-01-17T11:57:29Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• 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)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)

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.