This project focuses on revealing similarities between graphs at the node, as well as the graph level. It comprises 3 main problems:

Graph similarity with known correspondence

How much did a network change since yesterday? How different is the wiring between a left-handed male’s brain and a right-handed female’s brain? Graph similarity with known node correspon- dence, i.e., the detection of changes in the connectivity of graphs, arises in numerous settings. We developed DELTACON, a principled, intuitive, and scalable algorithm that assesses the similarity between two graphs on the same nodes (e.g. employees of a company, customers of a mobile carrier). We plan to extend the algorithm in order to include efficient node and edge attribution, i.e., find the areas in the graphs that are responsible for the dissimilarity between graphs.

Graph similarity without known correspondence:

How can we quickly assess the similarity between two given graphs, without solving the node-correspondence problem? We developed NETSIMILE a scalable graph similarity algorithm, which is based on the creation and comparison of descriptive-features-based network “signatures”. We applied NETSIMILE to tasks such as clustering, visualization, discontinuity detection, network transfer learning, and re-identification across networks.

Graph alignment

Can we identify structural twins in social networks? How should we permute the nodes of Facebook so that it best matches the Google+ graph, revealing this way interesting similarities between the networks and the users? Graph alignment – the task of finding the node correspondences between two given graphs – is a rather hard problem with applications in numerous domains, such as social networks analysis, bioinformatics, chemistry, pattern recognition. In [8], we introduce a new optimization formulation for aligning bipartite graphs (e.g., users-groups graph). The algorithm finds correspondences on multiple granularities: node-level, as well as community-level. Our current work focuses on extending the algorithm to attributed graphs, i.e. graphs for which there is information in addition to their structure.

People

• Christos Faloutsos
• Danai Koutra
• Michele Berlingerio (IBM Ireland)
• Tina Eliassi-Rad (Rutgers)
• Hanghang Tong (CUNY)
• Joshua T. Vogelstein (Duke)

Publications

1. M. Berlingerio, D. Koutra, T. Eliassi-Rad, and C. Faloutsos, "Network similarity via multiple social theories," in Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2013, pp. 1439-1440. PDF Bibtex

   @inproceedings{berlingerio2013network, title={Network similarity via multiple social theories},
      author={Berlingerio, Michele and Koutra, Danai and Eliassi-Rad, Tina and Faloutsos, Christos},
      booktitle={Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining},
      pages={1439--1440},
      year={2013},
      organization={ACM},
      url={http://www.cs.cmu.edu/~dkoutra/papers/asonam_network_similarity_via_multiple_social_theories.pdf},
    }

2. D. Koutra, H. Tong, and D. Lubensky, "BIG-ALIGN: Fast Bipartite Graph Alignment," in IEEE ICDM, 2013. PDF Bibtex

   @inproceedings{koutra2013big, title={BIG-ALIGN: Fast Bipartite Graph Alignment},
      author={Koutra, Danai and Tong, Hanghang and Lubensky, David},
      booktitle={IEEE ICDM},
      year={2013},
      url={http://www.cs.cmu.edu/~dkoutra/papers/BiG-Align.pdf},
    }

3. D. Koutra, J. T. Vogelstein, and C. Faloutsos, "DELTACON: A Principled Massive-Graph Similarity Function," in Proceedings of the 13th SIAM International Conference on Data Mining (SDM), 2013, pp. 162-170. PDF Bibtex

   @inproceedings{koutra2013deltacon, title={DELTACON: A Principled Massive-Graph Similarity Function},
      author={Koutra, Danai and Vogelstein, Joshua T. and Faloutsos, Christos},
      booktitle={Proceedings of the 13th SIAM International Conference on Data Mining (SDM)},
      pages={162--170},
      year={2013},
      organization={SIAM},
      url={http://www.cs.cmu.edu/~dkoutra/papers/DeltaCon_KoutraVF_withAppendix.pdf},
    }

4. M. Berlingerio, D. Koutra, T. Eliassi-Rad, and C. Faloutsos, "NetSimile: a scalable approach to size-independent network similarity," arXiv preprint arXiv:1209.2684, 2012. PDF Bibtex

   @article{berlingerio2012netsimile, title={NetSimile: a scalable approach to size-independent network similarity},
      author={Berlingerio, Michele and Koutra, Danai and Eliassi-Rad, Tina and Faloutsos, Christos},
      journal={arXiv preprint arXiv:1209.2684},
      year={2012},
      url={http://arxiv.org/pdf/1209.2684v1},
    }

5. D. Koutra, T. Ke, U. Kang, D. H. P. Chau, H. K. Pao, and C. Faloutsos, "Unifying guilt-by-association approaches: Theorems and fast algorithms." Springer, 2011, pp. 245-260. PDF Bibtex

   @incollection{koutra2011unifying, title={Unifying guilt-by-association approaches: Theorems and fast algorithms},
      author={Koutra, Danai and Ke, Tai-You and Kang, U and Chau, Duen Horng Polo and Pao, Hsing-Kuo Kenneth and Faloutsos, Christos},
      booktitle={Machine Learning and Knowledge Discovery in Databases},
      pages={245--260},
      year={2011},
      publisher={Springer},
      url={http://www.cs.cmu.edu/~dkoutra/papers/fabp_pkdd2011.pdf},
    }