CS224W_2019fall_note_01

Original article can be found here (source): Artificial Intelligence on Medium

I have been learning machine learning theories and techniques for almost 6 years. I don’t have experience studying aboard but I think some computer science programs from famous universities, e.g., Stanford, Berkeley, and so forth, is not that difficult to learn and I want to share what I have learned from these courses and some thoughts. That’s the reason why I want to start this series. Moreover, writing a series of blogs is an amazing way of organizing knowledge. And these materials could even be used as what you need to write a thesis in the future. Ok, let’s begin this journey.

What is network?

Let’s start with the question that what is network. Basically, network is universal language for describing complex system with heterogeneous of interacting among entities. Sometimes we use the word “graph” as the substitution of “network”. It’s noted that it’s “graph”, not “photograph”. A bunch of researches about graph theory are related to this word. By connecting thousands of nodes with thousands of edges, we have a network. It’s not the formal definition of network, but I wish that you could understand the meaning of that intuitively.

Types of network.

Many types of data could be described as networks. For example, social network. Social network is not a new thing but from ancient time. The society of human is a social network. The scale of social network is growing bigger and bigger as the time past and technology develop. In the era of internet of things(aka. IOT), more and more electronic devices are engaged in the social network, which could extremely enlarged the amount of data in it. Other types of network are showed as follows.

Why networks?

Apparently, a host of reasons contribute to the emergence of research of networks. From my perspective, the following 3 are the most essential ones.

Understanding of different systems.

The society could be regarded as a system, which has a large number of phenomena which we wanna understand. But how? The network could be a potential solution to it. Once we understand the network behind the society, we have a great chance to be able to model and predict it.

Enhancing the performance.

About 3 or 4 years ago, I read a book called the beauty of math written by professor WuJun. There is an impressive question asked by him, “why the communication between people is so brief and efficient?”. In communication system, if 2 machines want to cooperate with each other as well as possible, they need to transfer information to others as complete as possible. By contrast, human doesn’t, at least in most of scenarios. For instance, 2 people is talking about an NBA game between New York Nicks and LA Lakers. One says “what was the result tonight?”. His friend says “You know, BLACK MAMBA was in his zone tonight.” “alright. “. If the conversation is seen as corpus and fed to the machine learning model which harnesses the traditional NLP techniques, the model will get nothing. Because human have basic knowledge and common sense. They can reason something without getting the complete information. What we should do to fix this problem, just like I said, the network. Technically, the knowledge network. If we have knowledge graph which includes the knowledge that black mamba means Kobe Bryant, Kobe is a player in Lakers and “in zone” means great performance, the model might have a reasonable inference that the Lakers won tonight. The knowledge mentioned above could be called domain knowledge. Complex domains have rich relational structure, which can be represented as a relational graph. By explicitly modeling relationships we achieve better performance.

Sharing vocabulary between fields.

Using the same description language in different fields might be a good approach to organize knowledge.Furthermore, by gathering domain knowledge from different fields, e.g. economic, biology and statistics etc, probably we will be closer to artificial general intelligence (aka. AGI) .

Applications of network.

Several examples are showed in lecture 1. We could see that how powerful the graphs are. From my point of view, the network can be regarded as important complementary methods to natural language processing and they can enhance each other. For example, the meaning of a certain sentence could be better understood by the reasoning from the knowledge graph. On the other hand, the knowledge graph could be enlarged by extracting information from a large amount of raw corpus which is the hidden treasure in our world. Some examples of application are showed as follows.

The circle detection of human society.

Recommending products

Detecting fake new or correcting misinfomation

Predicting side effect

Basic knowledge of network.

After the briefly introduction of network, we might have already got concepts in our minds. You might be curious about more details about that. Then let’s go over some basic knowledge of network.

Structure of network

A network in a collection of objects where some pairs of objects are connected by links. For simplicity, we are gonna describe the components of network with some symbols.

Where N is the nodes or vertices, E is links or edges, and G is the whole graph composited by nodes and edges. I will continue to use this symbol set in latter notes.

As I mentioned before, the network is a universal language to describe different systems. As it’s showed above, the actor network and social network, both of them can be described as the a particular network with the same structure. What’s the advantage of that? It’s much easier to transform the practical question to a mathematical question. And once we do that, we could use the same methodology to solve them.

Defining a network

Before we build a network, some questions should be taken into account. What are nodes? What are edges? What domain knowledge do you want to access? For example, if we want to build a network with respect to nCOV-2019 disease problems in order to estimate the scale of infected people in China, we might need to define a contact network with people as nodes and the probability of contact as the edges in it. This paper

https://www.medrxiv.org/content/10.1101/2020.02.20.20023572v2

is a related work published on MedrXiv. It’s my honer that I am one of the participants of this work and I am YiNing Huang from Sinohealth Research Institution.

Edges of networks

Edges are important components for describing relationships in a graph, which make the networks more enriched and knowledgable. In order to represent information as much as possible, the variants of edges could be roughly viewed from 3 perspectives. Let’s go a bit further.

directness

Directness represents the directions which some nodes point to, which could be divided into to types, directed and undirected.

degree

How many edges go in to a node or come out from a node is one of the basic properties for describing a network and which is often used for modeling and predicting the behavior that the system performs. Nevertheless, the degree of a certain node can be viewed in terms of the directness.

You might have heard of a concept called complete graph. That means all the nodes are connected to the rest of them. You can imagine how dense this graph is. In most cases in the real world, they are sparse. You don’t every single person in the world, right?

weights

For the sake of represent the different importance between people, the concept the weights is introduced. You might have a lot friends, but you don’t treat them equally. There must be someone who you care about the most.

Connectivity of network

If any 2 nodes are connected to each other in an undirected graph, we can say that the graph is connected. However, in real world, not many graphs are fully connected. In specific, the clear definitions of connected component, isolated node, bridge edge, and articulation node are showed in the following slide snap shot/

Wherever, for the directed graph, there is more specific way to describe the connectivity, which are strongly connected directed graph and weakly connected directed graph.

Moreover, there are many other options can be taken into consideration when you are going to build a network.

Some ways of representing networks

K-partite graph

If the types of node in the network could be divided into K disjoint sets, it could be represent as K-partite graph. The example of Bipartite graph(2 disjoint sets) as showed as follows.

Adjacency matrix

For a graph composited by N nodes, we can get an N by N adjacency matrix. Furthermore, directness, weights can be represented by using elements in the matrix.

Edge list

Adjacency list

Noted that, if a graph is sparse but with a large number of nodes, you’d better use adjacency list to store it.

Some real world cases

There are some real world cases in terms of properties mentioned above. Hope that you could draw inspirations from the examples.

conclusion

So far, this is the first lecture of CS224w 2019 fall. We have gone over some basic stuff with respect to the network. I will cover the details as much as possible in the following notes even including homeworks and projects. One more thing, this is not an easy course to learn but I think you will get a lot if you insist to go over the whole course. Lastly, I wanna end up this note by using the photo of the idol of my whole life, mentor, never-met friend, the late Kobe Bryant. Heroes come and go, but legends are forever. MAMBA NEVER OUT.