On the Two Sides of Redundancy in Graph Neural Networks
- URL: http://arxiv.org/abs/2310.04190v2
- Date: Thu, 28 Mar 2024 12:56:25 GMT
- Title: On the Two Sides of Redundancy in Graph Neural Networks
- Authors: Franka Bause, Samir Moustafa, Johannes Langguth, Wilfried N. Gansterer, Nils M. Kriege,
- Abstract summary: We develop a novel aggregation scheme based on neighborhood trees.
We propose compact representations of neighborhood trees and merge them, exploiting computational redundancy.
Our method is less susceptible to oversquashing than traditional message passing neural networks.
- Score: 6.14580854336436
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Message passing neural networks iteratively generate node embeddings by aggregating information from neighboring nodes. With increasing depth, information from more distant nodes is included. However, node embeddings may be unable to represent the growing node neighborhoods accurately and the influence of distant nodes may vanish, a problem referred to as oversquashing. Information redundancy in message passing, i.e., the repetitive exchange and encoding of identical information amplifies oversquashing. We develop a novel aggregation scheme based on neighborhood trees, which allows for controlling redundancy by pruning redundant branches of unfolding trees underlying standard message passing. While the regular structure of unfolding trees allows the reuse of intermediate results in a straightforward way, the use of neighborhood trees poses computational challenges. We propose compact representations of neighborhood trees and merge them, exploiting computational redundancy by identifying isomorphic subtrees. From this, node and graph embeddings are computed via a neural architecture inspired by tree canonization techniques. Our method is less susceptible to oversquashing than traditional message passing neural networks and can improve the accuracy on widely used benchmark datasets.
Related papers
- Mitigating Degree Bias in Graph Representation Learning with Learnable Structural Augmentation and Structural Self-Attention [1.9019250262578853]
In real-world graphs, high-degree nodes dominate message passing, causing a degree bias where low-degree nodes remain under-represented.
We propose a novel Degree Fairness Graph Transformer, named DegFairGT, to mitigate degree bias.
Our key idea is to exploit non-adjacent nodes with similar roles in the same community to generate informative edges under our augmentation.
arXiv Detail & Related papers (2025-04-21T13:03:40Z) - NetDiff: Deep Graph Denoising Diffusion for Ad Hoc Network Topology Generation [1.6768151308423371]
We introduce NetDiff, a graph denoising diffusion probabilistic architecture that generates wireless ad hoc network link topologies.
Our results show that the generated links are realistic, present structural properties similar to the dataset graphs', and require only minor corrections and verification steps to be operational.
arXiv Detail & Related papers (2024-10-09T15:39:49Z) - 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) - 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) - A Systematic Evaluation of Node Embedding Robustness [77.29026280120277]
We assess the empirical robustness of node embedding models to random and adversarial poisoning attacks.
We compare edge addition, deletion and rewiring strategies computed using network properties as well as node labels.
We found that node classification suffers from higher performance degradation as opposed to network reconstruction.
arXiv Detail & Related papers (2022-09-16T17:20:23Z) - Shortest Path Networks for Graph Property Prediction [13.986963122264632]
Most graph neural network models rely on a particular message passing paradigm, where the idea is to iteratively propagate node representations of a graph to each node in the direct neighborhood.
We propose shortest path message passing neural networks, where the node representations of a graph are propagated to each node in the shortest path neighborhoods.
Our framework generalizes message passing neural networks, resulting in provably more expressive models.
arXiv Detail & Related papers (2022-06-02T12:04:29Z) - Improving Fraud detection via Hierarchical Attention-based Graph Neural
Network [6.7713383844867385]
Graph Neural Network (HA-GNN) for fraud detection incorporates weighted adjacency matrices across different relations against camouflage.
We generate node embeddings by aggregating information from local/long-range structures and original node features.
Experiments on three real-world datasets demonstrate the effectiveness of our model over the state-of-the-arts.
arXiv Detail & Related papers (2022-02-12T16:27:16Z) - Graph Tree Neural Networks [0.43012765978447565]
Graph tree neural networks (GTNNs) are designed to solve the problems of existing networks by analyzing the structure of human neural networks.
In GTNNs, information units are related to the form of a graph and then they become a bigger unit of information again and have a relationship with other information units.
arXiv Detail & Related papers (2021-10-31T07:58:00Z) - Reinforced Neighborhood Selection Guided Multi-Relational Graph Neural
Networks [68.9026534589483]
RioGNN is a novel Reinforced, recursive and flexible neighborhood selection guided multi-relational Graph Neural Network architecture.
RioGNN can learn more discriminative node embedding with enhanced explainability due to the recognition of individual importance of each relation.
arXiv Detail & Related papers (2021-04-16T04:30:06Z) - Artificial Neural Networks generated by Low Discrepancy Sequences [59.51653996175648]
We generate artificial neural networks as random walks on a dense network graph.
Such networks can be trained sparse from scratch, avoiding the expensive procedure of training a dense network and compressing it afterwards.
We demonstrate that the artificial neural networks generated by low discrepancy sequences can achieve an accuracy within reach of their dense counterparts at a much lower computational complexity.
arXiv Detail & Related papers (2021-03-05T08:45:43Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
We re-interpret node aggregation from the perspective of kernel weighting.
We present a framework to consider feature similarity in an aggregation scheme.
We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
arXiv Detail & Related papers (2020-05-16T04:44:29Z) - Temporal Network Representation Learning via Historical Neighborhoods
Aggregation [28.397309507168128]
We propose the Embedding via Historical Neighborhoods Aggregation (EHNA) algorithm.
We first propose a temporal random walk that can identify relevant nodes in historical neighborhoods.
Then we apply a deep learning model which uses a custom attention mechanism to induce node embeddings.
arXiv Detail & Related papers (2020-03-30T04:18:48Z)
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.