How hard is to distinguish graphs with graph neural networks?
Graph Chatbot
Chattez avec Graph Search
Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.
AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.
We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...
2020
, ,
Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...
We consider the variation of Ramsey numbers introduced by Erdos and Pach [J. Graph Theory, 7 (1983), pp. 137-147], where instead of seeking complete or independent sets we only seek a t-homogeneous set, a vertex subset that induces a subgraph of minimum de ...
Siam Publications2015
In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...
An abstract topological graph (briefly an AT-graph) is a pair A = (G, X) where G = (V, E) is a graph and X. E2 is a set of pairs of its edges. The AT-graph A is simply realizable if G can be drawn in the plane so that each pair of edges from X crosses exac ...
The problem of generating a minimal implementation of a given Boolean function is called exact synthesis. The parameter to be minimized is often the total number of gates used for the implementation. The exact synthesis engine is considered an essential to ...
A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...
Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...
Graphs are extensively used to represent networked data. In many applications, especially when considering large datasets, it is a desirable feature to focus the analysis onto specific subgraphs of interest. Slepian theory and its extension to graphs allow ...
Over the past decade, investigations in different fields have focused on studying and understanding real networks, ranging from biological to social to technological. These networks, called complex networks, exhibit common topological features, such as a h ...
