Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Adicionalmente, algumas aplicações Morethan-Moore, tais como circuitos baseados em eletrônica impressa, também podem ser beneficiadas pela abordagem proposta. / This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special interest for these applications. Additionally, some More-than-Moore applications, such as printed electronics designs, can also take benefit from the proposed approach.

Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Essa tese introduz um conjunto de algoritmos baseados em grafos para o mapeamento eficiente de circuitos VLSI com células simples. Os algoritmos propostos se baseiam em minimizar de maneira eficiente o número de elementos lógicos usados na implementação do circuito. Posteriormente, uma quantidade significativa de esforço é aplicada na minimização do número de inversores entre esses elementos lógicos. Por fim, essa representação lógica é mapeada para circuitos compostos somente por células NAND e NOR de duas entradas, juntamente com inversores. Células XOR e XNOR de duas entradas também podem ser consideradas. Como nós também consideramos circuitos sequenciais, flips-flops também são levados em consideração. Com o grande esforço de minimização de elementos lógicos, o circuito gerado pode conter algumas células com um fanout impraticável para os nodos tecnológicos atuais. Para corrigir essas ocorrências, nós propomos um algoritmo de limitação de fanout que considera tanto a área sendo utilizada pelas células quanto a sua profundidade lógica. Os algoritmos propostos foram aplicados sobre um conjunto de circuitos de benchmark e os resultados obtidos demonstram a utilidade dos métodos. Adicionalmente, algumas aplicações Morethan-Moore, tais como circuitos baseados em eletrônica impressa, também podem ser beneficiadas pela abordagem proposta. / This thesis introduces a set of graph-based algorithms for efficiently mapping VLSI circuits using simple cells. The proposed algorithms are concerned to, first, effectively minimize the number of logic elements implementing the synthesized circuit. Then, we focus a significant effort on minimizing the number of inverters in between these logic elements. Finally, this logic representation is mapped into a circuit comprised of only two-input NANDs and NORS, along with the inverters. Two-input XORs and XNORs can also be optionally considered. As we also consider sequential circuits in this work, flip-flops are taken into account as well. Additionally, with high-effort optimization on the number of logic elements, the generated circuits may contain some cells with unfeasible fanout for current technology nodes. In order to fix these occurrences, we propose an area-oriented, level-aware algorithm for fanout limitation. The proposed algorithms were applied over a set of benchmark circuits and the obtained results have shown the usefulness of the method. We show that efficient implementations in terms of inverter count, transistor count, area, power and delay can be generated from circuits with a reduced number of both simple cells and inverters, combined with XOR/XNOR-based optimizations. The proposed buffering algorithm can handle all unfeasible fanout occurrences, while (i) optimizing the number of added inverters; and (ii) assigning cells to the inverter tree based on their level criticality. When comparing with academic and commercial approaches, we are able to simultaneously reduce the average number of inverters, transistors, area, power dissipation and delay up to 48%, 5%, 5%, 5%, and 53%, respectively. As the adoption of a limited set of simple standard cells have been showing benefits for a variety of modern VLSI circuits constraints, such as layout regularity, routability constraints, and/or ultra low power constraints, the proposed methods can be of special interest for these applications. Additionally, some More-than-Moore applications, such as printed electronics designs, can also take benefit from the proposed approach.

Uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos e métodos de geração de grafos foram propostos pela comunidade científica nos últimos anos. Apesar de seu aparente sucesso empírico, a área de aprendizado semissupervisionado carece de um estudo empírico detalhado que avalie o impacto da geração de grafos na classificação semissupervisionada. Neste trabalho, é provido tal estudo empírico. Para tanto, combinam-se uma variedade de métodos de geração de grafos com uma variedade de algoritmos de aprendizado semissupervisionado baseado em grafos para compará-los empiricamente em seis bases de dados amplamente usadas na literatura de aprendizado semissupervisionado. Os algoritmos são avaliados em tarefas de classificação de dígitos, caracteres, texto, imagens e de distribuições gaussianas. A avaliação experimental proposta neste trabalho é subdividida em quatro partes: (1) análise de melhor caso; (2) avaliação da estabilidade dos classificadores semissupervisionados; (3) avaliação do impacto da geração de grafos na classificação semissupervisionada; (4) avaliação da influência dos parâmetros de regularização no desempenho de classificação dos classificadores semissupervisionados. Na análise de melhor caso, avaliam-se as melhores taxas de erro de cada algoritmo semissupervisionado combinado com os métodos de geração de grafos usando uma variedade de valores para o parâmetro de esparsificação, o qual está relacionado ao número de vizinhos de cada exemplo de treinamento. Na avaliação da estabilidade dos classificadores, avalia-se a estabilidade dos classificadores semissupervisionados combinados com os métodos de geração de grafos usando uma variedade de valores para o parâmetro de esparsificação. Para tanto, fixam-se os valores dos parâmetros de regularização (quando existirem) que geraram os melhores resultados na análise de melhor caso. Na avaliação do impacto da geração de grafos, avaliam-se os métodos de geração de grafos combinados com os algoritmos de aprendizado semissupervisionado usando uma variedade de valores para o parâmetro de esparsificação. Assim como na avaliação da estabilidade dos classificadores, para esta avaliação, fixam-se os valores dos parâmetros de regularização (quando existirem) que geraram os melhores resultados na análise de melhor caso. Na avaliação da influência dos parâmetros de regularização na classificação semissupervisionada, avaliam-se as superfícies de erro geradas pelos classificadores semissupervisionados em cada grafo e cada base de dados. Para tanto, fixam-se os grafos que geraram os melhores resultados na análise de melhor caso e variam-se os valores dos parâmetros de regularização. O intuito destes experimentos é avaliar o balanceamento entre desempenho de classificação e estabilidade dos algoritmos de aprendizado semissupervisionado baseado em grafos numa variedade de métodos de geração de grafos e valores de parâmetros (de esparsificação e de regularização, se houver). A partir dos resultados obtidos, pode-se concluir que o grafo k- vizinhos mais próximos mútuo (mutKNN) pode ser a melhor opção dentre os métodos de geração de grafos de adjacência, enquanto que o kernel RBF pode ser a melhor opção dentre os métodos de geração de matrizes ponderadas. Em adição, o grafo mutKNN tende a gerar superfícies de erro que são mais suaves que aquelas geradas pelos outros métodos de geração de grafos de adjacência. Entretanto, o grafo mutKNN é instável para valores relativamente pequenos de k. Os resultados obtidos neste trabalho indicam que o desempenho de classificação dos algoritmos semissupervisionados baseados em grafos é fortemente influenciado pela configuração de parâmetros. Poucos padrões evidentes foram encontrados para auxiliar o processo de seleção de parâmetros. As consequências dessa instabilidade são discutidas neste trabalho em termos de pesquisa e aplicações práticas / A variety of graph-based semi-supervised learning algorithms have been proposed by the research community in the last few years. Despite its apparent empirical success, the field of semi-supervised learning lacks a detailed empirical study that evaluates the influence of graph construction on semisupervised learning. In this work we provide such an empirical study. For such purpose, we combine a variety of graph construction methods with a variety of graph-based semi-supervised learning algorithms in order to empirically compare them in six benchmark data sets widely used in the semi-supervised learning literature. The algorithms are evaluated in tasks about digit, character, text, and image classification as well as classification of gaussian distributions. The experimental evaluation proposed in this work is subdivided into four parts: (1) best case analysis; (2) evaluation of classifiers stability; (3) evaluation of the influence of graph construction on semi-supervised learning; (4) evaluation of the influence of regularization parameters on the classification performance of semi-supervised learning algorithms. In the best case analysis, we evaluate the lowest error rates of each semi-supervised learning algorithm combined with the graph construction methods using a variety of sparsification parameter values. Such parameter is associated with the number of neighbors of each training example. In the evaluation of classifiers stability, we evaluate the stability of the semi-supervised learning algorithms combined with the graph construction methods using a variety of sparsification parameter values. For such purpose, we fixed the regularization parameter values (if any) with the values that achieved the best result in the best case analysis. In the evaluation of the influence of graph construction, we evaluate the graph construction methods combined with the semi-supervised learning algorithms using a variety of sparsification parameter values. In this analysis, as occurred in the evaluation of classifiers stability, we fixed the regularization parameter values (if any) with the values that achieved the best result in the best case analysis. In the evaluation of the influence of regularization parameters on the classification performance of semi-supervised learning algorithms, we evaluate the error surfaces generated by the semi-supervised classifiers in each graph and data set. For such purpose, we fixed the graphs that achieved the best results in the best case analysis and varied the regularization parameters values. The intention of our experiments is evaluating the trade-off between classification performance and stability of the graphbased semi-supervised learning algorithms in a variety of graph construction methods as well as parameter values (sparsification and regularization, if applicable). From the obtained results, we conclude that the mutual k-nearest neighbors (mutKNN) graph may be the best choice for adjacency graph construction while the RBF kernel may be the best choice for weighted matrix generation. In addition, mutKNN tends to generate error surfaces that are smoother than those generated by other adjacency graph construction methods. However, mutKNN is unstable for relatively small values of k. Our results indicate that the classification performance of the graph-based semi-supervised learning algorithms are heavily influenced by parameter setting. We found just a few evident patterns that could help parameter selection. The consequences of such instability are discussed in this work in research and practice

This thesis focuses on how unlabeled data can improve supervised learning classi-fiers in all contexts, for both scarce to abundant label situations. This is meant toaddress the limitations within supervised learning with regards to label availability.Extending the training set with unlabeled data can overcome issues such as selec-tion bias, noise and insufficient data. Based on the overall data distribution andthe initial set of labels, semi-supervised methods provide labels for additional datapoints. The semi-supervised approaches considered in this thesis belong to one ofthe following categories: transductive SVMs, Cluster-then-Label and graph-basedtechniques. Further, we evaluate the behavior of: Logistic regression, Single layerperceptron, SVM and Decision trees. By learning on the extended training set,supervised classifiers are able to generalize better. Based on the results, this the-sis recommends data-processing and algorithmic solutions appropriate to real-worldsituations.

This thesis deals with robot path planning by means of graph-based algorithms. The theoretical part contains basic approaches to robot path planning, and pay closer look at various methods of graph-based algorithms. In the second part of this thesis a simulation environment for robot navigation was created in C#. And in this environment chosen methods of graph-based algorithms have been implemented. This thesis was written within the research project MSM 0021630529: Intelligent systems in automation.

Research and experimentation in various scientific fields are based on the knowledge and ideas from scholarly literature. The advancement of research and development has, thus, strengthened the importance of literary analysis and understanding. However, in recent years, researchers have been facing massive scholarly documents published at an exponentially increasing rate. Analyzing this vast number of publications is far beyond the capability of individual researchers. This dissertation is motivated by the need for large scale analyses of the exploding number of scholarly literature for scientific knowledge discovery. In the first part of this dissertation, the interdependencies between scholarly literature are studied. First, I develop Delve – a data-driven search engine supported by our designed semi-supervised edge classification method. This system enables users to search and analyze the relationship between datasets and scholarly literature. Based on the Delve system, I propose to study information extraction as a node classification problem in attributed networks. Specifically, if we can learn the research topics of documents (nodes in a network), we can aggregate documents by topics and retrieve information specific to each topic (e.g., top-k popular datasets). Node classification in attributed networks has several challenges: a limited number of labeled nodes, effective fusion of topological structure and node/edge attributes, and the co-existence of multiple labels for one node. Existing node classification approaches can only address or partially address a few of these challenges. This dissertation addresses these challenges by proposing semi-supervised multi-class/multi-label node classification models to integrate node/edge attributes and topological relationships. The second part of this dissertation examines the problem of analyzing the interdependencies between terms in scholarly literature. I present two algorithms for the automatic hypothesis generation (HG) problem, which refers to the discovery of meaningful implicit connections between scientific terms, including but not limited to diseases, drugs, and genes extracted from databases of biomedical publications. The automatic hypothesis generation problem is modeled as a future connectivity prediction in a dynamic attributed graph. The key is to capture the temporal evolution of node-pair (term-pair) relations. Experiment results and case study analyses highlight the effectiveness of the proposed algorithms compared to the baselines’ extension.

Planning is essential for an action-oriented, goal-driven software agent. In order to achieve a specific goal, an agent must first generate a plan. However, as the poet Robert Burns once noted, the best laid plans can often go awry. Each step of the plan is subject to the possibility of failure, a truth particularly relevant in the realworld or a realistic simulated environment. External influences not originally considered can often cause sudden, unanticipated consequences during the execution of the plan. When this happens, an intelligent software agent needs to answer the following important questions: What are the consequences of this event on its plan? How will the plan be affected? Can the plan be adjusted to accommodate the unanticipated effects? The research described in this thesis develops a model whereby intelligent agents can automatically determine consequences of unplanned events. Such a model provides agents with the ability to detect if and how events will affect the plan. This allows agents to subsequently modify the plan to mitigate unfavorable consequences or take advantage of favorable consequences.

Expander codes are sparse graph-based codes with good decoding algorithms. We present a linear-time decoding algorithm for (C,D, alpha, gamma) expander codes based on graphs with any expansion factor given that the minimum distances of the inner codes are bounded below. We also design graph-based codes with hierarchical locality. Such codes provide tiered recovery, depending on the number of erasures. A small number of erasures may be handled by only accessing a few other symbols, allowing for small locality, while larger number may involve a greater number of symbols. This provides an alternative to requiring disjoint repair groups. We also consider availability in this context, relying on the interplay between inner codes and the Tanner graph. We define new families of algebraic geometry codes for the purpose of code-based cryptography. In particular, we consider twisted Hermitian codes, twisted codes from a quotient of the Hermitian curve; and twisted norm-trace codes. These codes have Schur squares with large dimensions and hence could be considered as potential replacements for Goppa codes in the McEliece cryptosytem. However, we study the code-based cryptosystem based on twisted Hermitian codes and lay foundations for a potential attack on such a cryptosystem. / Doctor of Philosophy / Coding theory finds applications in various places such as data transmission, data storage, and even post-quantum cryptography. The goal of data transmission is to ensure fast and efficient information transfer. It is ideal to correct maximum number of errors introduced during transmission by noisy channels. We provide a new construction of expander codes (graph-based codes) and provide a linear-time decoding algorithm which corrects a constant-fraction of errors for these codes given any expansion factor. In this context, channel noise causes distortion of symbols, so that received symbols may be different than those originally sent. We are also interested in codes for erasure recovery, meaning those which restore missing symbols. A recent technique to recover the sent messages is by accesing a small subset of this received information, called locality. We analyze the locality properties of Tanner codes equipped with specific inner code. Code-based cryptography is a leading candidate in the post-quantum setting, meaning it is believed to be secure against quantum algorithms. The McEliece cryptosystem in which the underlying code is a Goppa code is popularly studied and is a top candidate in the NIST competition. However, the adoption of this system is not immediate due to its large key sizes. Code-based cryptosystems based on codes other than Goppa codes might provide a solution. We provide constructions of a new family of codes, called twisted algebraic geomtery codes which may provide alternatives of Goppa codes in the McEliece cryptosystem.

Aujourd’hui, la biologie des systèmes est confrontée aux défis de l’analyse de l’énorme quantité de données biologiques et à la taille des réseaux métaboliques pour des analyses à grande échelle. Bien que plusieurs méthodes aient été développées au cours des dernières années pour résoudre ce problème, ce sujet reste un domaine de recherche en plein essor. Cette thèse se concentre sur l’analyse des propriétés structurales, le calcul des modes élémentaires de flux et la détermination d’ensembles de coupe minimales du graphe formé par ces réseaux. Dans notre recherche, nous avons collaboré avec des biologistes pour reconstruire un réseau métabolique de taille moyenne du métabolisme cellulaire de la plante, environ 90 noeuds et 150 arêtes. En premier lieu, nous avons fait l’analyse des propriétés structurelles du réseau dans le but de trouver son organisation. Les réactions points centraux de ce réseau trouvés dans cette étape n’expliquent pas clairement la structure du réseau. Les mesures classiques de propriétés des graphes ne donnent pas plus d’informations utiles. En deuxième lieu, nous avons calculé les modes élémentaires de flux qui permettent de trouver les chemins uniques et minimaux dans un réseau métabolique, cette méthode donne un grand nombre de solutions, autour des centaines de milliers de voies métaboliques possibles qu’il est difficile de gérer manuellement. Enfin, les coupes minimales de graphe, ont été utilisés pour énumérer tous les ensembles minimaux et uniques des réactions qui stoppent les voies possibles trouvées à la précédente étape. Le nombre de coupes minimales a une tendance à ne pas croître exponentiellement avec la taille du réseau a contrario des modes élémentaires de flux. Nous avons combiné l’analyse de ces modes et les ensembles de coupe pour améliorer l’analyse du réseau. Les résultats montrent l’importance d’ensembles de coupe pour la recherche de la structure hiérarchique du réseau à travers modes de flux élémentaires. Nous avons étudié un cas particulier : qu’arrive-t-il si on stoppe l’entrée de glucose ? En utilisant les coupes minimales de taille deux, huit réactions ont toujours été trouvés dans les modes élémentaires qui permettent la production des différents sucres et métabolites d’intérêt au cas où le glucose est arrêté. Ces huit réactions jouent le rôle du squelette / coeur de notre réseau. En élargissant notre analyse aux coupes minimales de taille 3, nous avons identifié cinq réactions comme point de branchement entre différent modes. Ces 13 réactions créent une classification hiérarchique des modes de flux élémentaires fixés et nous ont permis de réduire considérablement le nombre de cas à étudier (approximativement divisé par 10) dans l’analyse des chemins réalisables dans le réseau métabolique. La combinaison de ces deux outils nous a permis d’approcher plus efficacement l’étude de la production des différents métabolites d’intérêt par la cellule de plante hétérotrophique. / Nowadays, systems biology are facing the challenges of analysing the huge amount of biological data and large-scale metabolic networks. Although several methods have been developed in recent years to solve this problem, it is existing hardness in studying these data and interpreting the obtained results comprehensively. This thesis focuses on analysis of structural properties, computation of elementary flux modes and determination of minimal cut sets of the heterotrophic plant cellmetabolic network. In our research, we have collaborated with biologists to reconstructa mid-size metabolic network of this heterotrophic plant cell. This network contains about 90 nodes and 150 edges. First step, we have done the analysis of structural properties by using graph theory measures, with the aim of finding its owned organisation. The central points orhub reactions found in this step do not explain clearly the network structure. The small-world or scale-free attributes have been investigated, but they do not give more useful information. In the second step, one of the promising analysis methods, named elementary flux modes, givesa large number of solutions, around hundreds of thousands of feasible metabolic pathways that is difficult to handle them manually. In the third step, minimal cut sets computation, a dual approach of elementary flux modes, has been used to enumerate all minimal and unique sets of reactions stopping the feasible pathways found in the previous step. The number of minimal cut sets has a decreasing trend in large-scale networks in the case of growing the network size. We have also combined elementary flux modes analysis and minimal cut sets computation to find the relationship among the two sets of results. The findings reveal the importance of minimal cut sets in use of seeking the hierarchical structure of this network through elementary flux modes. We have set up the circumstance that what will be happened if glucose entry is absent. Bi analysis of small minimal cut sets we have been able to found set of reactions which has to be present to produce the different sugars or metabolites of interest in absence of glucose entry. Minimal cut sets of size 2 have been used to identify 8 reactions which play the role of the skeleton/core of our network. In addition to these first results, by using minimal cut sets of size 3, we have pointed out five reactions as the starting point of creating a new branch in creationof feasible pathways. These 13 reactions create a hierarchical classification of elementary flux modes set. It helps us understanding more clearly the production of metabolites of interest inside the plant cell metabolism.

Curiosity of human nature drives us to explore the origins of what makes each of us different. From ancient legends and mythology, Mendel's law, Punnett square to modern genetic research, we carry on this old but eternal question. Thanks to technological revolution, today's scientists try to answer this question using easily measurable gene expression and other profiling data. However, the exploration can easily get lost in the data of growing volume, dimension, noise and complexity. This dissertation is aimed at developing new machine learning methods that take data from different classes as input, augment them with knowledge of feature relationships, and train classification models that serve two goals: 1) class prediction for previously unseen samples; 2) knowledge discovery of the underlying causes of class differences. Application of our methods in genetic studies can help scientist take advantage of existing biological networks, generate diagnosis with higher accuracy, and discover the driver networks behind the differences. We proposed three new graph-based regularization algorithms. Graph Connectivity Constrained AdaBoost algorithm combines a connectivity module, a deletion function, and a model retraining procedure with the AdaBoost classifier. Graph-regularized Linear Programming Support Vector Machine integrates penalty term based on submodular graph cut function into linear classifier's objective function. Proximal Graph LogisticBoost adds lasso and graph-based penalties into logistic risk function of an ensemble classifier. Results of tests of our models on simulated biological datasets show that the proposed methods are able to produce accurate, sparse classifiers, and can help discover true genetic differences between phenotypes.