The DOI matches its Crossref record; 45 of the 45 references it cites were found in a registry or an index.
Local Higher-Order Graph Clustering
Open accessAbstract
Local graph clustering methods aim to find a cluster of nodes by exploring a small region of the graph. These methods are attractive because they enable targeted clustering around a given seed node and are faster than traditional global graph clustering methods because their runtime does not depend on the size of the input graph. However, current local graph partitioning methods are not designed to account for the higher-order structures crucial to the network, nor can they effectively handle directed networks. Here we introduce a new class of local graph clustering methods that address these issues by incorporating higher-order network information captured by small subgraphs, also called network motifs. We develop the Motif-based Approximate Personalized PageRank (MAPPR) algorithm that finds clusters containing a seed node with minimal \emph{motif conductance}, a generalization of the conductance metric for network motifs. We generalize existing theory to prove the fast running time (independent of the size of the graph) and obtain theoretical guarantees on the cluster quality (in terms of motif conductance). We also develop a theory of node neighborhoods for finding sets that have small motif conductance, and apply these results to the case of finding good seed nodes to use as input to the MAPPR algorithm. Experimental validation on community detection tasks in both synthetic and real-world networks, shows that our new framework MAPPR outperforms the current edge-based personalized PageRank methodology.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Granovetter, M. S. (1973) · American Journal of Sociology · doi:10.1086/225469 · Cited by 40,491
Fortunato, S. (2010) · Physics Reports · doi:10.1016/j.physrep.2009.11.002 · Cited by 11,293
Network motifs: simple building blocks of complex networks.
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002) · Science · doi:10.1126/science.298.5594.824 · Cited by 7,368
Algebraic connectivity of graphs
Fiedler, M. (1973) · Czechoslovak Mathematical Journal · doi:10.21136/cmj.1973.101168 · Cited by 3,977
Graph evolution: Densification and shrinking diameters
Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217301 · Cited by 2,461
Self-citationLeskovec, J., Lang, K. J., Dasgupta, A., & Mahoney, M. W. (2009) · Internet Mathematics · doi:10.1080/15427951.2009.10129177 · Cited by 1,872
Self-citationSchaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Defining and evaluating network communities based on ground-truth
Yang, J., & Leskovec, J. (2015) · Knowledge and Information Systems · doi:10.1007/s10115-013-0693-z · Cited by 1,411
Self-citationHigher-order organization of complex networks
Benson, A. R., Gleich, D. F., & Leskovec, J. (2016) · Science · doi:10.1126/science.aad9029 · Cited by 1,270
Self-citationLancichinetti, A., & Fortunato, S. (2009) · Physical Review E · doi:10.1103/physreve.80.016118 · Cited by 1,009
Local Graph Partitioning using PageRank Vectors
Andersen, R., Chung, F., & Lang, K. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.44 · Cited by 967
Biological network comparison using graphlet degree distribution
Pržulj, N. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl301 · Cited by 837
Sporns, O., & Kötter, R. (2004) · PLoS Biology · doi:10.1371/journal.pbio.0020369 · Cited by 796
Finding local community structure in networks
Clauset, A. (2005) · Physical Review E · doi:10.1103/physreve.72.026132 · Cited by 788
Social structure of Facebook networks
Traud, A. L., Mucha, P. J., & Porter, M. A. (2012) · Physica A: Statistical Mechanics and its Applications · doi:10.1016/j.physa.2011.12.021 · Cited by 707
Klimt, B., & Yang, Y. (2004) · Conference on Email and Anti-Spam · Cited by 575
The community-search problem and how to plan a successful cocktail party
Sozio, M., & Gionis, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835923 · Cited by 490
Querying k-truss community in large and dynamic graphs
Huang, X., Cheng, H., Qin, L., Tian, W., & Yu, J. X. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2610495 · Cited by 488
Local search of communities in large graphs
Cui, W., Xiao, Y., Wang, H., & Wang, W. (2014) · Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2588555.2612179 · Cited by 299
Revealing the Hidden Language of Complex Networks
Yaveroğlu, Ö. N., Malod-Dognin, N., Davis, D., Levnajic, Z., Janjic, V., Karapandza, R., Stojmirovic, A., & Pržulj, N. (2014) · Scientific Reports · doi:10.1038/srep04547 · Cited by 247
Efficient Graphlet Counting for Large Networks
Ahmed, N. K., Neville, J., Rossi, R. A., & Duffield, N. (2015) · 2015 IEEE International Conference on Data Mining · doi:10.1109/icdm.2015.141 · Cited by 229
Scalable Motif-aware Graph Clustering
Tsourakakis, C. E., Pachocki, J., & Mitzenmacher, M. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3038912.3052653 · Cited by 207
Heat kernel based community detection
Kloster, K., & Gleich, D. F. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623706 · Cited by 205
Self-citationVertex neighborhoods, low conductance cuts, and good seeds for local community methods
Gleich, D. F., & Seshadhri, C. (2012) · Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2339530.2339628 · Cited by 183
Self-citationJeub, L. G. S., Balachandran, P., Porter, M. A., Mucha, P. J., & Mahoney, M. W. (2015) · Physical Review E · doi:10.1103/physreve.91.012821 · Cited by 156
Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts
Jha, M. K., Seshadhri, C., & Pinar, A. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741101 · Cited by 132
Tensor Spectral Clustering for Partitioning Higher-order Network Structures
Benson, A. R., Gleich, D. F., & Leskovec, J. (2015) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611974010.14 · Cited by 114
Self-citationHigher-order clustering in networks
Yin, H., Benson, A. R., & Leskovec, J. (2018) · Physical review. E · doi:10.1103/physreve.97.052306 · Cited by 113
Self-citationUncovering the Small Community Structure in Large Networks: A Local Spectral Approach
Li, Y., He, K., Bindel, D., & Hopcroft, J. E. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741676 · Cited by 111
Large-Scale Community Detection on YouTube for Topic Discovery and Exploration
Gargi, U., Lu, W., Mirrokni, V., & Yoon, S. (2021) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v5i1.14191 · Cited by 89
Mahoney, M. W., Orecchia, L., & Vishnoi, N. K. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0912.0681 · Cited by 87
A Fast and Provable Method for Estimating Clique Counts Using Turán's Theorem
Jain, S., & Seshadhri, C. (2017) · International World Wide Web Conference (WWW) · doi:10.1145/3038912.3052636 · Cited by 83
TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size
Stefani, L. D., Epasto, A., Riondato, M., & Upfal, E. (2016) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2939672.2939771 · Cited by 82
Counting Graphlets: Space vs Time
Bressan, M., Chierichetti, F., Kumar, R., Leucci, S., & Panconesi, A. (2017) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3018661.3018732 · Cited by 78
Fixing two weaknesses of the Spectral Method
Lang, K. (2005) · Cited by 72
Local Partitioning for Directed Graphs Using PageRank
Andersen, R., Chung, F., & Lang, K. (2008) · Internet Mathematics · doi:10.1080/15427951.2008.10129297 · Cited by 61
Subgraph Frequencies: Mapping the Empirical and Extremal Geography of Large Graph CollectionsPreprint
Ugander, J. H., Bäckström, L., & Kleinberg, J. M. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1304.1548 · Cited by 52
Using Triangles to Improve Community Detection in Directed NetworksPreprint
Klymko, C., Gleich, D. F., & Kolda, T. G. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1404.5874 · Cited by 49
Self-citationSpectral affinity in protein networks
Voevodski, K., Teng, S., & Xia, Y. (2009) · BMC Systems Biology · doi:10.1186/1752-0509-3-112 · Cited by 47
Four proofs for the Cheeger inequality and graph partition algorithms
Chung, F. (2007) · Cited by 40
Using Local Spectral Methods to Robustify Graph-Based Learning Algorithms
Gleich, D. F., & Mahoney, M. W. (2015) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2783258.2783376 · Cited by 37
Self-citationGene Prioritization for Type 2 Diabetes in Tissue-specific Protein Interaction Networks ∗
Jiang, B., Wang, J., Xiao, J., et al. (2009) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 20
The blessing of transitivity in sparse and stochastic networksPreprint
Rohe, K., & Qin, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1307.2302 · Cited by 19
Solving Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
Chung, F., & Simpson, O. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-03536-9_16 · Cited by 19
Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs
Epasto, A., Feldman, J., Lattanzi, S., Leonardi, S., & Mirrokni, V. (2014) · International World Wide Web Conference (WWW) · doi:10.1145/2566486.2568025 · Cited by 12
Cited by
A Comprehensive Survey on Community Detection With Deep Learning
Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C., Hu, W., Paris, C., Nepal, S., Jin, D., et al. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3137396 · Cited by 353
Identifying influential spreaders by gravity model
Li, Z., Ren, T., Ma, X., Liu, S., Zhang, Y., & Zhou, T. (2019) · Scientific Reports · doi:10.1038/s41598-019-44930-9 · Cited by 256
Motif-Backdoor: Rethinking the Backdoor Attack on Graph Neural Networks via Motifs
Zheng, H., Xiong, H., Chen, J., Ma, H., & Huang, G. (2024) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2023.3267094 · Cited by 41
On the robustness of graph-based clustering to random network alterations
Stacey, R. G., Skinnider, M. A., & Foster, L. J. (2021) · Molecular & Cellular Proteomics · doi:10.1074/mcp.ra120.002275 · Cited by 11
Metadata
- Authors
- Yin, H., Benson, A. R., Leskovec, J., & Gleich, D. F.
- Venue
- Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
- Publisher
- ACM
- Published
- 2017-08-04
- Volume
- 2017
- Pages
- 555-564
- OpenAlex
- W2743418339
- Cited by
- 583
- References
- 45
- FWCI
- 73.46
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.