DataChats | Episode 13 | A Presentation by Eric Ma

Okay, we're good to go. First of all, thanks for coming, everyone. Welcome to this big Data Boston meetup. It's been a long while. So I'm Martin. I'm one of the co founders of datacamp. If you don't know what datacamp is, we're an online interactive learning platform for R, Python and data science. We have over 600,000 people taking courses on datacamp. If you want to learn more about it, just go to datacamp.com we have a couple free courses. Try them out. So today's speaker is Eric Ma. So Eric is a final year PhD student at the Department of Biological Engineering at MIT. He's passionate about open source software and about network analysis. So the title of the talk today is Networks, Networks Everywhere. I'm going to give the floor to Eric.

Thanks a lot. Thank you, Martin. So before I continue, I want to just let you all know my slides are online. And if at this moment you want to take two minutes to open up the URLs on your phone, I have absolutely no problem with that. I'll just introduce myself while you guys do your phone thing. So I'm Eric, I'm 15, I'm a sixth year graduate student at MIT. I work on influenza problems and networks have been a cornerstone of how I approach these problems. And so one of the reasons I got involved with datacamp was through sharing my knowledge on network analysis methods at places like Pycon and scipy and odscreek. And now for me, it's a great privilege to come and share some of these pieces of knowledge with you as well. So how are people doing with the links here? If you're good, can you give me a thumbs up? All right, I'll just assume you can find someone in your crowd who has already got that link. So yeah, that's me. How many of you have did your networking here already? Great. So we're all one big network here as well and I think that's going to be good. And I'd love myself to network with you after the talk as well. So today I'm going to do six things, five of which are listed up there. And then there's one so called one more thing that I've that if you scroll down on the website notes, you'll find out what it is. But for now I'm just not gonna reveal it. So first off I'm gonna share the what the fundamentals of networks are and then I'm gonna share with you some non intuitive ways in which networks have been used to solve cool problems. So before I go on, how many of you know a little bit about what networks are and can give me a definition of a network? How many of you think you can give me a definition of network? So, Amir, how about you? Exactly. So Amir said this is a graph. A network is essentially defined as a graph. And a graph comprises of two things, nodes, which are entities, and edges, which are relationships between those entities. Right. And so we've got essentially just two sets of items that we need to keep track of. We need to keep track of the nodes, and then we need to keep track of the relationships. So what kind of networks have you all heard of before? Just let's go popcorn style. Sorry. Social. Social networks. So we've got the Facebook, Twitter and LinkedIn. So what are the nodes inside a social network? They're the users. And what are the edges then? Pardon me? So if you're connected to another, you're a friend of another, then you're an edge. What's another example of a network? Road networks. Okay, so what are the nodes in a road network and what are the edges in a road network? Okay, so let's say we're doing highways and. Right. So if we're doing highways between major cities, the nodes would be the cities and the edges would be highway paths that move between them. Right. And what are some of these, some of the problems that we can solve with modeling data in this fashion? Well, there are some of the obvious ones. Right. So we can look at what are the shortest paths from one city to another and write an optimization problem for that. Right. We can ask, in fact, the breadth first search algorithm, which is one of the ways. One of the tools used in some of these optimization problems was first developed to figure out what the right path was out of a maze. We modeled the junctions as nodes and paths between the junctions as edges, and we can start to look for the shortest path outside of the maze. But there are some other problems which are not so obvious, and I'm going to talk to you about them today. How many of you know about the recommendation systems that social networks give? So, yeah, so we've got LinkedIn was the famous example, right? LinkedIn was the one that said I can probably build a recommendation system based on some simple principles acting on graphs. So that simple principle is if A is connected to B and A is connected to C, then probably B and C are connected in real life. And we'd like that to be reflected in the social graph that we have. Right? And then if we added A User D that was connected like A to B and C. That's another layer of evidence, another increased belief that B and C should be connected to one another, right? And then we can do. We can then add on other pieces of metadata that help inform our belief and write models that do that. So we have here friend recommendation systems, which were one of the earliest examples of a useful commercial product that came out of network theory. And the main concept that was utilized in this particular problem was what they called triadic closures, right? We look for things like open triangles inside here to say that. And we want to close these open triangles that are present. This is another example of recommendation system. How many of you have heard of collaborative filtering? Collaborative filtering is another example in which we have a graph that is a bipartite graph. Now, it's called a bipartite graph because we group the nodes into two partitions, therefore bipartite. And so in this particular case, let's say we're Amazon, right? And we want to know. We want to increase revenue by recommending products to users. There are ways that we can recommend products based on product history. How many of you have bought, like a watch on Amazon and have had Amazon recommend more watches to you? It doesn't really make sense. This is one where I think maybe Amazon might want to start thinking about it again, right? So if we have users that are buying products, if user a buys product 1, 2, and 3, and user B buys product 1, 2, 3 and 4, both users share an overlapping complement of products, which means they probably share some similarity in their buying patterns. And so by that logic, we may want to recommend that customer A may want to buy product number four, just like customer B did, right? And so that's another example of where graphs were used to solve this problem. And if you take a look at the online Notes version of the online Notes version of the slides, you'll see there's a link to collaborative filtering, the Wikipedia page. And so this was. These two examples here show how we can build recommendation systems just by first thinking through our users and modeling them not as just individual rows in a table, but actually people that are connected and share similarities. And that similarity graph, that network, is the magic of where network analysis comes in. All right, we. Have you heard of the Panama Papers? Yeah, the Panama Papers were, like, huge. How many of you read about the technology that went underneath the Panama Papers? So we've got. Have you all heard of Neo4J? Neo4J is this graph database that was used to help the journalists investigate the relationships between the actors inside, inside this big mess of finances and politics that went on in the world. So essentially this is the watered down simplified version. You do a lot of OCR and nlp, optical character recognition and natural language processing. You extract out text and then when you extract from that text is not just how many documents there were and what names were on those documents. You start to extract relationships between the players. So for example, this is a toy example that I drew. You might have corporations and individuals, right? You could have an individual, a text that was scanned from the Panama papers that said, oh, this user emailed that user or this individual player signed a contract with that company, right? And you can use graph databases to store these semantic relationships in a fashion that say traditional databases like, what do you call those relational RDBs. Relational databases may have a tough time handling. Whereas with graph databases it's. You can write natural queries, you can naturally write queries on the graph database, you can start to explore what went on. So one of the cool things that happened was there's this company called Linkurious. Now I'm not affiliated with them, they tried to sell me their services but I couldn't afford them back in the day. But Linkurious actually built a front end to the graph database and that let non tech savvy journalists click on a company and start to explore, oh, this company had this president, what did this president do with other people? What's the email trail saying? What's the relationships that are being modeled based on the email trail? Right. So you can start to jump from link to link to link and figure out what are the important players. You can ask what are the players that had the most financial ties to other types of players? Because by the nature of the data modeling, we're able to model multiple different types of relationships and not just a single type of relationship. So the graph database plus the Linkurious tool became a very instrumental thing in allowing the ICIJ to explore this terabytes data set at scale. And it turned out to be something that was done for social justice. So graphs are not just good for making companies money, they're also good for social justice purposes. I'm going to talk about two examples where networks, you might not think they show up, you might not necessarily think they show up in. Sorry, in which networks were used in also in non intuitive ways. This is from my own work. I work at the intersection of influenza ecology and evolution. And in this particular piece of work I was interested in the fact that flu can shuffle its genome, right? And by shuffling its genome, it's able to create these novel variants that our immune system can't handle. And so that's a pretty important public health problem. So flu has basically two modes of evolution. One is up here, reassortment. Reassortment is when a red virus and a blue virus come into one host, and the virus that gets spit out from that host has a combination of red and blue segments. And then we have clonal transmission, which is what we commonly think of when we see a virus being passed from one person to the next. So there are two modes of evolution, they're not exclusive. Flu can do both at the same time. You can have a shuffled virus that then gets clonally transmitted, or you can have a clonally transmitted virus that shuffles with another virus. And there's this long standing dogma in the influenza world that says genome shuffling. It's important for host switches because flu is, can infect almost any large animal that you've seen. Ducks are considered the reservoir host. It's common chickens and pigs, we know that from the farm animal outbreaks. But it's also found in dogs, horses, ostriches, penguins, seals, all these gulls, all these large animals that you can see, it probably already has infected them. So is genome shuffling important for host switching? So what I did was I set out to develop an algorithm that sought to figure out for each virus, where did its segments come from. And that in itself is a graph. Right. And I can ask through some complicated set of modeling and equations and sort of stuff behind the scenes, which I won't go into here, through that, I can essentially define two types of relationships between the viruses. I can define a clonal transmission relationship, and then I can define a reassortment relationship in which that's basically what I'm showing up here on that side, where you have viruses and the black lines represent clonal transmission, and where you have two sources for one virus that's a reassortant virus. Using this, there was again, a bit more math, a lot of statistics, and a lot of hardcore brute force simulation studies that had to conduct. But we were able to provide, in the end, we were able to show that compared to random chance, the presence of these red edges. The presence of these red edges occurred more often than we'd expect by random chance when you had pairs of nodes that were of different viruses isolated from different host species. And what's the use of this? Truth be told, I don't really know. There's no direct application that we know of But I do have one poignant example to highlight why studying this sort of stuff for viruses is important. We all know about the HIV outbreak, right? It's a pandemic that devastated lives worldwide. Where did that virus come from? The best evidence to date suggests that the human immunodeficiency virus was the result of a crossover, a gene shuffling event between two monkey viruses. And so this novel new virus that jumped over from monkeys into humans was the product of one of these gene shuffling events. And so here maybe the ability to identify a shuffled virus could be one factor in determining whether a virus is a dangerous virus that we might want to look out for. And not just for flu, but also for other viruses that we're hunting out in the wild. There's a link to the paper if you are ever so interested. I did have a first year undergrad classmate. So one of my classmates from my first year of undergrad, he visited recently in Boston and he told me he looked at that paper and it was so dense that the first sentence, he was already googling definitions. So be forewarned, be forewarned. But it was very fun to do. And the final example that I want to show you is also something related to my work. We all know about this big hype in machine learning, right? Machine learning has the capability to extract relationships from structured data, right? And structured large data has the promise to revolutionize a lot of stuff. And neural networks are sort of like the hottest, bestest, to borrow Donald Trump, greatest tool that's out there right now for doing machine learning. But not every single piece of data that you can think of is going to be available in that structured, nice format. So let me give you one simple, simple example. Let's say we knew nothing about chemistry and we wanted to learn from experimental data what small molecules are going to be soluble in water, what small molecules are going to be toxic to human cells. We got all the data, we just don't have any theory. So one of my collaborators did something on small molecules, which I thought was really cool. So if you look at small molecules, that isn't a regular structured input that you can provide to a machine learning algorithm. Methane CH4 contains five atoms. Methanol contains six atoms. And if you look at sugars, sugars are soluble in water, but they contain at least six carbons, a whole host of oxygens, and many more hydrogens. So how do you do machine learning on a piece of data where this is the input, the network of atoms and the bonds between them are inputs? How do you do that? Machine learning on that type of data. Well, my collaborator David at Harvard, who is now a professor at the University of Toronto, he came up with this really cool generalization of image convolutions. So I'm not going to go through what image convolutions are here, but just know that with images, essentially what we're doing is we're modeling our data as a lattice, a matrix, and we're doing math operations on every single group of pixels. As we scan a filter over my image, we're doing some math operation at the top. And so what my collaborator David realized was this. If we look at a molecule and we look at a matrix, the matrix is just a structured network. It's just a structured network of pixels being the nodes and neighbors, neighboring pixels having edges between them. And our convolution operation, in which we do some window of, in which we apply some math operation to some window of pixels, can be generalized to stuff that isn't a structured network. So let me give you an example with what's up there. Let's say we want to. Just to illustrate the concept of what this convolution operation is, okay? So we have a network of integers, and those integers represent something about each node and in the graph. And a convolution operation might be defined as, let me just take myself plus my neighbors and pass that on to the next level, right? It could be something defined as simple as that. So if we apply that operation to the input graph, two plus four gives me six, four two, one minus six gives me one, and so on and so on. And we do that, and then we do the standard neural network stuff and we pass that on. And what we get at the end is this single fingerprint operation in which we just simply sum up all of the values that are present on the nodes. The claim here is that that fingerprint uniquely represents the structure of the graph plus the values that are present on the graph. Now, this is the case where we do it for single integers on a graph. But imagine now you have a fixed length vector that's associated with every single node. What do you get then? You get a single fixed length vector at the end of the operation, at the end of the convolution plus fingerprinting operation. And in that way, what my collaborator David was able to do was essentially transform this arbitrarily structured network into a fixed length vector that could then be put into machine learning algorithms. And this was, for me, an epiphany to realize that this operation that he was doing was essentially the generalization of something that was commonly used in the image machine learning world. So he applied that to small molecules. There's a paper that we've linked, I've linked on the slides as well that you can take a look. He was able to learn things like hydrophobicity of a molecule, learn from experimental data whether certain chemical groups on a molecule were predictive of toxicity to a cell. And by the way, this is very important for pharmaceutical companies because the medicinal chemists are always coming up with new molecules and they have this library of molecules that are out there. But you need to know whether something's going to be bad for the human cell before you can even go and try and use it against a particular disease. So he was able to predict all of that simply from the experimental data. And that was really powerful. And then when I looked at it, I was thinking about the problems that I was thinking about in influenza. We've got drugs against influenza and proteins fold and they're a network of amino acids, just like small molecules are a network of atoms. So what if we took that same learning algorithm and transferred it over to protein structures? Would that work? The answer is I think it does, but it's part of, it's still in progress work and I'd be happy to report back later on it. So proteins are just large, small molecules, sort of. And that's what allows us. And modeling proteins not as this linear sequence that gets put into a machine learning algorithm, but instead modeling it as a network allows us to explicitly capture those interactions that are important for things like drug resistance. So this is another example of where we have neural networks operating on networks and we're using networks as the input to machine learning. And that for me was extremely, extremely eye opening to see that this could actually be done. And it opens up a lot of possibilities. Network neural networks, sorry, machine learning on graph structured data is sort of one of the latest, newest topics. You're not going to find a lot of common literature on that. And if there are machine learning groups that you're plugged into, I'd really highly recommend that you guys download some of those papers. Start with David's paper, move on to the other papers that have followed from there and go study them. They're really, really cool. So here we had four examples of where networks were useful for solving problems. And we had this meta network thing where networks operated on networks and that sort of stuff. I'm going to leave you. If there's nothing else that I've left you with, I want to leave you with the idea that you may want to start thinking relationally about your data points and not just thinking of them as independent, identically distributed samples from a population. Because the relationships, the edges in a network form the heart of a graph. And that is where the richness of network analysis comes from. The final thing that I want to talk about, which was item number six, was visualizing networks. Can you tell anything about these three networks here? You probably could only tell that they're really large. They're really, really large, and they're messy, and they're hairballs. And I've made it a personal mission, almost a crusade of sorts of. To make rational. Make network visualizations rational again. All right, and in this last segment, I just want to share with you some principles of visualizing networks and make a little pitch for a little package that I've been writing. In order to visualize networks rationally, the only thing that you have to pay attention to is, is the placement of nodes. So I'm going to. I'm one of the leads for this network visualization package that's in development called nxviz. And the mission of NXVIZ is to make network visualizations rational again. All right, make NetworkViz rational again. And I'm just gonna highlight four different ways of visualizing a network which will all be implemented in nxviz. So the first way of visualizing a network is by a matrix. You can have the nodes listed as rows and columns of a matrix. You get a square matrix. The diagonals represent connections from a node to itself, and everywhere else where I filled it in red represent edges that exist from one node to another node. So in this case, on the diagonal, all I've done is just highlight that that node is that particular node for that row and column. If you take a look at the arc plot, it's a much more aesthetic and simplified. Sorry, not simplified. It's a much more aesthetic and rational version of the hairball diagram that you might see. And the principle is not very difficult. The idea really is group your nodes in some fashion, and within group each group, order them in some fashion, and then place all the nodes along one axis, one cartesian axis, and then draw arcs to represent edges between them. And you can get very nice and beautiful visualizations from it. If you search online, there's an arc plot of cross references in the Bible, right? And this was curated by a pastor and a data visualization expert who found, who manually looked through and put together the arc plot. Now, this, that arc plot is not useful for understanding anything in the text, but it's much more aesthetically pleasing. An alternative to looking at networks is to use the Circos plot. Now, how many of you have heard of Circos plots? Those who are in the genomics world will definitely have heard of those, because the Circos plot was first demonstrated, first demonstrated its utility in genomics. So the idea for the Circos plot is not too difficult as well. You essentially take the arc plot, you take the two ends and join them together such that you get a circle. And now you draw, instead of arcs between the nodes, you draw curved lines within the circle. And then you can start to selectively highlight certain different types of edges that are present in the node. And if you have a series of Circos plots, you can get a CIRCOS panel in which each plot in the panel highlights a different set of nodes. The final thing I want to show you is what we call hive plots. Now, Circos plots and hive plots. I won't make any claims of inventing them because, no, I didn't invent them. They were invented. At the BC Cancer Research center, there was this guy, Martin Krasinski, who wrote a lot of very good articles on data visualization in Nature Methods. He's the guy who really led the development of Circos and hive plots. Now, hive plots take rational visualization to yet one more level. Instead of having one axis, whether it's the circular axis or the cartesian axis, instead of having just one axis for grouping the nodes, you can actually now put three groups of nodes and order them in some particular fashion. So if you take a look at this graph here, it looks like there are more nodes, but in fact the light blue nodes are on the vertical axis, the yellow nodes on the left axis, and the dark blue nodes are on the right. All we've done is just clone them to visualize the intra group and intergroup connectivity. And with this visualization, it becomes immediately clear those dark blue nodes are isolated, they aren't connected to anything else. Right? And so with this set of visualization, we get something that, in which the structure of, the structure of placement of the nodes actually conveys meaning as opposed to that big massive hairball in which we probably can't infer much from looking at that network. All right, so I just wanted to leave you with that in terms of visualization. In closing, the core ideas I wanted to convey here are one, Think about your data relationally. Yes, you've got iid. You may have IID samples But those IID samples that may have relationships between one another that you can actually model, it could be a similarity network, it could be an actual physical interaction network, whatever you'd like. So think relationally about it. Because if you think relationally about them, you can then use the network structure to creatively solve problems from the simple stuff like finding paths between to get from one place to another to the more complicated stuff like machine learning on network structured data. And with that, I just want to say thank you for your time. My contact information is on the slides. I have a personal website also linked there. We're making a class on network analysis on data Camp. I just wanted to shout out to datacamp, thanks for the invitation here as well to come and share some of this with you. I'd love to connect with you after the talk. And thank you again for your time. At the back. Does it take more work computationally intensive network data versus other types of data. So the question is, is it more computationally intensive to work with network data as opposed to other types of data? So by other types of data, I'm assuming something like structured tables? Essentially, yes. Okay, so it depends on the kind of question you're trying to answer. If you've got something where you have to. So that I'll just. Actually, so I'll backtrack a little bit. Network algorithms can have computational complexities from N to N to the power. So from N to all the way up to something that's two to the power of N or some constant to the power of N. So depending on the type of question that you're answering, you may end up with poor computational complexity where the number of nodes, the computation time increases exponentially with the number of nodes. Now there are some cases where things like the simple stuff that I know off the top of my head right now, those are not, those are worst case computational complexity N, if I remember correctly. So O number of nodes plus maybe some number of vertices that are present inside there. So that is sort of the computational complexity aspect of that. So if you have an algorithm that operates on a data table, essentially it's O however many. Most of the time it's O however many data items you have or, or data items squared. But with graph algorithms can be different. Now the. In terms of a qualitative aspect, that's, that's also one place where it gets. You need to have your head wrapped around network theory a little bit in order to understand that, understand your problem in network theory terms. So some resources that I really like include Alan Downey's book on Think Complexity and Think Complexity. I actually credit that book with helping me kick start half of my thesis. The other half was like getting kick started at Boston Python. So Think Complexity was one book where during this free time that I had during grad school, I picked it up, I started working through the problems. It's a book that appeals a lot. Alan Downey's books, Think X series essentially leverage your ability to think through computation to learn other concepts. So he teaches stats, he teaches Bayesian inference, all using your ability to program. Right. And so Think Complexity was one similar book in which I looked at some of. I started working through examples in his book and used that to help me wrap my head around things like computational complexity, you know, finding paths, breadth first search, all this sort of stuff. So I'd really recommend that if you're looking for a book to pick up. So are there any other questions on this, Amir? Okay, so the question was on my thesis work, how many viruses? What's the scale basically of things that I was dealing with? I dealt with thesis, the influenza research database. And in the influenza research database, one nice feature is we have 30 years of data collection. We have sequences from 30 years of historical viruses matched with the host species, and best of all, the data of collection that was crucial for reconstructing the network of influenza viruses. When the paper was published, there were about 18,000 odd viruses that ended up inside the final data set that I had downloaded to date. Now I think there are about 21 to 22,000 viruses. The database is always growing. My research group advisor is part of this network of influenza researchers that go out and do the hard work, literally using Cheetos to capture, to lure gulls, to then capture the gulls to swab them. Right. That sort of field work that we computational types take for granted. There's this network of people doing all of this hard work. There's a question here.

Yeah, I was going to ask about.

The.

Deep networks on the graph structure data. So I think the convolution is just like a subgraph that you're moving over the version graph and then you're converting as you.

So the. Right, right, right. So the short answer is yes, but I'll repeat the question anyways. So the question is, are we in the convolutional neural networks. When we say myself plus my neighbors, isn't that essentially just a subgraph being my filter, right. On which I do the convolution operation? And the answer is yes, it basically is that. And it can be expressed as. From a technical perspective, it can be expressed as a sparse binary matrix multiplied by a dense matrix operation.

If you're moving that template around, if you have a lot of. If you have a big quantum graph, you going to do other multiplications. So that's kind of one way the complexity might explore.

Exactly. So what's the complexity of computations here? It's at least N, which is the number of nodes that are present inside that graph. Exactly. All right. Are there any other questions, Richie?

I have a question about the visualization.

Yes.

Once you start getting into having thousands of nodes or tens of thousands of.

Nodes.

Which one of those works best?

So the question here is, when we go to large graphs, tens of thousands to millions of nodes, where do we start with these network visualizations? I would discourage you with the matrix, because the matrix, it's a bad place. No, the matrix visualization is the visual space is N square, right? So it's N square with the number of nodes that you have. So that's going to be. And it's going to be a very sparse graph as well if you have a very sparsely connected network. Where I would start is always the arc plot. So the length is O, which is the number of nodes that are present inside the graph. And so we can do these tricks where we compress things or we use summarize things with like, bands rather than visualizing individual nodes. And with the arc plot, as you probably can see, it's actually the foundation of the CIRCOS plot and the hive plots. Right. The arc plot is founded on the nodes being ordered linearly in some fashion. Linearly ordered or grouped first, then linearly ordered. So I'd start with that. And then the more important thing, though is I think, to highlight sub portions of the graph that convey interesting structure. Nothing can beat that doing that, because visualizing the whole graph is actually not a very good idea. So I do have one example from my own research, which I didn't put inside here. I had the HA and NA subtypes of each virus, sorry, every HA and NA combination, each subtype of the influenza virus. And I wanted to show that particular subtype's connectivity to every other subtype. So in this case, what I chose to do was a CIRCOS plot, sorry, a circos panel in which I had one CIRCOS plot in every single HN combination. And I only highlighted the edges from that HN combination to every other HN combination inside the network. So I did the summary network sort of thing. And what that allowed me to highlight then was that there were some subtypes that were very highly connected to other subtypes and there were some subtypes that only had three connections to other subtypes. And what the connections were I won't explain here, but that mode of visualization let me visualize and visually inspect and check whether my network inference was right, because there's some background information about the H3N8 subtypes being present in lots and lots of virus host species. So we'd expect it to overlap with a lot of other viral subtypes. And so that's where this idea of filtering interesting things and selectively displaying them becomes very important. So with network structured data, it's so high dimensional, we ultimately end up having to highlight sub portions that are interesting. So with your NX based library you're building, are you a. The question is, with nxviz, will we allow people to zoom out or do aggregations and that sort of stuff? At the moment, no, but I think it's a great idea. All right, if there are no other questions, I'm happy to talk with everybody afterwards and just mingle around. Thank you.