World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Selected Papers from 15th Iberoamerican Congress on Pattern RecognitionNo Access

EMBEDDING OF GRAPHS WITH DISCRETE ATTRIBUTES VIA LABEL FREQUENCIES

    https://doi.org/10.1142/S0218001413600021Cited by:6 (Source: Crossref)

    Graph-based representations of patterns are very flexible and powerful, but they are not easily processed due to the lack of learning algorithms in the domain of graphs. Embedding a graph into a vector space solves this problem since graphs are turned into feature vectors and thus all the statistical learning machinery becomes available for graph input patterns. In this work we present a new way of embedding discrete attributed graphs into vector spaces using node and edge label frequencies. The methodology is experimentally tested on graph classification problems, using patterns of different nature, and it is shown to be competitive to state-of-the-art classification algorithms for graphs, while being computationally much more efficient.

    References

    • R. Benavente, M. Vanrell and R. Baldrich, J. Opt. Soc. Am. A 25(10), 2582 (2008). CrossrefGoogle Scholar
    • C.   Bishop , Neural Networks for Pattern Recognition ( Oxford University Press , 1995 ) . CrossrefGoogle Scholar
    • M. C. Boeres, C. C. Ribeiro and I. Bloch, A randomized heuristic for scene recognition by graph matching, Proc. 3rd Workshop on Efficient and Experimental Algorithms3059, LNCS, eds. C. C. Ribeiro and S. L. Martins (Springer, 2004) pp. 100–113. Google Scholar
    • K. Borgwardtet al., Bioinformatics 21(1), 47 (2005). Crossref, ISIGoogle Scholar
    • H.   Bunke and G.   Allermann , Patt. Recogn. Lett.   1 , 245 ( 1983 ) . Crossref, ISIGoogle Scholar
    • H. Bunke and K. Riesen, Pattern Recogn. Lett. 33(7), 811 (2012). Crossref, ISIGoogle Scholar
    • H. Bunke and K. Shearer, Pattern Recogn. Lett. 19(3), 255 (1998). Crossref, ISIGoogle Scholar
    • D. Conteet al., Int. J. Pattern Recogn. Artif. Intell. 18(3), 265 (2004). Link, ISIGoogle Scholar
    • F. C. Curriero, Math. Geol. 38(8), 907 (2006). CrossrefGoogle Scholar
    • R.   Duda , P.   Hart and D.   Stork , Pattern Classification , 2nd edn. ( Wiley-Interscience , 2000 ) . Google Scholar
    • Development Therapeutics Program DTP, AIDS antiviral screen (2004), available at http://dtp.nci.nih.gov/docs/aids/aids data.html . Google Scholar
    • P. F. Felzenszwalb and D. P. Huttenlocher, Int. J. Comput. Vis. 59(2), 167 (2004). Crossref, ISIGoogle Scholar
    • M. L. Fernandez and G. Valiente, Pattern Recogn. Lett. 22(7), 753 (2001). Crossref, ISIGoogle Scholar
    • T.   Gärtner , Kernels for Structured Data ( World Scientific , 2008 ) . LinkGoogle Scholar
    • T. Gärtner, P. Flach and S. Wrobel, On graph kernels: Hardness results and efficient alternatives, Proc. 16th Annual Conference on Learning Theory, eds. B. Schölkopf and M. Warmuth (2003) pp. 129–143. Google Scholar
    • J.   Gasteiger and T.   Engel , Chemoinformatics: A Textbook ( Wiley-VCH , 2003 ) . CrossrefGoogle Scholar
    • J. M. Geusebroek, G. J. Burghouts and A. W. M. Smeulders, Int. J. Comput. Vis. 61(1), 103 (2005). Crossref, ISIGoogle Scholar
    • J. Gibert, E. Valveny and H. Bunke, Vocabulary selection for graph of words embedding, Proc. 5th Iberian Conf. Pattern Recognition and Image Analysis6669, LNCS, eds. J. Vitrià, J. M. Sanches and M. Hernández (Springer, 2011) pp. 216–223. Google Scholar
    • J. Gibert, E. Valveny and H. Bunke, Dimensionality reduction for graph of words embedding, Proc. 8th Int. Workshop on Graph-Based Representations for Pattern Recognition6658, LNCS, eds. X. Jiang, M. Ferrer and A. Torsello (Springer, 2011) pp. 22–31. Google Scholar
    • B. Haasdonk, IEEE Trans. Pattern Anal. Mach. Intell. 27(4), 482 (2005). Crossref, ISIGoogle Scholar
    • D. Haussler, Convolution kernels on discrete structures, Technical Report UCSC-CRL-99-10, University of California, Santa Cruz (1999) . Google Scholar
    • A. Inokuchi, T. Washio and H. Motoda, An apriori-based algorithm for mining frequent substructures from graph data, Proc. 4th Principles of Data Mining and Knowledge Discovery1910, LNAI, eds. D. A. Zighed, J. Komorowski and J. Zytkow (Springer, 2000) pp. 13–32. Google Scholar
    • S. Jouili and S. Tabbone, Graph Embedding using constant shift embedding, Proc. Int. Conf. Pattern Recognition6388, LNCS, eds. D. Ünay, Z. Çataltepe and S. Aksoy (Springer, 2010) pp. 83–92. Google Scholar
    • D. Justice and A. Hero, IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1200 (2006). Crossref, ISIGoogle Scholar
    • H. Kashima, K. Tsuda and A. Inokuchi, Marginalized kernels between labelled graphs, Proc. 20th Int. Conf. Machine Learning (2003) pp. 321–328. Google Scholar
    • J. Kazius, R. McGuire and R. Bursi, J. Med. Chem. 48(1), 312 (2005). Crossref, ISIGoogle Scholar
    • R. Kondor and J. Lafferty, Diffusion kernels on graphs and other discrete input spaces, Proc. 19th Int. Conf. Machine Learning (2002) pp. 315–322. Google Scholar
    • S. Kramer and L. De Raedt, Feature construction with version spaces for biochemical application, Proc. 18th Int. Conf. Machine Learning (2001) pp. 258–265. Google Scholar
    • J. Lafferty and G. Lebanon, Advances in Neural Information Processing Systems (MIT Press, 2003) pp. 375–382. Google Scholar
    • B. Luo, R. C. Wilson and E. R. Hancock, Pattern Recogn. 36(10), 2213 (2003). Crossref, ISIGoogle Scholar
    • P.   Mahé et al. , J. Chem. Inform. Model.   45 , 939 ( 2005 ) . Crossref, ISIGoogle Scholar
    • MAO dataset, available at http://iapt-tc15.greyc.fr/links.html#chemistry . Google Scholar
    • J.   Munkres , J. Soc. Ind. Appl. Math.   5 , 32 ( 1957 ) . Crossref, ISIGoogle Scholar
    • S. Nene, S. Nayar and H. Murase, Columbia object image library: COIL-100, Technical report, Department of Computer Science, Columbia University, New York (1996) . Google Scholar
    • M. Neuhaus and H. Bunke, IEEE Trans. Syst., Man, Cybern. B, Cybern. 35(3), 503 (2005). Crossref, ISIGoogle Scholar
    • M. Neuhaus and H. Bunke, Inf. Sci. 177(1), 239 (2007). Crossref, ISIGoogle Scholar
    • M.   Neuhaus and H.   Bunke , Bridging the Gap between Graph Edit Distance and Kernel Machines ( World Scientific , 2007 ) . LinkGoogle Scholar
    • M. Neuhaus, K. Riesen and H. Bunke, Fast suboptimal algorithms for the computation of graph edit distance, Proc. 11th Int. Workshop on Structural and Syntactic Pattern Recognition4109, LNCS, eds. D. Y. Yeunget al. (Springer, 2006) pp. 163–172. Google Scholar
    • E.   Pekalska and R.   Duin , The Dissimilarity Representation for Pattern Recognition: Foundations and Applications ( World Scientific , 2005 ) . LinkGoogle Scholar
    • E. Pekalska, R. Duin and P. Paclick, Pattern Recogn. 39(2), 189 (2006). Crossref, ISIGoogle Scholar
    • P. Ren, R. Wilson and E. Hancock, IEEE Trans. Neural Netw. 22(2), 233 (2011). Crossref, ISIGoogle Scholar
    • K. Riesen and H. Bunke, IAM Graph database repository for graph based pattern recognition and machine learning, Proc. Int. Workshops on Structural, Syntactic and Statistical Pattern Recognition5342, LNCS, eds. N. da Vitoria Loboet al. (Springer, 2008) pp. 287–297. Google Scholar
    • K. Riesen and H. Bunke, Image Vis. Comp. 27(4), 950 (2009). Crossref, ISIGoogle Scholar
    • K.   Riesen and H.   Bunke , Graph Classification and Clustering Based on Vector Space Embedding ( World Scientific , 2010 ) . LinkGoogle Scholar
    • A. Robles-Kelly and E. R. Hancock, IEEE Trans. Pattern Anal. Mach. Intell. 27(3), 365 (2005). Crossref, ISIGoogle Scholar
    • A. Sanfeliu and K. S. Fu, IEEE Trans. Syst., Man, Cybern. B, Cybern. 13(3), 353 (1983). Crossref, ISIGoogle Scholar
    • B.   Schölkopf and A. J.   Smola , Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond ( MIT Press , 2002 ) . Google Scholar
    • S. Sorlin and C. Solnon, Reactive tabu search for measuring graph similarity, Proc. 5th Int. Workshop on Graph-Based Representations for Pattern Recognition3434, LNCS, eds. L. Brun and M. Vento (Springer, 2005) pp. 172–182. Google Scholar
    • M. J. Tarr, The Object Databank, available at http://www.cnbc.cmu.edu/tarrlab/stimuli/objects/index.html . Google Scholar
    • S.   Vishwanathan et al. , J. Mach. Learn. Res.   11 , 1201 ( 2010 ) . ISIGoogle Scholar
    • W. D. Walliset al., Pattern Recogn. Lett. 22(6), 701 (2001). Crossref, ISIGoogle Scholar
    • C. Watkins, Advances in Large Margin Classifiers (MIT Press, 2000) pp. 39–50. CrossrefGoogle Scholar
    • J. H.   Wells and L. R.   Williams , Embeddings and extensions in analysis ( Springer-Verlag , New York , 1975 ) . CrossrefGoogle Scholar
    • R. Wilson, E. Hancock and B. Luo, IEEE Trans. Pattern Anal. Mach. Intell. 27(7), 1112 (2005). Crossref, ISIGoogle Scholar
    • J. Zhanget al., Int. J. Comput. Vis. 73(2), 213 (2007). Crossref, ISIGoogle Scholar