Learning on Large Graphs using Intersecting Communities
Message Passing Neural Networks (MPNNs) are a staple of graph machine learning. MPNNs iteratively update each node's representation in an input graph by aggregating messages from the node's neighbors, which necessitates a memory complexity of the order of the number of graph edges. This complexity might quickly become prohibitive for large graphs provided they are not very sparse. In this paper, we propose a novel approach to alleviate this problem by approximating the input graph as an intersecting community graph (ICG) -- a combination of intersecting cliques. The key insight is that the number of communities required to approximate a graph does not depend on the graph size. We develop a new constructive version of the Weak Graph Regularity Lemma to efficiently construct an approximating ICG for any input graph. We then devise an efficient graph learning algorithm operating directly on ICG in linear memory and time with respect to the number of nodes (rather than edges). This offers a new and fundamentally different pipeline for learning on very large non-sparse graphs, whose applicability is demonstrated empirically on node classification tasks and spatio-temporal data processing.
Code (1)
Tasks
Graph LearningLEMMANode ClassificationSimilar Papers 제목 키워드 기반
Efficient Learning on Large Graphs using a Densifying Regularity Lemma
Learning on large graphs presents significant challenges, with traditional Message Passing Neural Networks suffering from computational and memory costs scaling linearly with the number of edges. We introduce the Interse…
Graph Neural NetworkKnowledge Graph CompletionLEMMANode ClassificationKnotResolver: Tracking self-intersecting filaments in microscopy using directed graphs
Quantification of microscopy time-series of in vitro reconstituted motor driven microtubule (MT) transport in 'gliding assays' is typically performed using computational object tracking tools. However, these are limited …
Contour DetectionObject TrackingTime SeriesA new method for quantifying network cyclic structure to improve community detection
A distinguishing property of communities in networks is that cycles are more prevalent within communities than across communities. Thus, the detection of these communities may be aided through the incorporation of measur…
Community DetectionClique percolation method: memory efficient almost exact communities
Automatic detection of relevant groups of nodes in large real-world graphs, i.e. community detection, has applications in many fields and has received a lot of attention in the last twenty years. The most popular method …
Community DetectionOverlapping Community Detection by Online Cluster Aggregation
We present a new online algorithm for detecting overlapping communities. The main ingredients are a modification of an online k-means algorithm and a new approach to modelling overlap in communities. An evaluation on lar…
Community Detection