Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs 0.6
0.3
Chengjie Gu1 , Xiaoliang Xu1 , Yuxiang Wang1 , Kai Yao2 Mengzhao Wang1 , Tianxing Wu3 , Yingjie Xia1 , Xiangyu Ke4 1 Hangzhou Dianzi University, China; 2 Sichuan normal university, China; 0.9
3 Southeast University, China; 4 Zhejiang University, China
chengjiegu,xxl,lsswyx,[email protected], [email protected], [email protected],xiayingjie,[email protected] v0
PVLDB Reference Format: Chengjie Gu1 , Xiaoliang Xu1 , Yuxiang Wang1 , Kai Yao2 Mengzhao Wang1 , Tianxing Wu3 , Yingjie Xia1 , Xiangyu Ke4 . Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs. PVLDB, 20(1): XXX-XXX, 2027. doi:XX.XX/XXX.XX PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at URL_TO_YOUR_ARTIFACTS. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing [email protected]. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. 20, No. 1 ISSN 2150-8097. doi:XX.XX/XXX.XX
v1
v2
v0 0.9
0.8
A representative possible world (RPW) is a deterministic graph derived from an uncertain graph G where a designated structural feature closely approximates its expected value in G. Serving as a proxy for G, the RPW allows conventional deterministic algorithms to be directly executed on it for mining tasks targeting this feature, thereby avoiding computationally expensive enumeration or sampling on G. Existing studies on RPWs primarily focus on individual node features, e.g., degree or triangle degree. However, many mining tasks, such as link prediction, critically rely on the number of common neighbors between two nodes, which is a pairwise feature. To bridge this gap, we study the Common-neighbor-count-based Representative Possible World (CRPW) problem, extending RPWs from preserving node-level statistics to preserving pairwise structural relationships. The problem seeks the possible world that best preserves the expected numbers of common neighbors between node pair, and we prove that is NP-hard. To address it, we develop a two-stage basic algorithm that quickly initializes a possible world and then refines it iteratively. We next accelerate the refinement by replacing its costly floating-point evaluation with an efficient integer counting strategy, as the refinement only requires determining whether a change is beneficial, rather than computing its exact magnitude. Moreover, we design a Beta-based adaptive termination method to automatically stop the refinement once the desired quality of the possible world is reached, preventing over- or under-execution. Extensive experiments on real-world uncertain graphs demonstrate the effectiveness of our algorithms on diverse mining tasks. Especially on common-neighbor-related tasks, we achieve the best performance among all compared methods.
0.8
arXiv:2607.23085v1 [cs.DB] 25 Jul 2026
ABSTRACT
0.9
v5
v1
v4
v2
v5 v4
v3
v3
(a) Uncertain graph
(b) A possible world preserving triangle degree
v0 v1
Total discrepancy
v5 v4
v2
Possible Possible world of (b) world of (c)
Triangle degree
1.31
1.31
Number of common neighbors
8.48
4.68
Jaccard coefficient
1.70
0.78
v3 (c) A possible world preserving the number of common neighbors
(d) Total discrepancies from the expected values of three features
Figure 1: (a) An uncertain graph, (b-c) two of its possible worlds preserving the triangle degree and the number of common neighbors respectively, and (d) their total discrepancies from the expected values of three structural features.
1
INTRODUCTION
Graphs are widely used across scientific and industrial domains, where nodes represent objects and edges reflect the connections among them. In emany real-world scenarios, such connections canSelected edge: v v Gi Si (ev v ) = {ev v , ev v , ev v , ev v } not be observed or prev0 with certainty, v0 but are instead estimated v0 dicted, and are thus inherently associated with an existence probav1 v5 v1 v v0 bility. In protein-protein interaction networks,1 an interaction bev1throughv5noisy biological experv4 is established v2 proteins tween two v2 v3 derived from v3 iments and therefore holds only with a confidence experimental evidence [3, 13]. In social networks, (a) Possible World Gi (b) (c) (d) the influence or trust between two users is estimated from their interaction history, yielding a probabilistic connection [5, 22]. In knowledge graphs, relations are extracted by automated tools that often with errors, so each extracted edge carries a confidence score [8, 31]. To faithfully capture such uncertainty, uncertain graphs [27] are employed, in which each edge is annotated with an existence probability varies in [0, 1]. Figure 1(a) illustrates an uncertain graph with six nodes {𝑣 0, . . . , 𝑣 5 }, where the number attached to each edge is its existence probability, e.g., the edge 𝑒 𝑣0 𝑣1 exists with probability of 0.6. For clarity, edges with zero existence probability are often omitted. To interpret the semantics of uncertain graphs, the possible world model is widely adopted [6, 11, 32, 38, 40]. Under this model, each edge with existence probability 𝑝 is independently observed to be either present with probability 𝑝 or absent with probability 0 1
0 1
0 2
0 5
1 5
1 3
1 − 𝑝. After observing all edges, we then yields a possible world, i.e., a deterministic graph that retains exactly the edges observed to be present. Owing to the independence of the observations, such a possible world occurs with a probability equal to the product of existence probabilities of its present edges and non-existence probabilities of its absent ones. For example, Figure 1(b) shows a possible world of the uncertain graph in Figure 1(a), consisting of seven edges observed to be present while the other four edges are absent. The occurrence probability of such a possible world multiplies the existence probabilities {0.8, 0.5, 0.8, 0.3, 0.6, 0.9, 0.8} of all present edges {𝑒 𝑣0 𝑣3 , 𝑒 𝑣0 𝑣5 , 𝑒 𝑣1 𝑣2 , 𝑒 𝑣1 𝑣3 , 𝑒 𝑣1 𝑣4 , 𝑒 𝑣2 𝑣4 , 𝑒 𝑣3 𝑣5 } and the non-existence probabilities {1−0.6, 1−0.2, 1−0.9, 1−0.8} of all absent edges {𝑒 𝑣0 𝑣1 , 𝑒 𝑣0 𝑣2 , 𝑒 𝑣1 𝑣5 , 𝑒 𝑣2 𝑣3 }, yielding the result of 2.65 × 10−4 .
triangles gives the expected triangle degree of 𝑣 5 . This sum evaluates to 𝑝 (𝑒 𝑣5 𝑣0 ) 𝑝 (𝑒 𝑣5 𝑣3 ) 𝑝 (𝑒 𝑣0 𝑣3 ) + 𝑝 (𝑒 𝑣5 𝑣0 ) 𝑝 (𝑒 𝑣5 𝑣1 ) 𝑝 (𝑒 𝑣0 𝑣1 ) + · · · = 0.5×0.8×0.8+0.5×0.6×0.9+· · · = 0.81 in the uncertain graph, while 𝑣 5 has a triangle degree of 1 in Figure 1(b), staying close to its expected value. Preserving triangle degree in representative possible world shows potential for many common neighbor-relevant mining tasks, including: link prediction where candidate node pairs are ranked by their numbers of common neighbors [12, 26, 39]; Jaccard coefficient computation of two nodes that is directly derived from their common neighbors [23]; overlapping community detection, which groups nodes sharing more common neighbors into the same community [2, 20, 37]. Despite this, a triangle degree-preserving representative possible world is prone to inaccuracy in some cases, as it inherently ignores common neighbors between non-adjacent nodes, which lie beyond the expressive scope of triangle degree that only captures common neighbors of adjacent nodes. We illustrate this limitation with the following example.
Under the possible world model, an uncertain graph amounts to a probability distribution over its possible worlds. Because graph topology varies across possible worlds, structural features and mining task results also vary [18, 28, 33]. We therefore use expectations over this distribution to characterize them. Simple feature expectations are often directly computable from edge probabilities; e.g., a node’s expected degree equals the sum of its incident-edge probabilities. However, mining tasks, such as the expected shortest-path distance between two nodes, depend on the graph topology and generally cannot be derived directly from individual edge probabilities. Computing such results exactly requires executing the task on every possible world and probabilistically aggregating the outputs, which is prohibitive because the number of possible worlds grows exponentially with the number of edges [4, 16]. To this end, sampling-based methods execute the mining task on sampled possible worlds and use their outputs to estimate the target result [17, 29]. However, achieving sufficient estimation accuracy often requires a large sample size, incurring substantial overhead from possibleworld generation and repeated task execution [7]. Therefore, a more promising approach is to construct a single representative possible world (RPW) tailored to a designated structural feature [27]. An RPW closely approximates the expected value of this feature in the original uncertain graph while providing a complete deterministic topology. Consequently, for mining tasks driven by this feature, a conventional deterministic algorithm need only be executed once on the RPW, yielding a faithful approximation of the corresponding expected result over the uncertain graph [27, 35].
Example 1. We use node 𝑣 2 in Figure 1(b) to illustrate the limitation of triangle degree. 𝑣 2 belongs to the triangle (𝑣 1, 𝑣 2, 𝑣 4 ) and thus has a triangle degree of 1. This triangle captures the common-neighbor relationships between 𝑣 2 and its adjacent nodes 𝑣 1 and 𝑣 4 . However, the triangle degree of 𝑣 2 can not account for the common neighbors it shares with 𝑣 0 . In Figure 1(a), the expected common-neighbor count between 𝑣 0 and 𝑣 2 is 𝑝 (𝑒 𝑣0 𝑣1 )𝑝 (𝑒 𝑣1 𝑣2 ) + 𝑝 (𝑒 𝑣0 𝑣3 )𝑝 (𝑒 𝑣2 𝑣3 ) = 0.6 × 0.8 + 0.8 × 0.8 = 1.12, whereas their actual count in Figure 1(b) is zero. This is because 𝑒 𝑣0 𝑣2 is absent, any common neighbor shared by 𝑣 0 and 𝑣 2 cannot form a triangle with them, leaving this discrepancy unreflected in any node’s triangle degree. Hence, preserving individual nodes’ triangle degrees does not ensure accurate preservation of common-neighbor counts, particularly for non-adjacent node pairs. Motivated by the aforementioned discussion, in this paper, we study the Common-neighbor-count-based Representative Possible World (CRPW), which directly preserves the expected number of common neighbors between two nodes in an uncertain graph G. As shown in Figure 1(a), the expected number of common neighbors between 𝑣 0 and 𝑣 2 is 1.12. Figure 1(c) illustrates the CRPW that we aim for, it maintains this count at 1, yielding a minor discrepancy of 1.12 − 1 = 0.12. In contrast, the triangle-degree-preserving possible world in Figure 1(b) yields zero common neighbors, resulting in a larger discrepancy of 1.12. When aggregated over all node pairs, the total discrepancy of the number of common neighbors for Figure 1(c) is merely 4.68, lower than the 8.48 of the possible world preserving the triangle degree in Figure 1(b). This advantage extends to other common-neighbor-driven metrics, such as the Jaccard coefficient. As shown in Figure 1(d), the CRPW from Figure 1(c) achieves smaller discrepancies in both common neighbor count and Jaccard coefficient (0.78 vs. 1.7), while preserving the identical triangle degree as the possible world in Figure 1(b).
Prior studies and motivation. The representative possible world was first studied in [27], which constructs one that preserves the degree of each node. This degree-preserving representative possible world has proven effective for mining tasks that relevant to node degrees, such as computing shortest-path distance and betweenness centrality [27]. However, as Song et al. [35] point out, the degree of a node only describes how many neighbors it has, whereas triangles, a basic motif shaping the structure of realworld graphs, are left out. They therefore construct the trianglebased representative possible world that additionally preserves the triangle degree of each node, i.e., the number of triangles containing the node. Figure 1(b) is such a triangle-based representative possible world obtained from Figure 1(a). We use node 𝑣 5 as an example. Each triangle incident to 𝑣 5 in Figure 1(a) appears with probability equal to the product of the existence probabilities of its three edges. Summing this probability over all such
Challenges and our solutions. we face two non-trivial challenges for solving the CRPW problem. Challenge I: How to efficiently construct a CRPW? A brute-force approach to construct the CRPW would enumerate all possible worlds and select the one that best preserves the expected number of common neighbors. However, given an uncertain graph with the edge set E where each edge is independently present or absent, the search space grows exponentially to 2 | E | possible worlds, rendering 2
exhaustive enumeration computationally infeasible for large uncertain graphs. We further prove that the CRPW problem is NP-hard (§2.2), precluding the existence of an exact polynomial-time algorithm. Consequently, efficiently constructing a high-quality CRPW poses a significant algorithmic challenge. Solution I. To address this challenge, we resort to a heuristic that constructs a CRPW through iterative local refinement instead of entirely enumeration. The effectiveness of such a local refinement paradigm has been validated in prior studies on representative possible worlds that preserve degree and triangle degree [27, 35]. We present a two-stage basic algorithm in §3. It first rapidly initializes a possible world and then refines it iteratively. In each iteration, it randomly selects an edge and change its existence status, provided that this modification reduces the discrepancy between the commonneighbor counts in the current possible world and their expected values in the original uncertain graph. The key to this refinement lies in efficiently evaluating the impact of an edge state change. We precisely characterize the edges whose endpoints’ common neighbors are affected by such an edge state change, and record them in an edge influence set. Each impact evaluation is thus localized to this set rather than the entire graph, thereby accelerating the refinement process. We further optimize the refinement in §4. Specifically, we observe that the decision to change an edge state does not require computing its exact impact; it only requires determining whether the change is beneficial. Building on this insight, we replace the costly floating-point evaluation of the exact impact with an efficient integer counting strategy, further boosting the overall efficiency.
that the desired quality has been reached. Refinement terminates automatically once this confidence reaches a user-specified threshold, avoiding both insufficient and excessive iterations. Contribution. The main contributions are summarized as follows. • We propose the CRPW, a representative possible world that best preserves the expected numbers of common neighbors (§2.1), and prove that finding a CRPW is NP-hard (§2.2). • We present a two-stage basic algorithm that initializes a possible world and iteratively refine it (§3), along with an optimized algorithm that replaces costly floating-point evaluations with efficient integer counting (§4). • We design a Beta-based adaptive termination method that assesses refinement quality through edge sampling and terminates automatically once the user-desired quality is attained with sufficient confidence (§5). • We conduct extensive experiments on four real-world uncertain graphs to evaluate the effectiveness (§6.2), the efficiency (§6.3), the Beta-based adaptive termination (§6.4), and the parameter sensitivity (§6.5) of our algorithms.
2 PRELIMINARIES 2.1 Problem Definition Definition 1 (Uncertain Graph [27]). An uncertain graph G = (V, E, P) involves a node set V, an edge set E, and a function P : E → (0, 1] that assigns an existence probability 𝑝 (𝑒𝑢𝑣 ) ∈ (0, 1] to each undirected edge 𝑒𝑢𝑣 ∈ E between two nodes 𝑢 and 𝑣 in V. For simplicity, we omit the subscript of an edge when necessary.
Challenge II: How can the desired quality of the possible world be assessed during refinement to achieve adaptive termination? Algorithms based on the local refinement paradigm that tailored for constructing representative possible world, including our proposed approach, control the refinement process via a user-specified iteration count. However, determining an appropriate iteration budget is inherently challenging. The exact number of iterations required to achieve a good representative possible world is generally unknown and varies significantly across different uncertain graphs. Consequently, an explicit iteration count is fundamentally inflexible: an insufficient budget leads to premature termination and suboptimal representative graph quality, while an excessive budget incurs unnecessary computational overhead once the target quality is already met. This calls for the ability to perceive the quality of the possible world during refinement, enabling the algorithm to adaptively terminate once the desired quality is achieved. Solution II. To address this challenge, we present a Beta-based adaptive termination method in §5.As the refinement proceeds, fewer edges remain whose state changes can further reduce the discrepancy between the common-neighbor counts in the possible world and their expected values. We refer to such edges as state-changeable edges and use their proportion among all edges, termed the statechangeable edge proportion (SEP), to measure the refinement quality: a smaller SEP indicates a better-refined possible world. Since traversing all edges to compute the SEP exactly is infeasible, we estimate it through edge sampling and model the uncertainty using a Beta distribution. Under this distribution, the probability that the true SEP is below a user-specified quality threshold measures the confidence
Under the context of uncertain graph, observing any probabilistic edge 𝑒 ∈ E yields two outcomes: the edge is present with probability 𝑝 (𝑒) or absent with probability 1 − 𝑝 (𝑒). As a result, the topology of uncertain graph is nondeterministic and can change across different observations. To model this uncertainty and faithfully express the semantics of uncertain graphs, researchers commonly adopt the possible world model [6, 11, 28, 32, 38, 40], with the definition below. Definition 2 (Possible World [27]). Given an uncertain graph G = (V, E, P), a possible world 𝐺 = (𝑉 , 𝐸) of G is a deterministic graph derived from G, where 𝑉 = V and 𝐸 ⊆ E. With the possible world model, the independence of edge existence is a widely adopted assumption [16, 17, 30], facilitating the calculation of the existing probability of a specific possible world 𝐺. We denote the event that the uncertain graph G is observed as one possible world 𝐺 by 𝐺 ⊑ G. The probability of the event 𝐺 ⊑ G is then calculated by Eq. 1, denoted by 𝑃 {𝐺 ⊑ G} (shorten as 𝑃 {𝐺 } when no ambiguity arises). 𝑃 {𝐺 ⊑ G} =
Ö 𝑒 ∈𝐸
𝑝 (𝑒)
Ö
(1 − 𝑝 (𝑒))
(1)
𝑒 ∈ E\𝐸
Under the possible world model, an uncertain graph induces a distribution over all possible worlds, and a structural feature, such as the degree of a node, takes different values across different possible worlds [18, 28, 33]. To enable graph mining on uncertain graphs, existing works construct a representative possible world, i.e., a deterministic graph from the possible worlds that best preserves a task-relevant structural feature in expectation, thereby 3
Problem 1 (CRPW Problem). Given an uncertain graph G = (V, E, P), the CRPW Problem aims to find a possible world 𝐺 ⊑ G such that it has the smallest total discrepancy w.r.t. G, given by Eq. 6.
transforming mining on uncertain graphs to a deterministic one. Differ from prior works, in this paper, we focus on identifying the representative possible world that preserves the numbers of common-neighbors, to better support mining task relied on that feature.
𝐺 = arg min 𝑑𝑖𝑠 G (𝐺)
Definition 3 (Common Neighbors). Given a possible world 𝐺 = (𝑉 , 𝐸) and two nodes 𝑢, 𝑣 ∈ 𝑉 , the common neighbors between 𝑢 and 𝑣 in 𝐺, denoted as 𝐶𝐺 (𝑢, 𝑣), is defined as Eq. 2, where 𝑁𝐺 (𝑢) (𝑁𝐺 (𝑣)) is the set of neighbors of node 𝑢 (𝑣) in 𝐺. 𝐶𝐺 (𝑢, 𝑣) = 𝑁𝐺 (𝑢) ∩ 𝑁𝐺 (𝑣)
2.2
Analysis of Problem Complexity
We establish that the CRPW Problem is NP-hard. Since NP-hardness is defined over decision problems, we investigate the decision version of the CRPW Problem, which is formulated below. Problem 2 (CRPW Decision Problem). Given an uncertain graph G ∗ = (V ∗, E ∗, P ∗ ) and a threshold 𝑇 , the CRPW Decision Problem determines whether there exists a possible world 𝐺 ∗ ⊑ G ∗ such that the total discrepancy 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) ≤ 𝑇 .
(2)
For nodes 𝑢 and 𝑣 in a possible world 𝐺, we denote the number of their common neighbors by |𝐶𝐺 (𝑢, 𝑣)|. In the uncertain graph, this quantity becomes a random variable over possible worlds. We therefore consider its expectation, defined as follows.
Generally, the decision version of a problem is no harder than its optimization version [21]: any polynomial-time algorithm for the CRPW Problem also solves the CRPW Decision Problem, by computing the total discrepancy of the returned possible world and comparing it against 𝑇 . Thus, if the CRPW Decision Problem is NP-hard, then the CRPW Problem is NP-hard as well. Therefore, we focus on proving the NP-hardness of the CRPW Decision Problem.
Definition 4 (Expected Number of Common Neighbors). Given an uncertain graph G = (V, E, P) and two nodes 𝑢, 𝑣 ∈ V, their expected number of common neighbors 𝐶 G (𝑢, 𝑣) is shown in Eq. 3, where 𝐶 G (𝑢, 𝑣) denotes the set of common neighbors of 𝑢 and 𝑣 within the topological structure of G, ignoring edge probabilities. ∑︁ 𝐶 G (𝑢, 𝑣) = 𝑝 (𝑒𝑢𝑤 ) · 𝑝 (𝑒 𝑣𝑤 ) (3)
Theorem 1. The CRPW Decision Problem is NP-hard.
𝑤 ∈𝐶 G (𝑢,𝑣)
Proof. We prove the NP-hardness of the CRPW Decision Problem by a reduction from the Monotone 1-in-3 3SAT problem, a well-known NP-complete problem [34]. An instance of Monotone 1-in-3 3SAT consists of 𝑦 Boolean variables 𝐵 1, . . . , 𝐵 𝑦 and 𝑧 clauses 𝐴1, . . . , 𝐴𝑧 , where each clause contains exactly three positive variables (no negations). The Monotone 1-in-3 3SAT instance is satisfiable if there exists a truth assignment such that every clause has exactly one true variable. Our reduction maps a Monotone 1-in-3 3SAT instance to an uncertain graph G ∗ with a threshold 𝑇 , such that the Monotone 1-in-3 3SAT instance is satisfiable if and only if (G ∗,𝑇 ) is a Yes-instance of the CRPW Decision Problem. The two sides are stated in different languages: one is Boolean satisfiability, the other is the minimum total discrepancy over possible worlds. To establish this equivalence, we proceed in the following four steps.
Intuitively, a possible world 𝐺 is a representative instance of an uncertain graph G regarding common neighbors if the count for any two nodes 𝑢 and 𝑣 in 𝐺 closely approximates its expected value in G, that is, the discrepancy between them is small. Since nodes 𝑢 and 𝑣 uniquely determine the edge 𝑒𝑢𝑣 , we term this discrepancy in their common neighbors as the edge discrepancy for convenience. Definition 5 (Edge Discrepancy). Given an uncertain graph G = (V, E, P), a possible world 𝐺 ⊑ G, and an edge 𝑒𝑢𝑣 ∈ E, the edge discrepancy of 𝑒𝑢𝑣 is defined as the difference between the number of common neighbors of 𝑢 and 𝑣 in 𝐺 and their expected number of common neighbors in G, formally expressed as below. 𝑑𝑖𝑠𝐺 ⊑ G (𝑒𝑢𝑣 ) = |𝐶𝐺 (𝑢, 𝑣)| − 𝐶 G (𝑢, 𝑣)
(6)
𝐺⊑G
(4)
Step 1. Construction of the uncertain graph G ∗ . Given a Monotone 1-in-3 3SAT instance with boolean variables 𝐵 1, . . . , 𝐵 𝑦 and clauses 𝐴1, . . . , 𝐴𝑧 , we construct the uncertain graph G ∗ = (V ∗, E ∗, P ∗ ) as follows. (1) For node set V ∗ , it consists of: a center node 𝑐; a boolean variable node 𝑏𝑖 for each boolean variable 𝐵𝑖 ; and a clause node 𝑎 𝑗 for each clause 𝐴 𝑗 . (2) For edge set E ∗ , it consists of three types of edges. A variable edge 𝑒𝑐𝑏𝑖 connects the center node 𝑐 and the boolean variable node 𝑏𝑖 . A clause edge 𝑒𝑐𝑎 𝑗 connects the center node 𝑐 and the clause node 𝑎 𝑗 . A connection edge 𝑒𝑎 𝑗 𝑏𝑖 connects the clause node 𝑎 𝑗 and the boolean variable node 𝑏𝑖 , and is present only when boolean variable 𝐵𝑖 appears in clause 𝐴 𝑗 . (3) For existence probabilities P ∗ , we set 𝑝 (𝑒𝑐𝑏𝑖 ) = 13 for every variable edge and 𝑝 (𝑒𝑐𝑎 𝑗 ) = 𝑝 (𝑒𝑎 𝑗 𝑏𝑖 ) = 1 for every clause edge and connection edge. The presence of a variable edge in a possible world encodes 𝐵𝑖 = True, and its absence encodes 𝐵𝑖 = False. We set its probability to 13 so that the expected number of common neighbors between the endpoints of each clause edge 𝑒𝑐𝑎 𝑗 equals 3 × 13 = 1. This encodes the 1-in-3 condition of clause 𝐴 𝑗 into the discrepancy of 𝑒𝑐𝑎 𝑗 . The clause edges and connection edges are assigned
For brevity, we denote 𝑑𝑖𝑠𝐺 ⊑ G (𝑒𝑢𝑣 ) by 𝑑𝑖𝑠𝐺 (𝑒𝑢𝑣 ) when the context is clear. Based on Definition 5, we further define the total discrepancy of a possible world 𝐺 w.r.t. an uncertain graph G. Definition 6 (Total Discrepancy). Given an uncertain graph G = (V, E, P), a possible world 𝐺 ⊑ G, the total discrepancy of 𝐺, denoted as 𝑑𝑖𝑠 G (𝐺), is defined as the sum of the absolute values of the edge discrepancy over all edges in G, given by Eq. 5. ∑︁ 𝑑𝑖𝑠 G (𝐺) = |𝑑𝑖𝑠𝐺 ⊑ G (𝑒)| (5) 𝑒∈E
Total discrepancy provides a quantitative measure of how well a possible world 𝐺 preserves the expected number of common neighbors in the uncertain graph G. Accordingly, we seek a Commonneighbor-count-based Representative Possible World (CRPW) that minimizes this total discrepancy. A smaller discrepancy indicates a higher-quality representative possible world. Formally, the CRPW problem is defined as follows. 4
probability 1, so they are present in every possible world; therefore possible worlds differ only in which variable edges they retain. As a result, the constructed uncertain graph G ∗ has 1 + 𝑦 + 𝑧 nodes and 𝑦 + 𝑧 + 3𝑧 = 𝑦 + 4𝑧 edges, with all existence probabilities equal to 1 ∗ 3 or 1. Hence, G is constructed in polynomial time w.r.t. the size of the Monotone 1-in-3 3SAT instance, and the reduction is valid.
clauses are decoupled and the total discrepancy can be minimized by minimizing each 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) independently. Step 3. Minimum total discrepancy. We now determine the minimum total discrepancy over all possible worlds of G ∗ . By Eq. 8, the total discrepancy is the sum of the per-clause costs 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ), each minimized independently. We therefore first determine the minimum of a single 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ). Since 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) depends only on the number of boolean variables in clause 𝐴 𝑗 assigned true, i.e., Í 𝑖 ∈𝐴 𝑗 𝑥𝑖 ∈ {0, 1, 2, 3}, we enumerate the four cases: 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) = Í 2, 43 , 83 , 4 when 𝑖 ∈𝐴 𝑗 𝑥𝑖 = 0, 1, 2, 3, respectively. Hence 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) Í attains its minimum 43 uniquely when 𝑖 ∈𝐴 𝑗 𝑥𝑖 = 1, which obtained Eq. 9 with equality if and only if exactly one boolean variable in clause 𝐴 𝑗 is assigned true. 4 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) ≥ (9) 3 Summing Eq. 9 over all 𝑧 clauses gives a lower bound on the total discrepancy of any possible world, shown in Eq. 10. 𝑧 ∑︁ 4𝑧 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) = 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) ≥ (10) 3 𝑗=1
Step 2. Total discrepancy of 𝐺 ∗ ⊑ G ∗ . We next show the total discrepancy calculation of a possible world 𝐺 ∗ ⊑ G ∗ with an algebraic function. Since possible worlds differ only in which variable edges they retain, we encode this difference by an indicator 𝑥𝑖 ∈ {0, 1} for each variable edge 𝑒𝑐𝑏𝑖 , where 𝑥𝑖 = 1 if 𝑒𝑐𝑏𝑖 is present in 𝐺 ∗ and 𝑥𝑖 = 0 otherwise. Next, for each edge type, we compute the expected number of common neighbors of its endpoints in G ∗ by Definition 4, then express the edge discrepancy by Definition 5. (1) For clause edge 𝑒𝑐𝑎 𝑗 . In the topology of G ∗ , each boolean variable node 𝑏𝑖 with 𝐵𝑖 ∈ 𝐴 𝑗 is a common neighbor of 𝑐 Í and 𝑎 𝑗 . Thus 𝐶 G ∗ (𝑐, 𝑎 𝑗 ) = 𝐵𝑖 ∈𝐴 𝑗 𝑝 (𝑒𝑐𝑏𝑖 ) 𝑝 (𝑒𝑎 𝑗 𝑏𝑖 ) = 3 × 13 × 1 = 1. In 𝐺 ∗ , such a 𝑏𝑖 is a common neighbor only if its variable edge 𝑒𝑐𝑏𝑖 is present, i.e., 𝑥𝑖 = 1, so the number of common neighbor Í of 𝑎 𝑗 and 𝑏𝑖 is 𝑖 ∈𝐴 𝑗 𝑥𝑖 . Hence the edge discrepancy of 𝑒𝑐𝑎 𝑗 is Í 𝑑𝑖𝑠𝐺 ∗ (𝑒𝑐𝑎 𝑗 ) = 𝑖 ∈𝐴 𝑗 𝑥𝑖 − 1. (2) For connection edge 𝑒𝑎 𝑗 𝑏𝑖 . In the topology of G ∗ , the only common neighbor of 𝑎 𝑗 and 𝑏𝑖 is the center node 𝑐. Thus 𝐶 G ∗ (𝑎 𝑗 , 𝑏𝑖 ) = 𝑝 (𝑒𝑐𝑎 𝑗 ) 𝑝 (𝑒𝑐𝑏𝑖 ) = 13 . In 𝐺 ∗ , center node 𝑐 is a common neighbor only if the variable edge 𝑒𝑐𝑏𝑖 is present, i.e., 𝑥𝑖 = 1, so the number of common neighbor of 𝑎 𝑗 and 𝑏𝑖 is 𝑥𝑖 . Hence the edge discrepancy of 𝑒𝑎 𝑗 𝑏𝑖 is 𝑑𝑖𝑠𝐺 ∗ (𝑒𝑎 𝑗 𝑏𝑖 ) = 𝑥𝑖 − 13 . (3) For variable edge 𝑒𝑐𝑏𝑖 . In the topology of G ∗ , each clause node 𝑎 𝑗 whose clause 𝐴 𝑗 contains 𝐵𝑖 is a common neighbor of 𝑐 and 𝑏𝑖 . Thus Í Í 𝐶 G ∗ (𝑐, 𝑏𝑖 ) = 𝑗:𝐵𝑖 ∈𝐴 𝑗 𝑝 (𝑒𝑐𝑎 𝑗 ) 𝑝 (𝑒𝑎 𝑗 𝑏𝑖 ) = 𝑗:𝐵𝑖 ∈𝐴 𝑗 1, which means the number of clauses containing 𝐵𝑖 . In 𝐺 ∗ , each such 𝑎 𝑗 is connected to 𝑐 by 𝑒𝑐𝑎 𝑗 and to 𝑏𝑖 by 𝑒𝑎 𝑗 𝑏𝑖 , both of which are present, so every such 𝑎 𝑗 remains a common neighbor. Therefore the number of common neighbor of 𝑐 and 𝑏𝑖 is the number of clauses containing Í 𝐵𝑖 , i.e., 𝑗:𝐵𝑖 ∈𝐴 𝑗 1. So the edge discrepancy of 𝑒𝑐𝑏𝑖 is 𝑑𝑖𝑠𝐺 ∗ (𝑒𝑐𝑏𝑖 ) = 0. Summing the absolute edge discrepancies over all edges (Definition 6), we obtain the total discrepancy of 𝐺 ∗ ⊑ G ∗ as follows: 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) =
𝑧 ∑︁ ∑︁ 𝑗=1 𝑖 ∈𝐴 𝑗
𝑥𝑖 − 1 +
𝑧 ∑︁ ∑︁
𝑥𝑖 −
𝑗=1 𝑖 ∈𝐴 𝑗
𝑦 1 ∑︁ 0, + 3 𝑖=1
Step 4. Reduction correctness. We set the threshold 𝑇 of the CRPW Decision Problem to 𝑇 = 4𝑧3 , the minimum total discrepancy established in Eq. 10. We show that (G ∗,𝑇 ) is a Yes-instance, i.e., there exists a possible world 𝐺 ∗ with 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) ≤ 4𝑧3 , if and only if the Monotone 1-in-3 3SAT instance is satisfiable. Since 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) ≥ 4𝑧3 holds for every possible world by Eq. 10, the condition 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) ≤ 4𝑧3 is equivalent to 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) = 4𝑧3 . (⇒) Suppose the Monotone 1-in-3 3SAT instance is satisfiable. Then there is a truth assignment under which every clause has exactly one true variable. We construct a possible world 𝐺 ∗ by setting 𝑥𝑖 = 1 if 𝐵𝑖 is true and 𝑥𝑖 = 0 otherwise. Under this assignment, each clause has exactly one true variable, so 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) = 43 for every clause by Eq. 9, and thus 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) = 4𝑧3 . Hence (G ∗,𝑇 ) is a Yes-instance of the CRPW Decision Problem. (⇐) Suppose there is a possible world 𝐺 ∗ with 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) = 4𝑧3 . Í Since 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) = 𝑧𝑗=1 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) and each 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) ≥ 43 , the sum 4𝑧 equals 3 only if 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) = 43 for every clause. This forces every clause to have exactly one true variable under the assignment defined by 𝑥𝑖 , which thus satisfies the Monotone 1-in-3 3SAT instance. Combining both directions, the constructed CRPW Decision Problem instance (G ∗,𝑇 ) is a Yes-instance if and only if the Monotone 1-in-3 3SAT instance is satisfiable. Since the construction takes polynomial time and Monotone 1-in-3 3SAT is NP-complete, the CRPW Decision Problem is NP-hard. As established earlier, the NP-hardness of the CRPW Decision Problem implies that of the CRPW Problem. □
(7)
where the three terms come from the clause edges, the connection edges, and the variable edges, respectively. We next simplify the Eq.7. Since 𝑥𝑖 ∈ {0, 1}, we have |𝑥𝑖 − 31 | = 1 1 1 2 3 + 3 𝑥𝑖 : it equals 3 when 𝑥𝑖 = 0 and 3 when 𝑥𝑖 = 1. As each clause 𝐴 𝑗 contains exactly three boolean variables, summing this over the Í Í boolean variables in 𝐴 𝑗 gives 𝑖 ∈𝐴 𝑗 ( 13 + 31 𝑥𝑖 ) = 1 + 13 𝑖 ∈𝐴 𝑗 𝑥𝑖 . Substituting this into Eq. 7 and grouping all terms by clause, the total discrepancy becomes a sum of per-clause costs, 𝑑𝑖𝑠 G ∗ (𝐺 ∗ ) =
𝑧 ∑︁ 𝑗=1
𝐶𝑜𝑠𝑡 (𝐴 𝑗 ),
𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) =
∑︁ 𝑖 ∈𝐴 𝑗
𝑥𝑖 −1 +1+
The NP-hardness established above implies that finding an optimal possible world is intractable. We therefore resort to heuristics that efficiently produce a representative possible world in practice, as presented in the following sections.
1 ∑︁ 𝑥𝑖 , 3 𝑖 ∈𝐴 𝑗
(8) where 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) is the cost contributed by clause 𝐴 𝑗 , and 𝑖 ∈𝐴 𝑗 𝑥𝑖 is the number of boolean variables in clause 𝐴 𝑗 assigned true. Each 𝐶𝑜𝑠𝑡 (𝐴 𝑗 ) depends only on the boolean variables of clause 𝐴 𝑗 , so the
3
Í
BASIC ALGORITHM
To obtain a CRPW, a simple yet effective approach is to initialize a possible world from the uncertain graph and iteratively refine its 5
Algorithm 1: Probability-based Initialization
3.2
Input: uncertain graph G = ( V, E, P ) Output: an initial possible world 𝐺 0 ⊑ G 1 𝐸 ← ∅, 𝑉 ← V; 2 for 𝑒 ∈ E do 3 generate a random number 𝑟 uniformly in [0, 1]; // the acceptance-rejection mechanism 4 if 𝑟 ≤ 𝑝 (𝑒 ) then 5 add 𝑒 to 𝐸; /* accept 𝑒 */ 6 else 7 continue; /* reject 𝑒 */
After obtaining the initial possible world 𝐺 0 , we iteratively refine it by reducing the total discrepancy until a low-discrepancy CRPW 𝐺 is returned. To this end, we adopt a random selection-based refinement implemented in an iterative manner. Specifically, in the 𝑖-th iteration, we randomly select an edge 𝑒 ∈ E and consider changing its existence state in the current possible world 𝐺𝑖 , which yields a new possible world 𝐺𝑖+1 . To determine whether such a change is beneficial, we evaluate the difference in total discrepancy between 𝐺𝑖+1 and 𝐺𝑖 , referred to as the total discrepancy variation w.r.t. an edge 𝑒, which is formally defined as follows. If this variation is less than 0, the state of 𝑒 is changed, i.e., e is removed if 𝑒 ∈ 𝐺𝑖 , and added if 𝑒 ∉ 𝐺𝑖 , resulting in 𝐺𝑖+1 ; otherwise, 𝑒 remains unchanged.
8
return 𝐺 0 ← (𝑉 , 𝐸 );
total discrepancy. Therefore, in this section, we propose a two-stage basic algorithm, consisting of (1) probability-based initialization (in 3.1) and (2) random selection-based refinement (in 3.2).
3.1
Random Selection-based Refinement
Definition 7 (Total Discrepancy Variation). Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, and an edge 𝑒 ∈ E, let 𝐺𝑖+1 denote the possible world obtained by changing the existence state of 𝑒 in 𝐺𝑖 . The total discrepancy variation of 𝑒 in 𝐺𝑖 , denoted as 𝛿𝐺𝑖 ⊑ G (𝑒), is defined as the difference in total discrepancy between 𝐺𝑖+1 and 𝐺𝑖 , as shown in Eq. 13.
Probability-based Initialization
A straightforward approach is to randomly select a subset of edges from the uncertain graph G to form a possible world 𝐺. However, it fails to capture the expected topological structure of G and typically results in a large total discrepancy 𝑑𝑖𝑠 G (𝐺), thereby requiring more iterations to reduce 𝑑𝑖𝑠 G (𝐺). To avoid this, we adopt a probabilitybased initialization strategy, in which each edge 𝑒 is independently sampled according to its existence probability 𝑝 (𝑒), ensuring the sampling of 𝑒 follows a Bernoulli distribution with parameter 𝑝 (𝑒), where the edge exists with 𝑝 (𝑒) and does not exist with 1 − 𝑝 (𝑒).
𝛿𝐺𝑖 ⊑ G (𝑒) = 𝑑𝑖𝑠 G (𝐺𝑖+1 ) − 𝑑𝑖𝑠 G (𝐺𝑖 )
(13)
For brevity, we denote 𝛿𝐺𝑖 ⊑ G (𝑒) by 𝛿𝐺𝑖 (𝑒) when context is clear. Overview. Given an uncertain graph G and an initial possible world 𝐺 0 , the random selection-based refinement proceeds iteratively over 𝑘 iterations. In the 𝑖-th iteration, we randomly select an edge 𝑒𝑢𝑣 ∈ E, evaluate whether changing its existence state in the current possible world 𝐺𝑖 reduces the total discrepancy (i.e., 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0), and if so, change the state of 𝑒𝑢𝑣 to obtain 𝐺𝑖+1 . The key of random selection-based refinement is the efficient computation of 𝛿𝐺𝑖 (𝑒𝑢𝑣 ), which faces a challenge: Directly applying Eq. 13 requires traversing all edges in E to compute their edge discrepancies, whereas changing the state of 𝑒𝑢𝑣 only affects the common neighbors associated with a subset of edges, and hence only the discrepancies of those edges change; traversing the remaining edges introduces unnecessary computation. To address this challenge, we present an efficient computation of the total discrepancy variation 𝛿𝐺𝑖 (𝑒𝑢𝑣 ), which restricts the computation to the subset of edges whose discrepancies are affected by the state change of 𝑒𝑢𝑣 . Building upon this optimization, we then present the algorithm of random selection-based refinement.
Overview. Algorithm 1 outlines the process of probability-based initialization. For each edge 𝑒 ∈ E, we use the acceptance-rejection method [14] to simulate its independent sampling process (as justified in Theorem 2), where 𝑒 is accepted with 𝑝 (𝑒) and rejected with 1 − 𝑝 (𝑒) (lines 3-7). After all edges are processed, those accepted edges are collected to form the initial possible world. In Algorithm 1, we first initialize the possible world 𝐺 by setting its edge set 𝐸 to be empty and its node set 𝑉 to V (line 1). Then, for each edge 𝑒 ∈ E, we perform a sampling process as follows (lines 2-7): a random number 𝑟 is generated uniformly from the interval [0,1] (line 3). If 𝑟 ≤ 𝑝 (𝑒), the edge is accepted and added to 𝐸 (lines 4-5); otherwise, the edge is rejected and excluded from 𝐸 (lines 6-7). After all edges have been processed, it returns the initial possible world 𝐺 0 = (𝑉 , 𝐸) (line 8). Next, we explain the validity of using such a sampling process to simulate a Bernoulli distribution with parameter 𝑝 (𝑒).
Efficient Computation of Total Discrepancy Variation. To efficiently compute the total discrepancy variation 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) for the edge 𝑒𝑢𝑣 , we introduce an edge influence set that identifies edges whose discrepancies are affected by the state change of 𝑒𝑢𝑣 (Theorem 3). By aggregating the variation of absolute edge discrepancy only for edges from the edge influence set, we can efficiently obtain 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) (Theorem 5). Next, we begin by establishing how the state change of 𝑒𝑢𝑣 affects the number of common neighbors between the endpoints of adjacent edges (Lemma 1), which underlies the identification of edge influence set.
Theorem 2. Given an edge 𝑒 with existence probability 𝑝 (𝑒), let 𝑟 ∼ 𝑈 (0, 1). We define a discrete random variable 𝑋𝑒 and set 𝑋𝑒 = 1 if 𝑟 ⩽ 𝑝 (𝑒), and 𝑋𝑒 = 0 if 𝑟 > 𝑝 (𝑒). Then 𝑋𝑒 follows a Bernoulli distribution with parameter 𝑝 (𝑒). Proof. Since 𝑟 is drawn uniformly from 𝑈 [0, 1], the probability that 𝑋𝑒 = 1 and 𝑋𝑒 = 0 can be calculated by Eq. 11 and Eq. 12. Thus 𝑋𝑒 follows a Bernoulli distribution with parameter 𝑝 (𝑒). ∫ 𝑝 (𝑒 ) 𝑃 (𝑋𝑒 = 1) = 𝑃 (𝑟 ≤ 𝑝 (𝑒)) = 1 𝑑𝑥 = 𝑝 (𝑒) (11) ∫ 01 𝑃 (𝑋𝑒 = 0) = 𝑃 (𝑟 > 𝑝 (𝑒)) = 1 𝑑𝑥 = 1 − 𝑝 (𝑒) (12)
Lemma 1. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, an edge 𝑒𝑢𝑣 ∈ E, and a node 𝑤 ∈ 𝐶 G (𝑢, 𝑣), where 𝐶 G (𝑢, 𝑣) denotes the set of common neighbors of 𝑢 and 𝑣 within the topological structure of G, ignoring edge probabilities.
𝑝 (𝑒 )
□ 6
Selected edge: ev0 v1 Gi
v0
v1 v2
v5
v1
v4
v2
v3 (a) Possible World Gi
Si (ev0 v1 ) = {ev0 v2 , ev0 v5 , ev1v5 , ev1v3 }
v0
(b) Affected edge ev0v2
Algorithm 2: Random Selection-based Refinement
v0
v1
Input: uncertain graph G = ( V, E, P ), iterative starting point 𝐺 0 = (𝑉0 , 𝐸 0 ), iterations 𝑘 ≥ 0 Output: 𝐺𝐶 1 for 𝑖 ← 1 to 𝑘 do 2 𝐺𝑖 ← 𝐺𝑖 −1 ; 3 𝑒𝑢𝑣 ← randomly select an edge from E; 4 𝑆𝑖 (𝑒𝑢𝑣 ) ← get the influence set of 𝑒𝑢𝑣 ; /* Theorem 3 */ 5 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) ← compute total discrepancy variation via 𝑆𝑖 (𝑒𝑢𝑣 ) ; /* Theorem 5 */ 6 if 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 then 7 if 𝑒𝑢𝑣 ∈ 𝐸𝑖 then 8 remove 𝑒𝑢𝑣 from 𝐸𝑖 ; 9 else 10 add 𝑒𝑢𝑣 to 𝐸𝑖 ;
v1
v0 v5
v3 (c) Affected edge (d) Affected ev0v5 and ev1v5 edge ev1v3
Figure 2: Identifying the edge influence set 𝑆𝑖 (𝑒 𝑣0 𝑣1 ) of the selected edge 𝑒 𝑣0 𝑣1 in the possible world 𝐺𝑖 . When the existence state of 𝑒𝑢𝑣 changes in 𝐺𝑖 , the number of common neighbors |𝐶𝐺𝑖 (𝑢, 𝑤)| is affected if and only if 𝑒 𝑣𝑤 ∈ 𝐸𝑖 .
else
11
Proof. 𝑒𝑢𝑣 , 𝑒 𝑣𝑤 ∈ 𝐸 is the condition for 𝑣 to be a common neighbor of 𝑢 and 𝑤 in 𝐺, i.e., 𝑣 ∈ 𝐶𝐺 (𝑢, 𝑤). Let 𝐺𝑖+1 denote the possible world obtained by changing the existence state of 𝑒𝑢𝑣 in 𝐺𝑖 . We follow the existence state of 𝑒 𝑣𝑤 in 𝐸𝑖 to prove the lemma. (1) Suppose 𝑒 𝑣𝑤 ∈ 𝐸𝑖 . We next analyze the effect of the change in 𝑒𝑢𝑣 state on |𝐶𝐺𝑖 (𝑢, 𝑤)|. If 𝑒𝑢𝑣 ∈ 𝐸𝑖 , then 𝑒𝑢𝑣 , 𝑒 𝑣𝑤 ∈ 𝐸𝑖 , so 𝑣 ∈ 𝐶𝐺𝑖 (𝑢, 𝑤). After removing 𝑒𝑢𝑣 , we have 𝑣 ∉ 𝐶𝐺𝑖+1 (𝑢, 𝑤), so |𝐶𝐺𝑖+1 (𝑢, 𝑤)| = |𝐶𝐺𝑖 (𝑢, 𝑤)| − 1. If 𝑒𝑢𝑣 ∉ 𝐸𝑖 , then 𝑣 ∉ 𝐶𝐺𝑖 (𝑢, 𝑤). After adding 𝑒𝑢𝑣 , 𝑒𝑢𝑣 , 𝑒 𝑣𝑤 ∈ 𝐸𝑖+1 , so 𝑣 ∈ 𝐶𝐺𝑖+1 (𝑢, 𝑤), giving |𝐶𝐺𝑖+1 (𝑢, 𝑤)| = |𝐶𝐺𝑖 (𝑢, 𝑤)| + 1. In both sub-cases, |𝐶𝐺𝑖 (𝑢, 𝑤)| is affected. (2) Suppose 𝑒 𝑣𝑤 ∉ 𝐸𝑖 . Regardless of whether 𝑒𝑢𝑣 exists or not, 𝑣 cannot be a common neighbor of 𝑢 and 𝑤 in either 𝐺𝑖 or 𝐺𝑖+1 . Therefore, |𝐶𝐺𝑖 (𝑢, 𝑤)| is unaffected by the state change of 𝑒𝑢𝑣 . Combining both cases, |𝐶𝐺𝑖 (𝑢, 𝑤)| is affected by the state change of 𝑒𝑢𝑣 if and only if 𝑒 𝑣𝑤 ∈ 𝐸𝑖 . □
continue
13
return 𝐺𝐶 = 𝐺𝑘 ;
Having identified 𝑆𝑖 (𝑒𝑢𝑣 ) for an edge 𝑒𝑢𝑣 , we next characterize how the edge discrepancy of each 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ) changes when the state of 𝑒𝑢𝑣 is altered and finally present an optimized computation method of the total discrepancy variation. Theorem 4. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G, an edge 𝑒𝑢𝑣 ∈ E with edge influence set 𝑆𝑖 (𝑒𝑢𝑣 ), and 𝐺𝑖+1 denoting the possible world obtained by changing the existence state of 𝑒𝑢𝑣 in 𝐺𝑖 . For any edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ), the edge discrepancy 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) is given by Eq. 15. ( 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1, if 𝑒𝑢𝑣 ∈ 𝐸𝑖 , 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) = (15) 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1, if 𝑒𝑢𝑣 ∉ 𝐸𝑖 .
Theorem 3. Given an uncertain graph G = (V, E, P), an edge 𝑒𝑢𝑣 ∈ E, a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration (with an edge set 𝐸𝑖 ), the edge influence set of 𝑒𝑢𝑣 in 𝐺𝑖 , denoted as 𝑆𝑖 (𝑒𝑢𝑣 ), is calculated by Eq. 14. 𝑆𝑖 (𝑒𝑢𝑣 ) = {𝑒𝑢𝑤 : 𝑒 𝑣𝑤 ∈ 𝐸𝑖 , 𝑤 ∈ 𝐶 G (𝑢, 𝑣)}
12
Proof. By Theorem 3, 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ) implies there exists 𝑤 ∈ 𝐶 G (𝑢, 𝑣) such that 𝑒𝑥 𝑦 = 𝑒𝑢𝑤 and 𝑒 𝑣𝑤 ∈ 𝐸𝑖 . By Lemma 1, since 𝑒 𝑣𝑤 ∈ 𝐸𝑖 , the state change of 𝑒𝑢𝑣 affects |𝐶𝐺𝑖 (𝑢, 𝑤)|: |𝐶𝐺𝑖+1 (𝑢, 𝑤)| = |𝐶𝐺𝑖 (𝑢, 𝑤)| − 1 if 𝑒𝑢𝑣 ∈ 𝐸𝑖 , and |𝐶𝐺𝑖+1 (𝑢, 𝑤)| = |𝐶𝐺𝑖 (𝑢, 𝑤)| + 1 if 𝑒𝑢𝑣 ∉ 𝐸𝑖 . Since 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = |𝐶𝐺𝑖 (𝑢, 𝑤)| − 𝐶 G (𝑢, 𝑤) and 𝐶 G (𝑢, 𝑤) is independent of the state of 𝑒𝑢𝑣 , 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) changes by the same amount as |𝐶𝐺𝑖+1 (𝑢, 𝑤)|, yielding Eq. 15. □
(14)
Proof. Consider the edge 𝑒𝑢𝑤 with 𝑤 ∈ 𝐶 G (𝑢, 𝑣) and the state change of 𝑒𝑢𝑣 in 𝐺𝑖 . By Definition 6, we have the edge discrepancy of 𝑒𝑢𝑤 depends on |𝐶𝐺𝑖 (𝑢, 𝑤)|. By Lemma 1, when the state of 𝑒𝑢𝑣 changes, |𝐶𝐺𝑖 (𝑢, 𝑤)| is affected if and only if 𝑒 𝑣𝑤 ∈ 𝐸𝑖 . Therefore, the edge discrepancy of 𝑒𝑢𝑤 is affected by the state change of 𝑒𝑢𝑣 if and only if 𝑒 𝑣𝑤 ∈ 𝐸𝑖 , which yields Eq. 14. □
Theorem 5. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G, an edge 𝑒𝑢𝑣 ∈ E with 𝑆𝑖 (𝑒𝑢𝑣 ), and 𝐺𝑖+1 denoting the possible world obtained by changing the existence state of 𝑒𝑢𝑣 in 𝐺𝑖 , the total discrepancy variation 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) is given by Eq. 16, where 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) for each 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ) is determined by Theorem 4.
Example 2. We use Figure 2 to illustrate how the edge influence set is identified. Figure 2(a) shows a possible world 𝐺𝑖 of the uncertain graph G in Figure 1(a), where the selected edge 𝑒 𝑣0 𝑣1 (red dashed) is absent. In the topology of G, 𝑣 0 and 𝑣 1 have three common neighbors: 𝐶 G (𝑣 0, 𝑣 1 ) = {𝑣 2, 𝑣 5, 𝑣 3 }. We examine them in turn. For 𝑣 2 in Figure 2(b), the edge 𝑒 𝑣1 𝑣2 is present in 𝐺𝑖 , so changing the state of 𝑒 𝑣0 𝑣1 alters the number of common neighbors of 𝑣 0 and 𝑣 2 , and thus the edge discrepancy of 𝑒 𝑣0 𝑣2 . We therefore add 𝑒 𝑣0 𝑣2 to 𝑆𝑖 (𝑒 𝑣0 𝑣1 ). For 𝑣 5 in Figure 2(c), both 𝑒 𝑣0 𝑣5 and 𝑒 𝑣1 𝑣5 are present in 𝐺𝑖 , so the state change of 𝑒 𝑣0 𝑣1 affects the edge discrepancies of 𝑒 𝑣0 𝑣5 and 𝑒 𝑣1 𝑣5 , both of which are added to 𝑆𝑖 (𝑒 𝑣0 𝑣1 ). For 𝑣 3 in Figure 2(d), the edge 𝑒 𝑣0 𝑣3 is present in 𝐺𝑖 , which adds 𝑒 𝑣1 𝑣3 . Collecting these edges yields 𝑆𝑖 (𝑒 𝑣0 𝑣1 ) = {𝑒 𝑣0 𝑣2 , 𝑒 𝑣0 𝑣5 , 𝑒 𝑣1 𝑣5 , 𝑒 𝑣1 𝑣3 }.
𝛿𝐺𝑖 (𝑒𝑢𝑣 ) =
∑︁
|𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) | − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) |
(16)
𝑒𝑥 𝑦 ∈𝑆𝑖 (𝑒𝑢𝑣 )
Proof. By Definition 6, 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) = 𝑑𝑖𝑠 G (𝐺𝑖+1 ) − 𝑑𝑖𝑠 G (𝐺𝑖 ) = Í
𝑒𝑥 𝑦 ∈ E (|𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )|). By Theorem 3, only edges in
𝑆𝑖 (𝑒𝑢𝑣 ) have their edge discrepancies affected by the state change of 𝑒𝑢𝑣 , so the terms for edges outside 𝑆𝑖 (𝑒𝑢𝑣 ) vanish, yielding Eq. 16. For each remaining term 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ), Theorem 4 gives the exact value of 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ), which directly determines |𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )|. □ Algorithm of Random Selection-based Refinement. Next, we introduce the procedure of the random selection-based refinement 7
𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 reduces to identifying which edges in 𝑆𝑖 (𝑒𝑢𝑣 ) contribute +1 and which contribute −1. We establish this in the integerbased determination, and then present the algorithm of integer-based refinement.
in Algorithm 2. In each iteration, starting from the current possible world 𝐺𝑖 (𝑖 ∈ [1, 𝑘]) obtained from the previous iteration (line 2), we randomly select an edge 𝑒𝑢𝑣 ∈ E and identify its edge influence set 𝑆𝑖 (𝑒𝑢𝑣 ) (lines 3-4). Then, for each edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ), we compute 𝐶 G (𝑥, 𝑦), and substitute 𝐶 G (𝑥, 𝑦) into Eq. 16 to obtain 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) by Theorem 5 (line 5). If 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0, we change the existence state of 𝑒𝑢𝑣 in 𝐺𝑖 to obtain 𝐺𝑖+1 (lines 6-10); otherwise, we reject the change and keep 𝐺𝑖+1 = 𝐺𝑖 (lines 11-12). After 𝑘 iterations, we return the final possible world 𝐺𝑘 (line 13).
Integer-based Determination. For each 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ), whether its term |𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )| is +1 or −1 depends on the sign of 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ). We therefore partition 𝑆𝑖 (𝑒𝑢𝑣 ) into three subsets 𝑆𝑖<0 (𝑒𝑢𝑣 ), 𝑆𝑖=0 (𝑒𝑢𝑣 ), and 𝑆𝑖>0 (𝑒𝑢𝑣 ), corresponding to 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) < 0, 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 0, and 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) > 0, and analyze the |𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )| within each subset in Lemmas 2-4.
Complexity Analysis. We derive the time complexity of the basic algorithm by analyzing its two stages, i.e., the probability-based initialization (Algorithm 1) and the random selection-based refinement (Algorithm 2). In the initialization stage, Algorithm 1 performs a random number generation and a probability comparison for each edge in E, each taking 𝑂 (1) time. Thus, this stage takes 𝑂 (|E |) time. The random selection-based refinement consists of 𝑘 iterations. The cost of each iteration is divided into three parts: (1) randomly selecting an edge, which takes 𝑂 (1) time; (2) computing the total discrepancy variation 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) via Eq. 16, whose cost is dominated by identifying the edge influence set 𝑆𝑖 (𝑒𝑢𝑣 ). The cost of identifying 𝑆𝑖 (𝑒𝑢𝑣 ) is in turn dominated by computing the common neighbors 𝐶 G (𝑢, 𝑣), which is obtained by intersecting the neighbor sets of the two endpoints 𝑢 and 𝑣. Let 𝑑¯ denote the average degree of nodes in G. We use the hash set to store the neighbor set of each node. This ¯ time, and hence the second operation takes intersection takes 𝑂 (𝑑) ¯ time; and (3) changing the state of the selected edge, which 𝑂 (𝑑) ¯ time, and the takes 𝑂 (1) time. Therefore, each iteration takes 𝑂 (𝑑) ¯ time. Combining the two stages, the refinement stage takes 𝑂 (𝑘 𝑑) overall time complexity of the basic algorithm is 𝑂 |E | + 𝑘 𝑑¯ .
4
Lemma 2. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, an 𝑒𝑢𝑣 ∈ E with influence set 𝑆𝑖 (𝑒𝑢𝑣 ) and an edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖<0 (𝑒𝑢𝑣 ). Changing the state of 𝑒𝑢𝑣 from absent to present decreases the absolute edge discrepancy of 𝑒𝑥 𝑦 by 1; otherwise, it increases by 1. Proof. Let 𝐺𝑖 and 𝐺𝑖+1 denote the possible worlds before and after the state change of 𝑒𝑢𝑣 . According to Theorem 4, when the existence state of 𝑒𝑢𝑣 changes from absent to present, then the edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖<0 (𝑒𝑢𝑣 ), which satisfies 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) < 0, has 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 and the variation of the absolute edge discrepancy of 𝑒𝑥 𝑦 is given as follows: 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 + 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = −1
.
Conversely, when the existence state of 𝑒𝑢𝑣 changes from present to absent, then the edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖<0 (𝑒𝑢𝑣 ) has 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 and the variation of the absolute edge discrepancy is given as follows: 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 + 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )
INTEGER DISCREPANCIES FOR FAST REFINEMENT
=1
The core of Algorithm 2 is a per-iteration decision: whether changing the state of the selected edge 𝑒𝑢𝑣 reduces the total discrepancy, i.e., whether 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0. By Eq. 16, computing 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) requires the edge discrepancies of all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ); each is derived from the expected number of common neighbors and is thus a floating-point number. Consequently, every iteration performs costly floatingpoint arithmetic, which dominates the refinement cost; on Flickr dataset, it accounts for 63.2% of the total running time. To reduce this cost, we observe that determining whether to change the state of 𝑒𝑢𝑣 requires only the sign of 𝛿𝐺𝑖 (𝑒𝑢𝑣 ), not its exact value. We therefore propose integer-based refinement that rounds each edge discrepancy to the nearest integer, so that whether 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 is determined by cheap integer counting instead of costly floatingpoint arithmetic. Experiments show that this approach incurs limited quality loss while providing substantial efficiency gains (§6). Overview. We now show how rounding reduces the determination of 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 to integer counting. By Eq. 16, 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) is the sum of |𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )| over all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ). After rounding, 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) is an integer, and by Theorem 4 the state change of 𝑒𝑢𝑣 alters 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) by +1 or −1; hence each |𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 )| − |𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 )| equals +1 or −1, and 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 holds exactly when the −1 terms outnumber the +1 terms. Therefore, the determination of
.
Therefore, the lemma holds.
□
With the lemma 2, for any edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖<0 (𝑒𝑢𝑣 ), the variation of its absolute edge discrepancy under the existence state change of 𝑒𝑢𝑣 can be obtained efficiently. Lemma 3. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, an 𝑒𝑢𝑣 ∈ E with influence set 𝑆𝑖 (𝑒𝑢𝑣 ) and an edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖>0 (𝑒𝑢𝑣 ). Changing the state of 𝑒𝑢𝑣 from absent to present increases the absolute edge discrepancy of 𝑒𝑥 𝑦 by 1; otherwise, it decreases by 1. Proof. Let 𝐺𝑖 and 𝐺𝑖+1 denote the possible worlds before and after the state change of 𝑒𝑢𝑣 , respectively. Similar to the proof of Lemma 2, when the existence state of 𝑒𝑢𝑣 changes from absent to present, for the edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖>0 (𝑒𝑢𝑣 ) satisfying 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) > 0, the variation of its absolute edge discrepancy is given as follows: 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) =1 8
.
Similarly, when the existence state of 𝑒𝑢𝑣 changes from present to absent, the variation of the absolute edge discrepancy of 𝑒𝑥 𝑦 is given as follows:
initial possible world 𝐺 0 produced by Algorithm 1, it begins by rounding 𝑑𝑖𝑠𝐺 0 (𝑒) to the nearest integer for each edge 𝑒 ∈ E (lines 1-2). Then, in each of the 𝑘 iterations, starting from the current possible world 𝐺𝑖 (𝑖 ∈ [1, 𝑘]) obtained from the previous iteration (line 4), we randomly select an edge 𝑒𝑢𝑣 ∈ E and identify its edge influence set 𝑆𝑖 (𝑒𝑢𝑣 ) (lines 5-6). We partition 𝑆𝑖 (𝑒𝑢𝑣 ) into 𝑆𝑖<0 (𝑒𝑢𝑣 ), 𝑆𝑖=0 (𝑒𝑢𝑣 ), and 𝑆𝑖>0 (𝑒𝑢𝑣 ) according to Lemmas 2-4 and count their cardinalities (line 7). By Theorem 6, these cardinalities determine whether changing the state of 𝑒𝑢𝑣 reduces 𝑑𝑖𝑠 G (𝐺): if 𝑒𝑢𝑣 ∉ 𝐸𝑖 and |𝑆𝑖<0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖>0 (𝑒𝑢𝑣 )|, we add 𝑒𝑢𝑣 to 𝐸𝑖 and increment 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) by 1 for each 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ) (lines 8-10); if 𝑒𝑢𝑣 ∈ 𝐸𝑖 and |𝑆𝑖>0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖<0 (𝑒𝑢𝑣 )|, we remove 𝑒𝑢𝑣 from 𝐸𝑖 and decrement 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) by 1 for each 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ) (lines 11-13). Maintaining the integer-valued 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) through the ±1 updates in lines 10 and 14 ensures the validity of the counting-based determination in subsequent iterations. After 𝑘 iterations, the algorithm returns 𝐺𝐶 = 𝐺𝑘 (line 14).
𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = −1
.
Therefore, the lemma holds.
□
Leveraging Lemma 3, for any edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖>0 (𝑒𝑢𝑣 ), the variation of its absolute edge discrepancy under the existence state change of 𝑒𝑢𝑣 can be efficiently determined. Lemma 4. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, an 𝑒𝑢𝑣 ∈ E with influence set 𝑆𝑖 (𝑒𝑢𝑣 ) and an edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖=0 (𝑒𝑢𝑣 ). Regardless of the existence state change of 𝑒𝑢𝑣 , the variation of the absolute edge discrepancy of 𝑒𝑥 𝑦 is always increase by 1.
Complexity Analysis. We analyze the time complexity of the integer-based refinement (Algorithm 3). Let 𝑑¯ denote the average degree of nodes in G, and the neighbor set of each node is stored as a hash set. The algorithm consists of two parts: the integer rounding (lines 1-2) and the iterative refinement (lines 3-13). In the rounding stage, the algorithm rounds 𝑑𝑖𝑠𝐺 0 (𝑒) to the nearest integer for each edge 𝑒 ∈ E, taking 𝑂 (|E |) time. The refinement stage consists of 𝑘 iterations, each performing four steps. First, it randomly selects an edge 𝑒𝑢𝑣 in 𝑂 (1) time. Second, it identifies the edge influence set 𝑆𝑖 (𝑒𝑢𝑣 ), whose cost is dominated by intersecting the neighbor sets of 𝑢 and 𝑣 to compute the common neighbors 𝐶 G (𝑢, 𝑣), taking ¯ time. Third, it determines whether to change the state of 𝑂 (𝑑) 𝑒𝑢𝑣 by counting |𝑆𝑖<0 (𝑒𝑢𝑣 )|, |𝑆𝑖=0 (𝑒𝑢𝑣 )|, and |𝑆𝑖>0 (𝑒𝑢𝑣 )|, which scans ¯ time. 𝑆𝑖 (𝑒𝑢𝑣 ) once. Since |𝑆𝑖 (𝑒𝑢𝑣 )| ≤ |𝐶 G (𝑢, 𝑣)|, this step takes 𝑂 (𝑑) Fourth, if the state of 𝑒𝑢𝑣 is changed, it updates 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) for each ¯ time. Hence, each iteration takes 𝑂 (𝑑) ¯ 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ), taking 𝑂 (𝑑) ¯ time, and the refinement stage takes 𝑂 (𝑘 𝑑) time. Combining two ¯ time. It does stages, the integer-based refinement takes 𝑂 (|E | +𝑘 𝑑) not lower the asymptotic complexity of random selection-based refinement, but it replaces the costly floating-point arithmetic in each iteration with cheap integer counting, whose efficiency gain is demonstrated in our experiments (§6).
Proof. Let 𝐺𝑖 and 𝐺𝑖+1 denote the possible worlds before and after the state change of 𝑒𝑢𝑣 , respectively. The variation of the absolute edge discrepancy is derived as follows: 𝑑𝑖𝑠𝐺𝑖+1 (𝑒𝑥 𝑦 ) − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) ± 1 − 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) = |0 ± 1| − |0| =1
. □
Building on Lemma 4, for any edge 𝑒𝑥 𝑦 ∈ 𝑆𝑖=0 (𝑒𝑢𝑣 ), the variation of its absolute edge discrepancy can be readily obtained if the existence state of 𝑒𝑢𝑣 changes. Next, we utilize the three subsets 𝑆𝑖<0 (𝑒𝑢𝑣 ), 𝑆𝑖=0 (𝑒𝑢𝑣 ), and 𝑆𝑖>0 (𝑒𝑢𝑣 ) to analyze the condition under which 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0, as stated in the following theorem. Theorem 6. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, and an edge 𝑒𝑢𝑣 ∈ E. If 𝑒𝑢𝑣 is absent (present) in 𝐺𝑖 and |𝑆𝑖<0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖>0 (𝑒𝑢𝑣 )| (|𝑆𝑖>0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖<0 (𝑒𝑢𝑣 )|), then the total discrepancy variation 𝛿𝐺𝑖 ⊑ G (𝑒𝑢𝑣 ) < 0. Proof. We prove Theorem 6 according to the existence state of 𝑒𝑢𝑣 in 𝐺𝑖 . (1) If 𝑒𝑢𝑣 ∉ 𝐸𝑖 , according to Lemmas 2-4, when the state of 𝑒𝑢𝑣 changes (i.e., 𝑒𝑢𝑣 ∈ 𝐸𝑖+1 ), the absolute edge discrepancies of edges in 𝑆𝑖<0 (𝑒𝑢𝑣 ) decrease by 1, while those in 𝑆𝑖=0 (𝑒𝑢𝑣 ) and 𝑆𝑖>0 (𝑒𝑢𝑣 ) increase by 1. For 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 to hold, it must satisfy that |𝑆𝑖<0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖>0 (𝑒𝑢𝑣 )|. (2) Conversely, if 𝑒𝑢𝑣 ∈ 𝐸𝑖 , when the state of 𝑒𝑢𝑣 changes (i.e., 𝑒𝑢𝑣 ∉ 𝐸𝑖+1 ), the absolute edge discrepancies of edges in 𝑆𝑖>0 (𝑒𝑢𝑣 ) decrease by 1, while those in 𝑆𝑖=0 (𝑒𝑢𝑣 ) and 𝑆𝑖<0 (𝑒𝑢𝑣 ) increase by 1. For 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 to hold, it must satisfy that |𝑆𝑖>0 (𝑒𝑢𝑣 )| > |𝑆𝑖=0 (𝑒𝑢𝑣 )| + |𝑆𝑖<0 (𝑒𝑢𝑣 )|. □
5
BETA-BASED ADAPTIVE TERMINATION
The integer-based refinement in §4 requires users to set the iteration count 𝑘 in advance. However, users actually care about the quality of the resulting possible world rather than the iteration count. Since the 𝑘 required for a given quality varies with graph structure, when a user has a desired quality in mind, there is no reliable way to know how large 𝑘 must be to reach it on the graph at hand, which makes 𝑘 difficult to set appropriately. This motivates an adaptive alternative: rather than forcing users to guess an iteration count, we let them specify the desired quality directly, so that the refinement terminates on its own once that quality is attained. To enable this, we first need a way to measure how well the current possible world 𝐺𝑖 has been refined. Recall that the refinement reduces 𝑑𝑖𝑠 G (𝐺𝑖 ) by changing the existence states of edges. Hence, the proportion of edges whose state change reduces 𝑑𝑖𝑠 G (𝐺𝑖 ) in E
With Theorem 6, we can efficiently determine whether 𝛿𝐺𝑖 (𝑒𝑢𝑣 ) < 0 when the existence state of 𝑒𝑢𝑣 is changed, which in turn determines whether to update 𝑒𝑢𝑣 and obtain 𝐺𝑖+1 . Algorithm of Integer-based Refinement. Algorithm 3 presents the integer-based refinement. Given an uncertain graph G and an 9
Algorithm 3: Integer-based Refinement
Overview. We model the SEP estimation via Beta(𝛼, 𝛽), where the parameters 𝛼 and 𝛽 are determined by the number of successes and failures through edge sampling, respectively. Therefore, in the following, we first describe the process of edge sampling; and then model the SEP estimation via Beta(𝛼, 𝛽).
Input: uncertain graph G = ( V, E, P ), initial possible world 𝐺 0 = (𝑉0 , 𝐸 0 ), iterations 𝑘 ≥ 0 Output: 𝐺𝐶 1 for 𝑒𝑢𝑣 ∈ E do 2 𝑑𝑖𝑠𝐺 0 (𝑒𝑢𝑣 ) ← round 𝑑𝑖𝑠𝐺 0 (𝑒𝑢𝑣 ) to the nearest integer; 3 for 𝑖 ← 1 to 𝑘 do 4 𝐺𝑖 ← 𝐺𝑖 −1 ; 5 𝑒𝑢𝑣 ← randomly select an edge from E; 6 𝑆𝑖 (𝑒𝑢𝑣 ) ← get the edge influence set of 𝑒𝑢𝑣 ; /* Theorem 3 */ 7 count |𝑆𝑖<0 (𝑒𝑢𝑣 ) |, |𝑆𝑖=0 (𝑒𝑢𝑣 ) |, |𝑆𝑖>0 (𝑒𝑢𝑣 ) | ; /* Lemma 2-4 */ // determine whether to change 𝑒𝑢𝑣 by Theorem 6 8 if |𝑆𝑖<0 (𝑒𝑢𝑣 ) | > |𝑆𝑖=0 (𝑒𝑢𝑣 ) | + |𝑆𝑖>0 (𝑒𝑢𝑣 ) | and 𝑒𝑢𝑣 ∉ 𝐸𝑖 then 9 add 𝑒𝑢𝑣 to 𝐸𝑖 ; 10 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) ← 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 for all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ); if |𝑆𝑖>0 (𝑒𝑢𝑣 ) | > |𝑆𝑖=0 (𝑒𝑢𝑣 ) | + |𝑆𝑖<0 (𝑒𝑢𝑣 ) | and 𝑒𝑢𝑣 ∈ 𝐸𝑖 then remove 𝑒𝑢𝑣 from 𝐸𝑖 ; 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) ← 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 for all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 );
11 12 13 14
Process of Edge Sampling. To estimate the SEP, we repeatedly sample 𝑛 edges uniformly at random from E, where 𝑛 denotes the total number of edge samples. For each sampled edge, we record a success if it is state-changeable and a failure otherwise, constituting a Bernoulli trial whose success probability equals the true SEP. After 𝑛 samples, we denote the number of successes as 𝑚 and the number of failures as 𝑛 − 𝑚. These values are used to determine the parameters of the Beta distribution Beta(𝛼, 𝛽). Beta Distribution Modeling of SEP Estimation. Given 𝑚 statechangeable edges (𝑚 successes) and 𝑛 − 𝑚 non-state-changeable edges (𝑛 − 𝑚 failures) from the edge sampling, we model the estimation of SEP via Beta(𝛼, 𝛽), where 𝛼 = 𝑚 + 1 and 𝛽 = 𝑛 − 𝑚 + 1. Accordingly, the probability density function of Beta(𝛼, 𝛽) can be expressed as 𝑓 (𝑥; 𝑚 + 1, 𝑛 − 𝑚 + 1), which reflects how credible it is that the true SEP takes the value 𝑥 with 𝑚 and 𝑛 − 𝑚.
return 𝐺𝐶 = 𝐺𝑘 ;
reflects the current refinement degree of 𝐺𝑖 . Based on this observation, we define an edge 𝑒𝑢𝑣 ∈ E as state-changeable under 𝐺𝑖 if changing its existence state reduces 𝑑𝑖𝑠 G (𝐺𝑖 ), and take the proportion of state-changeable edges in E, termed the state-changeable edge proportion (SEP for short), as the measure. As the refinement proceeds, fewer state-changeable edges remain, so the SEP tends to decrease. How low the SEP must fall for 𝐺𝑖 to be considered well refined is left to the user. We therefore introduce a quality threshold 𝜏𝑞 ∈ (0, 1) as the user’s target on the SEP: once the SEP falls below 𝜏𝑞 (SEP < 𝜏𝑞 ), 𝐺𝑖 is regarded as refined to the degree the user desires, and the refinement can terminate. However, computing the SEP exactly requires enumerating every edge in E, which is infeasible. We therefore estimate the SEP through edge sampling. Since the Beta distribution is well suited to modeling an unknown proportion, we adopt it to model the SEP estimation, through which the confidence that the SEP < 𝜏𝑞 can be quantified. The user further specifies a confidence threshold 𝜏𝑐 ∈ (0, 1), the minimum confidence they require, and the refinement terminates once the confidence that SEP < 𝜏𝑞 reaches 𝜏𝑐 . In the following, we model the estimation of the SEP via the Beta distribution in §5.1. Built on this model, §5.2 establishes a termination criterion for the integer-based refinement. §5.3 presents the complete algorithm of Beta-based integer refinement.
5.1
5.2
Overview. Built on the Beta model in §5.1, which characterizes how credible each possible value of the true SEP is, the confidence that SEP < 𝜏𝑞 can be quantified. We therefore first formalize the termination criterion for the integer-based refinement. Since the confidence that SEP < 𝜏𝑞 is computed via 𝑓 (𝑥; 𝛼, 𝛽) whose parameters depend on the total number of edge samples 𝑛, we then determine the required sample size 𝑛 to make the criterion operational. Termination Criterion. Since 𝑓 (𝑥; 𝛼, 𝛽) reflects how credible it is that the true SEP takes the value 𝑥, the confidence that SEP < 𝜏𝑞 is obtained by integrating 𝑓 (𝑥; 𝑚 + 1, 𝑛 − 𝑚 + 1) over [0, 𝜏𝑞 ], where 𝑛 is the total number of edge samples and 𝑚 is the number of statechangeable edges observed among them. The termination criterion is formalized as follows. Theorem 7. Given an uncertain graph G = (V, E, P), a possible world 𝐺𝑖 ⊑ G at the 𝑖-th iteration, the total number of edge samples 𝑛, the number of state-changeable edges observed 𝑚, a quality threshold 𝜏𝑞 ∈ (0, 1), and a confidence threshold 𝜏𝑐 ∈ (0, 1), the integer-based refinement terminates if and only if Eq. 18 holds. ∫ 𝜏𝑞 𝑓 (𝑥; 𝑚 + 1, 𝑛 − 𝑚 + 1) 𝑑𝑥 ≥ 𝜏𝑐 (18)
Beta-based Estimation Modeling
0
The Beta distribution, denoted by Beta(𝛼, 𝛽), is a continuous probability distribution supported on [0, 1], with shape parameters 𝛼, 𝛽 > 0. Specifically, given a series of independent Bernoulli trials with 𝛼 − 1 successes and 𝛽 − 1 failures, Beta(𝛼, 𝛽) models the distribution of the unknown success probability. The probability density function 𝑓 (𝑥; 𝛼, 𝛽) of Beta(𝛼, 𝛽) is given by Eq. 17, where 𝐵(𝛼, 𝛽) denotes the Beta function [1]. For fixed parameters 𝛼 and 𝛽, the value of 𝑓 (𝑥; 𝛼, 𝛽) at a given 𝑥 indicates how credible it is that the true success probability takes the value 𝑥. 𝑓 (𝑥; 𝛼, 𝛽) =
𝑥 𝛼 −1 (1 − 𝑥) 𝛽 −1 , 𝐵(𝛼, 𝛽)
𝑥 ∈ [0, 1]
Termination Criterion
Proof. Once the confidence that SEP < 𝜏𝑞 reaches 𝜏𝑐 , the current possible world 𝐺𝑖 has been refined to the degree the user expects, and the integer-based refinement can be terminated. The confidence∫is given by the integral of 𝑓 (𝑥; 𝑚 + 1, 𝑛 − 𝑚 + 1) over 𝜏 [0, 𝜏𝑞 ], i.e., 0 𝑞 𝑓 (𝑥; 𝑚 + 1, 𝑛 −𝑚 + 1) 𝑑𝑥. Therefore, the termination condition is satisfied if and only if this integral is at least 𝜏𝑐 . □ The termination criterion in Theorem 7 depends on both 𝑚 and 𝑛. While 𝑚 is observed dynamically during edge sampling, 𝑛 must be determined before the sampling begins. We therefore determine the required sample size 𝑛 as follows.
(17) 10
Algorithm 4: Beta-based Integer Refinement
Sample-Size Determination. The criterion in Eq. 18 depends on the sample size 𝑛 and the observed success count 𝑚. Increasing 𝑛 strengthens the statistical evidence for SEP estimation but also raises the sampling cost. To balance them, we require the confidence that the true SEP is below 𝜏𝑞 to reach 𝜏𝑐 while minimize the sampling cost. We denote the minimum sample size by 𝑛 ∗ . Given 𝜏𝑞 and 𝜏𝑐 , a smaller 𝑚 require a smaller 𝑛∗ to satisfy Eq. 18 [15]. Although 𝑚 = 0 minimizes 𝑛 ∗ , it means a zero-success sample and provides no tolerance for an occasional state-changeable edge. Therefore, we set 𝑚 = 1 as a practical design choice and use the corresponding minimum sample size 𝑛 ∗ as the number of sampling iterations. The following theorem guarantees the existence of such an 𝑛 ∗ .
Input: uncertain graph G = ( V, E, P ), initial possible world 𝐺 0 = (𝑉0 , 𝐸 0 ), quality threshold 𝜏𝑞 ∈ (0, 1), confidence threshold 𝜏𝑐 ∈ (0, 1) Output: 𝐺𝐶 1 for 𝑒𝑢𝑣 ∈ E do 2 𝑑𝑖𝑠𝐺 0 (𝑒𝑢𝑣 ) ← round 𝑑𝑖𝑠𝐺 0 (𝑒𝑢𝑣 ) to the nearest integer; ∗ 3 𝑛 ← minimum sample size satisfying Eq. 19 ; /* Theorem 8 */ 4 𝑚 ← 0, 𝑖 ← 1; 5 while true do 6 𝐺𝑖 ← 𝐺𝑖 −1 ; 7 𝑒𝑢𝑣 ← randomly select an edge from E; 8 𝑆𝑖 (𝑒𝑢𝑣 ) ← get the edge influence set of 𝑒𝑢𝑣 ; /* Theorem 3 */ 9 count |𝑆𝑖<0 (𝑒𝑢𝑣 ) |, |𝑆𝑖=0 (𝑒𝑢𝑣 ) |, |𝑆𝑖>0 (𝑒𝑢𝑣 ) | ; /* Lemma 2-4 */ // determine whether to change 𝑒𝑢𝑣 by Theorem 6 10 if |𝑆𝑖<0 (𝑒𝑢𝑣 ) | > |𝑆𝑖=0 (𝑒𝑢𝑣 ) | + |𝑆𝑖>0 (𝑒𝑢𝑣 ) | and 𝑒𝑢𝑣 ∉ 𝐸𝑖 then 11 add 𝑒𝑢𝑣 to 𝐸𝑖 ; 12 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) ← 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) + 1 for all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ); 13 𝑚 ← 𝑚 + 1;
Theorem 8. For any 𝜏𝑞 , 𝜏𝑐 ∈ (0, 1), there exists a minimum positive integer 𝑛, i.e., 𝑛 ∗ , such that Eq. 19 is satisfied. ∫ 𝜏𝑞 𝑓 (𝑥; 2, 𝑛 ∗ ) 𝑑𝑥 ≥ 𝜏𝑐 (19) 0
if |𝑆𝑖>0 (𝑒𝑢𝑣 ) | > |𝑆𝑖=0 (𝑒𝑢𝑣 ) | + |𝑆𝑖<0 (𝑒𝑢𝑣 ) | and 𝑒𝑢𝑣 ∈ 𝐸𝑖 then remove 𝑒𝑢𝑣 from 𝐸𝑖 ; 16 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) ← 𝑑𝑖𝑠𝐺𝑖 (𝑒𝑥 𝑦 ) − 1 for all 𝑒𝑥 𝑦 ∈ 𝑆𝑖 (𝑒𝑢𝑣 ); 17 𝑚 ← 𝑚 + 1; ∗ 18 if 𝑖 mod ∫ 𝜏𝑛𝑞 = 0 then 19 if 0 𝑓 (𝑥; 𝑚 + 1, 𝑛 ∗ − 𝑚 + 1) 𝑑𝑥 ≥ 𝜏𝑐 then 20 break ; /* Theorem 7 */ 21 𝑚 ← 0; 22 𝑖 ← 𝑖 + 1; 23 return 𝐺𝐶 = 𝐺𝑖 ; 14
Proof. Since the integral is monotonically increasing as 𝑛 increases [15], the integral over [0, 𝜏𝑞 ] increases monotonically toward 1 > 𝜏𝑐 as 𝑛 → ∞. Therefore, there exists a 𝑛 ∗ such that the integral first reaches 𝜏𝑐 . □
15
∗ With the existence ∫ 𝜏𝑞of 𝑛 established, we next determine its value. Since the integral 0 𝑓 (𝑥; 2, 𝑛 ∗ − 1) 𝑑𝑥 cannot be analytically inverted with respect to 𝑛 ∗ , so 𝑛 ∗ must be determined via numerical search. To determine the value of 𝑛 ∗ more quickly, we locate 𝑛 ∗ by exponential search: starting from an initial value 𝑛 0 = ⌈1/𝜏𝑞 ⌉, we repeatedly double 𝑛 0 until the integral first exceeds 𝜏𝑐 , requiring only 𝑂 (log 𝑛 ∗ ) evaluations of the integral.
5.3
samples within a window span a sequence of possible worlds 𝐺𝑖 , 𝐺𝑖+1, . . . , 𝐺𝑖+𝑛∗ −1 . This design avoids the overhead of a separate sampling procedure: rather than explicitly sampling 𝑛 ∗ edges from E at each checkpoint, the algorithm reuses the edges already selected during the integer-based refinement iterations, incurring no additional cost. This deviation from the theoretical assumption remains acceptable. Since each state change in the integer-based refinement tends to reduce the SEP, the possible worlds in the early part of the window, i.e., 𝐺𝑖 , 𝐺𝑖+1 , tend to have a higher SEP than 𝐺𝑖+𝑛∗ −1 at the end of the window. Consequently, the observed 𝑚 tends to be larger than what would be obtained by sampling exclusively from 𝐺𝑖+𝑛∗ −1 . As the integral in Eq. 18 decreases monotonically with 𝑚 [15], an overestimated 𝑚 makes the criterion harder to satisfy, i.e., more conservative. Therefore, once the criterion is satisfied, the true SEP of 𝐺𝑖+𝑛∗ −1 is reliably at or below 𝜏𝑞 .
Algorithm of beta-based Integer Refinement
We present the algorithm of Beta-based integer refinement in Algorithm 4. It takes an uncertain graph G and an initial possible world 𝐺 0 as input, and replaces the fixed iteration count 𝑘 in Algorithm 3 with a quality threshold 𝜏𝑞 and a confidence threshold 𝜏𝑐 , enabling adaptive termination of the integer-based refinement based on the criterion in Theorem 7. Algorithm 4 begins by rounding 𝑑𝑖𝑠𝐺 0 (𝑒𝑢𝑣 ) to the nearest integer for each edge 𝑒𝑢𝑣 ∈ E (lines 1-2). It then determines 𝑛 ∗ , the minimum sample size satisfying Eq. 19, via exponential search (line 3). The state-changeable edge counter 𝑚 and the iteration counter 𝑖 are initialized to 0 and 1, respectively (line 4). In each iteration, the algorithm initializes 𝐺𝑖 from 𝐺𝑖 −1 (line 6), randomly selects an edge 𝑒𝑢𝑣 ∈ E, and determines whether to change its state in 𝐺𝑖 via Theorem 6 (lines 7-17), following the same procedure as lines 5-13 in Algorithm 3. If the state of 𝑒𝑢𝑣 is changed, 𝑒𝑢𝑣 is state-changeable under 𝐺𝑖 , and 𝑚 is incremented by 1 (lines 13, 17). After each 𝑛 ∗ iterations, the termination criterion in Theorem 7 is evaluated (lines 19-20). If the criterion is satisfied, the integer-based refinement terminates with 𝐺𝑖 (lines 20-21); otherwise, 𝑚 is reset to 0 and the integer-based refinement proceeds to the next iteration (line 22). Once the integer-based refinement terminates, it outputs 𝐺𝐶 = 𝐺𝑖 .
6
EXPERIMENTS
Our experiments address the following questions. All methods are implemented in Python 3.12 and run on a Linux server with a 3.7 GHz CPU and 128 GB memory. Our code is available at [9]. Q1: How well do the CRPW preserve the structural features of the uncertain graph, especially those centered on the number of common neighbors? (§6.2) Q2: How efficient are the proposed algorithms? (§6.3) Q3: Is the Beta-based termination effective in controlling the quality of the resulting representative possible world? (§6.4) Q4: How sensitive are our methods to their key parameters? (§6.5)
Remark. Strictly speaking, the termination criterion in Theorem 7 assumes that the 𝑛 ∗ samples are drawn from a fixed possible world. However, for the integer-based refinement in Algorithm 4, each iteration serves simultaneously as one edge sample, so the 𝑛 ∗ 11
Table 1: Statistics of datasets Datasets ↓
Nodes
Edges
Email Flickr Biomine DBLP
36,692 720,504 1,863,844 3,255,283
183,831 16,003,787 34,047,306 17,165,252
6.1
are instead governed by intermediate structures that themselves derive from common neighbors. The third group, global features, consists of global features that bear no direct algebraic relationship to common neighbors. This organization lets us examine whether the benefit of optimizing common neighbors extends to features derived from them and, further, to features unrelated to them. Common Neighbor-defined Features. This group contains two features. (1) The number of common neighbors (NCN) of a node pair (𝑢, 𝑣) is |𝑁 (𝑢) ∩ 𝑁 (𝑣)|, the feature our methods directly optimize. (2) The Jaccard coefficient of (𝑢, 𝑣) is |𝑁 (𝑢)∩𝑁 (𝑣)|/|𝑁 (𝑢)∪ 𝑁 (𝑣)| [23], whose numerator is the number of common neighbors. Common Neighbor-derived Features. This group contains two features. (3) The trussness of an edge, from the 𝑘-truss decomposition [10], is the largest 𝑘 such that the edge belongs to a subgraph where every edge lies in at least 𝑘 − 2 triangles. The number of triangles on an edge equals the number of common neighbors of its two endpoints, so the trussness derives from common neighbors. (4) 2𝐸 𝑣 The clustering coefficient of a node 𝑣 is 𝑑 𝑣 (𝑑 [36], where 𝐸 𝑣 𝑣 −1) is the number of edges among its neighbors and 𝑑 𝑣 is its degree; it depends on triangles and thus is derived from common neighbors. Global Features. This group contains (5) The shortest-path distance (SP distance). The feature is measured over pairs of reachable nodes, which is a global feature with no direct algebraic relationship to the number of common neighbors. For Refinement Quality, we measure the refinement quality of a possible world by its mean absolute discrepancy (MAD). For a possible world 𝐺 ⊑ G, MAD is the total discrepancy of 𝐺 (Definition 6) 𝑑𝑖𝑠 (𝐺 ) divided by the number of edges, given by MAD(𝐺) = |GE | . A smaller MAD indicates higher refinement quality. Default Parameters. Unless otherwise specified, each method uses the following settings. For P+RSR and P+IR, the number of iterations is set to 𝑘 = |E |. For P+BIR, the quality threshold and the confidence threshold are set to 𝜏𝑞 = 0.02 and 𝜏𝑐 = 0.9. ADR [27] Í and TRPW [35] run 10 𝑒 ∈ E 𝑝 (𝑒) iterations, following the settings in their papers. ABM [27] has no iteration count to set.
𝑪 G (𝒖, 𝒗 ) mean ± SD {25%, 50%, 75%} 2.98 ± 4.21 1.36 ± 2.96 4.05 ± 7.61 3.03 ± 3.40
{0.63, 1.55, 3.68} {0.04, 0.22, 1.13} {0.40, 1.42, 4.08} {1.26, 2.29, 3.62}
Experimental Setup
Datasets. Table 1 summarizes the statistics of four real-world uncertain graphs from different domains used in our experiments. (1) Email [22] is an email communication network. Each node is an email address, and an undirected edge connects two addresses if at least one email was sent between them. The edge probabilities are generated from a uniform distribution. (2) Flickr [29] is a photosharing social network. Each node is a user, and an edge connects two users who share at least oneinterest group. The probability of an edge is set to the Jaccard coefficient of the interest groups of its two endpoints. (3) Biomine [13] is a protein interaction network. Each node is a protein, and an undirected edge connects two interacting proteins. The probability of an edge reflects the confidence that the corresponding interaction exists. (4) DBLP [25, 29] is an academic collaboration network. Each node is an author, and an edge connects two authors who have coauthored at least one publication. The probability of an edge is derived from an exponential function of the number of collaborations between its two endpoints. The last two columns in Table 1 summarize the distribution of 𝐶 G (𝑢, 𝑣) over all edges (𝑢, 𝑣) ∈ E, reporting its mean, standard deviation together with its 25th, 50th, and 75th percentiles. Methods. We compare our three methods against three baselines. Our methods. (1) P+RSR is our basic algorithm, consisting of two stages: probability-based initialization (P, §3), which produces an initial possible world 𝐺 0 , and random selection-based refinement (RSR), which reduces the total discrepancy of 𝐺 0 . (2) P+IR optimizes the efficiency of RSR with integer-based refinement (IR, §4), which replaces the floating-point computation in each iteration with integer counting. (3) P+BIR builds upon IR with Beta-based integer refinement (BIR, §5), which adaptively terminates the refinement instead of running a fixed number of iterations. Baselines. (4) ADR (Average Degree Rewiring) and (5) ABM (Approximate B-Matching) [27] construct a degree-based representative possible world that preserves the expected node degrees. (6) TRPW [35] constructs a triangle-based representative possible world that preserves both the expected node degrees and the expected triangle degrees. Evaluation Dimensions. Our evaluation is organized along two dimensions. Representativeness measures how well the structural features computed on a resulting possible world approximate their expected values over the uncertain graph. Refinement quality measures how far our methods optimize the possible world. Metrics. For Representativeness, we adopt five structural features as the metrics, and organize them into three groups by their relationship to the number of common neighbors, the feature our methods optimize. The first group, common neighbor-defined features, consists of features whose definition contains this number directly. The second group, common neighbor-derived features, consists of features whose definition does not contain this number directly but
6.2
Effectiveness Evaluation
We evaluate each method by the residual between the feature distribution of the possible world it produces and the expected feature distribution over the uncertain graph G, where expected denotes the feature distribution that G induces in expectation. The former distribution is obtained directly: each method outputs a single deterministic possible world, on which we compute the feature value of every node (or node pair, or edge) and tally these values into a distribution. For example, for the common neighbor count, we count, over all node pairs in the output possible world, how many pairs share 0 common neighbors, how many share 1, and so on. The expected distribution is obtained as follows. For the common neighbor count, it can be computed exactly, since the expected count of a node pair equals a sum of products of edge probabilities (Definition 4); we tally these expected counts into a distribution in the same way. The remaining features cannot compute expectation directly, so we estimate their expected distributions by Monte Carlo over 1000 possible worlds sampled from G [27, 29], averaging the resulting distributions. We then partition the range of each feature into five equal-width bins and sum the counts falling in each bin, 12
P + R S R
R e s id u a l
0 .8
P + IR 4 F lic k r
E m a il
P + B IR
A D R 3 .0 B io m in e
0 .4 2
1 .5
0 .0
0
0 .0
0
2 0 N C N
4 0
0
2 0 N C N
4 0
T R P W
A B M D B L P
Table 3: Mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual on the Jaccard coefficient.
0 .2
Methods →
0 .0 0
1 5 0 N C N
3 0 0
0
E(r) var(r) E(r) var(r) E(r) var(r) E(r) var(r)
1 0 0 2 0 0 N C N
Flickr
Figure 3: Residual of NCN.
Biomine
Table 2: Mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual on NCN. Email Flickr Biomine DBLP
E(r) var(r) E(r) var(r) E(r) var(r) E(r) var(r)
P+RSR
P+IR
P+BIR
ADR
TRPW
ABM
6.62 × 10 −3 1.95 × 10 −5 2.36 × 10 −1 8.63 × 10 −2 1.81 × 10 −1 1.36 × 10 −2 6.88 × 10 −3 1.87 × 10 −5
6.10 × 10 −3 7.85 × 10 −5 3.50 × 10 −1 2.39 × 10 −1 5.37 × 10 −1 2.23 × 10 −1 7.16 × 10 −3 4.37 × 10 −5
1.27 × 10 −2 1.04 × 10 −4 2.96 × 10 −1 1.58 × 10 −1 3.74 × 10 −1 1.51 × 10 −1 1.10 × 10 −2 1.29 × 10 −4
2.36 × 10 −2 1.36 × 10 −4 5.25 × 10 −1 2.36 × 10 −1 6.53 × 10 −1 2.27 × 10 −1 8.45 × 10 −2 6.38 × 10 −3
4.50 × 10 −2 4.94 × 10 −4 7.43 × 10 −1 5.67 × 10 −1 1.422 1.47 2.42 × 10 −2 2.98 × 10 −4
3.93 × 10 −1 8.32 × 10 −2 2.02 2.17 1.890 2.17 1.38 × 10 −1 1.54 × 10 −2
R e s id u a l
P + R S R 0 .6 E m a il
P + IR F lic k r 0 .1
P + B IR
A D R B io m in e
T R P W
DBLP
0 .0
0 .3 0 .6 0 .9 J a c c a rd c o e ffic ie n t
0 .0 0 .4 0 .8 J a c c a rd c o e ffic ie n t
ABM 1.95 × 10 −1 5.80 × 10 −2 6.74 × 10 −2 2.14 × 10 −3 6.85 × 10 −2 2.65 × 10 −3 6.53 × 10 −2 1.34 × 10 −3
0 .0
0 .0
P + B IR
A D R 0 .6 B io m in e
T R P W 0 .6
0 .3 4
6
8
5 0
1 0 0 1 5 0 2 0 0 tru s s n e s s
A B M D B L P
0 .3
0 .0
1 5 0
3 0 0 4 5 0 tru s s n e s s
0 .0 6
1 2 tru s s n e s s
1 8
Figure 5: Residual of the trussness. Table 4: Mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual on the trussness
A B M 0 .2 D B L P
0 .0
TRPW 6.97 × 10 −2 6.34 × 10 −3 8.57 × 10 −2 2.61 × 10 −3 6.14 × 10 −2 1.84 × 10 −3 3.13 × 10 −2 6.49 × 10 −4
tru s s n e s s
Methods →
0 .1 0 .0
ADR 5.22 × 10 −2 3.89 × 10 −3 7.64 × 10 −2 2.55 × 10 −3 8.72 × 10 −2 2.82 × 10 −3 1.06 × 10 −1 5.11 × 10 −3
P + IR F lic k r 0 .4
0 .0 0 .4 0 .8 J a c c a rd c o e ffic ie n t
P+BIR 2.02 × 10 −2 4.66 × 10 −4 4.45 × 10 −2 8.93 × 10 −4 2.56 × 10 −2 7.83 × 10 −4 2.85 × 10 −2 7.04 × 10 −5
0 .4 E m a il
2
0 .3 0 .0
P+IR 2.03 × 10 −2 8.61 × 10 −4 2.85 × 10 −2 3.76 × 10 −4 2.92 × 10 −2 9.09 × 10 −4 4.17 × 10 −2 4.88 × 10 −4
P + R S R
R e s id u a l
Methods →
P+RSR 2.75 × 10 −2 2.09 × 10 −3 2.31 × 10 −2 1.82 × 10 −4 1.28 × 10 −2 1.22 × 10 −4 2.22 × 10 −2 3.47 × 10 −4
0 .3 0 .6 0 .9 J a c c a rd c o e ffic ie n t
Flickr
Figure 4: Residual of the Jaccard coefficient.
Biomine DBLP
yielding a five-bin distribution for both the method and expected. For the 𝑗-th bin, let 𝑐 𝑗 and 𝑐ˆ𝑗 be the summed counts in the distribution of amethod and in expected, respectively. The residual is
E(r) var(r) E(r) var(r) E(r) var(r) E(r) var(r)
P+RSR
P+IR
P+BIR
ADR
TRPW
ABM
4.09 × 10 −2 1.22 × 10 −3 3.37 × 10 −2 2.56 × 10 −3 6.04 × 10 −2 5.32 × 10 −3 4.65 × 10 −2 1.12 × 10 −3
7.92 × 10 −2 2.36 × 10 −3 6.61 × 10 −2 4.61 × 10 −3 8.63 × 10 −2 1.17 × 10 −2 6.87 × 10 −2 2.23 × 10 −3
6.71 × 10 −2 8.06 × 10 −4 5.56 × 10 −2 2.85 × 10 −3 2.80 × 10 −2 9.94 × 10 −4 6.41 × 10 −2 1.90 × 10 −3
9.04 × 10 −2 3.20 × 10 −3 1.55 × 10 −1 1.29 × 10 −2 1.74 × 10 −1 3.27 × 10 −2 2.11 × 10 −1 1.09 × 10 −1
7.63 × 10 −2 2.46 × 10 −3 9.37 × 10 −2 4.24 × 10 −3 4.64 × 10 −2 9.93 × 10 −4 1.19 × 10 −1 8.67 × 10 −3
1.32 × 10 −1 2.58 × 10 −2 2.67 × 10 −1 2.93 × 10 −2 2.54 × 10 −1 9.25 × 10 −2 1.74 × 10 −1 3.11 × 10 −2
R e s id u a l
P + R S R
𝑐 +1
𝑟 𝑗 = log10 𝑐ˆ 𝑗𝑗 +1 , so 𝑟 𝑗 = 0 indicates exact agreement with expected, and a lower residual curve over the five bins indicates a closer match. For the shortest-path distance, all-pairs computation is too costly on the full graph; following [27, 35], both the methods and the estimation are run on a forest-fire subgraph [24] instead. Common Neighbor-defined Features. This group comprises the number of common neighbors and the Jaccard coefficient. Figure 3 and Table 2 report the results of the number of common neighbors. Table 2 lists the mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual over each dataset for all methods, where the three shades of red, from dark to light, mark the lowest, second-lowest, and third-lowest values in each row; the same convention applies to all subsequent tables. Across all four datasets, the residual curves of our three methods stay close to 𝑟 𝑗 = 0, and their 𝐸 (𝑟 ) in Table 2 is consistently the lowest, followed by ADR and TRPW, with ABM the worst. This confirms that directly optimizing the number of common neighbors yields a possible world whose common neighbor distribution faithfully reflects 𝐶 G (𝑢, 𝑣). Averaged over all datasets, P+IR and P+BIR stay within 0.12 of P+RSR, showing that the integer-based refinement preserves representativeness while improving efficiency. Figure 4 and Table 3 report the results of the jaccard coefficient. Our three methods again stay close to Expected, and their 𝐸 (𝑟 ) in Table 3 is the lowest on most datasets. The integer-based refinements P+IR and P+BIR trail P+RSR by a small margin, and on some datasets even surpass it, confirming that they preserve representativeness while improving efficiency. Common Neighbor-derived Features. This group comprises the trussness and the clustering coefficient. Figure 5 and Table 4 report the results of the trussness. In Figure 5, the residual curves of our three methods and TRPW all stay close to 𝑟 𝑗 = 0, far below those of ADR and ABM. Moreover, in terms of the statistics in Table 4, our three methods slightly outperform
0 .2
P + IR F lic k r 0 .2
0 .0
0 .0
0 .4 E m a il
0 .0 0 .4 0 .8 C lu s te rin g c o e ffic ie n t
P + B IR
0 .0 0 .4 0 .8 C lu s te rin g c o e ffic ie n t
A D R B io m in e
T R P W
A B M D B L P
0 .3
0 .2
0 .0
0 .0
0 .0 0 .4 0 .8 C lu s te rin g c o e ffic ie n t
0 .0 0 .4 0 .8 C lu s te rin g c o e ffic ie n t
Figure 6: Residual of the clustering coefficient TRPW: averaging 𝐸 (𝑟 ) across the four datasets, P+RSR, P+IR, and P+BIR attain 0.045, 0.075, and 0.054, all below the 0.084 of TRPW. Figure 6 and Table 5 report the results of the clustering coefficient. The results mirror those for trussness: in Figure 6, the residual curves of our three methods and TRPW far below those of ADR and ABM. While the average 𝐸 (𝑟 ) across the four datasets of our methods slightly outperform TRPW: P+RSR, P+IR, and P+BIR attain 0.036, 0.046, and 0.044, all below the 0.049 of TRPW. These results show that preserving the number of common neighbors helps keep the features derived from it close to Expected. Global Features. Figure 7 and Table 6 report the results of the shortest-path distance. In Figure 7, it is obvious that no method keeps its advantage across all datasets, and the statistics in Table 6 confirm this: P+RSR attains the lowest 𝐸 (𝑟 ) on Email and Biomine, TRPW on Flickr, and ABM on DBLP. Overall, although the leading method varies, our methods still achieve good results across datasets. This shows that even on the shortest-path distance, a global feature with no direct relationship to the number of common neighbors, our methods remain competitive.
6.3
Efficiency Evaluation
Figure 8 reports the running time of all methods on the four datasets. Among the baselines, ABM is the fastest on all datasets, but at the price of its weak effectiveness (§6.2). ADR is also faster than our methods on most datasets, mainly because its iteration count is fixed Í at 10 𝑒 ∈ E 𝑝 (𝑒), far below ours on Flickr and Biomine (1.4M and 5.9M versus 16.0M and 34.0M); on DBLP, where the two iteration counts become close (12.4M versus 17.2M), this advantage disappears. TRPW is the slowest throughout: preserving both expected 13
Flickr Biomine DBLP
E(r) var(r) E(r) var(r) E(r) var(r) E(r) var(r)
P+RSR
P+IR
P+BIR
ADR
TRPW
ABM
6.90 × 10 −2 6.32 × 10 −3 1.81 × 10 −2 1.45 × 10 −4 3.74 × 10 −2 1.63 × 10 −3 2.02 × 10 −2 1.43 × 10 −4
8.15 × 10 −2 5.46 × 10 −3 3.04 × 10 −2 6.01 × 10 −4 3.32 × 10 −2 8.44 × 10 −4 3.97 × 10 −2 1.35 × 10 −3
6.16 × 10 −2 4.05 × 10 −3 4.52 × 10 −2 3.28 × 10 −3 3.28 × 10 −2 1.41 × 10 −3 3.45 × 10 −2 4.49 × 10 −4
1.43 × 10 −1 2.21 × 10 −2 7.84 × 10 −2 1.34 × 10 −2 2.25 × 10 −1 2.02 × 10 −2 9.68 × 10 −2 8.82 × 10 −3
5.86 × 10−2 5.25 × 10−3 4.95 × 10 −2 4.17 × 10 −3 3.72 × 10−2 8.81 × 10−4 4.85 × 10 −2 1.34 × 10−3
1.24 × 10 −1 1.35 × 10 −2 1.16 × 10 −1 4.44 × 10 −3 1.10 × 10 −1 6.71 × 10 −3 1.49 × 10 −1 1.01 × 10 −2
P + R S R
R e s id u a l
0 .6 E m a il
P + IR 0 .8 F lic k r
0 .3
0 .4
0 .1
0 .0
0 .0
0 .0
6
1 2 1 8 S P d is ta n c e
3
P + B IR
6
9
A D R 0 .2 B io m in e
T R P W
Flickr Biomine
T im e (s )
DBLP
1 0 2
E(r) var(r) E(r) var(r) E(r) var(r) E(r) var(r)
T R P W
8
1 0 0
3
6
E m a il
S P d is ta n c e
ADR
TRPW
ABM
3.68 × 10 −2 6.62 × 10 −4 1.36 × 10 −1 1.66 × 10 −2 1.92 × 10 −2 1.97 × 10 −4 4.13 × 10 −2 5.04 × 10 −3
3.64 × 10 −2 7.64 × 10 −4 1.51 × 10 −1 2.85 × 10 −2 3.77 × 10 −2 5.80 × 10 −4 4.23 × 10 −2 4.67 × 10 −3
5.13 × 10 −2 4.65 × 10 −3 1.2 × 10 −1 3.32 × 10 −2 3.31 × 10 −2 6.69 × 10 −4 5.15 × 10 −2 6.87 × 10 −3
5.77 × 10 −2 2.64 × 10 −3 1.74 × 10 −1 3.18 × 10 −2 2.73 × 10 −2 3.76 × 10 −5 4.71 × 10 −2 6.47 × 10 −3
3.36 × 10 −1 5.64 × 10 −2 1.03 × 10 −1 9.32 × 10 −3 3.09 × 10 −2 1.14 × 10 −3 6.36 × 10 −2 6.41 × 10 −3
2.12 × 10 −1 2.13 × 10 −2 3.40 × 10 −1 7.61 × 10 −2 8.74 × 10 −2 2.12 × 10 −3 2.75 × 10 −2 6.52 × 10 −4
A D R 6 × 1 0 3
A B M
6 × 1 0 4
P + B IR
3 × 1 0 4 F lic k r
5 .0 × 1
0
5
0 .0
0 .0 0 .0
8 .0 × 1
0
6
1 .6 × 1
0
7
0 .0
1 .8 × 1
0
7
3 .6 × 1
0
7
0 .0 0 .0
Ite ra tio n s k
Ite ra tio n s k
6
0 0 7 .5 × 1 1 .5 × 1
7
Ite ra tio n s k
0
2 0 4 0 6 0 8 0 1 0 0
0
P + IR 4 × 1 0 4 B io m in e
2 × 1 0 3 D B L P
3 × 1 0 3
2 × 1 0 4
1 × 1 0 3
0
0
6 × 1 0 3 F lic k r
P + R S R
2 0 4 0 6 0 8 0 1 0 0
2 0 4 0 6 0 8 0 1 0 0
2 0 4 0 6 0 8 0 1 0 0
the refinement is still incomplete and many edges remain statechangeable. It then rises steeply, marking the point where enough state-changeable edges have been removed for the SEP to fall below 𝜏𝑞 . The confidence is therefore a faithful signal of refinement progress, the first requirement for the termination to be effective. Quality Control via Thresholds. Figure 10 reports the MAD of the resulting possible world under varying 𝜏𝑞 and 𝜏𝑐 on the four datasets. Across all datasets, the MAD increases with 𝜏𝑞 and decreases with 𝜏𝑐 . The two trends follow from the roles of the two thresholds. 𝜏𝑞 is the threshold on the SEP at which the refinement may stop, so a larger 𝜏𝑞 permits more state-changeable edges to remain and stops the refinement earlier, leaving the possible world less refined and thus raising the MAD. 𝜏𝑐 is the confidence required before stopping, so a larger 𝜏𝑐 demands stronger evidence that SEP < 𝜏𝑞 , which defers the stop to a more refined possible world and thus lowers the MAD. Both trends are monotonic, so a user can steer the refinement quality predictably through 𝜏𝑞 and 𝜏𝑐 , which is the second requirement for the termination to be effective.
3 × 1 0 3 B io m in e
1 6 E m a il 1 2 8
Figure 11: Time of P+RSR and P+IR under varying iteration count 𝑘 (from 20% to 100% of |E |).
D B L P
Figure 8: Running time of all methods
node degrees and expected triangle degrees incurs the heaviest per-iteration computation. We then focus on our three methods. P+IR replaces the floatingpoint computation in each iteration of P+RSR with integer counting, which makes it 38.6% faster than P+RSR on average. P+BIR builds on P+IR and additionally maintains the Beta distribution to terminate the refinement adaptively once the desired quality is reached. This additional maintenance raises the running time by 7.2% on average over P+IR. In return, P+BIR no longer requires a manually specified iteration count, but instead lets the user specify the desired quality directly and stops on its own once that quality is attained.
6.4
5
9
P+BIR
1 0 3
0
Figure 10: MAD under varying 𝜏𝑞 and 𝜏𝑐 .
1 2
P+IR
1 0 1
2 .5 × 1
0 .0 4
S P d is ta n c e
P + IR
0 .0
1 .0 D B L P 0 .5
B io m in e
0 .5
A B M 0 .2 D B L P
P+RSR
P + R S R
0 .0
0 .1
S P d is ta n c e
1 0 4
1 .0
F lic k r
0 .5
Figure 9: Confidence that SEP < 𝜏𝑞 as the refinement proceeds
Table 6: Mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual on the SP distance Email
1 .0
E m a il
0 .5
Ite ra tio n s k
Figure 7: Residual of SP distance
Methods →
1 .0
T im e (s )
Methods → Email
C o n fid e n c e
Table 5: Mean 𝐸 (𝑟 ) and variance 𝑣𝑎𝑟 (𝑟 ) of the residual on the clustering coefficient
6.5
Parameter Sensitivity
Effect of Iteration Count. We vary the iteration 𝑘 from 20% to 100% of |E | for each dataset and report the MAD (Fig. 12) and running time (Fig. 11) of P+RSR and P+IR. As 𝑘 grows, the running time of both methods increases because each additional iteration performs one more refinement step, while their MAD decreases because the extra iterations give the refinement more chances to change edge states that reduce the total discrepancy. The MAD decrease slows as 𝑘 grows. This is because each iteration changes the state of a randomly selected edge, but the more iterations have been run, the fewer edges remain whose state change reduces the total discrepancy, so the reduction per iteration shrinks. Across the four datasets, P+IR raises the MAD by only 2.8% on average while reducing the running time by 32.3% on average, confirming that the integer rounding trades a small quality loss for a substantial efficiency gain. Effect of 𝜏𝑞 and 𝜏𝑐 . Figure 13 reports the running time of P+BIR under varying 𝜏𝑞 and 𝜏𝑐 on four datasets; their effect on the MAD is examined in §6.4. Across all datasets, the running time decreases as
Effectiveness of the Beta-based Termination
The Beta-based termination ends the integer-based refinement once the confidence that SEP < 𝜏𝑞 reaches 𝜏𝑐 . Its effectiveness rests on the two following requirements. First, the confidence must be a faithful signal of refinement progress, so that the point at which it reaches 𝜏𝑐 indeed corresponds to a well-refined possible world; we examine this in the Reliability of the Confidence Signal. Second, once the confidence is trustworthy, the two thresholds 𝜏𝑞 and 𝜏𝑐 must translate into predictable control over the refinement quality, so that the user can steer the output through them; we examine this in the Quality Control via Confidence Thresholds. Reliability of the Confidence Signal. Figure 9 reports how the confidence that SEP < 𝜏𝑞 evolves with the iteration count 𝑘 on the four datasets. The figure shows that the confidence cannot trigger the termination prematurely. For all datasets, the confidence stays negligible (as low as 10−200 ) for a long time, during which 14
M A D
0 .7
E m a il
P + R S R F lic k r
0 .5 0 0 .4 5
0 .6
2 0 4 0 6 0 8 0 1 0 0
0 .4 0
0 .9
P + IR B io m in e
0 .8
2 0 4 0 6 0 8 0 1 0 0
2 0 4 0 6 0 8 0 1 0 0
0 .6 0 0 .5 4 0 .4 8
termination that allows the refinement to stop once the user-desired quality is reached. Experiments on four real-world uncertain graphs demonstrate the effectiveness of our methods, with the best overall performance on common-neighbor-related tasks.
D B L P
2 0 4 0 6 0 8 0 1 0 0
Figure 12: MAD of P+RSR and P+IR under varying iteration count 𝑘 (from 20% to 100% of |E|).
REFERENCES [1] Milton Abramowitz and Irene A Stegun. 1948. Handbook of mathematical functions with formulas, graphs, and mathematical tables. Vol. 55. US Government printing office. [2] Khawla Asmi and Abdallah Abarda. 2022. An efficient local algorithm for overlapping community detection in social networks. Procedia Computer Science 201 (2022), 789–794. [3] Saurabh Asthana, Oliver D King, Francis D Gibbons, and Frederick P Roth. 2004. Predicting protein complex membership using probabilistic network reliability. Genome research 14, 6 (2004), 1170–1175. [4] Michael O Ball. 1986. Computational complexity of network reliability analysis: An overview. Ieee transactions on reliability 35, 3 (1986), 230–239. [5] Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, New York, NY, USA - August 24 - 27, 2014, Sofus A. Macskassy, Claudia Perlich, Jure Leskovec, Wei Wang, and Rayid Ghani (Eds.). ACM, 1316–1325. https://doi.org/10.1145/2623330.2623655 [6] Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 1316– 1325. [7] Russel E Caflisch. 1998. Monte carlo and quasi-monte carlo methods. Acta numerica 7 (1998), 1–49. [8] Xuelu Chen, Muhao Chen, Weijia Shi, Yizhou Sun, and Carlo Zaniolo. 2019. Embedding uncertain knowledge graphs. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33. 3363–3370. [9] Code. 2026. Code. https://github.com/KGLab-HDU/CRPW. [10] Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008), 1–29. [11] Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. 2021. Core decomposition on uncertain graphs revisited. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 196–210. [12] Simone Daminelli, Josephine Maria Thomas, Claudio Durán, and Carlo Vittorio Cannistraci. 2015. Common neighbours and the local-community-paradigm for topological link prediction in bipartite networks. New Journal of Physics 17, 11 (2015), 113037. [13] Lauri Eronen and Hannu Toivonen. 2012. Biomine: Predicting Links Between Biological Entities Using Network Models of Heterogeneous Databases. BMC Bioinformatics 13 (2012), 119. https://doi.org/10.1186/1471-2105-13-119 [14] Bernard D Flury. 1990. Acceptance–rejection sampling made easy. Siam Review 32, 3 (1990), 474–476. [15] Kurt Hornik. 2024. Two Monotonicity Results for Beta Distribution Functions. Entropy 26, 11 (2024), 938. [16] Ruoming Jin, Lin Liu, and Charu C Aggarwal. 2011. Discovering highly reliable subgraphs in uncertain graphs. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 992–1000. [17] Ruoming Jin, Lin Liu, Bolin Ding, and Haixun Wang. 2011. Distance-constraint reachability computation in uncertain graphs. Proceedings of the VLDB Endowment 4, 9 (2011), 551–562. [18] Amin Kaveh, Matteo Magnani, and Christian Rohner. 2021. Defining and measuring probabilistic ego networks. Social Network Analysis and Mining 11, 1 (2021), 2. [19] Xiangyu Ke, Arijit Khan, and Leroy Lim Hong Quan. 2019. An in-depth comparison of st reliability algorithms over uncertain graphs. arXiv preprint arXiv:1904.05300 (2019). [20] Faiza Riaz Khawaja, Zuping Zhang, and Aman Ullah. 2025. Common-neighbor based overlapping community detection in complex networks. Social Network Analysis and Mining 15, 1 (2025), 61. [21] Jon Kleinberg and Eva Tardos. 2006. Algorithm design. Pearson Education India. [22] Bryan Klimt and Yiming Yang. 2004. The enron corpus: A new dataset for email classification research. In European conference on machine learning. Springer, 217–226. [23] Peter M Kogge. 2016. Jaccard coefficients as a potential graph benchmark. In 2016 IEEE international parallel and distributed processing symposium workshops (IPDPSW). IEEE, 921–928. [24] Jure Leskovec and Christos Faloutsos. 2006. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. 631–636.
Figure 13: Time of P+BIR under varying 𝜏𝑞 and 𝜏𝑐 .
𝜏𝑞 grows and increases as 𝜏𝑐 grows, and both trends hold regardless of the value of the other threshold. A larger 𝜏𝑞 relaxes the target on the SEP, so the termination criterion is met after fewer iterations, shortening the running time. A larger 𝜏𝑐 requires the criterion to hold more strictly before terminating, deferring the iteration at which it is first met and thus lengthening the running time.
7
RELATED WORK
The research related to ours falls into two lines, reviewed below: querying and mining over uncertain graphs, and constructing representative possible worlds. Uncertain graph querying and mining. A wide range of querying and mining tasks has been studied over uncertain graphs. For querying, representative tasks include 𝑠-𝑡 reliability [19], 𝑘-nearestneighbor search [29], and SP distance [33]. For mining, classic deterministic problems such as core decomposition [6, 11] and truss decomposition [40] have been generalized to the uncertain setting. These tasks build on the possible world model, under which an uncertain graph represents a probability distribution over its possible worlds.A common approach samples a set of possible worlds, executes the task on each, and aggregates the outputs to estimate the target result. However, sufficient estimation accuracy often requires many samples, incurring substantial overhead from possible-world generation and repeated task execution. Representative possible worlds. To overcome this limitation, the RPW is introduced. Parchas et al. [27] first present the degreebased RPW, which preserve the expected degree of every node and characterizes the local connectivity of each individual node. Song et al. [35] further preserve the expected triangle degree of every node, as triangles are an important structure in many graph tasks such as clustering coefficient [36]. However, all these RPWs preserve only per-node features, while ignoring the number of common neighbors, a node pair feature. Yet the number of common neighbors is a key feature underlying many mining tasks [2, 39]. This motivates us to study CRPW problem in this paper.
8
CONCLUSION
We study the CRPW problem, which seek the possible world that best preserves expected common-neighbor counts, and establish its NP-hardness. We develop a two-stage algorithm combining quick initialization with iterative refinement. We accelerate the refinement by replacing its costly floating-point evaluation with cheap integer counting, and further design a Beta-based adaptive 15
Transactions on Big Data 9, 1 (2021), 37–50. [33] Arkaprava Saha, Ruben Brokkelkamp, Yllka Velaj, Arijit Khan, and Francesco Bonchi. 2021. Shortest paths and centrality in uncertain networks. Proceedings of the VLDB Endowment 14, 7 (2021), 1188–1201. [34] Thomas J Schaefer. 1978. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing. 216–226. [35] Shaoying Song, Zhaonian Zou, and Kang Liu. 2016. Triangle-based representative possible worlds of uncertain graphs. In International Conference on Database Systems for Advanced Applications. Springer, 283–298. [36] Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of ‘smallworld’networks. nature 393, 6684 (1998), 440–442. [37] Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. Acm computing surveys (csur) 45, 4 (2013), 1–35. [38] Bohua Yang, Dong Wen, Lu Qin, Ying Zhang, Lijun Chang, and Rong-Hua Li. 2019. Index-based optimal algorithm for computing k-cores in large uncertain graphs. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 64–75. [39] Lin Yao, Luning Wang, Lv Pan, and Kai Yao. 2016. Link prediction based on common-neighbors for dynamic social network. Procedia Computer Science 83 (2016), 82–89. [40] Zhaonian Zou and Rong Zhu. 2017. Truss decomposition of uncertain graphs. Knowledge and Information Systems 50, 1 (2017), 197–230.
[25] Michael Ley. 2002. The DBLP computer science bibliography: Evolution, research issues, perspectives. In International symposium on string processing and information retrieval. Springer, 1–10. [26] Linyuan Lü, Ci-Hang Jin, and Tao Zhou. 2009. Similarity index based on local paths for link prediction of complex networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 80, 4 (2009), 046122. [27] Panos Parchas, Francesco Gullo, Dimitris Papadias, and Franceseco Bonchi. 2014. The pursuit of a good possible world: extracting representative instances of uncertain graphs. In Proceedings of the 2014 ACM SIGMOD international conference on management of data. 967–978. [28] You Peng, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Lu Qin. 2018. Efficient probabilistic k-core computation on uncertain graphs. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 1192–1203. [29] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. k-Nearest Neighbors in Uncertain Graphs. Proceedings of the VLDB Endowment 3, 1 (2010), 997–1008. https://doi.org/10.14778/1920841.1920967 [30] Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-nearest neighbors in uncertain graphs. Proceedings of the VLDB Endowment 3, 1-2 (2010), 997–1008. [31] Jay Pujara, Hui Miao, Lise Getoor, and William Cohen. 2013. Knowledge graph identification. In International semantic web conference. Springer, 542–557. [32] Lianpeng Qiao, Rong-Hua Li, Zhiwei Zhang, Ye Yuan, Guoren Wang, and Hongchao Qin. 2021. Maximal quasi-cliques mining in uncertain graphs. IEEE
16