SEARCH · PubMed Health

Results for “Graph Neural Networks”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8Linked to original sources

PubMed2005

Systematic identification of statistically significant network measures.

We present a graph embedding space (i.e., a set of measures on graphs) for performing statistical analyses of networks. Key improvements over existing approaches include discovery of "motif hubs" (multiple overlapping significant subgraphs), computational efficiency relative to subgraph census, and flexibility (the method is easily generalizable to weighted and signed graphs). The embedding space is based on scalars, functionals of the adjacency matrix representing the network. Scalars are global, involving all nodes; although they can be related to subgraph enumeration, there is not a one-to-one mapping between scalars and subgraphs. Improvements in network randomization and significance testing--we learn the distribution rather than assuming Gaussianity--are also presented. The resulting algorithm establishes a systematic approach to the identification of the most significant scalars and suggests machine-learning techniques for network classification.

Algorithms↗

PubMed2004

Mapping topics and topic bursts in PNAS.

Scientific research is highly dynamic. New areas of science continually evolve; others gain or lose importance, merge, or split. Due to the steady increase in the number of scientific publications, it is hard to keep an overview of the structure and dynamic development of one's own field of science, much less all scientific domains. However, knowledge of "hot" topics, emergent research frontiers, or change of focus in certain areas is a critical component of resource allocation decisions in research laboratories, governmental institutions, and corporations. This paper demonstrates the utilization of Kleinberg's burst detection algorithm, co-word occurrence analysis, and graph layout techniques to generate maps that support the identification of major research topics and trends. The approach was applied to analyze and map the complete set of papers published in PNAS in the years 1982-2001. Six domain experts examined and commented on the resulting maps in an attempt to reconstruct the evolution of major research areas covered by PNAS.

Algorithms↗

PubMed2000

Molecular evolution of catalysis.

In this paper, we consider the evolutionary dynamics of catalytically active species with a distinct genotype-phenotype relationship. Folding landscapes of RNA molecules serve as a paradigm for this relationship with essential neutral properties. The landscape itself is partitioned by phenotypes (realized as RNA secondary structures). To each genotype (represented as a sequence) a structure is assigned in a unique way. The set of all sequences which map into a particular structure is modeled as a random graph in sequence space (the so-called neutral network). A catalytic network is realized as a random digraph with maximal out-degree two and secondary structures as vertex sets. A population of catalytic RNA molecules shows significantly different behavior compared to a deterministic description: hypercycles are able to co-exist and out-compete a parasite with superior catalytic support. A "switching" between different dynamic organizations of the network can be observed, dynamical stability of hypercyclic organizations against errors and the existence of an error-threshold of catalysis can be reported.

Animals↗

PubMed2005

Supervised nonlinear dimensionality reduction for visualization and classification.

When performing visualization and classification, people often confront the problem of dimensionality reduction. Isomap is one of the most promising nonlinear dimensionality reduction techniques. However, when Isomap is applied to real-world data, it shows some limitations, such as being sensitive to noise. In this paper, an improved version of Isomap, namely S-Isomap, is proposed. S-Isomap utilizes class information to guide the procedure of nonlinear dimensionality reduction. Such a kind of procedure is called supervised nonlinear dimensionality reduction. In S-Isomap, the neighborhood graph of the input data is constructed according to a certain kind of dissimilarity between data points, which is specially designed to integrate the class information. The dissimilarity has several good properties which help to discover the true neighborhood of the data and, thus, makes S-Isomap a robust technique for both visualization and classification, especially for real-world problems. In the visualization experiments, S-Isomap is compared with Isomap, LLE, and WeightedIso. The results show that S-Isomap performs the best. In the classification experiments, S-Isomap is used as a preprocess of classification and compared with Isomap, WeightedIso, as well as some other well-established classification methods, including the K-nearest neighbor classifier, BP neural network, J4.8 decision tree, and SVM. The results reveal that S-Isomap excels compared to Isomap and WeightedIso in classification, and it is highly competitive with those well-known classification methods.

Algorithms↗

PubMed2004

Linear response algorithms for approximate inference in graphical models.

Belief propagation (BP) on cyclic graphs is an efficient algorithm for computing approximate marginal probability distributions over single nodes and neighboring nodes in the graph. However, it does not prescribe a way to compute joint distributions over pairs of distant nodes in the graph. In this article, we propose two new algorithms for approximating these pairwise probabilities, based on the linear response theorem. The first is a propagation algorithm that is shown to converge if BP converges to a stable fixed point. The second algorithm is based on matrix inversion. Applying these ideas to gaussian random fields, we derive a propagation algorithm for computing the inverse of a matrix.

Algorithms↗

PubMed2004

On the limit cycle structure of threshold boolean networks over complete graphs.

In previous work, the limit structure of positive and negative finite threshold boolean networks without inputs (TBNs) over the complete digraph K(n) was analyzed and an algorithm was presented for computing this structure in polynomial time. Those results are generalized in this paper to cover the case of arbitrary TBNs over K(n). Although the limit structure is now more complicated, containing, not only fixed-points and cycles of length 2, but possibly also cycles of arbitrary length, a simple algorithm is still available for its determination in polynomial time. Finally, the algorithm is generalized to cover the case of symmetric finite boolean networks over K(n).

Algorithms↗

PubMed2001

Topological properties of citation and metabolic networks.

Topological properties of "scale-free" networks are investigated by determining their spectral dimensions d(S), which reflect a diffusion process in the corresponding graphs. Data bases for citation networks and metabolic networks together with simulation results from the growing network model [A.-L. Barabasi and R. Albert, Science 286, 509 (1999)] are probed. For completeness and comparisons lattice, random and small-world models are also investigated. We find that d(S) is around 3 for citation and metabolic networks, which is significantly different from the growing network model, for which d(S) is approximately 7.5. This signals a substantial difference in network topology despite the observed similarities in vertex-order distributions. In addition, the diffusion analysis indicates that the citation networks are treelike in structure, whereas the metabolic networks contain many loops.

Animals↗

PubMed2003

Network landscape from a Brownian particle's perspective.

Given a complex biological or social network, how many clusters should it be decomposed into? We define the distance d(i,j) from node i to node j as the average number of steps a Brownian particle takes to reach j from i. Node j is a global attractor of i if d(i,j)< or =d(i,k) for any k of the graph; it is a local attractor of i if j in E(i) (the set of nearest neighbors of i) and d(i,j)< or =d(i,l) for any l in E(i). Based on the intuition that each node should have a high probability to be in the same community as its global (local) attractor on the global (local) scale, we present a simple method to uncover a network's community structure. This method is applied to several real networks and some discussion on its possible extensions is made.

Algorithms↗

PubMed2003

On the structural complexity of a protein.

The determination of the configuration of a protein in three-dimensional (3D) space constitutes one of the major challenges in molecular biology research today. A method consists in choosing a protein structure from a database that minimizes an energy function. First, we model the problem in terms of dynamic programming and show that the determination of the order in which the variables must be considered to minimize the time complexity is an NP-hard problem. Second, we propose a new decomposition algorithm of the threading problem that is based on the connectivity of the graph induced by the 3D structure of a protein. Our decomposition could be used to solve the threading problem. The goal in this paper is to evaluate the intrinsic complexity of 3D structure, which can be viewed as information that may be incorporated into a solution method. It provides two indexes of complexity (time and space) and determines in polynomial time complex components of the 3D structure of a protein.

Algorithms↗

PubMed2005

Estimation and marginalization using the Kikuchi approximation methods.

In this letter, we examine a general method of approximation, known as the Kikuchi approximation method, for finding the marginals of a product distribution, as well as the corresponding partition function. The Kikuchi approximation method defines a certain constrained optimization problem, called the Kikuchi problem, and treats its stationary points as approximations to the desired marginals. We show how to associate a graph to any Kikuchi problem and describe a class of local message-passing algorithms along the edges of any such graph, which attempt to find the solutions to the problem. Implementation of these algorithms on graphs with fewer edges requires fewer operations in each iteration. We therefore characterize minimal graphs for a Kikuchi problem, which are those with the minimum number of edges. We show with empirical results that these simpler algorithms often offer significant savings in computational complexity, without suffering a loss in the convergence rate. We give conditions for the convexity of a given Kikuchi problem and the exactness of the approximations in terms of the loops of the minimal graph. More precisely, we show that if the minimal graph is cycle free, then the Kikuchi approximation method is exact, and the converse is also true generically. Together with the fact that in the cycle-free case, the iterative algorithms are equivalent to the well-known belief propagation algorithm, our results imply that, generically, the Kikuchi approximation method can be exact if and only if traditional junction tree methods could also solve the problem exactly.

Algorithms↗

PubMed2006

Probabilistic models of cognition: conceptual foundations.

Remarkable progress in the mathematics and computer science of probability has led to a revolution in the scope of probabilistic models. In particular, 'sophisticated' probabilistic methods apply to structured relational systems such as graphs and grammars, of immediate relevance to the cognitive sciences. This Special Issue outlines progress in this rapidly developing field, which provides a potentially unifying perspective across a wide range of domains and levels of explanation. Here, we introduce the historical and conceptual foundations of the approach, explore how the approach relates to studies of explicit probabilistic reasoning, and give a brief overview of the field as it stands today.

Algorithms↗

PubMed1999

Variable selection and multivariate methods for the identification of microorganisms by flow cytometry.

BACKGROUND: When exploited fully, flow cytometry can be used to provide multiparametric data for each cell in the sample of interest. While this makes flow cytometry a powerful technique for discriminating between different cell types, the data can be difficult to interpret. Traditionally, dual-parameter plots are used to visualize flow cytometric data, and for a data set consisting of seven parameters, one should examine 21 of these plots. A more efficient method is to reduce the dimensionality of the data (e.g., using unsupervised methods such as principal components analysis) so that fewer graphs need to be examined, or to use supervised multivariate data analysis methods to give a prediction of the identity of the analyzed particles. MATERIALS AND METHODS: We collected multiparametric data sets for microbiological samples stained with six cocktails of fluorescent stains. Multivariate data analysis methods were explored as a means of microbial detection and identification. RESULTS: We show that while all cocktails and all methods gave good accuracy of predictions (>94%), careful selection of both the stains and the analysis method could improve this figure (to > 99% accuracy), even in a data set that was not used in the formation of the supervised multivariate calibration model. CONCLUSIONS: Flow cytometry provides a rapid method of obtaining multiparametric data for distinguishing between microorganisms. Multivariate data analysis methods have an important role to play in extracting the information from the data obtained. Artificial neural networks proved to be the most suitable method of data analysis.

Bacillus subtilis↗

PubMed2002

Curvature of co-links uncovers hidden thematic layers in the World Wide Web.

Beyond the information stored in pages of the World Wide Web, novel types of "meta-information" are created when pages connect to each other. Such meta-information is a collective effect of independent agents writing and linking pages, hidden from the casual user. Accessing it and understanding the interrelation between connectivity and content in the World Wide Web is a challenging problem [Botafogo, R. A. & Shneiderman, B. (1991) in Proceedings of Hypertext (Assoc. Comput. Mach., New York), pp. 63-77 and Albert, R. & Barabási, A.-L. (2002) Rev. Mod. Phys. 74, 47-97]. We demonstrate here how thematic relationships can be located precisely by looking only at the graph of hyperlinks, gleaning content and context from the Web without having to read what is in the pages. We begin by noting that reciprocal links (co-links) between pages signal a mutual recognition of authors and then focus on triangles containing such links, because triangles indicate a transitive relation. The importance of triangles is quantified by the clustering coefficient [Watts, D. J. & Strogatz, S. H. (1999) Nature (London) 393, 440-442], which we interpret as a curvature [Bridson, M. R. & Haefliger, A. (1999) Metric Spaces of Non-Positive Curvature (Springer, Berlin)]. This curvature defines a World Wide Web landscape whose connected regions of high curvature characterize a common topic. We show experimentally that reciprocity and curvature, when combined, accurately capture this meta-information for a wide variety of topics. As an example of future directions we analyze the neural network of Caenorhabditis elegans, using the same methods.

Animals↗

PubMed1995

Synaptic feedback excitation has hypothalamic neural networks generate quasirhythmic burst activity.

1. Dissociated neurons from embryonic rat hypothalamus form synaptically coupled networks when cultured for several weeks. When synaptic inhibition is suppressed by the gamma-aminobutyric acid-A (GABAA) antagonist picrotoxin, neurons exhibit "rhythmic" burst activity that is blocked by the glutamate receptor antagonist 6-cyano-7-nitroquinoxaline-2,3-dione (CNQX). 2. We have examined whether this type of activity is generated by pacemaker cells driving follower cells synaptically or whether it is generated by a neuronal network through feedback excitation by Ca2+ imaging of Fura-2/AM-loaded neurons and single-cell recording. 3. IN the presence of the GABAA antagonist picrotoxin (20 microM), a large majority of neurons (> 85%) displayed quasirhythmic increases in intracellular concentration of Ca2+ ([Ca2+]i). Single-cell recording revealed that these increases in [Ca2+]i correspond to burst discharges in individual neurons. When excitatory synaptic transmission was blocked by CNQX (20 microM), none of the imaged neurons exhibited significant oscillations in [Ca2+]i. 4. Investigation of the intervals between bursts from single-cell recording revealed a random distribution over a range of 400% from the minimum interval. Poincaré maps of burst intervals, i.e., graphs of all burst intervals versus their preceding burst interval, revealed that a burst interval is unpredictable from its predecessor. 5. When synaptic coupling was attenuated by low concentrations of CNQX (50-500 nM), the mean burst interval was considerably increased without a change in the random character of burst activity. 4-Aminopyridine (1 mM), known to increase synaptic efficiency, reduced the mean burst interval.(ABSTRACT TRUNCATED AT 250 WORDS)

6-Cyano-7-nitroquinoxaline-2,3-dione↗

PubMed2003

Some asymptotic properties of duplication graphs.

Duplication graphs are graphs that grow by duplication of existing vertices, and are important models of biological networks, including protein-protein interaction networks and gene regulatory networks. Three models of graph growth are studied: pure duplication growth, and two two-parameter models in which duplication forms one element of the growth dynamics. A power-law degree distribution is found to emerge in all three models. However, the parameter space of the latter two models is characterized by a range of parameter values for which duplication is the predominant mechanism of graph growth. For parameter values that lie in this "duplication-dominated" regime, it is shown that the degree distribution either approaches zero asymptotically, or approaches a nonzero power-law degree distribution very slowly. In either case, the approach to the true asymptotic degree distribution is characterized by a dependence of the scaling exponent on properties of the initial degree distribution. It is therefore conjectured that duplication-dominated, scale-free networks may contain identifiable remnants of their early structure. This feature is inherited from the idealized model of pure duplication growth, for which the exact finite-size degree distribution is found and its asymptotic properties studied.

Models, Statistical↗

PubMed2006

Payoff-monotonic game dynamics and the maximum clique problem.

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.

Journal Article↗

PubMed1999

Propagating distributions up directed acyclic graphs.

In a previous article, we considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given position, we described how to build a model of uncertainty and use it for utility-directed growth of the search tree and for deciding on a move after search was completed. In some games, such as chess and Othello, the same position can occur more than once, collapsing the game tree to a directed acyclic graph (DAG). This induces correlations among the distributions at sibling nodes. This article discusses some issues that arise in extending our algorithms to a DAG. We give a simply described algorithm for correctly propagating distributions up a game DAG, taking account of dependencies induced by the DAG structure. This algorithm is exponential time in the worst case. We prove that it is #P complete to propagate distributions up a game DAG correctly. We suggest how our exact propagation algorithm can yield a fast but inexact heuristic.

Algorithms↗

PubMed1999

Revealing hidden interval graph structure in STS-content data.

MOTIVATION: STS-content data for genomic mapping contain numerous errors and anomalies resulting in cross-links among distant regions of the genome. Identification of contigs within the data is an important and difficult problem. RESULTS: This paper introduces a graph algorithm which creates a simplified view of STS-content data. The shape of the resulting structure graph provides a quality check - coherent data produce a straight line, while anomalous data produce branches and loops. In the latter case, it is sometimes possible to disentangle the various paths into subsets of the data covering contiguous regions of the genome, i.e. contigs. These straight subgraphs can then be analyzed in standard ways to construct a physical map. A theoretical basis for the method is presented along with examples of its application to current STS data from human genome centers. AVAILABILITY: Freely available on request.

Algorithms↗