Several problems such as network intrusion, community detection, and disease outbreak can be described by observations attributed to nodes or edges of a graph. In these applications presence of intrusion, community or disease outbreak is characterized by novel observations on some unknown connected subgraph. These prob…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
169,291 papers · 148 categories
Trend · papers per month
48 results for “Connected subgraph detection”
Detecting edge correlation between two graphs sharpens a threshold based on densest subgraph.
problem Detecting edge correlation between two Erdős-Rényi graphs.
method Formulated as a hypothesis testing problem, connecting to densest subgraph detection.
result Sharp information-theoretic threshold established for edge correlation detection.
A wide variety of application domains are concerned with data consisting of entities and their relationships or connections, formally represented as graphs. Within these diverse application areas, a common problem of interest is the detection of a subset of entities whose connectivity is anomalous with respect to the r…
We formalize the problem of detecting a community in a network into testing whether in a given (random) graph there is a subgraph that is unusually dense. We observe an undirected and unweighted graph on N nodes. Under the null hypothesis, the graph is a realization of an Erdös-Rényi graph with probability p0. Under th…
A new algorithm optimizes graph-structured sparsity for nonlinear functions.
problem Optimizing sparsity-constrained optimization with graph-structured constraints.
method Graph-Structured Matching Pursuit (Graph-Mp) algorithm.
result Graph-Mp algorithm achieves strong convergence rate and approximation accuracy.
GraphDETR detects subgraphs in large graphs using deep learning.
problem Detecting subgraphs in large graphs efficiently and accurately.
method Formulates subgraph detection as a set prediction problem using GraphDETR, a deep learning framework.
result GraphDETR can detect diverse patterns in large graphs, achieving strong performance on molecular functional group detection.
Receiver algorithms which combine belief propagation (BP) with the mean field (MF) approximation are well-suited for inference of both continuous and discrete random variables. In wireless scenarios involving detection of multiple signals, the standard construction of the combined BP-MF framework includes the equalizat…
StrGNN detects anomalies in dynamic graphs by analyzing subgraphs and temporal features.
problem Detecting anomalies in dynamic graphs with structural changes.
method StrGNN is an end-to-end model that uses structural subgraphs and temporal features for anomaly detection.
result StrGNN effectively detects anomalies in dynamic graphs, as shown by extensive experiments.
Sub2vec learns subgraph features for network mining tasks.
problem Lack of effective subgraph feature representations for mining tasks.
method Sub2vec, an unsupervised algorithm to learn feature representations of subgraphs.
result Sub2vec preserves local proximity and offers significant gains over state-of-the-art methods.
Network detection is an important capability in many areas of applied research in which data can be represented as a graph of entities and relationships. Oftentimes the object of interest is a relatively small subgraph in an enormous, potentially uninteresting background. This aspect characterizes network detection as …
Polynomial-time test for detecting dense subgraphs in heterogeneous networks.
problem Detecting a planted community in heterogeneous networks.
method Proposes a polynomial-time test with a standard normal distribution null limiting distribution.
result The test is efficient and performs well in both simulations and real data.
We consider the problem of detecting a tight community in a sparse random network. This is formalized as testing for the existence of a dense random subgraph in a random graph. Under the null hypothesis, the graph is a realization of an Erdös-Rényi graph on vertices and with connection probability ; under the …
New tests detect communities in dense bipartite graphs with high accuracy.
problem Detecting communities in dense bipartite graphs with high accuracy.
method Non-asymptotic upper and lower bounds, novel minimax-optimal tests, hard-thresholded nonlinear statistics.
result Non-asymptotic upper and lower bounds match for any configuration of graph sizes.
GLSearch uses GNN to learn efficient search strategies for finding large common subgraphs.
problem Finding the Maximum Common Subgraph (MCS) between two graphs is NP-hard and hard to solve efficiently.
method GLSearch combines GNN and DQN to learn optimal node pairs for expansion in a branch and bound algorithm.
result GLSearch finds significantly larger common subgraphs than heuristic search methods given the same computation budget.
New dataset and techniques detect money laundering patterns in crypto.
problem Detecting money laundering in cryptocurrency networks.
method Subgraph representation learning using scalable GNNs.
result Accurately classify new criminal activity in cryptocurrency.
SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Searchstat.ML
SubSearch detects graph outliers and estimates SBM parameters robustly.
problem Real-world graphs often deviate from ideal SBM assumptions.
method Subgraph search to find subgraphs that align with SBM assumptions.
result SubSearch accurately estimates SBM parameters and detects outliers.
Spectral algorithms solve optimal community detection and related problems.
problem Optimal detection of community structures and related substructures.
method Spectral algorithms applied to various planted substructures.
result Spectral algorithms achieve optimal performance for a wide range of planted substructures.
Edge augmentation connects disconnected graphs by elevating eigenvalues.
problem Connecting disconnected subgraphs in graphs with zero eigenvalues.
method Elevating zero eigenvalues of graph's spectrum to connect subgraphs.
result The algorithm consistently connects graph components, achieving >50% inter-community edges.
Unified method detects and localizes anomalous cliques in inhomogeneous networks.
problem Detect and localize anomalous cliques in inhomogeneous networks.
method Unified method based on egonets for detection and localization.
result Unified method can detect and localize anomalous cliques in inhomogeneous networks.
Estimates the number of connected components in a graph from a sampled subgraph.
problem Inferring the number of connected components in a larger graph from a sampled subgraph.
method A highly redundant and large-dimensional representation of the subgraph using counts of network motifs, leading to a novel estimator for the number of connected components.
result Improves upon competing algorithms for graphs with spectral gaps bounded away from zero.
EnsemFDet detects fraud by solving subproblems on small graphs, scaling up e-commerce fraud detection.
problem Detecting and preventing fraud in e-commerce, especially in large-scale bipartite graphs.
method EnsemFDet uses an ensemble approach to decompose the problem into smaller subproblems, solving them in parallel.
result EnsemFDet is up to 100x faster than state-of-the-art methods while maintaining high accuracy.
DSL learns discriminative subgraphs from graphs for robust prediction.
problem Learning discriminative subgraphs from graph data for robust prediction.
method Discriminative Subgraph Learning (DSL) framework that enforces sparsity, connectivity, and high discriminative power.
result DSL improves prediction accuracy by up to 16% compared to baselines.
The Pachner graph of 2-spheres is studied, focusing on subgraphs of flag and stacked 2-spheres.
problem Characterize subgraphs of the Pachner graph of 2-spheres.
method Analyzes various induced subgraphs of the Pachner graph of -vertex triangulated 2-spheres, proving connectivity and providing bounds on the number of connected components.
result The subgraph of -vertex flag 2-spheres is connected, while the subgraph of -vertex stacked 2-spheres has at least as many connected components as trees with specific properties.
The paper introduces subgraph nomination for finding similar subgraphs in networks.
problem Finding similar subgraphs in networks using example subgraphs.
method Formalizes subgraph nomination framework with user-supervised retrieval.
result User-supervised retrieval improves performance in subgraph nomination.
Estimates graph connected components from sampled subgraphs.
problem Estimating the number of connected components in large graphs from subgraph samples.
method Subgraph sampling model, focusing on chordal graphs.
result Optimal sample complexity and linear-time estimators for chordal graphs.
SubGNN tackles subgraph prediction challenges in graphs.
problem Subgraphs in graphs are challenging to predict due to their internal topology and external connectivity.
method SubGNN introduces a novel subgraph routing mechanism to learn disentangled subgraph representations.
result SubGNN achieves considerable performance gains on subgraph classification tasks, outperforming strong baseline methods.
GEM detects malicious accounts using adaptive embeddings from heterogeneous graphs.
problem Detecting malicious accounts on a leading mobile payment platform.
method Adaptive learning of discriminative embeddings from heterogeneous account-device graphs with attention mechanism for node importance.
result GEM consistently outperforms competitive methods in detecting malicious accounts.
This work presents a novel modeling and analysis framework for graph sequences which addresses the challenge of detecting and contextualizing anomalies in labelled, streaming graph data. We introduce a generalization of the BTER model of Seshadhri et al. by adding flexibility to community structure, and use this model …
Two new algorithms speed up community detection in large networks.
problem Community detection in large networks.
method Divide-and-conquer approach on small subgraphs.
result Consistent clustering results without losing accuracy.
Subgraph Entropymath.GT
Metric graphs have subgraphs with entropy at least λ.
problem Finding subgraphs with high entropy in metric graphs.
method Proving existence of subgraphs with entropy at least λ for graphs of rank r with entropy 1.
result Metric graphs have subgraphs with entropy at least λ.
Method finds interestingly dense subgroup connections in graphs.
problem Understanding patterns in graph connectivity based on node attributes.
method Information-theoretic definition of interestingness for subgroup connections.
result Identifies pairs of node subgroups with high or low edge density.
Extracts airways from 3D CT data using graph refinement methods.
problem Extracting airway trees from volumetric CT data.
method Two methods: mean-field approximation and graph neural networks.
result Both methods improve airway detection accuracy.
Proposes GIB for recognizing informative subgraphs in graphs.
problem Recognizing a subgraph that is maximally informative yet compressive.
method Graph Information Bottleneck (GIB) framework, mutual information estimator, bi-level optimization, connectivity loss.
result IB-subgraph improves graph classification, interpretation, and denoising.
RAW-Explainer generates interpretable subgraph explanations for link predictions in knowledge graphs.
problem Interpreting GNN predictions for link prediction in heterogeneous settings is challenging.
method RAW-Explainer uses random walk objective and neural network to generate connected, concise subgraph explanations.
result RAW-Explainer strikes a balance between explanation quality and computational efficiency.
The fine curve graph is hyperbolic and contains all countable graphs as induced subgraphs.
problem Characterizing the structure and properties of fine curve graphs.
method Analyzing the hyperbolicity and induced subgraph properties of fine curve graphs and their direct limits.
result The finitary curve graph has diameter 2, contains every countable graph as an induced subgraph, and has the homeomorphism group of the surface as its automorphism group.
New findings on hyperbolicity of fine curve graphs and their subgraphs.
problem Investigating hyperbolicity of fine curve graphs and their subgraphs.
method Analyzing large subgraphs of fine curve graphs and computing distances in specific cases.
result Large subgraphs of fine curve graphs contain flats of every finite dimension, indicating they are not hyperbolic.
A method to reconstruct subgraphs in Gaussian graphical models with limited information.
problem Reconstructing subgraphs in social networks with limited interaction data.
method Penalized likelihood approach using convex-concave iterative optimization.
result The method can accurately reconstruct subgraphs even with partial information.
Detects dense subhypergraphs in random hypergraphs using low-degree polynomials.
problem Detecting a planted dense subhypergraph in a random hypergraph model.
method Degree-n^o(1) polynomials of adjacency tensor entries.
result Thresholds for detection in different density regimes.
We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two connected induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistics a…
We consider supervised learning problems where the features are embedded in a graph, such as gene expressions in a gene network. In this context, it is of much interest to automatically select a subgraph with few connected components; by exploiting prior knowledge, one can indeed improve the prediction performance or o…
Graph neural networks struggle with counting certain substructures in graphs.
problem Detecting and counting specific substructures in graphs.
method Study of graph neural networks' ability to count attributed graph substructures.
result Graph neural networks like MPNNs, 2-WL, and 2-IGNs have limitations in counting certain substructures.
A new algorithm reduces graph complexity for better dense subgraph analysis.
problem Mining dense subgraphs in large graphs for better analysis.
method Multi-stage graph peeling algorithm (M-PA) with two-stage data screening.
result M-PA produces similar dense subgraphs to the previous PA but with reduced graph complexity.
Ripple Walk Training: A Subgraph-based training framework for Large and Deep Graph Neural Networkcs.LG
Ripple Walk Training tackles graph neural network training issues for large and deep graphs.
problem Neighbors explosion, node dependence, and oversmoothing in large and deep GNNs.
method Subgraph-based training framework with Ripple Walk Sampler for high-quality subgraph sampling.
result RWT improves training efficiency and reduces space complexity for deep and large GNNs.
Survey of methods for detecting fraud in networks.
problem Detecting anomalies in graph-based data for fraud detection.
method Anomaly detection techniques using graph structure and attributes.
result Survey of various methods for fraud detection in networks.
Detects adversarial inputs in neural networks using topological analysis.
problem Identifying inputs that adversarial attacks can manipulate.
method Viewing neural networks as graphs, comparing differences in induced graphs using persistent homology.
result The structure of the most persistent subgraphs differs between adversarial and unperturbed inputs.
Efficiently recovers network community structure from clients' small subgraphs.
problem Recovering community structure in federated myopic learning settings.
method Developed an algorithm to compute consensus signed weighted graph from clients' evidence.
result Exact recovery of network structure is possible in polynomial time under certain conditions.
A new method speeds up community detection in graphs.
problem Efficiently detecting communities in large graphs.
method Subsampled semidefinite programming for faster clustering.
result Statistical limits of sketching for community detection established.
The paper studies estimating motif counts in network samples.
problem Estimating motif counts in network samples using subgraph and neighborhood sampling.
method Statistical analysis of subgraph and neighborhood sampling schemes for motif counts.
result Optimal sampling ratios and estimators for motif counts under both sampling models.