WEBVTT Kind: captions Language: en 00:00:00.000 --> 00:00:03.920 Xingzhi Guo: So thanks for having us here. My name is Xingzhi.   00:00:03.920 --> 00:00:09.440 I'm a fourth year Ph.D. student working with  Professor Steven Skiena at Stony Brook University   00:00:09.440 --> 00:00:15.200 and Professor Skiena is also the Director of the  Stony Brook AI Institute. And this presentation   00:00:15.200 --> 00:00:21.040 is about how knowledge graph embedding  changes during COVID as our world changed.   00:00:21.040 --> 00:00:26.480 And the main content is based on a recent  paper published at SIGKDD 2021, collaborating   00:00:26.480 --> 00:00:34.320 with Boajian [Zhou] when he was a postdoc here. Okay, so let's go next. So first thing first.   00:00:34.320 --> 00:00:39.920 What is the graph embedding or others may call  it a network embedding or node embeddings? So   00:00:39.920 --> 00:00:46.080 basically, it's a function that maps a node in  the graph to a numerical vector which we call   00:00:46.080 --> 00:00:53.600 an embedding vector. So as the following example  shows, we could map every node in this graph to   00:00:53.600 --> 00:00:59.680 this 2D space. So the embedding could capture the  meaning of the node in the original graph but the   00:00:59.680 --> 00:01:06.400 fact that the closer nodes in the graph may have  similar vectors in the embedding space. So in this   00:01:06.400 --> 00:01:13.280 example, you can see the nodes with the same  color also get together to each other on this 2D   00:01:13.280 --> 00:01:20.240 plan. And most importantly, by this low  dimension numerical embedding vector, we   00:01:20.240 --> 00:01:25.680 could apply existing machine learning algorithms  for many downstream tasks. For example, the node   00:01:25.680 --> 00:01:33.840 classification, node clustering for the community  discovery or the outlier detection. And, however,   00:01:33.840 --> 00:01:40.720 this example is a static graph where there's  no new edge, no new node, everything is fixed,   00:01:40.720 --> 00:01:46.160 but in our real life our world is always changing.  So do the real world graphs and the nodes.  00:01:49.840 --> 00:01:54.560 Okay so let's take a look at the real world  changing graph - or we can call it a dynamic   00:01:54.560 --> 00:02:01.840 graph. So now in Wikipedia link knowledge graph,  each node is Wiki articles usually describing the   00:02:01.840 --> 00:02:08.560 real world entities and each edge is the hyperlink  connecting two articles, kind of like the citation   00:02:09.360 --> 00:02:15.200 we do when we're writing a paper. So this graph  is - it's large scale. We have millions of nodes   00:02:15.200 --> 00:02:20.080 and hundreds of millions of edges and it keeps  scaling up as you can see in this little figure.   00:02:20.720 --> 00:02:25.920 And certainly some entities may change  many and have been captured by this dynamic   00:02:25.920 --> 00:02:32.080 knowledge graph. And I want to show one  specific example of the city of Wuhan.  00:02:32.800 --> 00:02:40.640 Okay, so before COVID, Wuhan is probably less  famous to the people around the world. And at the   00:02:40.640 --> 00:02:48.320 end of 2019 and early 2020, I think most people  knew it as the first place of COVID outbreak.   00:02:48.320 --> 00:02:53.680 And I think - so I think this is a good example  of the changing of the or the changed entity.   00:02:54.320 --> 00:03:01.760 So here the figure shows a Wikipedia article of  Wuhan. And I highlight the hyperlinks it has. And   00:03:01.760 --> 00:03:07.040 the first two paragraphs are the geo[logical]  or some historical events related to Wuhan.   00:03:07.040 --> 00:03:15.200 But in 2019, suddenly, we see many COVID related  new links were created. So back to the graph   00:03:15.200 --> 00:03:22.080 embedding perspective, the question is how to  efficiently track those node embeddings in this   00:03:22.080 --> 00:03:28.240 dynamic massive graph so that we can detect the  embedding movement of the node and compare it   00:03:28.240 --> 00:03:36.320 across time so we can see how this changes? Okay, next, so this question motivates us   00:03:36.320 --> 00:03:42.560 to design a new algorithm that can handle a  problem that we call a subset node embedding   00:03:42.560 --> 00:03:48.640 in dynamic large graphs. So using this algorithm  we can track the embeddings of several predefined   00:03:48.640 --> 00:03:54.560 nodes. So it's a subset of nodes instead  of the four nodes in the graph that we are   00:03:54.560 --> 00:04:01.040 interested in as the graph keeps evolving. So  the key idea is to use personalized page rank   00:04:01.040 --> 00:04:08.160 which is very successful algorithm used by Google  search and one advantage over other methods is   00:04:08.160 --> 00:04:15.200 that we could compute only what we need for the  subset nodes of - for the subset nodes, while most   00:04:15.200 --> 00:04:22.240 other algorithms have to compute all embeddings of  every node across every time. But they finally use   00:04:22.240 --> 00:04:28.800 only part of them, so the rest of them are just  wasted. So our algorithm is more efficient and   00:04:28.800 --> 00:04:34.960 faster it's very suitable for this problem but for  more details please refer to our paper, which are   00:04:34.960 --> 00:04:39.520 just here [https://arxiv.org/abs/2106.01570].  And as this example illustrates the concept,   00:04:40.400 --> 00:04:45.840 our method can calculate the embeddings  of a specific node, in this case Wuhan,   00:04:45.840 --> 00:04:52.480 across different years. And we can expect a  huge embedding movement from 2019 to 2020.  00:04:53.440 --> 00:05:01.200 Okay, so next - so let's see the experiment  result. First, we collect the English Wikipedia   00:05:01.200 --> 00:05:07.440 graph snapshot every day in 2020. And as I  mentioned before is a very large dynamic graph.   00:05:07.440 --> 00:05:14.320 You can see in this table roughly we got 30,000  new edges inserted every day and we released the   00:05:14.320 --> 00:05:20.880 data in this GitHub repository so it's very easy  to access. And we keep track of Wuhan together   00:05:20.880 --> 00:05:28.480 with other hundreds of Chinese cities. And this  figure shows how the changes we detected in the   00:05:28.480 --> 00:05:34.080 embedding space so as you can see, the curve  of Wuhan is prominent. They have a huge peak   00:05:34.640 --> 00:05:40.960 and we highlight several peaks with annotation  and found that they are all correlated with,   00:05:40.960 --> 00:05:48.560 correlated to the timeline of COVID. And there's  another peak - you can see we spot one other peak   00:05:48.560 --> 00:05:54.160 in the city of Chengdu which reflects the  U.S.-China diplomatic tension when the U.S.   00:05:54.160 --> 00:06:01.040 decided to close the consulate in Chengdu. So it  has the serendipity we discovered in this study.  00:06:03.440 --> 00:06:10.480 So, oops, so, uh - we have another experiment  where we want to see the most changed cities in   00:06:10.480 --> 00:06:15.840 different time periods. So we rank the embedding  movements of the tracked node at each time   00:06:15.840 --> 00:06:23.040 and found that, you can see, Wuhan usually is  usually the top changed one among others as COVID   00:06:23.040 --> 00:06:30.880 evolves. And we highlight the news title  in that time period so we can have an idea   00:06:30.880 --> 00:06:38.400 of what happened in that place. Okay. So the major takeaways are:   00:06:38.960 --> 00:06:43.440 we have a very efficient node embedding  algorithm that can capture the embeddings   00:06:43.440 --> 00:06:50.000 in very large dynamic graphs. Then we investigate  the evolution of Wikipedia knowledge graph in 2020   00:06:50.000 --> 00:06:53.520 and found the interesting node  changes during COVID. For more detail,   00:06:53.520 --> 00:06:57.555 please refer to our paper and see the released  resources. [https://arxiv.org/abs/2106.01570 and   00:06:57.555 --> 00:07:00.560 https://github.com/zjlxgxz/DynamicPPE]  And yes, thank you, thanks!