BibSonomy publications for /user/diego_ma/graphsThu Feb 12 00:28:46 CET 2009Information Processing and Management135-41Using query expansion in graph-based approach for query-focused multi-document summarization.452009summarisation question_answering graphs This paper presents a novel query expansion method, which is combined in the graph-based algorithm for query-focused multi-document summarization, so as to resolve the problem of information limit in the original query. Our approach makes use of both the sentence-to-sentence relations and the sentence-to-word relations to select the query biased informative words from the document set and use them as query expansions to improve the sentence ranking result. Compared to previous query expansion approaches, our approach can capture more relevant information with less noise. We performed experiments on the data of document understanding conference (DUC) 2005 and DUC 2006, and the evaluation results show that the proposed query expansion method can significantly improve the system performance and make our system comparable to the state-of-the-art systems.Tue Feb 26 06:39:48 CET 2008CoRRinformal publicationMulti-document Summarization by Graph Search and Matchingcmp-lg/97120041997graphs summarisation We describe a new method for summarizing similarities and differences in a pair of related documents using a graph representation for text. Concepts denoted by words, phrases, and proper names in the document are represented positionally as nodes in the graph along with edges corresponding to semantic relations between items. Given a perspective in terms of which the pair of documents is to be summarized, the algorithm first uses a spreading activation technique to discover, in each document, nodes semantically related to the topic. The activated graphs of each document are then matched to yield a graph corresponding to similarities and differences between the pair, which is rendered in natural language. An evaluation of these techniques has been carried out.Wed Feb 06 06:48:51 CET 2008Proc. HLT/NAACL 2006 Workshop on Graph Algorithms for Natural Language Processing37-44Learning of Graph-based Question Answering Rules2006graphs AnswerFinder molla_publication In this paper we present a graph-based approach to question answering. The method assumes a graph representation of question sentences and text sentences. Question answering rules are automatically learnt from a training corpus of questions and answer sentences with the answer annotated. The method is independent from the graph representation formalism chosen. A particular example is presented that uses a specific graph representation of the logical contents of sentences.Tue Jan 29 07:21:22 CET 2008ZZZ-TREC14AnswerFinder at {TREC} 20052006AnswerFinder graphs molla_publication AnswerFinder has been completely redesigned for TREC 2005. The new architecture allows a fast development of question-answering systems for their deployment in the TREC tasks and other applications. The AnswerFinder modules use XML to express the services they provide, and they can be queried with XML for their services. The QA method now incorporates graph-based methods to compute the answerhood of a sentence and pin-point the answer. The system uses a set of graph-based rules that are learnt automatically. Unfortunately the system could not be completed and debugged before the TREC deadline and the runs did not fare well. Currently we are debugging and evaluating the system.Fri Dec 14 02:46:15 CET 2007Cognitive Psychology4532-631Conceptual Dependency: A Theory of Natural Language Understanding31972graphs NLP Fri Dec 14 02:45:26 CET 2007Semantic Information Processing216-270Semantic Memory1968graphs semantics Fri Dec 14 02:44:52 CET 2007Proceedings PASCAL RTE challenge 2005Textual Entailment as Syntactic Graph Distance: a rule based and a {SVM} based approach2005graphs entailment In this paper we define a measure for textual entailment recognition based on the \emph{graph matching theory} applied to syntactic graphs. We describe the experiments carried out to estimate measure's parameters with SVM and we report the results obtained on the Textual Entailment Challenge development and testing set.Fri Dec 14 02:44:23 CET 2007Journal of Experimentation and Theoretical Artificial Intelligence107-126Conceptual Graph Matching: a flexible algorithm and experiments41992graphs Graph matching is recognized as a central problem across a variety of application areas, and application-specific matchers have been developed with different simplifying assumptions to reduce computational complexity. Graph matching is viewed as a form of plausible reasoning when conceptual information contained in graphs are considered, and thus requires an underlying algorithm flexible and general enough to accommodate application-specific matching heuristics and schemes that determine the degree of plausibility. This paper presents such an algorithm, based on the notion of association graphs, developed for matching Sowa's conceptual graphs (CG). While the general subgraph isomorphism problem is known to be NP-complete, matching graphs containing conceptual information appears to be computationally tractable. Following the detailed description of the algorithm, some experimental results are shown to discuss the time complexity of the algorithm and its practicability.Fri Dec 14 02:43:29 CET 2007Proc. WWW05 workshop on Activities on Semantic Web Technologies in JapanSemantic-Structure-Based Search Engine2005inf_retrieval graphs logical_forms Our system represents the semantic structures of query and documents as graphs consisting of vertices as words and phrases and edges as dependency relations. Based on these semantic structures, the system provides the user with hints on how to revise his query. Preliminary experiments suggest that the system would reduce the user?s time and effort for retrieving suitable documents. We will present the overview of the system and its extension to deal with a large amount of data such as Web pages.Fri Dec 14 02:43:21 CET 2007Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics, companion volume (ACL 2004)Graph-based Ranking Algorithms for Sentence Extraction Applied to Text Summarization2004graphs summarisation This paper presents an innovative unsupervised method for automatic sentence extraction using graph-based ranking algorithms. We evaluate the method in the context of a text summarization task, and show that the results obtained compare favorably with previously published results on established benchmarks.Fri Dec 14 02:42:56 CET 2007Proc. Graph-Based Representations in Pattern Recognition (GbRPR)3434263-272LNCSFrom Exact to Approximate Maximum Common Subgraph2005graphs This paper presents an algorithm for the computation of the maximum common subgraph (MCS) between two directed, acyclic graphs with attributes. The core of the contribution resides in the modularity of the proposed algorithm which allows different heuristic techniques to be plugged in, depending on the application domain. Implemented heuristics for robust graph matching with respect to graph structural noise are discussed. As example of its effectiveness, the algortihm is applied to the problem of 3D shape similarity evaluation through structural shape descriptors.Fri Dec 14 02:41:47 CET 2007Software Practice and Experience591-607Common Subgraph Isomorphism Detection by Backtracking Search342004graphs common_subgraphs backtracking_algorithm Graph theory offers a convenient and highly attractive approach to various tasks of pattern recognition. Provided there is a graph representation of the object in question (e.g. a chemical structure or protein fold), the recognition procedure is reduced to the problem of common subgraph isomorphism (CSI). Complexity of this problem shows combinatorial dependence on the size of input graphs, which in many practical cases makes the approach computationally intractable. Among the optimal algorithms for CSI, the leading place in practice belongs to algorithms based on maximal clique detection in the association graph. Backtracking algorithms for CSI, first developed two decades ago, are rarely used. We propose an improved backtracking algorithm for CSI, which differs from its predecessors by better search strategy and is therefore more efficient. We found that the new algorithm outperforms the traditional maximal clique approach by orders of magnitude in computational time. Copyright � 2004 John Wiley & Sons, Ltd.Fri Dec 14 02:40:22 CET 2007Journal of Natural Language Processing43-31Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints132006graphs ambiguity DG Preference Dependency Grammar (PDG) is a framework for the morphological, syntactic and semantic analysis of natural language sentences, PDG gives packed shared data structures for emcompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence. This paper proposes the Graph Branch Algorithm for computing the optimum deptendenc tree ( the most plausible interpretation of a sentence) from a scored dependendency forest which is a packed shated data strucutre encompassing all possible dependency trees (interpretations) of a sentence. The graph branch algorithm adopts the branch and bound principle for managing arbitrary arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG. This paper also reports the espeiment using English texts showing the computational complexity and behavior of the graph branch algorithm.Fri Dec 14 02:36:52 CET 2007HeidelbergLecture Notes on Computer Science123-132A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs23962002graphs A graph $g$ is called a \emph{maximum common subgraph} of two graphs, $g_1$ and $g_2$, if there exists no other common subgraph of $g_1$ and $g_2$ that has more nodes than $g$. For the maximum common subgraph problem, exact and inexact algorithms are known from the literature. Nevertheless, until now no effort has been done for characterizing their performance. In this paper, two exact algorithms for maximum common subgraph detection are described. Moreover a database containing randomly connected pairs of graphs, having a maximum common graph of at least two nodes, is presented, and the performance of the two algorithms is evaluated on this database.