2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane
Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.
academic

Локальное причинное обнаружение для статистически эффективного причинного вывода

Основная информация

  • ID статьи: 2510.14582
  • Название: Local Causal Discovery for Statistically Efficient Causal Inference
  • Авторы: Mátyás Schubert (Амстердамский университет), Tom Claassen (Университет Радбауд Неймеген), Sara Magliacane (Амстердамский университет)
  • Классификация: stat.ML cs.AI cs.LG
  • Дата публикации: 16 октября 2025 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2510.14582v1

Аннотация

Методы причинного обнаружения могут идентифицировать действительные наборы корректировки для оценки причинного эффекта между парой целевых переменных, даже когда лежащий в основе причинный граф неизвестен. Глобальные методы причинного обнаружения сосредоточены на изучении всего причинного графа и, таким образом, способны восстановить оптимальные наборы корректировки (т.е. наборы с наименьшей асимптотической дисперсией), но они быстро становятся вычислительно неразрешимыми с увеличением количества переменных. Локальные методы причинного обнаружения предлагают более масштабируемую альтернативу, сосредоточиваясь на локальной окрестности целевых переменных, но ограничены статистически субоптимальными наборами корректировки. В данной работе авторы предлагают LOAD (Local Optimal Adjustment Discovery) — надежный и полный метод причинного обнаружения, который сочетает вычислительную эффективность локальных методов со статистической оптимальностью глобальных методов.

Исследовательский контекст и мотивация

Определение проблемы

В причинном выводе оценка причинного эффекта между двумя переменными является центральной задачей. Когда лежащий в основе причинный граф неизвестен, необходимо использовать методы причинного обнаружения для идентификации действительных наборов корректировки для оценки причинного эффекта. Существующие методы сталкиваются с фундаментальным компромиссом:

  1. Дилемма глобальных методов: Глобальные методы причинного обнаружения (такие как алгоритм PC) способны изучить полный причинный граф и восстановить оптимальные наборы корректировки, но вычислительная сложность растет экспоненциально с количеством переменных, что делает их неприменимыми для крупномасштабных задач.
  2. Ограничения локальных методов: Локальные методы причинного обнаружения (такие как MB-by-MB, LDECC) вычислительно эффективны, но могут восстановить только субоптимальные наборы корректировки, что приводит к более высокой асимптотической дисперсии при оценке причинного эффекта.

Исследовательская мотивация

Авторы выявили следующие проблемы в существующих локальных методах:

  • Алгоритм LocalPC недостаточно надежен при идентификации смежных переменных и может ошибочно идентифицировать несмежные супругов как смежные
  • Алгоритм LDECC неполный и в некоторых случаях не может ориентировать все ориентируемые ребра
  • Алгоритм LDP может ошибочно сообщить об идентифицируемости эффекта в некоторых случаях, когда эффект равен нулю

Следовательно, необходим новый метод, который сохраняет вычислительную эффективность локальных методов и одновременно достигает статистической оптимальности глобальных методов.

Основные вклады

  1. Разработка методов определения идентифицируемости причинного эффекта на основе локальной информации: Предложены необходимые и достаточные условия для определения идентифицируемости причинного эффекта, используя только локальную информацию.
  2. Предложение алгоритма LOAD: Надежный и полный метод, который может идентифицировать оптимальные наборы корректировки, используя только локальную информацию вокруг переменных.
  3. Комплексная экспериментальная оценка: Оценка LOAD на синтетических и реальных данных, демонстрирующая, что он может восстановить высококачественные наборы корректировки с низкими вычислительными затратами.
  4. Теоретические гарантии: Доказана надежность и полнота LOAD при определении идентифицируемости причинного эффекта и поиске оптимальных наборов корректировки.

Подробное описание метода

Определение задачи

Для пары целевых переменных X и Y цель состоит в:

  1. Определении причинной связи между X и Y (явный предок, возможный предок или определенный не-предок)
  2. Определении идентифицируемости причинного эффекта
  3. Если идентифицируемо, найти оптимальный набор корректировки; в противном случае вернуть локально действительный родительский набор корректировки

Архитектура алгоритма LOAD

Алгоритм LOAD состоит из 5 основных этапов:

Этап 1: Определение причинной связи между целевыми переменными

Использование алгоритма LocalRelate (Алгоритм 1) с применением следующих теорем:

  • Отношение явного предка (Теорема 4.1): Для любых двух различных узлов X и Y в CPDAG G, X ∈ ExplAn_G(Y) тогда и только тогда, когда X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
  • Определение отношения не-предка (Теорема 4.2): X является определенным не-предком Y тогда и только тогда, когда X ⊥⊥ Y | Pa_G(X)

Этап 2: Тестирование идентифицируемости причинного эффекта

Предложен адаптивный тест на основе локальной информации:

Лемма 4.3: Для X ∈ PossAn_G(Y) в CPDAG G, G является адаптированным относительно (X,Y) тогда и только тогда, когда:

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

Это условие может быть эффективно обнаружено алгоритмом LocalAmenTest (Алгоритм 2).

Этапы 3-5: Построение оптимального набора корректировки

Если причинный эффект идентифицируем, LOAD строит оптимальный набор корректировки следующим образом:

  1. Поиск явных потомков: Идентификация всех явных потомков T
  2. Идентификация узлов-посредников: Поиск узлов, которые являются одновременно явными потомками T и явными предками O
  3. Построение оптимального набора корректировки: 
    Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

Технические инновации

  1. Локальный тест адаптации: Впервые предложены необходимые и достаточные условия для тестирования адаптации, используя только локальную информацию, избегая необходимости проверки всех возможных направленных путей.
  2. Механизм кеширования: Улучшенный алгоритм MB-by-MB использует кеш для повторного использования ранее идентифицированных одеял Маркова и локальных структур, значительно повышая вычислительную эффективность.
  3. Теоретическая полнота: Доказана надежность и полнота LOAD при определении причинных связей, идентифицируемости и оптимальных наборов корректировки.

Экспериментальная установка

Наборы данных

  1. Синтетические данные:
    • Случайно сгенерированные графы Эрдёша–Рёньи
    • Количество переменных: 100-1000
    • Ожидаемая степень: d=2, максимальная степень: dmax=10
    • Размер выборки: nD=10000
  2. Реальные сети:
    • Сеть MAGIC-NIAB: 44 узла, средняя степень 3
    • Сеть ANDES: 223 узла, средняя степень 3.03

Метрики оценки

  1. Вычислительная эффективность: Количество тестов условной независимости
  2. Качество набора корректировки: Оценка F1 оптимального набора корректировки
  3. Качество оценки причинного эффекта: Расстояние вмешательства (intervention distance)

Методы сравнения

  • Глобальные методы: PC, MARVEL, SNAP(∞)
  • Локальные методы: MB-by-MB+, LDECC+, LDP+ (расширенные версии)

Детали реализации

  • Уровень значимости: α = 0.01
  • Три типа тестов условной независимости: oracle d-separation, тест Fisher-Z, тест G²
  • Каждая установка запускается 100 раз с исключением 5 лучших и 5 худших результатов

Результаты экспериментов

Основные результаты

Вычислительная эффективность

Количество тестов условной независимости для LOAD постоянно ниже, чем для глобальных методов, немного выше, чем для локальных методов:

  • При 1000 узлах LOAD требует 9.43×10³ тестов, тогда как PC требует 542.52×10³
  • По сравнению с 5.64×10³ тестами MB-by-MB+, дополнительные затраты LOAD являются приемлемыми

Качество набора корректировки (оценка F1)

  • Установка Oracle: LOAD достигает идеальной F1=1.0, сравнимо с глобальными методами
  • Тест Fisher-Z: LOAD превосходит базовые методы на всех количествах узлов, оценка F1 составляет примерно 0.91-0.95
  • Тест G²: Производительность LOAD является второй лучшей, но все еще хороша

Расстояние вмешательства

LOAD достигает наименьшего расстояния вмешательства в большинстве установок:

  • Установка Oracle: 0.003 (сравнимо с PC, SNAP)
  • Тест Fisher-Z: 0.014-0.026 (лучший)
  • Тест G²: 0.022-0.036 (второй лучший, уступает только PC)

Результаты на реальных данных

На сети MAGIC-NIAB:

  • LOAD достигает лучшей оценки F1 (0.62)
  • Реализует наименьшее расстояние вмешательства (0.007)
  • Количество тестов условной независимости (4.35×10³) находится между локальными и глобальными методами

Абляционные эксперименты

  1. Известное отношение лечение-результат: Когда предоставляется фоновое знание, LOAD* превосходит PC на двоичных данных
  2. Идентифицируемые целевые пары: Когда гарантирована идентифицируемость причинного эффекта, закономерности результатов остаются последовательными
  3. Чувствительность параметров: LOAD демонстрирует устойчивость к различным размерам выборок и ожидаемым степеням

Связанные работы

Глобальные методы причинного обнаружения

  • Алгоритм PC: Классический метод на основе ограничений, но с высокой вычислительной сложностью
  • MARVEL: Рекурсивный метод, все еще сложно масштабируется на сотни переменных
  • SNAP: Прогрессивная идентификация и удаление определенных не-предков, но все еще требует причинного обнаружения на всех возможных предках

Локальные методы причинного обнаружения

  • MB-by-MB: Последовательное обнаружение одеял Маркова, но ограничено субоптимальными наборами корректировки
  • LDECC: Эффективная проверка коллайдеров, но с проблемами надежности и полноты
  • LDP: Обучение наборам корректировки через разбиение, но все еще может быть субоптимальным и иметь ограничения предположений

Преимущества данной работы

LOAD — первый метод, одновременно достигающий:

  1. Использование только локальной информации
  2. Восстановление оптимальных наборов корректировки
  3. Предоставление теоретических гарантий (надежность и полнота)

Заключение и обсуждение

Основные выводы

  1. LOAD успешно сочетает вычислительную эффективность локальных методов со статистической оптимальностью глобальных методов
  2. Предложенный локальный тест адаптации обеспечивает эффективный способ определения идентифицируемости причинного эффекта
  3. На различных типах данных и структурах сетей LOAD демонстрирует превосходную производительность

Ограничения

  1. Предположение о причинной достаточности: Текущая версия предполагает отсутствие скрытых смешивающих факторов или смещения отбора
  2. Вычислительные узкие места в крупномасштабных сетях: На очень больших графах поиск одеял Маркова все еще может стать вычислительным узким местом
  3. Производительность на двоичных данных: Ограниченная производительность при использовании теста G² на двоичных данных

Будущие направления

  1. Расширение на причинно недостаточные установки: Обработка случаев со скрытыми смешивающими факторами
  2. Оптимизация обнаружения одеял Маркова: Дальнейшее повышение вычислительной эффективности для крупномасштабных сетей
  3. Улучшение производительности на конечных выборках: Особенно на двоичных данных

Глубокая оценка

Преимущества

  1. Значительный теоретический вклад: Впервые предложен тест адаптации на основе только локальной информации, имеющий важное теоретическое значение
  2. Высокая практичность: Достижение статистической оптимальности при сохранении вычислительной эффективности решает ключевую проблему практических приложений
  3. Комплексные эксперименты: Охватывают различные типы данных, масштабы сетей и метрики оценки, результаты убедительны
  4. Полнота алгоритма: Предоставляет теоретические гарантии надежности и полноты, дизайн алгоритма строг

Недостатки

  1. Ограничения предположений: Предположение о причинной достаточности может не выполняться в практических приложениях
  2. Проблемы масштабируемости: Хотя лучше, чем глобальные методы, все еще имеет вычислительные вызовы на сверхбольших сетях
  3. Производительность на конечных выборках: Производительность недостаточно стабильна в некоторых установках конечных выборок

Влияние

  1. Академическая ценность: Предоставляет новую теоретическую базу и идеи проектирования алгоритмов для области причинного обнаружения
  2. Практическая ценность: Имеет важное значение в практических приложениях, требующих оценки причинного эффекта
  3. Воспроизводимость: Предоставляет подробные описания алгоритмов и экспериментальные установки, облегчающие воспроизведение и расширение

Применимые сценарии

  1. Причинный вывод среднего масштаба: Задачи оценки причинного эффекта с количеством переменных в диапазоне сотен-тысяч
  2. Сценарии с ограниченными вычислительными ресурсами: Приложения, требующие баланса между вычислительной эффективностью и статистической производительностью
  3. Причинно достаточная среда: Наблюдательные исследования без важных скрытых смешивающих факторов

Библиография

Статья цитирует важную литературу в области причинного вывода, включая:

  • Pearl (2009): Causality — классический учебник по причинному выводу
  • Spirtes et al. (2000): Фундаментальные работы по причинному обнаружению на основе ограничений
  • Henckel et al. (2022): Графические критерии для оптимальных наборов корректировки
  • Perković et al. (2015): Определение и свойства адаптации

Общая оценка: Это высококачественная статья по причинному выводу с важными вкладами как на теоретическом, так и на практическом уровнях. Алгоритм LOAD искусно решает компромисс между вычислительной эффективностью и статистической оптимальностью в причинном обнаружении, имея важное академическое значение и перспективы применения.