[00:00:00] Elizabeth Hohman: So often in any place where you have a sponsor or a client who’s giving you data, often the sponsor or the client, they just slap some data on your table and say, find me something. They think that just having the data means that you can use machine learning to pull nuggets out of the data. They don’t even wanna define what that means. They just say, here’s my data, that’s my value. Use data science to show me something, and that can be frustrating. I have big data, I have so much value in my data, but really it’s your people who have the value. It’s your people who hold the knowledge about the data. That’s where the value exists. And how can you fuse person knowledge and data?

[00:00:41] Elizabeth Hohman: Because yes, you can use highly nonlinear machine learning things. You can build a neural net. You can do very complicated models over the data, but most of us believe that you are going to do better, more interpretable and actionable results when you actually understand the data.

[00:01:02] Eliza Mace: Hello and welcome to MITRE’s Tech Futures podcast.

[00:01:06] Eliza Mace: I’m your host Eliza Mace, and I’m a lead machine learning engineer here at MITRE. At MITRE, we offer unique vantage points and objective insights that we share in the public interest. In this podcast series, we showcase emerging technologies that will affect the government and our nation in the future. Today we are going to be exploring not just one, but two recent MITRE investigations into the world of learning with graphs.

[00:01:28] Eliza Mace: First, we will find out how to construct graphs from data and studying the resulting relationships and then we’ll take a peek into the future of machine learning with graph neural networks. Before we begin, I wanna say a huge thank you to Dr. Kris Rosfjord, the Tech Futures Innovation Area leader in MITRE’s research and Development program. This episode would not have happened without her support. Now without further ado, I bring you MITRE’s Tech Futures podcast, episode number 16.

[00:01:53] Eliza Mace: In our opening, you heard from Dr. Elizabeth Homan, a principal data scientist here at MITRE. Recently, Dr. Homan has been studying ways to do just what she described, use subject matter expertise to guide the analysis of big data. Specifically, she will walk us through the process of studying relationships and data by constructing a graph and then studying that graph’s properties using graph theory.

[00:02:24] Eliza Mace: But before we jump in, we need to get on that same page about what exactly we mean by graphs and graph theory. 

[00:02:30] Elizabeth Hohman: It’s important to define the kind of graphs we’re talking about. Lots of times when people hear graph analysis, they think analyzing plots, or doing analysis on data where you either end up with graphs, plots that we learned in high school. This is a graph right on graph paper, but that’s not what this kind of graph construction is talking about.

[00:02:51] Elizabeth Hohman: When you talk about graph databases and graph theory, it’s a very specific type of graph. It is actually a mathematical object. It’s not a drawing. It’s a mathematical object, and it consists of a set of entities and a set of relationships. So that’s very abstract. But let’s say this way, a set of entities like phone numbers and a set of relationships like this phone number calls this phone number.

[00:03:15] Elizabeth Hohman: When people say graphs and graph databases, the thing that holds all the rich information are the relationships. The fact that my phone number called your phone number. That’s what’s important. That’s the kind of graphs we’re talking about. Graphs where the thing you’re trying to represent and the thing you’re trying to learn from is how these entities are connected. So the entities are also called the vertices in the graph, and sometimes they’re called nodes.

[00:03:41] Elizabeth Hohman: When we’re talking about this kind of graph, it’s usually depicted with a picture of circles and lines. The circles are the entities and the lines are the relationships and this all comes from graph theory, how you represent the graph and how you actually do math on the graph comes from the mathematical subject area of graph theory, and most of the mathematics boils down to linear algebra.

[00:04:04] Eliza Mace: In lieu of an attempt to verbally describe linear algebra operations, let’s focus on the intuition behind the kinds of questions we can answer with graphs.

[00:04:13] Elizabeth Hohman: So now suppose we have this graph, which is a set of phone numbers. Those are the nodes or entities, and a set of relationships. My phone number calls your phone number. That is the straight line, the connector, that’s the edge. Now, we might ask questions about this graph or network, such as what’s the phone number that gets called the most often?

[00:04:33] Elizabeth Hohman: What are the set of phone numbers related to my phone number? Who are the people I call most often and what’s that network? Who are the people they call most often? And how do the edges between the network of people I call? What do those edges look like versus the edges coming out of, say the number for the pizza delivery service?

[00:04:52] Elizabeth Hohman: The number for the pizza delivery service kind of looks like a star. It has a bunch of lines out it to tons of different phone numbers. And those different phone numbers, they hardly ever call each other. So it’s like a star. The network between me and you as friends, there’s a link between me and you as friends, and there’s a link between me and a few other friends I have and that set of my five friends, a lot of them call each other cuz we’re a friend group.

[00:05:14] Elizabeth Hohman: My network that comes out from my node looks very different than the pizza parlor network, right? And so you can learn some things about the nodes, the entities, by looking at the edge structure that comes out of those nodes and entities. That’s called the degree of my node. The degree of the pizza number node is in the hundreds; the degree of my node is five. I have five edges coming out of me. There’s only five people I call. This is hypothetical. I have more friends than that.

[00:05:40] Eliza Mace: You know, Dr. Hohman, I think you’ll make a lot of new friends as people start to realize all of the possible applications of your work. There are so many real-world examples of entities and relationships that are relevant, not just to our work at MITRE, but to our functionality as a country.

[00:05:55] Eliza Mace: Consider the phone communications graph. Not just of Dr. Hohman and her favorite pizza joint, but of a network of nefarious actors -what can we learn about them? What about the integrity of supply chain operations, where many systems have to function individually and in tandem? Let’s hear from senior principal operations researcher Dr. Joe Hoffman about problems he has tackled with graph theory here at MITRE.

[00:06:17] Joe Hoffman: Graph theory is not just about the properties of an entity that’s in a system, but it is also about the relationships between different entities. And so the easiest way to understand it is an exchange between two entities. For instance, one person might send an email to another person and they send it to another person, and there’s a whole network of communications that happens there. Air traffic control is where I spend most of my time working. And when an airplane takes off, it’s talking to one controller and the controller hands it off to the next controller. And each controller has a sector in the country and they hand off aircraft back and forth to each other.

[00:07:01] Joe Hoffman: And when you look at the relationships between entities, you start to see things that are not visible. If you just look at the controllers themselves or the airplanes. The relationships between the various controllers can frequently tell you things about the capacity of the system, because, for instance, talking to the same person you were talking to a minute ago is easy.

[00:07:28] Joe Hoffman: You don’t have to start a new conversation. So if one controller is always talking to another control, and handing them an aircraft after aircraft after aircraft. That’s a very simple high capacity system. If you have aircraft coming from all different directions, so you’re talking to a different controller every time another airplane appears, that’s a much more complex situation and you might see that the capacity is lower.

[00:07:54] Joe Hoffman: This is something that air traffic controllers have told us since day one. It’s very hard to measure that if you just look at the number of aircraft per hour or some simple metric like that. The graph structure shows you the capacity of the system in a way that you can’t see looking event by event.

[00:08:13] Joe Hoffman: Networks and exchanges happen in all parts of life. For instance, the Bitcoin network, you can find people who are sending money back and forth to each other, and if you are interested in certain suspicious characters and whom they send money to and receive money from, then you can build the whole network out of that.

[00:08:32] Joe Hoffman: One classic case that was, I thought particularly brilliant maybe oh, 20 years ago even, is by looking at letters that were exchanged between various people in the colonies here in America, just before the Revolutionary War. A graph analysis enabled them to identify Paul Revere as the person who was going to be the critical link in the resistance against the British, just from who sent letters to whom. We are, I guess, lucky the British did not have advanced graph theory back in the 18th century.

[00:09:07] Eliza Mace: We’ve talked about extracting information from graphs, but how does this connect back to our opening where Dr. Homan described the issue of encoding domain expertise in data analysis? Let’s hear her walk through the process of going from, in her words, someone slapping data on your table all the way to a graph constructed with subject matter expertise baked in.

[00:09:27] Elizabeth Hohman: So in most graph applications, the graph is defined before the beginning. The graph is defined a priori that in this phone call network, the graph is defined. In the social network of relationships between people that graph is defined. Or in the social network analysis of a Twitter network or LinkedIn network, those graphs are defined. The relationship is there or not. You follow the person or you don’t, you email the person or you don’t.

[00:09:55] Elizabeth Hohman: In our case, we start with just a data table and we’re saying, let’s make each row a Vertex or an entity and we’ll connect rows -vertices or entities- if they’re similar under some definition of similar, but I have to tell you what similar means. I’ll have to define similar so that you end up with an induced graph over this data set that you started with. We’re not starting with, I have these telephone numbers and I know who has called whom. We’re actually starting with a data table like you’re used to seeing an Excel spreadsheet where each row is, say a person and each column contains some information about the person. The first column might be salary, and the second column might be a string saying where they work.

[00:10:38] Elizabeth Hohman: And the third column might be their height. And so we have columns that characterize the people. And then from that data frame, we want to draw a graph where people who are similar in certain ways have an edge between them. You want it to be such that the relationships between the rows in the data frame are meaningful in some way, and the cool power of that is you can define what meaningful in some way means An edge will exist if they’re similar.

[00:11:14] Elizabeth Hohman: You’re bringing in subject matter expertise cuz that person is saying, how do you define similar here? And that person doesn’t have to be a mathematician. You can ask the subject matter expert things about the columns of data, and then you can encode that so that you end up with a graph that captures relationships between your data that you started with.

[00:11:37] Eliza Mace: To summarize the process, you start with a list of properties of each entity, and then you use subject matter expertise to define how these different properties contribute to similarities between your entities. This is a hands-on way to select features of each node and their contributions to relationships.

[00:11:54] Eliza Mace: In contrast, as the field of machine learning advances, there has been renewed interest in leveraging advances in neural network techniques to study graphs without having to define the features by hand. Dr. James Tanis, a lead mathematician here at MITRE, has been studying graph neural networks, a marriage between deep learning and graph theory.

[00:12:11] Eliza Mace: Let’s hear about some of the challenges of adapting neural network technology to work with graphs. One quick note in his description, Dr. Tanis mentions convolutional neural networks, which are a special type of artificial neural network that are used to extract information about images. What you need to keep in mind is that many traditional neural network models can reuse a lot of the same structure, whereas as we are about to hear, the structure of graphs can make things a bit more complicated.

[00:12:39] James Tanis: This approach is based on feature learning, where you are incorporating the learning of features into the training process. And this should be successful because intuitively the features are directly adapted to the problem that you’re trying to solve. It’s historically well motivated in that there has been profound success in computer vision.

[00:13:10] James Tanis: One thing that I would like to differentiate between graph neural networks and the convolutional neural networks for image processing is that the graph neural networks are harder to use and that they are much more dependent on the graph data set that you are working with. The convolutional neural networks that have been so enormously successful over the last 10 years- it’s working on images, which are grids of pixels, and so these are extremely simple and very structured. Given any image, you can resize it into a range that the model will accept, but the graph neural networks are harder to use in that the components of the model are much more dependent on the task that you’re doing as well as the data set that you’re working on.

[00:14:10] James Tanis: The graphs can differ based on obviously, the number of nodes and edges would be the size of the graph, but then also within the graph there can be a lot of variation in that the number of connections between nodes can be very different from one node to another node, as well as in fact, you can have nodes that are completely isolated in a graph which doesn’t occur in images.

[00:14:43] James Tanis: The graph can also change over time. And not only in the data on the graph, but the structure of the graph can change over time. You can have a road network where the graph structure is fixed, but the data on the graph, meaning the velocity or volume data changes. But in a computer network, you can also have that the number of the nodes can change. They can appear, disappear, and connections between notes, which is to say the edges can appear or disappear.

[00:15:18] Eliza Mace: As you may be aware. The field of machine learning is changing rapidly with new innovations being published at a breakneck pace. So many of these techniques can transfer across fields, including into graph neural networks.

[00:15:29] Eliza Mace: I asked Dr. Tanis for a specific example of a shared technique from a different machine learning discipline. He described to me how the concept of attention is useful for the study of weighted graphs. The term weighted graphs just means that edges can have properties beyond just their presence. Like Dr. Tannis was saying earlier, If you had a network of roads connecting cities, the edges of the graph would be the roads that exist between the different cities and a property or weight of that edge might be the speed limit on that particular road, or the volume of traffic that traverses it in a given timeframe.

[00:16:01] Eliza Mace: So what does this have to do with attention? Attention, like many techniques in the machine learning field is named after a human behavior, in this case, paying attention to things. Basically we are training an algorithm, not just to consider a connection between two items, but also the strength of that connection.

[00:16:18] Eliza Mace: Consider a classic application of attention in natural language processing. I say the sentence, “Stephen has a dog and he is playful”. Which word is the antecedent of the pronoun “he”? Is it Stephen who is playful or is it his furry friend? A machine learning algorithm outfitted with an attention mechanism would hope to disambiguate such a sentence by checking how the word “he” attends to the other words in the sentence. Hopefully you can see where I’m going with the importance of this technique since we know by now that graphs are all about capturing relationships

[00:16:52] James Tanis: you want to learn the relationships between nodes as well as possible, and that especially includes what is the strength of that relationship, which could also be negative.

[00:17:04] James Tanis: So an example in Twitter, Someone sends a tweet and you can like it, and that would be a positive reinforcement of that tweet. And so then maybe your weight that you would give between the tweet, a person who likes it would be positive, but you could also have a person tweet and another person respond negatively saying, I don’t like this.

[00:17:30] James Tanis: And there you would want the weight to be negative between those two individuals. Weights can be positive or negative, and they should indicate some kind of relationship between them, which occurs both at data level, but also on the prediction or modeling level where you’re trying to understand the relationships.

[00:17:52] Eliza Mace: All of these techniques we’ve heard about today revolve around thinking about your data in terms of relationships. Dr. Hoffman left me with these words of wisdom.

[00:18:01] Joe Hoffman: The thing that I would like to encourage people is whenever you have a problem and you’re approaching it your usual way, and it seems intractably hard, ask yourself if this is actually a graph.

[00:18:15] Joe Hoffman: It’s a very cheap way to add an entire dimension to your capabilities for understanding what’s going on. Ask yourself if this is actually a graph because you have properties of entities and those are easy to measure, but when you look at the relationships among them, you notice there are relationships.

[00:18:33] Joe Hoffman: Between the properties of the nodes, there’s not just the message itself. So one kind of idea, for instance, can be at one part of a node and other connected nodes can start to get that idea too. If we’re talking about a social network we can talk about, you know, memes using in the Richard Dawkins idea, the original definition, not the LOLCATs.

[00:18:55] Joe Hoffman: You know, the idea that that a meme has as it percolates out through society. This is a graph based phenomenon.

[00:19:00] Eliza Mace: Okay. I bet you didn’t think a podcast about linear algebra would end up at memes, but it just goes to show you the value of grounding lofty mathematical ideas into real world applications. Speaking of which, if you have an idea for applying graph construction or graph neural networks to your work, you can check out Dr. Hohman’s recent paper or Dr. Tanis’ paper at techfutures.mitre.org

[00:19:22] Eliza Mace: Thanks so much for tuning into this episode of MITRE’s Tech Futures podcast. I wrote, produced and edited this show with the help of my co-host, Courtney Finn Clark, Dr. Kris Rosfjord, Dr. Heath Farris and Beverly Wood. Our guests for this episode were Dr. Elizabeth Hohman, Dr. Joe Hoffman, and Dr. James Tanis. The music in this episode is brought to you by Ooey, Truvio, Chill Cole, Imprisimed and ,Frank Jonsson.

[00:19:52] Eliza Mace: Copyright 2023, the Mire Corporation approved for public release; distribution unlimited. Public release case number 23- 0 2 69

[00:20:02] Eliza Mace: MITRE solving Problems for a Safer World.