Algraeph User Manual

Contents

1. Contents
2. Summary
3. Quick start
4. Introduction
5. Using Algraeph
6. Creating your own graphbanks and parallel graph corpora
7. Reference

Summary

Algraeph is a tool to manually align linguistic graphs, such as phrase structure trees or dependency graphs, where each node corresponds to a subsequence of the analyzed input sentence. It allows you to express the similarity between two graphs by aligning their nodes and attaching relation labels to these aligments.

Graphs are read from one or more graphbanks (or treebanks). Algraeph currently supports graphs in the general GraphML format and in the Alpino format (for Dutch). Alignment relations are user-defined. The alignments are stored in a simple XML format, which can be used for further processing. The result - a parallel graph corpus - is a useful data set for many tasks in computational linguistics and natural language processing such as automatic summarization, automatic translation, paraphrase extraction, recognizing textual entailment, etc. The DAESO library provides support for creating, processing and exploiting such aligned parallel corpora.

Algraeph is implemented in the Python programming language using the wxPython GUI toolkit. It has been tested on Mac OS X, GNU Linux and MS Windows, but should run on any platform which is supported by Python, wxPython and Graphviz.

Quick start

So you managed to install Algraeph and now you are in hurry to see if this is of any use to you? Sounds familiar :-) Try this:

• Start Algraeph by double clicking the program icon or typing "algraeph.py" at the command line.
• From the "File" menu, choose "Open", go to the "data/graphml/simple" directory included in the Algraeph distribution, and open the file "algraeph-simple-alignment.xml". After loading, the middle of the Algraeph window contains two simple phrase structure trees. The tree on the left is for the English phrase "spam and eggs"; the tree on the right is for the Dutch translation "smac en eieren". These full phrases are shown in the text boxes at the top. Aligned nodes, as indicate by green lines, are translations of each other.
• From the "View" menu, choose "Mark Selected Nodes".
• Again from the "View" menu, choose "Mark Selected Alignment."
• Click on the node labeled "spam" in the left tree. The selected node and its alignment are shown in yellow. The token sequence corresponding to the selected node ("spam") is shown in the text box in the left bottom. The alignment relation, which is simply "equals" here, is shown in between.
• Now click on the corresponding node "smac" in the right tree. Observe that the token sequence corresponding to this node ("spam") is shown in the text box in the right bottom, and that the relation has changed from "none" to "equals".
• Click on the radio button "none" to remove the alignment, and on "equals" to reestablish it.
• Now align the nodes "spam" and "eieren". As you can see, any existing alignments of the nodes involved are automatically removed, because by default only one-to-one alignment are allowed.
• So far, so good. Suggested continuations are:
  • Explore the other options (e.g. "Fold Node") in the View menu, which are also accessible from a popup menu by right clicking on a node.
  • Look at the next graph by choosing "Next" from the "Go" menu (or using the keyb board shortcut), and load any of the other examples in de "data" directory.
  • Open the file "simple-english-graphbank.xml" in a text editor and have a look at a graphbank in GraphML format.
  • Open the file "algraeph-simple-alignment.xml" in a text editor to see how the alignments are stored in a straight-forward XML format.
  • Read the rest of the manual (when it is finished ;-).

Introduction

...

Using Algraeph

This section explains how to use Algraeph for manually aligning graphs.

...

Folding: When folding a node, all successors nodes are hidden, the folded node is marked by a black rectangle and the menu item becomes checked. When unfolding a node, all successors nodes are revealed, the black rectangle mark is removed, and the menu item becomes unchecked.

Creating your own graphbanks and parallel graph corpora

This section explains how to create your own input for Algraeph in the form of graphbanks and a parallel graph corpus. You can create your own XML files, but we recommend using the Daeso Framework Python library, which provides a convenient API for creating, reading, manipulating and writing parallel graph corpora.

Your own graphbanks

Algraeph supports the general GraphML format. I suggest to have a look at the GraphML Primer, and at examples in the included "data/graphml" directory.

Notice however that there are a few additional requirements on top of those defined by the GraphML Schema/DTD:

1. Every node must have a "tokens" attribute which defines the token subsequences displayed in the text boxes at the bottom when a node is selected. In GraphML format, "tokens" is not a direct XML attribute of the "node" element, but character data contained in an embedded "data" element.
2. Similarly, every graph must have a "tokens" attribute which defines the tokens displayed in the text boxes at the top of the window.
3. Every graph must have a "root" attribute which defines a unique root node.
4. Every node must have a "label" attribute.
5. Edges may have a "label" attribute.
6. These GraphML attributes must be appropriately defined by means of a "key" element.

A minimal example is presented below:

<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns" 
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">

  <key id="label" for="node" attr.name="label" attr.type="string"/>
  <key id="tokens" attr.name="tokens" attr.type="string"/>
  <key id="root" for="graph" attr.name="root" attr.type="string"/>
  
  <graph id="g0" edgedefault="directed">  
    <data key="tokens">spam and eggs</data>
    <data key="root">n0</data>
    
    <node id="n0">
      <data key="label">and</data>
      <data key="tokens">spam and eggs</data>
    </node>
    <node id="n1">
      <data key="label">spam</data>
      <data key="tokens">spam</data>
    </node>
    <node id="n2">
      <data key="label">eggs</data>
      <data key="tokens">eggs</data>
    </node>
    
    <edge source="n0" target="n1"/>
    <edge source="n0" target="n2"/>
    
  </graph>
</graphml>

Your own parallel graph corpora

Algraeph represents a parallel graph corpus in a straight-forward XML format. If you want to use Algraeoh to annotate your own data, you will have to create your own parallel graph corpus in this format, either by hand or by program. The following is a minimal example of a parallel graph corpus:

<?xml version="1.0" encoding="utf-8"?>
<parallel_graph_corpus>
  <corpus_meta_data>
    <comment>simple alignment example</comment>
  </corpus_meta_data>
  <graphbanks>
    <file id="1" format="graphml">simple-english-graphbank.xml</file>
    <file id="2" format="graphml">simple-dutch-graphbank.xml</file>
  </graphbanks>
  <node_relations>
    <relation>equals</relation>
  </node_relations>
  <aligned_graphs>
    <graph_pair from_bank_id="1" from_graph_id="g0" to_bank_id="2" to_graph_id="g0">
      <aligned_nodes>
        <node_pair from_node_id="n0" relation="equals" to_node_id="n0"/>
        <node_pair from_node_id="n1" relation="equals" to_node_id="n1"/>
        <node_pair from_node_id="n2" relation="equals" to_node_id="n2"/>
      </aligned_nodes>
      <graph_meta_data>
        <comment>From the "Spam" sketch by Monty Python.</comment>
      </graph_meta_data>
    </graph_pair>
  </aligned_graphs>
</parallel_graph_corpus>

The XML elements are explained in the following table:

Reference

This section contains reference information an all available menus and key board shortcuts.

View Menu