# Questions tagged [graph-theory]

Graphs are abstract representations of objects and their mutual relations, where the objects are 'nodes' and the connections among them are 'edges'.

377 questions
Filter by
Sorted by
Tagged with
26 views

### Why Deep Learning needs to be performed in Graphical representations?

Why do we bother about devising new Deep Learning methods, which is to be applied on graphical representation of data? Why not use the traditional Deep Learning methods in the adjacency matrix ...
5 views

### Depth first search heuristic for large graph with very uneven distribution in terms of vertex's connections

Problem Context: I need to perform Depth first search on a large graph (think 50k Edges & 10K vertices) under 500MS latency constraint. The graph has the special property where the connections ...
1 vote
49 views

### How to interpret the minimum spanning tree in a fully-connected graph?

Can someone explain how the resulting graph is the minimum spanning tree (MST) from the fully-connected undirected graph? I don't understand how this is interpreted in this context. Definition ...
• 1,312
16 views

### Expected Num of Good Pairs in a Fully Connected Graph

I got the following question in my interview: there is a fully connected graph with each edge has a weight $w$, i.i.d generated from an unknown distribution $F$. A pair $(a, b)$ is called a good pair ...
• 213
1 vote
11 views

### Predict unseen samples with Graph Neural Networks

I am recently studying graph neural networks (GNNs). I have read some papers, e.g., Semi-Supervised Classification with Graph Convolutional Networks, and blogs, e.g., Training Graph Convolutional ...
• 111
1 vote
54 views

### Embedded minimum spanning trees for visualizing effects of dimensionality reduction?

Gist Construct a minimum spanning tree (MST) of the data, perform a dimensionality reduction procedure, and plot the embedding MST to study a "skeleton" of the transformed data. Mathematical ...
• 4,722
22 views

### Networkx Modularity and Simrank Similarity of Graph

I want to compute the modularity and Simrank similarity of a Networkx Graph. The Graph consists of 92000 edges and 25000 nodes. However, when I execute the following code, Colab crashes and restarts: <...
25 views

### sigma-separation question in cyclic causal graph - understanding sigma-separation

Main Question In https://arxiv.org/pdf/1807.03024.pdf, a generalization of d-separation in DAGs is introduced, called $\sigma$-separation for cyclic graphs. I am wondering how $v_1 \perp v_6$ using ...
• 185
11 views

### How can I model or estimate the probability of a given network connection in a bipartite graph of relationships that may or may not exist?

I have a large set of network data, with many groups. Within each group, there are some criteria for creating "candidate" relationships between entities. Below I have an example of 8 groups, ...
• 408
38 views

### Why is connectedness necessary for exact recovery of SBMs?

While reading this review on community detection, on the last paragraph of section 2.6, "SBM regimes and topology", the author states that "if the SBM graph is not connected, exact ...
1 vote
39 views

### Exponential Random Graph Model Implementation Python, Error [closed]

So I am trying to implement the most basic Exponential Random Graph Model implementation using Python. Concretely I'm trying to estimate the maximum pseudo likelihood estimate, which can be formulated ...
• 179
16 views

### How can I code, process, and quantify the features of a hierarchical network in a scheme that admits siblingship but also auntship links?

I am new to network analysis and I am currently facing a challenge with coding, processing, and quantifying networks in a hierarchical scheme. In this scheme, nodes pertain to differing hierarchical ...
1 vote
43 views

### Difference between Symmetrically normalized Laplacian matrix versus graph laplacian matrix

I am trying to understand the graph laplacian matrix in Graph Convolution networks. To get a basic understanding of graph laplacian matrix I am referring to this https://mbernste.github.io/posts/...
16 views

### Assemble neural networks to improve performance [duplicate]

I am approaching the world of Geometric Deep Learning for the first time and I have a question, I hope someone can answer it. I am currently working on models to classify some drugs as highly active, ...
1 vote
22 views

### Why are undirected graphical models (MRFs) not represented directly in terms of probability like directed graph models?

I have been reading the Deep Learning Book by Ian Goodfellow, and in that, there is a discussion about graphical models like Bayesian belief networks and Markov Random Fields. Here: One key diﬀerence ...
• 121
33 views

### Probability of player being selected at each draft order

Problem A set of 26 people (person A, B, ..., Z) play pick-up soccer 100+ times. Each time ...
• 163
5 views

### Why do we calculate probability distribution on leaf nodes at Sum-Product Networks (SPN)?

I am new to Sum-Product Networks (SPN) and still trying to understand some concepts. I understand that we need to give inputs at the leaf nodes of SPN. But why do we have gaussian distribution and ...
44 views

### Is normalizing input graph's node attributes before training GNNs required? How to do it

I am new in GNN, and I have a dataset of weighted graphs that each node in each graph has the following attributes: ...
• 21
1 vote
29 views

### Graph Convolutional Network work badly: my accuracy doesn’t grow!

I’m trying to classify some drugs like very active, active, non active (label: 0, 1, 2) against the cancer. To do that I built a Graph Convolutional Network using PyTorch Geometric, this is the code: <...
21 views

### Why is the closeness centrality value higher for less connected nodes?

I built an igraph graph from a data frame containing the (symbolic) edge list and weight. This is the data frame: ...
• 219
1 vote
43 views

### How to handle missing data when calculating network homophily/assortativity?

I am trying to calculate network homophily/assortativity for a graph. However, some of my nodes have missing values. It turns out igraph's assortativity functions have no "na.rm" function ...
• 381
1 vote
25 views

### Parents in a directed acyclic graph vs a partial ancestral graph

In DAGs, parents are defined as follows: A is a parent of B if 'A -> B' edge is in the graph. In PAGs, there are mixed type of edges, so you can have A -> B, A o-> B. Obviously if A -> B,...
• 185
1 vote
68 views

### List of algorithms used to cluster weighted undirected graphs

What clustering methods are suitable for weighted graphs, where the weights cannot be interpreted as a metric ? (e.g. they do not respect the triangle inequality). At the moment I found Markov ...
• 703
1 vote
24 views

### What metrics can be used to measure the difference in connectivity between graphs?

I have two sets of weighted and directed graphs with the same nodes. I expect that between these two families there is a variation in connectivity driven by some phenomenon. How could I highlight this ...
• 23
21 views

### Spatial crosscorrelation between a binary and continuous measurement on a graph

I have a graph $G$ with vertex set $V$ and edge set $E$. I measure two signals on the vertices of the graph $X$ and $Y$. If $X$ and $Y$ are both continuous, we can measure spatial crosscorrelations ...
• 659
47 views

### Algorithm to check if there is an inducing path between two nodes - constructing maximal ancestral graph (MAG) given a DAG

In causal inference, one generally learns a Markov equivalence class of causal graphs when trying to reconstruct causal structure from data. This is known as a maximal ancestral graph (MAG). I am ...
• 185
117 views

### Why do I even need DeepWalk and Node2Vec when I can build a visual graph structure?

While studying DeepWalk, I started wondering why I need "DeepWalk" when I can build a graph from data and visualize the structure of a graph. With a visualized graph, I can see which nodes ...
• 2,655
54 views

### TSP (Travel Salesman problem) for multigraph

I'm trying to solve the Travel Salesman problem for multigraph. Namely, I have a fully-connected graph with 2 oriented edges between every pair of nodes. The weight of the edge from x to y corresponds ...
81 views

• 151
1 vote
82 views

### Graph Classification via Random Forest

This is my first post here, just a brief presentation: my name is Gianmarco, I’m Medicinal Chemistry undergraduate student who is preparing his dissertation, my idea would be to create a classifier ...
21 views

### Getting two probability distributions over graphs to agree on the probability of a given graph?

I have a simple fully connected graph with $N$ nodes and hence $\binom{N}{2}$ edges. I am asked to colour this fully connected graph, where I pick the colour for the nodes w.r.t a Multinomial ...
• 151
221 views

### How to Cluster Several Graphs?

I'm relatively new to Graph Theory, but I'm wondering if I have a set of Graphs {G1, G2, ..., Gn}, are there any algorithms that allow for clustering these graphs? taking into account the nodes and ...
• 131
1 vote
10 views

### Associate prediction task to a graph autoencoder (GAE)

I have been reading about graph autoencoders and was wondering if it might be a reasonable idea trying to associate to the unsupervised setting which produces some best low-dimensional representation ...
• 517
1 vote
11 views

### Comparing properties of networks of different sizes

I want to compare some network properties such as density, average path and modularity among groups of sizes ranging from 100 to 4000. How can I correctly compare these networks? Considering the ...
1 vote
13 views

### Proof for a seemingly simple property for fully-connected coloured random graphs?

I have a probability distribution defined over a set of fully-connected simple graphs depending on their coloring. Let us have a fully connected graph with $N$ nodes, a node may have a color $i$ ...
• 151
29 views

### Passing entire dataset into convolution layer when training?

So for some context, I have been building my own computation graph to model the way PyTorch and Tensorflow build their machine learning frameworks. I have recently finished implementing the ...
49 views

### How to identify number of vertices, edges and weights in a cellular network

Suppose we have a cellular network then what are the vertices, edges and edges weights in this network. I have choose customers as vertices. Customers calling each other as edges. Time of duration ...
38 views

### Data association on data from multiple cameras

Suppose we have several cameras that cover a certain area. In each camera we track a person. Each person have a path in global coordinates, timestamps and a feature-vector. The goal is to group these ...
1 vote
46 views

### Are graphical neural networks the right approach for isomorphic graphs?

I have a set of $N$ observations ($N>100,000$): each observation takes the form of a homogeneous, undirected graph $G_n=(V,E)$ all graphs $G_n$ have the same nodes and edges - around 5,000 nodes ...
32 views

### Hyperparameter selection in Affinity Propagation without ground truth

My goal is to implement affinity propagation for clustering a given dataset (n=12 features), and I wish to find the optimal hyperparameter value (preference) allowing an educated guess of the number ...
• 11
14 views

• 517
115 views

### I-map Bayesian Network, Practical Explanation

I am having diffculty understanding the concept of an I-map in the context of Bayesian Networks. According to the PGM textbook by Koller & Friedman, an I-map is essentially a set of conditional ...
1 vote
38 views

### Validation of Clustering with labels

I am currently trying to perform clustering on 8 different datasets where I have 40-100 "labeled" data points per data set, representing which data points belong to the same cluster. I ...
• 111