Efficient Mining of GraphBased Data基于图形数据的高效挖掘.pptVIP

CSE@UTA SRL Workshop Efficient Mining of Graph-Based Data Motivation Structural/relational data Ease of graph representation Graph-Based Discovery Algorithm Create substructure for each unique vertex label Algorithm Expand best substructure by an edge or edge+neighboring vertex Algorithm Keep only best beam-width substructures on queue Terminate when queue is empty or #discovered substructures = limit Compress graph and repeat to generate hierarchical description Note: polynomially constrained Evaluation Metric Substructures evaluated based on ability to compress input graph Compression measured using minimum description length (DL) Best substructure S in graph G minimizes: DL(S) + DL(G|S) Examples Inexact Graph Match Some variations may occur between instances Want to abstract over minor differences Difference = cost of transforming one graph to isomorphism of another Match if cost/size threshold Parallel/Distributed Discovery Divide graph into P partitions using Metis, distribute to P processors Each processor performs serial Subdue on local partition Broadcast best substructures, evaluate on other processors Master processor stores best global substructures Close to linear speedup Graph-Based Concept Learning One graph stores positive examples One graph stores negative examples Find substructure that compresses positive graph but not negative graph (PosEgsNotCovered) + (NegEgsCovered) Multiple iterations implements set-covering approach Concept-Learning Example Concept-Learning Results Chess endgames (19,257 examples) Black King is (+) or is not (-) in check 99.8% FOIL, 99.21% Subdue More Concept-Learning Results Tic-Tac-Toe endgames + is win for X (958 examples) 100% Subdue, 92.35% FOIL Bach chorales Musical sequences (20 sequences) 100% Subdue, 85.71% FOIL Graph-Based Clustering Iterate Subdue until single vertex Each cluster (substructure) inserted into a classification lattice Clustering Example: Animals Graph-Based Clustering Results Cobweb Results