Bio-ontologies and Linked Data have become integral part of biological and biomedical knowledge bases with over 500 of them and millions of triples. Such knowledge bases are primarily developed for information retrieval, query processing, data integration, standardization, and provision. Developing machine learning methods which can exploit the background knowledge in such resources for predictive analysis and novel discovery in the biomedical domain has become essential. In this dissertation, we present novel approaches which utilize the plethora of data sets made available as bio-ontologies and Linked Data in a single uni ed framework as knowledge graphs. We utilize representation learning with knowledge graphs and introduce generic models for addressing and tackling computational problems of major implications to human health, such as predicting disease-gene associations and drug repurposing. We also show that our methods can compensate for incomplete information in public databases and can smoothly facilitate integration with biomedical literature for similar prediction tasks. Furthermore, we demonstrate that our methods can learn and extract features that outperform relevant methods, which rely on manually crafted features and laborious features engineering and pre-processing. Finally, we present a systematic evaluation of knowledge graph representation learning methods and demonstrate their potential applications for data analytics in biomedicine.

[Formulae and special characters can only be approximated here. Please see the pdf version of the abstract for an accurate reproduction.] This thesis concerns the study of homogeneous factorisations of complete graphs with edge-transitive factors. A factorisation of a complete graph Kn is a partition of its edges into disjoint classes. Each class of edges in a factorisation of Kn corresponds to a spanning subgraph called a factor. If all the factors are isomorphic to one another, then a factorisation of Kn is called an isomorphic factorisation. A homogeneous factorisation of a complete graph is an isomorphic factorisation where there exists a group G which permutes the factors transitively, and a normal subgroup M of G such that each factor is M-vertex-transitive. If M also acts edge-transitively on each factor, then a homogeneous factorisation of Kn is called an edge-transitive homogeneous factorisation. The aim of this thesis is to study edge-transitive homogeneous factorisations of Kn. We achieve a nearly complete explicit classification except for the case where G is an affine 2-homogeneous group of the form ZR p x G0, where G0 is less than or equal to ΓL(1,p to the power of R). In this case, we obtain necessary and sufficient arithmetic conditions on certain parameters for such factorisations to exist, and give a generic construction that specifies the homogeneous factorisation completely, given that the conditions on the parameters hold. Moreover, we give two constructions of infinite families of examples where we specify the parameters explicitly. In the second infinite family, the arc-transitive factors are generalisations of certain arc-transitive, self-complementary graphs constructed by Peisert in 2001.

In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them. A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star. We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed. We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.

The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing

[pt] O problema de particionamento de grafos em cliques ocorre freqüentemente em diversas áreas tais como Ciências sociais, Ciências Econômicas, Biologia, Análise de Agrupamentos e em todas as áreas onde é necessário a classificação de elementos. Estuda-se aqui os principais algoritmos exatos e as principais heurísticas que constam na literatura. É feita uma análise do desempenho das heurísticas no pior caso e apresenta-se uma classe especial de problemas para os quais o seu desempenho é arbitrariamente ruim. Apresentam-se quatro novas heurísticas para o problema, duas delas baseadas nos métodos conhecidos por simulated anneling e por tabu search. Elas são comparadas entre si através da análise dos resultados de suas aplicações a problemas-teste, a problemas que ocorre na realidade e a classe de problemas especiais mencionada acima. / [en] The clique partitioning problem arise very often in many fields as Social Science, Economics, Biology, Cluster analysis and in all other fields that need a classification of elements. The main exact algorithms and heuristics that appear in the literature are studied. A especial class of instances of the clique partitioning problem for which the most comonly used heuristics perform arbitrarily bad is exhibited. Four new heuristics are presented and two of them are based on the known simulated anneling and tabu search methods. They are analised by their application to test-problems, real-life-problems and to the special class of instances mentioned above

Submitted by Luis Miguel Rojas Aguilera (rojas@icomp.ufam.edu.br) on 2018-09-10T13:04:22Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-09-10T18:13:42Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) / Rejected by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br), reason: O Campo "Agência de Fomento" deve ser preenchido com o nome (ou sigla) da Agência de Fomento. on 2018-09-10T18:15:16Z (GMT) / Submitted by Luis Miguel Rojas Aguilera (rojas@icomp.ufam.edu.br) on 2018-09-10T18:57:05Z No. of bitstreams: 2 DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-09-10T20:49:15Z (GMT) No. of bitstreams: 2 DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-09-11T14:07:43Z (GMT) No. of bitstreams: 2 DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-09-11T14:07:43Z (GMT). No. of bitstreams: 2 DissertacaoLuisRojasComFichaCatalograficaEFolhaAprovacao.pdf: 6768066 bytes, checksum: 5c26bd8a9fe369e787ba394d81fd07f3 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-03-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Code mutation and metamorphism have been successfully employed to create and proliferate new malware instances from existing malicious code. With such techniques, it is possible to modify a code’s structure without altering its original functions, so, new samples can be made that lack structural and behavioral patterns present in knowledge bases of malware identification systems, which hinders their detection. Previous research endeavors addressing metamorphic malware detection can be grouped into two categories: identification through code signature matching and detection based on models of classification. Matching code signatures presents lower false positive rates in comparison with models of classification, since such structures are resilient to the effects of metamorphism and allow better discrimination among instances, however, temporal complexity of matching algorithms prevents the application of such technique in real detection systems. On the other hand, detection based on classification models present less algorithmic complexity, however, a models’ generalization capacity is affected by the versatility of patterns that can be obtained by applying techniques of metamorphism. In order to overcome such limitations, this work presents methods for metamorphic malware identification through matching annotated data dependency graphs, extracted from known malwares and suspicious instances in the moment of analysis. To deal with comparison algorithms’ complexity, using these methods on real detection systems, the databases of graphs were indexed using machine learning algorithms, resulting in multiclass classification models that discriminated among malware families based on structural features of graphs. Experimental results, employing a prototype of the proposed methods from a database of 40,785 graphs extracted from 4,530 malware instances, presented detection times below 150 seconds for all instances, as well as higher average accuracy than 56 evaluated commercial malware detection systems. / A mutação de código e o metamorfismo têm sido empregados com sucesso para a criação e proliferação de novas instâncias de malware a partir de códigos maliciosos existentes. Com estas técnicas é possível modificar a estrutura de um código sem alterar as funcionalidades originais para obter novas instâncias que não se encaixam nos padrões estruturais e de comportamento presentes em bases de conhecimento dos sistemas de identificação de malware, dificultando assim a detecção. Pesquisas anteriores que abordam a detecção de malware metamórfico podem ser agrupadas em: identificação por meio do matching de assinaturas de código e detecção baseada em modelos de classificação. O matching de assinaturas de código tem apresentado taxas de falsos positivos inferiores às apresentadas pelos modelos de classificação, uma vez que estas estruturas são resilientes aos efeitos do metamorfismo e permitem melhor discriminação entre as instâncias. Entretanto a complexidade temporal dos algoritmos de comparação impedem a aplicação desta técnica em sistemas de detecção reais. Por outro lado, a detecção baseada em modelos de classificação apresenta menor complexidade algorítmica, porém a capacidade de generalização dos modelos se vê afetada pela versatilidade de padrões que podem ser obtidos por médio da aplicação de técnicas de metamorfismo. Para superar estas limitações, este trabalho apresenta uma metodologia para a identificação de malware metamórfico através da comparação de grafos de dependência de dados anotados extraídos de malwares conhecidos e de instâncias suspeitas no momento da análise. Para lidar com a complexidade dos algoritmos de comparação, permitindo assim a utilização da metodologia em sistemas de detecção reais, as bases de grafos são indexadas empregando algoritmos de aprendizagem de máquina, resultando em modelos de classificação multiclasse que discriminam entre famílias de malwares a partir das características estruturais dos grafos. Resultados experimentais, utilizando um protótipo da metodologia proposta sobre uma base composta por 40,785 grafos extraídos de 4,530 instâncias de malwares, mostraram tempos de detecção inferiores aos 150 segundos para processar todas as instâncias e de criação dos modelos inferiores aos 10 minutos, bem como acurácia média superior à maioria de 56 ferramentas comerciais de detecção de malware avaliadas.

In a digital world of Flickr, Picasa and Google Images, developing a semantic image represen-tation has become a vital problem. Image processing and computer vision researchers to date, have used several di erent representations for images. They vary from low level features such as SIFT, HOG, GIST etc. to high level concepts such as objects and people. When asked to describe an object or a scene, people usually resort to mid-level features such as size, appearance, feel, use, behaviour etc. Such descriptions are commonly referred to as the attributes of the object or scene. These human understandable, machine detectable attributes have recently become a popular feature category for image representation for various vision tasks. In addition to image and object characteristics, object interactions and back-ground/context information and the actions taking place in the scene form an important part of an image description. It is therefore, essential, to develop an image representation which can e ectively describe various image components and their interactions. Towards this end, we propose a novel image representation, termed Attribute-Graph. An Attribute-Graph is an undirected graph, incorporating both local and global image character-istics. The graph nodes characterise objects as well as the overall scene context using mid-level semantic attributes, while the edges capture the object topology and the actions being per-formed. We demonstrate the e ectiveness of Attribute-Graphs by applying them to the problem of image ranking. Since an image retrieval system should rank images in a way which is compatible with visual similarity as perceived by humans, it is intuitive that we work in a human understandable feature space. Most content based image retrieval algorithms treat images as a set of low level features or try to de ne them in terms of the associated text. Such a representation fails to capture the semantics of the image. This, more often than not, results in retrieved images which are semantically dissimilar to the query. Ranking using the proposed attribute-graph representation alleviates this problem. We benchmark the performance of our ranking algorithm on the rPascal and rImageNet datasets, which we have created in order to evaluate the ranking performance on complex queries containing multiple objects. Our experimental evaluation shows that modelling images as Attribute-Graphs results in improved ranking performance over existing techniques.

Masters of Science / Codes Related to and Derived from Hamming Graphs T.R Muthivhi M.Sc thesis, Department of Mathematics, University of Western Cape For integers n; k 1; and k n; the graph 􀀀k n has vertices the 2n vectors of Fn2 and adjacency de ned by two vectors being adjacent if they di er in k coordinate positions. In particular, 􀀀1 n is the classical n-cube, usually denoted by H1(n; 2): This study examines the codes (both binary and p-ary for p an odd prime) of the row span of adjacency and incidence matrices of these graphs. We rst examine codes of the adjacency matrices of the n-cube. These have been considered in [14]. We then consider codes generated by both incidence and adjacency matrices of the Hamming graphs H1(n; 3) [12]. We will also consider codes of the line graphs of the n-cube as in [13]. Further, the automorphism groups of the codes, designs and graphs will be examined, highlighting where there is an interplay. Where possible, suitable permutation decoding sets will be given.

A caracterização de redes e o estudo de sistemas, ambos utilizando grafos, é algo muito usado por várias áreas científicas. Uma das linhas deste estudo é denominada de grafos aleatórios, que por sua vez auxilia na criação de modelos para análise de redes reais. Consideramos um modelo de grafo aleatório não homogêneo criado por Kang, Pachón e Rodríguez (2016), cuja construção é feita a partir da realização do grafo binomial G(n; p). Para este modelo, estudamos argumentos e métodos usados para encontrar resultados sobre o limiar de conectividade, importante propriedade relacionada a existência assintótica de vértices e componentes isolados. Em seguida, constatamos algumas características positivas e negativas a respeito da utilização do grafo para modelar redes reais complexas, onde usamos de simulações computacionais e medidas topológicas. / The characterization of networks and the study of systems, both using graphs, is very used by several scientific areas. One of the lines of this study is called random graphs, which in turn assists in creating models for the analysis of real networks. We consider an inhomogeneous random graph model created by Kang, Pachón e Rodríguez (2016), where its construction is made from the realization of the binomial graph G(n; p). For this model, we studied the arguments and methods used to find results on the connectivity threshold, important property related to asymptotic existence of vertices and isolated components. Then we found some positive and negative characteristics about the use of the graph to model complex real networks, using computer simulations and topological measures.