Dissertations / Theses: 'Learning on graphs'

1

Vitale, F. "FAST LEARNING ON GRAPHS." Doctoral thesis, Università degli Studi di Milano, 2011. http://hdl.handle.net/2434/155500.

Full text

Abstract:

We carry out a systematic study of classification problems on networked data, presenting novel techniques with good performance both in theory and in practice. We assess the power of node classification based on class-linkage information only. In particular, we propose four new algorithms that exploit the homiphilic bias (linked entities tend to belong to the same class) in different ways. The set of the algorithms we present covers diverse practical needs: some of them operate in an active transductive setting and others in an on-line transductive setting. A third group works within an explorative protocol, in which the vertices of an unknown graph are progressively revealed to the learner in an on-line fashion. Within the mistake bound learning model, for each of our algorithms we provide a rigorous theoretical analysis, together with an interpretation of the obtained performance bounds. We also design adversarial strategies achieving matching lower bounds. In particular, we prove optimality for all input graphs and for all fixed regularity values of suitable labeling complexity measures. We also analyze the computational requirements of our methods, showing that our algorithms can to handle very large data sets. In the case of the on-line protocol, for which we exhibit an optimal algorithm with constant amortized time per prediction, we validate our theoretical results carrying out experiments on real-world datasets.

APA, Harvard, Vancouver, ISO, and other styles

2

Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Simonovsky, Martin. "Deep learning on attributed graphs." Thesis, Paris Est, 2018. http://www.theses.fr/2018PESC1133/document.

Full text

Abstract:

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules
Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

APA, Harvard, Vancouver, ISO, and other styles

4

Rosar, Kós Lassance Carlos Eduardo. "Graphs for deep learning representations." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2020. http://www.theses.fr/2020IMTA0204.

Full text

Abstract:

Ces dernières années, les méthodes d'apprentissage profond ont atteint l'état de l'art dans une vaste gamme de tâches d'apprentissage automatique, y compris la classification d'images et la traduction automatique. Ces architectures sont assemblées pour résoudre des tâches d'apprentissage automatique de bout en bout. Afin d'atteindre des performances de haut niveau, ces architectures nécessitent souvent d'un très grand nombre de paramètres. Les conséquences indésirables sont multiples, et pour y remédier, il est souhaitable de pouvoir comprendre ce qui se passe à l'intérieur des architectures d'apprentissage profond. Il est difficile de le faire en raison de: i) la dimension élevée des représentations ; et ii) la stochasticité du processus de formation. Dans cette thèse, nous étudions ces architectures en introduisant un formalisme à base de graphes, s'appuyant notamment sur les récents progrès du traitement de signaux sur graphe (TSG). À savoir, nous utilisons des graphes pour représenter les espaces latents des réseaux neuronaux profonds. Nous montrons que ce formalisme des graphes nous permet de répondre à diverses questions, notamment: i) mesurer des capacités de généralisation ;ii) réduire la quantité de des choix arbitraires dans la conception du processus d'apprentissage ; iii)améliorer la robustesse aux petites perturbations ajoutées sur les entrées ; et iv) réduire la complexité des calculs
In recent years, Deep Learning methods have achieved state of the art performance in a vast range of machine learning tasks, including image classification and multilingual automatic text translation. These architectures are trained to solve machine learning tasks in an end-to-end fashion. In order to reach top-tier performance, these architectures often require a very large number of trainable parameters. There are multiple undesirable consequences, and in order to tackle these issues, it is desired to be able to open the black boxes of deep learning architectures. Problematically, doing so is difficult due to the high dimensionality of representations and the stochasticity of the training process. In this thesis, we investigate these architectures by introducing a graph formalism based on the recent advances in Graph Signal Processing (GSP). Namely, we use graphs to represent the latent spaces of deep neural networks. We showcase that this graph formalism allows us to answer various questions including: ensuring generalization abilities, reducing the amount of arbitrary choices in the design of the learning process, improving robustness to small perturbations added to the inputs, and reducing computational complexity

APA, Harvard, Vancouver, ISO, and other styles

5

Ghiasnezhad, Omran Pouya. "Rule Learning in Knowledge Graphs." Thesis, Griffith University, 2018. http://hdl.handle.net/10072/382680.

Full text

Abstract:

With recent advancements in knowledge extraction and knowledge management systems, an enormous number of knowledge bases have been constructed, such as YAGO, and Wikidata. These automatically built knowledge bases which contain millions of entities and their relations have been stored in graph-based schemas, and thus are usually referred to as knowledge graphs (KGs). Since KGs have been built based on the limited available data, they are far from complete. However, learning frequent patterns in the form of logical rules from these incomplete KGs has two main advantages. First, by applying the learned rules, we can infer new facts, so we could complete the KGs. Second, the rules are stand-alone knowledge which express valuable insight about the data. However, learning rules from KGs in relation to the real-world scenarios imposes several challenges. First, due to the vast size of real-world KGs, developing a rule learning method is challenging. In fact, existing methods are not scalable for learning rst order rules, while various optimisation strategies are used such as sampling and language bias (i.e., restrictions on the form of rules). Second, applying the learned rules to the vast KG and inferring new facts is another di cult issue. Learned rules usually contain a lot of noises and adding new facts can cause inconsistency of KGs. Third, it is useful but non-trivial to extend an existing method of rule learning to the case of stream KGs. Forth, in many data repositories, the facts are augmented with time stamps. In this case, we face a stream of data (KGs). Considering time as a new dimension of data imposes some challenges to the rule learning process. It would be useful to construct a time-sensitive model from the stream of data and apply the obtained model to stream KGs. Last, the density of information in a KG is varied. Although the size of a KG is vast, it contains a limited amount of information for some relations. Consequently, that part of KG is sparse. Learning a set of accurate and informative rules regarding the sparse part of a KG is challenging due to the lack of su cient training data. In this thesis, we investigate these research problems and present our methods for rule learning in various scenarios. We have rst developed a new approach, named Rule Learning via Learning Representation (RLvLR), to learning rules from KGs by using the technique of embedding in representation learning together with a new sampling method. RLvLR learns rst-order rules from vast KGs by exploring the embedding space. It can handle some large KGs that cannot be handled by existing rule learners e ciently, due to a novel sampling method. To improve the performance of RLvLR for handling sparse data, we propose a transfer learning method, Transfer Rule Learner (TRL), for rule learning. Based on a similarity characterised by the embedding representation, our method is able to select most relevant KGs and rules to transfer from a pool of KGs whose rules have been obtained. We have also adapted RLvLR to handle stream KGs instead of static KGs. Then a system called StreamLearner is developed for learning rules from stream KGs. These proposed methods can only learn so-called closed path rules, which is a proper subset of Horn rules. Thus, we have also developed a transfer rule learner (T-LPAD) that learns the structure of logic program with annotated disjunctions. T-LPAD is created by employing transfer learning to explore the space of rules' structures more e ciently. Various experiments have been conducted to test and validate the proposed methods. Our experimental results show that our methods outperform state-of-the-art methods in many ways.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
School of Info & Comm Tech
Science, Environment, Engineering and Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

6

Fan, Shuangfei. "Deep Representation Learning on Labeled Graphs." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/96596.

Full text

Abstract:

We introduce recurrent collective classification (RCC), a variant of ICA analogous to recurrent neural network prediction. RCC accommodates any differentiable local classifier and relational feature functions. We provide gradient-based strategies for optimizing over model parameters to more directly minimize the loss function. In our experiments, this direct loss minimization translates to improved accuracy and robustness on real network data. We demonstrate the robustness of RCC in settings where local classification is very noisy, settings that are particularly challenging for ICA. As a new way to train generative models, generative adversarial networks (GANs) have achieved considerable success in image generation, and this framework has also recently been applied to data with graph structures. We identify the drawbacks of existing deep frameworks for generating graphs, and we propose labeled-graph generative adversarial networks (LGGAN) to train deep generative models for graph-structured data with node labels. We test the approach on various types of graph datasets, such as collections of citation networks and protein graphs. Experiment results show that our model can generate diverse labeled graphs that match the structural characteristics of the training data and outperforms all baselines in terms of quality, generality, and scalability. To further evaluate the quality of the generated graphs, we apply it to a downstream task for graph classification, and the results show that LGGAN can better capture the important aspects of the graph structure.
Doctor of Philosophy
Graphs are one of the most important and powerful data structures for conveying the complex and correlated information among data points. In this research, we aim to provide more robust and accurate models for some graph specific tasks, such as collective classification and graph generation, by designing deep learning models to learn better task-specific representations for graphs. First, we studied the collective classification problem in graphs and proposed recurrent collective classification, a variant of the iterative classification algorithm that is more robust to situations where predictions are noisy or inaccurate. Then we studied the problem of graph generation using deep generative models. We first proposed a deep generative model using the GAN framework that generates labeled graphs. Then in order to support more applications and also get more control over the generated graphs, we extended the problem of graph generation to conditional graph generation which can then be applied to various applications for modeling graph evolution and transformation.

APA, Harvard, Vancouver, ISO, and other styles

7

Rommedahl, David, and Martin Lindström. "Learning Sparse Graphs for Data Prediction." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-295623.

Full text

Abstract:

Graph structures can often be used to describecomplex data sets. In many applications, the graph structureis not known but must be inferred from data. Furthermore, realworld data is often naturally described by sparse graphs. Inthis project, we have aimed at recreating the results describedin previous work, namely to learn a graph that can be usedfor prediction using an ℓ1-penalised LASSO approach. We alsopropose different methods for learning and evaluating the graph. We have evaluated the methods on synthetic data and real-worldSwedish temperature data. The results show that we are unableto recreate the results of the previous research team, but wemanage to learn sparse graphs that could be used for prediction. Further work is needed to verify our results.
Grafstrukturer kan ofta användas för att beskriva komplex data. I många tillämpningar är grafstrukturen inte känd, utan måste läras från data. Vidare beskrivs verklig data ofta naturligt av glesa grafer. I detta projekt har vi försökt återskapa resultaten från ett tidigare forskningsarbete, nämligen att lära en graf som kan användas för prediktion med en ℓ1pennaliserad LASSO-metod. Vi föreslår även andra metoder för inlärning och utvärdering av grafen. Vi har testat metoderna på syntetisk data och verklig temperaturdata från Sverige. Resultaten visar att vi inte kan återskapa de tidigare forskarnas resultat, men vi lyckas lära in glesa grafer som kan användas för prediktion. Ytterligare arbete krävs för att verifiera våra resultat.
Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

APA, Harvard, Vancouver, ISO, and other styles

8

Xu, Keyulu. "Graph structures, random walks, and all that : learning graphs with jumping knowledge networks." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/121660.

Full text

Abstract:

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 51-54).
Graph representation learning aims to extract high-level features from the graph structures and node features, in order to make predictions about the nodes and the graphs. Applications include predicting chemical properties of drugs, community detection in social networks, and modeling interactions in physical systems. Recent deep learning approaches for graph representation learning, namely Graph Neural Networks (GNNs), follow a neighborhood aggregation procedure, where the representation vector of a node is computed by recursively aggregating and transforming feature vectors of its neighboring nodes. We analyze some important properties of these models, and propose a strategy to overcome the limitations. In particular, the range of neighboring nodes that a node's representation draws from strongly depends on the graph structure, analogous to the spread of a random walk. To adapt to local neighborhood properties and tasks, we explore an architecture - jumping knowledge (JK) networks that flexibly leverages, for each node, different neighborhood ranges to enable better structure-aware representation. In a number of experiments on social, bioinformatics and citation networks, we demonstrate that our model achieves state-of-the-art performance. Furthermore, combining the JK framework with models like Graph Convolutional Networks, GraphSAGE and Graph Attention Networks consistently improves those models' performance.
by Keyulu Xu.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science

APA, Harvard, Vancouver, ISO, and other styles

9

Freeman, Guy. "Learning and predicting with chain event graphs." Thesis, University of Warwick, 2010. http://wrap.warwick.ac.uk/4529/.

Full text

Abstract:

Graphical models provide a very promising avenue for making sense of large, complex datasets. The most popular graphical models in use at the moment are Bayesian networks (BNs). This thesis shows, however, they are not always ideal factorisations of a system. Instead, I advocate for the use of a relatively new graphical model, the chain event graph (CEG), that is based on event trees. Event trees directly represent graphically the event space of a system. Chain event graphs reduce their potentially huge dimensionality by taking into account identical probability distributions on some of the event tree’s subtrees, with the added benefits of showing the conditional independence relationships of the system — one of the advantages of the Bayesian network representation that event trees lack — and implementation of causal hypotheses that is just as easy, and arguably more natural, than is the case with Bayesian networks, with a larger domain of implementation using purely graphical means. The trade-off for this greater expressive power, however, is that model specification and selection are much more difficult to undertake with the larger set of possible models for a given set of variables. My thesis is the first exposition of how to learn CEGs. I demonstrate that not only is conjugate (and hence quick) learning of CEGs possible, but I characterise priors that imply conjugate updating based on very reasonable assumptions that also have direct Bayesian network analogues. By re-casting CEGs as partition models, I show how established partition learning algorithms can be adapted for the task of learning CEGs. I then develop a robust yet flexible prediction machine based on CEGs for any discrete multivariate time series — the dynamic CEG model — which combines the power of CEGs, multi-process and steady modelling, lattice theory and Occam’s razor. This is also an exact method that produces reliable predictions without requiring much a priori modelling. I then demonstrate how easily causal analysis can be implemented with this model class that can express a wide variety of causal hypotheses. I end with an application of these techniques to real educational data, drawing inferences that would not have been possible simply using BNs.

APA, Harvard, Vancouver, ISO, and other styles

10

Pasteris, S. U. "Efficient algorithms for online learning over graphs." Thesis, University College London (University of London), 2016. http://discovery.ucl.ac.uk/1516210/.

Full text

Abstract:

In this thesis we consider the problem of online learning with labelled graphs, in particular designing algorithms that can perform this problem quickly and with low memory requirements. We consider the tasks of Classification (in which we are asked to predict the labels of vertices) and Similarity Prediction (in which we are asked to predict whether two given vertices have the same label). The first half of the thesis considers non- probabilistic online learning, where there is no probability distribution on the labelling and we bound the number of mistakes of an algorithm by a function of the labelling's complexity (i.e. its "naturalness"), often the cut- size. The second half of the thesis considers probabilistic machine learning in which we have a known probability distribution on the labelling. Before considering probabilistic online learning we first analyse the junction tree algorithm, on which we base our online algorithms, and design a new ver- sion of it, superior to the otherwise current state of the art. Explicitly, the novel contributions of this thesis are as follows: • A new algorithm for online prediction of the labelling of a graph which has better performance than previous algorithms on certain graph and labelling families. • Two algorithms for online similarity prediction on a graph (a novel problem solved in this thesis). One performs very well whilst the other not so well but which runs exponentially faster. • A new (better than before, in terms of time and space complexity) state of the art junction tree algorithm, as well as an application of it to the problem of online learning in an Ising model. • An algorithm that, in linear time, finds the optimal junction tree for online inference in tree-structured Ising models, the resulting online junction tree algorithm being far superior to the previous state of the art. All claims in this thesis are supported by mathematical proofs.

APA, Harvard, Vancouver, ISO, and other styles

11

Sonntag, Dag. "Chain Graphs : Interpretations, Expressiveness and Learning Algorithms." Doctoral thesis, Linköpings universitet, Databas och informationsteknik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-125921.

Full text

Abstract:

Probabilistic graphical models are currently one of the most commonly used architectures for modelling and reasoning with uncertainty. The most widely used subclass of these models is directed acyclic graphs, also known as Bayesian networks, which are used in a wide range of applications both in research and industry. Directed acyclic graphs do, however, have a major limitation, which is that only asymmetric relationships, namely cause and effect relationships, can be modelled between their variables. A class of probabilistic graphical models that tries to address this shortcoming is chain graphs, which include two types of edges in the models representing both symmetric and asymmetric relationships between the variables. This allows for a wider range of independence models to be modelled and depending on how the second edge is interpreted, we also have different so-called chain graph interpretations. Although chain graphs were first introduced in the late eighties, most research on probabilistic graphical models naturally started in the least complex subclasses, such as directed acyclic graphs and undirected graphs. The field of chain graphs has therefore been relatively dormant. However, due to the maturity of the research field of probabilistic graphical models and the rise of more data-driven approaches to system modelling, chain graphs have recently received renewed interest in research. In this thesis we provide an introduction to chain graphs where we incorporate the progress made in the field. More specifically, we study the three chain graph interpretations that exist in research in terms of their separation criteria, their possible parametrizations and the intuition behind their edges. In addition to this we also compare the expressivity of the interpretations in terms of representable independence models as well as propose new structure learning algorithms to learn chain graph models from data.

APA, Harvard, Vancouver, ISO, and other styles

12

Eid, Abdelrahman. "Stochastic simulations for graphs and machine learning." Thesis, Lille 1, 2020. http://www.theses.fr/2020LIL1I018.

Full text

Abstract:

Bien qu’il ne soit pas pratique d’étudier la population dans de nombreux domaines et applications, l’échantillonnage est une méthode nécessaire permettant d’inférer l’information.Cette thèse est consacrée au développement des algorithmes d’échantillonnage probabiliste pour déduire l’ensemble de la population lorsqu’elle est trop grande ou impossible à obtenir.Les techniques Monte Carlo par chaîne de markov (MCMC) sont l’un des outils les plus importants pour l’échantillonnage à partir de distributions de probabilités surtout lorsque ces distributions ont des constantes de normalisation difficiles à évaluer.Le travail de cette thèse s’intéresse principalement aux techniques d’échantillonnage pour les graphes. Deux méthodes pour échantillonner des sous-arbres uniformes à partir de graphes en utilisant les algorithmes de Metropolis-Hastings sont présentées dans le chapitre 2. Les méthodes proposées visent à échantillonner les arbres selon une distribution à partir d’un graphe où les sommets sont marqués. L’efficacité de ces méthodes est prouvée mathématiquement. De plus, des études de simulation ont été menées et ont confirmé les résultats théoriques de convergence vers la distribution d’équilibre.En continuant à travailler sur l’échantillonnage des graphes, une méthode est présentée au chapitre 3 pour échantillonner des ensembles de sommets similaires dans un graphe arbitraire non orienté en utilisant les propriétés des processus des points permanents PPP. Notre algorithme d’échantillonnage des ensembles de k sommets est conçu pour surmonter le problème de la complexité de calcul lors du calcul du permanent par échantillonnage d’une distribution conjointe dont la distribution marginale est un kPPP.Enfin, dans le chapitre 4, nous utilisons les définitions des méthodes MCMC et de la vitesse de convergence pour estimer la bande passante du noyau utilisée pour la classification dans l’apprentissage machine supervisé. Une méthode simple et rapide appelée KBER est présentée pour estimer la bande passante du noyau de la fonction de base radiale RBF en utilisant la courbure moyenne de Ricci de graphes
While it is impractical to study the population in many domains and applications, sampling is a necessary method allows to infer information. This thesis is dedicated to develop probability sampling algorithms to infer the whole population when it is too large or impossible to be obtained. Markov chain Monte Carlo (MCMC) techniques are one of the most important tools for sampling from probability distributions especially when these distributions haveintractable normalization constants.The work of this thesis is mainly interested in graph sampling techniques. Two methods in chapter 2 are presented to sample uniform subtrees from graphs using Metropolis-Hastings algorithms. The proposed methods aim to sample trees according to a distribution from a graph where the vertices are labelled. The efficiency of these methods is proved mathematically. Additionally, simulation studies were conducted and confirmed the theoretical convergence results to the equilibrium distribution.Continuing to the work on graph sampling, a method is presented in chapter 3 to sample sets of similar vertices in an arbitrary undirected graph using the properties of the Permanental Point processes PPP. Our algorithm to sample sets of k vertices is designed to overcome the problem of computational complexity when computing the permanent by sampling a joint distribution whose marginal distribution is a kPPP.Finally in chapter 4, we use the definitions of the MCMC methods and convergence speed to estimate the kernel bandwidth used for classification in supervised Machine learning. A simple and fast method called KBER is presented to estimate the bandwidth of the Radial basis function RBF kernel using the average Ricci curvature of graphs

APA, Harvard, Vancouver, ISO, and other styles

13

Li, Qilin. "Affinity Learning on Graphs with Diffusion Processes." Thesis, Curtin University, 2020. http://hdl.handle.net/20.500.11937/80408.

Full text

Abstract:

In the thesis, we propose machine learning algorithms utilising diffusion processes to learn the pairwise affinity between data samples. Diffusion processes propagates neighbour information on a node-edge graph, resulting in context-aware affinities that is smooth to the data manifold structure. Similar ideas are also embedded in graph convolutional networks for representation learning. These proposed algorithms improve performance for various machine learning tasks, such as data cluster analysis, dimensionality reduction, and semisupervised classification.

APA, Harvard, Vancouver, ISO, and other styles

14

Nguyen, Thi Kim Hue. "Structure learning of graphs for count data." Doctoral thesis, Università degli studi di Padova, 2018. http://hdl.handle.net/11577/3421952.

Full text

Abstract:

Biological processes underlying the basic functions of a cell involve complex interactions between genes. From a technical point of view, these interactions can be represented through a graph where genes and their connections are, respectively, nodes and edges. The main research objective of this thesis is to develop a statistical framework for modelling the interactions between genes when the activity of genes is measured on a discrete scale. We propose several algorithms. First, we deﬁne an algorithm for learning the structure of a undirected graph, proving its theoretical consistence in the limit of inﬁnite observations. Next, we tackle structure learning of directed acyclic graphs (DAGs), adopting a model speciﬁcation proved to guarantee identiﬁability of the models. Then, we develop new algorithms for both guided and unguided structure learning of DAGs. All proposed algorithms show promising results when applied to simulated data as well as to real data.
I processi biologici che regolano le funzioni di base di una cellula sono caratterizzati da numerose interazioni tra geni. Da un punto di vista matematico, è possibile rappresentare queste interazioni attraverso graﬁ in cui i nodi e gli archi rappresentano, rispettivamente, i geni coinvolti e le loro interazioni. L’obiettivo principale di questa tesi è quello di sviluppare un approccio statistico alla modellazione delle interazioni tra geni quando questi sono misurati su scala discreta. Vengono a tal ﬁne proposti vari algoritmi. La prima proposta è relativa ad un algoritmo disegnato per stimare la struttura di un grafo non orientato, per il quale si fornisce la dimostrazione di convergenza al crescere delle osservazioni. Altre tre proposte coinvolgono la deﬁnizione di algoritmi supervisionati per la stima della struttura di graﬁ direzionali aciclici, basati su una speciﬁcazione del modello statistico che ne garantisce l’identiﬁcabilità. Sempre con riferimento ai graﬁ direzionali aciclici, inﬁne, si propone un algoritmo non supervisionato. Tutti gli algoritmi proposti mostrano risultati promettenti in termini di ricostruzione delle vere strutture quando applicati a dati simulati e dati reali.

APA, Harvard, Vancouver, ISO, and other styles

15

Santacruz, Muñoz José Luis. "Error-tolerant Graph Matching on Huge Graphs and Learning Strategies on the Edit Costs." Doctoral thesis, Universitat Rovira i Virgili, 2019. http://hdl.handle.net/10803/668356.

Full text

Abstract:

Els grafs són estructures de dades abstractes que s'utilitzen per a modelar problemes reals amb dues entitats bàsiques: nodes i arestes. Cada node o vèrtex representa un punt d'interès rellevant d'un problema, i cada aresta representa la relació entre aquests vèrtexs. Els nodes i les arestes podrien incorporar atributs per augmentar la precisió del problema modelat. Degut a aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per computador, biomèdics, anàlisi de xarxes, etc. La Distància d'edició de grafs (GED) s'ha convertit en una eina important en el reconeixement de patrons estructurals, ja que permet mesurar la dissimilitud dels grafs. A la primera part d'aquesta tesi es presenta un mètode per generar una parella grafs juntament amb la seva correspondència en un cost computacional lineal. A continuació, se centra en com mesurar la dissimilitud entre dos grafs enormes (més de 10.000 nodes), utilitzant un nou algoritme de aparellament de grafs anomenat Belief Propagation. Té un cost computacional O(d^3.5N). Aquesta tesi també presenta un marc general per aprendre els costos d'edició implicats en els càlculs de la GED automàticament. Després, concretem aquest marc en dos models diferents basats en xarxes neuronals i funcions de densitat de probabilitat. S'ha realitzat una validació pràctica exhaustiva en 14 bases de dades públiques. Aquesta validació mostra que la precisió és major amb els costos d'edició apresos, que amb alguns costos impostos manualment o altres costos apresos automàticament per mètodes anteriors. Finalment proposem una aplicació de l'algoritme Belief propagation utilitzat en la simulació de la mecànica muscular.
Los grafos son estructuras de datos abstractos que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada arista representa la relación entre estos vértices. Los nodos y las aristas podrían incorporar atributos para aumentar la precisión del problema modelado. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como la visión por computador, biomédicos, análisis de redes, etc. La Distancia de edición de grafos (GED) se ha convertido en una herramienta importante en el reconocimiento de patrones estructurales, ya que permite medir la disimilitud de los grafos. En la primera parte de esta tesis se presenta un método para generar una pareja grafos junto con su correspondencia en un coste computacional lineal. A continuación, se centra en cómo medir la disimilitud entre dos grafos enormes (más de 10.000 nodos), utilizando un nuevo algoritmo de emparejamiento de grafos llamado Belief Propagation. Tiene un coste computacional O(d^3.5n). Esta tesis también presenta un marco general para aprender los costos de edición implicados en los cálculos de GED automáticamente. Luego, concretamos este marco en dos modelos diferentes basados en redes neuronales y funciones de densidad de probabilidad. Se ha realizado una validación práctica exhaustiva en 14 bases de datos públicas. Esta validación muestra que la precisión es mayor con los costos de edición aprendidos, que con algunos costos impuestos manualmente u otros costos aprendidos automáticamente por métodos anteriores. Finalmente proponemos una aplicación del algoritmo Belief propagation utilizado en la simulación de la mecánica muscular.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the modeled problem, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, bio-medics, network analysis, etc. Graph Edit Distance (GED) has become an important tool in structural pattern recognition since it allows to measure the dissimilarity of attributed graphs. The first part presents a method is presented to generate graphs together with an upper and lower bound distance and a correspondence in a linear computational cost. Through this method, the behaviour of the known -or the new- sub-optimal Error-Tolerant graph matching algorithm can be tested against a lower and an upper bound GED on large graphs, even though we do not have the true distance. Next, the present is focused on how to measure the dissimilarity between two huge graphs (more than 10.000 nodes), using a new Error-Tolerant graph matching algorithm called Belief Propagation algorithm. It has a O(d^3.5n) computational cost.This thesis also presents a general framework to learn the edit costs involved in the GED calculations automatically. Then, we concretise this framework in two different models based on neural networks and probability density functions. An exhaustive practical validation on 14 public databases has been performed. This validation shows that the accuracy is higher with the learned edit costs, than with some manually imposed costs or other costs automatically learned by previous methods. Finally we propose an application of the Belief propagation algorithm applied to muscle mechanics.

APA, Harvard, Vancouver, ISO, and other styles

16

Ricatte, Thomas. "Hypernode graphs for learning from binary relations between sets of objects." Thesis, Lille 3, 2015. http://www.theses.fr/2015LIL30001/document.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Amundsson, Karl. "Approximate Bayesian Learning of Partition Directed Acyclic Graphs." Thesis, KTH, Matematisk statistik, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-192853.

Full text

Abstract:

Partition directed acyclic graphs (PDAGs) is a model whereby the conditional probability tables (CPTs) are partitioned into parts with equal probability. In this way, the number of parameters that need to be learned can be significantly reduced so that some problems become more computationally feasible. PDAGs have been shown to be connected to labeled DAGs (LDAGs) and the connection is summarized here. Furthermore, a clustering algorithm is compared to an exact algorithm for determining a PDAG. To evaluate the algorithm, we use it on simulated data where the expected result is known.
Partitionerade riktade acykliska grafer (engelska: PDAGs) är en modell där tabeller över betingade sannolikheter partitioneras i delar med lika sannolikhet. Detta gör att antalet parametrar som ska bestämmas kan reduceras, vilket i sin tur gör problemet beräkningsmässigt enklare. Ett känt samband mellan PDAGs och betecknade riktade acykliska grafer (engelska: LDAGs) sammanfattas här. Sedan jämförs en klustringsalgoritm med en algoritm som exakt bestämmer en PDAG. Klustringsalgoritmens pålitlighet kollas genom att använda den på simulerad data där det förväntade resultatet är känt.

APA, Harvard, Vancouver, ISO, and other styles

18

Ma, Zongjie. "Searching on Massive Graphs and Regularizing Deep Learning." Thesis, Griffith University, 2018. http://hdl.handle.net/10072/385875.

Full text

Abstract:

We have designed di erent heuristics for both searching on Massive graphs and regularizing Deep Neural Networks in this work. Both the problem of nding a minimum vertex cover (MinVC) and the maximum edge weight clique (MEWC) in a graph are prominent NP-hard problems of great importance in both theory and application. During recent decades, there has been much interest in nding optimal or near-optimal solutions to these two problems. Many existing heuristic algorithms for MinVC are based on local search strategies. An algorithm called FastVC takes a rst step towards solving the MinVC problem for large real-world graphs. However, FastVC may be trapped at local minima during the local search stage due to the lack of suitable diversi cation mechanisms. Besides, since the traditional best-picking heuristic was believed to be of high complexity, FastVC replaces it with an approximate best-picking strategy. However, best-picking has been proved to be robust for a wide range of problems, so abandoning it may be a great sacri ce. Therefore, we rstly design a diversi cation heuristic to help FastVC escape from local minima, and the proposed solver is named WalkVC. Secondly, we develop a local search MinVC solver, named NoiseVC, which utilizes best-picking (low complexity) with noise to remove vertices during the local search stage in massive graphs. On the other hand, most of existing heuristics for the MEWC problem focus on academic benchmarks with relatively small size. However, very little attention was paid to solving the MEWC problem in large sparse graphs. In this thesis, we exploit the so-called deterministic tournament selection (DTS) heuristic for selecting edges to improve the local search based MEWC algorithms. Deep Neural Networks (DNN), have an extremely large number of parameters comparing with traditional machine earning methods, su er from the the problem of over tting. Dropout [Hinton et al., 2012, Srivastava et al., 2014] has been proposed to address this problem. Dropout is an useful technique for regularizing and preventing the co-adaptation of neurons in DNN. It randomly drops units with a probability p during the training stage of DNN to avoid over tting. The working mechanism of dropout can be interpreted as approximately and exponentially combining many di erent neural network architectures e ciently, leading to a powerful ensemble. We propose a novel diversi cation strategy for dropout named Tabu Dropout, which aims at generating more di erent neural network architectures in fewer numbers of iterations. Besides, a recent work named Curriculum Dropout achieves the state-of-the-art performance among the dropout variants by using a scheduled p instead of a xed one. It gradually increases the dropping probability from 0 to 1 􀀀 p according to a time scheduling from curriculum learning. The primary intuition is that dropout seems unnecessary at the beginning of training and Curriculum Dropout starts training the whole neural networks without dropping, which is called \starting easy". In this thesis, we design a new scheduled dropout strategy using \starting small" instead of \starting easy", which gradually decreases the dropping probability from 1 to p. We call this strategy Annealed Curriculum Dropout. Experiments conducted on related public standard datasets show that our proposed heuristics for both searching on massive graphs and regularizing deep learning have achieved better performance than the comparison methods.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Inst Integrated&IntelligentSys
Science, Environment, Engineering and Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

19

Chandra, Nagasai. "Node Classification on Relational Graphs using Deep-RGCNs." DigitalCommons@CalPoly, 2021. https://digitalcommons.calpoly.edu/theses/2265.

Full text

Abstract:

Knowledge Graphs are fascinating concepts in machine learning as they can hold usefully structured information in the form of entities and their relations. Despite the valuable applications of such graphs, most knowledge bases remain incomplete. This missing information harms downstream applications such as information retrieval and opens a window for research in statistical relational learning tasks such as node classification and link prediction. This work proposes a deep learning framework based on existing relational convolutional (R-GCN) layers to learn on highly multi-relational data characteristic of realistic knowledge graphs for node property classification tasks. We propose a deep and improved variant, Deep-RGCNs, with dense and residual skip connections between layers. These skip connections are known to be very successful with popular deep CNN-architectures such as ResNet and DenseNet. In our experiments, we investigate and compare the performance of Deep-RGCN with different baselines on multi-relational graph benchmark datasets, AIFB and MUTAG, and show how the deep architecture boosts the performance in the task of node property classification. We also study the training performance of Deep-RGCNs (with N layers) and discuss the gradient vanishing and over-smoothing problems common to deeper GCN architectures.

APA, Harvard, Vancouver, ISO, and other styles

20

Chamberlain, Benjamin Paul. "Practical challenges of learning and representation for large graphs." Thesis, Imperial College London, 2018. http://hdl.handle.net/10044/1/64783.

Full text

Abstract:

An ever-increasing amount of the humanity's information is being stored in large graphs. The world wide web, digital social networks, e-commerce platforms and chat networks now contain digital traces of the majority of living humans. Many of the most valuable companies ever created are dedicated to organising, managing and extracting useful information from large digital graphs. Machine learning has been shown to be an important tool for automating this task. Discovering scalable machine learning systems, to extract useful information from graphs, is a problem of great practical significance. Interesting graphs, such as the web graph, often contain more information than can be stored on a single computer, and so working with the raw data presents considerable challenges. Graph representations are often employed that encapsulate key properties of the underlying data and enable certain tasks to be performed efficiently, at the expense of others. Representations are chosen to balance time complexity, space complexity and predictive performance on a downstream task, such as labelling vertices with attributes. We are concerned with problems of extracting and inferring information from large graphs and applying the results in deployed commercial systems. The research revolves around two large-scale machine learning projects (1) A system for searching and organising data from social media graphs (2) A system to profile customers through their interactions with products on an e-commerce platform. We use representations of graphs to allow algorithms to be run faster, cheaper and more accurately. Doing so allows us to satisfy systems constraints that could not be achieved by operating directly on the raw data. We demonstrate how careful choices of representation can be used to improve machine learning performance on several real-world tasks. We do this under challenging industrial constraints such as real-time serving, runtime costs or maintainability.

APA, Harvard, Vancouver, ISO, and other styles

21

Urry, Matthew. "Learning curves for Gaussian process regression on random graphs." Thesis, King's College London (University of London), 2013. https://kclpure.kcl.ac.uk/portal/en/theses/learning-curves-for-gaussian-process-regression-on-random-graphs(c1f5f395-0426-436c-989c-d0ade913423e).html.

Full text

Abstract:

Gaussian processes are a non-parametric method that can be used to learn both regression and classification rules from examples for arbitrary input spaces using the ’kernel trick’. They are well understood for inputs from Euclidean spaces, however, much less research has focused on other spaces. In this thesis I aim to at least partially resolve this. In particular I focus on the case where inputs are defined on the vertices of a graph and the task is to learn a function defined on the vertices from noisy examples, i.e. a regression problem. A challenging problem in the area of non-parametric learning is to predict the general-isation error as a function of the number of examples or learning curve. I show that, unlike in the Euclidean case where predictions are either quantitatively accurate for a few specific cases or only qualitatively accurate for a broader range of situations, I am able to derive accurate learning curves for Gaussian processes on graphs for a wide range of input spaces given by ensembles of random graphs. I focus on the random walk kernel but my results generalise to any kernel that can be written as a truncated sum of powers of the normalised graph Laplacian. I begin first with a discussion of the properties of the random walk kernel, which can be viewed as an approximation of the ubiquitous squared exponential kernel in continuous spaces. I show that compared to the squared exponential kernel, the random walk kernel has some surprising properties which includes a non-trivial limiting form for some types of graphs. After investigating the limiting form of the kernel I then study its use as a prior. I propose a solution to this in the form of a local normalisation, where the prior scale at each vertex is normalised locally as desired. To drive home the point about kernel normalisation I then examine the differences between the two kernels when they are used as a Gaussian process prior over functions defined on the vertices of a graph. I show using numerical simulations that the locally normalised kernel leads to a probabilistically more plausible Gaussian process prior. After investigating the properties of the random walk kernel I then discuss the learning curves of a Gaussian process with a random walk kernel for both kernel normalisations in a matched scenario (where student and teacher are both Gaussian processes with matching hyperparameters). I show that by using the cavity method I can derive accu-rate predictions along the whole length of the learning curve that dramatically improves upon previously derived approximations for continuous spaces suitably extended to the discrete graph case. The derivation of the learning curve for the locally normalised kernel required an addi-tional approximation in the resulting cavity equations. I subsequently, therefore, investi-gate this approximation in more detail using the replica method. I show that the locally normalised kernel leads to a highly non-trivial replica calculation, that eventually shows that the approximation used in the cavity analysis amounts to ignoring some consistency requirements between incoming cavity distributions. I focus in particular on a teacher distribution that is given by a Gaussian process with a random walk kernel but different hyperparameters. I show that in this case, by applying the cavity method, I am able once more to calculate accurate predictions of the learning curve. The resulting equations resemble the matched case over an inflated number of variables. To finish this thesis I examine the learning curves for varying degrees of model mismatch.

APA, Harvard, Vancouver, ISO, and other styles

22

Araya, Valdivia Ernesto. "Kernel spectral learning and inference in random geometric graphs." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM020.

Full text

Abstract:

Cette thèse comporte deux objectifs. Un premier objectif concerne l’étude des propriétés de concentration des matrices à noyau, qui sont fondamentales dans l’ensemble des méthodes à noyau. Le deuxième objectif repose quant à lui sur l’étude des problèmes d’inférence statistique dans le modèle des graphes aléatoires géométriques. Ces deux objectifs sont liés entre eux par le formalisme du graphon, qui permet représenter un graphe par un noyau. Nous rappelons les rudiments du modèle du graphon dans le premier chapitre. Le chapitre 2 présente des bornes précises pour les valeurs propres individuelles d’une matrice à noyau, où notre principale contribution est d’obtenir des inégalités à l’échelle de la valeur propre en considération. Ceci donne des vitesses de convergence qui sont meilleures que la vitesse paramétrique et, en occasions, exponentielles. Jusqu’ici cela n’avait été établi qu’avec des hypothèses contraignantes dans le contexte des graphes. Nous spécialisons les résultats au cas de noyaux de produit scalaire, en soulignant sa relation avec le modèle des graphes géométriques. Le chapitre 3 étudie le problème d’estimation des distances latentes pour le modèle des graphes aléatoires géométriques dans la sphère Euclidienne. Nous proposons un algorithme spectral efficace qui utilise la matrice d’adjacence pour construire un estimateur de la matrice des distances latentes, et des garanties théoriques pour l’erreur d’estimation, ainsi que la vitesse de convergence, sont montrées. Le chapitre 4 étend les méthodes développées dans le chapitre précédent au cas des graphes aléatoires géométriques dans la boule Euclidienne, un modèle qui, en dépit des similarités formelles avec le cas sphérique, est plus flexible en termes de modélisation. En particulier, nous montrons que pour certains choix des paramètres le profil des dégrées est distribué selon une loi de puissance, ce qui a été vérifié empiriquement dans plusieurs réseaux réels. Tous les résultats théoriques des deux derniers chapitres sont confirmés par des expériences numériques
This thesis has two main objectives. The first is to investigate the concentration properties of random kernel matrices, which are central in the study of kernel methods. The second objective is to study statistical inference problems on random geometric graphs. Both objectives are connected by the graphon formalism, which allows to represent a graph by a kernel function. We briefly recall the basics of the graphon model in the first chapter. In chapter two, we present a set of accurate concentration inequalities for individual eigenvalues of the kernel matrix, where our main contribution is to obtain inequalities that scale with the eigenvalue in consideration, implying convergence rates that are faster than parametric and often exponential, which hitherto has only been establish under assumptions which are too restrictive for graph applications. We specialized our results to the case of dot products kernels, highlighting its relation with the random geometric graph model. In chapter three, we study the problem of latent distances estimation on random geometric graphs on the Euclidean sphere. We propose an efficient spectral algorithm that use the adjacency matrix to construct an estimator for the latent distances, and prove finite sample guaranties for the estimation error, establishing its convergence rate. In chapter four, we extend the method developed in the previous chapter to the case of random geometric graphs on the Euclidean ball, a model that despite its formal similarities with the spherical case it is more flexible for modelling purposes. In particular, we prove that for certain parameter choices its degree profile is power law distributed, which has been observed in many real life networks. All the theoretical findings of the last two chapters are verified and complemented by numerical experiments

APA, Harvard, Vancouver, ISO, and other styles

23

García, Durán Alberto. "Learning representations in multi-relational graphs : algorithms and applications." Thesis, Compiègne, 2016. http://www.theses.fr/2016COMP2271/document.

Full text

Abstract:

Internet offre une énorme quantité d’informations à portée de main et dans une telle variété de sujets, que tout le monde est en mesure d’accéder à une énorme variété de connaissances. Une telle grande quantité d’information pourrait apporter un saut en avant dans de nombreux domaines (moteurs de recherche, réponses aux questions, tâches NLP liées) si elle est bien utilisée. De cette façon, un enjeu crucial de la communauté d’intelligence artificielle a été de recueillir, d’organiser et de faire un usage intelligent de cette quantité croissante de connaissances disponibles. Heureusement, depuis un certain temps déjà des efforts importants ont été faits dans la collecte et l’organisation des connaissances, et beaucoup d’informations structurées peuvent être trouvées dans des dépôts appelés Bases des Connaissances (BCs). Freebase, Entity Graph Facebook ou Knowledge Graph de Google sont de bons exemples de BCs. Un grand problème des BCs c’est qu’ils sont loin d’êtres complets. Par exemple, dans Freebase seulement environ 30% des gens ont des informations sur leur nationalité. Cette thèse présente plusieurs méthodes pour ajouter de nouveaux liens entre les entités existantes de la BC basée sur l’apprentissage des représentations qui optimisent une fonction d’énergie définie. Ces modèles peuvent également être utilisés pour attribuer des probabilités à triples extraites du Web. On propose également une nouvelle application pour faire usage de cette information structurée pour générer des informations non structurées (spécifiquement des questions en langage naturel). On pense par rapport à ce problème comme un modèle de traduction automatique, où on n’a pas de langage correct comme entrée, mais un langage structuré. Nous adaptons le RNN codeur-décodeur à ces paramètres pour rendre possible cette traduction
Internet provides a huge amount of information at hand in such a variety of topics, that now everyone is able to access to any kind of knowledge. Such a big quantity of information could bring a leap forward in many areas if used properly. This way, a crucial challenge of the Artificial Intelligence community has been to gather, organize and make intelligent use of this growing amount of available knowledge. Fortunately, important efforts have been made in gathering and organizing knowledge for some time now, and a lot of structured information can be found in repositories called Knowledge Bases (KBs). A main issue with KBs is that they are far from being complete. This thesis proposes several methods to add new links between the existing entities of the KB based on the learning of representations that optimize some defined energy function. We also propose a novel application to make use of this structured information to generate questions in natural language

APA, Harvard, Vancouver, ISO, and other styles

24

Lê-Huu, Dien Khuê. "Nonconvex Alternating Direction Optimization for Graphs : Inference and Learning." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLC005/document.

Full text

Abstract:

Cette thèse présente nos contributions àl’inférence et l’apprentissage des modèles graphiquesen vision artificielle. Tout d’abord, nous proposons unenouvelle classe d’algorithmes de décomposition pour résoudrele problème d’appariement de graphes et d’hypergraphes,s’appuyant sur l’algorithme des directionsalternées (ADMM) non convexe. Ces algorithmes sontefficaces en terme de calcul et sont hautement parallélisables.En outre, ils sont également très générauxet peuvent être appliqués à des fonctionnelles d’énergiearbitraires ainsi qu’à des contraintes de correspondancearbitraires. Les expériences montrent qu’ils surpassentles méthodes de pointe existantes sur des benchmarkspopulaires. Ensuite, nous proposons une relaxationcontinue non convexe pour le problème d’estimationdu maximum a posteriori (MAP) dans les champsaléatoires de Markov (MRFs). Nous démontrons quecette relaxation est serrée, c’est-à-dire qu’elle est équivalenteau problème original. Cela nous permet d’appliquerdes méthodes d’optimisation continue pour résoudrele problème initial discret sans perte de précisionaprès arrondissement. Nous étudions deux méthodes degradient populaires, et proposons en outre une solutionplus efficace utilisant l’ADMM non convexe. Les expériencessur plusieurs problèmes réels démontrent quenotre algorithme prend l’avantage sur ceux de pointe,dans différentes configurations. Finalement, nous proposonsune méthode d’apprentissage des paramètres deces modèles graphiques avec des données d’entraînement,basée sur l’ADMM non convexe. Cette méthodeconsiste à visualiser les itérations de l’ADMM commeune séquence d’opérations différenciables, ce qui permetde calculer efficacement le gradient de la perted’apprentissage par rapport aux paramètres du modèle.L’apprentissage peut alors utiliser une descente de gradientstochastique. Nous obtenons donc un frameworkunifié pour l’inférence et l’apprentissage avec l’ADMMnon-convexe. Grâce à sa flexibilité, ce framework permetégalement d’entraîner conjointement de-bout-en-boutun modèle graphique avec un autre modèle, telqu’un réseau de neurones, combinant ainsi les avantagesdes deux. Nous présentons des expériences sur un jeude données de segmentation sémantique populaire, démontrantl’efficacité de notre méthode
This thesis presents our contributions toinference and learning of graph-based models in computervision. First, we propose a novel class of decompositionalgorithms for solving graph and hypergraphmatching based on the nonconvex alternating directionmethod of multipliers (ADMM). These algorithms arecomputationally efficient and highly parallelizable. Furthermore,they are also very general and can be appliedto arbitrary energy functions as well as arbitraryassignment constraints. Experiments show that theyoutperform existing state-of-the-art methods on popularbenchmarks. Second, we propose a nonconvex continuousrelaxation of maximum a posteriori (MAP) inferencein discrete Markov random fields (MRFs). Weshow that this relaxation is tight for arbitrary MRFs.This allows us to apply continuous optimization techniquesto solve the original discrete problem withoutloss in accuracy after rounding. We study two populargradient-based methods, and further propose a more effectivesolution using nonconvex ADMM. Experimentson different real-world problems demonstrate that theproposed ADMM compares favorably with state-of-theartalgorithms in different settings. Finally, we proposea method for learning the parameters of these graphbasedmodels from training data, based on nonconvexADMM. This method consists of viewing ADMM iterationsas a sequence of differentiable operations, whichallows efficient computation of the gradient of the trainingloss with respect to the model parameters, enablingefficient training using stochastic gradient descent. Atthe end we obtain a unified framework for inference andlearning with nonconvex ADMM. Thanks to its flexibility,this framework also allows training jointly endto-end a graph-based model with another model suchas a neural network, thus combining the strengths ofboth. We present experiments on a popular semanticsegmentation dataset, demonstrating the effectivenessof our method

APA, Harvard, Vancouver, ISO, and other styles

25

Zappella, G. "LEARNING ON GRAPHS: ALGORITHMS FOR CLASSIFICATION AND SEQUENTIAL DECISIONS." Doctoral thesis, Università degli Studi di Milano, 2014. http://hdl.handle.net/2434/234167.

Full text

Abstract:

In recent years, networked data have become widespread due to the increasing importance of social networks and other web-related applications. This growing interest is driving researchers to design new algorithms for solving important problems that involve networked data. In this thesis we present a few practical yet principled algorithms for learning and sequential decision-making on graphs. Classification of networked data is an important problem that has recently received a great deal of attention from the machine learning community. This is due to its many important practical applications: computer vision, bioinformatics, spam detection and text categorization, just to cite a few of the more conspicuous examples. We focus our attention on the task called ``node classification'', often studied in the semi-supervised (transductive) setting. We present two algorithms, motivated by different theoretical frameworks. The first algorithm is studied in the well-known online adversarial setting, within which it enjoys an optimal mistake bound (up to logarithmic factors). The second algorithm is based on a game-theoretic approach, where each node of the network is maximizing its own payoff. The setting corresponds to a Graph Transduction Game in which the graph is a tree. For this special case, we show that the Nash Equilibrium of the game can be reached in linear time. We complement our theoretical findings with an extensive set of experiments using datasets from many different domains. In the second part of the thesis, we present a rapidly emerging theme in the analysis of networked data: signed networks, graphs whose edges carry a label encoding the positive or negative nature of the relationship between the connected nodes. For example, social networks and e-commerce offer several examples of signed relationships: Slashdot users can tag other users as friends or foes, Epinions users can rate each other positively or negatively, Ebay users develop trust and distrust towards sellers in the network. More generally, two individuals that are related because they rate similar products in a recommendation website may agree or disagree in their ratings. Many heuristics for link classification in social networks are based on a form of social balance summarized by the motto “the enemy of my enemy is my friend”. This is equivalent to saying that the signs on the edges of a social graph tend to be consistent with some two-clustering structure of the nodes, where edges connecting nodes from the same cluster are positive and edges connecting nodes from different clusters are negative. We present algorithms for the batch transductive active learning setting, where the topology of the graph is known in advance and our algorithms can ask for the label of some specific edges during the training phase (before starting with the predictions). These algorithms can achieve different tradeoffs between the number of mistakes during the test phase and the number of labels required during the training phase. We also presented an experimental comparison against some state-of-the-art spectral heuristics presented in a previous work, where we show that the simplest or our algorithms is already competitive with the best of these heuristics. In the last chapter we present another way to exploit relational information for sequential predictions: the networks of bandits. Contextual bandits adequately formalize the exploration-exploitation trade-offs arising in several industrially relevant applications, such online advertisement and recommendation systems. Many practical applications have a strong social component whose integration in the bandit algorithm could lead to a significant performance improvement: for example, since often friends have similar taste, we may want to serve contents to a group of users by taking advantage of an underlying network of social relationships among them. We introduce a novel algorithmic approach to a particular networked bandit problem. More specifically, we run a bandit algorithm on each network node (e.g., user), allowing it to ``share'' feedback signals with the other nodes by employing the multi-task kernel. We derive the regret analysis of this algorithm and, finally, we report on the results of an experimental comparison between our approach and the state of the art techniques, on both artificial and real-world social networks.

APA, Harvard, Vancouver, ISO, and other styles

26

Lee, John Boaz T. "Deep Learning on Graph-structured Data." Digital WPI, 2019. https://digitalcommons.wpi.edu/etd-dissertations/570.

Full text

Abstract:

In recent years, deep learning has made a significant impact in various fields – helping to push the state-of-the-art forward in many application domains. Convolutional Neural Networks (CNN) have been applied successfully to tasks such as visual object detection, image super-resolution, and video action recognition while Long Short-term Memory (LSTM) and Transformer networks have been used to solve a variety of challenging tasks in natural language processing. However, these popular deep learning architectures (i.e., CNNs, LSTMs, and Transformers) can only handle data that can be represented as grids or sequences. Due to this limitation, many existing deep learning approaches do not generalize to problem domains where the data is represented as graphs – social networks in social network analysis or molecular graphs in chemoinformatics, for instance. The goal of this thesis is to help bridge the gap by studying deep learning solutions that can handle graph data naturally. In particular, we explore deep learning-based approaches in the following areas. 1. Graph Attention. In the real-world, graphs can be both large – with many complex patterns – and noisy which can pose a problem for effective graph mining. An effective way to deal with this issue is to use an attention-based deep learning model. An attention mechanism allows the model to focus on task-relevant parts of the graph which helps the model make better decisions. We introduce a model for graph classification which uses an attention-guided walk to bias exploration towards more task-relevant parts of the graph. For the task of node classification, we study a different model – one with an attention mechanism which allows each node to select the most task-relevant neighborhood to integrate information from. 2. Graph Representation Learning. Graph representation learning seeks to learn a mapping that embeds nodes, and even entire graphs, as points in a low-dimensional continuous space. The function is optimized such that the geometric distance between objects in the embedding space reflect some sort of similarity based on the structure of the original graph(s). We study the problem of learning time-respecting embeddings for nodes in a dynamic network. 3. Brain Network Discovery. One of the fundamental tasks in functional brain analysis is the task of brain network discovery. The brain is a complex structure which is made up of various brain regions, many of which interact with each other. The objective of brain network discovery is two-fold. First, we wish to partition voxels – from a functional Magnetic Resonance Imaging scan – into functionally and spatially cohesive regions (i.e., nodes). Second, we want to identify the relationships (i.e., edges) between the discovered regions. We introduce a deep learning model which learns to construct a group-cohesive partition of voxels from the scans of multiple individuals in the same group. We then introduce a second model which can recover a hierarchical set of brain regions, allowing us to examine the functional organization of the brain at different levels of granularity. Finally, we propose a model for the problem of unified and group-contrasting edge discovery which aims to discover discriminative brain networks that can help us to better distinguish between samples from different classes.

APA, Harvard, Vancouver, ISO, and other styles

27

Pineau, Edouard. "Contributions to representation learning of multivariate time series and graphs." Electronic Thesis or Diss., Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAT037.

Full text

Abstract:

Les algorithmes de machine learning sont construits pour apprendre, à partir de données, des modèles statistiques de décision ou de prédiction, sur un large panel de tâches. En général, les modèles appris sont des approximations d'un "vrai" modèle de décision, dont la pertinence dépend d'un équilibre entre la richesse du modèle appris, la complexité de la distribution des données et la complexité de la tâche à résoudre à partir des données. Cependant, il est souvent nécessaire d'adopter des hypothèses simplificatrices sur la donnée (e.g. séparabilité linéaire, indépendance des observations, etc.). Quand la distribution des donnée est complexe (e.g. grande dimension avec des interactions non-linéaires entre les variables observées), les hypothèses simplificatrices peuvent être contre-productives. Il est alors nécessaire de trouver une représentation alternatives des données avant d'apprendre le modèle de décision. L'objectif de la représentation des données est de séparer l'information pertinente du bruit, en particulier quand l'information est latente (i.e. cachée dans la donnée), pour aider le modèle statistique de décision. Jusqu'à récemment, beaucoup de représentations standards étaient construites à la main par des experts. Avec l'essor des techniques nouvelles de machine learning, et en particulier l'utilisation de réseaux de neurones, des techniques d'apprentissage de représentation ont surpassées les représentations manuelles dans de nombreux domaines. Dans cette thèse, nous nous sommes intéressés à l'apprentissage de représentation de séries temporelles multivariées (STM) et de graphes. STM et graphes sont des objets complexes qui ont des caractéristiques les rendant difficilement traitables par des algorithmes standards de machine learning. Par exemple, ils peuvent avoir des tailles variables et ont des alignements non-triviaux, qui empêchent l'utilisation de métriques standards pour les comparer entre eux. Il est alors nécessaire de trouver pour les échantillons observés (STM ou graphes) une représentation alternatives qui les rend comparables. Les contributions de ma thèses sont un ensemble d'analyses, d'approches pratiques et de résultats théoriques présentant des nouvelles manières d'apprendre une représentation de STM et de graphes. Deux méthodes de représentation de STM ont dédiées au suivi d'état caché de systèmes mécaniques. La première propose une représentation basée "model-based" appelée Sequence-to-graph (Seq2Graph). Seq2Graph se base sur l'hypothèse que les données observées ont été généré par un modèle causal simple, dont l'espace des paramètres sert d'espace de représentation. La second méthode propose une méthode générique de détection de tendances dans des séries temporelles, appelée Contrastive Trend Estimation (CTE), qui fait l'hypothèse que le vieillissement d'un système mécanique est monotone. Une preuve d'identifiabilité et une extension à des problèmes d'analyse de survie rendent cette approche puissante pour le suivi d'état de système mécaniques. Deux méthodes de représentation de graphes pour la classification sont aussi proposées. Une première propose de voir les graphes comme des séquences de nœuds et donc de les traiter avec un outil standard de représentation de séquences : un réseau de neurones récurrents. Une second méthode propose une analyse théorique et pratique du spectre du Laplacien pour la classification de graphes
Machine learning (ML) algorithms are designed to learn models that have the ability to take decisions or make predictions from data, in a large panel of tasks. In general, the learned models are statistical approximations of the true/optimal unknown decision models. The efficiency of a learning algorithm depends on an equilibrium between model richness, complexity of the data distribution and complexity of the task to solve from data. Nevertheless, for computational convenience, the statistical decision models often adopt simplifying assumptions about the data (e.g. linear separability, independence of the observed variables, etc.). However, when data distribution is complex (e.g. high-dimensional with nonlinear interactions between observed variables), the simplifying assumptions can be counterproductive. In this situation, a solution is to feed the model with an alternative representation of the data. The objective of data representation is to separate the relevant information with respect to the task to solve from the noise, in particular if the relevant information is hidden (latent), in order to help the statistical model. Until recently and the rise of modern ML, many standard representations consisted in an expert-based handcrafted preprocessing of data. Recently, a branch of ML called deep learning (DL) completely shifted the paradigm. DL uses neural networks (NNs), a family of powerful parametric functions, as learning data representation pipelines. These recent advances outperformed most of the handcrafted data in many domains.In this thesis, we are interested in learning representations of multivariate time series (MTS) and graphs. MTS and graphs are particular objects that do not directly match standard requirements of ML algorithms. They can have variable size and non-trivial alignment, such that comparing two MTS or two graphs with standard metrics is generally not relevant. Hence, particular representations are required for their analysis using ML approaches. The contributions of this thesis consist of practical and theoretical results presenting new MTS and graphs representation learning frameworks.Two MTS representation learning frameworks are dedicated to the ageing detection of mechanical systems. First, we propose a model-based MTS representation learning framework called Sequence-to-graph (Seq2Graph). Seq2Graph assumes that the data we observe has been generated by a model whose graphical representation is a causality graph. It then represents, using an appropriate neural network, the sample on this graph. From this representation, when it is appropriate, we can find interesting information about the state of the studied mechanical system. Second, we propose a generic trend detection method called Contrastive Trend Estimation (CTE). CTE learns to classify pairs of samples with respect to the monotony of the trend between them. We show that using this method, under few assumptions, we identify the true state underlying the studied mechanical system, up-to monotone scalar transform.Two graph representation learning frameworks are dedicated to the classification of graphs. First, we propose to see graphs as sequences of nodes and create a framework based on recurrent neural networks to represent and classify them. Second, we analyze a simple baseline feature for graph classification: the Laplacian spectrum. We show that this feature matches minimal requirements to classify graphs when all the meaningful information is contained in the structure of the graphs

APA, Harvard, Vancouver, ISO, and other styles

28

Neumann, Marion [Verfasser]. "Learning with Graphs using Kernels from Propagated Information / Marion Neumann." Bonn : Universitäts- und Landesbibliothek Bonn, 2015. http://d-nb.info/1077289626/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Moghadasin, Babak. "An Approach on Learning Multivariate Regression Chain Graphs from Data." Thesis, Linköpings universitet, Databas och informationsteknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-94019.

Full text

Abstract:

The necessity of modeling is vital for the purpose of reasoning and diagnosing in complex systems, since the human mind might sometimes have a limited capacity and an inability to be objective. The chain graph (CG) class is a powerful and robust tool for modeling real-world applications. It is a type of probabilistic graphical models (PGM) and has multiple interpretations. Each of these interpretations has a distinct Markov property. This thesis deals with the multivariate regression chain graph (MVR-CG) interpretation. The main goal of this thesis is to implement and evaluate the results of the MVR-PC-algorithm proposed by Sonntag and Peña in 2012. This algorithm uses a constraint based approach used in order to learn a MVR-CG from data.In this study the MRV-PC-algorithm is implemented and tested to see whether the implementation is correct. For this purpose, it is run on several different independence models that can be perfectly represented by MVR-CGs. The learned CG and the independence model of the given probability distribution are then compared to ensure that they are in the same Markov equivalence class. Additionally, for the purpose of checking how accurate the algorithm is, in learning a MVR-CG from data, a large number of samples are passed to the algorithm. The results are analyzed based on number of nodes and average number of adjacents per node. The accuracy of the algorithm is measured by the precision and recall of independencies and dependencies.In general, the higher the number of samples given to the algorithm, the more accurate the learned MVR-CGs become. In addition, when the graph is sparse, the result becomes significantly more accurate. The number of nodes can affect the results slightly. When the number of nodes increases it can lead to better results, if the average number of adjacents is fixed. On the other hand, if the number of nodes is fixed and the average number of adjacents increases, the effect is more considerable and the accuracy of the results dramatically declines. Moreover the type of the random variables can affect the results. Given the samples with discrete variables, the recall of independencies measure would be higher and the precision of independencies measure would be lower. Conversely, given the samples with continuous variables, the recall of independencies would be less but the precision of independencies would be higher.

APA, Harvard, Vancouver, ISO, and other styles

30

You, Chang Hun. "Learning patterns in dynamic graphs with application to biological networks." Pullman, Wash. : Washington State University, 2009. http://www.dissertations.wsu.edu/Dissertations/Summer2009/c_you_072309.pdf.

Full text

Abstract:

Thesis (Ph. D.)--Washington State University, August 2009.
Title from PDF title page (viewed on Aug. 19, 2009). "School of Electrical Engineering and Computer Science." Includes bibliographical references (p. 114-117).

APA, Harvard, Vancouver, ISO, and other styles

31

Kulla-Mader, Julia. "Graphs via Ink: Understanding How the Amount of Non-data Ink in a Graph Affects Perception and Learning." Thesis, School of Information and Library Science, 2007. http://hdl.handle.net/1901/379.

Full text

Abstract:

There is much debate in the design community concerning how to make an easy-to-understand graph. While expert designers recommend including as little non-data ink as possible, there is little empirical evidence to support their arguments. Non-data ink refers to any ink on a graph that is not required to display the graph's data. As a result of the lack of strong evidence concerning how to design graphs, there is widespread confusion when it comes to best practices. This paper describes a preliminary study of graph perception and learning using an eye-tracking system at UNC's School of Information and Library Science.

APA, Harvard, Vancouver, ISO, and other styles

32

Adjei, Seth Akonor. "Refining Learning Maps with Data Fitting Techniques." Digital WPI, 2015. https://digitalcommons.wpi.edu/etd-theses/178.

Full text

Abstract:

Learning maps have been used to represent student knowledge for many years. These maps are usually hand made by experts in a given domain. However, these hand-made maps have not been found to be predictive of student performance. Several methods have been proposed to find bet-ter fitting learning maps. These methods include the Learning Factors Analysis (LFA) model and the Rule-space method. In this thesis we report on the application of one of the proposed operations in the LFA method to a small section of a skill graph and develop a greedy search algorithm for finding better fitting models for this graph. Additionally an investigation of the factors that influence the search for better data fitting models using the proposed algorithm is reported. We also present an empirical study in which PLACEments, an adaptive testing system that employs a skill graph, is modified to test the strength of prerequisite skill links in a given learning map and propose a method for refining learning maps based on those findings. It was found that the proposed greedy search algorithm performs as well as an original skill graph but with a smaller set of skills in the graph. Additionally it was found that, among other factors, the number of unnecessary skills, the number of items in the graph, and the guess and slip rates of the items tagged with skills in the graph have an impact on the search. Further, the size of the evaluation data set impacts the search. The more data there is for the search, the more predictive the learned skill graph. Additionally, PLACEments, an adaptive testing feature of ASSISTments, has been found to be useful for refining skill graphs by detecting the strengths of prerequisite links between skills in a graph.

APA, Harvard, Vancouver, ISO, and other styles

33

Mayo, Quentin R. "Detection of Generalizable Clone Security Coding Bugs Using Graphs and Learning Algorithms." Thesis, University of North Texas, 2018. https://digital.library.unt.edu/ark:/67531/metadc1404548/.

Full text

Abstract:

This research methodology isolates coding properties and identifies the probability of security vulnerabilities using machine learning and historical data. Several approaches characterize the effectiveness of detecting security-related bugs that manifest as vulnerabilities, but none utilize vulnerability patch information. The main contribution of this research is a framework to analyze LLVM Intermediate Representation Code and merging core source code representations using source code properties. This research is beneficial because it allows source programs to be transformed into a graphical form and users can extract specific code properties related to vulnerable functions. The result is an improved approach to detect, identify, and track software system vulnerabilities based on a performance evaluation. The methodology uses historical function level vulnerability information, unique feature extraction techniques, a novel code property graph, and learning algorithms to minimize the amount of end user domain knowledge necessary to detect vulnerabilities in applications. The analysis shows approximately 99% precision and recall to detect known vulnerabilities in the National Institute of Standards and Technology (NIST) Software Assurance Metrics and Tool Evaluation (SAMATE) project. Furthermore, 72% percent of the historical vulnerabilities in the OpenSSL testing environment were detected using a linear support vector classifier (SVC) model.

APA, Harvard, Vancouver, ISO, and other styles

34

Ezzeddine, Diala. "A contribution to topological learning and its application in Social Networks." Thesis, Lyon 2, 2014. http://www.theses.fr/2014LYO22011/document.

Full text

Abstract:

L'Apprentissage Supervisé est un domaine populaire de l'Apprentissage Automatique en progrès constant depuis plusieurs années. De nombreuses techniques ont été développées pour résoudre le problème de classification, mais, dans la plupart des cas, ces méthodes se basent sur la présence et le nombre de points d'une classe donnée dans des zones de l'espace que doit définir le classifieur. Á cause de cela la construction de ce classifieur est dépendante de la densité du nuage de points des données de départ. Dans cette thèse, nous montrons qu'utiliser la topologie des données peut être une bonne alternative lors de la construction des classifieurs. Pour cela, nous proposons d'utiliser les graphes topologiques comme le Graphe de Gabriel (GG) ou le Graphes des Voisins Relatifs (RNG). Ces dernier représentent la topologie de données car ils sont basées sur la notion de voisinages et ne sont pas dépendant de la densité. Pour appliquer ce concept, nous créons une nouvelle méthode appelée Classification aléatoire par Voisinages (Random Neighborhood Classification (RNC)). Cette méthode utilise des graphes topologiques pour construire des classifieurs. De plus, comme une Méthodes Ensemble (EM), elle utilise plusieurs classifieurs pour extraire toutes les informations pertinentes des données. Les EM sont bien connues dans l'Apprentissage Automatique. Elles génèrent de nombreux classifieurs à partir des données, puis agrègent ces classifieurs en un seul. Le classifieur global obtenu est reconnu pour être très eficace, ce qui a été montré dans de nombreuses études. Cela est possible car il s'appuie sur des informations obtenues auprès de chaque classifieur qui le compose. Nous avons comparé RNC à d'autres méthodes de classification supervisées connues sur des données issues du référentiel UCI Irvine. Nous constatons que RNC fonctionne bien par rapport aux meilleurs d'entre elles, telles que les Forêts Aléatoires (RF) et Support Vector Machines (SVM). La plupart du temps, RNC se classe parmi les trois premières méthodes en terme d'eficacité. Ce résultat nous a encouragé à étudier RNC sur des données réelles comme les tweets. Twitter est un réseau social de micro-blogging. Il est particulièrement utile pour étudier l'opinion à propos de l'actualité et sur tout sujet, en particulier la politique. Cependant, l'extraction de l'opinion politique depuis Twitter pose des défis particuliers. En effet, la taille des messages, le niveau de langage utilisé et ambiguïté des messages rend très diffcile d'utiliser les outils classiques d'analyse de texte basés sur des calculs de fréquence de mots ou des analyses en profondeur de phrases. C'est cela qui a motivé cette étude. Nous proposons d'étudier les couples auteur/sujet pour classer le tweet en fonction de l'opinion de son auteur à propos d'un politicien (un sujet du tweet). Nous proposons une procédure qui porte sur l'identification de ces opinions. Nous pensons que les tweets expriment rarement une opinion objective sur telle ou telle action d'un homme politique mais plus souvent une conviction profonde de son auteur à propos d'un mouvement politique. Détecter l'opinion de quelques auteurs nous permet ensuite d'utiliser la similitude dans les termes employés par les autres pour retrouver ces convictions à plus grande échelle. Cette procédure à 2 étapes, tout d'abord identifier l'opinion de quelques couples de manière semi-automatique afin de constituer un référentiel, puis ensuite d'utiliser l'ensemble des tweets d'un couple (tous les tweets d'un auteur mentionnant un politicien) pour les comparer avec ceux du référentiel. L'Apprentissage Topologique semble être un domaine très intéressant à étudier, en particulier pour résoudre les problèmes de classification
Supervised Learning is a popular field of Machine Learning that has made recent progress. In particular, many methods and procedures have been developed to solve the classification problem. Most classical methods in Supervised Learning use the density estimation of data to construct their classifiers.In this dissertation, we show that the topology of data can be a good alternative in constructing classifiers. We propose using topological graphs like Gabriel graphs (GG) and Relative Neighborhood Graphs (RNG) that can build the topology of data based on its neighborhood structure. To apply this concept, we create a new method called Random Neighborhood Classification (RNC).In this method, we use topological graphs to construct classifiers and then apply Ensemble Methods (EM) to get all relevant information from the data. EM is well known in Machine Learning, generates many classifiers from data and then aggregates these classifiers into one. Aggregate classifiers have been shown to be very efficient in many studies, because it leverages relevant and effective information from each generated classifier. We first compare RNC to other known classification methods using data from the UCI Irvine repository. We find that RNC works very well compared to very efficient methods such as Random Forests and Support Vector Machines. Most of the time, it ranks in the top three methods in efficiency. This result has encouraged us to study the efficiency of RNC on real data like tweets. Twitter, a microblogging Social Network, is especially useful to mine opinion on current affairs and topics that span the range of human interest, including politics. Mining political opinion from Twitter poses peculiar challenges such as the versatility of the authors when they express their political view, that motivate this study. We define a new attribute, called couple, that will be very helpful in the process to study the tweets opinion. A couple is an author that talk about a politician. We propose a new procedure that focuses on identifying the opinion on tweet using couples. We think that focusing on the couples's opinion expressed by several tweets can overcome the problems of analysing each single tweet. This approach can be useful to avoid the versatility, language ambiguity and many other artifacts that are easy to understand for a human being but not automatically for a machine.We use classical Machine Learning techniques like KNN, Random Forests (RF) and also our method RNC. We proceed in two steps : First, we build a reference set of classified couples using Naive Bayes. We also apply a second alternative method to Naive method, sampling plan procedure, to compare and evaluate the results of Naive method. Second, we evaluate the performance of this approach using proximity measures in order to use RNC, RF and KNN. The expirements used are based on real data of tweets from the French presidential election in 2012. The results show that this approach works well and that RNC performs very good in order to classify opinion in tweets.Topological Learning seems to be very intersting field to study, in particular to address the classification problem. Many concepts to get informations from topological graphs need to analyse like the ones described by Aupetit, M. in his work (2005). Our work show that Topological Learning can be an effective way to perform classification problem

APA, Harvard, Vancouver, ISO, and other styles

35

Landrieu, Loïc. "Learning structured models on weighted graphs, with applications to spatial data analysis." Thesis, Paris Sciences et Lettres (ComUE), 2016. http://www.theses.fr/2016PSLEE046/document.

Full text

Abstract:

La modélisation de processus complexes peut impliquer un grand nombre de variables ayant entre elles une structure de corrélation compliquée. Par exemple, les phénomènes spatiaux possèdent souvent une forte régularité spatiale, se traduisant par une corrélation entre variables d’autant plus forte que les régions correspondantes sont proches. Le formalisme des graphes pondérés permet de capturer de manière compacte ces relations entre variables, autorisant la formalisation mathématique de nombreux problèmes d’analyse de données spatiales. La première partie du manuscrit se concentre sur la résolution efficace de problèmes de régularisation spatiale, mettant en jeu des pénalités telle que la variation totale ou la longueur totale des contours. Nous présentons une stratégie de préconditionnement pour l’algorithme generalized forward-backward, spécifiquement adaptée à la résolution de problèmes structurés par des graphes pondérés présentant une grande variabilité de configurations et de poids. Nous présentons ensuite un nouvel algorithme appelé cut pursuit, qui exploite les relations entre les algorithmes de flots et la variation totale au travers d’une stratégie de working set. Ces algorithmes présentent des performances supérieures à l’état de l’art pour des tâches d’agrégations de données geostatistiques. La seconde partie de ce document se concentre sur le développement d’un nouveau modèle qui étend les chaînes de Markov à temps continu au cas des graphes pondérés non orientés généraux. Ce modèle autorise la prise en compte plus fine des interactions entre noeuds voisins pour la prédiction structurée, comme illustré pour la classification supervisée de tissus urbains
Modeling complex processes often involve a high number of variables with anintricate correlation structure. For example, many spatially-localized processes display spatial regularity, as variables corresponding to neighboring regions are more correlated than distant ones. The formalism of weighted graphs allows us to capture relationships between interacting variables in a compact manner, permitting the mathematical formulation of many spatial analysis tasks. The first part of this manuscript focuses on optimization problems with graph-structure dregularizers, such as the total variation or the total boundary size. We first present the convex formulation and its resolution with proximal splitting algorithms. We introduce a new preconditioning scheme for the existing generalized forward-backward proximal splitting algorithm, specifically designed for graphs with high variability in neighbourhood configurations and edge weights. We then introduce a new algorithm, cut pursuit, which used the links between graph cuts and total variation in a working set scheme. We also present a variation of this algorithm which solved the problem regularized by the non convex total boundary length penalty. We show that our proposed approaches reach or outperform state-of-the-art for geostatistical aggregation as well as image recovery problems. The second part focuses on the development of a new model, expanding continuous-time Markov chain models to general undirected weighted graphs. This allows us to take into account the interactions between neighbouring nodes in structured classification, as demonstrated for a supervised land-use classification task from cadastral data

APA, Harvard, Vancouver, ISO, and other styles

36

Preece, Jenny. "Interpreting trends in graphs : a study of 14 and 15 year olds." Thesis, n.p, 1985. http://ethos.bl.uk/.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Yang, Karren Dai. "Learning causal graphs under interventions and applications to single-cell biological data analysis." Thesis, Massachusetts Institute of Technology, 2021. https://hdl.handle.net/1721.1/130806.

Full text

Abstract:

Thesis: S.M., Massachusetts Institute of Technology, Department of Biological Engineering, February, 2021
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, February, 2021
Cataloged from the official PDF version of thesis.
Includes bibliographical references (pages 49-51).
This thesis studies the problem of learning causal directed acyclic graphs (DAGs) in the setting where both observational and interventional data is available. This setting is common in biology, where gene regulatory networks can be intervened on using chemical reagents or gene deletions. The identifiability of causal DAGs under perfect interventions, which eliminate dependencies between targeted variables and their direct causes, has previously been studied. This thesis first extends these identifiability results to general interventions, which may modify the dependencies between targeted variables and their causes without eliminating them, by defining and characterizing the interventional Markov equivalence class that can be identified from general interventions. Subsequently, this thesis proposes the first provably consistent algorithm for learning DAGs in this setting. Finally, this algorithm as well as related work is applied to analyze biological datasets.
by Karren Dai Yang.
S.M.
S.M.
S.M. Massachusetts Institute of Technology, Department of Biological Engineering
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science

APA, Harvard, Vancouver, ISO, and other styles

38

Chávez, Escalante Diego Alonso 1988. "Semi-supervised learning with graphs methods using signal processing = Métodos de aprendizado semi-supervisionado com grafos usando processamento de sinais." [s.n.], 2014. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275521.

Full text

Abstract:

Orientador: Siome Klein Goldenstein
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-25T19:49:49Z (GMT). No. of bitstreams: 1 ChavezEscalante_DiegoAlonso_M.pdf: 1954210 bytes, checksum: c9a77d2f0545d5517700c34dd6cf3324 (MD5) Previous issue date: 2014
Resumo: No aprendizado de máquina, os problemas de classificação de padrões eram tradicionalmente abordados por algoritmos de aprendizado supervisionado que utilizam apenas dados rotulados para treinar-se. Entretanto, os dados rotulados são realmente difíceis de coletar em muitos domínios de problemas, enquanto os dados não rotulados são geralmente mais fáceis de recolher. Também em aprendizado de máquina só o aprendizado não supervisionado é capaz de aprender a topologia e propriedades de um conjunto de dados não rotulados. Portanto, a fim de conseguir uma classificação utilizando o conhecimento a partir de dados rotulados e não rotulados, é necessário o uso de conceitos de aprendizado supervisionado tanto como do não supervisionado. Este tipo de aprendizagem é chamado de aprendizado semi-supervisionado, que declara ter construído melhores classificadores que o tradicional aprendizado supervisionado em algumas condições especificas, porque não só aprende dos dados rotulados, mas também das propriedades naturais dos dados não rotulados como por exemplo a distribuição espacial deles. O aprendizado semi-supervisionado apresenta uma ampla coleção de métodos e técnicas para classificação, e um dos mais interessantes e o aprendizado semi-supervisionado baseado em grafos, o qual modela o problema da classificação semi-supervisionada utilizando a teoria dos grafos. Mas um problema que surge a partir dessa técnica é o custo para treinar conjuntos com grandes quantidades de dados, de modo que o desenvolvimento de algoritmos escaláveis e eficientes de aprendizado semi-supervisionado baseado em grafos e um problema muito interessante e prometedor para lidar com ele. Desta pesquisa foram desenvolvidos dois algoritmos, um para a construção do grafo usando redes neurais não supervisionadas e outro para a regularização do grafo usando processamento de sinais em grafos, especificamente usando filtros de resposta finita sobre o grafo. As duas soluções mostraram resultados comparáveis com os da literatura
Abstract: In machine learning, classification problems were traditionally addressed by supervised learning algorithms, which only use labeled data for training. However, labeled data in many problem domains are really hard to collect, while unlabeled data are usually easy to collect. Also, in machine learning, only unsupervised learning is capable to learn the topology and properties of a set of unlabeled data. In order to do a classification using knowledge from labeled and unlabeled data, it is necessary to use concepts from both supervised and unsupervised learning. This type of learning is called semi-supervised learning, which has claimed to build better classifiers than the traditional supervised learning in some specific conditions, because it does not only learn from the labeled data, but also from the natural properties of unlabeled data as for example spatial distribution. Semi-supervised learning presents a broad collection of methods and techniques for classification. Among them there is graph based semi-supervised learning, which model the problem of semi-supervised classification using graph theory. One problem that arises from this technique is the cost for training large data sets, so the development of scalable and efficient algorithms for graph based semi-supervised learning is a interesting and promising problem to deal with. From this research we developed two algorithms, one for graph construction using unsupervised neural networks; and other for graph regularization using graph signal processing theory, more specifically using FIR filters over a graph. Both solutions showed comparable performance to other literature methods in terms of accuracy
Mestrado
Ciência da Computação
Mestre em Ciência da Computação

APA, Harvard, Vancouver, ISO, and other styles

39

GARBARINO, DAVIDE. "Acknowledging the structured nature of real-world data with graphs embeddings and probabilistic inference methods." Doctoral thesis, Università degli studi di Genova, 2022. http://hdl.handle.net/11567/1092453.

Full text

Abstract:

In the artificial intelligence community there is a growing consensus that real world data is naturally represented as graphs because they can easily incorporate complexity at several levels, e.g. hierarchies or time dependencies. In this context, this thesis studies two main branches for structured data. In the first part we explore how state-of-the-art machine learning methods can be extended to graph modeled data provided that one is able to represent graphs in vector spaces. Such extensions can be applied to analyze several kinds of real-world data and tackle different problems. Here we study the following problems: a) understand the relational nature and evolution of websites which belong to different categories (e-commerce, academic (p.a.) and encyclopedic (forum)); b) model tennis players scores based on different game surfaces and tournaments in order to predict matches results; c) analyze preter- m-infants motion patterns able to characterize possible neuro degenerative disorders and d) build an academic collaboration recommender system able to model academic groups and individual research interest while suggesting possible researchers to connect with, topics of interest and representative publications to external users. In the second part we focus on graphs inference methods from data which present two main challenges: missing data and non-stationary time dependency. In particular, we study the problem of inferring Gaussian Graphical Models in the following settings: a) inference of Gaussian Graphical Models when data are missing or latent in the context of multiclass or temporal network inference and b) inference of time-varying Gaussian Graphical Models when data is multivariate and non-stationary. Such methods have a natural application in the composition of an optimized stock markets portfolio. Overall this work sheds light on how to acknowledge the intrinsic structure of data with the aim of building statistical models that are able to capture the actual complexity of the real world.

APA, Harvard, Vancouver, ISO, and other styles

40

Flores, Nicandro. "Counting directed acyclic graphs and its application to Monte Carlo learning of Bayesian networks." Connect to online resource, 2007. http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:1447692.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Navarin, Nicolò <1984&gt. "Learning with Kernels on Graphs: DAG-based kernels, data streams and RNA function prediction." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6578/1/navarin_nicolo_tesi.pdf.

Full text

Abstract:

In many application domains data can be naturally represented as graphs. When the application of analytical solutions for a given problem is unfeasible, machine learning techniques could be a viable way to solve the problem. Classical machine learning techniques are defined for data represented in a vectorial form. Recently some of them have been extended to deal directly with structured data. Among those techniques, kernel methods have shown promising results both from the computational complexity and the predictive performance point of view. Kernel methods allow to avoid an explicit mapping in a vectorial form relying on kernel functions, which informally are functions calculating a similarity measure between two entities. However, the definition of good kernels for graphs is a challenging problem because of the difficulty to find a good tradeoff between computational complexity and expressiveness. Another problem we face is learning on data streams, where a potentially unbounded sequence of data is generated by some sources. There are three main contributions in this thesis. The first contribution is the definition of a new family of kernels for graphs based on Directed Acyclic Graphs (DAGs). We analyzed two kernels from this family, achieving state-of-the-art results from both the computational and the classification point of view on real-world datasets. The second contribution consists in making the application of learning algorithms for streams of graphs feasible. Moreover,we defined a principled way for the memory management. The third contribution is the application of machine learning techniques for structured data to non-coding RNA function prediction. In this setting, the secondary structure is thought to carry relevant information. However, existing methods considering the secondary structure have prohibitively high computational complexity. We propose to apply kernel methods on this domain, obtaining state-of-the-art results.

APA, Harvard, Vancouver, ISO, and other styles

42

Navarin, Nicolò <1984&gt. "Learning with Kernels on Graphs: DAG-based kernels, data streams and RNA function prediction." Doctoral thesis, Alma Mater Studiorum - Università di Bologna, 2014. http://amsdottorato.unibo.it/6578/.

Full text

Abstract:

In many application domains data can be naturally represented as graphs. When the application of analytical solutions for a given problem is unfeasible, machine learning techniques could be a viable way to solve the problem. Classical machine learning techniques are defined for data represented in a vectorial form. Recently some of them have been extended to deal directly with structured data. Among those techniques, kernel methods have shown promising results both from the computational complexity and the predictive performance point of view. Kernel methods allow to avoid an explicit mapping in a vectorial form relying on kernel functions, which informally are functions calculating a similarity measure between two entities. However, the definition of good kernels for graphs is a challenging problem because of the difficulty to find a good tradeoff between computational complexity and expressiveness. Another problem we face is learning on data streams, where a potentially unbounded sequence of data is generated by some sources. There are three main contributions in this thesis. The first contribution is the definition of a new family of kernels for graphs based on Directed Acyclic Graphs (DAGs). We analyzed two kernels from this family, achieving state-of-the-art results from both the computational and the classification point of view on real-world datasets. The second contribution consists in making the application of learning algorithms for streams of graphs feasible. Moreover,we defined a principled way for the memory management. The third contribution is the application of machine learning techniques for structured data to non-coding RNA function prediction. In this setting, the secondary structure is thought to carry relevant information. However, existing methods considering the secondary structure have prohibitively high computational complexity. We propose to apply kernel methods on this domain, obtaining state-of-the-art results.

APA, Harvard, Vancouver, ISO, and other styles

43

Shah, Shivani. "Graph sparsification and unsupervised machine learning for metagenomic binning." Thesis, Tours, 2019. http://theses.scd.univ-tours.fr/index.php?fichier=2019/shivani.shah_18225.pdf.

Full text

Abstract:

La métagénomique est le domaine de la biologie qui concerne l’étude du contenu génomique des communautés microbiennes directement dans leur environnement. Les données métagénomiques utilisées dans ces travaux de thèse correspondent à des technologies de séquençage produisant des fragments d’ADN courts (reads). L'une des étapes clé de l'analyse des données métagénomiques et développée dans cette étude est le regroupement de reads, appelé également binning. Lors de cette tâche de binning, des groupes (bins) doivent être formés de sorte que chaque groupe soit composé de reads provenant de la même espèce ou genre. La méthodologie traditionnelle consiste à effectuer cette étape sur des séquences plus grandes (contigs), mais cette étape génère potentiellement des séquences dites chimériques. L'un des problèmes liés au binning appliqué aux lectures est lié à la taille importante des jeux de données. La méthodologie traditionnelle appliquée sur les reads, accable les ressources de calcul. Par conséquent, il est nécessaire de développer des approches de binning adaptables à de données massives.Dans cette thèse, nous abordons ce problème en proposant une méthode évolutive pour effectuer le binning. Nous positionnons notre travail parmi les approches de binning basées sur la composition et dans un contexte totalement non supervisé. Afin de réduire la complexité de la tâche de binning, des méthodes sont proposées pour filtrer préalablement les associations entre les données. Le développement de l'approche a été réalisé en deux étapes. D'abord, la méthodologie a été évaluée sur des ensembles de données métagénomiques plus petits (composés de quelques milliers de points). Dans un deuxième temps, nous proposons d’adapter cette approche à des ensembles de données plus volumineux (composés de millions de points) avec des méthodes d’indexation sensibles à la similarité (LSH). La thèse comporte trois contributions majeures.Premièrement, nous proposons un ensemble varié d’algorithmes de filtrage d’associations entre les données (reads) par l’intermédiaire de graphes de proximité. Ces graphes de proximité sont construits pour capturer les relations les plus pertinentes entre reads pour la tâche de binning. Nous exploitons par suite des algorithmes de détection de communautés sur ces graphes pour identifier les groupes de reads d’intérêts. Une étude exploratoire a été réalisée avec plusieurs graphes de proximité et algorithmes de détection de communautés sur trois jeux de données métagénomiques. Suite à cette étude, nous proposons une approche pipeline nommée ProxiClust couplant la construction d’un graphe de type kNN et l’algorithme Louvain de détection de communautés.Deuxièmement, afin d’adresser le problème de la scalabilité et aborder des jeux de données plus volumineux, la matrice de similarité utilisée dans le pipeline est remplacée par l’exploitation de tables de hachage sensibles à la similarité d’intérêt construites à partir de l'approche LSH Sim-Hash. Nous introduisons deux stratégies pour construire des graphes de proximité à partir des tables de hachage: 1) le graphe des microclusters et 2) le graphe kNN approché. Les performances et les limites de ces graphes ont été évaluées sur de grands ensembles de données MC et discutées. Sur la base de cette étude, nous retenons le graphe kNN mutuels comme le graphe de proximité le plus approprié pour les grands ensembles de données. Cette proposition a également été évaluée et confirmée sur des données de séquences métagénomiques de référence issues du challenge international CAMI.Enfin, nous examinons des approches de hachage alternatives pour construire des tables de hachage de meilleures qualités. L’approche de hachage dépendante des données ITQ est introduite et exploitée, puis nous en proposons deux variantes : orthogonale (ITQ-OrthSH) et non orthogonale (ITQ-SH). Ces approches de hachage ont été évaluées et discutées sur les données de reads massives à disposition
Metagenomics is the field biology that relates to the study of genomic content of microbial communities directly in their natural environments. The metagenomic data is generated by sequencing technology that take the enviormental samples as the input. The generated data is composed of short fragments of DNA (called reads), which originate from genomes of all species present in the sample. The datasets size range from thousands to millions of reads. One of the steps of metagenomic data analysis is binning of the reads. In binning groups (called bins) are to be formed such that each group is composed of reads which are likely to originate from the same specie or specie family. It has essentially been treated as a task of clustering in the metagenomic literature. One of the challenges in binning occurs due to the large size of the datasets. The method overwhelms the computational resources required while performing the task. Hence the development of binning approaches which are scalable to large datasets is required.In this thesis, we address this issue by proposing a scalable method to perform binning. We position our work among the compositional based binning approaches (use of short kmers) and in completely unsupervised context. On order to decrease the complexity of the binning task, methods are proposed to perform sparsification of the data prior to clustering. The development of the approach has been performed in two steps. First the idea has been evaluated on smaller metagenomic datasets (composed of few thousands of points). In the second step, we propose to scale this approach to larger datasets (composed of Millions of points) with similarity based indexing methods (LSH approaches). There are three major contributions of the thesis.First, we propose the idea of performing sparsification of the data with proximity graphs, prior to clustering. The proximity graphs are built on the data to capture pair-wise relationships between data points that are relevant for clustering. Then we leverage community detection algorithms on these graphs to identify clusters from the data. An exploratory study has been performed with several proximity graphs and community detection algorithm on three metagenomic datasets. Based on this study we propose an approach named ProxiClust with KNN graph and Louvain community detection to perform binning.Second, to scale this approach to larger datasets the distance matrix in the pipeline is replaced with hash tables built from Sim-hash LSH approach. We introduce two strategies to build proximity graphs from the hash tables: 1) Microclusters graph and 2) Approximate k nearest neighbour graph. The performance of these graphs have been evaluated on large MC datasets. The performance and limitations of these graphs are discussed. The baseline evaluation of these datasets have also been performed to determine their clustering difficulty. Based on this study we propose Mutual-KNN graph to be the appropriate proximity graph for the large datasets. This proposal has also evaluated and confirmed on the CAMI benchmark metagenomic datasets.Lastly, we examine alternative hashing approaches to build better quality hash tables. A data-dependent hashing approach ITQ and orthogonal version of Sim-hash have been included. Two new data dependent hashing approaches named ITQ-SH and ITQ-OrthSH are introduced. All the hashing approaches have been evaluated w.r.t their ability to hash the MC datasets with high precision and recall. AndThe introduction of Mutual-KNN as the appropriate proximity graph has led to new challenges in the pipeline. First, large number of clusters are generated due to high number of components in the Mutual-KNN graph. So, in order to obtain appropriate number of clusters, a strategy needs to be devised to merge the similar clusters. Also an approach to build Mutual-KNN graph from hash tables needs to be designed. This would complete the ProxiClust pipeline for the large datasets

APA, Harvard, Vancouver, ISO, and other styles

44

Bodily, Robert Gordon. "Designing, Developing, and Implementing Real-Time Learning Analytics Student Dashboards." BYU ScholarsArchive, 2018. https://scholarsarchive.byu.edu/etd/7258.

Full text

Abstract:

This document is a multiple-article format dissertation that discusses the iterative design, development, and evaluation processes necessary to create high quality learning analytics dashboard systems. With the growth of online and blended learning environments, the amount of data that researchers and practitioners collect from learning experiences has also grown. The field of learning analytics is concerned with using this data to improve teaching and learning. Many learning analytics systems focus on instructors or administrators, but these tools fail to involve students in the data-driven decision-making process. Providing feedback to students and involving students in this decision-making process can increase intrinsic motivation and help students succeed in online and blended environments. To support online and blended teaching and learning, the focus of this document is student-facing learning analytics dashboards. The first article in this dissertation is a literature review on student-facing learning analytics reporting systems. This includes any system that tracks learning analytics data and reports it directly to students. The second article in this dissertation is a design and development research article that used a practice-centered approach to iteratively design and develop a real-time student-facing dashboard. The third article in this dissertation is a design-based research article focused on improving student use of learning analytics dashboard tools.

APA, Harvard, Vancouver, ISO, and other styles

45

Richard, Émile. "Regularization methods for prediction in dynamic graphs and e-marketing applications." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2012. http://tel.archives-ouvertes.fr/tel-00906066.

Full text

Abstract:

Predicting connections among objects, based either on a noisy observation or on a sequence of observations, is a problem of interest for numerous applications such as recommender systems for e-commerce and social networks, and also in system biology, for inferring interaction patterns among proteins. This work presents formulations of the graph prediction problem, in both dynamic and static scenarios, as regularization problems. In the static scenario we encode the mixture of two different kinds of structural assumptions in a convex penalty involving the L1 and the trace norm. In the dynamic setting we assume that certain graph features, such as the node degree, follow a vector autoregressive model and we propose to use this information to improve the accuracy of prediction. The solutions of the optimization problems are studied both from an algorithmic and statistical point of view. Empirical evidences on synthetic and real data are presented showing the benefit of using the suggested methods.

APA, Harvard, Vancouver, ISO, and other styles

46

Morris, Christopher [Verfasser], Petra [Akademischer Betreuer] Mutzel, and Kristian [Gutachter] Kersting. "Learning with graphs: kernel and neural approaches / Christopher Morris ; Gutachter: Kristian Kersting ; Betreuer: Petra Mutzel." Dortmund : Universitätsbibliothek Dortmund, 2019. http://d-nb.info/1205157441/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Limnios, Stratis. "Graph Degeneracy Studies for Advanced Learning Methods on Graphs and Theoretical Results Edge degeneracy: Algorithmic and structural results Degeneracy Hierarchy Generator and Efficient Connectivity Degeneracy Algorithm A Degeneracy Framework for Graph Similarity Hcore-Init: Neural Network Initialization based on Graph Degeneracy." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX038.

Full text

Abstract:

L'extraction de sous-structures significatives a toujours été un élément clé de l’étude des graphes. Dans le cadre de l'apprentissage automatique, supervisé ou non, ainsi que dans l'analyse théorique des graphes, trouver des décompositions spécifiques et des sous-graphes denses est primordial dans de nombreuses applications comme entre autres la biologie ou les réseaux sociaux.Dans cette thèse, nous cherchons à étudier la dégénérescence de graphe, en partant d'un point de vue théorique, et en nous appuyant sur nos résultats pour trouver les décompositions les plus adaptées aux tâches à accomplir. C'est pourquoi, dans la première partie de la thèse, nous travaillons sur des résultats structurels des graphes à arête-admissibilité bornée, prouvant que de tels graphes peuvent être reconstruits en agrégeant des graphes à degré d’arête quasi-borné. Nous fournissons également des garanties de complexité de calcul pour les différentes décompositions de la dégénérescence, c'est-à-dire si elles sont NP-complètes ou polynomiales, selon la longueur des chemins sur lesquels la dégénérescence donnée est définie.Dans la deuxième partie, nous unifions les cadres de dégénérescence et d'admissibilité en fonction du degré et de la connectivité. Dans ces cadres, nous choisissons les plus expressifs, d'une part, et les plus efficaces en termes de calcul d'autre part, à savoir la dégénérescence 1-arête-connectivité pour expérimenter des tâches de dégénérescence standard, telle que la recherche d’influenceurs.Suite aux résultats précédents qui se sont avérés peu performants, nous revenons à l'utilisation du k-core mais en l’intégrant dans un cadre supervisé, i.e. les noyaux de graphes. Ainsi, en fournissant un cadre général appelé core-kernel, nous utilisons la décomposition k-core comme étape de prétraitement pour le noyau et appliquons ce dernier sur chaque sous-graphe obtenu par la décomposition pour comparaison. Nous sommes en mesure d'obtenir des performances à l’état de l’art sur la classification des graphes au prix d’une légère augmentation du coût de calcul.Enfin, nous concevons un nouveau cadre de dégénérescence de degré s’appliquant simultanément pour les hypergraphes et les graphes biparties, dans la mesure où ces derniers sont les graphes d’incidence des hypergraphes. Cette décomposition est ensuite appliquée directement à des architectures de réseaux de neurones pré-entrainés étant donné qu'elles induisent des graphes biparties et utilisent le core d'appartenance des neurones pour réinitialiser les poids du réseaux. Cette méthode est non seulement plus performant que les techniques d'initialisation de l’état de l’art, mais il est également applicable à toute paire de couches de convolution et linéaires, et donc adaptable à tout type d'architecture
Extracting Meaningful substructures from graphs has always been a key part in graph studies. In machine learning frameworks, supervised or unsupervised, as well as in theoretical graph analysis, finding dense subgraphs and specific decompositions is primordial in many social and biological applications among many others.In this thesis we aim at studying graph degeneracy, starting from a theoretical point of view, and building upon our results to find the most suited decompositions for the tasks at hand.Hence the first part of the thesis we work on structural results in graphs with bounded edge admissibility, proving that such graphs can be reconstructed by aggregating graphs with almost-bounded-edge-degree. We also provide computational complexity guarantees for the different degeneracy decompositions, i.e. if they are NP-complete or polynomial, depending on the length of the paths on which the given degeneracy is defined.In the second part we unify the degeneracy and admissibility frameworks based on degree and connectivity. Within those frameworks we pick the most expressive, on the one hand, and computationally efficient on the other hand, namely the 1-edge-connectivity degeneracy, to experiment on standard degeneracy tasks, such as finding influential spreaders.Following the previous results that proved to perform poorly we go back to using the k-core but plugging it in a supervised framework, i.e. graph kernels. Thus providing a general framework named core-kernel, we use the k-core decomposition as a preprocessing step for the kernel and apply the latter on every subgraph obtained by the decomposition for comparison. We are able to achieve state-of-the-art performance on graph classification for a small computational cost trade-off.Finally we design a novel degree degeneracy framework for hypergraphs and simultaneously on bipartite graphs as they are hypergraphs incidence graph. This decomposition is then applied directly to pretrained neural network architectures as they induce bipartite graphs and use the coreness of the neurons to re-initialize the neural network weights. This framework not only outperforms state-of-the-art initialization techniques but is also applicable to any pair of layers convolutional and linear thus being applicable however needed to any type of architecture

APA, Harvard, Vancouver, ISO, and other styles

48

Schwartz, Samuel David. "Machine Learning Techniques as Applied to Discrete and Combinatorial Structures." DigitalCommons@USU, 2019. https://digitalcommons.usu.edu/etd/7542.

Full text

Abstract:

Machine Learning Techniques have been used on a wide array of input types: images, sound waves, text, and so forth. In articulating these input types to the almighty machine, there have been all sorts of amazing problems that have been solved for many practical purposes. Nevertheless, there are some input types which don’t lend themselves nicely to the standard set of machine learning tools we have. Moreover, there are some provably difficult problems which are abysmally hard to solve within a reasonable time frame. This thesis addresses several of these difficult problems. It frames these problems such that we can then attempt to marry the allegedly powerful utility of existing machine learning techniques to the practical solvability of said problems.

APA, Harvard, Vancouver, ISO, and other styles

49

Weninger, Timothy Edwards. "Link discovery in very large graphs by constructive induction using genetic programming." Thesis, Manhattan, Kan. : Kansas State University, 2008. http://hdl.handle.net/2097/1087.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Bautista, Ruiz Esteban. "Laplacian Powers for Graph-Based Semi-Supervised Learning." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSEN081.

Full text

Abstract:

Les techniques d’apprentissage semi-supervisé basées sur des graphes (G-SSL) permettent d’exploiter des données étiquetées et non étiquetées pour construire de meilleurs classifiers. Malgré de nombreuses réussites, leur performances peuvent encore être améliorées, en particulier dans des situations ou` les graphes ont une faible séparabilité de classes ou quand le nombres de sujets supervisés par l’expert est déséquilibrés. Pour aborder ces limitations on introduit une nouvelle méthode pour G-SSL, appel´ee Lγ -PageRank, qui constitue la principal contribution de cette th`ese. Il s’agit d’une g´en´eralisation de l’algorithme PageRank ´a partir de l’utilisation de puissances positives γ de la matrice Laplacienne du graphe. L’étude théorique de Lγ -PageRank montre que (i) pour γ < 1, cela correspond `a une extension de l’algorithme PageRank aux processus de vol de L´evy: ou` les marcheurs aléatoires peuvent désormais relier, en un seul saut, des nœuds distants du graphe; et (ii) pour γ > 1, la classification est effectué sur des graphes signés: ou` les nœuds appartenant `a une même classe ont plus de chances de partager des liens positifs, tandis que les nœuds de classes différentes ont plus de chances d’être connectés avec des arêtes négatifs. Nous montrons l’existence d’une puissance optimale γ qui maximise la performance de classification, pour laquelle une méthode d’estimation automatique est conçue et évaluée. Des expériences sur plusieurs jeux de données montrent que les marcheurs aléatoires de vols de Lévy peuvent améliorer la détection des classes ayant des structures locales complexes, tandis que les graphes signés permet d’améliorer considérablement la séparabilité des données et de surpasser le problème des données étiquetées non équilibrées. Dans un second temps, nous étudions des implémentations efficaces de Lγ -PageRank. Nous proposons des extensions de Power Iteration et Gauss-Southwell pour Lγ -PageRank, qui sont des algorithmes initialement conçues pour calculer efficacement la solution de la méthode PageRank standard. Ensuite, les versions dynamiques de ces algorithmes sont également étendues à Lγ -PageRank, permettant de mettre `a jour la solution de Lγ -PageRank en complexité sub-linéaire lorsque le graphe évolue ou que de nouvelles données arrivent. Pour terminer, nous appliquons Lγ -PageRank dans le contexte du routage Internet. Nous abordons le problème de l’identification des systèmes autonomes (AS) pour des arêtes inter-AS `a partir du réseau d’adresses IP et des registres publics des AS. Des expériences sur des mesures traceroute d’Internet montrent que Lγ -PageRank peut résoudre cette tâche sans erreurs, même lorsqu’il n’y a pas d’exemples étiquetés par l’expert pour la totalité des classes
Graph-Based Semi-Supervised Learning (G-SSL) techniques learn from both labelled and unla- belled data to build better classifiers. Despite successes, its performance can still be improved, particularly in cases of graphs with unclear clusters or unbalanced labelled datasets. To ad- dress such limitations, the main contribution of this dissertation is a novel method for G-SSL referred to as the Lγ -PageRank method. It consists of a generalization of the PageRank algo- rithm based on the positive γ-th powers of the graph Laplacian matrix. The theoretical study of Lγ -PageRank shows that (i) for γ < 1, it corresponds to an extension of the PageRank algo- rithm to L´evy processes: where random walkers can now perform far-distant jumps in a single step; and (ii) for γ > 1, it operates on signed graphs: where nodes belonging to one same class are more likely to share positive edges while nodes from different classes are more likely to be connected with negative edges. We show the existence of an optimal γ-th power that maximizes performance, for which a method for its automatic estimation is devised and assessed. Exper- iments on several datasets demonstrate that the L´evy flight random walkers can enhance the detection of classes with complex local structures and that the signed graphs can significantly improve the separability of data and also override the issue of unbalanced labelled data. In addition, we study efficient implementations of Lγ -PageRank. Extensions of Power Iteration and Gauss-Southwell, successful algorithms to efficiently compute the solution of the standard PageRank algorithm, are derived for Lγ -PageRank. Moreover, the dynamic versions of Power Iteration and Gauss-Southwell, which can update the solution of standard PageRank in sub- linear complexity when the graph evolves or new data arrive, are also extended to Lγ -PageRank. Lastly, we apply Lγ -PageRank in the context of Internet routing. We address the problem of identifying the Autonomous Systems (AS) of inter-AS links from the network of IP addresses and AS public registers. Experiments on tracerout measurements collected from the Internet show that Lγ -PageRank can solve this inference task with no errors, even when the expert does not provide labelled examples of all classes

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Learning on graphs'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles