Skip to main content
The 2024 Developer Survey results are live! See the results

# Tag Info

## Hot answers tagged graph-theory

2 votes

### Why is the output of my graph neural network not permutation equivariant?

It seems that the graph filter layer in your GNN takes information from the immediate neighbors for every node and applies a ReLU nonlinearity. However, the architecture you've shown does not ...
2 votes

### How to solve Snake Game with a Hamiltonian graph algorithm?

A Hamiltonian path in a graph is a path that visits all the nodes/vertices exactly once, a hamiltonian cycle is a cyclic path, i.e. all nodes visited once and the start and the endpoint are the same. ...
• 121
2 votes
Accepted

### How do I train a bot to solve Katona style problems?

Your intuition is right: this is fundamentally a problem for combinatorial search. You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need ...
• 9,327
1 vote

### How to properly model the MDP of a weighted graph with the constraint of only visiting each vertex once (and not get stuck in infinite loops)?

Many environments are non-Markovian. Sometimes based on the perception of the agent a Markovian environment becomes non-Markovian (woods101 with perception aliasing). If the model assumes a Markovian ...
• 1,318
1 vote

### What is GNN Cheatsheet in PyG Docs

Regarding "what the purpose of this is as it shows a table and there are tick marks if checked.", it sounds like that the tick marks indicating convolution operation support. This means you ...
• 181
1 vote

### Why readout operation in message passing graph neural nets have to be invariant to node permutations?

It is necessary for GCNs / MPNNs to be invariant to node permutations in order to generalize properly. Firstly, node permutation means that you reindex the nodes. The edges also use this new indexing, ...
• 1,748
1 vote
Accepted

### Does the Weisfeiler-Lehman Isomorphism Test end?

Notice that a partition (set of nodes with the same label) can never get combined with another partition during an iteration. If two nodes are in different partitions, they stay in different ...
1 vote

### How can abstract graphs be recognized by neural nets?

I feel the commentary about "recognizable-patterns" is a bit misleading. In deep-learning graphs are, usually, fed into networks called GNNs (Graph NNs). GNNs work by updating features on ...
• 126
1 vote

### How can abstract graphs be recognized by neural nets?

The OP's (i.e. my) assumption is wrong. It is not true that for almost all random graphs under no permutation a pattern is visible, as can be seen in Tiago P. Peixoto's paper Bayesian stochastic ...
1 vote
Accepted

### What exactly is the eigenspace of a graph (in spectral clustering)?

In spectral clustering we not find the eigenvectors of a graph (a graph is not a matrix) but the eigenvalues/eigenvectors of the Laplacian matrix related to the adjacency matrix of the graph: graph =&...
• 1,293
1 vote
Accepted

### How do I turn this formula of the average degree of a graph into Python code?

Each node is a position in the arrays values = value of the node conn = indexes of connected nodes If its an undirected graph, each node must have all the nodes to which they are attached. Instead, ...
1 vote

### Solving a planning if finding the goal state is part of the problem

I think there are different ways to solve the problem you presented: 1) It could be seen as classical resource optimization problem that can be solved via Linear Programming setup (highly suggested ...
• 21
1 vote

### Solving a planning if finding the goal state is part of the problem

Your question is still nearly perfectly unclear, but let's make a few guesses in order to make some progress. The biggest mystery are your time slices: How many of them you need? With more granular ...
• 553

Only top scored, non community-wiki answers of a minimum length are eligible