Classification on Large Networks: A Quantitative Bound via Motifs and Graphons
When each data point is a large graph, graph statistics such as densities of certain subgraphs (motifs) can be used as feature vectors for machine learning. While intuitive, motif counts are expensive to compute and difficult to work with theoretically. Via graphon theory, we give an explicit quantitative bound for the ability of motif homomorphisms to distinguish large networks under both generative and sampling noise. Furthermore, we give similar bounds for the graph spectrum and connect it to homomorphism densities of cycles. This results in an easily computable classifier on graph data with theoretical performance guarantee. Our method yields competitive results on classification tasks for the autoimmune disease Lupus Erythematosus.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationSimilar Papers 제목 키워드 기반
When is Nontrivial Estimation Possible for Graphons and Stochastic Block Models?
Block graphons (also called stochastic block models) are an important and widely-studied class of models for random networks. We provide a lower bound on the accuracy of estimators for block graphons with a large number …
Graphon EstimationGeneralization Bounds for Message Passing Networks on Mixture of Graphons
We study the generalization capabilities of Message Passing Neural Networks (MPNNs), a prevalent class of Graph Neural Networks (GNN). We derive generalization bounds specifically for MPNNs with normalized sum aggregatio…
Generalization BoundsFlowette: Flow Matching with Graphette Priors for Graph Generation
We study generative modeling of graphs with recurring subgraph motifs. We propose Flowette, a continuous flow matching framework that employs a graph neural network-based transformer to learn a velocity field over graph …
Graph Neural NetworkGraph GenerationConsensus on Open Multi-Agent Systems Over Graphs Sampled from Graphons
We show how graphons can be used to model and analyze open multi-agent systems, which are multi-agent systems subject to arrivals and departures, in the specific case of linear consensus. First, we analyze the case of re…
Stochastic Block ModelInvestigating Literary Motifs in Ancient and Medieval Novels with Large Language Models
The Greek fictional narratives often termed love novels or romances, ranging from the first century CE to the middle of the 15th century, have long been considered as similar in many ways, not least in the use of particu…