Discovering Bands from Graphs
Discovering the underlying structure of a given graph is one of the fundamental goals in graph mining. Given a graph, we can often order vertices in a way that neighboring vertices have a higher probability of being connected to each other. This implies that the edges form a band around the diagonal in the adjacency matrix. Such structure may rise for example if the graph was created over time: each vertex had an active time interval during which the vertex was connected with other active vertices. The goal of this paper is to model this phenomenon. To this end, we formulate an optimization problem: given a graph and an integer $K$, we want to order graph vertices and partition the ordered adjacency matrix into $K$ bands such that bands closer to the diagonal are more dense. We measure the goodness of a segmentation using the log-likelihood of a log-linear model, a flexible family of distributions containing many standard distributions. We divide the problem into two subproblems: finding the order and finding the bands. We show that discovering bands can be done in polynomial time with isotonic regression, and we also introduce a heuristic iterative approach. For discovering the order we use Fiedler order accompanied with a simple combinatorial refinement. We demonstrate empirically that our heuristic works well in practice.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MiningSimilar Papers 제목 키워드 기반
Approximation algorithms for confidence bands for time series
Confidence intervals are a standard technique for analyzing data. When applied to time series, confidence intervals are computed for each time point separately. Alternatively, we can compute confidence bands, where we ar…
Time SeriesTime Series AnalysisEvaluating structure learning algorithms with a balanced scoring function
Several structure learning algorithms have been proposed towards discovering causal or Bayesian Network (BN) graphs. The validity of these algorithms tends to be evaluated by assessing the relationship between the learnt…
Discovering Locally Maximal Bipartite Subgraphs
Induced bipartite subgraphs of maximal vertex cardinality are an essential concept for the analysis of graphs. Yet, discovering them in large graphs is known to be computationally hard. Therefore, we consider in this wor…
Many Circuits, One Mechanism: Input Variation and Evaluation Granularity in Circuit Discovery
Circuit discovery methods identify subgraphs that explain specific model behaviors, and structural differences between discovered circuits are commonly interpreted as evidence of distinct mechanisms. We test this assumpt…
UrbanDS: A Graph-Guided LLM Multi-Agent System for Data-Intensive Urban Tasks
Large language model (LLM) agents have been widely applied in automating data science tasks. However, existing methods typically rely on a limited set of provided datasets, and they face challenges in data-intensive scen…