pith. sign in

arxiv: 2409.08405 · v2 · submitted 2024-09-12 · 💻 cs.SI · cs.DS

Consistent Tie-Strength Labeling for Multilayer Strong Triadic Closure

Lutz Oettershagen , Athanasios L. Konstantinidis , Fariba Ranjbar , Giuseppe F. Italiano This is my paper

Pith reviewed 2026-05-23 20:42 UTC · model grok-4.3

classification 💻 cs.SI cs.DS
keywords multilayer networksstrong triadic closuretie strengthapproximation algorithmsNP-hardconsistencynetwork labeling
0
0 comments X

The pith

Axiomatic multilayer STC and STC+ enforce consistent tie-strength labels across network layers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes new formulations called multilayer STC and its extension STC+ for labeling ties as strong or weak in multilayer networks. These formulations rest on axioms that require the labels to be consistent from one layer to the next, rather than allowing independent decisions per layer. Independent per-layer labeling can produce contradictory interpretations of the same relationship, which the new axioms prevent. The formulations are proven NP-hard, and the paper supplies 2- and 6-approximation algorithms together with exact solvers that return consistent labelings on real networks.

Core claim

We propose new formulations, multilayer STC and its extension STC+, which are axiomatically grounded and enforce cross-layer consistency. These problems are NP-hard; we present efficient 2- and 6-approximation algorithms alongside exact solutions.

What carries the argument

Multilayer STC and STC+ formulations that axiomatically enforce cross-layer consistency in tie labeling.

Load-bearing premise

The specific axioms chosen for multilayer STC and STC+ correctly capture the desired notion of cross-layer consistency without discarding important layer-specific structural information or introducing new inconsistencies.

What would settle it

A small multilayer graph on which the proposed algorithms return a labeling that assigns contradictory strong/weak labels to the same edge across layers would falsify the consistency claim.

Figures

Figures reproduced from arXiv: 2409.08405 by Athanasios L. Konstantinidis, Fariba Ranjbar, Giuseppe F. Italiano, Lutz Oettershagen.

Figure 1
Figure 1. Figure 1: A toy multilayer network with four nodes in two layers. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A multilayer graph with three layers. The blue edges [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) shows a multilayer graph with two layers. In each [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A multilayer graph with two layers and an optimal [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The empirical approximation ratios (*using lower [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original abstract

Inferring tie strengths (strong vs. weak) is a core task in network analysis, often guided by the Strong Triadic Closure (STC) principle. In multilayer networks, such as social platforms or biological systems, applying STC independently to each layer can lead to inconsistent tie labels, undermining interpretations that rely on coherent relationship semantics across layers. We propose new formulations, multilayer STC and its extension STC+, which are axiomatically grounded and enforce cross-layer consistency. These problems are NP-hard; we present efficient 2- and 6-approximation algorithms alongside exact solutions. Experiments on real-world networks demonstrate that our methods produce consistent tie strength labelings with a transparent structural justification, significantly improving over the baselines.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper introduces multilayer STC and STC+ formulations for inferring consistent strong/weak tie labels across layers in multilayer networks. These are presented as axiomatically grounded to enforce cross-layer consistency (unlike independent per-layer application of STC), proven NP-hard, equipped with 2- and 6-approximation algorithms plus exact solvers, and validated experimentally on real-world networks where they outperform baselines.

Significance. If the axiomatic grounding and approximation guarantees hold, the work supplies a principled, computationally tractable method for coherent tie-strength labeling in multilayer settings common to social platforms and biological systems. The explicit approximation ratios and experimental improvements constitute concrete, usable contributions to network analysis.

minor comments (2)
  1. [Abstract] Abstract: the phrase 'significantly improving over the baselines' should be supported by explicit quantitative metrics (e.g., consistency score deltas or objective values) or a forward reference to the relevant table/figure in the main text.
  2. The manuscript would benefit from a short table or paragraph explicitly listing the axioms used for multilayer STC and STC+ (including any differences between the two) to make the 'axiomatically grounded' claim immediately verifiable.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the thorough and positive review of our manuscript on multilayer STC and STC+ formulations. The recommendation for minor revision is appreciated, and we note that the report highlights the axiomatic grounding, approximation algorithms, and experimental results as contributions. No specific major comments or points of criticism were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces new problem formulations (multilayer STC and STC+) defined via explicitly stated axioms for cross-layer consistency, then proves NP-hardness and supplies approximation algorithms with stated ratios. No step reduces a claimed prediction or uniqueness result to a fitted parameter, self-citation chain, or definitional tautology; the axioms are chosen as modeling assumptions rather than derived from the algorithms or outputs, and the approximation guarantees follow from standard algorithmic analysis on the defined problems. The work is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard strong triadic closure principle as a domain assumption plus newly introduced axioms for consistency; no free parameters or invented entities are described in the abstract.

axioms (1)
  • domain assumption Strong Triadic Closure principle applies to tie-strength inference in networks.
    The work extends this established principle to the multilayer setting.

pith-pipeline@v0.9.0 · 5658 in / 1101 out tokens · 32776 ms · 2026-05-23T20:42:51.612780+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 1 internal anchor

  1. [1]

    Data Min

    Adriaens, F., De Bie, T., Gionis, A., Lijffijt, J., Matakos, A., Rozen- shtein, P.: Relaxing the strong triadic closure problem for edge strength inference. Data Min. Knowl. Discov. pp. 1–41 (2020)

    work page 2020

  2. [2]

    Journal of Algorithms 2(2), 198– 203 (1981)

    Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms 2(2), 198– 203 (1981)

    work page 1981

  3. [3]

    Physics reports 544(1), 1–122 (2014)

    Boccaletti, S., Bianconi, G., Criado, R., Del Genio, C.I., G ´omez- Gardenes, J., Romance, M., Sendina-Nadal, I., Wang, Z., Zanin, M.: The structure and dynamics of multilayer networks. Physics reports 544(1), 1–122 (2014)

    work page 2014

  4. [4]

    Scientific reports 3(1), 1344 (2013)

    Cardillo, A., G ´omez-Gardenes, J., Zanin, M., Romance, M., Papo, D., Pozo, F.d., Boccaletti, S.: Emergence of network features from multiplexity. Scientific reports 3(1), 1344 (2013)

    work page 2013

  5. [5]

    Crainic, T.G., Gendron, B., Kazemzadeh, M.R.A.: A taxonomy of multilayer network design and a survey of transportation and telecom- munication applications. Eu. J. of Oper. Res. 303(1), 1–13 (2022)

    work page 2022

  6. [6]

    Nature Physics 19(9), 1247–1262 (2023)

    De Domenico, M.: More is different in real-world multilayer networks. Nature Physics 19(9), 1247–1262 (2023)

    work page 2023

  7. [7]

    Nature comm

    De Domenico, M., Nicosia, V ., Arenas, A., Latora, V .: Structural reducibility of multilayer networks. Nature comm. 6(1), 6864 (2015)

    work page 2015

  8. [8]

    Physical Review X 3(4), 041022 (2013)

    De Domenico, M., Sol ´e-Ribalta, A., Cozzo, E., Kivel ¨a, M., Moreno, Y ., Porter, M.A., G´omez, S., Arenas, A.: Mathematical formulation of multilayer networks. Physical Review X 3(4), 041022 (2013)

    work page 2013

  9. [9]

    Cambridge University Press (2016)

    Dickison, M.E., Magnani, M., Rossi, L.: Multilayer social networks. Cambridge University Press (2016)

    work page 2016

  10. [10]

    Cambridge University Press (2016)

    Dickison, M.E., Magnani, M., Rossi, L.: Multilayer Social Networks. Cambridge University Press (2016)

    work page 2016

  11. [11]

    Easley, D.A., Kleinberg, J.M.: Networks, Crowds, and Markets - Rea- soning About a Highly Connected World (2010)

    work page 2010

  12. [12]

    In: CIKM

    Galimberti, E., Bonchi, F., Gullo, F.: Core decomposition and densest subgraph in multilayer networks. In: CIKM. pp. 1807–1816 (2017)

    work page 2017

  13. [13]

    In: Proceedings of the 27th International Conference on Human Factors in Computing Systems, CHI

    Gilbert, E., Karahalios, K.: Predicting tie strength with social media. In: Proceedings of the 27th International Conference on Human Factors in Computing Systems, CHI. pp. 211–220. ACM (2009)

    work page 2009

  14. [14]

    Computers & Operations Research 33(12), 3520– 3534 (2006)

    Gomes, F.C., Meneses, C.N., Pardalos, P.M., Viana, G.V .R.: Experimen- tal analysis of approximation algorithms for the vertex cover and set covering problems. Computers & Operations Research 33(12), 3520– 3534 (2006)

    work page 2006

  15. [15]

    Granovetter, M.S.: The strength of weak ties. A. J. of Soc. 78(6), 1360– 1380 (1973)

    work page 1973

  16. [16]

    Algorithmica 82, 853–880 (2020)

    Gr ¨uttemeier, N., Komusiewicz, C.: On the relation of strong triadic closure and cluster deletion. Algorithmica 82, 853–880 (2020)

    work page 2020

  17. [17]

    Big Data Analytics 5(1), 2 (2020)

    Hammoud, Z., Kramer, F.: Multilayer networks: aspects, implementa- tions, and application in biomedicine. Big Data Analytics 5(1), 2 (2020)

    work page 2020

  18. [18]

    PloS one 8(1), e52168 (2013)

    Jones, J.J., Settle, J.E., Bond, R.M., Fariss, C.J., Marlow, C., Fowler, J.H.: Inferring tie strength from online directed behavior. PloS one 8(1), e52168 (2013)

    work page 2013

  19. [19]

    In: Proceedings of the International AAAI Conference on Web and Social Media

    Kahanda, I., Neville, J.: Using transactional information to predict link strength in online social networks. In: Proceedings of the International AAAI Conference on Web and Social Media. vol. 3, pp. 74–81 (2009)

    work page 2009

  20. [20]

    Journal of complex networks 2(3), 203–271 (2014)

    Kivel ¨a, M., Arenas, A., Barthelemy, M., Gleeson, J.P., Moreno, Y ., Porter, M.A.: Multilayer networks. Journal of complex networks 2(3), 203–271 (2014)

    work page 2014

  21. [21]

    Konstantinidis, A.L., Nikolopoulos, S.D., Papadopoulos, C.: Strong triadic closure in cographs and graphs of low maximum degree. Th. Comp. Sci. 740, 76–84 (2018)

    work page 2018

  22. [22]

    Konstantinidis, A.L., Papadopoulos, C.: Maximizing the strong triadic closure in split graphs and proper interval graphs. Discret. Appl. Math. 285, 79–95 (2020)

    work page 2020

  23. [23]

    In: ALENEX

    Lamm, S., Schulz, C., Strash, D., Williger, R., Zhang, H.: Exactly solving the maximum weight independent set problem on large real- world graphs. In: ALENEX. pp. 144–158. SIAM (2019)

    work page 2019

  24. [24]

    In: SEA (2022)

    Langedal, K., Langguth, J., Manne, F., Schroeder, D.T.: Efficient min- imum weight vertex cover heuristics using graph neural networks. In: SEA (2022)

    work page 2022

  25. [25]

    In: International symposium on string processing and information retrieval

    Ley, M.: The dblp computer science bibliography: Evolution, research issues, perspectives. In: International symposium on string processing and information retrieval. pp. 1–10. Springer (2002)

    work page 2002

  26. [26]

    Europhysics Letters 89(1), 18001 (2010)

    L ¨u, L., Zhou, T.: Link prediction in weighted networks: The role of weak ties. Europhysics Letters 89(1), 18001 (2010)

    work page 2010

  27. [27]

    Combinatorial Analysis of Multiple Networks

    Magnani, M., Micenkova, B., Rossi, L.: Combinatorial analysis of multiple networks. arXiv preprint arXiv:1303.4986 (2013)

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  28. [28]

    Data Min

    Matakos, A., Gionis, A.: Strengthening ties towards a highly-connected world. Data Min. Knowl. Discov. 36(1), 448–476 (2022)

    work page 2022

  29. [29]

    In: ECMLPKDD

    Oettershagen, L., Konstantinidis, A.L., Italiano, G.F.: Inferring tie strength in temporal networks. In: ECMLPKDD. pp. 69–85 (2022)

    work page 2022

  30. [30]

    arXiv preprint arXiv:2206.11705 (2024)

    Oettershagen, L., Konstantinidis, A.L., Italiano, G.F.: Inferring tie strength in temporal networks. arXiv preprint arXiv:2206.11705 (2024)

    work page arXiv 2024

  31. [31]

    In: SEBD

    Pappalardo, L., Rossetti, G., Pedreschi, D.: Measuring tie strength in multidimensional networks. In: SEBD. pp. 223–230 (2013)

    work page 2013

  32. [32]

    ACM Trans

    Pham, H., Shahabi, C., Liu, Y .: Inferring social strength from spatiotem- poral data. ACM Trans. Database Syst. 41(1), 7:1–7:47 (2016)

    work page 2016

  33. [33]

    Rozenshtein, P., Tatti, N., Gionis, A.: Inferring the strength of social ties: A community-driven approach. In: KDD. pp. 1017–1025. ACM (2017)

    work page 2017

  34. [34]

    Sintos, S., Tsaparas, P.: Using strong triadic closure to characterize ties in social networks. In: KDD. pp. 1466–1475 (2014)

    work page 2014

  35. [35]

    In: Proceedings of the 2015 conference on empirical methods in natural language processing

    Toutanova, K., Chen, D., Pantel, P., Poon, H., Choudhury, P., Gamon, M.: Representing text for joint embedding of text and knowledge bases. In: Proceedings of the 2015 conference on empirical methods in natural language processing. pp. 1499–1509 (2015)

    work page 2015

  36. [36]

    PloS one 8(9), e73970 (2013)

    Vanhems, P., Barrat, A., Cattuto, C., Pinton, J.F., Khanafer, N., R ´egis, C., Kim, B.a., Comte, B., V oirin, N.: Estimating potential infection transmission routes in hospital wards using wearable proximity sensors. PloS one 8(9), e73970 (2013)

    work page 2013

  37. [37]

    In: International Conference on Machine Learning

    Veldt, N.: Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds. In: International Conference on Machine Learning. pp. 22060–22083. PMLR (2022)

    work page 2022

  38. [38]

    In: Proceedings of the 19th International Con- ference on World Wide Web, WWW

    Xiang, R., Neville, J., Rogati, M.: Modeling relationship strength in online social networks. In: Proceedings of the 19th International Con- ference on World Wide Web, WWW. pp. 981–990. ACM (2010)

    work page 2010