SGT^light is an implementation of a Spectral Graph Transducer (SGT) [Joachims, 2003] in C using Matlab libraries. The SGT is a method for transductive learning. It solves a normalized-cut (or ratio-cut) problem with additional constraints for the labeled examples using spectral methods. The approach is efficient enough to handle datasets with several ten-thousands of examples.

The program is free for scientific use. Please contact me, if you are planning to use the software for commercial purposes. The software must not be distributed without prior permission of the author. If you use SGT^light in your scientific work, please cite as

I would also appreciate, if you sent me (a link to) your papers so that I can learn about your research. The implementation was developed on Windows 2000 with mcc and Matlab R12, but compiles also on Linux and Solaris. The source code is available at the following location:

To compile and install the source code of SGT^light you need to download sgt_light.tar.gz. Unpack it with

You compile the source code with

which compiles all executables (type make info for additional options). Note that you have to have Matlab installed with the mcc compiler. You will have five executables:

To run the executables, you need the Matlab runtime library, which is available as the compressed archive mglinstaller. The runtime library is delivered with Matlab (see here). Copy mglinstaller into your sgt-light directory and call

To install one of the binary archives of SGT^light (e.g. sgt_light_solaris.tar.gz) you need to download it and unpack it with

To run the executables, you need the Matlab runtime libraries, which are included in the binary archive (also, see here for details on the Matlab libraries). Finally, you must extend your search path by executing

This section explains how to use the SGT^light software. The background is given in [Joachims, 2003].

SGT^light consists of three main modules and two additional programs for convenience. The main modules are, first, a program (sgt_buildknngraph) for constructing the k nearest neighbor graph from data in the form of feature vectors given in SVM^light format (see here). Second, a program (sgt_decompgraph) for computing the d smallest eigenvectors of the Laplacian of a graph, and third a module (sgt_predict) for computing the acutal predictions for a given training and test set. Furthermore, there is a program (sgt_traintestsplit) for computing a random test/training split and a program (sgt_addgraphs) for adding two adjacency matrices (used for co-training). 

You will find an example text classification problem at

Download this file into your sgt_light directory and unpack it with

The files example1/train.dat and example1/test.dat contain the train and test labels in the same order as in the file example1/examples.dat. +1 stands for a positive label, -1 stands for a negative label, and 0 for unlabeled. To compute the predictions for this training/test split, call

sgt_predict -c 1000 -l example1/test.dat example1/train.dat example1/graph.dcg example1/pred

Since the true test labels are given (-l example1/test.dat), the prediction accuracy on the test set is computed and printed to stdout. The trade-off between training error and complexity is set via -c 1000 similar to an SVM. The individual predictions on the training and test examples are output to example1/pred, in the same order as in the file example1/train.dat. A positive value indicates prediction as a positive example, a negative value indicates a negative prediction.

Sorry, not yet ready.

Questions and Bug Reports

If you find bugs or you have problems with the code you cannot solve by yourself, please contact me via email <tj@cs.cornell.edu>.

Disclaimer

History

V1.00 

• Initial version

References

Last modified August 22nd, 2003 by Thorsten Joachims <thorsten@joachims.org>