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'.

Filter by
Sorted by
Tagged with
3 votes
2 answers
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 ...
0 votes
0 answers
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
1 answer
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
0 votes
0 answers
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
0 answers
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
0 answers
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
0 votes
0 answers
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: <...
  • 1
3 votes
1 answer
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
0 votes
0 answers
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, ...
0 votes
0 answers
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
0 answers
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 ...
0 votes
0 answers
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
1 answer
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/...
0 votes
0 answers
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
1 answer
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 difference ...
0 votes
1 answer
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
0 votes
0 answers
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 ...
2 votes
0 answers
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
0 answers
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: <...
0 votes
0 answers
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
0 answers
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
0 answers
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
0 answers
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
0 answers
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
2 votes
0 answers
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
2 votes
0 answers
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
0 votes
1 answer
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
0 votes
0 answers
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 ...
  • 1
5 votes
1 answer
81 views

Intuition and meaning of a "discriminating path" in a causal DAG

In Ali, Richardson and Spirtes (2009) (open copy here) and many other papers in the causal DAG literature, there is the notion of a "discriminating path". The definition is: A path $\pi = ⟨...
  • 185
3 votes
1 answer
364 views

Weighted adjacency matrix normalization for GCN, how to normalize? what about self-loop values?

I am implementing a GCN that will work on a weighted graph. The edges' weights are in the range [1, 250]. When it comes to normalizing the adjacency matrix for GCNs, the standard formula of a ...
  • 308
2 votes
2 answers
337 views

Nodes' attribute scaling/normalization before graph embedding learning - GNN?

In a node classification setting, is it require to normalize/scale graph node attributes before learning node embeddings using graph neural networks? Why?
  • 308
1 vote
0 answers
47 views

Marginal Distribution of a Stochastic Block Model?

Let us say I have a Stochastic Block Model i.e. a random vector $X^{(n)} = [x_1,...,x_n]$ where $P(x_i = c) = P_{c}$, where $c \in \{1,...,u\}$, and a random simple undirected graph represented by $Y^{...
  • 151
1 vote
1 answer
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 ...
0 votes
0 answers
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
3 votes
1 answer
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
0 answers
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 ...
1 vote
0 answers
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
0 answers
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
0 votes
0 answers
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 ...
0 votes
1 answer
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 ...
  • 1
0 votes
0 answers
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
0 answers
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 ...
0 votes
0 answers
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
0 votes
0 answers
14 views

Higher order tensors for describe (hyper) graphs and features attached

I'm trying to understand better some notation I'm reading in the following paper: https://arxiv.org/pdf/1901.09342.pdf In particular, graph or hyper graph data can be described by using tensors $\...
0 votes
0 answers
19 views

Is there a concept for "almost parallel" edge?

By "almost parallel" I mean if set S of closing nodes has many conflicting edges with set T of closing nodes, then the edges between them are almost parallel. The emphasized edges in this ...
  • 277
2 votes
1 answer
113 views

Trace of quadratic form with Laplacian matrix notation

Reading some papers about spectral graph analysis and graph neural networks I have found the following notation which I'm not too sure how to expand: Given matrices $F, L \in \mathbb{R}^{n \times n}$, ...
0 votes
1 answer
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
0 answers
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
0 votes
0 answers
20 views

Which Connected Component algorithm is implemented in GraphX?

I would like to know which connected component is used by GraphX? I have found it on the internet but the only result I got is the tutorial on how to use the code. It will be better if there is a ...
  • 113
1 vote
0 answers
27 views

Difference between types of solutions in network matchings? [closed]

So there are so many different types of solutions: pareto, stable, rank-maximal, etc. etc. How do anyone know which one to use for any given problem? Particularly when some of them may not exist? And ...

1
2 3 4 5
8