Network Geometry

• 

  example hyperbolic random graph

• 

  example planar random graph

• 

  example spherical random graph

Poster: https://docs.google.com/presentation/d/1QcvTnimqvVQ5obhMPeuRP-tSzveF2szwTM6Z5DBmRug/edit?usp=sharing

Presentation: https://drive.google.com/file/d/1fqiHiPDm9Ab6Gr1_Lil8hFIix1U_c9cl/view?usp=sharing

Final writeup: https://docs.google.com/document/d/1lD5i1lnwMlrEMm1t9x1baYwmb_gbS1kps2lGzaGUuII/edit?usp=sharing

Github: https://github.com/wei-xy/CS2470-Project.git

What it does

We would like to examine how geometrical structure can be detected in networks (graphs). There are generally three classes of geometry of surfaces: positive, negative, and zero curvature (e.g. spherical, hyperbolic, and flat surfaces). One problem in network science is to determine if a given network is compatible with one of these three geometries in the sense that the network nodes could be arranged on some kind of surface such that nodes sufficiently close to each other in the surface are connected in the graph. We can train a neural network to classify the geometric structure by asking it to classify whether generated networks are consistent with positive, negative, or zero curvature surfaces. We can generate graphs/networks by randomly scattering points on a surface of a given type and connecting nodes that are within some given distance, forming a network, labeled by its geometry.

Why we care

It has been shown that various geometries in a network can be associated with hierarchical structure and even network security. Take a look at "Geometry of Network Security" by Edmond Jonckheere and Poonsuk Lohsoonthorn, or "Network Geometry" by Boguna et al (arxiv: 2001.03241) (2020). Graph curvature has even been shown to be related to the presence of cancer in gene co-expression networks! (Scientific Reports volume 5, Article number: 12323 (2015) )

The presence of geometry in networks remains an exciting avenue of study. Still, it can be difficult to say if a graph is geometric (in the first place) and if it is, what geometric construct it corresponds to. Our model is a basic step towards being able to reliably discern between different underlying geometries. From a more theoretical point of view, our exploration may also be interesting for those studying various notions of curvature in graphs (there are several such notions). Which notion of curvature is our model picking up on? Is it a new sense of curvature? Lastly, we would like to see what our model says about the geometry of several real-world networks: are they geometrical; if they are, does the underlying geometry suggest anything meaningful about the dynamics modeled by the network structure?

How we built it

We considered using convolutional neural network to perform the classification task. Our final model consists of three convolutional layers and three dense layers. The first convolutional layer has filter of shape 5x5 and stride length of 1, the second convolutional layer has filter of shape 5x5 and stride length of 1, and the third convolutional layer has filter of shape 3x3 and stride length of 1. All the convolutional layers use same padding. After each convolutional layer, a batch normalization was performed. A leaky relu and a max pooling layer were also applied. The first dense layer has an output size of 200. The second dense layer has an output size of 100. All the dense layers use relu activation. Between each dense layer, dropout was applied with a rate of 0.01.

The training data are processed in batches with different sizes. The loss is calculated using softmax cross entropy. ADAM was used as the optimizer, with a learning rate of 0.001. The training process was repeated for 15 epochs to achieve optimal performance.

Challenges

Our first challenge of this project is how the training data can be constructed. Because network geometry is not a well studied area, there has not been much literature and publicly available data on this topic. Therefore, we decided to simulate the training data. This can be done by generating the adjacency matrices for each type of network that we are considering. The difficulty of simulating the training data is that we have to ensure the simulation is practically meaningful. To encounter this problem, we set the area of the network surface to be equal for each type of the network. In addition, there are equal number of nodes on each network, such that the difference only comes from network type, and hopefully this difference can be distinguished by the neural network classifier. Another challenge is the model architecture in this classification. We start by considering the simplest architecture first: convolutional neural network. Each adjacency matrix can be considered as an image, and thus can be fed into CNN. Additional architecture to explore can include MPNN. Finally, there are challenges in evaluating the model performances. Due to the lack of existing classification methods that can perform similar tasks, we do not have any baseline performances to compare with. Also, we are unsure whether it is actually feasible to classify the networks based on geometry, but hopefully this is a question that we will be able to answer through this project.

Insights

In this project, we explored how different network geometry can be detected and classified using convolutional neural networks. We considered three geometry types: spherical, hyperbolic, and flat surfaces, which represent positive, negative, and zero curvature respectively. We simulated the training data with different parameter settings, and used convolutional neural network to perform the classification task. We were able to achieve an accuracy of around 90% on the test set after few epochs in the best case. Through our preliminary results, we are confident that our CNN model can be applied to distinguish different network geometry structures.

What's next for Network Geometry

Our model is a basic first step towards detecting geometric structure in networks. A more sophisticated version of our model might be able to compute the curvature of graphs, rather than simply identifying what kind of curvature (positive, negative, or zero) that best fits the graph. We would also like to see how our model could be adapted to study real world networks, such as the gene coexpression network above.

Built With

• python
• tensorflow