Unfolding kernel embeddings of graphs:enhancing class separation through manifold learning

In this paper, we investigate the use of manifold learning techniques to enhance the separation properties of standard graph kernels. The idea stems from the observation that when we perform multidimensional scaling on the distance matrices extracted from the kernels, the resulting data tends to be clustered along a curve that wraps around the embedding space, a behavior that suggests that long range distances are not estimated accurately, resulting in an increased curvature of the embedding space. Hence, we propose to use a number of manifold learning techniques to compute a low-dimensional embedding of the graphs in an attempt to unfold the embedding manifold, and increase the class separation. We perform an extensive experimental evaluation on a number of standard graph datasets using the shortest-path (Borgwardt and Kriegel, 2005), graphlet (Shervashidze et al., 2009), random walk (Kashima et al., 2003) and Weisfeiler-Lehman (Shervashidze et al., 2011) kernels. We observe the most significant improvement in the case of the graphlet kernel, which fits with the observation that neglecting the locational information of the substructures leads to a stronger curvature of the embedding manifold. On the other hand, the Weisfeiler-Lehman kernel partially mitigates the locality problem by using the node labels information, and thus does not clearly benefit from the manifold learning. Interestingly, our experiments also show that the unfolding of the space seems to reduce the performance gap between the examined kernels.

A quantum Jensen-Shannon graph kernel for unattributed graphs

In this paper, we use the quantum Jensen-Shannon divergence as a means of measuring the information theoretic dissimilarity of graphs and thus develop a novel graph kernel. In quantum mechanics, the quantum Jensen-Shannon divergence can be used to measure the dissimilarity of quantum systems specified in terms of their density matrices. We commence by computing the density matrix associated with a continuous-time quantum walk over each graph being compared. In particular, we adopt the closed form solution of the density matrix introduced in Rossi et al. (2013) [27,28] to reduce the computational complexity and to avoid the cumbersome task of simulating the quantum walk evolution explicitly. Next, we compare the mixed states represented by the density matrices using the quantum Jensen-Shannon divergence. With the quantum states for a pair of graphs described by their density matrices to hand, the quantum graph kernel between the pair of graphs is defined using the quantum Jensen-Shannon divergence between the graph density matrices. We evaluate the performance of our kernel on several standard graph datasets from both bioinformatics and computer vision. The experimental results demonstrate the effectiveness of the proposed quantum graph kernel.

An aligned subtree kernel for weighted graphs

In this paper, we develop a new entropic matching kernel for weighted graphs by aligning depth-based representations. We demonstrate that this kernel can be seen as an aligned subtree kernel that incorporates explicit subtree correspondences, and thus addresses the drawback of neglecting the relative locations between substructures that arises in the R-convolution kernels. Experiments on standard datasets demonstrate that our kernel can easily outperform state-of-the-art graph kernels in terms of classification accuracy.

On the k-anonymization of time-varying and multi-layer social graphs

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

A continuous-time quantum walk kernel for unattributed graphs

Kernel methods provide a way to apply a wide range of learning techniques to complex and structured data by shifting the representational problem from one of finding an embedding of the data to that of defining a positive semidefinite kernel. In this paper, we propose a novel kernel on unattributed graphs where the structure is characterized through the evolution of a continuous-time quantum walk. More precisely, given a pair of graphs, we create a derived structure whose degree of symmetry is maximum when the original graphs are isomorphic. With this new graph to hand, we compute the density operators of the quantum systems representing the evolutions of two suitably defined quantum walks. Finally, we define the kernel between the two original graphs as the quantum Jensen-Shannon divergence between these two density operators. The experimental evaluation shows the effectiveness of the proposed approach. © 2013 Springer-Verlag.

Information theoretic prototype selection for unattributed graphs

In this paper we propose a prototype size selection method for a set of sample graphs. Our first contribution is to show how approximate set coding can be extended from the vector to graph domain. With this framework to hand we show how prototype selection can be posed as optimizing the mutual information between two partitioned sets of sample graphs. We show how the resulting method can be used for prototype graph size selection. In our experiments, we apply our method to a real-world dataset and investigate its performance on prototype size selection tasks. © 2012 Springer-Verlag Berlin Heidelberg.

Dirac type condition and Hamiltonian graphs

2010 Mathematics Subject Classification: 05C38, 05C45.

On strongly regular graphs with m2 = qm3 and m3 = qm2

2010 Mathematics Subject Classification: 05C50.

Adversarial interpreting – a forensic linguistic perspective

Interactions with second language speakers in public service contexts in England are normally conducted with the assistance of one interpreter. Even in situations where team interpreting would be advisable, for example in lengthy courtroom proceedings, financial considerations mean only one interpreter is normally booked. On occasion, however, more than one interpreter, or an individual (or individuals) with knowledge of the languages in question, may be simultaneously present during an interpreted interaction, either monitoring it or indeed volunteering unsolicited input. During police interviews or trials in England this may happen when the interpreter secured by the defence team to interpret during private consultation with the suspect or defendant is present also in the interview room or the courtroom but two independently sourced interpreters need not be limited to legal contexts. In healthcare settings for example, service users sometimes bring friends or relatives along to help them communicate with service providers only to find that the latter have booked an interpreter as a matter of procedure. By analogy to the nature of the English legal system, I refer to contexts where an interpreter’s output is monitored and/or challenged, either during the speech event or subsequently, as ‘adversarial interpreting’. This conceptualisation reflects the fact that interpreters in such encounters are sourced independently, often by opposing parties, and as a result can rarely be considered a team. My main concern in this paper is to throw spotlight on adversarial interpreting as a hitherto rarely discussed problem in its own right. That it is not an anomaly is evidenced by the many cases around the world where the officially recorded interpreted output was challenged, as mentioned in for example Berk-Seligson (2002), Hayes and Hale (2010), and Phelan (2011). This paper reports on the second stage of a research project which has previously involved the analysis of a transcript of an interpreted police interview with a suspect in a murder case. I will mention the findings of the analysis briefly and introduce some new findings based on input from practising interpreters who have shared their experience of adversarial interpreting by completing an online questionnaire. I will try to answer the question of how the presence of two interpreters, or an interpreter and a monitoring participant, in the same speech event impacts on the communication process. I will also address the issue of forensic linguistic arbitration in cases where incompetent interpreting has been identified or an expert opinion is sought in relation to an adversarial interpreting event of significance to a legal dispute. References Berk-Seligson (2002), The Bilingual Courtroom: Court Interpreters in the Judicial Process, University of Chicago Press. Hayes, A. and Hale, S. (2010), "Appeals on incompetent interpreting", Journal of Judicial Administration 20.2, 119-130. Phelan, M. (2011), "Legal Interpreters in the news in Ireland", Translation and Interpreting 3.1, 76-105.

Translation, transcription, interpreting?

In this talk I discuss some of the problems involved in the transcription and translation of poor quality and/or covertly made recordings. My focus is on how Speech Act Theory can help inform transcription practice. I argue that transcribers should have a good understanding of the pragmatic level of language communication; I illustrate with real case examples how the lack of this understanding can lead to flawed interpretations (and thus potentially miscarriages of justice). I also discuss the problems inherent in forensic translation, where, given the evidential status of the material being translated, the translator’s linguistic choices are often circumscribed by elements of the legal context s/he may not be familiar with.

Ranked search on data graphs

Graph-structured databases are widely prevalent, and the problem of effective search and retrieval from such graphs has been receiving much attention recently. For example, the Web can be naturally viewed as a graph. Likewise, a relational database can be viewed as a graph where tuples are modeled as vertices connected via foreign-key relationships. Keyword search querying has emerged as one of the most effective paradigms for information discovery, especially over HTML documents in the World Wide Web. One of the key advantages of keyword search querying is its simplicity—users do not have to learn a complex query language, and can issue queries without any prior knowledge about the structure of the underlying data. The purpose of this dissertation was to develop techniques for user-friendly, high quality and efficient searching of graph structured databases. Several ranked search methods on data graphs have been studied in the recent years. Given a top-k keyword search query on a graph and some ranking criteria, a keyword proximity search finds the top-k answers where each answer is a substructure of the graph containing all query keywords, which illustrates the relationship between the keyword present in the graph. We applied keyword proximity search on the web and the page graph of web documents to find top-k answers that satisfy user’s information need and increase user satisfaction. Another effective ranking mechanism applied on data graphs is the authority flow based ranking mechanism. Given a top- k keyword search query on a graph, an authority-flow based search finds the top-k answers where each answer is a node in the graph ranked according to its relevance and importance to the query. We developed techniques that improved the authority flow based search on data graphs by creating a framework to explain and reformulate them taking in to consideration user preferences and feedback. We also applied the proposed graph search techniques for Information Discovery over biological databases. Our algorithms were experimentally evaluated for performance and quality. The quality of our method was compared to current approaches by using user surveys.

How Do Tourist Guides Add Value to An Ecotour? Interpreting Interpretation in the State of Amazonas, Brazil

In Ecotourism, interpretation by a guide creates or shapes the experience for the tourist, differentiating one episode from another. As such, the guide S interpretation adds value to the tourism product and contributes to the visitor S experience. This paper discussed the role of interpretation by guides in the State of Amazonas, Brazil, finding in them patterns from which lessons may be drawn. Given the intangibility of the Ecotourism product, this paper argues that it is the guide who defines the quality of the product. The guide may draw the tourist toward or away from sustainable practices, and significantly contributes to the success or failure of the escotouristic venture. The State of Amazonas in Brazil already has guides, but this study questions their education and training in interpretive skills as well as their professional organization and working conditions

Re -"interpreting" the conquest: European and Amerindian translators and go -betweens in the colonization of the Americas, 1492--1675

This dissertation aims to recover the lives and careers of those Amerindians and Europeans who voluntarily or involuntarily took on the role of intercultural interpreters in the contact, conquest, and early colonial period in the Americas between 1492 and 1675. It intends to prove that these so-called “marginal” figures assumed roles that went far beyond those of linguistic and cultural translators, and often had a decisive impact on early Indian-colonial relations. ^ In the course of my research, I consulted hundreds of published sixteenth- and seventeenth-century chronicles, narratives, and memoirs in my search for references to interpreters. I augmented these accounts with information derived from unpublished archival documents, drawn primarily from the Archivo General de Indias, in Seville, Spain. ^ I organized my findings in theme-driven chapters that begin with a consideration of the historiography of that subject. Each chapter is further subdivided into chronologically-arranged historical vignettes that focus on the interpreters who mediated between the Spanish, Portuguese, French, English and Dutch and the various Native American polities and cultures. ^ I found that colonial authorities and Amerindian communities alike recognized the absolute necessity of recruiting competent and loyal interpreters and go-betweens, and that both sides tried to secure their loyal service by means both fair and foul. Although pressured, pushed, and pulled in contrary directions, most interpreters recognized the pivotal position they held in cross-cultural negotiations and rarely remained passive pawns in the contests between the forces of domination and defense. ^ All across the Americas, interpreters used their linguistic and diplomatic skills, and their intimate knowledge of the “other” not simply to facilitate conquest or spearhead the opposition, but to transform themselves from “culture brokers” into “power brokers.” Many of the decisive events that shaped colonial-Indian relations turned on the actions of these culturally-ambiguous individuals, a fact bemoaned and begrudgingly acknowledged by most of the contemporary conquistadors, chroniclers, and colonial founders, and recognized by this author. ^

Effects of real -time captioning and sign language interpreting on the learning of college students who are deaf or hard of hearing

College personnel are required to provide accommodations for students who are deaf and hard of hearing (D/HoH), but few empirical studies have been conducted on D/HoH students as they learn under the various accommodation conditions (sign language interpreting, SLI, real-time captioning, RTC, and both). Guided by the experiences of students who are D/HoH at Miami-Dade College (MDC) who requested RTC in addition to SLI as accommodations, the researcher adopted Merten’s transformative-emancipatory theoretical framework that values perceptions and voice of students who are D/HoH. A mixed methods design addressed two research questions: Did student learning differ for each accommodation? What did students experience while learning through accommodations? Participants included 30 students who were D/HoH (60% women). They represented MDC’s majority minority population: 10% White (non-Hispanic), 20% Black (non-Hispanic, including Haitian/Caribbean), 67% Hispanic, and 3% other. Hearing loss, ranged from severe-profound (70%) to mild-moderate (30%). All were able to communicate with American Sign Language: Learning was measured while students who were D/HoH viewed three lectures under three accommodation conditions (SLI, RTC, SLI+RTC). The learning measure was defined as the difference in pre- and post-test scores on tests of the content presented in the lectures. Using repeated measure ANOVA and ANCOVA, confounding variables of fluency in American Sign Language and literacy skills were treated as covariates. Perceptions were obtained through interviews and verbal protocol analysis that were signed, videotaped, transcribed, coded, and examined for common themes and metacognitive strategies. No statistically significant differences were found among the three accommodations on the learning measure. Students who were D/HoH expressed thoughts about five different aspects of their learning while they viewed lectures: (a) comprehending the information, (b) feeling a part of the classroom environment, (c) past experiences with an accommodation, (d) individual preferences for an accommodation, (e) suggestions for improving an accommodation. They exhibited three metacognitive strategies: (a) constructing knowledge, (b) monitoring comprehension, and (c) evaluating information. No patterns were found in the types of metacognitive strategies used for any particular accommodation. The researcher offers recommendations for flexible applications of the standard accommodations used with students who are D/HoH.

História da matemática e teatro nas aulas sobre Teorema de Tales: um script proposto

This study will present the results of an investigation of how the history of mathematics and theater can contribute to the construction of mathematical knowledge of students in the 9th year of elementary school, through the experience, preparation and execution of a play, beyond presentation of the script. This brings a historical approach, defining space and time of events, putting the reader and viewer to do the route in the biography of Thales of Miletus (624-546 a.C), creating situations that led to the study and discussion of the content related to the episode possible to measure the height of the pyramid Khufu and the Theorem of Thales. That said, the pedagogical proposal implemented in this work was based on theoretical and methodological assumptions of the History of Mathematics and Theatre, drawing upon authors such as Mendes (2006), Miguel (1993), Gutierre (2010), Desgrandes (2011), Cabral (2012). Regarding the methodological procedures used qualitative research because it responds to particular issues, analyzing and interpreting the data generated in the research field. As methodological tools we have used participant observation, the questionnaire given to the students, field diary and dissertativos texts produced by students. The processing and analysis of data collected through the questionnaires were organized, classified and quantified in tables and graphs for easy viewing, interpretation, understanding and analysis of data. Data analysis corroborated our hypothesis and contributed to improving the use and display of the play as a motivating activity in mathematics classrooms. Thus, we consider that the script developed, ie the educational product proposed will bring significant contributions to the teaching of Mathematics in Primary Education