Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graph-theory]

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices, nodes, or points which are connected by edges, arcs, or lines. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another.

Filter by
Sorted by
Tagged with
6 votes
1 answer
109 views

It is possible to use deep learning to give approximate solutions to NP-hard graph theory problems?

It is possible to use deep learning to give approximate solutions to NP-hard graph theory problems? If we take, for example, the travelling salesman problem (or the dominating set problem). Let's say ...
0 votes
0 answers
17 views

Visual representation(s) for variable length m-tuples

I'm working with a dataset of sequences, each 200 characters long. Within these sequences are embedded 10-character patterns (P1 to P5). The co-occurrence of these patterns varies across sequences - ...
1 vote
1 answer
35 views

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)?

I'm trying to model a MDP to traverse a complete weighted graph (i.e. all vertex are connected). The states, and also the actions (i.e. S=A), are the vertex of the weighted graph. The transition ...
1 vote
2 answers
122 views

How can abstract graphs be recognized by neural nets?

Recognition of optical patterns (as pixel maps) by neural networks is standard. But optical patterns may be only slightly distorted or noisy, and may not be arbitrarily scrambled – e.g. by ...
-1 votes
1 answer
129 views

What is GNN Cheatsheet in PyG Docs [closed]

I am going through the Pytorch Geometric documentation: https://pytorch-geometric.readthedocs.io/en/latest/index.html which is built on Pytorch .Here they mentioned about GNN Cheatsheet: https://...
0 votes
0 answers
25 views

Convert specific domain knowledge text to a knowledge graph

As part of this semester assignment , I'm working on a project that aims to to represent the knowledge in "PMBOK 6th edition, section 11: Project Risk Management (page 395 -> 458)" and the knowledge ...
0 votes
1 answer
234 views

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

I am using Pytorch to train a graph neural network on a 4x4 graph. Each node has one feature, and the output has one feature. Essentially, the architecture of my GNN looks like this (I'm training the ...
2 votes
1 answer
149 views

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

I am reading the paper Neural Message Passing for Quantum Chemistry by Justin Gilmer et al. And I have a question regarding this passage The message functions $M_t$, vertex update functions $U_t$, ...
4 votes
1 answer
217 views

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

Cognitive psychology is researched since the 1940s. The idea was to understand human problem solving and the importance of heuristics in it. George Katona (an early psychologist) published in the ...
0 votes
1 answer
227 views

Does the Weisfeiler-Lehman Isomorphism Test end?

I am studying GNNs. I am interested in the Weisfeiler-Lehman Isomorphism Test (WL-Test). I was looking for information about whether the test always ends or not, but I didn't find a definitive answer. ...
1 vote
0 answers
24 views

Why is it difficult to propagate intransitive relations over a graph?

In the paper Semi-Supervised Learning by Mixed Label Propagation, they say One major limitation with most graph-based approaches is that they are unable to explore dissimilarity or negative ...
2 votes
1 answer
154 views

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

When we find the eigenvectors of a graph (say in the context of spectral clustering), what exactly is the vector space involved here? Of what vector space (or eigenspace) are we finding the ...
1 vote
0 answers
80 views

How can I evaluate a reinforcement learning algorithm over an entire problem space?

I am working on implementing an RL agent and I want to demonstrate its effectiveness over a bounded problem space. The setting is essentially a queueing network and so it can be represented as a graph....
1 vote
1 answer
485 views

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

I am working through the textbook "Graph-Based Natural Language Processing and Information Retrieval", where I've got a question on implementation of this first Latex looking formula/...
1 vote
0 answers
125 views

How to make sense of label propagation formula in graph neural networks?

In the label propagation algorithm in section 3.2.3, we know the label of some nodes and we want to predict the label for the rest of the nodes whose labels we don't know. The update formula for this ...
1 vote
0 answers
20 views

How to estimate the convolutional representation of a graph from its similarity to other graph convolutional representation?

Suppose we have two graphs A and B disconnected to each other (let's say 2-hops each), within a larger graph. If the convolutional representation of graph A is known, is it possible to estimate the ...
1 vote
0 answers
106 views

How to update edge features in a graph using a loss function?

Given a directed, edge attributed graph G, where the edge attribute is a probability value, and a particular node N (with binary features f1 and f2) in G, the algorithm that I want to implement is as ...
2 votes
2 answers
277 views

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

I having trouble finding some starting points for solving an occupancy problem which seems like a good candidate for ai. Assume the following situation: In a company I have n cars and m employees. ...
1 vote
1 answer
3k views

How to solve Snake Game with a Hamiltonian graph algorithm?

I wonder if there is a way to solve snake game using Hamiltonian algorithm? if there is a way how to apply it? what data structure will be used with algorithm? time complexity and space complexity? ...
1 vote
0 answers
22 views

Is there any time-varying directed graph dataset?

I am interested in the node classification task for graph data. So far,I've tried it with the Cora dataset, but it is an undirected graph and has word attributes as features. I want to extend this ...
1 vote
0 answers
31 views

What are the advantages of time-varying graph CNNs compared to fixed graph?

As I wrote in the title, what are the advantages of time-varying graph CNNs compared to fixed graph? For example, in CORA, which is a graph of citation relations of papers frequently used in graph CNN,...
2 votes
0 answers
33 views

Random graph as input in geometric deep learning on time-varying graph

I want to create a framework that allows GDL to be applied to time-varying graphs. I came up with the Erdos-renyi model as an example of a time-varying graphs. GDL for graphs takes node information ...
3 votes
0 answers
42 views

What are the benefits of using the state information that maintains the graph structure?

When you applying a graph structured data to the graph convolution network, what are the benefits of using the state information that maintains the graph structure?
2 votes
0 answers
199 views

How to choose method for solving planning problems? [closed]

There are many methods and algorithms dealing with planning problems. If I understand correctly, according to Wikipedia, there are classical planning problems, with: a unique known initial state, ...
1 vote
0 answers
37 views

Write Constraint Satisfaction Formulation for problem

Given $F_1,F_2,..,F_n$ as set of final exams of subjects taken by students $S_1,..,S_k$ in h slots such that no student takes two exams in a single slot.Here the objective is to maximize the number of ...