# Questions tagged [graphs]

Use for questions related to graph coloring and graph coloring games.

30 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
328 views

### What is the proof that the branch and bound algorithm always finds optimal path in a graph?

I've been studying Branch and Bound's graph algorithm and I hear it always finds the optimal path because it uses previously found solutions to find others However, I haven't been able to find a ...
• 351
1k views

### Can the degree and minimum remaining values heuristics be used in conjunction?

I am currently studying constraint satisfaction problems and have come across two heuristics for variable selection. The minimum remaining values(MRV) heuristic and the degree heuristic. The MRV ...
• 1,281
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
1k views

### What are examples of node 'features' in graph networks?

Context: I was reading Chapter 3 in the following book (here) about graph representation learning. Before I get to node embeddings, I wanted to make sure that I do understand what is meant by the ...
80 views

### Suitable deep learning algorithms for spatial / geometric data

I have a task of classifying spatial data from a geographic information system. More precisely, I need a way to filter out unnecessary line segments from the CAD system before loading into the GIS (...
• 121
20 views

### Improving graph decoder network

I have been using a network to generate graphs. The architecture that I have been using is the following: In this figure, $D_1$ is the signal generator and $D_2$ is the graph topology generator, ...
• 151
144 views

### Why does the ELBO come to a steady state and the latent space shrinks?

I'm trying to train a VAE using a graph dataset. However, my latent space shrinks epoch by epoch. Meanwhile, my ELBO plot comes to a steady state after a few epochs. I tried to play around with ...
• 151
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
538 views

### Does iterative deepening depth-first search expand at most twice as many nodes as breadth-first search?

My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off ...
• 101
1 vote
180 views

### Best algorithm for the Word Ladder puzzle

What would be the best performing algorithm to solve the Word Ladder problem, in terms of guaranteed finding of the shortest solution in the shortest possible time? Is it BFS, DFS, A*, IDA* or another ...
1 vote
272 views

### Why is the Graph Isomorphism Network powerful?

I am reading a paper known as GIN, How powerful are graph neural networks?, Xu et al. 2019 The paper, Lemma 5 and Corollary 6, introduces Graph Isomorphism Network (GIN). In Lemma 5, Moreover, any ...
• 125
1 vote
29 views

### What is the reason behind using node embeddings?

I was reading Chapter 3 from the following book (here) on graph representation learning. The chapter is about node embeddings. Question: What is the point of using node embeddings? Do we use them: to ...
1 vote
52 views

### How to use unmodified input in neural network?

My question may be a bit hard to explain... My neural network learns a categorical distribution, which serves as an index. This index will look up the value (= action_mean) in Input 2. From this ...
• 31
1 vote
97 views

### How to learn how to select a subgraph via reinforcement learning?

I have the following problem. I am given a graph with a lot (>30000) nodes. Nodes are associated with a low (<10)-dimensional feature vector, and edges are associated with a low (<10)-...
• 111
1 vote
154 views

### Applications of polar decomposition in Machine Learning

Assume there exists a new and very efficient algorithm for calculating the polar decomposition of a matrix $A=UP$, where $U$ is a unitary matrix and $P$ is a positive-semidefinite Hermitian matrix. ...
• 11
1 vote
70 views

### Model for supervised sequence classification task

The Problem I am currently working on a sequence classification problem I try to solve with machine learning. The target variable is the current state of a system. This target variable is following a ...
• 31
1 vote
108 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
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
1 vote
119 views

### How to create meaningful multiple object detection evaluation comparison graph?

I have got multi-class object detector. One model accuracy evaluation of detection consists of: mAP, FP, FN, TP for each class divided to two graphs and looks like this (I've used this repo for ...
• 213
1 vote
39 views

### How to visualize/interpret text prediction model results?

I am using LSTM model to predict the next xml markup from an input seed. I have trained my model on 1500 xml files. Each xml file is generated randomly. I am wondering if there is a way to visualize ...
• 169
1 vote
1k views

### Can I extend Graph Convolutional Networks to graphs with weighted edges?

I'm researching spatio-temporal forecasting utilising GCN as a side project, and I am wondering if I can extend it by using a graph with weighted edges instead of a simple adjacency matrix with 1's ...
18 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 - ...
• 101
23 views

I'm currently working on a system that predicts energy consumption of a set of buildings using graph convolutionals networks (GCN), which is a Graph-Level regression task (1 prediction for every ...
23 views

### Is it feasible to solve dynamic graph-level classification without labels?

I already did graph-level classification using heterogeneous hypergraph learning in an ICDM paper last year. However, I now want to extend it for dynamic graphs, i.e. the task is dynamic graph-level ...
• 101
39 views

### How to perform inference on a new node using GraphSage

I'm working with the GraphSage architecture to compute node embeddings right now. I understand that during training you fine tune the models parameters and then once fine tuned you can run this on a ...
96 views

### ST-GCN: graph convolution operator in Geometry-Aware Interaction Network (GAIN)

I need help implementing the model in this paper: They have adopted spatio-temporal graph convolution operator in ST-GCN [section 3.1.2]. I've found there is popular libraries available for GCN: ...
154 views

### Model Suggestion for graph data

I am trying to figure out the right model/algorithm for a graph dataset to develop a machine learning pipeline. I have looked into Graph Neural Network(GNN) but all of the tutorials I found, trained ...
37 views

### Is there any geometrical interpretation on overcoming gradient related problems by adjusting/changing loss function?

There are instances in literature where we need to change loss function in order to escape from gradient problems. Let $L_f$ be a loss function for a model I need to train on. Some times $L_f$ leads ...
• 3,890