2019/06/12 by Ryan A. Rossi, Rossi, Ryan A., Anup Rao +9
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Computational Drug Discovery Methods #FOS: Computer and information sciences #Graph theory and applications #Information Retrieval (cs.IR) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Social and Information Networks (cs.SI) #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.1906.05059
openalex publication_date 2019/06/12 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
In this paper, we introduce the notion of motif closure and describe\nhigher-order ranking and link prediction methods based on the notion of closing\nhigher-order network motifs. The methods are fast and efficient for real-time\nranking and link prediction-based applications such as web search, online\nadvertising, and recommendation. In such applications, real-time performance is\ncritical. The proposed methods do not require any explicit training data, nor\ndo they derive an embedding from the graph data, or perform any explicit\nlearning. Existing methods with the above desired properties are all based on\nclosing triangles (common neighbors, Jaccard similarity, and the ilk). In this\nwork, we investigate higher-order network motifs and develop techniques based\non the notion of closing higher-order motifs that move beyond closing simple\ntriangles. All methods described in this work are fast with a runtime that is\nsublinear in the number of nodes. The experimental results indicate the\nimportance of closing higher-order motifs for ranking and link prediction\napplications. Finally, the proposed notion of higher-order motif closure can\nserve as a basis for studying and developing better ranking and link prediction\nmethods.\n