Graph Coarsening with Message-Passing Guarantees
Graph coarsening aims to reduce the size of a large graph while preserving some of its key properties, which has been used in many applications to reduce computational load and memory footprint. For instance, in graph machine learning, training Graph Neural Networks (GNNs) on coarsened graphs leads to drastic savings in time and memory. However, GNNs rely on the Message-Passing (MP) paradigm, and classical spectral preservation guarantees for graph coarsening do not directly lead to theoretical guarantees when performing naive message-passing on the coarsened graph. In this work, we propose a new message-passing operation specific to coarsened graphs, which exhibit theoretical guarantees on the preservation of the propagated signal. Interestingly, and in a sharp departure from previous proposals, this operation on coarsened graphs is oriented, even when the original graph is undirected. We conduct node classification tasks on synthetic and real data and observe improved results compared to performing naive message-passing on the coarsened graph.
Code (0)
등록된 구현이 없습니다.
Tasks
Node ClassificationSimilar Papers 제목 키워드 기반
Next Level Message-Passing with Hierarchical Support Graphs
Message-Passing Neural Networks (MPNNs) are extensively employed in graph learning tasks but suffer from limitations such as the restricted scope of information exchange, by being confined to neighboring nodes during eac…
Graph ClassificationGraph LearningGraph Property PredictionGraph Regression+1A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening
Subgraph Graph Neural Networks (Subgraph GNNs) enhance the expressivity of message-passing GNNs by representing graphs as sets of subgraphs. They have shown impressive performance on several tasks, but their complexity l…
Graph LearningImproving the Effective Receptive Field of Message-Passing Neural Networks
Message-Passing Neural Networks (MPNNs) have become a cornerstone for processing and analyzing graph-structured data. However, their effectiveness is often hindered by phenomena such as over-squashing, where long-range d…
Graph ClassificationGraph RegressionNode ClassificationLocal-to-global Perspectives on Graph Neural Networks
This thesis presents a local-to-global perspective on graph neural networks (GNN), the leading architecture to process graph-structured data. After categorizing GNN into local Message Passing Neural Networks (MPNN) and g…
Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy
Graphs provide a natural language for relational data in chemistry, biology and optimisation. Graph neural networks (GNNs) have driven much of the recent progress in learning from such data through message passing, a sin…
Molecular Property PredictionGraph Neural NetworkGraph Learning