Improving Subgraph-GNNs via Edge-Level Ego-Network Encodings
We present a novel edge-level ego-network encoding for learning on graphs that can boost Message Passing Graph Neural Networks (MP-GNNs) by providing additional node and edge features or extending message-passing formats. The proposed encoding is sufficient to distinguish Strongly Regular Graphs, a family of challenging 3-WL equivalent graphs. We show theoretically that such encoding is more expressive than node-based sub-graph MP-GNNs. In an empirical evaluation on four benchmarks with 10 graph datasets, our results match or improve previous baselines on expressivity, graph classification, graph regression, and proximity tasks -- while reducing memory usage by 18.1x in certain real-world settings.
Code (1)
Tasks
Graph ClassificationGraph RegressionSimilar Papers 제목 키워드 기반
Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products
In the realm of Graph Neural Networks (GNNs), two exciting research directions have recently emerged: Subgraph GNNs and Graph Transformers. In this paper, we propose an architecture that integrates both approaches, dubbe…
Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality
We propose an expressive and efficient approach that combines the strengths of two prominent extensions of Graph Neural Networks (GNNs): Subgraph GNNs and Structural Encodings (SEs). Our approach leverages walk-based cen…
EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time
Understanding and explaining the predictions of Graph Neural Networks (GNNs), is crucial for enhancing their safety and trustworthiness. Subgraph-level explanations are gaining attention for their intuitive appeal. Howev…
On Explainability of Graph Neural Networks via Subgraph Explorations
We consider the problem of explaining the predictions of graph neural networks (GNNs), which otherwise are considered as black boxes. Existing methods invariably focus on explaining the importance of graph nodes or edges…
MAG-GNN: Reinforcement Learning Boosted Graph Neural Network
While Graph Neural Networks (GNNs) recently became powerful tools in graph learning tasks, considerable efforts have been spent on improving GNNs' structural encoding ability. A particular line of work proposed subgraph …
Combinatorial OptimizationGraph LearningGraph Neural Networkreinforcement-learning+2