[ot][spam][crazy][wrong] Reading a Book from Library Genesis

[Karl]

So!  Recap:

An adjacency matrix is an n-dimensional boolean array, where each
coordinate is a vertex, and each cell is whether or not there is an
edge connecting those vertices in coordinate order.

Then there is the unnormalized and normalized Laplacian matrix:
----

Defintion 2.28 (Laplacian Matrix)   For a given graph G = {V,E} with A
as its adjacency matrix, its Laplacian matrix is defined as
    L = D - A, (2.18)
where D is a diagonal degree matrix D = diag(d(v_1),...,d(v_|V|))

Another definition of the Laplacian matrix is a normalized version of
Eq. (2.18).

Definition 2.29 (Normalized Laplacian Matrix)    For a given graph G=
{V,E} with A as its adjacency matrix, its normalized Laplacian matrix
is defined as
    L = D^(-1/2)(D - A)D^(-1/2) = I - D^(-1/2)AD^(-1/2). (2.19)
----

The degree matrix wasn't pasted in.  d(v_1) appears to be the 'degree'
of node or vertex 1, which is the number of connections it has to an
edge. More at https://en.wikipedia.org/wiki/Degree_matrix .  A
diagonal matrix is a matrix that holds a single vector, with zeros
everywhere with inequal coordinates, and vector values where the
coordinates are equal.

The Laplacian matrix is simply the difference between the degree
matrix and the adjacency matrix.  Intuitively, I have no idea how that
makes sense, except for including the information from both, fully, if
there are no self-connections in the graph.

Noting, also, that if edges are multiple, you could use values >1 in
the adjacency matrix, and if edges are multiply propertied, you could
use multiple adjacency matrices or use an (n+1)-dimensioned
adjacency/Laplacian matrix for the additional properties.

I usually store graphs as an actual in-memory node graph, which I
imagine as taking far, far less memory, and this can be compressed to
a matrix of link indices which is only n * max_degree elements large.
I suppose with sparse matrices, the difference may matter little.

-

After the definition of adjacency matrices, the book continues with
Properties and Measures starting book page 19, pdf page 38.  A little
into this section interesting things are discussed, such as
eigenvector and betweenness centrality, but it seems like getting into
the model regressions faster could be interesting.  Anything that
shows current uses of some of these graph metrics.

Here's the start of section 2.5 Graph Signal Processing, book page 29
pdf page 48.
----
2.5 Graph Signal Processing

In many real-world graphs, there are often features or attributes
associated with the nodes.  This kind of graph structured data can be
viewed as graph signals, which capture both the structure information
(or connectivity between nodes) and data (or attributes at nodes).  A
graph signal consists of a graph G = {V, E} and a mapping function f
defined on the node domain, which maps the nodes to real values.
Mathematically, the mapping function can be represented as

f : V -> R^d, (2.24)

where d is the dimension of the value (vector) associated with each
node.  Without loss of generality, in this section we set d = 1 and
denote the mapped vaues for all nodes as f with [i] corresponding to
node v_i.
----

Okay, so graph signal processing sounds like just a way for
researchers to obscurify the fact that nodes hold data.  Flipping
forward ...

This looks like a helpful enumeration, book page 39, pdf page 58.
----
2.7 Computational Tasks on Graphs

There are a variety o computational tasks proposed for graphs.  These
tasks can be mainly divided into two categories: (1) node-focused
tasks where the entire data are usually represented as one graph with
nodes as the data samples; and (2) graph-focused tasks, where data
often consist of a set of graphs and each data sample is a graph.  In
this section, e briefly introduce representative tasks for each group.

2.7.1 Node-Focused Tasks

Numerous node-focused tasks have been extensively studied, such as
node classification, node ranking, link prediction, and community
detection.  Next we discuss two representative tasks including node
classification and link prediction.

Node classification
In many real-world graphs, nodes are associated with useful
information, which is often treated as labels of these nodes.  For
example, in social networks, such information can be demographic
properties of users such as age, sex, and occupation and users'
interests and hobbies.  These labels usually help characterize the
nodes and can be leveraged for many important applications.  For
example, on social media such as Facebook, labels related to interests
and hobbies can be utilized to recommend relevant items (i.e., news
and events) to their users.  However, in reality, it is often
difficult to get a full set of labels for all nodes.  For example,
less than 1% of Facebook users provide hteir complete demographic
profiles.  Hence, we are likely given a graph where only a part of the
nodes are associated with labels and we want to infer the labels for
those nodes without labels.  This motivates the problem of node
clsasification on graphs.

Definition 2.42 (Node classification)    Let G = {V, E} denote a graph
with V the set of nodes and E the set of edges.  Some of nodes in V
are associated with labels, and the set of these labeled nodes is
represented as V_l of V.  The remaining nodes do not have labels, and
this set of unlabeled nodes is denoted as V_u.  Specifically we have
V_l intersect V_u = 0.  The goal of the node classification task is to
learn a mapping Phi by leveraging G and labels of V_l, which can
predict the labels of unlabeled nodes (or v among V_u).

The above definition is for simple graphs and can be easily extended
to graphs with attributes and complex graphs introduced in Section
2.6.

Example 2.43 (Node Classification in Flickr)   Flickr is an
image-hosting platform that allows users to host their personal
photos.  It also serves as an online social community where users can
follow each other.  Hence, users on Flickr and their connections form
a graph.  Furthermore, users on Flickr can subscribe to interest
groups such as Black and White, The Fog and The Rain, and Dog World.
These subscriptions indicate the interest of users and can be used as
their labels.  A user can subscribe to multiple groups.  Hence, each
user can be associated with multiple labels.  A multilabel node
classification problem on graphs can help predict the potential groups
that users are interested in but have not yet subscribed to.  Such
data sets for Flickr can be found in Tang and Lui (2009).

Link Prediction
In many real-world applications, graphs are not complete with missing
edges.  On the one hand, some of the connections exist but they are
not observed or recorded, which leads to missing edges in the observed
graphs.  On the other hand, many graphs are naturally evolving.  On
social media such as Facebook, users can always become friends with
other users.  In academic collaboration graphs, a given author can
always build new collaboration relations with other authors.
Inferring or predicting these missing edges can benefit many
applications such as friend recommandations (Adamic and Adar, 2003),
knowledge graph completion (Nickel et al., 2015), and criminal
intelligence analysis (Berlusconi et al., 2016).  Next we give the
formal definition of the link prediction problem.

Definition 2.44 (Link Prediction)    Let G = {V, E} denote a graph
with V its set of nodes and E its set of edges.  Let M denote all
possible edges between the nodes in V.  Then, we denote the
complementary set of E with respect to M as E' = M - E.  The set E'
contains the unobserved edges between the nodes.  The goal of the link
prediction task is to predict the most likely edges.  Specifically, a
score can be assigned to each of the edges in E', which indicates how
likely it exists or will emerge in the future.

Note that the definition is stated for simple graphs and can be easily
extended to complex graphs introduced in Section 2.6.  For example,
for signed graphs, in addition to the existence of an edge, we want to
predict its sign.  For hypergraphs, we want to infer hyperedges that
describe the relations between multiple nodes.

Example 2.45 (Predicting Emerging Collaboration in the DBLP website)
DBLP is an online computer science bibliography website that hosts a
comprehensive list o research papers in computer science.  A
co-authorship graph can be constructed from the papers in DBLP where
the authors are the nodes and authors can be considered as connected
if they have co-authored at least one paper as recorded in DBLP.
Predicting what new collaborations between authors who have never
co-authored before is an interesting link prediction problem.  A large
DBLP collaboration data set for link prediction research can be found
inYang and Leskovec (2015).

2.7.2 Graph-Focused Tasks

There are numerous graph-focused tasks such as graph classification,
graph matching, and graph generation.  Next we discuss the most
representative graph-focused task; i.e., graph classification.

Graph Classification
Node classification treats each node in a graph as a data sample and
aims to assign labels to these unlabeled nodes.  In some applications,
each sample can be represented as a graph.  In chemoinformatics,
chemical molecules can be denoted as graphs where atoms are the nodes
and chemical bonds between them are the edges.  These chemical
molecules may have different properties such as solubility and
toxicity, which can be treated as their labels.  In reality, we may
want to automatically predict these properties for newly discovered
chemical molecules.  This goal can be achieved by the task of graph
classification, which aims to predict the labels for unlabeled graphs.
Due to the complexity of graph structures, graph classification cannot
be carried out by traditional classification, which calls for
dedicated efforts.  Next, we provide a formal definition of graph
classification.

Definition 2.46 (Graph Classification)    Given a set of labeled
graphs D = {(G_i, y_i)} with y_i as the label of the graph G_i, the
goal of the graph classification task is to learn a mapping function
Phi with D, which can predict the labels of unlabeled graphs.

In the definition above, we did not specify additional information
potentially associated with the graphs.  For example, in some
scenarios, each node in a graph is associated with certain features
that can be utilized for graph classification.

Example 2.47 (Classifying Protein Structure into Enzymes or Nonenzymes)
Proteins can be represented as graphs, where amino acids are the nodes
and edges between two nodes can be formed if they are less than 6
Angstroms apart.  Enzymes are a type of proteins that serve as
biological catalysts to catalyze biochemical reactions.  Given a
protein, predicting whether it is an enzyme or not can be treated as a
graph classification task where the label for each protein is either
enzyme or nonenzyme.
----

That's so cool!  It talked about social network prediction and
everything!  That was unfortunately a lot of hand-typing for me
(hand-typing helps me learn the material).  I want to do more but am a
little typed up right now.