Source-linked AI summary
Attribute Truss Community Search
Xin Huang, Laks V. S. Lakshmanan
TL;DR
The paper addresses attributed community search, where existing structure-focused methods overlook node-attribute cohesion. It proposes attributed truss communities with attribute-aware scoring, greedy and indexed processing, and reports effective recovery of ground-truth communities and social circles, while the optimization problem is NP-hard.
Problem
Existing community-search algorithms largely ignore node attributes, motivating communities that jointly capture dense connectivity and attribute homogeneity for queries containing nodes and attributes.
Method
The paper defines attributed truss communities using an attribute relevance score and connected, close k-trusses, then develops greedy, local-exploration, and indexed query-processing algorithms.
Results
The problem is NP-hard, and experiments on seven real datasets show that the model and algorithms efficiently and effectively find ground-truth communities and social circles, significantly outperforming previous work.
Takeaways & Limitations
ATC provides an attribute-aware community-search model for finding cohesive, tight communities that contain query nodes and share query-relevant attributes.
Takeaways & Limitations
The attribute score can fail to reward larger communities, and the ATC problem is computationally difficult because the score is non-monotone, non-submodular, and non-supermodular.
Abstract
from arXiv · showhide
Recently, community search over graphs has attracted significant attention and many algorithms have been developed for finding dense subgraphs from large graphs that contain given query nodes. In applications such as analysis of protein protein interaction (PPI) networks, citation graphs, and collaboration networks, nodes tend to have attributes. Unfortunately, previously developed community search algorithms ignore these attributes and result in communities with poor cohesion w.r.t. their node attributes. In this paper, we study the problem of attribute-driven community search, that is, given an undirected graph $G$ where nodes are associated with attributes, and an input query $Q$ consisting of nodes $V_q$ and attributes $W_q$, find the communities containing $V_q$, in which most community members are densely inter-connected and have similar attributes. We formulate our problem of finding attributed truss communities (ATC), as finding all connected and close k-truss subgraphs containing $V_q$, that are locally maximal and have the largest attribute relevance score among such subgraphs. We design a novel attribute relevance score function and establish its desirable properties. The problem is shown to be NP-hard. However, we develop an efficient greedy algorithmic framework, which finds a maximal $k$-truss containing $V_q$, and then iteratively removes the nodes with the least popular attributes and shrinks the graph so as to satisfy community constraints. We also build an elegant index to maintain the known $k$-truss structure and attribute information, and propose efficient query processing algorithms. Extensive experiments on large real-world networks with ground-truth communities shows the efficiency and effectiveness of our proposed methods.
1. INTRODUCTION
The paper frames attributed community search as finding communities that balance dense connectivity with homogeneous query-related attributes. It proposes attributed truss communities, algorithms, and indexing methods to address this problem efficiently.
- Motivation: Node attributes are important for interpreting communities, but conventional community search focuses on structure and can produce attribute-incohesive groups.Examples include expertise topics in collaboration networks and biological properties in protein networks.
- Motivation: Filtering a graph by query attributes can yield a sparse chain, whereas retaining a node without the attribute can produce a denser and better community.The example contrasts a chain with a 3-truss, motivating a balance between density and attribute homogeneity.
- Motivation: Keyword search is also insufficient because minimum-communication answers may be trees or single edges rather than cohesive communities.For query node q1 and attribute DB, keyword search returns the single edge connecting them.
- Approach: The proposed ATC model combines an attribute relevance score with a connected (k, d)-truss containing all query nodes and covering query attributes.The score balances attribute coverage and homogeneity, while (k, d)-trusses impose dense, tight structure.
- Challenges: The problem is NP-hard and the attribute score is non-monotone, non-submodular, and non-supermodular.These properties indicate substantial computational difficulty.
- Approach and evaluation: The paper develops greedy, local-exploration, and indexed query-processing strategies, and evaluates them on seven real datasets against previous work.The experiments target ground-truth communities and social circles and report efficiency and effectiveness.
2. PRELIMINARIES AND DESIDERATA
The paper defines attributed community search over connected subgraphs that contain query nodes, cover query attributes, share attributes, remain cohesive, and have low communication cost. These desiderata guide the formal community model.
- Graph model: Graphs are modeled as undirected, unweighted, simple graphs G=(V,E), with node attributes drawn from a graph-wide attribute set A.The notation includes n vertices, m edges, neighbor sets, degrees, and Vw for nodes carrying attribute w.
- ACS formulation: An ACS query consists of query nodes Vq and query attributes Wq, and seeks a subgraph containing Vq with dense connectivity and broad, shared attribute coverage.The formulation also requires low communication cost.
- Desiderata: A good attributed community must be connected and satisfy participation, cohesiveness, attribute coverage and correlation, and communication-cost criteria.The criteria distinguish structural cohesion from attribute relevance and distance.
- Desiderata: The attribute score should increase with both the number of query attributes covered and the number of attributes shared by community vertices.The paper motivates score functions that reward coverage and shared attributes together.
3. RELATED WORK
Related work spans community search, keyword search, team formation, and attributed community detection. The paper distinguishes its approach by combining dense subgraphs, multiple query nodes, and attribute-aware search.
- Community search: Traditional community-search models use quasi-cliques, densest subgraphs, k-cores, or k-trusses but generally ignore node attributes.The paper identifies this as a limitation for attribute cohesion.
- Keyword search: Keyword-search methods find minimal connected trees or subgraphs linking query terms, but they do not require cohesive dense structure.Their objectives differ from community search because communication cost, rather than density, drives the answer.
- Team formation: Team-formation studies typically seek experts connected by a low-cost tree, whereas community search requires a densely connected subgraph.This gives team formation a different structural target.
- Attributed community detection: Attributed community-detection methods combine structural and attribute similarity, use clustering or subspace techniques, and generally target communities globally rather than query-specific search.The cited approaches address dense components with homogeneous attributes.
- Comparison with attributed community search: Compared with prior k-core-based attributed search, this work uses denser k-trusses, supports multiple query nodes, and addresses communities that the prior approach may miss.The paper highlights k-trusses’ stronger connectivity properties and broader query support.
4. ATTRIBUTED COMMUNITY MODEL
The attributed community model combines dense connectivity, proximity to query nodes, and attribute relevance. It introduces (k, d)-trusses and an attribute score designed to reward query-attribute coverage and shared attributes while penalizing irrelevant nodes.
- Cohesiveness: A connected k-truss requires every edge to have support of at least k −2 within the subgraph.Edge support counts the triangles containing that edge.
- Attributed community model: The model seeks communities that are cohesive, close to query nodes, and rich in shared query attributes.These requirements correspond to dense subgraph structure, low query distance, and attribute relevance.
- (k, d)-truss: A (k, d)-truss is a connected k-truss containing all query nodes with graph query distance at most d.Increasing k strengthens cohesiveness, while decreasing d improves proximity to query nodes.
- Attribute score function: The attribute score increases with query-attribute coverage and attribute sharing, but decreases as irrelevant community nodes increase.These principles capture coverage, homogeneity, and exclusion of nodes unrelated to the query.
- Attribute score function: The proposed score weights each query attribute by its popularity and permits steiner nodes when they help connect relevant query-related nodes.For H4, the score is 9/4, while the less cohesive chain scores 3; H4 is a 3-truss and the chain is a 2-truss.
- Attribute score function: The framework is flexible enough to support any attribute score function satisfying the identified principles.The principles require high attribute coverage, high attribute correlation, and few irrelevant nodes.
5. PROBLEM ANALYSIS
The paper establishes NP-hardness for ATC through weighted-density problems and a reduction from weighted-density instances. It also identifies structural properties and non-monotone attribute scoring that motivate approximation algorithms.
- Weighted Density: Weighted density assigns each vertex its degree in the original graph and augments induced-subgraph density with these vertex weights.The WDalK-Problem asks whether an induced subgraph with at least k vertices reaches a weighted-density threshold.
- Hardness: The WDalK-Problem is NP-hard, extending hardness from exactly k vertices to induced subgraphs containing at least k vertices.The paper first establishes hardness for WDK-Problem and then extends it to WDalK-Problem.
- Reduction: The reduction constructs a complete graph whose vertex attributes encode edges of the original graph, equating the ATC attribute score with weighted density.A weighted-density solution maps to an ATC instance with query attributes representing every original edge.
- Hardness: The ATC-Problem is NP-hard, with hardness arising mainly from maximizing the attribute score of an attributed truss community.The proof proceeds through weighted-density problems and a reduction to ATC.
- Structural Properties: A connected k-truss has bounded diameter and hierarchical structure, while a (k, d)-truss additionally satisfies the query-distance bound.The paper states d ≤ diam(H) and bounds the diameter using the number of vertices and truss parameter k.
- Attribute Score: The attribute score is neither monotone nor anti-monotone, and it is neither submodular nor supermodular.This behavior complicates finding ATCs with maximum attribute score.
6. TOP-DOWN GREEDY ALGORITHM
The paper develops greedy methods that shrink dense truss candidates by removing vertices with weak attribute relevance while maintaining community constraints. It proves computational hardness, improves deletion decisions with look-ahead and bulk removal, and analyzes efficiency and limitations.
- Basic greedy algorithm: The algorithm first finds a maximal (k, d)-truss, then repeatedly removes vertices with the smallest attribute score contribution while preserving the truss constraints.It evaluates all generated candidates and returns the one with maximum attribute score.
- Basic greedy algorithm: Attribute score contribution measures the change in community attribute score caused by dropping a vertex, but the score may increase or decrease after removal.The method therefore seeks vertices whose removal causes the smallest score drop.
- Basic greedy algorithm: The Basic algorithm maintains candidate graphs through iterative edge, support, and query-distance pruning until the remaining graph is no longer a (k, d)-truss.Removing edges can increase query distance, while removing vertices can reduce edge support, so maintenance steps may trigger one another.
- Complexity: The algorithm’s time complexity is O(mρ + t(|Wq|n + |Vq|m)) and its space complexity is O(m + |attr(V)|).Here, t is bounded by O(min{n, m/k}) and ρ is the graph’s arboricity.
- Improved greedy algorithm: Basic can lose quality by ignoring cascading removals and can be inefficient because it deletes only one vertex per iteration.These limitations motivate look-ahead deletion criteria and bulk removal.
- Improved greedy algorithm: BULK uses attribute marginal gain to incorporate vertices that become invalid after a deletion and removes multiple low-gain vertices per iteration.The marginal gain is defined using the vertex and all vertices that violate (k, d)-truss after its removal.
7. INDEX-BASED SEARCH ALGORITHM
The paper builds ATindex to combine structural trussness, attribute trussness, and inverted attribute lists for faster attributed community search. LocATC uses this index to explore a focused neighborhood, then applies BULK to obtain a dense, attribute-cohesive community.
- ATindex: ATindex maintains structural trussness, attribute trussness, and an inverted attribute index to support attributed truss queries.Structural trussness alone cannot guarantee relevance to query attributes, motivating attribute-specific indexing.
- Trussness indexes: Structural trussness records the largest truss containing a vertex or edge, while attribute trussness computes the analogous value in each attribute-projected graph.Projected graphs contain the vertices associated with a particular attribute.
- ATindex construction: The index construction applies truss decomposition to the original graph and each attribute-projected graph, then stores structural and attribute trussness values with inverted node lists.The inverted lists order vertices possessing each attribute by decreasing structural trussness.
- LocATC: LocATC first builds an attribute-weighted Steiner tree connecting query nodes, expands it into a local neighborhood, and applies BULK to the resulting dense subgraph.The algorithm can automatically set k to the maximum trussness connecting query vertices and d to their query distance.
- LocATC: Attributed truss distance distinguishes Steiner trees with equal edge weight by favoring edges with stronger structural and attribute trussness.The index provides these trussness values in O(1) time, while minimum-weight Steiner tree computation is NP-hard.
- LocATC: A standard Steiner tree may seed a community with low trussness and attribute score even when another equal-weight tree supports a stronger attributed truss.The paper’s example contrasts two weight-2 trees, one whose edges have attribute trussness 4 and one unsuitable for a 2-truss with the target attribute.
8. EXPERIMENTS
Experiments on real-world and synthetic attributed networks evaluate community quality, query efficiency, scalability, indexing, parameter sensitivity, and behavior on good or bad queries. LocATC generally provides high-quality communities with competitive or improved efficiency.
- Experimental Setup: Experiments use seven real-world networks, including PPI, Facebook ego-networks, and university web graphs, with attributes and ground-truth communities.Additional networks without attributes receive synthetic attributes for controlled evaluation.
- Quality Evaluation: LocATC achieves the highest F1-score on most real-world networks and outperforms structure-only baselines and ACC-Q1.Its advantage is weaker on f104 and f1684, where ground-truth communities are structurally strong but less homogeneous in query attributes.
- Quality Evaluation: LocATC achieves the best F1-score on all five synthetic-attribute networks, while LocATC-Q1 outperforms ACC-Q1 on most networks.The synthetic evaluation uses DBLP, Amazon, Youtube, LiveJournal, and Orkut with ground-truth communities.
- Efficiency Evaluation: LocATC runs much faster than MDC and remains close to LCTC on large synthetic-attribute networks.The reported results indicate that attribute-cohesiveness reasoning adds small overhead relative to LCTC while improving discovered-community quality.
- Parameter Evaluation: Query time increases smoothly with query-vertex size and only modestly with query-attribute size, while LocATC remains the strongest method in these tests.BULK improves over Basic through bulk deletion, and local exploration is especially efficient for one query vertex.
- Index Evaluation: The ATindex size is comparable to the original graph and structural k-truss index, with O(m+Σ_{w∈A}|E(G_w)|) space complexity.On DBLP, ATindex construction takes 35.2 seconds, compared with nearly 20 seconds for individual non-indexed query runs.
- Additional Evaluation: Increasing attribute homogeneity improves LocATC performance on synthetic data, while bad queries can be processed 6.8 times faster than good queries on DBLP.The faster bad-query processing is associated with quickly returning empty answers when query structure or nearby attribute homogeneity is weak.
9. CONCLUSION
The paper proposes attributed truss communities (ATC) for finding query-containing communities that combine cohesive structure with homogeneous query attributes. It establishes computational hardness, develops efficient search and indexing strategies, and reports strong performance in experiments.
- ATC finds communities containing query nodes with cohesive, tight structure and homogeneous query attributes.
- Finding an ATC is NP-hard, and its attribute score is neither monotone, submodular, nor supermodular.
- The proposed greedy framework removes nodes with the least popular attributes while shrinking the graph to satisfy community constraints.
- The ATindex maintains k-truss structure and attribute information for efficient query processing using local exploration and bulk deletion.
- Experiments show that ATC accurately finds ground-truth communities and social circles while significantly outperforming previous approaches.