2013 · 97 citations · 25 references
ComputingComputer ScienceData AnalyticsData MiningData StructuresCommunity StructureGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryOutlier DetectionAttributed Graph MiningGraph Outlier DetectionGraph ProcessingMultivariate Outlier DetectionOutlier ScoringStatistical Outlier DetectionSubspace Outlier Detection
Current mining algorithms for attributed graphs exploit dependencies between attribute information and edge structure, referred to as homophily. However, techniques fail if this assumption does not hold for the full attribute space. In multivariate spaces, some attributes have high dependency with the graph structure while others do not show any dependency. Hence, it is important to select congruent subspaces (i.e., subsets of the node attributes) showing dependencies with the graph structure. In this work, we propose a method for the statistical selection of such congruent subspaces. More specifically, we define a measure which assesses the degree of congruence between a set of attributes and the entire graph. We use it as the core of a statistical test, which congruent subspaces must pass. To illustrate its applicability to common graph mining tasks and in order to evaluate our selection scheme, we apply it to community outlier detection. Our selection of congruent subspaces enhances outlier detection by measuring outlier ness scores in selected subspaces only. Experiments on attributed graphs show that our approach outperforms traditional full space approaches and gives way to better outlier detection.
25
Birds of a Feather: Homophily in Social Networks
Miller McPherson, Lynn Smith‐Lovin, James M. Cook · Annual Review of Sociology · 2001 · 18.6K citations
Mining association rules between sets of items in large databases
Rakesh Agrawal, Tomasz Imieliński, Arun Swami · 1993 · 14.8K citations · Full text
Individual Comparisons by Ranking Methods
Frank Wilcoxon · Biometrics Bulletin · 1945 · 14.4K citations
Business, Computer Science, Multi-criteria Decision Making +8
Markus Breunig, Hans‐Peter Kriegel, Raymond T. Ng et al. · ACM SIGMOD Record · 2000 · 5.2K citations