Joint Graph Rewiring and Feature Denoising via Spectral Resonance
When learning from graph data, the graph and the node features both give noisy information about the node labels. In this paper we propose an algorithm to jointly denoise the features and rewire the graph (JDR), which improves the performance of downstream node classification graph neural nets (GNNs). JDR works by aligning the leading spectral spaces of graph and feature matrices. It approximately solves the associated non-convex optimization problem in a way that handles graphs with multiple classes and different levels of homophily or heterophily. We theoretically justify JDR in a stylized setting and show that it consistently outperforms existing rewiring methods on a wide range of synthetic and real-world node classification tasks.
Code (1)
Tasks
DenoisingGraph LearningNode ClassificationSimilar Papers 제목 키워드 기반
GNNs Getting ComFy: Community and Feature Similarity Guided Rewiring
Maximizing the spectral gap through graph rewiring has been proposed to enhance the performance of message-passing graph neural networks (GNNs) by addressing over-squashing. However, as we show, minimizing the spectral g…
Node ClassificationLocality-Aware Graph-Rewiring in GNNs
Graph Neural Networks (GNNs) are popular models for machine learning on graphs that typically follow the message-passing paradigm, whereby the feature of a node is updated recursively upon aggregating information over it…
Inductive BiasDynamic Triangulation-Based Graph Rewiring for Graph Neural Networks
Graph Neural Networks (GNNs) have emerged as the leading paradigm for learning over graph-structured data. However, their performance is limited by issues inherent to graph topology, most notably oversquashing and oversm…
Node ClassificationFoSR: First-order spectral rewiring for addressing oversquashing in GNNs
Graph neural networks (GNNs) are able to leverage the structure of graph data by passing messages along the edges of the graph. While this allows GNNs to learn features depending on the graph structure, for certain graph…
Graph ClassificationPANDA: Expanded Width-Aware Message Passing Beyond Rewiring
Recent research in the field of graph neural network (GNN) has identified a critical issue known as "over-squashing," resulting from the bottleneck phenomenon in graph structures, which impedes the propagation of long-ra…
Graph ClassificationGraph Neural NetworkGraph RegressionNode Classification