Exploring Communities in Large Profiled Graphs

Yankai Chen, Yixiang Fang, Reynold Cheng, Yun Li, Xiaojun Chen, Jie Zhang

TL;DR

This paper introduces Profiled Community Search (PCS), a new approach to finding communities in large graphs where nodes have hierarchical labels (like expertise or topics). PCS goes beyond traditional community search by leveraging these hierarchical labels to find communities with shared semantic themes, not just structural connections. They developed an efficient CP-tree index and algorithms to make this analysis practical for large-scale networks.

What Problem Does This Paper Address?

Traditional community search (CS) in graphs focuses on finding densely connected subgraphs. However, many real-world networks, like social networks or collaboration networks, have rich semantic information associated with their nodes (e.g., user interests, research topics, author affiliations). Existing CS methods often ignore this information or only use simple keyword matching, leading to communities that might be structurally connected but semantically diverse or irrelevant. This paper addresses the need to find communities that are cohesive both structurally and semantically, using hierarchical label information to capture deeper thematic connections.

Methods

The core of this work is the Profiled Community Search (PCS) problem. To tackle it, the authors introduce:

  • Profiled Graphs: Graphs where each vertex has a hierarchical set of labels, represented as a "P-tree." This structure captures relationships between labels (e.g., "London" is a type of "UK city").
  • Profile Cohesiveness: A new metric for community quality that leverages the hierarchical labels. It aims to find communities where the P-trees of vertices have a large "maximal common subtree," representing a shared semantic theme.
  • CP-tree Index: A novel index structure that combines k-cores (for structural cohesiveness) with the P-tree hierarchy. This index allows for efficient retrieval of relevant subgraphs and P-tree information.
  • Index-Based Query Algorithms:
    • Basic Solution: An initial, but computationally expensive, approach that enumerates candidate subtrees and verifies them.
  • incre Algorithm: An improvement that uses the CP-tree index to prune the search space and avoid redundant computations.
  • Advanced Methods (adv-I, adv-D, adv-P): These algorithms adapt ideas from frequent subgraph mining (like MARGIN) to more efficiently find "cuts" (initial feasible/infeasible subtree pairs) and expand them. They significantly reduce the search space by focusing on the boundaries of feasible subtrees.

Datasets

The authors evaluated their methods on a combination of real-world and synthetic datasets:

  • Real Datasets:
    • ACMDL: A co-authorship network in computer science.
  • PubMed: A co-authorship network in biomedical areas.
  • Flickr: A social network dataset representing user "follow" relationships.
  • Synthetic Datasets:
    • DBLP: A co-authorship network.

They constructed P-trees for the real datasets by unifying hierarchical categorization information (like ACM CCS or MeSH) for authors or mapping textual content to subjects for Flickr users.

Key Insights and Ideas

  • Hierarchical Labels Matter: Simply matching keywords isn't enough. The hierarchical structure of labels (like expertise or affiliations) is crucial for identifying semantically meaningful communities.
  • Maximal Common Subtree is Key: The "maximal common subtree" of P-trees within a community effectively captures the shared semantic theme, providing a richer understanding than just counting common labels.
  • Index-Based Efficiency: A naive approach to PCS is prohibitively expensive. The CP-tree index and advanced algorithms are essential for making PCS practical and enabling online queries.
  • Advanced Methods Outperform: Algorithms inspired by subgraph mining (like MARGIN) significantly outperform incremental approaches by intelligently pruning the search space.
  • PCS Offers Higher Diversity: PCS can extract communities with more diverse semantic focuses compared to methods that only maximize shared keywords.

Key Results

  • Effectiveness: PCS identifies communities with higher semantic cohesiveness and diversity compared to existing methods like ACQ, Global, and Local CS. This is demonstrated through metrics like Community Pairwise Similarity (CPS) and Level-Diversity Ratio (LDR).
  • Efficiency: The proposed CP-tree index and advanced query algorithms (adv-I, adv-D, adv-P) achieve significant speedups.
  • The incre algorithm is up to 100 times faster than the basic method.
  • Advanced methods (adv-I, adv-D, adv-P) are up to 10 times faster than incre.
  • The adv-P method consistently shows the best performance across various datasets and configurations.
  • Scalability: Index construction scales linearly with dataset size, and query algorithms scale efficiently with the number of vertices, P-trees, and the global P-tree.
  • Location of Maximal Subtrees: Experiments showed that maximal feasible subtrees often lie in the middle of the search space, validating the motivation for advanced, non-incremental search strategies.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the basic solution is computationally expensive, motivating the need for indexing and advanced algorithms.
  • While advanced methods are efficient, their worst-case time complexity can still be high, though practical performance is much better.
  • Future Work:
    • Explore alternative structure cohesiveness measures (e.g., k-truss, k-clique) and profile cohesiveness measures.
  • Relax query conditions, such as allowing a minimum semantic similarity threshold (β) or a proportion of vertices meeting a degree threshold (δ).
  • Investigate the impact of directed edges on PCS and adapt algorithms for directed graphs (e.g., using D-core).
  • Extend PCS to other graph pattern matching problems and explore automatic generation of meaningful graph patterns.

Summary updated

Abstract

Given a graph $G$G and a vertex $q\in G$q∈G, the community search (CS) problem aims to efficiently find a subgraph of $G$G whose vertices are closely related to $q$q. Communities are prevalent in social and biological networks, and can be used in product advertisement and social event recommendation. In this paper, we study profiled community search (PCS), where CS is performed on a profiled graph. This is a graph in which each vertex has labels arranged in a hierarchical manner. Extensive experiments show that PCS can identify communities with themes that are common to their vertices, and is more effective than existing CS approaches. As a naive solution for PCS is highly expensive, we have also developed a tree index, which facilitates efficient and online solutions for PCS.
BibTeX
@article{chen2019exploring,
  author = {Yankai Chen and Yixiang Fang and Reynold Cheng and Yun Li and Xiaojun Chen and Jie Zhang},
  title = {{Exploring Communities in Large Profiled Graphs}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2019},
  url = {https://openreview.net/forum?id=wZ0h1LfdiuL},
}

Loading related content...

Figure