Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning

• URL: http://arxiv.org/abs/2309.03537v3
• Date: Mon, 08 Sep 2025 03:59:11 GMT
• Title: Data-Adaptive Graph Framelets with Generalized Vanishing Moments for Graph Machine Learning
• Authors: Ruigang Zheng, Xiaosheng Zhuang,
• Abstract summary: We construct tight framelet systems on graphs with localized supports based on partition trees.<n>We exploit the generality of our proposed graph framelet systems for heterophilous graph learning.<n>We derive a specific system of graph framelets and propose a method to select framelets as features for neural network input.
• Score: 4.498623132806496
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we propose a general framework for constructing tight framelet systems on graphs with localized supports based on partition trees. Our construction of framelets provides a simple and efficient way to obtain the orthogonality with $k$ arbitrary orthonormal vectors. When the $k$ vectors contain most of the energy of a family of graph signals, the orthogonality of the framelets intuitively possesses ``generalized ($k$-)vanishing'' moments, and thus, the coefficients are sparse. Moreover, our construction provides not only framelets that are overall sparse vectors but also fast and schematically concise transforms. In a data-adaptive setting, the graph framelet systems can be learned by conducting optimizations on Stiefel manifolds to provide the utmost sparsity for a given family of graph signals. Furthermore, we further exploit the generality of our proposed graph framelet systems for heterophilous graph learning, where graphs are characterized by connecting nodes mainly from different classes. The usual assumption that connected nodes are similar and belong to the same class for homophilious graphs is contradictory for heterophilous graphs. Thus, we are motivated to bypass simple assumptions on heterophilous graphs and focus on generating rich node features induced by the graph structure, so as to improve the graph learning ability of certain neural networks in node classification. We derive a specific system of graph framelets and propose a heuristic method to select framelets as features for neural network input. Several experiments demonstrate the effectiveness and superiority of our approach for non-linear approximation, denoising, and node classification.

Related papers

• Bespoke multiresolution analysis of graph signals [0.0]
  We present a novel framework for discrete multiresolution analysis of graph signals.<n>The main analytical tool is the samplet transform, originally defined in the Euclidean framework as a discrete wavelet-like construction.<n>For efficient numerical implementation, we combine heavy edge clustering, to partition the graph into meaningful patches.
  arXiv  Detail & Related papers  (2025-07-25T11:43:19Z)
• RGL: A Graph-Centric, Modular Framework for Efficient Retrieval-Augmented Generation on Graphs [58.10503898336799]
  We introduce the RAG-on-Graphs Library (RGL), a modular framework that seamlessly integrates the complete RAG pipeline. RGL addresses key challenges by supporting a variety of graph formats and integrating optimized implementations for essential components. Our evaluations demonstrate that RGL not only accelerates the prototyping process but also enhances the performance and applicability of graph-based RAG systems.
  arXiv  Detail & Related papers  (2025-03-25T03:21:48Z)
• Robust Graph Structure Learning under Heterophily [12.557639223778722]
  We propose a novel robust graph structure learning method to achieve a high-quality graph from heterophilic data for downstream tasks. We first apply a high-pass filter to make each node more distinctive from its neighbors by encoding structure information into the node features. Then, we learn a robust graph with an adaptive norm characterizing different levels of noise.
  arXiv  Detail & Related papers  (2024-03-06T12:29:13Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• Contrastive Learning for Non-Local Graphs with Multi-Resolution Structural Views [1.4445779250002606]
  We propose a novel multiview contrastive learning approach that integrates diffusion filters on graphs. By incorporating multiple graph views as augmentations, our method captures the structural equivalence in heterophilic graphs.
  arXiv  Detail & Related papers  (2023-08-19T17:42:02Z)
• 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)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53: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)
• Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport [26.58964162799207]
  We propose SLOTAlign, an unsupervised graph alignment framework that jointly performs Structure Learning and Optimal Transport Alignment. We incorporate multi-view structure learning to enhance graph representation power and reduce the effect of structure and feature inconsistency inherited across graphs. The proposed SLOTAlign shows superior performance and strongest robustness over seven unsupervised graph alignment methods and five specialized KG alignment methods.
  arXiv  Detail & Related papers  (2023-01-30T08:41:36Z)
• Graph Attention Retrospective [14.52271219759284]
  Graph-based learning is a rapidly growing sub-field of machine learning with applications in social networks, citation networks, and bioinformatics. In this paper, we theoretically study the behaviour of graph attention networks. We show that in an "easy" regime, where the distance between the means of the Gaussians is large enough, graph attention is able to distinguish inter-class from intra-class edges. In the "hard" regime, we show that every attention mechanism fails to distinguish intra-class from inter-class edges.
  arXiv  Detail & Related papers  (2022-02-26T04:58:36Z)
• 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)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• How Framelets Enhance Graph Neural Networks [27.540282741523253]
  This paper presents a new approach for assembling graph neural networks based on framelet transforms. We propose shrinkage as a new activation for the framelet convolution, which thresholds the high-frequency information at different scales.
  arXiv  Detail & Related papers  (2021-02-13T19:19:19Z)
• Promoting Graph Awareness in Linearized Graph-to-Text Generation [72.83863719868364]
  We study the ability of linearized models to encode local graph structures. Our findings motivate solutions to enrich the quality of models' implicit graph encodings. We find that these denoising scaffolds lead to substantial improvements in downstream generation in low-resource settings.
  arXiv  Detail & Related papers  (2020-12-31T18:17:57Z)
• Decimated Framelet System on Graphs and Fast G-Framelet Transforms [3.7277730514654555]
  An adequate representation of graph data is vital to the learning performance of a statistical or machine learning model for graph-structured data. We propose a novel multiscale representation system for graph data, called decimated framelets, which form a localized tight frame on the graph. The effectiveness is demonstrated by real-world applications, including multiresolution analysis for traffic network, and graph neural networks for graph classification tasks.
  arXiv  Detail & Related papers  (2020-12-12T23:57:17Z)
• Dirichlet Graph Variational Autoencoder [65.94744123832338]
  We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors. Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
  arXiv  Detail & Related papers  (2020-10-09T07:35:26Z)
• 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)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)
• Homology-Preserving Multi-Scale Graph Skeletonization Using Mapper on Graphs [5.86893539706548]
  We propose to apply the mapper construction -- a popular tool in topological data analysis -- to graph visualization. We develop a variation of the mapper construction targeting weighted, undirected graphs, called mog, which generates homology-preserving skeletons of graphs. We provide a software tool that enables interactive explorations of such skeletons and demonstrate the effectiveness of our method for synthetic and real-world data.
  arXiv  Detail & Related papers  (2018-04-03T19:18:36Z)

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.