Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation

• URL: http://arxiv.org/abs/2505.20992v1
• Date: Tue, 27 May 2025 10:26:15 GMT
• Title: Efficient Identity and Position Graph Embedding via Spectral-Based Random Feature Aggregation
• Authors: Meng Qin, Jiahong Liu, Irwin King,
• Abstract summary: Graph neural networks (GNNs) capture graph structures via a feature aggregation mechanism.<n>It is unclear for most GNN-based methods which property they can capture.<n>We propose random feature aggregation (RFA) for efficient identity and position embedding.
• Score: 37.25217644507099
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs), which capture graph structures via a feature aggregation mechanism following the graph embedding framework, have demonstrated a powerful ability to support various tasks. According to the topology properties (e.g., structural roles or community memberships of nodes) to be preserved, graph embedding can be categorized into identity and position embedding. However, it is unclear for most GNN-based methods which property they can capture. Some of them may also suffer from low efficiency and scalability caused by several time- and space-consuming procedures (e.g., feature extraction and training). From a perspective of graph signal processing, we find that high- and low-frequency information in the graph spectral domain may characterize node identities and positions, respectively. Based on this investigation, we propose random feature aggregation (RFA) for efficient identity and position embedding, serving as an extreme ablation study regarding GNN feature aggregation. RFA (i) adopts a spectral-based GNN without learnable parameters as its backbone, (ii) only uses random noises as inputs, and (iii) derives embeddings via just one feed-forward propagation (FFP). Inspired by degree-corrected spectral clustering, we further introduce a degree correction mechanism to the GNN backbone. Surprisingly, our experiments demonstrate that two variants of RFA with high- and low-pass filters can respectively derive informative identity and position embeddings via just one FFP (i.e., without any training). As a result, RFA can achieve a better trade-off between quality and efficiency for both identity and position embedding over various baselines.

Related papers

• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report [21.288230563135055]
  We propose a novel graph spectral sparsification method to approximate the propagation patterns of spectral Graph Neural Networks (GNNs)<n>Our method allows the application of linear layers on the input node features, enabling end-to-end training as well as the handling of raw features.
  arXiv  Detail & Related papers  (2025-01-08T15:36:19Z)
• LASE: Learned Adjacency Spectral Embeddings [7.612218105739107]
  We learn nodal Adjacency Spectral Embeddings (ASE) from graph inputs.<n>LASE is interpretable, parameter efficient, robust to inputs with unobserved edges.<n>LASE layers combine Graph Convolutional Network (GCN) and fully-connected Graph Attention Network (GAT) modules.
  arXiv  Detail & Related papers  (2024-12-23T17:35:19Z)
• Rank and Align: Towards Effective Source-free Graph Domain Adaptation [16.941755478093153]
  Graph neural networks (GNNs) have achieved impressive performance in graph domain adaptation. However, extensive source graphs could be unavailable in real-world scenarios due to privacy and storage concerns. We introduce a novel GNN-based approach called Rank and Align (RNA), which ranks graph similarities with spectral seriation for robust semantics learning.
  arXiv  Detail & Related papers  (2024-08-22T08:00:50Z)
• Noise-Resilient Unsupervised Graph Representation Learning via Multi-Hop Feature Quality Estimation [53.91958614666386]
  Unsupervised graph representation learning (UGRL) based on graph neural networks (GNNs) We propose a novel UGRL method based on Multi-hop feature Quality Estimation (MQE)
  arXiv  Detail & Related papers  (2024-07-29T12:24:28Z)
• Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Module [65.81781176362848]
  Graph Neural Networks (GNNs) can learn from graph-structured data through neighborhood information aggregation. As the number of layers increases, node representations become indistinguishable, which is known as over-smoothing. We propose a textbfPosterior-Sampling-based, Node-distinguish Residual module (PSNR).
  arXiv  Detail & Related papers  (2023-05-09T12:03:42Z)
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Neural Networks [46.14626839260314]
  We show that current Graph Neural Networks (GNNs) are potentially a problematic factor underlying all GNN models for learning on certain datasets. We augment the aggregation operations with their dual, i.e. diversification operators that make the node more distinct and preserve the identity. Such augmentation replaces the aggregation with a two-channel filtering process that, in theory, is beneficial for enriching the node representations. In the experiments, we observe desired characteristics of the models and significant performance boost upon the baselines on 9 node classification tasks.
  arXiv  Detail & Related papers  (2022-12-21T07:24:03Z)
• Local Augmentation for Graph Neural Networks [78.48812244668017]
  We introduce the local augmentation, which enhances node features by its local subgraph structures. Based on the local augmentation, we further design a novel framework: LA-GNN, which can apply to any GNN models in a plug-and-play manner.
  arXiv  Detail & Related papers  (2021-09-08T18:10:08Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  Graph Neural Networks (GNNs) explore the graph structure and node features by aggregating and transforming information within node neighborhoods. We propose SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs.
  arXiv  Detail & Related papers  (2020-11-19T04:18:01Z)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)
• Complete the Missing Half: Augmenting Aggregation Filtering with Diversification for Graph Convolutional Networks [46.14626839260314]
  We show that current Graph Neural Networks (GNNs) are potentially a problematic factor underlying all GNN methods for learning on certain datasets. We augment the aggregation operations with their dual, i.e. diversification operators that make the node more distinct and preserve the identity. Such augmentation replaces the aggregation with a two-channel filtering process that, in theory, is beneficial for enriching the node representations. In the experiments, we observe desired characteristics of the models and significant performance boost upon the baselines on 9 node classification tasks.
  arXiv  Detail & Related papers  (2020-08-20T08:45:16Z)

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.