Buchumschlag

On the Expressive Power of Spectral Invariant Graph Neural Networks

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Zhang, Bohang, Zhao, Lingxiao, Maron, Haggai
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Machine Learning Discrete Mathematics Data Structures and Algorithms Combinatorics Spectral Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness
von: Zhang, Bohang, et al.
Veröffentlicht: (2024)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
von: Paschalidis, Phevos, et al.
Veröffentlicht: (2023)

A Faster Isomorphism Test for Graphs of Small Degree
von: Grohe, Martin, et al.
Veröffentlicht: (2018)

EPTAS for Hard Graph Cut Problems for Dense Graphs
von: Deguchi, Kaisei, et al.
Veröffentlicht: (2026)

Extending Ghouila-Houri's Characterization of Comparability Graphs to Temporal Graphs
von: Charbit, Pierre, et al.
Veröffentlicht: (2025)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Non-Clashing Teaching Maps for Balls in Graphs
von: Chalopin, Jérémie, et al.
Veröffentlicht: (2023)

$α_i$-Metric Graphs: Hyperbolicity
von: Dragan, Feodor F., et al.
Veröffentlicht: (2024)

Palette Sparsification for Graphs with Sparse Neighborhoods
von: Dhawan, Abhishek
Veröffentlicht: (2024)

Colouring Probe $H$-Free Graphs
von: Paulusma, Daniël, et al.
Veröffentlicht: (2025)

Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds
von: Bhore, Sujoy, et al.
Veröffentlicht: (2026)

Hardness of Burning Number Problem on Regular Graphs
von: Antony, Dhanyamol, et al.
Veröffentlicht: (2026)

Light Edge Fault Tolerant Graph Spanners
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Bounding Width on Graph Classes of Constant Diameter
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2025)

Sandwich Monotonicity and the Recognition of Weighted Graph Classes
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

Graph parameters that are coarsely equivalent to path-length
von: Dragan, Feodor F., et al.
Veröffentlicht: (2025)

Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2024)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
von: Neuen, Daniel
Veröffentlicht: (2020)

Coarse Balanced Separators in Fat-Minor-Free Graphs
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
von: Bandyapadhyay, Sayan, et al.
Veröffentlicht: (2024)

Tree Independence Number IV. Even-hole-free Graphs
von: Chudnovsky, Maria, et al.
Veröffentlicht: (2024)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
von: Srinivasan, Eshwar, et al.
Veröffentlicht: (2026)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2025)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
von: Dudeja, Aditi, et al.
Veröffentlicht: (2024)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
von: Shakeri, Heman, et al.
Veröffentlicht: (2025)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2026)

A Method for Generating Connected Erdos-Renyi Random Graphs
von: Chinyaev, Boris
Veröffentlicht: (2025)

Construction of orientable sequences in $O(1)$-amortized time per bit
von: Gabric, Daniel, et al.
Veröffentlicht: (2024)

On constrained intersection representations of graphs and digraphs
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2025)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
von: Bencs, Ferenc, et al.
Veröffentlicht: (2024)

Approximating maximum-size properly colored forests
von: Bai, Yuhang, et al.
Veröffentlicht: (2024)

Problems on Group-labeled Matroid Bases
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
von: Guo, Heng, et al.
Veröffentlicht: (2024)

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

A logarithmic approximation of linearly ordered colourings
von: Håstad, Johan, et al.
Veröffentlicht: (2024)

On the sizes of BDDs and ZDDs representing matroids
von: Emoto, Hiromi, et al.
Veröffentlicht: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)