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.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...
• 181
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?
• 179
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 ...
• 179
1 vote
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 ...
1 vote
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....
• 131
1 vote
124 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 ...
• 693
1 vote
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 ...
• 129
1 vote
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 ...
• 11
1 vote
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
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,...
• 179
1 vote
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 ...
• 145