Task-driven Heterophilic Graph Structure Learning

• URL: http://arxiv.org/abs/2512.23406v1
• Date: Mon, 29 Dec 2025 11:59:16 GMT
• Title: Task-driven Heterophilic Graph Structure Learning
• Authors: Ayushman Raghuvanshi, Gonzalo Mateos, Sundeep Prabhakar Chepuri,
• Abstract summary: Graph neural networks (GNNs) often struggle to learn discriminative node representations for heterophilic graphs.<n>We propose frequency-guided graph structure learning (FgGSL), an end-to-end graph inference framework.
• Score: 30.767828037086844
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) often struggle to learn discriminative node representations for heterophilic graphs, where connected nodes tend to have dissimilar labels and feature similarity provides weak structural cues. We propose frequency-guided graph structure learning (FgGSL), an end-to-end graph inference framework that jointly learns homophilic and heterophilic graph structures along with a spectral encoder. FgGSL employs a learnable, symmetric, feature-driven masking function to infer said complementary graphs, which are processed using pre-designed low- and high-pass graph filter banks. A label-based structural loss explicitly promotes the recovery of homophilic and heterophilic edges, enabling task-driven graph structure learning. We derive stability bounds for the structural loss and establish robustness guarantees for the filter banks under graph perturbations. Experiments on six heterophilic benchmarks demonstrate that FgGSL consistently outperforms state-of-the-art GNNs and graph rewiring methods, highlighting the benefits of combining frequency information with supervised topology inference.

Related papers

• GLANCE: Graph Logic Attention Network with Cluster Enhancement for Heterophilous Graph Representation Learning [47.674647127050186]
  Graph Neural Networks (GNNs) have demonstrated significant success in learning from graph-structured data but often struggle on heterophilous graphs.<n>We propose GLANCE, a novel framework that integrates logic-guided reasoning, dynamic graph refinement, and adaptive clustering to enhance graph representation learning.
  arXiv  Detail & Related papers  (2025-07-24T15:45:26Z)
• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph [19.222317334613162]
  Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes.<n>We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance.<n>We introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph.
  arXiv  Detail & Related papers  (2025-05-18T13:28:56Z)
• 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)
• Towards Robust Graph Structural Learning Beyond Homophily via Preserving Neighbor Similarity [26.990618075974485]
  We explore the vulnerability of graph-based learning systems regardless of the homophily degree.<n>We propose a novel graph structural learning strategy that serves as a useful graph mining module.
  arXiv  Detail & Related papers  (2024-01-18T06:57:29Z)
• 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 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)
• 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)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning. We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
  arXiv  Detail & Related papers  (2021-08-03T17:57:53Z)

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.