8 citations · 15 across the 7 of their papers we have counts for
11 papers
Ordered Subgraph Aggregation Networks
Chendi Qian, Gaurav Rattan, Floris Geerts +2
Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message-passing) GNNs. However, there is a limite…
SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks
Christopher Morris, Gaurav Rattan, Sandra Kiefer +1
While (message-passing) graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, hig…
Homomorphism Tensors and Linear Equations
Martin Grohe, Gaurav Rattan, Tim Seppelt
Lovász (1967) showed that two graphs and are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph , the n…
Weisfeiler--Leman and Graph Spectra
Gaurav Rattan, Tim Seppelt
Two simple undirected graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues. Cospectrality yields an equivalence relation on the family…
Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
Christopher Morris, Martin Ritzert, Matthias Fey +4
In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion…
Graph Similarity and Approximate Isomorphism
Martin Grohe, Gaurav Rattan, Gerhard J. Woeginger
The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not rec…
Lovász Meets Weisfeiler and Leman
Holger Dell, Martin Grohe, Gaurav Rattan
In this paper, we relate a beautiful theory by Lovász with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensio…
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs
V. Arvind, Frank Fuhlbrück, Johannes Köbler +2
In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphi…
Graph Isomorphism, Color Refinement, and Compactness
V. Arvind, Johannes Köbler, Gaurav Rattan +1
Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a…
On the Complexity of Noncommutative Polynomial Factorization
V. Arvind, Pushkar S Joglekar, Gaurav Rattan
In this paper we study the complexity of factorization of polynomials in the free noncommutative ring of polynomials over the field $\m…
Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity
Vikraman Arvind, Gaurav Rattan
We give a time isomorphism testing algorithm for graphs of eigenvalue multiplicity bounded by which improves on the previous best running time bound of $O^*(2^{…