Automated Program Recognition by Graph Parsing

Recognizing standard computational structures (cliches) in a program can help an experienced programmer understand the program. We develop a graph parsing approach to automating program recognition in which programs and cliches are represented in an attributed graph grammar formalism and recognition is achieved by graph parsing. In studying this approach, we evaluate our representation's ability to suppress many common forms of variation which hinder recognition. We investigate the expressiveness of our graph grammar formalism for capturing programming cliches. We empirically and analytically study the computational cost of our recognition approach with respect to two medium-sized, real-world simulator programs.

The Use of Graph Grammars for Model-based Reasoning in Diagnostic Expert Systems

Flasinski M. and Lee M.H., The Use of Graph Grammars for Model-based Reasoning in Diagnostic Expert Systems, Prace Informatyczne, Zeszyty Naukowe Uniwersytetu Jagiellonskiego, 9, 1999, pp147-165.

An Hysteresis-Habituation mechanism for Sensorimotor Scaffolding

R. Gunstone and M.H. Lee ?An Hysteresis-Habituation Mechanism for Sensorimotor Scaffolding?, Proc. AISB?03 Second International Symposium on Imitation in Animals and Artifacts, 189-190, 2003.

Dynamical Systems in the Sensorimotor Loop: On the Interrelation Between Internal and External Mechanisms of Evolved Robot Behavior

Huelse, M., Wischmann, S., Manoonpong, P., Twickel, A.v., Pasemann, F.: Dynamical Systems in the Sensorimotor Loop: On the Interrelation Between Internal and External Mechanisms of Evolved Robot Behavior. In: M. Lungarella, F. Iida, J. Bongard, R. Pfeifer (Eds.) 50 Years of Artificial Intelligence, LNCS 4850, Springer, 186 - 195, 2007.

ROSSI: Emergence of communication in Robots through Sensorimotor and Social Interaction

ROSSI: Emergence of communication in Robots through Sensorimotor and Social Interaction, T. Ziemke, A. Borghi, F. Anelli, C. Gianelli, F. Binkovski, G. Buccino, V. Gallese, M. Huelse, M. Lee, R. Nicoletti, D. Parisi, L. Riggio, A. Tessari, E. Sahin, International Conference on Cognitive Systems (CogSys 2008), University of Karlsruhe, Karlsruhe, Germany, 2008 Sponsorship: EU-FP7

Graph Wavelets for Spatial Traffic Analysis

A number of problems in network operations and engineering call for new methods of traffic analysis. While most existing traffic analysis methods are fundamentally temporal, there is a clear need for the analysis of traffic across multiple network links — that is, for spatial traffic analysis. In this paper we give examples of problems that can be addressed via spatial traffic analysis. We then propose a formal approach to spatial traffic analysis based on the wavelet transform. Our approach (graph wavelets) generalizes the traditional wavelet transform so that it can be applied to data elements connected via an arbitrary graph topology. We explore the necessary and desirable properties of this approach and consider some of its possible realizations. We then apply graph wavelets to measurements from an operating network. Our results show that graph wavelets are very useful for our motivating problems; for example, they can be used to form highly summarized views of an entire network's traffic load, to gain insight into a network's global traffic response to a link failure, and to localize the extent of a failure event within the network.

Isoperimetric Graph Partitioning for Data Clustering and Image Segmentation

Spectral methods of graph partitioning have been shown to provide a powerful approach to the image segmentation problem. In this paper, we adopt a different approach, based on estimating the isoperimetric constant of an image graph. Our algorithm produces the high quality segmentations and data clustering of spectral methods, but with improved speed and stability.

Isoperimetric Partitioning: A New Algorithm for Graph Partitioning

Temporal structure is skilled, fluent action exists at several nested levels. At the largest scale considered here, short sequences of actions that are planned collectively in prefronatal cortex appear to be queued for performance by a cyclic competitive process that operates in concert with a parallel analog representation that implicitly specifies the relative priority of elements of the sequence. At an intermediate scale, single acts, like reaching to grasp, depend on coordinated scaling of the rates at which many muscles shorten or lengthen in parallel. To ensure success of acts such as catching an approaching ball, such parallel rate scaling, which appears to be one function of the basal ganglia, must be coupled to perceptual variables such as time-to-contact. At a finer scale, within each act, desired rate scaling can be realized only if precisely timed muscle activations first accelerate and then decelerate the limbs, to ensure that muscle length changes do not under- or over- shoot the amounts needed for precise acts. Each context of action may require a different timed muscle activation pattern than similar contexts. Because context differences that require different treatment cannot be known in advance, a formidable adaptive engine-the cerebellum-is needed to amplify differences within, and continuosly search, a vast parallel signal flow, in order to discover contextual "leading indicators" of when to generate distinctive patterns of analog signals. From some parts of the cerebellum, such signals control muscles. But a recent model shows how the lateral cerebellum may serve the competitive queuing system (frontal cortex) as a repository of quickly accessed long-term sequence memories. Thus different parts of the cerebellum may use the same adaptive engine design to serve the lowest and highest of the three levels of temporal structure treated. If so, no one-to-one mapping exists between leveels of temporal structure and major parts of the brain. Finally, recent data cast doubt on network-delay models of cerebellar adaptive timing.

The Graph Analysis Toolbox: Image Processing on Arbitrary Graphs

Office of Naval Research (N00014-01-1-0624)

Imaging Learned Song Representations in Populations of Sensorimotor Neurons Essential to Vocal Communication

Perceiving or producing complex vocalizations such as speech and birdsongs require the coordinated activity of neuronal populations, and these activity patterns can vary over space and time. How learned communication signals are represented by populations of sensorimotor neurons essential to vocal perception and production remains poorly understood. Using a combination of two-photon calcium imaging, intracellular electrophysiological recording and retrograde tracing methods in anesthetized adult male zebra finches (Taeniopygia guttata), I addressed how the bird's own song and its component syllables are represented by the spatiotemporal patterns of activity of two spatially intermingled populations of projection neurons (PNs) in HVC, a sensorimotor area required for song perception and production. These experiments revealed that neighboring PNs can respond at markedly different times to song playback and that different syllables activate spatially intermingled HVC PNs within a small region. Moreover, noise correlation analysis reveals enhanced functional connectivity between PNs that respond most strongly to the same syllable and also provides evidence of a spatial gradient of functional connectivity specific to PNs that project to song motor nucleus (i.e. HVC_RA cells). These findings support a model in which syllabic and temporal features of song are represented by spatially intermingled PNs functionally organized into cell- and syllable-type networks.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimization technique known as relative gain optimization which both balances the workload and attempts to minimize the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

A multilevel algorithm for force-directed graph drawing

We describe a heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm. The multilevel process groups vertices to form clusters, uses the clusters to define a new graph and is repeated until the graph size falls below some threshold. The coarsest graph is then given an initial layout and the layout is successively refined on all the graphs starting with the coarsest and ending with the original. In this way the multilevel algorithm both accelerates and gives a more global quality to the force- directed placement. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on a number of examples ranging from 500 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 30 seconds for a 10,000 vertex graph to around 10 minutes for the largest graph. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.