Difference of Prediction between Graph Representation and Data Matrix Representation

Question

In data mining, data can be usually represented in different forms such as records of a matrix, graphs or ordered data. While we find in research different papers addressing methods or solutions for these different representations, there is no clear description of the advantages of every representation compared to the other (i.e when different representations can be applied to solve the problem, under which conditions, a particular representation would have an advantage?).

Here, I am interested in knowing what is, in particular, the advantage of the graph representation over the data matrix representation and vice versa. I realize that different problems would have an intuitive representation as one of the two ways. For example, a social network, is intuitively, represented as a graph while patients records, is intuitively, represented as a data matrix. However, I want to know how these representation compare when there is a prediction task and both representation can be used to solve the task.

An example that may illustrate my interest is chemical-protein interaction network. In this network, chemicals that may have an effect on a specific protein target, will have an active relationship. This active relationship can be represented either as an edge of weight 1 between a chemical and a protein in a graph or as a positive label for a set of features describing the compound in a record. Another example would be the author-paper network. To predict the author of the paper, we may extract features from the papers and build our data matrix. Another way, would be building a graph in which a new paper is linked with the most similar paper and then, we try to predict who may be the authors based on traversing the graph.

One answer I would have once thinking about these two representations is the different levels of describing the data. In a data matrix, there is the advantage of having many variables describing a given case or sample. In graphs, on the other hand, it is only one variable representing the similarity between the samples. Nevertheless, a graph topology may highlight important nodes in the network. What else ?

In summary, I am interested to know the expert advise on when to use a graph representation or a data matrix representation and why? If you are someone who likes graphs and prefer mining them, tell me why?

Answer 1

I'm trying to answer the question in one aspect.

Generally a graph can be described by a matrix, with the columns and rows indexed by vertex, and elements corresponding to the edge weights. And adjacent matrix can also describe an undirect/direct graph. So graph analysis is usually equivalent to perform analysis on matrices. In fact, many graph-based algorithms can be implemented through matrix operations, and some big data problems such as biological network and social network (and also the most famous one,google page ranking) are often treated as a matrix to do the further numerical analysis.

Take social network as an example. Network analysis uses nodes to represent people and edges to represent ties or relations between two people. You can use two colors of nodes to represent the gender, and use a directed edge from node A to B indicating "A chooses B". When there is two directed edges from both A to B and B to A, their ties are reciprocated and they share a relationship. But that may be all the information a graph can include. We don't know whether a shared tie means A and B are spouse or friends, although we may induce more forms of lines to differentiate them (dash lines, color lines, etc.). Yet when there are many people in the network and/or many kinds of relations, the graph becomes too visually complicated to display the patterns.

Representing information in the form of matrices seems more flexible. Because we can

(1) establish a bunch of matrices. We separate different relations with binary matrices. We can also,

(2) implement matrix permutation, then obtain a block density matrix (for example the ratio of one specific relation between male and male, male and female, female and female...).

(3) With the boolean matrices, the AND, OR, XOR.., and with other matrices, addition, subtraction, multiplication, and even inverse operations can be implemented with the selected matrices for further processing.

(4) those matrix operations all have their practical meanings.

 (i) Adjacency matrix indicates whether there exists a path between two people, and the paths number of length one from each person to another; 

 (ii) Squared adjacency matrix tells us how many pathways of length two are there from each person to another, so on and so forth. Measuring the path number and lengths among the people in the social network allow us to index and infer some important tendencies; 

 (iii)The eigenvector analysis is another approach to find the "global" structure of the network in opposite to a  "local" feature. 

(5) Last but not least, structural analysts in subgroup , or clique (graph) can also be represented with matrix. And the clustering methods also handles high-dimensional arrays.