Impact sensitive ranking of structured documents
Year: 2011

Ranking is an algorithm that defines an ordering among object s. This thesis will address the challenge of ranking structured documents. Traditiona l ranking methods involve link analysis, relevancy measure, or manual assessment; the aim is to rank the "important" document higher than the less "important" documents. The me aning of the term "important" would need to be defined. For example, one may rank the do cuments according to their popularity, by considering the number of documents which are linked to it. One may consider the "quality" of the documents, and rank the doc uments according to this "quality" criterion. Or one may consider the "relevancy" of the documents, and rank documents higher the more relevant they are to a given situat ion. However, most of these methods are not taking into considera t on the contents of the document. The "popularity" and the contents of the document are actually inseparable in the study of document ranking according to an "important" cr i erion. The content of document as well as its structural properties can be extracted a nd the structural properties can be expressed as a graph representation, involving nodes (re presenting word tokens) and links (links among the word tokens) Note that in this repres entation, the word tokens are merely "symbols" they are not endowed with meanings, thus a voiding the tedious task of providing word tokens with meanings. The contextual info rmation is inferred from the statistical properties of words which co occurred in th e same order, and in similar context within the given text corpus. This graph representa tion is called a concept link graph. In this thesis, we propose a novel representation cal led graph of graphs (GoGs) representation to describe the structured documents, whic h may be connected by hyperlinks or citations. A GoGs is a hierarchy of graphs, the top le vel graph is the concept link graph, and the nodes in this top level concept link graph can b e described by other concept link graphs which represent the documents which linked into the top level document, vi and so on. Such a graph of graphs representation can be very us eful to model the interlinking of documents by encoding the structural informatio n at different levels, such as the relationships among documents, relationships among pa ragraphs within a document, relationships among words within a paragraph of a document, etc. This representation allows us to include document properties and contents to dif ferent depth, so that it can be used in different machine learning applications. We then propose a novel machine learning method (graph neura l networks for graph of graphs) GNN which is extended from a supervised learning method, viz. a graph neural network (GNN)  This model is capable of encoding GoGs without the need to pre process the graph representation into a set of vector ial inputs first, and is applicable to both classification and regression problems. This thesis will consider the ranking of large scale (hundre ds of thousands) corpus of structured documents using the popularity criterion, bu t with consideration of content information, by deploying the GNN 2 methods. The main questions which are studied include: what features and structures can be extracted from the documents; how to combine the extractions to encode the structures; what are the p rocessing methods for such structural documents; and how these methods perform on diff erent classification and clustering problems. Through investigating these questio n we conclude that the GNN 2 and GoGs representation are a good combination for solving t he ranking problem on a set of inter linked documents. This thesis presents a number of findings: A novel unsupervised machine learning method called probab ility mapping graph self organizing map (PMGraphSOM) this is capable of taking into consideration the structure of the documents, in a very similar manner to gr aph self organizing map technique, and this method is applied to a clustering tas k. This produced state of the art results on a benchmark document clusteri ng problem. The development of a novel approach based on Hidden Markov Mo dels for the encoding of sequences of graphs data structures. The approa ch allows the encoding of a time series of structured objects. Application of the GNN algorithm to a classification task involving a large set of documents represented as GoGs. vii A combined system containing both the PMGraphSOM, MLP and GN N applied to a Web spam detection problem. This produced state of the a rt r sults on a benchmark problem in Web spam detections. GNN is applied to encoding the temporal spatial graphs with an a im to produce ranking on the documents in the original CiteSeer database. Th temporal spatial graph is an instance of GoGs which encodes three levels of rel ationships: Time sequence: the status of the domain over time. Citation links: the referencing relationship between docu ments. Concept link: the contextual relationship among different concepts extracted from the documents. This is a very useful description of the documents in the stru ctured domain, hence can be trained by GNN 2 to infer the underlying ranking function and to predict the ranking of documents with yet unknown ranks. This methodolo gy is applied to the ranking of the documents in the original CiteSeer database. A there are no prior results in this area, it is not possible to assess if our resul ts are good or bad. In order to show that the proposed methodology is useful to th e modeling of temporal spatial problems involving graphs, we simulate a policemen database, in which we know the temporal spatial variations. We applied t he proposed methodology to this simulated dataset, and found that the results a re highly accurate. Thus, this shows that the proposed methodology can be applie d to model temporal spatial problems involving structures. This thesis also provides some potential directions for fut ure research: The PMGraphSOM is a state of the art unsupervised learnin g algorithm for structured domains. This can be recommended for problems which re quire classification of structured representation of objects, e.g. documents, images, videos. The graph of graphs representation is a general temporal sp atial representation of structured domains. This can encode inter linked document s, a set of images, or videos. viii The combined unsupervised and supervised approach can be re commended as a strategy for handling problems of deep learning, e.g. docu ments, handwritten character recognition, face recognition, human activity recog nition, etc. In our case, we recommend a particular combination, viz. the PMGraphSOM a nd GNN combination. This combination has proven effective in the case of We b spam detection problems. The GNN algorithm can be applied for supervised learning involving graph of graph situations. If the problem is relatively noise free, i n other words, if the noise contamination of the inputs is not high, this approach will y ield good results. This thesis also provide some potential directions for futu re research: Refine the PMGraphSOM for dealing with sparse graphs. Extend PMGraphSOM learning algorithm for clustering GoGs. Redevelop the code of GNN 2 based on a clear software design specification, and to provide an associated user manual. Apply the proposed model on benchmark problems which provid es ground truth information for the evaluation of impact sensitive rankingGoGs situations. Apply the proposed methodology to a wider range of problems, e.g. video information retrieval problems, image retrieval problems, chem ical informatics, etc. Develop different training algorithm for GNN e.g. map graphs to sequences, map graphs to graphs, etc.